2.2 谓词合式公式

一个谓词 P 和 n 个个体变元，如 x ₁ ， x ₂ ， x ₃ ，…， x _n ，表示成 P （ x ₁ ， x ₂ ， x ₃ ，…， x _n ）的形式，称为 n 元原子谓词公式 ，简称 n 元谓词公式 。例如 A （ x ）是一元谓词公式， B （ x ， y ）是二元谓词公式， P （ x ， y ， z ）是三元谓词公式。特别地，如果谓词公式中没有个体变元，即 n =0时称为0元谓词公式。0元谓词公式就是原子命题。下面给出谓词合式公式的定义。

定义2.2.1 谓词演算的合式公式，简称 谓词演算公式 ，定义如下。

1）每一个原子谓词公式都是谓词演算公式。

2）如果 A 是谓词公式，则 是谓词公式。

3）如果 A 和 B 都是谓词公式，则 A ∧ B 、 A ∨ B 、 A → B 、 A ←→ B 都是谓词公式。

4）如果 A 是谓词公式， x 是其中的任一变元，则∀ xA 和∃ xA 都是谓词公式。

5）只有有限次地应用上面的步骤得到的符号串才是谓词公式。

定义2.2.2 谓词公式∀ xA 和∃ xA 中出现在量词∀和∃后面的变元 x 称为量词的 指导变元 。每个量词后面的最小的谓词子公式，称为该量词的 辖域 。在量词的辖域中， x 的所有出现都称为 约束出现 。约束出现的变元称为 约束变元 。除约束变元以外的其他变元的出现称为 自由出现 。自由出现的变元称为 自由变元 。

例2.2.1 指出下列谓词公式中的量词及其辖域，指出各自由变元和约束变元。

1）∀ x （ P （ x ）∨ Q （ x ））∧ R

2）∀ x （ P （ x ）∧ Q （ x ））∧∃ xS （ x ）→ T （ x ）

3）∀ x （ P （ x ）→∃ y （ B （ x ， y ）∧ Q （ y ））∨ T （ y ））

4） P （ x ）→（∀ y ∃ x （ P （ x ）∧ B （ x ， y ））→ P （ x ））

5）∀ x ∃ y （ P （ x ， y ）∧ Q （ y ， z ））∧∀ yR （ x ， y ）

解 1）全称量词∀ x ，辖域为 P （ x ）∨ Q （ x ），其中 x 为约束变元， R 为命题常元。

2）全称量词∀ x ，辖域为 P （ x ）∧ Q （ x ），其中 x 为约束变元。存在量词∃ x ，其辖域为 S （ x ），其中 x 为约束变元。 T （ x ）中 x 为自由变元。

3）全称量词∀ x ，辖域为 P （ x ）→∃ y （ B （ x ， y ）∧ Q （ y ））∨ T （ y ），其中 x 为约束变元， T （ y ）中 y 为自由变元。存在量词∃ y ，辖域为 B （ x ， y ）∧ Q （ y ），其中 y 为约束变元。

4）全称量词∀ y ，辖域为∃ x （ P （ x ）∧ B （ x ， y ）），其中 y 为约束变元。存在量词∃ x ，辖域为 P （ x ）∧ B （ x ， y ），其中 x 为约束变元。不在量词辖域中的 P （ x ）中的 x 为自由变元。

5）∀ x 的辖域是∃ y （ P （ x ， y ）∧ Q （ y ， z ）），∃ y 的辖域是 P （ x ， y ）∧ Q （ y ， z ），∀ y 的辖域是 R （ x ， y ）。在∀ x ∃ y （ P （ x ， y ）∧ Q （ y ， z ））中， x 、 y 为约束变元， z 为自由变元。在∀ yR （ x ， y ）中， y 为约束变元， x 为自由变元。

◀

上例5）中的 x 既是约束变元，也是自由变元，这样会引起概念上的混淆。一个公式中的变元所使用的符号是无关紧要的，例如∀ xP （ x ）和∀ yP （ y ）的真值相同，∃ xP （ x ）和∃ yP （ y ）的真值相同，所以可以对公式中的约束变元或自由变元更改名称符号，使得一个变元在一个公式中只呈现一种形式，即呈自由出现或呈约束出现，以避免混淆。

对谓词公式中约束出现的变元更改符号名称，称为 约束变元换名 。

约束变元换名规则 ：将量词中的指导变元以及该量词辖域中该变元的所有出现更改为辖域中没有出现的变元名称，公式的其余部分不变。

对谓词公式中自由出现的变元更改符号名称，称为 自由变元代入 。

自由变元代入规则 ：对某自由出现的个体变元的每一处都代入与原公式中所有变元的名称不相同的变元。

例2.2.2 对下列谓词公式中的变元，使用变元换名规则进行正确换名。

1）∀ xP （ x ， y ）→∃ yQ （ y ）

2）∀ x ∃ y （ P （ x ， y ）∧ Q （ y ， z ））∧∀ xR （ x ， y ， z ）

解 1）利用约束变元换名规则，将∃ yQ （ y ）中的约束变元 y 换成 z ，得公式为

∀ xP （ x ， y ）→ ∃ zQ （ z ）

或利用自由变元代入规则，将∀ xP （ x ， y ）中的 y 用 z 代入，得公式为

∀ xP （ x ， z ）→ ∃ yQ （ y ）

2）利用约束变元换名规则，将∀ xR （ x ， y ， z ）中的约束变元 x 换成 s ，利用自由变元代入规则，将∀ xR （ x ， y ， z ）中自由出现的 y 用 t 代入，得公式为

∀ x ∃ y （ P （ x ， y ）∧ Q （ y ， z ））∧ ∀ sR （ s ， t ， z ）

◀

定义2.2.3 任一谓词公式 A ，若 A 中没有自由出现的个体变元，称 A 是 封闭的谓词公式 ，简称 闭式 。

例2.2.3 判断下列谓词公式是否是闭式。

1）∀ x （ P （ x ）∧ Q （ x ）∧∃ y （ S （ x ， y ）∧ F （ x ）））

2）∀ x ∃ y （ P （ x ， y ）∧ Q （ x ， y ））∧∀ xS （ x ， z ）

解 1）是闭式，因为无自由出现的变元；

2）不是闭式，有自由出现的变元 z 。

◀ t3XfYVZd64pay1Y1AjiUJTJ3aZ8wtTCxeKYaVCjj2u+2Hphi+Hom1z/xHzc/alX9