离散数学课后答案.doc

1、离散数学课后答案习题一6.将下列命题符号化。（1）小丽只能从框里那一个苹果或一个梨.（2）这学期，刘晓月只能选学英语或日语中的一门外语课.答：（1） （p q ）（pq） 其中 p:小丽拿一个苹果，q:小丽拿一个梨（2） （p q ）（pq） 其中 p:刘晓月选学英语，q:刘晓月选学日语14. 将下列命题符号化. (1) 刘晓月跑得快, 跳得高. (2)老王是山东人或河北人. (3)因为天气冷, 所以我穿了羽绒服. (4)王欢与李乐组成一个小组. (5)李辛与李末是兄弟. (6)王强与刘威都学过法语. (7)他一面吃饭, 一面听音乐. (8)如果天下大雨, 他就乘班车上班. (9)只有天下大雨

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

3、他吃饭, q: 他听音乐. (8)pq, 其中, p: 天下大雨, q: 他乘班车上班. (9)pq, 其中, p: 他乘班车上班, q: 天下大雨. (10)pq, 其中, p: 他乘班车上班, q: 天下大雨. (11)pq, 其中, p: 下雪路滑, q: 他迟到了. (12) (pq)或pq, 其中, p: 2 是素数, q: 4 是素数. (13) (pq)或 pq, 其中, p: 2 是素数, q: 4 是素数.16.19. 用真值表判断下列公式的类型: (1)p (pqr) (2)(pq) q (3) (qr) r (4)(pq) (qp) (5)(pr) ( pq) (6)(p

4、q) (qr) (pr) (7)(pq) (rs)答：(1), (4), (6)为重言式. (3)为矛盾式. (2), (5), (7)为可满足式习题二9.用真值表求下面公式的主析取范式. (1) (pq)(pr)(2) (pq) (pq) 答：(1)(2)p q (p q) (p q) 0 0 1 0 0 10 1 1 1 1 01 0 0 1 1 11 1 1 0 0 0 从真值表可见成真赋值为 01, 10. 于是(p q) (p q) m1 m211.用真值表求下面公式的主析取范式和主合取范式；(1) (pq)r(2) p(pqr)(3) (qp)p15. 用主析取范式判断下列公式是否

5、等值: (1) (pq) r 与 q (pr)(2) (pq)与(pq)答：(1)(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) (pqr)(pqr)(pqr)(pqr) = m0 m1 m4

6、m5 m0 m1 m2 m3 m1 m3 m5 m7 m0 m1 m2 m3 m4 m5 m7 (0, 1, 2, 3, 4, 5, 7). 两个公式的主吸取范式不同, 所以(pq) rk q (pr).16. 用主析取范式判断下列公式是否等值: (1)(pq) r 与 q (pr) (2) (pq)与 (pq)答：(1)(pq) r) m1m3m4m5m7 q (pr) m0m1m2m3m4m5m7所以(pq) r) k q (pr) (2) (pq) m0m1m2 (pq) m0 所以 (pq) k (pq)习题三15.在自然推理系统 P 中用附加前提法证明下面各推理: (1)前提: p

7、(qr), sp, q 结论: sr (2)前提: (pq) (rs), (st) u 结论: pu 答：(1)证明: s 附加前提引入 sp 前提引入 p 假言推理 p(qr) 前提引入 qr 假言推理 q 前提引入 r 假言推理 (2)证明: P 附加前提引入 pq 附加 (pq) (rs) 前提引入 rs 假言推理 化简 st 附加 (st) u 前提引入 u 假言推理 16.在自然推理系统 P 中用归谬法证明下面推理: (1)前提: pq, rq, rs 结论: p (2)前提: pq, pr, qs 结论: rs 答：(1)证明: P 结论否定引入 pq 前提引入 q 假言推理 rq

8、 前提引入 r 析取三段论 rs 前提引入 r 化简 rr 合取 为矛盾式, 由归谬法可知, 推理正确. (2)证明: (rs) 结论否定引入 pq 前提引入 pr 前提引入 qs 前提引入 rs 构造性二难 (rs) (rs) 合取 为矛盾式, 所以推理正确.18.在自然推理系统 P 中构造下面推理的证明. (1)如果今天是星期六, 我们就要到颐和园或圆明园去玩. 如果颐和园游人太多, 我们就不去颐和园玩. 今天是星期六. 颐和园游人太多. 所以我们去圆明园玩. (2)如果小王是理科学生, 他的数学成绩一定很好. 如果小王不是文科生, 他必是理科生. 小王的数学成绩不好. 所以小王是文科学生

