下载掌阅APP，畅读海量书库
立即打开
一个谓词公式可以化成与其等价的规范形式，称为前束范式。
定义2.5.1 一个谓词公式 A ，若具有形式 Q 1 x 1 Q 2 x 2 … Q n x n M ，其中每个 Q i （1≤ i ≤ n ）为∀或∃， M 为不含量词的谓词公式，则称谓词公式 A 为 前束范式 。 Q 1 x 1 Q 2 x 2 … Q n x n 称为 首标 ， M 称为 母式 。
例如，∀ x ∀ y （ A （ x ， y ）→ B （ x ， y ））、∃ x ∀ y （ A （ x ， y ， z ）∧ C （ x ， y ））等都是前束范式，而∀ xA （ x ）→∃ xB （ x ）、∃ xA （ x ）∨∃ xB （ x ， y ）等都不是前束范式。
定理2.5.1 任一谓词公式都存在着与之等价的前束范式。
证明 设 A 为任意一个谓词公式。
1）将公式化成只含3个联结词
、∧、∨的形式；
2）利用
、德·摩根律及量词转换律等将公式中的所有
符号移到原子公式的前面。如果需要的话，将约束变元换名；
3）利用量词辖域收缩及扩张律、量词分配律等，将所有量词提到公式的最前面。
按照以上步骤，可得到谓词公式 A 的前束范式。由于每一步变换都保持着等价的关系，所以得到的前束范式与原公式是等价的。
◀
定义2.5.2 在前束范式 Q 1 x 1 Q 2 x 2 … Q n x n M 中，如果 M 是析取范式，则称为 前束析取范式 ，如果 M 是合取范式，则称为 前束合取范式 。
例2.5.1 求下列谓词公式的前束范式。
1）
2）
3）
4）
解
或者
把一个公式化成前束范式时，结果可能不唯一。例如，在例2.5.1的3）式中使用∃对∨的分配律得到只带一个量词的前束范式，还可以对第二项用换名规则将 x 换为 y ，用量词辖域收缩和扩张律求得前束范式。4）式中∀对∨不满足分配律，必须通过换名使得两项的指导变元不重名。
例2.5.2 把谓词公式 ∀ x ∀ y （∃ z （ P （ x ， z ）∧ P （ y ， z ））→∃ uQ （ x ， y ， u ））化成前束范式。
解
