第一章命题逻辑

1、离散数学离散数学教材：教材：左孝凌等编著离散数学 上海科学技术文献出版社 习题集：习题集：离散数学 理论分析题解 上海科学技术文献出版社 联系方式联系方式 冯志慧冯志慧 E-Mail ： QQ：541161983考考 试试 卷面卷面 占占 70% 平时平时 占占 30%第第 一一 章章命题逻辑命题逻辑 数据逻辑最早传入中国是数据逻辑最早传入中国是在在19201920年。当时，作为数理逻年。当时，作为数理逻辑奠基人之一的罗素在北京大辑奠基人之一的罗素在北京大学作了五大讲演。在数理逻辑学作了五大讲演。在数理逻辑的讲题下，介绍了他创建的命的讲题下，介绍了他创建的命题演算和类演算。题演算和类演算。 摘

2、自摘自 宋文坚宋文坚“中国数理逻辑八十年中国数理逻辑八十年”伯特兰罗素是二十世纪英国哲学家、数学家、逻辑学家、历史学家，无神论或者不可知论者，也是上世纪西方最著名、影响最大的学者和和平主义社会活动家之一，1950年诺贝尔文学奖得主， 罗素悖论：罗素悖论： 把所有集合分为把所有集合分为2类，第一类中的集合以其自身为元素，第类，第一类中的集合以其自身为元素，第二类中的集合不以自身为元素，假令第一类集合所组成的集合为二类中的集合不以自身为元素，假令第一类集合所组成的集合为P，第二类所组成的集合为，第二类所组成的集合为Q，于是有：，于是有： P=A AA Q=A A A 问，问，QP 还是还是 QQ？

3、 若若QP，那么根据第一类集合的定义，必有，那么根据第一类集合的定义，必有QQ，但是，但是Q中任何集合都有中任何集合都有A A的性质，因为的性质，因为QQ，所以，所以QQ，引出矛，引出矛盾。盾。 若若QQ，根据第一类集合的定义，必有，根据第一类集合的定义，必有QP，而显然，而显然PQ= ，所以，所以Q Q，还是矛盾。，还是矛盾。 这就是著名的这就是著名的“罗素悖论罗素悖论”。罗素悖论还有一些较为通俗。罗素悖论还有一些较为通俗的版本，如的版本，如理发师悖论理发师悖论等。等。 逻辑学逻辑学: : 研究人的思维形式和规律的科研究人的思维形式和规律的科学由于研究的对象和方法各有侧重而又分为形学由于研究

4、的对象和方法各有侧重而又分为形式逻辑、辩证逻辑和数理逻辑式逻辑、辩证逻辑和数理逻辑 数理逻辑是用数理逻辑是用数学方法来研究来研究推理的形式结构和和推理规律的数学学科。这里所指的数学方的数学学科。这里所指的数学方法就是引进一套法就是引进一套符号体系的方法。所以数理逻辑的方法。所以数理逻辑又称又称符号逻辑，它是从量的侧面来研究思维规律，它是从量的侧面来研究思维规律的。的。 现代数理逻辑可分为逻辑演算、证明论、现代数理逻辑可分为逻辑演算、证明论、公理集合论、递归论和模型论。公理集合论、递归论和模型论。 研究思维的逻辑结构和推理，人们关心的研究思维的逻辑结构和推理，人们关心的问题是前提和结论之间是否存

5、在一种逻辑推理问题是前提和结论之间是否存在一种逻辑推理关系？如果前提和结论之间存在这样一种逻辑关系？如果前提和结论之间存在这样一种逻辑推理关系，那么，具体按照什么方法，在前提推理关系，那么，具体按照什么方法，在前提为真的情况下，可以推出结论为真？为真的情况下，可以推出结论为真？ 下面举二个例子来说明这一点。下面举二个例子来说明这一点。例例1 1 考虑一元二次方程考虑一元二次方程 ax ax2 2+bx+c=0+bx+c=0我们知道：如果我们知道：如果b b2 2-4ac0-4ac0，则方程有实数解。，则方程有实数解。显然，显然，b b2 2-4ac0-4ac0是是前提前提，方程有实数解是，方程

6、有实数解是结论结论抽象来看：当抽象来看：当前提前提为为真真时，可以推出时，可以推出结论结论为为真真。例例2 2 考虑来人是华佗，他能治疗关羽的箭伤这考虑来人是华佗，他能治疗关羽的箭伤这样一个历史事件。样一个历史事件。 显然，来人如果是华佗为显然，来人如果是华佗为前提前提，他（，他（= =来来人）能治疗关羽的箭伤是人）能治疗关羽的箭伤是结论结论。抽象来看：当抽象来看：当前提前提为为真真时，可以推出时，可以推出结论结论为为真真 上述两个看似不相关的实例说明了一个共上述两个看似不相关的实例说明了一个共同的问题：同的问题：推理问题推理问题，这就是我们要研究的。，这就是我们要研究的。 抽象成数理逻辑语言

7、表达方式：抽象成数理逻辑语言表达方式： 如果如果A A 蕴涵蕴涵 B B，现又有，现又有A A，则可以推导出，则可以推导出B B。 1.1 命题及其表示法命题及其表示法 1.2 联结词联结词 1.5 重言式与蕴含式重言式与蕴含式 1.4 真值表与等价公式真值表与等价公式第一章第一章 命题逻辑命题逻辑 1.3 命题公式与翻译命题公式与翻译 1.6 其他联结词其他联结词 1.7 对偶与范式对偶与范式 1.8 推理理论推理理论1 1、教学内容：、教学内容： 命题及表示、联结词、命题公式与翻译、真值命题及表示、联结词、命题公式与翻译、真值表与等价公式、重言式与蕴涵式、其他联结词、对表与等价公式、重言式

