信息与计算科学毕业设计

1、安徽建筑工业学院安徽建筑工业学院 毕 业 设 计 (论 文) 专专 业业 信息与计算科学信息与计算科学 班班 级级 07 信息（信息（2）班）班 学生姓名学生姓名 汪保来汪保来 学学 号号 07207010214 课课 题题 不同逻辑间翻译的完备性不同逻辑间翻译的完备性 指导教师指导教师 王焕宝王焕宝 2011 年年 5 月月 31 日日 不同逻辑间翻译的完备性 汪保来 (安徽建筑工业学院数理系，合肥 230022) 摘要摘要: 数理逻辑是用数学方法来研究推理的形式结构和推理规律的数学学科.它与数 学的其他分支、计算机科学、人工智能、语言学等学科均有密切的联系，它日益显示 出它的重要作用和更加

2、广泛的应用前景.数理逻辑是形式逻辑与数学思想结合的产物但 数理逻辑研究的是各学科共同遵从的一般性的逻辑规律，而各门学科只研究自身的具 体规律. 本论文讨论了在论域有限的情况下，命题逻辑与一阶逻辑的关系.该文提出了语 义忠实和语义满两条逻辑性质来确保可满足的公式翻译为可满足的公式，不可满足公 式翻译翻译为不可满足公式.本文说明了在 henkin 语义下，二阶逻辑到一阶逻辑的翻 译是满足完备性的. 关键字关键字: : 完备性；语义忠实翻译；语义满翻译；二阶逻辑；一阶逻辑 logical completeness on translation between different logical ab

3、stract mathematical logic is to use mathematical methods to study the structure and reasoning in the form of the law of mathematics reasoning. it with other branches of mathematics, computer science, artificial intelligence, linguistics and other subjects are closely linked, it is increasingly shows

4、 its important role and a more broad application prospects. mathematical logic is the product of the combination of formal logic and mathematical thinking, but mathematical logic is the study of various disciplines together to comply with the general laws of logic, but all subjects only research the

5、ir own specific rules. the situation of this paper discusses the domain limited , the relationship between propositional logic and first-order logic. in this paper, two logic properties: the failthfulness and the fullness are defined to ensure the preservations of the satisfiability and the unsatisf

6、iability. in this paper, translation between second-order logic and first-order logic meets completeness in henkin semantics. key words completeness; faithful translation; full translation; second-order logic; first- order 目目 录录 摘要摘要.ii abstract .iii 第一章第一章 绪论绪论.1 1.1 课题背景.1 1.2 主要问题及研究意义.1 第二章第二章 命

7、题逻辑与一阶逻辑命题逻辑与一阶逻辑.3 2.1 命题符号化及联结词.3 2.2 命题公式及分类.4 2.3 一阶逻辑基本概念.4 2.4 量词.5 2.5 一阶逻辑的合式公式.5 2.6 一阶逻辑的模型及赋值.6 2.7 命题逻辑与一阶逻辑的关系.6 2.7.1总体说明两者的关系.6 2.7.2分析一阶逻辑与命题逻辑间的公式间的关系.6 2.7.3实例讨论一阶逻辑与命题逻辑间的关系.7 第三章第三章 二阶逻辑二阶逻辑.9 3.1 二阶逻辑的简介.9 3.2 二阶逻辑到一阶逻辑的翻译的性质.11 3.2.1 性质的介绍及证明.11 3.2.2 完备性定理.12 3.2.3 二阶逻辑到一阶逻辑翻译

8、的完备性的分析.17 第四章第四章 总结与展望总结与展望.18 4.1 总结.18 4.2 展望.18 参考文献参考文献.19 致谢致谢.20 第一章第一章 绪论绪论 1.1 课题背景 数理逻辑这门学科建立以后，发展比较迅速，促进它发展的因素也是多 方面的.比如，非欧几何的建立，促使人们去研究非欧几何和欧氏几何的无 矛盾性. 数理逻辑近年来发展特别迅速，主要原因是这门学科对于数学其它分支 如集合论、数论、代数、拓扑学等的发展有重大的影响，特别是对新近形成 的计算机科学的发展起了推动作用 .反过来，其他学科的发展也推动了数理 逻辑的发展. 正因为它是以门新近兴起而又发展很快的学科，所以它本身也存

