离散数学课件(第1章)

1、12nM离散数学离散数学教案教案计算机科学与技术学院计算机科学与技术学院课程学时：课程学时：64主主 讲：宋讲：宋 成成河南理工大学河南理工大学电子教案电子教案12nM2n第第0篇：引言篇：引言n 课程的性质课程的性质n 离散数学与计算机离散数学与计算机n 课程的主要内容课程的主要内容n 课程的目的课程的目的n 教学要求教学要求n 学习方法学习方法n 教材和参考书教材和参考书n 考核方式考核方式12nM2n引言引言一、课程的性质一、课程的性质 离散数学（又称计算机数学）是现代离散数学（又称计算机数学）是现代数学的重要分支，数学的重要分支， 是计算机专业核是计算机专业核心基础课程之一。心基础课程

2、之一。12nM2n二、离散数学与计算机二、离散数学与计算机计算机开辟了脑力劳动机械化和自动计算机开辟了脑力劳动机械化和自动化的新纪元。化的新纪元。计算机的诞生，人们就要为它进一步计算机的诞生，人们就要为它进一步发展创建新的理论，就需要寻找新的发展创建新的理论，就需要寻找新的数学工具。数学工具。 例：为了描述新开拓的应用领域中的例：为了描述新开拓的应用领域中的各种数据的结构，就需要适宜的数学各种数据的结构，就需要适宜的数学工具。工具。引言引言12nM2n引言引言计算机各分支领域中的理论问题交错的使计算机各分支领域中的理论问题交错的使用着现代数学的各种不同的论题用着现代数学的各种不同的论题因为计算

3、机系统从本质上说是一种离散性因为计算机系统从本质上说是一种离散性的结构，它的许多性质可以在有限数学系的结构，它的许多性质可以在有限数学系统的框架中来理解，从中选出一些必要的统的框架中来理解，从中选出一些必要的而且是基本的主干论题称为离散数学而且是基本的主干论题称为离散数学因此，离散数学是随着因此，离散数学是随着计算机科学计算机科学的发展的发展而逐步建立的，它形成于七十年代初期，而逐步建立的，它形成于七十年代初期，是一门新兴的工具性学科是一门新兴的工具性学科12nM2n引言引言离散数学是现代数学的一个重要分支，是离散数学是现代数学的一个重要分支，是计算机科学与技术计算机科学与技术的理论基础，是的

4、理论基础，是计算机计算机科学与技术科学与技术专业的核心骨干课程，也是计专业的核心骨干课程，也是计算机专业考研的重要内容。算机专业考研的重要内容。它以研究离散量的结构和相互间的关系为它以研究离散量的结构和相互间的关系为主要目标，其研究对象一般是主要目标，其研究对象一般是有限个有限个或或可可数个数个元素。因此，它充分描述了计算机科元素。因此，它充分描述了计算机科学学离散性的离散性的特征特征12nM2n引言引言三、课程的内容三、课程的内容 离散数学课程的主要内容可以分为四个部分离散数学课程的主要内容可以分为四个部分n数理逻辑数理逻辑，包括命题逻辑和谓词逻辑（教材第一、二，包括命题逻辑和谓词逻辑（教材

5、第一、二章）章）n集合论集合论，包括集合与关系和函数（教材第三、四章），包括集合与关系和函数（教材第三、四章）n代数系统代数系统，包括代数系统的一般概念，几类典型的代，包括代数系统的一般概念，几类典型的代数系统和格（教材的第五、六章）数系统和格（教材的第五、六章）1.图论图论，包括图的基本概念，几种特殊的图（教材的第，包括图的基本概念，几种特殊的图（教材的第七章）七章）12nM2n引言引言四、学习该课程的目的四、学习该课程的目的1. 为了学习计算机的后续课程，如数据结为了学习计算机的后续课程，如数据结构、操作系统、编译原理、数据库原理、构、操作系统、编译原理、数据库原理、形式语言及自动机、软件

6、工程与方法学、形式语言及自动机、软件工程与方法学、计算机网络与人工智能、高级程序设计计算机网络与人工智能、高级程序设计语言、算法分析、逻辑设计、系统结构、语言、算法分析、逻辑设计、系统结构、容错技术等提供了必要的数学基础，为容错技术等提供了必要的数学基础，为阅读计算机文章作充分的数学准备阅读计算机文章作充分的数学准备12nM2n引言引言数理逻辑：数理逻辑：人工智能、数据库、形式语言与自动机、高级人工智能、数据库、形式语言与自动机、高级程序设计语言程序设计语言集合论：集合论：信息结构与检索、数据结构信息结构与检索、数据结构代数系统：代数系统：开关理论、逻辑设计和程序理论、语法分析开关理论、逻辑设

7、计和程序理论、语法分析图论：图论：可计算性理论、计算机网络、数据结构可计算性理论、计算机网络、数据结构2. 通过学习离散数学可以培养和提高自己通过学习离散数学可以培养和提高自己的抽象思维和逻辑推理能力，获得解决的抽象思维和逻辑推理能力，获得解决实际问题的能力，为以后的软硬件学习实际问题的能力，为以后的软硬件学习和研究开发工作打下坚实的数学基础和研究开发工作打下坚实的数学基础12nM2n引言引言五、教学要求五、教学要求 通过该课程的学习，学生应当了解并通过该课程的学习，学生应当了解并掌握计算机科学中普遍采用离散数学掌握计算机科学中普遍采用离散数学中的一些基本概念、基本思想、基本中的一些基本概念、

