离散数学第2章(屈)

离散数学

华南理工大学计算机学院张芩arcview@126.com1离散数学（DiscreteMath）数学所研究的对象根据它们的取值分为：

连续的，如长度、温度、面积等。

离散的，如商店商品，学生所学课程等。离散数学是研究离散对象的结构以及它们之间相互关系的一门数学学科。因为计算机不论硬件还是软件都属于离散结构，所以所应用的数学必是离散数学。2课程的性质、目的和任务

离散数学是计算机学科的专业基础课，通过介绍离散数学的基本理论、基本思想和基本方法，使学生掌握学习后继课程，如数据结构、数据库、网络、人工智能等必备的基础知识和基本技术，得到一个较好的数学训练，为从事计算机科学技术领域的工作打下一个扎实的理论基础。

3课程的要求教学基本要求要求掌握基本概念、基本原理，培养学生用离散数学的观点去分析解决计算机科学及工程应用中所遇到的问题，努力提高逻辑推理和抽象思维的能力。先修课程高等数学、线性代数4学习内容数理逻辑

（第二、三章）计算机科学的基础，应熟练掌握将现实生活中的条件化成逻辑公式，并能做适当的推理，这对程序设计、数字电路等课程是极有用处的。集合论

（第一、四、五章）数学的基础，对于学习程序设计、数据结构、编译原理等几乎所有计算机专业课程和数学课程都很有用处。熟练掌握有关集合、映射、关系等基本概念。图论

（第六、七章）对于解决许多实际问题很有用处，对于学习数据结构、编译原理课程也很有帮助。要求掌握有关图、树的基本概念，以及如何将图论用于实际问题的解决，并培养其使用数学工具建立模型的思维方式。5数理逻辑逻辑是研究人的思维的科学。辩证逻辑：研究人的思维中的辩证法。

用全面的和发展的观点观察事物；具体问题具体分析；实践是检查事物正误的唯一标准；等等。形式逻辑：研究人的思维的形式和一般规律。这里我们只关心形式逻辑。6形式逻辑人的思维过程：概念

判断

推理

正确的思维：概念清楚，判断正确，推理合乎逻辑。人们是通过各种各样的学习(理论学习和从实践中学习)来掌握许多概念和判断。而形式逻辑主要是研究推理的。推理：是由若干个已知的判断(前提)，推出新的判断(结论)的思维过程。7推理方法类比推理：由个别事实推出个别结论。如：地球上有空气、水，地球上有生物。火星上有空气、水。

火星上有生物。归纳推理：由若干个别事实推出一般结论。如：铜能导电。铁能导电。锡能导电。铅能导电。

一切金属都导电。演绎推理：由一般规律推出个别事实。形式逻辑主要是研究演绎推理的。8演绎推理举例例1：如果天下雨，则路上有水。(一般规律)

天下雨了。(个别事实)

推出结论：路上有水。(个别结论)例2：

(大前提)：所有金属都导电。(一般规律)(小前提)：铜是金属。(个别事实)

推出结论：铜能导电。(个别结论)9数理逻辑数理逻辑是用数学方法来研究推理过程的科学。主要是指引进一套符号体系的方法，因此数理逻辑一般又叫“符号逻辑”。基本内容

第二章命题逻辑

第三章一阶逻辑10数理逻辑把推理符号化之一设P表示：天下雨。设Q表示：路上有水。设表示：如果…则…例1的推理过程表示为：前提1:PQ(如果天下雨,则路上有水。)前提2：P(天下雨了。)结论：Q(路上有水。)这就是第二章“命题逻辑”中要讨论的问题。11数理逻辑把推理符号化之二设M(x):x是金属。设C(x):x能导电。设

x表示:所有的x。设

a表示铜。例2的推理过程表示为：前提1:

x(M(x)

C(x))(所有金属都导电)前提2:M(a)(铜是金属)结论:C(a)(铜能导电)其中符号M(x)是谓词，所以这就是第三章“一阶逻辑”中所讨论的内容.12第2章命题逻辑2.1命题逻辑基本概念

