形式语义教材-ch3 逻辑式语言.doc

– –72第三章第三章 逻逻 辑辑 式式 语语 言言§§3.1 概概 述述1972 年,Kowalski 和 Colmerauer 第一次提出了逻辑程序设计 概念, Colmerauer 和他的研究小组在法国 Marseille 大学第一个实 现了逻辑程序设计语言 PROLOG 语言的解释器在此之后，在 1983 年，D.H.D.Warren 第一个实现了 Prolog 的编译器自从编 译器诞生开始,Prolog 语言成了世界公认的著名语言Prolog 是 一个顺序的具体逻辑式语言,而并行的逻辑语言有 Parlog,Concurrent Prolog,GHP 等逻辑式语言的理论基础是 Horn 逻辑 逻辑式语言的应用领域有:关系数据库,问题求解,自然语言的 理解,方程式的符号解法,生物化学中的分子结构分析,数理逻辑, 人工智能等等逻辑式语言的特点有:■具有良好的逻辑性 ■具 有良好的并行性 ■具有良好的不确定性 ■可求多个解 ■有不完 全值概念■无类型概念§§3.2 有趣的有趣的 Prolog 语言语言在正式介绍逻辑式语言的理论、语法、语义等内容以前,首 先粗略地领会一下 Prolog 程序的风格和趣味性。

Prolog 程序和 我们所见到的过程式以及函数式语言有着很大的不同 在 Prolog 语言里,变量用大写字母打头的标识符来表示,凡是 小写字母打头的都是常量(整常数或原子)Prolog 程序由一组子句组成,其中子句有两类,其一叫做事实,其二叫做规则事实说明– –73一个断言,比如 like( mary,candy)表示这样一个事实：“mary喜欢 candy“规则部分,则用来表示推理,如下面是一个规则的例子:likes( mary, X)←←likes( john, X),likes( stoy, X). 它表示“如果 john 喜欢 X,并且 stoy 也喜欢 X,则 mary 喜欢 X “ 当然程序中的子句究竟代表什么内容,这是程序员自己才知道的 一个 Prolog 程序也可以是全部由事实部分组成我们知道程序必须有个输入部分那么,Prolog 程序的输入 是什么?这一点也和通常的程序不同,即输入的不是数据,而是一个 提问Prolog 系统将回答“yes“或“no“如果是 yes 情况,则具体还 指出提问中的变量取什么样的值时,能够使提问成为真例如,假 设有图 Prolog 程序则这是仅由4个事实(公理)组成的程序。

事实部分主要说的是谁 喜欢什么对于这个程序可以提出以下种种问题比如:□ ?- like( mary, candy). 回答回答yes （ mary喜欢candy吗?） □ ?- like( mary, mary). 回答回答no （ mary喜欢mary吗?） □ ?- like( mary, X ). 回答回答yes :X=candy,X=wine （mary都喜欢什么? ）□ ?- like( mary, X ),like(john,X). 回答回答yes :X=wine （什么东西(X)被mary和john所喜欢?）□ ?- like(mary,candy),like(john,candy). 回答回答no （mary和john都喜欢candy吗?）□ ?- like(X, candy). 回答回答yes :X=mary（ 都谁喜欢candy? ）图 3.2.1likes( mary, candy ). mary喜欢糖果likes( mary, wine ). mary喜欢水果likes( john, wine ). john 喜欢水果likes( john, meat ). john 喜欢肉类– –74□ ?- like(X, wine). 回答回答yes :X=mary,X=john（都谁喜欢wine?） □ ?- like(X, Y ). 回答回答yes : （谁都喜欢什么?）(1) X=mary ,Y=food (2) X=mary , Y=wine(3) X=john , Y=wine (4) X=john , Y=mary 从本例可以看出,对于同一程序可提出很多很多的问题。

