第编数理逻辑.ppt

第 3 编 数 理 逻 辑第 6 章 命 题 逻 辑16.1 6.1 命题的概念与表示命题的概念与表示命题命题• 日常语言不确切，具有二义性——需引入目标语言、公式符号• 目标语言：表达判断的一些语言的汇集• 判断：肯定、否定的思维形式• 命题：能表达判断，具有确定真值的陈述句2•真值：命题的判断结果称为真值只有“真”和“假”两种，记为“T”和“F”，或“1”和“0”•没有判断无所谓是非的句子——感叹句、疑问句、祈使句不是命题•原子命题：不能分为更简单的陈述句•复合命题：由联结词、标点符号和原子命题复合构成的命题•用大写字母A,B,...,P,Q,...或Ai,[12]等表示命题例 P: 今天下雨[12]: 今天刮风•命题标识符：表示命题的符号3例：语句是否命题真值中国人民是伟大的中国人民是伟大的雪是黑的雪是黑的1 + 1 = 10别的星球上有生物别的星球上有生物全体立正！全体立正！明天是否开会？明天是否开会？天气多好啊！天气多好啊！我正在说谎我正在说谎我学英语，或者我学日语我学英语，或者我学日语如果天气好，那么我去散步如果天气好，那么我去散步√√×√×××√√10?(悖论)√?4• 命题常量：一个命题标识符表示确定的命题。

• 命题变量：一个命题标识符仅表示任意命题的位置标志(无真值)• 原子变元：命题变元表示原子命题56. 2 命题联结词命题联结词• 复合命题——原子命题+联结词1)否定否定¬定义定义 设P为命题，P的否定是一个新的命题，记为¬P若P为T，则¬P为F；若P为F，则¬P为TP¬P1001例：P：上海是大城市 ¬P：上海不是大城市 或上海是不大的城市• 一元联结词62)合取合取∧(并且并且)定义定义 两个命题P、Q的合取是一个复合命题，记作P∧Q当且仅当P、Q同为T时，P∧Q为T ；在其它情况下，P∧Q的真值为FPQP∧Q000010100111例: P: 今天下雨. Q: 明天下雨.P∧Q: 今天下雨且明天下雨 今天明天都下雨 这两天都下雨• 二元联结词7• 与自然语言不同P：我们去看电影Q：房间里有十张桌子P∧Q：我们去看电影且房间里有十张桌子——仍是新命题•可将若干个命题联结一起P：高中毕业Q：上分数线R：被某大学录取P∧Q∧R：大学生83)析取析取∨(或者或者)定义定义 两个命题P、Q的析取是一个复合命题，记作P∨Q当且仅当P、Q同为F时，P∨Q为F ；在其它情况下，P∨Q的真值为T。

PQP∨Q000011101111例: P: 今天下雨. Q: 今天刮风.P∨Q: 今天下雨或者刮风• 二元联结词9• 日常语言中的“或者”可分“可兼或”与“不可兼或”两种：例例1：今天晚上我在家看电视或去剧院看戏不可兼或)例例2：他可能是100米或400米赛跑的冠军可兼或)• 析取是可兼或例例3：P: 他中了大奖Q: 他中了小奖P∨Q: 他中了大奖或者中了小奖也可能两奖都中)104)不可兼析取不可兼析取 (排斥析取排斥析取)定义定义 设设P、Q是两个命题，复合命题P Q称为P、Q的不可兼析取P Q的真值为T当且仅当P与Q的真值不相同；否则，P Q的真值为FPQP Q000011101110例: P: 他坐船去大连 Q: 他乘车去大连P Q: 他坐船或乘车去大连• 二元联结词• P Q  (P∧¬Q)∨(¬P∧Q)115)蕴含蕴含→(条件条件)定义定义 两个命题P、Q的蕴含是一个复合命题，记作P→Q当且仅当P的真值为T，Q的真值为F时，P→Q的真值为F ；在其它情况下，P→Q的真值为TPQP→Q001011100111例1: “如果某动物为哺乳动物，则它必胎生”。

