第9章逻辑程序设计课件

内容1.逻辑和逻辑程序2.Horn子句3.归结与合一4.Prolog语言1内容1.逻辑和逻辑程序11.逻辑和逻辑程序逻辑程序设计逻辑程序设计支持说明性程序设计范型根据问题的高层描述来构建程序告诉计算机“什么是真的”和“需要做什么”，而不是“怎样做”。程序员把精力放在问题（封闭的问题世界）的描述上，而不是写一些诸如“下一步做什么”之类的底层算法指令。21.逻辑和逻辑程序逻辑程序设计21.逻辑和逻辑程序谓词演算逻辑程序设计中使用的逻辑【例】用谓词表示的逻辑命题0是自然数2是自然数对于所有的x，如果x是自然数，则x+1也是自然数-1是自然数natural(0)natural(2)natural(-1)forallx,natural(x)natural(successor(x))二值逻辑31.逻辑和逻辑程序谓词演算natural(0)natural1.逻辑和逻辑程序谓词演算谓词演算元素①常量：数或名称②谓词：值域为真或假的函数名③函数：区别谓词的其余函数④变量：不确定值⑤连接词：⑥量词：描述变量⑦标点符号：(),;a为真时b为真ab存在量词全称量词natural(0)forallx,natural(x)natural(successor(x))41.逻辑和逻辑程序谓词演算a为真时b为真ab存在量词全称量词1.逻辑和逻辑程序谓词演算一阶谓词演算（first-orderpredicatecalculus）全称量化变量和存在量化变量仅可以指向论域中的对象，而不允许指向谓词和函数谓词和函数的参数是项常量变量函数51.逻辑和逻辑程序谓词演算51.逻辑和逻辑程序谓词演算推理规则【例】有如下三段论：“所有人会死；苏格拉底是人，所以苏格拉底会死。”

,abab61.逻辑和逻辑程序谓词演算,abab6【例】证明：Fido会死①Fido是狗②所有的狗都是动物③所有的动物都会死证明①所有的狗都是动物：②Fido是狗：③取式假言推理和{fido/X}：④所有的动物都会死：⑤取式假言推理和{fido/Y}：

