avatar

利用归结原理求解问题

求解问题的步骤

(1) 已知前提$F$用谓词公式表示并化为子句集$S$
(2) 把待求解的问题$Q$用谓词公式表示,并否定$Q$,在与$ANSWER$构成析取式$(\neg Q \vee ANSWER)$;
(3) 把$(\neg Q \vee ANSWER)$化为子句,并入到子句集$S$中,得到子句集$S’$;
(4) 对子句集$S’$应用归结原理进行归结;
(5) 若得到归结式 $ANSWER$, 则答案就在$ANSWER$中。


例子

(1) 已知:
$F_1$: 王先生(Wang)是小李(Li)的老师
$F_2$: 小李与小张(Zhang)是同班同学
$F_3$: 如果 x 与 y 是同班同学,则 x 的老师也是 y 的老师。
求:小张的老师是谁?

解:定义谓词
$T(x,y)$: x 是 y 的老师
$C(x,y)$: x 和 y 是同学
把已知前提表达成谓词公式:
$F_1:T(Wang,Li)$
$F_2:C(Li,Zhang)$
$F_3:\forall x\forall y\forall z(C(x,y)\wedge T(z,x)\rightarrow T(z,y))$
设$x$为小张的老师,把目标表示成谓词公式,并把它否定后与$ANSWER$析取:

把上述公式化为子句集啊啊啊:

$C_1:T(Wang,Li)$
$C_2:C(Li,Zhang)$
$C_3:\neg C(x,y)\vee \neg T(z,x)\vee T(z,y)$
$C_4:\neg T(u,Zhang)\vee ANSWER(u)$

应用归结原理进行归结:

$C_13 :\neg C(Li,y) \vee T(Wang,y)$
$C_134 :\neg C(Li,Zhang) \vee ANSWER(Wang)$
$C_1234 :ANSWER(Wang)$

故小张的老师是王老师。
归结过程

文章作者: Liam
文章链接: https://www.ccyh.xyz/p/a36d.html
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 屿
ღ喜欢记得五星好评哦~
打赏
  • 微信
    微信
  • 支付寶
    支付寶

评论