第9章逻辑程序设计精选文档.ppt
第第9 9章逻辑程序设计章逻辑程序设计本讲稿第一页，共九十页内容内容n1.逻辑和逻辑程序n2.Horn子句n3.归结与合一n4.Prolog语言2 2本讲稿第二页，共九十页1.1.逻辑和逻辑程序逻辑和逻辑程序n逻辑程序设计n逻辑程序设计支持说明性程序设计范型n根据问题的高层描述来构建程序n告诉计算机“什么是真的”和“需要做什么”，而不是“怎样做”。n程序员把精力放在问题（封闭的问题世界）的描述上，而不是写一些诸如“下一步做什么”之类的底层算法指令。3 3本讲稿第三页，共九十页1.1.逻辑和逻辑程序逻辑和逻辑程序n谓词演算n逻辑程序设计中使用的逻辑n【例】用谓词表示的逻辑命题n0是自然数n2是自然数n对于所有的x，如果x是自然数，则x+1也是自然数n-1是自然数natural(0)natural(2)natural(-1)forallx,natural(x)natural(successor(x)二值逻辑二值逻辑4 4本讲稿第四页，共九十页1.1.逻辑和逻辑程序逻辑和逻辑程序n谓词演算n谓词演算元素n常量：数或名称n谓词：值域为真或假的函数名n函数：区别谓词的其余函数n变量：不确定值n连接词：n量词：描述变量n标点符号：(),;(),;a为真时为真时b为真为真ab存在量词存在量词全称量词全称量词natural(0)forallx,natural(x)natural(successor(x)5 5本讲稿第五页，共九十页1.1.逻辑和逻辑程序逻辑和逻辑程序n谓词演算n一阶谓词演算（first-order predicate calculus）n全称量化变量和存在量化变量仅可以指向论域中的对象，而不允许指向谓词和函数n谓词和函数的参数是项n常量n变量n函数6 6本讲稿第六页，共九十页1.1.逻辑和逻辑程序逻辑和逻辑程序n谓词演算n推理规则n【例】有如下三段论：n“所有人会死；苏格拉底是人，所以苏格拉底会死。”,abab7 7本讲稿第七页，共九十页【例】证明：Fido会死Fido是狗 所有的狗都是动物 所有的动物都会死证明n所有的狗都是动物：nFido是狗：n取式假言推理和fido/X：n所有的动物都会死：n取式假言推理和fido/Y：谓词形式谓词形式1.1.逻辑和逻辑程序逻辑和逻辑程序8 8本讲稿第八页，共九十页1.1.逻辑和逻辑程序逻辑和逻辑程序n谓词演算n推理规则n为了应用推理规则进行推理，推理机必须能够判断两个表达式是否相同（匹配）。n这种寻找项对变量的置换，使谓词一致的过程叫做合一的过程（合一算法）n项：常量、函数或其他变量n公式集F=man(X)，man(socrates)中的两个公式是可合一的，置换=scorates/X是该公式集的一个合一。9 9本讲稿第九页，共九十页1.1.逻辑和逻辑程序逻辑和逻辑程序n谓词演算n推理规则n化简式（与消除）：PQ=P 和 PQ=Qn附加式：P=PQ 和 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）1010本讲稿第十页，共九十页1.1.逻辑和逻辑程序逻辑和逻辑程序n谓词演算n推理规则n自然演绎推理n从一组已知为真的事实出发，直接运用经典逻辑中的推理规则推出结论的过程1111本讲稿第十一页，共九十页内容内容n1.逻辑和逻辑程序n2.Horn子句n3.归结与合一n4.Prolog语言1212本讲稿第十二页，共九十页2.Horn 2.Horn 子句子句nHorn子句是形如 的命题 n其中a只能是简单的不包含连接词的命题 na的数量可以为零n注意：Horn子句能够被用来表示大多数的逻辑命题，但不是全部 没有没有or和量词和量词所有的所有的a为真为真则则b真真b恒恒真真事实事实1313本讲稿第十三页，共九十页【例】证明：Fido会死所有的狗都是动物 Fido是狗所有的动物都会死谓词形式谓词形式子句形式子句形式2.Horn 2.Horn 子句子句隐式全称隐式全称约束约束1414本讲稿第十四页，共九十页2.Horn 2.Horn 子句子句n目标驱动n自动推理系统，反向使用Horn子句n询问(目标语句)子句体子句体子句头子句头无头子句无头子句对对b的定义的定义1515本讲稿第十五页，共九十页内容内容n1.逻辑和逻辑程序n2.Horn子句n3.归结与合一n4.Prolog语言1616本讲稿第十六页，共九十页3.3.归结与合一归结与合一n归结(消解)n两个Horn子句n第一个Horn子句的头与第二个子句体的一个命题匹配n则第二个子句中的命题可以被替换为第一个子句的体n【例】bi匹配匹配a1717本讲稿第十七页，共九十页3.3.归结与合一归结与合一n归结过程(目标驱动)n用已知子句的头部来匹配无头子句体中的一个目标n如果成功，用已知子句的体替换被匹配的目标(归结)，建立新的子句n继续用同样的方式修改目标系列n这些新的目标被称为子目标n如果成功消除了所有的目标，则初始命题得证询问询问1818本讲稿第十八页，共九十页3.3.归结与合一归结与合一子句集子句集“死狗死狗”问题的归结证明问题的归结证明合一合一要匹配包含变量的语句必须令变量等于某项1919本讲稿第十九页，共九十页3 3 归结与合一归结与合一n必须解决的问题n逻辑程序系统必须使用一个高效执行的算法，规定n求解目标应用子句的顺序 2020本讲稿第二十页，共九十页3 3 归结与合一归结与合一2121本讲稿第二十一页，共九十页内容内容n1.逻辑和逻辑程序n2.Horn子句n3.归结与合一n4.Prolog语言2222本讲稿第二十二页，共九十页PrologProlog语言概述语言概述nProlog（ProProgramming in LogLogic）n诞生于20世纪70年代初n法国马赛大学作为自然语言理解项目的一部分研制成功n目前，爱丁堡大学开发的Prolog版本使用最为广泛n主要应用于人工智能领域相关问题的求解n易于表达人的逻辑思维n迄今最能体现逻辑程序设计思想的逻辑编程语言n“说明式”的语言；n采用一阶谓词演算说明（描述）问题n知识库（事实和规则）的描述采用子句（Clause）形式nProlog是目前唯一广泛使用的逻辑程序设计语言2323本讲稿第二十三页，共九十页PrologProlog语言概述语言概述nSWI-Prolognhttp:/www.swi-prolog.org/n安装文件（注意顺序安装）n（1）SWI-Prolog for MS-Windowsn（2）SWI-Prolog-Editornhttp:/lakk.bildung.hessen.de/netzwerk/faecher/informatik/swiprolog/indexe.html 2424本讲稿第二十四页，共九十页内容内容n1.逻辑和逻辑程序n2.Horn子句n3.归结与合一n4.Prolog语言n4.1 符号和数据结构n4.2 Prolog的执行n4.3 合一n4.4 Prolog的搜索策略n4.5 循环和控制结构2525本讲稿第二十五页，共九十页4.1 4.1 符号和数据结构符号和数据结构n基本符号n常量n以小写字母开始的一串字母、数字、下划线或用单引号界定的一串任何可打印的ASCII字符。n变量n以大写字母开始一串字母、数字和下划线；n下划线（_）表示匿名变量；n连接词n，/and n;/orn:-/implementation2626本讲稿第二十六页，共九十页4.1 4.1 符号和数据结构符号和数据结构n基本数据结构n结构（谓词/复杂项）n vertical(line(point(X,Y),point(X,Z).2727本讲稿第二十七页，共九十页4.1 4.1 符号和数据结构符号和数据结构n基本数据结构n表（List）：有限的元素序列。n由方括号 之间由逗号隔开的有序元素组成。n表中的元素可以是原子、结构、或任何其它的项，包括表在内。2828本讲稿第二十八页，共九十页4.1 4.1 符号和数据结构符号和数据结构n基本数据结构n表n任何非空的表=表头（head）+表尾（tail）n表头：表的第一个元素；n表尾：除第一个元素，表的其它元素组成的表。nProlog内部谓词“|”n用于将表分解为表头和表尾；n灵活使用灵活使用|是写好是写好PrologProlog表处理程序的关键表处理程序的关键！2929本讲稿第二十九页，共九十页4.1 4.1 符号和数据结构符号和数据结构n基本数据结构n表n谓词“|”的使用3030本讲稿第三十页，共九十页内容内容n1.逻辑和逻辑程序n2.Horn子句n3.归结与合一n4.Prolog语言n4.1 符号和数据结构n4.2 Prolog的执行n4.3 合一n4.4 Prolog的搜索策略n4.5 循环和控制结构3131本讲稿第三十一页，共九十页4.2 Prolog4.2 Prolog的执行的执行nProlog程序运行n通过提问查询知识库n使用分号（；）查询多个解（multiple answers）3232本讲稿第三十二页，共九十页内容内容n1.逻辑和逻辑程序n2.Horn子句n3.归结与合一n4.Prolog语言n4.1 符号和数据结构n4.2 Prolog的执行n4.3 合一n4.4 Prolog的搜索策略n4.5 循环和控制结构3333本讲稿第三十三页，共九十页4.3 4.3 合一合一n合一n对变量初始化或者分配存储空间和值的过程n在某种意义上是将两个项等同的过程 n?-a=a.yes /常量与自己合一n?-a=b.no /常量不能与其他常量合一n?-foo(a,b)=foo(a,b).yes /结构递归合一PrologProlog中中“=”表示合一表示合一3434本讲稿第三十四页，共九十页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.3 4.3 合一合一3535本讲稿第三十五页，共九十页4.3 4.3 合一合一 n合一算法n如果Term1和Term2是常量，那么当且仅当Term1和 Term2是相同的原子或整数；n如果Term1是变量，Term2是任何类型的项，那么 Term1实例化为Term2；n注：如果Term2也是变量，互相实例化，共享值。n如果Term1和Term2都是结构，两者合一，当且仅当n（a）两者有相同的算符（谓词）；n（b）两者对应的参数匹配，即能够递归地合一；n（c）变量实例化必须保持一致性；n当满足前面三种情况时，两者项合一。3636本讲稿第三十六页，共九十页4.3 4.3 合一合一n【思考】nProlog实现合一操作时是否使用标准的合一算法？n n老版本的Prolog实现: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(.)SICStus Prolog SWI Prolog X=father(*)3737本讲稿第三十七页，共九十页4.3 4.3 合一合一n利用合一简化操作nconsn表的构造与选择向后运行向后运行消解自动消解自动产生合一产生合一需要合一的模式需要合一的模式写入子句头写入子句头3838本讲稿第三十八页，共九十页4.3 4.3 合一合一n利用合一简化操作nappendn拼接两张表ABYB+YWA输入输入:W:结果结果:+3939本讲稿第三十九页，共九十页4.3 4.3 合一合一n利用合一简化操作nappend4040本讲稿第四十页，共九十页4.3 4.3 合一合一n利用合一简化操作nappend向后运行向后运行4141本讲稿第四十一页，共九十页4.3 4.3 合一合一n利用合一简化操作nreversen逆置表中元素4242本讲稿第四十二页，共九十页内容内容n1.逻辑和逻辑程序n2.Horn子句n3.归结与合一n4.Prolog语言n4.1 符号和数据结构n4.2 Prolog的执行n4.3 合一n4.4 Prolog的搜索策略n4.5 循环和控制结构4343本讲稿第四十三页，共九十页4.4 Prolog4.4 Prolog的搜索策略的搜索策略n搜索策略n搜索方向基于目标导向n搜索类型深度优先搜索n从左至右考虑子目标n从上到下考虑子句n合一失败，如何控制程序继续进行求解问题？n回溯nProlog内部最基本的自动的控制流机制n需要搜索更多解时，如何控制程序继续进行求解问题？n分号表示结束当前合一，回溯查找其它可满足的解4444本讲稿第四十四页，共九十页n回溯：回溯：系统地穿越状态空间的所有路径的一种技术系统地穿越状态空间的所有路径的一种技术4.4 Prolog4.4 Prolog的搜索策略的搜索策略4545本讲稿第四十五页，共九十页4.4 Prolog4.4 Prolog的搜索策略的搜索策略n【例1】4646本讲稿第四十六页，共九十页4.4 Prolog4.4 Prolog的搜索策略的搜索策略n【例1】4747本讲稿第四十七页，共九十页4.4 Prolog4.4 Prolog的搜索策略的搜索策略n【例2】匹配失败匹配失败4848本讲稿第四十八页，共九十页4.4 Prolog4.4 Prolog的搜索策略的搜索策略n【例2】4949本讲稿第四十九页，共九十页n【例3】4.4 Prolog4.4 Prolog的搜索策略的搜索策略5050本讲稿第五十页，共九十页n【例3】4.4 Prolog4.4 Prolog的搜索策略的搜索策略DR NO/Title5151本讲稿第五十一页，共九十页n【例3】4.4 Prolog4.4 Prolog的搜索策略的搜索策略DR NO/Title匹配失败匹配失败5252本讲稿第五十二页，共九十页n【例3】4.4 Prolog4.4 Prolog的搜索策略的搜索策略DR NO/Title310/Length5353本讲稿第五十三页，共九十页n【例3】4.4 Prolog4.4 Prolog的搜索策略的搜索策略DR NO/Title310/Length5454本讲稿第五十四页，共九十页4.4 Prolog4.4 Prolog的搜索策略的搜索策略n【例4】C=X=_G206seattle/_G206失败并回溯失败并回溯5555本讲稿第五十五页，共九十页4.4 Prolog4.4 Prolog的搜索策略的搜索策略n【例4】C=X=_G206seattle/_G206rochester/_G2065656本讲稿第五十六页，共九十页4.4 Prolog4.4 Prolog的搜索策略的搜索策略n【例5】X=_G206,Y=_G207a/X,c/Za/Y解解15757本讲稿第五十七页，共九十页4.4 Prolog4.4 Prolog的搜索策略的搜索策略n【例5】X=_G206,Y=_G207a/X,c/Za/Yb/Y解解2解解15858本讲稿第五十八页，共九十页4.4 Prolog4.4 Prolog的搜索策略的搜索策略n【例5】X=_G206,Y=_G207a/X,c/Za/Yb/Y解解2解解1b/X,c/Za/Y解解35959本讲稿第五十九页，共九十页4.4 Prolog4.4 Prolog的搜索策略的搜索策略n【例5】X=_G206,Y=_G207a/X,c/Za/Yb/Y解解2解解1b/X,c/Za/Y解解3b/Y解解46060本讲稿第六十页，共九十页4.4 Prolog4.4 Prolog的搜索策略的搜索策略e/X,b/Yn【例6】6161本讲稿第六十一页，共九十页4.4 Prolog4.4 Prolog的搜索策略的搜索策略e/X,b/Ye/X,b/Yd/Zd/Zn【例6】6262本讲稿第六十二页，共九十页4.4 Prolog4.4 Prolog的搜索策略的搜索策略e/X,b/Ye/X,b/Yd/Zd/Zd/X,b/Yc/Zn【例6】6363本讲稿第六十三页，共九十页4.4 Prolog4.4 Prolog的搜索策略的搜索策略nProlog是否是纯逻辑式编程语言？6464本讲稿第六十四页，共九十页4.4 Prolog4.4 Prolog的搜索策略的搜索策略n【例7】bob/Yamy/X,bob/Zbob/X,bob/Y6565本讲稿第六十五页，共九十页4.4 Prolog4.4 Prolog的搜索策略的搜索策略n【例7】bob/Yamy/X,bob/Zbob/X,bob/Ybob/X6666本讲稿第六十六页，共九十页4.4 Prolog4.4 Prolog的搜索策略的搜索策略n【例7】bob/Yamy/X,bob/Zbob/X,bob/Ybob/Xbob/X6767本讲稿第六十七页，共九十页4.4 Prolog4.4 Prolog的搜索策略的搜索策略n【例8】bob/YX/Z,bob/Y6868本讲稿第六十八页，共九十页4.4 Prolog4.4 Prolog的搜索策略的搜索策略n【例9】bob/X6969本讲稿第六十九页，共九十页4.4 Prolog4.4 Prolog的搜索策略的搜索策略n【例9】bob/Xbob/Ybob/Zamy/X7070本讲稿第七十页，共九十页4.4 Prolog4.4 Prolog的搜索策略的搜索策略n【例9】bob/Xbob/Yamy/XZ/X,bob/Y7171本讲稿第七十一页，共九十页内容内容n1.逻辑和逻辑程序n2.Horn子句n3.归结与合一n4.Prolog语言n4.1 符号和数据结构n4.2 Prolog的执行n4.3 合一n4.4 Prolog的搜索策略n4.5 循环和控制结构7272本讲稿第七十二页，共九十页4.5 4.5 循环和控制结构循环和控制结构n强制回溯n实现循环和重复搜索7373本讲稿第七十三页，共九十页4.5 4.5 循环和控制结构循环和控制结构n截断回溯n停止对整棵搜索树的遍历7474本讲稿第七十四页，共九十页4.5 4.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.立即失败SucceedFailRedoBacktrack7575本讲稿第七十五页，共九十页1/X1/X2/X3/X【例1】7676本讲稿第七十六页，共九十页1/X1/X【例2】7777本讲稿第七十七页，共九十页【例3】1/X1/Y2/Y3/Y0/X,0/Y7878本讲稿第七十八页，共九十页练练 习习n绘制程序n对询问n的搜索树7979本讲稿第七十九页，共九十页4.5 4.5 循环和控制结构循环和控制结构n否定n如何在逻辑程序设计中实现not操作n当目标X失败时，目标not(X)总是成功n回溯对not产生的问题8080本讲稿第八十页，共九十页实实 例例n【例1】求解以下六个英语单词的纵横字谜问题。nabalone,abandon,anagram,connect,elegant,enhance8181本讲稿第八十一页，共九十页实实 例例aabloneanagramocnnectaadneeeathneaadnbonleeatngnehnecaaaoeaarmcnet8282本讲稿第八十二页，共九十页实实 例例8383本讲稿第八十三页，共九十页实实 例例n【例2】对表进行排序8484本讲稿第八十四页，共九十页实实 例例n【例2】对表进行排序8585本讲稿第八十五页，共九十页实实 例例n【例3】八皇后问题n在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。8686本讲稿第八十六页，共九十页实实 例例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/Y88787本讲稿第八十七页，共九十页实实 例例n【例3】八皇后问题n双坐标表示方法8888本讲稿第八十八页，共九十页实实 例例n【例4】n n皇后问题n选择校验8989本讲稿第八十九页，共九十页实实 例例n【例4】n皇后问题n校验融合在选择中9090本讲稿第九十页，共九十页
