第一-命题逻辑

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

下列句子中哪些是命题？

(1)

北京是中华人民共和国的首都.(2)2+5＝8.(3)x+5＞3.(4)

你会开车吗？(5)2050年元旦北京是晴天.(6)

这只兔子跑得真快呀！(7)

请关上门！(8)

我正在说谎话.真命题假命题真值不确定疑问句感叹句祈使句悖论解：(1),(2),(5)是命题,(3),(4),(6)~(8)都不是命题真值确定,但未知实例3思考题：(1)年10月1日是晴天.(2)地球外的星球上也有人.（3）11＋1＝100.

4简单命题与复合命题简单命题(原子命题):简单陈述句构成的命题(不能分解成更简单的陈述句)简单命题的符号化:用p,q,r,…,pi,qi,ri(i≥1)表示用“1”表示真，用“0”表示假例如，令p：是有理数，则p的真值为0q：2+5=7，则q的真值为1复合命题:由简单命题通过联结词联结而成的陈述句

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

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

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

p,符号

称作否定联结词真值：

p为真当且仅当p为假例如：p:2是合数,

p:2不是合数,p为假,

p为真定义

设p,q为二命题,复合命题“p并且q”(或“p与q”)称为p与q的合取式,记作p∧q,∧称作合取联结词真值：p∧q为真当且仅当p与q同时为真例如：p:2是偶数,q:2是素数,

p∧q:2是偶素数

p为真,q为真,p∧q为真注意:感叹句、祈使句、疑问句都不是命题幂等律AAA,AAA联结词与复合命题(续)④ØqÚr前提引入Û(A1ÙA2Ù…ÙAkÙC)®B构造性二难(特殊形式)ØBÚØD如：在只有3个命题变元的情况下，pqr是极大项，(5)2050年元旦北京是晴天.得(pq)rm0m2m4m5m6pq为真当且仅当p,q不同时为真例10证明p(qr)(pq)rAÚC真值：p为真当且仅当p为假④(pÚq)®r前提引入例2

将下列命题符号化.(1)王晓既用功又聪明.(2)

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

记p:王晓用功,q:王晓聪明(1)p∧q(2)记r:张辉是三好生,s:王丽是三好生,r∧s(3)简单命题,记t:张辉与王丽是同学7思考题：(1)王晓不仅聪明，而且用功.(2)王晓虽然聪明，但不用功.(3)李文与李武是兄弟。8联结词与复合命题(续)定义设p,q为命题,复合命题“p或q”称作p与q的析取式,记作p∨q,∨称作析取联结词真值：

p∨q为假当且仅当p与q同时为假。例如：张三和李四至少有一人会英语设p:张三会英语,q:李四会英语,符号化为p∨q相容或与排斥或例如：这件事由张三或李四中的一人去做设p:张三做这件事,q:李四做这件事应符号化为(p∧

q)∨(

p∧q)9例3

将下列命题符号化(1)2或4是素数.(2)元元只能拿一个苹果或一个梨.(3)王晓红生于1975年或1976年.解：记p:2是素数,r:4是素数,s:6是素数(1)p∨r,(2)记t:元元拿一个苹果,u:元元拿一个梨真值:1(3)记v:王晓红生于1975年,w:王晓红生于1976年说明：由于命题v和w不能同时为真，所以可以简化为v∨w10思考题：（1）选小王或小李中的一人当班长.（2）小王现在在宿舍或图书馆里.11联结词与复合命题(续)定义设p,q为二命题,复合命题“如果p,则q”称作p与q的蕴涵式,记作p

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

称作蕴涵联结词真值：p

q为假当且仅当p为真且q为假.例如：如果明天天气好,我们就出去郊游设p:明天天气好,q:我们出去郊游,形式化为p

q注意：1.p与q不一定有内在联系

2.前件p为假时，p

q为真(不管q为真,还是为假)12蕴涵联结词(续)p

q的逻辑关系:

p为q的充分条件，q为p的必要条件“如果p,则q”的常用表述方式：若p,就q

只要p,就q13实例例4设p:天冷,q:小王穿羽绒服，将下列命题符号化：(1)只要天冷，小王就穿羽绒服.(2)如果天不冷，则小王不穿羽绒服.注意：

p

q与

q

p

等值（真值相同）p

