離散數(shù)學(xué)課后習(xí)題答案 (左孝凌版)

《離散數(shù)學(xué)課后習(xí)題答案 (左孝凌版)》由會員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)課后習(xí)題答案 (左孝凌版)（32頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、　 〔1〕 解： a) 是命題，真值為T。 b) 不是命題。 c) 是命題，真值要根據(jù)具體情況確定。 d) 不是命題。 e) 是命題，真值為T。 f) 是命題，真值為T。 g) 是命題，真值為F。 h) 不是命題。 i) 不是命題。 〔2〕 解： 原子命題：我愛北京天安門。 復(fù)合命題：如果不是練健美操，我就出外旅游拉。 〔3〕 解： a) (┓P ∧R)→Q b) Q→R c) ┓P d) P→┓Q 〔4〕 解： a)設(shè)Q:我將去參加舞會。R:我有時間。P:天下雨。 Q? (R∧┓P):我將去參加舞會當(dāng)且僅當(dāng)我有時間和天不下雨。 b)設(shè)R:我在看電

2、視。Q:我在吃蘋果。 R∧Q:我在看電視邊吃蘋果。 c) 設(shè)Q:一個數(shù)是奇數(shù)。R:一個數(shù)不能被2除。 〔Q→R〕∧(R→Q):一個數(shù)是奇數(shù)，那么它不能被2整除并且一個數(shù)不能被2整除，那么它是奇數(shù)。 (5) 解： a) 設(shè)P：王強身體很好。Q：王強成績很好。P∧Q b) 設(shè)P：小李看書。Q：小李聽音樂。P∧Q c) 設(shè)P：氣候很好。Q：氣候很熱。P∨Q d) 設(shè)P： a和b是偶數(shù)。Q：a+b是偶數(shù)。P→Q e) 設(shè)P：四邊形ABCD是平行四邊形。Q ：四邊形ABCD的對邊平行。P?Q f) 設(shè)P：語法錯誤。Q：程序錯誤。R：停機?！睵∨ Q〕→ R (6) 解： a)

3、 P:天氣炎熱。Q:正在下雨。 P∧Q b) P:天氣炎熱。R:濕度較低。 P∧R c) R:天正在下雨。S:濕度很高。 R∨S d) A:劉英上山。B:李進上山。 A∧B e) M:老王是革新者。N:小李是革新者。 M∨N f) L:你看電影。M:我看電影。 ┓L→┓M g) P:我不看電視。Q:我不外出。 R:我在睡覺。 P∧Q∧R h) P:控制臺打字機作輸入設(shè)備。Q:控制臺打字機作輸出設(shè)備。P∧Q 習(xí)題解答 〔1〕解： a) 不是合式公式，沒有規(guī)定運算符次序〔假設(shè)規(guī)定運算符次序后亦可作為合式公式〕 b) 是合式公式 c) 不是合式公式〔括弧不配

4、對〕 d) 不是合式公式〔R和S之間缺少聯(lián)結(jié)詞〕 e) 是合式公式。 〔2〕解： a〕 A是合式公式，(A∨B)是合式公式，(A→(A∨B)) 是合式公式。這個過程可以簡記為： A；(A∨B)；(A→(A∨B)) 同理可記 b〕 A；┓A ；(┓A∧B) ；((┓A∧B)∧A) c〕 A；┓A ；B；(┓A→B) ；(B→A) ；((┓A→B)→(B→A)) d〕 A；B；(A→B) ；(B→A) ；((A→B)∨(B→A)) 〔3〕解： a〕 ((((A→C)→((B∧C)→A))→((B∧C)→A))→(A→C)) b〕 ((B→A)∨(A→B))。

5、〔4〕解： a) 是由c) 式進行代換得到，在c) 中用Q代換P, (P→P)代換Q. d) 是由a) 式進行代換得到，在a) 中用 P→(Q→P)代換Q. e) 是由b) 式進行代換得到，用R代換P, S代換Q, Q代換R, P代換S. 〔5〕解： a) P: 你沒有給我寫信。 R: 信在途中喪失了。 P Q b) P: 張三不去。Q: 李四不去。R: 他就去。 (P∧Q)→R c) P: 我們能劃船。 Q: 我們能跑步。 ┓(P∧Q) d) P: 你來了。Q: 他唱歌。R: 你伴奏。 P→(Q?R) 〔6〕解： P:它占據(jù)空間。 Q:它有質(zhì)量。 R:它不

6、斷變化。 S:它是物質(zhì)。 這個人起初主張：(P∧Q∧R) ? S 后來主張：(P∧Q?S)∧(S→R) 這個人開頭主張與后來主張的不同點在于：后來認(rèn)為有P∧Q必同時有R，開頭時沒有這樣的主張。 〔7〕解： a) P: 上午下雨。 Q:我去看電影。 R:我在家里讀書。 S:我在家里看報。(┓P→Q)∧(P→(R∨S)) b) P: 我今天進城。Q:天下雨。┓Q→P c) P: 你走了。 Q:我留下。Q→P 〔4〕解：a) P Q R Q∧R P∧(Q∧R) P∧Q (P∧Q)∧R T T T T T

7、 F T F T T F F F T T F T F F F T F F F T F F F T F F F T F F F F F F F T T F F F

8、 F F F T F F F F F F F 所以，P∧(Q∧R) ? (P∧Q)∧R b) P Q R Q∨R P∨(Q∨R) P∨Q (P∨Q)∨R T T T T T F T F T T F F F T T F T F F F T F F 　F　 Ｔ Ｔ Ｔ Ｆ

