离散数学及其应用-课件 马立和 第1-5章 命题逻辑-函数

1.1命题和联结词1.2命题公式及分类1.3等值演算1.4联结词全功能集1.5对偶对范式1.6推理理论第一章命题逻辑。

命题任何基于命题分析的逻辑称为命题逻辑。定义1.1.1命题：能唯一判断真假的陈述句1.1.1命题命题的值

真,用T(或1)表示假,用F(或0)表示

下列语句是命题？【例1.1.1】判断下列句子哪些是命题:(1)2是偶数。(2)3能被2整除。(3)《几何原本》的作者是欧几里得。(4)2012年12月21日是玛雅人所说的世界末日。(5)地球外也有生命存在。(6)这盆花真漂亮!(7)你吃早餐了吗?(8)我正在说谎。(9)x>1。1.1.1命题解(1)是真命题。(2)是假命题。(3)可能有些人不能确定真假,但客观上能判断真假。(4)是假命题。(5)的真值也是客观存在的,只是人类尚不知道,未来随着科学技术的发展,其真值是可以知道的,所以也是命题。(6)(7)均不是陈述句,所以不是命题。(8)虽然是陈述句,但它的真假无法确定,即它是悖论,所以不是命题。(9)是陈述句,但它的真假取决于变量x的取值,当取x为2其值为1,取x为1时其值为0,其真值不唯一,因此不是命题1.1.1命题判断给定的句子是否为命题的基本步骤：(1)语句必须是陈述句。

(2)陈述句必须具有唯一的真值。说明：

(1)一个陈述句在客观上能判断真假，而不受人的知识范围

的限制。

(2)一个陈述句暂时不能确定真值，但到了一定时候就可以确定，与一个陈述句的真值不能唯一确定是不同的。1.1.1命题

命题的分类

原子命题——不可剖开或分解为更简单命题的命题，也称为简单命题。用p、q、r、pi、qi、ri等符号表示(必要时亦可用其他小写的英文字母表示)。

复合命题——由原子命题利用联结词构成的命题。

用了“且”、“非”、“或”、“如果……则……”、“当且仅当”等联结词。

1.1.2命题的类型【例1.1.2】下列命题不是简单命题:(1)5不是偶数。(2)小王既懂英语又懂法语。(3)李林不仅聪明而且用功。(4)如果你努力,则你能成功。(5)只要李明努力学习,他就会取得好成绩。1.1.2命题的类型下列句子是否复合命题？（1）并非雪是白的。（2）今晚我看书或者去看电影。（3）如果天气好，那么我去接你。（4）偶数a是质数，当且仅当a=2（a是常数）。（5）Tom和John是兄弟。

（6）2是偶数且3也是偶数。（7）你去了学校，我去了工厂。1.1.2命题的类型联结词联结词确定复合命题的逻辑形式，它来源于自然语言中的联结词，但与自然语言中的联结词有一定的差别；原子命题和联结词可以组合成复合命题。从本质上讲，这里讨论的联结词只注重“真值”，而不顾及具体内容，故亦称“真值联结词”。

1.1.3联结词

1.否定“┐”

设p为任一命题，复合命题“非p”(p的否定)称为p的否定式，记作：┐p。“┐”为否定联结词。┐p的真值亦可由表1.1.1所示的称为“真值表”的表格确定。由表1.1.1可知：命题┐p为真，当且仅当p为假。事实上，它定义了一个一元函数(称为一元真值函数)：1.1.3联结词1.1.3联结词p┐p0110表1.1.1

【例1.1.3】(1)p:2是素数。其真值为1。p:2不是素数。其真值为0。(2)p:煤炭是白色的。真值为0。p:煤炭是不是白色的。真值为1。(3)q:这些人都是学生。q:这些人不都是学生。但有时也会将带有“不”字的命题设为原子命题,例如:设p,p:今天天气不冷。1.1.3联结词

2.合取“∧”

设p、q是任意两个命题，复合命题“p且q”(p与q)称为p与q的合取式，记作：p∧q。“∧”是合取联结词。p∧q为真，当且仅当p、q均为真。1.1.3联结词

p∧q的真值表如表1.1.2所示，它定义了一个二元真值函数：

f∧：{00，01，10，11}→{0，1}

f∧(00)=0

f∧(01)=0

f∧(10)=0

f∧(11)=11.1.3联结词1.1.3联结词pqp∧q000010100111表1.1.2

【例1.1.4】(1)p:李丽聪明。q:李丽用功。则p∧q:李丽既聪明又用功。(2)p:2是偶数。r:煤是白的。则p∧r:2是偶数且煤是白的。1.1.3联结词

3.析取“∨”

设p、q是任意两个命题，复合命题“p或q”称为p、q的析取式，记作：p∨q。“∨”称为析取联结词。

p∨q为假，当且仅当p、q同为假。1.1.3联结词

p∨q的真值表如表1.1.3所示，它定义了一个二元真值函数：

f∨：{00，01，10，11}→{0，1}

f∨(00)=0

f∨(01)=1

f∨(10)=1

f∨(11)=11.1.3联结词1.1.3联结词pqp∨q000011101111表1.1.3

【例1.1.5】(1)p:派小王去出差。q:派小李去出差。则p∨q:派小王或小李去出差。(2)p:明天刮风。q:明天下雨。则p∨q:明天或者刮风或者下雨。1.1.3联结词可兼的“或”——不可兼的“或”【例1.1.6】李林明天出差去北京或去南京。p:“李林明天出差去北京”。q:“李林明天出差去南京”。分析(1)p、q可以同时为假,此时是假命题。(2)p为真、q为假,此时是真命题。(3)p为假、q为真,此时是真命题。然而,p、q不能同为真。因此,当且仅当只有其中一个命题为真时,其真值为1。这时的“或”具有排斥性,是“不可兼或”,不能用“∨”联结。解(p∧q)∨(p∧q)或(p∨q)∧(p∧q)。1.1.3联结词

4.蕴含“→”

设p、q是任意两个命题，复合命题“如果p，则q”称为p与q的蕴含式，记作：p→q。