谓词形式1.逻辑和逻辑程序7【例】证明：Fido会死谓词形式1.逻辑和逻辑程序71.逻辑和逻辑程序谓词演算推理规则为了应用推理规则进行推理，推理机必须能够判断两个表达式是否相同（匹配）。这种寻找项对变量的置换，使谓词一致的过程叫做合一的过程（合一算法）项：常量、函数或其他变量公式集F={man(X)，man(socrates)}中的两个公式是可合一的，置换θ=scorates/X是该公式集的一个合一。81.逻辑和逻辑程序谓词演算81.逻辑和逻辑程序谓词演算推理规则①化简式（与消除）：P∧Q=>P和P∧Q=>Q②附加式：P=>P∨Q和Q=>P∨Q③析取三段论：P，PVQ=>Q④取式假言推理：P，P→Q=>Q⑤拒式假言推理：Q，P→Q=>P⑥假言三段论：P→Q，Q→R=>P→R⑦二难推理：P∨Q，P→R，Q→R=>R⑧全称固化：（x）P（x）=>P（a）⑨存在固化：（x）P（x）=>P（a）91.逻辑和逻辑程序谓词演算91.逻辑和逻辑程序谓词演算推理规则自然演绎推理从一组已知为真的事实出发，直接运用经典逻辑中的推理规则推出结论的过程101.逻辑和逻辑程序谓词演算10内容1.逻辑和逻辑程序2.Horn子句3.归结与合一4.Prolog语言11内容1.逻辑和逻辑程序112.Horn子句Horn子句是形如的命题其中a只能是简单的不包含连接词的命题a的数量可以为零注意：Horn子句能够被用来表示大多数的逻辑命题，但不是全部没有or和量词所有的a为真则b真b恒真事实122.Horn子句Horn子句是形如没有or和量词所有的【例】证明：Fido会死①所有的狗都是动物②Fido是狗③所有的动物都会死谓词形式子句形式2.Horn子句隐式全称约束13【例】证明：Fido会死谓词形式子句形式2.Horn子句2.Horn子句目标驱动自动推理系统，反向使用Horn子句询问(目标语句)子句体子句头无头子句对b的定义142.Horn子句目标驱动子句体子句头无头子句对b的定义1内容1.逻辑和逻辑程序2.Horn子句3.归结与合一4.Prolog语言15内容1.逻辑和逻辑程序153.归结与合一归结(消解)两个Horn子句第一个Horn子句的头与第二个子句体的一个命题匹配则第二个子句中的命题可以被替换为第一个子句的体【例】bi匹配a163.归结与合一归结(消解)bi匹配a163.归结与合一归结过程(目标驱动)用已知子句的头部来匹配无头子句体中的一个目标如果成功，用已知子句的体替换被匹配的目标(归结)，建立新的子句继续用同样的方式修改目标系列这些新的目标被称为子目标如果成功消除了所有的目标，则初始命题得证询问173.归结与合一归结过程(目标驱动)询问173.归结与合一子句集“死狗”问题的归结证明□合一要匹配包含变量的语句必须令变量等于某项183.归结与合一子句集“死狗”问题的归结证明□合一要匹配包含3归结与合一必须解决的问题逻辑程序系统必须使用一个高效执行的算法，规定求解目标应用子句的顺序193归结与合一必须解决的问题193归结与合一203归结与合一20内容1.逻辑和逻辑程序2.Horn子句3.归结与合一4.Prolog语言21内容1.逻辑和逻辑程序21Prolog语言概述Prolog（ProgramminginLogic）诞生于20世纪70年代初法国马赛大学作为自然语言理解项目的一部分研制成功目前，爱丁堡大学开发的Prolog版本使用最为广泛主要应用于人工智能领域相关问题的求解易于表达人的逻辑思维迄今最能体现逻辑程序设计思想的逻辑编程语言“说明式”的语言；采用一阶谓词演算说明（描述）问题知识库（事实和规则）的描述采用子句（Clause）形式Prolog是目前唯一广泛使用的逻辑程序设计语言22Prolog语言概述Prolog（ProgrammingiProlog语言概述SWI-Prolog/安装文件（注意顺序安装）（1）SWI-PrologforMS-Windows（2）SWI-Prolog-Editorhttp://lakk.bildung.hessen.de/netzwerk/faecher/informatik/swiprolog/indexe.html

23Prolog语言概述SWI-Prolog23内容1.逻辑和逻辑程序2.Horn子句3.归结与合一4.Prolog语言4.1符号和数据结构4.2Prolog的执行4.3合一4.4Prolog的搜索策略4.5循环和控制结构24内容1.逻辑和逻辑程序244.1符号和数据结构基本符号常量以小写字母开始的一串字母、数字、下划线或用单引号界定的一串任何可打印的ASCII字符。变量以大写字母开始一串字母、数字和下划线；下划线（_）表示匿名变量；连接词，//and;//or:-//implementation254.1符号和数据结构基本符号254.1符号和数据结构基本数据结构结构（谓词/复杂项）

