离散数学基础-第二章-数理逻辑

数理逻辑部分逻辑学(1ogic)是研究人类推理规则（过程）的科学。逻辑学分为两大流派：传统逻辑（亚式逻辑）数理逻辑（符号逻辑）第一页1第二页，共166页。传统逻辑由亚里士多德创立（故称亚式逻辑），它是从日常生活的经验出发，训练我们在生活中如何使用概念，以及如何判断和推理。其推理的主要规则是定言三段论。数理逻辑(mathematicallogic)则是近代由欧美人创立的，使用的都是抽象的数学符号和数学公式，也就是用数学的方法来研究逻辑，所以数理逻辑又叫符号逻辑（symbolicLogic）。第二页2第三页，共166页。逻辑研究的内容：

——着重于推理过程是否正确；

——着重于语句之间的关系，而不是一个具体语句的内容。例:语句1:所有的数学家都穿凉鞋。语句2:任何一个穿凉鞋的人都是代数学家。语句3:所有数学家都是代数学家。从技术上来说，逻辑并不帮助确定这些语句是否为真;然而，如果前两个语句为真，逻辑可以保证语句3也为真。第三页3第四页，共166页。传统逻辑适用于日常生活中的推理；数理逻辑则偏重演算，适用于计算机实现推理。数理逻辑是计算机软件理论技术和硬件逻辑设计、人工智能等学科的重要理论基础。

程序＝算法＋数据

算法＝逻辑＋控制本课程包含了数理逻辑的两个基础演算(命题演算和谓词演算)，叫作逻辑代数。第四页4第五页，共166页。本章主要内容1、命题逻辑及联接词2、命题公式和分类3、等值演算与范式4、命题逻辑的推理理论第五页5第六页，共166页。第一节命题及连接词第六页6第七页，共166页。§1命题的定义与运算一、命题的概念推理的构成:

前提(一个或多个判断句)

结论(一个或多个判断句)

判断句----表达判断的陈述句----是推理的基本单位。

表达判断----有真假意义,要么为真,要么为假,但不能兼而有之。

【定义】能判断出真假的陈述句，称为命题（proposition或statement）。第七页7第八页，共166页。

命题的真值：作为命题的陈述句所表达的判断结果。真值只有两种取值：真(true)或假(false)。任何命题的真值都是唯一的。

真命题：假命题：判断给定句子是否为命题，一般分为两步：

首先判断它是否为陈述句，然后判断它是否有唯一真值。第八页8第九页，共166页。【例1】

判断下列句子是不是命题:4是素数。π是无理数。x

大于y。充分大的偶数等于两个素数之和。火星上有生物。你能帮助我吗？请不要吸烟！这朵花真美丽啊！我正在说假话。10）如果x>y，则x-y>0。（命题）（命题）（命题）（命题）（真值不唯一）（疑问句）（祈使句）（感叹句）（悖论）（命题）第九页9第十页，共166页。

解：1)、2)、4)、5)、10）这5句是命题，其中第１)句是假命题；第２)句是真命题；第4)句和第5)句虽然目前暂时无法判断其真假,但它们的真值是客观存在的，而且是唯一的，将来总会找到它们的真值。

6)是疑问句，7)是祈使句，8)是感叹句，不是命题

3)x,y表示变元，它们不是确定的对象（从而导致真值不惟一），所以不是命题。

9)是一个自相矛盾的病态语句----称为悖论，不是命题。第十页10第十一页，共166页。

二、原子命题和复合命题

【定义】不能再分解为更简单句子的命题叫原子命题（简单命题），否则称为复合命题。例：今天是星期一。例：今天是星期一并且今天天晴。

原子命题中的“原子”取原子的“不可再分”之意,它是最基本的命题,相当于自然语言的简单陈述句。第十一页11第十二页，共166页。

【例】

下面的命题由哪些原子命题组成:

1)王斌贫穷但快乐。

2)只要明天天气好,我就去春游。

3)如果10是一个大于１的整数,则10的大于１的最小因数一定是素数。第十二页12第十三页，共166页。

解

1)有两个原子命题P和Q,其中

P:王斌贫穷。Q:王斌快乐。

2)有两个原子命题R和s,其中

R:明天天气好。s:我去春游。

3)有两个原子命题a和b,其中

a:10是一个大于１的整数。

b:10的大于１的最小因数是素数。

第十三页13第十四页，共166页。三、命题及真值的符号化1、用小写字母p,q,r,…或加下标的小写字母pi,qi,ri,…表示命题。

【示例】

p:4是素数。（句中的“：”读作“表示”）

q:1+1=2

r:火星上有生物。2、用

T或1表示真，用

F或0表示假。示例中p

的真值为0，q

的真值为1，r的真值暂时还不知道。第十四页14第十五页，共166页。

由简单命题通过“非”、“并且”、“或者”、“如果…那么…”等联结词组合可产生新命题。但在自然语言中出现的联结词有时有二义性。因而在数理逻辑中，必须给出联结词的严格定义，并且将它们形式化。§2逻辑联结词第十五页15第十六页，共166页。定义设p是一个命题,复合命题“非p”称为p的否定式,记作┐p。┐称作否定联结词。

“┐”的读法：not（英）非、…的否定（中）1.非┐P的真值定义为：┐P为真

iff