9、Ｔ Ｔ Ｔ Ｆ Ｔ Ｔ Ｔ Ｔ Ｔ Ｔ Ｔ Ｆ　 　　?。? 　　?。? 　　?。? 　　?。? 　　?。? 　　?。? 　　?。? 　　?。?　　?。? 　　?。? 　　?。? 　　?。? 　　　Ｔ 　　?。? 　　?。? 　　?。? 所以，P∨(Q∨R) ? (P∨Q)∨R　 ｃ〕 Ｐ?。选。?Ｑ∨Ｒ Ｐ∧〔Ｑ∨Ｒ〕 Ｐ∧Ｑ Ｐ∧Ｒ 〔Ｐ∧Ｑ〕∨〔Ｐ∧Ｒ〕 Ｔ?。浴。? Ｔ?。浴。啤? Ｔ?。啤。? Ｔ?。啤。? Ｆ?。浴。? Ｆ?。浴。? Ｆ?。啤。? Ｆ?。啤。??。? Ｔ Ｔ ?。? ?。? ?。? 　Ｔ ?。?　　?。? 　　?。?

10、 　　?。? 　　?。? 　　?。? 　　?。? 　　?。? 　　?。??。? ?。? ?。? ?。? ?。? ?。? ?。? ?。??。浴? ?。? ?。? ?。? ?。? ?。? ?。? ?。?　　　　　Ｔ 　　　　?。? 　　　　?。? 　　　　?。? 　　　　?。? 　　　　?。? 　　　　?。? 　　　　?。啤　　　　? 所以，P∧(Q∨R) ? (P∧Q)∨(P∧R)　 ｄ〕 P Q ┓P ┓Q ┓P∨┓Q ┓(P∧Q) ┓P∧┓Q ┓(P∨Q) T T T F F T F F

11、 F F T T F T F T F T T T F T T T F F F T F F F T 所以，┓(P∧Q) ?┓P∨┓Q, ┓(P∨Q) ?┓P∧┓Q 〔5〕解：如表，對問好所填的地方，可得公式F1～F6，可表達為 P Q R F1 F2 F3 F4 F

12、5 F6 T T T T F T T F F T T F F F T F F F T F T T F F T T F T F F F T F T T F F T T T F F T T F F T F T F F F T F F F T

13、 T F T T T F F F F F T F T T T F1:(Q→P)→R F2:(P∧┓Q∧┓R)∨(┓P∧┓Q∧┓R) F3:(P←→Q)∧(Q∨R) F4:(┓P∨┓Q∨R)∧(P∨┓Q∨R) F5:(┓P∨┓Q∨R)∧(┓P∨┓Q∨┓R) F6:┓(P∨Q∨R) (6) P Q 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 F F F T F T F T F T F

14、T F T F T F T F T F F T T F F T T F F T T F F T T T F F F F F T T T T F F F F T T T T T T F F F F F F F F T T T T T T T T 解：由上表可得有關(guān)公式為 1.F 2.┓(P∨Q) 3.┓(Q→P) 4.┓P 5.┓(P→Q) 6.┓Q 7.┓(P?Q) 8.┓(P∧Q)

15、 9.P∧Q 10.P?Q 11.Q 12.P→Q 13.P 14.Q→P 15.P∨Q 16.T (7) 證明： a) A→(B→A)? ┐A∨(┐B∨A) ? A∨(┐A∨┐B) ? A∨(A→┐B) ?┐A→(A→┐B) b) ┐(A?B) ?┐((A∧B)∨(┐A∧┐B)) ?┐((A∧B)∨┐(A∨B)) ?(A∨B)∧┐(A∧B) 或 ┐(A?B) ?┐((A→B)∧(B→A)) ?┐((┐A∨B)∧(┐B∨A)) ?┐((┐A∧┐B)∨(┐A∧A)∨(B∧

16、┐B)∨(B∧A)) ?┐((┐A∧┐B)∨(B∧A)) ?┐(┐(A∨B))∨(A∧B) ?(A∨B)∧┐(A∧B) c) ┐(A→B) ? ┐(┐A∨B) ?A∧┐B d) ┐(A?B)?┐((A→B)∧(B→A)) ?┐((┐A∨B)∧(┐B∨A)) ?(A∧┐B)∨(┐A∧B) e) (((A∧B∧C)→D)∧(C→(A∨B∨D))) ?(┐(A∧B∧C)∨D)∧(┐C∨(A∨B∨D)) ?(┐(A∧B∧C)∨D)∧(┐(┐A∧┐B∧C)∨D) ? (┐(A∧B∧C)∧┐(┐A∧┐B∧C))∨D ?((A∧B∧C)∨(┐A∧┐B∧C))→D ?

17、(((A∧B)∨(┐A∧┐B))∧C)→D ? ((C∧(A?B))→D) f) A→(B∨C) ? ┐A∨(B∨C) ? (┐A∨B)∨C ?┐(A∧┐B)∨C ? (A∧┐B)→C g) (A→D)∧(B→D)?(┐A∨D)∧(┐B∨D) ?(┐A∧┐B)∨D ? ┐(A∨B)∨D ? (A∨B)→D h) ((A∧B)→C)∧(B→(D∨C)) ?(┐(A∧B)∨C)∧(┐B∨(D∨C)) ? (┐(A∧B)∧(┐B∨D))∨C ?(┐(A∧B) ∧┐(┐D∧B))∨C ?┐((A∧B)∨(┐D∧B))∨C ? ((A∨┐D)∧B

18、)→C ? (B∧(D→A))→C 〔8〕解： a) ((A→B) ? (┐B→┐A))∧C ? ((┐A∨B) ? (B∨┐A))∧C ? ((┐A∨B) ? (┐A∨B))∧C ?T∧C ?C b) A∨(┐A∨(B∧┐B)) ? (A∨┐A)∨(B∧┐B) ?T∨F ?T c) (A∧B∧C)∨(┐A∧B∧C) ? (A∨┐A) ∧(B∧C) ?T∧(B∧C) ?B∧C 〔9〕解：1〕設(shè)C為T，A為T，B為F，那么滿足A∨C?B∨C，但A?B不成立。 2〕設(shè)C為F，A為T，B為F，那么滿足A∧C?B∧C，但A?B不成立。 3〕由題

