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

3 習(xí)題一 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)化, 并給出各命題的 真值: (1)2+2＝4當(dāng)且僅當(dāng)3+3＝6. (2)2+2＝4的充要條件是3+3≠6. (3)2+2≠4與3+3＝6互為充要條件. (4)若2+2≠4, 則3+3≠6, 反之亦然. (1)p?q, 其中, p: 2+2＝4, q: 3+3＝6, 真值為1. (2)p?q, 其中, p: 2+2＝4, q: 3+3＝6, 真值為0. (3) p?q, 其中, p: 2+2＝4, q: 3+3＝6, 真值為0. (4) p?q, 其中, p: 2+2＝4, q: 3+3＝6, 真值為1. 將下列命題符號(hào)化, 并給出各命題的真值: (1)若今天是星期一, 則明天是星期二. (2)只有今天是星期一, 明天才是星期二. (3)今天是星期一當(dāng)且僅當(dāng)明天是星期二. (4)若今天是星期一, 則明天是星期三. 令 p: 今天是星期一; q: 明天是星期二; r: 明天是星期三. (1) p→q ? 1. (2) q→p ? 1. (3) p?q ? 1. (4) p→r當(dāng)p ? 0時(shí)為真; p ? 1 時(shí)為假. 將下列 命題符號(hào)化. (1) 劉曉月跑得快, 跳得高. (2)老王是山東人或河北人. (3)因?yàn)樘鞖饫? 所以我穿了羽絨服. (4)王歡與李樂(lè)組成一個(gè)小組. (5)李辛與李末是兄弟. (6)王強(qiáng)與劉威都學(xué)過(guò)法語(yǔ). (7)他一面吃飯, 一面聽(tīng)音樂(lè). (8)如果天下大雨, 他就乘班車上班. (9)只有天下大雨, 他才乘班車上班. (10)除非天下大雨, 他才乘班車上班. (11)下雪路滑, 他遲到了. (12)2與4都是素?cái)?shù), 這是不對(duì)的. (13)“2或4是素?cái)?shù), 這是不對(duì)的”是不對(duì)的. 4 (1)p∧q, 其中, p: 劉曉月跑得快, q: 劉曉月跳得高. (2)p∨q, 其中, p: 老王是山東人, q: 老王是河北人. (3)p→q, 其中, p: 天氣冷, q: 我穿了羽絨服. (4)p, 其中, p: 王歡與李樂(lè)組成一個(gè)小組, 是簡(jiǎn)單命題. (5)p, 其中, p: 李辛與李末是兄弟. (6)p∧q, 其中, p: 王強(qiáng)學(xué)過(guò)法語(yǔ), q: 劉威學(xué)過(guò)法語(yǔ). (7)p∧q, 其中, p: 他吃飯, q: 他聽(tīng)音樂(lè). (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是素?cái)?shù), q: 4是素?cái)?shù). (13) (p∨q)或p∨q, 其中, p: 2是素?cái)?shù), q: 4是素?cái)?shù). 設(shè)p: 2+3=5. q: 大熊貓產(chǎn)在中國(guó). r: 復(fù)旦大學(xué)在廣州. 求下列復(fù)合命題的真值: (1)(p?q) →r (2)(r→ (p∧q)) ? p (3) r→ (p∨q∨r) (4)(p∧q∧r) ? (( p∨q) →r) (1)真值為0. (2)真值為0. (3)真值為0. (4)真值為1. 注意: p, q是真命題, r是假命題. 1.16． 1.17． 1.18． 1.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) 5 (1), (4), (6)為重言式. (3)為矛盾式. (2), (5), (7)為可滿足式. 1.20． 1.21． 1.22． 1.23． 1.24． 1.25． 1.26． 1.27． 1.28． 1.29． 1.30． 1.31． 略 略 略 略 略 略 略 略 略 略 略 將下列 命題符號(hào)化, 并給出各命題的 真值: (1)若3+＝4, 則地球是靜止不動(dòng)的. (2)若3+2＝4, 則地球是運(yùn)動(dòng)不止的. (3)若地球上沒(méi)有樹(shù)木, 則人類不能生存. (4)若地球上沒(méi)有水, 則3是無(wú)理數(shù). (1)p→q, 其中, p: 2+2＝4, q: 地球靜止不動(dòng), 真值為0. (2)p→q, 其中, p: 2+2＝4, q: 地球運(yùn)動(dòng)不止, 真值為1. (3) p→q, 其中, p: 地球上有樹(shù)木, q: 人類能生存, 真值為1. (4) p→q, 其中, p: 地球上有水, q: 3是無(wú)理數(shù), 真值為1. 6 習(xí)題二 2.1. 設(shè)公式 A = p→q, B = p∧q, 用真值表驗(yàn)證公式 A 和 B 適合德摩根律: (A∨B) ? A∧B. A =p→q B =p∧q (A∨B) A∧B 0 0 1 1 0 1 0 1 1 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 因?yàn)?A∨B)和A∧B的真值表相同, 所以它們等值. 2.2. 略 2.3. 用等值演算法判斷下列公式的類型, 對(duì)不是重言式的可滿足式, 再用真值表法求出成真賦值. (1) (p∧q→q) (2)(p→ (p∨q)) ∨ (p→r) (3)(p∨q) → (p∧r) (1) (p∧q→q)? ((p∧q) ∨ q) ? (p ∨ q ∨ q) ? p∧q∧q ? p∧0 ? 0 ? 0. 矛盾式. (2)重言式. (3) (p∨q) → (p∧r) ? (p∨q) ∨ (p∧r) ? p∧q ∨ p∧r易見(jiàn), 是可滿足式, 但不是重言式. 成真賦值為: 000, 001, 101, 111 p ∧ q ∨ p∧r 1 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 0 1 0 1 0 0 0 0 0 1 0 1 2.4. 用等值演算法證明下面等值式: (1) p? (p∧q) ∨ (p∧q) (3) (p?q) ? (p∨q) ∧ (p∧q) (4) (p∧q) ∨ (p∧q) ? (p∨q) ∧ (p∧q) (1) (p∧q) ∨ (p∧q) ? p ∧ (q∨q) ? p ∧ 1 ? p. (3) (p?q) 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 7 ? ((p→q) ∧ (q→p)) ? ((p∨q) ∧ (q∨p)) ? (p∧q) ∨ (q∧p) ? (p∨q) ∧ (p∨p) ∧ (q∨q) ∧ (p∨q) ? (p∨q) ∧ (p∧q) (4) (p∧q) ∨ (p∧q) ? (p∨p) ∧ (p∨q) ∧ (q∨p) ∧ (q∨q) ? (p∨q) ∧ (p∧q) 2.5. 求下列公式的主析取范式, 并求成真賦值: (1)( p→q) → (q∨p) (2) (p→q) ∧q∧r (3)(p∨ (q∧r)) → (p∨q∨r) (1)(p→q) → (q∨p) ? (p∨q) ∨ (q∨p) ? p∧q ∨ q ∨ p? p∧q ∨ q ∨ p(吸收律)? (p∨p)∧q ∨ p∧(q∨q) ? p∧q ∨p∧q ∨ p∧q ∨ p∧q ? m10 ∨ m00 ∨ m11 ∨ m10 ? m0 ∨ m2 ∨ m3 ? ∑(0, 2, 3). 成真賦值為 00, 10, 11. (2)主析取范式為0, 無(wú)成真賦值, 為矛盾式. (3)m0∨m1∨m2∨m3∨m4∨m5∨m6∨m7 , 為重言式. 2.6. 求下列公式的主合取范式, 并求成假賦值: (1) (q→p) ∧p (2)(p∧q) ∨ (p∨r) (3)(p→ (p∨q)) ∨r (1) (q→p) ∧ p ? (q∨p) ∧ p ? q∧p ∧ p ? q∧0 ? 0 ? M0∧M1∧M2∧M3 這是矛盾式. 成假賦值為 00, 01, 10, 11. (2)M4 , 成假賦值為100. (3)主合取范式為1, 為重言式. 8 2.7. 求下列公式的主析取范式, 再用主析取范式求合取范式: (1)(p∧q) ∨r (2)(p→q) ∧ (q→r) (1)m1∨m3∨m5∨m6∨m7?M0∧M2∧M4 (2)m0∨m1∨m3∨m7?M2∧M4∧M5∧M6 2.8. 略 2.9. 用真值表求下面公式的主析取范式. (2) (p→q) → (p?q) (2)從真值表可見(jiàn)成真賦值為01, 10. 于是(p → q) → (p ? q) ? m1 ∨ m2 . 2.10. 略 2.11. 略 2.12. 略 2.13. 略 2.14. 略 2.15. 用主析取范式判斷下列公式是否等值: (1) (p→q) →r與q→ (p→r) (2)(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 ( p → q ) → ( 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 9 ∨(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). 兩個(gè)公式的主吸取范式不同, 所以(p→q) →r 2.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) q→ (p→r) (2) (p∧q) ?m0∨m1∨m2 (p∨q) ?m0 所以 (p∧q) (p∨q) 2.17. 用主合取范式判斷下列公式是否等值: (1)p→ (q→r)與 (p∧q) ∨r (2)p→ (q→r)與(p→q) →r (1) p→ (q→r) ?M6 (p∧q) ∨r?M6 所以p→ (q→r) ? (p∧q) ∨r (2) p→ (q→r) ?M6 (p→q) →r?M0∧M1∧M2∧M6 所以p→ (q→r) (p→q) →r 2.18. 略 2.19. 略 q→ (p→r). 2.20. 將下列公式化成與之等值且僅含 {, →} 中聯(lián)結(jié)詞的公式. (3) (p∧q)?r. 注意到A?B ? (A→B)∧(B→A)和 A∧B ? (A∨B) ? (A→B)以及 A∨B ? A→B. (p∧q)?r 10 ? (p∧q → r) ∧ (r → p∧q) ? ((p→q) → r) ∧ (r → (p→q)) ? (((p→q) → r) → (r → (p→q))) 注聯(lián)結(jié)詞越少, 公式越長(zhǎng). 2.21. 證明: (1) (p↑q) ? (q↑p), (p↓q) ? (q↓p). (p↑q) ? (p∧q) ? (q∧p) ? (q↑p). (p↓q) ? (p∨q) ? (q∨p) ? (q↓p). 2.22. 略 2.23. 略 2.24. 略 2.25. 設(shè)A, B, C為任意的命題公式. (1)若A∨C?B∨C, 舉例說(shuō)明 A?B不一定成立. (2)已知A∧C?B∧C, 舉例說(shuō)明A?B不一定成立. (3)已知A?B, 問(wèn): A?B一定成立嗎? (1) 取 A = p, B = q, C = 1 (重言式), 有 A∨C ? B∨C, 但 A B. (2) 取 A = p, B = q, C = 0 (矛盾式), 有 A∧C ? B∧C, 但 A B. 好的例子是簡(jiǎn)單, 具體, 而又說(shuō)明問(wèn)題的. (3)一定. 2.26. 略 2.27. 某電路中有一個(gè)燈泡和三個(gè)開(kāi)關(guān)A,B,C. 已知在且僅在下述四種情況下燈亮: (1)C的扳鍵向上, A,B的扳鍵向下. (2)A的扳鍵向上, B,C的扳鍵向下. (3)B,C的扳鍵向上, A的扳鍵向下. (4)A,B的扳鍵向上, C的扳鍵向下. 設(shè)F為1表示燈亮, p,q,r分別表示A,B,C的扳鍵向上. (a)求F的主析取范式. (b)在聯(lián)結(jié)詞完備集{, ∧}上構(gòu)造F. (c)在聯(lián)結(jié)詞完備集{, →,?}上構(gòu)造F. (a)由條件(1)-(4)可知, F的主析取范式為 F? (p∧q∧r) ∨ (p∧q∧r) ∨ (p∧q∧r) ∨ (p∧q∧r) ?m1∨m4∨m3∨m6 ?m1∨m3∨m4∨m6 11 (b)先化簡(jiǎn)公式 F? (p∧q∧r) ∨ (p∧q∧r) ∨ (p∧q∧r) ∨ (p∧q∧r) ?q∧ ((p∧r) ∨ (p∧r)) ∨q∧ ((p∧r) ∨ (p∧r)) ? (q∨q) ∧ ((p∧r) ∨ (p∧r)) ? (p∧r) ∨ (p∧r) ? ( (p∧r) ∧ (p∧r)) (已為{, ∧}中公式) (c) F? (p∧r) ∨ (p∧r) ? (p∧r) ∨ (p∧r) ? (p∧r) → (p∧r) ? (p∨r) → (p∨r) ? (r→p) → (p→r) (已為{, →,?}中公式) 2.28. 一個(gè)排隊(duì)線路, 輸入為A,B,C, 其輸出分別為F A,F B,F C. 本線路中, 在同一時(shí)間內(nèi)只能有一個(gè)信號(hào)通過(guò), 若同時(shí)有兩個(gè)和兩個(gè)以上信號(hào)申請(qǐng)輸出時(shí), 則按A,B,C的順序輸出. 寫(xiě)出F A,F B,F C在聯(lián)結(jié)詞完備集{, ∨} 中的表達(dá)式. 根據(jù)題目中的要求, 先寫(xiě)出F A,F B,F C的真值表(自己寫(xiě)) 由真值表可先求出他們的主析取范式, 然后化成{, ∧}中的公式 F A?m4∨m5∨m6∨m7 ?p F B?m2∨m3 ?p∧q F C?m1 ?p∧q∧r 2.29. 略 2.30. 略 (已為{, ∧}中公式) (已為{, ∧}中公式) (已為{, ∧}中公式) 12 習(xí)題三 3.1. 略 3.2. 略 3.3. 略 3.4. 略 3.5. 略 3.6. 判斷下面推理是否正確. 先將簡(jiǎn)單命題符號(hào)化, 再寫(xiě)出前提, 結(jié)論, 推理的形式結(jié)構(gòu)(以蘊(yùn)涵式的形式給 出)和判斷過(guò)程(至少給出兩種判斷方法): (1)若今天是星期一, 則明天是星期三；今天是星期一. 所以明天是星期三. (2)若今天是星期一, 則明天是星期二；明天是星期二. 所以今天是星期一. (3)若今天是星期一, 則明天是星期三；明天不是星期三. 所以今天不是星期一. (4)若今天是星期一, 則明天是星期二；今天不是星期一. 所以明天不是星期二. (5)若今天是星期一, 則明天是星期二或星期三. (6)今天是星期一當(dāng)且僅當(dāng)明天是星期三；今天不是星期一. 所以明天不是星期三. 設(shè)p: 今天是星期一, q: 明天是星期二, r: 明天是星期三. (1)推理的形式結(jié)構(gòu)為 (p→r) ∧p→r 此形式結(jié)構(gòu)為重言式, 即 (p→r) ∧p?r 所以推理正確. (2)推理的形式結(jié)構(gòu)為 (p→q) ∧q→p 此形式結(jié)構(gòu)不是重言式, 故推理不正確. (3)推理形式結(jié)構(gòu)為 (p→r) ∧r→p 此形式結(jié)構(gòu)為重言式, 即 (p→r) ∧r?p 故推理正確. (4)推理形式結(jié)構(gòu)為 (p→q) ∧p→q 此形式結(jié)構(gòu)不是重言式, 故推理不正確. (5)推理形式結(jié)構(gòu)為 p→ (q∨r) 它不是重言式, 故推理不正確. (6)推理形式結(jié)構(gòu)為 (p?r) ∧p→r 13 此形式結(jié)構(gòu)為重言式, 即 (p?r) ∧p?r 故推理正確. 推理是否正確, 可用多種方法證明. 證明的方法有真值表法, 等式演算法. 證明推理正確還可用構(gòu)造證明法. 下面用構(gòu)造證明法證明(6)推理正確. 前提: p?r, p 結(jié)論: r 證明: ①p?r ②(p→r) ∧ (r→p) ③ r→p ④p ⑤r 所以, 推理正確. 3.7. 略 3.8. 略 前提引入 ①置換 ②化簡(jiǎn)律 前提引入 ③④拒取式 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): (p → q) ∧ (r → q) → (r → p). …… 3.10.略 3.11.略 3.12.略 3.13.略 3.14.在自然推理系統(tǒng)P中構(gòu)造下面推理的證明: (1)前提: p→ (q→r), p, q 結(jié)論: r∨s (2)前提: p→q, (q∧r), r 結(jié)論: p (3)前提: p→q 結(jié)論: p→ (p∧q) (4)前提: q→p, q?s, s?t, t∧r 結(jié)論: p∧q (5)前提: p→r, q→s, p∧q 14 結(jié)論: r∧s (6)前提: p∨r, q∨s, p∧q 結(jié)論: t→ (r∨s) (1)證明: p→(q→r) ② p q→r ③ ④ q ⑤ r r∨s ⑥ (2)證明: (q∧r) ① q∨r ② ③ r q ④ p→q ⑤ p ⑥ (3)證明: p→q ① p∨q ② 前提引入 ①②假言推理 前提引入 ③④假言推理 ⑤附加律 前提引入 ①置換 前提引入 ②③析取三段論 前提引入 ④⑤拒取式 前提引入 ①置換 (p∨q) ∧ (p∨p) p∨ (p∧q) p→ (p∧q) 也可以用附加前提證明法, 更簡(jiǎn)單些. (4)證明: s?t (s→t) ∧ (t→s) t→s t∧r ⑤ t ⑥ s q?s ⑦ (s→q) ∧ (q→s) ⑧ s→q ⑨ ⑩ q ④化簡(jiǎn) ③⑤假言推理 前提引入 ⑦置換 ⑧化簡(jiǎn) ⑥⑥假言推理 15 q →p ○ 12 p p∧q ○ 13 (5)證明: p→r ① 前提引入 q→s ② 前提引入 p∧q ③ 前提引入 ④ ③化簡(jiǎn) p ⑤ ③化簡(jiǎn) q ⑩○假言推理 11 ⑩○合取 12 ⑥ r ⑦ s r∧s ⑧ (6)證明: ① t p∨r ② p∧q ③ ④ p ⑤ r r∨s ⑥ ①④假言推理 ②⑤假言推理 ⑥⑦合取 附加前提引入 前提引入 前提引入 ③化簡(jiǎn) ②④析取三段論 ⑤附加 說(shuō)明: 證明中, 附加提前t, 前提q∨s沒(méi)用上. 這仍是正確的推理. 3.15.在自然推理系統(tǒng)P中用附加前提法證明下面各推理: (1)前提: p→ (q→r), s→p, q 結(jié)論: s→r (2)前提: (p∨q) → (r∧s), (s∨t) →u 結(jié)論: p→u (1)證明: ① s s→p ② ③ p p→ (q→r) ④ q→r ⑤ ⑥ q ⑦ r 附加前提引入 前提引入 ①②假言推理 前提引入 ③④假言推理 前提引入 ⑤⑥假言推理 16 (2)證明: ① P p∨q ② (p∨q) → (r∧s) ③ r∧s ④ ⑤ S s∨t ⑥ (s∨t) →u ⑦ ⑧ u 附加前提引入 ①附加 前提引入 ②③假言推理 ④化簡(jiǎn) ⑤附加 前提引入 ⑥⑦假言推理 3.16.在自然推理系統(tǒng)P中用歸謬法證明下面推理: (1)前提: p→q, r∨q, r∧s 結(jié)論: p (2)前提: p∨q, p→r, q→s 結(jié)論: r∨s (1)證明: ① P p→q ② q ③ r∨q ④ r ⑤ r∧s ⑥ ⑦ r r∧r ⑧ 結(jié)論否定引入 前提引入 ①②假言推理 前提引入 ③④析取三段論 前提引入 ⑥化簡(jiǎn) ⑤⑦合取 ⑧為矛盾式, 由歸謬法可知, 推理正確. (2)證明: (r∨s) p∨q p→r q→s r∨s (r∨s) ∧ (r∨s) 17 ⑥為矛盾式, 所以推理正確. 3.17.P53 17. 在自然推理系統(tǒng) P 中構(gòu)造下面推理的證明: 只要 A 曾到過(guò)受害者房間并且11點(diǎn)以前沒(méi)用離開(kāi), A 就犯了謀殺罪. A 曾到過(guò)受害者房間. 如果 A 在 11點(diǎn)以前離開(kāi), 看門(mén)人會(huì)看到他. 看門(mén)人沒(méi)有看到他. 所以 A 犯了謀殺罪. 令 p: A 曾到過(guò)受害者房間; q: A 在11點(diǎn)以前離開(kāi)了; r: A 就犯了謀殺罪; s:看門(mén)人看到 A. 前提: p∧q → r, p, q → s, s. 結(jié)論: r. 前提: p∧q → r, p, q → s, s; 證明: ① s 前提引入 ② q → s 前提引入 ③ q ①②拒取 前提引入 ④ p ⑤ p∧q ③④合取 ⑥ p∧q → r 前提引入 ⑦ r ⑤⑥假言推理 結(jié)論: r. 3.18.在自然推理系統(tǒng)P中構(gòu)造下面推理的證明. (1)如果今天是星期六, 我們就要到頤和園或圓明園去玩. 如果頤和園游人太多, 我們就不去頤和園玩. 今天是星期六. 頤和園游人太多. 所以我們?nèi)A明園玩. (2)如果小王是理科學(xué)生, 他的數(shù)學(xué)成績(jī)一定很好. 如果小王不是文科生, 他必是理科生. 小王的數(shù)學(xué)成 績(jī)不好. 所以小王是文科學(xué)生. (3)明天是晴天, 或是雨天；若明天是晴天, 我就去看電影；若我看電影, 我就不看書(shū). 所以, 如果我看書(shū), 則明天是雨天. (1)令 p: 今天是星期六; q: 我們要到頤和園玩; r: 我們要到圓明園玩; s:頤和園游人太多. 前提: p→ (q∨r), s → q, p, s. 結(jié)論: r. ① p p→q∨r ② q∨r ③ ④ s s → q ⑤ q ⑥ ⑦ r 前提引入 p→q∨r s → q p s 前提引入 q∨r q ①②假言推理 前提引入 r 前提引入 (1)的證明樹(shù) ④⑤假言推理 ③⑥析取三段論 18 (2) 令p: 小王是理科生, q: 小王是文科生, r: 小王的數(shù)學(xué)成績(jī)很好. 前提: p→r, q→p, r 結(jié)論: q 證明: p→r q r ② 前提引入 p ③ ①②拒取式 p q→p ④ 前提引入 (2)的證明樹(shù) ⑤ ③④拒取式 q (3)令p: 明天是晴天, q: 明天是雨天, r: 我看電影, s: 我看書(shū). 前提: p∨q, p→r, r→s 結(jié)論: s→q 證明: ① 附加前提引入 s r→s ② 前提引入 r ③ ①②拒取式 p→r ④ 前提引入 p ⑤ ③④拒取式 p∨q ⑥ 前提引入 ⑦ ⑤⑥析取三段論 q p→q r→p r 19 習(xí)題四 4.1. 將下面命題用0元謂詞符號(hào)化: (1)小王學(xué)過(guò)英語(yǔ)和法語(yǔ). (2)除非李建是東北人, 否則他一定怕冷. (1) 令 F(x): x 學(xué)過(guò)英語(yǔ); F(x): x 學(xué)過(guò)法語(yǔ); a: 小王. 符號(hào)化為 F(a)∧F(b). 或進(jìn)一步細(xì)分, 令 L(x, y): x 學(xué)過(guò) y; a: 小王; b1 : 英語(yǔ); b2 : 法語(yǔ). 則符號(hào)化為 L(a, b1 )∧L(a, b2 ). (2) 令 F(x): x 是東北人; G(x): x 怕冷; a: 李建. 符號(hào)化為 F(a)→G(a) 或 G(a)→F(a). 或進(jìn)一步細(xì)分, 令 H(x, y): x 是 y 地方人; G(x): x 怕冷; a: 小王; b: 東北. 則符號(hào)化為 H(a, b)→G(a) 或 G(a)→ H(a, b). 4.2. 在一階邏輯中將下面命題符號(hào)化, 并分別討論個(gè)體域限制為(a),(b)時(shí)命題的真值: (1)凡有理數(shù)都能被2整除. (2)有的有理數(shù)能被2整除. 其中(a)個(gè)體域?yàn)橛欣頂?shù)集合, (b)個(gè)體域?yàn)閷?shí)數(shù)集合. (1)(a)中, ?xF(x), 其中, F(x): x能被2整除, 真值為0. (b)中, ?x(G(x) ∧F(x)), 其中, G(x): x為有理數(shù), F(x)同(a)中, 真值為0. (2)(a)中, ?xF(x), 其中, F(x): x能被2整除, 真值為1. (b)中, ?x(G(x) ∧F(x)), 其中, F(x)同(a)中, G(x): x為有理數(shù), 真值為1. 4.3. 在一階邏輯中將下面命題符號(hào)化, 并分別討論個(gè)體域限制為(a),(b)時(shí)命題的真值: (1)對(duì)于任意的x, 均有x2?2=(x+ 2 )(x?2 ). (2)存在x, 使得x+5=9. 其中(a)個(gè)體域?yàn)樽匀粩?shù)集合, (b)個(gè)體域?yàn)閷?shí)數(shù)集合. (1)(a)中, ?x(x2?2=(x+ 2 )(x?2 )), 真值為1. (b)中, ?x(F(x) → (x2?2=(x+ 2 )(x?2 )))), 其中, F(x): x為實(shí)數(shù), 真值為1. (2)(a)中, ?x(x+5=9), 真值為1. (b)中, ?x(F(x) ∧ (x+5=9)), 其中, F(x): x為實(shí)數(shù), 真值為1. 4.4. 在一階邏輯中將下列命題符號(hào)化: (1)沒(méi)有不能表示成分?jǐn)?shù)的有理數(shù). (2)在北京賣菜的人不全是外地人. 20 (3)烏鴉都是黑色的. (4)有的人天天鍛煉身體. 沒(méi)指定個(gè)體域, 因而使用全總個(gè)體域. (1) ?x(F(x) ∧G(x))或?x(F(x) →G(x)), 其中, F(x): x為有理數(shù), G(x): x能表示成分?jǐn)?shù). (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天天鍛煉身體. 4.5. 在一階邏輯中將下列命題符號(hào)化: (1)火車都比輪船快. (2)有的火車比有的汽車快. (3)不存在比所有火車都快的汽車. (4)“凡是汽車就比火車慢”是不對(duì)的. 因?yàn)闆](méi)指明個(gè)體域, 因而使用全總個(gè)體域 (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慢. 4.6. 略 4.7. 將下列各公式翻譯成自然語(yǔ)言, 個(gè)體域?yàn)檎麛?shù)集 , 并判斷各命題的真假. (1) ?x?y?z(x ? y = z); (2) ?x?y(x?y = 1). (1) 可選的翻譯: ①“任意兩個(gè)整數(shù)的差是整數(shù).” ② “對(duì)于任意兩個(gè)整數(shù), 都存在第三個(gè)整數(shù), 它等于這兩個(gè)整數(shù)相減.” ③ “對(duì)于任意整數(shù) x 和 y, 都存在整數(shù) z, 使得 x ? y = z.” 選③, 直接翻譯, 無(wú)需數(shù)理邏輯以外的知識(shí). 以下翻譯意思相同, 都是錯(cuò)的: “有個(gè)整數(shù), 它是任意兩個(gè)整數(shù)的差.” “存在一個(gè)整數(shù), 對(duì)于任意兩個(gè)整數(shù), 第一個(gè)整數(shù)都等于這兩個(gè)整數(shù)相減.” “存在整數(shù) z, 使得對(duì)于任意整數(shù) x 和 y, 都有 x ? y = z.” 這3個(gè)句子都可以符號(hào)化為 ?z?x?y(x ? y = z). 量詞順序不可隨意調(diào)換. (2) 可選的翻譯: 21 ①“每個(gè)整數(shù)都有一個(gè)倒數(shù).” ② “對(duì)于每個(gè)整數(shù), 都能找到另一個(gè)整數(shù), 它們相乘結(jié)果是零.” ③ “對(duì)于任意整數(shù) x, 都存在整數(shù) y, 使得 x?y = z.” 選③, 是直接翻譯, 無(wú)需數(shù)理邏輯以外的知識(shí). 4.8. 指出下列公式中的指導(dǎo)變?cè)? 量詞的轄域, 各個(gè)體變項(xiàng)的自由出現(xiàn)和約束出現(xiàn): (3)?x?y(F(x, y) ∧ G(y, z)) ∨ ?xH(x, y, z) ?x?y(F(x, y) ∧ G(y, z) ) ∨ ?x H(x, y, z) 前件 ?x?y(F(x, y)∧G(y, z)) 中, ? 的指導(dǎo)變?cè)?x, ? 的轄域是 ?y(F(x, y)∧G(y, z)); ? 的指導(dǎo)變?cè)?y, ? 的轄域 是 (F(x, y)∧G(y, z)). 后件 ?xH(x, y, z) 中, ? 的指導(dǎo)變?cè)?x, ? 的轄域是 H(x, y, z). 整個(gè)公式中, x 約束出現(xiàn)兩次, y 約束出現(xiàn)兩次, 自由出現(xiàn)一次; z 自由出現(xiàn)兩次. 4.9. 給定解釋I如下: (a)個(gè)體域D I為實(shí)數(shù)集合. (b)D I中特定元素?a =0. (c)特定函數(shù)?f (x,y)=x?y, x,y∈D I. (d)特定謂詞?F(x,y): x=y,?G(x,y): x<y, x,y∈D I. 說(shuō)明下列公式在I下的含義, 并指出各公式的真值: (1) ?x?y(G(x,y) →F(x,y)) (2) ?x?y(F(f(x,y),a) →G(x,y)) (3) ?x?y(G(x,y) →F(f(x,y),a)) (4) ?x?y(G(f(x,y),a) →F(x,y)) (1) ?x?y(x<y→x≠y), 真值為1. (2) ?x?y((x?y=0) →x<y), 真值為0. (3) ?x?y((x<y) → (x?y≠0)), 真值為1. (4) ?x?y((x?y<0) → (x=y)), 真值為0. 4.10.給定解釋I如下: (a)個(gè)體域D=(為自然數(shù)). (b)D中特定元素?a=2. (c)D上函數(shù)?f (x,y)=x+y,?g (x,y)=xy. (d)D上謂詞?F (x,y): x=y. 說(shuō)明下列公式在I下的含義, 并指出各公式的真值: (1) ?xF(g(x,a),x) (2) ?x?y(F(f(x,a),y) →F(f(y,a),x)) (3) ?x?y?z(F(f(x,y),z) (4) ?xF(f(x,x),g(x,x)) 22 (1) ?x(x2=x), 真值為0. (2) ?x?y((x+2=y) → (y+2=x)), 真值為0. (3) ?x?y?z(x+y=z),真值為1. (4) ?x(x+x=xx),真值為1. 4.11.判斷下列各式的類型: (1) F(x, y) → (G(x, y) → F(x, y)). (3) ?x?yF(x, y) → ?x?yF(x, y). (5) ?x?y(F(x, y) → F(y, x)). (1) 是命題重言式 p → (q → p) 的代換實(shí)例, 所以是永真式. (3) 在某些解釋下為假(舉例), 在某些解釋下為真(舉例), 所以是非永真式的可滿足式. (5) 同(3). 4.12.P69 12. 設(shè) I 為一個(gè)任意的解釋, 在解釋 I 下, 下面哪些公式一定是命題? (1) ?xF(x, y) → ?yG(x, y). (2) ?x(F(x) → G(x)) ∧ ?y(F( y) ∧ H( y)). (3) ?x(?yF(x, y) → ?yG(x, y)). (4) ?x(F(x) ∧ G(x)) ∧ H( y). (2), (3) 一定是命題, 因?yàn)樗鼈兪情]式. 4.13.略 4.14.證明下面公式既不是永真式也不是矛盾式: (1) ?x(F(x) →?y(G(y) ∧H(x,y))) (2) ?x?y(F(x) ∧G(y) →H(x,y)) (1) 取個(gè)體域?yàn)槿倐€(gè)體域. 解釋I1 : F(x): x為有理數(shù), G(y): y為整數(shù), H(x,y): x<y 在I1下: ?x(F(x) →?y(G(y) ∧H(x,y)))為真命題, 所以該公式不是矛盾式. 解釋I2 : F(x),G(y)同I1 , H(x,y): y整除x. 在I2下: ?x(F(x) →?y(G(y) ∧H(x,y)))為假命題, 所以該公式不是永真式. (2) 請(qǐng)讀者給出不同解釋, 使其分別為成真和成假的命題即可. 4.15.(1) 給出一個(gè)非閉式的永真式. (2) 給出一個(gè)非閉式的永假式. (3) 給出一個(gè)非閉式的可滿足式, 但不是永真式. (1) F(x) ∨ F(x). (2) F(x) ∧ F(x). (3) ?x(F(x, y) → F(y, x)). 23 習(xí)題五 5.1. 略 5.2. 設(shè)個(gè)體域D={a,b,c}, 消去下列各式的量詞: (1) ?x?y(F(x) ∧G(y)) (2) ?x?y(F(x) ∨G(y)) (3) ?xF(x) →?yG(y) (4) ?x(F(x,y) →?yG(y)) (1) ?x?y(F(x) ∧G(y)) ??xF(x) ∧?yG(y) ? (F(a) ∧F(b)) ∧F(c)) ∧ (G(a) ∨G(b) ∨G(c)) (2) ?x?y(F(x) ∨G(y)) ??xF(x) ∨?yG(y) ? (F(a) ∧F(b) ∧F(c)) ∨ (G(a) ∧G(b) ∧G(c)) (3) ?xF(x) →?yG(y) ? (F(a) ∧F(b) ∧F(c)) → (G(a) ∧G(b) ∧G(c)) (4) ?x(F(x,y) →?yG(y)) ??xF(x,y) →?yG(y) ? (F(a,y) ∨F(b,y) ∨F(c,y)) → (G(a) ∨G(b) ∨G(c)) 5.3. 設(shè)個(gè)體域D={1,2}, 請(qǐng)給出兩種不同的解釋I1和I2 , 使得下面公式在I1下都是真命題, 而在I2下都是假 命題. (1) ?x(F(x) →G(x)) (2) ?x(F(x) ∧G(x)) (1)I1 : F(x):x≤2,G(x):x≤3 F(1),F(2),G(1),G(2)均為真, 所以 ?x(F(x) →G(x)) ? (F(1) →G(1) ∧ (F(2) →G(2))為真. I2 : F(x)同I1 ,G(x):x≤0 則F(1),F(2)均為真, 而G(1),G(2)均為假, ?x(F(x) →G(x))為假. (2)留給讀者自己做. 5.4. 略 5.5. 給定解釋I如下: (a) 個(gè)體域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. 24 試求下列公式在I下的真值: (1) ?x?yF(x,y) (2) ?x?yF(x,y) (3) ?x?y(F(x,y) →F(f(x),f(y))) (1) ?x?yF(x,y) ? (F(3,3) ∨F(3,4)) ∧ (F(4,3) ∨F(4,4)) ? (0∨1) ∧ (1∨0) ?1 (2) ?x?yF(x,y) ? (F(3,3) ∧F(3,4)) ∨ (F(4,3) ∧F(4,4)) ? (0∧1) ∨ (1∧0) ?0 (3) ?x?y(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))) ? (0→0) ∧ (1→1) ∧ (1→1) ∧ (0→0) ?1 5.6. 略 5.7. 略 5.8. 在一階邏輯中將下列命題符號(hào)化, 要求用兩種不同的等值形式. (1) 沒(méi)有小于負(fù)數(shù)的正數(shù). (2) 相等的兩個(gè)角未必都是對(duì)頂角. (1) 令 F(x): x 小于負(fù)數(shù), G(x): x 是正數(shù). 符合化為: ?x((F(x) ∧ G(x)) ? ?x(G(x) → G(x)). (2) 令 F(x): x 是角, H(x, y): x 和 y 是相等的, L(x, y): x 與 y 是對(duì)頂角. 符合化為: ?x?y(F(x) ∧ F(y) ∧ H(x, y) → L(x, y)) ? ?x?y(F(x) ∧ F(y) ∧ H(x, y) ∧ L(x, y)) ? ?x(F(x) ∧ (?y(F(y) ∧ H(x, y) ∧ L(x, y))). 5.9. 略 5.10.略 5.11.略 5.12.求下列各式的前束范式. (1) ?xF(x) → ?yG(x, y); (3) ?xF(x, y) ? ?xG(x, y); (5) ?x1F(x1 , x2 ) → (F(x1 ) → ?x2G(x1 , x2 )). 前束范式不是唯一的. (1) ?xF(x) → ?yG(x, y) ? ?x(F(x) → ?yG(x, y)) 25 ? ?x?y(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) → ?