P为假。（iff表示“当且仅当”）第十六页16第十七页，共166页。┐p的真值定义为：┐p为真

iff

p为假。p┐p0110表2.1┐p的真值表第十七页17第十八页，共166页。【例如】P：3是偶数。┐

P：3不是偶数。(不是3是偶数。×)Q：今天是星期天。┐Q：今天不是星期天。

R：所有的苹果都是红的。┐R：不是所有的苹果都是红的。（所有的苹果都不是红的。×）第十八页18第十九页，共166页。

常见错误：命题的表述不符合日常规范。例：

p：3是偶数，则┐p表示的命题是什么？常见的错误答案是：“不是3是偶数”。正确的答案是：“3不是偶数”。第十九页19第二十页，共166页。

常见错误：部分否定与全部否定。例：

p：所有的苹果都是红的，则┐p表示的命题是什么？常见的错误答案是：“所有的苹果都不是红的”。正确的答案是：“并非所有的苹果都是红的”。第二十页20第二十一页，共166页。定义设p,q是两个命题,复合命题“p并且q”称为p与q的合取式，记做p∧q，∧称为合取联结词。“∧”的读法：and

（英）合取、且（中）

p∧q的真值定义为：

p∧q为真

iff

p,q都为真。2.与（且）第二十一页21第二十二页，共166页。pqp∧q000110110001表2.2p∧q真值表p∧q的真值定义为：p∧q为真

iff

p,q都为真。

第二十二页22第二十三页，共166页。可以抽象成合取词∧的自然语言的连接词有:“并且”“和”“及”“既…又…”“不但…而且…”“虽然…但是…”

“一面…一面…”第二十三页23第二十四页，共166页。【例】

将下列命题符号化。(1)吴颖既用功又聪明。(2)吴颖虽然聪明但不用功，这不是真的。(3)张辉与王丽都是三好学生。(4)张辉与王丽是同学。

解首先将原子命题符号化：

P:吴颖用功Q:吴颖聪明

R:张辉是三好学生s:王丽是三好学生

t:张辉与王丽是同学P∧Q┐(┐P∧Q)R∧st第二十四页24第二十五页，共166页。则符号化的命题如下：(1)p∧q

(2)

┐(┐p∧q)(3)r∧s(4)t第二十五页25第二十六页，共166页。关于命题符号化需要注意以下两点：

（1）p、q、r等符号用来代表肯定形式的命题，而不是否定形式的命题。如下面的符号化不合适（不是原子命题）:

命题：今天不是星期二并且今天天晴。设p：今天不是星期二

q：今天天晴则命题符号化为：p∧q。

（2）p、q、r等符号不能用来代表复合命题（上例其实也是这种情况），因为这样会掩盖命题的结构，不利于推理。第二十六页26第二十七页，共166页。定义设p,q是两个命题,复合命题“p或q”称为p与q的析取式，记做p∨q，∨称为析取联结词。“∨”的读法：or

（英）析取、或（中）p∨q的真值定义为：

p∨q为真

iff

p,q至少有一个为真3.或第二十七页27第二十八页，共166页。表2.3p∨q真值表

pqp∨q000110110111p∨q的真值定义为：p∨q为真

iff

p,q至少有一个为真第二十八页28第二十九页，共166页。

析取词∨是自然语言中的连接词“或者”等的逻辑抽象。但自然语言中的“或者”具有二义性：

(1)相容或(可兼或)：用它联结的命题具有相容性：命题可以同时为真，如：张三会讲英语或日语。

(2)排斥或(不可兼或)：用它联结的命题具有排斥性：命题不能同时为真，如：(1)这张桌子是红色或蓝色。

(2)派小王或小李中的一人去开会。∨表示相容或。第二十九页29第三十页，共166页。注：

在使用析取联结词时，首先应分析表达的是可兼或还是不可兼或。若是可兼或，以及p,q不能同时为真的不可兼或①，均可直接符号化为p∨q的形式。如果是不可兼或②，并且p与q可同时为真，就应符号化为(p∧┐q)∨(┐p∧q)的形式。第三十页30第三十一页，共166页。【例】

将下列命题符号化。张三选修了英语课或者微积分课。今晚张三要么只看书要么只听音乐。a>0或a=0。第三十一页31第三十二页，共166页。

分析：

(1)是“可兼或”（为什么？），可用析取式表示：p∨q

其中p:张三选修了英语课，

q:张三选修了微积分课(2)是“不可兼或②”：(p∧┐q)∨(┐p∧q)

(3)是“不可兼或①”：p∨q第三十二页32第三十三页，共166页。定义设p,q是两个命题,复合命题“如果p，则q”称为p与q的蕴涵式（条件式），记做p→q，→称为蕴涵联结词，p称为前件，q称为后件。“→

”的读法：implies,if…then…

（英）蕴涵、如果…则…

（中）p→q的真值定义为：

p→q为假

iff

p为真而q为假4.条件第三十三页33第三十四页，共166页。表2.4p→q真值表pqp→q000110111101p→q的真值定义为：

p→q为假

iff

p为真而q为假第三十四页34第三十五页，共166页。蕴涵词→是自然语言中的连接词“如果……,则……”“只要……,就……”“因为……,所以……”

“只有……,才……”“除非……,否则……”

等的逻辑抽象。