19、意知┐A和┐B的真值相同，所以A和B的真值也相同。 習(xí)題 1-5 〔1〕 證明： a) (P∧(P→Q))→Q ? (P∧(┐P∨Q))→Q ?(P∧┐P)∨(P∧Q)→Q ?(P∧Q)→Q ?┐(P∧Q)∨Q ?┐P∨┐Q∨Q ?┐P∨T ?T b) ┐P→(P→Q) ?P∨(┐P∨Q) ? (P∨┐P)∨Q ?T∨Q ?T c) ((P→Q)∧(Q→R))→(P→R) 因為(P→Q)∧(Q→R)?(P→R) 所以 (P→Q)∧(Q→R)為重言式。 d) ((a∧b)∨(b∧c) ∨(c∧a))?(a∨b)∧(b∨c)∧(c∨a

20、) 因為((a∧b)∨(b∧c)∨(c∧a)) ?((a∨c)∧b)∨(c∧a) ?((a∨c)∨(c∧a))∧(b∨(c∧a)) ?(a∨c)∧(b∨c)∧(b∨a) 所以((a∧b)∨(b∧c) ∨(c∧a))?(a∨b)∧(b∨c)∧(c∨a) 為重言式。 〔2〕 證明： a)(P→Q)?P→(P∧Q) 解法1： 設(shè)P→Q為T 〔1〕假設(shè)P為T，那么Q為T，所以P∧Q為T，故P→(P∧Q)為T 〔2〕假設(shè)P為F，那么Q為F，所以P∧Q為F，P→(P∧Q)為T 命題得證 解法2： 設(shè)P→(P∧Q)為F ，那么P為T，(P∧Q)為F ，故必有P為T，Q為F

21、，所以P→Q為F。 解法3： (P→Q) →(P→(P∧Q)) ?┐(┐P∨Q)∨(┐P∨(P∧Q)) ?┐(┐P∨Q)∨((┐P∨P)∧(┐P∨Q)) ?T 所以(P→Q)?P→(P∧Q) b)(P→Q)→Q?P∨Q 設(shè)P∨Q為F，那么P為F，且Q為F， 故P→Q為T，(P→Q)→Q為F， 所以(P→Q)→Q?P∨Q。 c)(Q→(P∧┐P))→(R→(R→(P∧┐P)))?R→Q 設(shè)R→Q為F，那么R為T，且Q為F，又P∧┐P為F 所以Q→(P∧┐P)為T，R→(P∧┐P)為F 所以R→(R→(P∧┐P))為F，所以(Q→(P∧┐P))→(R→(R→(P∧┐P)

22、))為F 即(Q→(P∧┐P))→(R→(R→(P∧┐P)))?R→Q成立。 〔3〕 解： a) P→Q表示命題“如果8是偶數(shù)，那么糖果是甜的〞。 b) a)的逆換式Q→P表示命題“如果糖果是甜的，那么8是偶數(shù)〞。 c) a)的反換式┐P→┐Q表示命題“如果8不是偶數(shù)，那么糖果不是甜的〞。 d) a)的逆反式┐Q→┐P表示命題“如果糖果不是甜的，那么8不是偶數(shù)〞。 〔4〕 解： a) 如果天下雨，我不去。 設(shè)P：天下雨。Q：我不去。P→Q 逆換式Q→P表示命題:如果我不去，那么天下雨。 逆反式┐Q→┐P表示命題:如果我去，那么天不下雨 b) 僅當(dāng)你走我將留下。 設(shè)

23、S：你走了。R：我將留下。R→S 逆換式S→R表示命題：如果你走了那么我將留下。 逆反式┐S→┐R表示命題：如果你不走，那么我不留下。 c) 如果我不能獲得更多幫助，我不能完成個任務(wù)。 設(shè)E：我不能獲得更多幫助。H：我不能完成這個任務(wù)。E→H 逆換式H→E表示命題：我不能完成這個任務(wù)，那么我不能獲得更多幫助。 逆反式┐H→┐E表示命題：我完成這個任務(wù)，那么我能獲得更多幫助 〔5〕 試證明P?Q，Q邏輯蘊含P。 證明：解法1： 此題要求證明(P?Q) ∧Q?P, 設(shè)(P?Q) ∧Q為T，那么(P?Q)為T，Q為T，故由?的定義，必有P為T。 所以(P?Q) ∧Q?P 解

24、法2： 由體題可知，即證((P?Q)∧Q)→P是永真式。 ((P?Q)∧Q)→P ? (((P∧Q) ∨(┐P∧┐Q)) ∧Q)→P ? (┐((P∧Q) ∨(┐P∧┐Q)) ∨┐Q) ∨P ? (((┐P∨┐Q) ∧(P∨Q)) ∨┐Q) ∨P ? ((┐Q∨┐P∨┐Q) ∧(┐Q∨P∨Q)) ∨P ? ((┐Q∨┐P) ∧T) ∨P ?┐Q∨┐P∨P ?┐Q∨T ?T 〔6〕 解： P：我學(xué)習(xí) Q：我數(shù)學(xué)不及格 R：我熱衷于玩撲克?！? 如果我學(xué)習(xí)，那么我數(shù)學(xué)不會不及格： P→┐Q 如果我不熱衷于玩撲克，那么我將學(xué)習(xí):

