1. 从“命题”到“谓词”为什么我们需要更强大的逻辑工具在数理逻辑的入门阶段我们通常从命题逻辑开始。命题逻辑处理的是一个个完整的、可以判断真假的陈述句比如“今天下雨”或者“224”。每个命题就像一个不可分割的原子我们用字母P,Q来表示它们然后用“且∧”、“或∨”、“非¬”、“如果…那么…→”这些连接词把它们组合起来研究它们之间的真假关系。这套工具简洁有力能解决很多推理问题。但很快你就会发现它的局限性。考虑这个经典的推理“所有人都是会死的。苏格拉底是人。所以苏格拉底是会死的。”这个推理在直觉上完全正确但用命题逻辑怎么表示你可能会写成P: 所有人都是会死的Q: 苏格拉底是人R: 苏格拉底是会死的。那么推理形式就是(P ∧ Q) → R。问题来了在命题逻辑里P,Q,R是三个完全独立的命题原子(P ∧ Q) → R这个公式并不是永真式你可以轻易给P,Q赋真给R赋假使整个公式为假。这显然不符合我们对这个推理有效性的认知。问题的根源在于命题逻辑看不到命题内部的结构。“所有人都是会死的”和“苏格拉底是人”这两个命题在内部共享了“人”和“会死的”这些概念并且涉及了“所有”这个量词以及“苏格拉底”这个个体。命题逻辑这把“锤子”太钝了敲不开命题这个“核桃”看看里面是什么。于是谓词逻辑通常指一阶谓词逻辑应运而生。它就像一套精密的手术刀允许我们深入到命题内部分析其中的个体、属性和关系。它引入了两个核心武器谓词和量词。谓词用来表达个体的属性或多个个体之间的关系比如“是人”、“会死的”、“大于”量词“对所有 ∀”、“存在 ∃”则允许我们对个体域中的对象进行概括性陈述。正是这套工具让我们能够精确刻画“苏格拉底三段论”这类涉及内部结构和普遍性陈述的推理使其有效性在逻辑上得到严格证明。对于计算机科学、人工智能知识表示、自动推理、语言学、哲学和数学基础等领域的学习者来说掌握谓词逻辑是迈向形式化思维的关键一步。2. 一阶谓词逻辑公式的“零件清单”与组装规则要写出合格的一阶谓词逻辑公式就像用乐高积木搭建一个模型你必须先清楚有哪些零件以及这些零件如何合法地拼接在一起。下面我们来逐一清点这些“零件”并理解“组装手册”。2.1 基础零件符号体系一阶逻辑的语言由以下几类符号构成个体变元通常用小写字母x,y,z,u,v,w可加下标如x₁表示。它们代表论域我们讨论的对象范围比如所有人的集合、所有自然数的集合中某个不确定的个体。你可以把它们想象成代数中的变量x在未赋值前它不代表一个具体的数。个体常元通常用小写字母a,b,c,d可加下标表示。它们代表论域中一个特定的、有名有姓的个体。例如s可以特指“苏格拉底”0可以特指数字零。谓词符号通常用大写字母P,Q,R,F,G,H可加下标表示。每个谓词符号都有一个元数即它需要搭配多少个个体变元或常元才能构成一个完整的陈述。一元谓词表达个体的属性。例如Man(x)表示“x是人”Mortal(x)表示“x是會死的”。这里的Man和Mortal就是一元谓词符号。n元谓词 (n≥2)表达n个个体之间的关系。例如Loves(x, y)表示“x爱y”二元Between(x, y, z)表示“y在x和z之间”三元。函数符号通常用小写字母f,g,h可加下标表示。和谓词一样函数符号也有元数。它的作用是从个体映射到个体。例如father(x)可以表示“x的父亲”一元函数sum(x, y)表示“x与y的和”二元函数。函数符号帮助我们构造更复杂的个体项。逻辑连接词从命题逻辑继承而来包括¬非∧且∨或→蕴含如果…则…↔等价当且仅当量词一阶逻辑的标志。∀全称量词读作“对所有…”、“任意…”。∀x P(x)表示“对论域中的所有个体x性质P(x)都成立”。∃存在量词读作“存在…”、“至少有一个…”。∃x P(x)表示“在论域中至少存在一个个体x使得性质P(x)成立”。辅助符号括号(和)以及逗号,用来消除歧义标明组合关系。2.2 中间产品项Term在组装成完整句子公式之前我们先要能指称个体。项就是用来指称论域中个体的表达式。它的归纳定义是个体变元是项。个体常元是项。如果f是一个n元函数符号且t₁, t₂, ..., tₙ是项那么f(t₁, t₂, ..., tₙ)也是项。示例x变元项a常元项father(john)一元函数应用结果是项sum(x, succ(y))嵌套函数应用succ可表示后继函数结果仍是项项本身没有真假值它只是个“名字”指代某个个体。2.3 最终成品公式Formula的归纳定义公式才是可以判断真假的陈述句。它的构造有严格的递归规则原子公式如果P是一个n元谓词符号且t₁, t₂, ..., tₙ是项那么P(t₁, t₂, ..., tₙ)是一个公式称为原子公式。示例Man(s)Loves(john, mary)GreaterThan(sum(x, y), z)。复合公式如果φ和ψ是公式那么以下表达式也是公式(¬φ)非(φ ∧ ψ)且(φ ∨ ψ)或(φ → ψ)蕴含(φ ↔ ψ)等价量化公式如果φ是一个公式x是一个个体变元那么以下表达式也是公式(∀x φ)全称量化(∃x φ)存在量化关于量词作用域与约束变元的重要说明在公式∀x P(x)中量词∀x的作用域就是紧跟在它后面的公式P(x)。变元x在这个作用域内的所有出现都称为约束出现这个x称为约束变元。它就像一个局部变量其名字本身不重要可以统一改名只要不冲突重要的是它被量词所“绑定”了。如果一个变元在公式中的某次出现没有被任何量词绑定则称为自由出现是自由变元。一个公式如果不包含任何自由变元则称为闭公式或句子它才有确定的真假值。2.4 组装避坑指南常见语法错误与正确写法理解了规则还要避免踩坑。下面是一些初学者常犯的错误及其纠正错误1谓词“缺参数”或“参数类型错配”错误Man一元谓词单独出现不是公式错误Loves(john)二元谓词只给了一个参数错误∀P(x)量词只能约束个体变元x, y, z...不能约束谓词符号P正确Man(s)Loves(john, mary)∀x Man(x)错误2连接词使用不当错误Man(x) ∧连接词后面必须有公式错误∀x (Man(x) → Mortal括号不匹配蕴含词→右边不完整正确Man(x) ∧ Mortal(x)∀x (Man(x) → Mortal(x))错误3混淆项与公式错误father(x) → Mortal(father(x))father(x)是项不是公式不能直接作为→的左端正确Mortal(father(x))这是一个完整的原子公式或者P(father(x)) → Q(father(x))其中P, Q是谓词。实操心得在书写复杂公式时养成多用括号的习惯即使根据运算符优先级可以省略。这能极大避免歧义也便于自己和他人阅读。例如∀x P(x) → Q(x)可能被理解为(∀x P(x)) → Q(x)还是∀x (P(x) → Q(x))前者表示“如果所有x都满足P那么Q(x)成立”这里x在Q(x)中是自由的后者才是正确的“所有满足P的x都满足Q”。显式地写成∀x (P(x) → Q(x))就万无一失。3. 公式拆解实战从自然语言到形式化表达现在我们利用上面的“零件”和“规则”来实际翻译几个自然语言语句。这是训练谓词逻辑思维的核心。论域设定为简化我们通常将论域设定为“所有事物的集合”或根据上下文明确如“所有人的集合”。在公式中论域通常隐含在谓词的含义中。3.1 示例1“所有乌鸦都是黑色的。”识别关键元素个体乌鸦我们谈论的对象。属性是乌鸦是黑色的。量词所有。选择符号设一元谓词R(x)表示“x是乌鸦”。设一元谓词B(x)表示“x是黑色的”。构造公式语句说对于任何一个个体x如果x是乌鸦那么x是黑色的。这直接对应逻辑结构∀x (R(x) → B(x))。为什么是“蕴含→”而不是“且∧”这是初学者最容易混淆的点。∀x (R(x) ∧ B(x))的意思是“所有事物x都既是乌鸦又是黑色的”。这断言了论域中每一个事物包括你、我、这张桌子都是乌鸦且是黑色的这显然不是原句的意思。原句只对是乌鸦的那些东西做出了“是黑色”的断言对那些不是乌鸦的东西比如白天鹅原句没有做出任何声称。R(x) → B(x)恰恰捕捉了这种“如果…则…”的关系当R(x)为假x不是乌鸦时无论B(x)是真是假蕴含式R(x) → B(x)都为真这符合原句对非乌鸦事物保持沉默的直觉。3.2 示例2“存在一只白色的乌鸦。”识别关键元素个体乌鸦。属性是乌鸦是白色的。量词存在至少一只。选择符号R(x)x是乌鸦。W(x)x是白色的。构造公式语句说至少存在一个个体x使得x同时是乌鸦并且是白色的。这对应逻辑结构∃x (R(x) ∧ W(x))。为什么存在量词后用“且∧”因为我们要断言找到的同一个个体x同时满足两个属性。∃x (R(x) → W(x))则是一个很弱的、几乎总是为真的陈述因为只要找到一个不是乌鸦的x比如一块石头R(x)为假那么R(x) → W(x)就为真整个存在式就成立了这完全不是“存在白色乌鸦”的意思。3.3 示例3“每个人都有父亲。”识别关键元素个体人父亲父亲本身也是一个人。属性是人。关系…是…的父亲。量词所有每个人。选择符号Person(x)x是人。FatherOf(x, y)x是y的父亲。这是一个二元谓词或者我们也可以引入函数符号father(x)表示x的父亲一个个体。用函数符号通常更简洁。构造公式两种方式仅用谓词对于每一个人x都存在某个个体y使得y是人并且y是x的父亲。∀x (Person(x) → ∃y (Person(y) ∧ FatherOf(y, x)))使用函数符号对于每一个人xfather(x)这个个体存在这是函数符号定义的隐含要求并且我们需要断言这个个体是人。∀x (Person(x) → Person(father(x)))第二种写法更简洁直观因为它直接用father(x)这个项指代了“x的父亲”而不需要引入一个存在量词和一个新的变元y来指代同一个东西。3.4 示例4“并非所有闪光的都是金子。”这个例子展示了如何处理自然语言中的否定和量词组合。理解语义这句话等价于“存在闪光的东西它不是金子”。或者否定的是“所有闪光的东西都是金子”这个整体。选择符号Glistens(x)x闪光的。Gold(x)x是金子。构造公式先写出被否定的部分“所有闪光的都是金子”∀x (Glistens(x) → Gold(x))然后对整个公式进行否定¬∀x (Glistens(x) → Gold(x))这个公式是正确的。但我们知道¬∀x φ(x)在逻辑上等价于∃x ¬φ(x)。因此它等价于∃x ¬(Glistens(x) → Gold(x))进一步¬(P → Q)等价于P ∧ ¬Q。所以最终等价于∃x (Glistens(x) ∧ ¬Gold(x))这正是我们的直观理解“存在一个x它闪光但不是金子”。实操心得在翻译复杂语句时特别是涉及多重否定“并非所有…都不…”或量词嵌套时分步进行是关键。先翻译最内层的子句再用连接词和量词组合起来。最后可以利用逻辑等价式如¬∀x P(x) ≡ ∃x ¬P(x)¬∃x P(x) ≡ ∀x ¬P(x)¬(P→Q) ≡ P ∧ ¬Q来化简或验证公式看其是否与自然语言直觉一致。这能有效避免逻辑错误。4. 量词的相互作用与嵌套理解“所有”和“存在”的微妙差别当多个量词出现在同一个公式中时它们的顺序至关重要。交换量词顺序通常会完全改变语句的含义。这是谓词逻辑中最精妙也最容易出错的部分之一。4.1 示例对比∀∃ 与 ∃∀考虑论域是所有人Loves(x, y)表示“x爱y”。公式 A∀x ∃y Loves(x, y)解读对每一个人x都存在某个人y使得x爱y。含义每个人都爱着某个人可能每个人爱的人都不同。这描述了一种普遍的“爱他人”的能力或状态。公式 B∃y ∀x Loves(x, y)解读存在某个人y使得对所有人xx都爱y。含义存在一个被所有人爱着的人比如一个万人迷、一个圣贤。这个断言比公式A要强得多。显然B蕴含A如果有一个被所有人爱的人那么自然每个人都爱着某个人——就是那个人但A不蕴含B可能每个人都爱着别人但没有一个共同的爱慕对象。量词顺序不可随意交换。4.2 嵌套量词的翻译练习语句“每个人的每个朋友都认识某个明星。”这个语句有三个量词“每个…”、“每个…”、“某个…”。我们需要仔细梳理。识别谓词和关系Person(x)x是人。FriendOf(x, y)x是y的朋友。Knows(x, y)x认识y。Celebrity(x)x是明星。为简化我们假设论域就是人可以省略Person(x)。分步构造核心是对于任意一个人a和a的任意一个朋友bb都认识某个明星c。“b认识某个明星c”∃c (Celebrity(c) ∧ Knows(b, c))“对于a的任意一个朋友b”∀b (FriendOf(b, a) → [b认识某个明星c])“对于任意一个人a”∀a (∀b (FriendOf(b, a) → ∃c (Celebrity(c) ∧ Knows(b, c))))最终公式∀a ∀b (FriendOf(b, a) → ∃c (Celebrity(c) ∧ Knows(b, c)))注意变元a,b,c的选择是任意的只要不产生混淆。这里c的存在量词∃c在∀b的作用域内这意味着对于不同的朋友b他们认识的明星c可能是不同的。这正是原句的意思。如果原句意思是“存在一个明星被每个人的每个朋友所认识”那么量词顺序就应该是∃c ∀a ∀b (...)。这再次强调了量词顺序的决定性作用。4.3 量词与连接词的相互作用辖域分析一个变元是自由的还是约束的取决于它是否在某个量词的辖域内。分析辖域是理解公式含义的基础。示例公式∀x (P(x) ∧ ∃y Q(x, y)) → R(x)识别量词及其辖域∀x的辖域是(P(x) ∧ ∃y Q(x, y))。在这个范围内所有x都是约束变元。∃y的辖域是Q(x, y)。在这个范围内y是约束变元。分析变元x在P(x)和Q(x, y)中出现的x都在∀x的辖域内所以是约束出现。在R(x)中出现的x不在任何量词的辖域内∀x的辖域到右括号就结束了所以是自由出现。因此这个公式不是闭公式句子因为它包含自由变元x。它的真值依赖于对自由变元x的赋值。它表达的是“如果所有x都满足P(x)并且存在y使得Q(x,y)成立那么R(x)成立”——注意结论R(x)里的x是自由的和前提里的约束变元x不是同一个“东西”。这通常不是我们想要表达的意思。可能我们想让R(x)中的x也被全称量词约束那么正确的写法应该是∀x [(P(x) ∧ ∃y Q(x, y)) → R(x)]。这时整个公式才是闭公式。避坑指南在书写包含多个量词和连接词的公式时务必显式地用括号标明每个量词的辖域。仔细检查每个变元出现是自由的还是约束的确保它符合你的意图。自由变元通常表示公式中的“参数”或“未知数”而约束变元只是占位符其名字可以系统性地更改称为α-转换而不改变公式含义例如∀x P(x)和∀y P(y)是等价的。5. 一阶逻辑的语义公式何时为“真”语法告诉我们公式怎么写是正确的而语义则告诉我们一个公式在什么情况下是真的。这是通过解释和赋值来实现的。5.1 解释Interpretation一个解释I为逻辑语言中的符号赋予具体的含义它包括论域 D一个非空集合是我们讨论的所有对象的全集。对每个个体常元的指定将每个常元符号a映射到论域D中的一个特定元素a^I。对每个n元谓词符号的指定将每个谓词符号P映射到论域D上的一个n元关系P^I ⊆ Dⁿ。也就是说P^I是D中满足关系P的所有n元组的集合。对每个n元函数符号的指定将每个函数符号f映射到论域D上的一个n元函数f^I: Dⁿ → D。示例考虑语言包含常元0一元谓词Even偶数二元谓词小于二元函数加法。一个自然的解释I是论域D 自然数集合N。0^I 数字0。Even^I {0, 2, 4, 6, ...} 所有偶数的集合。^I {(m, n) | m, n ∈ N 且 m n}。^I 普通的加法运算。5.2 赋值Assignment给定一个解释I一个赋值σ是一个函数它为每个个体变元x指定论域D中的一个值σ(x)。赋值解决了自由变元指代什么对象的问题。5.3 项和公式的语义归纳定义在固定的解释I和赋值σ下我们可以计算任何项t的值t^I[σ]它是D中的一个元素以及任何公式φ的真值I ⊨ φ [σ]读作“在解释I和赋值σ下φ成立”。项的值变元x^I[σ] σ(x)常元a^I[σ] a^I由解释I直接给出函数项f(t₁, ..., tₙ)^I[σ] f^I(t₁^I[σ], ..., tₙ^I[σ])公式的真值原子公式I ⊨ P(t₁, ..., tₙ) [σ]当且仅当(t₁^I[σ], ..., tₙ^I[σ]) ∈ P^I。连接词与命题逻辑相同根据子公式的真值递归定义。例如I ⊨ (φ ∧ ψ) [σ]当且仅当I ⊨ φ [σ]且I ⊨ ψ [σ]。全称量词I ⊨ ∀x φ [σ]当且仅当对于论域D中的每一个元素d都有I ⊨ φ [σ(x:d)]成立。这里σ(x:d)表示一个与σ几乎相同的赋值除了它将变元x映射到值d。存在量词I ⊨ ∃x φ [σ]当且仅当存在论域D中的至少一个元素d使得I ⊨ φ [σ(x:d)]成立。关键点对于闭公式句子其真值不依赖于赋值σ因为其中没有自由变元。所以我们可以直接说“解释I满足句子φ”记作I ⊨ φ。5.4 语义示例验证一个公式考虑公式φ: ∀x ∃y (x y)在自然数解释I如上定义下它是一个句子吗它为真吗它是句子因为没有自由变元。要判断I ⊨ ∀x ∃y (x y)是否为真根据语义我们需要检查对每一个自然数n作为x的值是否存在一个自然数m作为y的值使得(n, m) ∈ ^I即n m。对于任意给定的自然数n我们总可以取m n1那么n n1成立。因此对每一个x我们都能找到这样的y。所以I ⊨ φ成立。这个句子在自然数解释下为真。如果我们将论域改为有限的自然数集合比如D {0, 1, 2}那么对于x2就不存在y ∈ D使得2 y。因此在这个新的解释下该句子为假。这展示了解释特别是论域如何决定公式的真假。实操心得理解语义是理解逻辑推理有效性的基础。一个推理是有效的当且仅当在所有使得前提为真的解释下结论也为真。当你对一个复杂公式的含义感到困惑时尝试为其构造一个具体的、小的解释比如论域只有两三个元素并手动计算真值这是极好的练习方法能帮你直观把握量词和连接词的相互作用。