离散数学第三章 命题逻辑的推理理论

离散数学第三章命题逻辑的推理理论第一页，共二十五页，编辑于2023年，星期一13.1推理的形式结构定义3.1

设A1,A2,…,Ak,B为命题公式.若对于每组赋值，A1A2…

Ak

为假，或当A1A2…Ak为真时，B也为真，则称由前提A1,A2,…,Ak推出结论B的推理是有效的或正确的,并称B是有效结论.定理3.1由命题公式A1,A2,…,Ak推B的推理正确当且仅当A1A2…AkB为重言式注意:推理正确不能保证结论一定正确第二页，共二十五页，编辑于2023年，星期一2推理的形式结构2.A1A2…AkB

若推理正确,记为A1A2…AkB3.前提：A1,A2,…,Ak

结论：B判断推理是否正确的方法:

真值表法等值演算法主析取范式法推理的形式结构1.{A1,A2,…,Ak}B

若推理正确,记为{A1,A2,,An}B第三页，共二十五页，编辑于2023年，星期一3推理实例例1

判断下面推理是否正确(1)若今天是1号，则明天是5号.今天是1号.所以,明天是5号.(2)若今天是1号，则明天是5号.明天是5号.所以,今天是1号.解设p：今天是1号，q：明天是5号.(1)推理的形式结构:(pq)pq用等值演算法(pq)pq

((pq)p)q

pqq

1由定理3.1可知推理正确第四页，共二十五页，编辑于2023年，星期一4推理实例(2)推理的形式结构:(pq)qp用主析取范式法(pq)qp(pq)qp

((pq)q)p

qp(pq)(pq)(pq)(pq)

m0m2m3

结果不含m1,故01是成假赋值，所以推理不正确第五页，共二十五页，编辑于2023年，星期一5推理定律——重言蕴涵式1.A

(AB)附加律2.(AB)

A

化简律3.(AB)A

B

假言推理4.(AB)B

A

拒取式5.(AB)B

A

析取三段论6.(AB)(BC)(AC)假言三段论7.(AB)(BC)(AC)等价三段论8.(AB)(CD)(AC)(BD)构造性二难

(AB)(AB)

B

构造性二难(特殊形式)9.(AB)(CD)(BD)(AC)破坏性二难每个等值式可产生两个推理定律如,由AA可产生AA

和AA第六页，共二十五页，编辑于2023年，星期一63.2自然推理系统P定义3.2

一个形式系统I由下面四个部分组成：

(1)非空的字母表，记作A(I).(2)A(I)中符号构造的合式公式集，记作E(I).(3)E(I)中一些特殊的公式组成的公理集，记作AX(I).(4)推理规则集，记作R(I).

记I=<A(I),E(I),AX(I),R(I)>,其中<A(I),E(I)>是I的形式语言系统,<AX(I),R(I)>是I的形式演算系统.形式系统一般分为两类：自然推理系统:无公理,即AX(I)=公理推理系统推出的结论是系统中的重言式,称作定理第七页，共二十五页，编辑于2023年，星期一7自然推理系统P定义3.3自然推理系统P定义如下:1.

字母表

(1)命题变项符号：p,q,r,…,pi,qi,ri,…(2)联结词符号：,,,,(3)括号与逗号：(,),，2.合式公式（同定义1.6）3.

推理规则:(1)—(12)

(1)前提引入规则:在证明的任何步骤都可以引入前提.(2)结论引入规则:在证明的任何步骤所得的结论都有可以作为后继证明的前提.(3)置换规则:在证明的任何步骤,命题公式中的子公式都可以用等值的公式置换,得到公式序列中又一个公式.第八页，共二十五页，编辑于2023年，星期一8推理规则(4)假言推理规则

(6)化简规则

(8)假言三段论规则

ABA∴BA∴ABAB∴A(5)附加规则

(7)拒取式规则

(9)析取三段论规则

AB

B∴AABBC∴ACAB

B∴A第九页，共二十五页，编辑于2023年，星期一9推理规则(10)构造性二难推理规则(11)破坏性二难推理规则

(12)合取引入规则

ABCDAC∴BDABCDBD∴ACAB∴AC第十页，共二十五页，编辑于2023年，星期一10在自然推理系统P中构造证明设前提A1,A2,,Ak,结论B及公式序列C1,C2,,Cl.如果每一个Ci(1il)是某个Aj,或者可由序列中前面的公式应用推理规则得到,并且Cl=B,则称这个公式序列是由A1,A2,,Ak推出B的证明例2

