離散數(shù)學(xué)屈婉玲版課后答案
《離散數(shù)學(xué)屈婉玲版課后答案》由會(huì)員分享,可在線(xiàn)閱讀,更多相關(guān)《離散數(shù)學(xué)屈婉玲版課后答案(106頁(yè)珍藏版)》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
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)如果天下大雨, 他就乘班車(chē)上班. (9)只有天下大雨, 他才乘班車(chē)上班. (10)除非天下大雨, 他才乘班車(chē)上班. (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: 他乘班車(chē)上班. (9)p→q, 其中, p: 他乘班車(chē)上班, q: 天下大雨. (10)p→q, 其中, p: 他乘班車(chē)上班, 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. 略 略 略 用真值表判斷下列公式的類(lèi)型: (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)為可滿(mǎn)足式. 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ù)木, 則人類(lèi)不能生存. (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: 人類(lèi)能生存, 真值為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. 用等值演算法判斷下列公式的類(lèi)型, 對(duì)不是重言式的可滿(mǎn)足式, 再用真值表法求出成真賦值. (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), 是可滿(mǎ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ì)線(xiàn)路, 輸入為A,B,C, 其輸出分別為F A,F B,F C. 本線(xiàn)路中, 在同一時(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)在北京賣(mài)菜的人不全是外地人. 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在北京賣(mài)菜, 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)火車(chē)都比輪船快. (2)有的火車(chē)比有的汽車(chē)快. (3)不存在比所有火車(chē)都快的汽車(chē). (4)“凡是汽車(chē)就比火車(chē)慢”是不對(duì)的. 因?yàn)闆](méi)指明個(gè)體域, 因而使用全總個(gè)體域 (1) ?x?y(F(x) ∧G(y) →H(x,y)), 其中, F(x): x是火車(chē), G(y): y是輪船, H(x,y):x比y快. (2) ?x?y(F(x) ∧G(y) ∧H(x,y)), 其中, F(x): x是火車(chē), G(y): y是汽車(chē), 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是汽車(chē), G(y): y是火車(chē), 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是汽車(chē), G(y): y是火車(chē), 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- 1.請(qǐng)仔細(xì)閱讀文檔,確保文檔完整性,對(duì)于不預(yù)覽、不比對(duì)內(nèi)容而直接下載帶來(lái)的問(wèn)題本站不予受理。
- 2.下載的文檔,不會(huì)出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入(下載+內(nèi)容+預(yù)覽)歸上傳者、原創(chuàng)作者;如果您是本文檔原作者,請(qǐng)點(diǎn)此認(rèn)領(lǐng)!既往收益都?xì)w您。
下載文檔到電腦,查找使用更方便
15 積分
下載 |
- 配套講稿:
如PPT文件的首頁(yè)顯示word圖標(biāo),表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開(kāi)word文檔。
- 特殊限制:
部分文檔作品中含有的國(guó)旗、國(guó)徽等圖片,僅作為作品整體效果示例展示,禁止商用。設(shè)計(jì)者僅對(duì)作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞:
- 離散數(shù)學(xué) 屈婉玲版 課后 答案
鏈接地址:http://m.jqnhouse.com/p-9927704.html