離散數(shù)學(xué)課后答案離散數(shù)學(xué)屈婉玲版課后答案

《離散數(shù)學(xué)課后答案離散數(shù)學(xué)屈婉玲版課后答案》由會員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)課后答案離散數(shù)學(xué)屈婉玲版課后答案（178頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、 [離散數(shù)學(xué)課后答案]離散數(shù)學(xué)屈婉玲版課后答案 篇一 : 離散數(shù)學(xué)屈婉玲版課后答案 Canton, 2008.2 離散數(shù)學(xué)習(xí)題解 離散數(shù)學(xué)/耿素云, 屈婉玲編著. 2版. ?北京: 高等教育出版社, 2004. 1 1 習(xí)題解 華南農(nóng)業(yè)大學(xué)2007學(xué)年第二學(xué)期用 千言萬語不及一張圖 ----佚名 離散數(shù)學(xué)習(xí)題解 2 超 鏈 接 習(xí)題一 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,

2、 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31 習(xí)題二 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30 習(xí)題三 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18 習(xí)題四 1, 2, 3, 4, 5, 6, 7, 8, 9

3、, 10, 11, 12, 13, 14, 15 習(xí)題五 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25 習(xí)題六 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44,

4、45 習(xí)題七 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50 習(xí)題八 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25

5、, 26, 27, 28 習(xí)題九 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 39, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40 習(xí)題十 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 39, 31, 32,

6、33, 34, 35, 36, 37, 38, 39, 40 習(xí)題十一 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 39, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40 習(xí)題十二 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27,

7、28, 29, 39, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40 習(xí)題十三 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 39, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40 習(xí)題十四 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22,

8、23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50 習(xí)題十五 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22 習(xí)題十六 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 2

9、7, 28, 29, 30, 31, 32, 33, 34, 35 習(xí)題十七 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43 習(xí)題十八 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23

10、 離散數(shù)學(xué)習(xí)題解 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． 略 略 將下列命題符號化, 并給出各命題的真值: 2+2＝4當(dāng)且僅當(dāng)3+3＝6. 2+2＝4的充要條件是3+3≠6. 2+2≠4與3+3＝6互為充要條件. 若2+2≠4, 則3+3≠6, 反之亦然.

11、 p?q, 其中, p: 2+2＝4, q: 3+3＝6, 真值為1. p??q, 其中, p: 2+2＝4, q: 3+3＝6, 真值為0. ?p?q, 其中, p: 2+2＝4, q: 3+3＝6, 真值為0. ?p??q, 其中, p: 2+2＝4, q: 3+3＝6, 真值為1. 1.13． 將下列命題符號化, 并給出各命題的真值: 若今天是星期一, 則明天是星期二. 只有今天是星期一, 明天才是星期二. 今天是星期一當(dāng)且僅當(dāng)明天是星期二. 若今天是星期一, 則明天是星期三. 令 p: 今天

12、是星期一; q: 明天是星期二; r: 明天是星期三. p→q ? 1. q→p ? 1. p?q ? 1. p→r當(dāng)p ? 0時為真; p ? 1 時為假. 1.14． 將下列命題符號化. 劉曉月跑得快, 跳得高. 老王是山東人或河北人. 因?yàn)樘鞖饫? 所以我穿了羽絨服. 王歡與李樂組成一個小組. 李辛與李末是兄弟. 王強(qiáng)與劉威都學(xué)過法語. 他一面吃飯, 一面聽音樂. 如果天下大雨, 他就乘班車上班. 只有天下大雨, 他才乘班車上班.

13、 除非天下大雨, 他才乘班車上班. 下雪路滑, 他遲到了. 2與4都是素數(shù), 這是不對的. “2或4是素數(shù), 這是不對的”是不對的. 離散數(shù)學(xué)習(xí)題解 p∧q, 其中, p: 劉曉月跑得快, q: 劉曉月跳得高. p∨q, 其中, p: 老王是山東人, q: 老王是河北人. p→q, 其中, p: 天氣冷, q: 我穿了羽絨服. p, 其中, p: 王歡與李樂組成一個小組, 是簡單命題. p, 其中, p: 李辛與李末是兄弟. p∧q, 其中, p: 王強(qiáng)學(xué)過

14、法語, q: 劉威學(xué)過法語. p∧q, 其中, p: 他吃飯, q: 他聽音樂. p→q, 其中, p: 天下大雨, q: 他乘班車上班. p→q, 其中, p: 他乘班車上班, q: 天下大雨. p→q, 其中, p: 他乘班車上班, q: 天下大雨. p→q, 其中, p: 下雪路滑, q: 他遲到了. ? 或?p∨?q, 其中, p: 2是素數(shù), q: 4是素數(shù). ?? 或p∨q, 其中, p: 2是素數(shù), q: 4是素數(shù). 1.15． 設(shè)p: 2+3=5. 4 q: 大熊貓產(chǎn)在中國. r: 復(fù)

