第编数理逻辑课件

1、第 3 编 数 理 逻 辑第 6 章 命 题 逻 辑16.1 命题的概念与表示命题 日常语言不确切，具有二义性需引入目标语言、公式符号。 目标语言：表达判断的一些语言的汇集。 判断：肯定、否定的思维形式。 命题：能表达判断，具有确定真值的陈述句。2真值：命题的判断结果称为真值。只有“真”和“假”两种，记为“T”和“F”，或“1”和“0”。没有判断无所谓是非的句子感叹句、疑问句、祈使句不是命题。原子命题：不能分为更简单的陈述句。复合命题：由联结词、标点符号和原子命题复合构成的命题。用大写字母A,B,.,P,Q,.或Ai,12等表示命题。例 P: 今天下雨。12: 今天刮风。命题标识符：表示命题的

2、符号。3例：语句是否命题真值中国人民是伟大的。雪是黑的。1 + 1 = 10别的星球上有生物。全体立正！明天是否开会？天气多好啊！我正在说谎。我学英语，或者我学日语。如果天气好，那么我去散步。10?(悖论)?4 命题常量：一个命题标识符表示确定的命题。 命题变量：一个命题标识符仅表示任意命题的位置标志(无真值)。 原子变元：命题变元表示原子命题。56. 2 命题联结词 复合命题原子命题+联结词否定定义 设P为命题，P的否定是一个新的命题，记为P。若P为T，则P为F；若P为F，则P为T。PP1001例：P：上海是大城市。 P：上海不是大城市。 或上海是不大的城市。 一元联结词。6合取(并且)定义

3、 两个命题P、Q的合取是一个复合命题，记作PQ。当且仅当P、Q同为T时，PQ为T ；在其它情况下，PQ的真值为F。PQPQ000010100111例: P: 今天下雨. Q: 明天下雨.PQ: 今天下雨且明天下雨。 今天明天都下雨。 这两天都下雨。 二元联结词。7 与自然语言不同。P：我们去看电影。Q：房间里有十张桌子。PQ：我们去看电影且房间里有十张桌子。仍是新命题。可将若干个命题联结一起。P：高中毕业。Q：上分数线。R：被某大学录取。PQR：大学生。8析取(或者)定义 两个命题P、Q的析取是一个复合命题，记作PQ。当且仅当P、Q同为F时，PQ为F ；在其它情况下，PQ的真值为T。PQPQ0

4、00011101111例: P: 今天下雨. Q: 今天刮风.PQ: 今天下雨或者刮风。 二元联结词。9 日常语言中的“或者”可分“可兼或”与“不可兼或”两种：例1：今天晚上我在家看电视或去剧院看戏。(不可兼或)例2：他可能是100米或400米赛跑的冠军。(可兼或) 析取是可兼或。例3：P: 他中了大奖。Q: 他中了小奖。PQ: 他中了大奖或者中了小奖。(也可能两奖都中)10不可兼析取 (排斥析取)定义 设P、Q是两个命题，复合命题P Q称为P、Q的不可兼析取。P Q的真值为T当且仅当P与Q的真值不相同；否则，P Q的真值为F。PQP Q000011101110例: P: 他坐船去大连。 Q:

5、 他乘车去大连。P Q: 他坐船或乘车去大连。 二元联结词。 P Q (PQ)(PQ)11蕴含(条件)定义 两个命题P、Q的蕴含是一个复合命题，记作PQ。当且仅当P的真值为T，Q的真值为F时，PQ的真值为F ；在其它情况下，PQ的真值为T。PQPQ001011100111例1: “如果某动物为哺乳动物，则它必胎生”。将命题符号化。设P: 某动物为哺乳动物。 Q: 某动物胎生。命题符号化：PQ。且命题为真：PQ 1。 二元联结词。12例2: “如果我得到这本小说，那么我今天就读完它”。将命题符号化，并求命题的真值。解 设P: 我得到这本小说. Q: 我今天就读完它.命题符号化：PQ。且命题的真值

