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

《离散数学课件(第1章).ppt》由会员分享，可在线阅读，更多相关《离散数学课件(第1章).ppt（96页珍藏版）》请在三一办公上搜索。

1、离散数学教案,计算机科学与技术学院课程学时：64主 讲：宋 成,河南理工大学电子教案,第0篇：引言,课程的性质离散数学与计算机课程的主要内容课程的目的教学要求学习方法教材和参考书考核方式,引言,一、课程的性质 离散数学（又称计算机数学）是现代数学的重要分支，是计算机专业核心基础课程之一。,二、离散数学与计算机计算机开辟了脑力劳动机械化和自动化的新纪元。计算机的诞生，人们就要为它进一步发展创建新的理论，就需要寻找新的数学工具。例：为了描述新开拓的应用领域中的各种数据的结构，就需要适宜的数学工具。,引言,引言,计算机各分支领域中的理论问题交错的使用着现代数学的各种不同的论题因为计算机系统从本质上说

2、是一种离散性的结构，它的许多性质可以在有限数学系统的框架中来理解，从中选出一些必要的而且是基本的主干论题称为离散数学因此，离散数学是随着计算机科学的发展而逐步建立的，它形成于七十年代初期，是一门新兴的工具性学科,引言,离散数学是现代数学的一个重要分支，是计算机科学与技术的理论基础，是计算机科学与技术专业的核心骨干课程，也是计算机专业考研的重要内容。它以研究离散量的结构和相互间的关系为主要目标，其研究对象一般是有限个或可数个元素。因此，它充分描述了计算机科学离散性的特征,引言,三、课程的内容 离散数学课程的主要内容可以分为四个部分数理逻辑，包括命题逻辑和谓词逻辑（教材第一、二章）集合论，包括集合

3、与关系和函数（教材第三、四章）代数系统，包括代数系统的一般概念，几类典型的代数系统和格（教材的第五、六章）图论，包括图的基本概念，几种特殊的图（教材的第七章）,引言,四、学习该课程的目的为了学习计算机的后续课程，如数据结构、操作系统、编译原理、数据库原理、形式语言及自动机、软件工程与方法学、计算机网络与人工智能、高级程序设计语言、算法分析、逻辑设计、系统结构、容错技术等提供了必要的数学基础，为阅读计算机文章作充分的数学准备,引言,数理逻辑：人工智能、数据库、形式语言与自动机、高级程序设计语言集合论：信息结构与检索、数据结构代数系统：开关理论、逻辑设计和程序理论、语法分析图论：可计算性理论、计算

4、机网络、数据结构通过学习离散数学可以培养和提高自己的抽象思维和逻辑推理能力，获得解决实际问题的能力，为以后的软硬件学习和研究开发工作打下坚实的数学基础,引言,五、教学要求 通过该课程的学习，学生应当了解并掌握计算机科学中普遍采用离散数学中的一些基本概念、基本思想、基本方法等,引言,六、学习方法本课程有三个特点课时少，内容多且抽象定义、定理多 本课内容=定义+定理+例题课外作业较多为了学好这门课，特提出四点要求课前预习，课中互动，课后复习弄懂定义、定理，弄懂例题，加深对定义、定理的理解在复习的基础上，做好课外作业，同学之间可以讨论，但要弄懂、弄通做好课堂笔记,引言,七、教材与参考书离散数学左孝凌

5、等著 上海科学技文献出版社离散数学-理论.分析.题解左孝凌等著 上海科学技文献出版社离散数学及其应用魏雪丽等编著 机械工业出版社Discrete Mathematics and Its Applications(英文版)（美）Kenneth H.Rosen著 机械工业出版社,引言,八、考核方式 基本考试成绩占：70%平时成绩占：30%做两点说明：考试类容以课堂上讲的为范围；课后布置的作业，希望大家认真完成为搞好教学，需要双方共同的努力,逻辑学：研究思维形式及思维规律的科学。逻辑学分为两类：辩证逻辑：研究事物发展的客观规律；形式逻辑：对思维的形式结构和规律进行研究。,第一篇：数理逻辑,数理逻辑：

6、用数学的方法研究概念、判断和推理的科学，属于形式逻辑数理逻辑分为四大分支：证明论、模型论、递归论和公理集合论。我们这里介绍的是属于四大分支的共同基础古典数理逻辑（命题逻辑和谓词逻辑）。,第一章：命题逻辑,1.1 命题1.2 命题联接词1.3 命题公式与翻译1.4 真值表与等价公式1.5 重言式与蕴含式1.6 其他连接词 1.7 对偶与范式1.8 推理理论,第一章：命题逻辑,教学目的及要求：深刻理解和掌握命题逻辑中基本概念和基本方法教学类容：命题及表示、连接词、命题公式与翻译、真值表与等价公式、重言式与蕴含式、对偶与范式、推理理论教学重点：命题逻辑中的基本概念和基本推理方法 教学难点：推理理论,

