Skip to content

谓词逻辑

集合 & 数学符号与逻辑命题

命题逻辑的局限性与谓词逻辑

命题逻辑把整句话当成一个命题变元，只能回答「真/假」，看不出句子内部的结构。典型例子是苏格拉底三段论：「所有人都是要死的」「苏格拉底是人」→「苏格拉底是要死的」。在命题逻辑里，\(P,Q,R\) 三个命题之间没有能从 \(P,Q\) 推出 \(R\) 的形式结构，所以无法证明这个推理。

逻辑联系往往藏在「主语、性质、关系、数量」里，需要把句子拆开——这就是谓词逻辑（一阶逻辑）要做的事。

命题符号化的三个基本要素

要素 含义（直观） 记号习惯
个体词 被讨论的对象（具体或抽象） 常项 \(a,b,c,\ldots\)；变项 \(x,y,z,\ldots\)
谓词 对象的性质或对象之间的关系 \(F,G,H,\ldots\)；\(n\) 元谓词写 \(F(x_1,\ldots,x_n)\)
量词 「全体」或「存在」 全称 \(\forall\)；存在 \(\exists\)

  • \(P\)：谓词

  • \(x\)：个体词

  • \(P(x)\)：命题函数（含变项时在指定赋值前一般还不是命题）

其他定义

  • 个体常项：表示特定客体

  • 个体变项：表示泛指客体

  • 个体域：变项的取值范围；可以是有限集或 \(\mathbb{N},\mathbb{Z},\mathbb{R}\) 等。若讲课/做题未写明个体域，常默认使用全总个体域（「一切事物」），再用特性谓词限制范围（见 §4）。

  • 谓词常项：具体性质/关系

  • 谓词变项：抽象泛指

  • \(n\) 元谓词：含 \(n\) 个个体变项；\(n=1\) 为一元谓词

  • 零元谓词：不含个体变项，本质上就是命题

特性谓词与全总个体域

把个体域统一成全总个体域时，对「限制范围」要引入特性谓词 \(M(x)\)（如「\(x\) 是人」）：

  • 全称量词：特性谓词作蕴涵的前件

    Example

    「所有人长黑头发」——令 \(M(x)\)：\(x\) 是人，\(F(x)\)：\(x\) 长黑头发，符号化为 \(\forall x\,(M(x)\to F(x))\)。

  • 存在量词：特性谓词作合取的一支

    Example

    「有人登过月球」——\(\exists x\,(M(x)\land G(x))\)。

不要写反

全称很少与 \(\land\) 搭配、存在很少与 \(\to\) 搭配（否则容易变成「废话真」或不符合原意）。

一阶语言与合式公式

  • 字母表：个体常项与变项、函数符号、谓词符号、\(\forall,\exists\)、联结词 \(\neg,\land,\lor,\to,\leftrightarrow\)、括号与逗号等

  • 项：个体常项、变项是项；若 \(f\) 是 \(n\) 元函数符号，\(t_1,\ldots,t_n\) 是项，则 \(f(t_1,\ldots,t_n)\) 是项

  • 原子公式：若 \(R\) 是 \(n\) 元谓词，\(t_1,\ldots,t_n\) 是项，则 \(R(t_1,\ldots,t_n)\) 是原子公式

  • 合式公式：

    • 原子公式是公式

    • 若 \(A,B\) 是公式，则 \(\neg A,\ A\land B,\ A\lor B,\ A\to B,\ A\leftrightarrow B\) 是公式

    • 若 \(A\) 是公式，\(x\) 是个体变项，则 \(\forall x\,A,\ \exists x\,A\) 是公式

    • 仅由有限次使用前三点得到的是公式

为方便可省略最外层括号。

指导变元、辖域、自由出现与约束出现

  • 在 \(\forall x\,A\) 与 \(\exists x\,A\) 中：

    • \(x\) 是指导变元

    • \(A\) 是该量词的辖域

    • 辖域内 \(x\) 的出现是约束出现；不是约束出现的变项出现叫自由出现

  • 闭式：公式中没有自由出现的个体变项。闭式在给定解释下通常是命题

  • 换名规则：把某量词辖域里约束出现的指导变元及其辖域内该变元的出现，改成公式中未出现过的新变元符号，避免同一变元既约束又自由

  • 代替规则：把某自由变项的全部出现换成公式中未出现过的新变元