8、基本思想、基本方法等方法等12nM2n引言引言六、学习方法六、学习方法本课程有三个特点本课程有三个特点n课时少，内容多且抽象课时少，内容多且抽象n定义、定理多定义、定理多n 本课内容本课内容=定义定义+定理定理+例题例题n课外作业较多课外作业较多为了学好这门课，特提出四点要求为了学好这门课，特提出四点要求n课前预习，课中互动，课后复习课前预习，课中互动，课后复习n弄懂定义、定理，弄懂例题，加深对定义、定理的理解弄懂定义、定理，弄懂例题，加深对定义、定理的理解n在复习的基础上，做好课外作业，同学之间可以讨论，但要在复习的基础上，做好课外作业，同学之间可以讨论，但要弄懂、弄通弄懂、弄通n做好课堂笔

9、记做好课堂笔记12nM2n引言引言七、教材与参考书七、教材与参考书n 离散数学离散数学左孝凌等著左孝凌等著 上海科学技文献出上海科学技文献出版社版社n 离散数学离散数学-理论理论.分析分析.题解题解左孝凌等著左孝凌等著 上上海科学技文献出版社海科学技文献出版社n 离散数学及其应用离散数学及其应用魏雪丽等编著魏雪丽等编著 机械工机械工业出版社业出版社1. Discrete Mathematics and Its Applications(英文版英文版)（美）（美）Kenneth H.Rosen著著 机械工业出版社机械工业出版社12nM2n引言引言八、考核方式八、考核方式 基本考试成绩占：基本考试

10、成绩占：70% 平时成绩占：平时成绩占：30%做两点说明：做两点说明：考试类容以课堂上讲的为范围；考试类容以课堂上讲的为范围；课后布置的作业，希望大家认真完成课后布置的作业，希望大家认真完成为搞好教学，需要双方共同的努力为搞好教学，需要双方共同的努力12nM2n逻辑学：逻辑学：研究思维形式及思维规律的科学。研究思维形式及思维规律的科学。逻辑学分为两类：逻辑学分为两类：n 辩证逻辑：研究事物发展的客观规律；辩证逻辑：研究事物发展的客观规律；1. 形式逻辑：对思维的形式结构和规律进行研究。形式逻辑：对思维的形式结构和规律进行研究。第一篇：数理逻辑第一篇：数理逻辑数理逻辑：数理逻辑：用数学的方法研究

11、概念、判断和推理用数学的方法研究概念、判断和推理的科学，属于形式逻辑的科学，属于形式逻辑数理逻辑分为四大分支：数理逻辑分为四大分支：证明论、模型论、递归证明论、模型论、递归论和公理集合论。我们这里介绍的是属于四大分论和公理集合论。我们这里介绍的是属于四大分支的共同基础支的共同基础古典数理逻辑（命题逻辑和谓古典数理逻辑（命题逻辑和谓词逻辑）。词逻辑）。12nM2n第一章：命题逻辑第一章：命题逻辑1.1 命题命题1.2 命题联接词命题联接词1.3 命题公式与翻译命题公式与翻译1.4 真值表与等价公式真值表与等价公式1.5 重言式与蕴含式重言式与蕴含式1.6 其他连接词其他连接词 1.7 对偶与范式

12、对偶与范式1.8 推理理论推理理论12nM2n第一章：命题逻辑第一章：命题逻辑教学目的及要求：教学目的及要求： 深刻理解和掌握命题逻辑中基本概念和基本方法深刻理解和掌握命题逻辑中基本概念和基本方法教学类容：教学类容： 命题及表示、连接词、命题公式与翻译、真值表与命题及表示、连接词、命题公式与翻译、真值表与等价公式、重言式与蕴含式、对偶与范式、推理等价公式、重言式与蕴含式、对偶与范式、推理理论理论教学重点：教学重点：命题逻辑中的基本概念和基本推理方法命题逻辑中的基本概念和基本推理方法 教学难点：教学难点：推理理论推理理论12nM2n第一章：命题逻辑第一章：命题逻辑1.1 命题命题 定义：定义：

13、在数理逻辑中把能够确定真假值的陈述句在数理逻辑中把能够确定真假值的陈述句 叫命题叫命题讨论定义：讨论定义：n 只有陈述句才有可能成为命题，而其它的语句，如：感只有陈述句才有可能成为命题，而其它的语句，如：感叹句、祈使句、疑问句等都不是命题；叹句、祈使句、疑问句等都不是命题；n 一个语句虽是陈述句一个语句虽是陈述句,但不能判断真假不是命题；但不能判断真假不是命题；n 命题可以是真的，也可以是假的，但不能同时为真又为命题可以是真的，也可以是假的，但不能同时为真又为假，为真的命题为真命题，为假的命题为假命题；假，为真的命题为真命题，为假的命题为假命题；1. 虽然要求命题能判断真假，但不要求现在就能确

14、定真假，虽然要求命题能判断真假，但不要求现在就能确定真假，将来可以确定真假也可以；将来可以确定真假也可以；12nM2n第一章：命题逻辑第一章：命题逻辑 5. 命题的分类命题的分类n原子命题原子命题n 不能分解成更简单的命题，如：我是一位学生不能分解成更简单的命题，如：我是一位学生n复合命题复合命题 若干个原子命题使用适当的连接词组成的新命题，如：若干个原子命题使用适当的连接词组成的新命题，如：我是一位学生和他是一位工人我是一位学生和他是一位工人6. 命题所用符号（标识符）：常用大写命题所用符号（标识符）：常用大写26个英文字母个英文字母表示命题。表示命题。 用用A、B、CZ表示或带下表的大写表

15、示或带下表的大写字母等字母等7. 命题中所有的命题中所有的“真真”用用“T”或或“1”表示表示 命题中所有的命题中所有的“假假”用用“F”或或“0”表示表示12nM2n第一章：命题逻辑第一章：命题逻辑例：判断下列命题是否为命题例：判断下列命题是否为命题n 上海是个小村庄。上海是个小村庄。n 存在外星人。存在外星人。n 北京是中国的首都。北京是中国的首都。n 4是素数或是素数或6是素数。是素数。n 今天你吃了吗？今天你吃了吗？n 禁止吸烟！禁止吸烟！n 天气多好啊！天气多好啊！n 11+1=1001. 我正在说谎我正在说谎。 是假命题是假命题命题（待定）命题（待定）真命题真命题假命题假命题不是命