25、 ┐R→P 但我數(shù)學(xué)不及格: Q 因此我熱衷于玩撲克。 R 即此題符號化為：(P→┐Q)∧(┐R→P)∧Q?R 證： 證法1：((P→┐Q)∧(┐R→P)∧Q)→R ? ┐((┐P∨┐Q)∧(R∨P)∧Q) ∨R ? (P∧Q)∨(┐R∧┐P)∨┐Q∨R ? ((┐Q∨P)∧(┐Q∨Q))∨((R∨┐R)∧(R∨┐P)) ? ┐Q∨P∨R∨┐P ? T　 所以，論證有效。 證法2：設(shè)(P→┐Q)∧(┐R→P)∧Q為T， 那么因Q為T，(P→┐Q) 為T，可得P為F， 由(┐R→P)為

26、T，得到R為T。 故此題論證有效。 〔7〕 解： P：6是偶數(shù) Q：7被2除盡 R：5是素數(shù) 如果6是偶數(shù)，那么7被2除不盡 P→┐Q 或5不是素數(shù)，或7被2除盡 ┐R∨Q 5是素數(shù) R 所以6是奇數(shù) ┐P 即此題符號化為：〔P→┐Q〕∧〔┐R∨Q〕∧R ?┐P 證： 證法1：((P→┐Q)∧(┐R∨Q)∧R)→┐P ? ┐((┐P∨┐Q) ∧(┐R∨Q) ∧R) ∨┐P ? ((P∧Q) ∨(R∧┐Q) ∨┐R) ∨┐P ?

27、((┐P∨P) ∧(┐P∨Q)) ∨((┐R∨R) ∧(┐R∨┐Q)) ? (┐P∨Q) ∨(┐R∨┐Q) ?T　 所以，論證有效，但實際上他不符合實際意義。 證法2：(P→┐Q)∧(┐R∨Q)∧R為T， 那么有R為T，且┐R∨Q 為T，故Q為T， 再由P→┐Q為T，得到┐P為T。 〔8〕 證明： a) P?(┐P→Q) 設(shè)P為T，那么┐P為F，故┐P→Q為T b) ┐A∧B∧C?C 假定┐A∧B∧C為T，那么C為T。 c) C?A∨B∨┐B 因為A∨B∨┐B為永真，所以C?A∨B∨┐B成立。 d) ┐(A∧B) ?┐A∨┐B 設(shè)┐(A∧B)為T，那么A∧B

28、為F。 假設(shè)A為T，B為F，那么┐A為F，┐B為T，故┐A∨┐B為T。 假設(shè)A為F，B為T，那么┐A為T，┐B為F，故┐A∨┐B為T。 假設(shè)A為F，B為F，那么┐A為T，┐B為T，故┐A∨┐B為T。 命題得證。 e) ┐A→(B∨C)，D∨E，(D∨E)→┐A?B∨C 設(shè)┐A→(B∨C)，D∨E，(D∨E)→┐A為T， 那么D∨E為T，(D∨E)→┐A為T，所以┐A為T 又┐A→(B∨C)為T，所以B∨C為T。命題得證。 f) (A∧B)→C，┐D，┐C∨D?┐A∨┐B 設(shè)(A∧B)→C，┐D，┐C∨D為T，那么┐D為T，┐C∨D為T，所以C為F 又(A∧B)→C為T，所

29、以A∧B為F，所以┐A∨┐B為T。命題得證。 〔9〕解： a) 如果他有勇氣，他將得勝。 P：他有勇氣 Q：他將得勝 原命題：P→Q 逆反式：┐Q→┐P 表示：如果他失敗了，說明他沒勇氣。 b) 僅當(dāng)他不累他將得勝。 P：他不累 Q：他得勝 原命題：Q→P 逆反式：┐P→┐Q 表示：如果他累，他將失敗。 習(xí)題 1-6 (1)解： a) (P∧Q)∧┐P?(P∧┐P)∧Q?┐(T∨Q) b) (P→(Q∨┐R)) ∧┐P∧Q ? (┐P∨(Q∨┐R))∧┐P∧Q ?(┐P∧┓P∧Q)∨(Q∧┓P

30、∧Q)∨(┓R∧┓P∧Q) ?(┓P∧Q)∨(┓P∧Q)∨(┓P∧┓R∧Q) ?┓P∧Q ?┐(P∨┐Q) c) ┐P∧┐Q∧(┐R→P) ?┐P∧┐Q∧(R∨P) ?(┐P∧┐Q∧R)∨(┐P∧┐Q∧P) ?(┐P∧┐Q∧R)∨F ?┐P∧┐Q∧R ?┐(P∨Q∨┐R) (2) 解： a)┐P? P↓P b)P∨Q?┐(P↓Q) ? (P↓Q)↓(P↓Q) c)P∧Q?┐P↓┐Q? (P↓P)↓(Q↓Q) (3)解： P→(┐P→Q) ?┐P∨(P∨Q) ?T ?┐P∨P ? (┐P↑┐P)↑(P↑P) ?P↑(P↑P) P→(┐P

31、→Q) ?┐P∨(P∨Q) ?T ?┐P∨P ?┐(┐P↓P) ?┐((P↓P)↓P) ?((P↓P)↓P)↓((P↓P)↓P) (4)解： P↑Q ?┐(┐P↓┐Q) ?┐((P↓P)↓(Q↓Q)) ? ((P↓P)↓(Q↓Q))↓((P↓P)↓(Q↓Q)) (5)證明： ┐(B↑C) ?┐(┐B∨┐C) ? ┐B↓┐C ┐(B↓C) ?┐(┐B∧┐C) ?┐B↑┐C (6)解：聯(lián)結(jié)詞“↑〞和“↓〞不滿足結(jié)合律。舉例如下： a)給出一組指派：P為T，Q為F，R為F，那么(P↑Q)↑R為T，P↑(Q↑R)為F 故 (P↑Q)↑R P↑(Q

32、↑R). b)給出一組指派：P為T，Q為F，R為F，那么(P↓Q) ↓R為T，P↓(Q↓R)為F 故(P↓Q)↓R P↓(Q↓R). (7)證明： 設(shè)變元P，Q，用連結(jié)詞?,┐作用于P，Q得到：P，Q，┐P，┐Q，P?Q，P?P，Q?Q，Q?P。 但P?Q?Q?P，P?P?Q?Q，故實際有： P，Q，┐P，┐Q，P?Q，P?P〔T〕 〔A〕 用┐作用于〔A〕類，得到擴大的公式類〔包括原公式類〕： P，Q，┐P，┐Q，┐〔P?Q〕， T，F(xiàn)， P?Q 〔B〕 用?作用于〔A〕類，得到： P?

