第3章一阶逻辑的语言 第1节一阶逻辑的语言的定义和例子 学完了命题逻辑,我们对各种联词有了充分的了解,因而可以对由联词联结的复合语 句进行精确的分析。但命题逻辑语言的“最小单位”是命题符号,我们无法深入到单个命 题的里面来进行更细的研究,如对主语,谓语的分析等等。我们下面讨论的一阶语言能使 我们克服这一缺陷。大家将会看到,一阶语言与我们通常用的数学语言甚至自然语言非常 的接近。一阶逻辑是我们本课程的中心内容。 311一阶语言的定义 -阶逻辑的语言L包括 (0)括号:“(”和“)”; (1)命题联词:-和→ (2)(全称)量词符号:V; (3)变元:1,v (4)常数符号:若干(可以没有,也可以有无穷多个)符号; (5)函数符号:对每一自然数n,都有若干(可以没有,也可以有无穷多个)符号,称 为m-元函数符号; (6)谓词符号:对每一自然数n,都有若干(可以没有,也可以有无穷多个)符号,称 为n-元谓词符号 (7)等词符号(可以没有):≈。 注:与命题逻辑中联词的选取类似,一阶逻辑语言中的符号也与数学有密切的关系 我们逐项解释一下符号选取的动机。(但不要忘记,我们本节讨论的是语法,因此暂时仍 要认为所有的符号都是没有意义的。)
第 3 章 一阶逻辑的语言 第 1 节 一阶逻辑的语言的定义和例子 学完了命题逻辑，我们对各种联词有了充分的了解，因而可以对由联词联结的复合语 句进行精确的分析。但命题逻辑语言的“最小单位”是命题符号，我们无法深入到单个命 题的里面来进行更细的研究，如对主语，谓语的分析等等。我们下面讨论的一阶语言能使 我们克服这一缺陷。大家将会看到，一阶语言与我们通常用的数学语言甚至自然语言非常 的接近。一阶逻辑是我们本课程的中心内容。 3.1.1 一阶语言的定义 一阶逻辑的语言 L 包括 (0) 括号：“(”和“)”； (1) 命题联词：¬ 和 →； (2) （全称）量词符号：∀； (3) 变元：v1, v2, · · · ； (4) 常数符号：若干（可以没有，也可以有无穷多个）符号； (5) 函数符号：对每一自然数 n，都有若干（可以没有，也可以有无穷多个）符号，称 为n-元函数符号； (6) 谓词符号：对每一自然数 n，都有若干（可以没有，也可以有无穷多个）符号，称 为n-元谓词符号； (7) 等词符号 （可以没有）：≈。 注：与命题逻辑中联词的选取类似，一阶逻辑语言中的符号也与数学有密切的关系。 我们逐项解释一下符号选取的动机。（但不要忘记，我们本节讨论的是语法，因此暂时仍 要认为所有的符号都是没有意义的。） 1
第1节一阶逻辑的语言的定义和例子 第3章一阶逻辑的语言 语言中的(0)到(3)被称为逻辑符号。括号只是为了阅读方便。联词我们为了精炼只 挑两个,但我们知道{→,→}是功能完全的,不会因此而失掉一般性。量词和变元是一阶 逻辑的重要组成部分,有了它们,我们可以更精细地讨论数学对象之间的关系等等,在 命题逻辑中则做不到这一点。此外,量词的“控制范围”和变元的变化范围也是逻辑学 所关注的。所谓“一阶”逻辑,指的就是变元仅代表“个体”,量词所控制的也是“个 体”。在后继课程中我们会看到二阶逻辑,其中就有两种不同的量词和变元,一种谈论 个体”(即与一阶逻辑相同),另一种谈论“(由个体组成的)集合”或“(个体之间)的 关系”(即二阶部分)。尽管二阶逻辑的语言更丰富,但一阶逻辑在逻辑学中的主导地位仍 是不可动摇的,原因之一是一阶逻辑有完全性,而二阶逻辑则没有 语言中的(4)到(7)被称为非逻辑符号,可以说是从数学中提炼出来的。比如,当人 们讨论自然数的性质时,指定专门一个符号代表数字零,指定专门的运算符号来代表加法 和乘法是非常自然的。又比如,当人们研究图论时,指定符号代表“边”这个顶点之间的 二元关系(即二元谓词)也是顺理成章的。此外,我们有意把等词写成弯的,用来区别数 学中的等号=。当然如果读者能够分清对象语言和元语言中符号的区别,则完全可以采用 同一个符号。最后我们把等词(⑦)同(6)中一般的谓词符号分开,是因为(见后文)等词 必须解释成等号,而一般的谓词则允许有不同的解释 我们看几个例子。在讨论一阶语言时,我们通常只列出非逻辑符号,而默认逻辑符号 已经包含在其中了。在多数讨论数学的场合,我们还默认包含等词≈ 例3.1. (1)公理集合论的语言set={≈,e},其中∈为一个二元谓词符号。 (2)初等数论的语言为L={≈,<,0,S,+,},其中<为一个二元谓词符号,0为一个常 数符号,S为一个一元函数符号,+和·.为两个二元函数符号。 (3)序关系的语言为L={F},其中R为一个二元谓词符号,也可以选取L={R,≈}。 规定好语言之后,我们就可以定义公式。但之前我们先要定义“项”这一概念。直观 上说,项在公式中扮演名词在句子扮演的角色。 定义31.令L为一个一阶语言。定义L中所有项的集合为满足下列条件的最小的表达式 的集合 1)每个变元v都是一个项; (2)每个常数符号都是一个项; (3)如果t1,t2…,t是项并且∫为一个n元函数符号,则∫t1,t2,…,tn也是一个项。 注意:这又是“自上而下”的定义方式
第 1 节 一阶逻辑的语言的定义和例子 第 3 章 一阶逻辑的语言 语言中的 (0) 到 (3) 被称为逻辑符号。括号只是为了阅读方便。联词我们为了精炼只 挑两个，但我们知道 {¬,→} 是功能完全的，不会因此而失掉一般性。量词和变元是一阶 逻辑的重要组成部分，有了它们，我们可以更精细地讨论数学对象之间的关系等等，在 命题逻辑中则做不到这一点。此外，量词的“控制范围”和变元的变化范围也是逻辑学 所关注的。所谓“一阶”逻辑，指的就是变元仅代表“个体”，量词所控制的也是“个 体”。在后继课程中我们会看到二阶逻辑，其中就有两种不同的量词和变元，一种谈论 “个体”（即与一阶逻辑相同），另一种谈论“（由个体组成的）集合”或“（个体之间）的 关系”（即二阶部分）。尽管二阶逻辑的语言更丰富，但一阶逻辑在逻辑学中的主导地位仍 是不可动摇的，原因之一是一阶逻辑有完全性，而二阶逻辑则没有。 语言中的 (4) 到 (7) 被称为非逻辑符号，可以说是从数学中提炼出来的。比如，当人 们讨论自然数的性质时，指定专门一个符号代表数字零，指定专门的运算符号来代表加法 和乘法是非常自然的。又比如，当人们研究图论时，指定符号代表“边”这个顶点之间的 二元关系（即二元谓词）也是顺理成章的。此外，我们有意把等词写成弯的，用来区别数 学中的等号 =。当然如果读者能够分清对象语言和元语言中符号的区别，则完全可以采用 同一个符号。最后我们把等词 (7) 同 (6) 中一般的谓词符号分开，是因为（见后文）等词 必须解释成等号，而一般的谓词则允许有不同的解释。 我们看几个例子。在讨论一阶语言时，我们通常只列出非逻辑符号，而默认逻辑符号 已经包含在其中了。在多数讨论数学的场合，我们还默认包含等词 ≈。 例 3.1. (1) 公理集合论的语言 Set = {≈,∈}，其中 ∈ 为一个二元谓词符号。 (2) 初等数论的语言为 L = {≈, <, 0, S, +, ·}，其中 < 为一个二元谓词符号，0 为一个常 数符号，S 为一个一元函数符号，+ 和 · 为两个二元函数符号。 (3) 序关系的语言为 L = {R}，其中 R 为一个二元谓词符号，也可以选取 L = {R, ≈}。 规定好语言之后，我们就可以定义公式。但之前我们先要定义“项”这一概念。直观 上说，项在公式中扮演名词在句子扮演的角色。 定义 3.1. 令 L 为一个一阶语言。定义 L 中所有项 的集合为满足下列条件的最小的表达式 的集合： (1) 每个变元 vi 都是一个项； (2) 每个常数符号都是一个项； (3) 如果 t1, t2 · · · , tn 是项并且 f 为一个 n 元函数符号，则 f t1, t2, · · · , tn 也是一个项。 注意：这又是“自上而下”的定义方式。 2
第3章一阶逻辑的语言 第1节一阶逻辑的语言的定义和例子 例3.2.S0,+n1SSS0和×S0+0SSS0都是初等数论里的项。 定义3.2.令L为一个一阶语言。定义L中所有合式公式(简称公式)的集合为满足下列 条件的最小的表达式的集合 1)如果t,…,tn为L中的项,并且P为一个n元谓词符号,则Pt1,…,tn是一个合 式公式。我们称这样的公式为原子公式。特别地,≈t1t2是一个原子公式 2)如果a和B是合式公式,则(-a)和(a→B)也是; (3)如果a是合式公式,则vtv2a也是。 注 (1)我们引进符号∨,∧和分别作为(-a)→B),(-(a→(B),和(a→)A(B→ a)的简写。 (2)我们用彐a作为(vx(ma)的简写,并称彐为存在量词。 (3)我们用u≈t作为≈ut的简写,对其它二元谓词也同样处理;并且用u≈t作为 (→≈ut)的简写。这样做的目的是增加可读性 (4)同命题逻辑一样,一阶逻辑的合式公式也有唯一可读性。证明从略。 (5)同命题逻辑类似,在不引起混乱的情况下,我们也省略掉冗余的括号。除了第 章第四节的约定外,补充上“量词Ⅴ和彐的管辖范围尽可能短”这一条。例如, vva→B指的是(v2a)→B而不是vv(a→B) (6)我们通常会用大写的英文字母,如P,Q,R等等表示谓词符号;小写字母,如x,y,z 表示变元;用f,g,h表示函数符号;a,b,c表示常数符号;t表示项;小写希腊字母 如a,β,φ,σ,τ等等表示公式;用大写希腊字母,如,Δ,∑表示公式集。虽 然我们做不到完全没有例外,但把记号固定下来是一个好的习惯。 312一阶语言公式的例子 我们下面给出一些用一阶语言公式的例子。这些例子说明一阶逻辑的语言具有很强 的表达力。事实上,几乎所有数学命题皆可在某种一阶语言中表达。事实上,几乎所有一 般的语句(数学的和非数学的)都可翻译为一个形式的一阶语言的语句。这种翻译其实与 后面谈到的语义方面(如可定义性)关系更密切。但因为这是学习逻辑学的学生需要掌握 的技能,(加上举例的必要性)我们也把它放在本节的语法讨论当中。需要注意的是:尽 管我们在把一般的语句A翻译成一阶公式a时,期望a表达的就是A;但以后我们会看
第 3 章 一阶逻辑的语言 第 1 节 一阶逻辑的语言的定义和例子 例 3.2. S0，+v1SSS0 和 ×S0 + 0SSS0 都是初等数论里的项。 定义 3.2. 令 L 为一个一阶语言。定义 L 中所有合式公式 （简称公式）的集合为满足下列 条件的最小的表达式的集合： (1) 如果 t1, · · · , tn 为 L 中的项，并且 P 为一个 n 元谓词符号，则 P t1, · · · , tn 是一个合 式公式。我们称这样的公式为原子公式 。特别地，≈ t1t2 是一个原子公式。 (2) 如果 α 和 β 是合式公式，则 (¬α) 和 (α → β) 也是； (3) 如果 α 是合式公式，则 ∀vi α 也是。 注： (1) 我们引进符号 ∨，∧ 和 ↔ 分别作为 ((¬α) → β)，(¬(α → (¬β)))，和 ((α → β)∧(β → α)) 的简写。 (2) 我们用 ∃xα 作为 (¬∀x(¬α)) 的简写，并称 ∃ 为存在量词。 (3) 我们用 u ≈ t 作为 ≈ ut 的简写，对其它二元谓词也同样处理；并且用 u ̸≈ t 作为 (¬ ≈ ut) 的简写。这样做的目的是增加可读性。 (4) 同命题逻辑一样，一阶逻辑的合式公式也有唯一可读性。证明从略。 (5) 同命题逻辑类似，在不引起混乱的情况下，我们也省略掉冗余的括号。除了第二 章第四节的约定外，补充上“量词 ∀ 和 ∃ 的管辖范围尽可能短”这一条。例如， ∀viα → β 指的是 (∀viα) → β 而不是 ∀vi(α → β)。 (6) 我们通常会用大写的英文字母，如 P，Q, R 等等表示谓词符号；小写字母，如 x, y, z 表示变元；用 f, g, h 表示函数符号；a, b, c 表示常数符号；t 表示项；小写希腊字母， 如 α，β，φ，σ，τ 等等表示公式；用大写希腊字母，如 Γ，∆，Σ 表示公式集。虽 然我们做不到完全没有例外，但把记号固定下来是一个好的习惯。 3.1.2 一阶语言公式的例子 我们下面给出一些用一阶语言公式的例子。这些例子说明一阶逻辑的语言具有很强 的表达力。事实上，几乎所有数学命题皆可在某种一阶语言中表达。事实上，几乎所有一 般的语句（数学的和非数学的）都可翻译为一个形式的一阶语言的语句。这种翻译其实与 后面谈到的语义方面（如可定义性）关系更密切。但因为这是学习逻辑学的学生需要掌握 的技能，（加上举例的必要性）我们也把它放在本节的语法讨论当中。需要注意的是：尽 管我们在把一般的语句 A 翻译成一阶公式 α 时，期望 α 表达的就是 A；但以后我们会看 3
第1节一阶逻辑的语言的定义和例子 第3章一阶逻辑的语言 到,翻译成α之后,它仅仅是一个字符串而已,除了还原成A之外,我们无法避免a还 可能有其它的解释。这在讲语义时再详细谈。 哲学语言由于分析哲学的原因,很多哲学家喜欢用一阶语言重述一些哲学命题。这些命 题都是自然语言表达的,而自然语言的谓词和函数并无一个明确的列表,所以我们不可能 把用于哲学目的的一阶语言的所有非逻辑符号都列出来。但不管怎样,自然语言的谓词和 函数是有穷的,所以我们的的符号总是够用。在同一语境下,我们总是可以把谓词和函 数符号编上号以示区别。 当今的法国国王是秃子。 vr(P1(x)→P2(x) 这里P的上标1表示P是一个一元谓词,下标说明它代表第一个(在我们的编号 顺序下)谓词。我们把理和P的选择留给大家。注意,翻译的结果可能不唯一。 2.金山不存在。 =3x(P3(a)A Pl(a)) 晨星即暮星 vr(P(x)→Vy(P(y)→x≈y) 一阶算术语言L={≈,1并且x没有除自身和1之外的因子。 这样我们得到如下公式 S0< A Vyv2(y<x∧z<x)→y·z关x)
第 1 节 一阶逻辑的语言的定义和例子 第 3 章 一阶逻辑的语言 到，翻译成 α 之后，它仅仅是一个字符串而已，除了还原成 A 之外，我们无法避免 α 还 可能有其它的解释。这在讲语义时再详细谈。 哲学语言 由于分析哲学的原因，很多哲学家喜欢用一阶语言重述一些哲学命题。这些命 题都是自然语言表达的，而自然语言的谓词和函数并无一个明确的列表，所以我们不可能 把用于哲学目的的一阶语言的所有非逻辑符号都列出来。但不管怎样，自然语言的谓词和 函数是有穷的，所以我们的 的符号总是够用。在同一语境下，我们总是可以把谓词和函 数符号编上号以示区别。 1. 当今的法国国王是秃子。 ∀x(P 1 1 (x) → P 1 2 (x))。 这里 P 1 1 的上标 1 表示 P 1 1 是一个一元谓词，下标说明它代表第一个（在我们的编号 顺序下）谓词。我们把 P 1 1 和 P 1 2 的选择留给大家。注意，翻译的结果可能不唯一。 2. 金山不存在。 ¬∃x(P 1 3 (x) ∧ P 1 4 (x))。 3. 晨星即暮星。 ∀x(P 1 5 (x) → ∀y(P 1 6 (y) → x ≈ y))。 一阶算术语言 L = {≈, 1 并且 x 没有除自身和 1 之外的因子。 这样我们得到如下公式： S0 < x ∧ ∀y∀z((y < x ∧ z < x) → y · z ̸≈ x)。 4
第3章一阶逻辑的语言 第1节一阶逻辑的语言的定义和例子 集合论语言set={≈,∈} 两个集合相等当且仅当它们有共同的元素。 y(x≈y+V2(z∈ ∈y)) x是y的子集。 vz(z∈x→z∈y) 3.x是y的幂集。 vz(z∈x+W(∈z→u∈y) 4.集合z是空集。 Vr(e g a) 5.选择公理选择公理有很多种等价的表述,我们找一个比较容易叙述的: X((X≠0∧0gX) C(u∈X(a(a∈uAa∈C) ∧va((a∈u∧a∈CAb∈uAb∈C)→a=b) 注意到其中⑩不是我们语言sa中的常数符号,我们要利用它的定义来替换它。具体 做法是将第一行换成 VX(z(x(xgx)→(X≠ gAzE X) 其余不变。 最后再举两个代数中的例子 群论语言g={e,+} 群的公理可以表达如下 1.群的运算满足结合律。 Vavbvc(a +(b+c))a(a+b)+c) 2.e是单位元。 va(e+a≈a)
第 3 章 一阶逻辑的语言 第 1 节 一阶逻辑的语言的定义和例子 集合论语言 Set = {≈,∈} 1. 两个集合相等当且仅当它们有共同的元素。 ∀x∀y(x ≈ y ↔ ∀z(z ∈ x ↔ z ∈ y))。 2. x 是 y 的子集。 ∀z(z ∈ x → z ∈ y)。 3. x 是 y 的幂集。 ∀z(z ∈ x ↔ ∀u(u ∈ z → u ∈ y))。 4. 集合 z 是空集。 ∀x(x ̸∈ z)。 5. 选择公理 选择公理有很多种等价的表述，我们找一个比较容易叙述的： ∀X((X ̸= ∅ ∧ ∅ ̸∈ X) → ∃C(∀u ∈ X(∃a(a ∈ u ∧ a ∈ C) ∧∀a(∀b(a ∈ u ∧ a ∈ C ∧ b ∈ u ∧ b ∈ C) → a = b))))。 注意到其中 ∅ 不是我们语言 Set 中的常数符号，我们要利用它的定义来替换它。具体 做法是将第一行换成： ∀X(∀z(∀x(x ̸∈ z) → (X ̸= z ∧ z ̸∈ X)) → 其余不变。 最后再举两个代数中的例子： 群论语言 g = {e, +} 群的公理可以表达如下： 1. 群的运算满足结合律。 ∀a∀b∀c(a + (b + c)) ≈ (a + b) + c)。 2. e 是单位元。 ∀a(e + a ≈ a)。 5
第2节自由出现和约束出现 第3章一阶逻辑的语言 3.每个元素都有逆 va(b(a+b≈e) 4.如果群的运算还满足交换律,即 vavb(a+b≈b+a) 则这样的群称为交换群或阿贝尔群。 环的语言对群的语言扩张得到环论语言R≈{e,+,}。除了以上四条公理外,环论 的公理还包括 5.乘法结合律。 Varvel(a·(b·c)≈(a·b)·c) 6.乘法对加法的分配律。 Abyc(a·(b+c)≈a·b+a·c) 第2节自由出现和约束出现 接下来我们讨论语法中另一个现象:变元的自由出现和约束出现。在数学中,一个表 达式常常含有两类不同的变元,例如,f(x,t)d,∑1a1等。在积分的例子中,变元x 和t所起的作用是不同的;在求和的例子中,变元n和i的作用也不同。变元t和主要 起的是占位的作用,也有人管它们叫“哑元”。哑元可以被替换成任意“新的”变元而不 影响公式的意义,比如∑h=1a1和∑1a意义完全相同。而例中变元x和n则不能被随 便替换。逻辑中,约束变元就与哑元类似 直观上说,一个变元是自由的如果没有任何量词“管”着它。更准确地说,我们递归 地定义“变元x在公式a中自由出现”如下: 如果a是一个原子公式,则x在a中自由出现当且仅当x在a中出现。 2.如果a为(3),则x在a中自由出现当且仅当x在B中自由出现 3.如果a为(→7),则x在a中自由出现当且仅当x在β中自由出现或在?中自由 出现。 如果a为v2B,则x在a中自由出现当且仅当x在B中自由出现并且x≠v2
第 2 节 自由出现和约束出现 第 3 章 一阶逻辑的语言 3. 每个元素都有逆元。 ∀a(∃b(a + b ≈ e))。 4. 如果群的运算还满足交换律，即 ∀a∀b(a + b ≈ b + a)。 则这样的群称为交换群或阿贝尔群。 环的语言 对群的语言扩张得到环论语言 R ≈ {e, +, ·}。除了以上四条公理外，环论 的公理还包括： 5. 乘法结合律。 ∀a∀b∀c(a · (b · c)) ≈ (a · b) · c)。 6. 乘法对加法的分配律。 ∀a∀b∀c(a · (b + c) ≈ a · b + a · c)。 第 2 节 自由出现和约束出现 接下来我们讨论语法中另一个现象：变元的自由出现和约束出现。在数学中，一个表 达式常常含有两类不同的变元，例如，∫ 1 0 f(x, t)dt， ∑n i=1 ai 等。在积分的例子中，变元 x 和 t 所起的作用是不同的；在求和的例子中，变元 n 和 i 的作用也不同。变元 t 和 i 主要 起的是占位的作用，也有人管它们叫“哑元”。哑元可以被替换成任意“新的”变元而不 影响公式的意义，比如 ∑n i=1 ai 和 ∑n j=1 aj 意义完全相同。而例中变元 x 和 n 则不能被随 便替换。逻辑中，约束变元就与哑元类似。 直观上说，一个变元是自由的如果没有任何量词“管”着它。更准确地说，我们递归 地定义“变元 x 在公式 α 中自由出现”如下： 1. 如果 α 是一个原子公式，则 x 在 α 中自由出现当且仅当 x 在 α 中出现。 2. 如果 α 为 (¬β)，则 x 在 α 中自由出现当且仅当 x 在 β 中自由出现。 3. 如果 α 为 (β → γ)，则 x 在 α 中自由出现当且仅当 x 在 β 中自由出现或在 γ 中自由 出现。 4. 如果 α 为 ∀viβ，则 x 在 α 中自由出现当且仅当 x 在 β 中自由出现并且 x ̸= vi。 6
第3章一阶逻辑的语言 第2节自由出现和约束出现 在a中出现的变元如果不是自由出现,则被称为约束出现1。 如果在公式a中没有变元自由出现,则称α为一个闭公式或语句。 分清楚自由变元与约束变元之后,我们引进一个关于替换的表达式,这在后面会经常 用到。我们用a(也有的书用a(x|t)等不同记号)表示在公式a中将变元x在其自由 出现的地方用项t替换后得到的公式。a也可以用递归的方法定义如下 (1)如果a是原子公式,则a将a中所有的x用t替换所得的表达式。 (2)(-a)=(-az) (3)(a→B)2=( →6 (4)(Vya)f is wy(a2),如果x≠v; vya,如果x 约東出现, bounded occurrence,也被译作“受囿出现
第 3 章 一阶逻辑的语言 第 2 节 自由出现和约束出现 在 α 中出现的变元如果不是自由出现，则被称为约束出现 1 。 如果在公式 α 中没有变元自由出现，则称 α 为一个闭公式 或语句 。 分清楚自由变元与约束变元之后，我们引进一个关于替换的表达式，这在后面会经常 用到。我们用 α x t （也有的书用 α(x | t) 等不同记号）表示在公式 α 中将变元 x 在其自由 出现的地方用项 t 替换后得到的公式。α x t 也可以用递归的方法定义如下： (1) 如果 α 是原子公式，则 α x t 将 α 中所有的 x 用 t 替换所得的表达式。 (2) (¬α) x t = (¬α x t )。 (3) (α → β) x t = (α x t → β x t )。 (4) (∀yα) x t is { ∀y(α x t ), 如果 x ̸= y； ∀yα, 如果 x = y。 1约束出现，bounded occurrence，也被译作“受囿出现” 7
第2节自由出现和约束出现 第3章一阶逻辑的语言
第 2 节 自由出现和约束出现 第 3 章 一阶逻辑的语言 8
第4章形式证明 第1节一阶逻辑的一个公理系统 我们回忆一下在命题逻辑中学过的知识。令A为一个公理集,并且r为一个公式集。 一个从r到φ的一个证明或推演是一个公式序列 (ao,a 使得an=φ并且对所有的i≤n,公式a;或者属于rUA,或者存在j,k<i,a是利用 分离规则从a和ak得到的(即ak=a;→a)。如果存在一个从r到φ的一个推演,则 称φ为r的一个定理,记为r+p 上述的关于证明的定义对一阶逻辑仍然适用。所不同的仅仅是我们的公理集合变得 更复杂了。推理规则依然只有分离规则 我们现在描述一个一阶逻辑推演系统的公理集A。它们被分成6组。首先我们称公式 y是公式v的一个全称概括或概括如果存在自然数n≥0和变元x1,x2,…,xn使得 y=Vx1Vx2……Vxnv 注意:当η=0时,ψ的全称概括φ就是υ本身。一阶逻辑的公理集是由形如下列公式的 概括所组成的,其中x和y为变元并且a和B为公式 1.形如命题逻辑公理中(A1),(A2),(A3)的一阶公式 2.Vra→a,其中项t可以在a中替代x。 3.Vr(a→B)→(vra→VrB); 4.a→Vaa,其中x不在a中自由出现 在语言中包含等词的情形下,还要添上 5.x≈x;
第 4 章 形式证明 第 1 节 一阶逻辑的一个公理系统 我们回忆一下在命题逻辑中学过的知识。令 Λ 为一个公理集，并且 Γ 为一个公式集。 一个从 Γ 到 φ 的一个证明或推演是一个公式序列 (α0, α1, · · · , αn) 使得 αn = φ 并且对所有的 i ≤ n，公式 αi 或者属于 Γ ∪ Λ，或者存在 j, k < i，αi 是利用 分离规则从 αj 和 αk 得到的（即 αk = αj → αi）。如果存在一个从 Γ 到 φ 的一个推演，则 称 φ 为 Γ 的一个定理，记为 Γ ⊢ φ。 上述的关于证明的定义对一阶逻辑仍然适用。所不同的仅仅是我们的公理集合变得 更复杂了。推理规则依然只有分离规则。 我们现在描述一个一阶逻辑推演系统的公理集 Λ。它们被分成 6 组。首先我们称公式 φ 是公式 ψ 的一个全称概括 或概括 如果存在自然数 n ≥ 0 和变元 x1, x2, · · · , xn 使得 φ = ∀x1∀x2 · · · ∀xnψ。 注意：当 n = 0 时，ψ 的全称概括 φ 就是 ψ 本身。一阶逻辑的公理集是由形如下列公式的 概括所组成的，其中 x 和 y 为变元并且 α 和 β 为公式： 1. 形如命题逻辑公理中 (A1), (A2), (A3) 的一阶公式； 2. ∀xα → α x t ，其中项 t 可以在 α 中替代 x。 3. ∀x(α → β) → (∀xα → ∀xβ)； 4. α → ∀xα，其中 x 不在 α 中自由出现。 在语言中包含等词的情形下，还要添上 5. x ≈ x； 9
第1节一阶逻辑的一个公理系统 第4章形式证明 6.x≈y→(a→a),其中a为原子公式并且a’是将a中若干个x的出现用y替换所 得,(这里若干个可以是零个,一个或多个,不一定是全部)。 我们逐条解释。 首先看第一组公理。如果一阶公式a是原子公式或者是全称公式,即形如vxB,则我 们称a为素公式。对于任何一阶公式φ,我们将它的所有素子公式分别替换成命题符号 就得到命题逻辑中的一个公式y。如果φ在命题逻辑中[属于公理(A1),(A2),或(A3), 或者]是重言式,我们则[分别称φ为[形如(A1),(A2)或(A3),或是](一阶意义下的) 重言式。比如下列一阶公式y wgy=Py→=Px)→(Pr→wyPy) 就是一阶逻辑中的重言式,其对应的φ为(A1→-A2)→(42→-A1)。[读了模态逻辑那 节的读者对这种想法不应该感到陌生。 根据命题逻辑里的完全性定理,我们有 定理41.如果φ是一个一阶意义下的重言式,则φ,即φ为一阶逻辑的一个内定理 我们再看第二组公理,通常称为替换公理。它的直观意义是显然的:如果α对所有 的x都对,则a对项t也对。但是由于我们正在讨论语法,而a仅仅是机械地将a中自 由出现的x换成t,如果我们不小心的话,会出现下列我们不想要的结果: 例41.令a为一阶公式yx米y。则ra→a为 xyx米y→y2米y 但是vxa→ax则成为 Vxyx米y→yy米yo 因此我们需要加些条件以区别上例中的两个替换。仔细观察表明,问题出在项t里面 的变元y在替换a中的x之后被量词彐y“抓住了”,或者说,y在替换前是自由的,而替 换后却变成约束的了。我们需要禁止这样的t来替换α中的x。固定项t和变元x我们通 过对公式α递归将短语“t在α中可以替换x”精确定义如下 (1)对原子公式α,t总可以在a中替换r。 (2)t在公式中可以替换x当且仅当t在β中可以替换x;t在公式β→γ中可以替换 x当且仅当t在β和γ中都可以替换x (3)t在公式wyB中可以替换x当且仅当
第 1 节 一阶逻辑的一个公理系统 第 4 章 形式证明 6. x ≈ y → (α → α ′ )，其中 α 为原子公式并且 α ′ 是将 α 中若干个 x 的出现用 y 替换所 得，（这里若干个可以是零个，一个或多个，不一定是全部）。 我们逐条解释。 首先看第一组公理。如果一阶公式 α 是原子公式或者是全称公式，即形如 ∀xβ，则我 们称 α 为素公式 。对于任何一阶公式 φ，我们将它的所有素子公式分别替换成命题符号， 就得到命题逻辑中的一个公式 φ ′。如果 φ ′ 在命题逻辑中 [属于公理 (A1)，(A2)，或 (A3)， 或者] 是重言式，我们则 [分别] 称 φ 为 [ 形如 (A1)，(A2) 或 (A3)，或是]（一阶意义下的） 重言式。 比如下列一阶公式 φ： (∀y¬P y → ¬P x) → (P x → ¬∀y¬P y) 就是一阶逻辑中的重言式，其对应的 φ ′ 为 (A1 → ¬A2) → (A2 → ¬A1)。[读了模态逻辑那 一节的读者对这种想法不应该感到陌生。] 根据命题逻辑里的完全性定理，我们有 定理 4.1. 如果 φ 是一个一阶意义下的重言式，则 ⊢ φ，即 φ 为一阶逻辑的一个内定理。 我们再看第二组公理，通常称为替换公理。它的直观意义是显然的：如果 α 对所有 的 x 都对，则 α 对项 t 也对。但是由于我们正在讨论语法，而 α x t 仅仅是机械地将 α 中自 由出现的 x 换成 t，如果我们不小心的话，会出现下列我们不想要的结果： 例 4.1. 令 α 为一阶公式 ∃y x ̸≈ y。则 ∀xα → α x z 为 ∀x∃y x ̸≈ y → ∃y z ̸≈ y。 但是 ∀xα → α x y 则成为 ∀x∃y x ̸≈ y → ∃y y ̸≈ y。 因此我们需要加些条件以区别上例中的两个替换。仔细观察表明，问题出在项 t 里面 的变元 y 在替换 α 中的 x 之后被量词 ∃y “抓住了”，或者说，y 在替换前是自由的，而替 换后却变成约束的了。我们需要禁止这样的 t 来替换 α 中的 x。固定项 t 和变元 x 我们通 过对公式 α 递归将短语“t 在 α 中可以替换 x”精确定义如下： (1) 对原子公式 α，t 总可以在 α 中替换 x。 (2) t 在公式 ¬β 中可以替换 x 当且仅当 t 在 β 中可以替换 x; t 在公式 β → γ 中可以替换 x 当且仅当 t 在 β 和 γ 中都可以替换 x。 (3) t 在公式 ∀yβ 中可以替换 x 当且仅当 10