离散数学电子教案

离散数学电子教案第1页，课件共87页，创作于2023年2月离散数学主要内容

命题逻辑

谓词逻辑

集合

二元关系

函数

代数系统

群、环和域

格与布尔代数

图论

数理逻辑(MathematicsLogic)集合论(Sets)代数结构（或代数系统）(AlgebraStructure)图论(GraphTheory)第2页，课件共87页，创作于2023年2月哥尼斯堡七桥问题哈密尔顿周游世界问题四色定理第3页，课件共87页，创作于2023年2月离散数学课程设置：计算机系核心课程信息类专业必修课程其它类专业的重要选修课程第4页，课件共87页，创作于2023年2月离散数学的后继课程：

数据结构、编译技术、算法分析与设计、人工智能与机器人、数据库、网络和计算机图形学……第5页，课件共87页，创作于2023年2月教材及参考书左孝凌等，《离散数学》，上海科学技术文献出版社，1982同济大学应用数学系《离散数学》编写组，离散数学，统计大学出版社，2003第6页，课件共87页，创作于2023年2月第1章命题逻辑

逻辑学：研究思维形式及思维规律的科学。逻辑学

辩证逻辑：以辩证法的世界观为基础的逻辑学。形式逻辑：对思维的形式结构和规律进行研究的类似于语法的一门工具性学科。思维的形式结构概念：思维的基本单位。判断：通过概念对事物是否具有某种属性进行肯定或否定的回答。推理：由一个或几个判断推出另一判断的思维形式。数理逻辑：用数学方法来研究推理的规律。第7页，课件共87页，创作于2023年2月数理逻辑包括逻辑演算、证明论、公理集合论、模型论和递归论。本课程只介绍逻辑演算中的命题逻辑和谓词逻辑。17世纪中叶：德国数学家莱布尼茨(G.W.Leibnitz)创立。英国数学家布尔(G.Boole)：布尔代数德国数学家弗雷格(F.L.G.Frege)：量词与约束变元美国数学家歌德尔(K.Godel)：完全性定理意大利数学家皮亚诺(G.Peano)英国数学家德摩根(A.DeMorgen)、罗素(B.A.Russell)。所谓的数学方法，就是引进一套符号体系的方法，所以数理逻辑又称为符号逻辑。第8页，课件共87页，创作于2023年2月第1章命题逻辑

1.1命题及联结词

1.1.1命题的基本概念

在数理逻辑中把能判断真假的陈述句称为命题。一般用小写英文字母或小写英文字母带下标表示。命题的概念包含了以下3个要素：⑴只有陈述句才有可能成为命题，而其它的语句，如：感叹句、祈使句、疑问句等都不是命题。⑵一个语句虽是陈述句,但不能判断真假不是命题。⑶虽然要求命题能判断真假，但不要求现在就能确定真假，将来可以确定真假也可以。第9页，课件共87页，创作于2023年2月一个命题表达的判断结果称为命题的真值。命题的真值有“真”和“假”两种，分别用True、T、1(真)和False、F、0(假)来表示。真值为真的命题称为真命题，真值为假的命题称为假命题。任何命题的真值是唯一的。在命题逻辑中对命题不再细分，因而命题是命题逻辑中最基本的也是最小的研究单位。第10页，课件共87页，创作于2023年2月

【例1.1】判断以下语句是否为命题。若是命题，确定其真值。⑴上海是个小村庄。⑵存在外星人。⑶禁止吸烟！⑷北京是中国的首都。⑸4是素数或6是素数。⑹今天你吃了吗？⑺11+1=100 ⑻我正在说谎。命题(F)命题(待定)不是命题(祈使句)命题(T)命题(F)不是命题(疑问句)命题(由上下文确定)不是命题(悖论)第11页，课件共87页，创作于2023年2月表示命题的小写英文字母或带下标的小写英文字母常称为命题标识符。如果命题标识符表示一个具体、确定的命题，称为命题常元。如果命题标识符表示任意一个命题，称为命题变元。命题变元无确定的真值。

命题是能判断真假的陈述句。而命题变元代表任意的命题，其真值是不确定的。因而不是命题。

如果一个命题不能再分解成更简单的命题，则称该命题为原子命题。如果一个命题不是原子命题，称该命题为复合命题。如果命题变元表示原子命题时，该命题变元称为原子变元。

在自然语言中，可以通过“如果…，那么…”，“不但…，而且…”这样的连词将简单的陈述句联结成复合语句，同样在命题逻辑当中，也可以通过命题联结词将原子变元联结起来表示复合命题。第12页，课件共87页，创作于2023年2月

1.1.2命题联结词

常用的逻辑联结词有五种：否定联结词、合取联结词、析取联结词、条件联结词和双条件联结词。

表1.1

p

¬p

0

1

1

0

p和¬p的关系如表1.1所示，表1.1叫做否定联结词“¬”的真值表(下同)。

联结词“¬”也可以看作逻辑运算，它是一元运算。

【例1.2】否定下列命题。

p：王强是一名大学生。

