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

第1章 习题解答

⑻p→(q∨r) ??p∨(q∨r) (条件等价式) ?(?p∨q)∨r (结合律) ??(p∧?q)∨r (德·摩根律) ?(p∧?q)→r (条件等价式)

6.试用真值表证明下列命题定律。

⑴结合律：(p∨q)∨r?p∨(q∨r)，(p∧q)∧r?p∧(q∧r) 证明：证明结合律的真值表如表1.37和表1.38所示。

表1.37

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

表1.38

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?(p∧q)∧r?q∧r?p∧(q∧r)?0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1

由真值表可知结合律成立。

⑵分配律：p∧(q∨r)?(p∧q)∨(p∧r)，

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

证明：证明合取对析取的分配律的真值表如表1.39所示，析取对合取的的分配律的真值表如表1.40所示。

11

第1章 习题解答

表1.39

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

表1.40

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 q∧r?0 0 0 1 0 0 0 1 p∨(q∧r)?0 0 0 1 1 1 1 1 p∨q?0 0 1 1 1 1 1 1 p∨r?0 1 0 1 1 1 1 1 (p∨q)∧(p∨r)?0 0 0 1 1 1 1 1

由真值表可知分配律成立。 ⑶假言易位式：p→q??q→?p

证明：证明假言易位式的真值表如表1.41所示。

表1.41

p 0 0 1 1 q 0 1 0 1 p→q 1 1 0 1 ?q?1 0 1 0 ?p?1 1 0 0 ?q→?p?1 1 0 1

由真值表可知假言易位律成立。

⑷双条件否定等价式：p?q??p??q

证明：证明双条件否定的真值表如表1.42所示。

12

第1章 习题解答

表1.42

p 0 0 1 1 q 0 1 0 1 p?q 1 0 0 1 ?p?1 1 0 0 ?q?1 0 1 0 ?p??q?1 0 0 1

由真值表可知双条件否定等价式成立。

13

第1章 习题解答

习题 1.4

1.用真值表或等价演算判断下列命题公式的类型。 ⑴(p∨?q)→q ??(p∨?q)∨q ?(?p∧q)∨q

?q （可满足式） ⑵?(p→q)∧q ??(?p∨q)∧q ?(p∧?q)∧q ?F（永假式） ⑶(p→q)∧p→q ?(?p∨q)∧p→q

?(?p∧p)∨(q∧p)→q ?(q∧p)→q ??(q∧p)∨q ?(?q∨?p)∨q ?T(永真式) ⑷(p→q)∧q ?(?p∨q)∧q ?q（可满足式） ⑸(p→q)→(?q→?p) ?(p→q)→(p→q) ?T(永真式)

⑹((p→q)∧(q→r))→(p→r)

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

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

?(?p∨q∨r∨p)∧(?p∨q∨r∨?q) ?T(永真式) ⑺?p→(p→q) ? p∨(?p∨q) ?T(永真式) ⑻p→(p∨q∨r) ??p∨(p∨q∨r) ?T(永真式)

2.用真值表证明下列命题公式是重言式。

14

（条件等价式） （德·摩根律） （吸收律） （条件等价式） （德·摩根律） （结合律、矛盾律） （条件等价式） （分配律）

（同一律、矛盾律） （条件等价式） （德·摩根律） （零律、排中律） （条件等价式） （吸收律） （假言易位式）

（条件等价式） （德·摩根律） （分配律）

（同一律、排中律、零律）（分配律）

（条件等价式）

（条件等价式）

第1章 习题解答

⑴(p∧(p→q))→q

(p∧(p→q))→q的真值表如表1.43所示。由表1.43可以看出(p∧(p→q))→q是重言式。

表1.43

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

⑵(?q∧(p→q))→?p

(?q∧(p→q))→?p的真值表如表1.44所示。由表1.44可以看出(?q∧(p→q))→?p是重言式。

表1.44

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

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

(?p∧(p∨q))→q的真值表如表1.45所示。由表1.45可以看出(?p∧(p∨q))→q是重言式。

表1.45

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

⑷((p→q)∧(q→r))→(p→r)

((p→q)∧(q→r))→(p→r)的真值表如表1.46所示。由表1.46可以看出((p→q)∧(q→r))→(p→r)是重言式。

15