将命题符号化设P: 某动物为哺乳动物 Q: 某动物胎生命题符号化：P→Q且命题为真：P→Q  1• 二元联结词12例例2: “如果我得到这本小说，那么我今天就读完它”将命题符号化，并求命题的真值解解 设P: 我得到这本小说. Q: 我今天就读完它.命题符号化：P→Q且命题的真值有以下四种实际情况：(1) 我得到这本小说，我今天读完它T)(2) 我得到这本小说，我今天没有读完F)(3) 我没有得到这本小说，我今天读完它T)(4) 我没有得到这本小说，我今天没有读完T)13例例3: “如果雪是黑的，那么太阳从西方出”将命题符号化，并求命题的真值解解 设P: 雪是黑的Q: 太阳从西方出命题符号化：P→Q且命题的真值：P→Q  1. ■例例4: “如果雪是黑的，那么太阳从东方出”将命题符号化，并求命题的真值解解 设P: 雪是黑的Q: 太阳从东方出命题符号化：P→Q且命题的真值：P→Q  1. ■14• P→Q中P称为前件，Q称为后件• 自然语言中，若前提为假，无论结论为真或假，往往无法判断PQP→Q001011100111• 在条件命题中，当前提为假时，结论都为真 —— 称“善意的推定”。

• P→Q“如果P那么Q”  “只要P则Q” “从P推出Q”  “P仅当Q” “只有Q才P”  “P蕴含Q”156)等价等价(双条件双条件)定义定义 给定两个命题P和Q，复合命题PQ称为双条件命题当P、Q的真值相同时，PQ的真值为T ；在其它情况下，PQ的真值为FPQPQ001010100111例1: “两个三角形全等当且仅当对应边相等”设P: 两个三角形全等 Q: 三角形对应边相等命题符号化：PQ且命题为真：PQ 1• 二元联结词16例例2: “燕子飞回南方，春天来了”将命题符号化，并求命题的真值解解: 设P: 燕子飞回南方Q: 春天来了命题符号化：PQ且命题的真值：PQ  1. ■例例3: “2+2 = 4 当且仅当雪是白的”将命题符号化，并求命题的真值解解 设P: 2+2 = 4Q: 雪是白的命题符号化：PQ且命题的真值：PQ  1. ■17• 复合命题：设 A1,A2,…An是命题,用五种逻辑联结词将这n个命题联结起来，得到一个新命题，称为复合命题18练习练习1. 设命题P，Q的真值为1，命题R，S的真值为0，试确定下面命题的真值： (P∧Q∧R)∨¬((P∨Q)∧(R∨S));解： (P∧Q∧R)∨¬((P∨Q)∧(R∨S)) (1∧1∧0)∨¬((1∨1)∧(0∨0)) (1∧0)∨¬(1∧0) 0∨¬0 0∨1 1 ■196.3 命题公式的翻译与解释命题公式的翻译与解释• 用大写英文字母代表一个抽象命题, 而不代表一个具体命题, 这个抽象命题称为命题符号.• 原子：命题符号称为原子.定义 合式公式是如下定义的一个符号串(1) 原子是合式公式；(2) 若G, H是合式公式，则如下符号串(¬G), (GH), (GH), (GH), (GH), (G H)是合式公式；(3) 所有公式都是有限次使用(1)(2)得到的符号串。