p→q表明的逻辑关系是：p是q的充分条件，q是p的必要条件。第三十五页35第三十六页，共166页。日常生活中的“如果p,则q”是联系两个有逻辑关系的语句p和q。而在数理逻辑中，前件p和后件q可以没有任何逻辑联系，蕴涵式p→q的真值仅由p,q的真值惟一确定。例：如果1+1=2，那么雪是白的。

第三十六页36第三十七页，共166页。在数学和其他自然科学中，“如果p,则q”往往表达前件p为真，后件也为真的推理关系；而在数理逻辑中，当前件p为假，不管后件是真是假，规定

p→q都是真(∵复合命题p→q应有真值)。例：校长宣布：如果气温超过38℃，则全校停课。第三十七页37第三十八页，共166页。

关于“只有……,才……”和“除非……,否则……”的符号化：(1)只有肚子饿了，我才去麦当劳。

其意思相当于：

如果我去麦当劳，则我肚子饿了。设p：我肚子饿了q：我去麦当劳则原命题可符号化为：q→p

。第三十八页38第三十九页，共166页。(2)除非下雨，否则我就骑自行车上班。其意思相当于：

如果不下雨，我就骑自行车上班。设p：天下雨q：我骑自行车上班则原命题可符号化为：┐p→q

。第三十九页39第四十页，共166页。【例】下列命题是否是含有蕴涵的复合命题?若是,指出其前件和后件。a)只要你发给我一个电子邮件，我就会把地址寄给你。b)暖天持续一周苹果树就开花。c)活塞队赢得冠军就意味着他们打败了湖人队。d)必须走8英里才能到朗斯峰的顶峰。e)只有你购买的Mp4机不超过90天，你的保修单才有效。f)如果你驾车超过400英里，就需要买汽油了。第四十页40第四十一页，共166页。g)你获得这一职位表明你有最好的信誉。h)要成为美国公民，只要你生在美国就行了。i)除非下大雨，否则我是一定要出门的。j)要在服务器登录必须有一个有效的口令。第四十一页41第四十二页，共166页。

【定义】设P,Q是两个命题,复合命题“P当且仅当Q”称为P与Q的等价式，记做P

Q，

称为等价联结词。

P

Q的真值定义为：

P

Q为真

iff

P,Q真值相同因此,P,Q一真一假时,P

Q为假。

“

”的读法：ifandonlyif=

iff

（英）

当且仅当、等价

（中）复合命题P

Q的取值如表2―5所示。

第四十二页42第四十三页，共166页。表2-5P

Q真值表

等值词

是自然语言中的连接词“当且仅当”等的逻辑抽象。不难看出(P→Q)∧(Q→P)与P

Q

的逻辑关系完全一致，即都表示P与Q互为充要条件。PQP

Q000110111001第四十三页43第四十四页，共166页。【例】

将下列命题符合化，并讨论它们的真值。π

是无理数当且仅当加拿大位于亚洲。2+3=5的充要条件是是无理数。若两圆O1，O2的面积相等，则它们的半径相等，反之亦然。如果今天是星期三，则地球是圆的，反之，如果地球是圆的，今天是星期三。第四十四页44第四十五页，共166页。【例】

令

P:北京比天津人口多

Q:2+2=4

R:乌鸦是白色的求下列符合命题的真值：

((┐P∧Q)∨(P∧┐Q))→R(Q∨R)→(P→┐R)(┐P∨R)

(P∧┐R)第四十五页45第四十六页，共166页。

翻译时,为了减少圆括号,我们对5个命题联结词的强弱次序规定为

┐、∧、∨、→、

联结词小结：联结词类似于代数中的＋、－、×、/，只不过＋、－、×、/作用的是数（实数，甚至复数），而联结词作用的是命题。也就是说，联结词提供了命题之间的一种运算。在本质上，联结词用于反映复合命题的内部逻辑结构。第四十六页46第四十七页，共166页。练习一个人起初说：“占据空间的，有质量的而且不断变化的叫物质。”后来他改口说：“占据空间的，有质量的叫物质，而物质是不断变化的。”问他前后差异在什么地方，试以命题形式进行分析。第四十七页47第四十八页，共166页。练习1、指出下列语句哪些是命题，哪些不是命题。如果是命题，指出它的真值；如果不是命题，说明理由。（1）离散数学是计算机系的一门必修课。（2）你有空吗？（3）明天我去看电影。（4）请勿随地吐痰！（5）不存在最大的质数。（6）如果我掌握了英语、法语，那么学习其它欧洲语言就容易的多。（7）9＋5≤12。（8）x＝3。（9）我们要努力学习！第四十八页48第四十九页，共166页。2、试把下列命题符号化。（1）或者你没有给我写信，或者它在途中丢失了。（2）假如上午不下雨，我去看电影，否则就在家里读书或看报。（3）我今天进城，除非下雨。（4）仅当你走我将留下（5）如果你来了，那么她唱不唱歌将看你是否伴奏而定第四十九页49第五十页，共166页。逻辑联结词的应用----布尔检索逻辑联结词广泛用于在大量信息中检索，例如，检索网页索引。由于这些检索使用来自命题逻辑的技术，所以称为布尔检索。在布尔检索中，联结词AND用于匹配包含两个检索项的记录，联结词OR用于匹配两个检索项之一或两项均匹配的记录，而联结词NOT用于排除某个特定的检索项。第五十页50第五十一页，共166页。例