2.2命题逻辑等值演算

2.3范式2.4命题逻辑推理理论

132.1命题逻辑基本概念

2.1.1命题与联结词命题与真值(简单命题,复合命题)联结词(¬,,,,)

2.1.2

命题公式与分类命题公式及其赋值真值表命题公式的分类

14命题及其真值命题:判断的结果惟一的陈述句命题的真值:判断的结果,真或假真命题:真值为真的命题假命题:真值为假的命题注意:感叹句、祈使句、疑问句都不是命题。陈述句中的悖论以及判断的结果不惟一确定的也不是命题。15例1

下列句子中那些是命题？

(1)北京是中华人民共和国的首都.(2)2+5＝8.(3)x+5＞3.(4)你会开车吗？(5)2050年元旦北京是晴天.(6)这只兔子跑得真快呀！(7)请关上门！(8)我正在说谎话.真命题假命题真值不确定疑问句感叹句祈使句悖论(1),(2),(5)是命题,(3),(4),(6),(7),(8)都不是命题真值确定,但未知实例16简单命题与复合命题简单命题(原子命题):简单陈述句构成的命题简单命题的符号化:p,q,r,…,pi,qi

,ri(i≥1)用“1”表示真，用“0”表示假复合命题:由简单命题通过联结词联结而成的陈述句

例如如果明天天气好,我们就出去郊游设p:明天天气好,q:我们出去郊游,如果p,则q

又如张三一面喝茶一面看报设p:张三喝茶,q:张三看报,p并且q17联结词与复合命题定义2.1

设p为命题,复合命题“非p”(或“p的否定”)称为p的否定式,记作

p,符号

称作否定联结词,并规定

p为真当且仅当p为假。P

PT

FF

T例如p:2是合数,

p:2不是合数,

p为假,

p为真18联结词与复合命题定义2.2

设p,q为二命题,复合命题“p并且q”(或“p与q”)称为p与q的合取式,记作p∧q,∧称作合取联结词,并规定

p∧q为真当且仅当p与q同时为真。

PQ

P

Q

TT

T

TF

F

FT

F

FF

F例如p:2是偶数,q:2是素数,

p∧q

:2是偶素数,p为真,q为真,p∧q为真“和”，“与”，“并且”，“既...又...”，“不仅...而且...”“虽然...但是...”19实例例2

将下列命题符号化.(1)王晓既用功又聪明.(2)王晓不仅聪明，而且用功.(3)王晓虽然聪明，但不用功.(4)

张辉与王丽都是三好生.(5)张辉与王丽是同学.解

记p:王晓用功,q:王晓聪明(1)p∧q(2)p∧q(3)

p∧q(4)记r:张辉是三好生,s:王丽是三好生,r∧s(5)简单命题,记

t:张辉与王丽是同学20联结词与复合命题(续)定义2.3设p,q为命题,复合命题“p或q”称作p与q的析取式,记作p∨q,∨称作析取联结词,并规定p∨q为假当且仅当p与q同时为假.例如张三和李四至少有一人会英语设p:张三会英语,q:李四会英语,符号化为p∨q“相容或”与“排斥或”例如这件事只能由张三和李四中的一人去做设p:张三做这件事,

q:李四做这件事应符号化为(p∧

q)∨(

p∧q)

PQ

P

Q

TT

T

TF

T

FT

T

FF

F21实例例3

将下列命题符号化(1)2或4是素数.(2)2或3是素数.(3)4或6是素数.(4)元元只能拿一个苹果或一个梨.(5)王晓红生于1975年或1976年.解记p:2是素数,q:3是素数,r:4是素数,s:6是素数(1)p∨r,(2)

p∨q,(3)r∨s,(4)记t:元元拿一个苹果,u:元元拿一个梨真值:1真值:1真值:0(t∧

u)∨(

t∧u)(5)记v:王晓红生于1975年,w:王晓红生于1976年(v∧

w)∨(

v∧w)22联结词与复合命题(续)定义2.4设p,q为二命题,复合命题“如果p,则q”称作p与q的蕴涵式,记作p

