逻辑程序设计语言范型(逻辑程序设计理论基础).ppt

,2023年10月19日星期四,程序设计语言范型Programming Languages Paradigms,教师：张荣华 华北电力大学计算机系软件教研室（保定）,逻辑程序设计语言范型,逻辑程序设计理论基础,第三部分,第六章,逻辑程序设计理论基础,第六章-3,内容,1.逻辑程序设计概述2.知识的表示2.1 谓词演算2.2 基于谓词演算的知识表示2.3 谓词演算推理规则3.知识的利用3.1 搜索3.2 推理3.2.1 置换与合一3.2.2 自然演绎推理3.2.3 归结演绎推理3.2.4 子句集化简,逻辑程序设计理论基础,第六章-4,1.逻辑程序设计概述,逻辑程序设计逻辑程序设计支持说明性程序设计范型根据问题的高层描述来构建程序告诉计算机“什么是真的”和“需要做什么”，而不是“怎样做”。程序员把精力放在问题（封闭的问题世界）的描述上，而不是写一些诸如“下一步做什么”之类的底层算法指令。Prolog是目前唯一广泛使用的逻辑程序设计语言Prolog（Programming in Logic）20世纪70年代初、法国马赛大学主要应用于人工智能（人类智能活动的模拟）领域相关问题的求解。易于表达人的逻辑思维,逻辑程序设计理论基础,第六章-5,1.逻辑程序设计概述,【例1】：水平线与垂直线问题。使用两个谓词：vertical/2 和 horizontal/2,vertical(line(point(X,Y),point(X,Z).horizontal(line(point(X,Y),point(Z,Y).,vertical(line(point(1,1),point(1,3).yes,事实,查询/目标,horizontal(line(point(1,1),point(2,Y).Y=1;no,horizontal(line(point(2,3),P).P=point(_G434,3);no,逻辑程序设计理论基础,第六章-6,1.逻辑程序设计概述,【例2】求解以下六个英语单词的纵横字谜问题。abalone,abandon,anagram,connect,elegant,enhance,事实,规则,逻辑程序设计理论基础,第六章-7,1.逻辑程序设计概述,a,a,b,l,o,n,e,a,n,a,g,r,a,m,o,c,n,n,e,c,t,a,a,d,n,e,e,e,a,t,h,n,e,a,a,d,n,b,o,n,l,e,e,a,t,n,g,n,e,h,n,e,c,a,a,a,o,e,a,a,r,m,c,n,e,t,查询/目标,逻辑程序设计理论基础,第六章-8,内容,1.逻辑程序设计概述2.知识的表示2.1 谓词演算2.2 基于谓词演算的知识表示2.3 谓词演算推理规则3.知识的利用3.1 搜索3.2 推理3.2.1 置换与合一3.2.2 自然演绎推理3.2.3 归结演绎推理3.2.4 子句集化简,逻辑程序设计理论基础,第六章-9,2.知识的表示,知识阈值理论知识是一切智能行为的基础智能取决于知识的数量及其可运用的程度。要使计算机具有智能，就必须使它具有知识。知识表示方法（知识表示语言）谓词演算（一阶谓词逻辑表示法）产生式表示法语义网络表示法框架表示法脚本表示法面向对象表示法 等等,逻辑程序设计理论基础,第六章-10,2.知识的表示,选择知识表示方法的重要性,【例】缺角棋盘问题,逻辑程序设计理论基础,第六章-11,内容,1.逻辑程序设计概述2.知识的表示2.1 谓词演算2.2 基于谓词演算的知识表示2.3 谓词演算推理规则3.知识的利用3.1 搜索3.2 推理3.2.1 置换与合一3.2.2 自然演绎推理3.2.3 归结演绎推理3.2.4 子句集化简,逻辑程序设计理论基础,第六章-12,2.1 谓词演算,这里讨论的谓词演算 一阶谓词演算（first-order predicate calculus）全称量化变量和存在量化变量仅可以指向论域中的对象，而不允许指向谓词和函数。这样的谓词演算语言称为一阶谓词演算。二值逻辑不讨论其它逻辑形态多值逻辑、多维逻辑、缺省逻辑、动态逻辑,逻辑程序设计理论基础,第六章-13,2.1 谓词演算,【例】用谓词表示命题P：星期二下了雨。谓词表示：weather（tuesday，rain）允许使用变量建立关于实体类的通用断言 weather（X，rain）谓词演算符号（项）（以Prolog语言为例）由以下三部分组成：英文字母，包括大写和小写。数字0，19。下划线_。以字母开始，后面可以跟这些合法字符的任意序列。,逻辑程序设计理论基础,第六章-14,2.1 谓词演算,谓词演算符号（项）（以Prolog语言为例）真值符号：true和false（保留符号）变量符号:以大写字母开始的符号表达式。常量符号:以小写字母开始的符号表达式。函数符号:以小写字母开始的符号表达式。谓词符号：以小写字母开始的符号表达式。例如：likes（george，kate）%likes/2likes（george，sarah，tuesday）%likes/3likes（X，kate）friends（father_of(david)，father_of(kate)）,逻辑程序设计理论基础,第六章-15,内容,1.逻辑程序设计概述2.知识的表示2.1 谓词演算2.2 基于谓词演算的知识表示2.3 谓词演算推理规则3.知识的利用3.1 搜索3.2 推理3.2.1 置换与合一3.2.2 自然演绎推理3.2.3 归结演绎推理3.2.4 子句集化简,逻辑程序设计理论基础,第六章-16,2.2 基于谓词演算的知识表示,【例1】事实性知识：friends（father_of(david)，father_of(kate)）【例2】规则性知识：“所有的教师都有自己的学生”根据所表示的知识定义谓词teacher（X）：表示X是教师student（Y）：表示Y是学生teach（X，Y）：表示X是Y的老师 用2个量词和5个连接词把这些谓词连结成语句,逻辑程序设计理论基础,第六章-17,2.2 基于谓词演算的知识表示,【例3】机器人移盒子问题设在一房间里，C处有一个机器人，A和B处各有一张桌子，分别称为A桌和B桌，A桌子上有一盒子，如下图所示。要求机器人从C处出发把盒子从A桌上拿到B桌上，然后再回到C处。请用谓词逻辑来描述机器人的行动过程。,使用规则！,逻辑程序设计理论基础,第六章-19,谓词逻辑表示的应用,GOTO(x,y),C/x,A/y,Start,PICKUP(x),A/x,GOTO(x,y),A/x,B/y,SETDOWN(x),B/x,GOTO(x,y),B/x,C/y,逻辑程序设计理论基础,第六章-20,内容,1.逻辑程序设计概述2.知识的表示2.1 谓词演算2.2 基于谓词演算的知识表示2.3 谓词演算推理规则3.知识的利用3.1 搜索3.2 推理3.2.1 置换与合一3.2.2 自然演绎推理3.2.3 归结演绎推理3.2.4 子句集化简,逻辑程序设计理论基础,第六章-21,2.3 谓词演算推理规则,谓词公式的永真蕴含性对谓词公式 P和Q，如果 PQ永真，则称P永真蕴含 Q，且称Q为P的逻辑结论，P为Q的前提，记作P=Q。化简式（与消除）：PQ=P 和 PQ=Q附加式：P=PQ 和 Q=PQ析取三段论：P，P V Q=Q取式假言推理：P，PQ=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）,逻辑程序设计理论基础,第六章-22,内容,1.逻辑程序设计概述2.知识的表示3.知识的利用3.1 搜索3.2 推理3.2.1 置换与合一3.2.2 自然演绎推理3.2.3 归结演绎推理3.2.4 子句集化简,逻辑程序设计理论基础,第六章-23,3.知识的利用,知识的利用：基于对某个封闭世界已表示的知识的处理，以求解特定的问题。搜索：根据问题的实际情况，不断寻找可利用知识，从而构造一条代价最小的推理路线，使问题得以解决的过程，称为搜索。盲目搜索：深度优先搜索、宽度优先搜索；启发式搜索：最佳优先搜索、A*算法；推理：按照某种策略从已知事实出发去推出结论的过程问题求解的过程（思维过程）。自然演绎推理归结演绎推理（Prolog语言采用的推理机制，重点）合一（匹配）操作；推理（搜索）方向：深度优先；回溯机制；,逻辑程序设计理论基础,第六章-24,内容,1.逻辑程序设计概述2.知识的表示3.知识的利用3.1 搜索3.2 推理3.2.1 置换与合一3.2.2 自然演绎推理3.2.3 归结演绎推理3.2.4 子句集化简,逻辑程序设计理论基础,第六章-25,3.1 搜索,搜索的基础是图论例：九宫游戏的状态空间图,逻辑程序设计理论基础,第六章-26,基于图搜索的问题求解程序问题求解程序能否被赋予可靠的机制（不犯任何错误）穿越状态空间达到预期的目标状态，并建立解路径？,回溯：系统地穿越状态空间的所有路径的一种技术。,逻辑程序设计理论基础,第六章-27,3.1 搜索,对假想状态空间的深度优先搜索（回溯）,逻辑程序设计理论基础,第六章-28,内容,1.逻辑程序设计概述2.知识的表示3.知识的利用3.1 搜索3.2 推理3.2.1 置换与合一3.2.2 自然演绎推理3.2.3 归结演绎推理3.2.4 子句集化简,逻辑程序设计理论基础,第六章-29,3.2.1 置换与合一,【例】有如下三段论：“所有人会死；苏格拉底是人，所以苏格拉底会死。”,这种寻找项对变量的置换，使谓词一致的过程叫做合一的过程（合一算法）项：常量、函数或其他变量公式集F=man(X)，man(socrates)中的两个公式是可合一的，置换=scorates/X是该公式集的一个合一。,为了应用推理规则进行推理，推理机必须能够判断两个表达式是否相同（匹配）。,逻辑程序设计理论基础,第六章-30,3.2.1 置换与合一,合一算法 unify（E1，E2）计算两个谓词演算公式间的合一置换。返回合一置换或常量FAIL（当不可能合一时）【例】使用用列表语法表示谓词公式语法。,E：p（f（a），g（X，Y）,（p（f a）（g X Y）,逻辑程序设计理论基础,第六章-34,内容,1.逻辑程序设计概述2.知识的表示3.知识的利用3.1 搜索3.2 推理3.2.1 置换与合一3.2.2 自然演绎推理3.2.3 归结演绎推理3.2.4 子句集化简,逻辑程序设计理论基础,第六章-35,3.2.2 自然演绎推理,自然演绎推理从一组已知为真的事实出发，直接运用经典逻辑中的推理规则推出结论的过程。,化简式（与消除）：PQ=P 和 PQ=Q附加式：P=PQ 和 Q=PQ析取三段论：P，P V Q=Q取式假言推理：P，PQ=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）,逻辑程序设计理论基础,第六章-36,3.2.2 自然演绎推理,【例1】基于谓词逻辑演算的财务顾问该财务顾问的功能是帮助用户根据个人的年收入及已存款数量决策应该继续存款还是向股票市场投资。投资策略的标准如下：存款数额还不充足的个体始终该把提高存款额作为他们的首选目标，无论他们的收入如何。具有充足存款和充足收入的个体应该考虑风险较高但潜在投资收益也更高的股票市场。收入较低并且已经具有充足存款的个体可以考虑把他们的剩余收入在存款和股票间分摊，以便既能提高存款数额又能尝试通过股票提高收入。存款和收入的充足性可以由个体要供养的人数决定。充足的存款：供养一个人至少要在银行存款5000美元。充足的收入：收入必须是稳定的，而且年收入至少是15000美元，在加额外的给每个要供养的人4000美元。,初始逻辑系统（知识库）：,12.income(inadequate),13.savings_account(adequate),X,逻辑程序设计理论基础,第六章-38,3.2.2 自然演绎推理,推理方向数据驱动搜索（data-driven search）正向追索（forward chaining），问题求解程序从问题的给定事实和改变状态的合法移动和规则的集合入手。然后把规则应用到事实产生新的事实，接下来新的事实又被规则用来产生更多新的事实，搜索如此进行下去，直到产生满足目标条件的一条路径。目标驱动搜索（goal-driven search）反向追索（backward chaining），从求解的目标着手。先分析怎样使用合法的移动来产生这个目标，并求出要应用这些移动必须具备的条件。这些条件成为要搜索的新目标（子目标）。然后继续反向追溯相继的子目标，直至返回到问题中的事实。这样便找到了从问题到目标的移动规则链。,逻辑程序设计理论基础,第六章-39,3.2.2 自然演绎推理,【例2】基于谓词逻辑演算的财务顾问基于目标驱动的带回溯的深度优先搜索,X,逻辑程序设计理论基础,第六章-40,3.2.2 自然演绎推理,假定某个投资个体要供养2人，有20000美元存款，30000美元稳定收入。咨询的目标找到一种投资方案：,*失败*,财务顾问程序搜索的与/或树,成功：X=stocks,*失败并回溯*,逻辑程序设计理论基础,第六章-42,内容,1.逻辑程序设计概述2.知识的表示3.知识的利用3.1 搜索3.2 推理3.2.1 置换与合一3.2.2 自然演绎推理3.2.3 归结演绎推理3.2.4 子句集化简,逻辑程序设计理论基础,第六章-43,3.2.3 归结演绎推理,归结演绎推理是一种基于鲁宾逊归结原理的机器推理技术，使机器定理证明的自动化成为现实。鲁宾逊归结原理亦称为消解原理，是鲁宾逊于1965年在海伯伦理论的基础上提出的一种基于逻辑的“反证法”。,逻辑程序设计理论基础,第六章-44,3.2.3 归结演绎推理,相关概念：文字原子谓词公式及其否定统称为文字。例如：P(x)、Q(y)、P(x)、Q(y)子句（归结的对象）任何文字的析取式称为子句。例如，P(x)Q(y)，P(x,f(x)Q(x,g(x)空子句不包含任何文字的子句称为空子句。由于空子句不含有任何文字，也就不能被任何解释所满足，因此空子句是永假的，不可满足的。空子句一般被记为或NIL。子句集由Horn子句或空子句所构成的集合。,逻辑程序设计理论基础,第六章-45,3.2.3 归结演绎推理,鲁宾逊归结原理如果存在某个公理 和，那么 在逻辑上成立。称 是 和 的消解式。,归结演绎推理（反证法）的步骤：将前提和公理转化为子句的形式。将要证明的结论取反，并转化为子句形式，与第步形成的子句共同构成子句集。利用鲁宾逊归结原理归结这些子句，生成可以从逻辑上推导出的新子句。通过生成空子句得出矛盾。,【例】Fido是狗 所有的狗都是动物 所有的动物都会死证明：Fido会死。证明一（自然演绎推理）所有的狗都是动物：Fido是狗：取式假言推理和fido/X：所有的动物都会死：取式假言推理和fido/Y：,证明二（归结反驳推理）,谓词形式,子句形式,逻辑程序设计理论基础,第六章-47,3.2.3 归结演绎推理,子句集,“死狗”问题的归结证明,逻辑程序设计理论基础,第六章-48,内容,1.逻辑程序设计概述2.知识的表示3.知识的利用3.1 搜索3.2 推理3.2.1 置换与合一3.2.2 自然演绎推理3.2.3 归结演绎推理3.2.4 子句集化简,逻辑程序设计理论基础,第六章-49,3.2.4 子句集化简,【例】消去连接词“”和“”,减少否定符号的辖域,逻辑程序设计理论基础,第六章-50,3.2.4 子句集化简,重新命名变元，使不同量词约束的变元有不同的名字化为前束范式消去存在量词（skolemization斯柯伦化）（a）若存在量词不出现在全称量词的辖域内用一个新的个体常量替换受该存在量词约束的变元。,（b）若存在量词位于一个或多个全称量词的辖域内用 Skolem函数 y=f（x1,x2,xn）替换受该存在量词约束的变元，然后再消去该存在量词。,逻辑程序设计理论基础,第六章-51,3.2.4 子句集化简,化为Skolem 标准形Skolem 标准形的一般形式为：M（x1,x2,xn）是Skolem标准形的母式，它由子句的合取所构成。把谓词公式化为Skolem标准形需要使用以下等价关系,消去全称量词剩下的母式，仍假设其变元是被全称量词量化的。/Prolog子句中的变量总是全程量词,逻辑程序设计理论基础,第六章-52,4.子句集化简,子句形式与Prolog程序有着非常密切的关系一旦有了谓词公式子句形式，将它翻译成Prolog程序就非常容易。,(student(A)dorm_resident(A)(student(A)takes(A,B)class(B),student(A)(takes(A,B)class(B),student(A)(dorm_resident(A),student(A)dorm_resident(A),student(A)(takes(A,B)class(B),student(A):-dorm_resident(A),student(A):-takes(A,B),class(B),