33、Q，P?┐P?F，P?┐Q?┐〔P?Q〕，P?〔P?Q〕?Q，P?〔P?P〕?P， Q?┐P?┐〔P?Q〕，Q?┐Q?F，Q?〔P?Q〕?P，Q?T?Q, ┐P?┐Q?P?Q，┐P?〔P?Q〕?┐Q，┐P?T?┐P, ┐Q?〔P?Q〕?┐P，┐Q?T?┐Q, 〔P?Q〕?〔P?Q〕?P?Q. 因此，〔A〕類使用運算后，仍在〔B〕類中。 對〔B〕類使用┐運算得： ┐P，┐Q，P，Q， P?Q， F，T， ┐〔P?Q〕， 仍在〔B〕類中。 對〔B〕類使用?運算得： P?Q，P?┐P?F，P?┐Q?┐〔P?Q〕，P?┐〔P?Q〕?┐Q，P?T?P，P?F?┐P，P?〔P

34、?Q〕?Q， Q?┐P?┐〔P?Q〕，Q?┐Q?F，Q?┐〔P?Q〕?┐P，Q?T?Q, Q?F?┐Q， Q?〔P?Q〕?P， ┐P?┐Q?P?Q，┐P?┐〔P?Q〕?Q，┐P?T?┐P, ┐P?F?P,┐P?〔P?Q〕?┐Q， ┐Q?┐〔P?Q〕?P，┐Q?T?┐Q, ┐Q?T?┐Q,┐Q?〔P?Q〕?┐P， ┐〔P?Q〕?T?┐〔P?Q〕，┐〔P?Q〕?F?P?Q，┐〔P?Q〕?〔P?Q〕?F T?F?F，T?〔P?Q〕? P?Q F?〔P?Q〕? ┐〔P?Q〕 〔P?Q〕?〔P?Q〕?P?Q. 故由〔B〕類使用?運算后，結(jié)果仍在〔B〕中。 由上證明：用?,┐兩個連

35、結(jié)詞，反復(fù)作用在兩個變元的公式中，結(jié)果只能產(chǎn)生〔B〕類中的公式，總共僅八個不同的公式，故{?,┐}不是功能完備的，更不能是最小聯(lián)結(jié)詞組。 已證{?,┐}不是最小聯(lián)結(jié)詞組，又因為P Q? ┐〔P?Q〕，故任何命題公式中的聯(lián)結(jié)詞，如僅用{ , ┐}表達，那么必可用{?,┐}表達，其逆亦真。故{ , ┐}也必不是最小聯(lián)結(jié)詞組。 (8)證明{∨}，{∧}和{→}不是最小聯(lián)結(jié)詞組。 證明：假設(shè){∨}，{∧}和{→}是最小聯(lián)結(jié)詞，那么 ┐P?〔P∨P∨……〕 ┐P?〔P∧P∧……〕 ┐P?P→(P→(P→……) 對所有命題變元指派T

36、，那么等價式左邊為F，右邊為T，與等價表達式矛盾。 所以{∨}，{∧}和{→}不是最小聯(lián)結(jié)詞。 (9)證明{┐,→}和{┐, }是最小聯(lián)結(jié)詞組。 證明：因為{┐,∨}為最小聯(lián)結(jié)詞組，且P∨Q?┐P→Q 所以{┐,→}是功能完備的聯(lián)結(jié)詞組，又{┐},{→}都不是功能完備的聯(lián)結(jié)詞組。 所以{┐,→}是最小聯(lián)結(jié)詞組。 又因為P→Q?┐(P Q)，所以{┐, }是功能完備的聯(lián)結(jié)詞組，又{┐},{ }不是功能完備的聯(lián)結(jié)詞組， 所以{┐, }是最小聯(lián)結(jié)詞組。 習(xí)題 1-7 (1) 解： P∧(P→Q) ?P∧(┐P∨Q) ? (P∧┐P)∨(P∧Q)

37、 P∧(P→Q) ? (P∨(┐Q∧Q))∧(┐P∨Q) ? (P∨┐Q)∧(P∨Q)∧(┐P∨Q) (2) 解： a) (┐P∧Q)→R ?┐(┐P∧Q)∨R ? P∨┐Q∨R ?(P∧Q)∨(P∧┐Q) ∨(┐Q∧R)∨(┐Q∧┐R)∨(R∧P)∨(R∧┐P) b) P→((Q∧R)→S) ?┐P∨(┐(Q∧R)∨S) ?┐P∨┐Q∨┐R∨S ?(┐P∧Q)∨(┐P∧┐Q) ∨(┐Q∧R)∨(┐Q∧┐R)∨(┐R∧S)∨(┐R∧┐S)∨(S∧P)∨(S∧┐P) c) ┐(P∨┐Q)∧(S→T) ?(┐P∧Q)∧(┐S∨T) ?(┐P∧Q∧┐S)