网页检索的布尔检索技术。大部分网上检索引擎支持布尔检索，因为它有助于找到有关特定主题的网页。第五十一页51第五十二页，共166页。第五十二页52第五十三页，共166页。第二节命题公式和分类第五十三页53第五十四页，共166页。若P、Q、R、S为命题，则判断以下符号串，哪些构成复杂命题1）┐P→(Q∧┐R)2）(┐P∨┐Q)∧(R→┐s)3）→(┐P→Q)∨(┐∧R∧

┐s)§1命题变元和命题公式怎样的组合方式才能称之为命题公式？第五十四页54第五十五页，共166页。一、命题常元与命题变元命题常项（命题常元）----表示一个确定的、具体的简单命题的标识符。命题常项有确定的真值,其真值不是０就是１。命题变项（命题变元）----表示任意一个命题的标识符，以“真、假”或“1、0”为取值范围,仍用小写字母表示。一个命题变元若被某个确定的命题替代,就具有确定的真值。（参：常数与变量）

注：1）命题变元不是命题。（参：整数变量不是整数。）

2）

P表示命题常元还是命题变元可由上、下文来确定。第五十五页55第五十六页，共166页。二、命题公式【定义】

一个命题公式是由下列规则所产生的符号串:1)单个命题常元或命题变元是命题公式，称为原子命题公式。

2)若A是命题公式,则┐A也是命题公式。

3)若A,B是命题公式,则(A∧B),(A∨B),(A→B),(A

B)也是命题公式。

4)只有有限次地运用1),2),3)所产生的符号串才是命题公式。第五十六页56第五十七页，共166页。

命题公式也简称为公式。上述命题公式的定义采用了递归定义方式。由定义可知,下面的符号串∧P,(P

Q∨)，PQ→R都不是公式。而符号串

((P→Q)→R),((┐P

Q)∨(R∧s))都是公式。为了简便起见,我们常常省去公式最外层的圆括号。所以上面两个公式又可以分别写成

(P→Q)→R,(┐P

Q)∨(R∧s)第五十七页57第五十八页，共166页。一、命题公式的赋值命题公式的真值情况取决于其所含命题变元的真值。

【定义】

设p1,p2,…,pn是出现在公式A中的所有命题变元，给p1,p2,…,pn各指定一个真值，称为对公式A的一个真值指派（也称解释）。§2

命题公式的赋值和真值表N个命题变元有多少中不同的真值指派？第五十八页58第五十九页，共166页。pqp∧q000110110001

p∧q真值表例：成真赋值成假赋值第五十九页59第六十页，共166页。二、真值表的构造【示例】

求公式(p∧q)∧┐p的真值表。

解：分以下4步求得:1)写出个命题变元的真值指派；

2)写出公式p∧q的真值表;3)写出公式┐p的真值表;4)根据2)和3),写出公式(p∧q)∧┐p的真值表。为清楚起见,我们将这4步列在一个表内,见下表。第六十页60第六十一页，共166页。pqp∧q┐p(p∧q)∧┐p00011011000111000000(p∧q)∧┐p的真值表第六十一页61第六十二页，共166页。构造真值表注意事项：命题变元按下标进行排列，若无下标，则按字典顺序进行排列；命题变元的取值按二进制编码从小到大（或从大到小）排列，这样容易做到“不重不漏”；根据经验，最好是逐列求值，而不是逐行求值，这样不容易出错；对于一个具体的命题公式，其真值表究竟分成几列，要根据自己的熟练程度来定。第六十二页62第六十三页，共166页。

pqr┐p┐p∧q┐r(┐p∧q)→┐r【示例】

求(┐p∧q)→┐r的真值表。11110000001100001010101011101111000001010011100101110111第六十三页63第六十四页，共166页。PQ┐P┐QP∧┐PQ∧┐Q(P∧┐P)(Q∧┐Q)0001101111001010【例】

求公式(P∧┐P)

(Q∧┐Q)的真值表000000001111第六十四页64第六十五页，共166页。

PQRP→Q┐(P→Q)┐(P→Q)∧Q┐(P→Q)∧Q∧R000001010011100101110111【示例】求┐(P→Q)∧Q∧R的真值表11110011000011000000000000000000第六十五页65第六十六页，共166页。【定义】

设A为一个命题公式,

(1)若A在它的各种赋值下，其真值恒为１,则称为A重言式或永真式

;

(2)若A在它的各种赋值下，其真值恒为0，则称为A矛盾式或永假式；

(3)若A不是矛盾式（至少存在一种赋值，使A的真值为1），则称其为可满足式

。§3命题公式的分类第六十六页66第六十七页，共166页。

从一个命题公式的真值表可以判断公式的类型：若真值表最后一列全为1，则公式为重言式；若真值表最后一列全为0，则公式为矛盾式；若真值表最后一列至少有一个1，则公式为可满足式。第六十七页67第六十八页，共166页。第3节等值演算与范式第六十八页68第六十九页，共166页。定义设A,B是命题公式,如果在其任意的解释I下，其真值相同，记为A

B。§1等价和基本等价式注：1）区别

与

。

2）等值具有①自反性；②对称性；③传递性。

