离散数学电子教案.ppt

《离散数学电子教案.ppt》由会员分享，可在线阅读，更多相关《离散数学电子教案.ppt（87页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、离散数学电子教案现在学习的是第1页，共87页离散数学主要内容离散数学主要内容 命题逻辑命题逻辑 谓词逻辑谓词逻辑 集集 合合 二元关系二元关系 函函 数数 代数系统代数系统 群、环和域群、环和域 格与布尔代数格与布尔代数 图图 论论 数理逻辑数理逻辑(Mathematics Logic)集合论集合论(Sets)代数结构（或代数系统）代数结构（或代数系统）(Algebra Structure)图论图论(Graph Theory)现在学习的是第2页，共87页哥尼斯堡七桥问题哈密尔顿周游世界问题四色定理现在学习的是第3页，共87页离散数学课程设置：离散数学课程设置：计算机系核心课程计算机系核心课程

2、信息类专业必修课程信息类专业必修课程 其它类专业的重要选修课程其它类专业的重要选修课程现在学习的是第4页，共87页 离散数学的后继课程：离散数学的后继课程：数据结构、编译技术、数据结构、编译技术、算法分析与设计、人工智能算法分析与设计、人工智能与机器人与机器人、数据库、网络和计算机图形学数据库、网络和计算机图形学现在学习的是第5页，共87页教材及参考书教材及参考书 左孝凌等，离散数学，上海科学技术文献出版社，1982 同济大学应用数学系离散数学编写组，离散数学，统计大学出版社，2003现在学习的是第6页，共87页第1章 命题逻辑 逻辑学逻辑学：研究思维形式及思维规律的科学。：研究思维形式及思维

3、规律的科学。逻辑学逻辑学 辩证逻辑辩证逻辑：以辩证法的世界观为基础的逻辑学。：以辩证法的世界观为基础的逻辑学。形式逻辑形式逻辑：对思维的形式结构和规律进行研究：对思维的形式结构和规律进行研究的类似于语法的一门工具性学科。的类似于语法的一门工具性学科。思维的形式结构思维的形式结构 概念概念：思维的基本单位。：思维的基本单位。判断判断：通过概念对事物是否具有某种属性进行肯：通过概念对事物是否具有某种属性进行肯定或否定的回答。定或否定的回答。推理推理：由一个或几个判断推出另一判断的思维形：由一个或几个判断推出另一判断的思维形式。式。数理逻辑数理逻辑：用数学方法来研究推理的规律。：用数学方法来研究推理

4、的规律。现在学习的是第7页，共87页 数理逻辑包括逻辑演算、证明论、公理集合论、模型论和递归论数理逻辑包括逻辑演算、证明论、公理集合论、模型论和递归论。本课程只介绍逻辑演算中的。本课程只介绍逻辑演算中的命题逻辑命题逻辑和和谓词逻辑谓词逻辑。17世纪中叶：德国数学家莱布尼茨世纪中叶：德国数学家莱布尼茨(G.W.Leibnitz)创立。创立。英国数学家布尔英国数学家布尔(G.Boole)：布尔代数：布尔代数德国数学家弗雷格德国数学家弗雷格(F.L.G.Frege)：量词与约束变元：量词与约束变元美国数学家歌德尔美国数学家歌德尔(K.Godel)：完全性定理：完全性定理意大利数学家皮亚诺意大利数学家

5、皮亚诺(G.Peano)英国数学家德摩根英国数学家德摩根(A.DeMorgen)、罗素、罗素(B.A.Russell)。所谓的数学方法，就是引进一套符号体系的方法，所以数理逻辑又所谓的数学方法，就是引进一套符号体系的方法，所以数理逻辑又称为称为符号逻辑符号逻辑。现在学习的是第8页，共87页第第1 1章章 命题逻辑命题逻辑 1.1命题及联结词命题及联结词 1.1.1 命题的基本概念命题的基本概念 在数理逻辑中把在数理逻辑中把能判断真假的陈述句称为命题。一般用小写能判断真假的陈述句称为命题。一般用小写英文字母或小写英文字母带下标表示。英文字母或小写英文字母带下标表示。命题的概念包含了以下命题的概念