7、第一章：命题逻辑,1.1 命题 定义：在数理逻辑中把能够确定真假值的陈述句 叫命题讨论定义：只有陈述句才有可能成为命题，而其它的语句，如：感叹句、祈使句、疑问句等都不是命题；一个语句虽是陈述句,但不能判断真假不是命题；命题可以是真的，也可以是假的，但不能同时为真又为假，为真的命题为真命题，为假的命题为假命题；虽然要求命题能判断真假，但不要求现在就能确定真假，将来可以确定真假也可以；,第一章：命题逻辑,5.命题的分类原子命题 不能分解成更简单的命题，如：我是一位学生复合命题 若干个原子命题使用适当的连接词组成的新命题，如：我是一位学生和他是一位工人6.命题所用符号（标识符）：常用大写26个英文字

8、母表示命题。用A、B、CZ表示或带下表的大写字母等7.命题中所有的“真”用“T”或“1”表示 命题中所有的“假”用“F”或“0”表示,第一章：命题逻辑,例：判断下列命题是否为命题上海是个小村庄。存在外星人。北京是中国的首都。4是素数或6是素数。今天你吃了吗？禁止吸烟！天气多好啊！11+1=100我正在说谎。,是假命题命题（待定）真命题假命题不是命题不是命题不是命题视上下文而定悖论（命题逻辑中不讨论此类问题）,如果我的确正在撒谎，那么这句话是真的，所以我不在撤谎，如果我不在撒谎，那么这句话是假的，因而我正在撒谎。只给不自己刮胡子的人刮胡子,第一章：命题逻辑,如果命题标识符表示一个具体、确定的命题

9、，称为命题常量。如果命题标识符表示任意一个命题，称为命题变元。命题变元无确定的真值。命题是能判断真假的陈述句。而命题变元代表任意的命题，其真值是不确定的。因而不是命题。如果命题变元表示原子命题时，该命题变元称为原子变元。,1.2 命题联接词 在命题演算中，也有类似日常生活中的联接词，称为“逻辑联接词”或“命题联接词”。常用的逻辑联结词有五种：否定联结词、合取联结词、析取联结词、条件联结词和双条件联结词。1.否定联接词（否定、非）（1）定义：设P为命题，则P的否定是一个复合命题，记作：P，读作“非P”或“P的否定”。若P为T，则 P为F；若P为F，则 P的真值为T。,第一章：命题逻辑,第一章：命

10、题逻辑,（2）P和P的关系（真值表）如表1.1所示：,联结词“”也可以看作逻辑运算，它是一元运算,第一章：命题逻辑,（3）举例：P：王强是一名大学生。P：王强不是一名大学生。Q：每一种生物都是动物 Q：有些生物不是动物或不是每一种生物都是动物注：对量化命题的否定，除了对动词进行否定外，同时对量化词也要加以否定,第一章：命题逻辑,2.合取联接词（与、积）（1）定义：设P和Q均为命题，则P和Q的合取是一个复合命题，记作PQ，读作“P与Q”或“P合取Q”。定义为：当且仅当P和Q均为T时，PQ的才为T。（2）联结词“”的真值表如表1.2所示。联结词“”也可以看成逻辑运算，它是二元逻辑运算。,第一章：命

11、题逻辑,（3）举例：（a）设 P：2008年在北京举办奥运会。Q：中国是世界四大文明古国之一。,则PQ：2008年在北京举办奥运会 并且中国是世界四大文明古国之一。,（b）设P：王华的成绩很好。Q：王华的品德很好 则PQ：王华的成绩很好并且品德很好,（c）设P：我们去种树。Q：房间里有台电视机 则PQ：我们去种树与房间里有台电视机,注：由例（a）(c)可见,在日常生活中，合取词用在两个有关系的命题之间，而在逻辑学中，可以用在两个毫不相干的两个命题中,第一章：命题逻辑,3.析取联接词（1）定义：设P和Q均为命题，则P和Q的析取是一个复合命题，记作PQ，读作“P或Q”或者“P析取Q”。定义为：当且

12、仅当P和Q均为F时，PQ才为F。（2）联结词“”的真值表如表1.3所示。联结词“”可看成二元逻辑运算。,第一章：命题逻辑,“”与汉语中的“或”相似，但又不相同。汉语中的或有可兼或与不可兼或(排斥或)的区分。（3）举例：,在家电视上看这场杂技或在剧场里看这 场杂技。(不可兼)灯泡有故障或开关有故障。(可兼,“”是可兼或)今天下雨或打雷(可兼或),注：不可兼或（异或）通常用“”表示，P和Q的真值不同时PQ为T，真值表如表1.4,第一章：命题逻辑,4.（单）条件联接词（1）定义：设P和Q均为命题，其条件命题是个复合命题，记为：PQ。读作“如果P则Q”，“P蕴含Q”，“P仅当Q”“Q当且P”或“P是Q

