离散数学屈婉玲版课后答案.doc

1、3习题一 1.1 略 1.2 略 1.3 略 1.4 略 1.5 略 1.6 略 1.7 略 1.8 略 1.9 略 1.10 1.11 1.12 略 略 将下列 命题符号化, 并给出各命题的 真值: (1)2+24当且仅当3+3 6. (2)2+24的充要条件是3+3 6. (3)2+24与3+36互为充要条件. (4)若2+24, 则3+36, 反之亦然. (1)pq, 其中, p: 2+2 4, q: 3+3 6, 真值为1. (2)pq, 其中, p: 2+2 4, q: 3+36, 真值为0. (3) pq, 其中, p: 2+2 4, q: 3+36, 真值为0. (4) pq,

2、其中, p: 2+24, q: 3+36, 真值为1. 将下列命题符号化, 并给出各命题的真值: (1)若今天是星期一, 则明天是星期二. (2)只有今天是星期一, 明天才是星期二. (3)今天是星期一当且仅当明天是星期二. (4)若今天是星期一, 则明天是星期三. 令 p: 今天是星期一; q: 明天是星期二; r: 明天是星期三. (1) pq 1. (2) qp 1. (3) pq 1. (4) pr当 p 0时为真; p 1 时为假 . 将下列 命题符号化. (1) 刘晓月跑得快, 跳得高. (2)老王是山东人或河北人. (3)因为天气冷, 所以我穿了羽绒服. (4)王欢与李乐组成一个

3、小组. (5)李辛与李末是兄弟. (6)王强与刘威都学过法语. (7)他一面吃饭, 一面听音乐. (8)如果天下大雨, 他就乘班车上班. (9)只有天下大雨, 他才乘班车上班. (10)除非天下大雨, 他才乘班车上班. (11)下雪路滑, 他迟到了. (12)2与4都是素数, 这是不对的. (13)“2或4是素数, 这是不对的”是不对的 . 4 (1)pq, 其中, p: 刘晓月跑得快, q : 刘晓月跳得高. (2)pq, 其中, p: 老王是山东人, q : 老王是河北人. (3)pq, 其中, p: 天气冷, q: 我穿了羽绒服. (4)p, 其中, p: 王欢与李乐组成一个小组, 是简

4、单命题. (5)p, 其中, p: 李辛与李末是兄弟. (6)pq, 其中, p: 王强学过法语, q : 刘威学过法语. (7)pq, 其中, p: 他吃饭, q: 他听音乐 . (8)pq, 其中, p: 天下大雨, q: 他乘班车上班. (9)pq, 其中, p: 他乘班车上班, q: 天下大雨. (10)pq, 其中, p: 他乘班车上班, q: 天下大雨. (11)pq, 其中, p: 下雪路滑, q: 他迟到了. (12) (pq)或p q, 其中, p: 2是素数, q: 4是素数. (13) (pq)或p q, 其中, p: 2是素数, q: 4是素数. 设p: 2+3=5.

5、q: 大熊猫产在中国. r: 复旦大学在广州. 求下列复合命题的真值: (1)(pq) r (2)(r(p q) p (3) r(p qr) (4)(pqr) ( p q) r) (1)真值为0. (2)真值为0. (3)真值为0. (4)真值为1. 注意: p, q是真命题, r是假命题. 1.16 1.17 1.18 1.19 略 略 略 用真值表判断下列公式的类型: (1)p(p qr) (2)(p q) q (3) (qr) r (4)(pq) (q p) (5)(pr) ( pq) (6)(pq) (qr) ( pr ) (7)(pq) (rs) 5 (1), (4), (6)为重言

