命题逻辑推理理论.ppt

DiscreteMathematicsDate1DiscreteMath.,.,ChenChen推理是指从一些已知的命题公式(称为前提)应用推理规则推演出另一些命题公式(称为结论)的过程。,A2,…,Ak和B是命题公式,若对于A1,A2,…,Ak,B中出现的命题变项的任一组赋值,要么A1∧A2∧…∧Ak为假,要么A1∧A2∧…∧Ak为真且B也为真,则称由前提A1,A2,…,Ak推出B的推理是有效的(或正确的),并称B是有效的结论。§∧A2∧…∧AkB永真注:1、由前提A1,A2,…,Ak推结论B的推理是否正确与诸前提的排列次序无关。将一个推理诸前提的集合记为Г,则由Г推出结论B的推理记为Г├B。若该推理是正确的,则记为Г╞B(或ГB),否则记为Г⊭B(或Г⇏B)。称Г├B和{A1,A2,…,Ak}├B为推理的形式结构。Date3DiscreteMath.,ChenChen2、设命题公式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)即可。3、推理正确,并不能保证结论B一定为真。因为前提可能是假的(情况(1))。Date4DiscreteMath.,(1){p,p→q}├q;(2){p,q→p}├q解:用真值表法pqp∧(p→q)qp∧(q→p)q00011011(1)从真值表可见,没有出现前提p∧(p→q)为真,结论q为假的情况,故{p,p→q}q。(2)在赋值为10时,出现了前提p∧(q→p)为真而q为假的情况,故{p,q→p}⇏q。0001000100101111Date5DiscreteMath.,,A2,…,Ak推B的推理正确,即{A1,A2,…,Ak}╞B当且仅当(A1∧A2∧…∧Ak)→B为重言式。证明见教材43页。由该定理,推理的形式结构:{A1,A2,…,Ak}┣B()可用(A1∧A2∧…∧Ak)→B()表示。判断推理是否正确的三种直接方法:1、真值表法2、等值演算法3、主析取范式法或写成前提:A1,A2,…,Ak结论:B()然后论证推理是否正确!同时{A1,A2,…,Ak}╞B换成A1∧A2∧…∧AkBDate6DiscreteMath.,ChenChen(1) 若a能被4整除,则a能被2整除。a能被4整除,所以 a能被2整除。(2)下午马芳或去看电影或去游泳。她没去看电影,所以她去游泳了。(3)若下午气温超过30℃,则王小燕必去游泳。若她去游泳,她就不去看电影了。所以,若王小燕没去看电影,下午气温必超过了30℃。解:(1)设p:a能被4整除;q:a能被2整除前提:p→q,p结论:q推理的形式结构:(p→q)∧p→,即(p→q)∧pq。。Date7DiscreteMath.,ChenChen(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可见((p∨q)∧┐p)→q是重言式,故(p∨q)∧┐p)q,推理正确。Date8DiscreteMath.,ChenChen(3)设p:下午超过30℃;q:王小燕去游泳;r:王小燕去看电影。前提:p→q,q→┐r结论:┐r→p推理形式结构:((p→q)∧(q→┐r))→(┐r→p)我们用主析取式法检验该蕴含式是否为重言式。((p→q)∧(q→┐r))→(┐r→p)┐((┐p∨q)∧(┐q∨┐r))∨(r∨p)((p∧┐q)∨(q∧r))∨r∨pp∨r两次吸收律(p∧┐q∧┐r)∨(p∧┐q∧r)∨(p∧q∧┐r)∨(p∧q∧r)∨(┐p∧┐q∧r)∨(┐p∧q∧r)∨(p∧┐q∧r)∨(p∧q∧r)((1))m1∨m3∨m4∨m5∨m6∨m7可见,主析取范式中少两个极小项m0和m2,从而推理不正确。Date9DiscreteMath.,ChenChen在研