p称为蕴含式的前件，q称为蕴含式的后件，→称为蕴含联结词。p→q为假，当且仅当p为真、q为假。1.1.3联结词

p→q的真值表如表1.1.4所示，它定义了一个二元真值函数：

f→：{00，01，10，11}→{0，1}

f→(00)=1

f→(01)=1

f→(10)=0

f→(11)=11.1.3联结词1.1.3联结词pqp→q001011100111表1.1.3【例1.1.7】p:明天天气晴。q:我们去爬山。则p→q:如果明天天气晴,则我们去爬山。【例1.1.8】符号化下列命题:(1)只要小明努力学习,他就会取得好成绩。(2)只有小明努力学习,他才会取得好成绩。(3)除非小明努力学习,否则他不会取得好成绩。(4)仅当小明努力学习,他才会取得好成绩。解设p:小明努力学习。q:他会取得好成绩。则(1)符号化为p→q。(2)(3)(4)均符号化为q→p(或等价形式:p→q)。1.1.3联结词1.1.3联结词注意：

1.前件为假时，蕴含式命题为真

2.蕴含式前件、后件可以毫不相关。

3.可以将蕴含看作充分条件.如果P是充分条件的前件,q是后件,那么P蕴含q的意思就是有P必有q。在日常语言中，特别是在数学语言中，q是p的必要条件还有许多不同的叙述方式，如：“p仅当q(仅当q，则p)”、“只有q才p”、“只要p就q”、“除非q，否则非p(非p，除非q)”等，均可符号化成p→q

的形式。【例】

符号化下列命题：

(1)只要天下雨，我就回家。

(2)只有天下雨，我才回家。

(3)除非天下雨，否则我不回家。

(4)仅当天下雨，我才回家。

解设p：天下雨。q：我回家。则(1)符号化为p→q。(2)、(3)、(4)均符号化为q→p(或等价形式：┐p→┐q)。1.1.3联结词【例】甲对乙说：“如果今晚我们班上不开会，则我就和你一起去玩。”请问：在什么情形下，乙认为甲的这句话是假？解：如果班上没有开会，甲与乙一起去玩，则自然认为甲说的话为真；如果班上没有开会，甲没有与乙一起去玩，则显然认为甲的话为假；如果班上开会了，甲没有与乙一起去玩，则没有理由认为甲的话为假；如果班上开会了，但甲未参加而与乙一起去玩了，则也不能认为甲的话为假。1.1.3联结词在自然语言中，对于“如果……则……”这样的语句，当前提为假时，结论不管真假，这个语句的意义是无法判断的。因此在条件命题中，当前提为假时无论结论真值如何，其取值都为真的情况称为“善意的推定”。1.1.3联结词

5.等价“

”

设p、q是任意两个命题，复合命题“p当且仅当q”称为p与q的等价式，记作：p

q。“

”称为等价联结词。p

q为真，当且仅当p、q真值相同。

1.1.3联结词p

q的真值表如表1.1.5所示，它定义了一个二元真值函数：

：{00，01，10，11}→{0，1}

(00)=1(01)=0

(10)=0(11)=11.1.3联结词1.1.3联结词pqp

q001010100111表1.1.5【例1.1.9】(1)p:3>6。q:10>11。则p↔q:3>6当且仅当10>11。(2)p:1=1。q:中国的首都是北京。则p↔q:1=1当且仅当中国的首都是北京。“↔”的逻辑关系是:所联结的二命题互为充分必要条件。1.1.3联结词以上定义了5种联结词，它们构成了一个联结词集合{

┐，∧，∨，→，

}。其中┐是一元联结词，其余均为二元联结词，亦称逻辑运算符。将命题用联结词联结成复合命题的过程也称命题的逻辑运算。对自然语言中的一些复杂语句进行形式化，过程如下：

(1)用p、q、r等字母(命题表示符)表示简单命题。

(2)用逻辑联结词，根据自然语言中联结词的逻辑含义，将简单命题符联结起来。1.1.4联结词的应用【例1.1.10】将下列自然语言形式化:(1)李林与万丽都喜欢足球运动。(2)小明虽然聪明,但不用功。(3)于欣欣生于1995年或1996年。(4)除非小赵穿雨衣,否则天没有下雨。(5)锲而不舍,金石可镂;锲而舍之,朽木不折。1.1.4联结词的应用解(1)设p:李林喜欢足球运动,q:万丽喜欢足球运动。则原命题符号化为p∧q(2)设p:小明聪明,q:小明用功。则原命题符号化为p∧¬q(3)设p:于欣欣生于1995年,q:于欣欣生于1996年。则原命题符号化为(p∧¬q)∨(¬p∧q)或(p∨q)∧¬(p∧q)(4)设p:小赵穿雨衣,q:天下雨。则原命题符号化为¬q→p(5)设p:你锲,q:你舍,r:金石可镂,s:朽木折。则原命题符号化为((p∧¬q)→r)∧((p∧q)→¬s)1.1.4联结词的应用解：(1)设p：今天天下雨，q：今天天刮风，r：我去

书店。则原命题符号化为：

(┐p∧┐q)→r(2)设p：小王走路，q：小王唱歌。则原命题符号化为：

p∧q(3)设p：a能被2整除，q：a能被4整除。则原命题符号化为：

┐p→┐q

或q→p1.1.4联结词的应用(4)设p：小刚在学习，q：小刚在玩游戏。则原命题符号化为：

(p∧┐q)∨(┐p∧q)(5)设p：今天天下雨，q：我们去打篮球，r：今天班上有会。则原命题符号化为：

┐r→(┐p→q)或(┐r∧┐p)→q

1.1.4联结词的应用说明：使用多个联结词可以组成更复杂的复合命题，并可使用圆括号（、），（、）必须成对出现。联结词的运算优先顺序：1）（），﹁，∧，∨，→，

；自左向右优先级降低；2）同一优先级的运算从左至右顺序进行。1.1.4联结词的应用【例】设P：5＞3Q：2+2=4R：乌鸦是白色的求下列复合命题的真值：1）（（﹁P∧Q）∨（P∧﹁Q））∧R2）（Q∨R）→（P→﹁R)解：P，Q，R的真值分别为1，1，0，根据运算规则算出1），2）的真值分别是0，1。1.1.4联结词的应用【例】

