# 谓词逻辑

## 基本概念

客体定义：能够独立存在的事物，称为客体，也称为个 体。它可以是具体的，也可以是抽象的。通常用小 写英文字母a、b、c、...表示。 例如，小张、小李、8、a、沈阳、社会主义等等都 是客体。

客体变元定义：用小写英文字母x、y、z...表示任何客体，则 称这些字母为客体变元。

<mark style="color:blue;">**注意：客体变元本身不是客体**</mark>

谓词定义：谓词用来描述个体的性质或个体间的关系， 用大写字母后加括号表示，括号内为客体变元。 如果括号内有n个客体变元，称该谓词为n元谓词。

例如：

S(x):表示x是大学生。 一元谓词 G(x,y)：表示 x>y。 二元谓词 B(x,y,z)：表示x在y与z之间。三元谓词

命题函数：一般地用 P(x1,x2,…,xn)表示n元谓词。 n元谓词也称 简单命题函数，将若干个简单命题函数用逻辑联结 词联结起来，构成的表达式，称之为复合命题函数。 简单命题函数与复合命题函数统称为命题函数。

论域(个体域)：在命题函数中命题变元的取值范围， 称之为论域，也称之为个体域。由所有客体构成的论域，称之为全总 个体域。它是个“最大”的论域。

**约定:对于一个命题函数，如果没有给定论域， 则假定该论域是全总个体域**

#### 量 词

1. 存在量词：记作∃，表示“有些”、“一些”、 “某些”、“至少一个”等。&#x20;
2. 全称量词：记作∀，表示“每个”、“任何一 个”、“ 一切”、“所有的”、“凡是”、“任 意的”等

量词后边要有一个客体变元，指明 对哪个体变元量化，称此**客体变元**是**量词后的指导变元**。<br>

## 谓词公式及命题符号化

客体函数:

如果x是奇数，则2x是偶数。 其中客体x与客体2x之间就有函数关系，可以设 客体函数 g(x)=2x， 谓词 O(x)：x是奇数， E(x)：x是偶数， 则此命题可以表示为： ∀x(O(x)→E(g(x)))

#### 客体函数和谓词的区别：

1. 客体函数是论域到论域的映射，如： g:N→N，如果指定的客体a∈N，则 g(a)∈N。
2. 谓词是从论域到{T,F}的映射，即谓词 E(x)可以看成映射E:N→{T,F}，如果指定 客体a∈N，则E(a)的真值∈{T,F}。

**n元谓词P(x1,x2,...,xn)又称为原子谓词公式。 例如 P、Q(x) 、 A(x,f(x))、B(x,y,a) 都是原子 谓词公式**

#### 谓词公式

* 原子谓词公式是合式公式。
* 如果A是合式公式，则¬A也是合式公式。
* 如果A、B是合式公式，则(A∧B)、(A∨B)、 (A→B)、(A↔B)都是合式公式。
* .如果A是合式公式，x是Ａ中的任何客体变元，则∃xＡ和∀xＡ也是合式公式。
* 只有有限次应用上述四条规则得到的才是合式公式

**量词的作用域：**&#x91CF;词的作用范围，也叫量词的辖域。

* 如果量词后边只是一个原子谓词公式时，其辖域 为此原子谓词公式。
* 如果量词后边是括号，其辖域为括号所表示的区域。
* 紧挨着出现的多个量词，它们的辖域相同。

#### 自由变元与约束变元：

如果客体变元x在∃x或者∀x的辖域内， 则称x在此辖域内约束出现，并称x在此辖域 内是约束变元。(如Ｆ(x,y) 的x和P(y)中的y ) 否则x是自由出现，并称x是自由变元。

* 对约束变元用什么符号表示无关紧要。
* 一个谓词公式如果无自由变元，它就表示一个命题。
* 一个n元谓词P(x1,x2,…,xn)，若在前边添加k个量词，使其中的 k个客体变元变成约 束变元，则此n元谓词就变成了n-k元谓词。

#### 约束变元的改名规则：

* 约束变元改名的同时量词后的指导变元以及该量词的辖域 内此客体变元出现的各处同时换名
* 改名后用的客体变元名称，不能与该量词的辖域内的其它变元名称相同。

#### 命题符号化

* 命题的符号表达式与论域有关系
* 当论域扩大时，需要添加用来表示 客体特性的谓词，称此谓词为特性谓词
* 命题的符号表达式中所有客体变元必须都是约束变元，才能表示命题。有时给定命题中有些量词没有明确给出，要仔 细分析并写出这些隐含量词

#### 特性谓词的添加方法

* 如果前面是全称量词，特性谓词后面是蕴含连结词“→”
* 如果前面是存在量词，特性谓词后面是合取连结词“∧”

## 谓词演算的等价式与蕴涵式

#### 指派（对谓词公式赋值）：

若将给定的谓词公式中的命题变元， 用确定的命题代替，对公式中的客体变元 用论域中的客体代替，这个过程就称之为 对谓词公式作指派，或者称之为对谓词公式赋值

#### 永真式：

给定谓词公式A，E是其论域，如果 不论对公式A作任何赋值，都使得A的真值 为真，则称公式A在论域E上是永真式。如 果不论对什么论域E，都使得公式A为永真 式，则称A为永真式

#### 等价：

