离散数学电子教案.ppt

《离散数学电子教案.ppt》由会员分享，可在线阅读，更多相关《离散数学电子教案.ppt（87页珍藏版）》请在三一办公上搜索。

1、课程性质,Discrete Math.离散数学 研究离散对象及其相互间关系的一门数学学科。研究离散结构的数学分支。（辞海）,计算机科学、信息科学、数字化科学的数学基础,离散数学主要内容,命题逻辑 谓词逻辑 集 合 二元关系 函 数 代数系统 群、环和域 格与布尔代数 图 论,数理逻辑(Mathematics Logic),集合论(Sets),代数结构（或代数系统）(Algebra Structure),图论(Graph Theory),哥尼斯堡七桥问题,哈密尔顿周游世界问题,四色定理,离散数学课程设置：计算机系核心课程 信息类专业必修课程 其它类专业的重要选修课程,离散数学的后继课程：数据结构

2、、编译技术、算法分析与设计、人工智能与机器人、数据库、网络和计算机图形学,教材及参考书,左孝凌等，离散数学，上海科学技术文献出版社，1982同济大学应用数学系离散数学编写组，离散数学，统计大学出版社，2003,第1章 命题逻辑,逻辑学：研究思维形式及思维规律的科学。,逻辑学,辩证逻辑：以辩证法的世界观为基础的逻辑学。,形式逻辑：对思维的形式结构和规律进行研究的类似于语法的一门工具性学科。,思维的形式结构,概念：思维的基本单位。,判断：通过概念对事物是否具有某种属性进行肯定或否定的回答。,推理：由一个或几个判断推出另一判断的思维形式。,数理逻辑：用数学方法来研究推理的规律。,数理逻辑包括逻辑演算

3、、证明论、公理集合论、模型论和递归论。本课程只介绍逻辑演算中的命题逻辑和谓词逻辑。,17世纪中叶：德国数学家莱布尼茨()创立。英国数学家布尔(G.Boole)：布尔代数德国数学家弗雷格()：量词与约束变元美国数学家歌德尔(K.Godel)：完全性定理意大利数学家皮亚诺(G.Peano)英国数学家德摩根(A.DeMorgen)、罗素()。,所谓的数学方法，就是引进一套符号体系的方法，所以数理逻辑又称为符号逻辑。,第1章 命题逻辑 1.1命题及联结词 1.1.1 命题的基本概念 在数理逻辑中把能判断真假的陈述句称为命题。一般用小写英文字母或小写英文字母带下标表示。,命题的概念包含了以下3个要素：只

4、有陈述句才有可能成为命题，而其它的语句，如：感叹句、祈使句、疑问句等都不是命题。,一个语句虽是陈述句,但不能判断真假不是命题。,虽然要求命题能判断真假，但不要求现在就能确定真假，将来可以确定真假也可以。,一个命题表达的判断结果称为命题的真值。命题的真值有“真”和“假”两种，分别用True、T、1(真)和False、F、0(假)来表示。真值为真的命题称为真命题，真值为假的命题称为假命题。任何命题的真值是唯一的。,在命题逻辑中对命题不再细分，因而命题是命题逻辑中最基本的也是最小的研究单位。,【例1.1】判断以下语句是否为命题。若是命题，确定其真值。上海是个小村庄。存在外星人。禁止吸烟！北京是中国的

5、首都。4是素数或6是素数。今天你吃了吗？11+1=100 我正在说谎。,命题(F),命题(待定),不是命题(祈使句),命题(T),命题(F),不是命题(疑问句),命题(由上下文确定),不是命题(悖论),表示命题的小写英文字母或带下标的小写英文字母常称为命题标识符。如果命题标识符表示一个具体、确定的命题，称为命题常元。如果命题标识符表示任意一个命题，称为命题变元。命题变元无确定的真值。,命题是能判断真假的陈述句。而命题变元代表任意的命题，其真值是不确定的。因而不是命题。,如果一个命题不能再分解成更简单的命题，则称该命题为原子命题。如果一个命题不是原子命题，称该命题为复合命题。如果命题变元表示原子

