命题逻辑的推理理论5.ppt

《命题逻辑的推理理论5.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、命题逻辑的推理理论福建师范大学数学与计算机科学学院数理逻辑的主要任务是用数学的方法来研究数学中的推理。推理是指从前提出发推出结论的思维过程。前提是已知命题公式集合。结论是从前提出发应用推理规则推出的命题公式。证明是描述推理正确或错误的过程。要研究推理，首先应该明确什么样的推理是有效的或正确的。定义1.24设A1,A2,…,Ak和B都是命题公式，若对于A1,A2,…,Ak和B中出现的命题变项的任意一组赋值，（1）或者A1∧A2∧…∧Ak为假;（2）或者当A1∧A2∧…∧Ak为真时，B也为真;则

2、称由前提A1,A2,…,Ak推出B的推理是有效的或正确的，并称B是有效结论。有效推理的定义即：（A1∧A2∧…∧Ak）→B为重言式关于有效推理的说明＝{A1，A2，…，Ak}由推B的推理记为┣B若推理是正确的，记为╞B若推理是不正确的，记为B由前提A1，A2，…，Ak推结论B的推理是否正确与诸前提的排列次序无关。设A1，A2，…，Ak，B中共出现n个命题变项，对于任何一组赋值α1α2…αn(αi=0或者1，i=1,2,…,n)，前提和结论的取值情况有以下四种：(1)A1∧A2∧…∧Ak为

3、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)中的情况。推理正确，并不能保证结论B一定为真。(1){p,p→q}├q(2){p,q→p}├q例1判断下列推理是否正确。（真值表法）pqp(p→q)qp(q→p)q000000010101100010111111正确不正确当推理正确时，形式（1）记为╞B。形式（2）记为

4、A1A2…AkB。表示蕴涵式为重言式。={A1,A2,…,Ak}，记为┣B。A1A2…AkB前提：A1,A2,…,Ak结论：B说明推理的形式结构真值表法等值演算法主析取范式法判断推理是否正确的方法是否有其他的证明方法？思考当命题变项较少时,这三种方法比较方便。说明下午马芳或去看电影或去游泳。她没去看电影，所以，她去游泳了。例2判断下列推理是否正确。（等值演算法）解：设p:马芳下午去看电影，q:马芳下午去游泳。前提：p∨q，┐p结论：q推理的形式结构：((p∨q)∧┐p)→q

5、((p∨q)∧┐p)→q┐((p∨q)∧┐p)∨q((┐p∧┐q)∨p)∨q((┐p∨p)∧(┐q∨p))∨q(┐q∨p)∨q1例题(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)构造性二难(9)(A→B)∧(C→D)∧(┐B

6、∨┐D)(┐A∨┐C)破坏性二难推理定律--重言蕴含式关于推理定律的几点说明A,B,C为元语言符号，代表任意的命题公式。若一个推理的形式结构与某条推理定律对应的蕴涵式一致，则不用证明就可断定这个推理是正确的。1.3节给出的24个等值式中的每一个都派生出两条推理定律。例如双重否定律AA产生两条推理定律AA和AA。由九条推理定律可以产生九条推理规则,它们构成了推理系统中的推理规则。构造性证明方法判断推理是否正确的三种方法：真值表法、等值演算法和主析取范式法。当推理中包含的命题变项较

7、多时，上述三种方法演算量太大。对于由前提A1,A2,…,Ak推B的正确推理应该给出严谨的证明。证明是一个描述推理过程的命题公式序列，其中的每个公式或者是前提，或者是由某些前提应用推理规则得到的结论（中间结论或推理中的结论）。常用的推理规则（1）前提引入规则：在证明的任何步骤上，都可以引入前提。（2）结论引入规则：在证明的任何步骤上，所证明的结论都可以作为后续证明的前提。（3）置换规则：在证明的任何步骤上，命题公式中任何子命题公式都可以用与之等价的命题公式置换。（4）假言推理规则ABAB（5）

8、附加规则AAB（6）化简规则ABA（4）若今天下雪,则将去滑雪。今天下雪，所以去滑雪。（5）现在气温在冰点以下。因此，要么现在气温在冰点以下，要么现在下雨。（6）现在气温在冰点以下并且正在下雨。因此，现在气温在冰点以下。（7）拒取式规则ABBA（8） 假言三段论规则ABBCAC（9）析取三段论规则ABBA（10）构造性二难推理规则ABCDACBD（11）破坏性二难推理规则ABCDBDAC（12）合取引入规则ABA