令p：北京人口比天津多，

q：2+2=4，

r：乌鸦是白色的。

求下列复合命题的真值：

(1)（(┐p∧q)∨(p∧┐q))→r

(2)(q∨r)→(p→┐r)

(3)(┐p∨r)

(p∧┐r)

1.1.4联结词的应用1.1命题和联结词1.2命题公式及分类1.3等值演算1.4联结词全功能集1.5对偶对范式1.6推理理论第一章命题逻辑1.2.1命题公式的相关定义命题公式

命题常元：一个真值确定的命题。命题变元：一个真值尚未确定的命题，以p、q、r等表之。注意：命题变元不是命题，它只是一个可以用来表示命题的符号，因此没有确定的真值，只有当变元被代以确定的命题时，它变成了常元，此时方有真值。定义1.2.1命题公式的定义命题公式：由命题变元(常元)符、联结词和圆括号按一定逻辑关系联结起来的字符串。合理的命题公式叫做合式公式，记作：wff(wff=WellFormedFormulas)，也称真值函数。1.2.1命题公式的相关定义合式公式的递归定义定义1.2.1

合式公式的递归定义：［1］单个的命题符(或常元或变元)是合式公式。［2］如果A是一个合式公式，则(┐A)也是合式公式。［3］如果A、B均是合式公式，则(A∧B)、(A∨B)、(A→B)、(A

B)也都是合式公式。［4］只有有限次地应用［1］、［2］、［3］组成的字符串才是合式公式。

1.2.2合式公式注意：(1)A、B均代表任意的命题公式。(2)为方便起见，公式最外层及(┐A)的括号可省略。如果不写括号，通常默认联结词的优先级为：┐，∧，∨，→，

。1.2.2合式公式定义1.2.2层次(1)若A是单个命题(变元或常元)，则称为0层公式。(2)称A为n+1(n≥0)层公式是指A符合下列诸情况之一：①A=┐B，B是n层公式；

②A=B∧C，其中B为i层公式，C为j层公式，n=max(i，j)；

③A=B∨C，其中B、C的层次同②；

④A=B→C，其中B、C的层次同②；

⑤A=B

C，其中B、C的层次同②。1.2.2合式公式解释：指定命题变元代表某个具体的命题。

1.2.3命题公式的解释与真值表【例1.2.1】公式：A=(p∧q)→r。解释I1：假设

p：现在是白天，q：现在是晴天，r：我们能看见太阳。则A：如果现在是白天且是晴天，则我们能看见太阳。其真值为1。解释I2：假设p、q如上，r：我们能看见星星。则A：如果现在是白天且是晴天，则我们能看见星星。其真值为0。1.2.3命题公式的解释与真值表赋值

(真值指派)：对命题变元指派确定的真值。赋值是一组由0、1构成的数串，按字典顺序(或下标)对应公式中的命题符。如例1.2.1中，对公式A=(p∧q)→r：解释I1实际上是对变元p、q、r赋值111，得A的真值为1；解释I2实际上是对变元p、q、r赋值110，得A的真值为0；A的真值是在对p、q、r的某种赋值下所得的真值。

1.2.3命题公式的解释与真值表定义1.2.3

设p1，p2，…，pn是公式A中所包含的所有命题变元，给p1，p2，…，pn各赋一个真值称为对A的一个赋值，那些使A的真值为1的赋值称为A的成真赋值，使A的真值为0的赋值称为A的成假赋值。如例1.2.1中，111是A=(p∧q)→r的成真赋值，110是A的成假赋值。根据前面对联结词的讨论知：001、011、101、000、010也都是A的成真赋值。1.2.3命题公式的解释与真值表问题：若公式A含有n(n≥1)个命题变元，那么对A共有多少种不同的赋值？答：因为n个变元赋值后形成一个n位的二进制数，所以共有2n个。1.2.3命题公式的解释与真值表将公式A在所有赋值情况下的取值列成表，称为A的真值表。构造真值表的步骤如下：(1)找出命题公式中所含的所有命题变元并按下标或字典顺序给出；(2)按从低到高的顺序写出公式的各层次；(3)顺序列出所有的赋值(2n个)；对应每个赋值，计算命题公式各层次的真值，直到最后计算出命题公式的真值。1.2.3命题公式的解释与真值表

【例1.2.2】

求下列命题公式的真值表：(1)(┐p∧q)→q(2)┐(p→q)

┐(p∧┐q)(3)(p→q)∧┐r解

(1)公式(┐

p∧q)→q的真值表如表1.2.1所示。(2)公式┐(p→q)

┐(p∧┐q)的真值表如表1.2.2所示。(3)公式(p→q)∧┐r的真值表如表1.2.3所示。1.2.3命题公式的解释与真值表表1.2.1pq┐p┐p∧q(┐p∧q)→q001010111110001110011.2.3命题公式的解释与真值表表1.2.2pqp→q┐(p→q)┐pp∧┐q┐(p∧q)┐(p→q)

┐(p∧q)001010100110001010011100111100101.2.3命题公式的解释与真值表表1.2.2pqrp→q┐r(p→q)

∧┐r0001110011000101110111001000101010001101111111001.2.3命题公式的解释与真值表1.2.4命题公式的分类命题公式的分类：

永真式

(重言式)：所有赋值均为成真赋值的公式。永假式(矛盾式)：所有赋值均为成假赋值的公式。可满足式：至少有一组赋值是成真赋值的公式。

1.2.5例题选解【例1.2.3】

求下列命题公式的类型：

(1)（┐p∧q）→q

(2)（p→q）→┐r

将下列命题符号化。

(1)晚上做完了作业，如果有时间，他就会看电视或去公园散步。

(2)如果天不下雨，我们去打篮球，否则在教室自习。

(3)辱骂和恐吓绝不是战斗。

(4)鱼和熊掌不可兼得。