q,并称p是蕴涵式的前件,q为蕴涵式的后件.

称作蕴涵联结词,并规定,p

q为假当且仅当p为真且q为假.

T

T

F

T

P

Q

FF

FT

TF

TT

PQ例如如果明天天气好,我们就出去郊游。设p:明天天气好,

q:我们出去郊游,形式化为p

q23蕴涵联结词(续)p

q

的逻辑关系:q为p的必要条件“如果p,则q”的多种表述方式：若p,就q

只要p,就qp仅当q

只有q

才p除非q,才p

除非q,否则非p当p为假时，p

q为真(不管q为真还是为假)24实例例4

设p:天冷,q:小王穿羽绒服，将下列命题符号化

(1)只要天冷，小王就穿羽绒服.(2)因为天冷，所以小王穿羽绒服.(3)若小王不穿羽绒服，则天不冷.(4)只有天冷，小王才穿羽绒服.(5)除非天冷，小王才穿羽绒服.(6)除非小王穿羽绒服，否则天不冷.(7)如果天不冷，则小王不穿羽绒服.(8)小王穿羽绒服仅当天冷的时候.注意：

p

q与

q

p

等值（真值相同）p

qp

q

q

p

或p

q

q

p

或p

qq

p

p

q

或q

p

p

q或

q

pq

p25联结词与复合命题(续)定义2.5设p,q为命题,复合命题“p当且仅当q”称作p与q的等价式,记作p

q,

称作等价联结词.并规定p

q为真当且仅当p与q同时为真或同时为假.

p

q

的逻辑关系:p与q互为充分必要条件例如这件事张三能做好,且只有张三能做好。设p:张三做这件事,q:这件事做好了。形式化为:p

q

T

F

F

T

P

Q

FF

FT

TF

TT

PQ26实例例5

求下列复合命题的真值(1)2+2＝4当且仅当3+3＝6.(2)2+2＝4当且仅当3是偶数.(3)2+2＝4当且仅当太阳从东方升起.(4)2+2＝5

当且仅当美国位于非洲.101127联结词与复合命题(续)联结词优先级:(),

,

,

,

,

同级按从左到右的顺序进行

pq

pp∧qp∨qp

qp

q

0010011011011010001001101111基本复合命题的真值28合式公式命题常项:简单命题

命题变项:真值不确定的陈述句定义2.6

合式公式(命题公式,公式)递归定义如下：(1)单个命题常项或变项是合式公式,并称作原子合式公式(2)若A是合式公式,则(

A)也是合式公式(3)若A,B是合式公式,则(A

B),(A

B),(A

B),(A

B)也是合式公式(4)只有有限次地应用(1)~(3)形成的符号串才是合式公式说明:在不影响运算顺序时,括号可以省去

例如0,p,

p

q,(p

q)

(

p

r),

p

q

r,(p

q)

r29公式的赋值定义2.8设p1,p2,…,pn是出现在公式A中全部的命题变项,给p1,p2,…,pn指定一组真值,称为对A的一个赋值或解释.使公式为真的赋值称作成真赋值,使公式为假的赋值称作成假赋值。说明:(1)赋值记作

=

1

2…

n,

i=0或1,诸

i之间不加标点符号(2)通常赋值与命题变项之间按下标或字母顺序对应,即当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,…30实例例6

公式A=(

p1

p2

p3

)

(p1

p2)000是成真赋值,001是成假赋值公式B=(p

q)

r000是成假赋值,001是成真赋值31真值表例7给出公式的真值表(1)

(q

p)

q

p

pq

q

p

(q

p)

q

(q

p)

q

p

00011011

1011

0001

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

(

p

q)

q

pq

p

p

q

(

p

q)

(

p

q)

q00011011

110011010010000033实例(续)(3)(p

q)

r

pqr

p

q

r

(p

q)

r

000001010011100101110111

00111111

10101010

1110101034命题公式的分类重言式(永真式):无成假赋值的命题公式矛盾式(永假式):无成真赋值的命题公式可满足式:非矛盾式的命题公式注意:重言式是可满足式，但反之不真.例如上例中(1)