6、包含了以下3个要素个要素：只有陈述句才有可能成为命题，而其它的语句，如：感叹句、祈使只有陈述句才有可能成为命题，而其它的语句，如：感叹句、祈使句、疑问句等都不是命题。句、疑问句等都不是命题。一个语句虽是陈述句一个语句虽是陈述句,但不能判断真假不是命题。但不能判断真假不是命题。虽然要求命题能判断真假，但不要求现在就能确定真假，将来可虽然要求命题能判断真假，但不要求现在就能确定真假，将来可以确定真假也可以。以确定真假也可以。现在学习的是第9页，共87页 一个命题表达的判断结果称为命题的真值。命题一个命题表达的判断结果称为命题的真值。命题的真值有的真值有“真真”和和“假假”两种，分别用两种，分别用T

7、rue、T、1(真真)和和False、F、0(假假)来表示。真值为真的命题称来表示。真值为真的命题称为真命题，真值为假的命题称为假命题。任何命为真命题，真值为假的命题称为假命题。任何命题的真值是唯一的。题的真值是唯一的。在命题逻辑中对命题不再细分，因而在命题逻辑中对命题不再细分，因而命题是命命题是命题逻辑中最基本的也是最小的研究单位题逻辑中最基本的也是最小的研究单位。现在学习的是第10页，共87页 【例1.1】判断以下语句是否为命题。若是命题，确定其真值。上海是个小村庄。存在外星人。禁止吸烟！北京是中国的首都。4是素数或6是素数。今天你吃了吗？11+1=100 我正在说谎。命题(F)命题(待定

8、)不是命题(祈使句)命题(T)命题(F)不是命题(疑问句)命题(由上下文确定)不是命题(悖论)现在学习的是第11页，共87页 表示命题的小写英文字母或带下标的小写英文字母常称为命题命题标识符标识符。如果命题标识符表示一个具体、确定的命题，称为命题常元命题常元。如果命题标识符表示任意一个命题，称为命题变元命题变元。命题变元无确定的真值。命题是能判断真假的陈述句。而命题变元代表任意的命题，其真值是不确定的。因而不是命题。如果一个命题不能再分解成更简单的命题，则称该命题为原原子命题子命题。如果一个命题不是原子命题，称该命题为复合命题复合命题。如果命题变元表示原子命题时，该命题变元称为原子变元原子变元

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

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

11、且并且中国是世界四大文明古国之一。现在学习的是第14页，共87页 3.析取联结词析取联结词 定义1.1.3 设p和q均为命题，则p和q的析取是一个复合命题，记作pq，读作“p或q”或者“p析取q”。定义为：当且仅当p和q均为F时，pq才为F。联结词“”的真值表如表1.3所示。联结词“”也可以看成逻辑运算，它是二元逻辑运算二元逻辑运算。表1.3pqpq000011101111 “”与汉语中的“或”相似，但又不相同。汉语中的或有可兼可兼或或与不可兼或不可兼或(排斥或)的区分。【例1.4】我今天在电视上看这场杂技或在剧场里看这场杂技。灯泡有故障或开关有故障。现在学习的是第15页，共87页 4.条件联

12、结词条件联结词 定义1.1.4 设p和q均为命题，其条件命题是个复合命题，记为：pq。读作“如果p，那么q”或“若p，则q”。定义为：当且仅当p为T，q为F时，pq才为F。p称为条件命题pq的前件前件，q称为条件命题pq的后件后件。联结词“”真值表如表1.4所示。联结词“”也可以看成逻辑运算，它是二元逻辑运算二元逻辑运算。表1.4 pqpq001011100111 【例1.5】p：小王努力学习。q：小王学习成绩优秀。pq：如果小王努力学习，那么他的学习成绩就优秀。联结词“”与汉语中的“如果，那么”或“若，则”相似，但又是不相同的。(“”可不顾及前因后果)现在学习的是第16页，共87页 5.双条

13、件联结词双条件联结词 定义1.1.5设p和q均为命题，其复合命题pq称为双条件命题双条件命题，读作：“p双条件q”或者“p当且仅当q”。定义为：当且仅当p和q的真值相同时，pq为T。联结词“”的真值表如表1.5所示。联结词“”也可以理解成逻辑运算，它是二元逻辑运算二元逻辑运算。表1.5 pqpq001010100111 双条件联结词表示的是一个充分必充分必要关系要关系，与前面所述相同，也可以不必顾及其前因后果，而只根据联结词的定义来确定其真值。【例1.6】设p：张华是三好学生。q：张华德、智、体全优秀。pq：张华是三好学生当且仅当当且仅当德、智、体全优秀。现在学习的是第17页，共87页 1.2