一、等价定理设A,B是命题公式,A

B的充要条件是命题公式AB是永真式。第六十九页69第七十页，共166页。证明A

B的方法：（1）列举A与B的各种真值指派，证明其各种赋值之下，A与B的真值相同。（2）证明AB是永真式。（3）通过等值演算把A转化为B第七十页70第七十一页，共166页。我们常常利用真值表来判断两个命题公式是否逻辑等价。

【例】证明p→q

┐p∨qpqp→q┐p∨q0001101111011101从真值表可以看出：p→q

┐p∨q第七十一页71第七十二页，共166页。

【例】

判断下面两组公式是否等值：

(1)p→(q→r)与(p∧q)→r

(2)(p→

q)→r

与(p∧q)→r

解：从真值表可以看出：p→(q→r)

(p∧q)→r

但：(p→

q)→r

(p∧q)→r

pqrp→(q→r)(p→

q)→r(p∧q)→r

000001010011100101110111

111111010101110111111101第七十二页72第七十三页，共166页。练习用真值表判断下面两组公式是否等值：1）（(p→q)∧(p→r))，(p→(q∧r))2）┐((p∧q)∨(┐p∧┐q))，((p∨q)∧┐(p∧q))第七十三页73第七十四页，共166页。§2等值演算

1.双重否定律┐┐A

A2.幂等律A∨A

A，A∧A

A4.结合律(A∨B)∨C

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

A∧(B∧C)3.交换率A∨B

B∨A，A∧B

B∧A一、基本等值式第七十四页74第七十五页，共166页。9.同一律A∨0

A，A∧1

A7.吸收律A∨(A∧B)

A，A∧(A∨B)

A5.分配律A∨(B∧C)

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

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

┐A∧┐B┐(A∧B)

┐A∨┐B8.零律A∨1

1，A∧0

0第七十五页75第七十六页，共166页。13.等价等值式(A

B)

(A→B)∧(B→A)

12.蕴含等值式A→B

┐A∨B11.矛盾律A∧┐A

010.排中律A∨┐A

116.归谬论(A→B)∧(A→┐B)

┐A15.等价否定等值式A

B

┐A

┐B14.假言异位A→B

┐B→┐A第七十六页76第七十七页，共166页。

在上面的基本等值式中，很多是成对出现的，如果在仅含有连接词┐、∧,∨的命题公式,将∧,∨,０,１分别换为∨,∧,１,０,就得到另外一个等值式。这些等值式都可用列真值表的方法证明。由于联结词∨、∧满足可结合性，因此可将(P∨Q)∨R和P∨(Q∨R)简记为P∨Q∨R；

(P∧Q)∧R和(P∧Q)∧R简记为P∧Q∧R。第七十七页77第七十八页，共166页。二、代入规则和置换规则

由已知的等值式，可以推演出更多的等值式，我们称由已知的等值式推演出另外的等值式的过程称为等值演算。在等值演算中常使用下面两个重要的规则——代入规则和置换规则。

代入规则:

在等值式中,将某一命题变元都用同一命题公式代入后,得到的公式仍是等值式（反之不成立）（其正确性请读者思考，举反例）。例如,在A→(B→C)

(A∧B)→C中,若用公式(S∨R)代替A,则得

(S∨R)→(B→C)

((S∨R)∧B)→C第七十八页78第七十九页，共166页。

置换规则：

设Φ(A)是含公式A的命题公式，Φ(B)是用公式B置换了Φ(A)中所有的A后得到的命题公式，若A

B,则Φ(A)

Φ(B)

。置换规则的正确性是由于:A

B,所以对任一组命题变元的真值指派,A和B的真值都相同,而Φ(A),Φ(B)除A和B以外的部分都相同,因此Φ(A)和Φ(B)的真值都相同,即有Φ(A)

Φ(B)

。例如：┐Q∧（P→Q）

┐Q∧（┐P∨Q）第七十九页79第八十页，共166页。三、等值演算的用途

1）验证两个公式等值

2）判别命题公式的类型★3）解决实际问题第八十页80第八十一页，共166页。用途1：验证两个公式等值【示例】证明等值式:p→(q→r)

(p∧q)→r。证明p→(q→r)

p→(┐q∨r)(蕴含等值式)

┐p∨(┐q∨r)

(蕴含等值式)

(┐p∨┐q)∨r

(结合律)

┐(p∧q)∨r(德摩根律)

(p∧q)→r(蕴含等值式)这种证明方法我们称之为等值演算推导法。第八十一页81第八十二页，共166页。

【例】用等值演算验证等值式：

┐(p∨q)∨r(德摩根律)

(┐p∧┐q)∨r(幂等律、吸收律)

证(p→r)∧(q→r)

(┐p∨r)∧(┐q∨r)(蕴含等值式)(p∨q)→r

(p→r)∧(q→r)

(p∨q)→r(蕴含等值式)(┐p∧┐q)∨(┐p∧r)∨(r∧┐q)∨(r∧r)(分配律)第八十二页82第八十三页，共166页。

【示例】

证明等值式:(p∧q)→r

(p→q)→(p→r)。

证：(p→q)→(p→r)

┐(┐p∨q)∨(┐p∨r)(蕴含等值式)

(┐(┐p∨q)∨┐p)∨r(结合律)