8、与蕴涵式、其他联结词、对偶与范式、推理理论。偶与范式、推理理论。2 2、教学目的及要求：、教学目的及要求： 深刻理解和掌握命题逻辑中的基本概念和基本深刻理解和掌握命题逻辑中的基本概念和基本方法。方法。3 3、教学重点：、教学重点： 命题逻辑中的基本概念和基本推理方法。命题逻辑中的基本概念和基本推理方法。4 4、教学难点：、教学难点： 推理理论。推理理论。 推理是从前提推出结论推理是从前提推出结论。在各门具体科学的研究活动和人类日。在各门具体科学的研究活动和人类日常生活实践中，都离不开推理。推理中的前提和结论都是命题，都常生活实践中，都离不开推理。推理中的前提和结论都是命题，都有具体的涵义。从怎

9、样的前提出发，能推出怎样的结论，这是各门有具体的涵义。从怎样的前提出发，能推出怎样的结论，这是各门具体科学自己要研究的问题。具体科学自己要研究的问题。数理逻辑研究推理时，一般并不涉及数理逻辑研究推理时，一般并不涉及前提和结论的具体内容，而是研究前提和结论之间的关系，以及这前提和结论的具体内容，而是研究前提和结论之间的关系，以及这种关系的合理性。种关系的合理性。这里所述的前提和结论之间的关系包括形式推理这里所述的前提和结论之间的关系包括形式推理关系和逻辑推理关系两种，它们分别属于形式语言语法和语义研究关系和逻辑推理关系两种，它们分别属于形式语言语法和语义研究的范畴。（的范畴。（参看前面两命题推理

10、例子参看前面两命题推理例子） 我们已经知道，我们已经知道，逻辑演算是为了研究推理中前提和结论之间的逻辑演算是为了研究推理中前提和结论之间的形式推理关系而构造的形式语言形式推理关系而构造的形式语言。逻辑演算作为一个数学系统，需。逻辑演算作为一个数学系统，需要有符号，而作为一种形式语言，它必须要有构成语言的符号，即要有符号，而作为一种形式语言，它必须要有构成语言的符号，即字母，而且，从便于使用和理解的角度考虑，两者应该尽可能地保字母，而且，从便于使用和理解的角度考虑，两者应该尽可能地保持一致。持一致。第一章第一章 命题逻辑命题逻辑第一章第一章 命题逻辑命题逻辑逻辑成为一门科学，是从逻辑成为一门科学

11、，是从亚里士多德亚里士多德开始的开始的。命题（百度）：命题（百度）： 1.1 1.1 命题及其表示法命题及其表示法 在现代哲学、数学、逻辑学、语言学中，在现代哲学、数学、逻辑学、语言学中，命题是指一个判断（陈述）的语义（实际表达命题是指一个判断（陈述）的语义（实际表达的概念），这个概念是可以被定义并观察的现的概念），这个概念是可以被定义并观察的现象。象。命题命题不是指判断（陈述）本身，而是指所不是指判断（陈述）本身，而是指所表达的语义。当相异判断（陈述）具有相同语表达的语义。当相异判断（陈述）具有相同语义的时候，他们表达相同的命题。义的时候，他们表达相同的命题。第一章第一章 命题逻辑命题逻辑具

12、有单一、明确的含义具有单一、明确的含义。其基本元素是具有判断内容的陈述句其基本元素是具有判断内容的陈述句。日常中使用的语言称日常中使用的语言称。古典逻辑认为：命题或真或假，不能兼而有之古典逻辑认为：命题或真或假，不能兼而有之。 无所谓真假的语句（感叹、祈使、疑问）不能构成命题。无所谓真假的语句（感叹、祈使、疑问）不能构成命题。 1.1 1.1 命题及其表示法命题及其表示法第一章第一章 命题逻辑命题逻辑表示命题的符号称为表示命题的符号称为如：如：P P、A Ai i、 33 。命题有命题有： 不能分解为更简单的陈述句为不能分解为更简单的陈述句为； 由联结词、标点符号、原子命题构成由联结词、标点符

13、号、原子命题构成。对命题变元对命题变元P P以特定命题取代，称对以特定命题取代，称对P P进行进行。一个命题标识符（一个命题标识符（P P）如表示确定的命题，称）如表示确定的命题，称。 否则称否则称（不是命题）。（不是命题）。 1.1 1.1 命题及其表示法命题及其表示法第一章第一章 命题逻辑命题逻辑例：例：（1）雪是黑的；）雪是黑的；（2）张三唱歌并且张三跳舞；）张三唱歌并且张三跳舞；（3）全体立正！）全体立正！（4）你会开汽车吗？）你会开汽车吗？（5）我正在说谎。）我正在说谎。（6）如果天气好，那么我要进城去。）如果天气好，那么我要进城去。（7）如果地球是方的，那么恐龙现在还活着。）如果地

14、球是方的，那么恐龙现在还活着。（8）陈胜、吴广起义那天郑州下雨。）陈胜、吴广起义那天郑州下雨。（9）大于）大于2的偶数均可分解为两个质数的和（哥德的偶数均可分解为两个质数的和（哥德 巴赫猜想）。巴赫猜想）。 1.1 1.1 命题及其表示法命题及其表示法第一章第一章 命题逻辑命题逻辑 （1） 4是素数。是素数。例例 : 判断下列句子是否为命题判断下列句子是否为命题（7） 这朵花真美丽啊！这朵花真美丽啊！（6） 请不要吸烟！请不要吸烟！2（5） 大于大于 吗？吗？（4） 2050年元旦是晴天。年元旦是晴天。（3） 火星上有水。火星上有水。5（2） 是无理数是无理数 。第一章第一章 命题逻辑命题逻辑

