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

1、1-1，1-2 （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：王強(qiáng)身體很好。Q：王強(qiáng)成績很好。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的對邊平行。PQ f) 設(shè)P：語法錯誤。Q：程序錯誤。R：停機(jī)。（P∨ Q）→ R (6) 解：

3、a) P:天氣炎熱。Q:正在下雨。 P∧Q b) P:天氣炎熱。R:濕度較低。 P∧R c) R:天正在下雨。S:濕度很高。 R∨S d) A:劉英上山。B:李進(jìn)上山。 A∧B e) M:老王是革新者。N:小李是革新者。 M∨N f) L:你看電影。M:我看電影。 ┓L→┓M g) P:我不看電視。Q:我不外出。 R:我在睡覺。 P∧Q∧R h) P:控制臺打字機(jī)作輸入設(shè)備。Q:控制臺打字機(jī)作輸出設(shè)備。P∧Q 1-3 （1）解： a) 不是合式公式，沒有規(guī)定運(yùn)算符次序（若規(guī)定運(yùn)算符次序后亦可作為合式公式） 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) 式進(jìn)行代換得到，在c) 中用Q代換P, (P→P)代換Q. d) 是由a) 式進(jìn)行代換得到，在a) 中用 P→(Q→P)代換Q. e) 是由b) 式進(jìn)行代換得到，用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→(QR) （6）解： P:它占據(jù)空間。 Q:它有質(zhì)量。

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

7、 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 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　 Ｔ Ｔ Ｔ Ｆ Ｔ Ｔ Ｔ Ｆ Ｔ Ｔ Ｔ Ｔ Ｔ Ｔ Ｔ Ｆ　 　

8、　　Ｔ 　　?。? 　　　Ｔ 　　?。? 　　?。? 　　?。? 　　?。? 　　　Ｆ 　　?。? 　　　Ｔ 　　　Ｔ 　　?。? 　　　Ｔ 　　?。? 　　?。? 　　?。? 所以，P∨(Q∨R) (P∨Q)∨R　 ｃ） Ｐ　Ｑ?。? Ｑ∨Ｒ Ｐ∧（Ｑ∨Ｒ） Ｐ∧Ｑ Ｐ∧Ｒ （Ｐ∧Ｑ）∨（Ｐ∧Ｒ） Ｔ?。浴。? Ｔ?。浴。? Ｔ　Ｆ?。? Ｔ?。啤。? Ｆ?。浴。? Ｆ?。浴。? Ｆ?。啤。? Ｆ　Ｆ?。? Ｔ Ｔ Ｔ Ｆ Ｔ Ｔ Ｔ Ｆ Ｔ Ｔ Ｔ Ｆ Ｆ Ｆ Ｆ Ｆ Ｔ Ｔ Ｆ Ｆ Ｆ Ｆ Ｆ Ｆ Ｔ Ｆ Ｔ

9、 Ｆ Ｆ Ｆ Ｆ Ｆ Ｔ Ｔ Ｔ Ｆ Ｆ Ｆ Ｆ Ｆ 所以，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 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，可表達(dá)為 P Q R F1 F2 F3 F4

10、 F5 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 T F T T T F F F F F T F T T T

11、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 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

12、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.┓(PQ) 8.┓(P∧Q) 9.P∧Q 10.PQ 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) ┐

13、(AB) ┐((A∧B)∨(┐A∧┐B)) ┐((A∧B)∨┐(A∨B)) (A∨B)∧┐(A∧B) 或 ┐(AB) ┐((A→B)∧(B→A)) ┐((┐A∨B)∧(┐B∨A)) ┐((┐A∧┐B)∨(┐A∧A)∨(B∧┐B)∨(B∧A)) ┐((┐A∧┐B)∨(B∧A)) ┐(┐(A∨B))∨(A∧B) (A∨B)∧┐(A∧B) c) ┐(A→B) ┐(┐A∨B) A∧┐B d) ┐(AB)┐((A→B)∧(B→A)) ┐((┐A∨B)∧(┐B∨A)) (A∧┐B)∨(┐A∧B) e) (((A∧B∧C)→D)∧(C→(A∨B∨D))) (┐(A∧B∧

14、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 (((A∧B)∨(┐A∧┐B))∧C)→D ((C∧(AB))→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)∧(┐

15、B∨(D∨C)) (┐(A∧B)∧(┐B∨D))∨C (┐(A∧B) ∧┐(┐D∧B))∨C ┐((A∧B)∨(┐D∧B))∨C ((A∨┐D)∧B)→C (B∧(D→A))→C （8）解： a) ((A→B) (┐B→┐A))∧C ((┐A∨B) (B∨┐A))∧C ((┐A∨B) (┐A∨B))∧C T∧CC 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∨CB∨C，但A

16、B不成立。 2）設(shè)C為F，A為T，B為F，則滿足A∧CB∧C，但AB不成立。 3）由題意知┐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)

