例题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) |