離散數學課后答案離散數學屈婉玲版課后答案

《離散數學課后答案離散數學屈婉玲版課后答案》由會員分享，可在線閱讀，更多相關《離散數學課后答案離散數學屈婉玲版課后答案（178頁珍藏版）》請在裝配圖網上搜索。

1、離散數學課后答案離散數學屈婉玲版課后答案篇一 : 離散數學屈婉玲版課后答案 Canton, 2008.2 離散數學習題解 離散數學/耿素云, 屈婉玲編著. 2版. ?北京: 高等教育出版社, 2004. 1 1 習題解 華南農業(yè)大學2007學年第二學期用 千言萬語不及一張圖 -佚名 離散數學習題解 2 超 鏈 接 習題一 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 習題二 1, 2, 3, 4, 5, 6, 7,

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

3、 25 習題六 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 習題七 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,

4、 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50 習題八 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 習題九 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,

5、 33, 34, 35, 36, 37, 38, 39, 40 習題十 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 習題十一 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

6、, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40 習題十二 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 習題十三 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 習題十四 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 習題十五 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15

8、, 16, 17, 18, 19, 20, 21, 22 習題十六 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 習題十七 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, 3

9、6, 37, 38, 39, 40, 41, 42, 43 習題十八 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23 離散數學習題解 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+24當且僅當3+36. 2+24的充要條件是3+36. 2+24與3+36互為充要條件. 若2+24, 則3+36, 反之亦然. p?q, 其中, p:

10、2+24, q: 3+36, 真值為1. p?q, 其中, p: 2+24, q: 3+36, 真值為0. ?p?q, 其中, p: 2+24, q: 3+36, 真值為0. ?p?q, 其中, p: 2+24, q: 3+36, 真值為1. 1.13 將下列命題符號化, 并給出各命題的真值: 若今天是星期一, 則明天是星期二. 只有今天是星期一, 明天才是星期二. 今天是星期一當且僅當明天是星期二. 若今天是星期一, 則明天是星期三. 令 p: 今天是星期一; q: 明天是星期二; r: 明天是星期三. pq ? 1. qp ? 1. p?q ? 1. pr當p ? 0時為真; p ? 1

11、時為假. 1.14 將下列命題符號化. 劉曉月跑得快, 跳得高. 老王是山東人或河北人. 因為天氣冷, 所以我穿了羽絨服. 王歡與李樂組成一個小組. 李辛與李末是兄弟. 王強與劉威都學過法語. 他一面吃飯, 一面聽音樂. 如果天下大雨, 他就乘班車上班. 只有天下大雨, 他才乘班車上班. 除非天下大雨, 他才乘班車上班. 下雪路滑, 他遲到了. 2與4都是素數, 這是不對的. “2或4是素數, 這是不對的”是不對的. 離散數學習題解 pq, 其中, p: 劉曉月跑得快, q: 劉曉月跳得高. pq, 其中, p: 老王是山東人, q: 老王是河北人. pq, 其中, p: 天氣冷, q: 我穿

12、了羽絨服. p, 其中, p: 王歡與李樂組成一個小組, 是簡單命題. p, 其中, p: 李辛與李末是兄弟. pq, 其中, p: 王強學過法語, q: 劉威學過法語. pq, 其中, p: 他吃飯, q: 他聽音樂. pq, 其中, p: 天下大雨, q: 他乘班車上班. pq, 其中, p: 他乘班車上班, q: 天下大雨. pq, 其中, p: 他乘班車上班, q: 天下大雨. pq, 其中, p: 下雪路滑, q: 他遲到了. ? 或?p?q, 其中, p: 2是素數, q: 4是素數. ? 或pq, 其中, p: 2是素數, q: 4是素數. 1.15 設p: 2+3=5. 4 q

13、: 大熊貓產在中國. r: 復旦大學在廣州. 求下列復合命題的真值: r ) ? ?p ?r ? r) 真值為0. 真值為0. 真值為0. 真值為1. 注意: p, q是真命題, r是假命題. 1.16 1.17 1.18 1.19 略 略 略 用真值表判斷下列公式的類型: p ?q ? r ? ) ? 離散數學習題解 , , 為重言式. 為矛盾式. , , 為可滿足式. 1.20 1.21 1.22 1.23 1.24 1.25 1.26 1.27 1.28 1.29 1.30 略 略 略 略 略 略 略 略 略 略 略 5 pq, 其中, p: 2+24, q: 地球靜止不動, 真值為0.

