@3013216027 2016-11-28T17:08:53.000000Z 字数 2821 阅读 2422

归结原理

人工智能

张和狗问题

设 $AT(x,y)$ 表示 $x$ 在 $y$ 处
问题表示为：
$\forall y\left(AT(zhang,y)\to AT(dog,y)\right)$
$AT(zhang,train)$
$\lnot AT(dog,z)$ 解为 $~z$ 。
子句集为
$\left\{\lnot AT(zhang,y)\lor AT(dog,y),\:AT(zhang,train),\:\lnot AT(dog,z)\right\}$
归结上述子句集，得到 $~nil$ ，于是证明到 $~AT(dog,z)~$ 为真。
结论：狗在某处 $(AT(dog,z))$ 。

设： $AT(x,y)$ 表示 $x$ 在 $y$ 处
问题表示为：
$\forall y\left(AT(zhang,y)\to AT(dog,y)\right)$
$AT(zhang,train)$
$\lnot AT(dog,z)\lor answer(z)$ 解为 $~z$ 。
子句集为
$\left\{\lnot AT(zhang,y)\lor AT(dog,y),\:AT(zhang,train),\:\lnot AT(dog,z)\lor answer(z)\right\}$
归结上述子句集，得到 $~answer(train)$ 。
结论：狗在火车上 $(answer(train))$ 。

设 $~T(x,y)$ 表示 $x$ 是 $y$ 的老师， $C(x,y)$ 表示 $x$ 和 $y$ 是同班同学。
问题表示为
$T(wang,li)$
$C(li,zhang)$
$(\forall x)(\forall y)(\forall z)\left((C(x,y)\land T(z,x))\to T(z,y) \right)$
$\lnot T(w,zhang)\lor answer(w)$
子句集为
$\left\{\,\,T(wang,li),\:C(li,zhang),\:\lnot C(x,y)\lor \lnot T(z,x)\lor T(z,y),\:\\\lnot T(w,zhang)\lor answer(w)\,\right\}$
归结上述子句集，得到 $~answer(wang)$ 。
结论：小张的老师是王先生。

分析：本题涉及的句型比较多，窝们先从正面简单地尝试一下，意在表达解归结问题的完整分析过程，看看如何。句型包括“ $x~$ 爱 $~y$ ”、“ $x~$ 恨 $~y$ ”、“ $x~$ 杀 $~y$ ”、“ $x~$ 是 $~y$ ”。

设 $~L(x,y)~$ 表示 $~x~$ 爱 $~y$ ， $H(x,y)~$ 表示 $~x~$ 憎恨 $~y$ ， $K(x,y)~$ 表示 $~x~$ 杀 $~y$ ， $IS(x,y)~$ 表示 $~x~$ 是 $~y$ 。
问题表示如下。
- 爱生者，人爱之：
  $生$
  $(\forall x)\,(\forall y)\,(\forall z)\:IS(x,生)\land L(y,x)\to L(z,y)$
- 杀生者，人憎之：
  $生$
  $(\forall x)\,(\forall y)\,(\forall z)\:IS(x,生)\land K(y,x)\to H(z,y)$
- 甲爱生：
  $生甲$
  $\forall x\:IS(x,生)\to L(甲,x)$
- 甲或乙杀丙：
  $甲丙乙丙$
  $K(甲,丙)\lor K(乙,丙)$
- 丙是猫，猫是生：
  $丙猫$
  $IS(丙,猫)$
  $猫生$
  $IS(猫,生)$
- 使用格林技巧，待求解问题为：
  $丙$
  $\lnot K(w,丙)\lor answer(w)$
子句集为：
$生生生甲甲丙乙丙丙猫猫生丙$
$\left\{\:\lnot IS(x,生)\lor\lnot L(y,x)\lor L(z,y),\\\lnot IS(x,生)\lor\lnot K(y,x)\lor H(z,y),\\\lnot IS(x,生)\lor L(甲,x),\\K(甲,丙)\lor K(乙,丙),\\IS(丙,猫), IS(猫,生),\\\lnot K(w,丙)\lor answer(w)\:\right\}$
归约。但是不幸的是，窝们发现归约在进行几步后就没法往下走了。仔细观察，可以发现，窝们甚至无法从“丙是猫，猫是生”归约出“丙是生”，这是多么荒谬！因此，有必要重新考虑是否忽略了一些公理，从而导致归约条件的缺失。

从上面尝试性的求解过程，窝们发现了问题所在。所以在稍复杂的问题中，或者说，绕弯比较多的问题中，最容易忽略的就是一些“看似傻逼实则精妙至极”的公理的存在。这个问题中，至少有两个公理是窝们忽略掉的：
- 事物分类的传递性： $(\forall x)\,(\forall y)\,(\forall z)\:IS(x,y)\land IS(y,z)\to IS(x,z)$
- 爱恨(爱憎)的对立性，所谓“爱憎分明”，二者不相容： $(\forall z)\,(\forall y)\:L(z,y)\to\lnot H(z,y)~$ 或者 $~(\forall z)\,(\forall y)\:H(z,y)\to\lnot L(z,y)$
同样地，把它们转成 $~skolem~$ 范式并加入子句集，就可以继续愉快地归约了。

设 $~L(x,y)~$ 表示 $~x~$ 爱 $~y$ ， $H(x,y)~$ 表示 $~x~$ 憎恨 $~y$ ， $K(x,y)~$ 表示 $~x~$ 杀 $~y$ ， $IS(x,y)~$ 表示 $~x~$ 是 $~y$ 。
问题表示如下。
- 爱生者，人爱之：
  $生$
  $(\forall x)\,(\forall y)\,(\forall z)\:IS(x,生)\land L(y,x)\to L(z,y)$
- 杀生者，人憎之：
  $生$
  $(\forall x)\,(\forall y)\,(\forall z)\:IS(x,生)\land K(y,x)\to H(z,y)$
- 甲爱生：
  $生甲$
  $\forall x\:IS(x,生)\to L(甲,x)$
- 甲或乙杀丙：
  $甲丙乙丙$
  $K(甲,丙)\lor K(乙,丙)$
- 丙是猫，猫是生：
  $丙猫$
  $IS(丙,猫)$
  $猫生$
  $IS(猫,生)$
- 使用格林技巧，待求解问题为：
  $丙$
  $\lnot K(w,丙)\lor answer(w)$
- 公理 $~1$ ：
  $(\forall x)\,(\forall y)\,(\forall z)\:IS(x,y)\land IS(y,z)\to IS(x,z)$
- 公理 $~2$ ：
  $(\forall z)\,(\forall y)\:L(z,y)\to\lnot H(z,y)~$
子句集为：
$生生生甲甲丙乙丙丙猫猫生丙$
$\left\{\:\lnot IS(x,生)\lor\lnot L(y,x)\lor L(z,y),\\ \lnot IS(x,生)\lor\lnot K(y,x)\lor H(z,y),\\ \lnot IS(x,生)\lor L(甲,x),\\K(甲,丙)\lor K(乙,丙),\\ IS(丙,猫),\\ IS(猫,生),\\ \lnot IS(x,y)\lor\lnot IS(y,z)\lor IS(x,z),\\ \lnot L(z,y)\lor\lnot H(z,y),\\ \lnot K(w,丙)\lor answer(w)\:\right\}$
归约上述子句集，得到 $~answer(乙)$ 。
结论：乙杀了丙。