命题逻辑课件

命题逻辑ppt课件命题逻辑ppt课件命题逻辑ppt课件命题逻辑2第2章命题逻辑2.1命题及其表示2.2命题公式2.3命题公式间的关系2.4主范式与判定定理2.5命题逻辑的推理理论3命题逻辑ppt课件命题逻辑ppt课件命题逻辑ppt课件命题逻辑课件命题逻辑课件命题逻辑课件命题逻辑课件

例

下列句子中那些是命题？

(1)是无理数.(2)2+5＝8.(3)x+5＞3.(4)你有铅笔吗？(5)这只兔子跑得真快呀！(6)请不要讲话！(7)我正在说谎话.真命题假命题真值不确定疑问句感叹句祈使句悖论(3)~(7)都不是命题6例下列句子理发师悖论

某乡村有一位理发师，一天他宣布：只给不自己理发的人理发。这里就产生了问题：理发师给不给自己理发？如果他给自己理发，他就是自己理发的人，按照他的原则，他不能给自己理发；如果他不给自己理发，他就是不自己理发的人，按照他的原则，他就应该给自己理发。这就产生了矛盾。

7理发师悖论某乡村有一位理发师，一天他宣布：只给不自己理发的命题的分类

简单命题(原子命题)：简单陈述句构成的命题

复合命题：由简单命题用联结词联结而成的命题

8命题的分类简单命题(原子命题)：8简单命题符号化