14、 pq, 其中, p: 2+24, q: 地球運動不止, 真值為1. ?p?q, 其中, p: 地球上有樹木, q: 人類能生存, 真值為1. ?pq, 其中, p: 地球上有水, q是無理數, 真值為1. 離散數學習題解 6 2.1. 設公式 A = pq, B = p?q, 用真值表驗證公式 A 和 B 適合德摩根律: p q ? ? ?A?B. A =pq B =p?q ? ?A?B 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 因為?和?A?B的真值表相同, 所以它們等值. 2.2. 略 2.3. 用等值演算法判斷下列公式的類型, 對不是重言式的可滿足式, 再用真值表法求

15、出成真賦值. ? ) ? ? ? q) ? ? ? pq?q ? p0 ? 0 ? 0. 矛盾式. 重言式. ? ? ? ?p?q pr易見, 是可滿足式, 但不是重言式. 成真賦值為: 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 pr1 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 ?

16、p. ? 離散數學習題解 ? ) ? ) ? ? ? ? ? ? ? 2.5. 求下列公式的主析取范式, 并求成真賦值: ? qr ) ? ? ? ?p?q ?q p? ?p?q ?q p? ?q p ? p?q ?p?q pq p?q ? m10 m00 m11 m10 ? m0 m2 m3 ? . 成真賦值為 00, 10, 11. 主析取范式為0, 無成真賦值, 為矛盾式. m0m1m2m3m4m5m6m7, 為重言式. 2.6. 求下列公式的主合取范式, 并求成假賦值: ? ?p ) r ? ?p ? ? ?p ? qp ?p ? q0 ? 0 ? M0M1M2M3 這是矛盾式. 成假

17、賦值為 00, 01, 10, 11. M4, 成假賦值為100. 主合取范式為1, 為重言式. 7 離散數學習題解 2.7. 求下列公式的主析取范式, 再用主析取范式求合取范式: r m1m3m5m6m7?M0M2M4 m0m1m3m7?M2M4M5M6 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. 略 2.15. 用主析取范式判斷下列公式

18、是否等值: r與q r ? ? r ? ? r ? p?q r ? p?q r ? p?qr p?q?r pqr p?qr ?pqr ?p?qr = m101 m100 m111 m101 m011 m001 ? m1 m3 m4 m5 m7 = . 而 q ? ?q ? ?q ?p r ? ?q ?p r ? 離散數學習題解 = 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 ? 與? r) ?m1m3m4m

19、5m7 q ?m0m1m2m3m4m5m7 所以 r) k q ? ?m0m1m2 ? ?m0 所以? k ? 2.17. 用主合取范式判斷下列公式是否等值: p 與? r p 與 r p ?M6 ? r?M6 所以p ? ? r p ?M6 r?M0M1M2M6 所以p k r 2.18. 略 2.19. 略 2.20. 將下列公式化成與之等值且僅含 ?, 中聯結詞的公式. ?r. 注意到A?B ? 和 AB ? ? ? ?以及 AB ? ?AB. ?r 離散數學習題解 ? ? r) ) ? ? r) ?) 注)聯結詞越少, 公式越長. 2.21. 證明: ? , ? . ? ? ? ? ?

20、 . ? ? ? ? ? . 2.22. 略 2.23. 略 2.24. 略 2.25. 設A, B, C為任意的命題公式. 若AC?BC, 舉例說明 A?B不一定成立. 已知AC?BC, 舉例說明A?B不一定成立. 已知?A?B, 問: A?B一定成立嗎? 取 A = p, B = q, C = 1 , 有 AC ? BC, 但 A k B. 10 取 A = p, B = q, C = 0 , 有 AC ? BC, 但 A k B. 好的例子是簡單, 具體, 而又說明問題的. 一定. 2.26. 略 2.27. 某電路中有一個燈泡和三個開關A,B,C. 已知在且僅在下述四種情況下燈亮: C

