[计算机软件及应用]第6章 逻辑程序设计语言范型逻辑程序设计理论基础.ppt

,2019年4月18日星期四,程序设计语言范型 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/2 likes（george，sarah，tuesday） %likes/3 likes（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 子句集化简