¬p：王强不是一名大学生。1.否定联结词定义1.1.1设p为命题，则p的否定是一个复合命题，记作：¬p，读作“非p”或“p的否定”。定义为：若P为T，则¬p为F；若p为F，则¬p的真值为T。第13页，课件共87页，创作于2023年2月

2.合取联结词

定义1.1.2设p和q均为命题，则p和q的合取是一个复合命题，记作p∧q，读作“p与q”或“p合取q”。定义为：当且仅当p和q均为T时，p∧q的才为T。联结词“∧”的真值表如表1.2所示。联结词“∧”也可以看成逻辑运算，它是二元逻辑运算。

表1.2

pqp∧q0

00010100111

【例1.3】设

p：2008年北京举办了奥运会。

q：中国是世界四大文明古国之一。则p∧q：2008年北京举办了奥运会并且中国是世界四大文明古国之一。第14页，课件共87页，创作于2023年2月

3.

析取联结词定义1.1.3设p和q均为命题，则p和q的析取是一个复合命题，记作p∨q，读作“p或q”或者“p析取q”。定义为：当且仅当p和q均为F时，p∨q才为F。联结词“∨”的真值表如表1.3所示。联结词“∨”也可以看成逻辑运算，它是二元逻辑运算。表1.3pqp∨q000011101111

“∨”与汉语中的“或”相似，但又不相同。汉语中的或有可兼或与不可兼或(排斥或)的区分。

【例1.4】⑴我今天在电视上看这场杂技或在剧场里看这场杂技。⑵灯泡有故障或开关有故障。第15页，课件共87页，创作于2023年2月

4.条件联结词定义1.1.4设p和q均为命题，其条件命题是个复合命题，记为：p→q。读作“如果p，那么q”或“若p，则q”。定义为：当且仅当p为T，q为F时，p→q才为F。p称为条件命题p→q的前件，q称为条件命题p→q的后件。

联结词“→”真值表如表1.4所示。联结词“→”也可以看成逻辑运算，它是二元逻辑运算。

表1.4pqp→q001011100111

【例1.5】

p：小王努力学习。q：小王学习成绩优秀。

p→q：如果小王努力学习，那么他的学习成绩就优秀。联结词“→”与汉语中的“如果…，那么…”或“若…，则…”相似，但又是不相同的。(“→”可不顾及前因后果)第16页，课件共87页，创作于2023年2月

5.双条件联结词定义1.1.5设p和q均为命题，其复合命题p↔q称为双条件命题，读作：“p双条件q”或者“p当且仅当q”。定义为：当且仅当p和q的真值相同时，p↔q为T。联结词“↔”的真值表如表1.5所示。

联结词“↔”也可以理解成逻辑运算，它是二元逻辑运算。表1.5pqp↔q001010100111双条件联结词表示的是一个充分必要关系，与前面所述相同，也可以不必顾及其前因后果，而只根据联结词的定义来确定其真值。

【例1.6】设p：张华是三好学生。

q：张华德、智、体全优秀。p↔q：张华是三好学生当且仅当德、智、体全优秀。第17页，课件共87页，创作于2023年2月

1.2命题公式与翻译把命题常量，命题变量按照一定的逻辑顺序用命题联结词连接起来就构成了命题演算的合式公式，也叫命题公式。当使用联结词集¬，∧，∨，→，↔时，合式公式定义如下：

定义1.2.1按下列规则构成的符号串称为命题演算的合式公式，也称为命题公式，简称公式。⑴单个命题变元和常元是合式公式。⑵如果A是合式公式，那么¬A是合式公式。⑶如果A和B是合式公式，那么(A∧B)、(A∨B)、(A→B)和(A↔B)是合式公式。⑷当且仅当有限次地应用了⑴、⑵、⑶所得到的符号串是合式公式。命题公式一般的用大写的英文字母A，B，C，…表示。依照这个定义，下列符号串是合式公式：第18页，课件共87页，创作于2023年2月

¬(p∨q)，¬(p∨q)，(p→(p∨¬q))，

(((p→q)∧(q→r))↔(s↔t))

下列符号串不是合式公式：

(p→q)→(∧q)，(p→q，(p∧q)→q)定义1.2.1给出合式公式定义的方法称为归纳定义，它包括三部分：基础，归纳和界限。定义1.2.1中的⑴是基础，⑵和⑶是归纳，⑷是界限。下文中还将多次出现这种形式的定义。为方便起见，对命题公式约定如下：⑴最外层括号可以省略。⑵规定联结词的优先级由高到低依次为¬，∧，∨，→，↔。按此优先级别，如果去掉括号，不改变原公式运算次序，也可以省掉这些括号。一般地说，命题公式中包含命题变元，因而无法计算其真值，所以不是命题。命题公式中的命题变元，也叫命题公式的分量。第19页，课件共87页，创作于2023年2月

有了命题公式的概念，就可以用命题公式表示复合命题，常将这个过程称为命题的符号化。命题的符号化可按如下步骤进行：