15、旦大學(xué)在廣州. 求下列復(fù)合命題的真值: →r ) ? ?p ?r→ ? →r) 真值為0. 真值為0. 真值為0. 真值為1. 注意: p, q是真命題, r是假命題. 1.16． 1.17． 1.18． 1.19． 略 略 略 用真值表判斷下列公式的類型: p→ →?q ? ∧r → ? ∧ ) → ? 離散數(shù)學(xué)習(xí)題解

16、 , , 為重言式. 為矛盾式. , , 為可滿足式. 1.20． 1.21． 1.22． 1.23． 1.24． 1.25． 1.26． 1.27． 1.28． 1.29． 1.30． 略 略 略 略 略 略 略 略 略 略 略 5 p→q, 其中, p: 2+2＝4, q: 地球靜止不動, 真值為0. p→q, 其中, p: 2+2＝4, q: 地球運(yùn)動不止, 真值為1. ?p→?q, 其中, p:

17、 地球上有樹木, q: 人類能生存, 真值為1. ?p→q, 其中, p: 地球上有水, q是無理數(shù), 真值為1. 離散數(shù)學(xué)習(xí)題解 6 2.1. 設(shè)公式 A = p→q, B = p?∧q, 用真值表驗(yàn)證公式 A 和 B 適合德摩根律: p q ? ? ?A?∧B. A =p→q B =p?∧q ? ?A?∧B 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 因?yàn)?和?A?∧B的真值表相同, 所以它們等值. 2.2. 略 2.3. 用等值演算法判斷下列公式的

18、類型, 對不是重言式的可滿足式, 再用真值表法求出成真賦值. ? ) ∨ → ? ? ? ∨ q) ? ? ? p∧q∧?q ? p∧0 ? 0 ? 0. 矛盾式. 重言式. → ? ? ∨ ? ?p?∧q ∨ p∧r易見, 是可滿足式, 但不是重言式. 成真賦值為: 000, 001, 101, 111 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 ?p ∧ ?q ∨ p

19、∧r1 1 1 1 0 1 1 1 1 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 1 2.4. 用等值演算法證明下面等值式: p? ∨ ? ? ∧? ∨ ? ∧? ∨ ? p ∧ ? p ∧ 1 ? p. ? 離散數(shù)學(xué)習(xí)題解 ?? ∧ ) ?? ∧ ) ? ∨ ? ∧ ∧ ∧ ? ∧? ∨ ? ∧ ∧

20、 ∧ ? ∧? 2.5. 求下列公式的主析取范式, 并求成真賦值: → ? ∧q∧r ) → → ? ? ∨ ? ?p∧?q ∨ ?q ∨ p? ?p∧?q ∨ ?q ∨ p? ?∧q ∨ p∧ ? p?∧q ?∨p?∧q ∨ p∧q ∨ p?∧q ? m10 ∨ m00 ∨ m11 ∨ m10 ? m0 ∨ m2 ∨ m3 ? ∑. 成真賦值為 00, 10, 11. 主析取范式為0, 無成真賦值, 為矛盾式. m0∨m1∨m2∨m3∨m4∨

21、m5∨m6∨m7, 為重言式. 2.6. 求下列公式的主合取范式, 并求成假賦值: ? ∧?p ∨ ) ∨r ? ∧ ?p ? ? ∧ ?p ? q∧p ∧ ?p ? q∧0 ? 0 ? M0∧M1∧M2∧M3 這是矛盾式. 成假賦值為 00, 01, 10, 11. M4, 成假賦值為100. 主合取范式為1, 為重言式. 7 離散數(shù)學(xué)習(xí)題解 2.7. 求下列公式的主析取范式, 再用主析取范式求合取范式:

22、 ∨r ∧ m1∨m3∨m5∨m6∨m7?M0∧M2∧M4 m0∨m1∨m3∨m7?M2∧M4∧M5∧M6 2.8. 略 2.9. 用真值表求下面公式的主析取范式. → 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 8從真值表可見成真賦值為01, 10. 于是 → ? m1 ∨ m2. 2.10. 略 2.11. 略 2.12. 略 2.13. 略 2.14.

23、略 2.15. 用主析取范式判斷下列公式是否等值: →r與q→ →r ? ? ∨ r ? ? ∨ 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 = m101 ∨ m100 ∨ m111 ∨ m101 ∨ m011 ∨ m001 ? m1 ∨ m3 ∨ m4 ∨ m5 ∨ m7 = ∑. 而 q→ ? ?q ∨ ? ?