38、∨(┐P∧Q∧T) d) (P→Q)→R ?┐(┐P∨Q)∨R ?(P∧┐Q)∨R ?(P∨R)∧(┐Q∨R) e) ┐(P∧Q)∧(P∨Q) ?(┐P∨┐Q)∧(P∨Q) ?(┐P∧P)∨(┐P∧Q)∨(┐Q∧P)∨(┐Q∧Q) ? (┐P∧Q)∨(┐Q∧P) (3) 解： a) P∨(┐P∧Q∧R) ?(P∨┐P)∧(P∨Q)∧(P∨R) ?(P∨Q)∧(P∨R) b) ┐(P→Q)∨(P∨Q) ?┐(┐P∨Q)∨(P∨Q) ?(P∧┐Q)∨(P∨Q) ?(P∨P∨Q)∧(┐Q∨P∨Q) c) ┐(P→Q) ?┐(┐P∨Q) ?

39、P∧┐Q ?(P∨Q)∧(P∨┐Q)∧(┐Q∨┐P) d) (P→Q)→R ?┐(┐P∨Q)∨R ? (P∧┐Q)∨R ? (P∨R)∧(┐Q∨R) e) (┐P∧Q)∨(P∧┐Q) ?(┐P∨P)∧(┐P∨┐Q)∧(Q∨P)∧(Q∨┐Q) ?(┐P∨┐Q)∧(Q∨P) (4) 解： a) (┐P∨┐Q)→(P?┐Q) ?┐(┐P∨┐Q) ∨(P?┐Q) ? (P∧Q) ∨(P∧┐Q)∨(┐P∧Q) ??1，2，3 ?P∨Q=?0 b) Q∧(P∨┐Q) ? (P∧Q)∨(Q∧┐Q) ? P∧Q =?3 ??0，1，2 ?(P∨Q)∧(P∨┐Q) ∧(

40、┐P∨Q) c) P∨(┐P→(Q∨(┐Q→R)) ?P∨(P∨(Q∨(Q∨R)) ?P∨Q∨R=?0 ??1，2，3,4,5,6,7 =(┐P∧┐Q∧R) ∨(┐P∧Q∧┐R) ∨(┐P∧Q∧R) ∨(P∧┐Q∧┐R) ∨(P∧┐Q∧R) ∨(P∧Q∧┐R) ∨(P∧Q∧R) d) (P→(Q∧R) )∧(┐P→(┐Q∧┐R)) ? (┐P∨(Q∧R)) ∧(P∨(┐Q∧┐R)) ? (P∧┐P) ∨(P∧(Q∧R)) ∨ ((┐Q∧┐R) ∧┐P) ∨((┐Q∧┐R) ∧(Q∧R)) ? (P∧Q∧R) ∨(┐P∧┐Q∧┐R) =?0,7 ??1，2，3,4,5,6

41、 ? (P∨Q∨┐R) ∧(P∨┐Q∨R) ∧(P∨┐Q∨┐R) ∧(┐P∨Q∨R) ∧(┐P∨Q∨┐R) ∧(┐P∨┐Q∨R) e) P→(P∧(Q→P) ?┐P∨(P∧(┐Q∨P) ?(┐P∨P)∧(┐P∨┐Q∨P) ?T∨(T∧┐Q) ?T ??0,1,2,3= (┐P∧┐Q) ∨(┐P∧Q) ∨(P∧┐Q) ∨(P∧Q) f) (Q→P) ∧(┐P∧Q) ? (┐Q∨P) ∧┐P∧Q ? (┐Q∨P) ∧┐(P∨┐Q) ?F ??0,1，2，3= (P∨Q) ∧(P∨┐Q) ∧(┐P∨Q) ∧(┐P∨┐Q) (5) 證明： a) (A→B) ∧(A→C

42、) ? (┐A∨B) ∧(┐A∨C) A→(B∧C) ?┐A∨(B∧C) ? (┐A∨B) ∧(┐A∨C) b) (A→B) →(A∧B) ?┐(┐A∨B) ∨(A∧B) ? (A∧┐B) ∨(A∧B) ?A∧(B∨┐B) ?A∧T ?A (┐A→B) ∧(B→A) ? (A∨B) ∧(┐B∨A) ?A∨(B∧┐B) ?A∨F ?A c) A∧B∧(┐A∨┐B) ? ((A∧┐A)∨(A∧┐B))∧B ?A∧B∧┐B ?F ┐A∧┐B∧(A∨B) ? ((┐A∧A)∨(┐A∧B))∧┐B ?┐A∧┐B∧B ?F d)

