《命題邏輯習題.pdf》由會員分享，可在線閱讀，更多相關(guān)《命題邏輯習題.pdf（26頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、第一章 習題課 一 .命題符號化 注意講過的命題符號化方法。 P8習題 (3) P:天下雪。 Q:我將去鎮(zhèn)上。 R:我有時間。 a) 如果天不下雪且我有時間，那么我將去鎮(zhèn)上。 (?P∧R)→Q 只有 天不下雪且我有時間，我才去鎮(zhèn)上。 Q→ (?P∧R) b) 我將去鎮(zhèn)上，僅當我有時間。 Q→R d) 天下雪，那么我不去鎮(zhèn)上。 P→ ?Q P12習題 (5) a) 或者你沒有給我寫信，或者它在途中丟失了。 顯然這里的“或者”是“ 不可兼取的或 ”。 令 P:你給我寫信。 Q:信在途中丟失了。 表達式為 : ?P?Q 或 (P∧

2、 Q)∨ (?P∧ ?Q) c) 我們不能既劃船又跑步。 令 P:我們劃船。 Q:我們跑步。 表達式為 ?(P∧Q ) d)如果你來了，那么他唱不唱歌將看你是否為他 伴奏而定。 令 P:你來了。 Q:你為他伴奏。 R:他唱歌。 表達式為 : P→((Q→R)∧( ?Q→ ?R)) 也可以寫成： P→(Q ?R) P12習題 (7) a) 假如上午不下雨，我去看電影，否則就在家里 讀書或看報。 令 P:上午下雨。 Q:我去看電影。 R:我在家里讀 書。 S:我在家里看報。 表達式為 : (?P→Q)∧(P→(R ? S)) 不可以寫成 ： (?P→Q) ∨ (P→(

3、R ? S)) (?P→Q) ∨ (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) 我今天進城，除非下雨。 令 P:我今天進城。 Q:今天下雨。 表達式為 : ?Q→P c) 僅當你走我將留下。 令 P:你走。 Q:我留下。 表達式為 : Q→P 或者 ?P→ ?Q 二 .重言式的證明方法 方法 1：列真值表。 方法 2：公式的等價變換，化簡成“ T”。 方法 3：用公式的主析取

4、范式。 P23 (2)a)證明 (P→Q)→(P→(P∧ Q))是 重言式。 方法 1: P Q P?Q P→(P ∧ Q) (P→Q)→(P→(P ∧ Q)) F F T T T F T T T T T F F F T T T T T T 方法 2: (P→Q)→(P→(P∧ Q)) ??(?P∨ Q)∨ (?P∨ (P∧ Q)) (E16) ?(P∧ ?Q)∨ ((?P∨ P)∧ (?P∨ Q)) 摩根，分配 ?(P∧ ?Q)∨ (T∧ (?P∨ Q)) 互 補 ?(P∧ ?Q)∨ (?P∨ Q) 同一 ?(P∨ (?P∨ Q))

5、∧ (?Q∨ (?P∨ Q)) 分配 ?((P∨ ?P)∨ Q)∧ (?Q∨ (Q∨ ?P)) 結(jié) 合、交 換 ?(T∨ Q)∧ ((?Q∨ Q)∨ ?P) 互 補 、 結(jié) 合 ?T∧ (T∨ ?P) 零律、互 補 ? T∧ T 零律 ? T 冪 等 方法 3 (P→Q)→(P→(P∧ Q)) ??(?P∨ Q)∨ (?P∨ (P∧ Q)) 去 → ?(P∧ ?Q)∨ ?P∨ (P∧ Q)