17、∨(c∧a))(a∨b)∧(b∨c)∧(c∨a) 因為((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）若P為T，則Q為T，所以P∧Q為T，故P→(P∧Q)為T （2）若P為F，則Q為F，所以P∧Q為F，P→(P∧Q)為T 命題得證 解法2： 設(shè)P→(P∧Q)為F，則P為T，(P∧Q)為F，故必有

18、P為T，Q為F，所以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)→QP∨Q 設(shè)P∨Q為F，則P為F，且Q為F， 故P→Q為T，(P→Q)→Q為F， 所以(P→Q)→QP∨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)))

19、為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è)S：你走了

20、。R：我將留下。R→S 逆換式S→R表示命題：如果你走了則我將留下。 逆反式┐S→┐R表示命題：如果你不走，則我不留下。 c) 如果我不能獲得更多幫助，我不能完成個任務(wù)。 設(shè)E：我不能獲得更多幫助。H：我不能完成這個任務(wù)。E→H 逆換式H→E表示命題：我不能完成這個任務(wù)，則我不能獲得更多幫助。 逆反式┐H→┐E表示命題：我完成這個任務(wù)，則我能獲得更多幫助 （5） 試證明PQ，Q邏輯蘊(yùn)含P。 證明：解法1： 本題要求證明(PQ) ∧QP, 設(shè)(PQ) ∧Q為T，則(PQ)為T，Q為T，故由的定義，必有P為T。 所以(PQ) ∧QP 解法2： 由體題可知，即證((PQ)

21、∧Q)→P是永真式。 ((PQ)∧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í): ┐R→P 但我數(shù)學(xué)不及格: Q 因此我熱衷于玩撲克。 R 即本題符號化為

22、：(P→┐Q)∧(┐R→P)∧QR 證： 證法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)為T，得到R為T。 故本題論證有效。 （7） 解： P：6是偶數(shù) Q：7被2除盡 R：5是素數(shù) 如果6是偶數(shù)，則7被2除不盡 P→┐Q 或5不是素數(shù)，或7被2除