13、的充分条件”。定义为：当且仅当P为T，Q为F时，PQ才为F。P称为条件命题PQ的前件、条件、前提、假设，Q称为条件命题PQ的后件、结论。,（2）联结词“”的真值表如表1.5所示。联结词“”也可看成二元逻辑运算。,第一章：命题逻辑,联结词“”与汉语中的“如果，那么”或“若，则”相似，但又是不相同的。（3）举例：设P：小王努力学习。Q：小王学习成绩优秀。则PQ：如果小王努力学习，那么他的学习成绩就优秀。P：月亮出来了。Q：3*3=9。则PQ：如果月亮出来了，则3*3=9,通常称：a为形式条件命题前提和结果有某种形式和内容上的联系 b为实质条件命题前提和结果可以有联系，也可以没有联系，只要满足条件命

14、题的定义所以，形式条件命题一定是实质条件命题，反之不一定。有些实质条件命题在日常生活中不可能，但是在条件命题的定义中是允许的。,第一章：命题逻辑,5.双条件联接词（1）定义：设P和Q均为命题，其复合命题PQ称为双条件命题，读作：“P双条件Q”或者“P当且仅当Q”。定义为：当且仅当P和Q的真值相同时，PQ为T。（2）联结词“”的真值表如表1.6所示。,双条件联结词表示的是一个充分必要关系，与前面所述相同，也可以不必顾及其前因后果，而只根据联结词的定义来确定其真值。,第一章：命题逻辑,（3）举例：设P：张华是三好学生。Q：张华德、智、体全优秀。则PQ：张华是三好学生当且仅当德、智、体全优秀。注：在

15、双条件联接词中，P和Q的地位是平等的，即P、Q交换位置不会改变真值表中的值 P当且仅当Q PQ P当且Q Q P P仅当Q PQ,第一章：命题逻辑,命题联接词小结命题联接词在使用中的优先级先括号内，后括号外运算时的优先次序依次为：、联接词按从左到右的次序进行运算最外层的括号一律可以省去五个联接词的含义与日常生活中的联接词含义大致相同“或”可分为可兼（）或和不可兼或（）（异或）“”为一元运算，其余的为二元运算“”分形式条件命题和实质条件命题命题符号化的步骤：找出各简单命题，分别符号化找出各联接词，把简单命题逐个联接起来,第一章：命题逻辑,1.3 命题公式与翻译约定：（1）我们只注意命题的真假值，

16、而不再注意命题的汉语意义。（2）对命题的联接词，我们只注意真值表的定义，不注意他在日常生活中的含义命题公式（合式公式）命题常元：表示确定的命题 T，F。命题变元：以真假为其变域的变元，或没有指定真值的命题，常用大写英文字母表示命题公式：由命题变元、常元、联接词、括号以规则的格式联接起来的字符串。,第一章：命题逻辑,【定义】按下列规则可生成命题公式：单个命题变元和常元是命题公式。如果A是命题公式，那么A是命题公式。如果A和B是命题公式，那么(AB)、(AB)、(AB)和(AB)是命题公式。当且仅当有限次地应用了、所得到的命题变元、联接词和括号的符号串是命题公式。,依照这个定义，下列符号串是命题公