给定谓词公式A、B，E是它们的论 域，如果不论对公式A、B作任何赋值， 都使得A与B的真值相同(或者说A«B是永 真式)，则称公式A与B在论域E上是等价的。 如果不论对什么论域E，都使得公式A与B 等价，则称A与B等价，记作A↔B。

#### 永真蕴含 ：

给定谓词公式A、B，E是它们的论 域，如果不论对公式A、B作任何赋值，都 使得A→B为永真式，则称在论域E上公式 A永真蕴含B。如果不论对什么论域E，都 使得公式A→B为永真式，则称A永真蕴含 B，记作A⇒B。

#### 在命题演算的永真式中，将其中的同一个命题变 元，用同一个谓词公式代替，所得到的公式也是 永真式。

#### 带量词的公式在论域内的展开式：

1. ∀x A(x) ⇔ A(a₁) ∧ A(a₂) ∧ ⋯ ∧ A(an)
2. ∃x B(x) ⇔ B(a₁) ∨ B(a₂) ∨ ⋯ ∨ B(an)

#### 量词否定公式：

1. ¬(∀x A(x) ⇔ ∃x ¬A(x))
2. ¬(∃x A(x) ⇔ ∀x ¬A(x))

#### 量词辖域的扩充公式：

如果Ｂ是个不含客体变元x的谓词公式，且不在∀x和∃x的辖域内，可以将Ｂ放入∀x和∃x的辖域内。即得如下公式：

1. ∀x (A(x) ∨ B) ⇔ ∀x (A(x) ∨ B)
2. ∀x (A(x) ∧ B) ⇔ ∀x (A(x) ∧ B)
3. ∃x (A(x) ∨ B) ⇔ ∃x (A(x) ∨ B)
4. ∃x (A(x) ∧ B) ⇔ ∃x (A(x) ∧ B)
5. B → ∀x (A(x)) ⇔ ∀x (B → A(x))
6. B → ∃x (A(x)) ⇔ ∃x (B → A(x))
7. ∀x (A(x) → B) ⇔ ∃x (A(x) → B)
8. ∃x (A(x) → B) ⇔ ∀x (A(x) → B)

#### 量词分配公式：

1. ∃x (A(x) ∨ B(x)) ⇔ ∃x A(x) ∨ ∃x B(x)
2. ∀x (A(x) ∧ B(x)) ⇔ ∀x A(x) ∧ ∀x B(x)
3. ∃x (A(x) ∧ B(x)) ⇒ ∃x A(x) ∧ ∃x B(x)
4. ∀x A(x) ∨ ∀x B(x) ⇒ ∀x (A(x) ∨ B(x))

#### 其他公式：

1. x(A(x)→B(x))⇔∀x(A(x)→∀xB(x)
2. ∃xA(x)→∀xB(x)⇒∀x(A(x)→B(x))
3. ∀x∀yA(x,y)⇔∀y∀xA(x,y)
4. ∀x∀yA(x,y)⇒∃y∀xA(x,y)
5. ∃y∀xA(x,y)⇒∀x∃yA(x,y)
6. ∀x∃yA(x,y)⇒∀x∃yA(x,y)
7. ∀y∀xA(x,y)⇒∃x∀yA(x,y)
8. ∃x∀yA(x,y)⇒∀y∃xA(x,y)
9. ∀y∃xA(x,y)⇒∀x∃yA(x,y)
10. ∃x∃yA(x,y)⇔∃y∃xA(x,y)

<mark style="color:red;">注意：下面的式子不成立</mark>

<mark style="color:red;">∀x∃yA(x,y)⇒∃y∀xA(x,y)</mark>

## 前束范式

#### 定义：

如果一个谓词公式符合下面条件,它就是前束范式：

* 所有量词前面都没有联接词；
* 所有量词前面都没有联接词；
* 所有量词的辖域都延伸到公式的末尾。

#### 前束范式的写法：

给定一个带有量词的谓词公式，

1. 消去公式中的联接词→和↔(为了便于量词辖域的扩充)；
2. 如果量词前有“ ¬ ”，则用量词否定公式将“ ¬ ” 后移。再用摩根定律或求公式的否定公式，将“¬ ” 后移到原子谓词公式之前。
3. 用约束变元的改名规则或自由变元的代入规则对变元换名(为量词辖域扩充作准备)。
4. 用量词辖域扩充公式提取量词，使之成为前束范式形式

例：

$$∀x(P(x)∧R(x))→(¬∃xP(x)∧Q(x))$$

$$⇔¬∀x(P(x)∧R(x))∨(¬∃xP(x)∧Q(x))$$ （去掉蕴含符号）

$$⇔∃x¬(P(x)∧R(x))∨∀x(¬P(x)∧Q(x))$$ （量词转换）

$$⇔∃x(¬P(x)∨¬R(x))∨∀y(¬P(y)∧Q(z))$$ （后移 $$¬¬$$)

$$⇔∃x(¬P(x)∨¬R(x))∨∀y(¬P(y)∧Q(z))$$ （换变元）

$$⇔∃x(¬P(x)∨¬R(x))∨∀y(¬P(y)∧Q(z))$$ （扩大量词辖域）

$$⇔∀x∀y((¬P(x)∨¬R(x))∨(¬P(y)∧Q(z)))$$ （扩大量词辖域）

####

####