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

第十二章数理逻辑的公理化理论第1页，共19页，2023年，2月20日，星期三第十二章数理逻辑的公理化理论推理部分:系统中的公理,基本规则以及给出的系统中证明与定理的概念公理：按学科要求给出推理中最基本的事实基本规则：一种动态推理公式,分原始规则与导出规则证明:是一种由公理及推理规则按一定语法规则所进行的动态过程,并产生一个公式串.定理:由公理及推理规则按证明过程所得的结果第2页，共19页，2023年，2月20日，星期三12.1公理化理论的基本思想1)系统的不矛盾性系统的不矛盾性是对公理系统的最基本要求2)系统的完备性相对完备性:一个为某学科建立的公理系统,该学科中的所有定理和规则均能由系统推出绝对完备性:一个公理系统中如果将任一个非定理的公式作为公理加入系统后,所得到的系统均为矛盾的系统一个系统最好是完备的或相对完备的,但允许不完备3)系统的独立性系统中的每条公理均不能由其他公理推出一个系统可以是不独立的第3页，共19页，2023年，2月20日，星期三12.2.1命题逻辑的公理化理论命题逻辑永真公式的公理系统1.系统的组成部分 1)基本符号命题:P,Q,R,…;联结词:¬,∧,∨,→,↔括号:(,) 2)公式命题是公式如P,Q是公式,则(P∧Q),(P∨Q),(P→Q),(P↔Q)是公式公式由且仅由有限次使用(1)(2)而得第4页，共19页，2023年，2月20日，星期三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))第5页，共19页，2023年，2月20日，星期三12.2.1命题逻辑的公理化理论 (8)P∧Q→Q (9)P∧Q→P (10)P→(Q→P∧Q) (11)P→P∨Q (12)Q→P∨Q (13)(Q→P)→((R→P)→(Q∨R→P)) (14)(P→¬Q)→(Q→¬P) (15)¬¬P→P第6页，共19页，2023年，2月20日，星期三12.2.1命题逻辑的公理化理论2)推理过程 分离规则:P→Q,P├Q3)证明与定理 证明给出了公理系统中定理生成的过程,它是一个公式序列:P1,P2,…,Pn,其中每个Pi(i=1,2,…,n)必须满足下列的条件之一. (1)Pi是公理 (2)Pi是由Pk,Pr(k,r<i)施行分离规则而得 最后Pn=Q即为定理. 此公理系统是不矛盾,完备的(相对完备与绝对完备),但它不是独立.第7页，共19页，2023年，2月20日，星期三12.2.1命题逻辑的公理化理论例12.1试证P∨Q→Q∨P证明: (1)Q→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) 证明的每一步后面都附有说明叫证明根据.第8页，共19页，2023年，2月20日，星期三12.2.1命题逻辑的公理化理论只要公理系统中有蕴含式为公理,则可必可同时得到一个推理规则,由这种方法所推得的规则叫导出规则.利用导出规则可以从前面15条公理得到15条导出规则: 规则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第9页，共19页，2023年，2月20日，星期三12.2.1命题逻辑的公理化理论 规则7 P→Q,Q→P├P↔Q 规则8 P∧Q├Q 规则9 P∧Q├P 规则10 P,Q├P∧Q 规则11 P├P∨Q

规则12 Q├P∨Q

规则13 Q→P,R→P├Q∨R→P 规则14 P→¬Q├Q→¬P 规则15 ¬¬P├P第10页，共19页，2023年，2月20日，星期三12.2.1命题逻辑的公理化理论定理12.1推理定理 设有A1,A2,…,An├B,则必有 A1,A2,…,An-1├An→B推论 设有A1,A2,…,An├B,则必有 ├A1→(A2→(…(An→B))…)此定理说明,为证明一个带蕴含的公式,只要证明它的最后一个后件即成,而其所有前件(称为假设前提)均可作为已知条件(作为定理)使用,这种方法叫做假设推理方法.第11页，共19页，2023年，2月20日，星期三12.2.1命题逻辑的公理化理论假设推理方法的证明过程: 证明过程是一个公式序列:P1,P2,…,Pn,其中每个Pi(i=1,2,…,n)必须满足下列的条件之一. (1)Pi是假设前提 (2)Pi是公理 (3)Pi是由Pk,Pr(k,r<i)施行分离规则而得 最后Pn=Q即为定理.第12页，共19页，2023年，2月20日，星期三12.2.1命题逻辑的公理化理论例12.5:试证(P→Q)→((P→R)→(P→Q∧R))证明: 即证:P→Q,P→R,P├Q∧R (1)P→Q 假设前提 (2)P→R 假设前提 (3)P 假设前提 (4)Q 分(1)(3) (5)R 分(2)(3) (6)Q∧R 规则10第13页，共19页，2023年，2月20日，星期三12.2.2谓词逻辑的公理化理论谓词逻辑永真公式的公理系统推理部分1)公理 (16)∀xP(x)→P(x) (17)P(x)→∃P(x)2)推理规则 (1)分离规则:P→Q,P├Q (2)全称规则:Q→P(x)├Q→∀xP(x) (3)存在规则:P(x)→Q├∃xP(x)→Q第14页，共19页，2023年，2月20日，星期三12.2.2谓词逻辑的公理化理论3)证明与定理 证明是一个公式序列:P1,P2,…,Pn,其中每个Pi(i=1,2,…,n)必须满足下列的条件之一. (1) Pi是公理 (2) Pi是由Pk,Pr(k,r<i)施行分离规则而得 (3) Pi是由Pk(k<i)施行全称规则而得 (4) Pi是由Pk(k<i)施行全称规则而得 最后Pn=Q即为定理.第15页，共19页，2023年，2月20日，星期三12.2.2谓词逻辑的公理化理论4)全称规则另外的形式 P(x)├∀xP(x) (全称推广规则:UG) 规则16∀xP(x)├P(x) (全称指定规则:US) 规则17P(x)├∃P(x) (存在推广规则:EG)定理12.2谓词逻辑推理定理 设有R1,R2,…,Rn├Q,且在推理过程中对Ri(i=1,2,…,n)不作代入,各Ri至少被使用一次且在施行全称规则、存在规则时绝不对各Ri中的自由变元进行,则必有 R1,R2,…,Rn-1├Rn→Q第16页，共19页，2023年，2月20日，星期三12.2.2谓词逻辑的公理化理论推论 设有R1,R2,…,Rn├Q,且在推理过程中对Ri(i=1,2,…,n)不作代入,各Ri至少被使用一次且在施行全称规则、存在规则时绝不对各Ri中的自由变元进行,则必有 ├R1→(R2→(…(Rn→Q))…)规则18

∃xP(x)├P(e)(存在指定规则:ES)此规则中e叫额外变元,它是一种额外假设的自由变元,它的变化范围是使对∃xP(x)成立的x.第17页，共19页，2023年，2月20日，星期三12.2.2谓词逻辑的公理化理论可充分应用UG,US,EG,ES四条规则,通过US,ES将公式中的量词全部除去,从而得到一个命题逻辑公式，然后用命题逻辑方法推理,在最后得到结论前利用UG,EG重新加入量词，恢复成谓词逻辑公式.使用UG时需遵守:1)对假设前提中所出现的自由变元不能使用此规则2)对额外变元不能使用此规则3)一公式中含有额外变元则对此公式中的自由变元亦不能使用此规则.使用ES需遵守:不同额外变元需用不同符号表示,而且不能互相代入.第18页，共19页，2023年，2月20日，星期三12.2.2谓词逻辑的公理化理论例12.7:试证∀x(P(x)→Q(x)