[科普中国]-约束出现

基本介绍合式公式

首先约定： 称为谓词演算公式的原子公式，其中 是项(实体、变量符号、函数)。

定义1：谓词演算的合式公式（简称公式）是由原子命题、谓词填式或由它们利用联结词和量词构成的式子。

合式公式的形式定义如下：

(1) 原子命题P是合式公式；

(2) 谓词填式 是合式公式；

(3) 若A是公式，则 A是合式公式；

(4) 若A和B是合式公式，则(A∨B)，(A∧B)，(A→B)，(A B)为公式；

(5) 若A是合式公式，x是A中出现的任何个体变元，则 为合式公式；

(6) 只有有限次使用(1)、(2)、(3)、(4)、(5)所得到的式子才是合式公式。

约束出现与约束变元定义2 设α为任何一个谓词演算公式， 为公式α的子公式，此时紧跟在 之后的x称为量词的指导变元或作用变元，α（x）称为相应量词的作用域，在作用域中x的一切出现均称为约束出现，在α中除了约束出现外的一切出现均称为自由出现。2

定义3 若一个变元x在公式中有自由出现，则称此变元为自由变元；若有约束出现，则称为约束变元。

注意点自由出现的变元可以在量词的作用域中出现，但不受相应量词的约束，所以有时我们把它看作公式中的参数。特例：若公式中无自由变元，公式即为命题。

变元在谓词公式A中可同时有约束出现和自由出现两种情况，而只有当x的所有出现都是约束出现时，x才为A的约束变元。

当一个谓词公式中的所有变元均是约束出现而无自由出现，则此谓词公式是确定的，即此谓词公式就是命题，可以判别其真假，故呈约束出现的变元实际上已由不确定而转为确定。1

例题解析例1 指出合式公式 的作用域、约束出现和自由出现。

解： 的作用域为： ；

的作用域为： ；

公式中的 为约束出现，第一个y和z是自由出现， 中的y为约束出现。2

例2 指出下列公式中，各量词的辖域以及变元的自由出现和约束出现：

(1)

(2)

(3)

解：

(1) 量词 的辖域为： ，而量词 的辖域为 。变元的自由出现和约束出现分别为：公式中的 为约束出现，z是自由出现，第一个y是自由出现，后面两个y是约束出现。

(2) 量词 的辖域为： 。变元的自由出现和约束出现分别为：y是自由出现，前两个x是约束出现，最后一个x是自由出现。

(3) 量词 的辖域为： 量词 的辖域为 。变元的自由出现和约束出现分别为：公式中的 、 全为约束出现。1