qq

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

q,

称作等价联结词真值：p

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

p

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

p

q与(p

q)

(q

p)等值例如：这件事张三能做好,且只有张三能做好设p:张三做这件事,q:这件事做好了形式化为:p

q15实例例5

求下列复合命题的真值(1)2+2＝4当且仅当3+3＝6.(2)2+2＝4当且仅当3是偶数.(3)2+2＝4当且仅当太阳从东方升起.(4)f(x)在x0处可导的充要条件是它在

x0处连续.101016联结词与复合命题(续)联结词优先级:(),

,

,

,

,

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

pq

pp∧qp∨qp

qp

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

命题变元:真值不确定的陈述句，如:x+3>5(注意：命题变元不是命题！)定义合式公式(命题公式,公式)递归定义如下：(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)

r18公式的赋值定义设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..。

19实例例6公式A=(

p1

p2

p3

)

(p1

p2)000是成真赋值,001是成假赋值

公式B=(p

q)

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

(q

p)

q

p

pq

q

p

(q

p)

q

(q

p)

q

p

00011011101100011111真值表:命题公式在所有可能赋值下的取值的列表。含n个变元的公式有2n个赋值（1）列出所有命题变元，列出所有可能赋值（2）按运算的先后顺序写出命题公式各层次；（3）对应每个赋值，计算各层次的真值及整个命题公式的值21实例(续)

pq

p

p

q

(

p

q)

(

p

q)

q00011011110011010010000022实例(续)(3)(p

q)

r

pqr

p

q

r

(p

q)

r

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

p)

q

p为重言式(2)

(

p

q)

q为矛盾式(3)(p

q)

r为可满足式241.2命题逻辑等值演算1.2.1等值式与等值演算等值式与基本等值式真值表法与等值演算法25等值式定义若等价式A

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

B,并称A

B是等值式。

说明:(1)

是元语言符号,不要混同于

和=(2)A与B等值当且仅当A与B在所有可能赋值下的真值都相同,即A与B有相同的真值表26真值表法例8判断

(p

q)与

p

q

是否等值解：结论:

(p

q)

(

p

q)

pq

p

qp

q

(p

q)

p

q

(p

q)(

p

q)0011011101101001100110011100100127用真值表可验证两个公式是否等值请验证：p

(q

r)

(p

q)

rp

(q

r)(p

q)

r

注：蕴含式不满足结合律28基本等值式双重否定律

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)

A注意：A,B,C代表任意的命题公式000是成真赋值,001是成假赋值A®B同一律A0A,A1A（A运算后不变）(2)王晓虽然聪明，但不用功.定义在仅含有联结词,∧,∨的命题公式A中，将∨换成∧,∧长度为k的简单析取式可展开成2nk个极大项的合取③Ør①②拒取式(pqr)(pqr)极小项极大项这样的简单合取式(简单析取式)为极小项(极大项)。②r®s前提引入Am1m3m7设p:张三喝茶,q:张三看报,p并且q结论:rÙ(pÚq)（pqr)(pqr)29基本等值式(续)零律

A

1

1,A

0

0（A类似数字0）同一律

A

0

A,

A

1

A（A运算后不变）排中律

A

A

1矛盾律

A

A

0蕴涵等值式

A

B

A

B等价等值式

A

B

(A

B)

(B

A)

(A

B)

(

B

A)假言易位

A

B

B

A等价否定等值式

A

B

A

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

B,则

(B)

(A)

例10

证明

p

(q

r)

(p

q)

r证

p

(q

r)

p

(

q

r)（蕴涵等值式）

(

p

q)

r

（结合律）

(p

q)

r

（德摩根律）

(p

q)

r

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

(q

r)(p

q)

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

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

(p

q)

解q

(p

q)

q

(

p

q)（蕴涵等值式）

q

(p

q)（德摩根律）

p

(q

q)（交换律，结合律）

p

0（矛盾律）

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

q)

(

q

p)解

(p

q)

(

q

p)

(

p

q)

(q

p)（蕴涵等值式）

(

p

q)

(

p

q)（交换律）