15、定义定义 1 :设设 P 为命题，复合命题为命题，复合命题“非非P ” (即即 “P的否定的否定”)称为称为 P 的否定式，记为的否定式，记为 P 。 符号符号 称为称为否定否定联结词。联结词。规定：规定：P为真当且仅当为真当且仅当P 为假。为假。则则: (1) P ； (2) Q .例例 符号化：（符号化：（1）张伟不是三好学生）张伟不是三好学生; （2） 不是有理数不是有理数 。 2解：记解：记 P：张伟是三好学生。张伟是三好学生。 Q： 是有理数。是有理数。 2 1.2 1.2 联结词联结词联结词联结词是是复合命题复合命题中重要组成部分中重要组成部分 。第一章第一章 命题逻辑命题逻辑 1

16、.2 1.2 联结词联结词 定义定义2 ：设：设 P , P , Q Q 为两个命题。复合命题为两个命题。复合命题“ “ P P 与与Q Q” ” 即即“ “P P 并且并且Q Q” ” 称为称为 P P 与与 Q Q 的合取式，记为的合取式，记为 P P Q Q。符号。符号称为称为合取合取联结词。联结词。规定：规定： P P Q Q为真为真当且仅当当且仅当 P P 与与Q Q 同时为真同时为真。注：自然语言中注：自然语言中 “与与”, “和和”, “且且”, “既既.又又”, “不仅不仅而而且且”, “虽然虽然但是但是”, “一面一面一面一面”等联结词都可以符号等联结词都可以符号化为化为；

17、但并不是所有的但并不是所有的“与与”、“和和”等都能用联结词等都能用联结词替代。替代。第一章第一章 命题逻辑命题逻辑 (1) 吴颖既用功又聪明吴颖既用功又聪明. . (2) 吴颖吴颖不仅用功而且聪明不仅用功而且聪明. . (3) 吴颖吴颖虽然聪明，但不用功虽然聪明，但不用功. . (4) 张辉和王张辉和王丽丽都是三好学生都是三好学生. . (5) 张张辉辉和王丽是同学和王丽是同学. .例例：将下列命题符号化将下列命题符号化 PQ; PQ； QP；RS。(5) 是原子命题是原子命题, ,符号化为符号化为T: 张张辉辉和王丽是同学。和王丽是同学。则符号化分别为：则符号化分别为： 解解: (1)、(

18、2)、(3)、(4)： 令令P:吴颖吴颖用功；用功；Q:吴颖吴颖聪明，聪明， R: 张伟是三好学生；张伟是三好学生；S: 王辉是三好学生王辉是三好学生.第一章第一章 命题逻辑命题逻辑 1.2 1.2 联结词联结词定义定义3 ：设：设 P , Q 为两个命题为两个命题 , 复合命题复合命题 “ P 或或 Q ” 称为称为 P 与与 Q 的析取式的析取式, 记为记为 PQ。符号。符号称为称为析取析取联结词。联结词。规定：规定： PQ 为假当且仅当为假当且仅当 P 与与 Q 同时为假。同时为假。注注: 自然语言中的自然语言中的 “或或” 联结的两个命题可以具有相容性，联结的两个命题可以具有相容性，也

19、可以具有排斥性。也可以具有排斥性。前者称为前者称为相容或相容或，后者称为后者称为排斥或排斥或。析取联结词析取联结词指的是指的是“相容或相容或”。第一章第一章 命题逻辑命题逻辑（1）张晓静爱唱歌或爱听音乐。）张晓静爱唱歌或爱听音乐。（2）张晓静只能挑选）张晓静只能挑选202房或房或203房。房。（3）张晓静是江西人或安徽人。）张晓静是江西人或安徽人。解：解：(1)令令P:张晓静爱唱歌；张晓静爱唱歌；Q:张晓静爱听音乐，张晓静爱听音乐， 则：则：例例：将下列命题符号化将下列命题符号化PQ ; (2)令令R:张晓静住张晓静住202房；房；S:张晓静住张晓静住203房，房，则则:(RS)(RS);(3

20、)令令T:张晓静是江西人；张晓静是江西人；U:张晓静是安徽人，张晓静是安徽人，则：则：(TU U)(T TU U).).第一章第一章 命题逻辑命题逻辑 定义定义4 ：设设 P, ,Q为两个命题。复合命题为两个命题。复合命题 “ “如果如果 P, ,则则 Q ”称为称为P与与Q的的条件条件式，记作式，记作PQ。符号。符号称为称为条件条件联结词，联结词， 称称P是是条件条件式的式的前件前件，Q是是条件式的条件式的后件后件，Q是是P的必的必要条件。要条件。规定：规定： PQ为假为假当且仅当当且仅当 P 为真为真Q为假为假。第一章第一章 命题逻辑命题逻辑注：注： 1. 在自然语言中，在自然语言中，“如

21、果如果P, 则则Q”这种命题还有其它叙述方式，这种命题还有其它叙述方式，比如：比如：“只要只要P, 就就Q”，“ 因为因为P，所以，所以 Q”, “P仅当仅当Q”, “只有只有Q才才P”，“除非除非Q Q才才P”, “除非除非Q，否则非，否则非P ”等等，它们都可等等，它们都可符号化为符号化为 PQ。2. 在数学或其它自然科学中，在数学或其它自然科学中，“如果如果P,则则Q” 往往表达的是前件往往表达的是前件P为真，后件为真，后件Q也为真的推理关系。但在数理逻辑中，作为一种也为真的推理关系。但在数理逻辑中，作为一种规定，当规定，当 P为假时，无论为假时，无论Q是真是假，是真是假，PQ均为真（因

22、考虑的均为真（因考虑的整个语句）。整个语句）。3. 在自然语言中，在自然语言中，“如果如果 P, 则则 Q ” 中的前件中的前件 P 和后件和后件 Q 往往往往具有某种内在联系，而在数理逻辑中，具有某种内在联系，而在数理逻辑中，P 与与 Q 可以无任何内在可以无任何内在联系。联系。第一章第一章 命题逻辑命题逻辑(1) 如果如果3+3 = 6,则雪是白色的。则雪是白色的。(2) 如果如果3+3 6,则雪是白色的。则雪是白色的。(3) 如果如果3+3 = 6,则雪不是白色的。则雪不是白色的。(4) 如果如果3+3 6,则雪不是白色的。则雪不是白色的。(5) 只要只要 a 能被整除，则能被整除，则

