第12章逻辑式程序设计语言

《第12章逻辑式程序设计语言》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第12章第12章逻辑式程序设计语言无论是命令式还是函数式程序都把程序看作是从输入到输出的某种映射。当然命令式语言有时没有数据输出，但也要“输出”某些动作。为了实现这种映射，程序要对数据结构实施某个算法过程，算法实现该程序功能。算法又是以程序语言提供的控制机制实现计算逻辑。所以，R.Kowalski说:算法=逻辑+控制然而传统语言计算逻辑在程序员心里，隐式地体现在程序正文之中，为此程序正确性证明还要把它隐含的逻辑以断言形式地写出来。自然人们会想到能不能把描述计算的理论基础命题演算和谓词演算直接变为程序设计语言。这样，也许不必用求值来判定某件事情

2、的真、伪，直接根据事实和规则判定真伪，“找出”解。事实上，这是可行的，而且在人工智能的专家系统、语言理解、数据库查询中非常需要这种程序设计语言。1970年诞生的Prolog长久不衰就是例证。逻辑程序设计的基本观点是程序描述的是数据对象之间的关系，它的抽象层次更高而不限于函数(映射)关系。关系也是联系，对象和对象、对象和属性的联系就是我们所说的事实。事实之间的关系以规则表述，根据规则找出合乎逻辑的事实就是推理。因此，逻辑程序设计范型是陈述事实，制定规则，程序设计就是构造证明。程序的执行就在推理，和传统程序设计范型有较大的差异。本章我们从逻辑程序

3、设计理论基础，谓词演算导出逻辑程序语言的理论模型，并介绍逻辑程序设计语言Prolog的主要特征和实现要点。12.1谓词演算谓词演算是符号化事实的形式逻辑系统，它也是逻辑程序设计语言的模型，谓词演算在所有计算机理论的书籍中均有论述，本章仅简单复习，主要目的是引入术语。12.1.1谓词演算诸元素用形式方法研究论域上的对象需要一种语言，它能表达该域对象具有什么性质(properties)，以及对象间有些什么关系(relations)。为了一般化还要有变量(variable)指明域上某个(些)对象，以及准确说明对象情况的量词(quantifiers)

4、。当然这个语言还需要一些辅助的符号(继承自初等集合论)。描述以公式(Formulas)表达，即描述一般命题的谓词。谓词公式中各元素按一定逻辑规则变换即谓词演算(predicatecalculus)。以下是谓词公式的示例:$Xp(X)—存在具有性质p的对象X。"Yp(Y)—所有的Y，即域上任何对象，均具有性质p。"X$Y(X=2*Y)—对于所有的X都可以找到Y，其值为X的一半，其中的逻辑连接”=”是中缀表示。等效于=(X，2*Y)。第17页第12章谓词公式各元素符号表示法在各教程中不尽相同，谓词演算的表示由以下元素组成:(1)公式由一组约定的符

5、号组成的序列，它包括常量(指明域上的某个对象)、变量(域上任意对象)、逻辑连接(指明对象状态及对象间的关系，有数量上的>、>=、=、<、<=、/=和逻辑上的∨、∧、、→、<＝>)、命题函数(指明对象间的函数性质)，谓词(对象间约定的关系)，量词(逻辑连接的一种，指明对象状态)。一阶谓词演算系统中公式里不得嵌套谓词。(2)常量指明论域(universeofdiscourse)上的对象，也是数学对象。通常一个逻辑系统要引入多个论域，一般有十进制整数域、真值域、字符域，可用不同的符号表达有区别的域。常量可以看作是退化了的函数(没有变元)。常量以字面

6、量或小写字母表示。(3)变量可束定到特定域上某个范围的对象上，在演算(归约)期间它可以例化为具体对象(常量对象)，变量是数学意义的，一旦束定整个演算期间不变，变量以大写字母表示。(4)函数表征对象具有的映射关系，函数带参数，从变元域映射到结果值域(可以是不同的域)。变元一般是常量、变量、函数结果值、变元在语法上都叫项(term)。函数以小写标识符表示。(5)谓词表征对象某种性质的符号，谓词带上一到多个变元(对象)即为断言(assertion)。它断言这些对象具有谓词所指性质，谓词形如函数，当该变元确实具有所指性质时隐含真值，否则为假。当谓词应

7、用到的变元是常量或已被束定的变量上时，就叫做句子(senteuce)或命题(proposition)，查询时能返回真假值。当谓词应用到变量或包含变量的项上时，它依然是谓词但不能形成句子，只有例化才能判定真伪，形成句子。谓词变元的个数称作目(arity)，故有单目、N目谓词之称。例12-1N-目谓词的例子。谓词目含义odd(X)1X是奇数father(F，S)2F是S的父亲divide(N，D，Q，R)4N除D得商Q和余数R谓词例化结果值odd(2)Falsedivide(23，7，3，2)Turefather(changshan，changp

8、ing)Truedivide(23，7，3，N)N未例化，不知真假(6)量词变量可以代表域中任何对象，量词可以指定某种集合，量词有两个，一为全称‘"’、一为存在‘$