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

1、1 離散數(shù)學課后習題答案_(左孝凌版)（1） 解：a) 是命題，真值為 T。b) 不是命題。c) 是命題，真值要根據(jù)具體情況確定。d) 不是命題。e) 是命題，真值為 T。f) 是命題，真值為 T。g) 是命題，真值為 F。h) 不是命題。i) 不是命題。 （2） 解：原子命題：我愛北京天安門。復合命題：如果不是練健美操，我就出外旅游拉。（3） 解：a) (┓P ∧R)→Qb) Q→Rc) ┓Pd) P→┓Q（4） 解：a)設 Q:我將去參加舞會。R:我有時間。P:天下雨。Q? (R∧┓P):我將去參加舞會當且僅當我有時間和天不下雨。b)設 R:我在看電視。Q:我在吃蘋果。R∧Q:我在看電視邊

2、吃蘋果。 c) 設 Q:一個數(shù)是奇數(shù)。R:一個數(shù)不能被 2 除。（Q→R）∧(R→Q):一個數(shù)是奇數(shù)，則它不能被 2 整除并且一個數(shù)不能被 2 整除，則它是奇數(shù)。(5) 解：a) 設 P：王強身體很好。Q：王強成績很好。P∧Qb) 設 P：小李看書。Q：小李聽音樂。P∧Qc) 設 P：氣候很好。Q：氣候很熱。P∨Qd) 設 P： a 和 b 是偶數(shù)。Q：a+b是偶數(shù)。P→Qe) 設 P：四邊形 ABCD是平行四邊形。Q ：四邊形 ABCD的對邊平行。P?Qf) 設 P：語法錯誤。Q：程序錯誤。R：停機。（P∨ Q）→ R(6) 解：a) P:天氣炎熱。Q:正在下雨。 P∧Qb) P:天氣炎熱。

3、R:濕度較低。 P∧R c) R:天正在下雨。S:濕度很高。 R∨Sd) A:劉英上山。B:李進上山。 A∧Be) M:老王是革新者。N:小李是革新者。 M∨Nf) L:你看電影。M:我看電影。 ┓L→┓M 2 g) P:我不看電視。Q:我不外出。 R:我在睡覺。 P∧Q∧Rh) P:控制臺打字機作輸入設備。Q:控制臺打字機作輸出設備。P∧Q習題解答（1）解：a) 不是合式公式，沒有規(guī)定運算符次序（若規(guī)定運算符次序后亦可作為合式公式）b) 是合式公式c) 不是合式公式（括弧不配對）d) 不是合式公式（R 和 S 之間缺少聯(lián)結(jié)詞）e) 是合式公式。 （2）解：a） A是合式公式，(A∨B)是合式

4、公式，(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))。（4）解：a) 是由 c) 式進行代換得到，在 c) 中用 Q 代換 P, (P→P)代換 Q.d) 是由 a) 式進行代換得到，在 a) 中用 P→(Q→P)代換 Q.e

5、) 是由 b) 式進行代換得到，用 R代換 P, S 代換 Q, Q 代換 R, P代換 S.（5）解：a) P: 你沒有給我寫信。 R: 信在途中丟失了。 P Qb) P: 張三不去。Q: 李四不去。R: 他就去。 (P∧Q)→Rc) P: 我們能劃船。 Q: 我們能跑步。 ┓(P∧Q) d) P: 你來了。Q: 他唱歌。R: 你伴奏。 P→(Q?R)（6）解：P:它占據(jù)空間。 Q:它有質(zhì)量。 R:它不斷變化。 S:它是物質(zhì)。這個人起初主張：(P∧Q∧R) ? S后來主張：(P∧Q?S)∧(S→R) ∨ 3 這個人開頭主張與后來主張的不同點在于：后來認為有 P∧Q 必同時有 R，開頭時沒有這