在本书中用小写英文字母p,q,r,…,pi,qi,ri(i≥1）表示简单命题，将表示命题的符号放在该命题的前面，称为命题符号化。用“1”表示真，用“0”表示假对简单命题而言，它的真值是确定的，因而又称为命题常项或命题常元。例如，令p：是有理数，则p的真值为0q：2+5=7，则q的真值为1

见课本例1.29简单命题符号化在本书中用小写英文字母p,q,r,…联结词与复合命题

1.否定式与否定联结词“

”

定义2.1

设p为任一命题，复合命题“非p”（或“p的否定”）称为p的否定式，记作

p，符号

称作否定联结词，并规定

p

为真当且仅当（即：等价）p为假2.合取式与合取联结词“∧”

定义

2.2设p,q为两命题,复合命题“p并且q”(或“p与q”)称为p与q的合取式，记作p∧q，∧称作合取联结词，并规定p∧q为真当且仅当p与q同时为真注意：描述合取式的灵活性与多样性分清简单命题与复合命题10联结词与复合命题1.否定式与否定联结词“”10

例

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

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

令

p：王晓用功，q：王晓聪明，则(1)p∧q(2)p∧q(3)p∧

q.11例将下列命题符号化.

例(续)

(4)(p)∧

q.令

r:张辉是三好学生，s:王丽是三好学生(5)r∧s.(6)令

t:张辉与王丽是同学，t是简单命题.说明:(1)~(4)说明描述合取式的灵活性与多样性.(5)中“与”联结的是句子的主语成分，因而(5)中句子是简单命题.12例(续)(4)(p)∧q.说联结词与复合命题(续)

定义2.3设p,q为二命题，复合命题“p或q”称作p与q的析取式，记作p∨q，∨称作析取联结词，并规定p∨q为假当且仅当p与q同时为假.

即:p∨q为真当且仅当p与q至少有一个为真。此处定义的析取式p∨q表示的是一种相容性或，即允许p与q同时为真注意区分自然言语中“或”的二义性。见课本描述。例

将下列命题符号化(1)2或4是素数.(2)2或3是素数.(3)4或6是素数.(4)小元元只能拿一个苹果或一个梨.(5)王晓红生于1975年或1976年.

3.析取式与析取联结词“∨”13联结词与复合命题(续)定义2.3设p,q为二命题，复解

令p:2是素数,q:3是素数,r:4是素数,s:6是素数,则(1),(2),(3)均为相容或.分别符号化为:p∨r,p∨q,r∨s,

它们的真值分别为1,1,0.

而(4),(5)为排斥或.

令t:小元元拿一个苹果，u:小元元拿一个梨，则(4)符号化为(t∧

u)∨(

t∧u).

令v:王晓红生于1975年,w:王晓红生于1976年,则(5)既可符号化为(v∧

w)∨(

v∧w),又可符号化为v∨w,为什么?

（看v∧w的值是多少？）14解令p:2是素数,q:3是素数,r:4是素数,s:联结词与复合命题(续)

定义2.4设p,q为二命题，复合命题“如果p,则q”称作p与q的蕴涵式，记作p

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

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

q为假当且仅当p为真q为假.4.蕴涵式与蕴涵联结词“

”15联结词与复合命题(续)定义2.4设p,q为二命题，p

q的逻辑关系：q为p的必要条件或p为q的充分条件（找

关系时，要分清蕴涵式的前件与后件，即找准充分条件或必要条件）“如果p，则q”的不同表述法很多：若p，就q（p是q的充分条件）只要p，就q（p是q的充分条件）p仅当q（q是p的必要条件）只有q

才p（q是p的必要条件）

除非q,才p或除非q,否则非p，(必须记住)否则非可以理解为才当p为假时，p

q为真常出现的错误：不分充分与必要条件见课本中注意的两点事项联结词与复合命题(续)16pq的逻辑关系：q为p的必要条件或p为q的充分条件联结

例

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

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

p

q与

q

p

等值（真值相同）p

qp

qp

qp

qq

p

q

pq

pq

p17例设p:天冷，q:小王穿联结词与复合命题(续)定义2.5设p，q为二命题，复合命题“p当且仅当q”称作p与q的等价式，记作p

q，

称作等价联结词.

p

q为真当且仅当p与q同时为真或同时为假.说明:(1)p

q的逻辑关系:p与q互为充分必要条件(2)p

q为真当且仅当p与q同真或同假5.等价式与等价联结词“

”18联结词与复合命题(续)定义2.5设p，q为二命题，复合命题例

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

f(x)在x0

可导的充要条件是它在

x0连续.它们的真值分别为1，0，1，0，0.19例求下列复合命题的真值19用联结词把各种各样的复合命题符号化基本步骤：1：分析出各简单命题，将它们符号化；2：使用合适的联结词，把简单命题逐个联结起来，组成复合命题的符号化表示。注意析取联结词∨的应用20用联结词把各种各样的复合命题符号化基本步骤：20联结词与复合命题(续)以上给出了5个联结词：

,

,

,

,

，组成一个联结词集合{

,

,

,

,

}，

联结词的优先顺序为：

,

,

,

,;

1:如果出现的联结词同级，又无括号时，则按从左到右的顺序运算;

2:若遇有括号时，应该先进行括号中的运算.

注意:本书中使用的

括号全为圆括号（）.

21联结词与复合命题(续)以上给出了5个联结词：,,,2.2命题公式命题变项与合式公式公式的赋值真值表命题的分类重言式矛盾式可满足式222.2命题公式22命题变项与合式公式

命题常项：简单命题原子命题命题变项：真值不确定的陈述句定义2.6

合式公式(命题公式,公式)递归定义如下：(1)单个命题常项或变项p,q,r,…,pi,qi,ri,…,0,1是合式公式；(2)若A是合式公式，则(

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

B),(A

B),(A

B),(A

B)也是合式公式；(4)只有有限次地应用(1)~(3)形成的符号串才是合式公式。注:外层括号可以省去

问：命题公式是命题吗？不是，原因为：命题公式中可能含有命题变项。23命题变项与合式公式命题常项：简单命题原子命题23合式公式的层次

定义

2.7(1)若公式A是单个的命题(常项或变项）,则称A为0层公式.(2)称A是n+1(n≥0)层公式是指下面情况之一：(a)A=

B,B是n层公式；(b)A=B

C,其中B,C分别为i层和j层公式，且n=max(i,j)；(c)A=B

C,其中B,C的层次及n同(b)；(d)A=B

C,其中B,C的层次及n同(b)；(e)A=B

C,其中B,C的层次及n同(b).(3)若A的最高层次为k.则A是k层公式。24合式公式的层次定义2.724合式公式的层次(续)例如公式p0层

p1层

p

q2层

(p

q)

r3层

((

p

q)

r)

(

r

s)4层25合式公式的层次(续)例如公式25公式的赋值

定义2.8

给命题公式A中的所有的命题变项p1,p2,…,pn指定一组真值称为对A的一个赋值或解释成真赋值:使公式为真的赋值成假赋值:使公式为假的赋值说明：

赋值

=

1

2…

n之间不加标点符号，

i=0或1.

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…

含n个变项的公式有2n个赋值.

26公式的赋值定义2.826真值表

真值表:将命题公式A在所有赋值之下取值的情况列成表，成为A的真值表

例给出公式的真值表A=(q

p)

q

p的真值表pqq

p

(q

p)

q

(q

p)

q

p

00011011

1011

0001

111127真值表真值表:将命题公式A在所有赋值之下取值的情况列成例B=(

p

q)

q的真值表pq

p

p

q

(

p

q)

(

p

q)

q00011011

1100110100100000实例28例B=(pq)q的真值表p例C=(p

q)

r的真值表pqrp

q

r

(p

q)

r

000001010011100101110111

00111111

10101010

1110101029例C=(pq)r的真值表pq公式的类型

定义2.9设A为一个命题公式(1)若A在它的各种赋值下取值均为真，则称A为重言式(也称永真式)(2)若A在它的各种赋值下取值均为假，则称A为矛盾式(也称永假式)(3)若A至少存在一组赋值是成真赋值，则称A为可满足式注意：重言式是可满足式，但反之不真.上例中A为重言式，B为矛盾式，C为可满足式

A=(q

p)

q

p，B=(

p

q)

q，C=(p

q)

r30公式的类型定义2.9设A为一个命题公式30小结：本节主要内容：要理解所学的定义，利用所给的定义进行简单的判断和分析。1：命题命题常项命题变项简单命题复合命题的定义。2：联结词：

,

,

,

,定义取值情况，对应的语言词汇表达。3：命题公式层次成真赋值成假赋值真值表的定义4：构造真值表的具体步骤，重言式矛盾式可满足式定义31小结：本节主要内容：31上节知识复习1:定义：命题真(假)命题命题常(变)项2:五个联结词定义及取值情况，对应的语言表达3:复合命题符号化的步骤4:命题公式命题公式的层次定义及判断5:成真赋值成假赋值重言式矛盾式可满足式定义6:真值表定义及构造步骤32上节知识复习1:定义：命题真(假)命题命题常(变)项3随堂练习1：写出命题、简单命题的定义。2：用符号定义五个联结词及其各自取值情况。3：写出蕴涵式的定义，分析前件与后件的关系，列出对应的语言表达形式。4：写出遇到析取联结词二义性时的判断方式及对应符号表示。5：列出下面公式的真值表，说明各公式的层次(p

q)((p

q)

(q

p))(p

q)

(p

q)6：写出命题公式的定义33随堂练习1：写出命题、简单命题的定义。33随堂练习7：命题符号化：a:只有天冷,小王才穿羽绒服.b:除非天冷,小王才穿羽绒服.c:除非小王穿羽绒服,否则天不冷.d:如果天不冷,则小王不穿羽绒服.e:小王穿羽绒服仅当天冷的时候.f:只有4是偶数，3才能被2整除。g:选小王或小李中的一人当三好学生。h:小王现在在宿舍或在图书馆里。34随堂练习7：命题符号化：342.3命题公式间的关系

学习目标：等值式基本等值式等值演算置换规则352.3命题公式间的关系学习目标：35等值式

定义设A、B为两命题，若等价式A

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

B，并称A

B是等值式说明：定义中符号“”不是联结词符，它只是当A与B等值时的一种记法。注意区分“”、“=”和“

”可以用真值表验证两个公式是否等值等价关系具有自反性、对称性、传递性。请验证：p

(q

r)

(p

q)

rp

(q

r)(p

q)

r

36等值式定义设A、B为两命题，若等价式AB是重言式，则称

用真值表法的验证方式设A、B为两命题，由定义判断A与B是否等值，应判断A

B是否为重言式，若A

B的真值表最后一列全为1，则A

B为重言式，因而A

B，但最后一列全为1当且仅当在各赋值之下，A与B的真值相同。因而判断A与B是否等值等价于判断A、B的真值表是否相同。37用真值表法的验证方式设A、B为两命题，由定义判断A与B是基本等值式利用真值表法可以验证很多等值式：下面24个重要的等值式，是学好数理逻辑的关键基础，应当牢记！在下面的公式中，A、B、C代表任意的命题公式。38基本等值式利用真值表法可以验证很多等值式：38基本等值式

双重否定律

:1.

A

A等幂律：2.A

A

A,3.A

A

A交换律:4.A

B

B

A,5.A

B

B

A结合律:6.(A

B)

C

A

(B

C)7.(A

B)

C

A

(B

C)分配律:8.A

(B

C)

(A

B)

(A

C)9.A

(B

C)

(A

B)

(A

C)39基本等值式双重否定律:1.AA39基本等值式(续)德·摩根律

:10.

(A

B)

A

B11.

(A

B)

A

B吸收律:12.A

(A

B)

A,13.A

(A

B)

A零律:14.A

1

1,15.A

0

0同一律:16.A

0

A,17.A

1

A排中律:18.A

A

1矛盾律:19.A

A

040基本等值式(续)德·摩根律:10.(AB)A基本等值式(续)蕴涵等值式:20.A

B

A

B等价等值式:21.A

B

(A

B)

(B

A)假言易位:22.A

B

B

A等价否定等值式:23.A

B

A

B归谬论:24.(A

B)

(A

B)

A注意:A,B,C代表任意的命题公式牢记这些等值式是继续学习的基础41基本等值式(续)蕴涵等值式:20.AB等值演算与置换规则

等值演算:由已知的等值式推演出新的等值式的过程置换定理：设

(A)是含命题公式A的命题，

若A

B,则

(B)

(A)

等值演算的基础：

(1)等值关系的性质：自反、对称、传递(2)基本的等值式(3)置换规则42等值演算与置换规则等值演算:42应用举例——证明两个公式等值

例1证明p

(q

r)

(p

q)

r证p

(q

r)

p

(

q

r)（蕴涵等值式）

(

p

q)

r（结合律）

(p

q)

r（德摩根律）

(p

q)

r（蕴涵等值式）

说明:也可以从右边开始演算（请做一遍）因为每一步都用置换规则，故省略不写熟练后，基本等值式也可以不写出

43应用举例——证明两个公式等值例1证明p(qr)应用举例——证明两个公式不等值例2证明:p

(q

r)(p

q)

r用等值演算不能直接证明两个公式不等值,证明两个公式不等值的基本思想是找到一个赋值使一个成真,另一个成假.方法一真值表法（自己证）方法二观察赋值法.容易看出000,010等是左边的成真赋值，是右边的成假赋值.方法三用等值演算先化简两个公式，再观察.44应用举例——证明两个公式不等值例2证明:p(qr)应用举例——判断公式类型

例3

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

(p

q)

解q

(p

q)

q

(

p

q)（蕴涵等值式）

q

(p

q)（德摩根律）

p

(q

q)（交换律，结合律）

p

0（矛盾律）

0（零律）由最后一步可知，该式为矛盾式.

45应用举例——判断公式类型例3用等值演算法判断下列公式的类例3(续)(2)(p

q)

(

q

p)解(p

q)

(

q

p)

(

p

q)

(q

p)（蕴涵等值式）

(

p

q)

(

p

q)（交换律）

1由最后一步可知，该式为重言式.问：最后一步为什么等值于1？

46例3(续)(2)(pq)(qp)例3(续)(3)((p

q)

(p

q))

r)解((p

q)

(p

q))

r)