16、题不是命题不是命题不是命题不是命题不是命题视上下文而定视上下文而定悖论（命题逻辑中不讨论此类问题）悖论（命题逻辑中不讨论此类问题）如果我的确正在撒谎，那么这句话是真的，所以我不在撤谎，如果我的确正在撒谎，那么这句话是真的，所以我不在撤谎，如果我不在撒谎，那么这句话是假的，因而我正在撒谎如果我不在撒谎，那么这句话是假的，因而我正在撒谎 。只给不自己刮胡子的人刮胡子只给不自己刮胡子的人刮胡子12nM2n第一章：命题逻辑第一章：命题逻辑如果命题标识符表示一个具体、确定的命如果命题标识符表示一个具体、确定的命题，称为命题常量。如果命题标识符表示题，称为命题常量。如果命题标识符表示任意一个命题，称为命题

17、变元。命题变元任意一个命题，称为命题变元。命题变元无确定的真值。无确定的真值。命题是能判断真假的陈述句。而命题变元命题是能判断真假的陈述句。而命题变元代表任意的命题，其真值是不确定的。因代表任意的命题，其真值是不确定的。因而不是命题。而不是命题。如果命题变元表示原子命题时，该命题变如果命题变元表示原子命题时，该命题变元称为原子变元。元称为原子变元。12nM2n1.2 命题联接词命题联接词 在命题演算中，也有类似日常生活中的联接词，称为在命题演算中，也有类似日常生活中的联接词，称为“逻辑联接词逻辑联接词”或或“命题联接词命题联接词”。常用的逻辑联结词。常用的逻辑联结词有五种：否定联结词、合取联结

18、词、析取联结词、条件有五种：否定联结词、合取联结词、析取联结词、条件联结词和双条件联结词。联结词和双条件联结词。1. 否定联接词（否定、非）否定联接词（否定、非）（1）定义：设）定义：设P为命题，则为命题，则P的否定是一个复合命题，记的否定是一个复合命题，记作：作： P ，读作，读作“非非P”或或“P的否定的否定”。若。若P为为T，则，则 P为为F；若；若P为为F，则，则 P的真值为的真值为T。第一章：命题逻辑第一章：命题逻辑12nM2n第一章：命题逻辑第一章：命题逻辑（2）P和和P的关系（真值表）如表的关系（真值表）如表1.1所示：所示： 表1.1 P真值表 P P 0 1 1 0联结词联结

19、词“”也可以看作逻辑运算，它是一元运也可以看作逻辑运算，它是一元运算算12nM2n第一章：命题逻辑第一章：命题逻辑（3）举例：）举例： P：王强是一名大学生。：王强是一名大学生。 P：王强不是一名大学生。：王强不是一名大学生。 Q：每一种生物都是动物：每一种生物都是动物 Q：有些生物不是动物或不是每一：有些生物不是动物或不是每一种生物都是动物种生物都是动物注：对量化命题的否定，除了对动词进行否注：对量化命题的否定，除了对动词进行否定外，同时对量化词也要加以否定定外，同时对量化词也要加以否定12nM2n第一章：命题逻辑第一章：命题逻辑2. 合取联接词（与、积）合取联接词（与、积）（1）定义：设）

20、定义：设P和和Q均为命题，则均为命题，则P和和Q的合取是一个复合命题，的合取是一个复合命题，记作记作PQ，读作，读作“P与与Q”或或“P合取合取Q”。定义为：当且仅当。定义为：当且仅当P和和Q均为均为T时，时，PQ的才为的才为T。（2）联结词）联结词“”的真值表如表的真值表如表1.2所示。所示。 联结词联结词“”也可以看成逻辑运也可以看成逻辑运算，它是二元逻辑运算。算，它是二元逻辑运算。 表1.2 PQPQ0 0001010011112nM2n第一章：命题逻辑第一章：命题逻辑（3）举例：）举例： （a）设）设 P：2008年在北京举办奥运会。年在北京举办奥运会。 Q：中国是世界四大文明古国之一

21、。：中国是世界四大文明古国之一。 则则PQ：2008年在北京举办奥运会年在北京举办奥运会 并且中并且中国是世界四大文明古国之一。国是世界四大文明古国之一。（b） 设设P：王华的成绩很好。：王华的成绩很好。Q：王华的品德很好：王华的品德很好 则则PQ：王华的成绩很好并且品德很好：王华的成绩很好并且品德很好 （c） 设设P：我们去种树。：我们去种树。Q：房间里有台电视机：房间里有台电视机 则则PQ：我们去种树与房间里有台电视机：我们去种树与房间里有台电视机注：由例（注：由例（a）(c)可见可见,在日常生活中，合取词用在两个有关系的在日常生活中，合取词用在两个有关系的命题之间，而在逻辑学中，可以用在

22、两个毫不相干的两个命题中命题之间，而在逻辑学中，可以用在两个毫不相干的两个命题中12nM2n第一章：命题逻辑第一章：命题逻辑3. 析取联接词析取联接词（1）定义：设定义：设P和和Q均为命题，则均为命题，则P和和Q的析取是一个复合命题，记的析取是一个复合命题，记作作PQ，读作，读作“P或或Q”或者或者“P析取析取Q”。定义为：当且仅当。定义为：当且仅当P和和Q均为均为F时，时，PQ才为才为F。（2）联结词）联结词“”的真值表如表的真值表如表1.3所示。所示。 联结词联结词“” 可看成二元逻辑运可看成二元逻辑运算。算。表1.3PQPQ00001110111112nM2n第一章：命题逻辑第一章：命题