21、的扳鍵向上, A,B的扳鍵向下. A的扳鍵向上, B,C的扳鍵向下. B,C的扳鍵向上, A的扳鍵向下. A,B的扳鍵向上, C的扳鍵向下. 設F為1表示燈亮, p,q,r分別表示A,B,C的扳鍵向上. 求F的主析取范式. 在聯結詞完備集?, 上構造F. 在聯結詞完備集?, ,?上構造F. 由條件-可知, F的主析取范式為 F? ?m1m4m3m6 ?m1m3m4m6 離散數學習題解 先化簡公式 F? ?q ) q ) ? ) ? ? ? ) F? ? ? ? ? ? ? 11 2.28. 一個排隊線路, 輸入為A,B,C, 其輸出分別為FA,FB,FC. 本線路中, 在同一時間內只能有一個信

22、號通過, 若同時有兩個和兩個以上信號申請輸出時, 則按A,B,C的順序輸出. 寫出FA,FB,FC在聯結詞完備集?, 中的表達式. 根據題目中的要求, 先寫出FA,FB,FC的真值表 由真值表可先求出他們的主析取范式, 然后化成?, 中的公式 FA?m4m5m6m7 ?p FB?m2m3 ?pq FC?m1 ?p?qr 2.29. 略 2.30. 略 離散數學習題解 12 3.1. 略 3.2. 略 3.3. 略 3.4. 略 3.5. 略 3.6. 判斷下面推理是否正確. 先將簡單命題符號化, 再寫出前提, 結論, 推理的形式結構和判斷過程: 若今天是星期一, 則明天是星期三；今天是星期一.

23、 所以明天是星期三. 若今天是星期一, 則明天是星期二；明天是星期二. 所以今天是星期一. 若今天是星期一, 則明天是星期三；明天不是星期三. 所以今天不是星期一. 若今天是星期一, 則明天是星期二；今天不是星期一. 所以明天不是星期二. 若今天是星期一, 則明天是星期二或星期三. 今天是星期一當且僅當明天是星期三；今天不是星期一. 所以明天不是星期三. 設p: 今天是星期一, q: 明天是星期二, r: 明天是星期三. 推理的形式結構為 pr 此形式結構為重言式, 即 p?r 所以推理正確. 推理的形式結構為 qp 此形式結構不是重言式, 故推理不正確. 推理形式結構為 ?r?p 此形式結構

24、為重言式, 即 ?r?p 故推理正確. 推理形式結構為 ?p?q 此形式結構不是重言式, 故推理不正確. 推理形式結構為 p 它不是重言式, 故推理不正確. 推理形式結構為 ?p?r 離散數學習題解 此形式結構為重言式, 即 ?p?r 故推理正確. 13 推理是否正確, 可用多種方法證明. 證明的方法有真值表法, 等式演算法. 證明推理正確還可用構造證明法. 下面用構造證明法證明推理正確. 前提: p?r, ?p 結論: ?r 證明: p?r 前提引入 置換 rp 化簡律 ?p 前提引入 ?r 拒取式 所以, 推理正確. 3.7. 略 3.8. 略 3.9. 用三種方法證明下面推理是正確的:

25、若 a 是奇數, 則 a 不能被2 整除. 若 a 是偶數, 則 a 能被 2 整除. 因此, 如果 a 是偶數, 則 a 不是奇數. 令 p: a 是奇數; q: a 能被2 整除; r: a 是偶數. 前提: p ?q, r q. 結論: r ?p. 形式結構: . 3.10.略 3.11.略 3.12.略 3.13.略 3.14.在自然推理系統P中構造下面推理的證明: 前提: p , p, q 結論: rs 前提: pq, ? , r 結論: ?p 前提: pq 結論: p 前提: qp, q?s, s?t, tr 結論: pq 前提: pr, qs, pq 離散數學習題解 結論: rs

26、 前提: ?pr, ?qs, pq 結論: t 證明: 14 p p qr q r rs 前提引入 前提引入 假言推理 前提引入 假言推理 附加律 證明: ? ?q?r r ?q pq ?p 前提引入 置換 前提引入 析取三段論 前提引入 拒取式 證明: pq ?pq ?p p 前提引入 置換 置換 置換 置換 也可以用附加前提證明法, 更簡單些. 證明: s?t ts tr t s q?s sq q 前提引入 置換 化簡 前提引入 化簡 假言推理 前提引入 置換 化簡 假言推理 離散數學習題解 11 12 13 15q p p pq 前提引入 11假言推理 12合取 證明: pr qs pq