(p

(q

q))

r（分配律）

p

1

r（排中律）

p

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

0A为重言式当且仅当A

1说明：演算步骤不惟一,应尽量使演算短些47例3(续)(3)((pq)(pq))r)本节小结熟悉等值、等值演算的定义会用真值表法判断等值记熟会用24个重要的等值式48本节小结熟悉等值、等值演算的定义482.4主范式与判定为题

学习目标：析取范式与合取范式

主析取范式与主合取范式

492.4主范式与判定为题学习目标：49析取范式与合取范式

简单析取式:仅由有限个命题变项或其否定构成的析取式称为简单析取式。如p,

q,p

q,p

q

r,…简单合取式:仅由有限个命题变项或其否定构成的合取式称为简单合取式。如p,

q,p

q,p

q

r,…由定义可知：1:一个简单析取式是重言式，当且仅当它同时含一个命题变项及其否定。2:一个简单合取式是矛盾式，当且仅当它同时含一个命题变项及其否定。50析取范式与合取范式简单析取式:仅由有限个命题变项或其否定构析取范式与合取范式(续)析取范式:仅由有限个简单合取式组成的析取式称为析取范式。

A=A1

A2

Ar,其中A1,A2,,Ar是简单合取式。A是析取范式。合取范式:仅由有限个简单析取式组成的合取式称为合取范式。

