离散数学习题解
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
离散数学习题解
(b)先化简公式
F??(?p??q?r) ??(p??q??r) ??(?p?q?r) ??(p?q??r) ??q??((?p?r) ??(p??r)) ?q??((?p?r) ??(p??r)) ??(?q?q) ??((?p?r) ??(p??r)) ??(?p?r) ??(p??r)
???(??(?p?r) ???(p??r)) (已为{?, ?}中公式) (c) F??(?p?r) ??(p??r) ????(?p?r) ??(p??r) ???(?p?r) ??(p??r) ??(p??r) ???(?p?r) ??(r?p) ???(p?r) (已为{?, ?,?}中公式)
9
2.28.一个排队线路, 输入为 A,B,C, 其输出分别为 FA,FB,FC. 本线路中, 在同一时间内只能有一个信号通过, 若同
时有两个和两个以上信号申请输出时, 则按 A,B,C 的顺序输出. 写出 FA,FB,FC 在联结词完备集{?, ?} 中的表达式.
根据题目中的要求, 先写出 FA,FB,FC 的真值表(自己写) 由真值表可先求出他们的主析取范式, 然后化成{?, ?}中的公式 FA?m4?m5?m6?m7 ?p FB?m2?m3 ??p?q FC?m1 ??p??q?r
(已为{?, ?}中公式)
(已为{?, ?}中公式)
(已为{?, ?}中公式)
2.29. 略 2.30. 略
离散数学习题解 10
习题三
3.1. 略 3.2. 略 3.3. 略 3.4. 略 3.5. 略
3.6. 判断下面推理是否正确. 先将简单命题符号化, 再写出前提, 结论, 推理的形式结构(以蕴涵式的形式给
出)和判断过程(至少给出两种判断方法):
(1)若今天是星期一, 则明天是星期三；今天是星期一. 所以明天是星期三. (2)若今天是星期一, 则明天是星期二；明天是星期二. 所以今天是星期一. (3)若今天是星期一, 则明天是星期三；明天不是星期三. 所以今天不是星期一. (4)若今天是星期一, 则明天是星期二；今天不是星期一. 所以明天不是星期二. (5)若今天是星期一, 则明天是星期二或星期三. (6)今天是星期一当且仅当明天是星期三；今天不是星期一. 所以明天不是星期三.
设 p: 今天是星期一, q: 明天是星期二, r: 明天是星期三. (1)推理的形式结构为 (p?r) ?p?r
此形式结构为重言式, 即 (p?r) ?p?r 所以推理正确. (2)推理的形式结构为
(p?q) ?q?p 此形式结构不是重言式, 故推理不正确. (3)推理形式结构为 (p?r) ??r??p 此形式结构为重言式, 即 (p?r) ??r??p 故推理正确. (4)推理形式结构为
(p?q) ??p??q 此形式结构不是重言式, 故推理不正确. (5)推理形式结构为 p??(q?r)
它不是重言式, 故推理不正确. (6)推理形式结构为 (p?r) ??p??r