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

文档介绍：第3章命题逻辑的推理理论
离散数学
北方民族大学本科生课程
计算机科学与工程学院
推理的形式结构
数理逻辑的主要任务是用数学的方法来研究数学中的推理。
推理是指从前提出发推出结论的思维过程。
前提是已知命题公式集合。
结论是从前提出发应用推理规则推出的命题公式。
证明是描述推理正确或错误的过程。
要研究推理,首先应该明确什么样的推理是有效的或正确的。
设A1,A2,…,Ak和B都是命题公式,若对于A1,A2,…,Ak和B中出现的命题变项的任意一组赋值,(1)或者A1∧A2 ∧…∧Ak为假;(2)或者当A1∧A2 ∧…∧Ak为真时,B也为真;则称由前提A1,A2,…,Ak推出B的推理是有效的或正确的,并称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为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
判断下列推理是否正确。(真值表法)
p
q
p(p→q)
q
p(q→p)
q
0
0
0
0
0
0
0
1
0
1
0
1
1
0
0
0
1
0
1
1
1
1
1
1
例题
正确
不正确
命题公式A1,A2,…,Ak推B的推理正确当且仅当
(A1∧A2∧…∧Ak )→B 为重言式。
该定理是判断推理是否正确的另一种方法。
说明
有效推理的等价定理
推理的形式结构
{ A1, A2, …, Ak}┣B
等同于蕴涵式
(A1∧A2∧…∧Ak )→B
当推理正确时,
形式(1)记为╞ B。
形式(2)记为A1A2…AkB。 表示蕴涵式为重言式。
设={ A1, A2, …, Ak},记为┣B。
A1A2…AkB
前提: A1, A2, …, Ak 结论: B
推理的形式结构
真值表法
等值演算法
主析取范式法
判断推理是否正确的方法
是否有其他的证明方法?
思考
当命题变项较少时,这三种方法比较方便。
说明
(1) 下午马芳或去看电影或去游泳。她没去看电影,所以,她 去游泳了。
判断下列推理是否正确。(等值演算法)
解:设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
由定理 ,推理正确。
例题