9、在许多 问题有待于深入研究 .现在许多数学家正针对数理逻辑本身的问题进行研究. 人工智能逻辑方面的研究很广阔，一般说来，所有的哲学逻辑都是人工智 能逻辑，方向上涉及心理学、认知、决策、计算机等等都可以，数理逻辑和模 态逻辑是它的基础. 在人工智能知识表示领域根据不同的实际应用需求，人们可以使用多种不 同的式工具表示知识.比如：直觉多值逻辑，模糊模态逻辑，描述逻辑等等.表 达能力和推理任务是一个逻辑的两个重要的特征.面对这些不同形式的逻辑，如 何比较它们在表达能力和推理任务上的差异，目前通常的做法是建立两个逻辑 间的翻译，即把一个逻辑（源逻辑）翻译到另一个逻辑（目标逻辑）之上，怎 样确保翻译是好

10、的翻译，在提出语义忠实与语义满两条逻辑性质来说明可满足 的公式翻译为可满足的公式，不可满足公式翻译翻译为不可满足公式，并进一 步可以证明在 henkin 语义下，二阶逻辑到一阶逻辑的语义忠实与语义满的翻译， 也是满足完备性. 应用前景，坦白说，不管是学人工智能逻辑还是数理逻辑，将来最合适的 还是呆在研究机构里搞研究，而且主要是搞将元理论应用于其他理论的交叉研 究；至于能否应用于实际，这个比前面说的将理论应用于理论要难很多，要看 研究人员的机遇、原来的学科背景和能力了. 1.2 主要问题及研究意义 一个逻辑的表达能力可以从以下的 3 个角度来分析：（1）给定一个逻辑， 什么样的符号串是该逻辑的公

11、式（well-formed formula） ；（2）一个逻辑公式 的语义解释；（3）利用翻译把一个逻辑翻译到另一个逻辑之上，然后比较两个 逻辑的相对表达能力. 现有的许多翻译主要侧重讨论两个逻辑间语法的对应关系，建立逻辑语言 间的翻译和公式间的翻译，验证这样的翻译具备如下逻辑性质：（1）可靠性 （the soundness）.对任意的公式，如果可满足则翻译后的公式也满足. （2）完备性（the completeness）.对任意的公式，如果可满足，则可 满足.由式（1）和式（2）可知，公式的可满足性在可靠和完备的翻译下被保持.但 是这样的翻译不保持不可满足性，即可靠的和完备的翻译可以将不可满

12、足的公 式翻译为可满足的公式.造成这一问题的主要原因是在建立翻译的时候只考虑了 语言间的翻译和公式间的翻译，没有建立其相应的语义翻译. 针对上述问题，定义一个逻辑到另一个逻辑间的翻译由语法层翻译和语义 层翻译组成.语法层翻译是由逻辑语言间的翻译和公式间的翻译构成；语义层翻 译是由模型间的翻译和赋值间的翻译构成.为了确保源逻辑的可满足公式翻译为 目标逻辑的可满足公式，不可满足公式翻译为不可满足公式. 第二章第二章 命题逻辑与一阶逻辑命题逻辑与一阶逻辑 2.1 命题符号化及联结词 数理逻辑研究的中心问题是推理，而推理的前提和结论都是表达判断 的陈述句.因而，表达判断的陈述句构成了推理的基本单位.于

13、是，称能判断真 假的陈述句为命题.这种陈述句的判断只有两种可能，一种是正确的判断，一种 是错误的判断.称判断为正确的命题的真值为真，称判断为错误的命题的真值为 假，因而又可以称命题逻辑是具有唯一真值的陈述句.如：（1）2 是素数. （2）3 能被 2 整除.（1）和（2）都是简单的陈述句，都不能分解成更简单的 句子，称这样的命题为简单命题或原子命题.本论文中用小写的英文字母，p ， ，, ,表示简单命题，将表示命题的符号放在该命题的前面，qr i p i q i r 称为命题符号化. 以上讨论的是简单命题.在命题逻辑中，主要是研究由简单命题用联结词联 结而成的命题，这样的命题称为复合命题.以下

14、是对联结词的定义： 定义 2.1.1 设为任一命题.复合命题“非”（或“的否定”）称 2 ppp 为的否定式，记作.为否定联结词.为真当且仅当为假.pppp 定义 2.1.2 设，为两命题.复合命题“并且”（或“和”） 2 pqpqpq 称作与的合取式，记作.为合取联结词.为真当且仅当与同pqpqpqpq 时为真. 定义 2.1.3 设，为两命题.复合命题“或”称作与的析取式， 2 pqpqpq 记作.为析取联结词.为真当且仅当与中至少一个为真.pqpqpq 定义 2.1.4 设，为两命题.复合命题“如果，则”称作与的 2 pqpqpq 蕴涵式，记作，称蕴涵式的前件，为蕴涵式的后件.称作蕴涵联

