例1
求 (( x)( y)P(a,
x, y)→( x)( ( y)Q(y,
b)→R(x))) 的前束范式。
可按下述步骤实现:
(1) 消去联结词→, 。
得 ( ( x)( y)P(a,
x, y)∨( x)( ( y)Q(y,
b)∨R(x)))
(2) 内移(反复使用摩根律)
得 ( x)( y)P(a,
x, y)∧ ( x)(( y)Q(y,
b)∨R(x))
=( x)( y)P(a,
x, y)∧( x)(( y) Q(y,
b)∧ R(x))
(3) 量词左移(使用分配等值式)
得 ( x)(( y)P(a,
x, y)∧( y) Q(y,
b)∧ R(x))
(4) 变元易名。(使用变元易名分配等值式)
( x)(( y)P(a,
x, y)∧( z) Q(z,
b)∧ R(x))
= ( x)( y)( z)(P(a,
x, y)∧ Q(z,
b)∧ R(x))
= ( x)( y)( z)S(a,
b, x, y, z)
经过这几步,便可求得任一公式的前束范式。由于每一步变换都保持着等值性,所以,所得到的前束形与原公式是等值的。这里的
S(a, b, x, y, z)
便是原公式的母式。
由于前束中量词的次序排列,如( y)( x)可写成( z)($y)以及对母式都没有明确的限制,自然前束范式不是唯一的,如例1的前束范式也可以是
( x)( z)( y)(S(a,
b, x, y, z)∧P)
其中P可以是任一不含量词的普遍有效的公式。
|