1.2.5例题选解（1）设p：他晚上做完了作业，q：他有时间，r：他看电视，s：他去公园散步。则原命题符号化为：

(p∧q)→(rs)

(2)设p：今天天下雨，q：我们去打篮球，r：我们在教室自习。则原命题符号化为：

(┐p→q)∧(p→r)(3)设p：辱骂不是战斗，q：恐吓不是战斗。则原命题符号化为：

p∨q(4)设p:鱼可得,q:熊掌可得。则原命题符号化为：

┐(p∧q)1.2.5例题选解1.3等值演算命题公式间的重要关系之一：逻辑等值（逻辑等价）1.3等值演算【例1.3.1】构造公式┐p∨q、┐(p∧┐q)、p→q、┐q→┐p的真值表。表1.3.1pq┐p∨q(p∧┐q)┐(p∧┐q)p→q┐q→┐p00101110110111100100011101111.3等值演算解:公式┐p∨q、┐(p∧┐q)、p→q、┐q→┐p的真值表如表1.3.1所示。定义1.3.1

设A、B是任意两个命题公式，若等价式A

B为重言式，则称A与B是等值的，记作：A<=>B。等值也称为等价的、逻辑等值的、逻辑等价的。1.3.1公式等值定理1.3.1A

B为重言式，当且仅当A、B具有相同的真值表。

1.3.1公式等值说明：

(1)如果A

B不是重言式，则称A与B不等值，可记作：A<≠>B。(2)“<=>”与“=”不同，“A=B”表示两个公式一样，“A<=>B”表示两个公式真值一样，如：┐p∨q<=>p→q，但是┐p∨q≠p→q。(3)“<=>”与“

”是两个完全不同的符号。“

”既是联结词，也是运算符，A

B是一个公式。“<=>”不是联结词，而是两个公式之间的关系符，A<=>B并不是一个公式，而只是表示A与B是两个真值相同的公式。1.3.1公式等值为了判断两个公式是否是等值，一般可以通过将两个公式的真值表列出，判断两个真值表是否相同来判定。1.3.2基本等值定律1.3.2基本等值定律基本定律最基本、最重要的逻辑等价公式：(1)双重否定律A<=>┐┐A

(2)幂等律

A<=>A∨A

A<=>A∧A

(3)交换律

A∨B<=>

B∨AA∧B<=>

B∧A

(4)结合律

(A∨B)∨C<=>A∨(B∨C)

(A∧B)∧C

<=>

A∧(B∧C)(5)分配律

A∨(B∧C)<=>(A∨B)∧(A∨C)

A∧(B∨C)<=>(A∧B)∨(A∧C)

(6)德·摩根律

┐(A∨B)<=>┐A∧┐B

┐(A∧B)<=>┐A∨┐B

(7)吸收律

A∨(A∧B)<=>A

A∧(A∨B)<=>A

(8)零律

A∨1<=>1A∧0<=>0

(9)同一律

A∨0<=>A

A∧1<=>A

(10)排中律

A∨┐A<=>1

(11)矛盾律

A∧┐A<=>0

(12)蕴含等值式A→B<=>┐A∨B

(13)等价等值式A

B<=>(A→B)∧(B→A)

(14)假言易位A→B<=>┐B→┐A1.3.2基本等值定律

(15)等价否定等值式A

B<=>┐A

┐B(16)归谬论(A→B)∧(A→┐B)<=>┐A

由于A,B,C可以代表任意的公式，因而称这样的逻辑等值式为命题定律。每个命题定律都给出了无穷多个同类型的具体的逻辑等值式。1.3.2基本等值定律【例1.3.2】用等值演算验证等值式(p→q)∧(p→r)⇔(p→(q∧r))。

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

⇔(¬¬p∨q)∧(¬¬p∨r)(蕴含等值式)

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

⇔(p→(q∧r))(蕴含等值式)证毕1.3.2基本等值定律1.3.3等值演算子公式设Φ(A)是含公式A的命题公式，称A为Φ(A)的一个子公式。注意：(1)A是命题公式Φ(A)的连续的一部分；(2)A本身也是一个命题公式；例：公式(﹁𝐵∧𝐶)是公式(﹁𝐴∧(﹁𝐵∧𝐶))∨(𝐵∧𝐶)∨(𝐴∧𝐶)的子公式，但∨(𝐵∧𝐶)却不是公式(﹁𝐴∧(﹁𝐵∧𝐶))∨(𝐵∧𝐶)∨(𝐴∧𝐶)的子公式，因为∨(𝐵∧𝐶)虽是公式(﹁𝐴∧(﹁𝐵∧𝐶))∨(𝐵∧𝐶)∨(𝐴∧𝐶)中连续的一部分，但它自身不是公式。1.3.3等值演算置换规则

设A是命题公式Φ(A)的的一个子公式，Φ(B)是用命题公式B置换了Φ(A)中的A之后得到的命题公式，如果A<=>B，则Φ(A)<=>Φ(B)。1.3.3等值演算等值演算利用已知的最基本逻辑等值式和等价置换不仅可以证明一些较为复杂的命题公式间的逻辑等值、判断公式的类型，并且进行一些实际问题的分析，此类方法称为逻辑等价演算或等值演算的方法。1.3.3等值演算1）利用逻辑等价演算的方法，验证公式间的逻辑等价【例1.3.3判断公式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(零律)由此可知,这是一个重言式。

1.3.3等值演算2）判断公式类型【例1.3.4】判断公式(p→q)→(¬q→¬p)的类型。解(p→q)→(¬q→¬p)⇔(¬p∨q)→(¬¬q∨¬p)(蕴含等值式)⇔(¬p∨q)→(¬p∨q)(双重否定、交换律)⇔¬(¬p∨q)∨(¬p∨q)(蕴含等值式)⇔1(排中律)因此,公式(p→q)→(¬q→¬p)是重言式。1.3.3等值演算【例1.3.5】

判断公式((p∨q)∧┐q)→p的类型。1.3.3等值演算解：((p∨q)∧┐q)→p<=>((p∧┐q)∨(q∧┐q))→p

(分配律)<=>((p∧┐q)∨0)→p