17、式：(PQ)，(P Q)，(P(PQ)，(PQ)(QR)(ST)下列符号串不是命题公式：(PQ)(Q)，（p）,第一章：命题逻辑,定义给出命题公式定义的方法称为递归定义，递归包括三部分：基础，归纳和界限。定义中的是基础，和是归纳，是界限。有了命题公式的概念，就可以用命题公式表示复合命题，常将这个过程称为命题的符号化。命题的符号化可按如下步骤进行：找出复合命题中的原子命题。用大写的英文字母表示这些原子命题。使用相应的命题联结词将这些大写的英文字母连接起来。（教材例题）,第一章：命题逻辑,1.4 真值表与等价公式 1.真值表 命题变元用特定的命题来替代，这一过程称为对该命题变元进行的真值指派（赋值

18、或解释）命题公式可以看成是一个以真假值为定义域和以真假值为值域的一个函数。可以写成:例：公式P(QR)定义三元函数 Y=f(P，Q，R)=P(QR)【定义】在命题公式A中，对A的每一个赋值，就确定了A的一个真值，把它们汇列成表，称该表为命题公式A的真值表。,第一章：命题逻辑,【定义】若指定的指派使A的真值为T，则称这个指派为A的成真指派，若使A的真值为F，则称这个指派为A的成假指派。构造真值表的步骤：找出给定命题公式中所有的命题变元，列出所有可能的指派；按照从低到高的顺序写出命题公式的各层次；对应每个指派，计算命题各个层次的值，直到最后计算出整个命题公式的值。,第一章：命题逻辑,例：构造命题公

19、式PQ的真值表，并求成真指派和成假指派。解：命题公式PQ的真值表如表1.7所示。00，01，11是成真指派，10是成假指派。,第一章：命题逻辑,例：构造命题公式(PQ)(PQ)的真值表，并求成真指派和成假指派。解：命题公式(PQ)(PQ)的真值表如表1.8所示。00，11是成真指派，01，10是成假指派。,注：n个命题变元组成的命题公式有 种真值情况,第一章：命题逻辑,2、等价公式【定义】对于任意两个公式A，B不论做何种指派，它们的真值均相同，则称A和B是等价的或逻辑相等的，记为AB。可以证明，命题公式等价有下面的三条性质：自反性，即对任意命题公式A，AA 对称性，即对任意命题公式A和B，若A

20、B，则BA 传递性，即对任意命题公式A，B和C，若AB，BC，则AC例：根据等价的定义，用真值表证明P(QP)P(PQ)证明：构造P(QP)和P(PQ)真值表，如表1.9所示。二者真值表相同，故等价,第一章：命题逻辑,基本等价式常叫命题定律，下面是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.排中律 A

21、A111.矛盾律 AA012.条件等价式 ABAB 13.双条件等价式 AB(AB)(BA)14.假言易位式 ABBA15.双条件否定等价式 ABAB,第一章：命题逻辑,以上共23个等价式，原则上说，这些公式都可以用真值表证明。下面仅验证德摩根律。【例】用真值表证明德摩根律(AB)AB解：表1.10是(AB)和AB的真值表，从表中可以看出德摩根律成立。,第一章：命题逻辑,【定义】如果X是命题公式A的一部分且X本身也是命题公式，则称X为公式A的子公式。例：例如，A=Q(P(PQ)，X=PQ，则X是A的子公式。【定理】设X是命题公式A的子公式，若XY，如果将A中的X用Y来置换，得到的公式记为B，则

22、B与A等价，即AB 证明：对A、B的任一赋值，X与Y的真值相同，而A、B的其它部分完全相同，公式B与公式A的真值必相同，故AB。满足此定理的置换叫做等价置换（等价代换）,第一章：命题逻辑,【例】用等价演算法证明 PQ(PQ)(PQ)证明：PQ(PQ)(QP)(双条件等价式)(PQ)(QP)(条件等价式)(PQ)(PP)(QQ)(QP)(分配律)(PQ)00(QP)(矛盾律)(PQ)(QP)(同一律)(PQ)(PQ)(交换律)PQ(PQ)(PQ)(等价的传递性),第一章：命题逻辑,1.5 重言式与蕴含式1、重言式【定义】设公式A中有n个不同的原子变元（n为正整数）该变元组的任意一组确定的值 称为

23、A关于 的一个完全指派，其中 或为T，或为F。如果对A中的部分变元赋以确定的值，其余的变元没有赋以确定的值，则这样的一组值称为公式A的关于变元组的部分指派。【定义】如果一个命题公式所有的完全指派均为成真指派，则该命题公式称为重言式或永真式；如果一个命题公式所有的完全指派均为成假指派，则该命题公式称为矛盾式或永假式；如果一命题公式不是永假式，则为可满足式。显然，重言式的真值表的最后一列全为1，矛盾式的真值表的最后一列全为0，可满足的公式真值表的最后一列至少有一个1。,第一章：命题逻辑,【例】用等价演算法判断下列公式的类型。Q(PQ)P)(PP)(Q Q)R)(PQ)P 解：Q(PQ)P)Q(PP

24、)(QP)(分配律)Q(0(QP)(矛盾律)Q(QP)(同一律)Q(QP)(德摩根律)(QQ)P(结合律)1P(排中律)1(零律)由此可知，为永真式。,第一章：命题逻辑,(PP)(QQ)R)1(QQ)R)(排中律)1(0R)(矛盾律)10(零律)0(条件联结词的定义)由此可知，为永假式。(PQ)P(PQ)P(条件等价式)P(吸收律)由此可知，是可满足式。,第一章：命题逻辑,【定理1.5.1】任何两个重言式的合取或析取都是重言式。证明：设A、B是重言式，对A和 B的任何赋值，总有A为1，B为1，所以 AB1，AB1，故AB和AB都是重言式。【推论】任何两个矛盾式的合取或析取是矛盾式。【定理1.5