15、结pqpq 词.为假当且仅当为真且为假.pqpq 定义 2.1.5 设，为两命题.复合命题“当且仅当”称作与的 2 pqpqpq 等价式，记作.称作等价联结词.真当且仅当，真值相同.pqpqpq 2.2 命题公式及分类 真值可以变化的简单陈述句称为命题变项或命题变元，也用， ，pqr , ,表示.命题变项不是命题.若在复合命题中， 等不仅可以 i p i q i rpqr 代表常项，还可以代表命题变项，这样组成的复合命题形式称为命题公式.抽象 的说，命题公式是由命题常项，命题变项，联结词，括号等组成的符号串.但并 不是由这些符号组成的符号串都是命题公式，因而，必须给出命题公式的严格 定义： 定

16、义定义 2.2.12.2.1 （1）单个命题常项或变项， ，, ,，0，1pqr i p i q i r 是合式公式； （2）如果是合式公式，则（）也是合式公式；aa （3）如果，是合式公式，则（） ， （） ， （） ， （abababab ）也是合式公式；ab （4）只有有限次地应用（1）（3）组成的符号串才是合式公式. 在本论文中将合式公式称为命题公式，或简称为公式. 定义定义 2.2.22.2.2 设为一个命题公式.a （1）若在它的各种赋值下取值均为真，则称为重言式或永真式；aa （2）若在它的各种赋值下取值均为假，则称为矛盾式或永假式；aa （3）若至少存在一组赋值是成真赋值，则是

17、可满足式.aa 2.3 一阶逻辑基本概念 在一阶逻辑中，简单命题被分解成个体词和谓词两部分.所谓个体词是指可 以独立存在的客体，它可以是一个具体的事物，也可以是一个抽象的概念.例如， 李明，玫瑰花，黑板，自然数等都可以作为个体词.而谓词是刻画个体词的性质 或个体词之间关系的词，如下面 2 个简单命题中：（1）王宏是程序员.（2）小 李比小赵高 2 厘米.“王宏”，“小李”，“小赵”都是个体词.“.是程 序员”，“.比.高 2 厘米”都是谓词. 表示具体的或特定的个体的词称为个体常项，一般用小写的英文自母,ab ,.表示.表示抽象的，或泛指的个体的词称为个体变项，常用小写英文字母c ，表示.个体

18、变项的取值范围称为个体域或论域，个体域可以是有xyz 限事物的集合，也可以是无限事物的集合. 称表示具体性质或关系的谓词谓词常项，用大写英文字母，fgh 表示，例如表示“是无理数”.而表示抽象的或泛指的谓词称为谓词变项，f 也用，表示.个体变项具有性质，记作.个体变项，fghxf( )f xx 具有性质，记作，论文中称这种个体变项和谓词的联合体，yl( , )l x y 2 ( )f x 等为谓词.( , )l x y 2.4 量词 在一阶命题逻辑中，除了个体词和谓词外，还有表示数量的词，称表示数 量的词为量词.量词有两种： 1.全称量词：对应日常语言中的“一切” ， “所有的” ， “任意的

19、”等词，用 符号“”表示.表示对个体域里的所有个体.表示个体域里的所有x( )xf x 个体都有性质.f 2.存在量词：对应日常语言中的“存在着” ， “有一个” ， “至少有一个”等 词，用符号“”表示.表示存在个体域里的个体.表示存在着个体域x( )xf x 里的个体具有性质.f 命题逻辑中的五中联结词在一阶逻辑中均可应用. 2.5 一阶逻辑的合式公式 定义定义 2.5.12.5.1 项的定义如下： （1） 个体常项和变项是项 （2） 若是任意元函数， ，是项，则 12 ( ,.,) n x xxn 1 t 2 t n t 也是项； 12 ( , ,.,) n t tt （3） 只有有限次

20、的使用（1） ， （2）生成的符号串才是项. 定义定义 2.5.22.5.2 设是任意的元谓词， ，是项，则称 12 ( ,.,) n r x xxn 1 t 2 t n t 为原子公式. 12 ( , ,.,) n r t tt 定义定义 2.5.32.5.3 合式公式的定义如下： （1） 原子公式是合式公式； （2） 若是合式公式，则（）也是合式公式；aa （3） 若 ，是合式公式，则（） ， （） ， （） ， （）ababababab 也是合式公式； （4） 若是合式公式，则，也是合式公式；axaxa （5） 只有有限次地应用（1）（4）构成的符号串才是合式公式（也称谓词公 式）. 定

