拓冰网站定制 
如果你正在学离散数学或数理逻辑大概率会在教材、PPT和在线实训平台上反复看到这样一句话“谓词是表示个体性质或若干个体之间关系的词。”读起来每个字都认识合在一起就是不知道在说什么。我帮人看一阶谓词表示方法的练习时发现十个里至少有七个卡在这一步——不是不会写公式而是根本没理解“谓词”这个概念到底在定义什么。这篇文章就把这件事彻底讲透。我会从谓词的定义讲起把它和命题的关系理清楚然后重点拆解一阶谓词表示方法也就是怎么把一句自然语言翻译成规范的谓词公式中间会穿插大量例题、常见错误和排错经验。适合正在学离散数学、数理逻辑、人工智能基础的同学也适合准备考研复试、或者工作中要接触知识表示和形式化方法的人。放心即使你现在看到“∀”“∃”就头大跟着这篇走一遍也能把这块硬骨头啃下来。1. 先弄明白谓词到底定义了什么1.1 命题逻辑装不下的“内部结构”要理解谓词得先从命题逻辑的局限性说起。命题逻辑里一个原子命题就是一个不能再拆的盒子比如“苏格拉底是人”“苏格拉底会死”在命题逻辑里只能分别记为 P 和 Q完全没有内部结构。这样带来的麻烦是经典的苏格拉底三段论所有人都会死 苏格拉底是人 所以苏格拉底会死用命题逻辑根本没法证明它是有效的。你最多写成 (P∧Q)→R但这只是一个普通的合式公式真值表里它并不是永真式因为 R 和 P、Q 之间没有任何逻辑绑定。问题出在哪出在“所有人”和“苏格拉底”之间存在一种结构关系而这个关系被命题逻辑的原子盒子完全压扁了。谓词逻辑就是来补这个洞的它把“主语”和“谓语”拆开让“会死”成为一个可以被不同主语共享的谓词。于是上面的三段论可以写成∀x(Human(x) → Mortal(x)) Human(Socrates) 因此 Mortal(Socrates)看到区别了吗谓词让“Human”“Mortal”这些谓语成分显式出现个体Socrates也能作为独立成分被代入。这是谓词逻辑比命题逻辑强大的根本原因也是“谓词”这个概念存在的意义。1.2 谓词的定义与三个关键构件教材里的标准定义是谓词是表示个体性质或个体之间关系的语言成分。光看定义还是抽象换个角度谓词就是自然语言里“谓语”的逻辑化身。句子“小张是学生”里“是学生”就是谓语“小李喜欢小张”里“喜欢”是谓语而且它同时牵扯两个个体。要完整表达一个谓词公式需要三个关键构件个体常项表示具体的对象如 a、b、sSocrates、张三。个体变项表示论域中任意一个对象如 x、y、z。谓词符号表示性质或关系如 F、G、Human、Mortal。谓词和个体搭配后就还原成一个命题。比如 Human(Socrates) 是一个命题它有真或假Human(x) 严格来说不是命题它是一个命题形式要等 x 被赋予具体个体后才变成命题。这特别像编程里的函数谓词是函数名个体是实参返回值是真假值。你写 F(x) 就像定义一个函数F(a) 就像调用一次拿到一个布尔结果。这个“函数”类比非常重要后面做一阶谓词表示法练习时你把这个算法焊在脑子里很多问题会迎刃而解。1.3 一元谓词与多元谓词性质与关系的区别谓词有个重要参数叫“元数”也就是它接受几个个体常项或变项一元谓词表示单个个体的性质如“x 是偶数”Even(x)、“x 是红色的”Red(x)。二元谓词表示两个个体之间的关系如“x 喜欢 y”Likes(x,y)、“x 是 y 的父亲”Father(x,y)。n 元谓词表示 n 个个体之间的关系如“x 在 y 和 z 之间”Between(x,y,z)。注意参数顺序是有讲究的。Likes(x,y) 和 Likes(y,x) 在逻辑上完全不同一个说 x 喜欢 y另一个说 y 喜欢 x。我自己判题时就见过不少同学把 Father(x,y) 写成 Father(y,x)一道送分题直接白给。养成一个好习惯给多元谓词写注释时一定要写明每个参数位代表什么。比如写“Father(x,y)x 是 y 的父亲”而不是只写“Father(x,y)”。离散数学里讲关系的自反性、对称性、传递性本质上就是拿谓词公式来表达的。比如“关系 L 是自反的”写作 ∀x L(x,x)“L 是对称的”写作 ∀x∀y(L(x,y) → L(y,x))“L 是传递的”写作 ∀x∀y∀z((L(x,y) ∧ L(y,z)) → L(x,z))。所以学谓词并不只是学一堆符号它其实就是关系理论的符号化底座。2. 一阶谓词表示方法从自然语言到形式公式2.1 一阶谓词逻辑的“五件套”现在我们把注意力放到一阶谓词表示方法上。所谓“表示方法”就是把日常语言翻译成一阶谓词逻辑公式。做这件事之前先认清工具箱里有什么。一阶谓词逻辑的词汇表由五类符号组成个体常项a、b、c指特定对象。个体变项x、y、z在论域中取值的变量。谓词符号F、G、P、Q 等n 元谓词。量词∀全称量词读作“对于所有”、∃存在量词读作“存在”。联结词¬否定、∧合取、∨析取、→蕴含、↔等价。此外还需要括号、逗号这样的辅助符号个别场合会用到等号 。有了这些符号就能构造“项”和“原子公式”。个体常项和个体变项统称为项一个 n 元谓词后头跟上 n 个项就得到一个原子公式比如 P(x,a)、Likes(x,y)。原子公式通过联结词和量词组合起来就成了合式公式。这里要特别强调“一阶”的含义量词只能约束个体变项不能约束谓词。你只能写 ∀x P(x)不能写 ∀P P(x)。至于“为什么只能约束个体”后面第 5 章会具体讲这跟一阶逻辑的表达能力和完备性都有关系。2.2 四步翻译法论域、谓词、量词、联结词把一句中文翻译成一阶谓词公式很多同学上来就直接写符号结果量词乱用、联结词乱配。我的建议永远是按四步走每步都在草稿上写清楚再动笔。第一步确定论域。也就是个体变项的取值范围可以写“论域全体人类”“论域全体整数”“论域全体动物”。论域不同同一个句子翻译出来的公式结构可能完全不同。第二步抽取谓词。找出句子里所有的谓语成分为它们设定谓词符号并写明参数。第三步判定量词。看到“所有”“任意”“每一个”就用∀看到“存在”“有些”“至少有一个”就用∃看到“没有”“不存在”就用¬∃或∀加否定。第四步选择联结词。这一步最容易错。经验法则我后面会反复提到全称量词后面一般接蕴含→存在量词后面一般接合取∧。举个完整的例子。“所有学生都选修了离散数学”。论域可以设为全体学生。也可以设为全人类。先按全体学生来。谓词T(x) 表示“x 选修了离散数学”。量词“所有” - ∀。联结词只有一个谓词没有复合结构不需要额外联结词。结果∀x T(x)。但要小心如果论域是“全人类”那就不能直接写 ∀x T(x)因为这样会把“所有人都选修了离散数学”这种荒谬结论也断言出来。必须引入一个谓词限制论域S(x) 表示“x 是学生”公式改为 ∀x(S(x) → T(x))。这里用 → 而不是 ∧是因为我们不是要断言“全人类都是学生且都选课”而只是说“在满足‘是学生’的前提下进一步推出‘选课’”。再看存在量词的例子。“有些学生通过了考试”。论域全体学生。谓词P(x) 表示“x 通过了考试”。量词“有些” - ∃。联结词不需要。结果∃x P(x)。如果论域是全人类就需要 S(x) 表示“x 是学生”公式变为 ∃x(S(x) ∧ P(x))。这里用 ∧ 是因为我们要同时断言两件事x 是学生且 x 通过了考试。如果你写成 ∃x(S(x) → P(x))就会变成“存在一个对象如果它是学生则它通过了考试”只要有哪怕一个非学生对象存在这个蕴含式的前件为假整个式子就恒真语义完全崩坏。这个坑后面还会细讲。2.3 量词辖域与约束变项最容易翻车的地方量词后面跟的那个子公式叫做该量词的辖域。比如 ∀x(P(x) → Q(x)) 中量词 ∀x 的辖域是整个 (P(x) → Q(x))。处于辖域内的变项叫约束变项不在任何量词辖域内出现的变项叫自由变项。P(x) 里若 x 是自由的整个式子就不是命题只是一个命题形式。这里有两个实操中很实用的结论。第一约束变项可以换名且换名不改变语义。比如 ∀x(P(x) → Q(x)) 把 x 全部换成 y得到 ∀y(P(y) → Q(y))两者语义完全一样。但换名时不能跟其他自由变项撞名也不能把两个不同量词约束的同一个变量名搞混。比如 ∀x∃y L(x,y) 中x 和 y 各归各如果你把 y 换成 x得到 ∀x∃x L(x,x)就破坏了原有的结构语义被悄悄篡改了。第二同一个变项在公式中可能一部分约束、一部分自由。比如 ∀x P(x) ∧ Q(x) 里P(x) 中的 x 是被 ∀ 约束的而 Q(x) 中的 x 是自由的。这种公式读起来像命题但又带自由变项非常容易在读题时被忽略。规范的做法是给每个量词加括号把辖域写完整写成 ∀x(P(x)) ∧ Q(x)一眼就能看出 Q(x) 里的 x 是自由的不是一个真正的命题。画辖域的时候有个笨办法但很有效把量词的作用范围用括号括出来一开始就算挤一点也没关系等熟练了再省略。我见过太多因为辖域不清导致公式整体含义逆转的例子后面第 4 章会专门给排查清单。3. 一阶谓词表示方法典型例题实战3.1 单谓词句子的表示全称配蕴含存在配合取先看一组最基础也最常考的句子都是单谓词但结构不同。例 1凡人皆有死。论域全人类。谓词 H(x)x 是人M(x)x 会死。如果论域本身就是“人”公式是 ∀x M(x)如果论域比较宽泛比如全体生物就要写成∀x(H(x) → M(x))重点来了为什么不是 ∀x(H(x) ∧ M(x))因为 ∧ 表达的是“所有的对象既是人又会死”这等于在说论域里全是会死的人把“猫”“细菌”等其他对象全排除掉了显然不符合原意。而 → 表达的是“只要是人就会死”这正是“凡是人都……”的正确结构。记住这条铁律全称量词修饰限定性条件时后面接蕴含→。例 2有人能登上火星。论域全人类。谓词 M(x)x 能登上火星暂且用 M。写成∃x M(x)如果论域是整个宇宙中的物体则要先定义 H(x)x 是人写成 ∃x(H(x) ∧ M(x))。那为什么不是 ∃x(H(x) → M(x))前面已经说过一个简单直观的理由只要宇宙中存在哪怕一个不是人的东西比如一块石头蕴含式 H(x) → M(x) 对石头来说前件为假、整体为真于是整个 ∃x(H(x) → M(x)) 就自动为真了。这就等于说“只要宇宙中有个石头就存在能登上火星的人”荒谬。所以存在量词后面表示“既是 A 又是 B”时必须用 ∧。这两条铁律不是死记硬背的而是有真值条件做支撑的。理解之后做题速度快很多。3.2 多元关系与嵌套量词顺序决定语义单谓词只是热身真正体现一阶谓词表示方法威力的是多元谓词和嵌套量词。这里先给一个几乎必考的对比题。例 3每个学生都选了至少一门课。论域全体学生 全体课程。谓词 S(x)x 是学生C(y)y 是课程T(x,y)x 选了 y。公式∀x(S(x) → ∃y(C(y) ∧ T(x,y)))读法对任意 x如果 x 是学生那么存在某个 yy 是课程且 x 选了 y。注意量词顺序是 ∀x 在外、∃y 在内含义是每个人可以有自己不同的课。例 4存在一门课所有学生都选了它。公式∃y(C(y) ∧ ∀x(S(x) → T(x,y)))量词顺序变成 ∃y 在外、∀x 在内含义是先找出一门固定的课然后要求所有学生都选这门课。这两句话在现实里差别巨大。前者只要求每人都选课不同人选不同的课完全没问题后者强制所有人选同一门。我在批改练习时发现不少同学把这两个公式写混。这里提供一个自查方法量词里的变量谁的辖域大、谁在外层谁就先被确定。∀x∃y 是先给定一个人再找一个跟他相关的东西∃y∀x 是先找到一个东西再让所有人都跟它发生关系。人话版本前者是“每个人都各有各的妈”后者是“存在一个所有人都管它叫妈的妈”后者几乎不可能成立。再看一个有难度但经典的例子。例 5所有学生都喜欢所有老师。论域全体学生 全体老师。谓词 S(x)x 是学生T(y)y 是老师L(x,y)x 喜欢 y。公式∀x(S(x) → ∀y(T(y) → L(x,y)))这里嵌套了两层蕴含。拆开读任意学生 x任意老师 y若 x 是学生且 y 是老师则 x 喜欢 y。括清楚辖域后等价于 ∀x∀y((S(x) ∧ T(y)) → L(x,y))。这两种写法都是对的但初学时建议先把内层括号写完整再逐步简化。3.3 唯一性、否定与“没有”“并非所有”的表示接下来说三种高频句型唯一性、“没有”、和“并非所有”。例 6每个人都有且只有一个母亲。谓词 M(y,x)y 是 x 的母亲P(x)x 是人。先写“每个人都有母亲”∀x(P(x) → ∃y M(y,x))再升级为“有且只有一个”需要用合取来表达唯一性∀x(P(x) → ∃y(M(y,x) ∧ ∀z(M(z,x) → zy)))意思是存在一个 y 是 x 的母亲并且任意 z如果 z 也是 x 的母亲那么 z 和 y 是同一个对象。这就是把“唯一”翻译成了“任何竞争者都等于它”。这个写法在一阶谓词表示方法里属于进阶要求考试中如果出现注意别漏了后半段。例 7没有免费的午餐。论域全体事物。L(x)x 是午餐F(x)x 是免费的。可以写成¬∃x(L(x) ∧ F(x))也可以写成∀x(L(x) → ¬F(x))这两者是等价的依据是量词与否定交换的规律¬∃xφ 等价于 ∀x¬φ。这个换算在解题时特别常用比如“没有人喜欢被欺骗”可以先写成 ¬∃x(P(x) ∧ LikeDeceived(x))也可以改写成 ∀x(P(x) → ¬LikeDeceived(x))看你更习惯哪种形式。例 8并非所有学生都通过了考试。论域全体学生。P(x)x 通过了考试。直接按字面翻译¬∀x P(x)也可以利用等价关系改写成∃x ¬P(x)这两种都对。但注意千万不要写成 ∀x ¬P(x)那就变成了“所有学生都没通过考试”跟原句的力度完全不同。原句只否定“全部通过”允许“有的人没过有的人过了”而 ∀x ¬P(x) 则断言所有人都没过。这个区别在逻辑推理里能直接影响结论。4. 常见错误与排查技巧实录4.1 全称量词配蕴含、存在量词配合取反复验证的方法前面讲到的“全称配蕴含、存在配合取”足以排进谓词公式十大常见错误之首。这里再说深一点给你一个可以自己验证的工具。当你写完公式不确定时把量词去掉、代入一个典型对象看真值。比如公式 ∀x(S(x) → T(x))取 x 为一块石头S(石头) 为假蕴含式整体为真这没问题因为全称蕴含只约束满足条件的那部分对象对不满足的自动放行。再看 ∀x(S(x) ∧ T(x))石头会使得 S(石头) ∧ T(石头) 为假于是整个全称命题就被一块石头推翻了这显然不对。存在量词同理。∃x(S(x) ∧ T(x)) 只要找到一个是学生且通过的人即为真∃x(S(x) → T(x)) 则糟糕地允许任何非学生对象来充当那个“见证者”导致整个命题几乎无条件为真。这其实是量词与联结词互动的基本原则∀ 后接 → 是对全体做条件式声明∃ 后接 ∧ 是对存在做合取式声明。违反这条原则的公式要么过度断言导致全局崩溃要么被无关对象偷渡导致逻辑失效。4.2 否定位置与量词顺序别让一句话翻车第二个高频错误是否定放错位置第三个是量词顺序写反。先看不否定。句子“所有学生都没有缺席”正确∀x(S(x) → ¬A(x))错误¬∀x(S(x) → A(x))前者表示“每个学生都不缺席”后者表示“并非所有学生都不缺席”意思是“至少有人缺席了”与原句完全相反。之所以会错是因为有人习惯把“没有”直接翻成 ¬ 放在最前面却没有注意到否定在语义上应该作用于“缺席”这个谓词而不是作用于整个全称命题。判断否定位置的办法是先把句子拆成主谓结构想清楚“没有”修饰的是主语还是谓语。这里的“没有”修饰的是“缺席”这个行为所以 ¬ 要放在谓词 A 前面。再看不定量词顺序。考虑这个对比∀x∃y Likes(x,y)每个人都喜欢至少一个人。不同人喜欢的人可以不同。∃y∀x Likes(x,y)存在某个人所有人都喜欢他。Likes 的 y 参数被固定在同一个人身上。这两个公式的真值条件差异巨大。第一个式子在任何“每人都有自己偏好”的模型里都为真第二个式子则要求有一个“全民偶像”要求相当苛刻。做题时如果搞反顺序等于把问题从简单模式换成了地狱模式结论必然跑偏。我的自查习惯是把每个量词翻译成一句中文按从左到右的顺序朗读一遍看是否顺口且符合原意。∀x∃y 读作“对于每一个 x存在一个 y……”∃y∀x 读作“存在一个 y对于所有 x……”顺一遍自然就发现区别了。4.3 一阶谓词表示方法速查表把上面这些经验整理成一张表做题时贴在手边非常实用。要表达的句子推荐的谓词公式写法常见错误写法错误的原因所有 A 都是 B∀x(A(x) → B(x))∀x(A(x) ∧ B(x))后者断言论域中万物皆为 A 且 B过强有些 A 是 B∃x(A(x) ∧ B(x))∃x(A(x) → B(x))后者被任意非 A 对象偷渡为真失去意义没有 A 是 B∀x(A(x) → ¬B(x))¬∀x(A(x) → B(x))后者只是“并非所有 A 都是 B”允许一部分 A 是 B并非所有 A 都是 B¬∀x(A(x) → B(x))∀x(A(x) → ¬B(x))后者变成“所有 A 都不是 B”语义过强每个人都有至少一个 y∀x∃y L(x,y)∃y∀x L(x,y)后者要求所有 x 共享同一个 y条件过强这张表不需要背你把它从头到尾自己推导一遍感受每个错写在真值表下的后果以后写公式就会形成条件反射。5. 谓词不止在习题里现实应用与延伸5.1 数据库查询语言与谓词的底层关联很多人以为一阶谓词只活在数学课本里其实数据库就是一个巨大的谓词应用场。SQL 的 WHERE 子句本质上就是在有限论域上对谓词公式做求值。比如SELECT * FROM students WHERE age 18 AND major CS等价于对 students 论域中的每个对象 x 求值AgeGreaterThan18(x) ∧ MajorIsCS(x)条件成立就返回这一行不成立就过滤掉。再看稍微复杂一点的 NOT EXISTS 子查询它对应的就是 ¬∃ 的语义。JOIN 操作则可以理解成把两个关系里的元组通过共享变量做合取连接。这也是为什么很多计算机专业的学生学离散数学时觉得抽象学到数据库原理时突然“开窍”了——因为一阶谓词就是数据库查询语言背后的逻辑内核。理解这一层对你写 SQL 也有实际帮助。比如你知道“全称量词配蕴含”这个逻辑规则写“找出选了所有课程的学生”这类查询时就不会天真地直接用一个简单聚合去硬套而是能想到用 EXISTS 加 NOT EXISTS 的双重否定来实现。逻辑学能帮你改写查询语句的等价形式这在实际优化中很常见。5.2 知识图谱、逻辑编程与自动推理再往大了看整个知识表示领域都建立在谓词的基础上。知识图谱里的三元组 (主语, 谓词, 宾语)比如 (张三, fatherOf, 张小三)这里的“谓词”其实就是一个二元谓词 Father(x,y) 的实例化。RDF、OWL 这些语义网标准本质上是限定了一类特殊的谓词逻辑语言叫描述逻辑用它来表达概念之间的包含关系、属性约束和个体断言。逻辑编程语言 Prolog 更是直接把这个思想暴露在外。你写parent(X, Y)就是在定义一个二元谓词写规则时更像是在写一阶逻辑公式。比如定义祖先关系ancestor(X, Z) :- parent(X, Y), ancestor(Y, Z).这个规则翻译成逻辑语言就是对于任意 X、Y、Z如果 parent(X, Y) 且 ancestor(Y, Z)则 ancestor(X, Z)。可以看到Prolog 程序本身就是一组一阶谓词公式的子集霍恩子句它要回答一个查询本质上是证明一个目标公式能从已知公理中推出。自动定理证明和程序验证领域里SMT 求解器比如 Z3内部处理的就是一批一阶逻辑公式的可满足性问题。你在程序里写一个断言assert(x y z)它对应的就是一条带算术约束的谓词公式求解器会判断是否存在一组变量取值让整个公式组成立。这已经是非常成熟且实际落地的技术。学好谓词表示等于打通了从逻辑学通向人工智能、形式化验证的任督二脉。5.3 为什么叫“一阶”与二阶逻辑的边界最后回答一个很多人从不问、但一问就会卡住的问题为什么叫“一阶”因为在一阶谓词逻辑里量词只能约束个体变项不能约束谓词变项。你只能说“存在某个个体 x使得 P(x) 成立”但不能说“存在某个性质 P使得 P(x) 成立”。后者属于二阶逻辑的范畴。这里“阶”指的是被量化的对象的层次个体是第 0 层性质即一元谓词和关系多元谓词是第 1 层性质的集合、关系的关系是更高层。为什么数学家普遍偏爱一阶逻辑一个重要原因是一阶逻辑有哥德尔完备性定理所有一阶有效公式都能在一个可靠且完备的证明系统里被推出来。这意味着一阶逻辑的推理有扎实的算法基础可以构建自动推理工具。二阶逻辑的表达能力更强但失去了完备性自动化推理变得困难得多。“一阶谓词表示方法”里的“一阶”强调的正是我们只对个体做量化而谓词作为模板被固定下来这样既保留强大的表达力又保持推理的可计算性。这也是为什么实际工程里知识图谱、语义网、程序验证大多建立在一阶谓词或其子语言之上而不是一上来就上二阶逻辑。最后说点个人体会。学谓词表示最忌讳的是只看不练就像学外语只背单词不造句一到实际场景必然僵硬。我的经验是拿到一阶谓词表示方法的题目先在纸上写下“论域谓词量词联结词”四行再一格格填空填完检查量词顺序和蕴含/合取的选择。这套流程看起来慢但稳稳当当。等你做完二十道题熟练之后就会形成条件反射看到“所有”自动想到 ∀ 和 →看到“有些”自动想到 ∃ 和 ∧。这个门槛一旦迈过去离散数学后面很多内容比如关系的性质、函数的定义、归纳法证明都会顺畅很多。 一阶谓词表示方法详解：概念、翻译四步法与常见错误
如果你正在学离散数学或数理逻辑大概率会在教材、PPT和在线实训平台上反复看到这样一句话“谓词是表示个体性质或若干个体之间关系的词。”读起来每个字都认识合在一起就是不知道在说什么。我帮人看一阶谓词表示方法的练习时发现十个里至少有七个卡在这一步——不是不会写公式而是根本没理解“谓词”这个概念到底在定义什么。这篇文章就把这件事彻底讲透。我会从谓词的定义讲起把它和命题的关系理清楚然后重点拆解一阶谓词表示方法也就是怎么把一句自然语言翻译成规范的谓词公式中间会穿插大量例题、常见错误和排错经验。适合正在学离散数学、数理逻辑、人工智能基础的同学也适合准备考研复试、或者工作中要接触知识表示和形式化方法的人。放心即使你现在看到“∀”“∃”就头大跟着这篇走一遍也能把这块硬骨头啃下来。1. 先弄明白谓词到底定义了什么1.1 命题逻辑装不下的“内部结构”要理解谓词得先从命题逻辑的局限性说起。命题逻辑里一个原子命题就是一个不能再拆的盒子比如“苏格拉底是人”“苏格拉底会死”在命题逻辑里只能分别记为 P 和 Q完全没有内部结构。这样带来的麻烦是经典的苏格拉底三段论所有人都会死 苏格拉底是人 所以苏格拉底会死用命题逻辑根本没法证明它是有效的。你最多写成 (P∧Q)→R但这只是一个普通的合式公式真值表里它并不是永真式因为 R 和 P、Q 之间没有任何逻辑绑定。问题出在哪出在“所有人”和“苏格拉底”之间存在一种结构关系而这个关系被命题逻辑的原子盒子完全压扁了。谓词逻辑就是来补这个洞的它把“主语”和“谓语”拆开让“会死”成为一个可以被不同主语共享的谓词。于是上面的三段论可以写成∀x(Human(x) → Mortal(x)) Human(Socrates) 因此 Mortal(Socrates)看到区别了吗谓词让“Human”“Mortal”这些谓语成分显式出现个体Socrates也能作为独立成分被代入。这是谓词逻辑比命题逻辑强大的根本原因也是“谓词”这个概念存在的意义。1.2 谓词的定义与三个关键构件教材里的标准定义是谓词是表示个体性质或个体之间关系的语言成分。光看定义还是抽象换个角度谓词就是自然语言里“谓语”的逻辑化身。句子“小张是学生”里“是学生”就是谓语“小李喜欢小张”里“喜欢”是谓语而且它同时牵扯两个个体。要完整表达一个谓词公式需要三个关键构件个体常项表示具体的对象如 a、b、sSocrates、张三。个体变项表示论域中任意一个对象如 x、y、z。谓词符号表示性质或关系如 F、G、Human、Mortal。谓词和个体搭配后就还原成一个命题。比如 Human(Socrates) 是一个命题它有真或假Human(x) 严格来说不是命题它是一个命题形式要等 x 被赋予具体个体后才变成命题。这特别像编程里的函数谓词是函数名个体是实参返回值是真假值。你写 F(x) 就像定义一个函数F(a) 就像调用一次拿到一个布尔结果。这个“函数”类比非常重要后面做一阶谓词表示法练习时你把这个算法焊在脑子里很多问题会迎刃而解。1.3 一元谓词与多元谓词性质与关系的区别谓词有个重要参数叫“元数”也就是它接受几个个体常项或变项一元谓词表示单个个体的性质如“x 是偶数”Even(x)、“x 是红色的”Red(x)。二元谓词表示两个个体之间的关系如“x 喜欢 y”Likes(x,y)、“x 是 y 的父亲”Father(x,y)。n 元谓词表示 n 个个体之间的关系如“x 在 y 和 z 之间”Between(x,y,z)。注意参数顺序是有讲究的。Likes(x,y) 和 Likes(y,x) 在逻辑上完全不同一个说 x 喜欢 y另一个说 y 喜欢 x。我自己判题时就见过不少同学把 Father(x,y) 写成 Father(y,x)一道送分题直接白给。养成一个好习惯给多元谓词写注释时一定要写明每个参数位代表什么。比如写“Father(x,y)x 是 y 的父亲”而不是只写“Father(x,y)”。离散数学里讲关系的自反性、对称性、传递性本质上就是拿谓词公式来表达的。比如“关系 L 是自反的”写作 ∀x L(x,x)“L 是对称的”写作 ∀x∀y(L(x,y) → L(y,x))“L 是传递的”写作 ∀x∀y∀z((L(x,y) ∧ L(y,z)) → L(x,z))。所以学谓词并不只是学一堆符号它其实就是关系理论的符号化底座。2. 一阶谓词表示方法从自然语言到形式公式2.1 一阶谓词逻辑的“五件套”现在我们把注意力放到一阶谓词表示方法上。所谓“表示方法”就是把日常语言翻译成一阶谓词逻辑公式。做这件事之前先认清工具箱里有什么。一阶谓词逻辑的词汇表由五类符号组成个体常项a、b、c指特定对象。个体变项x、y、z在论域中取值的变量。谓词符号F、G、P、Q 等n 元谓词。量词∀全称量词读作“对于所有”、∃存在量词读作“存在”。联结词¬否定、∧合取、∨析取、→蕴含、↔等价。此外还需要括号、逗号这样的辅助符号个别场合会用到等号 。有了这些符号就能构造“项”和“原子公式”。个体常项和个体变项统称为项一个 n 元谓词后头跟上 n 个项就得到一个原子公式比如 P(x,a)、Likes(x,y)。原子公式通过联结词和量词组合起来就成了合式公式。这里要特别强调“一阶”的含义量词只能约束个体变项不能约束谓词。你只能写 ∀x P(x)不能写 ∀P P(x)。至于“为什么只能约束个体”后面第 5 章会具体讲这跟一阶逻辑的表达能力和完备性都有关系。2.2 四步翻译法论域、谓词、量词、联结词把一句中文翻译成一阶谓词公式很多同学上来就直接写符号结果量词乱用、联结词乱配。我的建议永远是按四步走每步都在草稿上写清楚再动笔。第一步确定论域。也就是个体变项的取值范围可以写“论域全体人类”“论域全体整数”“论域全体动物”。论域不同同一个句子翻译出来的公式结构可能完全不同。第二步抽取谓词。找出句子里所有的谓语成分为它们设定谓词符号并写明参数。第三步判定量词。看到“所有”“任意”“每一个”就用∀看到“存在”“有些”“至少有一个”就用∃看到“没有”“不存在”就用¬∃或∀加否定。第四步选择联结词。这一步最容易错。经验法则我后面会反复提到全称量词后面一般接蕴含→存在量词后面一般接合取∧。举个完整的例子。“所有学生都选修了离散数学”。论域可以设为全体学生。也可以设为全人类。先按全体学生来。谓词T(x) 表示“x 选修了离散数学”。量词“所有” - ∀。联结词只有一个谓词没有复合结构不需要额外联结词。结果∀x T(x)。但要小心如果论域是“全人类”那就不能直接写 ∀x T(x)因为这样会把“所有人都选修了离散数学”这种荒谬结论也断言出来。必须引入一个谓词限制论域S(x) 表示“x 是学生”公式改为 ∀x(S(x) → T(x))。这里用 → 而不是 ∧是因为我们不是要断言“全人类都是学生且都选课”而只是说“在满足‘是学生’的前提下进一步推出‘选课’”。再看存在量词的例子。“有些学生通过了考试”。论域全体学生。谓词P(x) 表示“x 通过了考试”。量词“有些” - ∃。联结词不需要。结果∃x P(x)。如果论域是全人类就需要 S(x) 表示“x 是学生”公式变为 ∃x(S(x) ∧ P(x))。这里用 ∧ 是因为我们要同时断言两件事x 是学生且 x 通过了考试。如果你写成 ∃x(S(x) → P(x))就会变成“存在一个对象如果它是学生则它通过了考试”只要有哪怕一个非学生对象存在这个蕴含式的前件为假整个式子就恒真语义完全崩坏。这个坑后面还会细讲。2.3 量词辖域与约束变项最容易翻车的地方量词后面跟的那个子公式叫做该量词的辖域。比如 ∀x(P(x) → Q(x)) 中量词 ∀x 的辖域是整个 (P(x) → Q(x))。处于辖域内的变项叫约束变项不在任何量词辖域内出现的变项叫自由变项。P(x) 里若 x 是自由的整个式子就不是命题只是一个命题形式。这里有两个实操中很实用的结论。第一约束变项可以换名且换名不改变语义。比如 ∀x(P(x) → Q(x)) 把 x 全部换成 y得到 ∀y(P(y) → Q(y))两者语义完全一样。但换名时不能跟其他自由变项撞名也不能把两个不同量词约束的同一个变量名搞混。比如 ∀x∃y L(x,y) 中x 和 y 各归各如果你把 y 换成 x得到 ∀x∃x L(x,x)就破坏了原有的结构语义被悄悄篡改了。第二同一个变项在公式中可能一部分约束、一部分自由。比如 ∀x P(x) ∧ Q(x) 里P(x) 中的 x 是被 ∀ 约束的而 Q(x) 中的 x 是自由的。这种公式读起来像命题但又带自由变项非常容易在读题时被忽略。规范的做法是给每个量词加括号把辖域写完整写成 ∀x(P(x)) ∧ Q(x)一眼就能看出 Q(x) 里的 x 是自由的不是一个真正的命题。画辖域的时候有个笨办法但很有效把量词的作用范围用括号括出来一开始就算挤一点也没关系等熟练了再省略。我见过太多因为辖域不清导致公式整体含义逆转的例子后面第 4 章会专门给排查清单。3. 一阶谓词表示方法典型例题实战3.1 单谓词句子的表示全称配蕴含存在配合取先看一组最基础也最常考的句子都是单谓词但结构不同。例 1凡人皆有死。论域全人类。谓词 H(x)x 是人M(x)x 会死。如果论域本身就是“人”公式是 ∀x M(x)如果论域比较宽泛比如全体生物就要写成∀x(H(x) → M(x))重点来了为什么不是 ∀x(H(x) ∧ M(x))因为 ∧ 表达的是“所有的对象既是人又会死”这等于在说论域里全是会死的人把“猫”“细菌”等其他对象全排除掉了显然不符合原意。而 → 表达的是“只要是人就会死”这正是“凡是人都……”的正确结构。记住这条铁律全称量词修饰限定性条件时后面接蕴含→。例 2有人能登上火星。论域全人类。谓词 M(x)x 能登上火星暂且用 M。写成∃x M(x)如果论域是整个宇宙中的物体则要先定义 H(x)x 是人写成 ∃x(H(x) ∧ M(x))。那为什么不是 ∃x(H(x) → M(x))前面已经说过一个简单直观的理由只要宇宙中存在哪怕一个不是人的东西比如一块石头蕴含式 H(x) → M(x) 对石头来说前件为假、整体为真于是整个 ∃x(H(x) → M(x)) 就自动为真了。这就等于说“只要宇宙中有个石头就存在能登上火星的人”荒谬。所以存在量词后面表示“既是 A 又是 B”时必须用 ∧。这两条铁律不是死记硬背的而是有真值条件做支撑的。理解之后做题速度快很多。3.2 多元关系与嵌套量词顺序决定语义单谓词只是热身真正体现一阶谓词表示方法威力的是多元谓词和嵌套量词。这里先给一个几乎必考的对比题。例 3每个学生都选了至少一门课。论域全体学生 全体课程。谓词 S(x)x 是学生C(y)y 是课程T(x,y)x 选了 y。公式∀x(S(x) → ∃y(C(y) ∧ T(x,y)))读法对任意 x如果 x 是学生那么存在某个 yy 是课程且 x 选了 y。注意量词顺序是 ∀x 在外、∃y 在内含义是每个人可以有自己不同的课。例 4存在一门课所有学生都选了它。公式∃y(C(y) ∧ ∀x(S(x) → T(x,y)))量词顺序变成 ∃y 在外、∀x 在内含义是先找出一门固定的课然后要求所有学生都选这门课。这两句话在现实里差别巨大。前者只要求每人都选课不同人选不同的课完全没问题后者强制所有人选同一门。我在批改练习时发现不少同学把这两个公式写混。这里提供一个自查方法量词里的变量谁的辖域大、谁在外层谁就先被确定。∀x∃y 是先给定一个人再找一个跟他相关的东西∃y∀x 是先找到一个东西再让所有人都跟它发生关系。人话版本前者是“每个人都各有各的妈”后者是“存在一个所有人都管它叫妈的妈”后者几乎不可能成立。再看一个有难度但经典的例子。例 5所有学生都喜欢所有老师。论域全体学生 全体老师。谓词 S(x)x 是学生T(y)y 是老师L(x,y)x 喜欢 y。公式∀x(S(x) → ∀y(T(y) → L(x,y)))这里嵌套了两层蕴含。拆开读任意学生 x任意老师 y若 x 是学生且 y 是老师则 x 喜欢 y。括清楚辖域后等价于 ∀x∀y((S(x) ∧ T(y)) → L(x,y))。这两种写法都是对的但初学时建议先把内层括号写完整再逐步简化。3.3 唯一性、否定与“没有”“并非所有”的表示接下来说三种高频句型唯一性、“没有”、和“并非所有”。例 6每个人都有且只有一个母亲。谓词 M(y,x)y 是 x 的母亲P(x)x 是人。先写“每个人都有母亲”∀x(P(x) → ∃y M(y,x))再升级为“有且只有一个”需要用合取来表达唯一性∀x(P(x) → ∃y(M(y,x) ∧ ∀z(M(z,x) → zy)))意思是存在一个 y 是 x 的母亲并且任意 z如果 z 也是 x 的母亲那么 z 和 y 是同一个对象。这就是把“唯一”翻译成了“任何竞争者都等于它”。这个写法在一阶谓词表示方法里属于进阶要求考试中如果出现注意别漏了后半段。例 7没有免费的午餐。论域全体事物。L(x)x 是午餐F(x)x 是免费的。可以写成¬∃x(L(x) ∧ F(x))也可以写成∀x(L(x) → ¬F(x))这两者是等价的依据是量词与否定交换的规律¬∃xφ 等价于 ∀x¬φ。这个换算在解题时特别常用比如“没有人喜欢被欺骗”可以先写成 ¬∃x(P(x) ∧ LikeDeceived(x))也可以改写成 ∀x(P(x) → ¬LikeDeceived(x))看你更习惯哪种形式。例 8并非所有学生都通过了考试。论域全体学生。P(x)x 通过了考试。直接按字面翻译¬∀x P(x)也可以利用等价关系改写成∃x ¬P(x)这两种都对。但注意千万不要写成 ∀x ¬P(x)那就变成了“所有学生都没通过考试”跟原句的力度完全不同。原句只否定“全部通过”允许“有的人没过有的人过了”而 ∀x ¬P(x) 则断言所有人都没过。这个区别在逻辑推理里能直接影响结论。4. 常见错误与排查技巧实录4.1 全称量词配蕴含、存在量词配合取反复验证的方法前面讲到的“全称配蕴含、存在配合取”足以排进谓词公式十大常见错误之首。这里再说深一点给你一个可以自己验证的工具。当你写完公式不确定时把量词去掉、代入一个典型对象看真值。比如公式 ∀x(S(x) → T(x))取 x 为一块石头S(石头) 为假蕴含式整体为真这没问题因为全称蕴含只约束满足条件的那部分对象对不满足的自动放行。再看 ∀x(S(x) ∧ T(x))石头会使得 S(石头) ∧ T(石头) 为假于是整个全称命题就被一块石头推翻了这显然不对。存在量词同理。∃x(S(x) ∧ T(x)) 只要找到一个是学生且通过的人即为真∃x(S(x) → T(x)) 则糟糕地允许任何非学生对象来充当那个“见证者”导致整个命题几乎无条件为真。这其实是量词与联结词互动的基本原则∀ 后接 → 是对全体做条件式声明∃ 后接 ∧ 是对存在做合取式声明。违反这条原则的公式要么过度断言导致全局崩溃要么被无关对象偷渡导致逻辑失效。4.2 否定位置与量词顺序别让一句话翻车第二个高频错误是否定放错位置第三个是量词顺序写反。先看不否定。句子“所有学生都没有缺席”正确∀x(S(x) → ¬A(x))错误¬∀x(S(x) → A(x))前者表示“每个学生都不缺席”后者表示“并非所有学生都不缺席”意思是“至少有人缺席了”与原句完全相反。之所以会错是因为有人习惯把“没有”直接翻成 ¬ 放在最前面却没有注意到否定在语义上应该作用于“缺席”这个谓词而不是作用于整个全称命题。判断否定位置的办法是先把句子拆成主谓结构想清楚“没有”修饰的是主语还是谓语。这里的“没有”修饰的是“缺席”这个行为所以 ¬ 要放在谓词 A 前面。再看不定量词顺序。考虑这个对比∀x∃y Likes(x,y)每个人都喜欢至少一个人。不同人喜欢的人可以不同。∃y∀x Likes(x,y)存在某个人所有人都喜欢他。Likes 的 y 参数被固定在同一个人身上。这两个公式的真值条件差异巨大。第一个式子在任何“每人都有自己偏好”的模型里都为真第二个式子则要求有一个“全民偶像”要求相当苛刻。做题时如果搞反顺序等于把问题从简单模式换成了地狱模式结论必然跑偏。我的自查习惯是把每个量词翻译成一句中文按从左到右的顺序朗读一遍看是否顺口且符合原意。∀x∃y 读作“对于每一个 x存在一个 y……”∃y∀x 读作“存在一个 y对于所有 x……”顺一遍自然就发现区别了。4.3 一阶谓词表示方法速查表把上面这些经验整理成一张表做题时贴在手边非常实用。要表达的句子推荐的谓词公式写法常见错误写法错误的原因所有 A 都是 B∀x(A(x) → B(x))∀x(A(x) ∧ B(x))后者断言论域中万物皆为 A 且 B过强有些 A 是 B∃x(A(x) ∧ B(x))∃x(A(x) → B(x))后者被任意非 A 对象偷渡为真失去意义没有 A 是 B∀x(A(x) → ¬B(x))¬∀x(A(x) → B(x))后者只是“并非所有 A 都是 B”允许一部分 A 是 B并非所有 A 都是 B¬∀x(A(x) → B(x))∀x(A(x) → ¬B(x))后者变成“所有 A 都不是 B”语义过强每个人都有至少一个 y∀x∃y L(x,y)∃y∀x L(x,y)后者要求所有 x 共享同一个 y条件过强这张表不需要背你把它从头到尾自己推导一遍感受每个错写在真值表下的后果以后写公式就会形成条件反射。5. 谓词不止在习题里现实应用与延伸5.1 数据库查询语言与谓词的底层关联很多人以为一阶谓词只活在数学课本里其实数据库就是一个巨大的谓词应用场。SQL 的 WHERE 子句本质上就是在有限论域上对谓词公式做求值。比如SELECT * FROM students WHERE age 18 AND major CS等价于对 students 论域中的每个对象 x 求值AgeGreaterThan18(x) ∧ MajorIsCS(x)条件成立就返回这一行不成立就过滤掉。再看稍微复杂一点的 NOT EXISTS 子查询它对应的就是 ¬∃ 的语义。JOIN 操作则可以理解成把两个关系里的元组通过共享变量做合取连接。这也是为什么很多计算机专业的学生学离散数学时觉得抽象学到数据库原理时突然“开窍”了——因为一阶谓词就是数据库查询语言背后的逻辑内核。理解这一层对你写 SQL 也有实际帮助。比如你知道“全称量词配蕴含”这个逻辑规则写“找出选了所有课程的学生”这类查询时就不会天真地直接用一个简单聚合去硬套而是能想到用 EXISTS 加 NOT EXISTS 的双重否定来实现。逻辑学能帮你改写查询语句的等价形式这在实际优化中很常见。5.2 知识图谱、逻辑编程与自动推理再往大了看整个知识表示领域都建立在谓词的基础上。知识图谱里的三元组 (主语, 谓词, 宾语)比如 (张三, fatherOf, 张小三)这里的“谓词”其实就是一个二元谓词 Father(x,y) 的实例化。RDF、OWL 这些语义网标准本质上是限定了一类特殊的谓词逻辑语言叫描述逻辑用它来表达概念之间的包含关系、属性约束和个体断言。逻辑编程语言 Prolog 更是直接把这个思想暴露在外。你写parent(X, Y)就是在定义一个二元谓词写规则时更像是在写一阶逻辑公式。比如定义祖先关系ancestor(X, Z) :- parent(X, Y), ancestor(Y, Z).这个规则翻译成逻辑语言就是对于任意 X、Y、Z如果 parent(X, Y) 且 ancestor(Y, Z)则 ancestor(X, Z)。可以看到Prolog 程序本身就是一组一阶谓词公式的子集霍恩子句它要回答一个查询本质上是证明一个目标公式能从已知公理中推出。自动定理证明和程序验证领域里SMT 求解器比如 Z3内部处理的就是一批一阶逻辑公式的可满足性问题。你在程序里写一个断言assert(x y z)它对应的就是一条带算术约束的谓词公式求解器会判断是否存在一组变量取值让整个公式组成立。这已经是非常成熟且实际落地的技术。学好谓词表示等于打通了从逻辑学通向人工智能、形式化验证的任督二脉。5.3 为什么叫“一阶”与二阶逻辑的边界最后回答一个很多人从不问、但一问就会卡住的问题为什么叫“一阶”因为在一阶谓词逻辑里量词只能约束个体变项不能约束谓词变项。你只能说“存在某个个体 x使得 P(x) 成立”但不能说“存在某个性质 P使得 P(x) 成立”。后者属于二阶逻辑的范畴。这里“阶”指的是被量化的对象的层次个体是第 0 层性质即一元谓词和关系多元谓词是第 1 层性质的集合、关系的关系是更高层。为什么数学家普遍偏爱一阶逻辑一个重要原因是一阶逻辑有哥德尔完备性定理所有一阶有效公式都能在一个可靠且完备的证明系统里被推出来。这意味着一阶逻辑的推理有扎实的算法基础可以构建自动推理工具。二阶逻辑的表达能力更强但失去了完备性自动化推理变得困难得多。“一阶谓词表示方法”里的“一阶”强调的正是我们只对个体做量化而谓词作为模板被固定下来这样既保留强大的表达力又保持推理的可计算性。这也是为什么实际工程里知识图谱、语义网、程序验证大多建立在一阶谓词或其子语言之上而不是一上来就上二阶逻辑。最后说点个人体会。学谓词表示最忌讳的是只看不练就像学外语只背单词不造句一到实际场景必然僵硬。我的经验是拿到一阶谓词表示方法的题目先在纸上写下“论域谓词量词联结词”四行再一格格填空填完检查量词顺序和蕴含/合取的选择。这套流程看起来慢但稳稳当当。等你做完二十道题熟练之后就会形成条件反射看到“所有”自动想到 ∀ 和 →看到“有些”自动想到 ∃ 和 ∧。这个门槛一旦迈过去离散数学后面很多内容比如关系的性质、函数的定义、归纳法证明都会顺畅很多。