6、命题时，该命题变元称为原子变元。,在自然语言中，可以通过“如果，那么”，“不但，而且”这样的连词将简单的陈述句联结成复合语句，同样在命题逻辑当中，也可以通过命题联结词将原子变元联结起来表示复合命题。,1.1.2 命题联结词 常用的逻辑联结词有五种：否定联结词、合取联结词、析取联结词、条件联结词和双条件联结词。,p和p的关系如表1.1所示，表1.1叫做否定联结词“”的真值表(下同)。,联结词“”也可以看作逻辑运算，它是一元运算。【例1.2】否定下列命题。p：王强是一名大学生。,p：王强不是一名大学生。,1.否定联结词 定义1.1.1 设p为命题，则p的否定是一个复合命题，记作：p，读作“非p”或

7、“p的否定”。定义为：若P为T，则p为F；若p为F，则p的真值为T。,2.合取联结词 定义设p和q均为命题，则p和q的合取是一个复合命题，记作pq，读作“p与q”或“p合取q”。定义为：当且仅当p和q均为T时，pq的才为T。联结词“”的真值表如表1.2所示。联结词“”也可以看成逻辑运算，它是二元逻辑运算。,【例1.3】设 p：2008年北京举办了奥运会。q：中国是世界四大文明古国之一。,则pq：2008年北京举办了奥运会并且中国是世界四大文明古国之一。,3.析取联结词 定义1.1.3 设p和q均为命题，则p和q的析取是一个复合命题，记作pq，读作“p或q”或者“p析取q”。定义为：当且仅当p和

8、q均为F时，pq才为F。联结词“”的真值表如表1.3所示。联结词“”也可以看成逻辑运算，它是二元逻辑运算。,“”与汉语中的“或”相似，但又不相同。汉语中的或有可兼或与不可兼或(排斥或)的区分。,【例1.4】我今天在电视上看这场杂技或在剧场里看这场杂技。灯泡有故障或开关有故障。,4.条件联结词 定义1.1.4 设p和q均为命题，其条件命题是个复合命题，记为：pq。读作“如果p，那么q”或“若p，则q”。定义为：当且仅当p为T，q为F时，pq才为F。p称为条件命题pq的前件，q称为条件命题pq的后件。联结词“”真值表如表1.4所示。联结词“”也可以看成逻辑运算，它是二元逻辑运算。,【例1.5】p：

9、小王努力学习。q：小王学习成绩优秀。,pq：如果小王努力学习，那么他的学习成绩就优秀。,联结词“”与汉语中的“如果，那么”或“若，则”相似，但又是不相同的。(“”可不顾及前因后果),5.双条件联结词 定义设p和q均为命题，其复合命题pq称为双条件命题，读作：“p双条件q”或者“p当且仅当q”。定义为：当且仅当p和q的真值相同时，pq为T。联结词“”的真值表如表1.5所示。联结词“”也可以理解成逻辑运算，它是二元逻辑运算。,双条件联结词表示的是一个充分必要关系，与前面所述相同，也可以不必顾及其前因后果，而只根据联结词的定义来确定其真值。,【例1.6】设p：张华是三好学生。q：张华德、智、体全优秀

10、。,pq：张华是三好学生当且仅当德、智、体全优秀。,1.2 命题公式与翻译 把命题常量，命题变量按照一定的逻辑顺序用命题联结词连接起来就构成了命题演算的合式公式，也叫命题公式。当使用联结词集，时，合式公式定义如下：,定义按下列规则构成的符号串称为命题演算的合式公式，也称为命题公式，简称公式。,单个命题变元和常元是合式公式。,如果A是合式公式，那么A是合式公式。,如果A和B是合式公式，那么(AB)、(AB)、(AB)和(AB)是合式公式。,当且仅当有限次地应用了、所得到的符号串是合式公式。,命题公式一般的用大写的英文字母A，B，C，表示。依照这个定义，下列符号串是合式公式：,(pq)，(pq)，