解释与赋值

解释 \(I\)包含：

  1. 非空个体域 \(D\)

  2. 为每个个体常项指定 \(D\) 中元素

  3. 为每个函数符号指定 \(D\) 上的函数

  4. 为每个谓词符号指定 \(D\) 上的关系（谓词）

对含自由变项的公式，往往还要对自由变项做赋值才能谈真值；闭式只需解释。

公式的类型

Review

可与命题逻辑类比。

  • 永真式（逻辑有效式）：任一解释下均为真

  • 矛盾式（永假式）：任一解释下均为假

  • 可满足式：至少存在一种解释使其为真

代换实例

  • 把命题公式 \(A_0(p_1,\ldots,p_n)\) 中的 \(p_i\) 处处换成谓词公式 \(A_i\)，得到 \(A\)。

  • 重言式的代换实例是永真式；矛盾式的代换实例是矛盾式。

注意

\(\forall x\,(F(x)\to G(x))\) 不是 \(p\to q\) 的代换实例（量词在最外且作用于整个蕴涵，结构不同）。

与命题逻辑的差异：一阶逻辑中不存在通用算法判定任意公式是否可满足；但对许多具体形式仍可分析

一阶逻辑等值式与变换

等值：\(A\leftrightarrow B\) 为永真式时称 \(A\) 与 \(B\) 等值。

量词否定

设 \(A(x)\) 含 \(x\) 自由出现，则（记法因教材略有写法差异，意义一致）：

  • \(\neg \forall x\,A(x)\ \Leftrightarrow\ \exists x\,\neg A(x)\)

  • \(\neg \exists x\,A(x)\ \Leftrightarrow\ \forall x\,\neg A(x)\)

Abstract

否定跨过量词，\(\forall\) 与 \(\exists\) 互换。

量词辖域收缩与扩张

在 \(B\) 不含 \(x\) 的自由出现时，可把与 \(x\) 无关的部分移入或移出量词辖域（全称对 \(\land\)、存在对 \(\lor\) 等有一套标准等值式，演算时查表即可）。

三条常用原则

  1. 换名：把某量词辖域里约束出现的指导变元及其辖域内该变元的出现，改成公式中未出现过的新变元符号，避免同一变元既约束又自由。

  2. 代替：把某自由变项的全部出现换成公式中未出现过的新变元。

  3. 置换规则：若 \(A\leftrightarrow B\)，则在更大公式中用 \(B\) 置换 \(A\) 的某些出现，所得公式与原公式等值（一阶与命题逻辑形式相同，只是 \(A,B\) 现在是一阶公式）

Warning

\(\forall\) 对 \(\lor\)、\(\exists\) 对 \(\land\) 没有像命题逻辑那样随意的分配律；改变多个量词的顺序一般会改变含义（除非在特定条件下可交换）

前束范式

前束范式是指形如

\[ Q_1 x_1\, Q_2 x_2\, \cdots\, Q_k x_k\, B \]

的公式，其中每个 \(Q_i\) 是 \(\forall\) 或 \(\exists\)，\(B\) 中不再含量词。

求法思路：

  1. 用量词否定把 \(\neg\) 深入到原子或谓词前。

  2. 用辖域扩张等把量词逐步移到最前

  3. 必要时用换名避免冲突

存在性

任何公式都有与之等值的前束范式，但一般不唯一。

符号化时的实操提醒

  1. 先写清个体域：有限定域按限定域翻译；未说明时常用全总个体域 + 特性谓词。

  2. 先拆谓词：性质（一元）与关系（多元）分开。

  3. 多个量词顺序：一般不可随意调换；\(\forall x\exists y\) 与 \(\exists y\forall x\) 语义不同。

  4. 一题多解：否定词位置不同可能得到不同但等值的符号化（如「没有不犯错误的人」）。