⑴找出复合命题中的原子命题。⑵用小写的英文字母或带下标的小写的英文字母表示这些原子命题。⑶使用命题联结词将这些小写的英文字母或带下标的小写的英文字母连接起来。【例1.7】将下列命题符号化：他今天上午或者骑自行车去学校，或者乘公共汽车去学校。解：令p：他今天上午骑自行车去学校。

q：他今天上午乘公共汽车去学校。此命题中的或是不可兼或，所以不能符号化为：p∨q。而要符号化为：¬(p↔q)或(¬p∧q)∨(p∧¬q)。第20页，课件共87页，创作于2023年2月

1.3真值表和等价公式

1.3.1命题公式的真值表

定义1.3.1

设pl，p2，…，pn是出现在公式A中的全部命题变元，给pl，p2，…，pn各指定一个真值，称为对公式A的一个赋值或解释。若指定的赋值使A的真值为T，则称这个赋值为A的成真赋值，若使A的真值为F，则称这个赋值为A的成假赋值。

例如，给公式(p∨q→r)赋值011是指p=0，q=1，r=1，它是该公式的成真赋值；赋值110是指p=1，q=1，r=0，它是该公式的成假赋值。定义1.3.2在命题公式A中，对A的每一个赋值，就确定了A的一个真值，把它们汇列成表，称该表为命题公式A的真值表。第21页，课件共87页，创作于2023年2月

【例1.8】构造命题公式¬p∨q的真值表，并求成真赋值和成假赋值。

表1.6pq¬p¬p∨q0011011110001101第22页，课件共87页，创作于2023年2月表1.7pqp∧q¬p¬q¬p∧¬q(p∧q)∨(¬p∧¬q)0001111010100010001001110001

【例1.9】构造命题公式(p∧q)∨(¬p∧¬q)的真值表，并求成真赋值和成假赋值。

解：命题公式(p∧q)∨(¬p∧¬q)的真值表如表1.7所示。00，11是成真赋值，01，10是成假赋值。第23页，课件共87页，创作于2023年2月

1.3.2命题公式的等价定义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.3.3，可以用真值表证明命题公式是等价的，请看下面的例题。

第24页，课件共87页，创作于2023年2月

【例1.12】根据等价的定义，用真值表证明

p→(q→p)¬p→(p→¬q)证明：构造p→(q→p)和p→(p→q)的真值表，如表1.10所示。p→(q→p)和¬p→(p→¬q)所在的列完全相同，它们具有相同的真值表。所以p→(q→p)p→(p→¬q)表1.10pq¬p¬qq→pp→(q→p)p→¬q¬p→(p→¬q)00111111011001111001111111001101第25页，课件共87页，创作于2023年2月证明等价的另外一种方法叫做等价演算法，其基本思想是：先用真值表证明一组基本等价式，以它们为基础进行公式之间的演算。基本等价式常叫命题定律。下面是常用的命题定律。

1.双重否定律

A¬¬A2.交换律

A∨BB∨A，

A∧BB∧A

3.结合律

(A∨B)∨CA∨(B∨C) (A∧B)∧CA∧(B∧C)

4.分配律

A∧(B∨C)(A∧B)∨(A∧C)

A∨(B∧C)(A∨B)∧(A∨C)5.德摩根律

¬(A∨B)¬A∧¬B

¬(A∧B)¬A∨¬B6.幂等律

A∧AA，A∨AA

第26页，课件共87页，创作于2023年2月

7.吸收律

A∨(A∧B)A，

A∧(A∨B)A8.零律

A∨11，A∧009.同一律

A∨0A，

A∧1A10.排中律

A∨¬A111.矛盾律

A∧¬A012.条件等价式

A→B¬A∨B

13.双条件等价式

A↔B(A→B)∧(B→A)14.假言易位式

A→B¬B→¬A15.双条件否定等价式

A↔B¬A↔¬B第27页，课件共87页，创作于2023年2月以上共23个等价式，原则上说，这些公式都可以用真值表证明。下面仅验证德摩根律。

【例1.13】用真值表证明德摩根律

¬(A∨B)¬A∧¬B

解：表1.11是¬(A∨B)和¬A∧¬B的真值表，从表中可以看出德摩根律成立。

表1.11AB¬A¬B¬A∧¬BA∨B¬(A∨B)0011101011001010010101100010第28页，课件共87页，创作于2023年2月定义1.3.4如果X是合式公式A的一部分且X本身也是合式公式，则称X为公式A的子公式。例如，Aq→(p∨(p∧q))，Xp∧q，则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页，创作于2023年2月【例1.17】用等价演算法证明p↔q(p∧q)∨(p∧q)证明：p↔q(p→q)∧(q→p) (双条件等价式)

(¬p∨q)∧(¬q∨p)(条件等价式)

(¬p∧¬q)∨(¬p∧p)∨(q∧¬q)∨(q∧p)(分配律)

(¬p∧¬q)∨0∨0∨(q∧p)(矛盾律)

(¬p∧¬q)∨(q∧p)(同一律)

(p∧q)∨(¬p∧¬q)(交换律)