21、义定义 2.5.42.5.4 设为一谓词公式，如果在任何赋值下都是真的，则称为逻辑aaa 有效式；如果在任何赋值下都是假的，则称是不可满足式；若至少存在一aa 个赋值使为真，则是可满足式.aa 2.6 一阶逻辑的模型及赋值 一般情况下，一个一阶逻辑合式公式中含有：个体常项，个体变项，谓词变 项等.由此我们可以定义一个模型：i 定义定义 2.6.12.6.1 一个模型由下面 4 部分组成：i 9 （1） 非空个体域；d （2）中一部分特定元素；d （3）上一些特定的函数；d （4）上一些特定的谓词；d 对各种变项指定特殊的常项去代替，就构成了一个公式的赋值. 2.7 命题逻辑与一阶逻辑的关系 2

22、.7.1 总体说明两者的关系总体说明两者的关系 在谓词中所包含的个体词数称为元数.含（）个个体词的谓词称为n1n 元谓词.用表示元谓词，它是以个体变项的个体域为定义域n 12 ( ,.) n p x xxn （论文中为有限域） ，以0，1为值域的元函数，在这里个个变项的顺序不nn 能随意改动.谓词不是命题，它的真值无法确定，要想使它成为命 12 ( ,.) n p x xx 题，必须指定某一谓词常项代替，同时还要用个个体常项代替个个体变pnn 项.例如，是一个 2 元谓词，它不是命题.当令表示“小于”( , )l x y( , )l x yxy 之后，该谓词中的谓词部分已为常项，但它还不是命题

23、.当取为 2，为 3 时，ab 才是命题，并且是真命题.当取 为 2，为 1 时，为假命题.将不( , )l a bcd( , )l c d 带个体变项的谓词称为 0 元谓词，例如，等都是 0 元谓词.一旦( , )l a b( , )l c d 其中的的意义明确之后，0 元谓词都是命题.因而命题逻辑中的简单命题都可l 以用 0 元谓词表示. 2.7.2 分析一阶逻辑与命题逻辑间的公式间的关系分析一阶逻辑与命题逻辑间的公式间的关系 在上文我们定义可知个体变项和谓词（在这里我们规定此谓词为谓词常项） 的联合体，等为谓词，我们又知在一阶逻辑中，简单命题被分为个( )f x( , )l x y 体词

24、和谓词（这里的谓词是谓词常项）.由上文对命题变元的定义可知，命题变 元可被分为个体变项与谓词.所以我们可以对，等谓词可以用命题( )f x( , )l x y 逻辑中的命题变元，表示.所以可以总结出：pq 设是含一阶逻辑的原子公式，的谓词公式， 0 a 1 a 2 a n a ，是个命题变元或命题常元，可以用处处代替（） ， 1 p 2 p n pn i p i a1in 所得命题公式称为的替代.a 0 a 在有限域中，如，由量词的意义对于任意的谓词，都 12 ,., n da aa( )a x 有： （1），此时的为个 12 ( )()().() n xa xa aa aa a 8 ( )(

25、1,2,., ) i a ain i a 体常项，即为 0 元谓词，则可以用命题逻辑中的简单命题表示.所以对( ) i a a i p 此形式的在命题逻辑中可以用复合命题来表示.( )xa x 12.n ppp （2），此时的为个 12 ( )()().() n xa xa aa aa a 8 ( )(1,2,., ) i a ain i a 体常项，即为 0 元谓词，则可以用命题逻辑中的简单命题表示.所以对( ) i a a i q 此形式的在命题逻辑中可以用复合命题表示.( )xa x 2 . in qqq 2.7.3 实例讨论一阶逻辑与命题逻辑间的关系实例讨论一阶逻辑与命题逻辑间的关系

