命题逻辑的推理理论.ppt

命题逻辑的推理理论,福建师范大学数学与计算机科学学院,数理逻辑的主要任务是用数学的方法来研究数学中的推理。推理是指从前提出发推出结论的思维过程。前提是已知命题公式集合。结论是从前提出发应用推理规则推出的命题公式。证明是描述推理正确或错误的过程。要研究推理，首先应该明确什么样的推理是有效的或正确的。,定义1.24设A1,A2,Ak和B都是命题公式，若对于A1,A2,Ak和B中出现的命题变项的任意一组赋值，（1）或者A1A2Ak为假;（2）或者当A1A2Ak为真时，B也为真;则称由前提A1,A2,Ak推出B的推理是有效的或正确的，并称B是有效结论。,有效推理的定义,即：（A1A2Ak）B为重言式,关于有效推理的说明,A1，A2，Ak由推B的推理记为B若推理是正确的，记为B若推理是不正确的，记为B,由前提A1，A2，Ak推结论B的推理是否正确与诸前提的排列次序无关。,设A1，A2，Ak，B中共出现n个命题变项，对于任何一组赋值12n(i=0或者1，i=1,2,n)，前提和结论的取值情况有以下四种：(1)A1A2Ak为0，B为0。(2)A1A2Ak为0，B为1。(3)A1A2Ak为1，B为0。(4)A1A2Ak为1，B为1。只要不出现(3)中的情况，推理就是正确的，因而判断推理是否正确，就是判断是否会出现(3)中的情况。推理正确，并不能保证结论B一定为真。,(1)p,pqq(2)p,qpq,例1判断下列推理是否正确。（真值表法）,正确,不正确,当推理正确时，形式（1）记为B。形式（2）记为A1A2AkB。表示蕴涵式为重言式。,=A1,A2,Ak，记为B。A1A2AkB前提：A1,A2,Ak结论：B,说明,推理的形式结构,真值表法等值演算法主析取范式法,判断推理是否正确的方法,是否有其他的证明方法？,思考,当命题变项较少时,这三种方法比较方便。,说明,下午马芳或去看电影或去游泳。她没去看电影，所以，她去游泳了。,例2判断下列推理是否正确。（等值演算法）,解：设p:马芳下午去看电影，q:马芳下午去游泳。前提：pq，p结论：q推理的形式结构：(pq)p)q(pq)p)q(pq)p)q(pq)p)q(pp)(qp)q(qp)q1,例题,(1)A(AB)附加律(2)(AB)A化简律(3)(AB)AB假言推理(4)(AB)BA拒取式(5)(AB)BA析取三段论(6)(AB)(BC)(AC)假言三段论(7)(AB)(BC)(AC)等价三段论(8)(AB)(CD)(AC)(BD)构造性二难(9)(AB)(CD)(BD)(AC)破坏性二难,推理定律-重言蕴含式,关于推理定律的几点说明,A,B,C为元语言符号，代表任意的命题公式。若一个推理的形式结构与某条推理定律对应的蕴涵式一致，则不用证明就可断定这个推理是正确的。1.3节给出的24个等值式中的每一个都派生出两条推理定律。例如双重否定律AA产生两条推理定律AA和AA。由九条推理定律可以产生九条推理规则,它们构成了推理系统中的推理规则。,构造性证明方法,判断推理是否正确的三种方法：真值表法、等值演算法和主析取范式法。当推理中包含的命题变项较多时，上述三种方法演算量太大。对于由前提A1,A2,Ak推B的正确推理应该给出严谨的证明。证明是一个描述推理过程的命题公式序列，其中的每个公式或者是前提，或者是由某些前提应用推理规则得到的结论（中间结论或推理中的结论）。,常用的推理规则,（1）前提引入规则：在证明的任何步骤上，都可以引入前提。（2）结论引入规则：在证明的任何步骤上，所证明的结论都可以作为后续证明的前提。（3）置换规则：在证明的任何步骤上，命题公式中任何子命题公式都可以用与之等价的命题公式置换。,（4）假言推理规则ABAB（5）附加规则AAB（6）化简规则ABA,（4）若今天下雪,则将去滑雪。今天下雪，所以去滑雪。（5）现在气温在冰点以下。因此，要么现在气温在冰点以下，要么现在下雨。（6）现在气温在冰点以下并且正在下雨。因此，现在气温在冰点以下。,（7）拒取式规则ABBA（8）假言三段论规则ABBCAC（9）析取三段论规则ABBA,（10）构造性二难推理规则ABCDACBD（11）破坏性二难推理规则ABCDBDAC（12）合取引入规则ABAB,构造证明,构造证明就是由一组公式作为前提，利用自然推理系统中的规则，推出结论。构造形式结构A1A2AkB的推理的书写方法：前提：A1,A2,Ak结论：B证明方法：直接证明法附加前提法归谬法（或称反证法）,例3.1构造下面推理的证明：前提：pq,rq,rs结论：pspq前提引入pq置换rq前提引入qr置换pr假言三段论rs前提引入ps假言三段论,例题,例3.2构造下面推理的证明：前提：p（qr）,pq结论：rsp（qr）前提引入pq前提引入p化简q化简qr假言推理r假言推理rs附加rs置换,技巧一：附加前提证明法,(A1A2Ak)(AB)等价于(A1A2AkA)B即原来结论中的前件变成前提了！,例4构造下面推理的证明。如果小张和小王去看电影，则小李也去看电影；小赵不去看电影或小张去看电影；小王去看电影。所以，当小赵去看电影时，小李也去看电影。构造证明：（1）将简单命题符号化：设p:小张去看电影。q:小王去看电影。r:小李去看电影。s:小赵去看电影。,（2）形式结构：前提：(pq)r,sp,q结论：sr（3）证明：用附加前提证明法s附加前提引入sp前提引入p析取三段论(pq)r前提引入q前提引入pq合取r假言推理,技巧二：归谬法,(A1A2Ak)B等价于（A1A2AkB）因此，若A1A2Ak与B不相容（即A1A2AkB为矛盾式，或（A1A2AkB）为重言式），则说明B是A1A2Ak的逻辑结论。这种将B作为附加前提推出矛盾的证明方法成为归谬法。,例5构造下面推理的证明。如果小张守第一垒并且小李向B队投球，则A队将取胜；或者A队未取胜，或者A队获得联赛第一名；A队没有获得联赛的第一名；小张守第一垒。因此，小李没有向B队投球。构造证明：（1）将简单命题符号化：设p:小张守第一垒。q:小李向B队投球。r:A队取胜。s:A队获得联赛第一名。（2）形式结构：前提：(pq)r,rs,s,p结论：q,例题,（3）证明：用归谬法q结论的否定引入rs前提引入s前提引入r析取三段论(pq)r前提引人(pq)拒取式pq置换p前提引入q析取三段论qq合取由于最后一步为矛盾式，所以推理正确。,小节结束,本节主要内容,推理的形式结构：推理的前提推理的结论推理正确判断推理是否正确的方法：真值表法等值演算法主析取范式法对于正确的推理，给予构造证明:1.常用的推理规则：2.附加前提证明法3.归谬法,本章学习要求,理解并记住推理的形式结构的三种等价形式，即A1,A2,AkBA1A2AkB前提：A1,A2,Ak结论：B在判断推理是否正确时，用；在系统中构造证明时用。熟练掌握判断推理是否正确的三种方法（真值表法，等值演算法，主析取范式法）。牢记各条推理规则。对于给定的正确推理，要求在系统中给出严谨的证明序列。会用附加前提证明法和归谬法。,典型例题,1、用不同的方法验证下面推理是否正确。对于正确的推理还要在系统中给出证明。（1）前提：pq,q结论：p（2）前提：qr,pr结论：qp,（1）不正确。验证答案，只需证明(pq)qp不是重言式。方法一等值演算(pq)qp(pq)q)p(pq)qp(pq)(qq)ppq易知10是成假赋值，故(pq)qp不是重言式，所以推理不正确。,方法二主析取范式法经过演算后可知(pq)qpm0m1m3未含m2,故(pq)qp不是重言式。,方法三直接观察出10是成假赋值。,方法四真值表法(pq)qp的真值表为,结论（不正确）是对的。,（2）推理正确方法一真值表法（自己做）方法二等值演算法（自己做）方法三主析取范式法（自己做）方法四构造证明证明：（直接证明法）pr（前提引入）rp（置换）qr（前提引入）qp（假言三段论）,2、构造下面推理的证明：如果今天是周六，我们就到颐和园或圆明园玩。如果颐和园游人太多，就不去颐和园。今天是周六，并且颐和园游人太多。所以