命题逻辑习题.pdf

第一章 习题课 一一. .命题符号化命题符号化 注意讲过的命题符号化方法。注意讲过的命题符号化方法。 P8习题习题(3) P:天下雪。天下雪。Q:我将去镇上。我将去镇上。R:我有时间。我有时间。 a) 如果天不下雪且我有时间，那么我将去镇上。如果天不下雪且我有时间，那么我将去镇上。 ( PR)QPR)Q 只有只有天不下雪且我有时间，我才去镇上。天不下雪且我有时间，我才去镇上。 QQ( PR)PR) b) 我将去镇上，仅当我有时间。我将去镇上，仅当我有时间。 QRQR d) 天下雪，那么我不去镇上。天下雪，那么我不去镇上。 P Q Q P12习题习题(5) a) 或者你没有给我写信，或者它在途中丢失了。或者你没有给我写信，或者它在途中丢失了。 显然这里的“或者”是“显然这里的“或者”是“不可兼取的或不可兼取的或”。”。 令令 P:你给我写信。你给我写信。Q:信在途中丢失了。信在途中丢失了。 表达式为表达式为: P Q 或或 (PQ)( P Q) c) 我们不能既划船又跑步。我们不能既划船又跑步。 令令 P:我们划船。我们划船。Q:我们跑步。我们跑步。 表达式为表达式为 (PQPQ) d)如果你来了，那么他唱不唱歌将看你是否为他如果你来了，那么他唱不唱歌将看你是否为他 伴奏而定。伴奏而定。 令令 P:你来了。你来了。Q:你为他伴奏。你为他伴奏。 R:他唱歌。他唱歌。 表达式为表达式为: P(QR)(P(QR)( QQ R)R) 也可以写成：也可以写成： P(QP(QR)R) P12习题习题(7) a) 假如上午不下雨，我去看电影，否则就在家里假如上午不下雨，我去看电影，否则就在家里 读书或看报。读书或看报。 令令 P:上午下雨。上午下雨。Q:我去看电影。我去看电影。 R:我在家里读我在家里读 书。书。S:我在家里看报。我在家里看报。 表达式为表达式为: ( PQ)(P(R PQ)(P(R S) 不可以写成不可以写成：( PQ)PQ)(P(R (P(R S) ( PQ)PQ)(P(R (P(R S) (PQ)( P(R S) (PQ)( P(R S) PQ P(R S) P P Q(R S) T b) 我今天进城，除非下雨。我今天进城，除非下雨。 令令 P:我今天进城。我今天进城。Q:今天下雨。今天下雨。 表达式为表达式为: QPQP c) 仅当你走我将留下。仅当你走我将留下。 令令 P:你走。你走。Q:我留下。我留下。 表达式为表达式为: QP QP 或者或者 PP Q Q 二.重言式的证明方法 方法1：列真值表。 方法2：公式的等价变换，化简成“T”。 方法3：用公式的主析取范式。 P23 (2)a)证明(PQ)(P(P(PQ)(P(PQ)是是重言式。 方法1: P Q PQ P(PQ) (PQ)(P(PQ) F F T T T F T T T T T F F F T T T T T T 方法方法2: (PQ)(P(PPQ)(P(PQ) ( PQ)( P(PQ) (E E16 16) (P Q)( PP)( PQ) 摩根，分配摩根，分配 (P Q)(T( PQ) 互互补补 (P Q)( PQ) 同一同一 (P( PQ)( Q( PQ) 分配分配 (P P)Q)( Q(Q P) 结结合、交合、交换换 (TQ)( QQ) P) 互互补补、结结合合 T(T P) 零律、互零律、互补补 TT 零律零律 T 幂幂等等 方法方法3 (PQ)(P(PPQ)(P(PQ) ( PQ)( P(PQ) 去去 (P Q) P(PQ) 后移后移 (P Q)( P(Q Q)(PQ) 补变补变元元Q (P Q)( PQ)( P Q)(PQ) 分配分配 (PQ)(P Q)( PQ)( P Q) 整理整理 m3m2m1m0 可见，该公式的主析取范式含有全部可见，该公式的主析取范式含有全部(四个四个)小项，小项， 这表明这表明(PQ)(P(PPQ)(P(PQ)是永真式。是永真式。 三.重言蕴涵式的证明方法 方法方法1 1. .列真值表。列真值表。( (即列永真式的真值表即列永真式的真值表) () (略略) ) 方法方法2.假设前件为真，推出后件也为真。假设前件为真，推出后件也为真。 方法方法3 3. .假设后件为假，推出前件也为假。假设后件为假，推出前件也为假。 P P23 23(8)e) (8)e)证明证明 ( A(BC) )(DE)(DE)A) BC 方法2 证明： 设前件设前件( A(BC) )(DE)(DE)A) 为真，则为真，则 A(BC) , DE, (DE)A 均为均为 真。由真。由DE, (DE)A 均为真用均为真用I11得得 A为真为真, 又由又由 A(BC)为真，得为真，得BC为真。所以得为真。所以得 ( A(BC) )(DE)(DE)A) BC ( A(BC) )(DE)(DE)A)BC 方法3 证明：设后件BC为为 F，则则 B与与C均均为为 F， 1. 如果如果DE 为为 T，则则 1).1).若若A A为为T T，则，则 A为为F，则，则(DE)A为为F，于是，于是 前件前件( A(BC) )(DE)(DE)A) 为为F。 2). 若若A为为 F，则则 A为为T，于是，于是 A(BC) 为为F， 故前件故前件( A(BC) )(DE)(DE)A)为为F。 2.如果如果DE 为为 F，则则 前件前件 ( A(BC) )(DE)(DE)A) 为为F。 ( A(BC) )(DE)(DE)A)BC 四. . 等价公式的证明方法 方法1：用列真值表。（不再举例） 方法2：用公式的等价变换.(用置换定律) P19(7)h)证明 (AB)C)(B(DC)(AB)C)(B(DC)(B(DA)C (B(DA)C 左式左式(AB)C)(AB)C)( B(DC) E(DC) E16 16 (AA B)C)(B)C)( B(DC) (DC) 摩根摩根 ( B B A)C)(A)C)( BD)C) D)C) 交换交换 结合结合 ( B B A)(A)( BD)C D)C 分配分配 ( B B (AD)C AD)C 分配分配 (B(AB(AD)C D)C 摩根摩根 (B(DA)CB(DA)C E E16 16 P19(8)c)化简(ABC)(BC)(AABCC） 上式上式 (AA)(A)(BCC） 分配分配 T(BCC） 互补互补 BC C 同一同一 提示提示：化简时注意使用下面：化简时注意使用下面使式子变短的公式使式子变短的公式： 分配律分配律 E6 P(QR)(PQ)(PR) E7 P(QR)(PQ)(PR) 用分配律时，是用分配律时，是提取公因式提取公因式。 幂等律幂等律 E10 PPP E11 PPP 同一律同一律 E12 PFP E13 PTP 零律零律 E14 PTT E15 PFF 吸收律吸收律 P(PQ)P P(PQ)P 互补律互补律 P PT P PF *补充题补充题. 令令P表示小张去表示小张去，Q表示小李去表示小李去，用最用最 简捷的语言说明下面公式简捷的语言说明下面公式 ()() 表达的含义表达的含义。 解解 ：将上面公式化简：将上面公式化简 原公式原公式 ()() (16，结合结合) ()() (双否律双否律，幂等律幂等律) ()() (交换律交换律) () (结合律结合律) (吸收律吸收律) 上面公式表示：如果小张去，则小李也去。上面公式表示：如果小张去，则小李也去。 五.范式的写法及应用 P39(4)d)写出(P(QR)( P( Q R)的的 主析取范式和主合取范式主析取范式和主合取范式 方法方法1，用真值表，用真值表 令令A(P,Q,R)(P(QR)( P( Q R) 它的真它的真值值表表见见下下页。页。 A(P,Q,R)m0 m7 ( P Q R)(PQR) A(P,Q,R) M1M2M3M4M5M6 (PQ R)(P QR)(P Q R) ( PQR)( PQ R)( P QR) A(P, Q, R)的主析取范式中含有小项的主析取范式中含有小项m0 , m7。 主合取范式中含有大项主合取范式中含有大项M1,M2 ,M3 ,M4 ,M5 ,M6 。 P Q R P(QR) 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(QR)( P( Q R) ( P(QR)(P( Q R) E E16 16 ( PP)(PQR) ( P Q R) (QR)( Q R) 分配分配 F(PQR)( P Q R)F 互补互补 (PQR)( P Q R) 同一同一 (P(QR)( P( Q R) ( P(QR) (P( Q R) ( PQ)( PR)(P Q)(P R) ( PQ(R R)( P(Q Q)R) (P Q(R R)(P(Q Q) R) ( PQR) ( PQ R) ( PQR) ( P QR) (P QR) (P Q R) (PQ R) (P Q R) ( PQR)( PQ R) ( P QR)(P QR) (P Q R)(PQ 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)( CD) A (C D)( CD) (B(BC)C) B B C C CD C C D D 总的条件为：总的条件为： ( ( A (C D)( CD) )( ( B B C) C) ( ( C C D) D) 令此式为真。令此式为真。 将将( ( A (C D)( CD) )( ( B B C) C) ( ( C C D) D) 化成析取范式。化成析取范式。 上式上式( ( A (C D)( CD) ) ( ( C C( B B D)D) ) ( ( A C)C) (C D C)C)( CD C)C) ( ( A B B D)D) (C D B B D) D) ( CD B B D)D) ( ( A C)C)FF( CD) )( ( A B B D)D) (C D B)B)FF 可以取可以取 A C C为为T T，得，得B B和和D D去。去。 取取 CD为为T T，得，得A A和和D D去，或者去，或者 B B和和D D去。去。 取取C D B B为为T T，得，得A A和和C C去去 。 最后得三种派法：最后得三种派法： A A和和C C去、去、A A和和D D去、去、B B和和D D去去。 *补充题补充题：有工具箱：有工具箱A、B、C、D，各个箱内装的工具如，各个箱内装的工具如 下表所示。试问如何携带数量最少工具箱，而所包含的下表所示。试问如何携带数量最少工具箱，而所包含的 工具种类齐全。工具种类齐全。 解：设解：设A、B、C、D分别表示带分别表示带A、B、C、D箱。箱。 则总的条件为：则总的条件为： (AC)(ABD)(BC)(BD) 为真。为真。 改锥改锥 扳手扳手 钳子钳子 锤子锤子 工具工具 箱箱 改改 锥锥 扳扳 手手 钳钳 子子 锤锤 子子 A 有有 有有 B 有有 有有 有有 C 有有 有有 D 有有 有有 将将(AC)(ABD)(BC)(BD)写成析取写成析取 范式，上式范式，上式 (AC)(BC)(A(BD)(BD) (交交换换 ) (AB)C)(BD) (分配分配(提取提取C)、吸收吸收) (ABB )(CB )(ABD)(CD) (分配分配) (AB)(CB )(ABD)(CD) 分别可以取分别可以取(AB)、(CB )、(CD)为真。为真。 于是可以得到三种携带方法：于是可以得到三种携带方法： 带带A和和B箱，箱， 带带B和和C箱，带箱，带C和和D箱。箱。 六. 逻辑推理 熟练掌握三种推理方法。熟练掌握三种推理方法。 P47(2)c) (AB)B)(CD), (DE)E)F AF F 1.直接推理直接推理 (AB)(CD) P (AB)(CD) T E16 ( A B)(CD) T E9 ( AC)( BC)( AD)( BD) T E7 AD T I2 AD T E16 (DE)F P (DE)F T E16 ( D E)F T E9 ( D F) ( EF) T E7 DF T I1 DF T E16 AF T I13 P47(2)c) (AB)B)(CD), (DE)E)F AF F 2.条件论证条件论证 A P (附加前提附加前提) AB T I I3 (AB)(CD) P CD T I11 D T I2 DE T I I3 (DE)F P F T I11 AF CP 显然此方法比直接推理简单。显然此方法比直接推理简单。 P47(2)c) (AB)B)(CD), (DE)E)F AF F 3.反证法反证法 (AF) P ( (假设前提假设前提) ) ( AF) T E16 16 A F T E9 A T I1 AB T I3 (AB)(CD) P CD T I11 D T I2 DE T I3 (DE)F P F T I11 F T I2 F F T I9 可见此法也比较简单可见此法也比较简单 *补充题