我们刚提的是 forward chaining，那当然我们 forward
就从 site 开始，就是以这个东西开始，位置一个一个找出来，当然我们同样可以反
向来操作，就是从我们想要找的目标然后反过来看，能不能导到这个目标。
那我们一样可以用类似 always 来写，但是我们现在换个说法来说， 就是我们用一个 and-or-graph
来讲哦，其实我们做，因为我们是一个 因为这些东西是 and
嘛，比如说 A and B 然后 我们现在 horn course 像这种东西，那其实相对应来说，就是你要得到
C 的话，那你需要一个 A 还有 B 你都必须要为 true，那你就画一个 and
这个符号大家应该还记得，我们在 non-classical search
那一讲又提到的 and-or-graph，所以你们我们把 KB 所有知道的东西全部画出来之后，如果全部画出来之后，我们就可以得到一个这样的
graph，我们要先给一个目标，然后之后从那个目标开始 backward 倒退回来。
那我们来看一下怎么做到。
好，那，这边我们用几个 sample 好吧，用红色的圆圈来当作
已知的，就是我们知道的 fact。像我们刚才 KB 里头我们知道 A 是 true B 是 true，然后我们把原文当作正要看的然后
整个实心的当作是已经 check 过的，那我们 先从 Q 开始 Q 就是我们现在正在看的东西，然后之后
Q 看过了， 我们要就把它涂实，然后之后我们要看的是 p，就是如果你要
我要导到 Q 为真的话，我的前提就是 P 必须要为真，好我们就这样 backward 这样导回去， 好，那接下来就是，接下来我
P 要为真的话，我必须就是 L 和 M，这是 M search 嘛，这是 and 好，那
A no 呢那我就 L 和 M 都必须要为真 好，那这时候呢，我们就在这时候，我们看一下，就是那
我 L 要为真的时候呢，我必须要做到的就是 A 为真而且
P 为真，就是我走着一条，L 有两种走法。
你 backward 的时候有走着一条和这一条，我们假设先从左边开始走，那这边是一个一样是 and。
好，A 和 P 必须要为真，可是这边产生一个 circle 嘛
circle 就是 我是从 P 开始的，那你又回到 P 要为真，所以这条路，我们遇到这边
遇到 circle 的时候就代表走不通，你不能 A，就是我要为真的时候，你要，然后你要，这条路代表你不
知道怎么怎么办，所以我们接下来就只好换着试走这一条，OK， 所以这一条是 fail 了，这一条 fail。
好，那接下来走右路，右路的时候你看这一边，就是 A、B，你会发现这两个我都知道。
这两个都是 true，所以你就可以得到就是 L 为真。
好，你就看这边，然后你就得到 L 为真，那这时候你就把 L 加在你的 已知的 fact 嘛，刚刚是有
A、B，所以我们现在用红圈来代表，就是已知的，然后接下来我们有一个正在 checking
的就是 M，对不对，我们刚也就 return 到这边，我们刚刚要 L、M 同时为真，那你再来看 M
的时候，M只有一条路，那这一样是 M search，所以你会需要这两个为真，那 这两个都已经是为真的，所以你就可以得到，
M 为真，然后接下来 return 回去，P 为真然后最后得到 Q 为真。
这就是一个 backward chaining，就是从后面用 tree search 的方式来 searh。
forward chaining 和 backward chaining 它的 complexity 呢，它的时间复杂度基本上都跟你的 knowledge base
的 size 成 linear 的关系，那有一些，因为它的本身特性不同，我们把 forward
chaining 又称为 data-driving，就是你有哪些资料，一开始你就一直 展下去。那
backward chaining 呢就是 goal-driven 你需要的一个目标，你从那边来开始导。
好，一般比较 general 而言，backward chaining 比较是人类在做 problem solving
的 事情，譬如说，我们在想说，我要是去哪里了或是我要怎么 pass 这一门课， 你可能是有目标，然后我再去找方法来做，那
forward chaining 比较不太 human 一点， 但是 forward chaining 有好有坏，它的好处是，它可以把所有
KB 能 entail 的东西全部都导出来，我们刚看过 iii 你就知道这种感觉。
KB entail
的是对的事情，它全部都会导出来，可是这个过程中呢，缺点就是你可能会导出很多没用的 conclusion， 你可能会跟你的目标毫无关系。
那一般而言，因为我的 backward chaining 是 goal-driving 我是
想要知道我要导什么，我再去做它的 influence，所以 in general
来说，backward chaining 的 速度会比 forward chaining 来得快一些。一般来说是这样的。
好，那我们再谈一下，我们这一讲，主要都在讲 propositional logic
我们再讲一下 propositional logic 的优缺点，当然好处其实蛮多的，第一个是像它是 declarative，也就是说
你只要把它宣告出来，那后面的 influence 可以蛮系统化了。
很多一些特性包含像它是 compositional，它是可以 组成的，就是它的语意基本上譬如说，B
1.1 P 1.2 这样的语意呢其实就是我不用额外再定义，我只要
我已知这个的 semantics 还有这个的 semantics 我就可以定义它的 semantics。
好，这个就是，在 1.1 我有感觉到 breeze 嘛，在 1.2 有
pit，你知道这两个语意的时候，你任何的 logic 任何的 and-or 组成，或是 indication 它的语意，自然而然的就被定出来了。
好，这是蛮好的一件事，那还有一个就是它的 意义呢，基本上就是所谓的我们叫
context independent 跟上下文无关， 就是跟上下文无关，那相对的有一种讲法，叫
context free 或 context indepentent，那像自然语言就不是了。
好，自然语言的话我们有很多，就有些讲话如果我们在讲双关语，将一些讽刺的话，那这- 个跟我们
就是你可能单看，就是有时候新闻媒体常做的事情是断章取义吗，你访问一个人，他讲一- 大堆话，
你就把他讲的某一段话，抽出来放在某些接在某些地方情况下，那我们会觉得他这句话，你就- 会觉得他是恶意的或是
它的代意义跟他原句，原文装是不太一样的，好，那在这 logic
里面是不会的，在 logic 它一句话就代表 只有它的意思跟上下文 independent。
那 propositional logic 当然有很多缺点，包含，像它的 expressive power 是不够的。
譬如说像我们刚刚在做 wumpus world 的时候，大家有看到，因为我们基本上有个 rule，就是说你只要站在
pit 的旁边，你就会感觉到 breeze， OK，那这句话你没办法在 propositional
logic 直接用一个 rule 定出来，我们要定得很累，就是你可能必须要 B
1.1 好然后它代表了 P 2.1 或 P 2.1，然后之后你还要再定一个
B 2.2，你又要再来，好，那这个东西，你对所有的 16 格，你可能都要
这样定，如果今天我的 wumpus 的世界在拓展，比如说，一百万乘一百万的格子， 你就等于说你要一百万乘一百万条
rule 来描述这件事，这是 propositional logic 做 不是很 express
的东西，那我们下一讲会讲到 first-order logic，这里面 introduce 一个 变数的概念，那就可以做到，因为我只要定义
B x.y，它就可以代表什么，可以代表 这边 introduce 变数，那我就可以用一条 rule 来描述我刚刚所讲的这句话。
好，以上我们总结一下我们这一讲的内容，基本上就是，我们使用了 逻辑式子
logic 来描述，然后我们所有的已知的东西，都会放在一个 knowledge base 里面。
好，那所有的这个 knowledge base 所表含的东西，所有它的 syntax 它的定义是有它
的语法和它语意所定出来的，那我们这边有讲到一个很重要的事情，大家记得一下，model 和
entailment 不管你用 syntax 来表示一件事情的时候，那它的 所以我们的
ground truth 就是你这个 knowledge base 所可以 entail 的任何东西，就是它的 ground truth。
好，那我们在 entail 上我们讲一些东西大家回想一下，那我们在讨论的时候，我们很在意的是 sound
还有 就是 sound 和 complete 这件事，在我们的任何 influence 来说就是已知的 导出来都是对的，对的你都能导出来，好，那在
propositional logic 里面，这样的 influence 是存在的，那 resolusion 就是其中一个，就是它记上的
又 complete，在你的 KB 表示成 conjunctive normal form 的情况下，那我们刚刚有讲过，任何一个逻辑
propositional logic 你都可以在 iii time 接近 linear time 你可以把它转成
conjunctive normal form，也就是说 resolution 是 iii
propositional logic，如果今天我们把 propositional logic 的范围再缩小一点。
这就是缩小到 horn cross，horn cross 的话，那这个不是全部的。
proposition 就是不是任何一个 propositional logic 的
syntax 都能转成 horn course 一个比较小的 subset，但是 anyway 如果在这个小一点的
subset 我们可以用 forward chaining 我们刚才讲的和 backward chaining，它基本上速度比 enquire
非常多，它基本上是 linear to knowledge base 的 size。
那尤其是 backward chaining 的话如果你已知你的目标，它的速度可以比 forward chaining 还更快一些，以上是我们这一讲的内容。
于天立(Tian-Li,Yu)副教授（Associate Professor）