43、A∨(A→(A∧B) ?A∨┐A∨(A∧B) ?T ┐A∨┐B∨(A∧B) ?┐(A∧B) ∨(A∧B) ?T (6)解：A?R↑(Q∧┐(R↓P)),那么A*? R↓(Q∨┐(R↑P)) A?R↑(Q∧┐(R↓P)) ?┐(R∧(Q∧(R∨P))) ?┐R∨┐Q∨┐(R∨P) ?┐(R∧Q) ∨┐(R∨P) A*?R↓(Q∨┐(R↑P)) ?┐(R∨(Q∨(R∧P)) ?┐R∧┐Q∧┐(R∧P) ?┐(R∨Q) ∧┐(R∧P) (7) 解：設(shè)A：A去出差。B：B去出差。C：C去出差。D：D去出差。 假設(shè)A去那么C和D中要去一個。 A→(C D)

44、B和C不能都去。 ┐(B∧C) C去那么D要留下。 C→┐D 按題意應(yīng)有：A→(C D)，┐(B∧C)，C→┐D必須同時成立。 因為C D ? (C∧┐D) ∨(D∧┐C) 故(A→(C D))∧┐(B∧C) ∧(C→┐D) ? (┐A∨(C∧┐D) ∨(D∧┐C)) ∧┐(B∧C) ∧(┐C∨┐D) ? (┐A∨(C∧┐D) ∨(D∧┐C)) ∧(┐B∨┐C) ∧(┐C∨┐D) ? (┐A∨(C∧┐D) ∨(D∧┐C)) ∧((┐B∧┐C) ∨(┐B∧┐D) ∨(┐C∧┐D) ∨┐C) ? (┐A∧┐B∧┐C) ∨(┐A∧┐B∧┐D)

45、 ∨(┐A∧┐C∧┐D) ∨(┐A∧┐C) ∨(┐B∧┐C∧D) ∨(┐C∧D∧┐B∧┐D) ∨(┐C∧D∧┐C∧┐D) ∨(┐C∧D∧┐C) ∨(┐D∧C∧┐B∧┐C) ∨(┐D∧C∧┐B∧┐D) ∨(┐D∧C∧┐C∧┐D) ∨(┐D∧C∧┐C) 在上述的析取范式中，有些〔畫線的〕不符合題意，舍棄，得 (┐A∧┐C) ∨(┐B∧┐C∧D) ∨〔┐C∧D〕∨(┐D∧C∧┐B) 故分派的方法為：B∧D ,或 D∧A,或 C∧A。 (8) 解：設(shè)P：A是第一。Q：B是第二。R：C是第二。S：D是第四。E：A是第二。 由題意得 (P Q) ∧(R S) ∧(E S)

46、? ((P∧┐Q) ∨(┐P∧Q)) ∧((R∧┐S) ∨(┐R∧S)) ∧((E∧┐S) ∨(┐E∧S)) ? ((P∧┐Q∧R∧┐S) ∨(P∧┐Q∧┐R∧S) ∨(┐P∧Q∧R∧┐S) ∨(┐P∧Q∧┐R∧S))∧((E∧┐S)∨(┐E∧S)) 因為 (P∧┐Q∧┐R∧S)與(┐P∧Q∧R∧┐S)不合題意，所以原式可化為 ((P∧┐Q∧R∧┐S) ∨(┐P∧Q∧┐R∧S))∧((E∧┐S) ∨(┐E∧S)) ? (P∧┐Q∧R∧┐S∧E∧┐S) ∨(P∧┐Q∧R∧┐S∧┐E∧S) ∨(┐P∧Q∧┐R∧S∧E∧┐S)∨(┐P∧Q∧┐R∧S∧┐E∧S) ? (

47、P∧┐Q∧R∧┐S∧E) ∨(┐P∧Q∧┐R∧S∧┐E) 因R與E矛盾，故┐P∧Q∧┐R∧S∧┐E為真， 即A不是第一，B是第二，C不是第二，D為第四，A不是第二。 于是得： A是第三 B是第二 C是第一 D是第四。 習(xí)題1-8 (1)證明： a)┐(P∧┐Q)，┐Q∨R，┐R?┐P (1) ┐R P (2) ┐Q∨R P (3) ┐Q (1)(2)T,I (4) ┐(P∧┐Q) P (5) ┐P∨Q (4)T,E (6) ┐P (3)(

48、5)T,I b)J→(M∨N)，(H∨G)→J，H∨G?M∨N (1) (H∨G) →J P (2) (H∨G) P (3) J (1)(2)T,I (4) J→(M∨N) P (5) M∨N (3)(4)T,I c)B∧C，(B?C)→(H∨G)??G∨H (1) B∧C P (2) B (1)T,I (3) C (1)T,I (4) B∨┐C (2)T,I (5) C∨┐B

49、(3)T,I (6) C→B (4)T,E (7) B→C (5)T,E (8) B?C (6)(7)T,E (9) (B?C) →(H∨G) P (10) H∨G (8)(9)T,I d)P→Q，(┐Q∨R)∧┐R，┐(┐P∧S)??┐S (1) (┐Q∨R) ∧┐R (2) ┐Q∨R (1)T,I (3) ┐R (1)T,I (4) ┐Q (2)(3)T,I (5) P→Q

50、 P (6) ┐P (4)(5)T,I (7) ┐(┐P∧┐S) P (8) P∨┐S (7)T,E (9) ┐S (6)(8)T,I (2) 證明： a)┐A∨B，C→┐B?A→┐C (1) ┐(A→┐C) P (2) A (1)T,I (3) C (1)T,I (4) ┐A∨B

51、 P (5) B (2)(4)T,I (6) C→┐B P (7) ┐B (3)(6)T,I (8) B∧┐B 矛盾。(5),(7) b)A→(B→C)，(C∧D)→E，┐F→(D∧┐E)??A→(B→F) (1) ┐(A→(B→F)) P (2) A (1)T,I (3) ┐(B→F) (1)T,I (4)

52、B (3)T,I (5) ┐F (3)T, (6) A→(B→C) P (7) B→C (2)(6)T,I (8) C (4)(7)T,I (9) ┐F→(D∧┐E) P (10) D∧┐E (5)(9)T,I (11) D (10)T,I (12) C∧D