(q

p)

q

p为重言式(2)

(

p

q)

q为矛盾式(3)(p

q)

r为可满足式352.2命题逻辑等值演算2.2.1等值式与等值演算等值式与基本等值式真值表法与等值演算法2.2.2联结词完备集真值函数联结词完备集与非联结词和或非联结词36定义2.11若等价式A

B是重言式,则称A与B等值,记作A

B,并称A

B是等值式说明:(1)

不要混同于

和=(2)A与B等值当且仅当A与B在所有可能赋值下的真值都相同,即A与B有相同的真值表。(3)可能有哑元出现.在B中出现,但不在A中出现的命题变项称作A的哑元.同样,在A中出现,但不在B中出现的命题变项称作B的哑元.哑元的值不影响命题公式的真值.等值式37真值表法例1

判断

(p

q)与

p

q

是否等值解结论:

(p

q)

(

p

q)

pq

p

qp

q

(p

q)

p

q

(p

q)(

p

q)0011011101101001100110011100100138真值表法(续)例2判断下述3个公式之间的等值关系:

p

(q

r),(p

q)

r,(p

q)

r解

pqrp

(q

r)(p

q)

r(p

q)

r000101

001111010101011111100111101111110000111111p

(q

r)与(p

q)

r等值,但与(p

q)

r不等值39基本等值式双重否定律

A

A幂等律

A

A

A,A

A

A交换律

A

B

B

A,A

B

B

A结合律(A

B)

C

A

(B

C)(A

B)

C

A

(B

C)分配律

A

(B

C)

(A

B)

(A

C)

A

(B

C)

(A

B)

(A

C)德摩根律

(A

B)

A

B

(A

B)

A

B吸收律

A

(A

B)

A,A

(A

B)

A40基本等值式(续)零律

A

1

1,A

0

0同一律

A

0

A,

A

1

A排中律

A

A

1矛盾律

A

A

0蕴涵等值式

A

B

A

B等价等值式

A

B

(A

B)

(B

A)假言易位

A

B

B

A等价否定等值式

A

B

A

B归谬论(A

B)

(A

B)

A41等值演算等值演算:由已知的等值式推演出新的等值式的过程置换规则:若A

B,则

(B)

(A)

例3

证明

p

(q

r)

(p

q)

r证

p

(q

r)

p

(

q

r)（蕴涵等值式）

(

p

q)

r

（结合律）

(p

q)

r

（德摩根律）

(p

q)

r

（蕴涵等值式）42实例等值演算不能直接证明两个公式不等值.证明两个公式不等值的基本思想是找到一个赋值使一个成真,另一个成假.例4证明:p

(q

r)(p

q)

r方法一真值表法（见例2）方法二观察法.容易看出000使左边成真,使右边成假.方法三先用等值演算化简公式,再观察.43实例例5

用等值演算法判断下列公式的类型(1)q

(p

q)

解q

(p

q)

q

(

p

q)（蕴涵等值式）

q

(p

q)（德摩根律）

p

(q

q)（交换律，结合律）

p

0（矛盾律）

0（零律）该式为矛盾式.44实例(续)(2)(p

q)

(

q

p)解(p

q)

(

q

p)

(

p

q)

(q

p)（蕴涵等值式）

(

p

q)

(

p

q)（交换律）

1该式为重言式.45实例(续)(3)((p

q)

(p

q))

r)解((p

q)

(p

q))

r)

(p

(q

q))

r

（分配律）

p

1

r

（排中律）

p

r

（同一律）非重言式的可满足式.如101是它的成真赋值,000是它的成假赋值.总结:A为矛盾式当且仅当A

0;A为重言式当且仅当A

1说明:演算步骤不惟一,应尽量使演算短些46真值函数定义2.12称F:{0,1}n

{0,1}为n元真值函数n元真值函数共有个每一个命题公式对应于一个真值函数每一个真值函数对应无穷多个命题公式1元真值函数

p

0001110101472元真值函数

pq

0000000000010000111110001100111101010101pq

