逻辑式程序设计语言

《逻辑式程序设计语言》由会员分享，可在线阅读，更多相关《逻辑式程序设计语言（37页珍藏版）》请在金锄头文库上搜索。

1、第06章 逻辑式程序设计语言程序要对数据结构实施某个算法过程,算法实现计算逻辑 算法 = 逻辑 + 控制逻辑程序设计的基本观点是程序描述的是数据对象之间的关系。关系也是联系对象和对象、对象和属性的联系就是我们所说的事实。事实之间的关系以规则表述，根据规则找出合乎逻辑的事实就是推理逻辑程序设计范型是陈述事实、制定规则，程序设计就是构造证明。程序的执行就在推理冗冗笼笼诚诚祷祷悄悄绞绞头头捎捎晕晕戴戴宗宗藕藕颊颊奠奠篓篓撵撵缚缚声声武武公公荚荚辱辱俯俯嚷嚷脂脂涩涩滤滤牲牲窗窗室室骄骄蜒蜒逻逻辑辑式式程程序序设设计计语语言言逻逻辑辑式式程程序序设设计计语语言言6.1谓词演算谓词演算 谓词演算是符号化事

2、实的形式逻辑系统，它也是逻辑程序设计语言的模型 谓词演算诸元素谓词演算诸元素 用形式方法研究论域上的对象需要一种语言，它能表达该域对象具有什么性质(properties)， 以及对象间有些什么关系(relations) 描述以公式(Formulas)表达。谓词公式中各元素按一定逻辑规则变换，即谓词演算(predicate calculus)乙乙谷谷轻轻尾尾埂埂人人标标捕捕侦侦依依疗疗借借踢踢匈匈蹭蹭锡锡酞酞脏脏掖掖魏魏咎咎铀铀驯驯樟樟瓷瓷窃窃孪孪程程吠吠跳跳野野笛笛逻逻辑辑式式程程序序设设计计语语言言逻逻辑辑式式程程序序设设计计语语言言(1)公式 由一组约定的符号组成的序列，它包括常量、变量、

3、逻辑连接、命题函数、谓词、量词(2)常量 指明论域上的对象(3)变量 可束定到特定域上某个范围的对象上(4)函数 表征对象具有的映射关系(5)谓词 表征对象某种性质的符号(6)量词 量词限定的变量名作用域是整个公式(7) 逻辑操作 and， or， not， (蕴含) (全等)当谓词应用到的变元是常量或已被束定的变量上时，就叫做句子(sentence)或命题(proposition)观观枉枉遗遗惧惧必必作作孽孽砸砸掏掏蜜蜜档档牡牡八八闷闷蔑蔑啦啦侥侥付付粒粒娩娩瞅瞅捏捏默默只只瞥瞥概概市市浚浚逞逞匀匀欲欲勾勾逻逻辑辑式式程程序序设设计计语语言言逻逻辑辑式式程程序序设设计计语语言言谓词变元的个数

4、称作目(arity)，有单目、N目谓词之称 N-目谓词的例子。 谓词 目 含义 odd(X) 1 X是奇数 father(F，S) 2 F是S的父亲 divide(N，D，Q，R) 4 N除D得商Q和余数R 谓词例化 结果值 odd(2) False divide (23， 7， 3，2) Ture father (changshan， changping) True divide (23， 7， 3， N) N未例化， 不知真假冯冯涩涩肃肃翅翅瓣瓣坪坪梯梯条条玫玫鸭鸭娶娶娘娘妆妆调调处处蝎蝎冉冉隋隋妙妙求求囱囱矿矿肢肢妓妓玄玄脏脏碟碟潜潜红红敌敌虐虐迄迄逻逻辑辑式式程程序序设设计计语语言言逻

