命題邏輯習(xí)題.pdf

第一章 習(xí)題課 一 .命題符號(hào)化 注意講過的命題符號(hào)化方法。 P8習(xí)題 (3) P:天下雪。 Q:我將去鎮(zhèn)上。 R:我有時(shí)間。 a) 如果天不下雪且我有時(shí)間，那么我將去鎮(zhèn)上。 (PR)Q 只有 天不下雪且我有時(shí)間，我才去鎮(zhèn)上。 Q (PR) b) 我將去鎮(zhèn)上，僅當(dāng)我有時(shí)間。 QR d) 天下雪，那么我不去鎮(zhèn)上。 P Q P12習(xí)題 (5) a) 或者你沒有給我寫信，或者它在途中丟失了。 顯然這里的“或者”是“ 不可兼取的或 ”。 令 P:你給我寫信。 Q:信在途中丟失了。 表達(dá)式為 : PQ 或 (P Q) (P Q) c) 我們不能既劃船又跑步。 令 P:我們劃船。 Q:我們跑步。 表達(dá)式為 (PQ ) d)如果你來了，那么他唱不唱歌將看你是否為他 伴奏而定。 令 P:你來了。 Q:你為他伴奏。 R:他唱歌。 表達(dá)式為 : P(QR)( Q R) 也可以寫成： P(Q R) P12習(xí)題 (7) a) 假如上午不下雨，我去看電影，否則就在家里 讀書或看報(bào)。 令 P:上午下雨。 Q:我去看電影。 R:我在家里讀 書。 S:我在家里看報(bào)。 表達(dá)式為 : (PQ)(P(R S) 不可以寫成 ： (PQ) (P(R S) (PQ) (P(R S) (P Q) (P (R S) (P Q) (P (R S) P Q P (R S) P P Q (R S) T b) 我今天進(jìn)城，除非下雨。 令 P:我今天進(jìn)城。 Q:今天下雨。 表達(dá)式為 : QP c) 僅當(dāng)你走我將留下。 令 P:你走。 Q:我留下。 表達(dá)式為 : QP 或者 P Q 二 .重言式的證明方法 方法 1：列真值表。 方法 2：公式的等價(jià)變換，化簡成“ T”。 方法 3：用公式的主析取范式。 P23 (2)a)證明 (PQ)(P(P Q)是 重言式。 方法 1: P Q PQ P(P Q) (PQ)(P(P Q) F F T T T F T T T T T F F F T T T T T T 方法 2: (PQ)(P(P Q) (P Q) (P (P Q) (E16) (P Q) (P P) (P Q) 摩根，分配 (P Q) (T (P Q) 互 補(bǔ) (P Q) (P Q) 同一 (P (P Q) (Q (P Q) 分配 (P P) Q) (Q (Q P) 結(jié) 合、交 換 (T Q) (Q Q) P) 互 補(bǔ) 、 結(jié) 合 T (T P) 零律、互 補(bǔ) T T 零律 T 冪 等 方法 3 (PQ)(P(P Q) (P Q) (P (P Q) 去 (P Q) P (P Q) 后移 (P Q) (P (Q Q) (P Q) 補(bǔ)變 元 Q (P Q) (P Q) (P Q) (P Q) 分配 (P Q) (P Q) (P Q) (P Q) 整理 m3 m2 m1 m0 可見，該公式的主析取范式含有全部 (四個(gè) )小項(xiàng)， 這表明 (PQ)(P(P Q)是永真式。 三 .重言蘊(yùn)涵式的證明方法 方法 1.列真值表。 (即列永真式的真值表 ) (略 ) 方法 2.假設(shè)前件為真，推出后件也為真。 方法 3.假設(shè)后件為假，推出前件也為假。 P23(8)e)證明 (A(B C) ) (D E) (D E)A) B C 方法 2 證明： 設(shè)前件 (A(B C) ) (D E) (D E)A) 為真，則 A(B C) , D E, (D E)A 均為 真。由 D E, (D E)A 均為真用 I11得 A為真 , 又由 A(B C)為真，得 B C為真。所以得 (A(B C) ) (D E) (D E)A) B C (A(B C) ) (D E) (D E)A)B C 方法 3 證明：設(shè)后件 B C為 F， 則 B與 C均 為 F， 1. 如果 D E 為 T， 則 1).若 A為 T，則 A為 F，則 (D E)A為 F，于是 前件 (A(B C) ) (D E) (D E)A) 為 F。 2). 若 A為 F， 則 A為 T，于是 A(B C) 為 F， 故前件 (A(B C) ) (D E) (D E)A)為 F。 2.如果 D E 為 F， 則 前件 (A(B C) ) (D E) (D E)A) 為 F。 (A(B C) ) (D E) (D E)A)B C 四 . . 等價(jià)公式的證明方法 方法 1：用列真值表。（不再舉例） 方法 2：用公式的等價(jià)變換 .(用置換定律 ) P19(7)h)證明 (AB)C)(B(DC) (B(DA)C 左式 (AB)C)( B(DC) E 16 (A B)C)( B(DC) 摩根 (B A)C)( BD)C) 交換 結(jié)合 (B A)( BD)C 分配 (B ( AD)C 分配 (B(A D)C 摩根 (B(DA)C E16 P19(8)c)化簡 (ABC)( A BC ） 上式 (A A)( BC ） 分配 T( BC ） 互補(bǔ) BC 同一 提示 ：化簡時(shí)注意使用下面 使式子變短的公式 ： 分配律 E6 P (Q R)(P Q) (P R) E7 P (Q R)(P Q) (P R) 用分配律時(shí)，是 提取公因式 。 冪等律 E10 P PP E11 P PP 同一律 E12 P FP E13 P TP 零律 E14 P TT E15 P FF 吸收律 P (P Q)P P (P Q)P 互補(bǔ)律 P PT P PF *補(bǔ)充題 . 令 P表示小張去 ， Q表示小李去 ， 用最 簡捷的語言說明下面公式 ( )( ( ) 表達(dá)的含義 。 解 ：將上面公式化簡 原公式 ( ) ( ) ) ( 16， 結(jié)合 ) ( ) ( ) (雙否律 ， 冪等律 ) ( ) ( ) (交換律 ) ( ) ) (結(jié)合律 ) (吸收律 ) 上面公式表示：如果小張去，則小李也去。 五 .范式的寫法及應(yīng)用 P39(4)d)寫出 (P(Q R) (P(Q R)的 主析取范式和主合取范式 方法 1，用真值表 令 A(P,Q,R)(P(Q R) (P(Q R) 它的真 值 表 見 下 頁。 A(P,Q,R)m0 m7 (P Q R) (P Q R) A(P,Q,R) M1 M2 M3 M4 M5 M6 (P Q R) (P Q R) (P Q R) (P Q R) (P Q R) (P Q R) A(P, Q, R)的主析取范式中含有小項(xiàng) m0 , m7。 主合取范式中含有大項(xiàng) M1,M2 ,M3 ,M4 ,M5 ,M6 。 P Q R P(Q R) P(Q R ) A(P, Q, R) 0 F F F T T T 1 F F T T F F 2 F T F T F F 3 F T T T F F 4 T F F F T F 5 T F T F T F 6 T T F F T F 7 T T T T T T 方法 2.等價(jià)變換 (P(Q R) (P(Q R) (P (Q R) (P (Q R) E16 (P P) (P Q R) (P Q R) (Q R) (Q R) 分配 F (P Q R) (P Q R) F 互補(bǔ) (P Q R) (P Q R) 同一 (P(Q R) (P(Q R) (P (Q R) (P (Q R) (P Q) (P R) (P Q) (P R) (P Q (R R) (P (Q Q) R) (P Q (R R) (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 R) (P Q R) (P Q R) (P Q R) (P Q R) (P Q R) 范式的應(yīng)用 P39(7)A,B,C,D四個(gè)人中要派兩個(gè)人出差，按下述三個(gè)條 件有幾種派法？ 若 A去則 C和 D中要去一個(gè)人。 B和 C不能都去。 C去則 D要留下。 解 .設(shè) A,B,C,D分別表示 A去， B去， C去， D去。 A(C D) (C D) A (C D) (C D) (B C) B C CD C D 總的條件為： (A (C D) (C D) ) (B C) (C D) 令此式為真。 將 (A (C D) (C D) ) (B C) (C D) 化成析取范式。 上式 (A (C D) (C D) ) (C( B D) (A C) (C D C) (C D C) (A B D) (C D B D) (C D B D) (A C)F (C D) (A B D) (C D B)F 可以取 A C為 T，得 B和 D去。 取 C D為 T，得 A和 D去，或者 B和 D去。 取 C D B為 T，得 A和 C去 。 最后得三種派法： A和 C去、 A和 D去、 B和 D去 。 *補(bǔ)充題 ：有工具箱 A、 B、 C、 D，各個(gè)箱內(nèi)裝的工具如 下表所示。試問如何攜帶數(shù)量最少工具箱，而所包含的 工具種類齊全。 解：設(shè) A、 B、 C、 D分別表示帶 A、 B、 C、 D箱。 則總的條件為： (A C) (A B D) (B C) (B D) 為真。 改錐 扳手 鉗子 錘子 工具 箱 改 錐 扳 手 鉗 子 錘 子 A 有 有 B 有 有 有 C 有 有 D 有 有 將 (A C) (A B D) (B C) (B D)寫成析取 范式，上式 (A C) (B C) (A (B D) (B D) (交 換 ) (A B) C) (B D) (分配 (提取 C)、 吸收 ) (A B B ) (C B ) (A B D) (C D) (分配 ) (A B) (C B ) (A B D) (C D) 分別可以取 (A B)、 (C B )、 (C D)為真。 于是可以得到三種攜帶方法： 帶 A和 B箱， 帶 B和 C箱，帶 C和 D箱。 六 . 邏輯推理 熟練掌握三種推理方法。 P47(2)c) (AB) (C D), (DE) F AF 1.直接推理 (A B)(C D) P (A B) (C D) T E16 (A B) (C D) T E9 (A C) (B C) (A D) (B D) T E7 A D T I2 AD T E16 (D E)F P (D E) F T E16 (D E) F T E9 (D F) (E F) T E7 D F T I1 DF T E16 AF T I13 P47(2)c) (AB) (C D), (DE) F AF 2.條件論證 A P (附加前提 ) A B T I3 (A B)(C D) P C D T I11 D T I2 D E T I3 (D E)F P F T I11 AF CP 顯然此方法比直接推理簡單。 P47(2)c) (AB) (C D), (DE) F AF 3.反證法 (AF) P (假設(shè)前提 ) (A F) T E16 A F T E9 A T I1 A B T I3 (A B)(C D) P C D T I11 D T I2 D E T I3 (D E)F P F T I11 F T I2 F F T I9 可見此法也比較簡單 *補(bǔ)充題 ：請根據(jù)下面事實(shí)，找出兇手： 1. 清潔工或者秘書謀害了經(jīng)理。 2. 如果清潔工謀害了經(jīng)理，則謀害不會(huì)發(fā)生在午夜前。 3.如果秘書的證詞是正確的，則謀害發(fā)生在午夜前。 4.如果秘書的證詞不正確，則午夜時(shí)屋里燈光未滅。 5. 如果清潔工富裕，則他不會(huì)謀害經(jīng)理。 6.經(jīng)理有錢且清潔工不富裕。 7.午夜時(shí)屋里燈滅了。 令 A:清潔工謀害了經(jīng)理。 B:秘書謀害了經(jīng)理。 C:謀害發(fā)生在午夜前。 D:秘書的證詞是正確的 . E:午夜時(shí)屋里燈光滅了。 H:清潔工富裕 . G:經(jīng)理有錢 . 命題符號(hào)為： AB,A C,DC,DE,HA,G H,E ? AB,A C,BC, DC DE,HA,G H,E ? E P DE P D T I D T E DC P C T I AC P A T I A B P B T I 結(jié)果是秘書謀害了經(jīng)理。 第一章 命題邏輯 到此結(jié)束