离散数学03.命题逻辑 推理理论ppt课件.ppt

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

1、§3.1推理的形式结构§3.2自然推理系统第三章命题逻辑的推理理论数理逻辑用数学的方法来研究推理.推理是由前提(应用推理规则)得出结论的过程={A1,A2,…,Ak}B.其中前提是命题公式的集合,结论是一个命题公式.若对于命题变元的任意一组赋值,(1)A1A2…Ak为假;或者(2)当A1A2…Ak为真时,B也为真,则称推理B是有效的,称B是的有效结论:B.否则是无效的:B./deduction/hypothesis/conclusion/valid/invalid†B表示一个推理,而B表示该推理是有效的.††B不意味着结论B为真.对于任

2、何一组赋值,前提和结论的取值情况有:只要不出现情况③,推理就是有效的.A1A2…AkB①00②01③10④11例1判断下列推理是否有效:(1){p,pq}q;(2){p,qp}q.解是否出现前提合取式为真,而结论为假的情况?(1){p,pq}q.1111101000010000p(qp)p(pq)pq(2){p,qp}q.1010q定理(有效推理的等价定理)命题公式A1,A2,…,Ak推B是有效的当且仅当(A1A2…Ak)B为重言式.证明略前提：A1，A2，…，Ak结论：B†蕴涵关系式HC表示条件式HC是重言式.形式结构推理有效性的判断

3、即对其形式结构(是一个命题公式)永真性的判断.方法有①真值表法,②等值演算法,③主析取范式法.例2判断下面推理是否正确:(1)他要么打球要么游泳;他没打球.所以他去游泳了.(等值演算法)(2)出了事他一定在场;他在场就不会闲着.所以他没闲着就一定出事了.(主析取范式法)解(1)设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.可见推理有效.(2)出了事他一定在场;他在场就不会闲着.所以他没闲着就一定出事了.设p:出事了;q:

4、他在场;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rp(用两次吸收律)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)m1m3m4m5m6m7(重排了序)这不是重言式,所以推理无效.推理定律（蕴涵关系式）1.A(AB)附加律2.(AB)A化简律3.(AB)AB假言推理4.(AB)BA拒取式5.(

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)构造性二难(AB)(AB)(AA)B构造性二难(特殊形式)9.(AB)(CD)(BD)(AC)破坏性二难例3证明拒取式:(AB)BA证(AB)BA((AB)B)A((AB)BA)((ABA)(BBA))(00)1.①上列推理定律都可以看成是模式:有无穷多的代换实例.②等值符与蕴涵符的关系:

6、AB当且仅当AB,BA,③常用等值式中的每一个都派生出两条运算律.例如吸收律AÚ(AÙB)ÛA派生两条推理定律:AÚ(AÙB)A和AAÚ(AÙB).§3.1推理的形式结构§3.2自然推理系统第三章命题逻辑的推理理论推理有效性的判断可以转换为对其形式结构(命题公式)永真性的判断,运用真值表,等值演算和主析取范式的方法.当命题变项较多时,计算量较大.下面给出一种形式系统,使得严谨的证明可以在其中进行.证明是一个描述推理过程的命题公式的序列,其中的每个公式都是按推理规则写出的(最后一个是推理的结论,其余叫中间结论).={A1,A2,…,Ak}B.定义3.2一个形式系统I

7、由下面四个部分组成:(1)非空的字符表,记作A(I).(2)A(I)中符号构造的合式公式集,记作E(I).(3)E(I)中一些特殊的公式组成的公理集,记作AX(I).(4)推理规则集,记作R(I).A=alphabet,E=equation,AX=axiom,R=rule.形式系统I=A(I),E(I),AX(I),R(I),其中A(I),E(I)是I的语言系统,AX(I),R(I)为I的演算系统.形式系统可分为两类.自然推理系统从任意给定的前提出发,得到的结论可能是重言式,也可