24、q ∨ ?p ∨r ? ?∧q∧ ∨ ?p∧∧ ∨ ∧∧r ? ∨∨∨ ∨∨∨∨ 離散數(shù)學(xué)習(xí)題解 ∨∨∨∨ = m0 ∨ m1 ∨ m4 ∨ m5 ∨ m0 ∨ m1 ∨ m2 ∨ m3 ∨ m1 ∨ m3 ∨ m5 ∨ m7 ? m0 ∨ m1 ∨ m2 ∨ m3 ∨ m4 ∨ m5 ∨ m7 ? ∑. 兩個公式的主吸取范式不同, 所以 →rk q→ . 9 2.16. 用主析取范式判斷下列公式是否等值: →r與q→

25、 ? 與? →r) ?m1∨m3∨m4∨m5∨m7 q→ ?m0∨m1∨m2∨m3∨m4∨m5∨m7 所以 →r) k q→ ? ?m0∨m1∨m2 ? ?m0 所以? k ? 2.17. 用主合取范式判斷下列公式是否等值: p→ 與? ∨r p→ 與 →r p→ ?M6 ? ∨r?M6 所以p→ ? ? ∨r p→ ?M6 →r?M0∧M1∧M2∧M6 所以p→ k →

26、r 2.18. 略 2.19. 略 2.20. 將下列公式化成與之等值且僅含 {?, →} 中聯(lián)結(jié)詞的公式. ?r. 注意到A?B ? ∧和 A∧B ? ? ? ?以及 A∨B ? ?A→B. ?r 離散數(shù)學(xué)習(xí)題解 ? ∧ ? → r) ∧ ) ? ? → r) → ?)) 注)聯(lián)結(jié)詞越少, 公式越長. 2.21. 證明: ? , ? . ? ? ? ? ? . ? ? ? ? ? . 2.22. 略 2.23.

27、 略 2.24. 略 2.25. 設(shè)A, B, C為任意的命題公式. 若A∨C?B∨C, 舉例說明 A?B不一定成立. 已知A∧C?B∧C, 舉例說明A?B不一定成立. 已知?A??B, 問: A?B一定成立嗎? 取 A = p, B = q, C = 1 , 有 A∨C ? B∨C, 但 A k B. 10 取 A = p, B = q, C = 0 , 有 A∧C ? B∧C, 但 A k B. 好的例子是簡單, 具體, 而又說明問題的. 一定. 2.26. 略 2.

28、27. 某電路中有一個燈泡和三個開關(guān)A,B,C. 已知在且僅在下述四種情況下燈亮: C的扳鍵向上, A,B的扳鍵向下. A的扳鍵向上, B,C的扳鍵向下. B,C的扳鍵向上, A的扳鍵向下. A,B的扳鍵向上, C的扳鍵向下. 設(shè)F為1表示燈亮, p,q,r分別表示A,B,C的扳鍵向上. 求F的主析取范式. 在聯(lián)結(jié)詞完備集{?, ∧}上構(gòu)造F. 在聯(lián)結(jié)詞完備集{?, →,?}上構(gòu)造F. 由條件-可知, F的主析取范式為 F? ∨ ∨ ∨ ?m1∨m4∨m3∨m6 ?m

29、1∨m3∨m4∨m6 離散數(shù)學(xué)習(xí)題解 先化簡公式 F? ∨ ∨ ∨ ??q∧ ∨ ) ∨q∧ ∨ ) ? ∧ ∨ ) ? ∨ ?? ∧? ) F? ∨ ??? ∨ ?? → ? →? ? →? 11 2.28. 一個排隊(duì)線路, 輸入為A,B,C, 其輸出分別為FA,FB,FC. 本線路中, 在同一時間內(nèi)只能有一個信號通過, 若同時有兩個和兩個以上信號申請輸出時, 則按A,B,C的順序輸出. 寫出F

30、A,FB,FC在聯(lián)結(jié)詞完備集{?, ∨}中的表達(dá)式. 根據(jù)題目中的要求, 先寫出FA,FB,FC的真值表 由真值表可先求出他們的主析取范式, 然后化成{?, ∧}中的公式 FA?m4∨m5∨m6∨m7 ?p FB?m2∨m3 ??p∧q FC?m1 ??p∧?q∧r 2.29. 略 2.30. 略 離散數(shù)學(xué)習(xí)題解 12 3.1. 略 3.2. 略 3.3. 略 3.4. 略 3.5. 略 3.6. 判斷下面推理是否正確

