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

1、離散數(shù)學(xué)習(xí)題解97習(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+24 當(dāng)且僅當(dāng) 3+36. (2)2+24 的充要條件是 3+3¹6. (3)2+2¹4 與 3+36 互為充要條件. (4)若 2+2¹4, 則 3+3¹6, 反之亦然.(1)p«q, 其中, p: 2+24, q: 3+36, 真值為 1. (2)p«Øq, 其中, p: 2+24, q: 3+36, 真值為 0. (3) Øp

2、1;q, 其中, p: 2+24, q: 3+36, 真值為 0. (4) Øp«Øq, 其中, p: 2+24, q: 3+36, 真值為 1.1.13將下列命題符號(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

3、) p®r 當(dāng) p Û 0 時(shí)為真; p Û 1 時(shí)為假.1.14 將下列 命題符號(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ì)的.(1)p&

4、#217;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

5、: 天下大雨. (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ù).1.15設(shè) p: 2+3=5.q: 大熊貓產(chǎn)在中國(guó). r: 復(fù)旦大學(xué)在廣州. 求下列復(fù)合命題的真值:(1)(p«q) ®r (2)(r® (p&#

6、217;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) Ø (

7、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)(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)化,

8、 并給出各命題的 真值: (1)若 3+4, 則地球是靜止不動(dòng)的.(2)若 3+24, 則地球是運(yùn)動(dòng)不止的. (3)若地球上沒(méi)有樹(shù)木, 則人類(lèi)不能生存.(4)若地球上沒(méi)有水, 則 3 是無(wú)理數(shù).(1)p®q, 其中, p: 2+24, q: 地球靜止不動(dòng), 真值為 0. (2)p®q, 其中, p: 2+24, q: 地球運(yùn)動(dòng)不止, 真值為 1.(3) Øp®Øq, 其中, p: 地球上有樹(shù)木, q: 人類(lèi)能生存, 真值為 1. (4) Øp®q, 其中, p: 地球上有水, q: 3 是無(wú)理數(shù), 真值為 1.習(xí)題二2.1.

9、 設(shè)公式 A = p®q, B = pØÙq, 用真值表驗(yàn)證公式 A 和 B 適合德摩根律:Ø(AÚB) Û ØAØÙB.pqA =p®qB =pØÙqØ(AÚB)ØAØÙB001000011000100100111000因?yàn)?Ø(AÚB)和 ØAØÙB 的真值表相同, 所以它們等值.2.2. 略2.3. 用等值演算法判斷下列公式的類(lèi)型, 對(duì)不是重言式的可滿(mǎn)足式, 再用真值表法

10、求出成真賦值. (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)重言式

11、.(3) (pÚq) ® (pÙr) Û Ø(pÚq) Ú (pÙr) Û ØpØÙq Ú pÙr 易見(jiàn), 是可滿(mǎn)足式, 但不是重言式. 成真賦值為: 000, 001, 101, 111p q r¬p ¬q pr00011110001111100101000001110000100001001010011111000000111000112.4. 用等值演算法證明下面等值式: (1) pÛ (pÙq) Ú

12、 (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)ÛØ

13、(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

14、Ù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)

15、(Ø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

16、6;Ù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®&#

17、216;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,

18、成假賦值為 100.(3)主合取范式為 1, 為重言式.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ÙM62.8. 略2.9. 用真值表求下面公式的主析取范式. (2) (p®q) ® (pØ«q

19、)p q(p q) (p ¬ q)001001011110100111111000(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Û &#

20、216;(Ø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

21、 Ú Ø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)Ø

22、17;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Ù&#

23、216;qÙØr)Ú(ØpÙØqÙr)Ú(ØpÙqÙØr)Ú(ØpÙqÙr)Ú(ØpÙØqÙr)Ú(ØpÙqÙr)Ú(pÙØqÙr)Ú(pÙqÙr)= m0 Ú m1 Ú m4 Ú m5Ú m0 Ú m1 Ú m2 &#

24、218; m3Ú m1 Ú m3 Ú m5 Ú m7Û m0 Ú m1 Ú m2 Ú m3 Ú m4 Ú m5 Ú m7Û å(0, 1, 2, 3, 4, 5, 7).兩個(gè)公式的主吸取范式不同, 所以(p®q) ®r q® (p®r).2.16. 用主析取范式判斷下列公式是否等值: (1)(p®q) ®r 與 q® (p®r)(2) Ø (pÙq)與Ø (

25、pÚq)(1)(p®q) ®r) Ûm1Úm3Úm4Úm5Úm7q® (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

26、. 用主合取范式判斷下列公式是否等值: (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

27、7;M6所以 p® (q®r) (p®q) ®r2.18. 略2.19. 略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&#

28、219; (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

29、¯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Û

30、;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 的扳鍵向上,

31、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&

32、#217;r) Ú (pÙqÙØr)Ûm1Úm4Úm3Úm6Ûm1Úm3Úm4Úm6(b)先化簡(jiǎn)公式FÛ (ØpÙØqÙr) Ú (pÙØqÙØr) Ú (ØpÙqÙr) Ú (pÙqÙØr)ÛØqÙ (ØpÙr) Ú (pÙ&#

33、216;r) ÚqÙ (ØpÙr) Ú (pÙØr)Û (ØqÚq) Ù (ØpÙr) Ú (pÙØr)Û (ØpÙr) Ú (pÙØr)ÛØ (Ø (ØpÙr) ÙØ (pÙØr) (已為Ø, Ù中公式) (c)FÛ (ØpÙr) 

34、18; (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, 其輸出分別為 FA,FB,FC. 本線(xiàn)路中,

35、 在同一時(shí)間內(nèi)只能有一個(gè)信號(hào)通過(guò), 若同時(shí)有兩個(gè)和兩個(gè)以上信號(hào)申請(qǐng)輸出時(shí), 則按 A,B,C 的順序輸出. 寫(xiě)出 FA,FB,FC 在聯(lián)結(jié)詞完備集Ø, Ú 中的表達(dá)式.根據(jù)題目中的要求, 先寫(xiě)出 FA,FB,FC 的真值表(自己寫(xiě)) 由真值表可先求出他們的主析取范式, 然后化成Ø, Ù中的公式 FAÛm4Úm5Úm6Úm7Ûp(已為Ø, Ù中公式)FBÛm2Úm3ÛØpÙq(已為Ø, Ù中公式)FCÛm1&

36、#219;ØpÙØqÙr(已為Ø, Ù中公式)2.29. 略2.30. 略習(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)若今天是星

37、期一, 則明天是星期二；今天不是星期一. 所以明天不是星期二. (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) Ù

38、16;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此形式結(jié)構(gòu)為重言式, 即(pÞr) ÙØpÞØr故推理正確.推理是否正確, 可用多種

39、方法證明. 證明的方法有真值表法, 等式演算法. 證明推理正確還可用構(gòu)造證明法. 下面用構(gòu)造證明法證明(6)推理正確.前提: pÞr, Øp結(jié)論: Ør證明: pÞr前提引入 (p®r) Ù (r®p)置換 r®p化簡(jiǎn)律Øp前提引入Ør拒取式 所以, 推理正確.3.7. 略3.8. 略3.9. 用三種方法(真值表法, 等值演算法, 主析取范式法)證明下面推理是正確的:若 a 是奇數(shù), 則 a 不能被 2 整除. 若 a 是偶數(shù), 則 a 能被 2 整除. 因此, 如果 a 是偶數(shù), 則 a 不是

40、奇數(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é)論: &

41、#216;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結(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)證明:Ø (

42、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前提引入置換化簡(jiǎn) 前提引入化簡(jiǎn)s假言推理

43、qÞs(s®q) Ù (q®s)s®q q前提引入置換化簡(jiǎn)假言推理11q ®p前提引入1213p pÙq11 假言推理12 合取(5)證明:p®r q®s前提引入 前提引入pÙq p前提引入化簡(jiǎn)q化簡(jiǎn)r假言推理s假言推理rÙs合取(6)證明:tØpÚr附加前提引入 前提引入pÙq p前提引入化簡(jiǎn)r析取三段論rÚs附加說(shuō)明: 證明中, 附加提前 t, 前提ØqÚs 沒(méi)用上. 這仍是正確的推理.3.15.在自然推理系統(tǒng) P 中用附

44、加前提法證明下面各推理: (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假言推理(2)證明:PpÚq附加前提引入附加(pÚq) ® (rÙs)前提引入rÙsS假言推理化簡(jiǎn)sÚt(sÚt)

45、74;u u附加 前提引入假言推理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)證明:Pp®Øq結(jié)論否定引入 前提引入ØqØrÚqØr rÙØs r假言推理前提引入析取三段論 前提引入化簡(jiǎn)ØrÙr合取為矛盾式, 由歸謬法可知, 推理正確. (2)證明:Ø

46、 (rÚs)結(jié)論否定引入pÚq前提引入p®r前提引入q®s前提引入rÚs構(gòu)造性二難Ø (rÚs) Ù (rÚs)合取為矛盾式, 所以推理正確.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)人看

47、到 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)造下面推理的證明.(1)如果今天是星期六, 我們就要到頤和園或圓明園去玩. 如果頤和園游人太多, 我們就不去頤和園玩. 今天是星期六

48、. 頤和園游人太多. 所以我們?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 pqr qrss ¬q¬q r假言推理前提引入 前提引入前提引入

49、前提引入pp®qÚr qÚrss ® ØqØqr假言推理(1)的證明樹(shù)析取三段論(2) 令 p: 小王是理科生, q: 小王是文科生, r: 小王的數(shù)學(xué)成績(jī)很好. 前提: p®r, Øq®p, Ør結(jié)論: q證明:p®r前提引入Ør前提引入Øp拒取式Øq®p前提引入q拒取式Øqp®qØpØr®p(2)的證明樹(shù)r(3)令 p: 明天是晴天, q: 明天是雨天, r: 我看電影, s: 我看書(shū).前提:

50、 pÚq, p®r, r®Øs結(jié)論: s®q證明:s r®Øs附加前提引入 前提引入Ør拒取式p®r前提引入Øp拒取式pÚq前提引入q析取三段論習(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)

51、化為L(zhǎng)(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 整

52、除. 其中(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í)命題的真值: (

53、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)

54、有不能表示成分?jǐn)?shù)的有理數(shù). (2)在北京賣(mài)菜的人不全是外地人.(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

55、是烏鴉, 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) 

56、7;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

57、(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ò)的:O “有個(gè)整數(shù), 它是任

58、意兩個(gè)整數(shù)的差.”0 “存在一個(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).0量詞順序不可隨意調(diào)換. (2) 可選的翻譯:“每個(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): (

59、3)"x$y(F(x, y) Ù G(y, z) Ú $xH(x, y, z)"x$y(F(x, y) Ù G(y, z) Ú $xH(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 約束出

60、現(xiàn)兩次, y 約束出現(xiàn)兩次, 自由出現(xiàn)一次; z 自由出現(xiàn)兩次.4.9. 給定解釋 I 如下: (a)個(gè)體域 DI 為實(shí)數(shù)集合.(b)DI 中特定元素a =0. (c)特定函數(shù)f (x,y)=x-y, x,yDI.(d)特定謂詞F(x,y): x=y,G(x,y): x<y, x,yDI. 說(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) ®Ø

61、;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

62、 中特定元素a=2.(c)D 上函數(shù)f (x,y)=x+y,g (x,y)=x·y. (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)(1) "x(x·2=x), 真值為 0.(2) "x"y(x+2=y) ® (y+2=x), 真值為 0.(3)

63、 "x"y$z(x+y=z),真值為 1.(4) $x(x+x=x·x),真值為 1.4.11.判斷下列各式的類(lèi)型:(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) 在某些解釋下為假(舉例), 在某些解釋下為真(舉例), 所以是非永真式的可滿(mǎn)足式. (5)

64、 同(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) "

65、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)為假命題, 所以該

66、公式不是永真式. (2) 請(qǐng)讀者給出不同解釋, 使其分別為成真和成假的命題即可.4.15.(1) 給出一個(gè)非閉式的永真式.(2) 給出一個(gè)非閉式的永假式.(3) 給出一個(gè)非閉式的可滿(mǎn)足式, 但不是永真式.(1) F(x) Ú ØF(x).(2) F(x) Ù ØF(x).(3) "x(F(x, y) ® F(y, x).習(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) &qu

67、ot;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(

68、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, 使得下

69、面公式在 I1 下都是真命題, 而在 I2 下都是假 命題.(1) "x(F(x) ®G(x)(2) $x(F(x) ÙG(x)(1)I1: F(x):x2,G(x):x3F(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):x0則 F(1),F(2)均為真, 而 G(1),G(2)均為假,"x(F(x) ®G(x)為假. (2)留給讀者自己做.5.4. 略5.5.

70、給定解釋 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.試求下列公式在 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) &

71、#219;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)Û

72、 (0®0) Ù (1®1) Ù (1®1) Ù (0®0) Û15.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):

73、 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)Û $x"y(F(x) ® G(x, y).(3) "xF(x,