26、对于谓词公式，并且对模型赋值为个体域为有限域( )( )xf xxf x ，这里没有特定元素和函数，谓词定义为“大于 0”.由以上1,2,3d ( )f xx 的一阶逻辑与命题逻辑公式间的替换规则可知，该谓词公式可以替换为命题逻 辑中的复合命题公式（）（）.我们知道 0 元谓词就 123 ppp 123 ppp 是命题逻辑中的简单命题，在这里就是表示的意义，即 大于 0.对 i p( )(1,2,3)f i i i 赋值后的谓词公式进行分析，在这里表示“1，2，3( )( )xf xxf x ( )xf x 都大于 0” ，则为真，在这里表示“在 1，2，3 中存在大于 0 的( )xf x(

27、 )xf x 数” ，则为真，可知谓词公式在此种赋值情况下为真.( )xf x( )( )xf xxf x 分析翻译后的复合命题公式（）（） ，由表示的意 123 ppp 123 ppp i p 义可知为真，则和都为真，则复合命题公式（ i p 123 ppp 123 ppp ）（）为真，有以上分析，可以归纳为： 123 ppp 123 ppp （1） 谓词公式：；( )( )xf xxf x （2） 个体域；1,2,3d （3） 谓词：表示“大于 0” ；( )f xx （4） 翻译：（）（） （( )( )xf xxf x 123 ppp 123 ppp 表示“ 大于 0” ，与意义相同）

