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

命题逻辑的推理理论福建师范大学数学与计算机科学学院?数理逻辑的主要任务是用数学的方法来研究数学中的推理。?推理是指从前提出发推出结论的思维过程。?前提是已知命题公式集合。?结论是从前提出发应用推理规则推出的命题公式。?证明是描述推理正确或错误的过程。?要研究推理,首先应该明确什么样的推理是有效的或正确的。定义 设A 1,A 2,…,A k和B都是命题公式,若对于 A 1,A 2,…,A k和B中出现的命题变项的任意一组赋值, (1)或者 A 1∧A 2∧…∧A k为假; (2)或者当 A 1∧A 2∧…∧A k为真时, B也为真; 则称由前提 A 1,A 2,…,A k推出 B的推理是有效的或正确的,并称 B是有效结论。有效推理的定义有效推理的定义即:( A 1∧A 2∧…∧A k)→B为重言式关于有效推理的说明关于有效推理的说明??={A 1,A 2,…,A k}由?推B的推理记为┣B 若推理是正确的,记为?╞B 若推理是不正确的,记为?B ?由前提 A 1,A 2,…,A k推结论 B的推理是否正确与诸前提的排列次序无关。?设A 1,A 2,…,A k,B中共出现 n个命题变项,对于任何一组赋值α 1α 2…α n(α i=0或者 1,i=1,2, …,n) ,前提和结论的取值情况有以下四种: (1) A 1∧A 2∧…∧A k为0,B为0。(2) A 1∧A 2∧…∧A k为0,B为1。(3) A 1∧A 2∧…∧A k为1,B为0。(4) A 1∧A 2∧…∧A k为1,B为1。?只要不出现(3) 中的情况,推理就是正确的,因而判断推理是否正确,就是判断是否会出现(3) 中的情况。?推理正确,并不能保证结论 B一定为真。(1) {p,p →q}├ q (2) {p,q →p}├ q 例1判断下列推理是否正确。(真值表法) 1 0 1 0 q 1 0 1 0 q1111 1001 0010 0000 p?(q→ p) p?(p→ q) qp 正确不正确当推理正确时, ?形式( 1)记为?╞ B。?形式( 2)记为 A 1?A 2?…?A k?B。?表示蕴涵式为重言式。⑴?={ A 1, A 2, …, A k},记为?┣B。⑵ A 1?A 2?…?A k?B ⑶前提: A 1, A 2, …, A k结论: B 说明推理的形式结构推理的形式结构?真值表法?等值演算法?主析取范式法判断推理是否正确的方法判断推理是否正确的方法?是否有其他的证明方法? 思考?当命题变项较少时,这三种方法比较方便。说明下午马芳或去看电影或去游泳。她没去看电影,所以,她去游泳了。例2判断下列推理是否正确。(等值演算法) 解:设 p:马芳下午去看电影, q:马芳下午去游泳。前提: p∨q,┐p结论: q 推理的形式结构: ((p ∨q)∧┐p)→q ((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∨┐D) ?(┐A∨┐C) 破坏性二难推理定律--重言蕴含式推理定律--重言蕴含式