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

第一篇数理逻辑逻辑：通常指人们思考问题，从某些已知条件出发推出合理的结论的规律。数理逻辑：用数学方法来研究推理的规律。包括命题逻辑和谓词逻辑。数理逻辑研究方法：采用一套数学的符号系统来描述和处理思维的形式和规律。第一章命题逻辑§1.命题与命题联结词§2.命题公式与真值表§3.命题公式的翻译§4.等价式与蕴含式§5.对偶与范式§6.命题逻辑的推理理论§7.其他联结词§1命题与命题联结词《定义》：具有唯一值的陈述句叫命题。讨论定义：(1)命题的值：命题值可以是真的，也可以是假的，但不能同时既为真又为假。(2)命题的真假值表示：命题中所有的“真”用“Ｔ”或“1”表示命题中所有的“假”用“Ｆ”或“0”表示。1命题(3)命题分类：ⅰ)原子命题：一个命题，不能分解成为更简单的命题。例：我是一位学生。ⅱ)复合命题：若干个原子命题使用适当的联结词所组成的新命题。例：我是一位老师和他是一位学生(4)命题的表示：常用26个大写的英文字母表示命题。注意：(1)命令句，感叹句，疑问句都不是命题。如：1）把门关上！2）你到哪里去？(2)语句既为真，同时又包含假的不是命题，这样的句子称为“悖论”。如：我正在说谎。在命题逻辑中不讨论悖论问题。例：判断下列语句是否为命题，若是，请给出其真值。（1）十是整数。（2）上海是一个城市。（3）加拿大是一个国家。（4）２是偶数而３不是奇数。（5）请勿闯红灯！（6）你今天出差吗？（7）x-y=6(T)(T)(T)(F)下面先介绍五个常用的命题联结词。(１)否定词：（否定运算、非运算）１）符号?,读作“非”，“否定”设命题为Ｐ，则?Ｐ读做“Ｐ的否定”或“非Ｐ”２）否定运算真值表P?PTFFT2命题联结词３）举例：Ｐ：北京是一座城市。?Ｐ：北京不是一座城市。Ｑ：每一种生物是动物。?Ｑ：有一些生物不是动物。这里?Ｑ不能讲成“每一种生物都不是动物”。对量化命题的否定，除对动词进行否定外，同时对量词也要加以否定。(2)合取词（“合取”、“与”运算）1)符号“Λ”设Ｐ，Ｑ为两个命题，则ＰΛＱ称Ｐ与Ｑ的合取，读作：“Ｐ与Ｑ”“Ｐ与Ｑ的合取”“Ｐ并且Ｑ”PQPΛQQΛPFFFFFTFFTFFFTTTT2)合取运算真值表注：①当且仅当Ｐ和Ｑ的真值均为Ｔ，则ＰΛＱ的真值为Ｔ。否则，其真值为Ｆ。②Ｐ和Ｑ地位是平等的，Ｐ和Ｑ的位置可以交换而不会影响ＰΛＱ的结果。3)举例：①P：王华的成绩很好Q：王华的品德很好。则ＰΛＱ：王华的成绩很好并且品德很好。②P：我们去种树Q：房间里有一台电视机则ＰΛＱ：我们去种树与房间里有一台电视机。③P：今天下大雨Q：3+3=6则ＰΛＱ：今天下大雨和3+3=6注：在日常生活中，合取词应用在二个有关系的命题之间。由例②，③可知，在逻辑学中，合取词可以用在二个毫不相干的命题之间。④P:王大和王二是亲兄弟。注：这是原子命题。(３)析取词（或运算）１)符号“∨”设Ｐ、Ｑ为二个命题，则（Ｐ∨Ｑ）称作Ｐ与Ｑ的“析取”，读作：“Ｐ或Ｑ”。２)析取运算真值表：注：①当且仅当Ｐ、Ｑ均为Ｆ时，Ｐ∨Ｑ为Ｆ。否则，其真值为Ｔ。②Ｐ和Ｑ地位是平等的，Ｐ和Ｑ的位置可以交换,不会影响Ｐ∨Ｑ的结果。PQP∨QQ∨PFFFFFTTTTFTTTTTT3)区分“可兼或”与“不可兼或（异或，排斥或）”析取联结词为可兼或例如：灯泡有故障或开关有故障。今天下雨或打雷。以上例句均为可兼或。“不可兼或”表示为：▽(异或),当P和Q均为“T”时，则P异或Q为“F”。PQP▽QFFFFTTTFTTTF例：他通过电视看杂技或到剧场看杂技。他乘火车去北京或乘飞机去北京。以上两句均为不“可兼或”。(４)单条件联结词：（“蕴含”联结词、蕴含词）１)符号“→