14、 命题公式与翻译 把命题常量，命题变量按照一定的逻辑顺序用命题联结词连接起来就构成了命题演算的合式公式合式公式，也叫命题公式命题公式。当使用联结词集，时，合式公式定义如下：定义1.2.1按下列规则构成的符号串称为命题演算的合式公式，也称为命题公式，简称公式。单个命题变元和常元是合式公式。如果A是合式公式，那么A是合式公式。如果A和B是合式公式，那么(AB)、(AB)、(AB)和(AB)是合式公式。当且仅当有限次地应用了、所得到的符号串是合式公式。命题公式一般的用大写的英文字母A，B，C，表示。依照这个定义，下列符号串是合式公式：现在学习的是第18页，共87页 (pq)，(pq)，(p(pq)，

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

16、念，就可以用命题公式表示复合命题，常将这个过程称为命题的符号化命题的符号化。命题的符号化可按如下步骤进行：找出复合命题中的原子命题。用小写的英文字母或带下标的小写的英文字母表示这些原子命题。使用命题联结词将这些小写的英文字母或带下标的小写的英文字母连接起来。【例1.7】将下列命题符号化：他今天上午或者骑自行车去学校，或者乘公共汽车去学校。解：令 p：他今天上午骑自行车去学校。q：他今天上午乘公共汽车去学校。此命题中的或是不可兼或，所以不能符号化为：pq。而要符号化为：(pq)或(pq)(pq)。现在学习的是第20页，共87页 1.3真值表和等价公式 1.3.1命题公式的真值表命题公式的真值表

17、定义1.3.1 设pl，p2，pn是出现在公式A中的全部命题变元，给pl，p2，pn各指定一个真值，称为对公式A的一个赋值赋值或解释。若指定的赋值使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的真值表真值表。现在学习的是第21页，共87页 【例1.8】构造命题公式pq的真值表，并求成真赋值和

18、成假赋值。表1.6pqppq0011011110001101现在学习的是第22页，共87页表1.7pqpqpqpq(pq)(pq)0001111010100010001001110001 【例1.9】构造命题公式(pq)(pq)的真值表，并求成真赋值和成假赋值。解：命题公式(pq)(pq)的真值表如表1.7所示。00，11是成真赋值，01，10是成假赋值。现在学习的是第23页，共87页 1.3.2命题公式的等价命题公式的等价 定义1.3.3 设A和B是两个命题公式，对A和B的任一赋值，A和B的真值都相同，则称A和B是等价的或逻辑相等的，记为AB 可以证明，命题公式等价有下面的三条性质：自反性自

19、反性，即对任意命题公式A，AA 对称性对称性，即对任意命题公式A和B，若AB，则BA 传递性传递性，即对任意命题公式A，B和C，若AB，BC，则AC 根据定义1.3.3，可以用真值表证明命题公式是等价的，请看下面的例题。现在学习的是第24页，共87页 【例1.12】根据等价的定义，用真值表证明 p(qp)p(pq)证明：构造p(qp)和p(pq)的真值表，如表1.10所示。p(qp)和p(pq)所在的列完全相同，它们具有相同的真值表。所以p(qp)p(pq)表1.10 pqpqqpp(qp)pqp(pq)00111111011001111001111111001101现在学习的是第25页，共8

20、7页 证明等价的另外一种方法叫做等价演算法等价演算法，其基本思想是：先用真值表证明一组基本等价式，以它们为基础进行公式之间的演算。基本等价式常叫命题定律命题定律。下面是常用的命题定律。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 现在学习的是第26页，共87页 7.吸收律吸收律 A(AB)A，A(AB)A 8.零律零律 A11，A00 9.同一律同一律 A0A，

21、A1A 10.排中律排中律 AA1 11.矛盾律矛盾律 AA0 12.条件等价式条件等价式ABAB 13.双条件等价式双条件等价式AB(AB)(BA)14.假言易位式假言易位式ABBA 15.双条件否定等价式双条件否定等价式 ABAB现在学习的是第27页，共87页 以上共23个等价式，原则上说，这些公式都可以用真值表证明。下面仅验证德摩根律。【例1.13】用真值表证明德摩根律(AB)AB 解：表1.11是(AB)和AB的真值表，从表中可以看出德摩根律成立。表1.11ABABABAB(AB)0011101011001010010101100010现在学习的是第28页，共87页 定义1.3.4如果

22、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 满足此定理的置换叫做等价置换等价置换。现在学习的是第29页，共87页【例1.17】用等价演算法证明 pq(pq)(pq)证明：pq(pq)(qp)(双条件等价式)(pq)(qp)(条件等价式)(pq)(pp)(qq)(qp)(分配律)(pq)00(qp)

23、(矛盾律)(pq)(qp)(同一律)(pq)(pq)(交换律)pq(pq)(pq)(等价的传递性)现在学习的是第30页，共87页 1.4重言式重言式 定义1.4.1 设A是任一命题公式。若对A的任意赋值，其真值永为真，则称命题公式A为重重言式言式或永真式永真式。若对A的任意赋值，其真值永为假，则称命题公式A为矛盾矛盾式式或永假式永假式。若A不是矛盾式，则称命题公式A为可满足式可满足式。由定义1.4.1可以看出，任何重言式都是可满足式。显然，重言式的真值表的最后一列全为1，矛盾式的真值表的最后一列全为0，可满足的公式真值表的最后一列至少有一个1。根据这个结论借助于真值表可以判断一个公式是否为重言

24、式，矛盾式或可满足的。当然也可以用等价演算法判断公式的类型。现在学习的是第31页，共87页【例1.18】用等价演算法判断下列公式的类型。q(pq)p)解：q(pq)p)q(pp)(qp)(分配律)q(0(qp)(矛盾律)q(qp)(同一律)q(qp)(德摩根律)(qq)p (结合律)1p (排中律)1 (零律)由此可知，为重言式。现在学习的是第32页，共87页 (pp)(qq)r)1(qq)r)(排中律)1(0r)(矛盾律)10 (零律)0 (条件联结词的定义)由此可知，为矛盾式。现在学习的是第33页，共87页 (pq)p (pq)p (条件等价式)p (吸收律)由此可知，是可满足式。定理定理