25、.2】一个重言式，对同一分量出现的每一处都用同一合式公式置换，其结果仍是重言式。证明：由于重言式 的真值与分量的指派无关，故对于同一分量以任何公式置换后，重言式的真值仍永为T。,第一章：命题逻辑,【例】证明(PQ)R)(PQ)R)为重言式。证明：由排中律知PP为重言式，以(PQ)R)去置换其中的P，得公式(PQ)R)(PQ)R)，根据定理，这是重言式。【定理1.5.3】设A、B为两个命题公式，AB当且仅当AB是重言式。证明：设AB，下证AB是重言式。给A，B的任何赋值，因为AB，所以A，B具有相同的真值，由双条件联结词的定义知AB为真，所以AB为重言式。设AB为重言式，下证AB 给A，B的任何

26、赋值，因为AB为重言式，故A，B的真值相同，由命题公式等价的定义知AB,第一章：命题逻辑,2、蕴含式【定义】设A和B是命题公式，若AB是重言式式，记为AB。说明：“AB”读作“A永真蕴含B”，“A蕴含B”,“A能推得B”，“”是关系符，AB不为命题公式根据定义可以用真值表或等价演算证明AB。证明AB的另外两种方法：对A指定真值1，若由此推出B的真值不为0，而为1，则AB是重言式，即AB。对B指定真值0，若由此推出A的真值不为1，而为0，则AB是重言式，即AB。,第一章：命题逻辑,【例】推证P(PQ)Q 解：证法1：假定P(PQ)为1，则P为1且PQ为1，则P为0且PQ为1，则Q为1。所以 P(

27、PQ)Q 证法2：假定Q为0，则P可以为1或0。当P为1时，P为0，所以P(PQ)为0。当P为0时，(PQ)为0，所以P(PQ)为0。故 P(PQ)Q,第一章：命题逻辑,蕴含式是逻辑推理的重要工具。下面是一些重要的蕴含式。它们都可以用上述两种方法证明，其中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)

28、(CD)(AC),第一章：命题逻辑,等价式和蕴含式有下面的关系。【定理】设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 再由双条件等价式得(AB)(AB)(BA)1 即AB为重言式，故有AB。,第一章：命题逻辑,根据此定理，以前学过的所有等价式都可以作两个蕴含式来使用。例如吸收律A(AB)A可以作两个蕴含式A(AB)A和AA(AB)来使用

29、。【定理】设A、B、C为合式公式。AA(即蕴含是自反的)若AB且A为重言式，则B必为重言式。若AB且BC，则AC(即蕴含是传递的)若AB且AC，则ABC 若AB且CB，则ACB 若AB，C是任意公式，则 ACBC 证明：仅证明。因为AB，CB,所以AB1，CB1(AC)B(AC)B(AC)B(AB)(CB)(AB)(CB)111由等价的传递性，(AC)B1，故ACB,第一章：命题逻辑,1.6 其它联接词设P和Q是两个命题，复合命题PQ称作P和Q的不可兼析取，也叫异或。定义为：PQ为T当且仅当P和Q的真值不相同时。联结词“”称为异或联结词。,联结词“”的真值表如表1.11所示。“”也可以看成逻辑

30、运算，它是二元逻辑运算。它在程序设中有广泛的应用。不可兼析取有下列的性质：PQQ P(交换律),P,Q,(PQ)RP(QR)(结合律),第一章：命题逻辑,P(QR)(PQ)(PR)(合取对异或的分配律)PQ(PQ)(PQ)PQ(PQ)PP0，0PP，1PP【定理】设P，Q，R为命题公式，如果PQR，则P RQ，QRP，PQ R为一矛盾式。证明：P R P PQ 0 Q Q QR P R R P 0 P PQ R PP 0,第一章：命题逻辑,【定义】设p和Q是两个命题，复合命题PQ称作P和Q的与非。定义为：当且仅当P和Q真值都是真时，PQ才为假。联结词“”称为与非联结词。,联结词“”的真值表如表

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

32、设S是一个联结词集合，如果任何n(n1)个变元组成的公式，都可以由S中的联结词来表示，则称S是全功能联结词集。根据命题公式的定义，是全功能联结词集。利用下列3个等价式可将任何命题公式中的命题联结词“”、“”和“”去掉。PQ(PQ)；PQ(PQ)；PQ(PQ)所以，是全功能联结词集。利用下列2个等价式可将任何命题公式中的命题联结词“”和“”去掉。PQPQ；PQ(PQ)(QP)(PQ)(Q P)所以，是全功能联结词集。用德摩根律可证明，和，是全功能联结词集。可以证明，的任何子集都不是全功能联结词集。,第一章：命题逻辑,【定义】设S是全功能联结词集，如果去掉其中的任何 联结词后，就不是全功能联结词集