p↔q(p∧q)∨(¬p∧¬q) (等价的传递性)第30页，课件共87页，创作于2023年2月

1.4重言式定义1.4.1

设A是任一命题公式。⑴若对A的任意赋值，其真值永为真，则称命题公式A为重言式或永真式。⑵若对A的任意赋值，其真值永为假，则称命题公式A为矛盾式或永假式。⑶若A不是矛盾式，则称命题公式A为可满足式。由定义1.4.1可以看出，任何重言式都是可满足式。显然，重言式的真值表的最后一列全为1，矛盾式的真值表的最后一列全为0，可满足的公式真值表的最后一列至少有一个1。根据这个结论借助于真值表可以判断一个公式是否为重言式，矛盾式或可满足的。当然也可以用等价演算法判断公式的类型。第31页，课件共87页，创作于2023年2月【例1.18】用等价演算法判断下列公式的类型。⑴q∨¬((¬p∨q)∧p)解：⑴q∨¬((¬p∨q)∧p)

q∨¬((¬p∧p)∨(q∧p)) (分配律)

q∨¬(0∨(q∧p))(矛盾律)

q∨¬(q∧p)(同一律)

q∨(¬q∨¬p)(德摩根律)

(q∨¬q)∨¬p (结合律)

1∨¬p(排中律)

1 (零律)由此可知，⑴为重言式。第32页，课件共87页，创作于2023年2月⑵(p∨¬p)→((q∧¬q)∧r)1→((q∧¬q)∧r)(排中律)

1→(0∧r)(矛盾律)

1→0(零律)0(条件联结词的定义)由此可知，⑵为矛盾式。第33页，课件共87页，创作于2023年2月⑶(p→q)∧¬p

(¬p∨q)∧¬p(条件等价式)

¬p(吸收律)由此可知，⑶是可满足式。

定理1.4.1

任何两个重言式的合取或析取都是重言式。证明：设A、B是重言式，对A和B的任何赋值，总有A为1，B为1，所以A∧B1，A∨B1，故A∧B和A∨B都是重言式。推论

任何两个矛盾式的合取或析取是矛盾式。定理1.4.2

一个重言式，对同一分量出现的每一处都用同一合式公式置换，其结果仍是重言式。推论：一个矛盾式，对同一分量出现的每一处都用同一合式公式置换，其结果仍是矛盾式。第34页，课件共87页，创作于2023年2月

【例1.19】利用定理1.4.2证明((p∨q)∧r)∨¬((p∨q)∧r)为重言式。

证明：由排中律知p∨¬p为重言式，以((p∨q)∧r)去置换其中的p，得公式((p∨q)∧r)∨¬((p∨q)∧r)，根据定理1.4.2，这是重言式。定理1.4.3

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

给A，B的任何赋值，因为A↔B为重言式，故A，B的真值相同，由命题公式等价的定义知AB第35页，课件共87页，创作于2023年2月作业判断下列命题公式的类型1）(P→Q)↔(¬Q→¬P)2)(¬Q→P)→(P→Q)3)((P∨Q)→R)→P4)(P∧Q)↔P5)(P→¬P)→¬P第36页，课件共87页，创作于2023年2月

1.5范式

1.5.1析取范式与合取范式定义1.5.1由一些命题变元或其否定构成的析取式称为基本和，也叫简单析取式。约定单个变元或其否定是基本和。例如，¬p∨q、p∨¬q、p∨q、¬q、¬p、q都是基本和。

定义1.5.2由一些命题变元或其否定构成的合取式称为基本积，也叫简单合取式。约定单个变元或其否定是基本积。例如，¬p∧q、p∧¬q、p∧q、¬p、¬q、p都是基本积。定义1.5.3由基本和的合取构成的公式叫做合取范式。约定单个基本和是合取范式。定义1.5.4由基本积的析取构成的公式叫做析取范式。约定单个基本积是析取范式。1)基本和和基本积既是析取范式，又是合取范式。2)析取范式和合取范式都仅含联结词¬,∧,∨。第37页，课件共87页，创作于2023年2月⑵利用双重否定律消去否定联结词“¬”或利用德摩根律将否定联结词“¬”移到各命题变元前(¬内移)。⑶利用分配律，结合律将公式归约为合取范式和析取范式。任何命题公式都可以化成与其等价的析取范式或合取范式。求析取范式和合取范式的步骤如下：⑴消去联结词“→”和“↔”第38页，课件共87页，创作于2023年2月【例1.21】求命题公式(p∨q)↔p的合取范式和析取范式。解：⑴求合取范式

(p∨q)↔p

((p∨q)→p)∧(p→(p∨q))(消去↔)

(¬(p∨q)∨p)∧(¬p∨(p∨q))(消去→)

((¬p∧¬q)∨p)∧(¬p∨(p∨q))(内移)

(¬p∨p)∧(¬q∨p)∧(¬p∨p∨q)(分配律)1∧(¬q∨p)∧(1∨q)(排中律)

1∧(¬q∨p)∧1(零律)

