第1章 离散数学习题解答(7)

第1章 习题解答

r为假；所以，q必为真；

因为q为真，r为假，所以q→r 必为假；因为p为真，所以，p→(q→r)必为假。 所以，原蕴含式成立。 ⑸p∧(p→q)?q

证明：假设前件p∧(p→q)为真，证明后件q也为真。因为p∧(p→q)为真，所以p为真，p→q也为真，根据条件的定义q必为真。

所以，原蕴含式成立。 ⑹?q∧(p→q)??p

证明：假设前件?q∧(p→q)为真，证明后件?p也为真。

因为?q∧(p→q)为真，所以，?q为真，q为假，又因为p→q为真，根据条件的定义p为假，所以?p必为真。

所以，原蕴含式成立。

5.设A是任意的命题公式，证明A?A

证明：由条件的定义可知：A→A是一个永真式；根据蕴含式的定义可知A?A。

31

第1章 习题解答

习题 1.8

1.用全真值表或部分真值表证明下列各题的有效结论。 ⑴(p→(q→r))，p∧q?r

((p→(q→r))∧(p∧q))→r的全真值表如表1.56所示。

表1.56

p q 0 0 0 0 0 1 0 1 1 0 1 0 1 1 1 1 r 0 1 0 1 0 1 0 1 q→r 1 1 0 1 1 1 0 1 p→(q→r) p∧q (p→(q→r))∧(p∧q) ((p→(q→r))∧(p∧q))→r 1 1 1 1 1 1 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1

由真值表可知，((p→(q→r))∧(p∧q))→r是永真式，所以(p→(q→r))，p∧q?r。 ⑵?p∨q,?(q∧?r),?r??p

((?p∨q)∧(?(q∧?r))∧?r)→?p的全真值表如表1.57所示。

表1.57

p 0 0 0 0 1 1 1 1 q 0 0 1 1 0 0 1 1 r ?p∨q ?r ?(q∧?r) (?p∨q)∧(?(q∧?r))∧?r ((?p∨q)∧(?(q∧?r))∧?r)→?p 0 1 0 1 0 1 0 1 1 1 1 1 0 0 1 1 1 0 1 0 1 0 1 0 1 1 0 1 1 1 0 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

由真值表可知：((?p∨q)∧(?(q∧?r))∧?r)→?p是永真式，所以?p∨q，?(q∧?r)，?r??p。

⑶?p∨q,r→?q?p→?r

((?p∨q)∧(r→?q))→(p→?r)的真值表如表1.58所示。

32

第1章 习题解答

表1.58

p 0 0 0 0 1 1 1 1 q 0 0 1 1 0 0 1 1 r 0 1 0 1 0 1 0 1 ?p∨q r→?q p→?r (?p∨q)∧(r→?q) ((?p∨q)∧(r→?q))→(p→?r) 1 1 1 1 0 0 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 0 1 0 1 1 1 0 0 0 1 0 1 1 1 1 1 1 1 1 由真值表可知：((?p∨q)∧(r→?q))→(p→?r)是永真式，所以?p∨q,r→?q?p→?r。 ⑷p→q，q→r?p→r

((p→q)∧(q→r))→(p→r)的真值表如表1.59所示。

表1.59

p 0 0 0 0 1 1 1 1 q 0 0 1 1 0 0 1 1 r 0 1 0 1 0 1 0 1 p→q 1 1 1 1 0 0 1 1 q→r 1 1 0 1 1 1 0 1 p→r 1 1 1 1 0 1 0 1 (p→q)∧(q→r) 1 1 0 1 0 0 0 1 ((p→q)∧(q→r))→(p→r) 1 1 1 1 1 1 1 1 由真值表可知：((p→q)∧(q→r))→(p→r)是永真式，所以p→q，q→r?p→r。 ⑸p∨?p,p→q,?p→q?q

((p∨?p)∧(p→q)∧(?p→q))→q的真值表如表1.60所示。

表1.60

p 0 0 0 0 1 1 1 1 q 0 0 1 1 0 0 1 1 r p∨?p p→q ?p→q (p∨?p)∧(p→q)∧(?p→q) ((p∨?p)∧(p→q)∧(?p→q))→q 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 0 0 1 1 1 1 1 1 0 0 1 1 0 0 1 1 1 1 1 1 1 1 1 1 由真值表可知：((p∨?p)∧(p→q)∧(?p→q))→q是永真式，所以p∨?p,p→q,?p→