20• 命题公式：由命题变项、联结词、括号按一定规则组成的合式公式为命题公式例：如下符号串 ((P  (Q  R))  (Q  ((¬S)  R))) 就是公式• 五种逻辑联结词的优先级按如下次序递减 ¬ ,  ,  ,  ,  故上例可写成: P(QR)Q(¬SR)• 对公式中的每个原子赋值后，公式就有一个真值对原子一组赋值称公式的一个解释21定义定义 设G是公式，A1, A2,…, An 是出现在G中的所有原子, 指定 A1,A2,…..An 一组真值, 则这组真值称为G的一组赋值(解释、指派）, 记作I例：G  PQR.G的真值记为 TI (G)1.• 一般地G是具有n个不同原子的公式, 则G有2n 个不同的赋值• 对一个公式G, 将它在所有赋值下所取的真值列成一个表, 称为G的真值表6.4 真值表与等价公式真值表与等价公式22PQR000001010011100101110111例例: 求G  P  (Q  ¬R) 的真值表。

PQR¬RQ ¬RP(Q ¬R)000110001000010110011010100111101000110111111011成真赋值成假赋值PQR¬RQ ¬R0001100100010110110110011101001101111101PQR¬R0001001001010110100110101101111023• 有时赋值 {0, 0, 0} 写成 {¬P, ¬Q, ¬R}, {0, 0, 1} 写成 {¬P, ¬Q, R}, {0, 1, 0} 写成 {¬P, Q, ¬R}, {1, 1, 1} 写成 { P, Q, R},24定义定义：如果公式G,H在任一组赋值 I 下真值相同，则称公式G,H等值，记作 G  H• “  ”不是联结词，它表示两个公式的关系逻辑等价25¬P Q1101可见在所有赋值 I 下真值相同，∴ P→Q  ¬P∨Q . ■例例：用真值表证明公式 P→Q 和 ¬P∨Q等值.证：由真值表：PQ00011011¬P1100P→Q110126例例：证明 P Q  (P∧¬Q)∨(¬P∧Q)。

P Q ¬P ¬Q P QP∧¬Q¬P∧Q (P∧¬Q)(¬P∧Q)0 01100000 11010111 00111011 1000000证证：由真值表可见在所有赋值 I 下真值相同，∴ P Q  (P∧¬Q)∨(¬P∧Q) ■27 共学了六个联结词：¬,∨,∧,,→,• 全功能联结词组：任一命题公式都可用组中的联结词表示，这样的联结词组称全功能联结词组如{¬,∨,∧,,→,}. 由于PQ  (P→Q)∧(Q→P)∴{¬,∨,∧,,→}也是全功能联结词组 由于P Q  (P∧¬Q)∨(¬P∧Q)∴{¬,∨,∧,→}也是全功能联结词组 由于P→Q  ¬P∨Q∴{¬,∨,∧}也是全功能联结词组28 并非所有联结词都是必要的，公式中有些联结词可由其它联结词代替• 最小联结词组：任一命题公式可由这些联结词表示，但不能再少一个如 {¬,∨} 因为 P∧Q  ¬(¬P∨¬Q) 如 {¬,∧} 因为 P∨Q  ¬(¬P∧¬Q) 29常用的逻辑等价式① A  B  (A  B)  (B  A) (等价式)② A  B  ¬ A  B (蕴含式)③ A  A  A， A  A  A (幂等律)④ A  B  B  A， A  B  B  A (交换律)⑤ A  (B  C)  (A  B)  C A  (B  C)  (A  B)  C (结合律)⑥ A  (A  B)  A，A  (A  B)  A (吸收律)⑦ A  (B  C)  (A  B)  (A  C) A  (B  C)  (A  B)  (A  C) (分配律)⑧ A  0  A， A  1  A (同一律) A  0  0， A  1  1 (零律)⑨ A  ¬A 1， A  ¬A  0 (否定律)⑩ ¬(A  B)  ¬A  ¬B, ¬(A  B)  ¬A  ¬B (德摩根律)30⑾ ¬ ¬A  A (双重否定律)⑿ A  B  ¬B  ¬A (假言易位)⒀ A  B  ¬A  ¬B (等价否定式)⒁ (A  B)(A  ¬B)  ¬A (归谬律)⒂ A B  (A  ¬B)  (¬A  B) (异或等值式)31•以上公式的证明有两种方法：(1)真值表；(2)利用公式。

例例：证明吸收律A  (A  B)  A证证一：ABA  B A  (A  B)0000010010011111∴A  (A  B)  A32证证二：A  (A  B)  (A  1)  (A  B) A  (1  B) A  1  A ∴A  (A  B)  A ■33代换规则 在等值式中某命题变项用新的命题公式取代，得到新的等值式 如由 A  A  A 可产生 (P  Q)  (P  Q) (P  Q) 等等•等值演算：从某公式A推导出新公式B，且使 A  B•由基本等值式可以产生无数个不同等值式34 重言式、永真式：G在所有的赋值下都是真的 矛盾式、永假式：G在所有的赋值下都是假的 可满足式：除矛盾式以外的公式 仅可满足式：除重言式和矛盾式以外的公式6.5 重言式与蕴含式重言式与蕴含式35例：① G  P ¬PQ  1PQ ¬P G0011011110011101∴ G 是重言式PQ ¬P ¬PQK00110011101000011011③ K  P(¬PQ) ∴K是可满足式。

仅可满足式)② H  P ¬PQ  0 ∴ H 是矛盾式PQ ¬P H001001101000110036重言蕴含式的三种等价定义重言蕴含式的三种等价定义定义定义1：设G,H是两个公式，如果对任意赋值I，都有TI(G)  TI(H)，则称G重言蕴含H，记作G  H.定义定义2：设G,H是两个公式，对任意赋值I，如果G为真，必有H为真，则称G重言蕴含H，记作G H.定义定义3：设G,H是两个公式，如果(GH)是恒真公式，则称G重言蕴含H，记作G  H.例例1: 证P  P∨G.证1:PGP∨∨G000011101111由定义1得证.■证2: 若P  1,则P∨G  1∨G  1由定义2得证.■证3: ∵P→(P∨G) ¬P∨(P∨G) ¬P∨P∨G 1∨G  1由定义3得证.■37(1) 证明两个公式等值，化简公式；(2) 判别公式的类型；(3) 解决实际问题• 等值式的推演能够解三类问题：38例例1 证明 (1) (P∧Q)∨(P∧¬Q)  P (2) P→(Q→R)  (P∧Q)→R 证证: (1) (P∧Q)∨(P∧¬Q)  P∧(Q∨¬Q) P∧1  P∴ (P∧Q)∨(P∧¬Q)  P(2) P→(Q→R)  ¬P∨(¬Q∨R)  ¬P∨¬Q∨R  ¬(P∧Q)∨R  (P∧Q)→R∴ P→(Q→R)  (P∧Q)→R ■39例例2 化简 ((A→B)(¬B→¬A))∧C.解解： ∵¬B→¬A  B∨¬A  ¬A∨B  A→B。