31、. 先將簡單命題符號化, 再寫出前提, 結(jié)論, 推理的形式結(jié)構(gòu)和判斷過程: 若今天是星期一, 則明天是星期三；今天是星期一. 所以明天是星期三. 若今天是星期一, 則明天是星期二；明天是星期二. 所以今天是星期一. 若今天是星期一, 則明天是星期三；明天不是星期三. 所以今天不是星期一. 若今天是星期一, 則明天是星期二；今天不是星期一. 所以明天不是星期二. 若今天是星期一, 則明天是星期二或星期三. 今天是星期一當(dāng)且僅當(dāng)明天是星期三；今天不是星期一. 所以明天不是星期三. 設(shè)p: 今天是星期一, q: 明天是星期二, r

32、: 明天是星期三. 推理的形式結(jié)構(gòu)為 ∧p→r 此形式結(jié)構(gòu)為重言式, 即 ∧p?r 所以推理正確. 推理的形式結(jié)構(gòu)為 ∧q→p 此形式結(jié)構(gòu)不是重言式, 故推理不正確. 推理形式結(jié)構(gòu)為 ∧?r→?p 此形式結(jié)構(gòu)為重言式, 即 ∧?r??p 故推理正確. 推理形式結(jié)構(gòu)為 ∧?p→?q 此形式結(jié)構(gòu)不是重言式, 故推理不正確. 推理形式結(jié)構(gòu)為 p→ 它不是重言式, 故推理不正確. 推理形式結(jié)

33、構(gòu)為 ∧?p→?r 離散數(shù)學(xué)習(xí)題解 此形式結(jié)構(gòu)為重言式, 即 ∧?p??r 故推理正確. 13 推理是否正確, 可用多種方法證明. 證明的方法有真值表法, 等式演算法. 證明推理正確還可用構(gòu)造證明法. 下面用構(gòu)造證明法證明推理正確. 前提: p?r, ?p 結(jié)論: ?r 證明: ①p?r 前提引入 ② ∧ ①置換 ③ r→p ②化簡律 ④?p 前提引入 ⑤?r ③④拒取式 所以, 推理正確. 3.7. 略 3.8.

34、 略 3.9. 用三種方法證明下面推理是正確的: 若 a 是奇數(shù), 則 a 不能被2 整除. 若 a 是偶數(shù), 則 a 能被 2 整除. 因此, 如果 a 是偶數(shù), 則 a 不是奇數(shù). 令 p: a 是奇數(shù); q: a 能被2 整除; r: a 是偶數(shù). 前提: p → ?q, r → q. 結(jié)論: r → ?p. 形式結(jié)構(gòu): ∧ → . …… 3.10.略 3.11.略 3.12.略 3.13.略 3.14.在自然推理系統(tǒng)P中構(gòu)造下面推理的證明: 前提: p→ , p, q

35、 結(jié)論: r∨s 前提: p→q, ? , r 結(jié)論: ?p 前提: p→q 結(jié)論: p→ 前提: q→p, q?s, s?t, t∧r 結(jié)論: p∧q 前提: p→r, q→s, p∧q 離散數(shù)學(xué)習(xí)題解 結(jié)論: r∧s 前提: ?p∨r, ?q∨s, p∧q 結(jié)論: t→ 證明: 14① ② ③ ④ ⑤ ⑥ p→ p q→r q r r∨s 前提引入 前提引入 ①②假言

36、推理 前提引入 ③④假言推理 ⑤附加律 證明: ① ② ③ ④ ⑤ ⑥ ? ?q∨?r r ?q p→q ?p 前提引入 ①置換 前提引入 ②③析取三段論 前提引入 ④⑤拒取式 證明: ① ② ③ ④ ⑤ p→q ?p∨q ∧ ?p∨ p→ 前提引入 ①置換 ②置換 ③置換 ④置換 也可以用附加前提證明法, 更簡單些. 證明: ① ② ③ ④ ⑤ ⑥ ⑦ ⑧

37、 ⑨ ⑩ s?t ∧ t→s t∧r t s q?s ∧ s→q q 前提引入 ①置換 ②化簡 前提引入 ④化簡 ③⑤假言推理 前提引入 ⑦置換 ⑧化簡 ⑥⑥假言推理 離散數(shù)學(xué)習(xí)題解 11 ○ 12 ○ 13 ○15q →p p p∧q 前提引入 11假言推理 ⑩○12合取 ⑩○ 證明: ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ p→r q→s p∧q p q r s r∧s 前提引入 前提引入 前提