23、逻辑 “”与汉语中的与汉语中的“或或”相似，但又不相同。汉相似，但又不相同。汉语中的或有可兼或与不可兼或语中的或有可兼或与不可兼或(排斥或排斥或)的区分。的区分。（3）举例：）举例： 在家电视上看这场杂技或在家电视上看这场杂技或在剧场里看这在剧场里看这 场杂技。场杂技。(不可兼不可兼) 灯泡有故障或开关有故障。灯泡有故障或开关有故障。(可兼可兼, “”是可兼或是可兼或) 今天下雨或打雷今天下雨或打雷(可兼或可兼或)表1.4PQPQ000011101110注：不可兼或（异或）通常用注：不可兼或（异或）通常用“”表示，表示，P和和Q的真值不同的真值不同时时PQ为为T，真值表如表，真值表如表1.41

24、2nM2n第一章：命题逻辑第一章：命题逻辑4. （单）条件联接词（单）条件联接词（1）定义：设）定义：设P和和Q均为命题，其条件均为命题，其条件命题是个复合命题，记为：命题是个复合命题，记为：PQ。读作读作“如果如果P则则Q”，“P蕴含蕴含Q”，“P仅当仅当Q”“Q当且当且P”或或“P是是Q的充的充分条件分条件” 。定义为：当且仅当。定义为：当且仅当P为为T，Q为为F时，时，PQ才为才为F。P称为条件命称为条件命题题PQ的前件、条件、前提、假设，的前件、条件、前提、假设，Q称为条件命题称为条件命题PQ的后件、结论。的后件、结论。表1.5 PQPQ001011100111（2）联结词）联结词“”

25、的真值表如表的真值表如表1.5所所示。示。 联结词联结词“” 也可看成二元逻辑运算。也可看成二元逻辑运算。12nM2n第一章：命题逻辑第一章：命题逻辑 联结词联结词“”与汉语中的与汉语中的“如果如果，那么，那么”或或“若若，则，则”相相似，但又是不相同的。似，但又是不相同的。（3）举例：）举例：n设设P：小王努力学习。：小王努力学习。Q：小王学习成绩优秀。：小王学习成绩优秀。n 则则PQ：如果小王努力学习，那么他的学习成绩就优秀。：如果小王努力学习，那么他的学习成绩就优秀。nP：月亮出来了。：月亮出来了。Q：3*3=9。a. 则则PQ：如果月亮出来了，则：如果月亮出来了，则3*3=9通常称：通

26、常称： a为形式条件命题为形式条件命题前提和结果有某种形式和内容上的联系前提和结果有某种形式和内容上的联系 b为实质条件命题为实质条件命题前提和结果可以有联系，也可以没有联系，前提和结果可以有联系，也可以没有联系，只要满足条件命题的定义只要满足条件命题的定义所以，形式条件命题一定是实质条件命题，反之不一定。有些实质所以，形式条件命题一定是实质条件命题，反之不一定。有些实质条件命题在日常生活中不可能，但是在条件命题的定义中是允许的。条件命题在日常生活中不可能，但是在条件命题的定义中是允许的。12nM2n第一章：命题逻辑第一章：命题逻辑5. 双条件联接词双条件联接词（1）定义：设）定义：设P和和Q

27、均为命题，其复均为命题，其复合命题合命题PQ称为双条件命题，读称为双条件命题，读作：作：“P双条件双条件Q”或者或者“P当且仅当且仅当当Q”。定义为：当且仅当。定义为：当且仅当P和和Q的的真值相同时，真值相同时，PQ为为T。（2）联结词）联结词“”的真值表如表的真值表如表1.6所示。所示。表1.6 pqpq001010100111双条件联结词表示的是一个充分必要关系，与前面所述双条件联结词表示的是一个充分必要关系，与前面所述相同，也可以不必顾及其前因后果，而只根据联结词的相同，也可以不必顾及其前因后果，而只根据联结词的定义来确定其真值。定义来确定其真值。12nM2n第一章：命题逻辑第一章：命题

28、逻辑（3）举例：）举例： 设设P：张华是三好学生。：张华是三好学生。 Q：张华德、智、体全优秀。：张华德、智、体全优秀。 则则PQ：张华是三好学生当且仅当德、智、体：张华是三好学生当且仅当德、智、体全优秀。全优秀。 注：在双条件联接词中，注：在双条件联接词中，P和和Q的地位是平等的，的地位是平等的，即即P、Q交换位置不会改变真值表中的值交换位置不会改变真值表中的值 P当且仅当当且仅当Q PQ P当且当且Q Q P P仅当仅当Q PQ 12nM2n第一章：命题逻辑第一章：命题逻辑命题联接词小结命题联接词小结n命题联接词在使用中的优先级命题联接词在使用中的优先级n先括号内，后括号外先括号内，后括号

29、外n运算时的优先次序依次为：运算时的优先次序依次为：、 、 、 、 n联接词按从左到右的次序进行运算联接词按从左到右的次序进行运算n最外层的括号一律可以省去最外层的括号一律可以省去n五个联接词的含义与日常生活中的联接词含义大致相同五个联接词的含义与日常生活中的联接词含义大致相同n“或或”可分为可兼（可分为可兼（ ）或和不可兼或（）或和不可兼或（） （异或）（异或）n“”为一元运算，其余的为二元运算为一元运算，其余的为二元运算n“”分形式条件命题和实质条件命题分形式条件命题和实质条件命题n命题符号化的步骤：命题符号化的步骤：n找出各简单命题，分别符号化找出各简单命题，分别符号化找出各联接词，把简

30、单命题逐个联接起来找出各联接词，把简单命题逐个联接起来12nM2n第一章：命题逻辑第一章：命题逻辑1.3 命题公式与翻译命题公式与翻译约定：约定：（1）我们只注意命题的真假值，而不再注意命题的汉语意义。）我们只注意命题的真假值，而不再注意命题的汉语意义。（2）对命题的联接词，我们只注意真值表的定义，不注意他在日常生活中）对命题的联接词，我们只注意真值表的定义，不注意他在日常生活中的含义的含义n命题公式（合式公式）命题公式（合式公式）n命题常元：命题常元：表示确定的命题表示确定的命题 T，F 。n命题变元：命题变元：以真假为其变域的变元，或没有指定真值的命以真假为其变域的变元，或没有指定真值的命