(¬q∨p)(同一律，合取范式)←合取范式第39页，课件共87页，创作于2023年2月⑵求析取范式

(p∨q)↔p((p∨q)∧p)∨(¬(p∨q)∧¬p)(消去↔)((p∨q)∧p)∨((¬p∧¬q)∧¬p)(内移)

p∨(¬p∧¬q∧¬p)(吸收律)

p∨(¬p∧¬p∧¬q) (交换律)

p∨(¬p∧¬q) (幂等律，析取范式)由此例可以看出，命题公式的析取范式也不惟一。←析取范式←析取范式第40页，课件共87页，创作于2023年2月1.5.2主析取范式由于析取范式和合取范式不惟一，所以使用起来很不方便。为此，引入主析取范式和主合取范式的概念。当命题变元的顺序约定以后，主析取范式和主合取范式是惟一的。析取范式和合取范式的基本成分是基本积和基本和，而主析取范式和主合取范式的基本成分是极小项和极大项，它们分别是特殊的基本积和基本和。第41页，课件共87页，创作于2023年2月

p，q的极小项为：p∧q，p∧¬q，¬p∧q，¬p∧¬q

定义1.5.5在基本积中，每个变元及其否定不同时存在，但两者之一必须出现且仅出现一次，这样的基本积叫做布尔合取也叫小项或极小项。表1.12是两个变元p和q的极小项的真值表。极小项有下列的性质：两个命题变元的极小项共4(=22)个,三个命题变元的极小项共8(=23)个,…。一般地说，n个命题变元共有2n个极小项。表1.12

pqp∧qp∧¬q¬p∧q¬p∧¬q000001010010100100111000第42页，课件共87页，创作于2023年2月表1.13极小项成真赋值名称¬p∧¬q00m0¬p∧q01m1p∧¬q10m2p∧q11m3⑴每个极小项只有一个成真赋值，且各极小项的成真赋值互不相同。极小项和它的成真赋值构成了一一对应的关系。可用成真赋值为极小项进行编码，并把编码作为m的下标来表示该极小项，叫做该极小项的名称。两个命题变元的极小项、成真赋值和名称如表1.13所示。三个命题变元的极小项，成真赋值和名称如表1.14所示。

第43页，课件共87页，创作于2023年2月表1.14极小项成真赋值名称¬p∧¬q∧¬r000m0¬p∧¬q∧r001m1¬p∧q∧¬r010m2¬p∧q∧r011m3p∧¬q∧¬r100m4p∧¬q∧r101m5p∧q∧¬r110m6p∧q∧r111m7从表1.13和表1.14中可以看出，极小项与其成真赋值的对应关系为：变元对应1，而变元的否定对应0。第44页，课件共87页，创作于2023年2月⑵

任意两个不同的极小项的合取式为永假式。例如：

m001∧m100(¬p∧¬q∧r)∧(p∧¬q∧¬r)¬p∧¬q∧r∧p∧¬q∧¬r0定义1.5.6对于给定的命题公式，如果有一个它的等价公式，仅由极小项的析取组成，称该公式为原公式的主析取范式。

m0∨m1∨…∨1任何命题公式都存在着与之等价的主析取范式。一个命题公式的主析取范式可以由以下两种方法求得：⑴等价演算法：即用基本等价公式推出。⑶全体极小项的析取式为永真式。记为：第45页，课件共87页，创作于2023年2月用等价演算法求主析取范式的步骤如下：

【例1.22】用等价演算法求(p∧q)∨(¬p∧r)∨(q∧r)的主析取范式。解：(p∧q)∨(¬p∧r)∨(q∧r)

(p∧q∧(r∨¬r))∨(¬p∧r∧(q∨¬q))∨(q∧r∧(p∨¬p))

(p∧q∧r)∨(p∧q∧¬r)∨(¬p∧q∧r)∨(¬p∧¬q∧r)∨(p∧q∧r)∨(¬p∧q∧r)

(p∧q∧r)∨(p∧q∧¬r)∨(¬p∧q∧r)∨(¬p∧¬q∧r)

m111∨m110∨m011∨m001

m7∨m6∨m3∨m1∑1，3，6，7④在基本积中补入没有出现的命题变元，即添加∧(p∨¬p)，再用分配律展开，最后合并相同的极小项。①化归为析取范式。②除去析取范式中所有永假的基本积。③在基本积中，将重复出现的合取项和相同变元合并。第46页，课件共87页，创作于2023年2月⑵真值表法：即用真值表求主析取范式。用真值表求主析取范式的步骤如下：①构造命题公式的真值表。②找出公式的成真赋值对应的极小项。③这些极小项的析取就是此公式的主析取范式。

【例1.24】用真值表法，求(p→q)→r的主析取范式。解：表1.15是(p→q)→r的真值表，公式的成真赋值对应的极小项为：

¬p∧¬q∧r (成真赋值为001)¬p∧q∧r (成真赋值为011)p∧¬q∧¬r (成真赋值为100)p∧¬q∧r (成真赋值为101)p∧q∧r(成真赋值为111)(p→q)→r的主析取范式为：第47页，课件共87页，创作于2023年2月