25、1.4.1 任何两个重言式的合取或析取都是重言式。证明：设A、B是重言式，对A和 B的任何赋值，总有A为1，B为1，所以 AB1，AB1，故AB和AB都是重言式。推论推论 任何两个矛盾式的合取或析取是矛盾式。定理定理1.4.2 一个重言式，对同一分量出现的每一处都用同一合式公式置换，其结果仍是重言式。推论：推论：一个矛盾式，对同一分量出现的每一处都用同一合式公式置换，其结果仍是矛盾式。现在学习的是第34页，共87页 【例1.19】利用定理1.4.2证明(pq)r)(pq)r)为重言式。证明：由排中律知pp为重言式，以(pq)r)去置换其中的p，得公式(pq)r)(pq)r)，根据定理1.4.2

26、，这是重言式。定理定理1.4.3 设A、B为两个命题公式，AB当且仅当AB是重言式。证明：设AB，下证AB是重言式。给A，B的任何赋值，因为AB，所以A，B具有相同的真值，由双条件联结词的定义知AB为真，所以AB为重言式。设AB为重言式，下证AB 给A，B的任何赋值，因为AB为重言式，故A，B的真值相同，由命题公式等价的定义知AB现在学习的是第35页，共87页作业 判断下列命题公式的类型 1）(PQ)(QP)2)(QP)(PQ)3)(PQ)R)P 4)(PQ)P 5)(PP)P现在学习的是第36页，共87页 1.5范式范式 1.5.1析取范式析取范式与合取范式 定义1.5.1由一些命题变元或其

27、否定构成的析取式称为基本基本和和，也叫简单析取式简单析取式。约定单个变元或其否定是基本和单个变元或其否定是基本和。例如，pq、pq、pq、q、p、q都是基本和。定义定义1.5.2由一些命题变元或其否定构成的合取式称为基本积基本积，也叫简单合取式简单合取式。约定单个变元或其否定是基本积单个变元或其否定是基本积。例如，pq、pq、pq、p、q、p都是基本积。定义1.5.3由基本和的合取构成的公式叫做合取范式合取范式。约定单个单个基本和是合取范式基本和是合取范式。定义1.5.4由基本积的析取构成的公式叫做析取范式析取范式。约定单个单个基本积是析取范式基本积是析取范式。1)基本和和基本积既是析取范式，