∴((A→B)  (¬B→¬A))∧C ((A→B)  (A→B))∧C 1∧C(由等价的定义：当P、Q的真值相同时，PQ的真值为 1 ) C. ■40例例3 判别下列公式的类型:(1) Q∨¬((¬P∨Q)∧P).解解：Q∨¬((¬P∨Q)∧P) Q∨(¬(¬P∨Q)∨¬P) ¬P∨Q∨¬(¬P∨Q) 1.∴公式Q∨¬((¬P∨Q)∧P)为重言式41(2) (P∨¬P)→((Q∧¬Q)∧R).解解：(P∨¬P)→((Q∧¬Q)∧R) 1→(0∧R) 1→0  0.∴公式(P∨¬P)→((Q∧¬Q)∧R)为矛盾式3) (P→Q)∧¬P.解解：(P→Q)∧¬P  (¬P∨Q)∧¬P  ¬P当P1, 公式 0；当P0, 公式 1∴公式(P→Q)∧¬P是可满足式 ■42对偶式•对偶式:在一个不含联结词和的公式里, 将换成,  换成, 1 换成0, 0换成1, 得一新公式, 称为原公式的对偶式.•将一个等值式的等号两端换成其对偶式, 得到一新等值式, 称为原等值式的对偶式.• 对偶性质: 如果一个等值式是成立的, 其对偶等值式也成立.6.6 范式范式43• 公式的形式千变万化：G  G  (G  H) G  G  G  1等等，是否有标准形式？定义定义：有限个命题变项或其否定构成的析取式称为简单析取式。

