离散数学及其应用-第2版 课件全套 第1-12章 命题逻辑 - 格和布尔代数

第1章

命题逻辑1第一部分数理逻辑数理逻辑是研究推理逻辑规则的一个数学分支，它采用数学符号化的方法，给出推理规则来建立推理体系，进而讨论推理体系的一致性、可靠性和完备（全）性等。2第1章命题逻辑1.1命题与联结词

1.2命题公式及其分类1.3命题演算的关系式1.4范式1.5命题演算的推理31.1命题与联接词1.1.1命题的概念定义命题的真值联结词4命题及其真值命题:是用陈述句表示的一个或者为真或者为假，但不能同时既为真又为假的判断语句。命题的真值:判断的结果,真（T或1）或假（F或0)真命题:真值为真的命题假命题:真值为假的命题5例题判断下列句子中那些是命题？若是命题的，判断其真值。

北京是中国的首都。2+3=6。3-x=5。请关上门。几点了？除地球外的星球有生物。多漂亮的花啊！我只给所有不给自己理发的人理发。6Y真Y假N真值不确定N疑问句N感叹句N祈使句N悖论Y真值确定,但未知命题的表示引入英文字母表示任意的命题表示命题的符号称为命题变量，通常用p、q、r...、P、Q、R...表示命题变量。命题变量没有真值，只有表示一个确定的命题后，才有真值。如用p表示命题：“2+3=6”，这时p的真值为假（F），也可以用p表示命题：“2+3=5”,这时p的真值为真（T）。7简单命题与复合命题简单命题(原子命题):不能分解为更简单的陈述语句的命题

简单命题：“北京是中国的首都”。复合命题:由两个或几个简单句和连词组合而成的命题复合命题：“如果明天天气好,我们就去爬山。”命题的符号化：用英文字母或英文字母和联结词的组合表示命题，称为命题的符号化。

联结词

-----连词8联结词（一）否定

定义1.1.4

设p是一个命题，

p表示一个新命题“非p”。命题

p称为p的否定。当且仅当p的真值为假时，

p的真值为真。

p的真值表：例如：p：今天是晴天。则

p：今天不是晴天。“非”，“不”，“没有”，“无”，“并非”等都可用

来表示。9p

pTFFT联结词（二）合取

定义1.1.5设p、q表示任意两个命题,p

q可表示复合命题“p并且q”。当且仅当p和q的真值同时为真时，p

q的真值为真。p

q的真值表：例如：p:今天是晴天；q:今天去公园。p

q:今天是晴天并且今天去公园。

“和”，“与”，“也”，“并且”，“既...又...”，“不仅...而且...”，“虽然...但是...”等都可用

来表示。10p

qp

qT

TT

FF

TF

FTFFF联结词（三）析取

定义1.1.6设p、q表示任意两个命题,p

q可表示复合命题“p或q”。当且仅当p和q的真值同时为假时，p

q的真值为假。p

q的真值表：例如：p:今天去看电影；q:今天去公园。p

q:今天去看电影或今天去公园。

“或”，“可能...可能...”，“或者...或者...”等可用

表示。11p

qp

qT

TT

FF

TF

FTTTF联结词自然语言中的“或”具有二义性：兼容性或和不兼容性或。兼容性或

电灯不亮是灯泡或线路有问题所致.不兼容性或（排斥或）

派小王或小李中的一人去开会

表示兼容性或例如：p:电灯不亮是灯泡有问题所致；q:电灯不亮是线路有问题所致。p

q:电灯不亮是灯泡或线路有问题所致。p：派小王去开会，q：派小李去开会，(p

q)

(

p

q):派小王或小李中的一人去开会12联结词（四）蕴涵

定义1.1.7设p、q表示任意两个命题,p

q可表示复合命题“如果p，则q”。当且仅当p的真值为真，q的真值为假时，p

q的真值为假。p

q的真值表：例如：p:今天天气晴朗；q:我们去海滩。p

q:如果今天天气晴朗，我们就去海滩。13p

qp

qT

TT

FF

TF

FTFTT联结词蕴涵式：p

qp为蕴涵前件，q为蕴涵后件p是q的充分条件，q是p的必要条件表示：“如果p，则q”，“如果p，那么q”，“当p则q”，“p仅当q”等。假设：p：天气晴朗；q：我们去海滩。如果天气晴朗，我们去海滩。p

q仅当天气晴朗，我们去海滩。q

p14联结词（五）等价

定义1.1.8设p、q表示任意两个命题,p

q可表示复合命题“p当且仅当q”。当且仅当p和q的真值同时为真或同时为假时，p

q的真值为真。p

q的真值表：例如：p:两个三角形是全等的。q：两个三角形的三条对应边相等。

p