6、樣的主張。（7）解：a) P: 上午下雨。 Q:我去看電影。 R:我在家里讀書。 S:我在家里看報。(┓P→Q)∧(P→(R∨S))b) P: 我今天進城。Q:天下雨。┓Q→Pc) P: 你走了。 Q:我留下。Q→P（4）解：a)P Q R Q∧R P∧(Q∧R) P∧Q (P∧Q)∧RT TTT TFT FTT FF F TTF TFF FTF FF TFFFTFFF TFFFFFFF TTFFFFFF TFFFFFFF所以，P∧(Q∧R) ? (P∧Q)∧R b) P QR Q∨R P∨(Q∨R) P∨Q (P∨Q)∨R 4 T TTT TFT FTT FFF T TF TFF FTF F

7、F ＴＴＴＦＴＴＴＦ ＴＴＴＴＴＴＴＦ ＴＴＴＴＴＴＦＦ ＴＴＴＴＴＴＴＦ所以，P∨(Q∨R) ? (P∨Q)∨R ｃ）Ｐ Ｑ Ｒ Ｑ∨Ｒ Ｐ∧（Ｑ∨Ｒ）Ｐ∧Ｑ Ｐ∧Ｒ （Ｐ∧Ｑ）∨（Ｐ∧Ｒ）Ｔ Ｔ ＴＴ Ｔ ＦＴ Ｆ ＴＴ Ｆ ＦＦ Ｔ Ｔ Ｆ Ｔ Ｆ ＴＴＴＦＴＴ ＴＴＴＦＦＦ ＴＴＦＦＦＦ ＴＦＴＦＦＦ ＴＴＴＦＦＦ 5 Ｆ Ｆ ＴＦ Ｆ Ｆ ＴＦ ＦＦ ＦＦ ＦＦ ＦＦ所以，P∧(Q∨R) ? (P∧Q)∨(P∧R)ｄ） P Q ┓P ┓Q ┓P∨┓Q ┓(P∧Q) ┓P∧┓Q ┓(P∨Q)T T T FF TF F FFTT FTFT FTTT FTTT FFFT FFFT所以，┓(

8、P∧Q) ?┓P∨┓Q, ┓(P∨Q) ?┓P∧┓Q（5）解：如表，對問好所填的地方，可得公式 F 1～F6，可表達為P Q R F1 F2 F3 F4 F5 F6T T T T F T T F FT T F F F T F F FT F T T F F T T FT F F F T F T T FF T T T F F T T FF T F T F F F T FF F T T F T T T FF F F F T F T T T F1:(Q→P)→RF2:(P∧┓Q∧┓R)∨(┓P∧┓Q∧┓R)F3:(P←→Q)∧(Q∨R)F4:(┓P∨┓Q∨R)∧(P∨┓Q∨R)F5:(┓P∨┓Q∨R)

9、∧(┓P∨┓Q∨┓R)F6:┓(P∨Q∨R)(6) 6 P Q 12 3 4 5 6 7 8 9 10 11 12 13 14 15 16F F F T F T F T F T F T F T F T F TF T F F T T F F T T F F T T F F T TT F F F F F T T T T F F F F T T T TT T F F F F F F F F T T T T T T T T解：由上表可得有關公式為1.F 2.┓(P∨Q) 3.┓(Q→P) 4.┓P 5.┓(P→Q) 6.┓Q 7.┓(P?Q) 8.┓(P∧Q)9.P∧Q 10.P?Q 11.Q 12.

10、P→Q13.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∧┐B)∨(B∧A))?┐((┐A∧┐B)∨(B∧A)) 7 ?┐(┐(A∨B))∨(A∧B)?(A∨B)∧┐(A∧B)c) ┐(A→B) ? ┐(┐A∨B) ?A∧┐Bd) ┐(A?B)?┐