31、题，常用大写英文字母表示题，常用大写英文字母表示1.命题公式：命题公式：由命题变元、常元、联接词、括号以规则的格由命题变元、常元、联接词、括号以规则的格式联接起来的字符串。式联接起来的字符串。12nM2n第一章：命题逻辑第一章：命题逻辑【定义】【定义】按下列规则可生成命题公式：按下列规则可生成命题公式：n单个命题变元和常元是命题公式。单个命题变元和常元是命题公式。n如果如果A是命题公式，那么是命题公式，那么A是命题公式。是命题公式。n如果如果A和和B是命题公式，那么是命题公式，那么(AB)、(AB)、 (AB)和和(AB)是命题公式。是命题公式。I.当且仅当有限次地应用了当且仅当有限次地应用了

32、、所得到的命题变所得到的命题变元、联接词和括号的符号串是命题公式。元、联接词和括号的符号串是命题公式。依照这个定义，下列符号串是命题公式：依照这个定义，下列符号串是命题公式： (PQ)，(P Q)，(P(PQ)， (PQ)(QR)(ST) 下列符号串不是命题公式：下列符号串不是命题公式： (PQ)(Q)，（，（p）12nM2n第一章：命题逻辑第一章：命题逻辑 定义给出命题公式定义的方法称为递归定定义给出命题公式定义的方法称为递归定义，递归包括三部分：义，递归包括三部分：基础基础，归纳归纳和和界限界限。定义中的定义中的是基础，是基础， 和和是归纳，是归纳，是是界限。界限。 有了命题公式的概念，就

33、可以用命题公式有了命题公式的概念，就可以用命题公式表示复合命题，常将这个过程称为命题的表示复合命题，常将这个过程称为命题的符号化。命题的符号化可按如下步骤进行：符号化。命题的符号化可按如下步骤进行：n 找出复合命题中的原子命题。找出复合命题中的原子命题。n 用大写的英文字母表示这些原子命题。用大写的英文字母表示这些原子命题。使用使用相应相应的命题联结词将这些大写的英文字的命题联结词将这些大写的英文字母连接起来。（教材例题）母连接起来。（教材例题）12nM2n第一章：命题逻辑第一章：命题逻辑1.4 真值表与等价公式真值表与等价公式 1.真值表真值表 命题变元用特定的命题来替代，这一过程称为对该命

34、命题变元用特定的命题来替代，这一过程称为对该命题变元进行的题变元进行的真值指派（赋值或解释）真值指派（赋值或解释） 命题公式可以看成是一个以真假值为定义域和以真命题公式可以看成是一个以真假值为定义域和以真假值为值域的一个函数。可以写成假值为值域的一个函数。可以写成: 例：公式例：公式P (QR)定义三元函数定义三元函数 Y=f(P，Q，R)= P (QR)【定义定义】在命题公式在命题公式A中，对中，对A的每一个赋值，就确定的每一个赋值，就确定了了A的一个真值，把它们汇列成表，称该表为命题公的一个真值，把它们汇列成表，称该表为命题公式式A的的真值表真值表。 32212nM2n第一章：命题逻辑第一

35、章：命题逻辑【定义】【定义】若指定的指派使若指定的指派使A的真值为的真值为T，则称这，则称这个指派为个指派为A的成真指派，若使的成真指派，若使A的真值为的真值为F，则称这个指派为则称这个指派为A的成假指派。的成假指派。构造真值表的步骤：构造真值表的步骤：n找出给定命题公式中所有的命题变元，列出所找出给定命题公式中所有的命题变元，列出所有可能的指派；有可能的指派；n按照从低到高的顺序写出命题公式的各层次；按照从低到高的顺序写出命题公式的各层次；I.对应每个指派，计算命题各个层次的值，直到对应每个指派，计算命题各个层次的值，直到最后计算出整个命题公式的值。最后计算出整个命题公式的值。12nM2n第

36、一章：命题逻辑第一章：命题逻辑例：例：构造命题公式构造命题公式PQ的真值表，的真值表，并求成真指派和成并求成真指派和成假指派。假指派。解：命题公式解：命题公式PQ的真值表的真值表如表如表1.7所示。所示。00，01，11是成真指是成真指派，派，10是成假指是成假指派派。 表1.7PQPPQ001101111000110112nM2n第一章：命题逻辑第一章：命题逻辑例：构造命题公式例：构造命题公式(PQ)(PQ)的真值表，并求成真指派和的真值表，并求成真指派和成假指派。成假指派。 解：命题公式解：命题公式(PQ)(PQ)的真值表如表的真值表如表1.8所示。所示。00， 11是成真指派，是成真指派

37、，01，10是成假指派是成假指派。 表1.8PQPQPQPQ (PQ)(PQ)000111101010001000100111000112(,. . .)yfX X X n注：注：n个命题变元组成的命题公式有个命题变元组成的命题公式有 种真值情况种真值情况12nM2n第一章：命题逻辑第一章：命题逻辑2、等价公式、等价公式【定义】【定义】对于任意两个公式对于任意两个公式A，B不论做何种指派，它们的真值均相不论做何种指派，它们的真值均相同，则称同，则称A和和B是等价的或逻辑相等的，记为是等价的或逻辑相等的，记为AB。可以证明，命题公式等价有下面的三条性质：可以证明，命题公式等价有下面的三条性质：

38、自反性，即对任意命题公式自反性，即对任意命题公式A， AA 对称性，即对任意命题公式对称性，即对任意命题公式A和和B，若，若AB，则，则BA 传递性，即对任意命题公式传递性，即对任意命题公式A，B和和C，若，若AB，BC，则，则AC例：例：根据等价的定义，用真值表证明根据等价的定义，用真值表证明P(QP)P(PQ)证明：证明：构造构造P(QP)和和P(PQ) 真值表，如表真值表，如表1.9所示。二者真值表相同，所示。二者真值表相同，故等价故等价表1.9 PQPQQPP(QP)PQP(PQ)0011111101100111100111111100110112nM2n第一章：命题逻辑第一章：命题逻

39、辑基本等价式常叫命题定律，下面是基本等价式常叫命题定律，下面是15组命题定律组命题定律：1.双重否定律双重否定律 AA2.交换律交换律 ABBA， ABBA 3.结合律结合律 (AB)CA(BC)，(AB)CA(BC)4.分配律分配律 A(BC)(AB)(AC) A(BC)(AB)(AC)5.德摩根律德摩根律 (AB)AB， (AB)AB6.幂等律幂等律 AAA，AAA7.吸收律吸收律 A(AB)A， A(AB)A8.零律零律 A11，A009.同一律同一律 A0A， A1A10.排中律排中律 AA111.矛盾律矛盾律 AA012.条件等价式条件等价式 ABAB 13.双条件等价式双条件等价式

40、 AB(AB)(BA)14.假言易位式假言易位式 ABBA15.双条件否定等价式双条件否定等价式 ABAB12nM2n第一章：命题逻辑第一章：命题逻辑 以上共以上共23个等价式，原则上说，这些公式都可以用真值表证个等价式，原则上说，这些公式都可以用真值表证明。下面仅验证德摩根律。明。下面仅验证德摩根律。 【例】【例】用真值表证明德摩根律用真值表证明德摩根律 (AB)AB解：解：表表1.10是是(AB)和和AB的真值表，从表中可以看出德摩根律成立。的真值表，从表中可以看出德摩根律成立。表1.10ABABABAB (AB)001110101100101001010110001012nM2n第一章：

41、命题逻辑第一章：命题逻辑【定义】【定义】如果如果X是命题公式是命题公式A的一部分且的一部分且X本身也是命本身也是命题公式，则称题公式，则称X为公式为公式A的子公式。的子公式。例：例：例如，例如，A=Q(P(PQ)，X=PQ，则，则X是是A的子公式。的子公式。【定理】【定理】设设X是命题公式是命题公式A的子公式，若的子公式，若XY，如果将，如果将A中的中的X用用Y来置换，得到的公式记为来置换，得到的公式记为B，则，则B与与A等等价，即价，即AB 证明：证明：对对A、B的任一赋值，的任一赋值，X与与Y的真值相同，而的真值相同，而A、B的其它部分完全相同，公式的其它部分完全相同，公式B与公式与公式A

42、的真值必相的真值必相同，故同，故AB。满足此定理的置换叫做等价置换（等价代换）满足此定理的置换叫做等价置换（等价代换）12nM2n第一章：命题逻辑第一章：命题逻辑【例】【例】用等价演算法证明用等价演算法证明 PQ(PQ)( P Q)证明：证明： PQ (PQ)(QP) (双条件等价式双条件等价式) (PQ)(QP) (条件等条件等价式价式) (PQ)(PP)(QQ)(QP) (分配律分配律) (PQ)00(QP) (矛盾律矛盾律) (PQ)(QP) (同一律同一律) (PQ)(PQ) (交换律交换律) PQ(PQ)(PQ) (等价的传等价的传递性递性)12nM2n第一章：命题逻辑第一章：命题逻

43、辑1.5 重言式与蕴含式重言式与蕴含式1、重言式、重言式【定义】【定义】设公式设公式A中有中有n个不同的原子变元个不同的原子变元 （n为正整数）为正整数）该变元组的任意一组确定的值该变元组的任意一组确定的值 称为称为A关于关于 的一个的一个完全指派完全指派，其中，其中 或为或为T，或为，或为F。如果对。如果对A中的部分变中的部分变元赋以确定的值，其余的变元没有赋以确定的值，则这样的元赋以确定的值，其余的变元没有赋以确定的值，则这样的一组值称为公式一组值称为公式A的关于变元组的的关于变元组的部分指派部分指派。【定义】【定义】如果一个命题公式所有的完全指派均为成真指派，则该如果一个命题公式所有的完

44、全指派均为成真指派，则该命题公式称为命题公式称为重言式重言式或或永真式永真式；如果一个命题公式所有的完；如果一个命题公式所有的完全指派均为成假指派，则该命题公式称为全指派均为成假指派，则该命题公式称为矛盾式矛盾式或或永假式永假式；如果一命题公式不是永假式，则为如果一命题公式不是永假式，则为可满足式可满足式。 显然，重言式的真值表的最后一列全为显然，重言式的真值表的最后一列全为1，矛盾式的，矛盾式的真值表的最后一列全为真值表的最后一列全为0，可满足的公式真值表的最，可满足的公式真值表的最后一列至少有一个后一列至少有一个1。iu1(,.)nuu1,.,nPPn2212nM2n第一章：命题逻辑第一章

45、：命题逻辑【例】【例】用等价演算法判断下列公式的类型。用等价演算法判断下列公式的类型。 Q (PQ)P) (PP)(Q Q)R) (PQ)P 解：解： Q(PQ)P) Q(PP)(QP) (分配律分配律) Q(0(QP) (矛盾律矛盾律) Q(QP) (同一律同一律) Q(QP) (德摩根德摩根律律) (QQ)P (结合律结合律) 1P (排中律排中律) 1 (零律零律) 由此可知，由此可知，为永真式。为永真式。12nM2n第一章：命题逻辑第一章：命题逻辑 (PP)(QQ)R) 1(QQ)R) (排中律排中律) 1(0R) (矛盾律矛盾律) 10 (零律零律) 0 (条件联结词的定义条件联结词

46、的定义)由此可知，由此可知，为永假式。为永假式。 (PQ)P (PQ)P (条件等价式条件等价式) P (吸收律吸收律) 由此可知，由此可知，是可满足式。是可满足式。12nM2n第一章：命题逻辑第一章：命题逻辑【定理【定理1.5.1】 任何两个重言式的合取或析取都是任何两个重言式的合取或析取都是重言式。重言式。证明：证明：设设A、B是重言式，对是重言式，对A和和 B的任何赋值，的任何赋值，总有总有A为为1，B为为1，所以，所以 AB1，AB1，故故AB和和AB都是重言式。都是重言式。【推论】【推论】任何两个矛盾式的合取或析取是矛盾式。任何两个矛盾式的合取或析取是矛盾式。【定理【定理1.5.2】