(p∧q∧r)∨(p∧¬q∧r)∨(p∧¬q∧¬r)∨(¬p∧q∧r)∨(¬p∧¬q∧r)m111∨m101∨m100∨m011∨m001m7∨m5∨m4∨m3∨m1

∑1，3，4，5，7表1.15pqrp→q(p→q)→r0001000111010100111110001101011101011111第48页，课件共87页，创作于2023年2月因而主析取范式含2n

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

p∨q，p∨¬q，¬p∨q，¬p∨¬q

三个命题变元p，q，r构成的极大项为：

p∨q∨r，p∨q∨¬r，p∨¬q∨r，p∨¬q∨¬r，

¬p∨q∨r，¬p∨q∨¬r，¬p∨¬q∨r，¬p∨¬q∨¬r

两个命题变元的极大项共4(=22)个,三个命题变元的极大项共8(=23)个,…。一般地说，n个变元共有2n个极大项。第50页，课件共87页，创作于2023年2月例如，两个变元p，q的极大项¬p∨¬q，它的成假赋值是11，表示为M11，把11理解为2进制数，它的10进制表示为3，所以M11又表示为M3。表1.16极大项成假赋值名称p∨q00M0p∨¬q01M1¬p∨q10M2¬p∨¬q11M3两个命题变元的极大项，成假赋值及名称见表1.16，三个命题变元的极大项，成假赋值及名称见表1.17。

极大项有下列三个性质：⑴每个极大项只有一个成假赋值，极大项不同，成假赋值也不同。极大项和它的成假赋值构成了一一对应的关系。故可用成假赋值为该极大项进行编码，并把编码作为M的下标来表示该极大项，叫做极大项的名称。第51页，课件共87页，创作于2023年2月从表1.16和表1.17中可以看出，极大项与成假赋值的对应关系为：变元对应0，而变元的否定对应1。表1.17极大项成假赋值名称p∨q∨r000M0p∨q∨¬r001M1p∨¬q∨r010M2p∨¬q∨¬r011M3¬p∨q∨r100M4p∨q∨¬r101M5¬p∨¬q∨r110M6¬p∨¬q∨¬r111M7M0∧M1∧…∧

0

⑶全体极大项的合取式为永假式。记为：永真式。⑵任意两个不同的极大项的析取式为第52页，课件共87页，创作于2023年2月定义1.5.8对于给定的命题公式，如果有一个它的等价公式，仅由极大项的合取组成，则该等价式称为原公式的主合取范式。

⑴等价演算法：即用基本等价公式推出。其演算步骤如下：①化归为合取范式。②除去所有永真的基本和。③在基本和中合并重复出现的析取项和相同的变元。④在基本和中补入没有出现的命题变元。即增加∨(p∧¬p)，然后，应用分配律展开公式，最后合并相同的极大项。任何命题公式都存在着与之等价的主合取范式。主合取范式也可以由以下两种方法求得。第53页，课件共87页，创作于2023年2月【例1.25】用等价演算法求(p→q)→r的主合取范式。解：(p→q)→r¬(¬p∨q)∨r(p∧¬q)∨r(p∨r)∧(¬q∨r)

(p∨r∨(q∧¬q))∧(¬q∨r∨(p∧¬p))

(p∨r∨q)∧(p∨r∨¬q)∧(p∨¬q∨r)∧(¬p∨¬q∨r)

(p∨q∨r)∧(p∨¬q∨r)∧(¬p∨¬q∨r)

M000∧M010∧M110M0∧M2∧M6∏0，2，6第54页，课件共87页，创作于2023年2月⑵真值表法：用真值表求主合取范式。用真值表求主合取范式的步骤如下：①构造命题公式的真值表。②找出公式的成假赋值对应的极大项。③这些极大项的析取就是此公式的主合取范式。【例1.26】用真值表法求(p→q)→r的主合取范式。解：(p→q)→r的真值表是表1.15。公式的成假赋值对应的大项为：

p∨q∨r (成假赋值为000)p∨¬q∨r (成假赋值为010)

¬p∨¬q∨r (成假赋值为110)

主合取范式为：(p∨q∨r)∧(p∨¬q∨r)∧(¬p∨¬q∨r)M000∧M010∧M110M0∧M2∧M6∏0，2，6

第55页，课件共87页，创作于2023年2月矛盾式无成真赋值，因而矛盾式的主合取范式含2n(n为公式中命题变元的个数)个极大项。而重言式无成假赋值，因而主合取范式不含任何极大项。将重言式的主合取范式记为1。至于可满足式，它的主合取范式中极大项的个数一定小于2n

。在例1.23和例1.24中求出(p→q)→r的主析取范式为：

m7∨m5∨m4∨m3∨m1∑1，3，4，5，7

在例1.25和例1.26中求出该公式的主合取范式为：

M0∧M2∧M6∏0，2，6