28、 ；并且在这种赋值情况(1,2,3) i p i i( )(1,2,3)f i i 下替换前和替换后的公式的真值都为真. 上面的例子说明在模型中不一定要写出特定元素与特定的函数，下面的例 子来做含有此两项的讨论：对于一阶逻辑合式公式，规( ( ( )( ,( )x f f xg a f x 定个体域为；中的特定元素；函数为，2,3d d2a ( )f x(2)3f ；谓词表示“是偶数” ，表示“大于” ；有公式间的(3)2f( )f xx( , )g x yxy 替换规则可知可被替换为命题逻辑中的复合公式( ( ( )( ,( )x f f xg a f x ，并且与表示相同的意义，即“3 是

29、偶数” ，所以 1122 ()()pqpq 1 p( (2)f f 的真值为假，与表示相同的意义，即“2 是偶数” ，所以的真值 1 p 2 p( (3)f f 2 p 为真；与表示相同的意义.即“2 大于 2” ，所以真值为假，与 1 q( ,(2)g a f 1 q 2 q 表示相同的意义，即“2 大于 3” ，真值为假，可知( ,(3)g a f 2 q 的真值为假；而此时表示“在 2，3 1122 ()()pqpq( ( ( )( ,( )x f f xg a f x 中存在偶数并且存在着小于 2 的数” ，可知的真值为假.( ( ( )( ,( )x f f xg a f x 在这里

30、要知道函数的定义域与值域必须是论域的除空集的子集，如果值( )f xd 域不是论域的除空集的子集，比如说的值域有不是中的元素，则对谓词( )f xd 进行赋值时就会含有不是论域中的个体常项，则进一步就说明论域要含有d ，则与不含有矛盾，所以的值域论域的除空集的子集.d( )f xd 第三章第三章 二阶逻辑二阶逻辑 3.1 二阶逻辑的简介 为了得到比一阶逻辑更丰富，更富有表现力的语言，我们可以对谓词符号和 函数符号添加量词.例如，是一个谓词公式，而( ( )( )x p xxp x 是一个二阶逻辑的公式.为了说明二阶逻辑的公式，下面( ( )( )p x p xxp x 介绍一下逻辑符号： （1

31、） 谓词变元：对于每个正整数，我们有元谓词变元， 10 nn 1 n x 2 n x （2） 函数变元：对于每个正整数，我们有元函数变元， 10 nn 1 n f 2 n f 下面定义二阶逻辑的合式公式： 定义定义 5.5.15.5.1 设是任意的元谓词， ，是项，则称 12 ( ,.,) n r x xxn 1 t 2 t n t 为原子公式. 12 ( , ,.,) n r t tt 定义定义 5.5.25.5.2 合式公式的定义如下： （1） 原子公式是合式公式； （2） 若是合式公式，则（）也是合式公式；aa （3） 若 ，是合式公式，则（） ， （） ， （） ， （）abababa

32、bab 也是合式公式； （4） 若是合式公式，则，也是合式公式；axaxa （5） 若是合式公式，则，也是合式公式；a n i x a n i f a （6） 只有有限次地应用（1）（5）构成的符号串才是合式公式. 对于二阶逻辑的模型其满足一阶逻辑模型的 4 部分，并且有所扩展：设是v 所有个体变元，谓词变元和函数变元的集合，并设 是上的函数，且满足sv 是论域中的一个元素，是论域中的元关系，是元运算， 1 ( )s v() n s xun() n s fn 这样可知谓词变元和函数变元的集合为.2u 11 现在对二阶逻辑做出总结，在这之前我们我们来看一个定义： 定义定义 5.5.35.5.3

33、若任一真值函数都可以用仅含某一联结词集中的联结词的命题公式 表示，则称该联结词集为全功能集. 由定义 5.5.3 可知为一全功能集，在证明这个结论前，先来介绍几, 6 个等值式，设为任意的命题公式： 12 ,a b （蕴涵等值式）abab (双重否定律)aa （等价等值式）()()ababba ，；（德.摩根律）()abab ()abab 证明：由以上分析可知 5 个联结词组成的联结词集为.由于, , , （1）pq （双重否定律）pqpq （蕴涵等值式）pqpq 即pqpq （2）pq （双重否定律）()pqpq （德.摩根律）()()pqpq （蕴涵等值式）()()pqpq 即()pqpq

34、 （3）pq （等价等值式）()()pqpqqp （双重否定律）()()()()pqqppqqp （德.摩根律）()()( ()()pqqppqqp （蕴涵等值式）( ()()()()pqqppqqp 由定义 5.5.1 可知为全功能集 ，证完., 我们可以用替换.x x 7 由以上我们总结二阶逻辑：二阶逻辑语言包含下列符号： 元谓词符号：，；n 0 p 1 p 逻辑联结词：；, 全称量词符号：； 个体变元：，； 0 x 1 x 函数变量符号和谓词变量符号：，； 0 x 1 x 标点符号：（， ）. 二阶逻辑的公式，定义为： 12 ( , ,.,)|( )|() n r t ttxxxx 二阶

35、逻辑有两种语义：一种是标准语义；另一种是 henkin 语义.如果二 1 阶逻辑采用的是标准语义，那么完备性定理在二阶逻辑中不成立；如果二阶逻 辑采用的是 henkin 语义，那么完备性定理在二阶逻辑中成立. 二阶逻辑在 henkin 语义下的模型是一个三元组（， ） ，mu nn n a i 其中为一个非空集合，为的非空子集，表示函数变量符号和谓词变量u n a2u 符号的取值域，是一个解释，使得是上的带类型的关系. n x n ai i pu 一个赋值函数 是变量集合到模型论域上的一个函数：对于任何个体变量， vx ；对任何函数变量和谓词变量，.( )v xu n x nn xa 二阶逻辑

36、在 henkin 语义下到一阶逻辑的翻译既是语义满的又是语义忠 实的. 1 3.2 二阶逻辑到一阶逻辑的翻译的性质 3.2.1 性质的介绍及证明性质的介绍及证明 一个逻辑到另一个逻辑间的翻译由语法层翻译和语义层翻译组成.语法层翻 译是由逻辑语言间的翻译和公式间的翻译构成；语义层翻译是由模型间的翻译 和赋值间的翻译组成.现在用表示一个逻辑，表示逻辑所在的逻辑语言；ss 表示可满足关系；假定的逻辑语言不含相等符号；表示上全体|s( )forms 公式所构成的集合；表示上所有模型所构成的集合；是上所有( )mods( )vs 赋值所构成的集合，给出如下到翻译的定义：s s 定义定义 3.2.13.2

37、.1 给定两个逻辑和，一个到的翻译是满足如下条件的s ss s 一个映射： （1）语法层.对中的任意非逻辑符号 ，映射 为中的非逻辑符号； 1 ss 对中的任意公式，映射为中的公式.( )form ()form （2）语法层.对中的任意模型，映射为中的模型； 1 ( )modmm ()mod 对中的任意赋值 ，映射中的赋值.( )vv ()v 定义定义 3.2.23.2.2 设是到的一个翻译，如果满足：对于任意给定的上s ss 的公式，模型，赋值 ，都有（， ）当且仅当（，）mvmv|()m( )v ，则称为一个语义忠实的翻译.|( ) 定义定义 3.2.33.2.3 设是到的一个翻译，如果满

38、足：对于任意给定的 3 s s 上的公式，任意的模型，赋值都有：如果（，），那s s m v m v|( ) 么存在的模型和赋值 使得（， ）并且，则smvmv| ()mm ( )vv 称为一个语义满的翻译. 命题命题 3.2.43.2.4.如果一个翻译是到的既语义忠实又语义满的翻译，那么s s 对的任意公式，在中不可满足当且仅当在中不可满足.ss( ) s 证明：假设在中不可满足但是在中可满足，那么存在模型和赋s( ) s m 值使得（，）.因为是语义满翻译，所以就有：的模型和 v m v|( ) sm 赋值 使得（， ）.这与在中不可满足矛盾.反之，若在中vmv|s( ) s 不可满足，但

39、是在中可满足，那么存在模型和赋值 使得（， ）ssmvmv .因为是语义忠实的翻译，所以就有（，）.这与|()m( )v|( ) 在中不可满足矛盾.证毕.( ) s 3.2.2 完备性定理完备性定理 定义定义 3.2.53.2.5（协调性）（表示公式的集合） ，当且仅当 4 ( )form ，使得并且（表示形式可推演性关系）( )aforma a 14 定义定义 3.2.63.2.6 （极大协调性）公式集是极大协调的，当且仅当满足 15 一下的（1）和（2）： （1）是协调集； （2）对于任何，是不协调的.a a 定理定理 3.2.73.2.7 设是极大协调集.于是，对于任何，当且仅当.aa

40、a 证明：如果，则有（） ，.下面证明其逆命题，设.如果aaa ，则由于是极大协调的，所以是不协调的.于是，因而a aa 不协调，这与的极大协调性矛盾.因此.a 定理定理 3.2.83.2.8 设是极大协调集.则对于任何和，ab （1），当且仅当；a a （2），当且仅当并且；abab （3），当且仅当或；abab （4），当且仅当蕴涵；abab （5），当且仅当等值于.abab 证明：证（1）先证.设.如果，则有（）可得aa a a 和，即是不协调的，与假设的的极大协调性矛盾.因此.aa a 下面证.设，如果，则可依次得到：aa aa （1）是不协调的；a （2）；a （3）.a 这与矛盾.

41、因此.aa 证（2）先证并且.设并且.由定理 3.2.7 可abab ab 得及（） （如果，则）：a b ab （1）；aa （2）.bb 因此.ab 下面证并且.设.如果“并且”aba babab 不成立，则依次可得： （1），；ab （2）， （由本定理（1） ） ；ab （3）（由本定理（2） ） ；ab （4）；ab （5）ab 又由假设可知，这样是不协调的，与的极大协调性矛盾.因abab 此并且.ab 证（3）先证或.设或.由定理 3.2.7 及abab ab （） （如果则，）可得：a abba （1）；aaabab （2）.bbabab 因此.ab 下面证或.设.如果“或”不a

42、ba babab 成立，则依次可得： （1），；ab （2）， （由本定理（1） ） ；ab （3）（由本定理（3） ） ；ab （4）；ab （5）()ab 又由假设可知，这样是不协调的，与的极大协调性矛盾.因abab 此或.ab 证（4）先证蕴涵.有定理 3.2.7 及（） （如果，ababa 则,）和（） （如果,则）： a abab .bb , ababab 因此ab 下面证蕴涵.如果“蕴涵”不成立，ababab 依次可得： （1），；ab （2）（由本定理（1） ） ；b （3）（由本定理（3） ） ；ab （4）；ab （5）()ab 又由于可知，即，这样是不协调的，与ab()ab

43、()ab 的极大协调性矛盾.因此蕴涵.ab 证（5）先证等值于.由定理 3.2.7 及（） （如果abab ，则）和（）可得：, ab,baab （1）；aa ,ba （2）；,bbab 由（1） （2）可知，所以.abab 下面证等值于.如果“等值于”不成立，ababab 依次可得： （1），；ab （2）（由本定理（1） ） ；b （3）（由本定理（1） ， （2） ， （3） ） ；( ()()abba （4）；( ()()abba （5）()()abba 又由于可知，这样是不协调的，与的ab()()abba 极大协调性矛盾.所以等值于.证毕.ab 定理定理 3.2.93.2.9 如果，

44、存在有限的，使得.a 0 0 a 证：对的结构作归纳.aa 基始.有规则（ref）生成的的前提本身是一个公式，所以 16 aaa 有定理中所说的性质.aa 归纳步骤.证明在剩下十种推演规则的情形. 规则（）的情形： 如果，a 则，. a 由归纳假设，存在有限的，使得.也是，的有限子集.因 0 0 a 0 此规则（）保存定理中所说的性质. 规则（）的情形： 如果，ab ，ab 则.a 我们先要证明： （1）存在有限的，使得，. 1 1 ab （2）存在有限的，使得，. 2 2 ab 由归纳假设，存在有限的，使得.若，则是 ,a b a 的有限子集.根据（） ，有可得，.令，这就 b ab 1 a

45、b 是（1）.若，则是的有限子集.令.我们有 a a 1 a ，从而得到（1）. 1 ,a （2）的证明是类似的. 根据（） ，可以由（1）和（2）得到： ， 1 2 ab ， 1 2 ab 由此可得，其中的，是的有限子集.故规则（）保存 1 2 a 1 2 5 定理中所说的性质. 规则（）的情形： 如果，ab ，a 则.b 由归纳假设，存在的有限子集和，使得并且.根据 1 2 1 ab 2 a （） ，可得： ， 1 2 ab ，. 1 2 a 于是有，其中的，是的有限子集.故规则（）保存定理 1 2 b 1 2 中所说的性质. 其他情形的证明是类似的. 由基始和归纳步骤，定理得证. 定理定

46、理 3.2.103.2.10（lindenbaum）任何协调的公式集能够扩充为极大协调集. 17 证：设是协调的公式集.是可数无限集.另( )form （1），是所有公式的任何一个排列.定义的无限 0 a 1 a 2 a( ) n form 序列（）如下：0n ，如果协调，则，否则 ；于是有： 0 nn a 1 nnn a 1nn （2）. 1nn （3）是协调的. n 其中的（2）是显然的， （3）能够由对作归纳而证明.n 令.显然有.下面证明是本定理所要求的极大协调集. * n n n * * 先证是协调集.如果不协调，即有，使得并且.根据 * * b * b * b 定理 3.2.9，有

47、中的有限个公式，和，使得： * 1 b k b 1k b l b ，； 1 b k bb ，. 1k b l bb 由此得到： ，. 1 b l bbb 故，是不协调的. 1 b l b 设，并且.由（2）可得，(1) i it bil 1 max( ,.,) n ttt 1 b l b t 因此是不协调的，这和（3）矛盾.故是协调的. t * 令，即.是（1）中的公式，令.根据的构 * c(0) n cnc m ca 1m 作情形，可知（即）是不协调的.（如果是协调的， mm a m c mm a 则，因此，即，这与，矛盾.） 1 mmm a 1mm a 1m c n c (0)n 这样，因

48、为，故是不协调的，因此是极大协调集. * m * c * 引理 3.2.11 设是极大协调集.构作真假赋值 ，使得对于任何原 * () p form v 子公式，当且仅当，于是，对于任何，当且p1 v p * p() p aform1 v a 仅当. * a 证明：对的结构作归纳.a 基始.是原子公式.由假设，引理成立.a 归纳步骤.有，或五种情形.abbcbcbcbc 的情形：ab * b （由定理 3.2.8（1） ） * b （由归纳假设）0 v b .()1 v b 的情形：abc * bc 或（由定理 3.2.8（3） ） * b * c 或（由归纳假设）1 v b 1 v c ()

49、1 v bc 的情形abc bc * 并且（由定理 3.2.8（2） ） * b * c 并且（由归纳假设）1 v b 1 v c ()1 v bc 的情形：abc * bc 蕴涵（由定理 3.2.8（4） ） * b * c 蕴涵（由归纳假设）1 v b 1 v c ()1 v bc 的情形：abc * bc 等值于（由定理 3.2.8（5） ） * b * c 等值于（由归纳假设）1 v b 1 v c ()1 v bc 由基始和归纳步骤，引理得证. 定理 3.2.12（完备性）设，() p form () p aform （1）如果是协调的，则是可满足的； （2）如果是协调的，则是可满足

50、的.aa 证：设是协调的.取任何.把扩充为极大协调集（由定理 3.2.10） ，b * 则有.由引理 3.2.11，使用其中的真假赋值 ，可得.因此 满足， * bv1 v b v 这就证明了（1）.（2）是（1）的特殊情形.得证. 3.2.3 二阶逻辑到一阶逻辑翻译的完备性的分析二阶逻辑到一阶逻辑翻译的完备性的分析 如果二阶逻辑在 henkin 语义下的翻译不是完备性翻译，我们可令二阶逻辑 合式公式集是满足完备性的，但翻译为一阶逻辑的合式公式集后不满足完 * 备性了，由定理 3.2.12 可以说是可满足的合式公式但翻译为一阶逻辑合式公 式集后含有了不可满足的公式，即有二阶逻辑中的可满足公式翻译为一阶逻 * 辑的不可满足公式.我们又知道二阶逻辑在 henkin 语义下与一阶逻辑的翻译 既是语义忠实又是语义满的翻译，这样由命题 3.2.4 可知一阶逻辑不可满足