11、((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? (((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)→Cg) (A→D)∧(B→D)?(┐A∨D)∧(┐B∨D)?(┐A∧┐B)

12、∨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 8 ?(┐(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∧C ?Cb) A∨(┐A∨(B∧┐B)) ? (A∨┐A)∨(B∧┐B) ?T∨F ?Tc) (A∧B∧C)∨(┐A∧B∧C)? (A∨┐A) ∧(

13、B∧C)?T∧(B∧C)?B∧C （9）解：1）設 C 為 T，A 為 T，B為 F，則滿足 A∨C?B∨C，但 A?B不成立。2）設 C 為 F，A 為 T，B 為 F，則滿足 A∧C?B∧C，但 A?B 不成立。3）由題意知┐A和┐B 的真值相同，所以 A 和 B 的真值也相同。習題 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?Tb) ┐P→(P→Q)?P∨(┐P∨Q) 9 ? (P∨┐P)∨Q?T∨Q?Tc) ((P→Q)∧(Q→R))→(P→R)因為(P→Q)∧

14、(Q→R)?(P→R)所以 (P→Q)∧(Q→R)為重言式。d) ((a∧b)∨(b∧c) ∨(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：設 P→Q 為 T（1）若 P 為 T，則 Q 為 T，所以 P∧Q 為 T，故 P→(P∧Q)為 T（2）若 P 為 F，則 Q 為 F，所以 P∧Q

15、 為 F，P→(P∧Q)為 T命題得證解法 2：設 P→(P∧Q)為 F ，則 P為 T，(P∧Q)為 F ，故必有 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)→Q?P∨Q設 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設 R→Q 為 F，則 R為 T，且 Q 為 F，又 P∧┐P

16、為 F所以 Q→(P∧┐P)為 T，R→(P∧┐P)為 F所以 R→(R→(P∧┐P))為 F，所以(Q→(P∧┐P))→(R→(R→(P∧┐P)))為 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) 如果天下雨，我不去。 10 設 P：天下雨。Q：我不去。P→

17、Q逆換式 Q→P 表示命題:如果我不去，則天下雨。逆反式┐Q→┐P表示命題:如果我去，則天不下雨b) 僅當你走我將留下。設 S：你走了。R：我將留下。R→S逆換式 S→R 表示命題：如果你走了則我將留下。逆反式┐S→┐R表示命題：如果你不走，則我不留下。c) 如果我不能獲得更多幫助，我不能完成個任務。設 E：我不能獲得更多幫助。H：我不能完成這個任務。E→H逆換式 H→E 表示命題：我不能完成這個任務，則我不能獲得更多幫助。逆反式┐H→┐E表示命題：我完成這個任務，則我能獲得更多幫助（5） 試證明 P?Q，Q 邏輯蘊含 P。證明：解法 1： 本題要求證明(P?Q) ∧Q?P,設(P?Q) ∧Q

18、 為 T，則(P?Q)為 T，Q 為 T，故由?的定義，必有 P為 T。所以(P?Q) ∧Q?P解法 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：我學習 Q：我數(shù)學不及格 R：我熱衷于玩撲克。如果我學習，那么我數(shù)學不會不及格： P→┐Q如果我不熱衷于玩撲克，那么我將學習: ┐R→P

19、但我數(shù)學不及格: 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：設(P→┐Q)∧(┐R→P)∧Q 為 T，則因 Q為 T，(P→┐Q) 為 T，可得 P 為 F， 11 由(┐R→P)為 T，得到 R為 T。故本題論證有效。（7） 解：P：6 是偶數(shù) Q：7 被 2 除盡 R：5 是素數(shù)如果 6是偶數(shù)，則 7

20、被 2除不盡 P→┐Q或 5 不是素數(shù)，或 7被 2除盡 ┐R∨Q5是素數(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

21、為 T。（8） 證明：a) P?(┐P→Q)設 P 為 T，則┐P 為 F，故┐P→Q 為 Tb) ┐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設┐(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)→┐A

22、?B∨C設┐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設(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：他將得勝 12 原命題：P→Q 逆反式：┐Q→┐P 表示：如果他失敗了，說明他沒勇氣。b) 僅當他不累他將得勝。P：他不累 Q：他得勝原命

23、題：Q→P 逆反式：┐P→┐Q 表示：如果他累，他將失敗。習題 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∧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↓Pb)P∨Q?┐(P↓Q) ? (P↓Q)↓(P↓Q)c)P∧Q?┐P↓┐

