离散数学 第三章 命题逻辑的推理理论课件.ppt

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

1、漳州师范学院计算机科学与工程系第三章命题逻辑的推理理论2021/7/311第三章命题逻辑的推理理论推理的形式结构自然推理系统P知识点：推理的形式结构、推理理论、自然系统P、推理规则教学要求：深刻理解和掌握命题逻辑中的基本推理方法教学重点：推理理论、推理规则学时:22021/7/312§3.1推理的形式结构数理逻辑的主要任务是用数学的方法研究推理什么是推理形式?一组前提,一个结论前提、结论都是命题若前提为A1,A2,…,An，结论为B，则将这样的推理形式称为A1,A2,…,An推出B要研究推理，首先应该明确什么样的推理是有效的或正确的。直观上，正确的推

2、理应该保证：如果前提正确，则结论也应该正确2021/7/313§3.1推理的形式结构定义3.1设A1,A2,…,Ak和B都是命题公式，若对于A1,A2,…,Ak和B中出现的命题变项的任意一组赋值，（1）或者A1∧A2∧…∧Ak为假;（2）或者当A1∧A2∧…∧Ak为真时，B也为真;则称由前提A1,A2,…,Ak推出结论B的推理是有效的或正确的，并称B是有效结论。例AB、A推出B是有效的A∨B、┐A推出B是有效的2021/7/314关于有效推理的说明由前提A1，A2，…，Ak推结论B的推理是否正确与诸前提的排列次序无关。即若“A1，A2，…，A

3、k推出B”是有效的，则对1，2，…，k的任一个排列i1，i2，…，ik，“Ai1，Ai2，…，Aik推出B”也是有效的，所以前提是一个集合，而不是一个序列＝{A1，A2，…，Ak}由推B的推理记为┣B若推理是正确的，记为╞B若推理是不正确的，记为B这里称┣B或{A1，A2，…，Ak}┣B为推理的形式结构2021/7/315关于有效推理的说明设A1，A2，…，Ak，B中共出现n个命题变项，对于任何一组赋值α1α2…αn(αi=0或者1，i=1,2,…,n),前提和结论的取值情况有以下四种：(1)A1∧A2∧…∧Ak为0，B为0。(2

4、)A1∧A2∧…∧Ak为0，B为1。(3)A1∧A2∧…∧Ak为1，B为0。(4)A1∧A2∧…∧Ak为1，B为1。只要不出现(3)中的情况，推理就是正确的，因而判断推理是否正确，就是判断是否会出现(3)中的情况。推理正确，并不能保证结论B一定为真。例如：设p为“太阳从西边升起”,q为”太阳从东边落下”pq为“如果太阳从西边升起则太阳从东边落下”推理{p,pq}┝q是正确的,即q是前提的有效结论,但q是个假命题2021/7/316§3.1推理的形式结构(1){p,p→q}├q(2){p,q→p}├q例3.1判断下列推理是否正确。（真值表法）p

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

6、分性。若蕴涵式A1∧A2∧…∧Ak→B为重言式，则对于任何赋值此蕴涵式均为真，因而不会出现前件为真后件为假的情况，即在任何赋值下，或者A1∧A2∧…∧Ak为假，或者A1∧A2∧…∧Ak和B同时为真，这正符合推理正确的定义。2021/7/319推理的形式结构当推理正确时，形式（1）记为╞B。形式（2）记为A1A2…AkB。表示蕴涵式为重言式。推理的形式结构设={A1,A2,…,Ak}，记为┣B。A1A2…AkB前提：A1,A2,…,Ak结论：B说明2021/7/3110判断推理是否正确的方法真值表法等值演算法主析取范式法是否有其

7、他的证明方法？思考当命题变项较少时,这三种方法比较方便。说明2021/7/3111例题（1）下午马芳或去看电影或去游泳。她没去看电影，所以，她去游泳了。例3.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由定理3.1可知，推理正确。2021/7/3112（2）若今天是1号，则明天是5号。明天是5号，所以今天是1

8、号。例判断下列推理是否正确。（主析取范式法）(pq)qp(pq)qp((pq)q)