(p∧q)→r(蕴含等值式)

┐(p∧q)∨r

(德摩根)

(┐q∨┐p)∨r(同一律)

(1∧(┐q∨┐p))∨r(排中律)

((p∨┐p)∧(┐q∨┐p))∨r(分配律)

((p∧┐q)∨┐p)∨r

(德摩根、双重否定律)第八十三页83第八十四页，共166页。用途2：判别命题公式的类型【例1.12】

用等值演算法判断下列公式的类型：(p→q)∧p→q

┐(p→(p∨q))∧rp∧(((p∨q)∧p)→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)∨q

┐q∨┐p∨q

┐q∨q∨┐p

1

∨┐p

1

所以，公式(1)是一个重言式。重言式永假式可满足式第八十四页84第八十五页，共166页。等值演算练习一、证明下列等价式。(1)A→(B→A)

┐A→(A→┐B)(2)┐(P∨┐Q)→(Q→R)

Q→(P∨R)二、用等值演算法判断下列公式的类型（1）┐((P∧Q)→P)（2）(┐P→Q)→(Q→┐P)第八十五页85第八十六页，共166页。用途3：解决实际问题A,B,C,D4人做百米竞赛，观众甲、乙、丙预报比赛的名次为：甲：C第一，B第二；乙：C第二，D第三；丙：A第二，D第四比赛结束后发现甲、乙、丙每人报告的情况都是各对一半，试问实际名次如何（无并列者）？解：ai,bi,ci,di表示A,B,C,D第i名，i=1,2,3,4①(c1∧┐b2)∨(┐c1∧b2)

1②(c2∧┐d3)∨(┐c2∧d3)

1③(a2∧┐d4)∨(┐a2∧d4)

1第八十六页86第八十七页，共166页。①∧②

1，C不能既第一又第二，B和C不能都第二，所以((c1∧┐b2)∨(┐c1∧b2))∧((c2∧┐d3)∨(┐c2∧d3))

(c1∧┐b2)∧((┐c2∧d3)∨(c2∧┐d3))∨(┐c1∧b2)∧((┐c2∧d3)∨(c2∧┐d3))(c1∧┐b2∧┐c2∧d3)∨(c1∧┐b2∧c2∧┐d3)

∨(┐c1∧b2∧┐c2∧d3)∨(┐c1∧b2∧c2∧┐d3)

(c1∧┐b2∧┐c2∧d3)∨(┐c1∧b2∧┐c2∧d3)1④(c1∧┐b2∧┐c2∧d3)∨(┐c1∧b2∧┐c2∧d3)1第八十七页87第八十八页，共166页。③∧④

1且A，B不能同时第二，D不能第三又第四，所以((a2∧┐d4)∨(┐a2∧d4))∧((c1∧┐b2∧┐c2∧d3)∨(┐c1∧b2∧┐c2∧d3))(a2∧┐d4)∧((c1∧┐b2∧┐c2∧d3)∨(┐c1∧b2∧┐c2∧d3))

∨(┐a2∧d4)∧((c1∧┐b2∧┐c2∧d3)∨(┐c1∧b2∧┐c2∧d3))(a2∧┐d4∧c1∧┐b2∧┐c2∧d3)∨(a2∧┐d4∧┐c1∧b2∧┐c2∧d3)∨(┐a2∧d4∧c1∧┐b2∧┐c2∧d3)∨(┐a2∧d4∧┐c1∧b2∧┐c2∧d3)(a2∧┐d4∧c1∧┐b2∧┐c2∧d3)1所以C第一，A第二，D第三，B第四第八十八页88第八十九页，共166页。（补）逻辑等价的应用【例】利用基本的逻辑等价关系，化简电路图rpsqpspqrp解：上述电路图可描述为：((p∧q∧r)∨(p∧q∧s))∧((p∧r)∨(p∧s))第八十九页89第九十页，共166页。利用基本逻辑等价式，化简公式可得：

