数理逻辑的公理化理论.ppt

《数理逻辑的公理化理论.ppt》由会员分享，可在线阅读，更多相关《数理逻辑的公理化理论.ppt（20页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关于数理逻辑的公理化理论关于数理逻辑的公理化理论现在学习的是第1页，共20页第十二章 数理逻辑的公理化理论 推理部分:系统中的公理,基本规则以及给出的系统中证明与定理的概念 公理：按学科要求给出推理中最基本的事实 基本规则：一种动态推理公式,分原始规则与导出规则 证明:是一种由公理及推理规则按一定语法规则所进行的动态过程,并产生一个公式串.定理:由公理及推理规则按证明过程所得的结果现在学习的是第2页，共20页12.1 公理化理论的基本思想1)系统的不矛盾性 系统的不矛盾性是对公理系统的最基本要求2)系统的完备性 相对完备性:一个为某学科建立的公理系统,该学科中的所有定理和规则均能由系统推出 绝

2、对完备性:一个公理系统中如果将任一个非定理的公式作为公理加入系统后,所得到的系统均为矛盾的系统 一个系统最好是完备的或相对完备的,但允许不完备3)系统的独立性 系统中的每条公理均不能由其他公理推出 一个系统可以是不独立的现在学习的是第3页，共20页12.2.1 命题逻辑的公理化理论命题逻辑永真公式的公理系统1.系统的组成部分1)基本符号 命题:P,Q,R,;联结词:,括号:(,)2)公式 命题是公式 如P,Q是公式,则(PQ),(PQ),(PQ),(PQ)是公式 公式由且仅由有限次使用(1)(2)而得现在学习的是第4页，共20页12.2.1 命题逻辑的公理化理论2.系统的推理部分1)公理如P,

3、Q,R为公式,则有下述的公理:(1)P P(2)(P(QR)(Q(PR)(3)(PQ)(QR)(PR)(4)(P(PQ)(PQ)(5)(PQ)(PQ)(6)(PQ)(QP)(7)(PQ)(QP)(PQ)现在学习的是第5页，共20页12.2.1 命题逻辑的公理化理论(8)PQ Q(9)PQ P(10)P (QPQ)(11)P PQ(12)Q PQ(13)(QP)(RP)(QRP)(14)(PQ)(QP)(15)P P现在学习的是第6页，共20页12.2.1 命题逻辑的公理化理论2)推理过程分离规则:PQ,PQ3)证明与定理证明给出了公理系统中定理生成的过程,它是一个公式序列:P1,P2,Pn,其

4、中每个Pi(i=1,2,n)必须满足下列的条件之一.(1)Pi是公理(2)Pi是由Pk,Pr(k,ri)施行分离规则而得最后Pn=Q即为定理.此公理系统是不矛盾,完备的(相对完备与绝对完备),但它不是独立.现在学习的是第7页，共20页12.2.1 命题逻辑的公理化理论例12.1 试证PQ QP证明:(1)Q QP 公(12)(2)P QP 公(11)(3)(PQP)(QQP)(PQQP)公(13)(4)(QQP)(PQQP)分(3),(2)(5)PQ QP 分(4),(1)证明的每一步后面都附有说明叫证明根据.现在学习的是第8页，共20页12.2.1 命题逻辑的公理化理论只要公理系统中有蕴含式

5、为公理,则可必可同时得到一个推理规则,由这种方法所推得的规则叫导出规则.利用导出规则可以从前面15条公理得到15条导出规则:规则1 P P规则2 P(QR)Q(PR)规则3 PQ,QR PR规则4 P(PQ)PQ规则5 PQ PQ规则6PQ QP现在学习的是第9页，共20页12.2.1 命题逻辑的公理化理论规则7 PQ,QP PQ规则8 PQ Q规则9 PQ P规则10 P,Q PQ规则11 P PQ规则12 Q PQ规则13 QP,RP QRP规则14 PQ QP规则15 P P现在学习的是第10页，共20页12.2.1 命题逻辑的公理化理论定理12.1 推理定理设有A1,A2,An B,则

6、必有 A1,A2,An-1 An B 推论设有A1,A2,An B,则必有 A1(A2(AnB)此定理说明,为证明一个带蕴含的公式,只要证明它的最后一个后件即成,而其所有前件(称为假设前提)均可作为已知条件(作为定理)使用,这种方法叫做假设推理方法.现在学习的是第11页，共20页12.2.1 命题逻辑的公理化理论假设推理方法的证明过程:证明过程是一个公式序列:P1,P2,Pn,其中每个Pi(i=1,2,n)必须满足下列的条件之一.(1)Pi是假设前提(2)Pi是公理(3)Pi是由Pk,Pr(k,ri)施行分离规则而得最后Pn=Q即为定理.现在学习的是第12页，共20页12.2.1 命题逻辑的公

7、理化理论例12.5:试证(PQ)(PR)(PQR)证明:即证:PQ,PR,P QR(1)PQ假设前提(2)PR 假设前提(3)P假设前提(4)Q分(1)(3)(5)R分(2)(3)(6)QR规则10现在学习的是第13页，共20页12.2.2 谓词逻辑的公理化理论谓词逻辑永真公式的公理系统推理部分1)公理(16)xP(x)P(x)(17)P(x)P(x)2)推理规则(1)分离规则:PQ,P Q(2)全称规则:QP(x)QxP(x)(3)存在规则:P(x)Q xP(x)Q 现在学习的是第14页，共20页12.2.2 谓词逻辑的公理化理论3)证明与定理证明是一个公式序列:P1,P2,Pn,其中每个P

