date: 2025-06-14T15:31:00 aliases:

• 离散数学第五章

谓词逻辑等值演算与推理

一、核心概念

• 谓词逻辑：包含个体变量、谓词和量词的逻辑系统
• 等值演算：通过逻辑等值式进行公式变换
• 前束范式：所有量词都移到公式最前面的标准形式

二、等值式与置换规则

1. 量词否定等值式

$¬∀xA(x) ⇔ ∃x¬A(x)$ $¬∃xA(x) ⇔ ∀x¬A(x)$

2. 量词分配等值式

$∀x(A(x)∧B(x)) ⇔ ∀xA(x)∧∀xB(x)$ $∃x(A(x)∨B(x)) ⇔ ∃xA(x)∨∃xB(x)$

三、置换规则

1. 等值代换原则

定义：在谓词公式中，若子公式 $A$ 与 $B$ 逻辑等值（$A \Leftrightarrow B$），则可将 $A$ 替换为 $B$ 而不改变原公式的真值。 规则说明：

• 可替换部分：可以是整个公式或子公式
• 替换范围：必须替换所有相同子公式（或选择性替换）
• 保持约束关系：替换时需确保不改变原公式中变元的约束状态 示例： 原式：$\forall x (P(x)) \to \color{red}{Q(x) \land R(x)}$
  已知等值式：$Q(x) \land R(x) \Leftrightarrow \neg(\neg Q(x) \lor \neg R(x))$
  替换后：$\forall x (P(x)) \to \color{yellow}{\neg(\neg Q(x) \lor \neg R(x))})$

2. 约束变项换名规则

定义：可以统一修改量词及其辖域内受约束变项的名称，但不改变公式逻辑含义。 操作规则：

1. 唯一性：新变项名必须在公式中未被使用（避免与自由变项冲突）
2. 完全替换：需替换量词和所有对应约束变项的出现
3. 保持层次：嵌套量词需逐层处理，内层量词优先换名 您对约束变项换名规则的疑问非常好理解！让我们用更直观的方式解析这个关键概念：

正确换名 vs 错误换名对比

▶ 正确换名示例（保持逻辑不变）

原式：
$\color{red}{\forall x} \Big( P(\color{red}{x}) \to \exists y Q(\color{red}{x}, y) \Big)$
↓ 将外层∀x统一换为∀z
换名后：
$\color{blue}{\forall z} \Big( P(\color{blue}{z}) \to \exists y Q(\color{blue}{z}, y) \Big)$
✅ 逻辑等价：所有x→z的替换是完整的，且y保持独立

▶ 错误换名示例（逻辑被破坏）

错误操作：
$\color{red}{\forall x} \Big( P(\color{red}{x}) \to \color{green}{\exists x} Q(\color{red}{x}, \color{green}{x}) \Big)$
❌ 问题本质：

1. 量词冲突：内层$\exists x$的x覆盖了外层$\forall x$的x，导致：
   • 原式中$Q(x,y)$的y是独立变元
   • 错误替换后$Q(x,x)$强制让两个参数相同
2. 约束关系混乱：内层$x$原本是自由变元，被错误地重新约束

关键原则总结

1. 无覆盖原则：内层量词必须使用新变元名（如y,z），不能重复使用外层量词变元名（x）
2. 完全替换原则：换名时要替换所有相同约束变元的出现
3. 自由变元保护：换名时不能影响公式中的自由变元

正确修正方法

若需要保留$x$，应先对内层量词换名：
原式：$\forall x (P(x) \to \exists y Q(x,y))$
↓ 先换内层变元
= $\forall x (P(x) \to \exists z Q(x,z))$
↓ 再换外层变元（如需）
= $\forall w (P(w) \to \exists z Q(w,z))$

3. 联合应用场景

当需要将公式化为前束范式时，通常需要：

1. 先用约束变项换名规则消除量词冲突
2. 再用等值代换进行公式变形 典型流程：

graph TD
A[原始公式] --> B{检查变元冲突}
B -->|有冲突| C[约束变项换名]
B -->|无冲突| D[等值代换]
C --> D
D --> E[前束范式]

三、前束范式

转化步骤：

1. 消去→和↔
2. 将¬内移（使用量词否定等值式）
3. 变项换名
4. 量词前移

示例：

原式：$∀xP(x)→∃yQ(y)$ 转化过程：

1. $¬∀xP(x)∨∃yQ(y)$
2. $∃x¬P(x)∨∃yQ(y)$
3. $∃x∃y(¬P(x)∨Q(y))$

四、推理理论

一、全称实例规则 (Universal Instantiation, UI)

规则形式：

核心思想：从"所有x满足A"可推出"某个具体c满足A" 示例：

1. 前提：$\forall x (Dog(x) \to Mammal(x))$
2. 应用UI：取$c=Fido$，得到$Dog(Fido) \to Mammal(Fido)$

限制条件：

• 必须替换为论域中确实存在的个体
• 在自然演绎系统中通常无需额外声明

二、存在实例规则 (Existential Instantiation, EI)

规则形式：

核心思想：从"存在x满足A"可推出"设某个新个体c满足A"

示例：

1. 前提：$\exists x (Cat(x) \land Black(x))$
2. 应用EI：引入新常项$a$，得到$Cat(a) \land Black(a)$

关键限制：

• 必须使用全新的常项（称为"临时常元"）
• 该常项不能出现在后续结论中（仅作为临时假设）

三、全称概括规则 (Universal Generalization, UG)

规则形式：

核心思想：若对任意个体y都能证明A(y)，则可推广到所有x

使用条件：

1. y不能是前提中出现的特定个体
2. y不能是通过EI引入的常项
3. 必须确保y的任意性（通常需声明"设y为任意个体"）

示例：

1. 设y为任意个体              [临时假设]
2. Dog(y) → Mammal(y)        [已知]
3. ∀x (Dog(x) → Mammal(x))   [UG于1-2]

四、存在概括规则 (Existential Generalization, EG)

规则形式：

核心思想：从"某个具体个体满足A"可推出"存在x满足A" 示例：

1. 已知：$Pythagorean(3,4,5)$
2. 应用EG：$\exists x \exists y \exists z Pythagorean(x,y,z)$ 特殊情形：

• 可多重量词同时引入：从$A(a,b)$得到$\exists x \exists y A(x,y)$
• 可部分替换：从$P(a,y)$得到$\exists x P(x,y)$（保留自由变元y）

规则对比表

复合应用示例

证明：$\forall x (P(x) \to Q(x)), \exists x P(x) \vdash \exists x Q(x)$

1. ∀x (P(x) → Q(x))          [前提]
2. ∃x P(x)                   [前提]
3. P(a)                      [EI于2，a为新常项]
4. P(a) → Q(a)               [UI于1]
5. Q(a)                      [MP于3,4]
6. ∃x Q(x)                   [EG于5]

2. 常用推理方法

graph TD
A[前提] --> B[消去量词]
B --> C[命题逻辑推理]
C --> D[引入量词]

五、典型例题

例1：证明

$∀x(P(x)→Q(x))∧∀x(Q(x)→R(x)) ⇒ ∀x(P(x)→R(x))$ 证明步骤：

1. 使用UI规则实例化x
2. 假言三段论
3. 使用UG规则推广