命题逻辑的推理理论

命题逻辑的推理理论关于“推理”推理：指从前提出发推出结论的思维过程，前提是已知命题公式集合，结论是从前提出发应用推理规则推出的命题公式。数理逻辑的主要任务是用数学的方法来研究数学中的推理。2推理的形式结构—问题的引入

推理举例:(1)正项级数收敛当且仅当部分和上有界.(2)若AÈCÍBÈD，则AÍB且CÍD.推理:从前提出发推出结论的思维过程上面(1)是正确的推理，而(2)是错误的推理.证明:描述推理正确或错误的过程.3推理的形式结构

定义设A1，A2，…，Ak，B都是命题公式,若对于A1，A2，…，Ak，B中出现的命题变项的任意一组赋值，A1ÙA2Ù…Ù

Ak

均为假，或当A1ÙA2Ù…ÙAk为真时,B也为真,则称由A1,A2,…,Ak推B的推理正确,并称B是有效的结论；否则推理不正确（错误）.4说明（1）：由前提A1，A2，…，Ak推结论B的推理是否正确与诸前提的排列次序无关。因而前提中的公式不一定是序列，而是一个有限公式集合，记为

Г。可将由Г推B的推理记为Г┞B，若推理是正确的，则记为Г|=B，否则记为Г|

B。这里可以称Г┞B和{A1，A2，…，Ak}┞B为推理的形式结构。5说明（2）设A1，A2，…，Ak，B中共出现n个命题变项，对于任一组赋值a1a2…an

（ai＝0或1，

i＝1，2，…n），前提和结论的取值情况有以下四种：（1）A1ÙA2Ù…ÙAk为0，B为0；（2）A1ÙA2Ù…ÙAk为0，B为1；（3）A1ÙA2Ù…ÙAk为1，B为0；（4）A1ÙA2Ù…ÙAk为1，B为1。由定义可知，只要不出现（3）中的情况，推理就是正确的，因而判断推理正确与否，就是判断是否会出现（3）中的情况。6例3.1判断下列推理是否正确（1）{p，p®q}┞q（2）{p，q®p

}┞q

解：只要写出前提的合取式与结论的真值表，看是否出现前提为真，而结论为假的情况即可。由下面真值表可看出，（1）推理正确，（2）推理不正确。7大家有疑问的，可以询问和交流可以互相讨论下，但要小声点89定理3.1

命题公式A1，A2，…，Ak推B的推理正确当且仅当：

（A1ÙA2Ù…ÙAk）®B为重言式。证明：必要性

若命题公式A1，A2，…，Ak推B的推理正确，则不会出现A1ÙA2Ù…ÙAk为真，而B为假的情况，因而在任何赋值下，蕴涵式（A1ÙA2Ù…ÙAk）®B均为真，故为重言式。10证明：充分性若蕴涵式（A1ÙA2Ù…ÙAk）®B为重言式，则对于任何赋值此重言式均为真，因而不会出现前件为真后件为假的情况。即在任何赋值下，或者A1ÙA2Ù…ÙAk为假，或者A1ÙA2Ù…ÙAk和B同时为真，这正符合定义3.1中推理正确的定义。11分析：由定理3.1可知，可以将由前提A1,A2,…,Ak推B的推理的形式结构

{A1ÙA2Ù…ÙAk}┞B

转换成蕴涵式

（A1ÙA2Ù…ÙAk）®B

推理前提的合取式成了蕴涵式的前件，结论成了蕴涵式的后件，并将推理正确{A1ÙA2Ù…ÙAk}|＝B转换成A1ÙA2Ù…ÙAkÞ

B

其中Þ是一种元语言符号，表示蕴涵式为重言式。12判断推理是否正确的方法真值表法等值演算法主析取范式法构造证明法说明：当命题变项比较少时，用前3个方法比较方便,此时采用形式结构“A1ÙA2Ù…ÙAk®B”.而在构造证明时，采用“前提:A1,A2,…,Ak,结论:B”.

13例3.2判断下面推理是否正确解上述类型的推理问题，首先应将简单命题符号化。然后分别写出前提、结论、推理的形式结构，接着进行判断。14（1）设p：a能被4整除

q：a能被2整除前提：p®q，p

结论：q

推理的形式结构：（p®q）Ùp®q可知此推理正确，即（p®q）ÙpÞq。

（1）若a能被4整除，则a能被2整除。a能被4整除，所以a能被2整除。15（2）若a能被4整除，则a能被2整除。a能被2整除，所以a能被4整除。（2）设p：a能被4整除

q：a能被2整除前提：p®q，q

结论：p

推理的形式结构：（p®q）Ùq®p可知上式不为重言式，所以此推理不正确，即（p®q）Ùp

>q。16

（3）下午马芳或去看电影或去游泳。她没去看电影。所以，她去游泳了。

（3）设p：马芳下午去看电影

q：马芳下午去游泳前提：pÚq，ØpÙ结论：q

推理的形式结构：（（pÚq）ÙØp）®q用等值演算法可知上市为重言式，所以，推理正确。

17（4）若下午气温超过30度，则王小燕必去游泳。若她去游泳，她就不去看电影。所以，若王小燕没去看电影，下午气温必超过了30度。（4）设p：下午气温超过30度

q：王小燕去游泳

r：王小燕去看电影前提：p®q，q®

Ør结论：Ør®p

推理的形式结构：（（p®q）Ù（q®

Ør））®（Ør®p）用主析取范式法可知上式不是重言式，所以推理不正确。1819推理定律(续)(A®B)Ù(ØA®B)Ù(AÚØA)Þ

B

构造性二难（特殊形式）(A®B)Ù(C®D)Ù(ØBÚØD)Þ(ØAÚØC)