在 这些提问里可包含一些变量 X1,X2,....,Xn如果回答是 yes,则将 指出当提问中的这些变量取什么样的值时使提问成为真在提问 时,只要把已知的内容写成常量,而把想知道的部分写成变量,那么 即可达到了解未知部分的目的,因此是很有趣的提问的语法结构是,由?-符号打头,并其后是一串原子式(用逗 号隔开)开始的提问部分称为初始总目标(或称目标子句),而其 中的每个原子式称为子目标总目标中的最前一个子目标称为当 前子目标如果所有子目标都成功,则总目标也就成功,这时系统 将发出 yes,并给出一个具体解 前面考虑了只有事实的 Prolog 程序但只有事实部分远不 能描述很多实际问题，比如“mary 喜欢的 john 都喜欢”等问题 下面再考虑带规则（推理）部分的 Prolog 程序例，具体如下:male( john ) . “ john 是男的“ male( stoy ) . “ stoy 是男的“ male( david ) . “david是男的“ female( mary ) . “mary 是女的“ female( rose ) . “rose 是女的“ female( mira ) . “mira 是女的“ parents_of( john, mary, davis ) . “ john的母父是 mary和 davis“ parents_of( stoy, mary, davis ) . “ stoy的母父是 mary和 davis“ parents_of( rose, mary, davis ) . “ rose的母父是 mary和 davis“ parents_of( mira, mary, davis ) . “ mira的母父是 mary和 davis“ sister_of(X,Y) :-female(X), female(Y), parents(X,M,F),parents(Y,M,F). – –75“Y是X的姐妹,当X是女的,且Y是女的,且X和Y的母父是一样的“brother_of(X,Y):-male(X),male(Y), parents(X,M,F),parents(Y,M,F). “Y是X的兄弟,若X是男的,且Y是男的,且X和Y的母父是一样的“child_of(X,Y) :-parents_of(Y,_,X). “若X是Y的父亲,则Y是X的儿子“ child_of(X,Y) :-parents_of(Y,X,_). “若X是Y的母亲,则Y是X的儿子“ inherit_of(X,Y):-child_of(X,Y). “若Y是X的儿子,则Y是X的后辈“ inherit_of(X,Y):-chile_of(Z,Y), inherit_of(X,Z).“若Y是Z的儿子,Z是X的后辈,则Y是X的后辈“ 程序由 10 个事实和 6 个规则组成。

可以提问如下种种问题:■ ?-female( X ). 谁是女的? .. .. .... .. 回答:X=mary;X=rose;X=mira■ ?-female( john ). john是女的吗? .... 回答:no■ ?-child_of( mary, X ). 谁是mary的孩子?...........回答:X=john;X=rose;X=mira■ ?-child_of( X, stoy ). stoy是谁的孩子?.. 回答:X=mary;X=davis■ ?-sister_of( mira,X ). mary的姐妹都是谁?... 回答:X = rose■ ?-brother_of( stoy,X ).stoy的兄弟都是谁? ■ ?-inherit _of( john, X ).john的后辈都是谁? ■ ?-inherit_ of( X,davis ).davis 的前辈都是谁?■ ?-inherit_ of( john,mary).john是mary的前辈吗? ■ ?-parents_of( john,M,F ).john的母亲和父亲是谁?■ ?-male(X), child_of(mary,X). 都有谁是mary的男孩?§§3.3 逻辑式语言逻辑式语言逻辑式程序设计的主要思想是把一阶谓词逻辑的公式作为程序设计的工具,而 Prolog 语言是顺序化了的特定逻辑式语言。

逻– –76辑式语言的理论基础是一阶理论与归结理论 ■■定义定义 3.3.1. 一阶理论(first order theory): 由四部分组成:( ∑∑, L, A, R ) [1] 字母表(alphabet) :∑∑ [2] 一阶语言(first order language) :L [3] 公理集(set of axioms ) :A [4] 推理规则集(set of inference rules) :R 其中字母表∑包括以下几类符号:□ Constant :a,b,c,.......... □ Variable :x,y,z,...........□ Function :f,g,h,........... □ Predicate :p,q,r,.......... □ Connective :~,∧,∨,→ □ Quantifier :,□ Punctuation: :(, ) ■■定义定义 3.3.2. 项项 原子原子(1)任何常量a∈Constant是项,任何变量x∈Variable是项;若f∈Function 是 n元函数符号, ti 是项, 则 f ( t1,t2,...,tn )是项。

2)设p∈Predicate是任一n元谓词符号(0≤n),并且ti是项,则 p(t1,t2,...,tn)是原子公式以后有时也简称为原子 ■■定义定义 3.3.3. 一阶语言一阶语言 一阶语言 L 是合适公式的集合其中合适公式的定义如下: (1) 原子公式是合适公式 (2) 若 F,F1,F2是合适公式,则下面公式都是合适公式:F1∧F2, F1∨F2, ~F1, (F), F1→F2, F1←F2, x.F, x.F ■■定义定义 3.3.4. 自由变量自由变量 设 F 是一个公式,并且变量 X 出现于公式 F 中如果X∈FreeF(F),则 称变量 X 为公式 F 的一个自由变量其中– –77FreeF(F)的定义如下:FreeF( A )= FreeA(A ) FreeF(F1∧F2) = FreeF(F1)∪FreeF(F2) FreeF(F1∨F2) = FreeF(F1)∪FreeF(F2) FreeF(~F)= FreeF(F) FreeF(x.F)= FreeF(F) -{ x } FreeF(x.F)= FfreeF( F) - { x } FreeT(const)= { } FreeT(X )= { var } FreeT(f(t1,..,tn) ) 。