53、 (8)(11)T,I (13) (C∧D) →E P (14) E (12)(13)T,I (15) ┐E (10)T,I (16) E∧┐E 矛盾。(14),(15) c)A∨B→C∧D，D∨E→F?A→F (1) ┐(A→F) P (2) A (1)T,I (3) ┐F (1)T,I

54、 (4) A∨B (2)T,I (5) (A∨B) →C∧D P (6) C∧D (4)(5)T,I (7) C (6)T,I (8) D (6)T,I (9) D∨E (8)T,I (10) D∨E→F P (11) F (9)(10)T,I (12) F∧┐F

55、 矛盾。(3),(11) d)A→(B∧C)，┐B∨D，(E→┐F)→┐D，B→(A∧┐E)??B→E (1) ┐(B→E) P (2) B (1)T,I (3) ┐E (1)T,I (4) ┐B∨D P (5) D (2)(4)T,I (6) (E→┐F) →┐D P (7) ┐(E→┐F) (

56、5)(6)T,I (8) E (7)T,I (9) E∧┐E 矛盾 e)(A→B)∧(C→D)，(B→E)∧(D→F)，┐(E∧F)，A→C?┐A (1) (A→B) ∧(C→D) P (2) A→B (1)T,I (3) (B→E) ∧(D→F) P (4) B→E (3)T,I (5) A→E (2)(4)T,I (6) ┐(E∧F)

57、 P (7) ┐E∨┐F (6)T,E (8) E→┐F (7)T,E (9) A→┐F (5)(8)T,I (10) C→D (1)T,I (11) D→F (3)T,I (12) C→F (10)(10)T,I (13) A→C P (14) A→F (

58、13)(12)T,I (15) ┐F→┐A (14)T,E (16) A→┐A (9)(15)T,I (17) ┐A∨┐A (16)T,E (18) ┐A (17) T,E (3) 證明： a)┐A∨B，C→┐B?A→┐C (1) A P (2) ┐A∨B P (3) B (1)(2)T,I (4) C→┐B

59、 P (5) ┐C (3)(4)T,I (6) A→┐C CP b)A→(B→C)，(C∧D)→E，┐F→(D∧┐E)??A→(B→F) (1) A P (2) A→(B→C) P (3) B→C (1)(2)T,I (4) B P (5) C (3)(4)T,I (6) (C∧D) →E P (7) C→(D→E) (6)T,E (8) D

60、→E (5)(7)T,I (9) ┐D∨E (8)T,E (10) ┐(D∧┐E) (9)T,E (11) ┐F→(D∧┐E) P (12) F (10)(11)T,I (13) B→F CP (14) A→(B→F) CP c)A∨B→C∧D，D∨E→F?A→F (1) A P (2) A∨B (1)T,I (3) A∨B→C∨D P (4) C∧D

61、 (2)(3)T,I (5) D (4)T,I (6) D∨E (5)T,I (7) D∨E→F P (8) F (6)(7)T,I (9) A→F CP d)A→(B∧C)，┐B∨D，(E→┐F)→┐D，B→(A∧┐E)??B→E (1) B P(附加前提) (2) ┐B∨D P (3) D

62、(1)(2)T,I (4) (E→┐F)→┐D P (5) ┐(E→┐F) (3)(4)T,I (6) E (5)T,I (7) B→E CP (4)證明： a) R→┐Q，R∨S，S→┐Q，P→Q?┐P (1) R→┐Q P (2) R∨S P (3) S→┐Q P (4) ┐Q (1)(2)(3)T,I (5) P→Q

63、 P (6) ┐P (4)(5)T,I b) S→┐Q，S∨R，┐R，┐P?Q?P 證法一： (1) S∨R P (2) ┐R P (3) S (1)(2)T,I (4) S→┐Q P (5) ┐Q (3)(4)T,I (6) ┐P?Q P (7)(┐P→Q)∧(Q→┐P) (6)T,E (8) ┐P→Q

64、 (7)T,I (9) P (5)(8)T,I 證法二：〔反證法〕 (1) ┐P P〔附加前提〕 (2) ┐P?Q P (3)〔┐P→Q〕∧〔 Q→┐P〕 (2)T，E (4) ┐P→Q (3)T,I (5) Q (1)(4)T,I (6) S→┐Q P (7) ┐S (5)(6)T,I (8) S∨R

65、 P (9) R (7)(8)T,I (10) ┐R P (11) ┐R∧R 矛盾〔9〕〔10〕T，I c)┐(P→Q)→┐(R∨S)，((Q→P)∨┐R)，R?P?Q (1) R P (2) (Q→P) ∨┐R P (3) Q→P (1)(2)T,I (4)┐(P→Q) →┐(R∨S) P (5) (R∨S) →(P→Q)

66、 (4)T,E (6) R∨S (1)T,I (7) P→Q (5)(6) (8) (P→Q) ∧(Q→P) (3)(7)T,I (9) P?Q (8)T,E (5) 解： a) 設(shè)P：我跑步。Q：我很疲勞。 前提為：P→Q，┐Q (1) P→Q P (2) ┐Q P (3) ┐P (1)(2)T,I 結(jié)論為：┐P，我沒有跑步。 b) 設(shè)S：他犯了錯誤。 R：他神色慌張。 前提為：S→R，R 因為〔S→R〕∧R?〔┐S∨R〕∧R?R。故此題沒有確定的結(jié)論。 實際上，假設(shè)S →R為真，R為真,那么S可為真，S也可為假，故無有效結(jié)論。 c) 設(shè)P：我的程序通過。 Q：我很快樂。 R：陽光很好。 S：天很暖和?！舶淹砩鲜稽c理解為陽光不好〕 前提