比较这两个结果，得出以下的结论:同一公式的主析取范式中m的下标和主合取范式中M的下标是互补的。因此，知道了主析(合)取范式就可以写出主合(析)取范式。第56页，课件共87页，创作于2023年2月

1.6全功能联结词集定义1.6.1

设p和q是两个命题，复合命题pq称作p和q的不可兼析取，也叫异或。定义为：pq为T当且仅当p和q的真值不相同时。联结词“

”称为异或联结词。

表1.18pq000011101110pq不可兼析取有下列的性质：⑴

pqqp(交换律)

⑵(pq)rp(qr)(结合律)联结词“”的真值表如表1.18所示。“”也可以看成逻辑运算，它是二元逻辑运算。它在程序设计中有广泛的应用。第57页，课件共87页，创作于2023年2月⑶

p∧(qr)(p∧q)(p∧r) (合取对异或的分配律)⑷

pq(p∧q)∨(p∧q)⑸

pq¬(p↔q)⑹

pp0，0pp，1p¬p

定理1.6.1设A，B，C为命题公式，如果ABC，则ACB，BCA，ABC为一矛盾式。

定义1.6.2

设p和q是两个命题，复合命题p↑q称作p和q的与非。定义为：当且仅当p和q真值都是真时，p↑q才为假。联结词“↑”称为与非联结词。由定义可以看出下式成立：

p↑q¬(p∧q)联结词“↑”的真值表如表1.19所示。“↑”也可以看成逻辑运算，它是二元逻辑运算。联结词“↑”还有以下几个性质：第58页，课件共87页，创作于2023年2月表1.19pqp↑q001011101110⑴

p↑p¬(p∧p)

¬p

⑵(p↑q)↑(p↑q)⑶(p↑p)↑(q↑q)

¬¬(p∧q)

¬(¬p∧¬q)

¬(p↑q)(¬p)↑(¬q)p∧qp∨q第59页，课件共87页，创作于2023年2月定义1.6.3设p和q是两个命题，复合命题p↓q称作p和q的或非。定义为：当且仅当p、q的真值都为假时，p↓q的真值为真。联结词“↓”称为或非联结词。联结词“↓”的真值表如表1.20所示。“↓”也可以看成逻辑运算，它是二元逻辑运算。表1.20pqp↓q001010100110由此定义可得到下面的公式：

p↓q¬(p∨q)

联结词↓还有下面的几个性质：⑴p↓p¬(p∨p)¬p⑵(p↓q)↓(p↓q)¬(p↓q)¬¬(p∨q)p∨q⑶(p↓p)↓(q↓q)¬p↓¬q¬(¬p∨¬q)p∧q

第60页，课件共87页，创作于2023年2月至此已经学了8个联结词：¬，∧，∨，→，↔，，↑，↓。类似于定义1.2.1的方法，可以定义包含上述8个联结词的命题公式。定义1.6.4设S是一个联结词集合，如果任何n(n≥1)个变元组成的公式，都可以由S中的联结词来表示，则称S是全功能联结词集。

利用下列3个等价式可将任何命题公式中的命题联结词“”、“↑”和“↓”去掉。根据命题公式的定义¬，∧，∨，→，↔，，↑，↓是全功能联结词集。第61页，课件共87页，创作于2023年2月

pq¬(p↔q)p↑q¬(p∧q)p↓q¬(p∨q)

所以¬，∧，∨，→，↔是全功能联结词集。利用下列2个等价式可将任何命题公式中的命题联结词“→”和“↔”去掉。

用德摩根律可证明¬，∧和¬，∨是全功能联结词集。可以证明∧，∨，→，↔不是全功能联结词集。

定义1.6.5设S是全功能联结词集，如果去掉其中的任何联结词后，就不是全功能联结词集，则称S是最小全功能联结词集。p→q¬p∨qp↔q(p→q)∧(q→p)(¬p∨q)∧(¬q∨p)所以¬，∧，∨是全功能联结词集。第62页，课件共87页，创作于2023年2月可以证明¬，∧，¬，∨，↑，↓是最小全功能联结词集。表1.21pq公式001或0011或0101或0111或0两个命题变元构成的命题公式的真值表的格式如表1.21所示。现在讨论，n个命题变元可以构成多少个不等价的命题公式。两个命题变元可以构成多少个不等价的命题公式？由等价的概念知道，等价的命题公式有相同的真值表，所以上述问题就转化为两个命题变元构成的命题公式有多少个不同的真值表？真值表中每行公式的真值都有1，0两种可能，所以命题公式的真值有2×2×2×2=24==16种可能，既有个不同的真值表。故有种不等价的公式。第63页，课件共87页，创作于2023年2月三个变元可构成28=个不等价的命题公式，n个变元可构成个不等价的命题公式。

1.7对偶式与蕰含式

1.7.1对偶式从1.3节的命题定律中可以看出，很多常用等价式是成对出现的，只要将其中的“∧”和“∨”分别换成“∨”和“∧”，就可以由一个得到另一个。例如，将命题定律

(A∨B)∧C(A∧C)∨(B∧C)中的“∨”换成“∧”,“∧”换成“∨”就得到了命题定律