38、引入 ③化簡 ③化簡 ①④假言推理 ②⑤假言推理 ⑥⑦合取 證明: ① ② ③ ④ ⑤ ⑥ t ?p∨r p∧q p r r∨s 附加前提引入 前提引入 前提引入 ③化簡 ②④析取三段論 ⑤附加 說明: 證明中, 附加提前t, 前提?q∨s沒用上. 這仍是正確的推理. 3.15.在自然推理系統(tǒng)P中用附加前提法證明下面各推理: 前提: p→ , s→p, q 結(jié)論: s→r 前提: → , →u 結(jié)論: p→u 證明: ① ②

39、 ③ ④ ⑤ ⑥ ⑦ s s→p p p→ q→r q r 附加前提引入 前提引入 ①②假言推理 前提引入 ③④假言推理 前提引入 ⑤⑥假言推理 離散數(shù)學(xué)習(xí)題解 證明: 16 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ P p∨q → r∧s S s∨t →u u 附加前提引入 ①附加 前提引入 ②③假言推理 ④化簡 ⑤附加 前提引入 ⑥⑦假言推理 3.16.在自然推理系統(tǒng)P中用歸謬法證明下面推理: 前提: p→?q, ?

40、r∨q, r∧?s 結(jié)論: ?p 前提: p∨q, p→r, q→s 結(jié)論: r∨s 證明: ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ P p→?q ?q ?r∨q ?r r∧?s r ?r∧r 結(jié)論否定引入 前提引入 ①②假言推理 前提引入 ③④析取三段論 前提引入 ⑥化簡 ⑤⑦合取 ⑧為矛盾式, 由歸謬法可知, 推理正確. 證明: ① ② ③ ④ ⑤ ⑥ ? p∨q p→r q→s r∨s

41、? ∧ 結(jié)論否定引入 前提引入 前提引入 前提引入 ②③④構(gòu)造性二難 ①⑤合取 離散數(shù)學(xué)習(xí)題解 ⑥為矛盾式, 所以推理正確. 3.17.P53 17. 在自然推理系統(tǒng) P 中構(gòu)造下面推理的證明: 17 只要 A 曾到過受害者房間并且11點(diǎn)以前沒用離開, A 就犯了謀殺罪. A 曾到過受害者房間. 如果 A 在11點(diǎn)以前離開, 看門人會看到他. 看門人沒有看到他. 所以 A 犯了謀殺罪. 令 p: A 曾到過受害者房間; q: A 在11點(diǎn)以前離開了; r: A 就犯了謀殺罪; s:看門人看到 A. 前提: p?∧q

42、 → r, p, q → s, ?s. 結(jié)論: r. 前提: p?∧q → r, p, q → s, ?s; 結(jié)論: r. 證明: ① ?s 前提引入 前提引入 ② q → s ③ ?q ①②拒取 ④ p 前提引入 ③④合取 前提引入 ⑤⑥假言推理 ⑤ p?∧q ⑥ p?∧q → r ⑦ r 3.18.在自然推理系統(tǒng)P中構(gòu)造下面推理的證明. 如果今天是星期六, 我們就要到頤和園或圓明園去玩. 如果頤和園游人太多, 我們就不去頤和園玩. 今天是星期六. 頤和園游人太多. 所以我

43、們?nèi)A明園玩. 如果小王是理科學(xué)生, 他的數(shù)學(xué)成績一定很好. 如果小王不是文科生, 他必是理科生. 小王的數(shù)學(xué)成績不好. 所以小王是文科學(xué)生. 明天是晴天, 或是雨天；若明天是晴天, 我就去看電影；若我看電影, 我就不看書. 所以, 如果我看書, 則明天是雨天. 令 p: 今天是星期六; q: 我們要到頤和園玩; r: 我們要到圓明園玩; s:頤和園游人太多. 前提: p→ , s → ?q, p, s. 結(jié)論: r. ① ② ③

44、 ④ ⑤ ⑥ ⑦ p p → q∨r q∨r s s → ?q ?q r 前提引入 前提引入 ①②假言推理

45、 前提引入 pp→q∨r q∨rrss → ?q ?q 前提引入 ④⑤假言推理 ③⑥析取三段論 的證明樹 離散數(shù)學(xué)習(xí)題解 令p: 小王是理科生, q: 小王是文科生, r: 小王的數(shù)學(xué)成績很好. 前提: p→r, ?q→p, ?r 結(jié)論: q 證明: 18 ① ② ③ ④ ⑤ p→r ?r ?p ?q→p q 前提引入 前提引入 ①②拒取式 前提引入 ③④拒取式 ? q? p的

