离散数学-Week3

一阶逻辑基本概念

解释与赋值

定义3.7 设一阶语言L 的个体常项集{aᵢ | i ≥ 1}，函数符号集{fᵢ | i ≥ 1}，谓词符号集{Fᵢ | i ≥ 1}，L的解释I由下面4部分组成:

1. 非空个体域Dᵢ
2. 对每一个个体常项aᵢ，āᵢ ∈ Dᵢ，称作aᵢ在I中的解释
3. 对每一个函数符号fᵢ，设其为m元的，f̄ᵢ是Dᵢ上的m元函数，称作fi在I中的解释
4. 对每一个谓词符号Fi，设其为n元的，F̄ᵢ是一个n元谓词，称作Fi在I中的解释对公式中个体域及个体常项符号、函数符号、谓词符号的指定称作解释。
5. 对每一个自由出现的个体变项x指定个体域中的一个值σ(x)，称作赋值σ。

任何公式在给定的解释和赋值下都是命题.

说明

1. 解释的作用：对公式中的个体域、个体常项符号、函数符号和谓词符号进行具体指定
2. 赋值的作用：为公式中自由出现的变元指定具体的个体值
3. 关键结论：任何公式在给定的解释 I 和赋值 σ 下都成为一个确定的命题（具有确定的真值）

实际应用

通过解释和赋值，抽象的符号公式被赋予具体的含义：

• 个体常项被解释为具体的对象
• 函数符号被解释为具体的运算
• 谓词符号被解释为具体的性质或关系
• 自由变元被赋值为具体的个体

闭式的性质

定理3.1 闭式在任何解释下都变成命题。

• 闭式只需给定解释。
• 只给定解释，非闭式可能成为命题，但通常不能成为命题。
• 只有给定解释和赋值，非闭式才能一定成为命题。

一阶逻辑公式的分类

• 永真式(逻辑有效式): 无成假解释和赋值
• 矛盾式(永假式): 无成真解释和赋值
• 可满足式: 至少有一个成真解释和赋值

在一阶逻辑中，公式的可满足性(永真性，永假性)是不可判定的，即不存在算法能在有限步内判断任给的公式是否是可满足式(永真式，矛盾式)

代换实例

定义3.9 设 A₀ 是含有命题变项 p₁, p₂, …, pₙ 的命题公式，A₁, A₂, …, Aₙ 是 n 个谓词公式。
用 Aᵢ 处处代替 A₀ 中的 pᵢ (1 ≤ i ≤ n)，所得公式 A 称为 A₀ 的代换实例。

示例

• F(x) → G(x)
• ∀xF(x) → ∃yG(y)

定理3.2 重言式的代换实例都是永真式，矛盾式的代换实例都是矛盾式

一阶逻辑等值演算

等值式

定义3.10 若 A ↔ B 是永真式，则称 A 与 B 是等值的，记作 A ⇔ B，并称 A ⇔ B 为等值式。

1. 命题逻辑基本等值式的代换实例 命题逻辑中的基本等值式在谓词逻辑中的代换实例仍然是等值式。
示例：

• ∀xF(x) → ∃yG(y) ⇔ ¬∀xF(x) ∨ ∃yG(y)
• ¬(∀xF(x) ∨ ∃yG(y)) ⇔ ¬∀xF(x) ∧ ¬∃yG(y)

2. 消去量词等值式 设个体域 D = {a₁, a₂, …, aₙ}：

• ∀xA(x) ⇔ A(a₁) ∧ A(a₂) ∧ … ∧ A(aₙ)
• ∃xA(x) ⇔ A(a₁) ∨ A(a₂) ∨ … ∨ A(aₙ)

3. 量词辖域收缩与扩张等值式 设 A(x) 是含 x 自由出现的公式，B 中不含 x 的自由出现：

关于全称量词：

• ∀x(A(x) ∨ B) ⇔ ∀xA(x) ∨ B
• ∀x(A(x) ∧ B) ⇔ ∀xA(x) ∧ B
• ∀x(A(x) → B) ⇔ ∃xA(x) → B
• ∀x(B → A(x)) ⇔ B → ∀xA(x)

关于存在量词：

• ∃x(A(x) ∨ B) ⇔ ∃xA(x) ∨ B
• ∃x(A(x) ∧ B) ⇔ ∃xA(x) ∧ B
• ∃x(A(x) → B) ⇔ ∀xA(x) → B
• ∃x(B → A(x)) ⇔ B → ∃xA(x)

4. 量词否定等值式
设 A(x) 是含 x 自由出现的公式：

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

5. 量词分配等值式

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

注意： ∀ 对 ∨，∃ 对 ∧ 无分配律。即：