28、又是合取范式基本和和基本积既是析取范式，又是合取范式。2)析取范式和合取范式都仅含联结词,。现在学习的是第37页，共87页 利用双重否定律消去否定联结词“”或利用德摩根律将否定联结词“”移到各命题变元前(内移)。利用分配律，结合律将公式归约为合取范式和析取范式。任何命题公式都可以化成与其等价的析取范式或合取范式。求析取范式和合取范式的步骤如下：消去联结词“”和“”现在学习的是第38页，共87页【例1.21】求命题公式(pq)p的合取范式和析取范式。解：求合取范式 (pq)p (pq)p)(p(pq)(消去)(pq)p)(p(pq)(消去)(pq)p)(p(pq)(内移)(pp)(qp)(ppq

29、)(分配律)1(qp)(1q)(排中律)1(qp)1 (零律)(qp)(同一律，合取范式)合取范式现在学习的是第39页，共87页 求析取范式 (pq)p (pq)p)(pq)p)(消去)(pq)p)(pq)p)(内移)p(pqp)(吸收律)p(ppq)(交换律)p(pq)(幂等律，析取范式)由此例可以看出，命题公式的析取范式也不惟一。析取范式析取范式现在学习的是第40页，共87页1.5.2主析取范式主析取范式 由于析取范式和合取范式不惟一，所以使用起来很不方便。为此，引入主析取范式和主合取范式的概念。当命题变元的顺序约定以后，主析取范式和主合取范式是惟一的。析取范式和合取范式的基本成分是基本积

30、和基本和，而主析取范式和主合取范式的基本成分是极小项极小项和极大项极大项，它们分别是特殊特殊的基本积和基本和的基本积和基本和。现在学习的是第41页，共87页 p，q的极小项为：pq，pq，pq，pq 定义1.5.5在基本积中，每个变元及其否定不同时存在，但两者之一必须出现且仅出现一次，这样的基本积叫做布尔合取布尔合取也叫小项小项或极小极小项项。表1.12是两个变元p和q的极小项的真值表。极小项有下列的性质：两个命题变元的极小项共4(=22)个,三个命题变元的极小项共8(=23)个,。一般地说，n个命题变元共有2n个极小项。表1.12 pqpqpqpqpq00000101001010010011

31、1000现在学习的是第42页，共87页表1.13极小项成真赋值名称pq00m0pq01m1pq10m2pq11m3每个极小项只有一个成真赋值，且各极小项的成真赋值互不相同。极小项和它的成真赋值构成了一一对应的关系。可用成真赋值为极小项进行编码，并把编码作为m的下标来表示该极小项，叫做该极小项的名称。两个命题变元的极小项、成真赋值和名称如表1.13所示。三个命题变元的极小项，成真赋值和名称如表1.14所示。现在学习的是第43页，共87页表1.14极小项成真赋值名称pqr000m0pqr001m1pqr010m2pqr011m3pqr100m4pqr101m5pqr110m6pqr111m7 从表

32、1.13和表1.14中可以看出，极小项与其成真赋值的对应关系为：变元对应1，而变元的否定对应0。现在学习的是第44页，共87页 任意两个不同的极小项的合取式为永假式。例如：m001m100(pqr)(pqr)pqrpqr0 定义1.5.6 对于给定的命题公式，如果有一个它的等价公式，仅由极小项的析取组成，称该公式为原公式的主析取范式主析取范式。120niimm0m1 112 nm 任何命题公式都存在着与之等价的主析取范式。一个命题公式的主析取范式可以由以下两种方法求得：等价演算法：即用基本等价公式推出。全体极小项的析取式为永真式。记为：现在学习的是第45页，共87页 用等价演算法求主析取范式的

33、步骤如下：【例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在基本积中补入没有出现的命题变元，即添加(pp)，再用分配律展开，最后合并相同的极小项。化归为析取范式。除去析取范式中所有永假的基本积。在基本积中，将重复出现的合取项和相同变元合并。现在学习的是第46页，共87页 真值表法：即用真值表求主析取范式。用真值表求主析取范式的步骤如下：构造命题公