23、a 一定能被整除。一定能被整除。(6) a 能被整除，仅当能被整除，仅当 a 能被整除。能被整除。(7) 除非除非 a 能被整除，能被整除，a 才能被整除。才能被整除。(8) 除非除非 a 能被整除，否则能被整除，否则 a 不能被整除。不能被整除。(9) 只有只有 a 能被整除，能被整除，a 才能被整除。才能被整除。例例：将下列命题符号化，并指出各复合命题的真值。将下列命题符号化，并指出各复合命题的真值。解：令解：令P：3+3=6； Q：雪是白色的。则：雪是白色的。则 (1) 到到 (4) 的符号化形式分别为：的符号化形式分别为： 令令R：a 能被整除；能被整除； S: : a能被整除。能被整

24、除。 (5) 到到 (9) 都可符号化为都可符号化为:PQ；PQ；PQ；PQ。它们的真值分别为：它们的真值分别为：,。RS, ,真值为。真值为。第一章第一章 命题逻辑命题逻辑 1.2 1.2 联结词联结词定义定义 5：设：设 P, Q 是两个命题，复合命题是两个命题，复合命题 “ P 当且当且仅当仅当 Q ”称为称为 P 与与 Q 的等价式，记为的等价式，记为 PQ。符号。符号称为称为双条件双条件联结词。联结词。规定：规定： PQ 为真当且仅当为真当且仅当 P 与与 Q 同时为真或同时同时为真或同时为假。为假。注：注：PQ 可理解为可理解为“Q与与P互为充分必要条件互为充分必要条件”； 它与它

25、与(PQ)(QPQP) )的逻辑关系完全一致。的逻辑关系完全一致。第一章第一章 命题逻辑命题逻辑 (1) 3 是无理数当且仅当加拿大位于亚洲。是无理数当且仅当加拿大位于亚洲。(2) 2+3=5的充要条件是的充要条件是3是无理数。是无理数。(3) 若两圆的面积相等若两圆的面积相等, 则它们的半径相等则它们的半径相等, 反之亦然。反之亦然。(4) 当王小红心情愉快当王小红心情愉快时时, 她就唱歌她就唱歌, 反之反之, 当她唱歌时当她唱歌时, 一定心情愉快。一定心情愉快。解：解：(1)令令P:3是无理数；是无理数；Q: 加拿大位于亚洲，则符号化为加拿大位于亚洲，则符号化为(4)令令U:王小红心情愉快

26、王小红心情愉快；V:王小红唱歌王小红唱歌，则，则符号化为符号化为P Q , 真值为真值为0。(2)令令R:2+3=5；令；令P:3是无理数，则是无理数，则符号化为符号化为 R P , 真值为真值为1。 (3)令令S:两圆面积相等；两圆面积相等；T:两圆半径相等，则符号化为两圆半径相等，则符号化为U V, 真值由具体情况而定。真值由具体情况而定。ST ,真值为真值为1。例例：将下列命题符号化，并讨论它们的真值。将下列命题符号化，并讨论它们的真值。第一章第一章 命题逻辑命题逻辑例例 : 将下列命题符号化。将下列命题符号化。 (1) 是有理数是不对的是有理数是不对的. .（2）2是偶素数是偶素数.

27、(3) 2或或4是偶素数是偶素数. (4) 如果如果2是素数，则是素数，则3也是素数也是素数. (5) 2是素数当且仅当是素数当且仅当3是素数是素数.2解：记解：记 P： 是有理数是有理数. Q：2是素数是素数. R：2是偶数是偶数. S：3是素数是素数. T：4是偶数是偶数.2则各语句表述为：则各语句表述为：非非P; (2) Q与与R; (3) P或或T; (4)如果如果Q,则则S；(5) Q当且仅当当且仅当S . 第一章第一章 命题逻辑命题逻辑 ：设：设P P是一个命题，是一个命题，P P的否定也是一个新命题。的否定也是一个新命题。( () ) ：设：设P P、Q Q是两个命题，是两个命题

28、，P PQ Q表示表示P P、Q Q的析取。的析取。( () ) ：设：设P P 、Q Q是命题，是命题，P PQ Q表示表示P P、Q Q的合取。（的合取。（）小小 结结：设设P P、Q Q是两个命题，是两个命题，P PQ Q表示命题若表示命题若P P则则Q Q。 Q Q是是P P的必要条件，的必要条件，P P是是，Q Q是是。：设：设P P、Q Q是两个命题，是两个命题，P PQ Q表示命题表示命题 “ “P PQ”Q”。第一章第一章 命题逻辑命题逻辑 以上定义的五种最基本的联结词组成一个联结词集以上定义的五种最基本的联结词组成一个联结词集， 。由其中某个联结词联结两个原子命题（。由其中某

29、个联结词联结两个原子命题（联结一联结一个原子命题）所形成的复合命题称为基本复合命题，它们的真值个原子命题）所形成的复合命题称为基本复合命题，它们的真值情况如下表。情况如下表。 P QPPQPQPQPQ小小 结结110000010111110110010 00 11 01 1第一章第一章 命题逻辑命题逻辑命题演算命题演算的合式公式（的合式公式（wff）规定为：）规定为：( (命题公式命题公式) )定义定义1：1)1)单个命题变元本身是一个单个命题变元本身是一个合式公式合式公式；2)2)如如A A是合式公式，则是合式公式，则 A A也是也是合式公式合式公式；3)3)如果如果A A和和B B是合式公

