第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={≈,<,0,S,+,} 1.0不是任何自然数的后继 Var(S r ?0 2.两个自然数的后继相等当且仅当这两个自然数相等 vrVy(x≈y+Sx≈Sy) 如果不使用省略的形式,则以上命题应该写作: vrvy(-(x≈y→Sx≈Sy)→=(Sx≈Sy→x≈y)。 3.给定任意公式φ(U1),数学归纳原理可以表示为以下公式 (y(0)Ar(y(x)→gp(Sx))→Wr(y(x) 4.x是素数。 首先,这个命题可以理解为 x>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 = {≈, <, 0, S, +, ·} 1. 0 不是任何自然数的后继。 ∀x(Sx ̸≈ 0)。 2. 两个自然数的后继相等当且仅当这两个自然数相等。 ∀x∀y(x ≈ y ↔ Sx ≈ Sy)。 如果不使用省略的形式，则以上命题应该写作： ∀x∀y(¬((x ≈ y → Sx ≈ Sy) → ¬(Sx ≈ Sy → x ≈ y))))。 3. 给定任意公式 φ(v1)，数学归纳原理可以表示为以下公式： (φ(0) ∧ ∀x(φ(x) → φ(Sx))) → ∀x(φ(x))。 4. x 是素数。 首先，这个命题可以理解为： x > 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