那prolog system它其实是用，它整个导论的过程，是用backward

chaining，我们刚刚有看到，也就是说，从我们的query开始，然后一个一个递回，

用DFS的方式来找答案。那我们之前有提过一个occur check这个东西，也就是说，

在unify的时候，因为unify的过程它要找两边一样，那它这个过程，两边左右两式- 其实都是用树状结构一直往下搜寻，

直到找到某一个地方，它可以match这个文字，完全match的时候，就是等于说，你找到unify，可是，这个过程其实，如果你要check说

是不是在同一层，或是某些地方，你是不是经过同样的替代的话，那这个过程我们称为occur

check，我们那时候有提到，其实，有点接近像是你要check

某些state，它是不是有repeat，有在重复出现，那这个，你这样可以做，

当然还蛮耗费记忆体的，也蛮耗费时间，那所以在proglog的system里面，其实- 是不做occur check的，那因为不做occur check的结果，

就可能会导致unsum的结果，就是有些东西其实不对，但是你会推导出来，那我们来看一- 下，prolog其实是

会发生这件事情的。好，我们看一下这个程式是这样写的，好，这个程式的部分，是，我说test

is true，if p(A，A) 是true，好不好，p是个反正就是一个我要用的function，那A和A就是两-

个变数，就是左边和右边都一样的时候，test就会true，那接下来我给它的一个fact

就是p，然后括弧A和f(A)为true，那因为A和f(A)，你不管p换什么东西进去，

它第一个argument和第二个argument已经不会一样，因为第二个argum- ent已经多一个f，那我们接下来，我们问问看test

大家应该是跟我讲false，但是这个case我们讲yes，也就是说，它其实不应该match出来，但是它match出来的，我们可以trace

可是这个trace又蛮长的，我一幕可能不是很容易show，它基本上就是你如果trace它的话，你问test它会，

它会呼叫，就是某变数64，64号变数和64号变数，然后接下来呢，它会一次resol- ve这个东西，

还有因为这个recursive，就是它在找unify的时候，它会找到所有fff这样- 一直括下去，然后一直和右边这边，

fffff一直下去，那这个如果你没有做occur check的话，

你不会知道，左边的f的次数跟右边的f的个数是不是一样，它到一个地步，它不能用尽，

它已经没办法再受令下去了，它就认为找到一样的，它就会认为这是true，就是说tes- t为true。

好，像这个就是一个例子，就是prolog可以给我们错误的，就是推论，它其实本来应该是sum的，可是因为我们没做occur

check，以至于它的结果可能是不对的，那它因为是做depth-first，然后当然是左数开始下去，

那有可能，会造成无穷回旋，就是你左支那里因为DFS，这时DFS移项的

移项的问题，它既用的少，但是如果左支一开始很快就进入无穷回旋的话，就不会回来，

那这当然有很多解决方法，我们在很早的时候，第而讲第三讲的时候就提过，我们可以用 depth-limit或是iterate-deepening来解决这些事情，但是p-

rolog system大部分的实作为了效率，为了推导效率，都没做这件事，也就是说prolog一样可以给我们

除了可能给我们unsum的结果，也可以给我们incomplete的结果，也就是说，- 你的有什么东西应该是应该是对，但是你没办法导出来。

那这个is，我们刚刚有讲过，那就大致上反正is你不可以作arbitrary的equation

solve，也就是说你说，five 5 is x+y

这时做不到的，因为当然，因为它到x+y要给你什么东西，它有很多可能性，那你只能，- 只能是做

一种predicate，就是你如果右式这边，你可以evaluate出一个值，那它可- 以用unify时的左式右式一样，那还是做得到的。

prolog的使用并不完全是first-order logic semantic，那它实际上用的是一个代数，我们称为database

semantic的一个东西，那它这个语义会使得prolog在写的过程会更简介有利一点，那它基本上

database semantic有三个假设，在我们等一下的部分会提到，那我们这边看一下，我们刚看过-

unsumness的的结果，那我们看一下incompleteness，就是有些是对的，但是并不导出来，

譬如说我们在这个例子里面是，a跟b之间有个连线，我们看一下这边，

就是，ok，a跟b之间有连线，然后b跟c之间有连线，那我们要问，我们定义，这是link是定义，就是a跟b之间有link，b跟c之间有link，那我-

们要问， path，就是到a到c之间有没有一条路，那我们试着要定义 path这个东西，那path我们可以有定义很单纯，我们可以说，

ok，如果x跟z之间有path，你有link就代表你一定有path，那另外一个可能就是，你x跟z之间有path呢，也可以是

你有一条path可以到y，y我还不知道是什么，但是然后y到z有一个Link，

这样也可以，这是一个递回定义。那我定义完了以后，我就可以问说，a到c之间有没有一条- path，

那根据given这个定义，我们人类很明显的知道，就是a跟c之间，当然要有个path- 嘛，对不对，

因为b跟c之间有个link，这是第二条路，b跟c之间有个link，而且a到b之间有- path，

ok，有个path，好那为什么a跟b之间有path呢，因为第一条

那我们知道，a跟b之间有link的意义，就代表a跟b之间有path，所以应该是，应该可以正确的导出来。

但是其实这个，这个结果会跟你的你怎么写有关系，好，我们看一下这一个，这是我们第一版path

1，那我这里面的knowledge

base里面就是，a到b之间有个link，然后 b到c之间有link，那path就是我们刚刚讲的，你有link的话，就代表path

或是你这有一个c的一个点，那你a到c有path，然后c到b有link，这样是一个p- ath。

那接下来我可以，就会问，a到c之间有没有一条path，有没有一条路径可以到。

那这个结果就会跟我讲，就是yes，ok？好，这是这个部分，