破坏性二难说明：(1)A,B,C为元语言符号，代表任意的命题公式。(2)若某推理符合某条推理定律，则它自然是正确的.(3)AÛB产生两条推理定律:AÞB,BÞA.2021实例例判断下面推理是否正确

(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得证推理正确22实例(续)(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是成假赋值，所以推理不正确.2324推理定律(续)(A®B)Ù(ØA®B)Ù(AÚØA)Þ

B

构造性二难（特殊形式）(A®B)Ù(C®D)Ù(ØBÚØD)Þ(ØAÚØC)

破坏性二难说明：A,B,C为元语言符号若某推理符合某条推理定律，则它自然是正确的AÛB产生两条推理定律:AÞB,BÞA253.2自然推理系统P判断推理是否正确的三种常用方法：1.真值表技术2.演绎法3.间接证明方法当命题变项较多时，以上三种方法的演算量太大，此时可考虑推理证明的方法。而要构造严谨的证明必须要在形式系统中进行。26形式系统的定义一个形式系统I由下面四个部分组成：（1）非空的字母表，记做A(I)。（2）A(I)中符号构造的合式公式集，记做E(I)。（3）E(I)中一些特殊的公式组成的公理集，记做Ax(I)。（4）推理规则集，记做R(I)。可以将I记为4元组<A(I),E(I),Ax(I),R(I)>。其中<A(I),E(I)>是I的形式语言系统，而<Ax(I),R(I)>为I的形式演算系统。27形式系统的分类（1）自然推理系统它的特点是从任意给定的前提出发，应用系统中的推理规则进行推理演算，得到的最后命题公式是推理的结论（可能是重言式，也可能不是）。（2）公理推理系统它的特点是只能从若干条给定的公理出发，应用系统中的推理规则进行演算，得到的是系统中的定理（是重言式）。28定义3.3自然推理系统P定义如下：

1、字母表（1）命题变项符号：p，q，r，……

（2）联结词符号：Ø,®,Ú,

Ù,«

（3）括号与逗号：（），，

2、合式公式(参见定义1.6

P10）3、推理规则29推理规则（1）前提引入规则：在证明的任何步骤上都可以引入前提。（2）结论引入规则：在证明的任何步骤上所得到的结论都可以做为后续证明的前提。（3）置换规则：在证明的任何步骤上所得到的结论都可以作为后续证明的前提。30推理规则（续）(4)假言推理规则

A®BA

\B(5)附加规则

A

\AÚB

(6)化简规则

AÙB

\A(7)拒取式规则

A®B

ØB

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

A®B

B®C

\A®C

31推理规则(续)

(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ÚD32构造证明——直接证明法例3.3在自然推理系统P中构造下面推理的证明；（1）前提：pÚq，q®r，p®s，Ø

s

结论：rÙ

（pÚq）（2）前提：Ø

pÚq，rÚ

Øq，r®s

结论：p®s33（1）前提：pÚq，q®r，p®s，Ø

s

结论：rÙ

（pÚq）

证明:(1)

p®s前提引入

(2)Ø

s前提引入

(3)Ø

p(1)(2)拒取式

(4)pÚq前提引入(5)q(3)(4)析取三段论(6)q®r前提引入(7)r(5)(6)假言推理(8)rÙ

（pÚq）(7)(4)合取34

（2）前提：Ø

pÚq，rÚ

Øq，r®s

结论：p®s

35构造证明——直接证明法例3.4在自然推理系统P中构造下面推理的证明；若a是实数，则它不是无理数就是有理数。若a不能表示成分数，则它不是有理数。a是实数且它不能表示成分数。所以a是无理数。解：首先将简单命题符号化：

p：a是实数。q：a是有理数。

r：a是无理数。S：a能表示成分数。则可知：前提：p®(qÚr)，Ø

s®

Øq，pÙ

Ø

s结论：r36

前提：p®(qÚr)，Ø

s®

Øq，pÙ

Ø

s

结论：r

证明:(1)pÙ

Ø

s前提引入(2)p(1)化简(3)Ø

s(1)化简(4)p®(qÚr)前提引入(5)qÚr(2)(4)假言推理(6)Ø

s®

Øq前提引入(7)Øq

(3)(6)假言推理(8)r(5)(7)析取三段论37构造证明——附加前提证明法

欲证明前提：A1,A2,…,Ak

结论：C®B等价地证明前提：A1,A2,…,Ak,C

结论：B

理由：(A1ÙA2Ù…ÙAk)®(C®B)

Û

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

Û

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

Û(A1ÙA2Ù…ÙAkÙC)®B将C称为附加前提38附加前提证明法例3.5在自然推理系统P中构造下面推理的证明。如果小张和小王去看电影，则小李也去看电影。小赵不去看电影或小张去看电影。小王去看电影。所以，当小赵去看电影时，小李也去。解：将简单命题符号化：

p：小张去看电影

q：小王去看电影

r：小李去看电影

s：小赵去看电影

39前提：（pÙq）®

r，Ø

sÚp，q

结论：s®r40附加前提证明法(续)

例构造下面推理的证明:2是素数或合数.若2是素数，则是无理数.

若是无理数，则4不是素数.所以，如果4是素数，则2是合数.

用附加前提证明法构造证明解设p：2是素数，q：2是合数，

r：是无理数，s：4是素数形式结构前提：pÚq,p®r,r®Øs

结论：s®q41附加前提证明法(续)42构造证明——归谬法（反证法）

欲证明前提：A1,A2,…,Ak

结论：B将ØB加入前提，若推出矛盾，则得证推理正确.理由:

A1ÙA2Ù…ÙAk®B