有限个命题变项或其否定构成的合取式称为简单合取式如：¬P∨Q ； A∧¬B∧¬C.定义定义：有限个简单合取式构成的析取式称为析取范式有限个简单析取式构成的合取式称为合取范式如：P∨(P∧Q )∨(P∧¬Q∧R )；Q∧(¬P∨Q )∧(P∨¬Q∨R ).44• 析取范式的对偶式称为合取范式；合取范式的对偶式称为析取范式如：(P∧Q )∨(P∧¬Q∧R )；对偶式为 (P∨Q )∧(P∨¬Q∨R ).• P∨¬Q∨R 既是析取范式，又是合取范式• P∧¬Q∧R 既是析取范式，又是合取范式• P 既是析取范式，又是合取范式45定理定理 (范式存在定理)：对于任意公式，都存在等值于它的析取范式和合取范式证证：对任意公式G，通过如下算法可得出等值于G的范式：(1) 将,,∨化为¬, ∨, ∧；(2) 将¬ 移到原子前；(3) 反复使用分配律,即可得到等值于G的范式■例例1: 将G (P(QR)) S 化为析取范式和合取范式.解：G  (P(QR))S  ¬(P(¬QR))S  (¬P(Q ¬R))S  ¬P(Q¬R) S  (¬PS )(Q¬R) (¬PSQ)(¬PS¬R)■析取范式合取范式46例例2：将P(QR)化为析取范式和合取范式。

解解：P(QR) (合取范式) (PQ)  (PR)(析取范式) ■• 析取范式和合取范式不唯一如：P  P  1  P(Q¬Q)  (PQ)(P¬Q). P  P  0  P(Q¬Q)  (PQ)(P¬Q).(第二式由对偶关系得到)• 主析取范式和主合取范式唯一47定义定义：n个命题变项P1,P2,…,Pn , 每个变项与它的否定不同时出现，但是两者必须出现一个, 且排列顺序与 P1,P2,…,Pn的顺序一致, 这样的简单合取式称为关于P1,P2,…,Pn 的一个极小项或布尔合取• 含n个命题变项的公式G共有2n个极小项，且与公式G的2n个赋值对应48例例：公式G中包含P,Q,R三个命题变项：极小项成真赋值记法¬P∧¬Q∧¬R0 0 0m0¬P∧¬Q∧ R0 0 1m1¬P∧ Q∧¬R0 1 0m2¬P∧ Q∧ R0 1 1m3 P∧¬Q∧¬R1 0 0m4 P∧¬Q∧ R1 0 1m5 P∧ Q∧¬R1 1 0m6 P∧ Q∧ R1 1 1m749定义定义：对于含有n个命题变项的命题公式，如果有一个仅由极小项的析取构成的等值式, 则该等值式称为原命题公式的主析取范式。

定理定理：任何命题公式都存在与之等值的主析取范式，并且是唯一的求主析取范式的方法求主析取范式的方法 : 1. 真值表法 在一个命题公式的真值表中，真值为1的赋值所对应的极小项的析取，即为此命题公式的主析取范式50例3 用真值表法求 P→Q, P∧Q, ¬(P∧Q) 的主析取范式解：PQP→QP  Q¬ (P  Q)00101011011000111110P→Q  (¬P¬Q)∨(¬PQ)∨(PQ)  m0∨m1∨m3 (0, 1, 3)P  Q  (PQ)  m3  (3)¬ (P  Q)  (¬P¬Q)∨(¬PQ)∨(P¬Q) m0∨m1∨m2  (0, 1, 2)512. 等值演算法： (1) 求命题公式的析取范式；(2) “消去”命题公式中所有矛盾式的析取项(如 P ¬P)，合并相同项；(3) 若析取范式的某个合取项缺少命题变项Pj或¬Pj，则添加(Pj ¬Pj)，再用分配律展开；(4) 将极小项按由小到大的次序排列，用表示之52例例：求公式G  ¬(RP)  (Q  (P  R)) 的主析取范式解解：G  ¬(RP)  (Q  (P  R))  ¬(¬RP)  (Q  ( P  R))  (R  ¬P)  (Q  P)  (Q  R)  ((R  ¬P)(Q  ¬Q)) ((QP)(R ¬R)) ((Q  R)(P  ¬P))  (R¬PQ)(R¬P¬Q)(QPR) (QP¬R)(QRP)(QR¬P)  (¬PQR)(¬P¬QR)(PQR) (PQ¬R)(PQR)(¬PQR)53 (¬PQR)(¬P¬QR)(PQR) (PQ¬R) m3  m1  m7  m6 m1 m3  m6 m7   (1, 3, 6, 7). ■• 对任意公式G, 存在唯一一个与G等值的主析取范式。