A=A1

A2

Ar,其中A1,A2,,Ar是简单析取式。A是合取范式。显然：任何析取范式的对偶式为合取范式，任何合取范式的对偶式为析取范式，51析取范式与合取范式(续)析取范式:仅由有限个简单合取式组成析取范式与合取范式(续)析取范式与合取范式有下列性质：1：一个析取范式是矛盾式，当且仅当它的每个简单合取式都是矛盾式。2：一个合取范式是重言式，当且仅当它的每个简单析取式都是重言。52析取范式与合取范式(续)析取范式与合取范式有下列性质：52析取范式与合取范式(续)范式:析取范式与合取范式的总称

公式A的析取范式:与A等值的析取范式公式A的合取范式:与A等值的合取范式说明：

单个命题变项及其否定既是简单析取式，又是简单合取式形如p

q

r,

p

q

r的公式既是析取范式，又是合取范式(为什么?)

53析取范式与合取范式(续)范式:析取范式与合取范式的总称

53命题公式的范式

定理（范式存在定理）任何命题公式都存在着与之等值的析取范式和合取范式.求公式A的范式的步骤：(1)由于{,,}是全功能集，因而若A中含联结词,

,,,等，可用基本的等值式及置换规则将这些联结词消去。(2)否定联结词

的内移或消去(3)使用分配律