30、式，则是合式公式，则ABAB、ABAB、A AB B、ABAB 也是也是合式公式合式公式； 4)4)当且仅当能够有限次地应用当且仅当能够有限次地应用1)1)、2)2)、3)3)所得到的包含所得到的包含 命题变元、联结词和括号的符号串是命题变元、联结词和括号的符号串是合式公式合式公式。 1.3 1.3 命题公式与翻译命题公式与翻译 第一章第一章 命题逻辑命题逻辑 由于命题公式中含有命题变元，故其真值一般是不确定的。由于命题公式中含有命题变元，故其真值一般是不确定的。当公式中所有命题变元都指派成具体的命题后，命题公式就成当公式中所有命题变元都指派成具体的命题后，命题公式就成了真值确定的命题了。了真

31、值确定的命题了。 例如，命题公式例如，命题公式 (PQ)R :则命题公式则命题公式 (PQ)R 就被解释成了一个真命题。就被解释成了一个真命题。 若将若将 P 解释成解释成:2 是素数是素数, Q 解释成解释成:3是偶数是偶数, R 解释成：解释成： 是是无理数。无理数。2则则 (PQ)R 就被解释成了一个假命题。就被解释成了一个假命题。另外，如果另外，如果P, Q 的解释不变，而将的解释不变，而将R解释成：解释成： 是有理数，是有理数，2第一章第一章 命题逻辑命题逻辑 14次车下午五点半开或六点开。次车下午五点半开或六点开。我们要做到身体好、学习好、工作好，为祖四化建设而我们要做到身体好、学

32、习好、工作好，为祖四化建设而奋斗。奋斗。他既聪明又用功。他既聪明又用功。他虽聪明但不用功。他虽聪明但不用功。除非天气好，否则我不去公园。（天气好也不一定去）除非天气好，否则我不去公园。（天气好也不一定去）张三或李四都可以做这件事。张三或李四都可以做这件事。 1.3 1.3 命题公式与翻译命题公式与翻译 第一章第一章 命题逻辑命题逻辑符号化：符号化：辱骂和恐吓决不是战斗。辱骂和恐吓决不是战斗。小王和小李是夫妻，他们都很自私。小王和小李是夫妻，他们都很自私。如果天不下雨，则我去看足球比赛，否则我在家复习功课。如果天不下雨，则我去看足球比赛，否则我在家复习功课。如果苹果是红的或者是甜的，那么我买。如

33、果苹果是红的或者是甜的，那么我买。除非你努力，否则你将失败。除非你努力，否则你将失败。 1.3 1.3 命题公式与翻译命题公式与翻译 第一章第一章 命题逻辑命题逻辑符号化：符号化：张三是大学生，张三获奖学金，张三放声歌唱。张三是大学生，张三获奖学金，张三放声歌唱。我和他之间至少有一个要去边疆。我和他之间至少有一个要去边疆。如果他不来，那么他或是生病了，或是不在本地。如果他不来，那么他或是生病了，或是不在本地。如果你和他不都是傻子，那么你俩都不会去自讨没趣。如果你和他不都是傻子，那么你俩都不会去自讨没趣。说小学生编不了程序，或说小学生用不了计算机，那是不说小学生编不了程序，或说小学生用不了计算机

34、，那是不对的。对的。 1.3 1.3 命题公式与翻译命题公式与翻译 第一章第一章 命题逻辑命题逻辑 对命题公式中各分量（命题变元）指派所有可能的真对命题公式中各分量（命题变元）指派所有可能的真值，及由此确定的命题公式的真值汇列成的表称值，及由此确定的命题公式的真值汇列成的表称。定义定义1： 有些命题公式在分量不同的指派下，对应的真值与另有些命题公式在分量不同的指派下，对应的真值与另一命题公式的真值完全相同。一命题公式的真值完全相同。 真值表中，命题公式真值的取值数目，决定于分量的个真值表中，命题公式真值的取值数目，决定于分量的个数。数。n个命题变元组成的命题公式共有个命题变元组成的命题公式共有

35、2n种真值情况。种真值情况。 1.4 1.4 真值表与等价公式真值表与等价公式 第一章第一章 命题逻辑命题逻辑 1.4 1.4 真值表与等价公式真值表与等价公式 含含n n个命题变个命题变元元的公式共有的公式共有2 2n n 个不同的赋值。构造个不同的赋值。构造真值表的一般步骤如下：真值表的一般步骤如下：（1 1）列出命题公式中的所有命题变列出命题公式中的所有命题变元元 P, Q, ，列列出这些变出这些变元元的所有的所有2 2n n 个赋值。个赋值。 （2 2） 按从低到高的顺序依次列出公式的各个层。按从低到高的顺序依次列出公式的各个层。（3） 对应于变元的对应于变元的2 2n n 个赋值分别

36、计算出各层的真值，个赋值分别计算出各层的真值，直至算出公式的真值。直至算出公式的真值。第一章第一章 命题逻辑命题逻辑例例 写出下列公式的真值表，并求它们的成真、成假赋值。写出下列公式的真值表，并求它们的成真、成假赋值。 (1)(PQ)R; (2)(PP)(QQ); (3) (PQ)QRP Q RPRPQ(PQ)R解：解： (PQ)R 的真值表的真值表 111100000 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1101010100011000011101111(PP)(QQ)的真值表的真值表 P QPQPPQQ(PP)(QQ)0 00 11 01 1(PQ)Q

37、R 的真值表的真值表 P Q RPQ(PQ)(PQ)Q(PQ)QR0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 11111110010100000000011110011000011000000000000000000第一章第一章 命题逻辑命题逻辑 真值表中，两个命题公式真值表中，两个命题公式A A、B B在分量的不同指派，在分量的不同指派，其真值总是相同，则称其真值总是相同，则称A A和和B B是是等价等价的或的或逻辑相等逻辑相等的，并的，并记作：记作：ABAB。定义定义2： 当两个命题公式逻辑等价时，这两个命题公式具有当两个命题公式逻辑等价时，这两个命题公式