6、有以下四种实际情况：(1) 我得到这本小说，我今天读完它。(T)(2) 我得到这本小说，我今天没有读完。(F)(3) 我没有得到这本小说，我今天读完它。(T)(4) 我没有得到这本小说，我今天没有读完。(T)13例3: “如果雪是黑的，那么太阳从西方出”。将命题符号化，并求命题的真值。解 设P: 雪是黑的。Q: 太阳从西方出。命题符号化：PQ。且命题的真值：PQ 1. 例4: “如果雪是黑的，那么太阳从东方出”。将命题符号化，并求命题的真值。解 设P: 雪是黑的。Q: 太阳从东方出。命题符号化：PQ。且命题的真值：PQ 1. 14 PQ中P称为前件，Q称为后件。 自然语言中，若前提为假，无论结

7、论为真或假，往往无法判断。PQPQ001011100111 在条件命题中，当前提为假时，结论都为真 称“善意的推定”。 PQ“如果P那么Q” “只要P则Q” “从P推出Q” “P仅当Q” “只有Q才P” “P蕴含Q”15等价(双条件)定义 给定两个命题P和Q，复合命题PQ称为双条件命题。当P、Q的真值相同时，PQ的真值为T ；在其它情况下，PQ的真值为F。PQPQ001010100111例1: “两个三角形全等当且仅当对应边相等”。设P: 两个三角形全等。 Q: 三角形对应边相等。命题符号化：PQ。且命题为真：PQ 1。 二元联结词。16例2: “燕子飞回南方，春天来了”。将命题符号化，并求命

8、题的真值。解: 设P: 燕子飞回南方。Q: 春天来了。命题符号化：PQ。且命题的真值：PQ 1. 例3: “2+2 = 4 当且仅当雪是白的”。将命题符号化，并求命题的真值。解 设P: 2+2 = 4。Q: 雪是白的。命题符号化：PQ。且命题的真值：PQ 1. 17 复合命题：设 A1,A2,An是命题,用五种逻辑联结词将这n个命题联结起来，得到一个新命题，称为复合命题。18练习1. 设命题P，Q的真值为1，命题R，S的真值为0，试确定下面命题的真值： (PQR)(PQ)(RS);解： (PQR)(PQ)(RS) (110)(11)(00) (10)(10) 00 01 1 196.3 命题公