对

分配（求析取范式）

对

分配（求合取范式）公式的范式存在，但不惟一，这是它的局限性

54命题公式的范式定理（范式存在定理）任何命题公式都存在求公式的范式举例

例

求下列公式的析取范式与合取范式(1)A=(p

q)

r解(p

q)

r

(

p

q)

r

（消去

）

p

q

r

（结合律）这既是A的析取范式（由3个简单合取式组成的析取式），又是A的合取范式（由一个简单析取式组成的合取式）55求公式的范式举例例求下列公式的析取范式与合取范式55求公式的范式举例(续)(2)B=(p

q)

r解

(p

q)

r

(

p

q)

r

（消去第一个

）

(

p

q)

r

（消去第二个

）

(p

q)

r

（否定号内移——德摩根律）这一步已为析取范式（两个简单合取式构成）继续：(p

q)

r

(p

r)

(q

r)（

对

分配律）这一步得到合取范式（由两个简单析取式构成）

56求公式的范式举例(续)(2)B=(pq)r56极小项定义

在含n个命题变项的简单合取式中，若每个命题变项与其否定不同时存在，而两者之一必出现且仅出现一次，且第i（1

i

n）个命题变项或其否定出现在从左起的第i位上（若命题变项无角标，则按字典顺序排序），称这样的简单合取式为极小项.说明：n个命题变项产生2n个极小项。2n个极小项均互不等值用mi表示第i个极小项，将mi里的命题变项看成1，命题变项的否定看成0，则每个极小项对应一个二进制数，也对应一个十进制数。二进制数正是该极小项的成真赋值，十进制数i是该极小项成真赋值的十进制表示也是该极小项抽象表示法的角码.57极小项定义在含n个命题变项的简单合取式中，若每个命题变公式

成真赋值名称

p

q

r

p

q

r

p

q

r

p

q

rp

q

rp

q

rp

q

rp

q

r000001010011100101110111m0m1m2m3m4m5m6m7极小项

由p,q,r三个命题变项形成的极小项58公式成真名称pqr000m0极小项由知识回顾1:定义：排斥或与非式或非式全功能集冗余的（独立的）联结词2:对偶式对偶原理简单合取式简单析取式析取范式与合取范式极小项3:求公式A的范式的步骤59知识回顾1:定义：排斥或与非式或非式全功能集冗余的（主析取范式定义：主析取范式:设命题公式A中含n个命题变项，如果A的析取范式中的简单合取式全是极小项，则称该析取范式为A的主析取范式例如，n=3,命题变项为p,q,r时，(

p

q

r)

(

p

q

r)

m1

m3

是主析取范式

A的主析取范式:与A等值的主析取范式60主析取范式定义：主析取范式:设命题公式A中含n个命题变项，主析取范式(续)定理2.5任何命题公式的主析取范式都是存在的,并且是惟一的.

用等值演算法求给定命题公式的主析取范式的步骤：(1)先求A的析取范式A’。

(2)若A’的某简单合取式B中不含命题变项pi,也不含否定

pi，则将B展成如下形式B

B

1

B

(pi

pi)(

B

pi)(B

pi)(3)将重复出现的命题变项、矛盾式及重复出现的极小项都“消去”，如p

