一-3命题逻辑的推理理论.ppt

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

1、第3章命题逻辑的推理理论离散数学本章说明本章的主要内容推理的形式结构自然推理系统P本章与后续各章的关系本章是第五章的特殊情况和先行准备第一节推理的形式结构数理逻辑的主要任务：是用数学的方法来研究推理问题。推理：是指从前提出发推出结论的思维过程。前提：是已知命题公式的集合。结论：是从前提出发应用推理规则推出的命题公式。要研究推理，首先应该明确什么样的推理是有效的或正确的。铺垫定义3.1：设A1,A2,…,Ak和B都是命题公式，若对于A1,A2,…,Ak和B中出现的命题变项的任意一组赋值，（1）或者A1

2、∧A2∧…∧Ak为假;（2）或者当A1∧A2∧…∧Ak为真时，B也为真;则称由前提A1,A2,…,Ak推出B的推理是有效的或正确的，并称B是有效结论。有效推理的定义关于有效推理的说明2.＝{A1，A2，…，Ak}由推B的推理记为┣B若推理是正确的，记为╞B若推理是不正确的，记为B1.由前提A1，A2，…，Ak推结论B的推理是否正确与诸前提的排列次序无关。关于有效推理的说明3.设A1，A2，…，Ak，B中共出现n个命题变项，对于任何一组赋值α1α2…αn(αi=0或者1，i=1,2,…,

3、n)，前提和结论的取值情况有以下四种：(1)A1∧A2∧…∧Ak为0，B为0。(2)A1∧A2∧…∧Ak为0，B为1。(3)A1∧A2∧…∧Ak为1，B为0。(4)A1∧A2∧…∧Ak为1，B为1。4.只要不出现(3)中的情况，推理就是正确的，因而判断推理是否正确，就是判断是否会出现(3)中的情况。5.推理正确，并不能保证结论B一定为真。我们注重的是推理过程的正确性。(1){p,p→q}├q(2){p,q→p}├q例3.1判断下列推理是否正确。（真值表法）pqp(p→q)qp(q→p)q0

4、00000010101100010111111例题正确q是有效结论不正确q不是有效结论定理3.1：命题公式A1,A2,…,Ak推B的推理正确当且仅当(A1∧A2∧…∧Ak)→B为重言式。该定理是判断推理是否正确的另一种方法。说明有效推理的等价定理定理3.1的证明(1)证明必要性。若A1,A2,…,Ak推B的推理正确，则对于A1,A2,…,Ak,B中所含命题变项的任意一组赋值，不会出现A1∧A2∧…∧Ak为真，而B为假的情况，因而在任何赋值下，蕴涵式(A1∧A2∧…∧Ak)→B均为真，故它为重言式。(2

5、)证明充分性。若蕴涵式(A1∧A2∧…∧Ak)→B为重言式，则对于任何赋值此蕴涵式均为真，因而不会出现前件为真后件为假的情况，即在任何赋值下，或者A1∧A2∧…∧Ak为假，或者A1∧A2∧…∧Ak和B同时为真，这正符合推理正确的定义。前提：A1,A2,…,Ak结论：B推理的形式结构对推理的理解：◎设={A1,A2,…,Ak}，记为┣B（前提推结论）◎A1A2…AkB（讨论此蕴涵式的真值情况）推理正确时╞B推理正确时A1A2…AkB为重言式记为A1A2…AkB推理的形式结构

6、：(A1∧A2∧…∧Ak)→B真值表法等值演算法主析取范式法判断推理是否正确的方法当命题变项较少时,这三种方法比较方便。说明表中不会出现前提合取为真，结论为假的情况A1A2…AkB析取范式中含全部极小项A1A2…AkB为重言式（1）下午马芳或去看电影或去游泳.她没去看电影，所以，她去游泳了。例3.2判断下列推理是否正确。（等值演算法）解：设p:马芳下午去看电影，q:马芳下午去游泳。前提：p∨q，┐p结论：q推理的形式结构：((p∨q)∧┐p)→q((p∨q)∧┐p)→q┐((p∨q)

7、∧┐p)∨q((┐p∧┐q)∨p)∨q((┐p∨p)∧(┐q∨p))∨q(┐q∨p)∨q1由定理3.1可知，推理正确。例题（2）若今天是1号，则明天是5号;明天是5号，所以今天是1号。例3.2判断下列推理是否正确。（主析取范式法）(pq)qp(pq)qp((pq)q)p(pq)qp(pq)(pq)(pq)(pq)(pq)m0m2m3主析取范式不含m1，故不是重言式（01是成假赋值），所以推理不正确。解：设p：今天是1号

8、，q：明天是5号。前提：pq，q结论：p推理的形式结构：(pq)qp例题(pq)q(pp)p(qq)(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)构造性二难