38、具有相同的相同的逻辑含义逻辑含义。 1.4 1.4 真值表与等价公式真值表与等价公式 第一章第一章 命题逻辑命题逻辑 给定给定n个命题变个命题变元元，使用联结词和括号，可构成无穷，使用联结词和括号，可构成无穷多个命题公式。多个命题公式。 个命题变个命题变元元共有共有 2 2n n 个可能的赋值，而在每个赋值下个可能的赋值，而在每个赋值下公式只能取公式只能取值值0或或1。因此含个命题变项的公式其真值表。因此含个命题变项的公式其真值表只有只有2 22 2种可能的情况。从而必有无穷多个公式具有相同种可能的情况。从而必有无穷多个公式具有相同的真值表。的真值表。第一章第一章 命题逻辑命题逻辑例例 ：下列

39、公式中哪些具有相同的真值表？下列公式中哪些具有相同的真值表？(1)PQ； (2)PQ； (3) (PQ)；(4) (PQ)(QP)； (5) QPP QPQPQ(PQ)(PQ)(QP)QP0 00 11 01 1解：解： 5个公式的真值表个公式的真值表 从上表可见，命题公式从上表可见，命题公式 “PQ” 与与 “ (PQ) ”有相同的真值表有相同的真值表。1101100111011001 1011命题命题 “PQ” 与与 “ (PQ)(QP) ” 有相同的真值表。有相同的真值表。第一章第一章 命题逻辑命题逻辑例例 ：判断公式判断公式(PQ) (PQ) 与与 PQ PQ是否等值。是否等值。解：用

40、真值表法判断解：用真值表法判断, 如下：如下：P QPQPQ(PQ)PQ(PQ)(PQ)0 00 11 01 1注：注：A A与与B B等值当且仅当等值当且仅当A A与与B B的真值表相同。因此，检验的真值表相同。因此，检验A A与与B B是否等值，也可通过是否等值，也可通过检查检查A A与与B B的真值表是否相同来实现。的真值表是否相同来实现。从表中可见，从表中可见，(PQ)(PQ)与与P PQQ等值。等值。110111101001011001001001第一章第一章 命题逻辑命题逻辑 (1) P(QR)(1) P(QR)与与(PQ)R; (2)(PQ)R (PQ)R; (2)(PQ)R 与

41、与(PQ)R(PQ)R。解：所给的解：所给的3 3个公式的真值表如下：个公式的真值表如下：P Q RP(QR)(PQ)R(PQ)R0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1但但(PQ)R(PQ)R(PQ)R.(PQ)R.110111110111111111000111由真值表可见，由真值表可见，P(QR)P(QR)(PQ)R,(PQ)R,第一章第一章 命题逻辑命题逻辑 当命题公式中变当命题公式中变元元较多时，用上述方法判断两个公式是否等值计算量很较多时，用上述方法判断两个公式是否等值计算量很大。为此，人们将一组经检验为正确的等值式作为大。为此，人们将一组经

42、检验为正确的等值式作为命题定律（逻辑等价式命题定律（逻辑等价式，可用真值表验证可用真值表验证），通过公式间的等值演算来判断两公式是否等值。常用的，通过公式间的等值演算来判断两公式是否等值。常用的命题定律命题定律(P15 表表1-4.8)如下如下： 1. 1.双重否定律：双重否定律：P P (P) 2. (P) 2.幂等律：幂等律：P PPP, PPP, PPPPP 3. 3.交换律交换律: PQ: PQQP, PQQP, PQQPQP 4. 4.结合律结合律: (PQ)R: (PQ)RP(QR), (PQ)RP(QR), (PQ)RP(QR)P(QR) 5. 5.分配律：分配律：P(QR)P(

43、QR)(PQ)(PR) (PQ)(PR) (对对的分配律的分配律) ) P(QR) P(QR)(PQ)(PR) (PQ)(PR) (对对的分配律的分配律) ) 6. 6.德摩根律：德摩根律：(PQ)(PQ) PQ, (PQ) PQ, (PQ)PQPQ 7. 7.吸收律：吸收律：P(PQ)P(PQ)P, P(PQ)P, P(PQ)P P第一章第一章 命题逻辑命题逻辑8.8.零律：零律：PPT TT T, P, PF FF F9. 9. 同一律：同一律：PPF FP, PP, PT TP P10. 10. 排中律：排中律：PPPPT T （否定律）（否定律）11. 11. 矛盾律：矛盾律：PPPP

44、F F （否定律）（否定律）12. 12. 条件条件等值式：等值式：PQPQPQPQ13. 13. 双条件双条件等值式等值式: (P: (PQ)Q)(PQ)(QP)(PQ)(QP)14. 14. 假言易位假言易位: PQ: PQ QP QP15. 15. 双条件双条件否定等值否定等值式式: P: PQ QPPQQ16. 16. 归谬论归谬论: (PQ)(PQ) : (PQ)(PQ) P P第一章第一章 命题逻辑命题逻辑 1.4 1.4 真值表与等价公式真值表与等价公式 利用这利用这1616组组2424个等值式可以推演出更多的个等值式可以推演出更多的逻辑等价逻辑等价式式。由已知的。由已知的逻辑等

45、价式逻辑等价式推演出另一些推演出另一些逻辑等价式逻辑等价式的的过过程称为等值演算。在等值演算中程称为等值演算。在等值演算中, ,经常用到如下置换规经常用到如下置换规则则（定理（定理1 1）。 第一章第一章 命题逻辑命题逻辑 如果如果X X是合式公式是合式公式A A的一部分，且的一部分，且X X本身也是一个合式本身也是一个合式公式，则称公式，则称。定义定义3：定理定理1： 1.4 1.4 真值表与等价公式真值表与等价公式 设设X X是合式公式是合式公式A A的子公式，若的子公式，若X YX Y，如果将，如果将A A中中的的X X用用Y Y来置换，所得到公式来置换，所得到公式B B与公式与公式A

