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

第1章 习题解答

⑵ p→(q∨r) 的真值表如表1.25所示。

表1.25

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

使得公式p→(q∨r)成真的赋值是：000，001，010，011，101，110，111，使得公式p→(q∨r)成假的赋值是：100。

⑶ (p∨q)?(q∨p) 的真值表如表1.26所示。

表1.26

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

所有的赋值均使得公式(p∨q)?(q∨p)成真，即(p∨q)?(q∨p)是一个永真式。 ⑷ (p∧?q)∨(r∧q)→r的真值表如表1.27所示。

表1.27

p 0 0 0 0 1 1 1 q 0 0 1 1 0 0 1 r 0 1 0 1 0 1 0 ?q 1 1 0 0 1 1 0 p∧?q 0 0 0 0 1 1 0 r∧q 0 0 0 1 0 0 0 (p∧?q)∨(r∧q)?0 0 0 1 1 1 0 (p∧?q)∨(r∧q)→r 1 1 1 1 0 1 1 1 1 1 0 0 1 1 1 使得公式(p∧?q)∨(r∧q)→r成真的赋值是：000，001，010，011，101，110，111，

6

第1章 习题解答

使得公式(p∧?q)∨(r∧q)→r成假的赋值是：100。

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

表1.28

p 0 0 0 0 1 1 1 1 q 0 0 1 1 0 0 1 1 r p∧?q ?p→(p∧?q) (?p→(p∧?q))→r 0 1 0 1 0 1 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 1 0 1 q∧?r ((?p→(p∧?q))→r)∨(q∧?r) 0 0 1 0 0 0 1 0 1 1 1 1 0 1 1 1 使得公式((?p→(p∧?q))→r)∨(q∧?r)成真的赋值是：000，001，010，011，101，110，111，使得公式((?p→(p∧?q))→r)∨(q∧?r)成假的赋值是：100。

4.用真值表证明下列等价式： ⑴?(p→q)?p∧?q

证明：证明?(p→q)?p∧?q的真值表如表1.29所示。

表1.29

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

由上表可见：?(p→q)和p∧?q的真值表完全相同，所以?(p→q)?p∧?q。 ⑵p→q??q→?p

证明：证明p→q??q→?p的真值表如表1.30所示。

表1.30

p 0 0 1 1 q p→q 0 1 0 1 1 1 0 1 ?p?1 1 0 0 ?q?1 0 1 0 ?q→?p?1 1 0 1 由上表可见：p→q和?q→?p的真值表完全相同，所以p→q??q→?p。

7

第1章 习题解答

⑶?(p?q)?p??q

证明：证明?(p?q)和p??q的真值表如表1.31所示。

表1.31

p 0 0 1 1 q p?q ?(p?q)??q?0 1 0 1 1 0 0 1 0 1 1 0 1 0 1 0 p??q?0 1 1 0

由上表可见：?(p?q)和p??q的真值表完全相同，所以?(p?q)?p??q。 ⑷p→(q→r)?(p∧q)→r

证明：证明p→(q→r)和(p∧q)→r的真值表如表1.32所示。

表1.32

p 0 0 0 0 1 1 1 1 q 0 r 0 q→r?p→(q→r)?p∧q?(p∧q)→r?1 1 0 1 1 1 0 1 1 1 1 1 1 1 0 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 1 0 1 1 1 0 0 0 1 0 1 1 0 1 1 由上表可见：p→(q→r)和(p∧q)→r的真值表完全相同，所以p→(q→r)?(p∧q)→r。 ⑸p→(q→p)???p→(p→?q)

证明：证明p→(q→p)和?p→(p→?q)的真值表如表1.33所示。

表1.33

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

由上表可见：p→(q→p)和?p→(p→?q)的真值表完全相同，且都是永真式，所以p→(q→p)??p→(p→?q)。

⑹?(p?q)?(p∨q)∧?(p∧q)

8

第1章 习题解答

证明：证明?(p?q)和(p∨q)∧?(p∧q)的真值表如表1.34所示。

表1.34

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

由上表可见：?(p?q)和(p∨q)∧?(p∧q)的真值表完全相同，所以?(p?q)?(p∨q)∧?(p∧q)

⑺?(p?q)?(p∧?q)∨(?p∧q)

证明：证明?(p?q)和(p∧?q)∨(?p∧q)的真值表如表1.35所示。

表1.35

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

由上表可见：?(p?q)和(p∧?q)∨(?p∧q)的真值表完全相同，所以?(p?q)?(p∧?q)∨(?p∧q)。

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

证明：证明p→(q∨r)和(p∧?q)→r的真值表如表1.36所示。

表1.36

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

由上表可见：p→(q∨r)和(p∧?q)→r的真值表完全相同，所以p→(q∨r)?(p∧?q)→r。

9

第1章 习题解答

5. 用等价演算证明习题4中的等价式。 ⑴?(p→q) ??(?p∨q) ?p∧?q ⑵?q→?p ???q∨?p ?q∨?p ??p∨q ? p→q ⑶?(p?q)

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

?((p∧?q)∨q)∧((p∧?q)∨?p) ?(p∨q)∧(?q∨?p) ?(?p∨?q)∧(q∨p) ?(p→?q)∧(?q→p) ?p??q ⑷p→(q→r) ??p∨(?q∨r) ?(?p∨?q)∨r ??(p∧q)∨r ?(p∧q)→r ⑸p→(q→p) ??p∨(?q∨p) ?T

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

?T

所以p→(q→p)???p→(p→?q) ⑹?(p?q)

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

所以?(p?q)?(p∨q)∧?(p∧q) ⑺?(p?q)

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

(条件等价式) (德·摩根律) (条件等价式) (双重否定律) (交换律)

(条件等价式) (双条件等价式) (条件等价式) (德·摩根律) (分配律) (分配律) (交换律) (条件等价式) (双条件等价式) (条件等价式) (结合律)

(德·摩根律) (条件等价式) (条件等价式)?

(条件等价式)?

(例1.17) (德·摩根律) (德·摩根律)

(双条件等价式) (条件等价式) (德·摩根律)

10