q表示“两个三角形是全等的当且仅当它们的三条对应边相等”。15p

qp

qT

TT

FF

TF

FTFFT联结词等值式p

q表示p与q互为充分必要条件的逻辑关系表示形如“p当且仅当q”，“如果p，那么q，反之亦然”等的命题。16例题将下列命题符号化：虽然天气很冷，老王还是来了。小王和小李是好朋友。小王和小李是好学生。小王或小李中的一人是游泳冠军。只有你学过微积分或是数学系的学生，才可以选修这门课。如果明天早晨6点不下雨，我就去跑步。今天下雨与3+3=6。登陆服务器必须输入一个有效的口令。2+3=5的充要条件是加拿大位于亚洲。17

解：虽然天气很冷，老王还是来了。

设p：天气很冷。q：老王来了。

则符号化为：p

q。小王和小李是好朋友。

这句虽然有连词“和”，但是个简单句，

可用p表示：小王和小李是好朋友。小王和小李是好学生。

设p：“小王是好学生”

q：“小李是好学生”，

则符号化为：p

q。18

解：小王或小李中的一人是游泳冠军。设p：“小王是游泳冠军”，q：“小李是游泳冠军”

(p

q)

(

p

q)只有你学过微积分或是数学系的学生，才可以选修这门课。

设

p：你学过微积分；q：你是数学系的学生；r：你可以选修这门课。

r

(p

q)如果明天早晨6点不下雨，我就去跑步。设p：明天早晨6点下雨。q：我去跑步

符号化为：

p

q,或者：

q

p。19

解：今天下雨与3+3=6。设p：今天下雨。q：3+3=6。符号化为：p

q。登陆服务器必须输入一个有效的口令。设p：登陆服务器,q:输入一个有效的口令,符号化为：p

q。2+3=5的充要条件是加拿大位于亚洲。设p：2+3=5,q:加拿大位于亚洲,符号化为p

q。20联结词

（），

，

，

，

，

优先级高

21括号有时被省略，如pq是p和q的合取，这里是省略了p的括号，即(p)q

pq

pp∧qp∨qp

qp

q0010011011011010001001101111联结词的真值表低例题将下列命题符号化，并指出它们的真值：1+1=2和2+3=61+1=2或猴子是飞禽若2+3=6，则猴子是飞禽。若猴子不是飞禽，则1+1=2和2+3=6。若2+3=6或猴子是飞禽，则1+1=2。2+3=6当且仅当猴子不是飞禽。22解

设p：1+1=2，q：2+3=6，r:猴子是飞禽

1+1=2和2+3=6,p

q，真值为0，

1+1=2或猴子是飞禽,

p

q，真值为1，

若2+3=6，则猴子是飞禽,

q

r，真值为1若猴子不是飞禽，则1+1=2和2+3=6。

r

p

q，真值为0，