27、 p q r s rs 前提引入 前提引入 前提引入 化簡 化簡 假言推理 假言推理 合取 證明: t ?pr pq p r rs 附加前提引入 前提引入 前提引入 化簡 析取三段論 附加 說明: 證明中, 附加提前t, 前提?qs沒用上. 這仍是正確的推理. 3.15.在自然推理系統P中用附加前提法證明下面各推理: 前提: p , sp, q 結論: sr 前提: , u 結論: pu 證明: s sp p p qr q r 附加前提引入 前提引入 假言推理 前提引入 假言推理 前提引入 假言推理 離散數學習題解 證明: 16 P pq rs S st u u 附加前提引入 附加 前提引入

28、假言推理 化簡 附加 前提引入 假言推理 3.16.在自然推理系統P中用歸謬法證明下面推理: 前提: p?q, ?rq, r?s 結論: ?p 前提: pq, pr, qs 結論: rs 證明: P p?q ?q ?rq ?r r?s r ?rr 結論否定引入 前提引入 假言推理 前提引入 析取三段論 前提引入 化簡 合取 為矛盾式, 由歸謬法可知, 推理正確. 證明: ? pq pr qs rs ? 結論否定引入 前提引入 前提引入 前提引入 構造性二難 合取 離散數學習題解 為矛盾式, 所以推理正確. 3.17.P53 17. 在自然推理系統 P 中構造下面推理的證明: 17 只要 A 曾

29、到過受害者房間并且11點以前沒用離開, A 就犯了謀殺罪. A 曾到過受害者房間. 如果 A 在11點以前離開, 看門人會看到他. 看門人沒有看到他. 所以 A 犯了謀殺罪. 令 p: A 曾到過受害者房間; q: A 在11點以前離開了; r: A 就犯了謀殺罪; s:看門人看到 A. 前提: p?q r, p, q s, ?s. 結論: r. 前提: p?q r, p, q s, ?s; 結論: r. 證明: ?s 前提引入 前提引入 q s ?q 拒取 p 前提引入 合取 前提引入 假言推理 p?q p?q r r 3.18.在自然推理系統P中構造下面推理的證明. 如果今天是星期六, 我

30、們就要到頤和園或圓明園去玩. 如果頤和園游人太多, 我們就不去頤和園玩. 今天是星期六. 頤和園游人太多. 所以我們去圓明園玩. 如果小王是理科學生, 他的數學成績一定很好. 如果小王不是文科生, 他必是理科生. 小王的數學成績不好. 所以小王是文科學生. 明天是晴天, 或是雨天；若明天是晴天, 我就去看電影；若我看電影, 我就不看書. 所以, 如果我看書, 則明天是雨天. 令 p: 今天是星期六; q: 我們要到頤和園玩; r: 我們要到圓明園玩; s:頤和園游人太多. 前提: p , s ?q, p, s. 結論: r. p p qr qr s s ?q ?q r 前提引入 前提引入 假言

31、推理 前提引入 ppqr qrrss ?q ?q 前提引入 假言推理 析取三段論 的證明樹 離散數學習題解 令p: 小王是理科生, q: 小王是文科生, r: 小王的數學成績很好. 前提: pr, ?qp, ?r 結論: q 證明: 18 pr ?r ?p ?qp q 前提引入 前提引入 拒取式 前提引入 拒取式 ? q? p的證明樹pq ?rpr 令p: 明天是晴天, q: 明天是雨天, r: 我看電影, s: 我看書. 前提: pq, pr, r?s 結論: sq 證明: s r?s ?r pr ?p pq q 附加前提引入 前提引入 拒取式 前提引入 拒取式 前提引入 析取三段論 離散數