34、式的真值表。找出公式的成真赋值对应的极小项。这些极小项的析取就是此公式的主析取范式。【例1.24】用真值表法，求(pq)r的主析取范式。解：表1.15是(pq)r的真值表，公式的成真赋值对应的极小项为：pqr(成真赋值为001)pqr (成真赋值为011)pqr(成真赋值为100)pqr(成真赋值为101)pqr (成真赋值为111)(pq)r 的主析取范式为：现在学习的是第47页，共87页 (pqr)(pqr)(pqr)(pqr)(pqr)m111m101m100m011m001m7m5m4m3m1 1，3，4，5，7表1.15pqrpq(pq)r0001000111010100111110

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

36、qr，pqr，pqr，pqr 两个命题变元的极大项共4(=22)个,三个命题变元的极大项共8(=23)个,。一般地说，n个变元共有2n个极大项。现在学习的是第50页，共87页 例如，两个变元p，q的极大项pq，它的成假赋值是11，表示为M11，把11理解为2进制数，它的10进制表示为3，所以M 11又表示为M3。表1.16极大项成假赋值名称pq00M0pq01M1pq10M2pq11M3 两个命题变元的极大项，成假赋值及名称见表1.16，三个命题变元的极大项，成假赋值及名称见表1.17。极大项有下列三个性质：每个极大项只有一个成假赋值，极大项不同，成假赋值也不同。极大项和它的成假赋值构成了一一

37、对应的关系。故可用成假赋值为该极大项进行编码，并把编码作为M的下标来表示该极大项，叫做极大项的名称。现在学习的是第51页，共87页 从表1.16和表1.17中可以看出，极大项与成假赋值的对应关系为：变元对应0，而变元的否定对应1。表1.17极大项成假赋值名称pqr000M0pqr001M1pqr010M2pqr011M3pqr100M4pqr101M5pqr110M6pqr111M7120niiMM0M1 12 nM0 全体极大项的合取式为永假式。记为：永真式。任意两个不同的极大项的析取式为现在学习的是第52页，共87页 定义1.5.8 对于给定的命题公式，如果有一个它的等价公式，仅由极大项的