001111111101000011111000110011110101010148联结词完备集定义2.13

设S是一个联结词集合,如果任何n(n

1)元真值函数都可以由仅含S中的联结词构成的公式表示,则称S是联结词完备集定理2.1下述联结词集合都是完备集:(1)S1={

,

,

,

,

}(2)S2={

,

,

,

}(3)S3={

,

,

}(4)S4={

,

}(5)S5={

,

}(6)S6={

,

}A

B(A

B)(B

A)A

B

A

BA

B

(A

B)

(A

B)A

B

(A

B)A

B

(A)B

A

B49复合联结词与非式:p

q(p

q),

称作与非联结词p

q为真当且仅当p,q不同时为真

T

T

T

Fp

q

FF

FT

TF

TT

pqpp

(p

p)

p(pq)(pq)

（p

q)

p

q(pp)(qq)

p

q

p

q50复合联结词或非式:p

q(p

q),

称作或非联结词p

q为真当且仅当p,q不同时为假

T

F

F

Fp

q

FF

FT

TF

TT

pqp

p

(p

p)

p(pq)(pq)

（p

q)

p

q(pp)(qq)

p

q

p

q定理2.2{

},{

}是联结词完备集512.3范式2.3.1析取范式与合取范式简单析取式与简单合取式析取范式与合取范式2.3.2主析取范式与主合取范式极小项与极大项52简单析取式与简单合取式文字:命题变项及其否定的统称简单析取式:有限个文字构成的析取式如p,

q,p

q,p

q

r,…简单合取式:有限个文字构成的合取式如p,

q,p

q,p

q

r,…定理2.3

(1)一个简单析取式是重言式当且仅当它同时含某个命题变项和它的否定(2)一个简单合取式是矛盾式当且仅当它同时含某个命题变项和它的否定例如，简单析取式p

q

p是重言式。简单合取式p

p

q是矛盾式。53析取范式与合取范式析取范式:由有限个简单合取式组成的析取式

A1

A2

Ar,其中A1,A2,,Ar是简单合取式例如,

p

(pq)(p

qr)是析取范式。合取范式:由有限个简单析取式组成的合取式

A1

A2

Ar,其中A1,A2,,Ar是简单析取式例如：(p

q

r)

(

pq)

q是合取范式。范式:析取范式与合取范式的统称

定理2.4

(1)一个析取范式是矛盾式当且仅当它的每一个简单合取式都是矛盾式(2)一个合取范式是重言式当且仅当它的每一个简单析取式都是重言式54范式存在定理定理2.5

任何命题公式都存在着与之等值的析取范式与合取范式.证求公式A的范式的步骤：(1)消去A中的

,

A

B

A

B

A

B

(

A

B)

(A

B)(2)否定联结词

的内移或消去

A

A

(A

B)

A

B

(A

B)

A

B55范式存在定理(续)(3)使用分配律A

(B

C)

(A

B)

(A

C)求合取范式

A

(B

C)

(A

B)

(A

C)求析取范式例1

求

(p

q)

r的析取范式与合取范式解

(p

q)

r

(

p

q)

r

(p

q)

r

析取范式

(p

r)(q

r)合取范式注意:公式的析取范式与合取范式不惟一.56极小项与极大项定义2.17

在含有n个命题变项的简单合取式(简单析取式)中,若每个命题变项和它的否定式不同时出现，而二者之一必出现且仅出现一次，且第i个命题变项或它的否定式出现在从左算起的第i位上(按下标或字母顺序排列),称这样的简单合取式(简单析取式)为极小项(极大项)。说明:(1)

n个命题变项产生2n个极小项和2n个极大项(2)2n个极小项(极大项)均互不等值(3)用mi表示第i个极小项,其中i是该极小项成真赋值的十进制表示.用Mi表示第i个极大项,其中i是该极大项成假赋值的十进制表示,mi(Mi)称为极小项(极大项)的名称.

57极小项与极大项(续)定理2.6设mi与Mi是由同一组命题变项形成的极小项和极大项,则

mi

Mi,

Mi