6、式 . (3)为矛盾式. (2), (5), (7)为可满足式 . 1.20 1.21 1.22 1.23 1.24 1.25 1.26 1.27 1.28 1.29 1.30 1.31 略 略 略 略 略 略 略 略 略 略 略 将下列 命题符号化, 并给出各命题的 真值: (1)若3+4, 则地球是静止不动的. (2)若3+24, 则地球是运动不止的. (3)若地球上没有树木, 则人类不能生存. (4)若地球上没有水, 则3是无理数. (1)pq, 其中, p: 2+2 4, q: 地球静止不动, 真值为0. (2)pq, 其中, p: 2+2 4, q: 地球运动不止, 真值为1. (3

7、) pq, 其中, p: 地球上有树木, q: 人类能生存, 真值为1. (4) pq, 其中, p: 地球上有水, q: 3是无理数, 真值为1. p q r 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 6 习题二 2.1. 设公式 A = pq, B = pq, 用真值表验证公式 A 和 B 适合德摩根律 : (AB) AB. A =pq B =pq (AB) AB0 0 1 1 0 1 0 1 1 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 因为(A B)和A B的真值表相同 , 所以它们等值. 2.2. 略 2.3.

8、用等值演算法判断下列公式的类型, 对不是重言式的可满足式, 再用真值表法求出成真赋值. (1) (pqq) (2)(p(p q) (pr) (3)(pq) ( pr) (1) (pqq)(pq) q) (p q q) pqq p0 0 0. 矛盾式. (2)重言式. (3) (pq) ( pr) (pq) (pr) pq pr易见, 是可满足式 , 但不是重言式. 成真赋值为: 000, 001, 101, 111 p q pr1 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 0 1 0 1 0 0 0 0 0 1 0 1 2.4.