11、(p(pq)，(pq)(qr)(st),下列符号串不是合式公式：(pq)(q)，(pq，(pq)q),定义给出合式公式定义的方法称为归纳定义，它包括三部分：基础，归纳和界限。定义中的是基础，和是归纳，是界限。下文中还将多次出现这种形式的定义。,为方便起见，对命题公式约定如下：最外层括号可以省略。规定联结词的优先级由高到低依次为，。按此优先级别，如果去掉括号，不改变原公式运算次序，也可以省掉这些括号。,一般地说，命题公式中包含命题变元，因而无法计算其真值，所以不是命题。命题公式中的命题变元，也叫命题公式的分量。,有了命题公式的概念，就可以用命题公式表示复合命题，常将这个过程称为命题的符号化。命题

12、的符号化可按如下步骤进行：,找出复合命题中的原子命题。用小写的英文字母或带下标的小写的英文字母表示这些原子命题。使用命题联结词将这些小写的英文字母或带下标的小写的英文字母连接起来。,【例1.7】将下列命题符号化：他今天上午或者骑自行车去学校，或者乘公共汽车去学校。,解：令 p：他今天上午骑自行车去学校。q：他今天上午乘公共汽车去学校。,此命题中的或是不可兼或，所以不能符号化为：pq。而要符号化为：(pq)或(pq)(pq)。,1.3真值表和等价公式 命题公式的真值表 定义 设pl，p2，pn是出现在公式A中的全部命题变元，给pl，p2，pn各指定一个真值，称为对公式A的一个赋值或解释。若指定的

13、赋值使A的真值为T，则称这个赋值为A的成真赋值，若使A的真值为F，则称这个赋值为A的成假赋值。,例如，给公式(pqr)赋值011是指p=0，q=1，r=1，它是该公式的成真赋值；赋值110是指p=1，q=1，r=0，它是该公式的成假赋值。,定义1.3.2 在命题公式A中，对A的每一个赋值，就确定了A的一个真值，把它们汇列成表，称该表为命题公式A的真值表。,【例1.8】构造命题公式pq的真值表，并求成真赋值和成假赋值。,【例1.9】构造命题公式(pq)(pq)的真值表，并求成真赋值和成假赋值。,解：命题公式(pq)(pq)的真值表如表1.7所示。00，11是成真赋值，01，10是成假赋值。,命题

14、公式的等价 定义1.3.3 设A和B是两个命题公式，对A和B的任一赋值，A和B的真值都相同，则称A和B是等价的或逻辑相等的，记为AB,可以证明，命题公式等价有下面的三条性质：自反性，即对任意命题公式A，AA 对称性，即对任意命题公式A和B，若AB，则BA 传递性，即对任意命题公式A，B和C，若AB，BC，则AC,根据定义，可以用真值表证明命题公式是等价的，请看下面的例题。,【例1.12】根据等价的定义，用真值表证明 p(qp)p(pq),证明：构造p(qp)和p(pq)的真值表，如表1.10所示。p(qp)和p(pq)所在的列完全相同，它们具有相同的真值表。所以p(qp)p(pq),证明等价的

15、另外一种方法叫做等价演算法，其基本思想是：先用真值表证明一组基本等价式，以它们为基础进行公式之间的演算。基本等价式常叫命题定律。下面是常用的命题定律。1.双重否定律 AA 2.交换律 ABBA，ABBA 3.结合律(AB)CA(BC)(AB)CA(BC),4.分配律 A(BC)(AB)(AC)A(BC)(AB)(AC)5.德摩根律(AB)AB(AB)AB 6.幂等律 AAA，AAA,7.吸收律 A(AB)A，A(AB)A 8.零律 A11，A00 9.同一律 A0A，A1A 10.排中律 AA1 11.矛盾律 AA0 12.条件等价式ABAB 13.双条件等价式AB(AB)(BA)14.假言易

16、位式ABBA 15.双条件否定等价式 ABAB,以上共23个等价式，原则上说，这些公式都可以用真值表证明。下面仅验证德摩根律。【例1.13】用真值表证明德摩根律(AB)AB 解：表1.11是(AB)和AB的真值表，从表中可以看出德摩根律成立。,定义如果X是合式公式A的一部分且X本身也是合式公式，则称X为公式A的子公式。例如，Aq(p(pq)，Xpq，则X是A的子公式。,定理1.3.1 设X是合式公式A的子公式，若XY，如果将A中的X用Y来置换，得到的公式记为B，则B与A等价，即AB,证明：对A、B的任一赋值，X与Y的真值相同，而A、B的其它部分完全相同，公式B与公式A的真值必相同。AB 满足此

17、定理的置换叫做等价置换。,【例1.17】用等价演算法证明 pq(pq)(pq),证明：pq(pq)(qp)(双条件等价式),(pq)(qp)(条件等价式),(pq)(pp)(qq)(qp)(分配律),(pq)00(qp)(矛盾律),(pq)(qp)(同一律),(pq)(pq)(交换律),pq(pq)(pq)(等价的传递性),1.4重言式 定义 设A是任一命题公式。若对A的任意赋值，其真值永为真，则称命题公式A为重言式或永真式。若对A的任意赋值，其真值永为假，则称命题公式A为矛盾式或永假式。若A不是矛盾式，则称命题公式A为可满足式。,由定义可以看出，任何重言式都是可满足式。显然，重言式的真值表的

18、最后一列全为1，矛盾式的真值表的最后一列全为0，可满足的公式真值表的最后一列至少有一个1。根据这个结论借助于真值表可以判断一个公式是否为重言式，矛盾式或可满足的。当然也可以用等价演算法判断公式的类型。,【例1.18】用等价演算法判断下列公式的类型。q(pq)p),解：q(pq)p),q(pp)(qp)(分配律),q(0(qp)(矛盾律),q(qp)(同一律),q(qp)(德摩根律),(qq)p(结合律),1p(排中律),1(零律)由此可知，为重言式。,(pp)(qq)r),1(qq)r)(排中律),1(0r)(矛盾律),10(零律),0(条件联结词的定义),由此可知，为矛盾式。,(pq)p,(

19、pq)p(条件等价式),p(吸收律)由此可知，是可满足式。,定理 任何两个重言式的合取或析取都是重言式。,证明：设A、B是重言式，对A和 B的任何赋值，总有A为1，B为1，所以 AB1，AB1，故AB和AB都是重言式。,推论 任何两个矛盾式的合取或析取是矛盾式。,定理 一个重言式，对同一分量出现的每一处都用同一合式公式置换，其结果仍是重言式。,推论：一个矛盾式，对同一分量出现的每一处都用同一合式公式置换，其结果仍是矛盾式。,【例1.19】利用定理证明(pq)r)(pq)r)为重言式。,证明：由排中律知pp为重言式，以(pq)r)去置换其中的p，得公式(pq)r)(pq)r)，根据定理，这是重言