mi极小项极大项公式成真赋值名称公式成假赋值名称

p

q00m0

p

q00M0

p

q01m1

p

q01M1p

q10m2

p

q10M2

p

q11m3

p

q11M3p,q形成的极小项与极大项58主析取范式与主合取范式主析取范式:由极小项构成的析取范式主合取范式:由极大项构成的合取范式例如，n=3,命题变项为p,q,r时，(

p

q

r)

(

p

q

r)

m1

m3

是主析取范式

(p

q

r)

(

p

q

r)

M1

M5

是主合取范式定理2.7任何命题公式都存在着与之等值的主析取范式和主合取范式,并且是惟一的.59求主析取范式的步骤设公式A含命题变项p1,p2,…,pn(1)求A的析取范式A

=B1

B2

…

Bs，其中Bj

是简单合取式j=1,2,…,s

(2)若某个Bj

既不含pi，又不含

pi，则将Bj

展开成

Bj

Bj

(pi

pi)(Bj

pi)(Bj

pi)重复这个过程,直到所有简单合取式都是长度为n的极小项为止(3)消去重复出现的极小项,即用mi代替mi

mi(4)将极小项按下标从小到大排列60求主合取范式的步骤设公式A含命题变项p1,p2,…,pn(1)求A的合取范式A

=B1

B2

…

Bs,其中Bj

是简单析取式j=1,2,…,s

(2)若某个Bj

既不含pi，又不含

pi

，则将Bj

展开成

Bj

Bj

(pi

pi)(Bj

pi)(Bj

pi)重复这个过程,直到所有简单析取式都是长度为n的极大项为止(3)消去重复出现的极大项,即用Mi代替Mi

Mi(4)将极大项按下标从小到大排列61实例例1(续)

求

(p

q)

r的主析取范式与主合取范式解(1)

(p

q)

r

(p

q)

r

p

q

(p

q)1同一律

(p

q)(r

r)排中律

(p

q

r)

(p

q

r)分配律

m4

m5

r

(p

p)(q

q)

r

同一律,排中律

(p

q

r)(p

q

r)(p

q

r)(p

q

r)

m0

m2

m4

m6

分配律得

(p

q)

r

m0

m2

m4

m5

m6可记作

(0,2,4,5,6)62实例(续)(2)

(p

q)

r

(p

r)(q

r)

p

r

p0r

同一律

p(q

q)r矛盾律(p

q

r)(p

q

r)

分配律

M1

M3

q

r

(p

p)q

r

同一律,矛盾律(p

q

r)

(

p

q

r)分配律

M3

M7得

(p

q)

r

M1

M3

M7可记作

(1,3,7)63快速求法设公式含有n个命题变项,则长度为k的简单合取式可展开成2n

k个极小项的析取例如公式含p,q,r

q

(p

q

r)(p

q

r)(p

q

r)(p

q

r)

m2

m3

m6

m7长度为k的简单析取式可展开成2n

k个极大项的合取例如p

r

(p

q

r)(p

q

r)

M1

M364实例例2(1)求A(p

q)(p

q

r)

r

的主析取范式解用快速求法(1)

p

q

(

p

q

r)

(

p

q

r)

m2

m3

p

q

r

m1r

(

p

q

r)

(

p

q

r)

(p

q

r)

(p

q

r)

m1

m3

m5

m7得A

m1

m2

m3

m5

m7

(1,2,3,5,7)65实例(续)(2)求B

p(p

q

r)的主合取范式解

p

(

p

q

r)(

p

q

r)

(

p

q

r)

(

p

q

r)

M4

M5

M6

M7p

q

r

M1得B

M1

M4

M5

M6

M7

(1,4,5,6,7)66主析取范式的用途(1)求公式的成真赋值和成假赋值设公式A含n个命题变项,A的主析取范式有s个极小项,则A有s个成真赋值,它们是极小项下标的二进制表示,其余2n

s

个赋值都是成假赋值例如

(p

q)

r

m0

m2

m4

m5

m6

成真赋值:000,010,100,101,110;成假赋值:001,011,11167主析取范式的用途(续)(2)判断公式的类型

