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

1主要内容推理的形式结构推理的正确与错误推理的形式结构判断推理正确的方法推理定律自然推理系统P形式系统的定义与分类自然推理系统P在P中构造证明:直接证明法、附加前提证明法、归谬法第三章命题逻辑的推理理论23.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为重言式注意:推理正确不能保证结论一定正确3推理的形式结构2.A1A2…AkB若推理正确,记为A1A2…AkB3.前提：A1,A2,…,Ak结论：B判断推理是否正确的方法:真值表法等值演算法主析取范式法推理的形式结构1.{A1,A2,…,Ak}B若推理正确,记为{A1,A2,,An}B4推理实例例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可知推理正确5推理实例(2)推理的形式结构:(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是成假赋值，所以推理不正确6推理定律——重言蕴涵式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构造性二难(特殊形式)9.(AB)(CD)(BD)(AC)破坏性二难每个等值式可产生两个推理定律如,由AA可产生AA和AA73.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)=公理推理系统推出的结论是系统中的重言式,称作定理8自然推理系统P定义3.3自然推理系统P定义如下:1.字母表(1)命题变项符号：p,q,r,…,pi,qi,ri,…(2)联结词符号：,,,,(3)括号与逗号：(,),，2.合式公式（同定义1.6）3.推理规则:(1)—(12)(1)前提引入规则:在证明的任何步骤都可以引入前提.(2)结论引入规则:在证明的任何步骤所得的结论都有可以作为后继证明的前提.(3)置换规则:在证明的任何步骤,命题公式中的子公式都可以用等值的公式置换,得到公式序列中又一个公式.9推理规则(4)假言推理规则(6)化简规则(8)假言三段论规则ABA∴BA∴ABAB∴A(5)附加规则(7)拒取式规则(9)析取三段论规则ABB∴AABBC∴ACABB∴A10推理规则(10)构造性二难推理规则(11)破坏性二难推理规则(12)合取引入规则ABCDAC∴BDABCDBD∴ACAB∴AC11在自然推理系统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：我今天备课12直接证明法(2)写出证明的形式结构前提：(pq)r,rs,s结论：pq(3)证明①rs前提引入②s前提引入③r①②拒取式④(pq)r前提引入⑤(pq)③④拒取式⑥pq⑤置换13附加前提证明法附加前提证明法适用于结论为蕴涵式欲证前提：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)B14附加前提证明法实例例3构造下面推理的证明2是素数或合数.若2是素数，则是无理数.若是无理数，则4不是素数.所以，如果4是素数，则2是合数.解用附加前提证明法构造证明(1)设p：2是素数，q：2是合数，r：是无理数，s：4是素数(2)推理的形式结构前提：pq,pr,rs结论：sq22215附加前提证明法实例(3)证明①s附加前提引入②pr前提引入③rs前提引入④ps②③假言三段论⑤p①④拒取式⑥pq前提引入⑦q⑤⑥析取三段论16归谬法（反证法）归谬法(反证法)欲证前提：A1,A2,…,Ak结论：B做法在前提中加入B，推出矛盾.理由A1A2…AkB(A1A2…Ak)B(A1A2…AkB)(A1A2…AkB)0A1A2…AkB017归谬法实例例4前提：(pq)r,rs,s,p结论：q证明用归缪法①q结论否定引入②rs前提引入③s前提引入④r②③拒取式⑤(pq)r前提引入⑥(pq)④⑤析取三段论⑦pq⑥置换⑧p①⑦析取三段论⑨p前提引入pp⑧⑨合取18第三章小结主要内容推理的形式结构判断推理是否正确的方法真值表法等值演算法主析取范式法推理定律自然推理系统P构造推理证明的方法直接证明法附加前提证明法归谬法(反证法)19基本要求理解并记住推理形式结构的两种形式：1.(A1A2…Ak)B2.前提：A1,A2,…,Ak结论：B熟练掌握判断推理是否正确的不同方法（如真值表法、等值演算法、主析取范式法等）牢记P系统中各条推理规则熟练掌握构造证明的直接证明法、附加前提证明法和归谬法会解决实际中的简单推理问题20练习1：判断推理是否正确1.判断下面推理是否正确:(1)前提：pq,q结论：p解推理的形式结构:(pq)qp方法一：等值演算法(pq)qp((pq)q)p(pq)qp((pq)(qq))ppq易知10是成假赋值，不是重言式，所以推理不正确.21练习1解答方法二：主析取范式法，(pq)qp((pq)q)ppqM2m0m1m3未含m2,不是重言式,推理不正确.22练习1解答方法三真值表法不是重言式,推理不正确111001110100(pq)qpqppq0111(pq)q0010方法四直接观察出10是成假赋值23练习1解答用等值演算法(qr)(pr)(qp)(qr)(pr)(qp)((qr)(pr))(qp)((qp)(qr)(rp))(qp)((qp)(qr)(rp))(qp)1推理正确(2)前提：qr,pr结论：qp解推理的形式结构：(qr)(pr)(qp)24练习2：构造证明2.在系统P中构造下面推理的证明：如果今天是星期六，我们就到颐和园或圆明园去玩.如果颐和园游人太多，我们就不去颐和园玩.今天是星期六.颐和园游人太多.所以,我们去圆明园或动物园玩.证明：(1)设p：今天是周六，q：到颐和园玩，r：到圆明园玩，s：颐和园游人太多t：到动物园玩(2)前提：p(qr),sq,p,s结论：rt25练习2解答(3)证明：①p(qr)前提引入②p前提引入③qr①②假言推理④sq前提引入⑤s前提引入⑥q④⑤假言推理⑦r③⑥析取三段论⑧rt⑦附加前提：p(qr),sq,p,s结论：rt