离散数学课件第一章(第1讲).ppt

《离散数学课件第一章(第1讲).ppt》由会员分享，可在线阅读，更多相关《离散数学课件第一章(第1讲).ppt（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第一篇第一篇 数理逻辑数理逻辑逻辑逻辑：通常指人们思考问题，从某些已知条件出发推出合：通常指人们思考问题，从某些已知条件出发推出合理的结论的规律。理的结论的规律。数理逻辑数理逻辑：用数学方法来研究推理的规律。包括命题逻辑：用数学方法来研究推理的规律。包括命题逻辑和谓词逻辑。和谓词逻辑。数理逻辑研究方法数理逻辑研究方法：采用一套数学的符号系统来描述和处：采用一套数学的符号系统来描述和处理思维的形式和规律。理思维的形式和规律。第一章第一章 命题逻辑命题逻辑1.命题与命题联结词命题与命题联结词2.命题公式与真值表命题公式与真值表3.命题公式的翻译命题公式的翻译4.等价式与蕴含式等价式与蕴含式5.对偶

2、与范对偶与范 式式6.命题逻辑的推理理论命题逻辑的推理理论7.其他联结词其他联结词1 命题与命题联结词命题与命题联结词定义定义：具有具有唯一值唯一值的的陈述句陈述句叫命题。叫命题。讨论定义：讨论定义：(1)命题的值：命题的值：命题值可以是真的，也可以是假的，但不能同时命题值可以是真的，也可以是假的，但不能同时既为真又为假。既为真又为假。(2)命题的真假值表示：命题的真假值表示：命题中所有的命题中所有的“真真”用用“”或或“1”表示表示 命题中所有的命题中所有的“假假”用用“”或或“0”表示。表示。1 命题命题(3)命题分类命题分类：)原子命题原子命题：一个命题，不能分解成为更简单的命题。：一个

3、命题，不能分解成为更简单的命题。例：我是一位学生。例：我是一位学生。)复合命题复合命题：若干个原子命题使用适当的联结词所组：若干个原子命题使用适当的联结词所组成的新命题。成的新命题。例：我是一位老师和他是一位学生例：我是一位老师和他是一位学生(4)命题的表示命题的表示：常用：常用26个大写的英文字母表示命题。个大写的英文字母表示命题。注意：注意：(1)命令句，感叹句，疑问句都不是命题。如：命令句，感叹句，疑问句都不是命题。如：1）把门关上！）把门关上！2）你到哪里去？）你到哪里去？(2)语句既为真，同时又包含假的不是命题，这样的句语句既为真，同时又包含假的不是命题，这样的句子称为子称为“悖论悖

4、论”。如：我正在说谎。如：我正在说谎。在命题逻辑中不讨论悖论问题。在命题逻辑中不讨论悖论问题。例例：判断下列语句是否为命题，若是，请给出其真值。：判断下列语句是否为命题，若是，请给出其真值。（1）十是整数。）十是整数。（2）上海是一个城市。）上海是一个城市。（3）加拿大是一个国家。）加拿大是一个国家。（4）是偶数而不是奇数。）是偶数而不是奇数。（5）请勿闯红灯！）请勿闯红灯！（6）你今天出差吗？）你今天出差吗？（7）x-y=6(T)(T)(T)(F)下面先介绍五个常用的命题联结词。下面先介绍五个常用的命题联结词。()否定词：否定词：（否定运算、非运算）（否定运算、非运算）符号）符号 ,读作读作

5、“非非”，“否定否定”设命题为，则设命题为，则 读做读做“的否定的否定”或或“非非”）否定运算真值表）否定运算真值表P PTFFT2 命题联结词命题联结词）举例：）举例：北京是一座城市。北京是一座城市。：北京不是一座城市。：北京不是一座城市。：每一种生物是动物。每一种生物是动物。：有一些生物不是动物。：有一些生物不是动物。这里这里 不能讲成不能讲成“每一种生物都不是动物每一种生物都不是动物”。对对量化命题量化命题的否定，除对动词进行否定外，同时对量词的否定，除对动词进行否定外，同时对量词也要加以否定。也要加以否定。(2)合取词合取词（“合取合取”、“与与”运算）运算）1)符号符号“”设，为两个

6、命题，则设，为两个命题，则称与的合取，称与的合取，读作：读作：“与与”“与的合取与的合取”“并且并且”PQP QQPFFFFFTFFTFFFTTTT2)合取运算真值表合取运算真值表 注：注：当且仅当和的真值均为当且仅当和的真值均为 ，则，则 的真值的真值为为 。否则，其真值为。否则，其真值为 。和地位是平等的，和的位置可以交换而不会和地位是平等的，和的位置可以交换而不会影响影响的结果。的结果。3)举例：举例：P：王华的成绩很好：王华的成绩很好 Q：王华的品德很好。：王华的品德很好。则则：王华的成绩很好并且品德很好。：王华的成绩很好并且品德很好。P：我们去种树：我们去种树 Q：房间里有一台电视机