• 恒假公式的主析取范式用 0 表示54• 主合取范式定义定义：n个命题变项P1,P2,…,Pn , 每个变项与它的否定不同时出现，但是两者必须出现一个, 且排列顺序与 P1,P2,…,Pn的顺序一致, 这样的简单析取式称为关于P1,P2,…,Pn 的一个极大项或布尔析取• 极小项的对偶称为极大项• 含n个原子的公式G共有2n个极大项，且与公式G的2n个赋值对应55例例：公式G中包含P,Q,R三个命题变项：极大项成假赋值记法 P∨ Q∨ R0 0 0M0 P∨ Q∨¬R0 0 1M1 P∨¬Q∨ R0 1 0M2 P∨¬Q∨¬R0 1 1M3¬P∨ Q∨ R1 0 0M4¬P∨ Q∨¬R1 0 1M5¬P∨¬Q∨ R1 1 0M6¬P∨¬Q∨¬R1 1 1M756定义定义：对于含有n个命题变项的命题公式，如果有一个仅由极大项的合取构成的等值式, 则该等值式称为原命题公式的主合取范式定理定理：任何命题公式都存在与之等值的主合取范式，并且是唯一的57例5 用真值表法求 (R→(P∨Q))∧(P→(¬Q ∧R)) 的主合取范式。

解：P Q RR→(P∨Q)P→(¬Q ∧R)(R→(P∨Q))∧(P→(¬Q ∧R))0 0 01110 0 10100 1 01110 1 11111 0 01001 0 11111 1 01001 1 110058  M1∨M4∨M6∨M7  (1, 4, 6, 7) ∴(R→(P∨Q))∧(P→(¬Q ∧R))  (P∨Q∨¬R)∧(¬P∨Q∨R)∧(¬P∨¬Q∨R)∧(¬P∨¬Q∨¬R)59等值演算法： (1) 求命题公式的合取范式；(2) “消去”命题公式中所有永真的合取项(如 P  ¬P)，合并相同项；(3) 若合取范式的某个析取项缺少命题变项Pj或¬Pj，则添加(Pj ¬Pj)，再用分配律展开；(4) 将极大项按由小到大的次序排列，用表示之60•主合取范式的求法与主析取范式的求法类似例例：求公式G  ¬(PQ)  P 的主合取范式解：G  ¬(PQ)  P ¬(¬PQ)  P (P¬Q)  P (P  P)  (¬Q  P) P  (¬Q  P) P(Q  ¬Q)  (¬Q  P) (PQ)  (P ¬Q)  (P  ¬Q) (PQ)  (P ¬Q) M0  M1  (0, 1).■61主析取范式、主合取范式和真值表之间的关系：主析取范式主合取范式真值表• 知道三者之一能直接求出另外两个。

62例例: G  ¬(RP)  (Q  (P  R)), 求G的主析取范式，主合取范式和真值表P Q RG0 0 000 0 110 1 000 1 111 0 001 0 101 1 011 1 11解解：前已求出G的主析取范式G  (¬PQR) (¬P¬QR) (PQR)(PQ¬R)  m1  m3  m6 m7   (1, 3, 6, 7)   (0, 2, 4, 5)  M0M2M4M5  (PQR)(P¬QR) (¬PQR)(¬PQ¬R)(主合取范式↑)(真值表→). ■63• 同一赋值对应的极小项和极大项不相同如公式G中包含P,Q二个原子P Q极小项极大项0 0¬P∧¬Q P∨ Q0 1¬P∧ Q P∨¬Q1 0 P∧¬Q¬P∨ Q1 1 P∧ Q¬P∨¬Q• 主析取范式  极小项  成真赋值• 主合取范式  极大项  成假赋值64• 主范式的用途：(1) 判断(证明)两个公式等值；(2) 判断公式的类型：• 解题可考虑三种方法：①等值公式；②主范式；③真值表。