23例题(续）例题（续）若2+3=6或猴子是飞禽，则1+1=2q

r

p，真值为1，

2+3=6当且仅当猴子不是飞禽。q

r，真值为024其它联结词定义1.1.9

设p和q是任意两个命题,p

q可表示复合命题“p和q的与非”,

称为与非联结词。命题p

q称为p和q的与非式。当且仅当p和q的真值同时为真时，p

q的真值为假.p

q的真值表25p

qp

qT

TT

FF

TF

FFTTT其它联结词定义1.1.10设p、q是任意两个命题,p

q可表示复合命题“p和q的或非”,

称为或非联结词。命题p

q称为p和q的或非式。当且仅当p和q的真值同时为假时，p

q的真值为真.p

q的真值表26p

qp

qT

TT

FF

TF

FFFFT其它联结词定义1.1.11设p和q是任意两个命题,p

q可表示复合命题“p、q之中恰有一个成立”,

称为异或（不兼容性或）联结词。命题p

q称为p和q的异或式。当且仅当p和q的真值恰有一个为真时，p

q的真值为真。p

q的真值表27p

qp

qT

TT

FF

TF

FFTTF联结词的真值

28

pq

p∧qp

qp∨qp

q

p

q

p

q000

1

0

1

10010

1100110011001111

010

10联结词的真值p

q1101逻辑关系的数字门电路实现

用数字电路中的“非门”实现，

联结词用“与门”实现，

联结词用“或门”实现29非门与门或门

逻辑门电路符号命题公式的门电路实现命题公式G

(p

q)

p30逻辑电路联结词的应用布尔检索中，联结词AND用于匹配同时包含两个检索项的记录，联结词OR用于匹配至少包含一个检索项的记录，而联结词NOT用于排除某个特定的检索项。如：把自然语言表示的命题翻译成由命题变量和逻辑联结词组成的表达式，进行判断和推理31例题

三个客人坐在餐馆，服务生问：“每个人都要咖啡吗？”，第一位客人回答：“我不知道。”接着第二位客人也回答：“我不知道。”最后，第三位客人回答：“不是每个人都要咖啡。”一会儿，服务生回来，将咖啡递给需要的客人。请问服务生是如何判断哪位客人需要咖啡的？解：根据三位客人的回答，服务生给第一位客人和第二为客人送来咖啡。32例题解：设p、q、r分别表示第一、二、三位客人要咖啡如果每个人都要咖啡，则p

q

r为真。根据第一个客人的回答“我不知道。”，服务生可以判断p为真；根据第二个人的回答“我不知道。”可以判断q为真

；第三位客人的回答：“不是每个人都要咖啡。”说明r为假

因此，服务员可以断定第一位和第二位客人要咖啡，第三位客人不要咖啡。331.2命题公式及其分类命题常元:代表特定简单命题。命题变元:代表任意命题，取值为1(真)或0(假)的变量。定义1.2.1

命题公式（公式）的定义如下：每一个命题常元或命题变元都是命题公式。如果A是命题公式，则(

A)是命题公式。如果A和B都是命题公式，则(A

B)，(A

B)，(A

B)，(A

B)都是命题公式。一个由命题常元或命题变元、联结词和括号所组成的符号串是命题公式，当且仅当这个符号串是有限次应用上面的步骤得到的。34命题公式一个含有命题变元的命题公式的真值是不确定的.只有当公式中的所有命题变元被指定代表特定的命题时，命题公式才成为命题，其真值才唯一确定。

例如，命题公式p

q若指定p为“2是素数”，q为“3是奇数”

则p

q为真命题

若指定p为“2是素数”，q为“3是偶数”

则p

q为假命题

35公式的赋值定义1.2.2

若命题公式A含有的全部命题变元为p1,p2,…,pn，给p1,p2,…,pn指定一组真值，称为对A的一个解释或赋值。使A的真值为真的赋值称为成真赋值，使A的真值为假的赋值称为成假赋值。说明通常赋值与命题变元之间按下标或字母顺序对应,即当A的全部命题变元为p1,p2,…,pn时,给A赋值

1

2…

n，是指p1=

1,p2=

2,…,pn=

n;当A的全部命题变元为p,q,r,…时,给A赋值

1

2

3…是指p=

1,q=

2,r=

3,…。36命题公式的真值表例给出公式的真值表

p

(q

r)(p

q)

(

p

q)

(

p

q)

q37真值表:命题公式在所有可能的赋值下的取值的列表含n个变项的公式有2n个赋值例题(续)(1)p

(q

r)38

pqr

r

q

r

p

(q

r)000001010011100101110111101010100010001

0

11110010例题(续)（2）(p

q)

(

p

q)39

pqp

q

p

q

(p

q)

(

p

q)00011011110101111111例题(续)(3)

(

p

q)

q40

pq

p

p

q

(

p

q)

(

p

q)

q000110111100011110000000n个命题变元的不同的真值表有命题公式的分类定义1.2.3设A为一个命题公式(1)若A在它的各种赋值下取值均为真，则称A为重言式或永真式。(2)若A在它的各种赋值下取值均为假，则称A为矛盾式或永假式。(3)若至少存在一种赋值使A的真值为真，则称A为可满足式。例如(1)p

(q

r)为非重言式的可满足式

（2）(p

q)

(

p

q)为重言式(3)

(

p

q)

q为矛盾式41命题公式的分类这三类公式之间有下面的关系：公式A永真，则

A永假，反之亦然。公式A是可满足的，当且仅当

A不是永真式。公式A不是可满足的，则一定是永假式。公式A不是永假式，则一定是可满足的。判断命题公式类型的方法：构造真值表421.3命题演算的关系式等价关系式定义1.3.1

设A和B是两个命题(或命题公式)，若A

B是永真式，命题A和B称为逻辑等价的，可记为A

B。说明：A

B是永真式，表示命题公式A和B在所有的赋值下都有相同的真值，也就是说命题公式A和B有相同的真值表。可以用真值表判定两个命题是否等价。

43例题证明：p

q和

p

q等价。证列出真值表44所以有:p

q

p

qp

qp

q

p

p

q00111011111000011101例题证明p

(q

r)和(p

q)

(p

r)逻辑等价证列出真值表45所以有：p

(q

r)和(p

q)

(p

r)等价p

q

rp

(q

r)(p

q)

(p

r)0000000100010000110010000101111101111111等价关系式双重否定律

p

p同一律p

0

p,p

1

p零元律p

1

1,p

0

0等幂律p

p

p,p

p

p交换律p

q

q

p,p

q

q

p结合律(p

q)

r

p

(q

r)(p

q)

r

p

(q

r)德摩根律

(p

q)

p

q

(p

q)

p

q吸收律p

(p

q)

p,p

(p

q)

p46基本等值式(续)分配律p

(q

r)

(p

q)

(p

r)p

(q

r)

(p

q)

(p

r)排中律p

p

1矛盾律p

p

0蕴涵等值式p

q

p

q等价等值式p

q

(p

q)

(q

p)假言易位p

q

q

p等价否定等值式p

q

p

q归谬论(p

q)

(p

q)

p47等价运算置换规则

若公式G中的一部分A(包含G中几个连续的符号)是公式，称A为G的子公式；用与A逻辑等价的公式B置换A不改变公式G的真值。

利用已知的等价关系式，将其中的子公式用和它等价的公式置换可以推出其它一些等价关系式，这一过程称为命题的等价运算。利用命题的等价运算，可以判断两个命题是否等价判断命题公式的类型命题公式的化简等。48例题例1.3.3证明p

q

q

p解

p

q

p

q

蕴涵等价式

(

q)

p

交换律和双重否定式

q

p

蕴涵等价式

条件命题：

p

q否命题：

p

q

逆命题：

q

p逆否命题：

q

p

条件命题和它的逆否命题等价49例题例1.3.4

利用命题的等价运算判断下列公式的类型。（1）

p

(p

q)解

p

(p

q)

p

(

p

q)蕴涵等价式

p

(p

q)摩根律

(

p

p)

q

结合律

F

q

矛盾式

F

零元律

该式是永假式50例题（2）p

(p

q)解p

(p

q)

p

(

p

q)蕴涵等价式

(p

p)

(p

q)分配律

F

(p

q)零元律

p

q同一律该式是可满足式51例题(3)(p

q)

(

q

p)解(p

q)

(

q

p)

(p

q)

(q

p)摩根律

(p

q)

(p

q)交换律

T排中律该式是永真式52例题化简公式(p

q)

(p

q)解(p

q)

(p

q)

p

(q

q)分配律

p

T

排中律

p

同一律53例题对于图1.3.1所示的逻辑电路，可否用更简单的电路实现该逻辑关系？54解：F

(p

q)

(

p

q)

(p

q)

(p

q)

q

p

q全功能联结词集定义1.3.2设G是一个联结词的集合，若任意一个命题公式都可用G中的联结词构成的公式来表示，则称G为全功能联结词集。如在G中去掉任何一个联结词，就不再具有这种特性，就称其为最小全功能联结词集。{

、

、

}，{

、

}，{

、

}，{

、

}，{

}和{

}都是全功能联结词集，而{

、

}，{

、

}，{

、

}，{

}和{

}都是最小全功能联结词集。55A

B(A

B)(B

A)A

B

A

BA

B

(A

B)

(A

B)A

B

(A

B)A

B

(A)B

A

B例题证明：{

},{

}是最小全功能联结词集证：

p(p

p)

p

pp

q(p

q)(p

q)(p

q)(p

q)得证{

}是联结词完备集.对于{

}可类似证明.

只用一个

或

就可以实现联结词

，

，

、

、

表示的逻辑关系。在数字电子技术中，只用与非门或者或非门组成的电路就可以实现任何逻辑运算。56

与非门或非门例题用只有一种与非门的逻辑电路实现F

(p

q)

(

p

q)

(p

q)。解：F

(p

q)

(

p

q)

(p

q)

p

q

(

p

q)

(p

p)

q57对偶式定义1.3.3在仅含有联结词

，

，

的公式A中，将其中的

换成

，

换成

，T(或1)换成F(或0)，F(或0)换成T(或1)，其它符号不变得到的公式称为A的对偶式，记为A*。p

q

和p

q

，p

q和p

q，

p

(q

r)和

p

(q

r)，p

q和p

q都互为对偶式58对偶式设A(p1，p2，…pn)和A*(p1，p2，…pn)互为对偶式，其中p1，p2，…pn是出现在A和A*中的全部的命题变元，则

A(p1，p2，…pn)

A*(

p1，

p2，…

pn)

A(

p1，

p2，…

pn)

A*(p1，p2，…pn)定理1.3.1设A和B为两个命题公式，A和A*，B和B*互为对偶式，若A

B，则A*

B*。证明

因为A(p1，p2，…pn)

A*(

p1，

p2，…

pn)，B(p1，p2，…pn)

B*(

p1，

p2，…

pn)，若A(p1，p2，…pn)

B(p1，p2，…pn)，则

A*(

p1，

p2，…

pn)

B*(

p1，

p2，…

pn)，即A*(

p1，

p2，…

pn)

B*(

p1，

p2，…

pn)，则A*(p1，p2，…pn)

B*(p1，p2，…pn)。59例题求公式A

p

(

p

(q

q))的对偶式。解

公式A的对偶式A*为：A*

p

(

p

(q

q))重言式A的对偶式A*是矛盾式601.4范式1.4.1析取范式与合取范式1.4.2主析取范式与主合取范式极小项与极大项主析取范式与主合取范式主范式的用途61析取范式与合取范式定义1.4.1一个命题公式具有形式A1

A2

….

.An(n

1)，其中A1，A2，

….，An

都是由命题变元或其否定所组成的合取式，则称该命题公式为析取范式。

如：

p

(p

q

r)

(

p

q)

q是析取范式。定义1.4.2一个命题公式具有B1

B2

….

.Bn(n

1)，其中B1，B2，

….，Bn都是由命题变元或其否定所组成的析取式，则称该命题公式为合取范式。

如：(p

q

r)

(

p

q)

q是合取范式。62范式存在定理定理1.4.1

任何一个命题公式都存在着与之等值的析取范式与合取范式.证

设G为任意一个公式，将公式化成只含

、

、

3个联结词的形式。将否定联结词内移或消去。利用分配律、交换律和结合律等将公式归纳为析取范式和合取范式。通过上面3个步骤可以求出与G等价的析取范式和合取范式，任意一个命题公式都存在着与之等价的析取范式和合取范式。

以上亦是求析取范式和合取范式的步骤。63例题求命题公式(p

(p

q))

q

的析取范式和合取范式。解

(p

(p

q))

q

(p

(

p

q))

q

(p

p)

(p

q)

q

析取范式

(p

q)

q

析取范式

q

析取范式

(p

q)

q

合取范式

(p

q)

(

p

q)合取范式

q

合取范式注意:公式的析取范式与合取范式不惟一.64主析取范式与主合取范式定义1.4.3

含有n个命题变元的合取式中，若每个命题变元与其否定不同时出现，而二者之一必出现且仅出现一次，这样的合取式称为极小项。定义1.4.4含有n个命题变元的析取式中，若每个命题变元与其否定不同时出现，而二者之一必出现且仅出现一次，这样的析取式称为极大项。说明:(1)由n个命题变元产生的不同的极大项和极小项的个数均为2n个。(2)每个极小项在它的2n个赋值中只有一个成真赋值(3)每个极大项在它的2n个赋值中只有一个成假赋值

65主析取范式与主合取范式(续)66

p

q

r

p

q

r

p

q

r

p

q

rp

q

rp

q

rp

q

rp

q

rm000

或

m0

m001

或

m1m010

或

m2m011

或

m3m100

或

m4m101

或

m5m110

或

m6m111

或

m73个命题变元的极小项

一般地，n个命题变元形成的极小项可表示为：主析取范式与主合取范式(续)3个命题变元的极大项67p

q

rp

q

rp

q

rp

q

r

p

q

r

p

q

r

p

q

r

p

q

rM000

或

M0M001

或

M1M010

或

M2M011

或

M3M100

或

M4M101

或

M5M110

或

M6M111

或

M7

一般地，n个命题变元形成的极小项可表示为：主析取范式与主合取范式定义1.4.5如果含n个命题变元的命题公式的析取范式的每个合取式全是极小项，则称该析取范式为主析取范式。定理1.4.2任何命题公式的主析取范式都是存在的，并且是唯一的。证明

给定命题公式A，1.求A的析取范式A´，A´的形式为A1

A2

….

.An(n

1)；；

2.若A´中的某个简单合取式Ai不是极小项，则补入在Ai中没有出现的变元。例如，若pi和

pi都不在Ai中，则将Ai展成如下形式：Ai

Ai

(pi

pi)

(Ai

pi)

(Ai

pi);3.重复步骤2)，直到所有的简单合取式都含有所有的命题变元或它的否定式；4.消去重复出现的命题变项、矛盾式及重复出现的极小项。