这是我们认为是合理的，也是正确的，但是如果我们今天把中间这一个，

这个路呢，我们把它换过来，我把这条路跟下面一条路，我反过来写的话，我们来看，这是path 2的版本，好，path

2的版本其实跟path 1非常接近，它的差别就是我刚刚讲的，就是我把两条路我互换，次序互换，那这个次序互换会造成它在backward

chaining的时候的左支，现在优先会走这一条，这是它的左边，就在backward chaining

的左边，然后之后还会search下面一条。那我同样的，我问a到c之间，有没有一条 path呢？其实这个应该会当掉，

我还会进入无穷回圈，然后基本上就停止运作，那也许有一些其它的prolog的incr- ementation

会到一个地方，会终止，然后跟你说，它无法知道，那我们来看为什么，其实原因也不难，

我们开始trace，然后我们来看一下，问a到c之间是不是有一个，有一条path，好，那第一件事情

它就呼叫这个，然后我现在问path a

c的话，它前面两个当然都被link到，那第一个问的就是这边，它会把x换成a，然后把z换成c，然后接下来呢，它就要问，

就是x是已知的，就是a嘛，然后a能到哪里有条path，这就是我们看到的这个部分。

它就会问a到y是多少，y是不知道的。好，

那a到y，它接下来一样，递回呼叫，它又马上的跑到这边，

你从上往下看，对不对，就是你这边看到，一样是，这边x一样是a，那z呢会换成d，

105号变数，然后接下来它会问，它query是这一个，一样是a能到哪，那就换成一- 个a的到

能到哪里，这个哪里变成129号变数，然后就递回呼叫，153号， 177号，这只是它内部一个流水号，但它在不断的卡在这边，进入无穷回旋，

然后一直到它记忆体用不够，它就当掉。我们如果看画成树状结构的话，

我们用原来的，现在这个结构的话，那就是

我们次序如果是先这个，这是我先写这个路，再写这个路的话，那它其实就是，它在search

path a c的时候，它会先apply第一个路，它的左支在这边，它会这个找不到，那之后会走右支这一块，那就搞定了。就是path

a y，然后这边，然后a y的时候它可以找到link a y，那这个可以找到a到b有个link，好，那如果我是，我们现在反过来，

就是我的，我刚刚show的这时写第二，写在下面，写在上面的话，它的左边呢，path a c的左边变成path

a y，就是 path a替换，然后y是不知道的，接下来path a y呢又会变成一个path

a y‘，再search path a y‘，那这一支，大家可以看到从左边用DFS一路往下冲的结果，就是一个无穷回旋，那一直都不会回来。

也就是说，prolog我们没有做occur check，所以它会给以上的结果，

那它在backward chaining的时候用DFS为了省记忆体，所以它也可能先用无穷回旋进入了

给你，以至于没办法给complete的结果。那接下来我们还是可以讲一下，就是在prolog里面用backward

chaining，那我们提过 backward

chaining在很多时候，其实比forward chaining来的有效率，但是这不是百分之百的事情，例如像课本，就是提的一个例子，

就是，如果我们刚刚一样用link把这些箭头，就是哪个点到哪个点，link的全部写到- kb里面，

那在这个地方，我问说从a1这个点，能不能到j4这个点。

那在backward chaining的时候，这个课本里面的统计，那你用prolog里面backward-

回来，你需要花877次的inference，其实蛮久的，也就是说，我从倒过来走，那你如果forward

chaining，其实你如果做到好的话，其实跟这跟choosing path一样的，是一个dynamic programming的过程，

其实你往前，然后你记录a1能到的地方，就是你第一步先记a1能到这里，然后这里，

一开始a1就能到这里，然后之后再，你再算这两个点能到的，就是这里，这里，以及这里。

然后之后你再一步一步，就这样从左到右，一步一步的这样往下走，那其实只需要62步就可- 以搞定。

虽然forward chaining一般来讲，它通常有时候比较没效率，就是它会induce出所有

就是所有可以是正确的结论，forward chaining都会给你，那backward

chaining会根据你的query，来决定你要怎么走，但是即使这样，一般而言，我们是用backward

chaining比较有效率，但是其实，在很多case里面， forward

chaining有时候是更有效率的。那是我们这边讲的就是，如果在backward chaining，我们希望让它有效率一点，其实在dynamic

programming里面常用一个方法，就是memoization是一个很好用的方法，但是其实你的，你就要花额外的记忆体来-

记住说，哪些state 是已经到过的。好，这边要做一个简单的总结，就是其实prolog这个

是一个在AI里面很常用的logic programming的tool，但是它因为为了inference的效率来说，它做了它可以给你incomplete的结果，-

还有unsum的结果，然后它在某些问题上，其实我们并不见得比forward chaining来的好，我们讲的一些

比较虚弱的地方，但是given这些事实，prolog仍然在AI界是被非常广为应用，

而且可以很容易inference出，证出来很多事情的一个语言。

那么最后要show的一个事情，就是west这个东西，west这个东西就是我们如果把课本的，我们要证明current

west是有最这个东西，我们把sentence整个写出来，大家可以看一下，其实这里面对应的就是我们之前所提的，就是，譬如说，

我们知道nono有一个m1，有个missile，那我们知道m1是个missile，- 然后我们知道

west是american等等，这边整个资料，knowledge base我们是很忠实的，

把它整个我们上课讲的这个资料写成prolog，那解析来，我们很容易可以去问，criminal

west，那这个资料库很理所当然可以瞬间跟你讲yes，我们可以看，其实prolog即使我给它更多的clause，

极大说west criminal这件事是，相对来说还是非常简单有率效的。

7-7 Logic Programing (ii) - Redundant Inference and Infinite Loops in Prolog

人工智慧(Artificial Intelligence)

与讲师见面