33、，则称S是最小全功能联结词集。可以证明，是最小全功能联结词集。现在讨论，n个命题变元可以构成多少个不等价的命题公式。两个命题变元可以构成多少个不等价的命题公式？由等价的概念知道，等价的命题公式有相同的真值表，所以上述问题就转化为两个命题变元构成的命题公式有多少个不同的真值表？,第一章：命题逻辑,两个命题变元构成的命题公式的真值表的格式如表1.14所示。真值表中每行公式的真值都有1，0两种可能，所以命题公式的真值有2222=16种可能，既有 个不同的真值表。故有 种不等价的公式。,三个变元可构成=个不等价的命题公式，n个变元可构成 个不等价的命题公式。,第一章：命题逻辑,1.7 对偶与范式1、对

34、偶 从前面介绍的命题定律中可以看出，很多常用等价式是成对出现的，只要将其中的“”和“”分别换成“”和“”，就可以由一个得到另一个。例如，将命题定律(AB)CA(BC)中的“”换成“”就得到了命题定律(AB)CA(BC)。这些成对出现的等价式反映了等价的对偶性。本节介绍对偶式和对偶原理。【定义】在仅含联结词，的命题公式A中，将联结词，F，T分别换成，T，F所得的公式称为公式A的对偶式，记为A*。设A*是A的对偶式，将A*中的，F，T分别换成，T，F，就会得到A。即A 是A*的对偶式，(A*)*A。所以说A*和A互为对偶式。,第一章：命题逻辑,【例】求PQ和PQ的对偶式。解：PQ(PQ)(PQ)的

35、对偶式是(PQ)PQ 故PQ的对偶式是PQ；同样的方法可以证明PQ的对偶式是PQ。根据上例，对偶式概念可以推广为：在仅含有联结词，的命题公式中，将联结词，F，T分别换成，T，F，就得到了它的对偶式。关于对偶式有以下两个结论。【定理1】设A*是A的对偶式，P1，P2，Pn是出现在A和A*中的原子变元，则 A(P1，P2，Pn)A*(P1，P2，Pn)A(P1，P2，Pn)A*(P1，P2，Pn),第一章：命题逻辑,【例】设命题公式A(P,Q,R)(PQ)R，试用此公式验证定理1的有效性。证明：验证 A(P,Q,R)A*(P,Q,R)A(P,Q,R)(PQ)R A(P,Q,R)(PQ)R)(PQ)

36、R A*(P,Q,R)(PQ)R A*(P,Q,R)(PQ)R所以，A(P,Q,R)A*(P,Q,R)验证 A(P,Q,R)A*(P,Q,R)A(P,Q,R)(PQ)R(PQ)R)A*(P,Q,R),第一章：命题逻辑,【定理 2】(对偶原理)设P1，P2，Pn是出现在公式A和B中的所有原子变元，如果AB，则A*B*证明：因为 AB所以 A(p1，p2，pn)B(p1，p2，pn)是重言式 在上述重言式中用pi置换 pi，i1,n，所得的公式仍为重言式，即 A(p1，p2，pn)B(p1，p2，pn)是重言式。所以 A(p1，p2，pn)B(p1，p2，pn)由定理1知 A*(p1，p2，pn)

37、B*(p1，p2，pn)即 A*B*由双条件否定等价式知 A*B*定理2叫做对偶原理。对偶原理是数理逻辑中最基本的规律之一。,第一章：命题逻辑,【例】证明重言式的对偶式是矛盾式，矛盾式的对偶式是重言式。证明：设A是重言式，即A1，因为1的对偶式是0，由对偶原理知A*0。所以A*是矛盾式；设A是矛盾式，即A0，而0的对偶式是1，所以A*1。所以A*是重言式。,第一章：命题逻辑,2、范式如何判断一个命题为永真式、永假式、可满足式或两个命题等价，归纳起来有三种方法：真值表法：对于变元的所有真值指派，看对应命题公式的值；命题演算法：化简命题至最简式，看是否存在和T等价，否则为可满足式；范式方法：本节所

38、介绍的内容,第一章：命题逻辑,2.1、析取范式与合取范式【定义】由一些命题变元或其否定构成的析取式称为基本和，也叫简单析取式。约定单个变元或其否定是基本和。例如，PQ、PQ、PQ、Q、P、Q都是基本和。【定义】由一些命题变元或其否定构成的合取式称为基本积，也叫简单合取式。约定单个变元或其否定是基本积。例如，PQ、PQ、PQ、P、Q、P都是基本积。【定义】由基本和的合取构成的公式叫做合取范式。约定单个基本和是合取范式。【定义】由基本积的析取构成的公式叫做析取范式。约定单个基本积是析取范式。任何命题公式都可以化成与其等价的析取范式或合取范式。求析取范式和合取范式的步骤如下：消去联结词“”和“”,第