24、Q? (P↓P)↓(Q↓Q)(3)解： P→(┐P→Q)?┐P∨(P∨Q)?T?┐P∨P? (┐P↑┐P)↑(P↑P)?P↑(P↑P) 13 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，R為 F，則(

25、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)證明：設變元 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?Q，P?┐P?F，P?┐Q?┐（P?

26、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,?? 14 ∨∨ ┐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?Q）?Q，Q?┐P?┐（P?Q），Q?┐Q?F，Q?┐（P?Q）?┐

27、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）?FT?F?F，T?（P?Q）? P?QF?（P?Q）? ┐（P?Q）（P?Q）?（P?Q）?P?Q.故由（B）類使用?運算后，結(jié)果仍在（B）中。由上證明：用?,┐兩個連結(jié)詞，反復作用在兩個變元的公式中，結(jié)果只能產(chǎn)生（B）類中的公式，總共僅八個不同的公式，故{?,┐}不是功能完備的

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

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

30、)∨(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) ? (┐P∧Q)∨(┐Q∧P)(3) 解：a) P∨(┐P∧Q∧R)?(P∨┐P)∧(P

31、∨Q)∧(P∨R)?(P∨Q)∧(P∨R) 16 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) 解：a) (┐P∨┐Q)→(P?┐Q)?┐(┐P∨┐Q) ∨(P?┐Q)? (P∧Q) ∨(P∧┐Q)∨(┐P∧Q)?? 1，2，

32、3?P∨Q=?0b) Q∧(P∨┐Q)? (P∧Q)∨(Q∧┐Q)? P∧Q =?3??0，1，2?(P∨Q)∧(P∨┐Q) ∧(┐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∧

33、R))? (P∧Q∧R) ∨(┐P∧┐Q∧┐R) =? 0,7??1，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 17 ??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)

34、 證明：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∧(┐A∨┐B)? ((A∧┐A)∨(A∧┐B))∧B?A∧B∧┐B?F┐A∧┐B∧(A∨B)? ((┐A∧A)∨(┐A∧B))∧┐B?┐A∧┐B∧B?Fd)A∨(A→(A∧B)?A∨┐A∨(A∧B)?T ┐A∨┐B∨(A∧B)?┐(A∧B) ∨(A

35、∧B)?T(6)解：A?R↑(Q∧┐(R↓P)),則 A*? R↓(Q∨┐(R↑P)) 18 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) 解：設 A：A 去出差。B：B 去出差。C：C 去出差。D：D 去出差。若 A 去則 C和 D中要去一個。 A→(CVD)B和 C不能都去。 ┐(B∧C)C去則 D 要留下。 C→┐D按題意應有：A→(CVD)，┐(B∧C)，C→┐D 必須同時成立。 因為 CVD ?

36、(C∧┐D) ∨(D∧┐C)故(A→(CVD))∧┐(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) ∨(┐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

37、∧┐D) ∨(┐D∧C∧┐C)在上述的析取范式中，有些（畫線的）不符合題意，舍棄，得(┐A∧┐C) ∨(┐B∧┐C∧D) ∨（┐C∧D）∨(┐D∧C∧┐B)故分派的方法為：B∧D ,或 D∧A,或 C∧A。(8) 解：設 P：A是第一。Q：B是第二。R：C是第二。S：D 是第四。E：A 是第二。 由題意得 (PVQ) ∧(RVS) ∧(EVS)? ((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))因為 (

38、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)? (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 是第四。習題 1-8(1)證明： a)┐(P∧┐Q)，┐Q∨R，┐R?

39、┐P(1) ┐R P(2) ┐Q∨R P 19 (3) ┐Q (1)(2)T,I(4) ┐(P∧┐Q) P(5) ┐P∨Q (4)T,E(6) ┐P (3)(5)T,Ib)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,Ic)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 (3)T,I(6) C→B (4)T,E(7) B→C (5)T,E(8) B?

40、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 20 (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→┐B?A→┐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)

