例题2-2
将下式化为Skolem标准形:
~( 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))
第二步,~深入到量词内部,得:
( 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))
第三步,全称量词左移,(利用分配律),得
( x)( ( y)P(a,
x, y) ∧( y)(~Q(y,
b)∧~R(x)))
第四步,变元易名,存在量词左移,直至所有的量词移到前面,得:
( x)( ( y)P(a,
x, y) ∧( y)(~Q(y,
b)∧~R(x)))
= ( x)
( ( y)P(a,
x, y) ∧( z)(~Q(z,
b)∧~R(x)))
= ( x)
( y) ( z)
(P(a, x, y) ∧~Q(z, b)∧~R(x))
由此得到前述范式
第五步,消去" "(存在量词),略去" "全称量词
消去( y),因为它左边只有("x),所以使用x的函数f(x)代替之,这样得到:
( x)( z)(
P(a, x, f(x)) ∧~Q(z, b)∧~R(x))
消去( z),同理使用g(x)代替之,这样得到:
( x) (
P(a, x, f(x)) ∧~Q(g(x), b)∧~R(x))
则,略去全称变量,原式的Skolem标准形为:
P(a, x, f(x)) ∧~Q(g(x), b)∧~R(x) |