8、i(i=1,2,n)必须满足下列的条件之一.(1)Pi是公理(2)Pi是由Pk,Pr(k,ri)施行分离规则而得(3)Pi是由Pk(ki)施行全称规则而得(4)Pi是由Pk(ki)施行全称规则而得最后Pn=Q即为定理.现在学习的是第15页，共20页12.2.2 谓词逻辑的公理化理论4)全称规则另外的形式P(x)xP(x)(全称推广规则:UG)规则16 xP(x)P(x)(全称指定规则:US)规则17 P(x)P(x)(存在推广规则:EG)定理12.2 谓词逻辑推理定理设有R1,R2,Rn Q,且在推理过程中对Ri(i=1,2,n)不作代入,各Ri至少被使用一次且在施行全称规则、存在规则时绝不对

9、各Ri中的自由变元进行,则必有 R1,R2,Rn-1 Rn Q现在学习的是第16页，共20页12.2.2 谓词逻辑的公理化理论 推论设有R1,R2,Rn Q,且在推理过程中对Ri(i=1,2,n)不作代入,各Ri至少被使用一次且在施行全称规则、存在规则时绝不对各Ri中的自由变元进行,则必有 R1(R2(RnQ)规则18 xP(x)P(e)(存在指定规则:ES)此规则中e叫额外变元,它是一种额外假设的自由变元,它的变化范围是使对xP(x)成立的x.现在学习的是第17页，共20页12.2.2 谓词逻辑的公理化理论可充分应用UG,US,EG,ES四条规则,通过US,ES将公式中的量词全部除去,从而得

10、到一个命题逻辑公式，然后用命题逻辑方法推理,在最后得到结论前利用UG,EG重新加入量词，恢复成谓词逻辑公式.使用UG时需遵守:1)对假设前提中所出现的自由变元不能使用此规则2)对额外变元不能使用此规则3)一公式中含有额外变元则对此公式中的自由变元亦不能使用此规则.使用ES需遵守:不同额外变元需用不同符号表示,而且不能互相代入.现在学习的是第18页，共20页12.2.2 谓词逻辑的公理化理论例12.7:试证 x(P(x)Q(x)(xP(x)xQ(x)证明:只要证明x(P(x)Q(x),xP(x)xQ(x)(1)x(P(x)Q(x)假设前提(2)P(x)Q(x)US(1)(3)xP(x)假设前提(4)P(x)US(3)(5)Q(x)分(2)(4)(6)xQ(x)UG(5)现在学习的是第19页，共20页感谢大家观看感谢大家观看现在学习的是第20页，共20页