20、式。,定理 设A、B为两个命题公式，AB当且仅当AB是重言式。,证明：设AB，下证AB是重言式。给A，B的任何赋值，因为AB，所以A，B具有相同的真值，由双条件联结词的定义知AB为真，所以AB为重言式。,设AB为重言式，下证AB 给A，B的任何赋值，因为AB为重言式，故A，B的真值相同，由命题公式等价的定义知AB,作业,判断下列命题公式的类型1）(PQ)(QP)2)(QP)(PQ)3)(PQ)R)P4)(PQ)P5)(PP)P,1.5范式 析取范式与合取范式 定义由一些命题变元或其否定构成的析取式称为基本和，也叫简单析取式。约定单个变元或其否定是基本和。,例如，pq、pq、pq、q、p、q都是

21、基本和。,定义由一些命题变元或其否定构成的合取式称为基本积，也叫简单合取式。约定单个变元或其否定是基本积。例如，pq、pq、pq、p、q、p都是基本积。,定义由基本和的合取构成的公式叫做合取范式。约定单个基本和是合取范式。,定义由基本积的析取构成的公式叫做析取范式。约定单个基本积是析取范式。,1)基本和和基本积既是析取范式，又是合取范式。,2)析取范式和合取范式都仅含联结词,。,利用双重否定律消去否定联结词“”或利用德摩根律将否定联结词“”移到各命题变元前(内移)。,利用分配律，结合律将公式归约为合取范式和析取范式。,任何命题公式都可以化成与其等价的析取范式或合取范式。求析取范式和合取范式的步