9、. (1)令 p: 今天是星期六; q: 我们要到颐和园玩; r: 我们要到圆明园玩; s:颐和园游人太多. 前提: p (qr), s q, p, s. 结论: r. 证明 p 前提引入 pqr 前提引入 qr假言推理s 前提引入 s q 前提引入 q 假言推理 r 析取三段论 r q s q sqr pqr p(2)令 p: 小王是理科生, q: 小王是文科生, r: 小王的数学成绩很好. 前提: pr, qp, r 结论: q 证明： pr 前提引入 r 前提引入 p 拒取式 qp 前提引入 q 拒取式习题四在一阶逻辑中将下列命题符号化:(1)没有不能表示成分数的有理数.(2)在北京卖菜

10、的人不全是外地人. (3)乌鸦都是黑色的.(4)有的人天天锻炼身体. 没指定个体域, 因而使用全总个体域.答：(1) x(F(x) G(x)或x(F(x) G(x), 其中 , F(x): x 为有理数, G(x): x 能表示成分数. (2) x(F(x) G(x)或x(F(x) G(x), 其中 , F(x): x 在北京卖菜, G(x): x 是外地人. (3) x(F(x) G(x), 其中, F(x): x 是乌鸦, G(x): x 是黑色的. (4) x(F(x) G(x), 其中, F(x): x 是人, G(x): x 天天锻炼身体. 5. 在一阶逻辑中将下列命题符号化: (1

11、)火车都比轮船快. (2)有的火车比有的汽车快. (3)不存在比所有火车都快的汽车. (4)“凡是汽车就比火车慢”是不对的. 答：因为没指明个体域, 因而使用全总个体域 (1) xy(F(x) G(y) H(x,y), 其中, F(x): x 是火车, G(y): y 是轮船, H(x,y):x 比 y 快. (2) xy(F(x) G(y) H(x,y), 其中, F(x): x 是火车, G(y): y 是汽车, H(x,y):x 比 y 快. (3) x(F(x) y(G(y) H(x,y) 或x(F(x) y(G(y) H(x,y), 其中, F(x): x 是汽车, G(y): y

12、是火车, H(x,y):x 比 y 快. (4) xy(F(x) G(y) H(x,y) 或xy(F(x) G(y) H(x,y) ),其中, F(x): x 是汽车, G(y): y 是火车, H(x,y):x 比 y 慢.9. 给定解释 I 如下: (a)个体域 DI 为实数集合. (b)DI 中特定元素a =0. (c)特定函数f (x,y)=xy, x,yDI. (d)特定谓词F(x,y): x=y, G(x,y): xy, x,yDI. 说明下列公式在 I 下的含义, 并指出各公式的真值: (1) xy(G(x,y) F(x,y) (2) xy(F(f(x,y),a) G(x,y)

13、(3) xy(G(x,y) F(f(x,y),a) (4) xy(G(f(x,y),a) F(x,y) 答：(1) xy(xyxy), 真值为 1. (2) xy(xy=0) xy), 真值为 0. (3) xy(xy) (xy0), 真值为 1. (4) xy(xy0) (x=y), 真值为 0.习题五5. 给定解释 I 如下: (a) 个体域 D=3,4. (b)f (x)为f (3)=4,f (4)=3. (c)F(x,y)为F(3,3)=F(4,4)=0, F(3,4)=F(4,3)=1. 试求下列公式在 I 下的真值: (1) xyF(x,y) (2) xyF(x,y)(3) xy(

14、F(x,y) F(f(x),f(y)答：(1) xyF(x,y)(F(3,3)F(3,4)(F(4,3)F(4,4) (01)(10) 1(2)xyF(x,y)(F(3,3)F(3,4)(F(4,3)F(4,4) (01)(10)0(3)xy(F(x,y)F(f(x),f(y)(F(3,3)F(f(3),f(3)(F(4,3)F(f(4),f(3)(F(3,4)F(f(3),f(4)(F(4,4)F(f(4),f(4) (00)(11)(11)(00)112. 求下列各式的前束范式. (1) xF(x) yG(x, y);(3) xF(x, y) xG(x, y); 答：前束范式不是唯一的.

15、(1) xF(x) yG(x, y) x(F(x) yG(x, y) xy(F(x) G(x, y). (3) xF(x, y) xG(x, y) (xF(x, y) xG(x, y) (xG(x, y) xF(x, y) (x1F(x1, y) x2G(x2, y) (x3G(x3, y) x4F(x4, y) x1x2(F(x1, y) G(x2, y) x3 x4(G(x3, y) F(x4, y) x1x2x3x4(F(x1, y) G(x2, y) (G(x3, y) F(x4, y). 13.将下列命题符号化, 要求符号化的公式全为前束范式: (1) 有的汽车比有的火车跑得快. (

16、2) 有的火车比所有的汽车跑得快. (3) 说所有的火车比所有的汽车跑得快是不对的. (4) 说有的飞机比有的汽车慢是不对的. 答：(1)令 F(x):x 是汽车,G(y):y 是火车,H(x,y):x 比 y 跑得快.x(F(x) y(G(y)H(x,y) xy(F(x)G(y)H(x, y).(2)令 F(x):x 是火车, G( y): y 是汽车,H(x,y):x 比 y 跑得快.x(F(x) y(G(y) H(x,y)xy(F(x)(G y)H(x,y).;错误的答案:xy(F(x)G(y)H(x,y).(3)令 F(x):x 是火车,G(y):y 是汽车,H(x,y):x 比 y

17、跑得快.x(F(x) y(G(y)H(x,y)xy(F(x)(G(y)H(x,y) xy(F(x)G(y)H(x,y)(不是前束范式) xy(F(x)G(y)H(x,y).(4)令 F(x):x 是飞机,G(y):y 是汽车,H(x,y):x 比 y 跑得慢.x(F(x) y(G(y)H(x,y)xy(F(x)G(y)H(x,y)(不是前束范式)xy(F(x)G(y)H(x,y)xy(F(x)G(y)H(x,y).21.24. 在自然推理系统 F 中, 构造下面推理的证明: 每个喜欢步行的人都不喜欢骑自行车. 每个人或者喜欢骑自行车或者喜欢乘汽车. 有的人不喜欢乘汽车, 所以有的人不喜欢步行.

18、 (个体域为人类集合) 答：令 F(x): x 喜欢步行, G( x): x 喜欢骑自行车, H(x): x 喜欢乘汽车. 前提:x(F(x)G(x), x(G(x)H(y),xH(x).结论:xF(x). x(G(x) H(y) 前提引入 G(c) H(c) UI xH(x) 前提引入 H(c) UI G(c) 析取三段 x(F(x) G(x) 前提引入 F(c) G(c) UI F(c) 拒取 xF(x) EG习题七12. 设 A=0, 1, 2, 3, R 是 A 上的关系, 且 R=0, 0, 0, 3, 2, 0, 2, 1, 2, 3, 3, 2 给出 R 的关系矩阵和关系图.16

19、. 设 A=a,b,c,d, R1,R2 为 A 上的关系, 其中 R1=a,a,a,b,b,d R2=a,d,b,c,b,d,c,b 求 R1R2, R2R1,R1,R2. R1R2=a,a,a,c,a,d, R2R1=c,d, R1=a,a,a,b,a,d, R2=b,c,b,d,c,b20. 设 R1 和 R2 为 A 上的关系, 证明: (1)(R1R2) 1=R11R21 (2)(R1R2) 1=R11R21 答：(1)(R1R2)1=R11R21 任取x,y x,y(R1R2)1y,x(R1R2) y,xR1 (y,x)R2) x,yR11x,yR2 1x,yR11R21所以(R1R2) 1=R11R21 (2)(R1R2) 1=R11R21 任取x,y x,y(R1R2) 1y,x(R1R2) y,xR1 (y,x)R2)x,yR1 1x,yR21 x,yR11R21 所以(R1R2) 1=R11R2126.33.43.16.47.