33

第1章 习题解答

q?q。

⑹p?q，q?r?p?r

((p?q)∧(q?r))→(p?r)的真值表如表1.61所示。

表1.61

p q 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 r 0 1 0 1 0 1 0 1 p?q 1 1 0 0 0 0 1 1 q?r 1 0 0 1 1 0 0 1 p?r 1 0 1 0 0 1 0 1 (p?q)∧(q?r) ((p?q)∧(q?r))→(p?r) 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1

由真值表可知：((p?q)∧(q?r))→(p?r)是永真式，所以p?q，q?r?p?r。 2.用等价演算法，主析取范式法或蕴含演算法证明上题中的各有效结论。 ⑴(p→(q→r)),p∧q?r ((p→(q→r))∧(p∧q))→r

??((p→(q→r))∧(p∧q))∨r ??((?p∨?q∨r)∧(p∧q))∨r ?(p∧q∧?r)∨?(p∧q)∨r ?(p∧q∧?r)∨?(p∧q∧?r) ?1

所以(p→(q→r)),p∧q?r ⑵?p∨q,?(q∧?r),?r??p

((?p∨q)∧(?(q∧?r))∧?r)→?p

??((?p∨q)∧(?(q∧?r))∧?r)∨?p ?((p∧?q)∨(q∧?r)∨r)∨?p ?(p∧?q)∨(q∧?r)∨r∨?p ?((p∧?q)∨?p)∨((q∧?r)∨r) ?(?p∨?q)∨(q∨r) ?1

所以?p∨q,?(q∧?r),?r??p ⑶?p∨q,r→?q?p→?r ((?p∨q)∧(r→?q))→(p→?r)

?((?p∨q)∧(?r∨?q))→(?p∨?r) ??((?p∨q)∧(?r∨?q))∨(?p∨?r) ?((p∧?q)∨(r∧q))∨(?p∨?r)

34

第1章 习题解答

?((p∧?q)∨?p)∨((r∧q)∨?r) ?(?p∨?q)∨(q∨?r)

?1

所以?p∨q,r→?q?p→?r ⑷p→q，q→r?p→r ((p→q)∧(q→r))→(p→r)

?((?p∨q)∧(?q∨r))→(?p∨r) ??((?p∨q)∧(?q∨r))∨(?p∨r) ?(p∧?q)∨(?r∧q)∨?p∨r ?((p∧?q)∨?p)∨((?r∧q)∨r) ?(?p∨?q)∨(q∨r) ?1

所以p→q，q→r?p→r ⑸p∨?p,p→q,?p→q?q

((p∨?p)∧(p→q)∧(?p→q))→q

?(1∧(?p∨q)∧(p∨q))→q ??((?p∨q)∧(p∨q))∨q ?(p∧?q)∨(?p∧?q)∨q ??q∨q ?1

所以p∨?p,p→q,?p→q?q ⑹p?q，q?r?p?r ((p?q)∧(q?r))→(p?r)

?((?p∨q)∧(?q∨p)∧(?q∨r)∧(?r∨q))→(p?r)

??((?p∨q)∧(?q∨p)∧(?q∨r)∧(?r∨q))∨(p∧r)∨(?p∧?r) ?(p∧?q)∨(p∧r)∨(r∧?q)∨(q∧?r)∨(q∧?p)∨(?p∧?r) ?((p∧(?q∨r))∨?(?q∨r))∨(r∧?q)∨(q∧?p)∨(?p∧?r)

?((?(?q∨r)∨(?q∨r))∧(p∨?(?q∨r)))∨(r∧?q)∨(q∧?p)∨(?p∧?r) ?(T∧(p∨?(?q∨r)))∨(r∧?q)∨(q∧?p)∨(?p∧?r) ?p∨(q∧?r)∨(r∧?q)∨(q∧?p)∨(?p∧?r) ?p∨(q∧?r)∨((q∧?p)∨(?p∧?r))∨(r∧?q) ?p∨(q∧?r)∨((?p∧(q∨?r))∨?(q∨?r)) ?p∨(q∧?r)∨?p∨(?q∧r) ?T

所以p?q，q?r?p?r

3.推理证明下列各题的有效结论。 ⑴p→(q∨r)，(t∨s)→p，(t∨s)?q∨r 证明：

⑴t∨s

P

35