((p∧q∧r)∨(p∧q∧s))∧((p∧r)∨(p∧s))=((p∧q∧(r∨s))∧(p∧(r∨s))=p∧q∧(r∨s)；srqp第九十页90第九十一页，共166页。【例】将下面程序语言进行化简。ifAthen

ifBthenXelseYelseifBthenXelseYTFFTFTStartAXYEndBB

解：执行X的条件为：

(Ａ∧Ｂ)∨(

Ａ∧Ｂ)

执行Y的条件为：

(Ａ∧

Ｂ)∨(

Ａ∧

Ｂ)第九十一页91第九十二页，共166页。

执行X的条件可化简为：

(Ａ∧Ｂ)∨(

Ａ∧Ｂ)＝(Ａ∨

Ａ)∧Ｂ＝Ｂ执行Y的条件可化简为：

(Ａ∧

Ｂ)∨(

Ａ∧

Ｂ)＝(Ａ∨

Ａ)∧

Ｂ＝

ＢTXYEndStartBF程序可简化为：IfBthenXelseY第九十二页92第九十三页，共166页。思考以下问题：（1）(0001010)2与(10)10

那个大？（2）两个形式不同的命题公式是否等值？（3）为什么要有范式？为命题公式制定一种标准表达形式，使得命题公式的成真或成假赋值一目了然。§3范式第九十三页93第九十四页，共166页。要了解什么是范式,先得介绍组成范式的基本成分——简单合取式和简单析取式。

【定义】

仅由命题变元或命题变元的否定所组成的析取式称为简单析取式，仅由命题变元或命题变元的否定所组成的合取式称为简单合取式。一、范式第九十四页94第九十五页，共166页。

若p,q,r是命题变元,则

p,q,r,┐p,┐q∧r,r∧┐r,p∧q∧r,p∧┐q∧┐p等都是简单合取式;p,q,r,┐p,┐p∨r,p∨┐r,p∨q∨r,p∨┐q∨┐p等都是简单析取式。第九十五页95第九十六页，共166页。

【定义】由有限个简单合取式的析取构成的析取式称为析取范式。由有限个简单析取式的合取构成的合取式称为合取范式。析取范式和合取范式统称为范式。设Ai(i=1,2,…,n)为简单合取式，则A=A1∨A2∨…∨An为A析取范式。设Bi(i=1,2,…,n)为简单析取式，则B=B1∧B2∧…∧Bn为B合取范式。

注意：一个简单合取式为即为析取范式，又为合取范式。第九十六页96第九十七页，共166页。公式A的析取范式常用来判定A是否是矛盾式;

公式A的合取范式常用来判定A是否是重言式。

【定理】(1)一个析取范式为矛盾式当且仅当它的每个简单合取式都是矛盾式。

(2)一个合取范式为重言式当且仅当它的每个简单析取式都是重言式。

第九十七页97第九十八页，共166页。

【定理】(范式存在定理)任一命题公式都存在与之等值得析取范式与合取范式。

从定义可知,一个范式有以下特征:1)不含蕴含联结词→和等价联结词

;2)不含双重否定┐┐;3)否定词┐仅出现在命题变元之前;4)析取范式是简单合取式的析取,而合取范式是简单析取式的合取。

所以,求一个公式的范式就是求满足以上四点的公式。其具体步骤是:

第九十八页98第九十九页，共166页。1)消去联结词→和

:

p→q

┐p∨q

p

q

(p→q)∧(q→p)

(┐p∨q)∧(┐q∨p)(1)

(p∧q)∨(┐p∧┐q)(2)

把p

q化为(1)还是(2)依所求的是析取范式还是合取范式而定。

2)消去┐┐:┐┐p

p3)使┐出现在命题变元之前:┐(p∨q)

┐p∧┐q┐(p∧q)

┐p∨

┐q4)利用分配律将公式化为所求范式:

p∧(q∨r)

(p∧q)∨(p∧r)

p∨(q∧r)

(p∨q)∧(p∨r)第九十九页99第一百页，共166页。【例】

求下面公式的析取范式（1）(P∨Q)→((QR)∧S)（2）(P→┐Q)→((Q∨R)→┐S)(1)(P∨Q)→((QR)∧S)

┐(P∨Q)∨((┐Q∨R)∧

(┐R

∨Q)∧S)

(

┐P∧

┐Q)∨((┐Q∨R)∧

(┐R

∨Q)∧S)

(

┐P∧

┐Q)∨((┐Q∧

┐R)∨(R

∧Q)∧S)

(

┐P∧

┐Q)∨(┐Q∧

┐R∧S)∨(R

∧Q∧S)

第一百页100第一百零一页，共166页。（2）(P→┐Q)→((Q∨R)→┐S)┐(┐P∨┐Q)∨

(┐(Q∨R)∨┐S)(P∧Q)∨

(

(┐Q∧┐

R)∨┐S)(P∧Q)∨

(┐Q∧┐

R)∨┐S第一百零一页101第一百零二页，共166页。【例】