41、 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) B (3)T,I(5) ┐F (3)T,(6) A→(B→C) P 21 (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(1

42、5) ┐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 (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 22 (1) ┐(B→E) P(2) B (1)T,I(3) ┐E

43、 (1)T,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,I(10) C→D (1)T,I(11) D→F (

44、3)T,I (12) C→F (10)(10)T,I(13) A→C P(14) A→F (13)(12)T,I 23 (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 P(5) ┐C (3)(4)T,I(6) A→┐C CPb)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(

45、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 24 (12) F (10)(11)T,I(13) B→F CP(14) A→(B→F) CPc)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 (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

46、CPd)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→┐Q P 25 (2) R∨S P(3) S→┐Q P(4) ┐Q (1)(2)(3)T,I(5) P→Q P(6) ┐P (4)(5)T,Ib) S→┐Q，S∨R，┐R，┐P?Q?P證法一： (1) S∨R P(2) ┐R P(3) S (1)(2)T

47、,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 (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 26 (8) S∨R P(9) R (7)(8)T,I(10) ┐R P(11) ┐R∧R 矛盾（9）（10）T，Ic)┐(P→Q)→┐(R∨S)，((Q→P)∨┐R)，R?P?Q(1)

48、 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)(8) (P→Q) ∧(Q→P) (3)(7)T,I(9) P?Q (8)T,E (5) 解：a) 設 P：我跑步。Q：我很疲勞。前提為：P→Q，┐Q(1) P→Q P(2) ┐Q P(3) ┐P (1)(2)T,I結(jié)論為：┐P，我沒有跑步。 b) 設 S：他犯了錯誤。 R：他神色慌張。前提為：S→R，R因為（S→R）∧R?（┐S∨R）∧R?R。故本題沒有確定的結(jié)論。 27 實際上，

49、若 S →R 為真，R 為真,則 S 可為真，S也可為假，故無有效結(jié)論。c) 設 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，我的程序沒有通過習題 2-1,2-2（1） 解：a) 設 W（x）：x 是工人。c：小張。則有 W（c） b) 設 S（x）：x 是田徑運動員。B（x）：x是球類運動員。h：他則有 S（h）?B（h）c) 設 C（x）：x是聰

50、明的。B（x）：x 是美麗的。l：小莉。則有 C（l）? B（l）d）設 O（x）：x是奇數(shù)。則有 O（m）? O（2m）。e)設 R（x）：x 是實數(shù)。Q（x）：x是有理數(shù)。 則有 （?x）（Q（x）?R（x））f) 設 R（x）：x是實數(shù)。Q（x）：x是有理數(shù)。則有 （?x）（R（x）?Q（x）） 28 g) 設 R（x）：x是實數(shù)。Q（x）：x是有理數(shù)。則有 （?x）（R（x）?Q（x））h)設 P（x，y）：直線 x 平行于直線 yG（x，y）：直線 x 相交于直線 y。則有 P（A，B）?G（A，B）（2） 解：a) 設 J(x)：x是教練員。L(x)：x 是運動員。 則有 （?x）

51、（J（x）?L（x））b) 設 S(x)：x是大學生。L(x)：x 是運動員。則有 （?x）（L（x）?S（x））c) 設 J(x)：x是教練員。O(x)：x 是年老的。V（x）：x是健壯的。則有 （?x）（J（x）?O（x）?V（x））d) 設 O(x)：x是年老的。V（x）：x 是健壯的。j：金教練則有 O（j）?V（j） e) 設 L(x)：x是運動員。J(x)：x 是教練員。則 （?x）（L（x）?J（x））本題亦可理解為：某些運動員不是教練。故 （?x）（L（x）?J（x））f) 設 S（x）：x 是大學生。L（x）：x是運動員。C（x）：x 是國家選手。則有 （?x）（S（x）?

52、L（x）?C（x））g) 設 C（x）：x 是國家選手。V（x）：x 是健壯的。 則有 （?x）（C（x）?V（x））或（?x）（C（x）?V（x））h) 設 C（x）：x 是國家選手。O（x）：x 是老的。L（x）：x 是運動員。則有 （?x）（O（x）?C（x）?L（x）） 29 i) 設 W（x）：x是女同志。H（x）：x 是家庭婦女。C（x）：x 是國家選手。則有 （?x）（W（x）?C（x）?H（x））j）W（x）：x 是女同志。J（x）：x 是教練。C（x）：x 是國家選手。則有（?x）（W（x）?J（x）?C（x））k）L（x）：x 是運動員。J（y）：y 是教練。A(x,y)：

