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

第十二章数理逻辑的公理化理论 12 1公理化理论的基本思想公理 学科领域中最基本的原理与规则公理系统 以公理为基础所建立的基于一定语法规范的形式系统公理系统一般由两部分内容组成 组成部分 基本符号 按学科要求建立公式 由基本符号按一定语法规则组成 第十二章数理逻辑的公理化理论 推理部分 系统中的公理 基本规则以及给出的系统中证明与定理的概念公理 按学科要求给出推理中最基本的事实基本规则 一种动态推理公式 分原始规则与导出规则证明 是一种由公理及推理规则按一定语法规则所进行的动态过程 并产生一个公式串 定理 由公理及推理规则按证明过程所得的结果 12 1公理化理论的基本思想 1 系统的不矛盾性系统的不矛盾性是对公理系统的最基本要求2 系统的完备性相对完备性 一个为某学科建立的公理系统 该学科中的所有定理和规则均能由系统推出绝对完备性 一个公理系统中如果将任一个非定理的公式作为公理加入系统后 所得到的系统均为矛盾的系统一个系统最好是完备的或相对完备的 但允许不完备3 系统的独立性系统中的每条公理均不能由其他公理推出一个系统可以是不独立的 12 2 1命题逻辑的公理化理论 命题逻辑永真公式的公理系统1 系统的组成部分1 基本符号命题 P Q R 联结词 括号 2 公式命题是公式如P 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 Q 13 Q P R P Q R P 14 P Q Q P 15 P P 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即为定理 此公理系统是不矛盾 完备的 相对完备与绝对完备 但它不是独立 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 证明的每一步后面都附有说明叫证明根据 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规则6P Q Q P 12 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 P 12 2 1命题逻辑的公理化理论 定理12 1推理定理设有A1 A2 An B 则必有A1 A2 An 1 An B推论设有A1 A2 An B 则必有 A1 A2 An B 此定理说明 为证明一个带蕴含的公式 只要证明它的最后一个后件即成 而其所有前件 称为假设前提 均可作为已知条件 作为定理 使用 这种方法叫做假设推理方法 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 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 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 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即为定理 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 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 12 2 2谓词逻辑的公理化理论 可充分应用UG US EG ES四条规则 通过US ES将公式中的量词全部除去 从而得到一个命题逻辑公式 然后用命题逻辑方法推理 在最后得到结论前利用UG EG重新加入量词 恢复成谓词逻辑公式 使用UG时需遵守 1 对假设前提中所出现的自由变元不能使用此规则2 对额外变元不能使用此规则3 一公式中含有额外变元则对此公式中的自由变元亦不能使用此规则 使用ES需遵守 不同额外变元需用不同符号表示 而且不能互相代入 12 2 2谓词逻