1该式为重言式.34实例(续)(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说明:演算步骤不唯一,应尽量使演算短些对偶式和对偶原理定义在仅含有联结词

,∧,∨的命题公式A中，将∨换成∧,∧

换成∨，若A中含有0或1，就将0换成1，1换成0，所得命题公式称为A的对偶式，记为A*.

从定义不难看出，(A*)*还原成A例：

(p∧q)与

(p∨q)0与1

(p∨q)∨0与(p∧

q)∧1定理（对偶原理）设A，B为两个命题公式，若A

B，则A*

B*.例：

1.A

1（重言式），则A*

0（矛盾式）

2.A

0（矛盾式），则A*

1（重言式）

3.p∨(

p∨(q∧q)）

1

则p∧(

p∧(q∨q)）

0

371.3范式1.3.1析取范式与合取范式简单析取式与简单合取式析取范式与合取范式1.3.2主析取范式与主合取范式极小项与极大项38简单析取式与简单合取式简单析取式:有限个命题变元及其否定构成的析取式。如p,

q,p

q,p

q

r,…简单合取式:有限个命题变元及其否定构成的合取式如p,

q,p

q,p

q

r,…定理1.3(1)一个简单析取式是重言式当且仅当它同时含某个命题变元和它的否定(2)一个简单合取式是矛盾式当且仅当它同时含某个命题变项和它的否定39析取范式与合取范式析取范式:由有限个简单合取式组成的析取式A1

A2

Ar,其中A1,A2,,Ar是简单合取式，如(p

q

r)(p

q

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

A1

A2

Ar,其中A1,A2,,Ar是简单析取式，如（p

q

r)

(p

q

r)范式:析取范式与合取范式的统称

说明：1.单个命题变元及其否定既是简单析取式，又是简单合取式2.形如p

q

r,

p

q

r的公式既是析取范式，又是合取范式(为什么?)3.范式中不包含

和

4.析取范式的对偶式为合取范式，合取范式的对偶式为析取范式定理1.4(1)一个析取范式是矛盾式当且仅当它的每一个简单合取式都是矛盾式；(2)一个合取范式是重言式当且仅当它的每一个简单析取式都是重言式。41范式存在定理定理1.5

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

求公式A的范式的步骤：(1)消去A中的

,

A

B

A

B

A

B

(

A

B)

(A

B)

(A

B)

(

A

B)(2)否定联结词

的内移或消去

A

A

(A

B)

A

B

(A

B)

A

B注意：范式中的否定符应当紧接着命题变元42范式存在定理(续)例14求下列公式的析取范式与合取范式(1)A=(p

q)

r解(p

q)

r

(

p

q)

r

（消去

）

p

q

r

（结合律）这既是A的析取范式（由3个简单合取式组成的析取式），又是A的合取范式（由一个简单析取式组成的合取式）45极小项与极大项定义1.17

在含有n个命题变元的简单合取式(简单析取式)

中,若每个命题变元均以文字(命题变元及其否定统称为文字）的形式出现且仅出现一次，而且第i(1

i

n)

个文字(按下标或字母顺序排列)出现在左起第i位上,称这样的简单合取式(简单析取式)为极小项(极大项)。如：在只有3个命题变元的情况下，p

q

r是极大项，

p

q

r是极小项说明:(1)

n个命题变元产生2n个极小项和2n个极大项；

(2)2n个极小项(极大项)均互不等值；

(3)用mi表示第i个极小项,其中i是该极小项成真赋值的十进制表示；（记忆：合取成真极小）

用Mi表示第i个极大项,其中i是该极大项成假赋值的十进制表示；（记忆：析取成假极大）

mi(Mi)称为极小项(极大项)的名称。

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

mi

Mi,

Mi

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

p

q00m0

p

q00M0

p

q01m1

p

q01M1p

q10m2

p

q10M2

p

q11m3

p

q11M3

p,q形成的极小项与极大项（注：上述m3中3的二进制为11）47主析取范式与主合取范式主（特异）析取范式:由极小项构成的析取范式主（特异）合取范式:由极大项构成的合取范式例如，n=3,命题变元为p,q,r时，

(

p

q

r)

(

p

q

r)

m1

m3

是主析取范式

(p

q

r)

(

p

q

r)

M6

M2

是主合取范式定理1.7任何命题公式都存在着与之等值的主析取范式和主合取范式,并且是唯一的.48求主析取范式的步骤设公式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)将极小项按下标从小到大排列49求主合取范式的步骤设公式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)将极大项按下标从小到大排列50实例例15

求

(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)51实例(续)(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)52快速求法设公式含有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

M3注：先获得公式的析取（合取）范式，再由上述规则便可快速得到公式对应的主析取（主合取）范式53实例例16(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)54实例(续)(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)55主析取范式的用途(1)求公式的成真赋值和成假赋值设公式A含n个命题变元,A的主析取范式有s个极小项,则A有s个成真赋值,它们是极小项下标的二进制表示,其余2n

s个赋值都是成假赋值例如

(p

q)

r

m0

m2

m4

m5

m6

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

设A含n个命题变元，则

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

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

(p

q)

q(2)B

p(p

q)解：(1)A

(

p

q)

q

(p

q)

q0矛盾式(2)B

p(p

q)1m0

m1

m2

m3

重言式(3)C(p

q)r（作业）58主析取范式的用途(续)(3)判断两个公式是否等值例18用主析取范式判断下面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)59(2)(p

q)r与p(q

r)（作业）60实例例19某单位要从A,B,C三人选派若干人出国考察,需满足下述条件:(1)若A去,则C必须去;(2)若B去,则C不能去;(3)A和B必须去一人且只能去一人.问有几种可能的选派方案?解此类问题的步骤为：①将简单命题符号化②写出各复合命题③写出由②中复合命题组成的合取式④求③中所得公式的主析取范式61实例接上例：某单位要从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))62求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去63主合取范式由主析取范式求主合取范式设没有出现的极小项是其中t=2n

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