设A含n个命题变项，则

A为重言式当且仅当A的主析取范式含2n个极小项A为矛盾式当且仅当

A的主析取范式不含任何极小项,记作0A为可满足式当且仅当A的主析取范式中至少含一个极小项68实例例3用主析取范式判断公式的类型:(1)A

(p

q)

q

(2)B

p(p

q)(3)C(p

q)r解(1)A

(

p

q)

q

(p

q)

q0矛盾式(2)B

p(p

q)1m0

m1

m2

m3

重言式(3)C

(p

q)r

(p

q)r

(p

q

r)(p

q

r)(p

q

r)(p

q

r)(p

q

r)(p

q

r)

m0

m1

m3

m5

m7

非重言式的可满足式69主析取范式的用途(续)(3)判断两个公式是否等值例4用主析取范式判断下面2组公式是否等值:(1)p与(p

q)(p

q)解p

p(q

q)(p

q)(p

q)

m2

m3(p

q)(p

q)(p

q)(p

q)

(p

q)(p

q)

m2

m3故p

(p

q)(p

q)70实例(续)(2)(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)

m1

m3

m5

m6

m7p(q

r)(p

q)(p

r)(p

q

r)(p

q

r)(p

q

r)(p

q

r)

m5

m6

m7故(p

q)r

p(q

r)71实例例5某单位要从A,B,C三人选派若干人出国考察,需满足下述条件:(1)若A去,则C必须去;(2)若B去,则C不能去;(3)A和B必须去一人且只能去一人.问有几种可能的选派方案?解记p:派A去,q:派B去,r:派C去(1)p

r,(2)q

r,(3)(p

q)

(

p

q)求下式的成真赋值A=(p

r)

(q

r)

((p

q)

(

p

q))72实例(续)求A的主析取范式A=(p

r)

(q

r)

((p

q)

(

p

q))

(

p

r)

(

q

r)

((p

q)

(

p

q))((

p

q)

(

p

r)

(r

q)

(r

r))

((p

q)

(

p

q))((

p

q)

(p

q))((

p

r)

(p

q))

((r

q)

(p

q))

((

p

q)

(

p

q))((

p

r)

(

p

q))((r

q)

(

p

q))

(p

q

r)(p

q

r)成真赋值:101,010结论:方案1派A与C去,方案2派B去73主合取范式由主析取范式求主合取范式设没有出现的极小项是其中t=2n

s,于是74主合取范式(续)例6求A=(p

q

r)(p

q

r)(p

q

r)的主合取范式解A

m1

m3

m7

M0

M2

M4

M5

M6矛盾式的主合取范式含全部2n个极大项重言式的主合取范式不含任何极大项,记作175pqr000001010011100

101110111p

（q

r)

00001011p

（q

r)(4,6,7)

（主析取范式）

(0,1,2,3,5)（主合取范式）已知真值表，写出主范式。例题762.4命题逻辑推理理论2.4.1推理的形式结构推理的前提与结论,正确推理推理定律2.4.2自然推理系统P推理规则直接证明法,附加前提证明法,归谬法(反证法),归结证明法77有效推理定义2.20若对于每组赋值,A1ÙA2Ù…Ù

Ak

为假,或者当A1ÙA2Ù…ÙAk为真时,B也为真,则称由前提A1,A2,…,Ak推B的推理有效或推理正确,并称B是有效的结论定理2.8由前提A1,A2,…,Ak

推出B的推理正确当且仅当

A1ÙA2Ù…ÙAk®B为重言式.78推理的形式结构形式(1)

A1ÙA2Ù…ÙAk®B形式(2)前提:A1,A2,…,Ak

结论:B

推理正确记作A1ÙA2Ù…ÙAkÞB判断推理是否正确的方法:真值表法等值演算法主析取范式法构造证明法79实例例1判断下面推理是否正确:(1)若今天是1号,则明天是5号.今天是1号.所以明天是5号.解设p:今天是1号,q:明天是5号推理的形式结构为(p®q)Ùp®q证明用等值演算法(p®q)Ùp®q