p用p取代，p

p用0取代，mi

mi用mi取代。

(4)将极小项按由小到大的顺序排序.并用∑表示，如m1

m2

m5用∑(1,2,5)表示。61主析取范式(续)定理2.5任何命题公式的主析取范式都是存主析取范式用途1：判断两命题公式是否等值由于任何命题公式的主析取范式都是唯一的，因而若A

B，说明A与B有相同的主析取范式。反之，若A与B有相同的主析取范式，必有A

B。2：判断命题公式的类型设A是含n个命题变项的命题公式，A为重言式，当且仅当A的主析取范式中含全部2n个极小项。A为矛盾式，当且仅当A的主析取范式中不含任何极小项。若A的主析取范式中至少含一个极小项，则A是可满足式。3：求命题公式的成真和成假赋值。62主析取范式用途1：判断两命题公式是否等值62极大项定义

在含有n个命题变项的简单析取式中，若每个命题变项与其否定不同时存在，而两者之一必出现且仅出现一次，且第i（1

i

n）个命题变项或其否定出现在从左起的第i位上，称这样的简单析取式为极大项.说明：n个命题变项产生2n个极大项。2n个极大项均互不等值用Mi表示第i个极大项，将Mi里的命题变项看成0，命题变项的否定看成1，则每个极大项对应一个二进制数，也对应一个十进制数。二进制数正是该极大项的成假赋值，十进制数i是该极大项成真赋值的十进制表示也是该极大项抽象表示法的角码.63极大项定义在含有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

000001010011100101110111M0M1M2M3M4M5M6M7

极大项

64由p,q,r三个命题变项形成的极大项公式成假名称p知识回顾掌握对偶式定义对偶原理定理1.2简单合取式、简单析取式、析取范式、合取范式、主析取范式、主合取范式定义主析取范式、主合取范式的求法、表示意义、与真值表之间的转化方式极小项、极大项定义、二进制的成真赋值（成假赋值）与对应的十进制角标关系65知识回顾掌握对偶式定义对偶原理定理1.265极小项与极大项注意：mi(Mi)称为极小项(极大项)的名称.

mi与Mi的关系:

mi

Mi,

Mi

mi

（结合定理1.2理解）记忆理解极小项与极大项的定义、取值、用法时，重点记忆一个，另一个利用上述关系式推导即可66极小项与极大项注意：66极小项与极大项(续)由p,q两个命题变项形成的极小项与极大项

公式

成真赋值名称

公式

成假赋值名称

p

q

p

qp

qp

q00011011m0m1m2m3

p

q

p

q

p

q

p

q

00011011

M0M1M2M3

极小项

极大项

67极小项与极大项(续)由p,q两个命题变项形成的极小项与极大主合取范式定义：主合取范式:设命题公式A中含n个命题变项，如果A的合取范式中的简单析取式全是极大项，则称该合取范式为A的主合取范式例如，n=3,命题变项为p,q,r时，(p

q

r)

(

p

q

r)

M1

M5

是主合取范式

A的主合取范式:与A等值的主合取范式68主合取范式定义：主合取范式:设命题公式A中含n个命题变项，主合取范式（续）任意命题公式的主合取范式一定存在，且是唯一的。求一命题公式A的主合取范式与求主析取范式的步骤非常相似，也是先求出合取范式A’。若A’的某简单析取式B中不含命题变项pi,，

也不含否定

pi，则将B展成如下形式：B

B0

B

(pi

pi)(B

pi)(B

pi)69主合取范式（续）任意命题公式的主合取范式一定存在，且是唯一的主合取范式(续)由A的主析取范式求主合取范式的步骤为：(1):求出A的主析取范式中没包含的极小项

(2):求出与(1)中极小项角码相同的极大项(3):由以上极大项构成的合取式为A的主合取式。70主合取范式(续)由A的主析取范式求主合取范式的步骤为：70求公式的主范式例

求公式

A=(p

q)

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

(p

q)

r

(p

q)

r,（析取范式）

①(p

q)

(p

q)

(

r

r)

(p

q

r)

(p

q

r)

m6

m7,②71求公式的主范式例求公式A=(pq)r的主析取范式与求公式的主范式(续)r

(

p

p)

(

q

q)

r

(

p

q

r)

(

p

q

r)

(p

q

r)

(p

q

r)

m1

m3

m5

m7