q

r)(p

q

r)(p

q

r)的主合取范式解：已经有了主析取范式，即

A

m1

m3

m7

M0

M2

M4

M5

M6矛盾式的主合取范式含全部2n个极大项重言式的主合取范式不含任何极大项,记作11.4命题逻辑推理理论1.4.1推理的形式结构推理的前提与结论,正确推理推理定律1.4.2自然推理系统P推理规则直接证明法,附加前提证明法,

归谬法(反证法)有效推理定义2.20

若对于每组赋值,A1ÙA2Ù…Ù

Ak

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

由前提A1,A2,…,Ak

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

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

A1ÙA2Ù…ÙAk®B形式(2)

前提:A1,A2,…,Ak

结论:B

推理正确记作A1ÙA2Ù…ÙAkÞB68判断推理是否正确的方法真值表法等值演算法主析取范式法构造证明法说明：当命题变元比较少时，用前3个方法比较方便,此时采用形式结构“

A1ÙA2Ù...ÙAk®B”.

当命题变元比较多时，用构造证明法，采用“前提:A1,A2,…,Ak,结论:B”.

实例例22判断下面推理是否正确:(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ÚØqÚq

Û

1得证推理正确实例(续)(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Úm301是成假赋值,所以推理不正确.推理定律——重言蕴涵式这一步已为析取范式（两个简单合取式构成）例11证明:p(qr)(pq)r例如：如果明天天气好,我们就出去郊游解：设p:今天是1号,q:明天是5号.形式(1)A1ÙA2Ù…ÙAk®B(pq)r（消去）q：2+5=7，则q的真值为1②ØpÚq前提引入pq为真当且仅当p,q不同时为真设公式A含n个命题变元,A的主析取范式有s个极小项,则A证p(qr)主析取范式的用途(续)(AB)AB析取范式的对偶式为合取范式，合取范式的对偶式为析取范式(pq)r（蕴涵等值式）自然推理系统P自然推理系统P由下述3部分组成:1.字母表(1)命题变元符号:p,q,r,…,pi,qi,ri,…(2)联结词:

,

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

A®B

ØB

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

A®B

B®C

\A®C

(1)假言推理规则

A®BA

\B(2)附加规则

A

\AÚB(3)化简规则

AÙB

\A

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

A®B

C®D

ØBÚØD

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

A

B

\AÙB

(6)析取三段论规则

AÚB

ØB

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

A®B

C®D

AÚC

\BÚD直接证明法例23

在自然推理系统P中构造下面推理的证明:前提:

pÚq,q®r,p®s,Øs结论:rÙ(pÚq)证明：①p®s前提引入②Øs

前提引入③Øp①②拒取式④pÚq

前提引入⑤q③④析取三段论

⑥q®r

前提引入⑦r