数理逻辑的公理化理论

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第十二章 数理逻辑的公理化理论,12.1 公理化理论的基本思想,公理,:学科领域中最基本的原理与规则,公理系统,:以公理为基础所建立的基于一定语法规范的形式系统,公理系统一般由两部分内容组成:,组成部分:,基本符号：按学科要求建立,公式：由基本符号按一定语法规则组成,第十二章 数理逻辑的公理化理论,推理部分:系统中的公理,基本规则以及给出的系统中证明与定理的概念,公理：按学科要求给出推理中最基本的事实,基本规则：一种动态推理公式,分原始规则与导出规则,证明:是一种由公理及推理规则按一定语法规则所进行的动态过程,并产生一个公式串.,定理:由公理及推理规则按证明过程所得的结果,12.1 公理化理论的基本思想,1)系统的不矛盾性,系统的不矛盾性是对公理系统的最基本要求,2)系统的完备性,相对完备性:一个为某学科建立的公理系统,该学科中的所有定理和规则均能由系统推出,绝对完备性:一个公理系统中如果将任一个非定理的公式作为公理加入系统后,所得到的系统均为矛盾的系统,一个系统最好是完备的或相对完备的,但允许不完备,3)系统的独立性,系统中的每条公理均不能由其他公理推出,一个系统可以是不独立的,命题逻辑的公理化理论,命题逻辑永真公式的公理系统,1.系统的组成部分,1)基本符号,命题:P,Q,R,;,联结词:,括号:(,),2)公式,命题是公式,如P,Q是公式,则(PQ),(PQ),(PQ),(PQ)是公式,公式由且仅由有限次使用(1)(2)而得,命题逻辑的公理化理论,2.系统的推理部分,1)公理,如P,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),命题逻辑的公理化理论,(8)PQ Q,(9)PQ P,(10)P (QPQ),(11)P P,Q,(12),Q P,Q,(13),(QP)(RP)(Q,R,P),(14)(P,Q)(Q,P),(15),P P,命题逻辑的公理化理论,2)推理过程,分离规则:,PQ,PQ,3)证明与定理,证明给出了公理系统中定理生成的过程,它是一个公式序列:P,1,P,2,P,n,其中每个P,i,(i=1,2,n)必须满足下列的条件之一.,(1)P,i,是公理,(2)P,i,是由P,k,P,r,(k,ri)施行分离规则而得,最后P,n,=Q即为定理.,此公理系统是不矛盾,完备的(相对完备与绝对完备),但它不是独立.,命题逻辑的公理化理论,例12.1 试证P,Q Q,P,证明:,(1)Q,Q,P 公(12),(2)P Q,P 公(11),(3)(PQ,P)(QQ,P)(P,Q,Q,P),公(13),(4)(QQ,P)(P,Q,Q,P)分(3),(2),(5)P,Q Q,P 分(4),(1),证明的每一步后面都附有说明叫证明根据.,命题逻辑的公理化理论,只要公理系统中有蕴含式为公理,则可必可同时得到一个推理规则,由这种方法所推得的规则叫导出规则.,利用导出规则可以从前面15条公理得到15条导出规则:,规则1 P P,规则2 P(QR)Q(PR),规则3 PQ,QR PR,规则4 P(PQ)PQ,规则5 PQ PQ,规则6PQ QP,命题逻辑的公理化理论,规则7 PQ,QP PQ,规则8 PQ Q,规则9 PQ P,规则10 P,Q PQ,规则11 P P,Q,规则,12,Q P,Q,规则,13,QP,RP Q,R,P,规则14 P,Q Q,P,规则15,P P,命题逻辑的公理化理论,定理12.1,推理定理,设有A,1,A,2,A,n,B,则必有,A,1,A,2,A,n-1,A,n,B,推论,设有A,1,A,2,A,n,B,则必有,A,1,(A,2,(A,n,B),此定理说明,为证明一个带蕴含的公式,只要证明它的最后一个后件即成,而其所有前件(称为假设前提)均可作为已知条件(作为定理)使用,这种方法叫做,假设推理方法,.,命题逻辑的公理化理论,假设推理方法的证明过程:,证明过程是一个公式序列:P,1,P,2,P,n,其中每个P,i,(i=1,2,n)必须满足下列的条件之一.,(1)P,i,是假设前提,(2)P,i,是公理,(3)P,i,是由P,k,P,r,(k,ri)施行分离规则而得,最后P,n,=Q即为定理.,命题逻辑的公理化理论,例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,谓词逻辑的公理化理论,谓词逻辑永真公式的公理系统,推理部分,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,谓词逻辑的公理化理论,3)证明与定理,证明是一个公式序列:P,1,P,2,P,n,其中每个P,i,(i=1,2,n)必须满足下列的条件之一.,(1)P,i,是公理,(2)P,i,是由P,k,P,r,(k,ri)施行分离规则而得,(3)P,i,是由P,k,(ki)施行全称规则而得,(4)P,i,是由P,k,(ki)施行全称规则而得,最后P,n,=Q即为定理.,谓词逻辑的公理化理论,4)全称规则另外的形式,P(x)xP(x)(全称推广规则:UG),规则16 xP(x)P(x)(全称指定规则:US),规则17 P(x)P(x)(存在推广规则:EG),定理12.2,谓词逻辑推理定理,设有R,1,R,2,R,n,Q,且在推理过程中对R,i,(i=1,2,n)不作代入,各R,i,至少被使用一次且在施行全称规则、存在规则时绝不对各Ri中的自由变元进行,则必有,R,1,R,2,R,n-1,R,n,Q,谓词逻辑的公理化理论,推论,设有R,1,R,2,R,n,Q,且在推理过程中对R,i,(i=1,2,n)不作代入,各R,i,至少被使用一次且在施行全称规则、存在规则时绝不对各Ri中的自由变元进行,则必有,R,1,(R,2,(R,n,Q),规则18,xP(x)P(e)(存在指定规则:ES),此规则中e叫额外变元,它是一种额外假设的自由变元,它的变化范围是使对xP(x)成立的x.,谓词逻辑的公理化理论,可充分应用UG,US,EG,ES四条规则,通过US,ES将公式中的量词全部除去,从而得到一个命题逻辑公式，然后用命题逻辑方法推理,在最后得到结论前利用UG,EG重新加入量词，恢复成谓词逻辑公式.,使用UG时需遵守:,1)对假设前提中所出现的自由变元不能使用此规则,2)对额外变元不能使用此规则,3)一公式中含有额外变元则对此公式中的自由变元亦不能使用此规则.,使用ES需遵守:,不同额外变元需用不同符号表示,而且不能互相代入.,谓词逻辑的公理化理论,例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),