32、學習題解 19 4.1. 將下面命題用0元謂詞符號化: 小王學過英語和法語. 除非李建是東北人, 否則他一定怕冷. 令 F: x 學過英語; F: x 學過法語; a: 小王. 符號化為 FF. 或進一步細分, 令 L: x 學過 y; a: 小王; b1: 英語; b2: 法語. 則符號化為 LL. 令 F: x 是東北人; G: x 怕冷; a: 李建. 符號化為 ?FG 或 ?GF. 或進一步細分, 令 H: x 是 y 地方人; G: x 怕冷; a: 小王; b: 東北. 則符號化為 ?HG 或 ?G H. 4.2. 在一階邏輯中將下面命題符號化, 并分別討論個體域限制為,時命題的真

33、值: 凡有理數都能被2整除. 有的有理數能被2整除. 其中個體域為有理數集合, 個體域為實數集合. 中, ?xF, 其中, F: x能被2整除, 真值為0. 中, ?x F), 其中, G: x為有理數, F同中, 真值為0. 中, ?xF, 其中, F: x能被2整除, 真值為1. 中, ?x F), 其中, F同中, G: x為有理數, 真值為1. 中, ?x 中, ?x : x為實數, 真值為1. 中, ?x, 真值為1. 中, ?x ), 其中, F: x為實數, 真值為1. 4.4. 在一階邏輯中將下列命題符號化: 沒有不能表示成分數的有理數. 在北京賣菜的人不全是外地人. 離散數學

34、習題解 烏鴉都是黑色的. 有的人天天鍛煉身體. 沒指定個體域, 因而使用全總個體域. ?x ?G)或?x G), 其中, F: x為有理數, G: x能表示成分數. ?x G)或?x ?G), 其中, F: x在北京賣菜, G: x是外地人. ?x G), 其中, F: x是烏鴉, G: x是黑色的. ?x G), 其中, F: x是人, G: x天天鍛煉身體. 4.5. 在一階邏輯中將下列命題符號化: 火車都比輪船快. 有的火車比有的汽車快. 不存在比所有火車都快的汽車. “凡是汽車就比火車慢”是不對的. 因為沒指明個體域, 因而使用全總個體域 ?x?y G H), 其中, F: x是火車,

35、 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是火車, H:x比y快. ?x?y G H) 或?x?y G ?H ), 其中, F: x是汽車, G: y是火車, H:x比y慢. 4.6. 略 4.7. 將下列各公式翻譯成自然語言, 個體域為整數集 ?, 并判斷各命題的真假. ?x?y?z; ?x?y. 可選的翻譯: “任意兩個整數的差是整數.” “對于任意兩個整數, 都存在第三個整數, 它等于這兩個整數相減.” “對于任意整數 x 和 y, 都存

36、在整數 z, 使得 x ? y = z.” 20選, 直接翻譯, 無需數理邏輯以外的知識. 以下翻譯意思相同, 都是錯的: n “有個整數, 它是任意兩個整數的差.” o “存在一個整數, 對于任意兩個整數, 第一個整數都等于這兩個整數相減.” p “存在整數 z, 使得對于任意整數 x 和 y, 都有 x ? y = z.” 這3個句子都可以符號化為 ?z?x?y. ;量詞順序不可隨意調換. 可選的翻譯: 離散數學習題解 “每個整數都有一個倒數.” “對于每個整數, 都能找到另一個整數, 它們相乘結果是零.” “對于任意整數 x, 都存在整數 y, 使得 x?y = z.” 21 選, 是直

37、接翻譯, 無需數理邏輯以外的知識. 4.8. 指出下列公式中的指導變元, 量詞的轄域, 各個體變項的自由出現和約束出現: ?x?y G) ?xH 前件 ?x?yG) 中, ? 的指導變元是 x, ? 的轄域是 ?yG); ? 的指導變元是 y, ? 的轄域是 G). 后件 ?xH 中, ? 的指導變元是 x, ? 的轄域是 H. 整個公式中, x 約束出現兩次, y 約束出現兩次, 自由出現一次; z 自由出現兩次. 4.9. 給定解釋I如下: 個體域DI為實數集合. DI中特定元素?a =0. 特定函數?f =x?y, x,yDI. 特定謂詞?F: x=y,?G: x 說明下列公式在I下的含

38、義, 并指出各公式的真值: ?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上函數?f =x+y,?g =xy. D上謂詞?F : x=y. 說明下列公式在I下的含義, 并指出各公式的真值: ?xF,x) ?x?y,y) F,x) ?x?y?z,z) ?xF,g) 離散數學習題解 ?x, 真值為0. ?x?y ), 真值為0. ?x?y?z,真值為1. ?x,真值為1. 4.11.判斷下列各式的類型