3) 解决实际问题；(4) 求公式的成真赋值和成假赋值含2n个极小项(1) ——永真式含0个极小项(0) ——永假式至少含1个极小项 ——可满足656.7 命题逻辑的推理理论命题逻辑的推理理论推理推理：从给定的前提推出一个结论也称为演绎、形式证明、蕴含定义定义：设A1,A2,...,Am,C为命题公式，如果(A1,A2,...,Am)C 为重言式，则称C为前提{A1,A2,...,Am}的有效结论，或称由{A1,A2,...,Am}逻辑地推出C. 记作A1∧A2∧...∧Am C 上式为重言蕴含式66• 判断推理的五种方法：真值表法等值演算法主析取范式法直接证法间接证法1. 真值表法如果A1∧A2∧...∧Am=1, C也为1，则有A1∧A2∧...∧Am C67例例1：C是否是前提A1和A2的有效结论1) A1: P→QA2: PC: Q (2) A1: P→QA2: ¬PC: Q (3) A1: P→QA2: QC: P PQ¬PP→Q0011011110001101解：构造真值表(1) 当A1和A2都为1时，C为1，∴P→Q , P  Q .(2) 当A1和A2都为1时，C有值为0，∴ Q不是P→Q和¬P 的有效结论 .(2) 当A1和A2都为1时，C有值为0，∴ P不是P→Q和Q 的有效结论 .682 等值演算法例2: 证例1中各题(1) A1: P→Q A2: P C: Q 解：(1) ((P→Q)∧P)→Q ¬((¬P∨Q)∧P)∨Q ((P∧¬Q)∨¬P)∨Q (P∧¬Q)∨¬P∨Q (P∨¬P∨Q)∧(¬Q∨¬P∨Q) 1∧1  1所以 P→Q , P  Q .69(2) ((P→Q)∧¬P)→Q(2) A1: P→Q A2: ¬P C: Q  ¬((¬P∨Q)∧¬P)∨Q ((P∧¬Q)∨P)∨Q P∨Q不是重言式，所以Q 不是 P→Q 和 ¬P 的有效结论。

703 主析取范式法例3: 证例1中各题(1) A1: P→Q A2: P C: Q 解：(1) ((P→Q)∧P)→Q ¬((¬P∨Q)∧P)∨Q  ((P∧¬Q)∨¬P)∨Q (P∧¬Q)∨¬P∨Q (P∧¬Q)∨(¬P∧Q)∨(¬P∧¬Q) ∨(P∧Q)∨(¬P∧Q) (P∧¬Q)∨(¬P∧Q)∨(¬P∧¬Q)∨(P∧Q) m0∨m1∨m2∨m3   (0, 1, 2, 3)所以 P→Q , P  Q .71(2) ((P→Q)∧¬P)→Q(2) A1: P→Q A2: ¬P C: Q  ¬((¬P∨Q)∧¬P)∨Q ((P∧¬Q)∨P)∨Q P∨Q M0   (0)  (1, 2, 3)不是重言式，所以Q 不是 P→Q 和 ¬P 的有效结论724 直接证法直接证法(形式演绎形式演绎)• A1，A2，...，An  B (从前提推演出结论)• 形式演绎规则: • 规则P: 在推导的过程中引入已知前提公式;• 规则T: 在演绎过程中可以利用前面演绎出来的中间结果推出新的命题公式• 演绎过程中需要用到等值式和重言蕴含式。

73重言蕴含式(14个)I1 A  B  A I2 A  B  B (化简)I3 A  A  B I4 B  A  B (附加)I5 ¬A  (A  B) I6 B  (A  B)I7 ¬(A  B)  A I8 ¬(A  B)  ¬BI9 A, B  A  B (合取引入)I10 ¬A, A  B  B (析取三段论)I11 A, A  B  B (假言推论)I12 ¬B, A  B  ¬A (拒取式)I13 A  B, B  C  A  C (假言三段论)I14 A  B, A  C, B  C  C (构造性二难)• I5和I7、I6和I8互为逆否命题。

I1 A  B  A I2 A  B  B (化简)I3 A  A  B I4 B  A  B (附加)I5 ¬A  (A  B) I6 B  (A  B)I7 ¬(A  B)  A I8 ¬(A  B)  ¬BI9 A, B  A  B (合取引入)I10 ¬A, A  B  B (析取三段论)I11 A, A  B  B (假言推论)I12 ¬B, A  B  ¬A (拒取式)I13 A  B, B  C  A  C (假言三段论)I14 A  B, A  C, B  C  C (构造性二难)• I5和I7、I6和I8互为逆否命题。