46、證明樹p→q ?r→pr 令p: 明天是晴天, q: 明天是雨天, r: 我看電影, s: 我看書. 前提: p∨q, p→r, r→?s 結(jié)論: s→q 證明: ① ② ③ ④ ⑤ ⑥ ⑦ s r→?s ?r p→r ?p p∨q q 附加前提引入 前提引入 ①②拒取式 前提引入 ③④拒取式 前提引入 ⑤⑥析取三段論 離散數(shù)學(xué)習(xí)題解 19 4.1. 將下面命題用0元謂詞符號化: 小王學(xué)過英語和法語. 除非李建是東北人, 否

47、則他一定怕冷. 令 F: x 學(xué)過英語; F: x 學(xué)過法語; a: 小王. 符號化為 F∧F. 或進(jìn)一步細(xì)分, 令 L: x 學(xué)過 y; a: 小王; b1: 英語; b2: 法語. 則符號化為 L∧L. 令 F: x 是東北人; G: x 怕冷; a: 李建. 符號化為 ?F→G 或 ?G→F. 或進(jìn)一步細(xì)分, 令 H: x 是 y 地方人; G: x 怕冷; a: 小王; b: 東北. 則符號化為 ?H→G 或 ?G→ H. 4.2. 在一階邏輯中將下面命題符號化, 并分別討論個體域限制為,時命題的真值: 凡有理數(shù)

48、都能被2整除. 有的有理數(shù)能被2整除. 其中個體域?yàn)橛欣頂?shù)集合, 個體域?yàn)閷?shí)數(shù)集合. 中, ?xF, 其中, F: x能被2整除, 真值為0. 中, ?x ∧F), 其中, G: x為有理數(shù), F同中, 真值為0. 中, ?xF, 其中, F: x能被2整除, 真值為1. 中, ?x ∧F), 其中, F同中, G: x為有理數(shù), 真值為1. 中, ?x 中, ?x → : x為實(shí)數(shù), 真值為1. 中, ?x, 真值為1. 中, ?x ∧ ), 其

49、中, F: x為實(shí)數(shù), 真值為1. 4.4. 在一階邏輯中將下列命題符號化: 沒有不能表示成分?jǐn)?shù)的有理數(shù). 在北京賣菜的人不全是外地人. 離散數(shù)學(xué)習(xí)題解 烏鴉都是黑色的. 有的人天天鍛煉身體. 沒指定個體域, 因而使用全總個體域. ??x ∧?G)或?x →G), 其中, F: x為有理數(shù), G: x能表示成分?jǐn)?shù). ??x →G)或?x ∧?G), 其中, F: x在北京賣菜, G: x是外地人. ?x →G), 其中, F: x是烏鴉, G: x是黑色的. ?x ∧G),

50、其中, F: x是人, G: x天天鍛煉身體. 4.5. 在一階邏輯中將下列命題符號化: 火車都比輪船快. 有的火車比有的汽車快. 不存在比所有火車都快的汽車. “凡是汽車就比火車慢”是不對的. 因?yàn)闆]指明個體域, 因而使用全總個體域 ?x?y ∧G →H), 其中, F: x是火車, G: y是輪船, H:x比y快. ?x?y ∧G ∧H), 其中, F: x是火車, G: y是汽車, H:x比y快. ??x ∧?y →H)) 或?x →?y ∧?H)), 其中, F: x是汽車, G: y是火車

51、, H:x比y快. ??x?y ∧G →H) 或?x?y ∧G ∧?H ), 其中, F: x是汽車, G: y是火車, H:x比y慢. 4.6. 略 4.7. 將下列各公式翻譯成自然語言, 個體域?yàn)檎麛?shù)集 ??, 并判斷各命題的真假. ?x?y?z; ?x?y. 可選的翻譯: ①“任意兩個整數(shù)的差是整數(shù).” ② “對于任意兩個整數(shù), 都存在第三個整數(shù), 它等于這兩個整數(shù)相減.” ③ “對于任意整數(shù) x 和 y, 都存在整數(shù) z, 使得 x ? y = z.” 20選③, 直接翻譯, 無需數(shù)理邏輯以外的知識.

52、 以下翻譯意思相同, 都是錯的: n “有個整數(shù), 它是任意兩個整數(shù)的差.” o “存在一個整數(shù), 對于任意兩個整數(shù), 第一個整數(shù)都等于這兩個整數(shù)相減.” p “存在整數(shù) z, 使得對于任意整數(shù) x 和 y, 都有 x ? y = z.” 這3個句子都可以符號化為 ?z?x?y. ;量詞順序不可隨意調(diào)換. 可選的翻譯: 離散數(shù)學(xué)習(xí)題解 ①“每個整數(shù)都有一個倒數(shù).” ② “對于每個整數(shù), 都能找到另一個整數(shù), 它們相乘結(jié)果是零.” ③ “對于任意整數(shù) x, 都存在整數(shù) y, 使得 x?y = z.”