9、式的翻译与解释 用大写英文字母代表一个抽象命题, 而不代表一个具体命题, 这个抽象命题称为命题符号. 原子：命题符号称为原子.定义 合式公式是如下定义的一个符号串(1) 原子是合式公式；(2) 若G, H是合式公式，则如下符号串(G), (GH), (GH), (GH), (GH), (G H)是合式公式；(3) 所有公式都是有限次使用(1)(2)得到的符号串。20 命题公式：由命题变项、联结词、括号按一定规则组成的合式公式为命题公式。例：如下符号串 (P (Q R) (Q (S) R) 就是公式。 五种逻辑联结词的优先级按如下次序递减 , , , , 故上例可写成: P(QR)Q(SR) 对

10、公式中的每个原子赋值后，公式就有一个真值。对原子一组赋值称公式的一个解释。21定义 设G是公式，A1, A2, An 是出现在G中的所有原子, 指定 A1,A2,.An 一组真值, 则这组真值称为G的一组赋值(解释、指派）, 记作I。例：G PQR.G的真值记为 TI (G)1. 一般地G是具有n个不同原子的公式, 则G有2n 个不同的赋值。 对一个公式G, 将它在所有赋值下所取的真值列成一个表, 称为G的真值表。6.4 真值表与等价公式22PQR000001010011100101110111例: 求G P (Q R) 的真值表。PQRRQ RP(Q R)000110001000010110

11、011010100111101000110111111011成真赋值成假赋值PQRRQ R0001100100010110110110011101001101111101PQRR0001001001010110100110101101111023 有时赋值 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。 “ ”不是联结词，它表示两个公式的关系。逻辑等价25P Q1101可见在所有赋值 I 下真值相

12、同， PQ PQ . 例：用真值表证明公式 PQ 和 PQ等值.证：由真值表：PQ00011011P1100PQ110126例：证明 P Q (PQ)(PQ)。PQPQP QPQPQ(PQ)(PQ)00110000011010111001110111000000证：由真值表可见在所有赋值 I 下真值相同， P Q (PQ)(PQ)。 27 共学了六个联结词：, 全功能联结词组：任一命题公式都可用组中的联结词表示，这样的联结词组称全功能联结词组。如,. 由于PQ (PQ)(QP),也是全功能联结词组。 由于P Q (PQ)(PQ),也是全功能联结词组。 由于PQ PQ,也是全功能联结词组。28

13、并非所有联结词都是必要的，公式中有些联结词可由其它联结词代替。 最小联结词组：任一命题公式可由这些联结词表示，但不能再少一个。如 ,。 因为 PQ (PQ) 如 ,。 因为 PQ (PQ) 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，

14、 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 BA (A B)0000010010011111A (A B) A。32证二：A (A B) (A 1) (A B) A (1 B) A 1 A A (A B)

15、A。 33代换规则 在等值式中某命题变项用新的命题公式取代，得到新的等值式。 如由 A A A 可产生 (P Q) (P Q) (P Q) 等等。等值演算：从某公式A推导出新公式B，且使 A B。由基本等值式可以产生无数个不同等值式。34 重言式、永真式：G在所有的赋值下都是真的。 矛盾式、永假式：G在所有的赋值下都是假的。 可满足式：除矛盾式以外的公式。 仅可满足式：除重言式和矛盾式以外的公式。6.5 重言式与蕴含式35例： G P PQ 1PQPG0011011110011101 G 是重言式。PQPPQK00110011101000011011 K P(PQ) K是可满足式。(仅可满足式

16、) H P PQ 0 H 是矛盾式。PQPH001001101000110036重言蕴含式的三种等价定义定义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是两个公式，如果(GH)是恒真公式，则称G重言蕴含H，记作G H.例1: 证P PG.证1:PGPG000011101111由定义1得证.证2: 若P 1,则PG 1G 1由定义2得证.证3: P(PG) P(PG) PPG 1G 1由定义3得证.37(1) 证明两个公式等值，化

17、简公式；(2) 判别公式的类型；(3) 解决实际问题。 等值式的推演能够解三类问题：38例1 证明 (1) (PQ)(PQ) P (2) P(QR) (PQ)R 证: (1) (PQ)(PQ) P(QQ) P1 P (PQ)(PQ) P(2) P(QR) P(QR) PQR (PQ)R (PQ)R P(QR) (PQ)R 39例2 化简 (AB)(BA)C.解： BA BA AB AB。(AB) (BA)C (AB) (AB)C 1C(由等价的定义：当P、Q的真值相同时，PQ的真值为 1 ) C. 40例3 判别下列公式的类型:(1) Q(PQ)P).解：Q(PQ)P) Q(PQ)P) PQ(

18、PQ) 1.公式Q(PQ)P)为重言式。41(2) (PP)(QQ)R).解：(PP)(QQ)R) 1(0R) 10 0.公式(PP)(QQ)R)为矛盾式。(3) (PQ)P.解：(PQ)P (PQ)P P当P1, 公式 0；当P0, 公式 1。公式(PQ)P是可满足式。 42对偶式对偶式:在一个不含联结词和的公式里, 将换成, 换成, 1 换成0, 0换成1, 得一新公式, 称为原公式的对偶式.将一个等值式的等号两端换成其对偶式, 得到一新等值式, 称为原等值式的对偶式. 对偶性质: 如果一个等值式是成立的, 其对偶等值式也成立.6.6 范式43 公式的形式千变万化：G G (G H) G

19、G G 1等等，是否有标准形式？定义：有限个命题变项或其否定构成的析取式称为简单析取式。有限个命题变项或其否定构成的合取式称为简单合取式。如：PQ ； ABC.定义：有限个简单合取式构成的析取式称为析取范式。有限个简单析取式构成的合取式称为合取范式。如：P(PQ )(PQR )；Q(PQ )(PQR ).44 析取范式的对偶式称为合取范式；合取范式的对偶式称为析取范式。如：(PQ )(PQR )；对偶式为(PQ )(PQR ). PQR 既是析取范式，又是合取范式。 PQR 既是析取范式，又是合取范式。 P 既是析取范式，又是合取范式。45定理 (范式存在定理)：对于任意公式，都存在等值于它的