47、 一个重言式，对同一分量出现的每一个重言式，对同一分量出现的每一处都用同一合式公式置换，其结果仍是重言一处都用同一合式公式置换，其结果仍是重言式。式。证明：证明：由于重言式由于重言式 的真值与分量的指派无关，故的真值与分量的指派无关，故对于同一分量以任何公式置换后，重言式的真对于同一分量以任何公式置换后，重言式的真值仍永为值仍永为T。12nM2n第一章：命题逻辑第一章：命题逻辑【例】【例】证明证明(PQ)R)(PQ)R)为重言式。为重言式。证明：证明：由排中律知由排中律知PP为重言式，以为重言式，以(PQ)R)去置去置换其中的换其中的P，得公式，得公式(PQ)R)(PQ)R)，根据定理根据定理

48、1.5.2，这是重言式。，这是重言式。【定理【定理1.5.3】 设设A、B为两个命题公式，为两个命题公式，AB当且仅当当且仅当AB是重言式。是重言式。证明：证明：设设AB，下证，下证AB是重言式。是重言式。 给给A，B的任何赋值，因为的任何赋值，因为AB，所以，所以A，B具有相同具有相同的真值，由双条件联结词的定义知的真值，由双条件联结词的定义知AB为真，所以为真，所以AB为重言式。为重言式。 设设AB为重言式，下证为重言式，下证AB 给给A，B的任何赋值，因为的任何赋值，因为AB为重言式，故为重言式，故A，B的的真值相同，由命题公式等价的定义知真值相同，由命题公式等价的定义知AB12nM2n

