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

離散數(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, 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, 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, 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, 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, 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, 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, 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, 27, 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 離散數(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 略 略 將下列命題符號(hào)化, 并給出各命題的真值: 2+24當(dāng)且僅當(dāng)3+36. 2+24的充要條件是3+36. 2+24與3+36互為充要條件. 若2+24, 則3+36, 反之亦然. p?q, 其中, p: 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 將下列命題符號(hào)化, 并給出各命題的真值: 若今天是星期一, 則明天是星期二. 只有今天是星期一, 明天才是星期二. 今天是星期一當(dāng)且僅當(dāng)明天是星期二. 若今天是星期一, 則明天是星期三. 令 p: 今天是星期一; q: 明天是星期二; r: 明天是星期三. pq ? 1. qp ? 1. p?q ? 1. pr當(dāng)p ? 0時(shí)為真; p ? 1 時(shí)為假. 1.14 將下列命題符號(hào)化. 劉曉月跑得快, 跳得高. 老王是山東人或河北人. 因?yàn)樘鞖饫? 所以我穿了羽絨服. 王歡與李樂組成一個(gè)小組. 李辛與李末是兄弟. 王強(qiáng)與劉威都學(xué)過法語. 他一面吃飯, 一面聽音樂. 如果天下大雨, 他就乘班車上班. 只有天下大雨, 他才乘班車上班. 除非天下大雨, 他才乘班車上班. 下雪路滑, 他遲到了. 2與4都是素?cái)?shù), 這是不對(duì)的. “2或4是素?cái)?shù), 這是不對(duì)的”是不對(duì)的. 離散數(shù)學(xué)習(xí)題解 pq, 其中, p: 劉曉月跑得快, q: 劉曉月跳得高. pq, 其中, p: 老王是山東人, q: 老王是河北人. pq, 其中, p: 天氣冷, q: 我穿了羽絨服. p, 其中, p: 王歡與李樂組成一個(gè)小組, 是簡(jiǎn)單命題. p, 其中, p: 李辛與李末是兄弟. pq, 其中, p: 王強(qiáng)學(xué)過法語, q: 劉威學(xué)過法語. pq, 其中, p: 他吃飯, q: 他聽音樂. pq, 其中, p: 天下大雨, q: 他乘班車上班. pq, 其中, p: 他乘班車上班, q: 天下大雨. pq, 其中, p: 他乘班車上班, q: 天下大雨. pq, 其中, p: 下雪路滑, q: 他遲到了. ? 或?p?q, 其中, p: 2是素?cái)?shù), q: 4是素?cái)?shù). ? 或pq, 其中, p: 2是素?cái)?shù), q: 4是素?cái)?shù). 1.15 設(shè)p: 2+3=5. 4 q: 大熊貓產(chǎn)在中國(guó). r: 復(fù)旦大學(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í)題解 , , 為重言式. 為矛盾式. , , 為可滿足式. 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: 地球靜止不動(dòng), 真值為0. pq, 其中, p: 2+24, q: 地球運(yùn)動(dòng)不止, 真值為1. ?p?q, 其中, p: 地球上有樹木, q: 人類能生存, 真值為1. ?pq, 其中, p: 地球上有水, q是無理數(shù), 真值為1. 離散數(shù)學(xué)習(xí)題解 6 2.1. 設(shè)公式 A = pq, B = p?q, 用真值表驗(yàn)證公式 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 因?yàn)?和?A?B的真值表相同, 所以它們等值. 2.2. 略 2.3. 用等值演算法判斷下列公式的類型, 對(duì)不是重言式的可滿足式, 再用真值表法求出成真賦值. ? ) ? ? ? 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 ? p. ? 離散數(shù)學(xué)習(xí)題解 ? ) ? ) ? ? ? ? ? ? ? 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 這是矛盾式. 成假賦值為 00, 01, 10, 11. M4, 成假賦值為100. 主合取范式為1, 為重言式. 7 離散數(shù)學(xué)習(xí)題解 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. 用主析取范式判斷下列公式是否等值: 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 ? 離散數(shù)學(xué)習(xí)題解 = m0 m1 m4 m5 m0 m1 m2 m3 m1 m3 m5 m7 ? m0 m1 m2 m3 m4 m5 m7 ? . 兩個(gè)公式的主吸取范式不同, 所以 rk q . 9 2.16. 用主析取范式判斷下列公式是否等值: r與q ? 與? r) ?m1m3m4m5m7 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. 將下列公式化成與之等值且僅含 ?, 中聯(lián)結(jié)詞的公式. ?r. 注意到A?B ? 和 AB ? ? ? ?以及 AB ? ?AB. ?r 離散數(shù)學(xué)習(xí)題解 ? ? r) ) ? ? r) ?) 注)聯(lián)結(jié)詞越少, 公式越長(zhǎng). 2.21. 證明: ? , ? . ? ? ? ? ? . ? ? ? ? ? . 2.22. 略 2.23. 略 2.24. 略 2.25. 設(shè)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. 好的例子是簡(jiǎn)單, 具體, 而又說明問題的. 一定. 2.26. 略 2.27. 某電路中有一個(gè)燈泡和三個(gè)開關(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? ?m1m4m3m6 ?m1m3m4m6 離散數(shù)學(xué)習(xí)題解 先化簡(jiǎn)公式 F? ?q ) q ) ? ) ? ? ? ) F? ? ? ? ? ? ? 11 2.28. 一個(gè)排隊(duì)線路, 輸入為A,B,C, 其輸出分別為FA,FB,FC. 本線路中, 在同一時(shí)間內(nèi)只能有一個(gè)信號(hào)通過, 若同時(shí)有兩個(gè)和兩個(gè)以上信號(hào)申請(qǐng)輸出時(shí), 則按A,B,C的順序輸出. 寫出FA,FB,FC在聯(lián)結(jié)詞完備集?, 中的表達(dá)式. 根據(jù)題目中的要求, 先寫出FA,FB,FC的真值表 由真值表可先求出他們的主析取范式, 然后化成?, 中的公式 FA?m4m5m6m7 ?p FB?m2m3 ?pq FC?m1 ?p?qr 2.29. 略 2.30. 略 離散數(shù)學(xué)習(xí)題解 12 3.1. 略 3.2. 略 3.3. 略 3.4. 略 3.5. 略 3.6. 判斷下面推理是否正確. 先將簡(jiǎn)單命題符號(hào)化, 再寫出前提, 結(jié)論, 推理的形式結(jié)構(gòu)和判斷過程: 若今天是星期一, 則明天是星期三；今天是星期一. 所以明天是星期三. 若今天是星期一, 則明天是星期二；明天是星期二. 所以今天是星期一. 若今天是星期一, 則明天是星期三；明天不是星期三. 所以今天不是星期一. 若今天是星期一, 則明天是星期二；今天不是星期一. 所以明天不是星期二. 若今天是星期一, 則明天是星期二或星期三. 今天是星期一當(dāng)且僅當(dāng)明天是星期三；今天不是星期一. 所以明天不是星期三. 設(shè)p: 今天是星期一, q: 明天是星期二, r: 明天是星期三. 推理的形式結(jié)構(gòu)為 pr 此形式結(jié)構(gòu)為重言式, 即 p?r 所以推理正確. 推理的形式結(jié)構(gòu)為 qp 此形式結(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é)構(gòu)為 ?p?r 離散數(shù)學(xué)習(xí)題解 此形式結(jié)構(gòu)為重言式, 即 ?p?r 故推理正確. 13 推理是否正確, 可用多種方法證明. 證明的方法有真值表法, 等式演算法. 證明推理正確還可用構(gòu)造證明法. 下面用構(gòu)造證明法證明推理正確. 前提: p?r, ?p 結(jié)論: ?r 證明: p?r 前提引入 置換 rp 化簡(jiǎn)律 ?p 前提引入 ?r 拒取式 所以, 推理正確. 3.7. 略 3.8. 略 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 結(jié)論: rs 前提: pq, ? , r 結(jié)論: ?p 前提: pq 結(jié)論: p 前提: qp, q?s, s?t, tr 結(jié)論: pq 前提: pr, qs, pq 離散數(shù)學(xué)習(xí)題解 結(jié)論: rs 前提: ?pr, ?qs, pq 結(jié)論: t 證明: 14 p p qr q r rs 前提引入 前提引入 假言推理 前提引入 假言推理 附加律 證明: ? ?q?r r ?q pq ?p 前提引入 置換 前提引入 析取三段論 前提引入 拒取式 證明: pq ?pq ?p p 前提引入 置換 置換 置換 置換 也可以用附加前提證明法, 更簡(jiǎn)單些. 證明: s?t ts tr t s q?s sq q 前提引入 置換 化簡(jiǎn) 前提引入 化簡(jiǎn) 假言推理 前提引入 置換 化簡(jiǎn) 假言推理 離散數(shù)學(xué)習(xí)題解 11 12 13 15q p p pq 前提引入 11假言推理 12合取 證明: pr qs pq p q r s rs 前提引入 前提引入 前提引入 化簡(jiǎn) 化簡(jiǎn) 假言推理 假言推理 合取 證明: t ?pr pq p r rs 附加前提引入 前提引入 前提引入 化簡(jiǎn) 析取三段論 附加 說明: 證明中, 附加提前t, 前提?qs沒用上. 這仍是正確的推理. 3.15.在自然推理系統(tǒng)P中用附加前提法證明下面各推理: 前提: p , sp, q 結(jié)論: sr 前提: , u 結(jié)論: pu 證明: s sp p p qr q r 附加前提引入 前提引入 假言推理 前提引入 假言推理 前提引入 假言推理 離散數(shù)學(xué)習(xí)題解 證明: 16 P pq rs S st u u 附加前提引入 附加 前提引入 假言推理 化簡(jiǎn) 附加 前提引入 假言推理 3.16.在自然推理系統(tǒng)P中用歸謬法證明下面推理: 前提: p?q, ?rq, r?s 結(jié)論: ?p 前提: pq, pr, qs 結(jié)論: rs 證明: P p?q ?q ?rq ?r r?s r ?rr 結(jié)論否定引入 前提引入 假言推理 前提引入 析取三段論 前提引入 化簡(jiǎn) 合取 為矛盾式, 由歸謬法可知, 推理正確. 證明: ? pq pr qs rs ? 結(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)以前離開, 看門人會(huì)看到他. 看門人沒有看到他. 所以 A 犯了謀殺罪. 令 p: A 曾到過受害者房間; q: A 在11點(diǎn)以前離開了; r: A 就犯了謀殺罪; s:看門人看到 A. 前提: p?q 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)造下面推理的證明. 如果今天是星期六, 我們就要到頤和園或圓明園去玩. 如果頤和園游人太多, 我們就不去頤和園玩. 今天是星期六. 頤和園游人太多. 所以我們?nèi)A明園玩. 如果小王是理科學(xué)生, 他的數(shù)學(xué)成績(jī)一定很好. 如果小王不是文科生, 他必是理科生. 小王的數(shù)學(xué)成績(jī)不好. 所以小王是文科學(xué)生. 明天是晴天, 或是雨天；若明天是晴天, 我就去看電影；若我看電影, 我就不看書. 所以, 如果我看書, 則明天是雨天. 令 p: 今天是星期六; q: 我們要到頤和園玩; r: 我們要到圓明園玩; s:頤和園游人太多. 前提: p , s ?q, p, s. 結(jié)論: r. p p qr qr s s ?q ?q r 前提引入 前提引入 假言推理 前提引入 ppqr qrrss ?q ?q 前提引入 假言推理 析取三段論 的證明樹 離散數(shù)學(xué)習(xí)題解 令p: 小王是理科生, q: 小王是文科生, r: 小王的數(shù)學(xué)成績(jī)很好. 前提: pr, ?qp, ?r 結(jié)論: q 證明: 18 pr ?r ?p ?qp q 前提引入 前提引入 拒取式 前提引入 拒取式 ? q? p的證明樹pq ?rpr 令p: 明天是晴天, q: 明天是雨天, r: 我看電影, s: 我看書. 前提: pq, pr, r?s 結(jié)論: sq 證明: s r?s ?r pr ?p pq q 附加前提引入 前提引入 拒取式 前提引入 拒取式 前提引入 析取三段論 離散數(shù)學(xué)習(xí)題解 19 4.1. 將下面命題用0元謂詞符號(hào)化: 小王學(xué)過英語和法語. 除非李建是東北人, 否則他一定怕冷. 令 F: x 學(xué)過英語; F: x 學(xué)過法語; a: 小王. 符號(hào)化為 FF. 或進(jìn)一步細(xì)分, 令 L: x 學(xué)過 y; a: 小王; b1: 英語; b2: 法語. 則符號(hào)化為 LL. 令 F: x 是東北人; G: x 怕冷; a: 李建. 符號(hào)化為 ?FG 或 ?GF. 或進(jìn)一步細(xì)分, 令 H: x 是 y 地方人; G: x 怕冷; a: 小王; b: 東北. 則符號(hào)化為 ?HG 或 ?G H. 4.2. 在一階邏輯中將下面命題符號(hào)化, 并分別討論個(gè)體域限制為,時(shí)命題的真值: 凡有理數(shù)都能被2整除. 有的有理數(shù)能被2整除. 其中個(gè)體域?yàn)橛欣頂?shù)集合, 個(gè)體域?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 ), 其中, F: x為實(shí)數(shù), 真值為1. 4.4. 在一階邏輯中將下列命題符號(hào)化: 沒有不能表示成分?jǐn)?shù)的有理數(shù). 在北京賣菜的人不全是外地人. 離散數(shù)學(xué)習(xí)題解 烏鴉都是黑色的. 有的人天天鍛煉身體. 沒指定個(gè)體域, 因而使用全總個(gè)體域. ?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), 其中, F: x是人, G: x天天鍛煉身體. 4.5. 在一階邏輯中將下列命題符號(hào)化: 火車都比輪船快. 有的火車比有的汽車快. 不存在比所有火車都快的汽車. “凡是汽車就比火車慢”是不對(duì)的. 因?yàn)闆]指明個(gè)體域, 因而使用全總個(gè)體域 ?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是火車, H:x比y快. ?x?y G H) 或?x?y G ?H ), 其中, F: x是汽車, G: y是火車, H:x比y慢. 4.6. 略 4.7. 將下列各公式翻譯成自然語言, 個(gè)體域?yàn)檎麛?shù)集 ?, 并判斷各命題的真假. ?x?y?z; ?x?y. 可選的翻譯: “任意兩個(gè)整數(shù)的差是整數(shù).” “對(duì)于任意兩個(gè)整數(shù), 都存在第三個(gè)整數(shù), 它等于這兩個(gè)整數(shù)相減.” “對(duì)于任意整數(shù) x 和 y, 都存在整數(shù) z, 使得 x ? y = z.” 20選, 直接翻譯, 無需數(shù)理邏輯以外的知識(shí). 以下翻譯意思相同, 都是錯(cuò)的: n “有個(gè)整數(shù), 它是任意兩個(gè)整數(shù)的差.” o “存在一個(gè)整數(shù), 對(duì)于任意兩個(gè)整數(shù), 第一個(gè)整數(shù)都等于這兩個(gè)整數(shù)相減.” p “存在整數(shù) z, 使得對(duì)于任意整數(shù) x 和 y, 都有 x ? y = z.” 這3個(gè)句子都可以符號(hào)化為 ?z?x?y. ;量詞順序不可隨意調(diào)換. 可選的翻譯: 離散數(shù)學(xué)習(xí)題解 “每個(gè)整數(shù)都有一個(gè)倒數(shù).” “對(duì)于每個(gè)整數(shù), 都能找到另一個(gè)整數(shù), 它們相乘結(jié)果是零.” “對(duì)于任意整數(shù) x, 都存在整數(shù) y, 使得 x?y = z.” 21 選, 是直接翻譯, 無需數(shù)理邏輯以外的知識(shí). 4.8. 指出下列公式中的指導(dǎo)變?cè)? 量詞的轄域, 各個(gè)體變項(xiàng)的自由出現(xiàn)和約束出現(xiàn): ?x?y G) ?xH 前件 ?x?yG) 中, ? 的指導(dǎo)變?cè)?x, ? 的轄域是 ?yG); ? 的指導(dǎo)變?cè)?y, ? 的轄域是 G). 后件 ?xH 中, ? 的指導(dǎo)變?cè)?x, ? 的轄域是 H. 整個(gè)公式中, x 約束出現(xiàn)兩次, y 約束出現(xiàn)兩次, 自由出現(xiàn)一次; z 自由出現(xiàn)兩次. 4.9. 給定解釋I如下: 個(gè)體域DI為實(shí)數(shù)集合. DI中特定元素?a =0. 特定函數(shù)?f =x?y, x,yDI. 特定謂詞?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如下: 個(gè)體域D=. D中特定元素?a=2. D上函數(shù)?f =x+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). 是命題重言式 p 的代換實(shí)例, 所以是永真式. 在某些解釋下為假, 在某些解釋下為真, 所以是非永真式的可滿足式. 同. 4.12.P69 12. 設(shè) I 為一個(gè)任意的解釋, 在解釋 I 下, 下面哪些公式一定是命題? ?xF ?yG. ?x G) ?y H). ?x ?yG). ?x G) H. , 一定是命題, 因?yàn)樗鼈兪情]式. 4.13.略 4.14.證明下面公式既不是永真式也不是矛盾式: ?x ?y H) ?x?y G H) 取個(gè)體域?yàn)槿倐€(gè)體域. 解釋I1: F: x為有理數(shù), G: y為整數(shù), H: x 在I1下: ?x ?y H)為真命題, 所以該公式不是矛盾式. 解釋I2: F,G同I1, H: y整除x. 在I2下: ?x ?y H)為假命題, 所以該公式不是永真式. 請(qǐng)讀者給出不同解釋, 使其分別為成真和成假的命題即可. 4.15. 給出一個(gè)非閉式的永真式. 給出一個(gè)非閉式的永假式. 給出一個(gè)非閉式的可滿足式, 但不是永真式. F ?F. F ?F. ?x F). 22 離散數(shù)學(xué)習(xí)題解 23 5.1. 略 5.2. 設(shè)個(gè)體域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 F) G G) ?x ?yG) ?xF ?yG ? F F) G G) 5.3. 設(shè)個(gè)體域D=1,2, 請(qǐng)給出兩種不同的解釋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如下: 個(gè)體域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) ? F,f) F,f) F,f) F,f) ? ?1 5.6. 略 5.7. 略 5.8. 在一階邏輯中將下列命題符號(hào)化, 要求用兩種不同的等值形式. 沒有小于負(fù)數(shù)的正數(shù). 相等的兩個(gè)角未必都是對(duì)頂角. 令 F: x 小于負(fù)數(shù), G: x 是正數(shù). 符合化為: ?x G) ? ?x ?G). 24 令 F: x 是角, H: x 和 y 是相等的, L: x 與 y 是對(duì)頂角. 符合化為: ?x?y F 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) ? ?x2G) ?x4F) ? ?x1?x2 G) ?x3?x4 F) ? ?x1?x2?x3?x4 G) F). 5.13.將下列命題符號(hào)化, 要求符號(hào)化的公式全為前束范式: 有的汽車比有的火車跑得快. 有的火車比所有的汽車跑得快. 說所有的火車比所有的汽車跑得快是不對(duì)的. 說有的飛機(jī)比有的汽車慢是不對(duì)的. 令 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). ;錯(cuò)誤的答案: ?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 ?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 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 假言推理 化簡(jiǎn) 合取 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 前提引入 析取三段論 析