第十二章 数理逻辑公理化理论

《第十二章 数理逻辑公理化理论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十二章数理逻辑的公理化理论12.1公理化理论的基本思想公理:学科领域中最基本的原理与规则公理系统:以公理为基础所建立的基于一定语法规范的形式系统公理系统一般由两部分内容组成:组成部分:基本符号：按学科要求建立公式：由基本符号按一定语法规则组成第十二章数理逻辑的公理化理论推理部分:系统中的公理,基本规则以及给出的系统中证明与定理的概念公理：按学科要求给出推理中最基本的事实基本规则：一种动态推理公式,分原始规则与导出规则证明:是一种由公理及推理规则按一定语法规则所进行的动态过程,并产生一个公式串.定理:由公理及推理规则按证明过程所得的结果12.1公理

2、化理论的基本思想1)系统的不矛盾性系统的不矛盾性是对公理系统的最基本要求2)系统的完备性相对完备性:一个为某学科建立的公理系统,该学科中的所有定理和规则均能由系统推出绝对完备性:一个公理系统中如果将任一个非定理的公式作为公理加入系统后,所得到的系统均为矛盾的系统一个系统最好是完备的或相对完备的,但允许不完备3)系统的独立性系统中的每条公理均不能由其他公理推出一个系统可以是不独立的12.2.1命题逻辑的公理化理论命题逻辑永真公式的公理系统1.系统的组成部分1)基本符号命题:P,Q,R,…;联结词:¬,∧,∨,→,↔括号:(,)2)公式命题是公式如P,

3、Q是公式,则(P∧Q),(P∨Q),(P→Q),(P↔Q)是公式公式由且仅由有限次使用(1)(2)而得12.2.1命题逻辑的公理化理论2.系统的推理部分1)公理如P,Q,R为公式,则有下述的公理:(1)P→P(2)(P→(Q→R))→(Q→(P→R))(3)(P→Q)→((Q→R)→(P→R))(4)(P→(P→Q))→(P→Q)(5)(P↔Q)→(P→Q)(6)(P↔Q)→(Q→P)(7)(P→Q)→((Q→P)→(P↔Q))12.2.1命题逻辑的公理化理论(8)P∧Q→Q(9)P∧Q→P(10)P→(Q→P∧Q)(11)P→P∨Q(12)Q→P

4、∨Q(13)(Q→P)→((R→P)→(Q∨R→P))(14)(P→¬Q)→(Q→¬P)(15)¬¬P→P12.2.1命题逻辑的公理化理论2)推理过程分离规则:P→Q,P├Q3)证明与定理证明给出了公理系统中定理生成的过程,它是一个公式序列:P1,P2,…,Pn,其中每个Pi(i=1,2,…,n)必须满足下列的条件之一.(1)Pi是公理(2)Pi是由Pk,Pr(k,r

5、Q∨P公(12)(2)P→Q∨P公(11)(3)(P→Q∨P)→((Q→Q∨P)→(P∨Q→Q∨P))公(13)(4)((Q→Q∨P)→(P∨Q→Q∨P))分(3),(2)(5)P∨Q→Q∨P分(4),(1)证明的每一步后面都附有说明叫证明根据.12.2.1命题逻辑的公理化理论只要公理系统中有蕴含式为公理,则可必可同时得到一个推理规则,由这种方法所推得的规则叫导出规则.利用导出规则可以从前面15条公理得到15条导出规则:规则1P├P规则2P→(Q→R)├Q→(P→R)规则3P→Q,Q→R├P→R规则4P→(P→Q)├P→Q规则5P↔Q├P→Q规则6

6、P↔Q├Q→P12.2.1命题逻辑的公理化理论规则7P→Q,Q→P├P↔Q规则8P∧Q├Q规则9P∧Q├P规则10P,Q├P∧Q规则11P├P∨Q规则12Q├P∨Q规则13Q→P,R→P├Q∨R→P规则14P→¬Q├Q→¬P规则15¬¬P├P12.2.1命题逻辑的公理化理论定理12.1推理定理设有A1,A2,…,An├B,则必有A1,A2,…,An-1├An→B推论设有A1,A2,…,An├B,则必有├A1→(A2→(…(An→B))…)此定理说明,为证明一个带蕴含的公式,只要证明它的最后一个后件即成,而其所有前件(称为假设前提)均可作为已知条件(

7、作为定理)使用,这种方法叫做假设推理方法.12.2.1命题逻辑的公理化理论假设推理方法的证明过程:证明过程是一个公式序列:P1,P2,…,Pn,其中每个Pi(i=1,2,…,n)必须满足下列的条件之一.(1)Pi是假设前提(2)Pi是公理(3)Pi是由Pk,Pr(k,r

8、规则1012.2.2谓词逻辑的公理化理论谓词逻辑永真公式的公理系统推理部分1)公理(16)∀xP(x)→P(x)(17)P