命题逻辑习题.pdf

第一章 习题课 一 .命题符号化 注意讲过的命题符号化方法。 P8习题 (3) P:天下雪。 Q:我将去镇上。 R:我有时间。 a) 如果天不下雪且我有时间，那么我将去镇上。 (PR)Q 只有 天不下雪且我有时间，我才去镇上。 Q (PR) b) 我将去镇上，仅当我有时间。 QR d) 天下雪，那么我不去镇上。 P Q P12习题 (5) a) 或者你没有给我写信，或者它在途中丢失了。 显然这里的“或者”是“ 不可兼取的或 ”。 令 P:你给我写信。 Q:信在途中丢失了。 表达式为 : PQ 或 (P Q) (P Q) c) 我们不能既划船又跑步。 令 P:我们划船。 Q:我们跑步。 表达式为 (PQ ) d)如果你来了，那么他唱不唱歌将看你是否为他 伴奏而定。 令 P:你来了。 Q:你为他伴奏。 R:他唱歌。 表达式为 : P(QR)( Q R) 也可以写成： P(Q R) P12习题 (7) a) 假如上午不下雨，我去看电影，否则就在家里 读书或看报。 令 P:上午下雨。 Q:我去看电影。 R:我在家里读 书。 S:我在家里看报。 表达式为 : (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) 我今天进城，除非下雨。 令 P:我今天进城。 Q:今天下雨。 表达式为 : QP c) 仅当你走我将留下。 令 P:你走。 Q:我留下。 表达式为 : QP 或者 P Q 二 .重言式的证明方法 方法 1：列真值表。 方法 2：公式的等价变换，化简成“ 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) 互 补 (P Q) (P Q) 同一 (P (P Q) (Q (P Q) 分配 (P P) Q) (Q (Q P) 结 合、交 换 (T Q) (Q Q) P) 互 补 、 结 合 T (T P) 零律、互 补 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) 补变 元 Q (P Q) (P Q) (P Q) (P Q) 分配 (P Q) (P Q) (P Q) (P Q) 整理 m3 m2 m1 m0 可见，该公式的主析取范式含有全部 (四个 )小项， 这表明 (PQ)(P(P Q)是永真式。 三 .重言蕴涵式的证明方法 方法 1.列真值表。 (即列永真式的真值表 ) (略 ) 方法 2.假设前件为真，推出后件也为真。 方法 3.假设后件为假，推出前件也为假。 P23(8)e)证明 (A(B C) ) (D E) (D E)A) B C 方法 2 证明： 设前件 (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 证明：设后件 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 四 . . 等价公式的证明方法 方法 1：用列真值表。（不再举例） 方法 2：用公式的等价变换 .(用置换定律 ) 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) 交换 结合 (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 ） 互补 BC 同一 提示 ：化简时注意使用下面 使式子变短的公式 ： 分配律 E6 P (Q R)(P Q) (P R) E7 P (Q R)(P Q) (P R) 用分配律时，是 提取公因式 。 幂等律 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 互补律 P PT P PF *补充题 . 令 P表示小张去 ， Q表示小李去 ， 用最 简捷的语言说明下面公式 ( )( ( ) 表达的含义 。 解 ：将上面公式化简 原公式 ( ) ( ) ) ( 16， 结合 ) ( ) ( ) (双否律 ， 幂等律 ) ( ) ( ) (交换律 ) ( ) ) (结合律 ) (吸收律 ) 上面公式表示：如果小张去，则小李也去。 五 .范式的写法及应用 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)的主析取范式中含有小项 m0 , m7。 主合取范式中含有大项 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.等价变换 (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 互补 (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) 范式的应用 P39(7)A,B,C,D四个人中要派两个人出差，按下述三个条 件有几种派法？ 若 A去则 C和 D中要去一个人。 B和 C不能都去。 C去则 D要留下。 解 .设 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去 。 *补充题 ：有工具箱 A、 B、 C、 D，各个箱内装的工具如 下表所示。试问如何携带数量最少工具箱，而所包含的 工具种类齐全。 解：设 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 (假设前提 ) (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 可见此法也比较简单 *补充题 ：请根据下面事实，找出凶手： 1. 清洁工或者秘书谋害了经理。 2. 如果清洁工谋害了经理，则谋害不会发生在午夜前。 3.如果秘书的证词是正确的，则谋害发生在午夜前。 4.如果秘书的证词不正确，则午夜时屋里灯光未灭。 5. 如果清洁工富裕，则他不会谋害经理。 6.经理有钱且清洁工不富裕。 7.午夜时屋里灯灭了。 令 A:清洁工谋害了经理。 B:秘书谋害了经理。 C:谋害发生在午夜前。 D:秘书的证词是正确的 . E:午夜时屋里灯光灭了。 H:清洁工富裕 . G:经理有钱 . 命题符号为： 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 结果是秘书谋害了经理。 第一章 命题逻辑 到此结束