02_Predicate Logic

一、 谓词逻辑基础

• 命题逻辑的局限性：命题逻辑无法充分表达对象的通用规则或属性。

• 变量与谓词：谓词逻辑将陈述分为主语（变量，如 \(x, y\)）和其具备的属性（谓词，如 \(P, Q\)）。

• 命题函数 \(P(x)\)：它本身不是命题，只有当变量 \(x\) 被赋予特定值时，才成为有真假的命题。命题函数可以包含多个变量，如 \(n\) 元函数 \(P(x_1, x_2, \dots, x_n)\)。

• 论域 (Domain/Universe of Discourse, \(U\))：变量允许取值的确切范围。

---

二、 量词 (Quantifiers)

量词用于表达谓词在给定论域内的成立范围。量词的优先级高于所有标准逻辑运算符（\(\wedge, \vee, \rightarrow, \leftrightarrow\)）。

• 全称量词 (\(\forall x P(x)\))：断言 \(P(x)\) 对论域内的所有 \(x\) 均为真。它等价于论域内所有元素的合取（AND）。只要存在一个反例使得 \(P(x)\) 为假，该语句即为假。

• 存在量词 (\(\exists x P(x)\))：断言论域内存在至少一个 \(x\) 使得 \(P(x)\) 为真。它等价于论域内所有元素的析取（OR）。仅当所有 \(x\) 都使 \(P(x)\) 为假时，该语句才为假。

• 唯一量词 (\(\exists! x P(x)\))：断言存在唯一的 \(x\) 使得 \(P(x)\) 为真。

---

三、 变量状态与作用域

• 约束变量 (Bound Variable)：附带量词（\(\forall\) 或 \(\exists\)）或被赋予具体数值的变量。

• 自由变量 (Free Variable)：未受量词约束且未被赋值的变量。包含自由变量的表达式仍是命题函数，而非命题。

• 作用域 (Scope)：量词作用的表达式部分。根据覆盖范围，可分为宽作用域（覆盖整个表达式）和窄作用域（仅覆盖特定子表达式）。

---

四、 嵌套量词 (Nested Quantifiers)

当一个量词位于另一个量词的作用域内时，即为嵌套量词。求值过程可类比为编程中的嵌套循环。

• 量词顺序：

  • 同类可换：相同类型的量词可以互换位置而不改变真值（例如 \(\forall x \forall y \equiv \forall y \forall x\)）。

  • 异类不可换：互换不同类型的量词通常会改变语句的逻辑含义（例如 \(\forall x \exists y \not\equiv \exists y \forall x\)）。

• 双变量真值条件：

  • \(\forall x \forall y P(x,y)\)：对所有 \(x, y\) 对均为真。

  • \(\forall x \exists y P(x,y)\)：对于每个 \(x\)，都存在一个对应的 \(y\) 满足条件。

  • \(\exists x \forall y P(x,y)\)：存在一个特定的 \(x\)，它对所有的 \(y\) 都满足条件。

  • \(\exists x \exists y P(x,y)\)：至少存在一对 \(x, y\) 满足条件。

---

五、 逻辑等价、否定与分配

• 谓词逻辑等价定义：无论使用何种论域，无论代入何种特定谓词，两个语句的真值始终相同 (\(S \equiv T\))。

• 量词的德·摩根定律：对量化语句取反时，量词翻转，否定符号内移。

  • \(\neg \exists x P(x) \equiv \forall x \neg P(x)\)。

  • \(\neg \forall x P(x) \equiv \exists x \neg P(x)\)。

• 嵌套量词的否定：连续应用德·摩根定律，将否定符号向内推进至谓词。

• 量词分配律：

  • 有效分配：全称量词 \(\forall\) 可以在合取 \(\wedge\) 上分配；存在量词 \(\exists\) 可以在析取 \(\vee\) 上分配。

  • 无效分配：\(\forall\) 不可以在 \(\vee\) 上分配；\(\exists\) 不可以在 \(\wedge\) 上分配；两者通常都不能在蕴含式 \(\rightarrow\) 上分配。

---

六、 断言分类与自然语言翻译

• 断言的真值分类：

  • 有效 (Valid)：对所有论域和所有代入的谓词均成立。

  • 可满足 (Satisfiable)：至少在一个论域内存在某种谓词代入使其成立。

  • 不可满足 (Unsatisfiable)：在所有解释和论域下均为假。

• 翻译技巧：

  • 使用广义论域时：全称量词 \(\forall\) 通常搭配蕴含 \(\rightarrow\) ；存在量词 \(\exists\) 通常搭配合取 \(\wedge\)。

  • 受限论域的转换：全称受限等价于条件句（\(\forall x < 0 \equiv \forall x (x < 0 \rightarrow \dots)\)）；存在受限等价于合取句（\(\exists y > 0 \equiv \exists y (y > 0 \wedge \dots)\)）。