离散数学课件（第4版）

离散数学

、/一.1.

刖a

课程性质：计算机数学基础

课程安排:三个学期教授三个部分

第一部分:离散数学第一篇:数理逻辑

第二篇:集合论

第三篇：图论代数系统

第二部分:计算数学

第三部分:组合数学

学习目的：1、初步掌握现代数学的观点和方法；

2、初步掌握处理离散结构和方法，提高计算机系统设计和程序设计的逻辑数

字的能力；

3、初步掌握计算机在进行数的处理时的方法和计算；

4、培养学习抽象思维和缜密思考的能力；

第一篇数理逻辑

第一章命题逻辑

?1.1命题和命题联结词

一.命题：

定义:具有确定真值的表达判断的陈述句称为命题。

说明:？命题的真值:作为命题所表达的判断只有两个结果:正确和错误，此结果

称为

命题的真值。

命题是正确的，称此命题的真值为真;命题是错误的，称此命题的真值为假。

真值为真的命题称为真命题；真值为假的命题称为假命题。

?其它类型的句子，如疑问句、祈使句、感叹句均没有真假意义，因为均不是

题。

在数理逻辑中，命题的真值的真和假，有时分别用1和0来表达，也有时分别

用T和F来表达。

命题的分类：

原子命题:不能分解成更简单的命题的命题。

复合命题：由若干个原子命题用命题联结词、标点符号联结起来的命题。

例：

(1)10是整数。真原子命题

(2)北京是我们祖国的首都。真原子命题

(3)雪是黑的。假原子命题

(4)煤是白的。假原子命题

(5)今天是7号。在一定条件下是真命题(如果今天是7号)。

(6)1+11=100。在一定条件下是真命题(在二进制中)。

(7)我学英语，或者学法文。复合命题(8)如果天气好，我就去游泳。复合

命题(9)向右看齐〜祈使句非命题

(10)请勿吸烟〜祈使句非命题

(11)你吃饭了吗,疑问句非命题

(12)你上网了吗,疑问句非命题

(13)本命题是假的。悖论

(14)我正在说谎。悖论

（15）我不给所有自己给自己理发的人理发，但是却会给所有自己不给自己理发

的人理

发。悖论

命题标识符:用大写字母P、Q、R、P、P来表示命题，这些大写字母称12

为命题标识符。

命题常量:用命题标识符表示的确定的命题称为命题常量，它有确定的真值。

命题变量:表示任何一个命题的标识符，称为命题变量，它有不确定的真值。

二（命题联结词：

常见联结词

否定、合取、析取、蕴含、等价和异或

,1.否定符号：

,P是命题，P读作“非P”。

，P真值表为

，PP

01

10

否定的性质

,,双重否定律：（P）P,

,说明：1、P是一元联结词

所谓一元联结词就是联结一个命题的联结词。

2、念作“等值”，表示该符号两边的两个命题在任何情况下真值相同。，

2.合取符号：,

P、Q是命题

PQ读作“P且Q”，“P合取Q”。,

PQ真值表，

PQPQ,

000

010

100

111

例:P：今天下雨。Q：今天刮风。则PQ:今天下雨且刮风。

合取的性质

1）幕等律PPP,,

2）交换律PQQP,,,

3）结合律（PQ）CP（QC）,,,,,

4）零一律P00,,

5）同一律PlP,,

，6）否定律PP0,,

3.析取符号：，

P、Q是命题，记作PQ，读作“P或Q”，“P析取Q”。

PQ真值表，

PQPQ,

000

011

101

111

例:P：今天下雨。Q：今天刮风。则PQ:今天下雨或刮风。

析取的性质：

1)嘉等律ppp,,

QQP2)交换律P,,,

3)结合律(PQ)CP(QC),,,,,

OP4)同一律P,,

5)零一律PH,,

,6)否定律PP0,,

7)吸收律P(PQ)P,P(PQ)P,,,,,,

8)分配律P(QC)(PQ)(PC)P(QC)(PQ),,,,,,,,,,

(PC),,

,,,,,,9)德、摩根律(PQ)PQ,(PQ)PQ,,,,,,说明：(1)和混合运算

只能用分配律，不能用结合律。例:P(PQ)与P

不等值。

(2)和的分配律:P(QC)(PQ)(PC),形如乘与加的分配律

PX,,,,,,,,(Q+C)。

(3)可兼或与不可兼或

可兼或：明天下雨或刮风。

不可兼或:今天晚上去电影院看电影，或在家看电视。

4.蕴含符号：，

P、Q是命题

PQ读作''P蕴含Q"，“如果P则Q”，“当P,则Q"，“P是Q的充分条

件”。，

例:P:我去上海。Q:我给你买衣服。

PQ:如果我去上海，就给你买衣服。，

P假Q假我没去上海，也没给你买衣服。PQ真，

P假Q真我没去上海，但没给你买衣服。PQ真，

P真Q假我去了上海，但没给你买衣服。PQ假，

P真Q真我没去上海，也没给你买衣服。PQ真，

PQ真值表，

PQPQ,

001

011

100

111

P也称为前件;Q称为后件。

前件为假时，PQ必为真；，

后件为真时，PQ必为真。，

蕴含的性质

,,1)归化:PQPQ所谓归化就是用、、表示其它联结词。，，，，，

,,2)PQQP,,,

证明：

,,QPPQ,PQP,,

00111

01111

10000

11011

,,,,在全部四种情况下，PQ与QP的真值表相同，所以PQQP,,,,,

,,3)(PQ)PQ,,,

例:将下列命题符号化