(矛盾律)<=>(p∧┐q)→p

(同一律)<=>┐(p∧┐q)∨p

(蕴含等值式)<=>(┐p∨q)∨p

(德·摩根律、双重否定律)<=>(┐p∨p)∨q(交换律、结合律)<=>1∨q(排中律)<=>1(零律)因此，公式((p∨q)∧q)→p是一个重言式。1.3.3等值演算【例1.3.6

】用等值演算法判断下列公式的类型：

(1)（p→q)∧p→q

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

(3)p∧(((p∨q)∧┐p)→q)1.3.3等值演算【例1.3.7

】用等值演算法验证等值式：

(p∨q)→r<=>(p→r)∧(q→r)

p→(q→r)<=>(p∧q)→r1.3.3等值演算【例1.3.7】用等值演算法验证等值式：

(1)(p∨q)→r<=>(p→r)∧(q→r)

(2)p→(q→r)<=>(p∧q)→r1.3.3等值演算1.4联结词全功能集前面我们一共介绍了五个联结词：┐、∧、∨、→和

，并用它们构成了一些命题公式，且看到了有些公式书写形式尽管不同，但实际上是等值的。1.4联结词全功能集因此我们不禁要问：(1)互不等值的命题公式的个数是有限的吗？总共有多少个命题公式？(2)联结词的个数是有限的吗？总共有多少个联结词？1.4联结词全功能集对于含有两个命题变元的公式，理论上讲可以书写出无穷多个公式，但互不等值的公式恰有=24=16个,对应着16个不同的真值表(真值表共有22行，行上的每个记入值又可在0、1中任取其一，因此构成个不同的真值表)，亦即对应着16个真值函数Fi(i=0，1，…，15)，其中Fi：{00，01，10，11}→{0，1}，如表1.4.1所示。

表

1.4.1pqF0F1F2F3F4F5F6F700000000000100001111100011001111010101011.4联结词全功能集续表pqF8F9F10F11F12F13F14F1500111111110100001111100011001111010101011.4联结词全功能集1.4.1异或联结词1.如果……则……的否定“”设p、q为任意两个命题，复合命题“如果p则q的否定”称为p、q蕴含的否定，记作：p

q。“”称为蕴含的否定联结词。p

q为真，当且仅当p为真，q为假。

由上面所述可知，F2是二元真值函数p

q。

p

q

<=>┐(p→q)2.异或(排斥或)“”

设p、q为任意两个命题，复合命题“p异或q”称为p、q的异或(排斥或)，记作：p

q。“”称为异或(排斥或)联结词。p

q为真，当且仅当p、q中恰有一个为真。

1.4.1异或联结词1.4.2与非联结词与非“↑”

设p、q为任意两个命题，复合命题“p与q的否定”称为p、q的与非，记作：p↑q。“↑”称为与非联结词。p↑q为假，当且仅当p、q均为真。性质

(p↑q)↑r(p↑q↑r)

【例1.4.3】

将下列公式化成仅含联结词“↑”的公式。(1)¬p(2)p∧q解(1)¬p⇔¬(p∧p)⇔p↑p(2)p∧q⇔¬¬(p∧q)⇔¬(p↑q)⇔(p↑q)↑(p↑q)1.4.2与非联结词1.4.3或非联结词或非“↓”

设p、q为任意两个命题，复合命题“p或q的否定”称为p、q的或非，记作：p↓q。“↓”称为或非联结词。p↓q为真，当且仅当p、q均为假。

事实上，每一个公式(表中的每一列)都是定义域为{0，1}2={00，01，10，11}，值域为{0，1}的函数，我们称这样的函数为二元真值函数。一般地，n个命题变元仅能构成个互不等值的命题公式，它们是定义域为{0，1}n={00…00，00…01，…，11…11}(由0、1构成的长度为n的符号串，称为维卡氏积)，值域为{0，1}的函数，称为n元真值函数。

每个n元真值函数均对应着无穷个与之等值的命题公式，这些公式都是由联结词联结而成的。1.4.4联结词全功能集理论上讲，每个真值函数都可定义一个联结词，于是，一元的有=4个，二元的有=16个，三元的有=256个。但实际上由真值表可知，一元联结词只有“”１个，二元联结词共有8个，而三元联结词我们也只用“if…then…else…”(如果……则……否则)，且这个联结词完全可以用一元、二元的、∧和→表示(参看例1.8.1(2))。在不同的形式系统中，联结词集合中的联结词有的多些，有的少些，但无论联结词集合中的联结词有多少，它们都必须具备共同的功能，即可以表示出所有的真值函数。1.4.4联结词全功能集1.4.4联结词全功能集全功能集(功能完备集):任一真值函数均可用仅含该集中的联结词的公式表示。对于一个联结词集来说，如果集中的某个联结词可以用集中的其他联结词所定义，则称这个联结词是冗余的联结词。1.4.4联结词全功能集极小全功能集(全功能完备集):不含冗余联结词的全功能集。由于三元联结词可用一元和二元的联结词表示，所以是冗余的。考察前面的二元真值函数的真值表可知：{┐

，∧，∨，→，

}是全功能集。而因为A

B<=>(A→B)∧(B→A)，因此“

”是冗余的，得新的联结词集{，∧，∨，→}是全功能集。又因为A→B<=>┐A∨B，因此“→”是冗余的，得联结词集{┐，∧，∨}是全功能集。再由A∨B<=>┐(┐A∧┐B)，所以“∨”也是冗余的，可得{┐，∧}是全功能集。

1.4.4联结词全功能集可以证明{┐，∧}是极小全功能集。

类似可证，{┐，∨}、{┐，→}均是极小全功能集。再由上面例1.4.3可得{↑}及{↓}也均是极小全功能集。1.4.4联结词全功能集【例1.4.4】

将公式p∧(q

r)化成仅含联结词┐、∧的公式形式。

1.4.4联结词全功能集【例1.4.5】

将公式p→q化成仅含联结词↑、↓的公式形式。1.4.4联结词全功能集定义1.5.1