构造下面推理的证明：若明天是星期一或星期四，我明天就有课.若我明天有课，今天必备课.我今天没备课.所以，明天不是星期一、也不是星期四.解(1)设命题并符号化设p：明天是星期一，q：明天是星期四，

r：我明天有课，s：我今天备课第十一页，共二十五页，编辑于2023年，星期一11直接证明法(2)写出证明的形式结构前提：(pq)r,rs,s

结论：pq(3)证明

①rs

前提引入②s

前提引入③r①②拒取式④(pq)r

前提引入⑤(pq)③④拒取式⑥pq⑤置换第十二页，共二十五页，编辑于2023年，星期一12附加前提证明法附加前提证明法适用于结论为蕴涵式欲证前提：A1,A2,…,Ak

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

结论：B理由：

(A1A2…Ak)(CB)

(A1A2…Ak)(CB)

(A1A2…AkC)B(A1A2…AkC)B第十三页，共二十五页，编辑于2023年，星期一13附加前提证明法实例例3

构造下面推理的证明

2是素数或合数.若2是素数，则是无理数.若是无理数，则4不是素数.所以，如果4是素数，则2是合数.解用附加前提证明法构造证明

(1)设p：2是素数，q：2是合数，

r：是无理数，s：4是素数

(2)推理的形式结构前提：pq,pr,rs

结论：sq

第十四页，共二十五页，编辑于2023年，星期一14附加前提证明法实例

(3)证明①s

附加前提引入②pr

前提引入③rs

前提引入④ps②③假言三段论⑤p①④拒取式⑥pq

前提引入⑦q⑤⑥析取三段论第十五页，共二十五页，编辑于2023年，星期一15归谬法（反证法）归谬法(反证法)欲证前提：A1,A2,…,Ak

结论：B做法在前提中加入B，推出矛盾.理由

A1A2…AkB

(A1A2…Ak)B

(A1A2…AkB)

(A1A2…AkB)0

A1A2…AkB0第十六页，共二十五页，编辑于2023年，星期一16归谬法实例例4

前提：(pq)r,rs,s,p

结论：q证明用归缪法①q

结论否定引入②rs

前提引入③s

前提引入④r②③拒取式⑤(pq)r

前提引入⑥(pq)④⑤析取三段论⑦pq⑥置换⑧p①⑦析取三段论⑨p

前提引入

pp⑧⑨合取第十七页，共二十五页，编辑于2023年，星期一17第三章小结主要内容推理的形式结构判断推理是否正确的方法真值表法等值演算法主析取范式法推理定律自然推理系统P构造推理证明的方法直接证明法附加前提证明法归谬法(反证法)第十八页，共二十五页，编辑于2023年，星期一18基本要求理解并记住推理形式结构的两种形式：

1.(A1A2…Ak)B2.前提：A1,A2,…,Ak

结论：B熟练掌握判断推理是否正确的不同方法（如真值表法、等值演算法、主析取范式法等）牢记P系统中各条推理规则熟练掌握构造证明的直接证明法、附加前提证明法和归谬法会解决实际中的简单推理问题第十九页，共二十五页，编辑于2023年，星期一19练习1：判断推理是否正确1.判断下面推理是否正确:

(1)前提：pq,q

结论：p解推理的形式结构:(pq)qp方法一：等值演算法(pq)qp

((pq)q)p(pq)qp((pq)(qq))p

pq易知10是成假赋值，不是重言式，所以推理不正确.第二十页，共二十五页，编辑于2023年，星期一20练习1解答方法二：主析取范式法，(pq)qp((pq)q)ppqM2m0m1m3未含m2,不是重言式,推理不正确.第二十一页，共二十五页，编辑于2023年，星期一21练习1解答方法三真值表法

不是重言式,推理不正确111001110100(pq)qpqppq0111(pq)q0010方法四直接观察出10是成假赋值第二十二页，共二十五页，编辑于2023年，星期一22练习1解答用等值演算法(qr)(pr)(qp)(qr)(pr)(qp)

((qr)(pr))(qp)

((qp)(qr)(rp))(qp)((qp)(qr)(rp))(qp)1推理正确(2)前提：qr,pr结论：q