22、骤如下：,消去联结词“”和“”,【例1.21】求命题公式(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(pqp)(吸收律),p(ppq)(交换律),p(pq)(幂等律，析取范式),由此例可以看出，命题公式的析取范式也不惟一。,析取范式,析取范式,主析取范式 由于

23、析取范式和合取范式不惟一，所以使用起来很不方便。为此，引入主析取范式和主合取范式的概念。当命题变元的顺序约定以后，主析取范式和主合取范式是惟一的。,析取范式和合取范式的基本成分是基本积和基本和，而主析取范式和主合取范式的基本成分是极小项和极大项，它们分别是特殊的基本积和基本和。,p，q的极小项为：pq，pq，pq，pq,定义在基本积中，每个变元及其否定不同时存在，但两者之一必须出现且仅出现一次，这样的基本积叫做布尔合取也叫小项或极小项。,表1.12是两个变元p和q的极小项的真值表。极小项有下列的性质：,两个命题变元的极小项共4(=22)个,三个命题变元的极小项共8(=23)个,。一般地说，n个

24、命题变元共有2n个极小项。,每个极小项只有一个成真赋值，且各极小项的成真赋值互不相同。极小项和它的成真赋值构成了一一对应的关系。可用成真赋值为极小项进行编码，并把编码作为m的下标来表示该极小项，叫做该极小项的名称。,两个命题变元的极小项、成真赋值和名称如表1.13所示。,三个命题变元的极小项，成真赋值和名称如表1.14所示。,从表1.13和表1.14中可以看出，极小项与其成真赋值的对应关系为：变元对应1，而变元的否定对应0。,任意两个不同的极小项的合取式为永假式。例如：m001m100(pqr)(pqr)pqrpqr0,定义1.5.6 对于给定的命题公式，如果有一个它的等价公式，仅由极小项的析

25、取组成，称该公式为原公式的主析取范式。,m0m1 1,任何命题公式都存在着与之等价的主析取范式。一个命题公式的主析取范式可以由以下两种方法求得：等价演算法：即用基本等价公式推出。,全体极小项的析取式为永真式。记为：,用等价演算法求主析取范式的步骤如下：,【例1.22】用等价演算法求(pq)(pr)(qr)的主析取范式。解：(pq)(pr)(qr),(pq(rr)(pr(qq)(qr(pp),(pqr)(pqr)(pqr)(pqr)(pqr)(pqr),(pqr)(pqr)(pqr)(pqr),m111m110m011m001,m7m6m3m11，3，6，7,在基本积中补入没有出现的命题变元，即

26、添加(pp)，再用分配律展开，最后合并相同的极小项。,化归为析取范式。,除去析取范式中所有永假的基本积。,在基本积中，将重复出现的合取项和相同变元合并。,真值表法：即用真值表求主析取范式。用真值表求主析取范式的步骤如下：构造命题公式的真值表。找出公式的成真赋值对应的极小项。这些极小项的析取就是此公式的主析取范式。,【例1.24】用真值表法，求(pq)r的主析取范式。解：表1.15是(pq)r的真值表，公式的成真赋值对应的极小项为：pqr(成真赋值为001)pqr(成真赋值为011)pqr(成真赋值为100)pqr(成真赋值为101)pqr(成真赋值为111)(pq)r 的主析取范式为：,(pq

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

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

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

30、1.25】用等价演算法求(pq)r的主合取范式。解：(pq)r,(pq)r(pq)r(pr)(qr),(pr(qq)(qr(pp),(prq)(prq)(pqr)(pqr),(pqr)(pqr)(pqr),M000M010M110M0M2M60，2，6,真值表法：用真值表求主合取范式。用真值表求主合取范式的步骤如下：构造命题公式的真值表。找出公式的成假赋值对应的极大项。这些极大项的析取就是此公式的主合取范式。,【例1.26】用真值表法求(pq)r的主合取范式。,解：(pq)r的真值表是表1.15。公式的成假赋值对应的大项为：pqr(成假赋值为000)pqr(成假赋值为010),pqr(成假赋值

31、为110)主合取范式为：(pqr)(pqr)(pqr)M000M010M110M0M2M60，2，6,矛盾式无成真赋值，因而矛盾式的主合取范式含2n(n为公式中命题变元的个数)个极大项。而重言式无成假赋值，因而主合取范式不含任何极大项。将重言式的主合取范式记为1。至于可满足式，它的主合取范式中极大项的个数一定小于2n。,在例1.23和例1.24中求出(pq)r的主析取范式为：m7m5m4m3m11，3，4，5，7 在例1.25和例1.26中求出该公式的主合取范式为：M0M2M60，2，6 比较这两个结果，得出以下的结论:,同一公式的主析取范式中m的下标和主合取范式中M的下标是互补的。因此，知道

32、了主析(合)取范式就可以写出主合(析)取范式。,1.6 全功能联结词集 定义1.6.1 设p和q是两个命题，复合命题p q称作p和q的不可兼析取，也叫异或。定义为：p q为T当且仅当p和q的真值不相同时。联结词“”称为异或联结词。,p,q,不可兼析取有下列的性质：p qq p(交换律),(p q)rp(q r)(结合律),联结词“”的真值表如表1.18所示。“”也可以看成逻辑运算，它是二元逻辑运算。它在程序设计中有广泛的应用。,p(q r)(pq)(pr)(合取对异或的分配律)p q(pq)(pq)p q(pq)p p0，0 pp，1 pp 定理1.6.1 设A，B，C为命题公式，如果A BC

33、，则A CB，B CA，A B C为一矛盾式。,定义 设p和q是两个命题，复合命题pq称作p和q的与非。定义为：当且仅当p和q真值都是真时，pq才为假。联结词“”称为与非联结词。,由定义可以看出下式成立：pq(pq),联结词“”的真值表如表1.19所示。“”也可以看成逻辑运算，它是二元逻辑运算。,联结词“”还有以下几个性质：,pp(pp)p,(pq)(pq),(pp)(qq),(pq),(pq),(pq),(p)(q),pq,pq,定义1.6.3 设p和q是两个命题，复合命题pq称作p和q的或非。定义为：当且仅当p、q的真值都为假时，pq的真值为真。联结词“”称为或非联结词。,联结词“”的真值

34、表如表1.20所示。“”也可以看成逻辑运算，它是二元逻辑运算。,由此定义可得到下面的公式：pq(pq),联结词还有下面的几个性质：pp(pp)p(pq)(pq)(pq)(pq)pq(pp)(qq)pq(pq)pq,至此已经学了8个联结词：，。类似于定义的方法，可以定义包含上述8个联结词的命题公式。,定义1.6.4 设S是一个联结词集合，如果任何n(n1)个变元组成的公式，都可以由S中的联结词来表示，则称S是全功能联结词集。,利用下列3个等价式可将任何命题公式中的命题联结词“”、“”和“”去掉。,根据命题公式的定义，是全功能联结词集。,p q(pq)pq(pq)pq(pq)所以，是全功能联结词集

35、。,利用下列2个等价式可将任何命题公式中的命题联结词“”和“”去掉。,用德摩根律可证明，和，是全功能联结词集。,可以证明，不是全功能联结词集。,定义1.6.5 设S是全功能联结词集，如果去掉其中的任何联结词后，就不是全功能联结词集，则称S是最小全功能联结词集。,pqpqpq(pq)(qp)(pq)(qp),所以，是全功能联结词集。,可以证明，是最小全功能联结词集。,两个命题变元构成的命题公式的真值表的格式如表1.21所示。,现在讨论，n个命题变元可以构成多少个不等价的命题公式。,两个命题变元可以构成多少个不等价的命题公式？,由等价的概念知道，等价的命题公式有相同的真值表，所以上述问题就转化为两

36、个命题变元构成的命题公式有多少个不同的真值表？,真值表中每行公式的真值都有1，0两种可能，所以命题公式的真值有2222=24=16种可能，既有 个不同的真值表。故有 种不等价的公式。,三个变元可构成28=个不等价的命题公式，n个变元可构成 个不等价的命题公式。,1.7 对偶式与蕰含式 对偶式 从1.3节的命题定律中可以看出，很多常用等价式是成对出现的，只要将其中的“”和“”分别换成“”和“”，就可以由一个得到另一个。例如，将命题定律(AB)C(A C)(B C)中的“”换成“”,“”换成“”就得到了命题定律(AB)C(AC)(B C)这些成对出现的等价式反映了等价的对偶性。本节介绍对偶式和对偶

37、原理。,定义在仅含联结词，的命题公式A中，将联结词，F，T分别换成，T，F所得的公式称为公式A的对偶式，记为A*。,设A*是A的对偶式，将A*中的，F，T分别换成,【例1.27】求pq和pq的对偶式。,解：pq(pq),(pq)的对偶式是(pq)pq,故pq的对偶式是pq；同样的方法可以证明pq的对偶式是pq。,根据例1.27，对偶式概念可以推广为：在仅含有联结词，的命题公式中，将联结词，F，T分别换成，T，F，就得到了它的对偶式。,关于对偶式有以下两个结论。定理1.7.1 设A*是A的对偶式，p1，p2，pn是出现在A和A*中的原子变元，则 A(p1，p2，pn)A*(p1，p2，pn)A(

38、p1，p2，pn)A*(p1，p2，pn),，T，F，就会得到A。即A 是A*的对偶式，(A*)*A。所以说A*和A互为对偶式。,【例1.28】设命题公式A(p,q,r)(pq)r，试用此公式验证定理的有效性。,证明：验证 A(p,q,r)A*(p,q,r),A(p,q,r)(pq)r,A(p,q,r)(pq)r)(pq)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),定理1.7.2(对偶原理)设p1，p2，pn是出现在公式A和B中的

39、所有原子变元，如果AB，则A*B*,根据定理，在上述重言式中用pi置换 pi，i1,n，所得的公式仍为重言式，即 A(p1，p2，pn)B(p1，p2，pn)是重言式。,所以 A(p1，p2，pn)B(p1，p2，pn),由定理1.7.1A*(p1，p2，pn)B*(p1，p2，pn),即:A*B*,由双条件否定等价式知 A*B*,定理叫做对偶原理。对偶原理是数理逻辑中最基本的规律之一。,证明：因为 AB所以 A(p1，p2，pn)B(p1，p2，pn)是重言式。,【例1.29】证明重言式的对偶式是矛盾式，矛盾式的对偶式是重言式。,证明：设A是重言式，即A1，因为1的对偶式是0，由对偶原理知A

40、*0。所以A*是矛盾式；设A是矛盾式，即A0，而0的对偶式是1，所以A*1。所以A*是重言式。,蕴含式 定义1.7.2 设A和B是命题公式，若AB是重言式，则称A蕴含B，记为AB。,根据定义可以用真值表或等价演算证明AB。,AB定义为：AB为重言式。又由条件命题的定义知，仅在AT，BF时，AB为假，其余情况都为真。故要证明AB，只需排除AT，BF的情况。于是就有了证明AB的第二种方法：,对A指定真值T，若由此推出B的真值不为F，而为T，则AB是重言式，即AB。对B指定真值F，若由此推出A的真值不为T，而为F，则AB是重言式，即AB。,【例1.31】推证p(pq)q 解：证法1：,证法2：假定q

41、为F，则p可以为T或F。,假定p(pq)为Tp为T且pq为Tp为F且pq为Tq为T。所以 p(pq)q,当p为T时，p为F，所以p(pq)为F。,当p为F时，(pq)为F，所以p(pq)为F。故 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.构造性二难(AC)(AB)(CD)BD

42、(AA)(AB)(AB)B 9.破坏性二难(BD)(AB)(CD)(AC),等价式和蕴含式有下面的关系。定理1.7.3 设A，B为任意两个命题公式，则AB的充分必要条件是AB且BA 证明：设AB，下证AB且BA 因为AB，所以ABT由双条件等价式得(AB)(BA)ABT因而AB与BA都是重言式，故有AB且BA。设AB且BA，下证AB。因为AB且BA，所以AB与BA都是重言式，重言式的合取也是重言式，即(AB)(BA)T再由双条件等价式得(AB)(AB)(BA)T即AB为重言式，故有AB。,根据此定理，以前学过的所有等价式都可以作两个蕴含式来使用。例如吸收律A(AB)A可以作两个蕴含式A(AB)

43、A和AA(AB)来使用。,证明：仅证明。因为AB，CB,所以ABT，CBT,(AC)B(AC)B(AC)B,(AB)(CB)(AB)(CB)TTT,由等价的传递性，(AC)BT，故ACB,定理 设A、B、C为合式公式。AA(即蕴含是自反的)若AB且A为重言式，则B必为重言式。若AB且BC，则AC(即蕴含是传递的)若AB且AC，则ABC 若AB且CB，则ACB 若AB，C是任意公式，则 ACBC,作业,求主合取范式和主析取范式1）(P Q)(P Q)2)Q(P Q)3)P(P(Q(Q R)4)(P(Q R)(P(Q R),1.8 命题逻辑的推理理论 数理逻辑的主要任务是用逻辑的方法研究数学中的推

44、理。所谓推理是指从前提出发，应用推理规则推出结论的思维过程。任何一个推理都由前提和结论两部分组成。前提就是推理所根据的已知命题，结论则是从前提出发通过推理而得到的新命题。要研究推理，首先应该明确什么样的推理是有效的或正确的。,定义1.8.1 设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，A2，An 的有效结论，只需证明A1A2AnC为重言式。,用真值表证明有效结论有以下两种方法：,证

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

46、A2，An都为真的行，若C也为真，则A1A2AnC，即C为前提A1，A2，An 的有效结论。,找出C为假的行，若在每个这样的行中，A1，A2，An的真值至少有一个为假，则A1A2AnC，即C为一组前提A1，A2，An 的有效结论。,【例1.32】分析事实：“如果我有时间，那么我就去上街；如果我上街，那么我就去书店买书；但我没有去书店买书，所以我没有时间。”。试指出这个推理前提和结论，并证明结论是前提的有效结论。,解：令 p：我有时间。q：我去上街。r：我去书店买书。,根据题意，前提为：pq，qr，r 结论为：p 以下证明p是一组前提pq，qr，r的有效结论。即证明：(pq)(qr)rp,下面用

47、部分真值表进行证明。作公式pq，qr，r，p的真值表，如表1.23所示。从表中可以看出：,所以(pq)(qr)rp,p为0的行(赋值100，101，110，111的行)pq，qr，r至少有一个为0，,pq，qr，r都为1的行(赋值000的行)，p也为1。,我们已经有了判断推理是否正确的4种方法，即真值表法、等值演算法、主范式法和蕴含演算法。当推理中包含的命题变元较多时，以上4种方法的演算量太大，给推理带来了困难。为此引入命题逻辑的推理理论。,命题逻辑的推理是一个描述推理过程的命题公式序列，其中的每个命题公式或者是已知前提，或者是由某些前提应用推理规则得到的结论(中间结论或推理中的结论)。它有两

48、种方法：直接推理和间接推理。,直接推理 直接推理的基本思想是：由一组前提出发，利用一些公认的规则，根据已知的等价式或蕴含式，推演得到有效结论。,公认的推理规则有4条：P规则：前提在推导过程中的任何时候都可以引入使用。T规则：推理中，如果一个或多个公式，蕴含了公式 S，则公式S可以引入到以后的推理之中。,置换规则：在推导过程的任何步骤上，命题公式中的子公式都可以用与之等价的公式置换。合取引入规则：任意两个命题公式A，B可以推出AB,常用的等价式和蕴合式包括1.3节中的23个命题定律，以及1.7节中的13个重要的蕴含式。,【例1.34】用直接推理法证明(pq)(qr)pr,证明：pq,p,q,qr

49、,r,间接推理 间接推理常有下列两种方法：CP规则 有时要证明的有效结论是一个条件命题，即要证明：,P,P,P,T假言推理,T假言推理,H1H2Hn(AB)其中，H1，H2，Hn，A，B是命题公式。,令 SH1H2Hn 则上式可以简化为 S(AB),而由S(AB)S(AB)(SA)B(SA)B(SA)B H1H2HnAB,所以，要证明H1H2Hn(AB)，只需证明H1H2HnAB，其中A叫做附加前提。,由蕴含的定义知需要证明:S(AB)1,即需证明 H1H2HnAB,这种间接推理方法称为CP规则。,【例1.37】用CP规则证明：p(qr)，tp，qtr 证明：,t P(附加前提),tp P,p

50、 T析取三段论,p(qr)P,qr T假言推理,q P,r T假言推理,tr CP规则,归谬法 设要证明H1H2Hn C 其中，H1，H2，Hn，C是命题公式。,令 SH1H2Hn 则上式可以简化为 SC,由蕴含的定义有 1SCSC,两边否定 0SC H1H2HnC即要证明C是前提H1，H2，Hn的有效结论，只须证明 H1H2HnC0,由定理知，上式等价下面两式：0H1H2HnC 和 H1H2HnC0,根据条件联结词的定义，前一式显然成立。所以只需证明 H1H2HnC0 其中，C叫做附加前提。,这种间接推理方法称为归谬法，它就是常说的反证法。,【例1.38】用归谬法证明(pq)r，rs，s，p