38、合取组成，则该等价式称为原公式的主合取范式主合取范式。等价演算法等价演算法：即用基本等价公式推出。其演算步骤如下：化归为合取范式。除去所有永真的基本和。在基本和中合并重复出现的析取项和相同的变元。在基本和中补入没有出现的命题变元。即增加(pp)，然后，应用分配律展开公式，最后合并相同的极大项。任何命题公式都存在着与之等价的主合取范式。主合取范式也可以由以下两种方法求得。现在学习的是第53页，共87页【例1.25】用等价演算法求(pq)r的主合取范式。解：(pq)r (pq)r(pq)r(pr)(qr)(pr(qq)(qr(pp)(prq)(prq)(pqr)(pqr)(pqr)(pqr)(pq

39、r)M000M010M110M0M2M60，2，6 现在学习的是第54页，共87页 真值表法真值表法：用真值表求主合取范式。用真值表求主合取范式的步骤如下：构造命题公式的真值表。找出公式的成假赋值对应的极大项。这些极大项的析取就是此公式的主合取范式。【例1.26】用真值表法求(pq)r的主合取范式。解：(pq)r的真值表是表1.15。公式的成假赋值对应的大项为：pqr (成假赋值为000)pqr(成假赋值为010)pqr(成假赋值为110)主合取范式为：(pqr)(pqr)(pqr)M000M010M110M0M2M60，2，6 现在学习的是第55页，共87页 矛盾式无成真赋值，因而矛盾式的主

40、合取范式含2n(n为公式中命题变元的个数)个极大项。而重言式无成假赋值，因而主合取范式不含任何极大项。将重言式的主合取范式记为1。至于可满足式，它的主合取范式中极大项的个数一定小于2n。在例1.23和例1.24中求出(pq)r的主析取范式为：m7m5m4m3m11，3，4，5，7 在例1.25和例1.26中求出该公式的主合取范式为：M0M2M60，2，6 比较这两个结果，得出以下的结论:同一公式的主析取范式中m的下标和主合取范式中M的下标是互补的。因此，知道了主析(合)取范式就可以写出主合(析)取范式。现在学习的是第56页，共87页 1.6 全功能联结词集全功能联结词集 定义1.6.1 设p和

41、q是两个命题，复合命题p q称作p和q的不可兼析取不可兼析取，也叫异或异或。定义为：p q为T当且仅当p和q的真值不相同时。联结词“”称为异或联结词。表1.18pq000011101110pq不可兼析取有下列的性质：p qq p (交换律)(p q)rp (q r)(结合律)联结词“”的真值表如表1.18所示。“”也可以看成逻辑运算，它是二元逻辑运算。它在程序设计中有广泛的应用。现在学习的是第57页，共87页 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，则A CB，B

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

43、且仅当p、q的真值都为假时，pq的真值为真。联结词“”称为或非联结词或非联结词。联结词“”的真值表如表1.20所示。“”也可以看成逻辑运算，它是二二元逻辑运算元逻辑运算。表1.20pqpq001010100110 由此定义可得到下面的公式：pq(pq)联结词还有下面的几个性质：pp(pp)p (pq)(pq)(pq)(pq)pq (pp)(qq)pq(pq)pq 现在学习的是第60页，共87页 至此已经学了8个联结词：，。类似于定义1.2.1的方法，可以定义包含上述8个联结词的命题公式。定义1.6.4 设S是一个联结词集合，如果任何n(n1)个变元组成的公式，都可以由S中的联结词来表示，则称S

44、是全功能联结词集全功能联结词集。利用下列3个等价式可将任何命题公式中的命题联结词“”、“”和“”去掉。根据命题公式的定义，是全功能联结词集。现在学习的是第61页，共87页 p q(pq)pq(pq)pq(pq)所以，是全功能联结词集。利用下列2个等价式可将任何命题公式中的命题联结词“”和“”去掉。用德摩根律可证明，和，是全功能联结词集。可以证明，不是全功能联结词集。定义1.6.5 设S是全功能联结词集，如果去掉其中的任何联结词后，就不是全功能联结词集，则称S是最小全功能联结词集最小全功能联结词集。pqpqpq(pq)(qp)(pq)(qp)所以，是全功能联结词集。现在学习的是第62页，共87页

45、 可以证明，是最小全功能联结词集。表1.21pq公式001或0011或0101或0111或0 两个命题变元构成的命题公式的真值表的格式如表1.21所示。现在讨论，n个命题变元可以构成多少个不等价的命题公式。两个命题变元可以构成多少个不等价的命题公式？由等价的概念知道，等价的命题公式有相同的真值表，所以上述问题就转化为两个命题变元构成的命题公式有多少个不同的真值表？222222222 真值表中每行公式的真值都有1，0两种可能，所以命题公式的真值有2222=24=16种可能，既有 个不同的真值表。故有 种不等价的公式。现在学习的是第63页，共87页 三个变元可构成28=个不等价的命题公式，n个变元

46、可构成 个不等价的命题公式。322n221.7 对偶式与蕰含式对偶式与蕰含式 1.7.1对偶式对偶式 从1.3节的命题定律中可以看出，很多常用等价式是成对出现的，只要将其中的“”和“”分别换成“”和“”，就可以由一个得到另一个。例如，将命题定律 (AB)C(A C)(B C)中的“”换成“”,“”换成“”就得到了命题定律 (AB)C(AC)(B C)这些成对出现的等价式反映了等价的对偶性等价的对偶性。本节介绍对偶式和对偶原理。定义1.7.1在仅含联结词，的命题公式A中，将联结词，F，T分别换成，T，F所得的公式称为公式A的对偶式对偶式，记为A*。设A*是A的对偶式，将A*中的，F，T分别换成现

47、在学习的是第64页，共87页 【例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(p1，p2，pn)A*(p1，p2，pn)，T，F，就会得到A。即A 是A*的对偶式，(A*)*A。所以说A*和A互为对偶式。现在学习的是第6

48、5页，共87页 【例1.28】设命题公式A(p,q,r)(pq)r，试用此公式验证定理1.7.1的有效性。证明：验证 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)现在学习的是第66页，共87页 定理1.7.2(对偶原理对偶原理)设p1，p2，pn是出现在公式A和B中的所有原子变元，如果AB，则A*B*根据定理1.4.2，在上述重言式中用pi置换

49、 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*定理1.7.2叫做对偶原理。对偶原理是数理逻辑中最基本的规律之一。证明：因为 AB所以 A(p1，p2，pn)B(p1，p2，pn)是重言式。现在学习的是第67页，共87页 【例1.29】证明重言式的对偶式是矛盾式，矛盾式的对偶式是重言式。证明：设A是重言式，即A1，因为1的对偶式是0，由对偶原理知A*0。所以A*是矛盾式；设A是矛盾式，即A0

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