vertical(line(point(X,Y),point(X,Z))).264.1符号和数据结构基本数据结构264.1符号和数据结构基本数据结构表（List）：有限的元素序列。由方括号[]之间由逗号隔开的有序元素组成。表中的元素可以是原子、结构、或任何其它的项，包括表在内。274.1符号和数据结构基本数据结构274.1符号和数据结构基本数据结构表任何非空的表=表头（head）+表尾（tail）表头：表的第一个元素；表尾：除第一个元素，表的其它元素组成的表。Prolog内部谓词“|”用于将表分解为表头和表尾；灵活使用|是写好Prolog表处理程序的关键！284.1符号和数据结构基本数据结构284.1符号和数据结构基本数据结构表谓词“|”的使用294.1符号和数据结构基本数据结构29内容1.逻辑和逻辑程序2.Horn子句3.归结与合一4.Prolog语言4.1符号和数据结构4.2Prolog的执行4.3合一4.4Prolog的搜索策略4.5循环和控制结构30内容1.逻辑和逻辑程序304.2Prolog的执行Prolog程序运行通过提问查询知识库使用分号（；）查询多个解（multipleanswers）314.2Prolog的执行Prolog程序运行31内容1.逻辑和逻辑程序2.Horn子句3.归结与合一4.Prolog语言4.1符号和数据结构4.2Prolog的执行4.3合一4.4Prolog的搜索策略4.5循环和控制结构32内容1.逻辑和逻辑程序324.3合一合一对变量初始化或者分配存储空间和值的过程在某种意义上是将两个项等同的过程?-a=a.yes//常量与自己合一?-a=b.no//常量不能与其他常量合一?-foo(a,b)=foo(a,b).yes//结构递归合一Prolog中“=”表示合一334.3合一合一Prolog中“=”表示合一33合一?-X=a.X=a;//变量和常量合一no//仅此一次合一?-foo(a,b)=foo(X,b).X=a;//参数合一no//只有是一种可能?-A=B.A=_G206B=_G206;no内部共享变量4.3合一34合一内部共享变量4.3合一344.3合一合一算法①如果Term1和Term2是常量，那么当且仅当Term1和Term2是相同的原子或整数；②如果Term1是变量，Term2是任何类型的项，那么Term1实例化为Term2；注：如果Term2也是变量，互相实例化，共享值。③如果Term1和Term2都是结构，两者合一，当且仅当（a）两者有相同的算符（谓词）；（b）两者对应的参数匹配，即能够递归地合一；（c）变量实例化必须保持一致性；④当满足前面三种情况时，两者项合一。354.3合一合一算法354.3合一【思考】Prolog实现合一操作时是否使用标准的合一算法？

老版本的Prolog实现:Not

enough

memory

to

complete

query!现代版本的Prolog实现： X

=

