逻辑程序设计

逻辑程序设计是相当接近于第七章中描述的陈述性思想的一种技术：应该采用形式语言表达知识从而构建系统，并且应该在这些知识上运行推理过程从而求解问题。该思想可以用罗伯特·科瓦尔斯基（Robert Kowalski）的等式进行总结，

算法 = 逻辑+控制

Prolog是应用最广泛的逻辑程序设计语言。它的用户成千上万。它最初作为快速原型语言，用于符号操作任务诸如写编译器（Van Roy，1990）和对自然语言进行语法分析（Pereira和Warren，1980）。法律、医疗、商业和其它领域的许多专家系统都是用Prolog语言编写的。

Prolog程序是用与标准一阶逻辑稍有不同的符号编写的确定子句集。Prolog采用大写字母表示变量，小写字母表示常量。在书写子句的时候，子句头在子句体的前面；“:-”表示左蕴涵，逗号将子句体内的文字分隔开，句号表示语句的结束：

criminal(X) :- american(X),weapon(Y),sells(X,Y,Z),hostile(Z).

Prolog包括用于表符号和算术的“句法便利”。作为一个例子，有一段关于append(X,Y,Z)的Prolog程序，如果表Z是拼接表X和表Y的结果，则程序运行成功：

append([],Y,Y)

append([A|X],Y,[A|Z]) :- append(X,Y,Z)

在自然语言中，我们可以将这些子句读作：(1)将表Y拼接到一个空表，产生同一个表Y；以及(2)[A|Z]是将[A|X]拼接到Y的结果，倘若Z是将X拼接到Y的结果的话。append的定义显得与Lisp语言中的相应定义非常相似，但实际上功能更强。例如，我们可以提出查询append(A,B,[1,2])：什么样的两个表可以拼接得到[1,2]？我们找到了解

A=[]　　　　 B=[1,2]

A=[1]　　　　B=[2]

A=[1,2]　　　B=[]

Prolog程序的执行是通过深度优先的反向链接完成的，子句按照它们写入到知识库的顺序被尝试。Prolog的某些方面脱离了标准的逻辑推理：

• 有一个用于算术的内建函数集。采用这些函数符号的文字是通过执行代码而不是做更进一步的推理来“证明”的。例如，在X绑定7时，目标“X为4+3”是成功的。另一方面，“5等于X+Y”是失败的，因为内建函数不能完成任意等式求解[32]。

• 有内建谓词，在执行期间会产生副作用。这包括用于修改知识库的输入-输出谓词和assert/retract谓词。这类谓词无逻辑上的副本，同时会生成一些令人困惑的影响——例如，如果事实是在证明树的一个最终会失败的分支内断言的。

• Prolog 允许一种否定格式，称为失败的否定式。如果系统无法证明 P，就可以认为否定目标not P已被证明。因此，语句

alive(x) :- not dead(x)

可以理解为“如果不是能被证明已经死亡，那么每个人都是活着的”。

• Prolog有一个等式运算符，＝，但它缺少逻辑等式的全部能力。如果两个项可以合一，那么它们之间的等式目标能成功，否则目标是失败的。因此，当X绑定2且Y绑定3时，X+Y =2+3成功，但morningstar = eveningstar失败。（对经典逻辑而言，后一个等式可能为真也有可能不为真。）没有关于等式的事实或者规则可以被断言。

• Prolog的合一算法中省略了发生检测。这意味着会进行一些不可靠的推理；这很少是一个问题，除了当用Prolog进行数学定理证明时。

在设计 Prolog 程序时所做的决策表现了陈述性和执行效率之间的折中——因为效率的问题在设计Prolog时就已经很了解了。我们将在观察Prolog程序是怎样实现的之后重新考虑这个问题。