按上述步骤求得的就是A的主析取范式。

唯一性证明（略）

68例题求命题公式(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)

(

p

r)

(p

q

r)析取范式

((

p

q)

(r

r))

((

p

r)

(q

q))

(p

q

r)

(

p

q

r)

(

p

q

r)

(

p

r

q)

(

p

r

q)

(p

q

r)

(

p

q

r)

(

p

q

r)

(

p

q

r)

(p

q

r)

m0

m1

m2

m7

(0，1，2，7)69主析取范式例题试由p

q

r的真值表求它的主析取范式。

p

q

r的真值表

解：p

q

r的成真赋值为001，011，101，110，111p

q

r

(1，3，5，6，7)(

p

q

r)

(

p

q

r)

(p

r

q)

(p

r

q)

(p

q

r)一个命题公式的主析取范式中的每一个极小项的成真赋值就是该公式的一个成真赋值70p

q

rp

q

r00000101001110010111011101010111主析取范式与主合取范式定义1.4.6如果含n个命题变元的命题公式的析取范式的每个合取式全是极小项，则称该析取范式为

主合取范式。定理1.4.3任何命题公式的主合取范式都是存在的，并且是唯一的。证明

给定命题公式A，1.求A的合取范式B´，B´的形式为B1

B2

….

.Bn(n

1)；2.若B´中的某个析取式Bi不是极大项，则补入在Bi中没有出现的变元。例如，若pi和

