第9章逻辑程序设计课件.ppt

《第9章逻辑程序设计课件.ppt》由会员分享，可在线阅读，更多相关《第9章逻辑程序设计课件.ppt（91页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 逻辑程序设计逻辑程序设计内容内容n1.逻辑和逻辑程序n2.Horn子句n3.归结与合一n4.Prolog语言1 逻辑程序设计逻辑程序设计1.1.逻辑和逻辑程序逻辑和逻辑程序n逻辑程序设计n逻辑程序设计支持说明性程序设计范型n根据问题的高层描述来构建程序n告诉计算机“什么是真的”和“需要做什么”，而不是“怎样做”。n程序员把精力放在问题（封闭的问题世界）的描述上，而不是写一些诸如“下一步做什么”之类的底层算法指令。2 逻辑程序设计逻辑程序设计1.1.逻辑和逻辑程序逻辑和逻辑程序n谓词演算n逻辑程序设计中使用的逻辑n【例】用谓词表示的逻辑命题n0是自然数n2是自然数n对于所有的x，如果x是自然数

2、，则x+1也是自然数n-1是自然数natural(0)natural(2)natural(-1)forallx,natural(x)natural(successor(x)二值逻二值逻辑辑3 逻辑程序设计逻辑程序设计1.1.逻辑和逻辑程序逻辑和逻辑程序n谓词演算n谓词演算元素n常量：数或名称n谓词：值域为真或假的函数名n函数：区别谓词的其余函数n变量：不确定值n连接词：n量词：描述变量n标点符号：(),;(),;a为真时为真时b为真为真ab存在量存在量词词全称量全称量词词natural(0)forallx,natural(x)natural(successor(x)4 逻辑程序设计逻辑程序设计

3、1.1.逻辑和逻辑程序逻辑和逻辑程序n谓词演算n一阶谓词演算（first-order predicate calculus）n全称量化变量和存在量化变量仅可以指向论域中的对象，而不允许指向谓词和函数n谓词和函数的参数是项n常量n变量n函数5 逻辑程序设计逻辑程序设计1.1.逻辑和逻辑程序逻辑和逻辑程序n谓词演算n推理规则n【例】有如下三段论：n“所有人会死；苏格拉底是人，所以苏格拉底会死。”,abab6 逻辑程序设计逻辑程序设计【例】证明：Fido会死Fido是狗 所有的狗都是动物 所有的动物都会死证明n所有的狗都是动物：nFido是狗：n取式假言推理和fido/X：n所有的动物都会死：n取式

4、假言推理和fido/Y：谓词形式谓词形式1.1.逻辑和逻辑程序逻辑和逻辑程序7 逻辑程序设计逻辑程序设计1.1.逻辑和逻辑程序逻辑和逻辑程序n谓词演算n推理规则n为了应用推理规则进行推理，推理机必须能够判断两个表达式是否相同（匹配）。n这种寻找项对变量的置换，使谓词一致的过程叫做合一的过程（合一算法）n项：常量、函数或其他变量n公式集F=man(X)，man(socrates)中的两个公式是可合一的，置换=scorates/X是该公式集的一个合一。8 逻辑程序设计逻辑程序设计1.1.逻辑和逻辑程序逻辑和逻辑程序n谓词演算n推理规则n化简式（与消除）：PQ=P 和 PQ=Qn附加式：P=PQ 和

5、 Q=PQn析取三段论：P，P V Q=Qn取式假言推理：P，PQ=Qn拒式假言推理：Q，P Q=Pn假言三段论：P Q，Q R=P R n二难推理：P Q，P R，Q R=Rn全称固化：（x）P（x）=P（a）n存在固化：（x）P（x）=P（a）9 逻辑程序设计逻辑程序设计1.1.逻辑和逻辑程序逻辑和逻辑程序n谓词演算n推理规则n自然演绎推理n从一组已知为真的事实出发，直接运用经典逻辑中的推理规则推出结论的过程10 逻辑程序设计逻辑程序设计内容内容n1.逻辑和逻辑程序n2.Horn子句n3.归结与合一n4.Prolog语言11 逻辑程序设计逻辑程序设计2.Horn 2.Horn 子句子句nH

6、orn子句是形如 的命题 n其中a只能是简单的不包含连接词的命题 na的数量可以为零n注意：Horn子句能够被用来表示大多数的逻辑命题，但不是全部 没有没有or和量词和量词所有的所有的a为真为真则则b真真b恒恒真真事实事实12 逻辑程序设计逻辑程序设计【例】证明：Fido会死所有的狗都是动物 Fido是狗所有的动物都会死谓词形式谓词形式子句形式子句形式2.Horn 2.Horn 子句子句隐式全隐式全称约束称约束13 逻辑程序设计逻辑程序设计2.Horn 2.Horn 子句子句n目标驱动n自动推理系统，反向使用Horn子句n询问(目标语句)子句子句体体子句子句头头无头子无头子句句对对b的定义的定

7、义14 逻辑程序设计逻辑程序设计内容内容n1.逻辑和逻辑程序n2.Horn子句n3.归结与合一n4.Prolog语言15 逻辑程序设计逻辑程序设计3 3.归结归结与与合一合一n归结(消解)n两个Horn子句n第一个Horn子句的头与第二个子句体的一个命题匹配n则第二个子句中的命题可以被替换为第一个子句的体n【例】bi匹配匹配a16 逻辑程序设计逻辑程序设计3 3.归结归结与与合一合一n归结过程(目标驱动)n用已知子句的头部来匹配无头子句体中的一个目标n如果成功，用已知子句的体替换被匹配的目标(归结)，建立新的子句n继续用同样的方式修改目标系列n这些新的目标被称为子目标n如果成功消除了所有的目标

8、，则初始命题得证询问询问17 逻辑程序设计逻辑程序设计3 3.归结归结与与合一合一子句集子句集“死狗死狗”问题的归结证问题的归结证明明合一合一要匹配包含变量的语句必须令变量等于某项18 逻辑程序设计逻辑程序设计3 3 归结归结与与合一合一n必须解决的问题n逻辑程序系统必须使用一个高效执行的算法，规定n求解目标应用子句的顺序 19 逻辑程序设计逻辑程序设计3 3 归结归结与与合一合一20 逻辑程序设计逻辑程序设计内容内容n1.逻辑和逻辑程序n2.Horn子句n3.归结与合一n4.Prolog语言21 逻辑程序设计逻辑程序设计PrologProlog语言概述语言概述nProlog（ProProgr

9、amming in LogLogic）n诞生于20世纪70年代初n法国马赛大学作为自然语言理解项目的一部分研制成功n目前，爱丁堡大学开发的Prolog版本使用最为广泛n主要应用于人工智能领域相关问题的求解n易于表达人的逻辑思维n迄今最能体现逻辑程序设计思想的逻辑编程语言n“说明式”的语言；n采用一阶谓词演算说明（描述）问题n知识库（事实和规则）的描述采用子句（Clause）形式nProlog是目前唯一广泛使用的逻辑程序设计语言22 逻辑程序设计逻辑程序设计PrologProlog语言概述语言概述nSWI-Prolognhttp:/www.swi-prolog.org/n安装文件（注意顺序安装）

10、n（1）SWI-Prolog for MS-Windowsn（2）SWI-Prolog-Editornhttp:/lakk.bildung.hessen.de/netzwerk/faecher/informatik/swiprolog/indexe.html 23 逻辑程序设计逻辑程序设计内容内容n1.逻辑和逻辑程序n2.Horn子句n3.归结与合一n4.Prolog语言n4.1 符号和数据结构n4.2 Prolog的执行n4.3 合一n4.4 Prolog的搜索策略n4.5 循环和控制结构24 逻辑程序设计逻辑程序设计4.1 4.1 符号和数据结构符号和数据结构n基本符号n常量n以小写字母开

11、始的一串字母、数字、下划线或用单引号界定的一串任何可打印的ASCII字符。n变量n以大写字母开始一串字母、数字和下划线；n下划线（_）表示匿名变量；n连接词n，/and n;/orn:-/implementation25 逻辑程序设计逻辑程序设计4.1 4.1 符号和数据结构符号和数据结构n基本数据结构n结构（谓词/复杂项）n vertical(line(point(X,Y),point(X,Z).26 逻辑程序设计逻辑程序设计4.1 4.1 符号和数据结构符号和数据结构n基本数据结构n表（List）：有限的元素序列。n由方括号 之间由逗号隔开的有序元素组成。n表中的元素可以是原子、结构、或任

12、何其它的项，包括表在内。27 逻辑程序设计逻辑程序设计4.1 4.1 符号和数据结构符号和数据结构n基本数据结构n表n任何非空的表=表头（head）+表尾（tail）n表头：表的第一个元素；n表尾：除第一个元素，表的其它元素组成的表。nProlog内部谓词“|”n用于将表分解为表头和表尾；n灵活使用灵活使用|是写好是写好PrologProlog表处理程序的关键表处理程序的关键！28 逻辑程序设计逻辑程序设计4.1 4.1 符号和数据结构符号和数据结构n基本数据结构n表n谓词“|”的使用29 逻辑程序设计逻辑程序设计内容内容n1.逻辑和逻辑程序n2.Horn子句n3.归结与合一n4.Prolog

13、语言n4.1 符号和数据结构n4.2 Prolog的执行n4.3 合一n4.4 Prolog的搜索策略n4.5 循环和控制结构30 逻辑程序设计逻辑程序设计4 4.2 2 PrologProlog的执行的执行nProlog程序运行n通过提问查询知识库n使用分号（；）查询多个解（multiple answers）31 逻辑程序设计逻辑程序设计内容内容n1.逻辑和逻辑程序n2.Horn子句n3.归结与合一n4.Prolog语言n4.1 符号和数据结构n4.2 Prolog的执行n4.3 合一n4.4 Prolog的搜索策略n4.5 循环和控制结构32 逻辑程序设计逻辑程序设计4 4.3 3 合一合

14、一n合一n对变量初始化或者分配存储空间和值的过程n在某种意义上是将两个项等同的过程 n?-a=a.yes /常量与自己合一n?-a=b.no /常量不能与其他常量合一n?-foo(a,b)=foo(a,b).yes /结构递归合一PrologProlog中中“=”表示合表示合一一33 逻辑程序设计逻辑程序设计n合一n?-X=a.X=a;/变量和常量合一no /仅此一次合一 n?-foo(a,b)=foo(X,b).X=a;/参数合一no /只有是一种可能n?-A=B.nA=_G206nB=_G206;nno 内部共享变量内部共享变量4 4.3 3 合一合一34 逻辑程序设计逻辑程序设计4 4.

15、3 3 合一合一 n合一算法n如果Term1和Term2是常量，那么当且仅当Term1和 Term2是相同的原子或整数；n如果Term1是变量，Term2是任何类型的项，那么 Term1实例化为Term2；n注：如果Term2也是变量，互相实例化，共享值。n如果Term1和Term2都是结构，两者合一，当且仅当n（a）两者有相同的算符（谓词）；n（b）两者对应的参数匹配，即能够递归地合一；n（c）变量实例化必须保持一致性；n当满足前面三种情况时，两者项合一。35 逻辑程序设计逻辑程序设计4 4.3 3 合一合一n【思考】nProlog实现合一操作时是否使用标准的合一算法？n n老版本的Prol

16、og实现:nNotenoughmemorytocompletequery!n现代版本的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(.)SICSt

17、us Prolog SWI Prolog X=father(*)36 逻辑程序设计逻辑程序设计4 4.3 3 合一合一n利用合一简化操作nconsn表的构造与选择向后运向后运行行消解自消解自动产生动产生合一合一需要合一的模式需要合一的模式写入子句头写入子句头37 逻辑程序设计逻辑程序设计4 4.3 3 合一合一n利用合一简化操作nappendn拼接两张表ABYB+YWA输入输入:W:结果结果:+38 逻辑程序设计逻辑程序设计4 4.3 3 合一合一n利用合一简化操作nappend39 逻辑程序设计逻辑程序设计4 4.3 3 合一合一n利用合一简化操作nappend向后运向后运行行40 逻辑程序

18、设计逻辑程序设计4 4.3 3 合一合一n利用合一简化操作nreversen逆置表中元素41 逻辑程序设计逻辑程序设计内容内容n1.逻辑和逻辑程序n2.Horn子句n3.归结与合一n4.Prolog语言n4.1 符号和数据结构n4.2 Prolog的执行n4.3 合一n4.4 Prolog的搜索策略n4.5 循环和控制结构42 逻辑程序设计逻辑程序设计4 4.4 4 PrologProlog的搜索策略的搜索策略n搜索策略n搜索方向基于目标导向n搜索类型深度优先搜索n从左至右考虑子目标n从上到下考虑子句n合一失败，如何控制程序继续进行求解问题？n回溯nProlog内部最基本的自动的控制流机制n需

19、要搜索更多解时，如何控制程序继续进行求解问题？n分号表示结束当前合一，回溯查找其它可满足的解43 逻辑程序设计逻辑程序设计n回溯：回溯：系统地穿越状态空间的所有路径的一种技术系统地穿越状态空间的所有路径的一种技术4 4.4 4 PrologProlog的搜索策略的搜索策略44 逻辑程序设计逻辑程序设计4 4.4 4 PrologProlog的搜索策略的搜索策略n【例1】45 逻辑程序设计逻辑程序设计4 4.4 4 PrologProlog的搜索策略的搜索策略n【例1】46 逻辑程序设计逻辑程序设计4 4.4 4 PrologProlog的搜索策略的搜索策略n【例2】匹配失败匹配失败47 逻辑程

20、序设计逻辑程序设计4 4.4 4 PrologProlog的搜索策略的搜索策略n【例2】48 逻辑程序设计逻辑程序设计n【例3】4 4.4 4 PrologProlog的搜索策略的搜索策略49 逻辑程序设计逻辑程序设计n【例3】4 4.4 4 PrologProlog的搜索策略的搜索策略DR NO/Title50 逻辑程序设计逻辑程序设计n【例3】4 4.4 4 PrologProlog的搜索策略的搜索策略DR NO/Title匹配失败匹配失败51 逻辑程序设计逻辑程序设计n【例3】4 4.4 4 PrologProlog的搜索策略的搜索策略DR NO/Title310/Length52 逻辑

21、程序设计逻辑程序设计n【例3】4 4.4 4 PrologProlog的搜索策略的搜索策略DR NO/Title310/Length53 逻辑程序设计逻辑程序设计4 4.4 4 PrologProlog的搜索策略的搜索策略n【例4】C=X=_G206seattle/_G206失败并回溯失败并回溯54 逻辑程序设计逻辑程序设计4 4.4 4 PrologProlog的搜索策略的搜索策略n【例4】C=X=_G206seattle/_G206rochester/_G20655 逻辑程序设计逻辑程序设计4 4.4 4 PrologProlog的搜索策略的搜索策略n【例5】X=_G206,Y=_G207

22、a/X,c/Za/Y解解156 逻辑程序设计逻辑程序设计4 4.4 4 PrologProlog的搜索策略的搜索策略n【例5】X=_G206,Y=_G207a/X,c/Za/Yb/Y解解2解解157 逻辑程序设计逻辑程序设计4 4.4 4 PrologProlog的搜索策略的搜索策略n【例5】X=_G206,Y=_G207a/X,c/Za/Yb/Y解解2解解1b/X,c/Za/Y解解358 逻辑程序设计逻辑程序设计4 4.4 4 PrologProlog的搜索策略的搜索策略n【例5】X=_G206,Y=_G207a/X,c/Za/Yb/Y解解2解解1b/X,c/Za/Y解解3b/Y解解459

23、逻辑程序设计逻辑程序设计4 4.4 4 PrologProlog的搜索策略的搜索策略e/X,b/Yn【例6】60 逻辑程序设计逻辑程序设计4 4.4 4 PrologProlog的搜索策略的搜索策略e/X,b/Ye/X,b/Yd/Zd/Zn【例6】61 逻辑程序设计逻辑程序设计4 4.4 4 PrologProlog的搜索策略的搜索策略e/X,b/Ye/X,b/Yd/Zd/Zd/X,b/Yc/Zn【例6】62 逻辑程序设计逻辑程序设计4 4.4 4 PrologProlog的搜索策略的搜索策略nProlog是否是纯逻辑式编程语言？63 逻辑程序设计逻辑程序设计4 4.4 4 PrologPro

24、log的搜索策略的搜索策略n【例7】bob/Yamy/X,bob/Zbob/X,bob/Y64 逻辑程序设计逻辑程序设计4 4.4 4 PrologProlog的搜索策略的搜索策略n【例7】bob/Yamy/X,bob/Zbob/X,bob/Ybob/X65 逻辑程序设计逻辑程序设计4 4.4 4 PrologProlog的搜索策略的搜索策略n【例7】bob/Yamy/X,bob/Zbob/X,bob/Ybob/Xbob/X66 逻辑程序设计逻辑程序设计4 4.4 4 PrologProlog的搜索策略的搜索策略n【例8】bob/YX/Z,bob/Y67 逻辑程序设计逻辑程序设计4 4.4 4

25、 PrologProlog的搜索策略的搜索策略n【例9】bob/X68 逻辑程序设计逻辑程序设计4 4.4 4 PrologProlog的搜索策略的搜索策略n【例9】bob/Xbob/Ybob/Zamy/X69 逻辑程序设计逻辑程序设计4 4.4 4 PrologProlog的搜索策略的搜索策略n【例9】bob/Xbob/Yamy/XZ/X,bob/Y70 逻辑程序设计逻辑程序设计内容内容n1.逻辑和逻辑程序n2.Horn子句n3.归结与合一n4.Prolog语言n4.1 符号和数据结构n4.2 Prolog的执行n4.3 合一n4.4 Prolog的搜索策略n4.5 循环和控制结构71 逻辑

26、程序设计逻辑程序设计4 4.5 5 循环和控制结构循环和控制结构n强制回溯n实现循环和重复搜索72 逻辑程序设计逻辑程序设计4 4.5 5 循环和控制结构循环和控制结构n截断回溯n停止对整棵搜索树的遍历73 逻辑程序设计逻辑程序设计4 4.5 5 循环和控制结构循环和控制结构nProlog cut（截断/阻止回溯）机制n使用内部无参谓词（！）；n可以作为子目标放在规则子句的体内；n n解释：n程序调用cut总是成功；n当某个子目标失败回溯时，不允许越过！回溯。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

27、.立即失败SucceedFailRedoBacktrack74 逻辑程序设计逻辑程序设计1/X1/X2/X3/X【例1】75 逻辑程序设计逻辑程序设计1/X1/X【例2】76 逻辑程序设计逻辑程序设计【例3】1/X1/Y2/Y3/Y0/X,0/Y77 逻辑程序设计逻辑程序设计练练 习习n绘制程序n对询问n的搜索树78 逻辑程序设计逻辑程序设计4 4.5 5 循环和控制结构循环和控制结构n否定n如何在逻辑程序设计中实现not操作n当目标X失败时，目标not(X)总是成功n回溯对not产生的问题79 逻辑程序设计逻辑程序设计实实 例例n【例1】求解以下六个英语单词的纵横字谜问题。nabalone,

28、abandon,anagram,connect,elegant,enhance80 逻辑程序设计逻辑程序设计实实 例例aabloneanagramocnnectaadneeeathneaadnbonleeatngnehnecaaaoeaarmcnet81 逻辑程序设计逻辑程序设计实实 例例82 逻辑程序设计逻辑程序设计实实 例例n【例2】对表进行排序83 逻辑程序设计逻辑程序设计实实 例例n【例2】对表进行排序84 逻辑程序设计逻辑程序设计实实 例例n【例3】八皇后问题n在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。85 逻辑程序设计逻辑程序设计实实 例例n【例3】八皇后问题n双坐标表示方法 1 2 3 4 5 6 7 8 X 8 7 6 5 4 3 2 1YX1/Y1,X2/Y2,X3/Y3,X4/Y4,X5/Y5,X6/Y6,X7/Y7,X8/Y886 逻辑程序设计逻辑程序设计实实 例例n【例3】八皇后问题n双坐标表示方法87 逻辑程序设计逻辑程序设计实实 例例n【例4】n n皇后问题n选择校验88 逻辑程序设计逻辑程序设计精品精品课件件！逻辑程序设计逻辑程序设计精品精品课件件！逻辑程序设计逻辑程序设计实实 例例n【例4】n皇后问题n校验融合在选择中91