49、第一章：命题逻辑第一章：命题逻辑2、蕴含式、蕴含式【定义】【定义】设设A和和B是命题公式，若是命题公式，若AB是重言式式，记是重言式式，记为为AB。说明：说明： “AB”读作读作“A永真永真蕴含蕴含B”，“A蕴含蕴含B”,“A能推得能推得B”，“”是关系符，是关系符， AB不为命不为命题公式题公式根据定义可以用真值表或等价演算证明根据定义可以用真值表或等价演算证明AB。证明证明AB的另外两种方法：的另外两种方法：n 对对A指定真值指定真值1，若由此推出，若由此推出B的真值不为的真值不为0，而为，而为1，则，则AB是重言式，即是重言式，即AB。1. 对对B指定真值指定真值0，若由此推出，若由此推

50、出A的真值不为的真值不为1，而为，而为0，则，则AB是重言式，即是重言式，即AB。12nM2n第一章：命题逻辑第一章：命题逻辑【例】【例】推证推证P (PQ)Q 解：证法解：证法1： 假定假定P(PQ)为为1，则，则P为为1且且PQ为为1，则则P为为0且且PQ为为1，则则Q为为1。所以所以 P(PQ)Q 证法证法2： 假定假定Q为为0，则，则P可以为可以为1或或0。 当当P为为1时，时，P为为0，所以，所以P(PQ)为为0。 当当P为为0时，时，(PQ)为为0，所以，所以P(PQ)为为0。故故 P(PQ)Q12nM2n第一章：命题逻辑第一章：命题逻辑蕴含式是逻辑推理的重要工具。下面是一些重要的

51、蕴含式。它们蕴含式是逻辑推理的重要工具。下面是一些重要的蕴含式。它们都可以用上述两种方法证明，其中都可以用上述两种方法证明，其中A，B，C，D是任意的命题是任意的命题公式。公式。 1. AAB， BAB 2. ABA， ABB 3. A(AB)B 4. B(AB)A 5. A(AB)B， B(AB)A 6. (AB)(BC)(AC) 7. (AB)(BC)(AC) 8. A AB， B AB 9. (AB) A， (AB) B 10. (AB)(CD) （ A C B D ） 11. (AB)(AC)(BC)C 12. (BD)(AB)(CD)(AC )12nM2n第一章：命题逻辑第一章：命题

52、逻辑等价式和蕴含式有下面的关系。等价式和蕴含式有下面的关系。【定理】【定理】设设A，B为任意两个命题公式，则为任意两个命题公式，则AB的充分必要条的充分必要条件是件是AB且且BA 证明：设证明：设AB，下证，下证AB且且BA 因为因为AB，所以，所以AB1 由双条件等价式得由双条件等价式得 (AB)(BA)AB1 因而因而AB与与BA都是重言式，故有都是重言式，故有AB且且BA。 设设AB且且BA，下证，下证AB。 因为因为AB且且BA，所以，所以AB与与BA都是重言式，重言都是重言式，重言式的合取也是重言式，即式的合取也是重言式，即 (AB)(BA)1 再由双条件等价式得再由双条件等价式得