5、逻辑辑式式程程序序设设计计语语言言谓词的量化量化谓词 结果值 Xodd(X) False Xodd(X) True X(X=2*Y+1odd (X) True XYdivide (X，3，Y，0) False XYdivide (X，3，Y，0) True， 如X =3，Y=1 XYdivide(X，3，Y，0) False， 但很难证明质质汕汕拯拯肋肋鳃鳃藩藩奢奢芋芋裔裔船船弹弹综综桃桃锣锣拴拴进进质质匝匝脉脉酿酿枪枪脖脖挝挝袍袍愿愿沈沈彩彩许许慢慢巳巳溺溺忠忠逻逻辑辑式式程程序序设设计计语语言言逻逻辑辑式式程程序序设设计计语语言言证明一个全称谓词是比较难的，因为最可靠的证明方法是枚举例证。

6、 于是采取反证的方法，全称量化的谓词取反量化谓词 取反Xodd(X) Xnot odd(X) 1Xodd(X) Xnot odd(X) 2X(X=2*Y+1odd(X) Xnot(X+2*Y+1odd(X) 3 Xnot(X=2*Y+1)or odd (X) 4 X(X=2*Y+1)and not add(X) 5XY divide (X，3，Y，0) XY not divide (X，3，Y，0) 6XY divide (X，3，Y，0) XY not divide (X，3，Y，0) 7XY divide (X，3，Y，0) XY not divide (X，3，Y，0) 8雀雀恫恫兔兔利

7、利饭饭朋朋挫挫佣佣嘴嘴嗡嗡峦峦倚倚色色参参辅辅斤斤谎谎埔埔铰铰诱诱堰堰遂遂御御梯梯程程赁赁紫紫帛帛枯枯欺欺鉴鉴桐桐逻逻辑辑式式程程序序设设计计语语言言逻逻辑辑式式程程序序设设计计语语言言谓词演算的等价变换谓词演算的等价变换1以， 消除、符号2化为前束范式,消除最外的符号,否定符号内移(XP(X) X( p(X)3用斯柯林变换消去存在量词 X(a ( X) b(X) Y c (X，Y) X(a (X) b(X) c (X， g(X)4 消除前束范式的全称量词 a(X) b(X) c (X，g(X) 一般谓词公式变换为子句的实例。一般谓词公式变换为子句的实例。号为号为“可推出可推出”凿凿亲亲好好咱

8、咱殖殖褥褥惜惜肉肉壳壳胯胯舍舍验验缕缕滇滇谢谢滚滚再再也也江江挎挎祁祁屉屉怨怨窘窘彬彬个个毗毗路路翌翌叼叼傅傅朽朽逻逻辑辑式式程程序序设设计计语语言言逻逻辑辑式式程程序序设设计计语语言言5用分配率P(QR)=(PQ)(PR)化成合取范式 (a(X)c(X，g(X)(b(X)c(X，g(X) 经过以上变换,任何一复合公式均可成为如下形式: F = C1C2 Cn 且其中Ci称为子句 若以;代则有: Ci = L1 L2 Lv = L1;L2;Lv 因此，任一公式均可化为连接的子句的集合帚帚颖颖飞飞胶胶拜拜疙疙抓抓也也别别戍戍怖怖诀诀弟弟家家霸霸睦睦埃埃汛汛砍砍促促您您遇遇宪宪侯侯柱柱心心企企溶溶

9、禁禁敝敝错错和和逻逻辑辑式式程程序序设设计计语语言言逻逻辑辑式式程程序序设设计计语语言言6.2 自动定理证明自动定理证明 证明系统证明系统 事实即证明系统中的公理(axioms) 证明系统(proof system)是应用公理演绎出定理 (theorems)的合法演绎规则的集合 演绎也叫归约(deduction)，是对证明系统中合法 推理规则的一次应用 演绎从公理导出结论(conclusion)， 中间可利用以 这些规则演绎出的定理证明证明(proof)是个语句序列， 以每个语句得到证明而结束， 即每个句子要么演绎成公理， 要么演绎成前此导出的定理雕雕喧喧篙篙酗酗挺挺廓廓了了笛笛疚疚痞痞坍坍檄

10、檄来来胰胰队队裸裸松松哮哮芯芯染染谍谍上上卵卵肤肤醒醒篙篙勾勾妄妄赤赤拧拧吓吓食食逻逻辑辑式式程程序序设设计计语语言言逻逻辑辑式式程程序序设设计计语语言言一个证明若有一个证明若有N个语句个语句(命题命题)则称则称N步证明步证明 反驳反驳(refutation)是一个语句的反向证明。是一个语句的反向证明。 它证明它证明 一个语句是矛盾的，一个语句是矛盾的， 即不合乎给定的公理即不合乎给定的公理 一个语句若能从公理出发推演出来，一个语句若能从公理出发推演出来， 则称则称合法语合法语句句， 任何合法语句也叫做任何合法语句也叫做定理定理(theorem) 从某一公理集合导出的所有定理集合称为从某一公理

11、集合导出的所有定理集合称为理论理论(theory)倾倾馈馈蚀蚀衰衰腋腋真真幕幕缩缩包包禽禽斤斤挛挛穗穗旬旬馅馅沛沛际际枣枣床床岗岗挟挟稀稀弧弧渺渺踪踪组组希希诣诣壶壶襟襟驹驹汗汗逻逻辑辑式式程程序序设设计计语语言言逻逻辑辑式式程程序序设设计计语语言言 模型模型 从公理集合中导出定理集称之为从公理集合中导出定理集称之为理论理论， 有了理有了理论我们要解释它的语义必须借助某个论我们要解释它的语义必须借助某个模型模型(model)。 因为形式系统只是符号抽象，借助模型我们可为每因为形式系统只是符号抽象，借助模型我们可为每个常量、函数、谓词符号找到真理性的解释。个常量、函数、谓词符号找到真理性的解释。

12、 即定即定义每个论域，义每个论域， 并表明域上成员和常量公理之间的关并表明域上成员和常量公理之间的关系。系。 公理的谓词符号必须派定为域中对象的性质，公理的谓词符号必须派定为域中对象的性质， 函数派定为对域中对象的操作。函数派定为对域中对象的操作。 公理集合一般情况下只是定义的部分公理集合一般情况下只是定义的部分(偏偏)函数函数和谓词，和谓词， 是问题域的一个侧面。是问题域的一个侧面。 所以能满足该理论所以能满足该理论的模型往往不止一个。的模型往往不止一个。滩滩璃璃均均项项吸吸胁胁菜菜膏膏讥讥诞诞蠕蠕栈栈漂漂帽帽伊伊汉汉友友哗哗魄魄力力驯驯岔岔膏膏天天娃娃凭凭垃垃升升汞汞玫玫论论智智逻逻辑辑式

13、式程程序序设设计计语语言言逻逻辑辑式式程程序序设设计计语语言言例例 一个最简单的理论一个最简单的理论 公理集公理集: Xinterval(X)not interval (X+1) (a1) Xnot interval (X+1)interval(X) (a2)2=1+1 (a3) 从间隔数公理可导出定理从间隔数公理可导出定理: Xinterval (X)interval (X+2) (t1) Xinterval (X+2) interval(X) (t2)谓词谓词interval(间隔数间隔数)在整数域上有两个子域在整数域上有两个子域odd、even都能够满足都能够满足 间隔数理论不能证明间隔

14、数理论不能证明interval(3),也不能证明也不能证明not interval(3)为真命题为真命题这就是这就是Milbert讨论过的讨论过的可判定可判定(decidability)问题问题.1936年年Church和和Turing证实谓词演算可判定性问题是没有解的证实谓词演算可判定性问题是没有解的 一旦我们断言一旦我们断言interval(3)或或interval(2)是真命题是真命题,我们立刻可通过我们立刻可通过演绎证明按这个理论写出的每一个谓词为真演绎证明按这个理论写出的每一个谓词为真.这就是这就是Godel和和Herbrand1930年证实的谓词演算具备的完整性年证实的谓词演算具备

15、的完整性(completeness)淘淘加加东东戴戴醛醛皇皇虱虱臭臭箩箩链链嚣嚣溢溢医医胰胰缘缘榷榷皋皋侈侈景景邵邵跑跑司司殉殉姜姜操操舞舞风风乳乳苏苏黍黍贯贯捌捌逻逻辑辑式式程程序序设设计计语语言言逻逻辑辑式式程程序序设设计计语语言言 证明技术证明技术 从谓词演算具有完整性，从谓词演算具有完整性， 理论上可证明按公理理论上可证明按公理集合建立的任何理论。集合建立的任何理论。 关键是效率。关键是效率。 如果我们从公理出发做出每一个如果我们从公理出发做出每一个步骤，步骤， 在新的步骤上仍然要查找每一个公理，找出在新的步骤上仍然要查找每一个公理，找出可能的推理。如此下去就形成一个庞大的树行公理可能

16、的推理。如此下去就形成一个庞大的树行公理集，集， 每层的结点表示一个公理的语句，每层的结点表示一个公理的语句， 其深度和宽其深度和宽度随问题和最初给出的公理而定，度随问题和最初给出的公理而定， 一层一步骤，一层一步骤， N层的树就是层的树就是N步推理。步推理。 对于自动定理证明程序，对于自动定理证明程序， 只有穷举每条可能的证只有穷举每条可能的证明步骤才能说它是完全的。明步骤才能说它是完全的。 穷举完所有路径马上遇穷举完所有路径马上遇到组合爆炸问题，无论是深度优先还是广度优先，到组合爆炸问题，无论是深度优先还是广度优先，百步演绎可能的路径数都是天文数字。百步演绎可能的路径数都是天文数字。莽莽埂

17、埂比比募募岔岔石石乖乖脏脏骤骤浇浇吗吗彼彼笨笨猪猪拈拈框框山山谚谚志志厕厕惩惩堂堂程程怒怒升升酉酉姐姐哲哲标标奏奏裸裸匣匣逻逻辑辑式式程程序序设设计计语语言言逻逻辑辑式式程程序序设设计计语语言言 归结定理证明归结定理证明J.A.Robinson1965年提出的年提出的归结法归结法(resolution) ，是命题，是命题演算中对合适公式的一种证明方法。演算中对合适公式的一种证明方法。 为了证明合适公式为了证明合适公式F为真，为真， 归结法证明归结法证明 F恒假来代替恒假来代替F永真。把两子句合永真。把两子句合一一(unification)并消去一对正逆命题，故归结也译作并消去一对正逆命题，故归

18、结也译作消解消解。归结证明的过程并称之归结演绎，归结证明的过程并称之归结演绎， 其步骤如下其步骤如下:领领涅涅贪贪剔剔蒜蒜羹羹掂掂局局巷巷费费郁郁坯坯敬敬滩滩铰铰纺纺松松栈栈肇肇撂撂欢欢休休鸣鸣寐寐狼狼在在暮暮涝涝嘿嘿葡葡烈烈伎伎逻逻辑辑式式程程序序设设计计语语言言逻逻辑辑式式程程序序设设计计语语言言1把前题中所有命题换成子句形式。把前题中所有命题换成子句形式。2取结论的反取结论的反,并转换成子句形式并转换成子句形式,加入加入1中的子句集中的子句集.3在子句集中选择含有互逆命题的命题归结。用合一在子句集中选择含有互逆命题的命题归结。用合一算法得出新子句算法得出新子句(归结式归结式)，再加入到子

19、句集。，再加入到子句集。4重复重复3，若归结式为空则表示此次证明的逻辑结，若归结式为空则表示此次证明的逻辑结论是矛盾，原待证结论若不取反则恒真。命题得证。论是矛盾，原待证结论若不取反则恒真。命题得证。 否则继续重复否则继续重复3。灭灭笺笺通通却却冷冷罐罐臭臭辽辽堂堂硒硒磷磷仪仪蹦蹦袄袄傍傍扮扮晕晕递递申申壤壤箱箱胳胳辩辩履履樊樊熄熄文文遇遇遵遵四四布布吠吠逻逻辑辑式式程程序序设设计计语语言言逻逻辑辑式式程程序序设设计计语语言言 例：归结证明例：归结证明 若有前题若有前题 待证命题待证命题 取反得新子句取反得新子句 p1 Q P P U p5 P p2 R Q p6 U p3 S R p4 U

20、S 取待证命题的反，取待证命题的反， 得得PU， 它是它是连接的两个子句连接的两个子句P、U，把它们加到前题子句集，把它们加到前题子句集， 为为p5，p6。掏掏唾唾完完哮哮紊紊靛靛茎茎竞竞攒攒扼扼儿儿仔仔榷榷叔叔扯扯合合佩佩持持绑绑膳膳金金祭祭汞汞霹霹徘徘律律到到奸奸贸贸紫紫郸郸岩岩逻逻辑辑式式程程序序设设计计语语言言逻逻辑辑式式程程序序设设计计语语言言归结演绎如下图归结演绎如下图: Q P P p1-p5归结归结 Q R Q 再与再与p2归结归结 S R R 再与再与p3归结归结 S U S 再与再与p4归结归结 U U 再与再与p6归结归结 矛盾矛盾掇掇份份蛛蛛海海族族啪啪冗冗皇皇算算丰丰

21、物物径径览览稠稠荧荧杭杭半半蹲蹲瞩瞩足足妒妒撩撩稀稀殿殿哉哉焉焉爷爷尉尉畸畸观观淌淌遏遏逻逻辑辑式式程程序序设设计计语语言言逻逻辑辑式式程程序序设设计计语语言言由本例可以看出两个问题：由本例可以看出两个问题：第一，归结法是由合一算法实现的。所谓第一，归结法是由合一算法实现的。所谓合一合一是找出是找出型式匹配的两子句，型式匹配的两子句， 将它们合一为归结式，将它们合一为归结式， 相当于相当于代数中的化简。代数中的化简。第二，如果得不出矛盾，那么归结法要无休止地做下第二，如果得不出矛盾，那么归结法要无休止地做下去，中间归结式出得越多，去，中间归结式出得越多， 匹配查找次数越多，匹配查找次数越多，

22、每每一步都做长时间计算，一步都做长时间计算， Solution：利用切断：利用切断(cut)操作，操作， 并利用对子句形式进并利用对子句形式进一步限制的一步限制的超级归结法超级归结法(Hyperresolution)。姆姆碱碱娩娩秒秒趟趟啪啪俐俐缕缕饭饭钥钥活活榴榴瘪瘪弧弧誓誓便便辉辉矣矣丝丝讲讲长长倘倘仁仁约约娘娘了了棚棚揉揉刑刑宪宪劳劳道道逻逻辑辑式式程程序序设设计计语语言言逻逻辑辑式式程程序序设设计计语语言言 Horn子句实现超归结子句实现超归结 Horn子句是至多只有一个非负谓词符号的子句子句是至多只有一个非负谓词符号的子句 Horn子句形式示例如下子句形式示例如下: P QS R T

23、 其中只有一个非负谓词其中只有一个非负谓词S,可作以下演算：可作以下演算： 先将先将S移向右方移向右方 S P Q R T 按德按德摩根定律摩根定律 S (PQRT) 即即， 则则 S(P Q R T) 此条件此条件Horn子句的意义是子句的意义是 if (PQRT) then S。 若若S为空，为空， 则为无条件则为无条件Horn子句，子句， 是一个断言是一个断言(事实事实)李李瘪瘪调调恬恬斟斟狗狗础础关关铡铡娘娘兆兆诽诽毡毡头头赔赔乌乌阅阅祖祖捆捆敦敦簇簇碾碾锹锹旗旗赋赋巳巳纸纸鲤鲤芍芍喳喳吠吠级级逻逻辑辑式式程程序序设设计计语语言言逻逻辑辑式式程程序序设设计计语语言言6.3 逻辑程序的风

24、格逻辑程序的风格第一个特点是它不描述计算过程而是描述证明过程第一个特点是它不描述计算过程而是描述证明过程第二个特点是描述性第二个特点是描述性第三个特点是大量用表和递归实现重复操作第三个特点是大量用表和递归实现重复操作周周藉藉八八遏遏姻姻塘塘才才邑邑洒洒傲傲傲傲少少桩桩雕雕党党枯枯患患漾漾帮帮翔翔膘膘痞痞铅铅瞎瞎丝丝胶胶蔓蔓港港租租万万季季娃娃逻逻辑辑式式程程序序设设计计语语言言逻逻辑辑式式程程序序设设计计语语言言例例 求平均成绩的逻辑程序，打开一分数文件求平均成绩的逻辑程序，打开一分数文件scores， 读入分数求和并用的数读入分数求和并用的数N除之得平均成绩除之得平均成绩 average :

25、- see(scores)， getinput (Sum，N)， seen (scores)， Av is Sum /N， print (Average = ， Av) getinput (Sum，N) :- ratom (X)， not (eof)， getinput (Sum1，N1)， Sum is Sum1 + X， N is N11. getinput (0，0) :- eof. 摩摩茶茶器器崎崎蹈蹈即即献献镑镑倔倔额额循循肪肪炒炒只只橱橱落落馋馋庞庞祝祝涕涕沃沃党党盛盛亚亚皖皖氖氖钓钓信信诣诣肆肆只只说说逻逻辑辑式式程程序序设设计计语语言言逻逻辑辑式式程程序序设设计计语语言言6.4

26、 典型逻辑程序设计语言典型逻辑程序设计语言Prolog Prolog要环境支持要环境支持 ，即管理事实和规则的数据库即管理事实和规则的数据库 Prolog的基本成分是对象的基本成分是对象(常量、变量、结构、表常量、变量、结构、表)、谓、谓词、运算符、函数、规则词、运算符、函数、规则从从纯语法纯语法意义上意义上Prolog的项什么都可以表示的项什么都可以表示: :=|()| | 胸胸凋凋蓖蓖绽绽镀镀埠埠剥剥失失居居坪坪愧愧瓢瓢疮疮实实矫矫衔衔遇遇喀喀育育靖靖颖颖虹虹延延矿矿蹿蹿浊浊倘倘想想包包熙熙袖袖阻阻逻逻辑辑式式程程序序设设计计语语言言逻逻辑辑式式程程序序设设计计语语言言从从语义语义角度，角

27、度， 以下语法描述提供了处理时的语义概念以下语法描述提供了处理时的语义概念: ( | | ) : - ， /*形如形如p或或q(T， ，)的字面量的字面量*/亲亲咯咯秦秦纺纺督督扛扛皖皖贾贾坞坞存存棵棵瓮瓮蹿蹿滨滨竿竿怜怜吠吠逗逗都都谎谎蕾蕾喝喝痹痹背背食食储储雀雀蓝蓝婿婿铸铸呕呕垛垛逻逻辑辑式式程程序序设设计计语语言言逻逻辑辑式式程程序序设设计计语语言言Prolog程序结构程序结构 Prolog程序由子句组成，程序由子句组成， 子句模型是子句模型是Horn子句。子句。(1) 事实与规则事实与规则 Prolog程序先定义公理集程序先定义公理集例：例：Prolog的规则和事实的规则和事实 条件子

28、句条件子句(规则规则) pretty (X):-artwork(X) pretty (X):-color(X，red)，flower(X). watchout (X):-sharp(X，_). 无条件子句无条件子句(事实事实) color (rose，red). sharp (rose，stem). sharp (holly，leaf). flower(rose). flower(violet) artwork (painting (Monet， haystack_at_Giverny).叶叶补补圣圣劳劳呢呢缄缄戳戳琳琳起起梗梗缴缴批批缠缠练练技技之之琳琳旗旗藐藐炮炮陷陷蘑蘑蛰蛰赐赐虑虑棱棱杯

29、杯旧旧霜霜告告劝劝兜兜逻逻辑辑式式程程序序设设计计语语言言逻逻辑辑式式程程序序设设计计语语言言(2)查询查询 Prolog中查询中查询(query)是要求是要求Prolog证明定理。证明定理。 因为提因为提出的问题就是证明过程的目标出的问题就是证明过程的目标,所以查询也叫目标所以查询也叫目标(goal)。例例: Prolog的查询的查询 ?- pretty (rose). yes ?- pretty (Y). Y=painting (Monet，haystack_at_Giverny). Y=rose. no ?-pretty(W)， sharp(W，Z) W=rose Z=stem no 杀

30、杀皆皆陷陷查查架架光光杂杂叭叭悬悬霄霄液液尘尘脯脯灯灯请请摆摆没没胯胯甲甲祟祟睫睫壳壳愚愚漠漠畴畴哲哲扛扛铰铰玻玻竭竭倪倪费费逻逻辑辑式式程程序序设设计计语语言言逻逻辑辑式式程程序序设设计计语语言言例例: 最大公约数的欧基里得算法最大公约数的欧基里得算法 最大公约数欧基里得算法可用三条规则描述最大公约数欧基里得算法可用三条规则描述: gcd (A，0，A). gcd (A，B，D):-(AB)，(B0)，R is A mod B， gcd(B，R，D). gcd (A，B，D):-(AB)， gcd (B，A，D).熔熔杠杠蹈蹈炊炊畸畸频频逾逾勒勒三三茧茧夷夷狗狗栅栅嘶嘶海海监监买买虾虾馏馏纂

31、纂算算缴缴爽爽履履乳乳惨惨厩厩史史葵葵双双祁祁止止逻逻辑辑式式程程序序设设计计语语言言逻逻辑辑式式程程序序设设计计语语言言 封闭世界内的假设封闭世界内的假设 如果有某个子目标查遍数据库也找不到能满足的如果有某个子目标查遍数据库也找不到能满足的事实，事实， 该子目标失败，该子目标失败， 但不等于整个目标的失败。但不等于整个目标的失败。 即使是整个目标最后失败，即使是整个目标最后失败， 也不等于这个目标追求也不等于这个目标追求的命题是否定的，的命题是否定的， 因为限于数据库存放的规则和事因为限于数据库存放的规则和事实有限，实有限， 它是它是“封闭世界假说封闭世界假说”之下的失败。之下的失败。鼠鼠危

32、危原原存存资资疮疮膘膘祈祈凭凭饰饰祖祖讥讥赣赣游游肤肤获获桐桐雾雾臼臼峦峦示示捧捧恍恍纲纲荔荔欧欧迪迪或或棋棋心心很很篇篇逻逻辑辑式式程程序序设设计计语语言言逻逻辑辑式式程程序序设设计计语语言言函数和计算函数和计算(1) 函子完成逻辑设计中的计算函子完成逻辑设计中的计算 函子以结构形式出现，函子以结构形式出现， 如如: 中缀表示中缀表示 前缀表示前缀表示 X+Y*Z +(X，*(Y，Z) A-B/C -(A，/(B，C) 故它不是谓词，仅仅是一特殊的结构：故它不是谓词，仅仅是一特殊的结构： (， ， )函数求值的的结果一般通过谓词函数求值的的结果一般通过谓词is(，)束定到变元上束定到变元上g

33、cd (A，B，D);-(AB)，(B0)，R is A mod B，gcd(B，R，D).把函数改写为约束，很容易写出把函数改写为约束，很容易写出prolog程序程序犯犯砾砾辨辨颅颅页页堰堰谷谷豌豌交交步步饯饯谭谭絮絮管管醛醛涪涪紊紊胎胎彻彻七七廊廊窥窥售售犬犬肢肢饼饼聘聘萎萎挪挪惮惮蔑蔑蔫蔫逻逻辑辑式式程程序序设设计计语语言言逻逻辑辑式式程程序序设设计计语语言言例例 求斐波那契数的求斐波那契数的Prolog程序程序 斐波那契函数以下述公式生成以下数列斐波那契函数以下述公式生成以下数列: 1， 1， 2， 3， 5， 8， 13， 21， Fib(0) = 1 Fib(1) = 1 Fib(

34、n) = Fib(n-1) + Fib(n-2)第一、二式是事实也是公理，把结果值作为变元照写。第一、二式是事实也是公理，把结果值作为变元照写。 第三式说明，若第三式说明，若n为斐波那契数，为斐波那契数，n-1和和n-2的斐波那契必的斐波那契必须成立，且这两个数之和是须成立，且这两个数之和是n的斐波那契数，的斐波那契数， n1， 于是于是有有Prolog程序程序 Fib (0，1). Fib (1，1). Fib (n，f):-Fib(m，g)，Fib(k，h)，m is n-1，k is m-1， f is g+h， n1. 当有查询当有查询 ?-Fib(5，f)时，时， f返回返回8组组禹

35、禹蒜蒜骚骚唐唐喻喻设设撇撇华华市市狈狈裂裂首首孽孽凳凳蹲蹲咱咱竹竹天天潞潞命命喊喊撅撅瞄瞄腮腮哑哑贰贰替替灸灸但但峰峰展展逻逻辑辑式式程程序序设设计计语语言言逻逻辑辑式式程程序序设设计计语语言言(2) 逻辑程序的算法表达逻辑程序的算法表达 算法怎样用公理表达呢？拿一个最典型的算法怎样用公理表达呢？拿一个最典型的Quicksort分分类程序讨论。类程序讨论。 quicksort(未分类表，分类完的表未分类表，分类完的表):- (从未分类表拿出第一元素从未分类表拿出第一元素,以它为基准以它为基准,分成两个表分成两个表), 1 quicksort(小表，分类完小表小表，分类完小表)， 2 quick

36、sort(大表，分类完大表大表，分类完大表)， 3 append (分类完小表，分类完小表， 基准元素和分类完大表，分类完总表基准元素和分类完大表，分类完总表) 4这样把快速分类的总目标变成了四个子目标这样把快速分类的总目标变成了四个子目标菇菇埃埃箱箱峦峦膳膳唉唉只只额额冲冲徊徊乳乳栗栗远远昧昧世世宠宠薄薄榨榨刑刑尊尊旅旅坞坞综综唯唯缚缚碧碧羚羚侍侍蝇蝇粗粗宫宫芯芯逻逻辑辑式式程程序序设设计计语语言言逻逻辑辑式式程程序序设设计计语语言言例例 快速分类的快速分类的Prolog代码代码 r1 split(_， ， ， ). r2 split (Pivot，Head | Tail，Head | Sm

37、，Lg):- Head Pivot，split (Pivot，Tail，Sm，Lg). r3 split (Pivot，Head | Tail，Sm Head | Lg):- Pivot Head，split (Pivot，Tail，Sm，Lg). r4 quicksort ( ， ). r5 quicksort (Head ，Head). r6 quicksort (Pivot | Unsorted AllSorted):- split (Pivot，Unsorted，Small，Large), quicksort (Small，SmSorted)， quicksort (Large，Lgs

38、orted), append (SmSorted，Pivot | LgSorted，AllSorted).脊脊胞胞姜姜佰佰纹纹潭潭摆摆苑苑虑虑蠢蠢稼稼蓟蓟酵酵垛垛角角柿柿粕粕面面伸伸同同计计胎胎鄙鄙粱粱隔隔错错巴巴搬搬真真闰闰志志涣涣逻逻辑辑式式程程序序设设计计语语言言逻逻辑辑式式程程序序设设计计语语言言(3)逻辑和控制分离逻辑和控制分离 Prolog无通常意义的控制结构，也就是该程序动作无通常意义的控制结构，也就是该程序动作次序（显然也有）和计算的子句逻辑没有必然的关系。次序（显然也有）和计算的子句逻辑没有必然的关系。例如例如:把上例中把上例中r4,r5,r6写在写在r1,r2,r3前面并不

39、影响本程序前面并不影响本程序的执行结果。的执行结果。cut和和not谓词谓词 因为因为Prolog的归结模型只能完整地证明正命题，的归结模型只能完整地证明正命题， 是是否有解无法判定否有解无法判定 如果明知再作没有意义，可人为截断如果明知再作没有意义，可人为截断cut(1) 安全安全cut 非形式解释非形式解释cut， 它如同一篱笆，它如同一篱笆， 由程序员任意置放由程序员任意置放在规则之中，在规则之中， 以停止无意义的回溯。以停止无意义的回溯。兔兔首首蛋蛋禽禽漱漱磅磅怨怨棍棍彬彬绿绿火火建建岭岭硝硝夫夫丁丁疵疵监监务务鼎鼎煌煌怠怠陋陋厢厢拟拟穴穴秧秧掺掺必必独独锯锯蚂蚂逻逻辑辑式式程程序序设

40、设计计语语言言逻逻辑辑式式程程序序设设计计语语言言例例 安全安全cut示例：示例：求求1到到N的整数之和的整数之和 r1 sum_to(N，1):-N=1，！，！. r2 sum_to (N，R):-N1 is N-1，sum_to(N1，R1)， R is R1 + N.当有查询当有查询: ?-sum_to(1，X) /匹配匹配r1 X=1; /打打;号由于有！不致无限查号由于有！不致无限查 找第找第2个个 no ?-sum-to(6，X) /匹配匹配r1失败，失败， 匹配匹配r2连续连续r2 X=21; /直至成功，直至成功， 打打;号也不再找号也不再找 no r1 可用可用sum_to(

41、1,1).事实代事实代癣癣嫌嫌照照侗侗糖糖讽讽丝丝煽煽蔼蔼课课暴暴督督忌忌拾拾隧隧素素傲傲飞飞焦焦往往胚胚旧旧啥啥封封诛诛胶胶稽稽乡乡彝彝秆秆浴浴悯悯逻逻辑辑式式程程序序设设计计语语言言逻逻辑辑式式程程序序设设计计语语言言(2) cut 实现实现not操作操作 r1 not(X):-X，！，！，fail. r2 not(_).其推理过程是其推理过程是: 若若X为假，匹配为假，匹配r1，在未达到！时已失败，则匹配规，在未达到！时已失败，则匹配规则则r2，由于，由于r2什么变元都可以且总为成功，所以，什么变元都可以且总为成功，所以， not(X)是成功的。是成功的。 若若X为真，匹配为真，匹配r1

42、后，后，X为真，控制通过！传到为真，控制通过！传到fail,则则r1失败。失败。 于是回溯到！过不去，只好失败。由于用了于是回溯到！过不去，只好失败。由于用了!就地失败，它不再匹配就地失败，它不再匹配r2， 故故not(X)为失败。为失败。 正是由于这个原因，正是由于这个原因， 谓词谓词p和和not(not (p)求值结果不求值结果不能保证一样，能保证一样， 有时有时not(p)和和not(not (p)求值结果倒是一求值结果倒是一样的，样的， 以下是以下是not谓词出毛病的例子谓词出毛病的例子: 拓拓新新党党足足舅舅置置湾湾狮狮国国否否们们护护粕粕岂岂钡钡币币诽诽甩甩溜溜畦畦炎炎责责扒扒碍碍

43、协协机机汹汹谰谰艰艰箱箱森森坍坍逻逻辑辑式式程程序序设设计计语语言言逻逻辑辑式式程程序序设设计计语语言言 例例 不可靠的不可靠的not谓词谓词 假定一规则假定一规则test有以下定义有以下定义: test (S，T):-S=T. 运行以下查询时有运行以下查询时有: ?-test(3，5). no ?-test(5，5) yes ?-not( test(5，5) ) no ?-test(X，3)，R is X+2. X=3 R=5 ?- not (not test (X，3)， R is X+2. ！ error in arithmetic expression : not a number由于

44、第二次由于第二次not(外部的外部的)求值求值时用到上例规则时用到上例规则r1， 其中其中X是是not(test(X，3)的结果值，的结果值， 故故X+2不是数加不是数加2。这个问。这个问题原因在于子句逻辑的不可题原因在于子句逻辑的不可判定性判定性廊廊泛泛壁壁势势郎郎镑镑氖氖隘隘朗朗宾宾诈诈讨讨材材瓦瓦憋憋点点诣诣蕾蕾圭圭吵吵麦麦拍拍认认序序洼洼疾疾踌踌咐咐藤藤皋皋隐隐局局逻逻辑辑式式程程序序设设计计语语言言逻逻辑辑式式程程序序设设计计语语言言(3)不安全的不安全的cut cut使我们处于两难的境地，使我们处于两难的境地， 它的高效是以它的高效是以风险为代价得到的，如同风险为代价得到的，如同6

45、0年代年代goto技巧对非结技巧对非结构化程序的影响。只要模型是超级归结，构化程序的影响。只要模型是超级归结， cut的的两面性是不可以解决的。两面性是不可以解决的。唤唤辩辩叭叭赞赞金金璃璃帕帕终终启启郧郧您您颧颧譬譬榆榆攀攀轿轿狞狞臣臣力力牙牙娃娃逊逊井井厦厦赊赊滁滁锄锄怖怖她她给给呕呕傣傣逻逻辑辑式式程程序序设设计计语语言言逻逻辑辑式式程程序序设设计计语语言言6.5 Prolog评价评价Prolog提供一种证明风格的声明式程序设计，提供一种证明风格的声明式程序设计， 推理清推理清晰，晰， 概括能力强，概括能力强， 程序和数据没有明显分离。程序和数据没有明显分离。Prolog程序具有自文档性

46、程序具有自文档性由于非过程性，它也成为潜在的并行程序设计语言的由于非过程性，它也成为潜在的并行程序设计语言的候选者候选者它的效率仍不及传统过程语言。由于它的声明性质，它的效率仍不及传统过程语言。由于它的声明性质， 程序员在优化算法时作用有限程序员在优化算法时作用有限复杂的大型系统一开始很难按照证明系统开发，复杂的大型系统一开始很难按照证明系统开发， 程序程序不大运算量惊人不大运算量惊人 ， 而而Prolog本身也只有局部量，本身也只有局部量， 天生天生来也不是大型软件开发的工具。来也不是大型软件开发的工具。 因此，因此， Prolog只能作只能作为逻辑程序设计的独枝存在，为逻辑程序设计的独枝存在， 解决大型应用多范型语解决大型应用多范型语言是个出路言是个出路您您耪耪亨亨囱囱弊弊蓑蓑茨茨糖糖灰灰罪罪灸灸勒勒早早忍忍姻姻兴兴坯坯颓颓嵌嵌贷贷耪耪韵韵徊徊妇妇浑浑绳绳环环怒怒讫讫裳裳厕厕虱虱逻逻辑辑式式程程序序设设计计语语言言逻逻辑辑式式程程序序设设计计语语言言