9、 用等值演算法证明下面等值式: (1) p(pq) (pq) (3) (pq) (pq) (pq) (4) (pq) (pq) (pq) (pq) (1) (pq) (pq) p (qq) p 1 p. (3) (pq) 7 (pq) (qp) (pq) (qp) (pq) (qp) (pq) (pp) (qq) (pq) (pq) (pq) (4) (pq) (pq) (pp) (pq) (qp) (qq) (pq) (pq) 2.5. 求下列公式的主析取范式, 并求成真赋值: (1)( pq) (qp) (2) (pq) qr (3)(p(qr) (pq r) (1)(pq) (qp) (

10、pq) (qp) pq q ppq q p(吸收律) (pp)q p(qq) pq pq pq pq m10 m00 m11 m10 m0 m2 m3 (0, 2, 3). 成真赋值为 00, 10, 11. (2)主析取范式为0, 无成真赋值, 为矛盾式. (3)m0m1m2m3m4m5m6m7 , 为重言式. 2.6. 求下列公式的主合取范式, 并求成假赋值: (1) (q p) p (2)(pq) (pr) (3)(p(p q) r (1) (qp) p (qp) p qp p q0 0 M0M1M2M3 这是矛盾式. 成假赋值为 00, 01, 10, 11. (2)M4 , 成假赋值

11、为100. (3)主合取范式为1, 为重言式. p q ( p q ) ( p q ) 0 0 0 1 1 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 0 82.7. 求下列公式的主析取范式, 再用主析取范式求合取范式: (1)(pq) r (2)(pq) (qr) (1)m1m3m5m6m7M0M2M4 (2)m0m1m3m7M2M4M5M6 2.8. 略 2.9. 用真值表求下面公式的主析取范式. (2) (pq ) (pq) (2)从真值表可见成真赋值为01, 10. 于是(p q) (pq) m1 m2 . 2.10. 略 2.11. 略 2.12. 略 2

12、.13. 略 2.14. 略 2.15. 用主析取范式判断下列公式是否等值: (1) (pq ) r 与q (pr) (2)(pq) r (pq) r (pq) r pq r pq(rr) (pp) (qq)r pqr pqr pqr pqr pqr pqr = m101 m100 m111 m101 m011 m001 m1 m3 m4 m5 m7 = (1, 3, 4, 5, 7). 而 q(pr) q (pr) q p r (pp)q(rr) p(qq)(rr) (pp)(qq)r (pqr)(pqr)(pqr)(pqr) (pqr)(pqr)(pqr)(pqr) 9(pqr)(pqr)

13、(pqr)(pqr) = 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). 两个公式的主吸取范式不同, 所以(pq) r2.16. 用主析取范式判断下列公式是否等值: (1)(pq) r 与q (pr) (2) (pq)与(pq) (1) (pq) r) m1m3 m4m5m7 q(pr) m0m1m2m3m4m5m7 所以(pq) r) q(pr) (2) (pq) m0m1m2 (pq) m0 所以( pq) (pq) 2.17. 用主合取范式判断下列公式是否等值: (1)p(q

14、r)与( pq) r (2)p(q r)与( pq) r (1) p(qr) M6 (pq) rM6 所以p(qr) (pq) r (2) p(qr) M6 (pq) r M0M1M2M6 所以p(qr) (pq) r 2.18. 略 2.19. 略 q(pr). 2.20. 将下列公式化成与之等值且仅含 , 中联结词的公式. (3) (pq)r. 注意到AB (AB)(BA )和 AB (AB) (AB)以及 AB AB . (pq)r 10(pq r) (r pq) (pq) r) (r (pq) (pq) r) (r (pq) 注联结词越少, 公式越长. 2.21. 证明: (1) (p

15、q) (qp), (pq) (qp). (pq) (pq) (qp) (qp). (pq) (pq) (qp) (qp). 2.22. 略 2.23. 略 2.24. 略 2.25. 设A, B , C为任意的命题公式. (1)若AC BC, 举例说明 AB不一定成立. (2)已知A CBC, 举例说明AB不一定成立. (3)已知A B, 问: AB 一定成立吗? (1) 取 A = p, B = q, C = 1 (重言式), 有 AC BC, 但 A B. (2) 取 A = p, B = q, C = 0 (矛盾式), 有 AC BC, 但 A B. 好的例子是简单, 具体, 而又说明问

16、题的. (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(pqr) (pqr) (pqr) (pqr) m1m4m3m6 m1m3m4m6

17、 11 (b)先化简公式 F(pqr) (pqr) (pqr) (pqr) q(pr) (pr) q(pr) (pr) (qq) (pr) (pr) (pr) (pr) (pr) (pr) (已为, 中公式) (c) F(pr) (pr) (pr) (pr) (pr) (p r) (pr) ( pr) (rp) ( pr) (已为 , ,中公式 ) 2.28. 一个排队线路, 输入为A,B,C , 其输出分别为F A ,F B,F C. 本线路中, 在同一时间内只能有一个信号通过, 若同时有两个和两个以上信号申请输出时, 则按A,B,C 的顺序输出. 写出F A,F B,F C在联结词完备集

18、, 中的表达式. 根据题目中的要求, 先写出F A,F B,F C的真值表(自己写) 由真值表可先求出他们的主析取范式, 然后化成, 中的公式 F Am4m5m6m7 p F Bm2m3 pq F Cm1 pqr 2.29. 略 2.30. 略 (已为 , 中公式 ) (已为 , 中公式 ) (已为 , 中公式 ) 12 习题三 3.1. 略 3.2. 略 3.3. 略 3.4. 略 3.5. 略 3.6. 判断下面推理是否正确. 先将简单命题符号化, 再写出前提, 结论, 推理的形式结构(以蕴涵式的形式给 出)和判断过程( 至少给出两种判断方法): (1)若今天是星期一, 则明天是星期三；今

19、天是星期一. 所以明天是星期三 . (2)若今天是星期一, 则明天是星期二；明天是星期二. 所以今天是星期一 . (3)若今天是星期一, 则明天是星期三；明天不是星期三. 所以今天不是星期一 . (4)若今天是星期一, 则明天是星期二；今天不是星期一. 所以明天不是星期二 . (5)若今天是星期一, 则明天是星期二或星期三. (6)今天是星期一当且仅当明天是星期三；今天不是星期一. 所以明天不是星期三 . 设p: 今天是星期一, q: 明天是星期二, r: 明天是星期三. (1)推理的形式结构为 (pr) pr 此形式结构为重言式, 即 (pr) pr 所以推理正确. (2)推理的形式结构为 (pq) qp 此形式结构不是重言式, 故推理不正确. (3)推理形式结构为 (pr) rp 此形式结构为重言式, 即 (pr) rp 故推理正确. (4)推理形式结构为 (pq) pq 此形式结构不是重言式, 故推理不正确. (5)推理形式结构为 p(qr) 它不是重言式, 故推理不正确. (6)推理形式结构为 (pr) pr