③②,③代入①并排序，得(p

q)

r

m1

m3

m5

m6

m7（主析取范式）

72求公式的主范式(续)r72求公式的主范式(续)(2)求A的主合取范式

(p

q)

r

(p

r)

(q

r),（合取范式）

①

p

r

p

(q

q)

r

(p

q

r)

(p

q

r)

M0

M2,

②73求公式的主范式(续)(2)求A的主合取范式73求公式的主范式(续)

q

r

(p

p)

q

r

(p

q

r)

(

p

q

r)

M0

M4③

②,③代入①并排序，得(p

q)

r

M0

M2

M4（主合取范式）

74求公式的主范式(续)qr74主范式的用途——与真值表相同

(1)求公式的成真赋值和成假赋值

例如(p

q)

r

m1

m3

m5

m6

m7，其成真赋值为001,011,101,110,111，其余的赋值000,010,100为成假赋值.

类似地，由主合取范式也可立即求出成假赋值和成真赋值.75主范式的用途——与真值表相同(1)求公式的成真赋值和成主范式的用途(续)(2)判断公式的类型

设A含n个命题变项，则

A为重言式

A的主析取范式含2n个极小项

A的主合取范式为1.A为矛盾式

A的主析取范式为0

A的主合析取范式含2n个极大项A为非重言式的可满足式

A的主析取范式中至少含一个且不含全部极小项

A的主合取范式中至少含一个且不含全部极大项

76主范式的用途(续)(2)判断公式的类型76主范式的用途(续)例

用主析取范式判断下述两个公式是否等值：⑴

p

(q

r)与(p

q)

r⑵

p

(q

r)与(p

q)

r解

p

(q

r)=m0

m1

m2

m3

m4

m5

m7

(p

q)

r=m0

m1

m2

m3

m4

m5

m7(p

q)

r=m1

m3

m4

m5

m7显见，⑴中的两公式等值，而⑵的不等值.

(3)判断两个公式是否等值说明：由公式A的主析取范式确定它的主合取范式，反之亦然.用公式A的真值表求A的主范式.77主范式的用途(续)例用主析取范式判断下述两个公式是否等值：主范式的用途(续)

例

某公司要从赵、钱、孙、李、周五名新毕业的大学生中选派一些人出国学习.选派必须满足以下条件：

(1)若赵去，钱也去；(2)李、周两人中至少有一人去；(3)钱、孙两人中有一人去且仅去一人；(4)孙、李两人同去或同不去；(5)若周去，则赵、钱也去.试用主析取范式法分析该公司如何选派他们出国？78主范式的用途(续)例某公司要从赵、钱、孙、李、周五名新例(续)解此类问题的步骤为：①

将简单命题符号化②

写出各复合命题③

写出由②中复合命题组成的合取式

④

求③中所得公式的主析取范式

79例(续)解此类问题的步骤为：79例(续)解

①

设p：派赵去，q：派钱去，r：派孙去，

s：派李去，u：派周去.②(1)(p

q)(2)(s

u)(3)((q

r)

(

q

r))(4)((r

s)

(

r

s))(5)(u

(p

q))③(1)~(5)构成的合取式为

A=(p

q)

(s

u)

((q

r)

(

q

r))

((r

s)

(

r

s))

(u

(p

q))80例(续)解①设p：派赵去，q：派钱去，r：派孙去，80例(续)④A

(

p

q

r

s

u)

(p

q

r

s

u)结论：由④可知，A的成真赋值为00110与11001，因而派孙、李去（赵、钱、周不去）或派赵、钱、周去（孙、李不去）.A的演算过程如下:

A

(

p

q)

((q

r)

(

q

r))

(s

u)

(

u

(p

q))

((r

s)

(

r

s))

（交换律)B1=(

p

q)

((q

r)

(

q

r))

((

p

q

r)

(

p

q

r)

(q

r))（分配律）81例(续)④A(pqrsu)例(续)B2=(s

u)

(

u

(p

q))

((s

u)

(p

q

s)

(p

q

u))（分配律）B1

B2

(

p

q

r

s

u)

(

p

q

r

s

u)

(q

r

s

u)

(p

q

r

s)

(p

q

r

u)再令

B3=((r

s)

(

r

s))得A

B1

B2

B3

(

p

q

r

s

u)

(p

q

r

s

u)注意：在以上演算中多次用矛盾律要求：自己演算一遍

