离散数学-第3章.ppt

《离散数学-第3章.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、主要内容推理的形式结构推理的正确与错误推理的形式结构判断推理正确的方法推理定律自然推理系统P形式系统的定义与分类自然推理系统P在P中构造证明:直接证明法、附加前提证明法、归谬法第三章命题逻辑的推理理论13.1推理的形式结构定义3.1设A1,A2,…,Ak,B为命题公式.若对于每组赋值，A1A2…Ak为假，或当A1A2…Ak为真时，B也为真，则称由前提A1,A2,…,Ak推出结论B的推理是有效的或正确的,并称B是有效结论.定理3.1由命题公式A1,A2,…,Ak推B的推理正确当且仅当A1A2…AkB为重言式注意:推理正确不能保证结论一定正确2推理的形式结构2.A1A2…

2、AkB若推理正确,记为A1A2…AkB3.前提：A1,A2,…,Ak结论：B判断推理是否正确的方法:真值表法等值演算法主析取范式法推理的形式结构1.{A1,A2,…,Ak}B若推理正确,记为{A1,A2,,An}B3推理实例例1判断下面推理是否正确(1)若今天是1号，则明天是5号.今天是1号.所以,明天是5号.(2)若今天是1号，则明天是5号.明天是5号.所以,今天是1号.解设p：今天是1号，q：明天是5号.(1)推理的形式结构:(pq)pq用等值演算法(pq)pq((pq)p)qpqq1由定理3.1可知推理正确4推理实例(2)推理的形式结构:(

3、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是成假赋值，所以推理不正确5推理定律——重言蕴涵式1.A(AB)附加律2.(AB)A化简律3.(AB)AB假言推理4.(AB)BA拒取式5.(AB)BA析取三段论6.(AB)(BC)(AC)假言三段论7.(AB)(BC)(AC)等价三段论8.(AB)(CD)(AC)(BD)构造性二难(AB)(AB)B构造性二难(特殊形式

4、)9.(AB)(CD)(BD)(AC)破坏性二难每个等值式可产生两个推理定律如,由AA可产生AA和AA63.2自然推理系统P定义3.2一个形式系统I由下面四个部分组成：(1)非空的字母表，记作A(I).(2)A(I)中符号构造的合式公式集，记作E(I).(3)E(I)中一些特殊的公式组成的公理集，记作AX(I).(4)推理规则集，记作R(I).记I=,其中是I的形式语言系统,是I的形式演算系统.自然推理系统:无公理,即AX(

5、I)=公理推理系统推出的结论是系统中的重言式,称作定理7自然推理系统P定义3.3自然推理系统P定义如下:1.字母表(1)命题变项符号：p,q,r,…,pi,qi,ri,…(2)联结词符号：,,,,(3)括号与逗号：(,),，2.合式公式（同定义1.6）3.推理规则(1)前提引入规则(2)结论引入规则(3)置换规则8推理规则(4)假言推理规则(6)化简规则(8)假言三段论规则ABA∴BA∴ABAB∴A(5)附加规则(7)拒取式规则(9)析取三段论规则ABB∴AABBC∴ACABB∴A9推理规则(10)构造性二难推理规则(11)破坏性二难推理规则(12)合取引入规

6、则ABCDAC∴BDABCDBD∴ACAB∴AC10在自然推理系统P中构造证明设前提A1,A2,,Ak,结论B及公式序列C1,C2,,Cl.如果每一个Ci(1il)是某个Aj,或者可由序列中前面的公式应用推理规则得到,并且Cl=B,则称这个公式序列是由A1,A2,,Ak推出B的证明例2构造下面推理的证明：若明天是星期一或星期三，我明天就有课.若我明天有课，今天必备课.我今天没备课.所以，明天不是星期一、也不是星期三.解(1)设命题并符号化设p：明天是星期一，q：明天是星期三，r：我明天有课，s：我今天备课11直接证明法(2)写出证明的形式结构前提：(pq)

7、r,rs,s结论：pq(3)证明①rs前提引入②s前提引入③r①②拒取式④(pq)r前提引入⑤(pq)③④拒取式⑥pq⑤置换12附加前提证明法附加前提证明法适用于结论为蕴涵式欲证前提：A1,A2,…,Ak结论：CB等价地证明前提：A1,A2,…,Ak,C结论：B理由：(A1A2…Ak)(CB)(A1A2…Ak)(CB)(A1A2…