离散数学上册：自由变元与约束变元

给定α为一个谓词公式，其中有一部分公式形式为（∀x）P（x）或（∃x）P（x）。这里∀、∃后面所跟的x叫作量词的指导变元或作用变元，P（x）叫作相应量词的作用域或辖域。在作用域中x的一切出现，称为x在α中的约束出现，x亦称为被相应量词中的指导变元所约束，也称x为约束亦元。在α中除去约束变元以外所出现的变元称作自由变元。自由变元是不受约束的变元，虽然它有时也在量词的作用域中出现，但它不受相应量词中指导变元的约束，故我们可把自由变元看作是公式中的参数。

例1 试考察下列公式：

(1)(∀x)P(x,y);

(2)(∀x)(P(x)→(∃y)R(x,y));

(3)(∀x)(P(x)→R(x))∨(∀x)(P(x)→Q(x));

(4)(∃x)P(x)∧Q(x)。

在公式（1）中，P（x，y）是量词（∀x）的辖域，x的出现是约束出现；而y的出现，则是自由出现。在公式（2）中，量词（∀x）的辖域是P（x）→（∃y）R（x，y）；同时量词（∃y）的辖域是R（x，y）；x和y的出现，都是约束出现。在公式（3）中，第一个量词（∀x）的辖域是P（x）→R（x），第二个量词（∀x）的辖域是P（x）→Q（x）；x的所有出现，都是约束出现。在公式（4）中，量词（∃x）的辖域是P（x），其中x的出现是约束出现；Q（x）中的变元x的出现，是个自由出现。由此能够看出，在同一个公式中，某个变元的出现，既可以是约束的又可以是自由的。

偶尔可能会遇见（∀x）P（y）类型的公式，其中变元y的出现，是个自由出现；而量词（∀x）的辖域中不包含变元x。在这种情况下，使用量词（∀x）是毫无意义的。还应提到，在一个谓词公式中，若出现了自由变元，则该公式必定是个命题函数；若每一个变元都是约束变元，而不是自由变元，则该公式必定是一个命题。

由前面的讨论可知，（∀x）P（x，y）等价于（∀z）P（z，y），也就是说，用什么样的字母表示客体变元并不重要。不过，在同一个公式中，不能用同一个字母表示两个不同的客体变元。

为了避免由于变元的约束与自由同时出现，引起概念上的混乱，故可对约束变元进行换名，使得一个变元在一个公式中只呈一种形式出现，即呈自由出现或呈约束出现。

对约束变元换名应遵循以下两个原则：

（1）对于约束变元可以换名，其更改的变元名称范围是量词中的指导变元，以及该量词作用域中所出现的该变元，在公式的其余部分不变。

（2）换名时一定要更改为作用域中没有出现的变元名称。

例2 对（∀x）（P（x）→R（x，y））∧Q（x，y）换名。

解 可换名为：（∀z）（P（z）→R（z，y））∧Q（x，y），但不能改名为：（∀y）（P（y）→R（y，y））∧Q（x，y）以及（∀z）（P（z）→R（x，y））∧Q（x，y）。因为后两种更改都将使公式中量词的约束范围有所变动。(www.xing528.com)

对于公式中的自由变元，也允许更改，这种更改叫作代入。自由变元的代入，亦需遵守一定的规则，这个规则叫作自由变元的代入规则，现说明如下：

（1）对于谓词公式中的自由变元，可以作代入，代入时需对公式中出现该自由变元的每一处进行。

（2）用以代入的变元与原公式中所有变元的名称不能相同。

例3 对（∃x）（P（y）∧R（x，y））代入。

解 对y施行代入，经代入后公式为

(∃x)(P(z)∧R(x,z))

但是（∃x）（P（x）∧R（x，x））与（∃x）（P（z）∧R（x，y））这两种代入都是与规则不符的。

需要指出，量词作用域中的约束变元，当论域的元素是有限时，客体变元的所有可能的取代是可枚举的。

设论域元素为a1，a2，…，an，则

(∀x)A(x)⇔A(a1)∧A(a2)∧…∧A(an)

(∃x)A(x)⇔A(a1)∨A(a2)∨…∨A(an)

量词对变元的约束，往往与量词的次序有关。

又，（∀y）（∃x）（x＜（y-2））表示任何y均有x，使得x＜y-2。（∃y）（∃x）（x＜（y-2））表示存在y有x，使得x＜y-2。

这些命题中的多个量词，我们约定从左到右的次序读出。需要注意的是量词次序不能颠倒，否则将与原命题意义不符。