23、盡 ┐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 ((┐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)

24、P(┐P→Q) 設(shè)P為T，則┐P為F，故┐P→Q為T b) ┐A∧B∧CC 假定┐A∧B∧C為T，則C為T。 c) CA∨B∨┐B 因為A∨B∨┐B為永真，所以CA∨B∨┐B成立。 d) ┐(A∧B) ┐A∨┐B 設(shè)┐(A∧B)為T，則A∧B為F。 若A為T，B為F，則┐A為F，┐B為T，故┐A∨┐B為T。 若A為F，B為T，則┐A為T，┐B為F，故┐A∨┐B為T。 若A為F，B為F，則┐A為T，┐B為T，故┐A∨┐B為T。 命題得證。 e) ┐A→(B∨C)，D∨E，(D∨E)→┐AB∨C 設(shè)┐A→(B∨C)，D∨E，(D∨E)→┐A為T， 則D∨E為T，(D∨

25、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，所以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

26、) (P∧Q)∧┐P(P∧┐P)∧Q┐(T∨Q) b) (P→(Q∨┐R)) ∧┐P∧Q (┐P∨(Q∨┐R))∧┐P∧Q (┐P∧┓P∧Q)∨(Q∧┓P∧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→(

27、┐P→Q) ┐P∨(P∨Q) T ┐P∨P (┐P↑┐P)↑(P↑P) P↑(P↑P) P→(┐P→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，

28、R為F，則(P↑Q)↑R為T，P↑(Q↑R)為F 故 (P↑Q)↑R P↑(Q↑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，PQ，PP，QQ，QP。 但PQQP，PPQQ，故實際有： P，Q，┐P，┐Q，PQ，PP（T） （A） 用┐作用于（A）類，得到擴(kuò)大的公式類（包括原公式類）： P，Q，┐P，┐Q，┐（PQ）， T，F(xiàn)， PQ

29、 （B） 用作用于（A）類，得到： PQ，P┐PF，P┐Q┐（PQ），P（PQ）Q，P（PP）P， Q┐P┐（PQ），Q┐QF，Q（PQ）P，QTQ, ┐P┐QPQ，┐P（PQ）┐Q，┐PT┐P, ┐Q（PQ）┐P，┐QT┐Q, （PQ）（PQ）PQ. 因此，（A）類使用運(yùn)算后，仍在（B）類中。 對（B）類使用┐運(yùn)算得： ┐P，┐Q，P，Q， PQ， F，T， ┐（PQ）， 仍在（B）類中。 對（B）類使用運(yùn)算得： PQ，P┐PF，P┐Q┐（PQ），P┐（PQ）┐Q，PTP，PF┐P，P（PQ）Q， Q┐P┐（PQ），Q┐QF，Q┐（PQ）┐P

30、，QTQ, QF┐Q， Q（PQ）P， ┐P┐QPQ，┐P┐（PQ）Q，┐PT┐P, ┐PFP,┐P（PQ）┐Q， ┐Q┐（PQ）P，┐QT┐Q, ┐QT┐Q,┐Q（PQ）┐P， ┐（PQ）T┐（PQ），┐（PQ）FPQ，┐（PQ）（PQ）F TFF，T（PQ） PQ F（PQ） ┐（PQ） （PQ）（PQ）PQ. 故由（B）類使用運(yùn)算后，結(jié)果仍在（B）中。 由上證明：用,┐兩個連結(jié)詞，反復(fù)作用在兩個變元的公式中，結(jié)果只能產(chǎn)生（B）類中的公式，總共僅八個不同的公式，故{,┐}不是功能完備的，更不能是最小聯(lián)結(jié)詞組。 ∨ 已證{,┐}不是最小聯(lián)結(jié)詞組，又因為P Q

31、┐（PQ），故任何命題公式中的聯(lián)結(jié)詞，如僅用{ , ┐}表達(dá)，則必可用{,┐}表達(dá)，其逆亦真。故{ , ┐}也必不是最小聯(lián)結(jié)詞組。 (8)證明{∨}，{∧}和{→}不是最小聯(lián)結(jié)詞組。 證明：若{∨}，{∧}和{→}是最小聯(lián)結(jié)詞，則 ┐P（P∨P∨……） ┐P（P∧P∧……） ┐PP→(P→(P→……) 對所有命題變元指派T，則等價式左邊為F，右邊為T，與等價表達(dá)式矛盾。 → c 所以{∨}，{∧}和{→}不是最小聯(lián)結(jié)詞。 (9)證明{┐,→}和{┐, }是最小聯(lián)結(jié)詞組。 證明：因為{┐,∨}為最小聯(lián)結(jié)詞組，且P∨Q┐P→Q 所以{┐,→}是功能

32、完備的聯(lián)結(jié)詞組，又{┐},{→}都不是功能完備的聯(lián)結(jié)詞組。 → c → c → c 所以{┐,→}是最小聯(lián)結(jié)詞組。 → c 又因為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) 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)∨(

33、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)∨(┐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) (

34、┐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) 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) 解：

35、 a) (┐P∨┐Q)→(P┐Q) ┐(┐P∨┐Q) ∨(P┐Q) (P∧Q) ∨(P∧┐Q)∨(┐P∧Q) 1，2，3 P∨Q=P0 b) Q∧(P∨┐Q) (P∧Q)∨(Q∧┐Q) P∧Q =3 P0，1，2 (P∨Q)∧(P∨┐Q) ∧(┐P∨Q) c) P∨(┐P→(Q∨(┐Q→R)) P∨(P∨(Q∨(Q∨R)) P∨Q∨R=P0 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

36、∧┐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 P1，2，3,4,5,6 (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

37、→P) ∧(┐P∧Q) (┐Q∨P) ∧┐P∧Q (┐Q∨P) ∧┐(P∨┐Q) F P0,1，2，3= (P∨Q) ∧(P∨┐Q) ∧(┐P∨Q) ∧(┐P∨┐Q) (5) 證明： a) (A→B) ∧(A→C) (┐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∧

38、(┐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) A∨(A→(A∧B) A∨┐A∨(A∧B) T ┐A∨┐B∨(A∧B) ┐(A∧B) ∨(A∧B) T (6)解：AR↑(Q∧┐(R↓P)),則A* R↓(Q∨┐(R↑P)) AR↑(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∨

39、Q) ∧┐(R∧P) (7) 解：設(shè)A：A去出差。B：B去出差。C：C去出差。D：D去出差。 若A去則C和D中要去一個。 A→(CD) B和C不能都去。 ┐(B∧C) C去則D要留下。 C→┐D 按題意應(yīng)有：A→(CD)，┐(B∧C)，C→┐D必須同時成立。 因為CD (C∧┐D) ∨(D∧┐C) 故(A→(CD))∧┐(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∧

40、┐D) ∨(┐C∧┐D) ∨┐C) (┐A∧┐B∧┐C) ∨(┐A∧┐B∧┐D) ∨(┐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是第四

41、。E：A是第二。 由題意得 (PQ) ∧(RS) ∧(ES) ((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

42、)∨(┐P∧Q∧┐R∧S∧┐E∧S) (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) ┐RP (2) ┐Q∨R P (3) ┐Q (1)(2)T,I (4) ┐(P∧┐Q) P (5) ┐P∨Q (4)T,E (6) ┐P (3)(5)T,I b)J→(M∨N)，(H∨G)→J，H∨GM∨N (1) (H∨G) →

43、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，(BC)→(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 (3)T,I (6) C→B(4)T,E (7) B→C (5)T,E (8) BC (6)(7)T,E (9) (BC) →(H∨G) P (10) H∨G(8)(9)T,I d)P→Q，(┐Q∨R)∧┐R，┐(┐P∧S) ┐S (1) (┐Q∨R) ∧┐R (2)

44、 ┐Q∨R (1)T,I (3) ┐R (1)T,I (4) ┐Q (2)(3)T,I (5) P→Q 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→┐BA→┐C (1) ┐(A→┐C) P (2) A (1)T,I (3) C (1)T,I (4) ┐A∨B 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，┐

45、F→(D∧┐E) A→(B→F) (1) ┐(A→(B→F)) P (2) A (1)T,I (3) ┐(B→F) (1)T,I (4) 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 (8)(11)T,I (13) (C∧D) →E P (14) E (12)(13)T,I (15) ┐E (10)T,I (16) E∧┐E 矛盾。(14),(

46、15) c)A∨B→C∧D，D∨E→FA→F (1) ┐(A→F) P (2) A (1)T,I (3) ┐F (1)T,I (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矛盾。(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,

47、I (4) ┐B∨D P (5) D (2)(4)T,I (6) (E→┐F) →┐D P (7) ┐(E→┐F) (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) P (7) ┐E∨┐F (6)T,E (8) E→┐F (7)T,E (9) A→┐F (5)(8)T,

48、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 (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→┐BA→┐C (1) A P (2) ┐A∨B P (3) B (1)(2)T,I (4) C→┐B P (5) ┐C (3)(4)T,I (6) A→┐C CP b)A→(B→C)，(C∧D)→E，

49、┐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→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→FA→F (1) A P (2) A∨B (1)T,I (3) A

50、∨B→C∨D P (4) C∧D(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 (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→┐

51、Q P (2) R∨S P (3) S→┐Q P (4) ┐Q (1)(2)(3)T,I (5) P→Q P (6) ┐P (4)(5)T,I b) S→┐Q，S∨R，┐R，┐PQP 證法一： (1) S∨R P (2) ┐R P (3) S (1)(2)T,I (4) S→┐Q P (5) ┐Q (3)(4)T,I (6) ┐PQ P (7)(┐P→Q)∧(Q→┐P) (6)T,E (8) ┐P→Q (7)T,I (9) P (5)(8)T,I 證法二：（反證法） (1) ┐P P（附加前提） (2) ┐PQP (3)（┐P→Q）∧（ Q→┐

52、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 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)，RPQ (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)(4)T,E (6) R∨S (1)T,I (7) P→Q(5)(6

53、) (8) (P→Q) ∧(Q→P)(3)(7)T,I (9) PQ (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）∧RR。故本題沒有確定的結(jié)論。 實際上，若S →R為真，R為真,則S可為真，S也可為假，故無有效結(jié)論。 c) 設(shè)P：我的程序通過。 Q：我很快樂。 R：陽光很好。 S：天很暖和。（把晚上十一點理解為陽光不好） 前提為：P→Q，Q→R，┐R∧S (1) P→Q P (2) Q→R P (3) P→R (1)(2)T,I (4) ┐R∨S P (5) ┐R (4)T,I (6) ┐P (3)(5)T,I 結(jié)論為： ┐P，我的程序沒有通過