53、x 欽佩 y。則有 （?x）（L（x）? （?y）（J（y）?A（x，y）））l）設 S（x）：x 是大學生。L（x）：x 是運動員。A(x,y)：x欽佩 y。 則（?x）（S（x）?（?y）（L（y）? A(x,y)））習題 2-3（1）解：a）5是質(zhì)數(shù)。b）2是偶數(shù)且2是質(zhì)數(shù)。c）對所有的x，若x能被2除盡，則x是偶數(shù)。d）存在x，x是偶數(shù)，且x能除盡6。（即某些偶數(shù)能除盡6） e）對所有的x，若x不是偶數(shù)，則x不能被2除盡。f）對所有的x，若x是偶數(shù)，則對所有的y，若x能除盡y，則y也是偶數(shù)。g）對所有的 x，若 x 是質(zhì)數(shù)，則存在y，y 是偶數(shù)且 x 能除盡y（即所有質(zhì)數(shù)能除盡某些偶數(shù)

54、）。h）對所有的 x，若 x 是奇數(shù)，則對所有 y，y 是質(zhì)數(shù)，則x 不能除盡y（即任何奇數(shù)不能除盡任何質(zhì)數(shù)）。（2）解：（?x）(?y)((P(x)∧P(y)∧┐E(x,y)→(?!z)(L(z)∧R(x,y,z)))或 （?x）(?y)((P(x)∧P(y)∧┐E(x,y)→(?z)(L(z)∧R(x,y,z) ∧┐(?u)(┐E(z,u) ∧L(u)∧R(x,y,u)))) （3）解：a) 設N(x):x是有限個數(shù)的乘積。 z(y):y為0。 30 P(x):x的乘積為零。 F(y):y是乘積中的一個因子。則有 (?x)((N(x)∧P(x)→(?y)(F(y)∧z(y)))b) 設R(

55、x):x是實數(shù)。Q(x,y):y大于x。 故 (?x)(R(x)→(?y)(Q(x,y)∧R(y)))c)R(x):x是實數(shù)。G(x,y):x大于y。 則(?x)(?y)(?z)(R(x)∧R(y)∧R(z)∧G(x+y,xz)（4）解：設G(x,y):x大于y。則有 (?x)(?y)(?z)(G(y,x) ∧G(0,z)→G(xz,yz))（5）解：設N(x):x是一個數(shù)。 S(x,y):y是x的后繼數(shù)。E(x,y)：x=y.則 a) (?x)(N(x)→(?!y)(N(y)∧S(x,y)))或(?x)(N(x)→(?y)(N(y)∧S(x,y) ∧┐(?z)(┐E(y,z) ∧N(z)∧S

56、(x,z))))b) ┐(?x)(N(x)∧S(x,1))c) (?x)(N(x)∧┐S(x,2)→(?!y)(N(y) ∧S(y,x)))或(?x)(N(x)∧┐S(x,2)→(?y)(N(y) ∧S(y,x) ∧┐(?z)(┐E(y,z) ∧N(z)∧S(z,x))))（6）解：設S(x):x是大學生。 E(x):x是戴眼睛的。F(x):x是用功的。 R(x,y):x在看y。 G(y):y是大的。 K(y):y是厚的。 J(y):y是巨著。 a:這本。 b:那位。則有 E(b)∧F(b)∧S(b)∧R(b,a)∧G(a)∧K(a)∧J(a)（7）解：設P(x,y):x在y連續(xù)。 Q(x,y

57、):x>y。則P(f,a)?((?ε)(?δ)(?x)(Q(ε,0)→(Q(δ,0)∧Q(δ,|x-a|)→Q(ε,|f(x)-f(a)|))))習題 2-4(1) 解：a)x是約束變元，y是自由變元。b) x 是約束變元，P(x)∧Q(x)中的x 受全稱量詞?的約束，S(x)中的x 受存在量詞?的約束。 c)x，y都是約束變元,P(x)中的x受?的約束，R(x)中的x受?的約束。d)x，y是約束變元，z是自由變元。 31 (2) 解：a)P(a)∧P(b)∧P(c)b)R(a)∧R(b)∧R(c)∧S(a)∧S(b)∧S(c)c)(P(a)→Q(a))∧(P(b)→Q(b))∧(P(c)→Q

58、(c)d)(┐P(a)∧┐P(b)∧┐P(c))∨(P(z)∧P(b)∧P(c))e)(R(a)∧R(b)∧R(c))∧(S(a)∨S(b)∨S(c))(3) 解：a)(?x)(P(x)∨Q(x))?(P(1)∨Q(1))∧(P(2)∨Q(2))， 但P(1)為T，Q(1)為F，P(2)為F，Q(2)為T,所以(?x)(P(x)∨Q(x))?(T∨F)∧(F∨T)??T。b)(?x)(P→Q(x))∨R(a)?((P→Q(?2))∧(P→Q(3))∧(P→Q(6)))∨R(a)因為P 為T，Q(?2)為T，Q(3)為T，Q(6)為F，R(5)為F，所以(?x)(P→Q(x))∨R(a)? ((

59、T→T)∧(T→T)∧(T→F))∨F?F(4) 解：a)(?u)(?v)(P(u，z)→Q(v))?S(x，y)b) (?u)(P(u)→(R(u)∨Q(u))∧(?v)R(v))→(?z)S(x,z) (5) 解：a)((?y)A(u，y)→(?x)B(x，v))∧(?x)(?z)C(x，t，z)b) ((?y)P(u，y)∧(?z)Q(u，z))∨(?x)R(x，t)習題2-5（1）解： a) P(a,f(a))∧P(b,f(b))?P(1,f(1))∧P(2,f(2))?P(1,2)∧P(2,1)??T∧F?Fb)(?x)(?y)P(y,x)?(?x)(P(1,x)∨P(2,x))?(

60、P(1,1)∨P(2,1))∧(P(1,2)∨P(2,2))? (T∨F)∧(T∨F)??Tc)(?x)(?y)(P(x,y)→P(f(x),f(y)))? ?(?x)((P(x,1)→P(f(x),f(1)))∧(P(x,2)→P(f(x)f(2))))?(P(1,1)→P(f(1),f(1)))∧(P(1,2)→P(f(1),f(2)))∧(P(2,1)→P(f(2),f(1)))∧(P(2,2)→P(f(2),f(2))) 32 ?(P(1,1)→P(2,2))∧(P(1,2)→P(2,1))∧(P(2,1)→P(1,2))∧(P(2,2)→P(1,1))?(T→F∧(T→F)∧(F→T

61、)∧(F→T)?F∧F∧T∧T?F（2）解：a)(?x)(P(x)→Q(f(x),a))??(P(1)→Q(f(1),1))∧(P(2)→Q(f(2),1))?(F→Q(2,1))∧(T→Q(1,1))??(F→F)∧(T→T)??Tb)(?x)(P(f(x))∧Q(x,f(a))? ?(P(f(1))∧Q(1,f(1)))∨(P(f(2))∧Q(2,f(1)) ?(T∧T)∨(F∧F)??Tc) (?x)(P(x)∧Q(x,a))?(P(1)∧Q(1,a))∨(P(2)∧Q(2,a))?(P(1)∧Q(1,1))∨(P(2)∧Q(2,1))??(F∧T)∨(T∧F)??Fd) (?x)(?y

62、)(P(x)∧Q(x,y))??(?x)(P(x)∧(?y)Q(x,y))? ?(?x)(P(x)∧(Q(x,1)∨Q(x,2)))?(P(1)∧(Q(1,1)∨Q(1,2)))∧(P(2)∧(Q(2,1)∨Q(2,2)))?(F∧(T∨T))∧(T∧(F∨F))??F(3) 舉例說明下列各蘊含式。a) ?((?x)(P(x)∧Q(a))?(?x)P(x)??Q(a)b) (?x) (?P(x)?Q(x)),(?x)?Q(x)?P(a)c) (?x) (P(x)?Q(x)),(?x)(Q(x)?R(x))? (?x)(P(x)?R(x))d) (?x) (P(x)?Q(x)),(?x)?P(x

63、)?(?x)Q(x)e) (?x) (P(x)?Q(x)),(?x)?P(x)?(?x)Q(x) 解：a）因為?((?x)(P(x)∧Q(a))??(?x)P(x)∨?Q(a)故原式為?(?x)P(x)∨?Q(a)?(?x)P(x)??Q(a) 33 設P（x）：x是大學生。Q（x）：x是運動員前提 或者不存在x，x是大學生，或者a是運動員結(jié)論 如果存在x是大學生，則必有a是運動員。b)設P（x）：x是研究生。Q（x）：x是大學生。a：論域中的某人。前提：對論域中所有x，如果x不是研究生則x是大學生。對論域中所有x， x不是大學生。結(jié)論：對論域中所有x都是研究生。 故，對論域中某個a，必有結(jié)論