Û

Ø((ØpÚq)Ùp)ÚqÛ((pÙØq)ÚØp)ÚqÛ((pÚØp)Ù(ØqÚØp))ÚqÛ(1Ù(ØqÚØp))ÚqÛ

ØpÚ

(ØqÚq)Û1得证推理正确80实例(续)(2)若今天是1号,则明天是5号.明天是5号.所以今天是1号.解设p:今天是1号,q:明天是5号.推理的形式结构为(p®q)Ùq®p证明用主析取范式法(p®q)Ùq®p

Û(ØpÚq)Ùq®p

Û

q®p

Û

ØqÚp

Û(ØpÙØq)Ú(pÙØq)Ú(pÙØq)Ú(pÙq)

Û

m0Úm2Úm301是成假赋值,所以推理不正确.81推理定律——重言蕴涵式

A

Þ(AÚB)附加律(AÙB)Þ

A

化简律(A®B)ÙA

Þ

B

假言推理(A®B)ÙØB

Þ

ØA

拒取式(AÚB)ÙØB

Þ

A

析取三段论(A®B)Ù(B®C)Þ(A®C)假言三段论(A«B)Ù(B«C)Þ(A«C)等价三段论(A®B)Ù(C®D)Ù(AÚC)Þ(BÚD)构造性二难(A®B)Ù(ØA®B)Ù(AÚØA)Þ

B

构造性二难(特殊形式)(A®B)Ù(C®D)Ù(ØBÚØD)Þ(ØAÚØC)破坏性二难82自然推理系统P自然推理系统P由下述3部分组成:1.字母表(1)命题变项符号:p,q,r,…,pi,qi

,ri

,…(2)联结词:

,

,,,(3)括号与逗号:()，,2.合式公式3.推理规则(1)前提引入规则(2)结论引入规则(3)置换规则83自然推理系统P(续)(7)拒取式规则

A®B

ØB

\ØA(8)假言三段论规则

A®B

B®C

\A®C

(4)假言推理规则

A®BA

\B(5)附加规则

A

\AÚB(6)化简规则

AÙB

\A

84自然推理系统P(续)(11)破坏性二难推理规则

A®B

C®D

ØBÚØD

\ØAÚØC(12)合取引入规则

A

B

\AÙB

(9)析取三段论规则

AÚB

ØB

\A(10)构造性二难推理规则

A®B

C®D

AÚC

\BÚD85直接证明法例2在自然推理系统P中构造下面推理的证明:前提:

pÚq,q®r,p®s,Øs结论:rÙ(pÚq)证明①

p®s前提引入

②Øs

前提引入

③

Øp

①②拒取式

④

pÚq

前提引入

⑤q

③④析取三段论

⑥q®r

前提引入

⑦r

⑤⑥假言推理

⑧rÙ(pÚq)

⑦④合取推理正确,rÙ(pÚq)是有效结论86实例例3构造推理的证明:若明天是星期一或星期三,我就有课.若有课,今天必须备课.我今天下午没备课.所以,明天不是星期一和星期三.解设p:明天是星期一,q:明天是星期三，

r:我有课，s:我备课前提:(pÚq)®r,r®s,Øs结论:ØpÙØq

87实例(续)前提:(pÚq)®r,r®s,Øs结论:ØpÙØq

证明①r®s

前提引入②Øs

前提引入③Ør①②拒取式④(pÚq)®r

前提引入⑤Ø(pÚq)③④拒取式⑥ØpÙØq⑤置换结论有效,即明天不是星期一和星期三88附加前提证明法欲证明等价地证明前提:A1,A2,…,Ak

前提:A1,A2,…,Ak

,C结论:C®B结论:B理由:(A1ÙA2Ù…ÙAk)®(C®B)

Û

Ø(A1ÙA2Ù…ÙAk)Ú(ØCÚB)

Û

Ø(A1ÙA2Ù…ÙAkÙC)ÚB

Û(A1ÙA2Ù…ÙAkÙC)®B89实例例4构造下面推理的证明:前提:Øp

Úq,Ø