20、析取范式和合取范式。证：对任意公式G，通过如下算法可得出等值于G的范式：(1) 将,化为, , ；(2) 将 移到原子前；(3) 反复使用分配律,即可得到等值于G的范式。例1: 将G (P(QR) S 化为析取范式和合取范式.解：G (P(QR)S (P(QR)S (P(Q R)S P(QR) S (PS )(QR) (PSQ)(PSR)析取范式合取范式46例2：将P(QR)化为析取范式和合取范式。解：P(QR) (合取范式) (PQ) (PR)(析取范式) 析取范式和合取范式不唯一。如：P P 1 P(QQ) (PQ)(PQ). P P 0 P(QQ) (PQ)(PQ).(第二式由对偶关系得

21、到) 主析取范式和主合取范式唯一。47定义：n个命题变项P1,P2,Pn , 每个变项与它的否定不同时出现，但是两者必须出现一个, 且排列顺序与 P1,P2,Pn的顺序一致, 这样的简单合取式称为关于P1,P2,Pn 的一个极小项或布尔合取。 含n个命题变项的公式G共有2n个极小项，且与公式G的2n个赋值对应。48例：公式G中包含P,Q,R三个命题变项：极小项成真赋值记法PQR0 0 0m0PQ R0 0 1m1P QR0 1 0m2P Q R0 1 1m3 PQR1 0 0m4 PQ R1 0 1m5 P QR1 1 0m6 P Q R1 1 1m749定义：对于含有n个命题变项的命题公式，

22、如果有一个仅由极小项的析取构成的等值式, 则该等值式称为原命题公式的主析取范式。定理：任何命题公式都存在与之等值的主析取范式，并且是唯一的。求主析取范式的方法 : 1. 真值表法 在一个命题公式的真值表中，真值为1的赋值所对应的极小项的析取，即为此命题公式的主析取范式。50例3 用真值表法求 PQ, PQ, (PQ) 的主析取范式。解：PQPQP Q (P Q)00101011011000111110PQ (PQ)(PQ)(PQ) m0m1m3 (0, 1, 3)P Q (PQ) m3 (3) (P Q) (PQ)(PQ)(PQ) m0m1m2 (0, 1, 2)512. 等值演算法： (1)

23、 求命题公式的析取范式；(2) “消去”命题公式中所有矛盾式的析取项(如 P P)，合并相同项；(3) 若析取范式的某个合取项缺少命题变项Pj或Pj，则添加(Pj Pj)，再用分配律展开；(4) 将极小项按由小到大的次序排列，用表示之。52例：求公式G (RP) (Q (P R) 的主析取范式。解：G (RP) (Q (P R) (RP) (Q ( P R) (R P) (Q P) (Q R) (R P)(Q Q) (QP)(R R) (Q R)(P P) (RPQ)(RPQ)(QPR) (QPR)(QRP)(QRP) (PQR)(PQR)(PQR) (PQR)(PQR)(PQR)53 (PQ

24、R)(PQR)(PQR) (PQR) 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

25、 P QR0 0 1M1 PQ R0 1 0M2 PQR0 1 1M3P Q R1 0 0M4P QR1 0 1M5PQ R1 1 0M6PQR1 1 1M756定义：对于含有n个命题变项的命题公式，如果有一个仅由极大项的合取构成的等值式, 则该等值式称为原命题公式的主合取范式。定理：任何命题公式都存在与之等值的主合取范式，并且是唯一的。57例5 用真值表法求 (R(PQ)(P(Q R) 的主合取范式。解：PQRR(PQ)P(Q R)(R(PQ)(P(Q R)00011100101001011101111110010010111111010011110058 M1M4M6M7 (1, 4, 6

26、, 7) (R(PQ)(P(Q R) (PQR)(PQR)(PQR)(PQR)59等值演算法： (1) 求命题公式的合取范式；(2) “消去”命题公式中所有永真的合取项(如 P P)，合并相同项；(3) 若合取范式的某个析取项缺少命题变项Pj或Pj，则添加(Pj Pj)，再用分配律展开；(4) 将极大项按由小到大的次序排列，用表示之。60主合取范式的求法与主析取范式的求法类似。例：求公式G (PQ) P 的主合取范式。解：G (PQ) P (PQ) P (PQ) P (P P) (Q P) P (Q P) P(Q Q) (Q P) (PQ) (P Q) (P Q) (PQ) (P Q) M0

27、M1 (0, 1).61主析取范式、主合取范式和真值表之间的关系：主析取范式主合取范式真值表 知道三者之一能直接求出另外两个。62例: G (RP) (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 (PQR) (PQR) (PQR)(PQR) m1 m3 m6 m7 (1, 3, 6, 7) (0, 2, 4, 5) M0M2M4M5 (PQR)(PQR) (PQR)(PQR)(主合取范式)(真值表). 63 同一赋值对应的极小项和极大项不相同。如

28、公式G中包含P,Q二个原子。P Q极小项极大项0 0PQ P Q0 1P Q PQ1 0 PQP Q1 1 P QPQ 主析取范式 极小项 成真赋值 主合取范式 极大项 成假赋值64 主范式的用途：(1) 判断(证明)两个公式等值；(2) 判断公式的类型： 解题可考虑三种方法：等值公式；主范式；真值表。(3) 解决实际问题；(4) 求公式的成真赋值和成假赋值。含2n个极小项(1) 永真式含0个极小项(0) 永假式至少含1个极小项 可满足656.7 命题逻辑的推理理论推理：从给定的前提推出一个结论。也称为演绎、形式证明、蕴含。定义：设A1,A2,.,Am,C为命题公式，如果(A1,A2,.,Am

29、)C 为重言式，则称C为前提A1,A2,.,Am的有效结论，或称由A1,A2,.,Am逻辑地推出C. 记作A1A2.Am C 上式为重言蕴含式。66 判断推理的五种方法：真值表法等值演算法主析取范式法直接证法间接证法1. 真值表法如果A1A2.Am=1, C也为1，则有A1A2.Am C67例1：C是否是前提A1和A2的有效结论。(1) A1: PQA2: PC: Q (2) A1: PQA2: PC: Q (3) A1: PQA2: QC: P PQPPQ0011011110001101解：构造真值表(1) 当A1和A2都为1时，C为1，PQ , P Q .(2) 当A1和A2都为1时，C有

30、值为0， Q不是PQ和P 的有效结论 .(2) 当A1和A2都为1时，C有值为0， P不是PQ和Q 的有效结论 .682 等值演算法例2: 证例1中各题(1) A1: PQ A2: P C: Q 解：(1) (PQ)P)Q (PQ)P)Q (PQ)P)Q (PQ)PQ (PPQ)(QPQ) 11 1所以 PQ , P Q .69(2) (PQ)P)Q(2) A1: PQ A2: P C: Q (PQ)P)Q (PQ)P)Q PQ不是重言式，所以Q 不是 PQ 和 P 的有效结论。703 主析取范式法例3: 证例1中各题(1) A1: PQ A2: P C: Q 解：(1) (PQ)P)Q (P

31、Q)P)Q (PQ)P)Q (PQ)PQ (PQ)(PQ)(PQ) (PQ)(PQ) (PQ)(PQ)(PQ)(PQ) m0m1m2m3 (0, 1, 2, 3)所以 PQ , P Q .71(2) (PQ)P)Q(2) A1: PQ A2: P C: Q (PQ)P)Q (PQ)P)Q PQ M0 (0) (1, 2, 3)不是重言式，所以Q 不是 PQ 和 P 的有效结论。724 直接证法(形式演绎) A1，A2，.，An B (从前提推演出结论) 形式演绎规则: 规则P: 在推导的过程中引入已知前提公式; 规则T: 在演绎过程中可以利用前面演绎出来的中间结果推出新的命题公式。 演绎过程中

32、需要用到等值式和重言蕴含式。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 (附加

33、)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: 证明CD, (CD)H, H(AB), (AB)(RS) RS.证: (1) CD P (2) (CD)H P (3) H T (1)(2) (4) H(AB) P (5) AB T (3)(4) (6) (AB

34、)(RS) P (7) RS T (5)(6) CD, (CD)H, H(AB), (AB)(RS) RS. 75例5: 证明AB, AC, DE, DC, E B 证: (1) E P (2) DE P (3) D T (1)(2) (4) DC P (5) C T (3)(4) (6) ACP (7) A T (5)(6) (8) ABP (9) B T (7)(8)AB, AC, DE, DC, E B 76例6: 证明 P Q, PR, QS SR.证: (1) P Q P (2) PQ T (1) (3) QS P (4) PS T (2)(3) (5) SP T (4) (6) PR P (7) SR T (5)(6) (8) SR T (7) P Q, PR, QS SR 77