46、A等价，即等价，即ABAB。 第一章第一章 命题逻辑命题逻辑 1.4 1.4 真值表与等价公式真值表与等价公式 例如，对公式例如，对公式(PQ)R,(PQ)R,如果用如果用PQPQ置换其中的置换其中的PQ,PQ,则得则得(PQ)R.(PQ)R.由于由于PQPQPQPQ，故，故(PQ)R (PQ)R (PQ)R(PQ)R。类似地，可进行如下等值演算：类似地，可进行如下等值演算： (PQ)R (PQ)R (PQ)R(PQ)R (PQ)R (PQ)R (PQ)R (PQ)R (PR)(QR)(PR)(QR)为简便起见为简便起见, 以后凡用到置换规则时以后凡用到置换规则时, 均不必标出。均不必标出。条

47、件等值式，置换规则）条件等值式，置换规则）( (条件等值式，置换规则）条件等值式，置换规则）( (德摩根律，置换规则）德摩根律，置换规则）( (分配律，置换规则）分配律，置换规则）第一章第一章 命题逻辑命题逻辑 1.4 1.4 真值表与等价公式真值表与等价公式 例例 用等值演算证明用等值演算证明: (P: (PQ)Q)R (PR)(QR)(PR)(QR) 注：用等值演算证明等值式时，既可以从左向右推演，也可以从右向左推演。注：用等值演算证明等值式时，既可以从左向右推演，也可以从右向左推演。证：证：(PR)(QR)(PR)(QR)(PR)(QR)(PR)(QR)(PQ)R(PQ)R(PQ)R(P

48、Q)R(PQ)R (PQ)R ( (条件等值式条件等值式) )( (分配律分配律) )( (德摩根律德摩根律) )( (条件等值式条件等值式)第一章第一章 命题逻辑命题逻辑 例例 证明：证明：(PQ)R (PQ)R P(QR P(QR）. .方法二方法二: : 记记A=(PQ)R, B= P(QR)A=(PQ)R, B= P(QR)。先将。先将A,BA,B等值演算等值演算 化成易于观察真值的公式，再进行判断。化成易于观察真值的公式，再进行判断。 A=(PQ)RA=(PQ)R(PQ)R(PQ)R (PQ)R (PQ)R (PQ)R(PQ)R B=P(QR) B=P(QR)P(QR)P(QR) P

49、QRPQR 易见，易见，000000，010010是是A A的成假赋值，而它们是的成假赋值，而它们是B B的成真赋值。的成真赋值。 (PQ)R (PQ)R P(QR) P(QR)。证：方法一：真值表法。证：方法一：真值表法。故故 ( (条件等值式条件等值式) ) ( (条件等值式条件等值式) ) ( (德摩根律德摩根律) )( (条件等值式条件等值式) )( (结合律结合律) )第一章第一章 命题逻辑命题逻辑v例 在某次研讨会的休息时间，3名与会者根据王教授的口音对他是哪个省市的人进行了判断：v 甲说王教授不是苏州人，是上海人。v 乙说王教授不是上海人，是苏州人。v 丙说王教授不是上海人，也不

50、是杭州人。v听完3人的判断，王教授笑着说，他们3人中有一人说得全对，有一人说对了一半，有一人说得全不对。试用逻辑演算法分析王教授到底是哪里的人？ v解： 设命题 P, Q, R分别表示 ： 王教授是苏州、上海、杭州人。则P, Q, R中必有一个真命题，两个假命题。要通过逻辑演算将真命题找出来。v设： 甲的判断为： A1= PQ; 乙的判断为：A2= PQ; 丙的判断为：A3= QR。 第一章第一章 命题逻辑命题逻辑v那么甲的判断全对： B1= A1= PQv 甲的判断对一半： B2=(PQ)(PQ)v 甲的判断全错： B3=PQv 乙的判断全对： C1= A2= PQv 乙的判断对一半： C2

51、=(PQ)(PQ)v 乙的判断全错： C3=PQv 丙的判断全对： D1= A3=QRv 丙的判断对一半： D2=(QR)(QR)v 丙的判断全错： D3=QR v由王教授所说 v E=(B1C2D3) (B1C3D2) (B2C1D3) v (B2C3D1) (B3C1D2) (B3C2D1) v为真命题. 第一章第一章 命题逻辑命题逻辑vB1C2D3=(PQ) (PQ)(PQ)(QR)v (PQQR) (PQPR)0vB1C3D2=(PQ)(PQ)(QR)(QR)v (PQR) (PQQR)v PQRvB2C1D3=(PQ)(PQ) (PQ)(QR)v (PPPQQR) (PQQR)v 0

52、v类似可得v B2C3D10, B3C1D2PQR, B3C2D10v于是，由同一律可知 E(PQR) (PQR)v但因为王教授不能既是苏州人，又是杭州人，因而P,R必有一个为假命题，即PQR0 。v于是 EPQR 为真命题，因而必有P,R为假命题，Q为真命题，即王教授为上海人，甲说得全对，丙说对了一半，而乙全说错啦。 第一章第一章 命题逻辑命题逻辑 给定一命题公式，无论对分量作怎样的指派，其对给定一命题公式，无论对分量作怎样的指派，其对应真值永为应真值永为T T，则称该命题公式为，则称该命题公式为重言式重言式或或永真式永真式。 定义定义1：定义定义2： 1.5 1.5 重言式与蕴含式重言式与

53、蕴含式 给定一命题公式，无论对分量作怎样的指派，其对给定一命题公式，无论对分量作怎样的指派，其对应真值永为，则称该命题公式为应真值永为，则称该命题公式为永假式永假式或或矛盾式矛盾式。 第一章第一章 命题逻辑命题逻辑 1.5 1.5 重言式与蕴含式重言式与蕴含式 若若A既不是永真式又不是矛盾式，则称既不是永真式又不是矛盾式，则称A为为可满足式可满足式。 注：注：A是可满足式当且仅当是可满足式当且仅当A至少存在一个成真赋值。至少存在一个成真赋值。 1. 重言式必是可满足式，但反之不真。重言式必是可满足式，但反之不真。 2. 可用真值表来判断公式的类型：可用真值表来判断公式的类型：(1) 若真值表最

54、后一列全为若真值表最后一列全为T，则公式为重言式；，则公式为重言式；(2) 若真值表最后一列全为若真值表最后一列全为F，则公式为矛盾式；，则公式为矛盾式；(3)若真值表最后一列至少有一个若真值表最后一列至少有一个T，则公式为可满足式。，则公式为可满足式。第一章第一章 命题逻辑命题逻辑(1)（(PQ)P)Q; (2) (P(PQ)R; (3) P(PQ)P)Q).解解: (1) （PQ)PQ (PQ)P)Q (PQ)P)Q (PQ)P)Q (PQ)P)Q (PP)(QP)Q (T(QP)Q (QP)Q (QQ)P TP T 故故 (PQ)PQ是重言式。是重言式。例例:用用等值演算判断下列公式的类

55、型等值演算判断下列公式的类型(条件等值式条件等值式)(条件等值式条件等值式)(德摩根律德摩根律)(德摩根律德摩根律)(分配律分配律)(排中律排中律)(同一律）同一律）(交换律，结合律）交换律，结合律）（排中律）（排中律）（零律）（零律）第一章第一章 命题逻辑命题逻辑(2) (2) (P(PQ)R (PPQ)R (PP Q)R (FQ)R FR F 故故 (P(PQ)R是矛盾式。是矛盾式。( (条件等值式，结合律）条件等值式，结合律） ( (德摩根律）德摩根律）( (矛盾律）矛盾律）( (零律零律) )( (零律）零律）第一章第一章 命题逻辑命题逻辑P(PQ)P)Q) P(PQ)P)Q) ( (

56、条件条件等值式等值式) ) P(PP)(QP)Q) ( (分配律分配律) ) P(0(QP)Q) ( (矛盾律矛盾律) ) P(QP)Q) ( (同一律同一律) ) P(QP)Q) ( (德摩根律，双重否定律德摩根律，双重否定律) ) P(QQ)P) ( (交换律，结合律交换律，结合律) ) P(TP) （排中律）（排中律） PT （零律）（零律） P （同一律）（同一律） 可见，（可见，（3 3）中公式不是重言式，因为）中公式不是重言式，因为0000，01 01 都是成假赋值；都是成假赋值；它也不是矛盾式，因为它也不是矛盾式，因为1010，11 11 都是其成真赋值，故它是可满足式。都是其成

57、真赋值，故它是可满足式。第一章第一章 命题逻辑命题逻辑 任何两个重言式的合取、析取，仍是一个重言式。任何两个重言式的合取、析取，仍是一个重言式。 定理定理1：定理定理2： 1.5 1.5 重言式与蕴含式重言式与蕴含式 一个重言式，对同一分量都用任一合式公式置换，一个重言式，对同一分量都用任一合式公式置换，其结果仍为一重言式。其结果仍为一重言式。 第一章第一章 命题逻辑命题逻辑1、其否定为永假式；、其否定为永假式；2、其合、析取、（双）条件都永真，可由简单、其合、析取、（双）条件都永真，可由简单 推出复杂重言式；推出复杂重言式；3、其中有许多有用的恒等式和永真蕴含式。、其中有许多有用的恒等式和永

58、真蕴含式。 重言式有以下特点：重言式有以下特点： 1.5 1.5 重言式与蕴含式重言式与蕴含式 第一章第一章 命题逻辑命题逻辑设设A A、B B为两命题公式，为两命题公式，ABAB当且仅当当且仅当ABAB为一重言式。为一重言式。定理定理3：定义定义3： 1.5 1.5 重言式与蕴含式重言式与蕴含式 当且仅当当且仅当P PQ Q是一个重言式时，我们称是一个重言式时，我们称“P P蕴含蕴含Q Q”：P=QP=Q。P PQ Q的的逆换式：逆换式：Q QP P； 反换式：反换式： P P Q Q； 逆反式：逆反式： Q Q P P。 第一章第一章 命题逻辑命题逻辑 在研究推理过程中，人们发现了一些重要

59、的重言蕴含式，并将它在研究推理过程中，人们发现了一些重要的重言蕴含式，并将它们作为推理定律，在推理过程中可直接引用。常用的推理定律（们作为推理定律，在推理过程中可直接引用。常用的推理定律（P21P21表表1-5.21-5.2蕴含式蕴含式）有：）有：(1)(1) 附加律附加律: A AB(2) 化简律化简律: AB A(3) 假言推理假言推理: (AB)A B(4) 拒取式拒取式: (AB)B A(5) 析取三段论析取三段论: (AB)B A(6) 假言三段论假言三段论: (AB)(BC) (AC)(7) 等价三段论等价三段论: (AB)(BC) (AC)(8) 构造性二难构造性二难: (AB)

60、(CD)(AC) (BD) 构造性二难构造性二难(特殊形式特殊形式): (AB)(AB)(AA) B(9) 破坏性二难破坏性二难: (AB)(CD)(BD)(AC)推理定律推理定律第一章第一章 命题逻辑命题逻辑 此外此外, 1 1.4中中给出的给出的24个个逻辑逻辑等等价价式中的每一个都派生出两条推理式中的每一个都派生出两条推理定律定律. 比如比如 A A产生出产生出AA 和和A A . 还有一些等还有一些等价价式和重言蕴含式可在推理中引用式和重言蕴含式可在推理中引用。如如:A (AB)(AB)(AB) ABA(BC) (AB) C(AB) (AB)(AB)(AB) ABA ABB ABAB