在仅含联结词┐、∧、∨的命题公式A中，将∨换成∧，将∧换成∨，若A中含有0或1，则将0换成1，1换成0，所得命题公式称为A的对偶式，记作A*。由定义易知，对偶式是相互的，(A*)*=A，我们称A与A*是对偶的。1.5.1对偶定理例：(1)(p∧┐q)∨r∨1与(p∨┐q)∧r∧0互为对偶式。(2)┐(p∨q)∧(┐q∨r)与┐(p∧q)∨(┐q∧r)是对偶的。(3)┐((p∨q)∧r∧q)与┐((p∧q)∨r∨q)对偶式。1.5.1对偶定理定理1.5.1

设A与A*是对偶的，p1,p2,…，pn是出现在A、A*中的所有命题变元，则

A(p1，p2，…,pn)<=>A*(┐p1，┐p2，…，┐pn)(1)

A(┐p1，┐p2，…，┐pn)<=>┐A*(p1，p2，…，pn)(2)1.5.1对偶定理定理1.5.2设A*、B*分别是公式A、B的对偶式，如果A<=>B，则A*<=>B*。本定理称为对偶原理。1.5.1对偶定理1.5.2析取范式和合取范式定义1.5.2

将命题变元及其否定统称为文字,p与┐p称为一对相反的文字。简单析取式(基本和)：仅由有限个文字构成的析取式。简单合取式(基本积)：仅由有限个文字构成的合取式。例如，p、┐q既是一个文字的简单析取式，又是一个文字的简单合取式。p∧q∧r、p∧q∧┐q均是有三个文字的简单合取式。1.5.2析取范式和合取范式性质：(1)一个文字既是简单析取式又是简单合取式。(2)一个简单析取式是重言式，当且仅当它同时含有一对相反的文字。(3)一个简单合取式是矛盾式，当且仅当它同时含有一对相反的文字。例如，p∨q∨┐p是重言式，p∧┐q∧q是矛盾式

1.5.2析取范式和合取范式析取范式：由有限个简单合取式构成的析取式。合取范式：由有限个简单析取式构成的合取式。1.5.2析取范式和合取范式定理1.5.3（范式存在定理）任一命题公式都存在着与之等值的析取范式，任一命题公式都存在着与之等值的合取范式。

1.5.2析取范式和合取范式求范式的步骤：（1）消去连接词。（2）否定号的消去（利用双重否定律）或内移（利用德摩根率）

（3）利用分配律：利用∧对∨的分配律求析取范式，利用∨对∧的分配律求合取范式。

1.5.2析取范式和合取范式【例1.5.2】求公式¬((¬p∨q)∧(r→¬p))∨¬((¬r→q)→¬p)的析取范式。解¬((¬p∨q)∧(r→¬p))∨¬((¬r→q)→¬p)⇔¬((¬p∨q)∧(¬r∨p))∨¬((¬¬r∨q)∨¬p)(消→、蕴含等值式、双重否定律)⇔(p∧¬q)∨(p∧r)∨((r∨q)∧p)(德·摩根律、双重否定律、交换律)⇔(p∧¬q)∨(p∧r)∨(p∧r)∨(p∧q)(分配律)⇔(p∧q)∨(p∧r)∨(p∧q)(幂等律)1.5.2析取范式和合取范式【例1.5.3】

求公式((p∨q)→r)

p的合取范式。

1.5.2析取范式和合取范式1.5.3主析取范式和主合取范式定义1.5.4

在含有n个命题变项的简单合取式（简单析取式）中，若每个命题变项和它的否定式不同时出现，而二者之一必出现且仅出现一次，且第i个命题变项或它的否定式出现在从左算起的第i个位置上（若命题变项无角标，就按字典顺序排列），称这样的简单合取式（简单析取式）极小项（极大项）

【例1.5.4】

求公式A(p，q)的极小项和极大项。

1.5.3主析取范式和主合取范式即极小(大)项的个数等于22个。(n元的公式为2n个。)我们做出仅含两个命题变元的公式的极小项的真值表，如表1.5.1所示。表1.5.1pq┐p∧┐q(m0)┐p∧q(m1)p∧┐q(m2)p∧q(m3)0010000101001000101100011.5.3主析取范式和主合取范式由真值表可看出：对于p、q的任一组赋值，有且仅有一个极小项的真值为1，即极小项之间是不等值的，4个真值赋值与4个极小项值之间有一一对应关系。我们用mi表示在十进制为i的赋值下真值为1的极小项。

1.5.3主析取范式和主合取范式极小项的性质及说明：（1）由于每个命题变元在极小项中以原形或否定式形式出现且仅出现一次，因而n个命题变元共可产生2n个不同的极小项。（2）每个极小项都有且仅有一个成真赋值；若成真赋值所对应的二进制数转换为十进制数i，就将所对应极小项记作mi.（3）2n个极小项两两互不逻辑等价。（4）任意两个不同极小项的合取式永假。（5）2n个极小项的析取式永真。

1.5.3主析取范式和主合取范式定义1.5.5

对于公式A：主析取范式:与A等值的由极小项构成的析取范式；主合取范式:与A等值的由极大项构成的合取范式。由定理1.5.3知，任一公式的析(合)取范式总是存在的，求主范式只需在求范式的基础上将每个简单合(析)取式化成极小(大)项。1.5.3主析取范式和主合取范式求主范式的步骤：1)求出析取范式（合取范式）；2)补充命题变元；3)消去重复出现的极小（大）项和矛盾式（重言式）。1.5.3主析取范式和主合取范式【例1.5.5】

求公式((p∨q)→r)

p的主析取范式。

1.5.3主析取范式和主合取范式【例1.5.6】

求(p→(p∨r))∧(q

p)的主析取范式。1.5.3主析取范式和主合取范式【例1.5.7】用真值表法求(p→(p∨r))∧(q

p)的主析取范式。1.5.3主析取范式和主合取范式结论(主析取范式的用途)(1)重言式的主析取范式包含公式的全部2n个极小项。(2)(规定)矛盾式的主析取范式为0。(3)二等值的公式必有相同的主析取范式(不计极小项的顺序)。(4)不列真值表，由主析取范式可得公式的成真、成假赋值。(5)仅由真值表，可得公式的表达式(主析取范式形式)。(6)解决应用问题。1.5.3主析取范式和主合取范式表1.5.2pqrp∨rp→(p∨r)p

