离散数学(部编)课件

离散数学第三章逻辑代数(上)命题演算2007年6月§3.1逻辑学的概念§3.2命题和逻辑联结词§3.3命题符号化§3.4命题公式§3.6对偶与范式§3.5逻辑等价式和逻辑蕴涵式章节介绍：教学时数：12节§3.7推理理论2007年6月楚雄师范学院计科系§3.1逻辑学的概念逻辑学是一门研究思维形式及思维规律的科学例:如果今天是周一,则要进行离散数学或C语言程序设计两门课中的一门的考试。如果C语言设计老师有会，则不考C语言程序设计。今天是周一。C语言程序设计老师又有会。结论：今天要进行离散数学考试。2007年6月楚雄师范学院计科系由于研究对象和方法的侧重点不同而分为形式逻辑、辨证逻辑。数理逻辑是用数学方法研究推理，是研究推理中前提和结论之间的形式的科学，所谓推理就是由一个或多个判断推出一个新判断的思维形式，所谓数学方法就是要建立通用的符号语言和通用的代数思想，在通用符号中实现语句的符号化，推理过程表现为符号序列的变形，只要对符号体系能作出明确的规定，就可以按照这些规定机械地推理。2007年6月楚雄师范学院计科系§3.２命题和逻辑联结词定义1命题是指具有真假态的陈述句，具真或具假二者必居其一，具真用1或表示，具假用0或表示。例1(1)今天是五一国际劳动节。(2)飞碟是从外星来的。(3)太阳从西边升起。(4)１＋101=110。(5)全体立正！(6)他去北京吗?§3.２.1命题2007年6月楚雄师范学院计科系注１:命题的真值是客观存在且唯一的,与我们的感觉或是否知道是真是假无关。2007年6月楚雄师范学院计科系注２：命题的真值通常与命题论及的范围、时间和空间有关。注3：（9）、（1２）是矛盾句，不是命题。注4：一个陈述句不具有真假态，就不是命题。如例1（12）、

（９）定义2除其本身外，它的任何局部不是命题，这样的命题称为原子命题。例2：雪是白的。定义3把原子命题和逻辑联结词共同组成的命题称为复合命题。2007年6月楚雄师范学院计科系原子命题通常用等大写字母表示．原子命题符号化步骤是：用大写字母可表示具体原子命题，此时它们称为命题常量。大写字母还可表示一个待定的命题，此时称它们为命题变量。2007年6月楚雄师范学院计科系§3.2.2逻辑联结词

0110真值表2007年6月楚雄师范学院计科系真值表0011010100012007年6月楚雄师范学院计科系注１：逻辑学的形式语言与论述的具体内容和我们的自身感受无关，上例完全符合逻辑学上的语法规则。注２：“与”、“和”有时不是我们定义的合取联结词。：小张与小王是同学。不是合取联结词：小张与小王都是三好生。是合取联结词小张是三好生且小王是三好生。2007年6月楚雄师范学院计科系真值表0011010101112007年6月楚雄师范学院计科系注1：命题逻辑中联结词“或”与自然语言中的“或”有较大区别，命题联结词中的“或”是“可兼或”。例：今天食堂供应米饭或馒头。注2：自然语言中的“或”还有“不可兼或”的意义。真值表00110101

01102007年6月楚雄师范学院计科系注3:自然语言中有些“或”并不是联结词。例：电影院里大约有400或500名观众。真值表0011010111012007年6月楚雄师范学院计科系注1:自然语言中,往往有因果关系，但在数理逻辑中不一定有因果关系。是前件，为后件。注2：一定要分析句子中那部分是前件，那部分是后件。2007年6月楚雄师范学院计科系例1：你将一事无成，除非你努力。

如果你不努力，那么你将一事无成。

令：你努力；：你将一事无成。

则命题符号化为：。

例2：只有天不下雨，我才骑自行车上班。

如果我骑自行车上班，那么天不下雨。令：天下雨；

：我骑自行车上班。

则命题符号化为：。2007年6月楚雄师范学院计科系真值表0011010110012007年6月楚雄师范学院计科系§3.3命题符号化原子命题符号化一般用大写字母符号化。如。习惯将这些符号放在命题前面。2.复合命题符号化，要正确的表示出原子命题和选择恰当逻辑联结词。例：对下列命题符号化：（1）我和他既是兄弟又是同学。（2）我和你之间至少有个要去海南岛。（3）狗急跳墙。（4）除非他来，否则我不同他谈判。如果我与他谈判，那么他来。（5）如果他没来见你，那么他或者生病了，或者他不在本地。2007年6月楚雄师范学院计科系§3.4命题公式...等可表示一个具体命题，此时...为命题常元。..等也可表示某一待定的命题，此时为命题变元，命题变元不是命题。可用表示两个特殊的命题：永假命题和永真命题。联结词、命题常元、命题变元及圆括号经过适当连接，得到字符串称为命题公式或合式公式，命题公式用.....等表示。2007年6月楚雄师范学院计科系2007年6月楚雄师范学院计科系定义2公式称为公式的子式，如果是公式中字母相互毗连的一部分，且自身为一公式。2007年6月楚雄师范学院计科系定义4真值表2007年6月楚雄师范学院计科系§3.5逻辑等价式和逻辑蕴涵式定义5公式称为重言式（又称永真式）公式称为矛盾式（永假式）公式称为可满足式2007年6月楚雄师范学院计科系2007年6月楚雄师范学院计科系2007年6月楚雄师范学院计科系001101011101001111112007年6月楚雄师范学院计科系2007年6月楚雄师范学院计科系2007年6月楚雄师范学院计科系2007年6月楚雄师范学院计科系2007年6月楚雄师范学院计科系Th3(代入原理)为永真式,为中变元,将中的出现处全部用公式代换后的命题公式(称为的一个代入实例)仍为一永真式。注：可用于证明一个公式是永真式，证明等价蕴涵中很有用2007年6月楚雄师范学院计科系2007年6月楚雄师范学院计科系2007年6月楚雄师范学院计科系§3.6对偶与范式§3.5.1对偶例：写出下列公式对偶式2007年6月楚雄师范学院计科系2007年6月楚雄师范学院计科系§3.5.2主范式2007年6月楚雄师范学院计科系