64、a 是研究生，即P（a）成立。c）設P（x）：x是研究生。Q（x）：x曾讀過大學。R（x）：x曾讀過中學。前提 對所有x，如果x是研究生，則x曾讀過大學。對所有x，如果x曾讀過大學，則x曾讀過中學。結(jié)論：對所有x，如果x是研究生，則x曾讀過中學。d）設P（x）：x是研究生。Q（x）：x是運動員。前提 對所有x，或者x是研究生，或者x是運動員。 對所有x，x不是研究生結(jié)論 必存在x，x是運動員。e）設P（x）：x是研究生。Q（x）：x是運動員。前提 對所有x，或者x是研究生，或者x是運動員。對所有x，x不是研究生結(jié)論 對所有x，x是運動員。（4）證明：(?x)(A(x)→B(x))?(?x) (

65、┐A(x)∨B(x))? (?x)┐A(x)∨ (?x)B(x) ? ┐(?x)A(x)∨(?x)B(x)? (?x)A(x)→(?x)B(x)（5）設論域D={a，b，c}，求證(?x)A(x)∨(?x)B(x)?( ?x)(A(x)∨B(x))證明：因為論域D={a，b，c}，所以 34 (?x)A(x)∨(?x)B(x)?(A(a) ∧A(b) ∧A(c)) ∨(B(a) ∧B(b) ∧B(c))?(A(a) ∨B(a)) ∧(A(a) ∨B(b)) ∧(A(a) ∨B(c)) ∧(A(b) ∨B(a)) ∧(A(b) ∨B(b)) ∧(A(b)∨B(c)) ∧(A(c) ∨B(a))

66、∧(A(c) ∨B(b)) ∧(A(c) ∨B(c))?(A(a) ∨B(a)) ∧(A(b) ∨B(b))∧(A(c) ∨B(c))?( ?x)(A(x)∨B(x))所以(?x)A(x)∨(?x)B(x)?(?x)(A(x)∨B(x))（6）解：推證不正確，因為┐(?x)(A(x)∧┐B(x))?┐((?x)A(x)∧(?x)┐B(x)) （7）求證(?x)(?y)(P(x)→Q(y))? (?x)P(x)→(?y)Q(y)證明：(?x)(?y)(P(x)→Q(y))?(?x)(?y)( ┐P(x) ∨Q(y))?(?x) ┐P(x) ∨(?y)Q(y)?┐(?x)P(x) ∨(?y)Q(y)?( ?x)P(x)→(?y)Q(y)習題2-6 （1）解：a) (?x)(P(x)→(?y)Q(x,y))?(?x)( ┐P(x) ∨(?y)Q(x,y))?(?x)(?y) (┐P(x) ∨Q(x,y))b) (?x)(┐((?y)P(x,y))→((?z)Q(z)→R(x)))?(?x)((?y)P(x,y)∨((?z)Q(z)→R(x)))?(?x)((?y