(A∧B)∨C(A∨C)∧(B∨C)这些成对出现的等价式反映了等价的对偶性。本节介绍对偶式和对偶原理。定义1.7.1在仅含联结词¬，∧，∨的命题公式A中，将联结词∨，∧，F，T分别换成∧，∨，T，F所得的公式称为公式A的对偶式，记为A*。

设A*是A的对偶式，将A*中的∨，∧，F，T分别换成第64页，课件共87页，创作于2023年2月

【例1.27】求p↑q和p↓q的对偶式。

解：

p↑q¬(p∧q)

¬(p∧q)的对偶式是¬(p∨q)p↓q

故p↑q的对偶式是p↓q；同样的方法可以证明p↓q的对偶式是p↑q。根据例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互为对偶式。第65页，课件共87页，创作于2023年2月

【例1.28】设命题公式A(p,q,r)(p∨q)∧r，试用此公式验证定理1.7.1的有效性。

证明：⑴验证¬A(p,q,r)A*(¬p,¬q,¬r)

A(p,q,r)(p∨q)∧r

¬A(p,q,r)¬((p∨q)∧r)(¬p∧¬q)∨¬r

A*(p,q,r)(p∧q)∨r

A*(¬p,¬q,¬r)(¬p∧¬q)∨¬r所以，¬A(p,q,r)A*(¬p,¬q,¬r)

⑵验证A(¬p,¬q,¬r)¬A*(p,q,r)

A(¬p,¬q,¬r)(¬p∨¬q)∧¬r

¬((p∧q)∨r)¬A*(p,q,r)第66页，课件共87页，创作于2023年2月定理1.7.2(对偶原理)设p1，p2，…，pn是出现在公式A和B中的所有原子变元，如果AB，则A*B*

根据定理1.4.2，在上述重言式中用¬pi置换pi，i＝1,…,n，所得的公式仍为重言式，即

A(¬p1，¬p2，…，¬pn)↔B(¬p1，¬p2，…，¬pn)是重言式。所以A(¬p1，¬p2，…，¬pn)B(¬p1，¬p2，…，¬pn)由定理1.7.1¬A*(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页，创作于2023年2月

【例1.29】证明重言式的对偶式是矛盾式，矛盾式的对偶式是重言式。

证明：设A是重言式，即A1，因为1的对偶式是0，由对偶原理知A*0。所以A*是矛盾式；设A是矛盾式，即A0，而0的对偶式是1，所以A*1。所以A*是重言式。1.7.2蕴含式

定义1.7.2设A和B是命题公式，若A→B是重言式，则称A蕴含B，记为AB。

根据定义可以用真值表或等价演算证明AB。

AB定义为：A→B为重言式。又由条件命题的定义知，仅在AT，BF时，A→B为假，其余情况都为真。故要证明AB，只需排除AT，BF的情况。于是就有了证明AB的第二种方法：第68页，课件共87页，创作于2023年2月⑴

对A指定真值T，若由此推出B的真值不为F，而为T，则A→B是重言式，即AB。⑵

对B指定真值F，若由此推出A的真值不为T，而为F，则A→B是重言式，即AB。【例1.31】推证¬p∧(p∨q)q

解：证法1：证法2：假定q为F，则p可以为T或F。

假定¬p∧(p∨q)为T¬p为T且p∨q为Tp为F且p∨q为Tq为T。所以¬p∧(p∨q)q①当p为T时，¬p为F，所以¬p∧(p∨q)为F。②当p为F时，(p∨q)为F，所以¬p∧(p∨q)为F。故¬p∧(p∨q)q第69页，课件共87页，创作于2023年2月蕴含式是逻辑推理的重要工具。下面是一些重要的蕴含式。它们都可以用上述两种方法证明，其中A，B，C，D是任意的命题公式。

1.附加律AA∨B，

BA∨B2.化简律A∧BA，

A∧BB3.假言推理A∧(A→B)B4.拒取式¬B∧(A→B)¬A5.析取三段论¬A∧(A∨B)B，

¬B∧(A∨B)A6.假言三段论(A→B)∧(B→C)(A→C)7.等价三段论(A↔B)∧(B↔C)(A↔C)8.构造性二难(A∨C)∧(A→B)∧(C→D)B∨D(A∨¬A)∧(A→B)∧(¬A→B)B9.破坏性二难(¬B∨¬D)∧(A→B)∧(C→D)(¬A∨¬C)

第70页，课件共87页，创作于2023年2月等价式和蕴含式有下面的关系。定理1.7.3设A，B为任意两个命题公式，则AB的充分必要条件是AB且BA

证明：设AB，下证AB且BA

因为AB，所以A↔BT由双条件等价式得

(A→B)∧(B→A)A↔BT因而A→B与B→A都是重言式，故有AB且BA。

设AB且BA，下证AB。因为AB且BA，所以A→B与B→A都是重言式，重言式的合取也是重言式，即

(A→B)∧(B→A)T再由双条件等价式得(A↔B)(