谓词逻辑

∃ ∀

基本概念

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

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

注意：客体变元本身不是客体

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

例如：

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

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

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

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

量 词

1. 存在量词：记作∃，表示“有些”、“一些”、 “某些”、“至少一个”等。

2. 全称量词：记作∀，表示“每个”、“任何一 个”、“ 一切”、“所有的”、“凡是”、“任 意的”等

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

谓词公式及命题符号化

客体函数:

如果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Ａ也是合式公式。

• 只有有限次应用上述四条规则得到的才是合式公式

量词的作用域：量词的作用范围，也叫量词的辖域。

• 如果量词后边只是一个原子谓词公式时，其辖域 为此原子谓词公式。

• 如果量词后边是括号，其辖域为括号所表示的区域。

• 紧挨着出现的多个量词，它们的辖域相同。

自由变元与约束变元：

如果客体变元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)

注意：下面的式子不成立

∀x∃yA(x,y)⇒∃y∀xA(x,y)

前束范式

定义：

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

• 所有量词前面都没有联接词；

• 所有量词前面都没有联接词；

• 所有量词的辖域都延伸到公式的末尾。

前束范式的写法：

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

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)))$ （扩大量词辖域）