6、 ? 后移 ?(P∧ ?Q)∨ (?P∧ (Q∨ ?Q))∨ (P∧ Q) 補變 元 Q ?(P∧ ?Q)∨ (?P∧ Q)∨ (?P∧ ?Q)∨ (P∧ Q) 分配 ? (P∧ Q)∨ (P∧ ?Q)∨ (?P∧ Q)∨ (?P∧ ?Q) 整理 ? m3∨ m2∨ m1∨ m0 可見，該公式的主析取范式含有全部 (四個 )小項， 這表明 (P→Q)→(P→(P∧ Q))是永真式。 三 .重言蘊涵式的證明方法 方法 1.列真值表。 (即列永真式的真值表 ) (略 ) 方法 2.假設(shè)前件為真，推出后件也為真。 方法 3.假設(shè)后件為假，推出前件也為假。 P23(8)e)

7、證明 (?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， 則

8、 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)??

9、A)?B∨ C 四 . . 等價公式的證明方法 方法 1：用列真值表。（不再舉例） 方法 2：用公式的等價變換 .(用置換定律 ) P19(7)h)證明 ((A∧B)→C)∧(B→(D∨C)) ?(B∧(D→A))→C 左式 ?(?(A∧B)∨C)∧( ?B∨(D∨C)) E 16 ?((?A∨ ?B)∨C)∧( ?B∨(D∨C)) 摩根 ?((?B ∨ ?A)∨C)∧(( ?B∨D)∨C) 交換 結(jié)合 ?((?B ∨ ?A)∧( ?B∨D))∨C 分配 ?(?B ∨( ?A∧D))∨C 分配 ? ?(B∧(A∨ ?D))∨C 摩根 ?

10、(B∧(D→A))→C E16 P19(8)c)化簡 (A∧B∧C)∨( ?A∧ B∧C ） 上式 ? (A∨ ?A)∧( B∧C ） 分配 ?T∧( B∧C ） 互補 ?B∧C 同一 提示 ：化簡時注意使用下面 使式子變短的公式 ： 分配律 E6 P∧ (Q∨ R)?(P∧ Q)∨ (P∧ R) E7 P∨ (Q∧ R)?(P∨ Q)∧ (P∨ R) 用分配律時，是 提取公因式 。 冪等律 E10 P∨ P?P

11、 E11 P∧ P?P 同一律 E12 P∨ F?P E13 P∧ T?P 零律 E14 P∨ T?T E15 P∧ F?F 吸收律 P∨ (P∧ Q)?P P∧ (P∨ Q)?P 互補律 P∨ ?P?T P∧ ?P?F *補充題 . 令 P表示小張去 ， Q表示小李去 ， 用最 簡捷的語言說明下面公式 ?(Ｐ ∧ Ｑ )→( ?Ｐ ∨ (?Ｐ ∨ Ｑ )) 表達的含義 。 解 ：將上面公式化簡 原公式 ?(Ｐ ∧ Ｑ )∨ ((?

12、Ｐ ∨ ?Ｐ )∨ Ｑ ) (Ｅ 16， 結(jié)合 ) ?(Ｐ ∧ Ｑ )∨ (?Ｐ ∨ Ｑ ) (雙否律 ， 冪等律 ) ?(Ｐ ∧ Ｑ )∨ (Ｑ ∨ ?Ｐ ) (交換律 ) ?((Ｐ ∧ Ｑ )∨ Ｑ )∨ ?Ｐ (結(jié)合律 ) ?Ｑ ∨ ?Ｐ (吸收律 ) ?Ｐ → Ｑ 上面公式表示：如果小張去，則小李也去。 五 .范式的寫法及應用 P39(4)d)寫出 (P?(Q∧ R))∧ (?P?(?Q∧ ?R))的 主析取范式和主合取范式 方法 1，用真值表 令 A(P,Q,R)?(P?(Q∧ R))∧

13、 (?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)的主析取范式中含有小項 m0 , m7。 主合取范式中含有大項 M1,M2 ,M3 ,M4 ,M5 ,M6 。 P Q R P?(Q∧ R) ?P?(?Q∧ ?R ) A(P, Q, R) 0

14、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.等價變換 (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 互

15、補 ?(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∨

16、 Q∨ ?R) ∧ (P∨ ?Q∨ ?R) ? (?P∨ Q∨ R)∧ (?P∨ Q∨ ?R))∧ (?P∨ ?Q∨ R)∧ (P∨ ?Q∨ R)∧ (P∨ ?Q∨ ?R)∧ (P∨ Q∨ ?R) 范式的應用 P39(7)A,B,C,D四個人中要派兩個人出差，按下述三個條 件有幾種派法？ ①若 A去則 C和 D中要去一個人。 ② 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)?

17、?B∨ ?C ③ C??D? ?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)

