例1
( x)(P(x)→Q(x))∧( x)(Q(x)→R(x)) ( x)(P(x)→R(x))
首先写出公式G
G = ( x)(P(x)→Q(x))∧( x)(Q(x)→R(x))∧ ( x)(P(x)→R(x))为求G的子句集S,
可分别对( x)(
P(x)→Q(x)), ( x)(Q(x)→R(x)), ( x)(P(x)→R(x))作子句集,
然后求并集来作G的"子句集"(这个"子句集"不一定是S, 但与S同时是不可满足的, 而且较S来得简单,
于是为方便可将这个"子句集"视作S)。
( x)(P(x)→Q(x))的子句集为{ P(x)∨Q(x)}
( x)(Q(x)→R(x))的子句集为{ Q(x)∨R(x)}
( x)(P(x)→R(x))
= ( x) ( P(x)∨R(x))
= ( x)(P(x)∧ R(x))
SKOLEM化(SKOLEM标准形(二)), 得子句集 {P(a), R(a)}于是G的子句集
S = { P(x)∨Q(x), Q(x)∨R(x),
P(a), R(a)}
证明S是不可满足的, 有归结过程:
(1) P(x)∨Q(x) |
|
(2) Q(x)∨R(x) |
|
(3) P(a) |
|
(4) R(a) |
|
(5) Q(a) (1) |
(3)归结 |
(6) R(a) |
(2)(5)归结 |
(7) □ |
(4)(6)归结 |
例2
A1 = ( x)(P(x)∧( y)(D(y)→L(x,
y)))
A2 =( x)(P(x)→( y)(Q(y)→ (L(x,
y)))
B = ( x)(D(x)→ Q(x))
求证 A1∧A2 B
证明
不难建立A1的子句集为{P(a), D(y)∨L(a,
y)}
A2的子句集为{ P(x)∨ Q(y)∨ L(x,
y)}
B的子句集为{D(b),
Q(b)}。求并集得子句集S,S = {P(a), D(y)∨L(a,
y), P(x)∨ Q(y)∨ L(x,
y),D(b), Q(b)}, 进而建立归结过程:
(1) P(a) |
|
(2) D(y)∨L(a,
y) |
|
(3) P(x)∨ Q(y)∨ L(x,
y) |
|
(4) D(b) |
|
(5) Q(b) |
|
(6) L(a, b) |
(2)(4)归结 |
(7) Q(y)∨ L(a,
y) |
(1)(3)归结 |
(8) L(a,
b) |
(5)(7)归结 |
(9) □ |
(6)(8)归结 |
|