39、一章：命题逻辑,利用双重否定律消去否定联结词“”或利用德摩根律将否定联结词“”移到各命题变元前(内移)。利用分配律，结合律将公式归约为合取范式和析取范式。【例】求命题公式(PQ)P的合取范式和析取范式。解：求合取范式(PQ)P(PQ)P)(P(PQ)(消去)(PQ)P)(P(PQ)(消去)(PQ)P)(P(PQ)(内移)(PP)(QP)(PPQ)(分配律，合取范式)1(QP)(1Q)(排中律)1(QP)1(零律，合取范式)(QP)(同一律，合取范式)由此例可以看出，公式的合取范式并不惟一。,第一章：命题逻辑,求析取范式(PQ)P(PQ)P)(PQ)P)(消去)(PQ)P)(PQ)P)(内移)P

40、(PQP)(吸收律，析取范式)P(PPQ)(交换律)P(PQ)(幂等律，析取范式)由此例可以看出，命题公式的析取范式也不惟一。,第一章：命题逻辑,2.2、主析取范式 由于析取范式和合取范式不惟一，所以使用起来很不方便。为此，引入主析取范式和主合取范式的概念。当命题变元的顺序约定以后，主析取范式和主合取范式是惟一的。析取范式和合取范式的基本成分是基本积和基本和，而主析取范式和主合取范式的基本成分是极小项和极大项，它们分别是特殊的基本积和基本和。【定义】在基本积中，每个变元及其否定不同时存在，但两者之一必须出现且仅出现一次，这样的基本积叫做叫小项或极小项。P，Q的极小项为：PQ，PQ，PQ，PQ

41、两个命题变元的极小项共4(=22)个,三个命题变元的极小项共8(=23)个,。一般地说，n个命题变元共有2n个极小项。,第一章：命题逻辑,表1.15是两个变元P和Q的极小项的真值表。极小项有下列的性质：每个极小项只有一个成真赋值，且各极小项的成真赋值互不相同。极小项和它的成真赋值构成了一一对应的关系。可用成真赋值为极小项进行编码，并把编码作为m的下标来表示该极小项，叫做该极小项的名称。两个命题变元的极小项、成真赋值和名称如表1.16所示。,第一章：命题逻辑,三个命题变元的极小项，成真赋值和名称如表1.17所示。从表1.16和表1.17中可以看出，极小项与其成真赋值的对应关系为：变元对应1，而变

42、元的否定对应0。,第一章：命题逻辑,第一章：命题逻辑,任意两个不同的极小项的合取式为永假式。例如：m001m100()()0全体极小项的析取式为永真式。记为：,m0m1 1,【定义】对于给定的命题公式，如果有一个它的等价公式，仅由极小项的析取组成，称该公式为原公式的主析取范式。任何命题公式都存在着与之等价的主析取范式。一个命题公式的主析取范式可以由以下两种方法求得：等价演算法：即用基本等价公式推出。,第一章：命题逻辑,用等价演算法求主析取范式的步骤如下：化归为析取范式。除去析取范式中所有永假的基本积。在基本积中，将重复出现的合取项和相同变元合并。在基本积中补入没有出现的命题变元，即添加(pp)

43、，再用分配律展开，最后合并相同的极小项。【例】用等价演算法求(PQ)(PR)(QR)的主析取范式。解：()()()()()()()()()()()()()()()()m111m110m011m001 m7m6m3m11，3，6，7,第一章：命题逻辑,真值表法：即用真值表求主析取范式。用真值表求主析取范式的步骤如下：构造命题公式的真值表。找出公式的成真赋值对应的极小项。这些极小项的析取就是此公式的主析取范式。【例】用真值表法，求()的主析取范式。解：表1.1是()的真值表，公式的成真赋值对应的极小项为：(成真赋值为001)(成真赋值为011)(成真赋值为100)(成真赋值为101)(成真赋值为1

44、11)()的主析取范式为：,第一章：命题逻辑,()()()(Q)()m111m101m100m011m001m7m5m4m3m1 1，3，4，5，7,第一章：命题逻辑,矛盾式无成真赋值，因而主析取范式不含任何极小项，将矛盾式的主析取范式记为0。而重言式无成假赋值，因而主析取范式含2n(n为公式中命题变元的个数)个极小项。至于可满足式，它的主析取范式中极小项的个数一定小于或等于2n。,第一章：命题逻辑,2.3、主合取范式【定义】在基本和中，每个变元及其否定不同时存在，但两者之一必须出现且仅出现一次，这样的基本和叫大项或极大项。两个变元，构成的极大项为：，三个命题变元，构成的极大项为：，q，两个命

