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