82例(续)B2=(su)(u(pq))822.5命题逻辑的推理理论

本节目标：推理的形式结构判断推理是否正确的方法推理定律与推理规则构造证明法832.5命题逻辑的推理理论本节目标：83推理的形式结构—问题的引入

推理举例:(1)正项级数收敛当且仅当部分和上有界.(2)若AÈCÍBÈD，则AÍB且CÍD.推理:从前提推出结论的思维过程前提是指已知的命题公式，结论是从前提出发应用推理规则推出的命题公式上面(1)是正确的推理，而(2)是错误的推理.证明:描述推理正确或错误的过程.84推理的形式结构—问题的引入推理举例:84推理的形式结构定义：若(A1ÙA2Ù…ÙAk)®B为重言式,则称A1,A2,…,Ak推出结论B的推理正确,B是A1,A2,…,Ak的逻辑结论或有效结论。称(A1ÙA2Ù…ÙAk)®B为由前提A1,A2,…,Ak推出结论B的推理的形式结构。用AÞB表示A®B是重言式。若由前提A1,A2,…,Ak推出结论B的推理正确，则记作：A1ÙA2Ù…ÙAkÞB.85推理的形式结构定义：若(A1ÙA2Ù…ÙAk)®B判断推理是否正确的方法由定义可知：判断推理是否正确的方法就是判断重言蕴涵式的方法：真值表法等值演算法主析取范式法构造证明法说明：当命题变项比较少时，用前3个方法比较方便,此时采用形式结构“A1ÙA2Ù…ÙAk®B”.而在构造证明时，采用“前提:A1,A2,…,Ak,结论:B”.

86判断推理是否正确的方法由定义可知：判断推理是否正确的方法就是实例例判断下面推理是否正确(1)若今天是1号，则明天是5号.今天是1号.所以明天是5号.解设p：今天是1号，q：明天是5号.证明的形式结构为:(p®q)Ùp®q证明（用等值演算法）(p®q)Ùp®q

Û

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

Û

ØpÚØqÚq

Û1得证推理正确87实例例判断下面推理是否正确87实例(续)(2)若今天是1号，则明天是5号.明天是5号.所以今天是1号.解设p：今天是1号，q：明天是5号.证明的形式结构为:(p®q)Ùq®p证明（用主析取范式法）(p®q)Ùq®p

Û(ØpÚq)Ùq®p

Û

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

Û

ØqÚp

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

Û

m0Úm2Úm3结果不含m1,故01是成假赋值，所以推理不正确.88实例(续)(2)若今天是1号，则明天是5号.明天是5号推理定律——重言蕴涵式

重要的推理定律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)构造性二难89推理定律——重言蕴涵式重要的推理定律89推理定律(续)(A®B)Ù(ØA®B)Ù(AÚØA)Þ

B

构造性二难（特殊形式）(A®B)Ù(C®D)Ù(ØBÚØD)Þ(ØAÚØC)破坏性二难（可由构造性二难推导出）说明：A,B,C为命题公式符号若某推理符合某条推理定律，则它自然是正确的AÛB产生两条推理定律:AÞB,BÞA90推理定律(续)(A®B)Ù(ØA®B)Ù(AÚØA)Þ推理定律(续)8条推理定律可以分为四组记忆：第一组：第1、2条第二组：第3、4、5条第三组：第6、7条（传递性）第四组：第8条（构造性二难）说明：证明是一个描述推理过程的命题公式序列，其中的每个命题公式或者是已知的前提，或者是由某些前提应用推理规则得到的结论。91推理定律(续)8条推理定律可以分为四组记忆：91推理规则：1：前提引入规则：在证明的任何步骤上，都可以引入前提。2：结论引入规则：在证明的任何步骤上，所证明的结论都可作为后续证明的前提。3：置换规则：在证明的任何步骤上，命题公式的任何子命题公式都可以用与之等值的命题公式置换。例：可用ØAÚB置换A®B等。注：课本上P23中例1.20上面规则中，(4)--(10)其实就是8条推理定律，(11)其实是两个前提的记法。92推理规则：1：前提引入规则：在证明的任何步骤上，都可以引入前构造证明——直接证明法例构造下面推理的证明：若明天是星期一或星期三，我就有课.若有课，今天必备课.我今天下午没备课.所以，明天不是星期一和星期三.解

设p：明天是星期一，q：明天是星期三