求下面公式的合取范式:（1）(P→Q)→R（2）P→(Q

R)（3）(┐P→Q)→(Q∧(R→S)）(P→Q)→R

┐(┐

P∨Q)∨R

(P∧

┐Q)∨R

(P∨R）∧（

┐

Q∨R)第一百零二页102第一百零三页，共166页。(2)P→(Q

R)

┐P∨((┐Q∨R)∧(

┐R∨Q))(┐P∨┐Q∨R)∧(┐P∨┐R∨Q)(3)(┐P→Q)→(Q∧(R→S))

┐(P∨

Q)∨

(Q∧(┐

R∨

S))

(┐P∧

┐Q)∨

(Q∧(┐

R∨

S))((┐P∧

┐Q)∨Q)∧((┐P∧

┐Q)∨(┐R∨S))((┐P∨Q)∧(

┐Q∨Q))∧((┐P∧

┐Q)∨(┐R∨S))

(┐P∨Q)∧((┐P∨┐R∨S)∧(┐Q∨┐R∨S))

(┐P∨Q)∧(┐P∨┐R∨S)∧(┐Q∨┐R∨S)第一百零三页103第一百零四页，共166页。二、主范式为使范式惟一,我们引入了一种特殊的范式——主范式。主范式的基本成分是特殊的简单合取式和简单析取式,它们分别称为极小项和极大项。

1、极小项和极大项【定义】

设有n个命题变元p1,p2,…,pn,则简单合取式p1′∧p2′∧…pn′称为由n个命题变元所产生的极小项，简单析取式p1′∨p2′∨…pn′

称为由n个命题变元p1,p2,…,pn所产生的极大项。其中pi′或为pi或为┐pi（i=1,2,…,n）。第一百零四页104第一百零五页，共166页。极大、极小项的特征：极小项————n个变元不重不漏的简单合取式极大项————n个变元不重不漏的简单析取式示例：若有三个命题变元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所产生的极大项。一般地,由ｎ个命题变元所产生的全部不同的极小项和极大项都是2n个。第一百零五页105第一百零六页，共166页。

每个极小项p1′∧p2′∧…pn′都有且仅有一个成真赋值，不妨假设其对应的二进制数为δ1δ2……δn

,其中：(i=1,2,…,n）

每个极大项p1′∨p2′∨

…pn′

都有且仅有一个成假赋值，不妨假设其对应的二进制数为δ1δ2……δn

,其中：(i=1,2,…,n）注意：δi

的取值规则极小项与极小项时正好相反第一百零六页106第一百零七页，共166页。

如果一个极小项对应的二进制数为δ1δ2…δn，则将对应的十进制数r作为该极小项的序号，并将该极小项简记为mr。显然r从０取到2n－1。以３个命题变元p1,p2,p3为例,极小项┐p1∧┐p2∧┐p3对应的二进制数为000,其序号为０，用m0表示;极小项┐p1∧p2∧p3对应的二进制数为011,其序号为3，用m3表示。反之,如果要求m5对应的极小项，因为序号5对应的二进制数为101，所以该极小项是p1∧┐p2∧p3。由此可见,极小项与其序号一一对应。第一百零七页107第一百零八页，共166页。8个极小项对应情况如下：极小项成真赋值记号┐p∧┐q∧┐r－－000－－0记作m0┐p∧┐q∧r－－001－－1记作m1┐p∧q∧┐r－－010－－2记作m2┐p∧q∧r－－011－－3记作m3p∧┐q∧┐r－－100－－4记作m4p∧┐q∧r－－101－－5记作m5p∧q∧┐r－－110－－6记作m6p∧q∧r－－111－－7记作m7第一百零八页108第一百零九页，共166页。极小项的性质：(1)对一个含有n个变项的公式来说,所有可能的极小项个数和该公式的解释个数一样多,都是2n

。(2)每个极小项只在一个赋值下为真，且与它所对应的二进值编号相同。(3)极小项两两不等值,而且mi∧mj=F(i,j)。(4)任一含有n个变项的公式,都可由k个(k≤2n)极小项的析取来表示。第一百零九页109第一百一十页，共166页。

类似地，如果一个极大项对应的二进制数为δ1δ2…δn，就将对应的十进制数r作为该极大项序号，并将该极大项简记为Mr。显然r从０到2n－1。以３个命题变元P1,P2,P3为例,

极大项p1∨p2∨p3对应的二进制数为000,其序号为０，用M0表示；极大项┐p1∨p2∨p3对应的二进制数为100,其序号为4，用M4表示。反之,如果要求M5对应的极大项，因为序号5对应的二进制数为101，所以该极大项是┐p1∨p2∨┐p3。由此可见,极大项与其序号一一对应。第一百一十页110第一百一十一页，共166页。8个极大项对应情况如下：极大项成假赋值记号p∨q∨r－－000－－0记作M0p∨q∨┐r－－001－－1记作M1p∨┐q∨r－－010－－2记作M2p∨┐q∨┐r－－011－－3记作M3┐p∨q∨r－－100－－4记作M4┐p∨q∨┐r－－101－－5记作M5┐p∨┐q∨r－－110－－6记作M6┐p∨┐q∨┐r－－111－－7记作M7第一百一十一页111第一百一十二页，共166页。极大项的性质：对一个含有n个变项的公式来说,所有可能的极大项个数和该公式的解释个数一样多,都是2n

。每个极大项只在一个解释下为假，且与它所对应的二进值编号相同。极大项两两不等值,而且Mi∨Mj=T(i≠j)。任一含有n个变项的公式,都可由k个(k≤2n)极大项的合取来表示。

第一百一十二页112第一百一十三页，共166页。2、极小项与极大项的关系

【定理】设mi与Mi是有命题变元p1,p2,…pn形成的极小项和极大项，则┐mi

Mi，

┐

Mi

mi3、主析取范式与主合取范式

【定义】由若干不同的极小项所组成的析取式叫做主析取范式。由若干不同的极大项所组成的合取式叫做主合取范式。

【定义】与公式A等值的主析取范式（主合取范式）称为公式A的主析取范式（主合取范式）。

【定理】（存在唯一性）

任何命题公式都存在与之等值的主析取范式和主合取范式，并且是唯一的。第一百一十三页113第一百一十四页，共166页。4、主范式的求法一般有两种方法：

(1)真值表方法

(2)公式化归法-----等值推演方法下面先通过例子来说明真值表方法。

【例】

求命题公式p→q的主析取范式和主合取范式。所有p→q

m0∨

m1∨

m3

M2pqp→q极小项极大项000110111101m0m1m3M2第一百一十四页114第一百一十五页，共166页。pqp→qm0┐p∧┐qm1┐p∧qm3p∧qm0∨m1∨m3M2p∧┐q00011011110110000100000111011101第一百一十五页115第一百一十六页，共166页。由前面的例子可以归纳出真值表法的步骤：1)

写出命题公式的真值表。2)

找出所有的成真赋