45、题变元的极大项共4(=22)个,三个命题变元的极大项共8(=23)个,。一般地说，n个变元共有2n个极大项。极大项有下列三个性质：每个极大项只有一个成假赋值，极大项不同，成假赋值也不同。极大项和它的成假赋值构成了一一对应的关系。故可用成假赋值为该极大项进行编码，并把编码作为M的下标来表示该极大项，叫做极大项的名称。,第一章：命题逻辑,例如，两个变元，的极大项，它的成假赋值是11，表示为M11，把11理解为2进制数，它的10进制表示为3，所以M 11又表示为M3。,两个命题变元的极大项，成假赋值及名称见表1.19，三个命题变元的极大项，成假赋值及名称见表1.20,从表1.19和表1.20中可以看

46、出，极大项与成假赋值的对应关系为：变元对应0，而变元的否定对应1。任意两个不同的极大项的析取式为永真式。全体极大项的合取式为永假式。记为：,第一章：命题逻辑,M0M1,0,第一章：命题逻辑,【定义】对于给定的命题公式，如果有一个它的等价公式，仅由极大项的合取组成，则该等价式称为原公式的主合取范式。任何命题公式都存在着与之等价的主合取范式。主合取范式也可以由以下两种方法求得。等价演算法：即用基本等价公式推出。其演算步骤如下：化归为合取范式。除去所有永真的基本和。在基本和中合并重复出现的析取项和相同的变元。在基本和中补入没有出现的命题变元。即增加(PP)，然后，应用分配律展开公式，最后合并相同的极

47、大项。【例】用等价演算法求(PQ)R的主合取范式。解：(PQ)R,第一章：命题逻辑,(PQ)R(PQ)R(PR)(QR)(PR(QQ)(QR(PP)(PRQ)(PRQ)(PQR)(PQR)(PQR)(PQR)(PQR)M000M010M110M0M2M60，2，6 真值表法：用真值表求主合取范式。用真值表求主合取范式的步骤如下：构造命题公式的真值表。找出公式的成假赋值对应的极大项。这些极大项的合取就是此公式的主合取范式。【例】用真值表法求(PQ)R的主合取范式。解：(PQ)R的真值表是表1.18。公式的成假赋值对应的大项为：PQR(成假赋值为000)PQR(成假赋值为010),第一章：命题逻辑

48、,PQR(成假赋值为110)主合取范式为：(PQR)(PQR)(PQR)M000M010M110M0M2M60，2，6 矛盾式无成真赋值，因而矛盾式的主合取范式含2n(n为公式中命题变元的个数)个极大项。而重言式无成假赋值，因而主合取范式不含任何极大项。将重言式的主合取范式记为1。至于可满足式，它的主合取范式中极大项的个数一定小于2n。我们已经通过例子求出(PQ)R的主析取范式为：m7m5m4m3m11，3，4，5，7(PQ)R的主合取范式为：M0M2M60，2，6 比较这两个结果，得出以下的结论：同一公式的主析取范式中m的下标和主合取范式中M的下标是互补的。因此，知道了主析(合)取范式就可以

49、写出主合(析)取范式。,第一章：命题逻辑,1.8 推理理论 数理逻辑的主要任务是用逻辑的方法研究数学中的推理。所谓推理是指从前提出发，应用推理规则推出结论的思维过程。任何一个推理都由前提和结论两部分组成。前提就是推理所根据的已知命题，结论则是从前提出发通过推理而得到的新命题。要研究推理，首先应该明确什么样的推理是有效的或正确的。【定义】设A1，A2，An和C是n+1个命题公式，若A1A2AnC，则称C为A1，A2，An 的有效结论。也称C可由A1，A2，An 逻辑的推出。A1，A2，An叫做C的一组前提。A1A2AnC，亦可记为A1，A2，AnC。由【定义】可以看出，要证明C是一组前提A1，A

50、2，An 的有效结论，只需证明A1A2AnC为重言式。证明一个公式为重言式，可以用真值表、等价演算、主析(合)取范式或已,第一章：命题逻辑,知的蕴含式等方法进行。用等价演算和主析(合)取范式证明重言式的方法前面已经讨论过了，我们已经非常熟悉了。这里仅对真值表法作简单说明。用真值表证明有效结论有以下两种方法：用全真值表证明 要证明C为前提A1，A2，An 的有效结论，只需构造命题公式A1A2AnC的真值表，证明它是重言式。用部分真值表证明 因为条件命题A1A2AnC为假当且仅当它的前件A1A2An为真，后件C为假。只要能排除前件为真，后件为假的情况，A1A2AnC就是重言式。从而C为一组前提A1