53、(AB)(AB)(BA)1 即即AB为重言式，故有为重言式，故有AB。 12nM2n第一章：命题逻辑第一章：命题逻辑根据此定理，以前学过的所有等价式都可以作两个蕴含式来使根据此定理，以前学过的所有等价式都可以作两个蕴含式来使用。例如吸收律用。例如吸收律A(AB)A可以作两个蕴含式可以作两个蕴含式A(AB)A和和AA(AB) 来使用。来使用。【定理】【定理】 设设A、B、C为合式公式。为合式公式。 AA (即蕴含是自反的即蕴含是自反的) 若若AB且且A为重言式，则为重言式，则B必为重言式。必为重言式。 若若AB且且BC，则，则AC (即蕴含是传递的即蕴含是传递的) 若若AB且且AC，则，则ABC

54、 若若AB且且CB，则，则ACB 若若AB，C是任意公式，则是任意公式，则 ACBC 证明：仅证明证明：仅证明 。 因为因为AB，CB, 所以所以AB1，CB1 (AC)B(AC)B(AC)B (AB)(CB)(AB)(CB)111由等价的传递性，由等价的传递性，(AC)B1，故，故ACB12nM2n第一章：命题逻辑第一章：命题逻辑1.6 其它联接词其它联接词设设P和和Q是两个命题，复合命题是两个命题，复合命题PQ称作称作P和和Q的不可兼的不可兼析取，也叫异或。定义为：析取，也叫异或。定义为：PQ为为T当且仅当当且仅当P和和Q的真值不相同时。联结词的真值不相同时。联结词“ ”称为异或联结词。称

55、为异或联结词。 联结词联结词“”的真值表如表的真值表如表1.11所示。所示。“”也可以看成逻辑运算，也可以看成逻辑运算，它是二元逻辑运算。它在程序设它是二元逻辑运算。它在程序设中有广泛的应用。中有广泛的应用。 不可兼析取有下列的性质：不可兼析取有下列的性质： PQQ P (交换律交换律)表1.11PQ000011101110PQ (PQ)RP(QR) (结合律结合律)12nM2n第一章：命题逻辑第一章：命题逻辑 P(QR)(PQ)(PR) (合取对异或的合取对异或的分配律分配律) PQ(P Q)( PQ) PQ(PQ) PP0，0PP，1PP【定理】【定理】 设设P，Q，R为命题公式，如果为命

56、题公式，如果PQR，则，则P RQ，QRP，PQ R为一矛盾式。为一矛盾式。证明：证明： P R P PQ 0 Q Q QR P R R P 0 P PQ R PP 012nM2n第一章：命题逻辑第一章：命题逻辑【定义】【定义】 设设p和和Q是两个命题，复合命题是两个命题，复合命题PQ称作称作P和和Q的与非。定义为：当且仅当的与非。定义为：当且仅当P和和Q真值都是真时，真值都是真时，PQ才为假。才为假。 联结词联结词“”称为与非联结词。称为与非联结词。联结词联结词“”的真值表如表的真值表如表1.12所示。所示。 “”也可以看成是二元逻辑运算。也可以看成是二元逻辑运算。 由定义可以看出下式成立：

57、由定义可以看出下式成立： PQ(PQ) 联结词联结词“”还有以下几个性质：还有以下几个性质： PP(PP) P (PQ)(PQ) (PQ) (PQ)PQ (PP)(QQ)(P)(Q) (PQ)PQ表1.12PQPQ00101110111012nM2n第一章：命题逻辑第一章：命题逻辑【定义】【定义】设设P和和Q是两个命题，复合命题是两个命题，复合命题PQ称作称作P和和Q的或非。定义为：当且仅当的或非。定义为：当且仅当P、Q的真值都为假时，的真值都为假时，PQ的真值为真。联结词的真值为真。联结词“”称为或非联结词。称为或非联结词。联结词联结词“”的真值表如表的真值表如表1.13所示。所示。 “”也

58、可以看成是二元逻辑运算。也可以看成是二元逻辑运算。由此定义可得到下面的公式：由此定义可得到下面的公式： PQ(PQ) 联结词联结词还有下面的几个性质：还有下面的几个性质： PP(PP) P表1.13PQPQ001010100110 (PQ)(PQ) (PQ) (PQ)PQ (PP )(QQ) PQ(PQ)PQ12nM2n第一章：命题逻辑第一章：命题逻辑【定义】【定义】 设设S是一个联结词集合，如果任何是一个联结词集合，如果任何n(n1)个变元组成的个变元组成的公式，都可以由公式，都可以由S中的联结词来表示，则称中的联结词来表示，则称S是全功能联结词集。是全功能联结词集。 根据命题公式的定义根据

59、命题公式的定义 ， ， 是全功能是全功能联结词集。联结词集。 利用下列利用下列3个等价式可将任何命题公式中的命题联结词个等价式可将任何命题公式中的命题联结词“”、“”和和 “”去掉。去掉。 PQ(PQ)；PQ(PQ)； PQ(PQ) 所以所以 ， 是全功能联结词集。是全功能联结词集。 利用下列利用下列2个等价式可将任何命题公式中的命题联结词个等价式可将任何命题公式中的命题联结词“”和和“” 去掉。去掉。 PQPQ；PQ(PQ)(QP)(PQ)(Q P) 所以所以 ， 是全功能联结词集。是全功能联结词集。 用德摩根律可证明用德摩根律可证明 ， 和和 ， 是全功能联结词集。是全功能联结词集。 可以

60、证明可以证明 ， 的任何子集都不是全功能联结词集。的任何子集都不是全功能联结词集。12nM2n第一章：命题逻辑第一章：命题逻辑【定义】【定义】设设S是全功能联结词集，如果去掉其中的任何是全功能联结词集，如果去掉其中的任何 联结词后，联结词后，就不是全功能联结词集，则称就不是全功能联结词集，则称S是最小全功能联结词集。是最小全功能联结词集。 可以证明可以证明 ， ， ， ， ， 是最小全功是最小全功能联结词集。能联结词集。 现在讨论，现在讨论，n个命题变元可以构成多少个不等价的命个命题变元可以构成多少个不等价的命题公式。题公式。 两个命题变元可以构成多少个不等价的命题公式？两个命题变元可以构成多