1)如果1+2,3,则太阳从东边升起PQ,

,2)如果1+2?3,则太阳从东边升起PQ,

,3)如果1+2,3,则太阳从东边升起PQ,

,,4)如果1+2?3,则太阳从东边升起PQ,P:1+2=3

Q：表示太阳从东边升起

说明(1)蕴涵不存在交换律、结合律

PQ与QP不等值,,

(PQ)R与P(QP)等值,,,,

(2)在数理逻辑中，即使

Q没有内在联系PQ仍有意义P、，

5.等价符号：，

P、Q是命题

从读作“P等价于Q”，“P当且仅当Q"，“P是Q的充要条件”。

PQ真值表，

PQPQ,

001

010

100

111

等价的性质PQ(PQ)(QP)从,，，，，

,,,,(PQ)(PQ)(PQ)(PQ,,,,,,,

1)交换律:PQQP,,,

2)结合律：(PQ)RP(QR),,,,,

3)PQ(PQ)(QP),,,,,

,,，，4)归化:PQ(PQ)(PQ)(PQ)(PQ),,,,,,,,,

证明结合律

PQRP(QR)QPQR(PQ)R,,,,,,

0001010

0011101

0100101

0110010

1000111

1010000

1101000

1111111

左右两边在全部八种情况下均相等，所以两边等值，(PQ)RP(QR)。，，，，，

说明：

1)是逻辑联结词，而是公式关系符。A、B是命题，AB仍是命题，而AB,,,,

不是命题。

2)P、Q两命题，没有内在联系PQ仍有意义。,

例:2+2=5的充要条件是太阳从西边升起。真

该命题为真

6.不可兼或(异或)，

两个公式P、Q的异或是复合命题，

记作“PQ”,

读作“P异或Q”，“P不可兼析取Q”。

不可兼或就是两个命题不可能同时为真，当且仅当一个为真，一个为假时，为

真。

例：(1)今天下雨或刮风。(可兼或)

(2)今天第一节课是语文课或数学课。(不可兼或)

(3)他现在在301室或302室。(不可兼或)

P.Q真值表

PQP.Q

000

011

101

110

与或的区别:P为1且Q为1时，PQ为假。，

性质：(1)PQQP交换律，，，

(2)(PQ)RP(QR)结合律，，，，，

(3)P(QR)(PQ)(PR)对的分配律,,,,,,,,

,,(4)PQ(PQ)(PQ),,,,,

,,(PQ)(PQ),,,,

,(5)PQ(PQ),,,