• ∀x(A(x) ∨ B(x)) ⇔ ∀xA(x) ∨ ∀xB(x) 不成立
• ∃x(A(x) ∧ B(x)) ⇔ ∃xA(x) ∧ ∃xB(x) 不成立

置换规则、换名规则

1. 置换规则

设 Φ(A) 是含公式 A 的公式，Φ(B) 是用公式 B 取代 Φ(A) 中的所有 A 得到的公式，则：
Φ(A) ⇔ Φ(B)

2. 换名规则

将公式 A 中某量词的指导变元及其在辖域内的所有约束出现改成该量词辖域内未曾出现的某个个体变项，其余部分不变，记所得公式为 A′，则：
A′ ⇔ A

应用示例

1.消去公式中既约束出现、又自由出现的个体变项

(1) ∀xF(x,y,z) → ∃yG(x,y,z)
⇔ ∀uF(u,y,z) → ∃yG(x,y,z) （换名规则）
⇔ ∀uF(u,y,z) → ∃vG(x,v,z) （换名规则）

(2) ∀x(F(x,y) → ∃yG(x,y,z))
⇔ ∀x(F(x,y) → ∃tG(x,t,z)) （换名规则）

2.消去量词（设个体域 D = {a,b,c}）

(1) ∀x(F(x) → G(x))
⇔ (F(a) → G(a)) ∧ (F(b) → G(b)) ∧ (F(c) → G(c))

(2) ∀x(F(x) ∨ ∃yG(y))
⇔ ∀xF(x) ∨ ∃yG(y) （量词辖域收缩）
⇔ (F(a) ∧ F(b) ∧ F(c)) ∨ (G(a) ∨ G(b) ∨ G(c))

(3) ∃x∀yF(x,y)
⇔ ∃x(F(x,a) ∧ F(x,b) ∧ F(x,c))
⇔ (F(a,a) ∧ F(a,b) ∧ F(a,c)) ∨ (F(b,a) ∧ F(b,b) ∧ F(b,c)) ∨ (F(c,a) ∧ F(c,b) ∧ F(c,c))

3.求公式在解释 I 下的真值

设解释 I：

• 个体域 D = {2,3}
• F(x): x是奇数
• G(x,y): x=2 ∨ y=2
• L(x,y): x=y

(1) ∃x(F(f(x)) ∧ G(x, f(x)))
⇔ (F(f(2)) ∧ G(2, f(2))) ∨ (F(f(3)) ∧ G(3, f(3)))
⇔ (1 ∧ 1) ∨ (0 ∧ 1) ⇔ 1

(2) ∃x∀yL(x,y)
⇔ ∀yL(2,y) ∨ ∀yL(3,y)
⇔ (L(2,2) ∧ L(2,3)) ∨ (L(3,2) ∧ L(3,3))
⇔ (1 ∧ 0) ∨ (0 ∧ 1) ⇔ 0

4.证明等值式

证明：¬∃x(M(x) ∧ F(x)) ⇔ ∀x(M(x) → ¬F(x))

证明： 左边 ⇔ ¬∃x(M(x) ∧ F(x))
⇔ ∀x¬(M(x) ∧ F(x)) （量词否定等值式）
⇔ ∀x(¬M(x) ∨ ¬F(x)) （德摩根律）
⇔ ∀x(M(x) → ¬F(x)) （蕴涵等值式）

前束范式

定义3.11 设 A 为一个一阶逻辑公式，若 A 具有如下形式：
Q₁x₁Q₂x₂…QₖxₖB
则称 A 为前束范式，其中：

• Qᵢ 为 ∀ 或 ∃ (1 ≤ i ≤ k)
• B 为不含量词的公式

示例

是前束范式：

• ∀x∃y(F(x) → (G(y) ∧ H(x,y)))
• ∀x¬(F(x) ∧ G(x))

不是前束范式：

• ∀x(F(x) → ∃y(G(y) ∧ H(x,y)))
• ¬∃x(F(x) ∧ G(x))

定理3.3（前束范式存在定理）
一阶逻辑中的任何公式都存在与之等值的前束范式。

例：求公式的前束范式
∀xF(x) ∧ ¬∃xG(x)
解法1：
⇔ ∀xF(x) ∧ ∀x¬G(x) （量词否定等值式）
⇔ ∀x(F(x) ∧ ¬G(x)) （量词分配等值式）

解法2：
⇔ ∀xF(x) ∧ ¬∃yG(y) （换名规则）
⇔ ∀xF(x) ∧ ∀y¬G(y) （量词否定等值式）
⇔ ∀x(F(x) ∧ ∀y¬G(y)) （量词辖域扩张）
⇔ ∀x∀y(F(x) ∧ ¬G(y)) （量词辖域扩张）