39、: F F). ?x?yF ?x?yF. ?x?y F). 是命題重言式 p 的代換實例, 所以是永真式. 在某些解釋下為假, 在某些解釋下為真, 所以是非永真式的可滿足式. 同. 4.12.P69 12. 設 I 為一個任意的解釋, 在解釋 I 下, 下面哪些公式一定是命題? ?xF ?yG. ?x G) ?y H). ?x ?yG). ?x G) H. , 一定是命題, 因為它們是閉式. 4.13.略 4.14.證明下面公式既不是永真式也不是矛盾式: ?x ?y H) ?x?y G H) 取個體域為全總個體域. 解釋I1: F: x為有理數, G: y為整數, H: x 在I1下: ?x

40、?y H)為真命題, 所以該公式不是矛盾式. 解釋I2: F,G同I1, H: y整除x. 在I2下: ?x ?y H)為假命題, 所以該公式不是永真式. 請讀者給出不同解釋, 使其分別為成真和成假的命題即可. 4.15. 給出一個非閉式的永真式. 給出一個非閉式的永假式. 給出一個非閉式的可滿足式, 但不是永真式. F ?F. F ?F. ?x F). 22 離散數學習題解 23 5.1. 略 5.2. 設個體域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) ?x

41、F ?yG ? F F) G G) ?xF ?yG ? F F) G G) ?x ?yG) ?xF ?yG ? F F) G G) 5.3. 設個體域D=1,2, 請給出兩種不同的解釋I1和I2, 使得下面公式在I1下都是真命題, 而在I2下都是假 命題. ?x G) ?x G) I1: F:x2,G:x3 F,F,G,G均為真, 所以 ?x G) ? G G)為真. I2: F同I1,G:x0 則F,F均為真, 而G,G均為假, ?x G)為假. 留給讀者自己做. 5.4. 略 5.5. 給定解釋I如下: 個體域D=3,4. ?f 為?f =4,?f =3. ?F為?F=?F=0,?F=?F

42、=1. 離散數學習題解 試求下列公式在I下的真值: ?x?yF ?x?yF ?x?y F,f) ?x?yF ? F) F) ? ?1 ?x?yF ? F) F) ? ?0 ?x?y F,f) ? F,f) F,f) F,f) F,f) ? ?1 5.6. 略 5.7. 略 5.8. 在一階邏輯中將下列命題符號化, 要求用兩種不同的等值形式. 沒有小于負數的正數. 相等的兩個角未必都是對頂角. 令 F: x 小于負數, G: x 是正數. 符合化為: ?x G) ? ?x ?G). 24 令 F: x 是角, H: x 和 y 是相等的, L: x 與 y 是對頂角. 符合化為: ?x?y F

43、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) 離散數學習題解 ? ?x?y G). ?xF ? ?xG ? ?xG) ?xF) ? ?x2G) ?x4F) ? ?x1?x2 G) ?x3?x4 F) ? ?x1?x2?x3?x4 G) F). 5.13.將下列命題符號化, 要求符號化的公式全為前束范式: 有的汽車比有的火車跑得快. 有的火車比所有的汽車跑得快. 說所有的火車比所有的

44、汽車跑得快是不對的. 說有的飛機比有的汽車慢是不對的. 令 F: x 是汽車, G: y 是火車, H: x 比 y 跑得快. ?x ?y H) ? ?x?y G H). 25 令 F: x 是火車, G: y 是汽車, 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 是飛機, G: y 是汽車, H: x 比 y 跑得慢. ? ?x ?y H) ? ? ?x?y

45、G H) ? ?x?y ? G H) ? ?x?y G ?H). 5.14.略 5.15.在自然推理系統F中構造下面推理的證明: 前提: ?xF ?y G) R), ?xF 結論: ?xR. 前提: ?x R), ?xF 結論: ?x R) 前提: ?x G), ?xG 結論: ?xF 前提: ?x G), ?x ?R), ?xR 結論: ?xF 離散數學習題解 證明: 26 ?xF ?y 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 前提引入 析取三段論 析