逻辑编程是数学逻辑吗

分析查询语言与数学逻辑的差异：过程式解释、无限循环以及 not 的特殊语义。

逻辑编程是数学逻辑吗？

查询语言使用的组合手段，初看起来可能与数学逻辑的 and、or 和 not 运算完全相同，而且查询语言规则的应用确实是通过一种正当的推理方法完成的。然而，把查询语言等同于数学逻辑并不真正成立，因为查询语言提供了一种把逻辑语句作过程式解释的控制结构。我们常常可以利用这种控制结构。例如，要找出所有程序员的上级，我们可以用下面两种逻辑上等价的形式之一来构造查询：

(and (job ?x (computer programmer))
     (supervisor ?x ?y))

或

(and (supervisor ?x ?y)
     (job ?x (computer programmer)))

如果一家公司的上级比程序员多得多（通常情况），那么用第一种形式比第二种好，因为 and 的第一个子句每产生一个中间结果（框架），都必须扫描一遍数据库。

逻辑编程的目的，是为程序员提供把计算问题分解为两个独立问题的技术：“算什么”和”如何算”。这是通过选取数学逻辑语句的一个子集来实现的，这个子集要强大到足以描述人们想算的任何东西，又要弱到能有可控的过程式解释。这里的意图是：一方面，用逻辑编程语言指定的程序应该是一个能由计算机执行的有效程序。控制（“如何”算）通过使用语言的求值顺序来实现。我们应当能够安排子句的顺序和每个子句内子目标的顺序，使计算以被认为有效且高效的顺序进行。同时，我们又应当能够把计算的结果（“算”什么）看作逻辑定律的简单推论。

我们的查询语言可以看作正是这样一个可过程式解释的数学逻辑子集。一条断言表示一个简单事实（原子命题）。一条规则表示这样一种蕴含：在规则体成立的那些情况下规则结论成立。规则有一种自然的过程式解释：要确立规则的结论，就要确立规则的体。因此，规则规定计算。然而，由于规则也可以看作数学逻辑的语句，我们可以这样为逻辑程序完成的任何”推理”辩护：断言同样的结果完全在数学逻辑内工作也能获得。

无限循环

逻辑程序过程式解释的一个后果是：有可能为解决某些问题而构造出毫无希望地低效的程序。低效的极端情形发生在系统作推理时陷入无限循环。举个简单的例子，假设我们正在建立一个名婚姻关系的数据库，包括

(assert! (married Minnie Mickey))

如果我们现在问

(married Mickey ?who)

我们不会得到任何回应，因为系统不知道如果 A 与 B 结婚，那么 B 也与 A 结婚。于是我们断言规则

(assert! (rule (married ?x ?y)
               (married ?y ?x)))

然后再查询

(married Mickey ?who)

不幸的是，这将使系统陷入无限循环，过程如下：

系统发现 married 规则适用；也就是说，规则结论 (married ?x ?y) 成功地与查询模式 (married Mickey ?who) 合一，产生一个 ?x 绑定到 Mickey、?y 绑定到 ?who 的框架。于是解释器接着在这个框架中求值规则体 (married ?y ?x)——实际上就是处理查询 (married ?who Mickey)。
有一个答案直接作为断言出现在数据库中：(married Minnie Mickey)。
married 规则也适用，于是解释器再次求值规则体，这一次它等价于 (married Mickey ?who)。

系统现在陷入了无限循环。的确，系统是在陷入循环之前还是之后找到简单答案 (married Minnie Mickey)，取决于系统检查数据库中各条目顺序的相关实现细节。这是可能出现的各种循环的一个非常简单的例子。相互关联的规则集合可能导致更难预料出现的循环，而循环的出现可能取决于 and 中子句的顺序，或取决于系统处理查询顺序的底层细节。

`not` 的问题

查询系统中另一个古怪之处与 not 有关。给定前面介绍的 Microshaft 数据库，考虑下面两个查询：

(and (supervisor ?x ?y)
     (not (job ?x (computer programmer))))
(and (not (job ?x (computer programmer)))
     (supervisor ?x ?y))

这两个查询产生的结果不同。第一个查询先找出数据库中所有匹配 (supervisor ?x ?y) 的条目，然后过滤得到的框架，剔除其中 ?x 的值满足 (job ?x (computer programmer)) 的那些。第二个查询先过滤输入框架，剔除能满足 (job ?x (computer programmer)) 的那些。由于唯一的输入框架是空框架，它检查数据库，看是否有模式满足 (job ?x (computer programmer))。由于一般存在这种形式的条目，not 子句过滤掉空框架，返回一个空框架流。因此整个复合查询返回空流。

问题在于，我们对 not 的实现实际上是想让它充当变量值上的过滤器。如果一个 not 子句在含有未绑定变量的框架中被处理（如上面例子中的 ?x），系统将产生意外的结果。lisp-value 的使用也有类似的问题——如果某些实参未绑定，Lisp 谓词无法工作。

查询语言的 not 与数学逻辑的 not 还有一种严重得多的差异。在逻辑中，我们把语句”非 P”解释为 P 不为真。然而在查询系统中，“not P”意味着 P 不能从数据库中的知识推出。例如，给定 Microshaft 数据库，系统会高高兴兴地推出各种各样的非语句，比如 Ben Bitdiddle 不是棒球迷，外面不在下雨，2 + 2 不等于 4.7。换句话说，逻辑编程语言的 not 反映了所谓的封闭世界假设（closed world assumption），即所有相关信息都已包含在数据库中。

要点

在本小节中，你学到了：

逻辑编程是数学逻辑的一个可过程式解释的子集。
存在陷阱：循环和 not。

逻辑编程是数学逻辑吗