离散数学习题解

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

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

5

??(p?q) ???(p?q) (4) (p??q) ??(?p?q)

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

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

2.5. 求下列公式的主析取范式, 并求成真赋值: (1)( ?p?q) ??(?q?p) (2) ??(p?q) ?q?r

(3)(p??(q?r)) ??(p?q?r) (1)(?p?q) ??(?q?p) ???(p?q) ??(?q?p)

???p??q ???q ??p???p??q ???q ??p(吸收律)??(p??p)??q ??p?(q??q) ??p??q ??p??q ??p?q ??p??q ??m10 ??m00 ??m11 ??m10 ??m0 ??m2 ??m3 ???(0, 2, 3).

成真赋值为 00, 10, 11.

(2)主析取范式为 0, 无成真赋值, 为矛盾式. (3)m0?m1?m2?m3?m4?m5?m6?m7, 为重言式.

2.6. 求下列公式的主合取范式, 并求成假赋值: (1) ??(q??p) ??p (2)(p?q) ??(?p?r)

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

??M0?M1?M2?M3

这是矛盾式. 成假赋值为 00, 01, 10, 11. (2)M4, 成假赋值为 100. (3)主合取范式为 1, 为重言式.

离散数学习题解

2.7. 求下列公式的主析取范式, 再用主析取范式求合取范式: (1)(p?q) ?r

6

(2)(p?q) ??(q?r)

(1)m1?m3?m5?m6?m7?M0?M2?M4 (2)m0?m1?m3?m7?M2?M4?M5?M6

2.8. 略

2.9. 用真值表求下面公式的主析取范式.

(2) (p?q) ??(p??q)

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

(2)从真值表可见成真赋值为 01, 10. 于是(p ??q) ??(p????q) ??m1 ??m2.

2.10. 略 2.11. 略 2.12. 略 2.13. 略 2.14. 略

2.15. 用主析取范式判断下列公式是否等值: (1)

(p?q) ?r 与 q??(p?r)

(2)(p?q) ?r ???(?p?q) ??r ???(?p?q) ??r ??p??q ??r

??p??q?(r??r) ??(p??p) ??(q??q)?r ??p??q?r ??p??q??r ??

p?q?r ??p??q?r ???p?q?r ???p??q?r = m101 ??m100 ??m111 ??m101 ??m011 ??m001 ??m1 ??m3 ??m4 ??m5 ??m7 = ?(1, 3, 4, 5, 7). 而 q?(p?r) ???q ??(?p?r) ???q ???p ?r

??(?p?p)??q?(?r?r) ???p?(?q?q)?(?r?r) ??(?p?p)?(?q?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)?(p?q?r) = m0 ??m1 ??m4 ??m5 ??m0 ??m1 ??m2 ??m3 ??m1 ??m3 ??m5 ??m7

???m0 ??m1 ??m2 ??m3 ??m4 ??m5 ??m7 ???(0, 1, 2, 3, 4, 5, 7).

两个公式的主吸取范式不同, 所以(p?q) ?r? q??(p?r).

7

2.16. 用主析取范式判断下列公式是否等值: (1)(p?q) ?r 与 q??(p?r) (2) ??(p?q)与??(p?q)

(1)

(p?q) ?r) ?m1?m3?m4?m5?m7

q??(p?r) ?m0?m1?m2?m3?m4?m5?m7 所以(p?q) ?r) ? q??(p?r) (2)

??(p?q) ?m0?m1?m2 ??(p?q) ?m0

所以??(p?q) ? ??(p?q)

2.17. 用主合取范式判断下列公式是否等值: (1)p??(q?r)与??(p?q) ?r (2)p??(q?r)与(p?q) ?r

(1)

p??(q?r) ?M6 ??(p?q) ?r?M6

所以 p??(q?r) ????(p?q) ?r (2)

p??(q?r) ?M6

(p?q) ?r?M0?M1?M2?M6 所以 p??(q?r) ? (p?q) ?r

2.18. 略 2.19. 略

2.20.将下列公式化成与之等值且仅含 {?, ?} 中联结词的公式.

(3) (p?q)?r.

注意到 A?B ??(A?B)?(B?A)和 A?B ???(?A??B) ???(A??B)以及 A?B ???A?B. (p?q)?r

离散数学习题解

??(p?q ??r) ??(r ??p?q) ??(?(p??q) ??r) ??(r ???(p??q)) ???((?(p??q) ??r) ???(r ???(p??q))) 注?联结词越少, 公式越长.

8

2.21. 证明:

(1) (p?q) ??(q?p), (p?q) ??(q?p). (p?q) ???(p?q) ???(q?p) ??(q?p).

(p?q) ???(p?q) ???(q?p) ??(q?p). 2.22. 略 2.23. 略 2.24. 略

2.25. 设 A, B, C 为任意的命题公式.

(1)若 A?C?B?C, 举例说明 A?B 不一定成立. (2)已知 A?C?B?C, 举例说明 A?B 不一定成立. (3)已知?A??B, 问: A?B 一定成立吗?

(1) 取 A = p, B = q, C = 1 (重言式), 有

A?C ??B?C, 但 A ? B. (2) 取 A = p, B = q, C = 0 (矛盾式), 有

A?C ??B?C, 但 A ? B.

好的例子是简单, 具体, 而又说明问题的. (3)一定.

2.26. 略

2.27.某电路中有一个灯泡和三个开关 A,B,C. 已知在且仅在下述四种情况下灯亮: (1)C 的扳键向上, A,B 的扳键向下. (2)A 的扳键向上, B,C 的扳键向下. (3)B,C 的扳键向上, A 的扳键向下. (4)A,B 的扳键向上, C 的扳键向下.

设 F 为 1 表示灯亮, p,q,r 分别表示 A,B,C 的扳键向上. (a)求 F 的主析取范式.

(b)在联结词完备集{?, ?}上构造 F. (c)在联结词完备集{?, ?,?}上构造 F.

(a)由条件(1)-(4)可知, F 的主析取范式为 F??(?p??q?r) ??(p??q??r) ??(?p?q?r) ??(p?q??r) ?m1?m4?m3?m6 ?m1?m3?m4?m6