74例例4: 证明CD, (CD)¬H, ¬H(A¬B), (A¬B)(RS)  RS.证证: (1) CD P (2) (CD)¬H P (3) ¬H T (1)(2) (4) ¬H(A¬B) P (5) A¬B T (3)(4) (6) (A¬B)(RS) P (7) RS T (5)(6)∴ CD, (CD)¬H, ¬H(A¬B), (A¬B)(RS)  RS. ■75例例5: 证明AB, A¬C, DE, ¬DC, ¬E  B 证证: (1) ¬E P (2) DE P (3) ¬D T (1)(2) (4) ¬DC P (5) C T (3)(4) (6) A¬CP (7) ¬A T (5)(6) (8) ABP (9) B T (7)(8)∴AB, A¬C, DE, ¬DC, ¬E  B ■76例例6: 证明 P  Q, PR, QS  SR.证证: (1) P  Q P (2) ¬PQ T (1) (3) QS P (4) ¬PS T (2)(3) (5) ¬SP T (4) (6) PR P (7) ¬SR T (5)(6) (8) SR T (7)∴ P  Q, PR, QS  SR ■77例例6: 证明 P  Q, PR, QS  SR.证二证二: (1) Q  S P (2) ¬S  ¬Q T (1) (3) P  Q P (4) ¬Q  P T (3) (5) ¬S  P T (2)(4) (6) P  R P (7) ¬S  R T (5)(6) (8) SR T (7)∴ P  Q, PR, QS  SR ■785 间接证法 有时要证明的结论以蕴含式的形式出现：A1，A2，...，An  B  C由于 A1A2...An (B  C)  (A1A2...An B)  C 这说明可把B作为附加前提加入到前提中，这种方法称为附加前提证法，简称CP规则。

规则CP: 如果需要演绎出的公式具有B  C 的形式,则可以将B 做为附加前提使用, 而力图演绎出C即可79例例7: 证明 P  (Q  S), ¬R  P, Q  R  S.证证: (1) R P (附加) (2) ¬R  P P (3) P T (1)(2) (4) P(QS) P (5) QS T (3)(4) (6) Q P (7) S T (5)(6) (8) RS CP (1)(7)∴ P  (Q  S), ¬R  P, Q  R  S. ■80例例7: 证明 P  (Q  S), ¬R  P, Q  R  S.证二证二: (1) Q P (2) P(QS) P (3) ¬P ¬Q  S T (2) (4) ¬P  S T (1)(3) (5) P  S T (4) (6) ¬R  P P (7) R  P T (6) (8) R  S T (5)(7)∴ P  (Q  S), ¬R  P, Q  R  S. ■81例例6: 证明 P  Q, PR, QS  SR.证三证三: 等价于证 P  Q, PR, QS  ¬SR. (1) ¬S P (附加) (2) Q  S P (3) ¬S  ¬Q T (2) (4) ¬Q T (1)(3) (5) P  Q P (6) P T (4)(5) (7) P  R P (8) R T (6)(7) (9) ¬SR CP (1)(8)∴ P  Q, PR, QS  SR ■82• 反证法反证法(归谬法归谬法)例例8: 证明 R→¬Q, RS, S→¬Q, P→Q  ¬P.证证:反证法 (1) P P (附加) (2) P→Q P (3) QT (1)(2) (4) R→¬Q P (5) ¬R T (3)(4) (6) RS P (7) S T (5)(6) (8) S→¬Q P (9) ¬Q T (7)(8) (3)(9)矛盾∴ ¬(P  ¬Q), ¬Q  R, ¬R  ¬P. ■83例例9: 证明 ¬(P  ¬Q), ¬Q  R, ¬R  ¬P.证证: 反证法。

(1) P P (附加) (2) ¬(P  ¬Q) P (3) ¬P  Q T (2) (4) Q T (1)(3) (5) ¬Q  R P (6) R T (4)(5) (7) ¬R P (6)与(7)矛盾，∴ ¬(P  ¬Q), ¬Q  R, ¬R  ¬P. ■84。