pi都不在Bi中，则将Bi展成如下形式：

Bi

Bi

(pi

pi)

(B

pi)

(B

pi);3.重复步骤2)，直到所有的简单析取式都含有所有的命题变元或它的否定式；4.消去重复出现的命题变项、重言式及重复出现的极大项。

按上述步骤求得的就是A的主合取范式。

唯一性证明（略）

71例题求命题公式(p

(q

r))

(p

q

r)的主合取范式。

解

(p

(q

r))

(p

q

r)

(

p

(

q

r))

(p

q

r)

(

p

q)

(

p

r)

(

q

r

p)合取范式

((

p

q)

(r

r))

((

p

r)

(q

q))

(p

q

r)

(

p

q

r)

(

p

q

r)

(

p

q

r)

(p

q

r)

主合取范式

M3

M4

M5

M6

(3，4，5，6)

m0

m1

m2

m7

(0，1，2，7)72主析(合）取范式的用途（1）判断命题公式是否等价例1.4.5判断(

p

q)

(

q

r)

(

r

p)和(p

q)

(q

r)

(r

p)是否等价。解

(

p

q)

(

q

r)

(

r

p)

(M100

M101)

(M010

M110)

(M001

M011)

M4

M5

M2

M6

M1

M3

(1,2,3,4,5,6)(p

q)

(q

r)

(r

p)

(M010

M011)

(M001

M101)

(M100

M110)

M2

M3

M1

M5

M4

M6

(1,2,3,4,5,6)所以,(

p

q)

(

q

r)

(

r

p)和(p

q)

(q

r)

(r

p)等价。73主析(合）取范式的用途(2)求公式的成真赋值和成假赋值设公式A含n个命题变项,A的主析取范式有s个极小项,则A有s个成真赋值,它们是极小项下标的二进制表示,其余2n-s个赋值都是成假赋值例如

(p

q)

r

m0

m2

m4

m5

m6

成真赋值:000,010,100,101,110;成假赋值:001,011,11174主析（合）取范式的用途(续)(3)判断公式的类型设A含n个命题变项，则A为重言式当且仅当A的主析取范式含2n个极小项A为矛盾式当且仅当A的主析取范式不含任何极小项,记作0A为可满足式当且仅当A的主析取范式中至少含一个极小项A为矛盾式当且仅当A的主合取范式含2n个极大项A为重言式当且仅当A的主合取范式不含任何极大项,记作1

A为可满足式当且仅当A的主合取范式不是包含全部2n个极大项75例题判断公式G

(p

q)

(

q

p)是否重言式？解G

(p

q)

(

q

p)

(

p

q)

(q

p)

(p

q)

q

p

m10

(m01

m11)

(m00

m01)

m2

m1

m3

m0

m1

(0，1，2，3)公式G

(p

q)

(

q

p)是重言式76例题例1.4.7

设计一个集成学习系统，该系统综合三个基学习器的分类预测（正类或负类），以投票的方式决定输入样本的预测类别，即在超过半数基学习器给出正类的情况下判定该样本为正类，否则为负类。设计满足上述条件的集成学习分类器，并尝试以逻辑电路图的方式画出该分类器。77例题（续）

7800000010010001111000101111011111

例题

一种简单的三人表决器，表决者每人座位旁有一个按钮，表决时，若表示同意则按按钮，若不同意不按按钮；表决结果超过半数时，喇叭发出声音。设计满足上述条件的表决器。解

三个表决者的按钮分别为p，q，r，按按钮为1，不按按钮为0，喇叭为A，喇叭发声为1，不发声为0。A

(

p

q

r)

(p

q

r)

(p

q

r)

(p

q

r)

(p

q)

(p

r)

(q

r)

(p

(q

r))

(q

r)79p

q

rA00000101001110010111011100010111例题

某单位选派A、B、C三位业务骨干去进修，由于工作需要，选派要满足如下条件：若A去，则C同去。若B去，则C不能去。若C不去，则A或B可以去。问可以有哪些选派方案？80例题（续）解

设p:派A去，q:派B去，r:派C去。81有3个成真赋值，所以有3种选派方案：A和B不去，C去；A和C不去，B去；A和C去，B不去。该公式的成真赋值就是可行的选派方案。写出该公式的主析取范式：由已知条件可得：

1.5命题演算的推理1.5.1推理理论1.5.2推理证明方法82推理理论定义1.5.1设A和B是两个命题公式，当且仅当命题A

B是重言式时(即A

B

T时)，称从A可推出B，或A蕴涵B，或B是前提A的结论，可以表示成A

B。一般地，推理的前提可以有多个，若(A1

A2

An)

B是重言式，则称由前提A1，A2，

，An可推出结论B，可表示为(A1

A2

An)

B。83例题判断下列推理是否正确：p

(p

q)

q(p

q)

q

p解

写出p

(p

q)

q和(p

q)

q

p的真值表。

p

(p

q)

q

正确(p

q)

q

p不正确

84p

qp

(p

q)

q(p

q)

q

p0011011010111111例题证明“如果牛吃草，则马会飞；马不会飞，所以牛不吃草。”是正确的推理。证明

设：p：牛吃草；q：马会飞。前提符号化为：p

q，

q，结论符号化为：

p。

而(p

q)

q

p

((p

q)

q)

p

(p

q)

q

p

(p

q)

(p

q)T所以，

p是p

q和

q的有效结论，这个推理是正确的。注意：推理时，只要推理过程的每一步骤都遵循正确的推理规则，推出的结论都称为有效结论，推理都是有效的。85推理定律

86定理（CP规则）若H1，H2，...，Hm和P推出Q，则H1，H2，...，Hm推出P

Q。证明

从定理的假设有：H1

H2

...

Hm

P

Q

根据定义1.5.1，即有：H1

H2

...

Hm

P

Q

T令H1

H2

...

Hm

H，则

H

P

Q

(H

P)

Q

H

P

Q

H

(P

Q)

T所以H

P

Q，即：H1

H2

...

Hm

P

Q87推理证明方法真值表法等价演算法演绎法附加前提证明法间接推演法(归谬法)归结证明法881、真值表法通过写出真值表判断A

B的类型，若A

B是重言式，则由前提A可以退出结论B。例证明前提p

q和

p

r，可以推出结论q

r。证明

根据定义1.5.1，只需证明(p

q)

(

p

r)

q

r是重言式。列出真值表：

89

p

qrp

q

p

rq

r(p

q)

(

p

r)

q

r0000101001011101011110111111100100110111111101011111111190由真值表可知，(p

q)

(

p

r)

q

r是重言式，所以前提p

q和

p

r，可以推出结论q

r。2、等价演算法利用命题的等值演算判断A

B的类型，若A

B是重言式，则由前提A可以退出结论B。证明q是

p和

p

q的结论。证明

p

(p

q)

q

(

p

(p

q))

q

p

(

p

q)

q

p

q

q

T913、演绎法演绎法是从前提（假设）出发，依据公认的推理规则和推理定律，推导出一个结论来。命题演算推理系统：推理规则

推理定律基本等价公式92推理规则

1）前提引入规则

在推导的过程中，可随时引入前提集合中的任意一个前提。2）结论引入规则

在推导的过程中所得到的结论都可做为后续推导的前提。3）置换规则

在推导的过程中，命题公式的子公式都可以用等值的公式置换。4）CP规则(附加前提规则)如果推出的结论形为P

Q，则可以把P放到前提中去，设法推出Q即可。93例题证明：前提“今天下午有课且今天比昨天冷；只有今天下午没有课，我们才去游泳；如果我们不去游泳，则我们打蓝球；如果我们打篮球，我们就会感到精力充沛。”推出结论“我们感到精力充沛”是正确的。证明：设：p：今天下午有课，q：今天比昨天冷，r：我们去游泳，s：我们打篮球，h：我们感到精力充沛。则前提为：p

q，r

p，

r

s，s

h，结论是：h

94例题

证明：

步骤

公式

理由p

q

前提引入p(1)化简r

p

前提引入

r(2)，(3)拒取式

r

s

前提引入s(4)，(5)假言推理s

h

前提引入

h(6)，(7)假言推理

95例题证明

r

s是p

(q

r)，p˄q的结论。证明：

步骤

公式

理由p

q

前提引入p(1)化简q(1)化简p

(q

r)前提引入

q

r(2)，(4)假言推理

r(3)，(5)假言推理r˅s(6)附加

r

s(7)置换规则964、附加前提证明法证明r

s是p

(q

s)，

r

p，q的结论。证明

步骤

公式

理由r

附加前提引入

r

p

前提引入p(1)(2)析取三段论p

(q

s)前提引入q

s(3)(4)假言推理q

前提引入s(6)(5)假言推理975、间接推演法(归谬法)间接推演法就是把要推出的结论否定后与原来的前提一起使用推出矛盾结论的证明方法。

定义1.5.2设H1，H2，.....Hr是r个命题公式。若H1

H2

.....

Hr是矛盾式，则称H1，H2，.....Hr是不相容的，否则称H1，H2，.....Hr是相容的。98例题用间接法证明：

p是p

q，q

r，r

s的结论证明：

步骤

公式

理由

p

否定结论p(1)双重否定p

q

前提引入

q(2)，(3)假言推理q

r

前提引入

r(4)，(5)析取三段论r

s

前提引入r(7)化简F(8)，(6)合取996、归结证明法归结规则:(p

q)˄(

p

r)

q

r归结证明法：前提和结论必须被表示为子句，对于非子句的语句，可以用一个或多个等价的是子句的语句替换它子句是变元或其否定的析取，如p

q、

p

r等是子句100归结证明法证明：如果小张守门或小李上场，则A队获胜；或者A队未获胜，或者A队成为联赛第一名；A队没有成为联赛第一名。因此小张没有守门并且小李没有上场。证明

设p:小张守门;q:小李上场；r:A队获胜；s:A队成为联赛第一名.前提：(p˅q)

r，

r˅s，

s结论：

p˄

q前提中的(p˅q)

r

(p

q)

r

(

p

r)˄(

q

r)，所以用两个子句

p

r和

q

r代替(p˅q)

r。结论为两个子句：

p和

q101例题用归结规则证明如下：步骤

公式

理由

p

r

前提引入

r

s

前提引入

p

s(1)，(2)归结规则

q

r

前提引入

q

s(2)，(4)归结规则

s

前提引入

p(3)，(6)归结规则

q(5)，(6)归结规则

p˄

q(7)，(8)合取102离散数学及其应用103第2章谓词逻辑2.1谓词逻辑的基本概念2.2谓词合式公式2.3谓词公式的解释和分类2.4谓词演算的关系式2.5前束范式2.6谓词演算的推理1042.1谓词逻辑的基本概念2.1.1个体词和谓词定义2.1.1个体词是指可以独立存在的客体，可以是一个具体的事物或抽象的概念，是原子命题所描述的对象。

谓词是用来说明个体的性质或个体间的关系。例如，小王是个大学生

3大于2105谓词个体词个体词个体词谓词谓词

形如“b是A”类型的命题可表达为A(b)；表示多个个体间关系的命题，可表达为B(a，b)，或P(a，b，c)定义2.1.2

和一个个体相联系的谓词称为一元谓词，和二个个体相联系的谓词称为二元谓词，和n个个体相联系的谓词称为n元谓词。

个体常元

表示具体的或特定的个体，如a，b，c，

等；个体变元

表示抽象的或泛指的个体，如x，y，z，

等。

谓词常项

表示具体性质或关系的谓词，R(a)表示a是人；

谓词变项

表示抽象或泛指的谓词

，如：P(a)表示a具有P性质。106谓词表达式和命题函数定义2.1.3

一个原子命题可以用一个谓词常项P和几个个体常元，如a，b，c，

，表示成P(a，b，c，

)的形式。称P(a，b，c，

)为原子命题或命题的谓词表达式。

一个谓词常项P和几个个体变元如x，y，z，

表示成P(x，y，z，

)的形式，称为命题函数，其中的个体变元可以代表任意一个个体。注意：命题的谓词表达式是有真值的，命题函数的真值是不确定的。107例题写出下列命题的谓词表达式。

1.小王和小李是大学生。解：设A(x)：x是大学生。a：小王，b：小李。

A(a)

A(b)2.

北京是中国的首都。解：设F(x，y)：x是y的首都。a：北京，b：中国。F(a，b)3.如果你来，他就走。解：设P(x)：x来。Q(x)：x走。a：你，b：他。

P(a)

Q(b)108例题（续）4.如果3

2，2

1，则3

1。解：设B(x，y)：x

y。a：3，b：2，c：1。则

：

B(a，b)

B(b，c)

B(a，c)武汉位于北京和广州之间。解：设Q(x，y，z)：y位于x和z之间。a：北京，b：广州，c：武汉。Q(a，c，b)109个体域定义2.1.4命题函数中，个体变元的取值范围称为个体域或论述域。

个体域可以是有限的，也可以是无限的。把宇宙中一切事物作为对象的的集合称为全总个体域。通常，没有特别说明时，个体变元的论述域是指全总个体域。如：A(x)表示：x是大学生。个体域：华工计科1班学生，则A(x)是永真式。个体域：华工附中1班学生，则A(x)是永假式。个体域：xx公司员工，其中有些是大学生，有些不是大学生，则对有些人，A(x)为真，对有些人，A(x)为假。110例题给出执行语句“If

P(x)then