三(命题公式：

1(命题公式

由命题标识符、逻辑联结词和圆括号按照一定的正确规则组成的合式，简称公

式。

命题公式的规定：

(1)单个命题变项是合式公式。

,(2)如果A是合式公式，则A是合式公式。

(3)如果A、B是合式公式,则AB、AB、AB、AB、AB也是合,，，，,

式公式。

(4)当且仅当有限次运用(1)(2)(3)所得到的符号串是合式公式。

逻辑联结词的运算优先次序依次为：

'，，，，，

，例:(PQ)，P(QR)，P(QR)是公式,,,,,

,(PQ,P,PQ,P不是公式，，，

P(QR)的括号可以省略，，

(PQ)R的括号不能省略,,

2(命题变项的指派(赋值)

,公式(PQ)(PQ)对命题变项P、Q、R没有真值指定，公式没有确定,，，

的真值。

指派(赋值)：命题公式中出现n个不同的命题变项PP,对这n个命题给定In

一组真值指定称为这个公式的一个指派或称为一个赋值。

若一个公式中出现n个不同的命题变项，每个变项分别可以取成1、0,那么该

n式共有个2不同的指派。

3例:前面公式共有P、Q、R三个不同命题变项，则共有2=8个指派。

PQR

000

001

010

011

100

101

110

111

3(公式的真值表

列出公式的所有指派及其相应的公式真值形成的表格称为公式的真值表

PC(QR)的真值表例：，

PQR(QR)P(QR,,,

00001

00101

01001

01111

10000

10100

11000

11111

公式真值表对我们进行证明以及判断公式的恒真、恒假起很大作用

4(两公式的等值

n给定两公式A、B,A、B中共出现n个不同的命题变项，对于所有的个2不同

的

指派，A、B两公式的真值均相同，记AB,读作“A与B等值”。，说明：

等值与等价不是一回事

等价是命题联结词，是AB公式，在某些指派下为真，某些指派下为假。，

等值不是逻辑联结词是公式关系符，AB描述了A、B两公式之间的关系，，

只有“成立”，“不成立”的区别。

5(全功能联结词组

定义了六个联结词，某些联结词可以同其他联结词替换

，例:PQPQ,,,

,,PQ(PQ)(PQ),,,,,

,,P,Q(PQ)(PQ),,,,

,、、，可以用、、等代换，，，，

一个联结词集合，若对于任何一个公式均可以用该集合中的联结词来等值比

较，

就称他为全功能联结词组(联结功能完备集)如果该集合任意去掉一个联结

词，就不再具备这种特性，就称为最小全功能联结

词组(最小功能完备集)

,例：｛、、｝是全功能联结词组,,

，,，又因PQ=(PQ),,

,,｛、｝、｛、｝是最小全功能联结词组，，

第一节小结

必须熟练掌握:什么是命题

什么是命题逻辑联结词

命题联结词的真值表的定义及命题联结词的性质

?1.2命题公式与赋值

命题公式:简单讲就是由命题表示符，逻辑联结词，括号按正确的规律联结起

来，形成

的符号串。

n公式的指派:一个公式中如果出现n个不同的命题变项，那么此公式就有2个

公式指

派。

公式真值表:将所有的公式指派列出来，并且相对应的列出公式的真值所得到

的表格。

例:求下列公式的真值表

，(1)PQ,

，(2)(PQ)P,,

，一(3)(PQ)(PQ),,,

,(4)(PQ)R,,

(5)(P(PQ))R,,,

,(6)(PQ)QR,,,

六个公式的真值表如下:

，⑴PQ,

,PQPQ,

001

011

100

111

,(2)(PQ)P,,

,PQPQ(PQ)P,,,

0000

0100

1000

1110

,,,(3)(PQ)(PQ),,,

,，(PQ)(PQ),,PQRPQ(PQ)PQ,,,,

0000111

0010111

0100111

0110111

1000111

1010111

1101001

1111001

Q)R⑷(P,,

PQRQPQ(PQ)R,,,000101001101010001011

001100110101111110001111001

，(5)(PQ)QR,,,

QP,,(PQ)(PQ)QR,,,PQR,,

000100

001100

010100

011100

100010

101010

110100

111100

(6)(P(PQ))R,,,

(PQ)(P(PQ))RPPQRPQ,,,,,,

0000110010110101110111111001111011

11110111111111

命题公式的分类：

永真式（重言式）：公式在一切赋值下的真值均为真。永假式（矛盾式）：公式在

一切赋值下的真值均为假。

可满足式：如公式不是矛盾式就是可满足式，即至少存在一个赋值使公式为

真。

仅可满足式:既不是矛盾式，又不是重言式的公式，即至少存在一个指派使公

式为真，

至少存在一个指派使公式为假。

,矛盾式

公式，，重言式

,可满足式，

,仅可满足式

说明：

（1）公式若不是永真式未必是永假式。

,（2）如公式G是永真式，则公式G是永假式（反之也成立）。

（3）证明公式是永真式和永假式的方法：

方法之一:使用真值表

方法之二：

，否定律:PP1（永真式），，

,PP0（永假式），,

零一律:P00（永假式），，

P11（永真式），,

第二节小结

讲解了公式的分类，永真式、永假式及其判断方法，，，，，，

第四节范式

一、对偶式和对偶原理

定义1:在仅含有联结词，，，，，，的命令题公式A中，将，换成，，将，换

成，，同时T和F

**(既0和1)互相替代，所得公式A称为A的对偶式。显然A是A的对偶式A

的对偶式。

例一(试写出下列命题公式的对偶式

(1)A:(P,Q),R

*则A为(P,Q),R

(2)A:(P,Q),(P,,(Q,,S))

*则A为(P,Q),(P,,(Q,,S))

(3)A:((P,Q),O),(1,,(R,,P))

*则A为((P,Q),1),(0,,(R,,P))

下面两个定理是对偶定理

定理2:A和是互为对偶式，P,P,,,,,P是出现在A和的原子变元，则2n*,

A(P,”，P),A(,P,,,,,P)nn**A(,P,”，，P),,A(P,,,,P)nn

即公式的否定等值于其变元否定的对偶式。

*例:A为P,Q,则A为P,Q,则，(P,Q),,P,,Q这就是DeMorgan律。

*再例如:A为(P,,刈，(i则人为小,，R),Q则，((P,,R),Q),(,P,R),,Q

****定理3:设A,B分别是A和B的对偶式，如果A,B,则A,B。这就是对

偶原理。如果证明了一个等值公式，其对偶式的等值式同时也成立。可以起到事半

功倍的效果。

例如:A,(P,Q),(,P,(,P,Q))B,,P,Q可以证明A,B

*而人的对偶式为A,(P,Q),(,P,(,P,Q))

*B的对偶式为B,,P,Q

**根据对偶原理，则A,B也成立。

说明：1)含有另外三个联结词，，，，，的公式，必须将其归化为然后再化为对

偶式。例:P,Q,(,P,Q),(P,,Q)

P,Q,(,P,Q),(P,,Q)

从而可知P,Q的对偶式是P,Q

*2)对偶原理不是说A与其对偶式A等值，一般公式与对偶是不是等值的。

二、范式：

1(简单析取式和简单合取式

定义2:仅有有限个命题变元或其否定的析取构成的析取式称为简单析取式。而

仅有有限个命题变元或其否定的合取构成的合取式称为简单合取式。例如：，

P,Q,R,,P,,Q,P是简单析取式，，P,R,Q,R,,Q是简单合取式。P,,Q一个

变项本身可以看作简单析取式也可以看作简单合取式。

而，P,(Q,R),(P,Q),,R不是简单析取式。

2(范式：

定义3:

?析取范式：由有限个简单合取式的析取构成的析取式称为析取范式。

?合取范式：由有限个简单析取式的合取构成的合取式称为合取范式。

例:P,(P,Q),(,P,,Q,,R)是析取范式

(P,Q),,Q,(Q,,R,S)是合取范式

P,Q,R是析取范式是三个简单合取范式的析取，同时也是合取范式是一个简单

析取范式的合取。而(P,Q),(,P,(Q,R))不是析取范式，因为，P,(Q,R)不是简单合

取范式。含有双重刮号的公式，肯定不是范式。

(P,Q),(Q,R)不是合取范式，因为其含有，，范式中只能包含，、，、，等逻辑

联结词。3、范式的存在性

定理:任意一个命题公式均存在一个与之等值的析取范式和合取范式

此定理证明是一个构造性证明，证明过程说明了公式的范式如何求得。

,第一步：将公式中出现的，，，，用，，来归化。，，，，

，所用公式为?PQPQ,,,

,,?PQ(PQ)(PQ),,,,,

,,(PQ)(PQ),,,,

,,?PQ(PQ)(PQ),,,,,

,,(PQ)(PQ),,,,

,,,第二步:用双重否定律PQ,或用德莫根律将一直移到命题变元之前，

第三步:用分配律、结合律化去额二重以上刮号成为析取范式或合取范式例2:

求公式((PQ)R)的析取范式和合取范式，，

,,,解：((PQ)R)((PQ)R)P((PQ)R)P,,,,,,,,,,

,,(PQ)(QR)P析取范式，，，，，

,,,(P(PR))(QR)P(QR)析取范式，，，，，，，，

,,，原式：((PQ)R)P(PQP)(RP)合取范式(PQ)(PR),,,,,,,,,,,,,合取范式

例3:求公式(PQ)(QR)的析取范式和合取范式，，，

,,,,,解：(PQ)(QR)(PQ)(QR)(QR)(PQ),,,,,,,,,,,,

,,91?)—析取范式，，,

,,,,,,,原式(PQ)((QR)(QR))(PQ)((QR)(QR)),,,,,,,,,,,,

,,,,,,,,(PQR)(PQR)(QQR)(QQR)合取范,，，，，，，，，，，，

，,，，,式(PQR)(PQR)(QR)合取范式，，，，，，，,

总结：

一个公式的析取范式与合取范式并不唯一。要使任一命题公式化为唯一的等值

命题的标准形式，就要用到主析取范式与主合取范式的概念。

三、主析取范式：

1(极小项

定义4:如公式中共有N个命题变项P,……，P这N个变项的合取n

式中，每个变项P或其否定，P,均出现且两者仅出现一个，并且按ii

命题变项的下标排列(字母按字典序列)这样的简单合取式称为极小项，又称布

尔合取。

例如:公式中出现P,Q,R三个命题变项

P,,Q,R,,P,Q,,R是极小项

P,,Q不是极小项，其中没出现R

P,,Q,,P不是极小项，P,,P同时出现

2(极小项和赋值的一一对应

n每一个极小项只有一个赋值使其为真，其余2-1个赋值使其为假。

例如:公式中出现P,Q,R三个不同的赋值。极小项，P,Q,,R,赋

3值010使其为真，其余2-1=7个赋值使其为假。这样极小项与赋值建立了一

一对应关系。而，P,Q不是极小项，有两个赋值010,011使其为真，其余6个赋

值使其为假。

3(极小项的记法

n公式共有2个赋值，每个赋值对应一个极小项。如极大项对应赋值

naaa,把其看作二进数，化为十进数为k,k,2-1,则该极小项记作1230

m,也记作mala2a3k

极小项对应的赋值十进制数记法

0000M或M,P,,Q,,R0000

0011M或M,P,,Q,R0011

0102M或M,P,Q,,R0102

0113或MM,P,Q,R0113

1004或MMP,,Q,,R1004

1015M或MP,,Q,R1015

1106M或MP,Q,,R1106

1117M或MP,Q,R1117

4.主析取范式：

定义4:若干个不同的极小项的析取式，称为主析取范式定理5:任何一个命题

公式均存在一个与之等值的主析取范式，

而且是唯一的。

例如：

P,(,P,Q),(P,Q),(,P,R)是析取范式,但不是主析取范式。(P,Q,,R),(,

P,Q,R)是主析取范式，当然也是析取范式。5(求主析取范式方法之一:真值表法

一个公式的主析取范式与该公式的真值是一一对应的例如：由三个极小项组成

的主析取范式

(P,Q,R),(,P,Q,R),(,P,Q,,R)

这三个极小项对应的赋值分别是111,Oil,010,则该三个赋值使公式为真，

而其它五个赋值使公式为假。

而反过来如果这三个赋值公式为真，而其它赋值使公式为假，则该公式的主析

取范式就是有这三个赋值对应的极小值的析取而成。

因此我们可以用真值表的方法来求出公式的主析取范式。例4:用真值表的方

法求，(P,Q)的主析取范式

解：，(P,Q)的真值表

PQ,(P,Q)P,Q

0001

0101

1001

1110

找使公式为真的赋值。

00对应的极小项是，P,,Q(m)0

01对应的极小项是，P,Q(m)1

10对应的极小项是P,,Q(m)2

则原公式的主析取范式是

，(P,Q),(,P,,Q),(,P,Q),(P,,Q)

,m,m,m012

例5:用真值表的方法求(P,Q),(Q,R)的主析取范式。解：(P,Q),(Q,R)的真值表

PQR(P,Q),(Q,R)对应极小项P,QQ,R

000011,P,,Q,,R001001,P,,Q,R01010001111

1,P,Q,R100111P,,Q,,R101100110100111111

P,Q,R找使公式真值为1的赋值。

由此主析取范式为：

(P.Q),(Q,R),(,P,,Q,,R),(,P,,Q,R),(,P,Q,R)

,(P,,Q,,R),(P,Q,R)

,m,m,m,m,m01347

6.求主析取范式的方法之二:等值演算法

利用十六个命题公式、命题定理用等值演算的方法一步步将它化为主析取范

式。第一步:将公式化为析取范式，“消去”含有矛盾式的简单合取式，这是因

为(P,,P,Q),G,G,而P,P用P代替。0

第二步:若析取范式中的简单合取式项不是极小项，即该项中缺命题变项，则

添加(P,,P)再用分配律展开。ii

例如:公式中含P、Q、R,某合取项为P,,R,缺Q。则P,,R,P,,R,(Q,,

Q),(P,Q,,R),(P,,Q,,R)第三步:用幕等律将重复的极小项删去，即m,m,m然

后将各极小iil

项按顺序排列。

例6:求(求Q),R),P的主析取范式。

解:原公式，，(，(P,Q),R),P

,((P,Q),,R),P

,(P,,R),(Q,,R),P(析取范式)

,P,(Q,,R)(析取范式)

,(P,(Q,,Q),(R,,R)),((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)

,(,P,Q,,R)

,m,m,m,m,m24567

,,(2,4,5,6,7)

5、间接证法

1)CP规则:

有时要证的结论以蕴含的形式出现。要证Al?A2?,,?Am,B,C。如果把结论中的

前件B作为附加条件加入前提集合中，即证出了Al,A2,,,,Am,B,C,则原来要证的

结论成立。称之为附加前提证明法。

简称CP规则。

证明:Al,A2,”,Am,B,C,Al,A2,,,,Am,B,C证明:Al,A2,,,,Am,B,C,Al,A2,Am,

(B,C),,(Al,A2,,,,Am),(,B,C),(,(Al,A2,”,Am),,B),C,,

(Al,A2,,,,Am,B),C,(Al,A2,„,Am,B),C?CP规则成立。

例6:试证(P?(Q?S))?(,R?P)?Q,R?S前提公式集合P?(Q?S),,R?P,Q,结论

R?S将结论R,S中的前项R引入前提集合，而去演绎出S。证明：(1),R?P规则P

(2)R规则P(附加前提)

(3)P规则T由⑴(2)(析取三段论)

(4)P?(Q?S)规则P

(5)Q?S规则T由⑶(4)(假言推理)

(6)Q规则P

(7)S规则T由(5)(6)(假言推理)

(8)R?S规则CP

例：证明｛,A?B,,B?C,C?D｝逻辑的推出A?D证法1:用CP规则

(1),A?B规则P

(2)A规则P(附加前提)

(3)8规则丁由(1)(2)(析取三段论)

(4),B?C规则P

⑸C规则T由⑶(4)(析取三段论)

(6)C?D规则P

(7)D规则T由⑸(6)(假言推理)

(8)A?D规则CP

证法2:不用CP规则

(1),A?B规则P

(2)A?B规则T由(1)(蕴含律)

(3),B?C规则P

(5)A?C规则T由(2)(4)(假言三段论)

(4)B?C规则T由(3)(蕴含律)

(6)C?D规则P

(7)A?D规则T由(5)(6)(假言三段论)

2)归谬法

设Al,A2,,,,Am是命题公式，

如果Al?A2,,,,Am是可满足的,称Al,A2,”,Am是相容的。如果Al,A2,”,Am

是矛盾式，称Al,A2,”，Am是不相容的。理论根据

Al,A2,Am,C,,,Al,A2,Am,,C,,,Al,A2,Am,,C)则

Al,A2,,,,Am,C,即Al,A2,,,,Am,C为重言式，Al,A2,,,,Am,,C是矛盾式。

从而得到如Al,A2,”，Am,,C不相容，则C是Al,A2,”，Am的有效结

论。

因此我们可以把，C作为附加前提推出矛盾来，从而可以得到C是Al,A2,

,,,Am的有效结

论。这种方法称为归谬法，也就是我们通常说的反证法。例7:是证明(R,,

Q),(R,S),(S,,Q),(P,Q),,P证明：(1)P,Q规则P

(2)P规则P(附加前提)

⑶Q规则T由⑴(2)(假言推理)

(4)R,,Q规则P

(5),R规则T由(3)(4)(拒取式)

(6)S,,Q规则P

(7),S规则T由(3)(6)(拒取式)

(8),R,,S规则T由⑷(7)(合取引入)

(9),,R.S,规则T由(8)(德.摩根律)

(10)R,S规则P

(11),,R,S,,,R,S,规则T由⑼(10)(合取引入)(12),,R,S,,,

R,S,是矛盾式，所以P为前提公式的有效结论

?1.7自我练习

1：求命题公式(P,(P,Q)),R的真值表

自我练习2:

求(P,Q,R),(,P,,Q,,R)的主析取范式。

解:原公式，(，P,(Q,R)),(P,(,Q,,R))

,(,P,P),(,P,,Q,,R),(Q,R,P),(Q,R,,Q,,R),0,(,P,,Q,,R),

(P,Q,R),0

,0,(,P,,Q,,R),(P,Q,R),m0,m7,?(0,7)自我练习3:

((A,B),C),(B,(D,0),(B,(D,A)),C

证明：左边，(，(A,B),C),(,B,(D.O),(,A,,B,C),(,B,C,D)

右边，，(B,(,D,A)),C,(,B,(D,,A)),C,(,A,,B,C),(,B,C,D)所以左边,

右边

自我练习4:构造下面推理证明

前提:，，P,,Q,,,Q,R,,R

结论:，P

证明：

(1),Q,R规则P

(2),R规则P

(3),Q规则T由(1)(2)(析取三段论)

(4),(P,,Q)规则P

(5),P,Q规则T由(3)(德•摩根律)

(6),P规则T由(3)(5)(析取三段论)

作业：

P32练习1.5:(A)l,3,5(B)1,2,3P35习题1:8(2)(3)(4)(5)

第二章谓词逻辑

苏格拉底三段论：

凡人要死，苏格拉底是人，所以苏格拉底要死，

P：凡人要死

Q：苏格拉底是人

R：苏格拉底要死

此三段论表示为(P,Q),R

苏格拉底三段论是正确的，但P,Q,R却不是重言式，这就是命题逻

辑的局限性。

?2.1谓词逻辑的基本概念

一、谓词

1.个体域：

命题逻辑中将命题(句子)继续细分。命题是由主语和谓语

两部分组成。主语是名词，称之为个体词。是独立存在的客体，可以

是具体事物也可以是抽象概念。

在谓语中含有宾语，它也是名词，它也是个体词。个体域:客体(个体)的取值

范围。

例如:吴华是大学生，用P表示，

李明是大学生，用Q表示。

在命题逻辑中就没办法表示出两句的联系。

“……是大学生”用A(X)表示，x是大学生，命题符号含有个体词变量。

a表示吴华，A(a)表示吴华是大学生。

b表示李明，A(b)表示李明是大学生。

相当于“……是大学生”，用A(?)来表示，这就是谓词。例：张三比李四高，

用H(x,y)表示x比y高。

a:张三b:李四

H(a,b):张三比李四高

H(b,a):李四比张三高

x,y,a,b表示客体，H(?,?)是谓词这个谓词涉及了两个客体，是二元谓词。

2.谓词：

只涉及一个客体的谓词称为一元谓词，涉及两个客体的谓词称为二元谓词，涉

及n个客体的谓词称为n元谓词。

一般，如A表示谓词符号，用X表示第i个客体变项，则ni

元谓词表示为A(x,…,x),如a,a,…,a是个体域中的客体名词,则lnl2n

A(a,a,…,a)是个命题。不含客体变项的谓词称零元谓词，零元谓12n

词本身就是命题。

注意：

(1)n元谓词中，客体变项的次序很重要。

例：F(x,y)表示x是y的父亲，

a:张三，b:张小明。

F(a,b)表示张三是张小明的父亲。

F(b,a)表示张小明是张三的父亲。

两个命题至多一个是真

(2)在讨论一个问题是必须先确定好个体域D。

如不作限制，表示宇宙一切事物组成的个体，成为全总个体域。(3)同一个n

元谓词，取不同的客观，真假会不同。

A(x):x是大学生。A(a)真值可能为真，而A(b)真

值可能为假。

(4)对于同一谓词，个体域D不同，真值可能也不同。

例:对于A(x),x是大学生。

如口=｛大学生全体｝,A(x)是重言式。

如口=｛学生全体｝,A(x)是仅可满足式。

如口=｛计算机全体｝,A(x)是永假式。3.命题函数

对于谓词B(x),B(x,y),H(x,y,z)等，本身不是命

题。

只有命题变项在D中取出个体名称时才成为一个确定的命题。

故谓词也称为命题函数或简单命题函数。

有限个简单命题函数用联结词，，，，，，，，，，，进行联结而成，成为复合命

题函数。

二、量词：

1.全称量词：

“所有的”，“任何一个”，“每一个”，“凡是”，“一切”表示个体域中

每一个，用符号”表示，称为全称量词。

例1:将下列命题符号化

(1)所有人都要呼吸

(2)每个人都是要死的

解：(1)设M(x):x是人，M(x):x是要呼吸。

命题符号化为:,x(M(x),H(x))。

(3)设M(设：x是人,D(x):x是要死的。

命题符号化为:,x(M(x),D(x))0

2.存在量词：

“有些”，“存在”，“至少有一个”，表示个体域D中存在个体，用符号

”表示。

例2:将下列命题符号化

(1)有些人是聪明和美丽的。

(2)有人早饭吃面包。

解：(1)设M(x):x是人，Q(x):x是聪明的，

R(x):x是美丽的。

命题符号化为：，x(M(x),Q(x),R(x))o

(3)设M(x):x是人，E(x):x是早饭时吃面包，

命题符号化为：，x(M(x),E(x))

说明:命题符号化之前，必须明确个体域的范围，以上两例子均为

全总个体域。

如果将个体域改为D=｛人类｝,则特性谓词M(x)就不需要

了。

例1:(1),xH(x),(2),xD(x)

例2:(1),x(Q(x),R(x))

(2),xE(x)

3.含量词的谓词的真值规定

说明：不含量词的谓词公式G(x),它不是命题，而是命题函

数，其真值依赖于x从个体域中取的个体名词的不同而不

同。

例:D表示某班全体学生，G(x)表示x是男生。

则G(李刚)是真，而G(王芳)是假。

而,xG(x)与,xG(x)是命题了，x仅是一个“指导变量”

,xG(x)与,xG(y)意义完全相同。

,xG(x):全班每个人均是男生。

,xG(x):全班存在一个人是男生。

含量词的谓词公式的真值不再依赖于x的选取了。

(1),xG(x)的真值规定

,xG(x)的命题是“对任意x,D,均有G(x)”

,xG(x)的真值为1,当且仅当，对一切x,D,G(x)真值

均为1,,xG(x)的真值为0,当且仅当，对一切x,D,0

G(x)真值为0。0

(2),xG(x)的真值规定

,xG(x)的命题是“存在一个x,D,使得G(x)成00立”

，xG(x)的真值为1,当且仅当存在x,D,0

66)的真值为1。0

,xG(x)的真值为0,当且仅当，对一切x,D,

G(x)的真值为0。

例如:D={a,b,c},由以上规定可知：

,xG(x),G(a),G(b),G(c)

,xG(x),G(a),G(b),G(c)

注:对于一个谓词，如其每个变量均在量词的管辖下，则该

不是命题函数，而是命题了，它有确定的真值了。

例3将下列语句表示为谓词逻辑的命题。

(1)所有的正数均可开方。

)若个体域为全体正实数R+,S(X):X可以开方，则命题符号化为:，xS(x)

解：(i

(ii)若个体域为全体实数集R,G(x,y):x>y,则命题符号化为:，x((G(x,0),

S(x))(iii)若D,全总个体域,R(x):x是实数,则符号化为:,x(R(x)?G(x,0),

S(x))

4:03

(2)没有最大的自然数

即理解为“对所有x,若x是自然数，则存在y,y也是自然数，且y>x”

解:N(x):x是自然数，G(x,y):x>y,符号化为:，x(N(x),,y(N(y)?G(y,x))也可以

理解为“下句话是不对的'存在一个x,x是自然数且对一切自然数y,x均大于

y’”,符号化为:，，x(N(x)?,y(N(y),G(x,y))

以后可以证明，这两个公式是等值的。8:15注:不可以用最大来直接定义谓

词。

设B(x):x是最大的,N(x):x是自然数。

以上命题可以表示为：，，x(B(x)?N(x))

这是不对的。“最大”是比较而来，依赖于其它客体，最大最小不能直接作谓

而jO

10:08

?2.2谓词公式

一、谓词公式的定义：

L谓词公式中出现的字母表：

定义1：字母表如下：

(1)个体常量:a,b,c,...,al,a2,a3,...

(2)个体变量:x,y,z,...,xl,x2,x3,...

(3)函数符号:f,g,h,...,f1,f2,f3,...

(4)谓词符号:P,Q,R,....SO,SI,S2,...

(5)量词符号:，…

(6)逻辑符号：，，，，，，，，，，，

(7)括号和逗号：(,)，15:10:302.项的定义:

项在谓词公式中起的是名词的作用，它不是句子。

定义2:项的递归定义如下：

(1)任意个体常量或个体变量是项。

(2)如果f(Xl,X2,X3,...,Xn)是任意n元函数,tl,t2,...tn是项,则

f(tl,t2,...,tn)

仍然是项。

(3)只有有限次使用(1),(2)生成的符号串才是项。19:10例:D是个体名称

集，x,D,人名变量，a:张三，b:李四。

x,a,b是项,

f(x):x的父亲,S(x,y),x和y的儿子。

f(a):张三的父亲，仍然是个名词，不是句子，它仍是项。

f(f(a)):张三的祖父,

而P(x,y):x是y的父亲，是句子而不是名词。其是命题函数，而不是项了。

23:17

例:D:是实数集的全体。

f(x)=lnx,g(x,y)=x+y,h(x,y)=x*y

其均是函数，算术表达式，其结果仍是数，仍可以在函数的自变量位置上出

现。g(g(x,y),h(x,y))=((x+y)+(x*y))

f(g(x,y))=In(x+y)

x+y=5,x*y+a〉5,此类是逻辑表达式，其结果不是数了，是成立或不成立，是真

或

假,因而不是项。26:51

3(原子公式的定义

原子公式是公式的最小单位，最小的句子单位。项不是公式。

定义3:若P(xl,...,xn)是n元谓词，tl,...,tn是项，则tn)为

原子公式。(1)从中可以看出，项也可以出现在谓词的变量位置，相当于名词，可

以做句子的主语或宾语。

(2)函数,tn)不是句子，仅是词，因而不是公式仅是项。项的结果仍

是个体名称集中的名词，而公式的结果(真值)是成立或不成立(是1或0)。30:37

4(谓词公式的定义：

定义4:合式公式的递归定义如下：

(1)原子公式是合式公式；

(2)如A,B是公式,则，A,A,B,A,B,A,B,A,B,A,B也是公式；

(3)如A是公式，x是A中出现的任意有关变元，贝LxA,,xA也是合式公式。

(4)只有有限次使用(1)(2)(3)生成的符号串才是合式公式(也称谓词公式)

例:H(a,b),C(x),B(x),,x(M(x),H(x)),,x(M(x),C(x),B(x)),,x,y(M(x),

H(x,y),L(x,y))等均是合式公式。当然以上出现的大写英文字母均是谓词符号。

38:01二、约束变量和自由变量

定义5:在合式公式,xA和，xA中，x是指导变元，A为相应量词的作用域或辖

域。在辖域中x的出现称为x在公式A中的约束出现;约束出现的变元称为约束变

元;A中不是约束出现的其它变元称为该变元的自由出现，自由出现的变元成为自

由变元。40:05例一指出各公式的指导变元，辖域、约束变元和自由变元。

(1),x(p(x),,yQ(x,y))

解：由，x后的()，x是指导变元，，x的辖域是后面整个式子，y是指导变元，

辖域仅Q(x,y)此部分。x两次出现均是约束出现，y的一次出现是约束出现，故

x,y是约束变元，而不是自由变元。

(2),xF(x),G(x,y))

解：，x的辖域仅F(x),x是指导变元，变元x第一次出现是约束出现，第二次

出现是自由出现，y的出现是自由出现。所以第一个x是约束变元，第二个x是自

由变元，本质上这两个x的含义是不同的;而y仅是自由变元。45:22

22(3),x(x=y,x+x<5,x<z),x=5y

222x+x是函数不是谓词，x=y,x+x<5,x〈z,x=5y这是四个原子公式。用逻辑

词，，，，，来联结起来的。

x是指导变元、，x的辖域是0内的这部分。因此，x第一、二、三、四次出现

是约束出现，x第五次出现是自由出现。而y,z的出现均是自由出现。47:56

三、换名规则

从以上例子中可以看此在谓词公式中一个变元可能既是约束出现，同时又有自

由出现,则该变元既是自由变元又是约束变元,本质上这两种出现,用的是一个符号,

实质上是不同的含义。为避免混淆，需要改名。改名要采用以下规则，使谓词公式的

含义不改变。2:151、换名规则:对约束变元进行换名。

将量词辖域内出现的某个约束变元及其相应量词中的指导变元，可以换成一个

其他变元，

改变元不能与本辖域内的其他变元同名，公式中的其他部分不改变。

2、代入规则:对自由变元进行代入。

整个谓词公式中同一个字母的自由变元是指同一个个体名词。因此可以用整个

公式中所

有变元的符号来代替，且要求整个公式中该变元同时用同一个符号代替。

4:35例：(l),xF(x,y)?,xG(x,y)

x是约束变元,y是自由变元。而x的两次出现尽管均是约束的，但分别在不同

的辖域。含义是互相无关的。可以将一处换名，但不能与y同名。

改为,xF(x,y)?,uG(u,y)

(2),x(F(x,y),P(x))?,y(Q(x,y),R(x)

x前两次出现是约束的,后两次出现是自由的。y第一次出现是自由的，第二次

是约束的,准备将自由变元x改为u,自由变元y改为V,成为

,x(F(x,v),P(x))?,y(Q(u,y),R(u))11:04

说明：(1)如果D是有限集，谓词公式中的量词可以用逻辑联结词来解释。例

D={a,b,c)

,xP(x),P(a)?P(b)?P(c)

,,xP(x),P(a),P(b),P(c)

(2)量词不能随便换顺序。对于，和，这两个量词交换位置，其意义不同了，相应

真值也可能改变。

例:D:自然数全体,G(x,y):x小于y„

,x,yG(x,y)表示任意一个自然数x,总存在自然数y,使得x小于y,该命题是真

的。

,y,xG(x,y)表示存在一个自然数y,使得对一切自然数x,使x小于y,即y是最

的自然数。该命题是假的。14:55

?2.3谓词的等值演算

一、谓词逻辑中的解释(赋值)

在命题逻辑对每个命题符号作个真值指定可以得一个公式的一个指派，又称赋

n值,又称解释。如公式中共出现n个不同的命题符号,则共有2个解释，因而可

列出公式的真值表。而谓词逻辑中公式的赋值解释是怎样的呢，

16:33

1.谓词公式的赋值(解释)

定义6:谓词公式的赋值是对以下一些符号进行指定:谓词公式A的个体域为

D(这也必须指定)

(1)每一个个体常项指定D中的一个元素

n(2)每一个n元函数D到D的一个映射

n(3)每一个n元谓词D到{0,1}的一个映射

以上一组指定称为谓词公式A的一个解释或赋值19:16

例1:已知一个解释I如下：

1)0={2,3}2)指定a=2?Dx

3)函数f:D,D指定f(2)=3,f(3)=2

4)谓词P:D,{0,1}指定P(2)=0,P(3)=1。

2Q:D,{O,ll.QCi,j)=l,i,J=2,3

在该解释I下

,x(P(x),Q(x,y)),(P(2),Q⑵2)),(P(3),Q(3,2)),(0,1),

(1,1),0

公式，x(P(f(x)),Q(x,f(a)),(P(f(2)),Q(2,f(2)),

(P(f(3)),Q(3,f(2)),(P(3)

,Q(2,3)),(P(2),Q(3,3),(1,1),1

25:25

例2:已知指定一个解释N如下：

(1)个体域为自然数集合DN

(2)指定常项a=0

(3)D上的指定函数f(x,y)=x+y,g(x,y)=x*yN

(4)指定谓词F(x,y)为x=y

在以上指定的解释N下，说明下列公式的真值

(1),xF(g(x,a),x)即，x(x*0=x)该命题假的(2),x,

y(F(f(x,a),y),F(f(y,a),x))

在解释N下此公式:，，x,y(x+0=y,y+0=x)此命题为真

(3)F(f(x,y),f(y,z))在解释N下该公式,x+y=y+z

此时,x,y,z均为自由变元,解释不对自由变元进行指定。因而该公式是命题函

数，

不是命题，真值不能确定。34:23

说明：

(1)一个谓词公式如果不含自由变元,则在一个解释下,可以得到确定的诊治，

不同的解释下可能得到不同的真值。

(2)公式的解释并不对变元进行指定,如果公式中含有自由变元,即使对公式进

行了一个指派,也得不到确定的真值,其仅是个命题函数，但约束变元不受此限制。

(3)有公式的解释定义可以看出，公式的解释有许多的解释，当D为无限集时，

公式有无限多个解释,根本不可能将其一一列出，因而谓词逻辑的公式不可

能有真值表可列。38:50

2.永真式和永假式

定义7:设A为一个谓词公式,如果A在任何解释下均为真,称A为逻辑有效式

(或称永真式)；如果A在任何解释下均为假,称A为矛盾式(或称永假式);如果存在

一个解释使A为真,则称A为可满足式；

例如：，P(x),P(x)是永真式

,P(x),P(x)是永假式

43:33

作业布置：

P14练习2.1(A)1(2)(3),2(1),(B)l,2,4

P44练习2.2(A),(B)2,5

47:28

第2编集合论

第3章集合及其运算

?3.1集合的概念和表示方法

一、集合：

将一个确定的，可以区分的事物的全体称为集合，而这些事物称为集合的元

素。

集合用大写字母A,B,”来表示，而集合的元素一般用小写字母表示。

若a是A的元素称a属于A,记作