《第九章 命题逻辑.ppt》由会员分享，可在线阅读，更多相关《第九章 命题逻辑.ppt（88页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第九章第九章 命题逻辑命题逻辑第九章第九章 命题逻辑命题逻辑第九章1数理逻辑是计算机应用和理论研究的理论基础。本章数理逻辑是计算机应用和理论研究的理论基础。本章介绍介绍命题逻辑命题逻辑逻辑是研究思维的形式结构及其规律的科学逻辑是研究思维的形式结构及其规律的科学逻逻辑辑数理逻辑数理逻辑辨证逻辑辨证逻辑命题逻辑命题逻辑谓词逻辑谓词逻辑(用数学方法用数学方法)符号逻辑符号逻辑传统逻辑传统逻辑两种逻辑的区别只是在于它们工具语言的不同两种逻辑的区别只是在于它们工具语言的不同。2习题习题：1作业9.1命题、连接词9.1 9.1 命题和命题联结词命题和命题联结词自然语言中的句子，只有陈述句能分辨真假。自然语
2、言中的句子，只有陈述句能分辨真假。定义定义：把每个能分辨真假的陈述句称为：把每个能分辨真假的陈述句称为命题命题，命题的命题的 结果称为结果称为真值真值。如果一个命题是真的，则称它的真值为如果一个命题是真的，则称它的真值为真真，用用“1 1”表示；如果一个命题是假的，则称它的真表示；如果一个命题是假的，则称它的真 值为值为假假，用用“0 0”表示表示3习题习题：1作业 例例例：今天下雪今天下雪 光绪皇帝死的那一天，是大晴天光绪皇帝死的那一天，是大晴天 任何一个大于任何一个大于 2 2 的偶数都可以表示成两个素数的偶数都可以表示成两个素数 之和之和 上帝保佑！上帝保佑！规定规定：在数理逻辑中，命题
3、用大写字母或带下标的大：在数理逻辑中，命题用大写字母或带下标的大 写字母表示。写字母表示。天蓝蓝，海蓝蓝天蓝蓝，海蓝蓝 x xy y5 54习题习题：原子命题原子命题：若一个命题已不能分解成更简单的命题，若一个命题已不能分解成更简单的命题，则称该命题为则称该命题为原子命题原子命题 或或 原始命题原始命题命题联结词命题联结词：若干原子命题通过以下五种联结词可以若干原子命题通过以下五种联结词可以 构成新的命题，称这五种联结词为构成新的命题，称这五种联结词为命题联结词命题联结词复合命题复合命题：若干原子命题通过命题联结词构成的新的若干原子命题通过命题联结词构成的新的 命题称为命题称为复合命题复合命题
4、五种联结词是五种联结词是 “否定否定”、“合取合取 ”、“析取析取 ”、“蕴涵蕴涵”、“等值等值 ”概念5习题习题：否定否定 “”把对一个命题把对一个命题 P 的否定的命题称为的否定的命题称为否命题否命题，记为记为“P”，读成读成“非非 P”。真值表：真值表：PP 0 1 1 0 “”在自然语言中相当于在自然语言中相当于“非非”、“不不”、“没有没有”、“不成立不成立”等词等词例：例：P：“今天上午打雷了今天上午打雷了”，它的否定句可以是：，它的否定句可以是：P：今天上午没有打雷；今天上午没有打雷；P：今天上午打雷这件事不成立今天上午打雷这件事不成立定义定义：当且仅当当且仅当 P 为假时，为假
5、时，P 为真。为真。1,否定6习题习题：注注：数理逻辑中的数理逻辑中的“”，是对一个命题的严格否定。，是对一个命题的严格否定。自然语言中的否定词往往有较大的差别，使用自然语言中的否定词往往有较大的差别，使用 时要注意。时要注意。“”联结词在集合运算中相当于联结词在集合运算中相当于“补补”运算符运算符“”例例如：如：P：这些都是男同学；这些都是男同学；则则 P 应应是：是：“这些不都是男同学这些不都是男同学”；不能是：不能是：“这些都不是男同学这些都不是男同学”注7 合取合取 “”合取是关于两个命题的联结词，记为合取是关于两个命题的联结词，记为“”。合取合取“”在在自然语言中相当于自然语言中相当
6、于“并且并且”、“和和”、“以及以及”、“既既又又”、“不仅不仅而且而且”、“虽然虽然但是但是”等等 真值表：真值表：P PQ 0 0 0 0 1 0 Q0 1 0 1 1 1 习题习题：定义定义：当且仅当命题当且仅当命题 P 和和 Q 均为真时，均为真时，PQ 才为真才为真 2,合取8例例：P：张新：张新成绩很好，成绩很好，Q：张新性格很好。张新性格很好。PQ：PQ：李珊与刘菲到五楼去了。李珊与刘菲到五楼去了。P：桌子是黄色的，桌子是黄色的，Q：火星上有生命。火星上有生命。PQ：习题习题：张新不仅成绩很好而且性格很好张新不仅成绩很好而且性格很好 P：Q：李珊到五楼去了李珊到五楼去了 刘菲到五
7、楼去了。刘菲到五楼去了。桌子是黄色的并且火星上有生命桌子是黄色的并且火星上有生命 李珊与刘菲是同乡李珊与刘菲是同乡 例93.析取析取 “”析取是关于两个命题的联结词，记为析取是关于两个命题的联结词，记为“”。析取析取“”在自然语言中相当于在自然语言中相当于“或者或者”真值表：真值表：P PQ 0 0 0 1 1 1 Q0 1 0 1 1 1 习题习题：定义：当且仅当命题定义：当且仅当命题 P 和和 Q 至少有一个取值为真时，至少有一个取值为真时，P Q 便取值为真。便取值为真。3,析取10习题习题：1例例：P：这餐饭吃鱼，这餐饭吃鱼，Q：这餐饭吃白菜。这餐饭吃白菜。P Q：P Q：今晚我写字或
8、看书。今晚我写字或看书。P：Q：这餐饭吃鱼或吃白菜这餐饭吃鱼或吃白菜今晚我写字今晚我写字 今晚我看书今晚我看书 张曜在图书馆或在宿舍里。张曜在图书馆或在宿舍里。设设 P：张曜在图书馆张曜在图书馆 Q：张曜在宿舍里。张曜在宿舍里。则复合命题应为：则复合命题应为：(PQ)(PQ)例11注注：集合运算中的集合运算中的“”是是“”的特例的特例 自然语言中的自然语言中的“或者或者”的含义有两种，一种是的含义有两种，一种是 “可兼或可兼或”，一种是，一种是“不可兼或不可兼或”。而数理逻辑中定义的析取而数理逻辑中定义的析取“”的含义是的含义是“可兼或可兼或”的意思：命题的意思：命题 P 成立，或者命题成立，
9、或者命题 Q成立，或者命题成立，或者命题 P 和和 Q 都成立。都成立。不能表示不能表示“不可兼或不可兼或”的意思的意思 “不可兼或不可兼或”在命题逻辑中表示在命题逻辑中表示成成 (PQ)(PQ)习题习题：意为：意为：“要么要么要么要么”注12 蕴涵蕴涵 “”蕴涵蕴涵“”在在自然语言中相当于自然语言中相当于“如果如果必须必须”、“如果如果那么那么”、“必须必须以便以便”、“Q 对于对于 P 是必要的是必要的”、“P 对于对于 Q 是充分的是充分的”PQ 定义定义 中的中的 P 称为蕴涵式的称为蕴涵式的前件前件，Q 称为蕴涵式称为蕴涵式的的后件后件。习题习题：蕴涵的真值表：蕴涵的真值表：P PQ
10、 0 0 1 1 1 0 Q0 1 0 1 1 1 4,蕴涵13例例：如果你走路时看书，那么你一定会成为近视眼如果你走路时看书，那么你一定会成为近视眼 PQ：“如果我放了假，我就到桂林去”；习题习题：解：设：解：设：P：你走路；你走路；Q：你看书；你看书；R：你会成为近视眼你会成为近视眼 则复合命题为：则复合命题为：(PQ)R解：解：P：我放了假，我放了假，Q：我到桂林去我到桂林去 例14注注：蕴涵的真假值表的特点是，只有当后件为蕴涵的真假值表的特点是，只有当后件为“假假”，前件为前件为“真真”时，蕴涵式的值才为时，蕴涵式的值才为“假假”，其他，其他情况情况 蕴涵式的值均为蕴涵式的值均为“真真
11、”蕴涵实质上就是通常的“必要条件”的一种抽象讨论讨论：蕴涵的真假值表中不大好理解的是，当后件为：蕴涵的真假值表中不大好理解的是，当后件为 “真真”时，无论前件为真为假，时，无论前件为真为假，蕴涵式的值都为蕴涵式的值都为“真真”其实，这样的定义方式也反映了客观实际，它并其实，这样的定义方式也反映了客观实际，它并不违背我们的逻辑思维常识。不违背我们的逻辑思维常识。看看前面的看看前面的例例习题习题：注15等值等值 “”等值等值“”在在自然语言中相当于自然语言中相当于“当且仅当当且仅当”、“相当于相当于”、“和和一样一样”、“等价于等价于”、“P 是是 Q 的充要条件的充要条件”习题习题：P PQ 0
12、 0 1 0 1 0 Q0 1 0 1 1 1 等值的真值表：等值的真值表：5,等值16例例：除非他以书面或口头的方式正式通知我，否则除非他以书面或口头的方式正式通知我，否则 我不参加明天的会议。我不参加明天的会议。PQ：“仅当你去我将留下仅当你去我将留下”；P：Q：习题习题：解解：设：设 P：他：他书面通知我；书面通知我；Q：他口头通知我；他口头通知我；R：我参加明天的会议我参加明天的会议则复合命题表示为：则复合命题表示为：(PQ)R我留下我留下 你去你去 例17如何把一个句子符号化如何把一个句子符号化步骤步骤：分析出句子中的原子命题，将它符号化；：分析出句子中的原子命题，将它符号化；使用合
13、适的联结词把原子命题联结起来，组成使用合适的联结词把原子命题联结起来，组成 复合命题的符号化表示。复合命题的符号化表示。注意注意：自然语言中的联结词与命题联结词的含义不是：自然语言中的联结词与命题联结词的含义不是 完全对应的，需要具体分析。完全对应的，需要具体分析。习题习题：1、2、3 句子符号化18例例：小李虽聪明，但不用功小李虽聪明，但不用功解解：令：令 P：小李聪明，小李聪明，Q：小李用功小李用功 若不是他生病或出差了，我是不会同意他不若不是他生病或出差了，我是不会同意他不 参加学习。参加学习。解解:令令 P：他生病了，他生病了，Q：他出差了，他出差了，R：我同意他不参加学习我同意他不参
14、加学习习题习题：1、2、3命题表示为：命题表示为：PQ命题表示为：命题表示为：(PQ)R 或者或者 (PQ)R 例19 小张现在在图书馆或在宿舍里小张现在在图书馆或在宿舍里解解：令：令 P：小张在图书馆，小张在图书馆，Q：小张在宿舍小张在宿舍 命题表示为：命题表示为：习题习题：他写了他写了 30 行或行或 50 行字行字解解：这里的：这里的“或或”可以有两种不同的理解：可以有两种不同的理解：(PQ)(PQ)一是，一是，“不可兼得的或不可兼得的或”，如上题，如上题写写成一成一复合命题；复合命题；二是，可作二是，可作“或许或许”，“大概大概”理解，就理解，就是一个原子是一个原子命题。命题。例20习
15、题习题：1、2、3 赵常与钱深是好学生赵常与钱深是好学生解解：令：令 P：赵常是好学生，赵常是好学生，Q：钱深是好学生钱深是好学生 赵常与钱深是好朋友赵常与钱深是好朋友解解：这：这是一个原子命题。是一个原子命题。命题表示为：命题表示为：PQ 例21判断下列语句哪些是命题判断下列语句哪些是命题 我正在说谎。我正在说谎。练习 3x 3x5858 圆的面积等于半径的立方乘以圆的面积等于半径的立方乘以 。2 2 或是质数或是合数。或是质数或是合数。你学过了法语，真好！你学过了法语，真好！公元前公元前 194 194 年发生过十天日食。年发生过十天日食。如果你下午不开会就到我这里来，好吗？如果你下午不开
16、会就到我这里来，好吗？22命题符号化练习命题符号化练习 练习 2 23 35 5 当且仅当当且仅当 是无理数是无理数 如果你来了，那么他唱不唱歌将看你是否伴奏而定如果你来了，那么他唱不唱歌将看你是否伴奏而定 生命不息战斗不止生命不息战斗不止 张颖是张颖是 18 18 岁，或是岁，或是 19 19 岁岁 李珊学过德语或法语李珊学过德语或法语 赵玲与陈实在讨论问题赵玲与陈实在讨论问题 莫伸手，伸手必被捉。莫伸手，伸手必被捉。小代和小李是俩夫妻，他们都很贪婪小代和小李是俩夫妻，他们都很贪婪239.2 命题公式命题公式命题常元命题常元：若一个表示命题的符号具有确定的真值若一个表示命题的符号具有确定的真
17、值 (1 或或 0)，则称它为，则称它为命题常元命题常元习题习题：4命题变元命题变元：一个任意的，真值不确定的命题我们称一个任意的，真值不确定的命题我们称 它为它为命题变元命题变元，仍用大写字母表示，仍用大写字母表示一、一、几个概念几个概念9.2命题公式 一，概念24 0、1是命题公式是命题公式习题习题：4定义定义 9-6：关于：关于命题公式命题公式(或简称或简称公式公式)的定义的定义 命题变元是命题公式命题变元是命题公式 如果如果 A 是命题公式，则是命题公式，则 P 是命题公式是命题公式 如果如果 A 和和 B 是命题公式，则是命题公式，则(AB)、(AB)、(AB)、(AB)也是命题公式
18、也是命题公式 只有有限次地利用上述只有有限次地利用上述、产生的产生的 符号串才是命题公式符号串才是命题公式 定义25例例：看看下面的符号串哪些是公式：看看下面的符号串哪些是公式：(AB)(PQ)习题习题：4作业(AB)P Q注注：命题公式不一定是命题，若公式中有命题变元时，：命题公式不一定是命题，若公式中有命题变元时，只有每一个命题变元都被赋以确定的真值时，公只有每一个命题变元都被赋以确定的真值时，公 式的真值才被确定，成为一个命题式的真值才被确定，成为一个命题(AB)R)(PQ)BQ 10P QP 例26真值指派真值指派：为一个公式的所有变元取一组确定的真值，为一个公式的所有变元取一组确定的
19、真值，称为该公式关于各变元的一组称为该公式关于各变元的一组真值指派真值指派习题习题：4作业例例：(PQ)(QS)公式的各组真值指派就是其中公式的各组真值指派就是其中3个变元在真值表最个变元在真值表最左边列出的左边列出的8组值组值 真值指派27重言式重言式：若一个公式对于它的所有命题变元的任何一若一个公式对于它的所有命题变元的任何一 组真值指派，取值恒为真，则称该公式为组真值指派，取值恒为真，则称该公式为重言式重言式 或或永真公式永真公式，常用常用“1”表示表示习题习题：5、6作业二、公式的类型二、公式的类型例例：命题公式：命题公式 F1(PQ)(PQ)的真值表如下：的真值表如下：P0 0 1
20、Q0 1 0 1 1 PQ 1 1 0 1 P1 1 0 0 PQ1 1 0 1(PQ)(PQ)1 1 1 1 二,公式的类型28习题习题：5、6作业矛盾式矛盾式：若一个公式对于它的所有命题变元的任何一：若一个公式对于它的所有命题变元的任何一 组真值指派，取值恒为假，则称该公式为组真值指派，取值恒为假，则称该公式为矛盾式矛盾式 或或永假公式永假公式，常用常用“0”表示表示可满足公式可满足公式：若一个公式至少有一组真值指派使公式若一个公式至少有一组真值指派使公式 的值为真，则称该公式为的值为真，则称该公式为可满足公式可满足公式例例：(PQ)(QS)P0 0 0 Q0 0 1 0 1 PQ QQS
21、(PQ)(QS)S0 1 0 1 1 0 1 1 0 0 1 0 1 1 1 1 1 1 0 1 1 0 0 0 0 1 1 1 0 1 0 1 0 1 0 1 1 0 1 1 0 1 0 0 0 1 0 1 299.3 命题公式的等值关系和蕴涵关系命题公式的等值关系和蕴涵关系 就像代数式之间有等式和不等式一样，命题公式之就像代数式之间有等式和不等式一样，命题公式之间也常有一些关系，最基本的关系是等值关系和蕴涵间也常有一些关系，最基本的关系是等值关系和蕴涵关系关系习题习题：4作业 等值关系实质上是表示两个公式之间的一种关等值关系实质上是表示两个公式之间的一种关 系，系，“”是一个表示关系的符号
22、。是一个表示关系的符号。公式等值公式等值：设设 A和和B是两个命题公式，当且仅当是两个命题公式，当且仅当A和和B 的真值表完全相同时，称的真值表完全相同时，称 A 和和 B 是是等值等值公式公式 记为记为 A B 注注：公式等值的另一种定义是：公式等值的另一种定义是：若若 AB 为重言式，则称为重言式，则称 A和和B是是等值公式等值公式9.3命题公式的关系 等值30基本等值关系：下面列出基本等值关系：下面列出 26 个重要的等值关系，它们可以像集个重要的等值关系，它们可以像集 合恒等式一样用于推导其它等值关系合恒等式一样用于推导其它等值关系E1：PQ QP E1：PQ QP E2：(PQ)R
23、P(QR)E2：(PQ)R P(QR)E3：P(QR)(PQ)(PR)E3：P(QR)(PQ)(PR)E4：P1 P E1：P0 PE5：P P 1 E5：PP 0 E6、E6：(P)P E8：P 0 0 E8：P 1 1 交换交换律律 结合结合律律 分配分配律律 同一同一律律 零一零一律律 互否互否律律 双重否定双重否定律律 E7：P P P E7：P P P 等幂等幂律律 E9：P(PQ)P E9：P(PQ)P吸收吸收律律 E10：(PQ)PQE10：(PQ)PQ德摩根定律德摩根定律基本等值关系习题习题：31 E11：P Q P Q E12：P Q(P Q)(P Q)E13：P(Q R)(
24、P Q)R E14：P Q(P Q)(Q P)E16：P Q Q P E17：(P Q)P Q E15：(P Q)P Q32说明说明：这这 26 个等值关系中，前个等值关系中，前 19 个与集合恒等式的基本公式个与集合恒等式的基本公式(参见书参见书 p16)非常相似非常相似 这里的这里的“”相当于集合运算符相当于集合运算符“”这里的这里的“”相当于集合运算符相当于集合运算符“”这里的这里的“”相当于集合运算符相当于集合运算符“”这这 26 个等值关系中，后个等值关系中，后 7 个关系表明，所有命题公式个关系表明，所有命题公式 都能用都能用 “”、“”、“”表示表示 这这 26 个等值关系的证明
25、都可以用真值表进行，个等值关系的证明都可以用真值表进行，这是最基本的证明方法。这是最基本的证明方法。习题习题：说明33解解：列真值表：列真值表PP Q 0 0 1 1 1 0 Q0 1 0 1 1 1 PP Q 0 0 1 1 1 0 Q0 1 0 1 1 1 P1 1 0 0 习题习题：例例 1：证明等值关系：证明等值关系：P Q P Q 从真值表可看出从真值表可看出 P Q P Q 成立成立 例34解解：列真值表：列真值表PP Q 0 0 1 0 1 0 Q0 1 0 1 1 1 P P Q 0 0 0 0 1 0 Q0 1 0 1 1 1 P1 1 0 0 Q1 0 1 0 P Q 1
26、0 0 0(P Q)(P Q)1 0 0 1 习题习题：例例 2：证明等值关系：证明等值关系：P Q(P Q)(P Q)从真值表可看出从真值表可看出 P Q(P Q)(P Q)例35 在代数中对公式进行推导时，可以使用变量代换在代数中对公式进行推导时，可以使用变量代换和公式代换。在这里，等值关系的推导中也有同样的和公式代换。在这里，等值关系的推导中也有同样的代换规则。代换规则。代换实例代换实例：设设 A 是一个命题公式，是一个命题公式，P1，P2，Pn 是是 其中出现的所有命题变元。其中出现的所有命题变元。用某些表达式代换 A 中的某些命题变元；若用表达式 Qi 代换 Pi 则必须用 Qi 代
27、换 A 中所有的 Pi。那么，由此得到的新命题公式那么，由此得到的新命题公式 B 叫做表达式叫做表达式 A 的的一个一个代换实例代换实例习题习题：5作业 代换实例36例例 1：对于表达式：对于表达式 A=P(RP)中，用中，用 QS 代换其中的代换其中的 P，得到表达式得到表达式 B=(QS)(R(QS)则表达式则表达式 B 就是就是 A 的一个代换实例的一个代换实例注注：用表达式：用表达式 QS 代换表达式代换表达式 A 中的中的 P 时，必须把时，必须把 A 中的所中的所有有 P 都都代换掉，不能漏掉一个。代换掉，不能漏掉一个。例例 2：对于表达式：对于表达式 A=PQ，先用先用 QS 代
28、换其中的代换其中的 P，得到表得到表 达式达式 B1=(QS)Q；再用再用 R 代换其中的代换其中的 Q，得到表达式得到表达式 B2=(RS)R，则则 B2 就不是就不是 A 的代换实例的代换实例注注：若用多个表达式对多个变元进行代换，则代换必须同时进行：若用多个表达式对多个变元进行代换，则代换必须同时进行习题习题：5作业 例37定理定理 9-2：(代入规则代入规则)重言式的任一代换实例仍然是重言式重言式的任一代换实例仍然是重言式解释解释：这个定理的意义在于，前面的：这个定理的意义在于，前面的 26 个等值关系中的变元个等值关系中的变元 P、Q、R 不仅可以是任何命题变元，而且它们被换成命不仅
29、可以是任何命题变元，而且它们被换成命 题公式时，这些等值关系也是成立的。题公式时，这些等值关系也是成立的。这相当于代数式中的任何一个变量可以全部换成另一个这相当于代数式中的任何一个变量可以全部换成另一个 变量，也可换成另一个表达式变量，也可换成另一个表达式习题习题：7作业例例：分配：分配律律 E3：P(QR)(PQ)(PR)用表达式用表达式 XY 代换其中的变量代换其中的变量 Q 得：得：P(XY)R)(P(XY)(P R)代入规则 例38(PQ)、RP、Q(RP)都是都是 A 的子表达式的子表达式子公式子公式：如果如果 C 是表达式是表达式 A 的一个符号子串，而的一个符号子串，而 C 本身
30、也本身也 是一个表达式，则称是一个表达式，则称 C 为为 A 的的子公式子公式(子表达式子表达式)例例 1：表达式：表达式 A=(PQ)(Q(RP)中，中，(PQ)、(RP)、Q 都不是都不是 A 的子表达式的子表达式习题习题：7作业 子公式 例39定理定理 9-3：(置换规则置换规则)表达式表达式 A 的任何一个子表达式的任何一个子表达式 C，可以可以用用 C 的等值表达式的等值表达式 D 置换，所得的新的表达式仍与原表达式置换，所得的新的表达式仍与原表达式 A 等值等值解释解释：定理定理9-3 就像代数中的表达式一样，可以把其中的任何一个子就像代数中的表达式一样，可以把其中的任何一个子 表
31、达式换成另一个与它等值的表达式，保持原表达式值不变。表达式换成另一个与它等值的表达式，保持原表达式值不变。在命题公式中，也可把其中的任何一个子表达式换成另一个在命题公式中，也可把其中的任何一个子表达式换成另一个 等值的表达式。等值的表达式。有了代入规则和置换规则，我们就可以像代数中的恒等变换有了代入规则和置换规则，我们就可以像代数中的恒等变换 一样，利用已知的等值关系式推导出其它一些更复杂的等值一样，利用已知的等值关系式推导出其它一些更复杂的等值 关系式。关系式。习题习题：7作业 置换规则40习题习题：7作业 原原等值等值关系关系式成立式成立例例 1 证明：证明：(P(Q S)(P(Q S)Q
32、 S 证证：(P(QS)(P(QS)(PP)(QS)(分配律分配律)1(QS)(互否律互否律)QS (零一律零一律)例41习题习题：7作业证证：一般，把：一般，把“蕴涵蕴涵”转换为转换为“非非”、“且且”、“或或”原原等值等值关系式关系式成立成立(公式公式 E11)例例 3 证明：证明：P(Q R)(PQ)R左边为 P(QR)P(QR)P(QR)PQR(PQ)R(PQ)R (摩根定律摩根定律)(PQ)R 例42习题习题：7作业 原原等值等值关系关系式成立式成立例例 4 证明：证明：PQ(PQ)(QP)证证：右边为右边为 (PQ)(QP)(PQ)(QP)(P(QP)(Q(QP)(PQ)(PP)(
33、QQ)(QP)(PQ)(QP)左边为左边为 PQ(PQ)(QP)例43习题习题：7作业例例 5 证明：证明：Q(PQ)P)是一个重言式是一个重言式 原式原式是一个重言式是一个重言式证证：Q(PQ)P)Q(PP)(QP)Q(0(QP)Q(QP)QQP 1 例44 集合中的被包含关系与这里的蕴涵关系完全相似，可以对集合中的被包含关系与这里的蕴涵关系完全相似，可以对 照着理解和记忆照着理解和记忆“”是是命题联结词，命题联结词，AB 是是一个公式，表示一个命题一个公式，表示一个命题 蕴涵关系是一个偏序关系，满足自反性、反对称性、可蕴涵关系是一个偏序关系，满足自反性、反对称性、可 传递性传递性(为以下定
34、理为以下定理4、定理、定理5支持支持)：习题习题：公式蕴涵公式蕴涵：设设 A 和和 B 是是两个命题公式，若表达式两个命题公式，若表达式 AB 是重言式，是重言式，即即 (AB)1，则称公式，则称公式 A 蕴涵蕴涵 B，记为记为 AB注注：注意注意“”和和“”是两个完全不同的符号。是两个完全不同的符号。“”不是联结词，而只是一个表示关系的符号，不是联结词，而只是一个表示关系的符号，AB 不是公式，不代不是公式，不代 表任何命题表任何命题对任意公式对任意公式 A，有有 AA对任意公式对任意公式 A、B，若若 AB，BA，则必有，则必有 A B 对任意公式对任意公式 A、B、C，若若 AB，BC，
35、则则 AC 公式蕴涵45反之亦然反之亦然习题习题：定理定理 9-4：设设 A、B 为两个命题公式，为两个命题公式，AB 的的 充要条件是，充要条件是，AB 且且 BA 证证：设：设 AB，则则 AB 是是重言式，即重言式，即 AB 1而而 A B(AB)(BA)(AB)(BA)1，则，则 AB 1 且且 BA 1 按蕴涵关系的定义，有按蕴涵关系的定义，有 AB 且且 BA 定理446习题习题：定理定理 9-5：设：设 A、B、C 是公式，是公式，若若 AB，BC，则则 AC证证：由：由 AB 和和BC 得得 AB 和和 BC 都是重言式都是重言式而 AB AB，BC BC AB 1，BC 1
36、AC(AC)0(AC)(BB)(ACB)(ACB)即 AC 1 AC成立(A1)(1C)111 定理547蕴涵关系：下面列出几蕴涵关系：下面列出几 个重要的蕴涵关系，它们可以个重要的蕴涵关系，它们可以 按照定义直接证明按照定义直接证明习题习题：PQ P PQ Q P PQ Q PQP PQ Q PQ 蕴涵关系48证明蕴涵关系的方法证明蕴涵关系的方法根据蕴涵关系的定义证。把蕴涵关系相应的蕴涵式根据蕴涵关系的定义证。把蕴涵关系相应的蕴涵式 PQ的等值式的等值式 PQ 变换成变换成 1 即可。即可。列出蕴涵关系左右公式的真值表，用真值表比较列出蕴涵关系左右公式的真值表，用真值表比较习题习题：根据蕴涵
37、联结词的定义证。蕴涵关系相应的蕴涵式根据蕴涵联结词的定义证。蕴涵关系相应的蕴涵式 PQ的的前前件件 P 为真时，证明后件为真时，证明后件 Q 必为真，则必为真，则 PQ 1，于是就有了，于是就有了 PQ，否则该蕴涵关系不成立否则该蕴涵关系不成立 根据蕴涵联结词的定义证。蕴涵关系相应的蕴涵式根据蕴涵联结词的定义证。蕴涵关系相应的蕴涵式 PQ的后件的后件 Q 为假时，证明前件为假时，证明前件 P 必为假，则必为假，则 PQ 1，于是就有了，于是就有了 PQ，否则该蕴涵关系不，否则该蕴涵关系不 成立成立 证明蕴涵关系49 原蕴涵关系成立习题习题：例 1 证明：(PQ)(QR)PR证：设 X (PQ)
38、(QR)(PR)(取蕴涵关系的蕴涵式)(PQ)(QR)(PR)X (PQ)(QR)(PR)(取蕴涵式的等值式)(PQ)(QR)PR (德摩根定律)(PQ)P(QR)R (交换律)QPQR(QQ)PR 1PR (互否律)1 例50 则必有 P 为真，且(PQ)为真 (根据合取的真值表)原蕴涵关系成立 (蕴涵关系的定义)由 P 为真，得 P 为假，证：假设前件 P(P Q)为真，由 P 为假，再由 PQ 为真，得后件 Q 必为真 (析取的真值表)(P(PQ)Q 是个重言式 (蕴涵的真值表)习题习题：例 2 证明：P(PQ)Q 例51若 P 为真，则 P 为假，则 P(PQ)为假 (合取的真值表)前
39、件 P(P Q)必然为假若 P 为假，由 Q 为假，则得 PQ 为假，仍有 P(PQ)为假 原蕴涵关系成立 (蕴涵关系的定义)证：假设后件 Q 为假，(P(P Q)Q 是个重言式 (蕴涵的真值表)例 2 证明：P(P Q)Q习题习题：例52 原蕴涵关系成立 (蕴涵关系的定义)习题习题：例 3 证明：Q(P Q)P 证 ：设 X(Q(P Q)P (取蕴涵关系的蕴涵式)X (Q(P Q)P (取蕴涵式的等值式)(Q P)(Q Q)P (分配律)(Q P)0)P (互否律)(Q P)P (同一律)1 QPP Q1 (德摩根定律)例53证：假设前件 Q(P Q)为真，则必有 Q 为真，且(P Q)为真
40、 (根据合取的真值表)原蕴涵关系成立 (蕴涵关系的定义)由 Q 为真，得 Q 为假由 Q 为假，再由 P Q 为真，又得 P 必为假 (根据蕴涵的真值表)后件 P 必为真 (Q(P Q)P 是个重言式 (根据蕴涵的真值表)习题习题：例 3 证明：Q(P Q)P 例54 若 Q 为假，则 Q(P Q)为假 (根据合取的真值表)前件 Q(P Q)总是为假 若 Q 为真，则 Q 为假 原蕴涵关系成立 (蕴涵关系的定义)证：假设后件 P 为假，则 P 为真 由 Q 为假，加上 P 为真，则得 P Q 为假 (根据蕴涵的真值表)(Q(P Q)P 是个重言式 (根据蕴涵的真值表)仍有 Q(P Q)为假习题
41、习题：例55习题习题：例 4 设 A、B、C 是公式，若 A B 且 A C，证明：A (B C)A(B C)成立 (蕴涵关系的定义)证：设 X A(B C)(取蕴涵关系的蕴涵式)X A(B C)(取蕴涵式的等值式)(AB)(AC)(A B)(A C)(蕴涵的定义)代入(A B)(A C)得 1 A(B C)1 由 A B 且 A C 得 A B 1 且 A C 1 例56 B 是重言式习题习题：例 5 设 A、B 是公式，若 A B 且 A 是重言式，则 B 一定也是重言式 证：A B 1 A B (蕴涵关系的定义)AB A 是重言式 A 0 上式为：1 0 B B 例57对偶对偶：在公式在
42、公式 A 中，若把所有联结词中，若把所有联结词 代换成代换成 ，把，把 代换代换 成成，把，把 0 代换成代换成 1，把，把1 代换成代换成 0，则所得的公式称为，则所得的公式称为 A 的的对偶对偶，记作，记作 AD 公式中的所有联结词公式中的所有联结词 和和 都可以置换成都可以置换成、，所以，所以，在公式推导中总是把公式变成只包含在公式推导中总是把公式变成只包含、这三种这三种联结词的联结词的形式。形式。定理定理 8：设设 A、AD 是是两个互为对偶的公式，两个互为对偶的公式，P1，P2，Pn 是是 其命题变元，则其命题变元，则习题习题：A(P1，P2，Pn)AD(P1，P2，Pn)对偶、定理
43、858习题习题：定理定理 9(对偶原理对偶原理)：设设 A(P1，P2，Pn)和和 B(P1，P2，Pn)是两个是两个 公式，若公式，若 A B，则则 AD BD 定理9599.5 命题演算的推理理论命题演算的推理理论 逻辑推理就是由已知命题得到新命题的思维过程逻辑推理就是由已知命题得到新命题的思维过程推理前提(命题)结论(命题)一般地，前提可以是若干个命题的“且”习题习题：定义定义：设 A、B 是两个命题公式，若 A B(即 A B 是重言式)，则称 B 是前提前提 A 的结论结论，或 从从 A 推出结论推出结论 B。设 H1，H2，Hn 和 C 是一些命题公式，若 H1H2Hn C 则称
44、从前提从前提 H1，H2，Hn 推出结论推出结论 C，也可记为 H1，H2，Hn C 并称 H1，H2，Hn为 C 的前提集合前提集合注：从一组前提是否可以推出某个结论的实质就是证明下述 蕴涵关系是否成立 H1H2Hn C9.5推理理论60分析分析：前面：前面已经讲了证明蕴涵关系处理的四种方法：已经讲了证明蕴涵关系处理的四种方法：列出蕴涵关系的蕴涵式，通过等值变换把该蕴涵列出蕴涵关系的蕴涵式，通过等值变换把该蕴涵 式变换成式变换成 1 即可。即可。设蕴涵式的设蕴涵式的前前件为真，证明后件必为真件为真，证明后件必为真 设蕴涵式的后件为假，证明前件必为假设蕴涵式的后件为假，证明前件必为假 列出蕴涵
45、关系左右公式的真值表，用真值表比较列出蕴涵关系左右公式的真值表，用真值表比较这四种方法都可以用于证明前提由多个命题变元这四种方法都可以用于证明前提由多个命题变元组成的蕴涵关系。组成的蕴涵关系。习题习题：分析61习题习题：第第 3 种方法在前提由多个命题变元组成时，要设所种方法在前提由多个命题变元组成时，要设所有前提为真，由此推出结论为真，即可。这就是一般有前提为真，由此推出结论为真，即可。这就是一般的的“直接证明法直接证明法”。显然，前两种方法受蕴涵关系的规模的限制，在前显然，前两种方法受蕴涵关系的规模的限制，在前提和结论都是比较复杂的命题公式或者包含的命题变提和结论都是比较复杂的命题公式或者
46、包含的命题变元很多时，这两种方法就很困难了。元很多时，这两种方法就很困难了。第第 4 种方法在前提由多个命题变元组成时，要设结种方法在前提由多个命题变元组成时，要设结论为假，由此推出前提中有一个为假，即可。这就是论为假，由此推出前提中有一个为假，即可。这就是我们很熟悉的我们很熟悉的“反证法反证法”，也叫也叫“间接证明法间接证明法”。分析62形式证明形式证明：一个描述推理过程的命题序列，其中每个命题或者是一个描述推理过程的命题序列，其中每个命题或者是 已知命题，或者是由某些前提推得的结论，序列中最后一个已知命题，或者是由某些前提推得的结论，序列中最后一个 命题就是所要求的结论，这样的命题序列称为
47、命题就是所要求的结论，这样的命题序列称为形式证明形式证明。推理规则推理规则：前提引入规则前提引入规则：在证明的任何步骤上都可以引入前提在证明的任何步骤上都可以引入前提 结论引用规则结论引用规则：在证明的任何步骤上所得到的结论都可在证明的任何步骤上所得到的结论都可 以在其后的证明中引用以在其后的证明中引用 置换规则置换规则：在证明的任何步骤，命题公式的子公式都可在证明的任何步骤，命题公式的子公式都可 以用与它等值的其它命题公式置换以用与它等值的其它命题公式置换 代入规则代入规则：在证明的任何步骤，重言式的任一命题变元在证明的任何步骤，重言式的任一命题变元 都可用一命题公式代入，得到的仍是重言式。
48、都可用一命题公式代入，得到的仍是重言式。习题习题：构造一个逻辑结构严谨的形式证明，需要以下推理规则的支持构造一个逻辑结构严谨的形式证明，需要以下推理规则的支持 形式证明63例例 1：有前提：有前提 H1，H2，和，和结论结论 C，判断推理能否成立：判断推理能否成立：H1：P Q ，H2：P ，C：Q H1：P Q ，H2：Q ，C：P 列真值表如下：列真值表如下：P(PQ)P0 0 0 0 1 0 Q0 1 0 1 1 1 P1 1 0 1 Q(P Q)Q0 1 0 1 习题习题：例(P Q)P)Q1 1 1 1(PQ)Q)P1 0 1 1 64例 1：有前提 H1，H2，和结论 C，判断推理
49、能否成立：H1：P Q ，H2：P ，C：Q H1：P Q ，H2：Q ，C：P 显然，第 小题中，从 H1，H2 能够推出 C；第 小题中，不能从 H1，H2 推出 C 把具体命题代入上例中的命题变元 P，Q，则更容易理解 P Q ：如果今天出太阳，他就进城 P ：今天出了太阳Q ：他进城了 P Q ：如果狗有翅膀，则狗会飞上天 P ：狗有了翅膀Q ：狗飞上了天 P Q ：如果 n 是素数，则 n 一定是整数Q ：n 是整数P ：n 是素数习题习题：例65例 2：证明 C：P 是前提 H1：P Q 和 H2：(P Q)的结论 C 是前提 H1 和 H2 的结论习题习题：(P Q)(P Q)P
50、 (PQ)(PQ)P (P(Q Q)P (P 0)P P P P P 1证 (H1 H2)C (P Q)(P Q)P 例266 用直接证明法用直接证明法，我们设每一个前提的真值为真，我们设每一个前提的真值为真，能推导出，能推导出结论的真值也为真，则原推理正确，否则不正确。结论的真值也为真，则原推理正确，否则不正确。例 3：证明 P 是前提(P Q)，QR，R 的结论 P 是前提(PQ)，QR，R 的结论习题习题：证 设 R为真 (前提3为真)得 R 为假 将 R为假代入得：Q为真 继得 Q 为假 设(PQ)为真 (前提1为真)得 PQ 为真 将 Q 为假代入得：P为真(结论为真)设 QR 为真