7、：房间里有一台电视机 则则：我们去种树与房间里有一台电视机。：我们去种树与房间里有一台电视机。P：今天下大雨：今天下大雨 Q：3+3=6 则则：今天下大雨和：今天下大雨和3+3=6注：在日常生活中，合取词应用在二个有关系的命题注：在日常生活中，合取词应用在二个有关系的命题之间。由例之间。由例，可知，在逻辑学中，合取词可以可知，在逻辑学中，合取词可以用在二个毫不相干的命题之间。用在二个毫不相干的命题之间。P:王大和王二是亲兄弟。王大和王二是亲兄弟。注：这是原子命题。注：这是原子命题。()析取词析取词（或运算）（或运算）)符号符号“”设、为二个命题，则（设、为二个命题，则（）称作与的）称作与的“析

8、取析取”，读作：，读作：“或或”。)析取运算真值表：析取运算真值表：注：注：当且仅当、均为当且仅当、均为 时，时，为为 。否则，其真值为否则，其真值为 。和地位是平等的，和的位置可以交换和地位是平等的，和的位置可以交换,不会不会影响影响的结果。的结果。PQP QQPFFFFFTTTTFTTTTTT3)区分区分“可兼或可兼或”与与“不可兼或不可兼或（异或，排斥或）（异或，排斥或）”析取联结词为析取联结词为可兼或可兼或例如：例如：灯泡有故障或开关有故障。灯泡有故障或开关有故障。今天下雨或打雷。今天下雨或打雷。以上例句均为可兼或。以上例句均为可兼或。“不可兼或不可兼或”表示为：表示为：(异或异或),

9、当当P和和Q均为均为“T”时，时，则则P异或异或Q为为“F”。PQPQFFFFTTTFTTTF例：例：他通过电视看杂技或到剧场看杂技。他通过电视看杂技或到剧场看杂技。他乘火车去北京或乘飞机去北京。他乘火车去北京或乘飞机去北京。以上两句均为不以上两句均为不“可兼或可兼或”。()单条件联结词单条件联结词：（：（“蕴含蕴含”联结词、蕴含词）联结词、蕴含词）)符号符号“”设、为二个命题，则设、为二个命题，则 读作：读作：“如果则如果则”，“蕴含蕴含”，“仅当仅当”，“当且当且”，“是的充分条件是的充分条件”：称为前件、条件、前提、假设：称为前件、条件、前提、假设 ：称为后件、结论：称为后件、结论)蕴含

10、运算真值表蕴含运算真值表 PQPQFFTFTTTFFTTT注注:当为当为“”，为，为“”时，则（时，则（）为）为“”，否则（，否则（）都为）都为“”。)举例：举例：P：我拿起一本书：我拿起一本书 Q：我一口气读完了这本书：我一口气读完了这本书PQ：如果我拿起一本书，则我一口气读完了这本书。：如果我拿起一本书，则我一口气读完了这本书。P：月亮出来了：月亮出来了 Q：33=9 PQ：如果月亮出来了，则：如果月亮出来了，则33=9。(5)双条件联结词双条件联结词（“等价等价”词）词）)符号符号“”设、为二个命题，则设、为二个命题，则读作：读作：当且仅当当且仅当 等价等价 是的充分必要条件是的充分必要

11、条件 注：注：每当和的真值相同时，（每当和的真值相同时，（）的真值为）的真值为“”，否则（，否则（）的真值为）的真值为“”。、的地位是平等的，、交、的地位是平等的，、交 换位置不会改变换位置不会改变的的值。值。PQPQQPFFTTFTFFTFFFTTTT)等价运算真值表等价运算真值表 )举例：举例：ABC是等腰三角形是等腰三角形 ：ABC有两只角相等有两只角相等：ABC是等腰三角形当且仅当是等腰三角形当且仅当ABC中有两中有两只角相等。只角相等。：春天来了：春天来了 ：燕子飞回来了：燕子飞回来了：春天来了当且仅当燕子飞回来了。：春天来了当且仅当燕子飞回来了。：平面上两直线平行：平面上两直线平行

12、 ：二直线不相交二直线不相交：平面上二直线平行，当且仅当这二直线不相交。：平面上二直线平行，当且仅当这二直线不相交。：2+2=4 ：雪是白色的：雪是白色的：当且仅当雪是白色的。当且仅当雪是白色的。4)单条件联结词与双条件联结词的表达单条件联结词与双条件联结词的表达 当且仅当当且仅当 仅当仅当 当且当且n 3命题联结词的运算要求命题联结词的运算要求(1)先括号内，后括号外先括号内，后括号外(2)运算时联结词的优先次序由高到低排序为：运算时联结词的优先次序由高到低排序为：(3)含有相同含有相同 联结词的命题公式，如果联结词满足结合律，联结词的命题公式，如果联结词满足结合律，则可省去括号，否则不可省

13、去括号。则可省去括号，否则不可省去括号。例：例：（）可省去括号）可省去括号而而（）中的括号不能省去，因为）中的括号不能省去，因为“”不满不满足结合律。足结合律。(4)命题公式最外层的括号可以省去命题公式最外层的括号可以省去（）可写成）可写成 4命题联结词小结：命题联结词小结：(1)“或或”可分为可兼或（可分为可兼或（）和不可兼或（）和不可兼或（）(2)除除“”为一元运算外，其余四个均为二元运算。为一元运算外，其余四个均为二元运算。(3)命题联结词是命题或命题之间的联结词，而不是名词命题联结词是命题或命题之间的联结词，而不是名词之间、数字之间和动词之间的联结词。之间、数字之间和动词之间的联结词。