father(father(father(father(father(father

(father(father(father(father(father(father

(father(father(father(father(father(father

(father(father(father(father(father(father(father(father(father(father(father(fatherX

=

father(father(father(father(...))))))))SICStusPrologSWIPrologX

=

father(**)364.3合一【思考】X

=

father(father(fa4.3合一利用合一简化操作cons表的构造与选择向后运行消解自动产生合一需要合一的模式写入子句头374.3合一利用合一简化操作向后运行消解自动产生合一需要合一4.3合一利用合一简化操作append拼接两张表ABYB+YWA输入:W:结果:+384.3合一利用合一简化操作ABYB+YWA输入:W:结果:4.3合一利用合一简化操作append394.3合一利用合一简化操作394.3合一利用合一简化操作append向后运行404.3合一利用合一简化操作向后运行404.3合一利用合一简化操作reverse逆置表中元素414.3合一利用合一简化操作41内容1.逻辑和逻辑程序2.Horn子句3.归结与合一4.Prolog语言4.1符号和数据结构4.2Prolog的执行4.3合一4.4Prolog的搜索策略4.5循环和控制结构42内容1.逻辑和逻辑程序424.4Prolog的搜索策略搜索策略搜索方向—基于目标导向搜索类型—深度优先搜索从左至右考虑子目标从上到下考虑子句合一失败，如何控制程序继续进行求解问题？回溯Prolog内部最基本的自动的控制流机制需要搜索更多解时，如何控制程序继续进行求解问题？分号表示结束当前合一，回溯查找其它可满足的解434.4Prolog的搜索策略搜索策略43回溯：系统地穿越状态空间的所有路径的一种技术4.4Prolog的搜索策略44回溯：系统地穿越状态空间的所有路径的一种技术4.4Prol4.4Prolog的搜索策略【例1】454.4Prolog的搜索策略【例1】454.4Prolog的搜索策略【例1】464.4Prolog的搜索策略【例1】464.4Prolog的搜索策略【例2】匹配失败474.4Prolog的搜索策略【例2】匹配失败474.4Prolog的搜索策略【例2】484.4Prolog的搜索策略【例2】48【例3】4.4Prolog的搜索策略49【例3】4.4Prolog的搜索策略49【例3】4.4Prolog的搜索策略'DRNO‘/Title50【例3】4.4Prolog的搜索策略'DRNO‘/Tit【例3】4.4Prolog的搜索策略'DRNO‘/Title匹配失败51【例3】4.4Prolog的搜索策略'DRNO‘/Tit【例3】4.4Prolog的搜索策略'DRNO‘/Title310/Length52【例3】4.4Prolog的搜索策略'DRNO‘/Tit【例3】4.4Prolog的搜索策略'DRNO‘/Title310/Length53【例3】4.4Prolog的搜索策略'DRNO‘/Tit4.4Prolog的搜索策略【例4】C=X=_G206seattle/_G206失败并回溯544.4Prolog的搜索策略【例4】C=X=_G206se4.4Prolog的搜索策略【例4】C=X=_G206seattle/_G206rochester/_G206554.4Prolog的搜索策略【例4】C=X=_G206se4.4Prolog的搜索策略【例5】X=_G206,Y=_G207a/X,c/Za/Y解1564.4Prolog的搜索策略【例5】X=_G206,Y=4.4Prolog的搜索策略【例5】X=_G206,Y=_G207a/X,c/Za/Yb/Y解2解1574.4Prolog的搜索策略【例5】X=_G206,Y=4.4Prolog的搜索策略【例5】X=_G206,Y=_G207a/X,c/Za/Yb/Y解2解1b/X,c/Za/Y解3584.4Prolog的搜索策略【例5】X=_G206,Y=4.4Prolog的搜索策略【例5】X=_G206,Y=_G207a/X,c/Za/Yb/Y解2解1b/X,c/Za/Y解3b/Y解4594.4Prolog的搜索策略【例5】X=_G206,Y=4.4Prolog的搜索策略e/X,b/Y【例6】604.4Prolog的搜索策略e/X,b/Y【例6】604.4Prolog的搜索策略e/X,b/Ye/X,b/Yd/Zd/Z【例6】614.4Prolog的搜索策略e/X,b/Ye/X,b4.4Prolog的搜索策略e/X,b/Ye/X,b/Yd/Zd/Zd/X,b/Yc/Z【例6】624.4Prolog的搜索策略e/X,b/Ye/X,b4.4Prolog的搜索策略Prolog是否是纯逻辑式编程语言？634.4Prolog的搜索策略Prolog是否是纯逻辑式编程4.4Prolog的搜索策略【例7】bob/Yamy/X,bob/Zbob/X,bob/Y644.4Prolog的搜索策略【例7】bob/Yamy/X,4.4Prolog的搜索策略【例7】bob/Yamy/X,bob/Zbob/X,bob/Ybob/X654.4Prolog的搜索策略【例7】bob/Yamy/X,4.4Prolog的搜索策略【例7】bob/Yamy/X,bob/Zbob/X,bob/Ybob/Xbob/X664.4Prolog的搜索策略【例7】bob/Yamy/X,4.4Prolog的搜索策略【例8】bob/YX/Z,bob/Y674.4Prolog的搜索策略【例8】bob/YX/Z,b4.4Prolog的搜索策略【例9】bob/X684.4Prolog的搜索策略【例9】bob/X684.4Prolog的搜索策略【例9】bob/Xbob/Ybob/Zamy/X694.4Prolog的搜索策略【例9】bob/Xbob/Yb4.4Prolog的搜索策略【例9】bob/Xbob/Yamy/XZ`/X,bob/Y704.4Prolog的搜索策略【例9】bob/Xbob/Ya内容1.逻辑和逻辑程序2.Horn子句3.归结与合一4.Prolog语言4.1符号和数据结构4.2Prolog的执行4.3合一4.4Prolog的搜索策略4.5循环和控制结构71内容1.逻辑和逻辑程序714.5循环和控制结构强制回溯实现循环和重复搜索724.5循环和控制结构强制回溯724.5循环和控制结构截断回溯停止对整棵搜索树的遍历734.5循环和控制结构截断回溯734.5循环和控制结构Prologcut（截断/阻止回溯）机制使用内部无参谓词（！）；可以作为子目标放在规则子句的体内；

解释：①程序调用cut总是成功；②当某个子目标失败回溯时，不允许越过！回溯。a:-b,c,d,e,!,f,g,h,I,j.

a:-b,c,d,e,!,f,g,h,I,j.a:-b,c,d,e,!,f,g,h,I,j.立即失败SucceedFailRedoBacktrack744.5循环和控制结构Prologcut（截断/阻止回溯）1/X1/X2/X3/X【例1】751/X1/X2/X3/X【例1】751/X1/X【例2】761/X1/X【例2】76【例3】1/X1/Y2/Y3/Y0/X,0/Y