q(p→(p∨r))∧(p

q)0000111m00011111m10100100m20111100m31001100m41011100m51101111m61111111m71.5.3主析取范式和主合取范式【例1.5.8】

不列真值表，求公式(p→q)→r的成真赋值。1.5.3主析取范式和主合取范式【例1.5.9】已知命题公式A(p,q)的真赋值为01，10，11，求A。1.5.3主析取范式和主合取范式【例1.5.10】四人比赛，三人估计成绩。甲说：“A第一，B第二”，乙说：“C第二，D第四”，丙说：“A第二，D第四”。结果每人都说对了一半，假设无并列名次，问A、B、C、D实际名次如何？1.5.3主析取范式和主合取范式我们做出仅含两个命题变元的公式的极大项的真值表，如表1.5.3所示。表1.5.3pqp∨q(M0)p∨┐q(M1)┐p∨q(M2)┐p∨┐q(M3)0001110110111011011111101.5.3主析取范式和主合取范式由真值表可看出：对于p、q的任一组赋值，有且仅有一个极大项的真值为0，即极大项之间是不等值的，4个真值赋值与4个极大项值之间有一一对应关系。我们用Mi表示在十进制为i的赋值下真值为0的极大项。

1.5.3主析取范式和主合取范式关于极大项的性质：（1）n个命题变元共可产生2n个极大项；（2）每个极大项有且仅有一个成假赋值，将其对应的十进制数i做极大项的脚标，记作Mi。（3）2n个极大项两两互不逻辑等价。（4）任意两个不同极大项的析取式永真。（5）2n个极大项的合取式永假。1.5.3主析取范式和主合取范式关于极大项的性质：（1）n个命题变元共可产生2n个极大项；（2）每个极大项有且仅有一个成假赋值，将其对应的十进制数i做极大项的脚标，记作Mi。（3）2n个极大项两两互不逻辑等价。（4）任意两个不同极大项的析取式永真。（5）2n个极大项的合取式永假。1.5.3主析取范式和主合取范式注意：对于任一公式，在它的2n个赋值中，非0即1，因此其主析取范式中的极小项和其主合取范式中的极大项的个数之和恰为2n，且其下标不会相同。故当我们知道了一个公式的所有成真赋值时，也就知道了它的所有成假赋值，亦即知道了主析取范式，相应地也就得到了主合取范式，反之亦然。另外，任一公式的主合取范式同样具有存在唯一性且(规定)重言式的主合取范式为1。1.5.3主析取范式和主合取范式【例1.5.11】

求公式(p∧q)∨r的主合取范式。1.5.3主析取范式和主合取范式【例1.5.12】求（A∨B）→C的主析取范式和主合取范式。

解：（A∨B）→C

﹁（A∨B）∨C

（﹁A∧﹁B）∨C

（﹁A∧﹁B∧﹁C）∨（﹁A∧﹁B∧C）∨(A∧B∧C)

∨(﹁A∧B∧C)∨(A∧﹁B∧C)此为主析取范式

m0∨m1

∨m3∨m5∨m7

其主合取范式为：

（A∨B）→C

（﹁A∨C）∧（﹁B∨C）

（﹁A∨﹁B∨C）∧（﹁A∨B∨C）∧（A∨﹁B∨C）

M2∨

M4

∨

M6

1.5.3主析取范式和主合取范式【例1.5.13】某研究所有赵、钱、孙、李、周五位高级工程师。现需派一些人出国考察，由于各方面的限制，此次选派必须满足下列条件：

(1)若赵去，则钱也去。

(2)李、周两人中必有人去。

(3)钱、孙两人中去且仅去一人。

(4)孙、李两人同去或都不去。

(5)若周去，则赵、钱也同去。1.5.3主析取范式和主合取范式解:设p：赵去，q：钱去，r：孙去，s：李去，t：周去，选派方案为F。则F

(p→q)∧(s∨t)∧((q∧┐r)∨(┐q∧r))∧((r∧s)∨

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

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

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

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

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

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

∧┐q∧r∧s)∨

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

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

(┐p∧┐q∧r∧s∧┐t)∨(p∧q∧┐r∧┐s∧t)——主析取范式所以方案有两个：①孙、李同去。②赵、钱、周三人同去。1.5.3主析取范式和主合取范式。

【例1.5.14】

求p→q的主析取范式与主合取范式1.5对偶与范式

。

【例1.5.15】

求(┐p∨r)∧(p→q)∧(q→r)的主析取范式与主合取范式。1.5.3主析取范式和主合取范式研究如何保证推理是正确的。1.6推理理论1.6.1推理的基本概念定理1.6.1

称蕴含式(A1∧A2∧…∧An)→B为推理的形式结构，A1，A2，…，An为推理的前提，B为推理的结论。若(A1∧A2∧…∧An)→B是重言式，则称从前提A1，A2，…，An推出结论B的推理正确，B是A1，A2，…，An的有效结论或逻辑结论。记作：(A1∧A2∧…∧An)=>B或A1,A2,…,An=>B