18、∨ (?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去 。 *補充題 ：有工具箱 A、 B、 C、 D，各個箱內(nèi)裝的工具如 下表所示。試問如何攜帶數(shù)量最少工具箱，而所包含的 工具種類齊全。 解：設(shè) A、 B、 C、 D分別表示帶 A、 B、 C、 D箱。 則總的條件為： (A∨ C)∧ (A∨ B∨ D)∧ (B∨ C)∧ (B∨ D) 為真。

19、 改錐 扳手 鉗子 錘子 工具 箱 改 錐 扳 手 鉗 子 錘 子 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 )∨

20、 (A∧ B∧ D)∨ (C∧ D) 分別可以取 (A∧ B)、 (C∧ B )、 (C∧ D)為真。 于是可以得到三種攜帶方法： 帶 A和 B箱， 帶 B和 C箱，帶 C和 D箱。 六 . 邏輯推理 熟練掌握三種推理方法。 P47(2)c) (A∨B) ?(C∧ D), (D∨E) ?F ? A?F 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 ⑶ E

21、7 ⑸ ?A∨ D T ⑷ I2 ⑹ A?D 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 ⑿ D?F T ⑾ E16 ⒀ A?F T ⑹⑿ I13 P4

22、7(2)c) (A∨B) ?(C∧ D), (D∨E) ?F ? A?F 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 ⑼ A?F CP 顯然此方法比直接推理簡單。 P47(2)

23、c) (A∨B) ?(C∧ D), (D∨E) ?F ? A?F 3.反證法 ⑴ ?(A?F) 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

24、)?F P ⑾ F T ⑹⑺ I11 ⑿ ?F T ⑶ I2 ⒀ F∧ ?F T ⑾ ⑿ I9 可見此法也比較簡單 *補充題 ：請根據(jù)下面事實，找出兇手： 1. 清潔工或者秘書謀害了經(jīng)理。 2. 如果清潔工謀害了經(jīng)理，則謀害不會發(fā)生在午夜前。 3.如果秘書的證詞是正確的，則謀害發(fā)生在午夜前。 4.如果秘書的證詞不正確，則午夜時屋里燈光未滅。 5. 如果清潔工富裕，則他不會謀害經(jīng)理。 6.經(jīng)理有錢且清潔工不富裕。 7.午夜時屋里燈滅了。 令 A:清潔工謀害了經(jīng)理。 B

25、:秘書謀害了經(jīng)理。 C:謀害發(fā)生在午夜前。 D:秘書的證詞是正確的 . E:午夜時屋里燈光滅了。 H:清潔工富裕 . G:經(jīng)理有錢 . 命題符號為： A∨B,A ??C,D?C,?D??E,H??A,G∧ ?H,E ?? A∨B,A ??C,B?C, D?C ?D??E,H??A,G∧ ?H,E ?? ⑴ E P ⑵ ?D??E P ⑶ ??D T ⑴⑵ I ⑷ D T ⑶ E ⑸ D?C P ⑹ C T ⑷⑸ I ⑺ A??C P ⑻ ?A T ⑹⑺ I ⑼ A∨ B P ⑽ B T ⑻⑼ I 結(jié)果是秘書謀害了經(jīng)理。 第一章 命題邏輯 到此結(jié)束