离散数学课后答案.doc

离散数学课后答案习题一6.将下列命题符号化1）小丽只能从框里那一个苹果或一个梨.（2）这学期，刘晓月只能选学英语或日语中的一门外语课.答：（1）（p Λ¬q ）ν（¬pΛq） 其中p:小丽拿一个苹果，q:小丽拿一个梨（2）（p Λ¬q ）ν（¬pΛq） 其中p:刘晓月选学英语，q:刘晓月选学日语14. 将下列命题符号化. (1) 刘晓月跑得快, 跳得高. (2)老王是山东人或河北人. (3)因为天气冷, 所以我穿了羽绒服. (4)王欢与李乐组成一个小组. (5)李辛与李末是兄弟. (6)王强与刘威都学过法语. (7)他一面吃饭, 一面听音乐. (8)如果天下大雨, 他就乘班车上班. (9)只有天下大雨, 他才乘班车上班. (10)除非天下大雨, 他才乘班车上班. (11)下雪路滑, 他迟到了. (12)2与4都是素数, 这是不对的. (13)“2或4是素数, 这是不对的”是不对的. 答： (1)p∧q, 其中, p: 刘晓月跑得快, q: 刘晓月跳得高. (2)p∨q, 其中, p: 老王是山东人, q: 老王是河北人. (3)p→q, 其中, p: 天气冷, q: 我穿了羽绒服. (4)p, 其中, p: 王欢与李乐组成一个小组, 是简单命题. (5)p, 其中, p: 李辛与李末是兄弟. (6)p∧q, 其中, p: 王强学过法语, q: 刘威学过法语. (7)p∧q, 其中, p: 他吃饭, q: 他听音乐. (8)p→q, 其中, p: 天下大雨, q: 他乘班车上班. (9)p→q, 其中, p: 他乘班车上班, q: 天下大雨. (10)p→q, 其中, p: 他乘班车上班, q: 天下大雨. (11)p→q, 其中, p: 下雪路滑, q: 他迟到了. (12) ¬ (p∧q)或¬p∨¬q, 其中, p: 2是素数, q: 4是素数. (13) ¬ ¬ (p∨q)或p∨q, 其中, p: 2是素数, q: 4是素数.16.19. 用真值表判断下列公式的类型: (1)p→ (p∨q∨r) (2)(p→¬q) →¬q (3) ¬ (q→r) ∧r (4)(p→q) → (¬q→¬p) (5)(p∧r) ↔ ( ¬p∧¬q) (6)((p→q) ∧ (q→r)) → (p→r) (7)(p→q) ↔ (r↔s)答：(1), (4), (6)为重言式. (3)为矛盾式. (2), (5), (7)为可满足式习题二9.用真值表求下面公式的主析取范式. (1) (pνq)ν(¬pΛr)(2) (p→q) → (¬p↔q) 答：(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) (pνq)Λr(2) p→(pνqνr)(3) ¬(q→¬p)Λ¬p15. 用主析取范式判断下列公式是否等值: (1) (p→q) →r与q→ (p→r)(2) ¬(pΛq)与(¬pνq)答：(1)(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) →rk q→ (p→r).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) k q→ (p→r) (2) ¬ (p∧q) ⇔m0∨m1∨m2 ¬ (p∨q) ⇔m0 所以¬ (p∧q) k ¬ (p∨q)习题三15.在自然推理系统P中用附加前提法证明下面各推理: (1)前提: p→ (q→r), s→p, q 结论: s→r (2)前提: (p∨q) → (r∧s), (s∨t) →u 结论: p→u 答：(1)证明: ① s 附加前提引入 ② s→p 前提引入 ③ p ①②假言推理 ④ p→(q→r) 前提引入 ⑤ q→r ③④假言推理 ⑥ q 前提引入 ⑦ r ⑤⑥假言推理 (2)证明: ① P 附加前提引入 ② p∨q ①附加 ③ (p∨q) → (r∧s) 前提引入 ④ r∧s ②③ 假言推理 ⑤ ④化简 ⑥ s∨t ⑤附加 ⑦ (s∨t) →u 前提引入 ⑧ u ⑥⑦假言推理 16.在自然推理系统P中用归谬法证明下面推理: (1)前提: p→¬q, ¬r∨q, r∧¬s 结论: ¬p (2)前提: p∨q, p→r, q→s 结论: r∨s 答：(1)证明: ① P 结论否定引入 ② p→¬q 前提引入 ③ ¬q ①②假言推理 ④ ¬r∨q 前提引入 ⑤ ¬r ③④析取三段论 ⑥ r∧¬s 前提引入 ⑦ r ⑥化简 ⑧ ¬r∧r ⑤⑦合取 ⑧ 为矛盾式, 由归谬法可知, 推理正确. (2)证明: ① ¬ (r∨s) 结论否定引入 ② p∨q 前提引入 ③ p→r 前提引入 ④ q→s 前提引入 ⑤ r∨s ②③④构造性二难 ⑥ ¬ (r∨s) ∧ (r∨s) ①⑤合取 ⑥为矛盾式, 所以推理正确.18.在自然推理系统P中构造下面推理的证明. (1)如果今天是星期六, 我们就要到颐和园或圆明园去玩. 如果颐和园游人太多, 我们就不去颐和园玩. 今天是星期六. 颐和园游人太多. 所以我们去圆明园玩. (2)如果小王是理科学生, 他的数学成绩一定很好. 如果小王不是文科生, 他必是理科生. 小王的数学成绩不好. 所以小王是文科学生. (1)令 p: 今天是星期六; q: 我们要到颐和园玩; r: 我们要到圆明园玩; s:颐和园游人太多. 前提: p→ (q∨r), s → ¬q, p, s. 结论: r. 证明① p 前提引入② p→q∨r前提引入 ③q∨r①②假言推理④s前提引入⑤ s →¬q前提引入⑥ ¬q ④⑤假言推理⑦ r ③⑥析取三段论 r ¬q s → ¬q sq∨r p→q∨r p(2)令p: 小王是理科生, q: 小王是文科生, r: 小王的数学成绩很好. 前提: p→r, ¬q→p, ¬r 结论: q 证明：① p→r 前提引入 ② ¬r 前提引入 ③ ¬p ①②拒取式 ④ ¬q→p 前提引入 ⑤ q ③④拒取式习题四在一阶逻辑中将下列命题符号化:(1)没有不能表示成分数的有理数.(2)在北京卖菜的人不全是外地人. (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)火车都比轮船快. (2)有的火车比有的汽车快. (3)不存在比所有火车都快的汽车. (4)“凡是汽车就比火车慢”是不对的. 答：因为没指明个体域, 因而使用全总个体域 (1) ∀x∀y(F(x) ∧G(y) →H(x,y)), 其中, F(x): x是火车, G(y): y是轮船, H(x,y):x比y快. (2) ∃x∃y(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是火车, H(x,y):x比y快. (4) ¬∀x∀y(F(x) ∧G(y) →H(x,y)) 或∃x∃y(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)=x−y, x,y∈DI. (d)特定谓词⎯F(x,y): x=y,⎯G(x,y): x