否则称推理不正确，或B不是前提A1，A2，…，An的有效结论。注意:“=>”亦读作“蕴含”，但它不是联结词。“=>”具有的性质：(1)A=>A。(自反性)(2)若A=>B且B=>A，则A<=>B。(反对称性)(3)若A=>B且B=>C，则A=>C。(传递性)判断重言式的方法(已学的)有三种：真值表法、等值演算法和主析取范式法等。1.6.1推理的基本概念【例1.6.1】验证下面推理是否正确：如果天气凉快,小林就不去游泳。今天天气凉快,所以小林没去游泳。1.6.1推理的基本概念证明:设p:天气凉快,q:小林去游泳。推理的形式结构为((p→┐q)∧p)→┐q。1.6.1推理的基本概念从表1.6.1看到,其最后一列全为1,因而公式是重言式,所以推理正确。表1.6.11.6.1推理的基本概念(2)等值演算法：((p→¬q)∧p)→¬q⇔¬((¬p∨¬q)∧p)∨¬q(蕴含等值式)⇔((p∧q)∨¬p)∨¬q(德·摩根律)⇔((p∨¬p)∧(¬p∨q))∨¬q(分配律、交换律)⇔(¬p∨q)∨¬q(排中律、同一律)⇔¬p∨(q∨¬q)(结合律)⇔1(零律)因为推理的形式结构是重言式,所以推理正确。1.6.1推理的基本概念(3)主析取范式法。((p→¬q)∧p)→¬q⇔¬((¬p∨¬q)∧p)∨¬q(蕴含等值式)⇔((p∧q)∨¬p)∨¬q(德·摩根律)⇔((p∨¬p)∧(¬p∨q))∨¬q(分配律、交换律)⇔(¬p∨q)∨¬q(排中律、同一律)⇔¬p∨(q∨¬q)(结合律)⇔1(零律)⇔m0∨m1∨m2∨m3因为主析取范式包含22个极小项,所以推理正确。1.6.1推理的基本概念1.6.2推理的基本定律推理定律(重言蕴涵式)：利用真值表法、等值演算法以及分析法等容易证明下述推理定律的正确性。(1)A=>(A∨B)附加(2)(A∧B)=>A

化简(3)((A→B)∧A)=>B

假言推理(4)((A→B)∧┐B)=>

┐A拒取式

(5)((A∨B)∧┐B)=>

A

析取三段论(6)((A→B)∧(B→C))=>(A→C)假言三段论(7)((A

B)∧(B

C))=>(A

C)等价三段论(8)((A→B)∧(C→D)∧(A∨C))=>(B∨D)构造性二难【例1.6.2】证明拒取式((A→B)∧┐B)=>┐A

证明:

((A→B)∧┐B)→┐A<=>┐((┐A∨B)∧┐B)∨┐A

<=>┐(┐A∧┐B)∨┐A

<=>

A∨B∨┐A<=>1

1.6.2推理的基本定律命题演算推理由三个要素组成：推理根据、推理规则和证明方法。1）推理根据：命题演算推证的命题定律和推理定律；即主要指已知的基本逻辑等价式和逻辑蕴涵式。2）推理规则:（1）前提引入规则（P规则）：在证明的任何步骤上，都可以引入前提。（2）结论引入规则（T规则）：在证明的任何步骤上,所得到的结论均可作后续证明的前提加以引用。（3）附加前提规则（CP规则）：若从A和B能有效地推出C，则从A可有效地推出B→C。（通常在结论为蕴涵式时使用）（4）置换规则：在证明的任何步骤上，命题公式中的任何子公式都可以用与之等值的公式置换(等值式见本章第1.3节)。

1.6.3推理的基本方法3）证明方法包括:(1)直接证法：构造证明法。(2)间接证明方法：反证法和附加前提证法

1.6.3推理的基本方法构造证明法构造证明实质上就是一串公式的序列，其中的每个公式都是按照事先规定的规则得到的，且需将所用的规则在公式后写明，该序列的最后一个公式正是所要证明的结论。注意:(1)构造证明法作为推理系统有其固有的书写格式，必须严格遵守。(2)不同的推理系统所给出的推理规则集合不尽相同。

1.6.3推理的基本方法推理规则：(这里A1，A2，…，An╞B表示B是A1，A2，…，An的逻辑结论。)附加规则:A╞(A∨B)

化简规则:(A∧B)╞A

假言推理规则:(A→B)，

A╞B拒取式规则:(A→B)，┐B╞┐A假言三段论规则:(A→B)，(B→C)╞(A→C)析取三段论规则:(A∨B)，┐B╞A构造性二难规则:(A→B)，(C→D)，(A∨C)╞(B∨D)合取引入规则:A，B╞(A∧B)1.6.3推理的基本方法【例1.6.3】

构造下列推理的证明。前提：

p∨q，p→┐r，s→t，┐s→r，┐t

结论：q证明：(1)s→t

前提引入(2)┐t

前提引入(3)┐s(1)(2)拒取式(4)┐s→r

前提引入(5)r(3)(4)假言推理(6)┐┐r(5)置换

1.6.3推理的基本方法(7)p→┐r

前提引入(8)┐p(6)(7)拒取式(9)p∨q

前提引入(10)q∨p(9)置换(11)q(10)(8)析取三段论1.6.3推理的基本方法【例1.6.4】用构造证明的方法证明下列推理的正确性。

如果今天是星期五,则要进行语文或数学考试,如果语文老师有会,则不考语文。今天是星期五,语文老师有会,所以进行数学考试。1.6.3推理的基本方法解:设p:今天是星期五,q:进行语文考试,r:进行数学考试,s:语文老师有会。前提:p→(q∨r),s→┐q,p,s。结论:r。(1)p→(q∨r)前提引入。(2)p前提引入。(3)q∨r(1)(2)假言推理。(4)s→┐q前提引入。(5)s前提引入。(6)┐q(4)(5)假言推理。(7)r(3)(6)析取三段论。1.6.3推理的基本方法【例1.6.5】公安人员审理某珠宝商店的钻石项链的失窃案，已知侦察结果如下：（10分）

(1)营业员A或B盗窃了钻石项链；

(2)若B作案，则作案时间不在营业时间；

(3)若A提供的证词正确，则货柜未上锁；

(4)若A提供的证词不正确，则作案时间发生在营业时间；

(5)货柜上锁了。

问：作案者是谁？请写出推理过程。

1.6.3推理的基本方法解：设p：营业员A盗窃钻石项链，q：营业员B盗窃钻石项链，

r：作案时间发生在营业时间，

s：A提供的证词正确，t：货柜上锁

前提：p∨q，q→﹁r，s→﹁t，﹁s→r，t

推理：

(1)t 前提引入

(2)s→﹁t 前提引入

(3)﹁s (1)(2)拒取式

(4)﹁s→r 前提引入

(5)r (3)(4)假言推理