第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