53、 21 選③, 是直接翻譯, 無需數(shù)理邏輯以外的知識. 4.8. 指出下列公式中的指導(dǎo)變元, 量詞的轄域, 各個體變項(xiàng)的自由出現(xiàn)和約束出現(xiàn): ?x?y ∧ G) ∨ ?xH 前件 ?x?y∧G) 中, ? 的指導(dǎo)變元是 x, ? 的轄域是 ?y∧G); ? 的指導(dǎo)變元是 y, ? 的轄域是 ∧G). 后件 ?xH 中, ? 的指導(dǎo)變元是 x, ? 的轄域是 H. 整個公式中, x 約束出現(xiàn)兩次, y 約束出現(xiàn)兩次, 自由出現(xiàn)一次; z 自由出現(xiàn)兩次. 4.9. 給定解釋I如下: 個體域DI為實(shí)數(shù)集合\.

54、 DI中特定元素?a =0. 特定函數(shù)?f =x?y, x,y∈DI. 特定謂詞?F: x=y,?G: x 說明下列公式在I下的含義, 并指出各公式的真值: ?x?y →?F) ?x?y,a) →G) ?x?y →?F,a)) ?x?y,a) →F) ?x?y, 真值為1. ?x?y →x ?x?y → ), 真值為1. ?x?y → ), 真值為0. 4.10.給定解釋I如下: 個體域D=`. D中特定元素?a=2. D上函數(shù)?f =x

55、+y,?g =x·y. D上謂詞?F : x=y. 說明下列公式在I下的含義, 并指出各公式的真值: ?xF,x) ?x?y,y) →F,x)) ?x?y?z,z) ?xF,g) 離散數(shù)學(xué)習(xí)題解 ?x, 真值為0. ?x?y → ), 真值為0. ?x?y?z,真值為1. ?x,真值為1. 4.11.判斷下列各式的類型: F → → F). ?x?yF → ?x?yF. ?x?y → F). 是

56、命題重言式 p → 的代換實(shí)例, 所以是永真式. 在某些解釋下為假, 在某些解釋下為真, 所以是非永真式的可滿足式. 同. 4.12.P69 12. 設(shè) I 為一個任意的解釋, 在解釋 I 下, 下面哪些公式一定是命題? ?xF → ?yG. ?x → G) ∧ ?y ∧ H). ?x → ?yG). ?x ∧ G) ∧ H. , 一定是命題, 因?yàn)樗鼈兪情]式. 4.13.略 4.14.證明下面公式既不是永真式也不是矛盾式: ?x →?y ∧H)) ?x?y ∧G

57、→H) 取個體域?yàn)槿倐€體域. 解釋I1: F: x為有理數(shù), G: y為整數(shù), H: x 在I1下: ?x →?y ∧H))為真命題, 所以該公式不是矛盾式. 解釋I2: F,G同I1, H: y整除x. 在I2下: ?x →?y ∧H))為假命題, 所以該公式不是永真式. 請讀者給出不同解釋, 使其分別為成真和成假的命題即可. 4.15. 給出一個非閉式的永真式. 給出一個非閉式的永假式. 給出一個非閉式的可滿足式, 但不是永真式. F ∨ ?F. F ∧ ?F.

58、 ?x → F). 22 離散數(shù)學(xué)習(xí)題解 23 5.1. 略 5.2. 設(shè)個體域D={a,b,c}, 消去下列各式的量詞: ?x?y ∧G) ?x?y ∨G) ?xF →?yG ?x →?yG) ?x?y ∧G) ??xF ∧?yG ? ∧F) ∧F) ∧ ∨G ∨G) ?x?y ∨G) ??xF ∨?yG ? ∧F ∧F) ∨ ∧G ∧G) ?xF →?yG ? ∧F ∧

59、F) → ∧G ∧G) ?x →?yG) ??xF →?yG ? ∨F ∨F) → ∨G ∨G) 5.3. 設(shè)個體域D={1,2}, 請給出兩種不同的解釋I1和I2, 使得下面公式在I1下都是真命題, 而在I2下都是假 命題. ?x →G) ?x ∧G) I1: F:x≤2,G:x≤3 F,F,G,G均為真, 所以 ?x →G) ? →G ∧ →G)為真. I2: F同I1,G:x≤0 則F,F均為真, 而G,G均為假, ?x →G)為假. 留給讀者自己做.

60、 5.4. 略 5.5. 給定解釋I如下: 個體域D={3,4}. ?f 為?f =4,?f =3. ?F為?F=?F=0,?F=?F=1. 離散數(shù)學(xué)習(xí)題解 試求下列公式在I下的真值: ?x?yF ?x?yF ?x?y →F,f)) ?x?yF ? ∨F) ∧ ∨F) ? ∧ ?1 ?x?yF ? ∧F) ∨ ∧F) ? ∨ ?0 ?x?y →F,f)) ? →

61、F,f)) ∧ →F,f)) ∧ →F,f)) ∧ →F,f)) ? ∧ ∧ ∧ ?1 5.6. 略 5.7. 略 5.8. 在一階邏輯中將下列命題符號化, 要求用兩種不同的等值形式. 沒有小于負(fù)數(shù)的正數(shù). 相等的兩個角未必都是對頂角. 令 F: x 小于負(fù)數(shù), G: x 是正數(shù). 符合化為: ??x ∧ G) ? ?x → ?G). 24 令 F: x 是角, H: x 和 y 是相等的, L: x 與 y 是對頂角. 符合化為: ??x?y ∧ F ∧

62、 H → L) ? ?x?y ∧ F ∧ H ∧ ?L) ? ?x ∧ ∧ H ∧ ?L)). 5.9. 略 5.10.略 5.11.略 5.12.求下列各式的前束范式. ?xF → ?yG; ?xF ? ?xG; ?x1F → → ??x2G). 前束范式不是唯一的. ?xF → ?yG ? ?x → ?yG) 離散數(shù)學(xué)習(xí)題解 ? ?x?y → G). ?xF ? ?xG ? → ?xG) ∧ → ?xF) ? → ?

63、x2G) ∧ → ?x4F) ? ?x1?x2 → G) ∧ ?x3?x4 → F) ? ?x1?x2?x3?x4 → G) ∧ → F)). 5.13.將下列命題符號化, 要求符號化的公式全為前束范式: 有的汽車比有的火車跑得快. 有的火車比所有的汽車跑得快. 說所有的火車比所有的汽車跑得快是不對的. 說有的飛機(jī)比有的汽車慢是不對的. 令 F: x 是汽車, G: y 是火車, H: x 比 y 跑得快. ?x ∧ ?y ∧ H) ? ?x?y ∧ G ∧ H). 25 令 F: x 是火車, G: y 是汽

64、車, H: x 比 y 跑得快. ?x ∧ ?y → H)) ? ?x?y ∧ → H)). ;錯誤的答案: ?x?y ∧ G → H). 令 F: x 是火車, G: y 是汽車, H: x 比 y 跑得快. ??x → ?y → H)) ? ??x?y → → H)) ? ??x?y ∧ G → H) ? ?x?y ∧ G ∧ H). 令 F: x 是飛機(jī), G: y 是汽車, H: x 比 y 跑得慢. ? ?x ∧ ?y ∧ H)) ? ? ?x?y ∧ G ∧ H) ? ?x?y ? ∧ G ∧ H) ? ?x?y ∧ G

65、→ ?H). 5.14.略 5.15.在自然推理系統(tǒng)F中構(gòu)造下面推理的證明: 前提: ?xF → ?y ∨ G) → R), ?xF 結(jié)論: ?xR. 前提: ?x → ∧R)), ?xF 結(jié)論: ?x ∧R) 前提: ?x ∨G), ??xG 結(jié)論: ?xF 前提: ?x ∨G), ?x ∨?R), ?xR 結(jié)論: ?xF 離散數(shù)學(xué)習(xí)題解 證明: 26① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ?xF → ?y

66、 ∨ G) → R) ?xF ?y ∨ G) → R) ∨ G) → R F F ∨ G R ?xR 前提引入 前提引入 ①②假言推理 ③UI ①EI ⑤附加 ④⑥假言推理 ⑦EG 證明: ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ?xF ?x → ∧ )) F → ∧R) G ∧R R F ∧R ?x ∧R) 前提引入 前提引入 ④UI ②④假言推理 ⑤化簡 ②⑥合取 ⑥EG F EI① 證明: ① ② ③ ④ ⑤ ⑥ ⑦ ??xG ?x?G ?G ?x ∨G F ∨G F ?xF 前提引入 ①置換 ②UI 前提引入 ④UI ③⑤析取三段論 ⑥EG 證明: ① ② ④ ⑤ ⑥ ⑦ ⑧ ⑥ ?x ∨G) F ∨G ③?x ∨?R) ?G ∨?R ?xR ?G F ?xF 前提引入 ①UI 前提引入 ③UI 前提引入 ④⑥析取三段論 ②⑦析