第六章-逻辑程序设计语言.ppt

第六章-逻辑程序设计语言.ppt

《第六章-逻辑程序设计语言.ppt》由会员分享，可在线阅读，更多相关《第六章-逻辑程序设计语言.ppt（89页珍藏版）》请在冰点文库上搜索。

,2023年4月30日星期日,程序设计语言范型ProgrammingLanguagesParadigms,第六章,逻辑程序设计语言,逻辑程序设计理论基础,第一部分,第一部分理论基础,第六章-4,内容,逻辑程序设计概述知识表示简介谓词演算知识的利用,第一部分理论基础,第六章-5,逻辑程序设计概述,逻辑程序设计语言（说明性语言）Prolog是唯一广泛使用的逻辑程序设计语言；易于表达人的思维，主要应用于专家系统、规划、自然语言理解、机器定理证明等人工智能相关问题的求解。

区别于命令式语言和函数式语言，逻辑式语言都支持说明性程序设计风范；根据问题约束的高层描述来构建程序；告诉计算机“什么是真的”和“需要做什么”，而不是“怎样做”；允许程序员集中精力对待求解问题（一个封闭的世界）的描述，而不是写一些诸如“下一步做什么”之类的底层算法指令。

第一部分理论基础,第六章-6,逻辑程序设计概述,【例】：

水平线与垂直线问题。

使用两个谓词：

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,第一部分理论基础,第六章-7,逻辑程序设计概述,【例】求解以下六个英语单词的纵横字谜问题。

abalone,abandon,anagram,connect,elegant,enhance,事实,规则,第一部分理论基础,第六章-8,逻辑程序设计概述,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,查询/目标,第一部分理论基础,第六章-9,内容,逻辑程序设计概述知识表示简介谓词演算知识的利用,第一部分理论基础,第六章-10,知识表示简介,物理符号系统假设（Simon）推论一:

既然人具有智能，那么他（她）就一定是个物理符号系统。

推论二:

既然计算机是一个物理符号系统，它就一定能够表现出智能。

推论三:

既然人是一个物理符号系统，计算机也是一个物理符号系统，那么我们就能够用计算机来模拟人的活动。

物理符号系统假设的意义明确地揭示了人工智能研究所依赖的一些根本假定；为早期人工智能的发展奠定了理论基础；,第一部分理论基础,第六章-11,知识表示简介,知识表示的目的不仅仅是为了把知识用数据结构的形式存储在计算机中，而更重要的是能够方便且正确地运用和管理知识。

知识表示方法（知识表示语言）一阶谓词逻辑表示法产生式表示法语义网络表示法框架表示法脚本表示法面向对象表示法等等,第一部分理论基础,第六章-12,知识表示简介,如何评价知识表示语言的优劣？

表现力（expressiveness）和效率（efficiency）是评价知识表示语言的主要尺度。

效率和表现力达到最佳平衡时智能系统设计者的一个主要任务。

例：

数组表示的自然性和高效性。

图基因在转位期中的数字图像,第一部分理论基础,第六章-13,知识表示简介,知识表示语言应该具备的功能：

处理定性的知识。

可以从一系列事实和规则中推断出新的知识。

既可以表示特殊情况，又可以表示一般原则。

捕捉复杂的语义内涵。

允许元级推理。

第一部分理论基础,第六章-14,知识表示简介,处理定性的知识例：

考虑如何组织如图所示桌子上的积木。

谓词演算（Predicatecalculus）:

clear（c）clear（a）ontable（a）ontable（b）on（c,b）cube（b）cube（a）pyramid（c）,图积木世界,第一部分理论基础,第六章-15,知识表示简介,可以从一系列事实和规则中推断出新的知识根据对世界的描述推断出新知识的能力是智能体的一个关键特征。

例：

对于积木世界，判断一块积木是否clear,第一部分理论基础,第六章-16,知识表示简介,既可以表示特殊情况，又可以表示一般原则为了使智能系统尽可能通用，知识表示语言应支持变量注意：

逻辑式程序设计语言中的变量不同于命令式语言中的变量的含义。

没有赋值的概念；变量通过合一（匹配）操作可以与任何东西匹配。

第一部分理论基础,第六章-17,知识表示简介,捕捉复杂的语义内涵很多人工智能问题需要大量结构化的相互关联的知识。

例：

蓝鸟的描述：

“蓝鸫是一种小的蓝颜色的鸟，鸟是一种有羽毛的会飞行的脊椎动物。

”,蓝鸟的语义网络描述,第一部分理论基础,第六章-18,知识表示简介,允许元级推理元知识：

“对自己知道什么的知识”构成的一种更高层次的知识。

一个智能系统不仅必须知道外界事物，而且还要认识到自己知道什么。

不仅要求解决问题而且还要解释出它是如何求解的以及为什么做出某个决策。

例如：

西尔勒的“中文屋子问题”（ChineseRoomProblem）,第一部分理论基础,第六章-19,知识表示简介,麦克德莫特（McDermott1981）成功编写基于知识的程序的关键是选取一种合适的表示工具。

AI更关心定性的问题求解而不是定量问题求解；AI更关心推理而不是演算；AI更关心如何组织庞大的数量变化的知识而不是实现单一的已经具完善定义的算法；Lisp和Prolog是用来实现这些表示的语言。

第一部分理论基础,第六章-20,内容,逻辑程序设计概述知识表示简介谓词演算逻辑谓词演算的语法基于谓词演算的知识表示谓词演算的推理规则知识的利用,第一部分理论基础,第六章-21,引言,这里讨论的谓词演算一阶谓词演算（first-orderpredicatecalculus）全称量化变量和存在量化变量仅可以指向论域中的对象，而不允许指向谓词和函数。

这样的谓词演算语言称为一阶谓词演算。

基于二值逻辑,第一部分理论基础,第六章-22,内容,逻辑程序设计概述知识表示简介谓词演算逻辑谓词演算的语法基于谓词演算的知识表示谓词演算的推理规则知识的利用,第一部分理论基础,第六章-23,1.逻辑,逻辑有多种形态，如二值逻辑/二值图象多值逻辑/灰度图象墨多维逻辑/彩色图象之缺省逻辑/缺省图象舞动态逻辑/动画视频,第一部分理论基础,第六章-24,1.逻辑,逻辑学分为:

形式逻辑研究具有内在同一性和外在确定性的概念、命题之间的必然联系；形式逻辑的数学化得到经典数理逻辑，它是刚性逻辑学（Rigidlogics）。

辨证逻辑研究具有内在矛盾性和外在不确定性的概念、命题之间的必然联系。

辨证逻辑的数学化得到非经典数理逻辑，它是柔性逻辑学（Flexibilitylogics）。

逻辑的发展趋势：

建立统一开放的数理逻辑理论架构，实现数理逻辑的柔性化泛逻辑学（何华灿）,第一部分理论基础,第六章-25,内容,逻辑程序设计概述知识表示简介谓词演算逻辑谓词演算的语法基于谓词演算的知识表示谓词演算的推理规则知识的利用,第一部分理论基础,第六章-26,2.谓词演算的语法,在谓词逻辑中，命题是用谓词来表示的。

命题：

P：

星期二下了雨。

谓词：

weather（tuesday，rain）谓词演算还允许表达式中含有变量可以建立关于实体类的通用断言。

如申明所有的X，X是某一周的一天，weather（X，rain）定义：

谓词演算符号构成谓词演算符号的字符表有以下三部分组成：

英文字母，包括大写和小写。

数字0，19。

下划线_。

谓词演算的符号以字母开始，后面可以跟这些合法字符的任意序列。

第一部分理论基础,第六章-27,2.谓词演算的语法,定义：

符号或项（Term）（注：

项的大小写按照Prolog规范）真值符号：

true和false（保留符号）变量符号:

以大写字母开始的符号表达式。

常量符号:

以小写字母开始的符号表达式。

函数符号:

以小写字母开始的符号表达式。

谓词符号：

以小写字母开始的符号表达式。

例如：

likes（george，kate）%likes/2likes（george，sarah，tuesday）%likes/3likes（X，kate）friends（father_of（david），father_of（kate））,第一部分理论基础,第六章-28,2.谓词演算的语法,谓词和函数从形式上看很相似，容易混淆。

但是，它们是两个完全不同的概念。

谓词的真值是真和假，而函数无真值可言，其值是个体域（值域）中的某个个体。

谓词实现的是从个体域中的个体到T或F的映射，而函数所实现的是从一个个体（定义域）到另一个个体（值域）的映射。

在谓词逻辑中，函数本身不能单独使用，它必须嵌入到谓词之中。

第一部分理论基础,第六章-29,2.谓词演算的语法,由于命题逻辑可看作谓词逻辑的一种特殊形式，因此一阶谓词逻辑中的5个连接词也都适应于命题逻辑，但2个量词仅适应于谓词逻辑。

全程量词：

X命题（x）P（x）为真，当且仅当对论域中的所有x，都有P（x）为真。

命题（x）P（x）为假，当且仅当至少存在一个x0D，使得P（x0）为假。

存在量词：

命题（彐x）P（x）为真，当且仅当至少存在一个x0D，使得P（x0）为真。

命题（彐x）P（x）为假，当且仅当对论域中的所有x，都有P（x）为假。

彐X,第一部分理论基础,第六章-30,2.谓词演算的语法,定义：

谓词演算语句（合式公式）单个原子谓词公式是合式公式。

若A是合式公式，则A也是合式公式。

若A、B都是合式公式，则AB，AB，AB，AB也都是合式公式。

若A是合式公式，x是变量，则（x）A和（彐x）A也都是合式公式。

在合式公式中，连接词之间的优先级别是，,第一部分理论基础,第六章-31,内容,逻辑程序设计概述知识表示简介谓词演算逻辑谓词演算的语法基于谓词演算的知识表示谓词演算的推理规则知识的利用,第一部分理论基础,第六章-32,3.基于谓词演算的知识表示,谓词演算不仅可以用来表示事物的状态、属性、概念等事实性知识，也可以用来表示事物的因果关系，即规则。

对事实性知识，通常是用否定、析取或合取符号连接起来的谓词公式表示。

对事物间的因果关系，通常用蕴含式表示，例如，对“如果x，则y”,可表示为“xy”。

用谓词逻辑表示知识的方法：

根据所表示的知识定义谓词；用连接词或量词把这些谓词连结起来，形成一个谓词公式。

第一部分理论基础,第六章-33,3.基于谓词演算的知识表示,例1用谓词逻辑表示知识“每个人都有一个父亲”。

首先定义谓词：

person（X）：

表示x是人has_father（X,Y）：

表示x有父亲y此时，该知识可用谓词表示为：

（X）（彐Y）（person（X）has_father（X,Y）例2用谓词逻辑表示知识“所有教师都有自己的学生”teacher（X）：

表示x是教师student（Y）：

表示y是学生teachs（X，Y）：

表示x是y的老师（X）（彐Y）（teacher（X）teachs（X,Y）student（Y）,第一部分理论基础,第六章-34,3.基于谓词演算的知识表示,机器人移盒子问题设在一房间里，C处有一个机器人，A和B处各有一张桌子，分别称为A桌和B桌，A桌子上有一盒子，如图所示。

要求机器人从C处出发把盒子从A桌上拿到B桌上，然后再回到C处。

请用谓词逻辑来描述机器人的行动过程。

图机器人移盒子,第一部分理论基础,第六章-35,3.基于谓词演算的知识表示,求解步骤：

在这个例子中，不仅要用谓词公式来描述事物的状态、位置，而且还要用谓词公式表示动作。

为此，需要定义谓词公式如下：

第一部分理论基础,第六章-36,3.基于谓词演算的知识表示,使用规则！

问题的初始状态,问题的目标状态,第一部分理论基础,第六章-37,3.基于谓词演算的知识表示,求解步骤：

机器人行动的目标是把问题的初始状态转换为目标状态，而要实现问题状态的转换需要完成一系列的操作。

对于每个操作，一般都可分为条件和动作两个部分：

条件部分用来说明执行该操作必须具备的先决条件；动作部分给出了该操作对问题状态的改变情况。

条件部分可用谓词公式来表示，动作部分则是通过在执行该操作前的问题状态中删去和增加相应的谓词来实现的。

在本问题中，机器人需要执行以下三个操作：

第一部分理论基础,第六章-38,3.基于谓词演算的知识表示,第一部分理论基础,第六章-39,3.基于谓词演算的知识表示,求解步骤：

创建操作序列1.Beginfromthestartstate；2.Searchforanoperatorwhosepreconditionsaresatisfiedbycurrentstate3.Performtheoperatorandchangestatetoanewone.4.Gotostep2,untilthegoalstateisgenerated.,第一部分理论基础,第六章-40,谓词逻辑表示的应用,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,第一部分理论基础,第六章-41,内容,逻辑程序设计概述知识表示简介谓词演算逻辑谓词演算的语法基于谓词演算的知识表示谓词演算的推理规则知识的利用,第一部分理论基础,第六章-42,4.谓词演算的推理规则,谓词公式的等价性和永真蕴含性可分别用相应的等价式和永真蕴含式来表示，这些等价式和永真蕴含式都是演绎推理的主要依据，因此也称它们为推理规则。

1.定义：

谓词公式的等价性设P与Q是D上的两个谓词公式，若对D上的任意解释，P与Q都有相同的真值，则称P与Q在D上是等价的。

如果D是任意非空个体域，则称P与Q是等价的，记作PQ。

第一部分理论基础,第六章-43,4.谓词演算的推理规则,双重否定率：

交换率：

结合率：

分配率：

德摩根定律：

连词化归率:

吸收率：

补余率：

量词转换率：

量词分配率：

和,和,第一部分理论基础,第六章-44,4.谓词演算的推理规则,2.定义：

谓词公式的永真蕴含性对谓词公式P和Q，如果PQ永真，则称P永真蕴含Q，且称Q为P的逻辑结论，P为Q的前提，记作P=Q。

化简式（与消除）：

PQ=P和PQ=Q附加式：

P=PQ和Q=PQ析取三段论：

P，PVQ=Q取式假言推理：

P，PQ=Q拒式假言推理：

Q，PQ=P假言三段论：

PQ，QR=PR二难推理：

PQ，PR，QR=R全称固化：

（x）P（x）=P（a）存在固化：

（x）P（x）=P（a）,第一部分理论基础,第六章-45,内容,逻辑程序设计概述知识表示简介谓词演算知识的利用搜索推理自然演绎推理置换与合一归结演绎推理,第一部分理论基础,第六章-46,1.引言,知识的利用：

即基于对某个封闭世界已表示的知识的处理，以求解特定的问题。

搜索：

根据问题的实际情况，不断寻找可利用知识，从而构造一条代价最小的推理路线，使问题得以解决的过程，称为搜索。

盲目搜索：

深度优先搜索、宽度优先搜索；启发式搜索：

最佳优先搜索、A*算法；推理：

按照某种策略从已知事实出发去推出结论的过程问题解决的过程（思维过程）。

自然演绎推理归结演绎推理（Prolog语言的推理机制）合一（匹配）操作；推理（搜索）方向：

深度优先；回溯机制；,第一部分理论基础,第六章-47,2.搜索,搜索的基础是图论例：

九宫游戏的状态空间图,第一部分理论基础,第六章-48,2.搜索,例：

基于九宫游戏状态空间图的启发式搜索通过对称抵消后的九宫游戏状态空间的前三层,12*7！

第一部分理论基础,第六章-49,2.搜索,例：

基于九宫游戏状态空间图的启发式搜索采用如下“启发”裁减九宫游戏状态空间,顶角方格有三种胜利路线,中央方格有四种胜利路线,边方格有两种胜利路线,第一部分理论基础,第六章-50,2.搜索,第一部分理论基础,第六章-51,2.搜索,图搜索的实现问题由来：

问题求解程序能否被赋予可靠的机制（不犯任何错误）穿越状态空间达到预期的目标状态，并建立解路径？

问题求解程序必须考虑穿越空间的不同路径直到找到目标。

回溯（Backtracking）：

是系统地穿越状态空间的所有路径的一种技术。

可以在面向堆栈的递归环境中自然地实现。

回溯搜索：

从起始状态出发沿一条路径前进直到要么达到目标，要么到达一个“死端”。

如果发现目标，退出搜索并返回解路径；如果到达一个死端，那么便回溯到路径上含有未分析过兄弟的最近节点，并沿这个分支继续下去。

第一部分理论基础,第六章-52,2.搜索,第一部分理论基础,第六章-53,2.搜索,对假想状态空间的回溯搜索,第一部分理论基础,第六章-54,内容,逻辑程序设计概述知识表示简介谓词演算知识的利用搜索推理自然演绎推理置换与合一自然演绎推理评析推理方向归结演绎推理,第一部分理论基础,第六章-55,1.自然演绎推理,自然演绎推理从一组已知为真的事实出发，直接运用经典逻辑中的推理规则推出结论的过程。

在这种推理中，最基本的推理规则是三段论推理，它包括取式假言推理、拒式假言推理、假言三段论等。

第一部分理论基础,第六章-56,1.自然演绎推理,【例】设已知如下事实：

A，B，AC，BCD，DQ求证：

Q为真。

证明：

A，AC=C,B，C=BC,BC，BCD=D,D，DQ=Q,取式假言推理,引入合取词,取式假言推理,取式假言推理,第一部分理论基础,第六章-57,1.1置换与合一,例如有如下三段论：

“所有人会死；苏格拉底是人，所以苏格拉底会死。

”,这种寻找项对变元的置换，使谓词一致的过程叫做合一的过程（合一算法）。

为了应用推理规则（例如：

取式假言推理），推理系统必须能够判断两个表达式何时相同，也就是这两个表达式何时匹配。

第一部分理论基础,第六章-58,1.1置换与合一,置换（Substitution）置换可以简单的理解为是在一个谓词公式中用置换项去替换变量。

其形式定义如下：

置换是形如t1/x1,t2/x2,tn/xn的有限集合。

t1,t2,tn是项；x1,x2,xn是互不相同的变元；ti/xi表示用ti置换xi。

并且要求ti与xi不能相同，xi不能循环地出现在另一个ti中。

例如：

ax，cy，f（b）z是一个置换。

例如：

g（y）/x，f（x）/y不是一个置换。

通常，置换是用希腊字母、等来表示的。

=t1/x1,t2/x2,tn/xn,第一部分理论基础,第六章-59,1.1置换与合一,合一（Unifier）合一可以简单地理解为是寻找项对变量的置换，使两个谓词公式一致。

其形式定义如下:

设有公式集F=F1，F2，Fn，若存在一个置换，可使F1=F2=F3=Fn。

则称是F的一个合一。

称F1,F2,.,Fn是可合一的。

公式集F=man（X），man（socrates）中的两个公式是可合一的，置换=scorates/X是该公式集的一个合一。

一个公式集的合一可能不是唯一的。

第一部分理论基础,第六章-60,1.1置换与合一,定义3设是公式集F的一个合一,如果对F的任一个合一都存在另外一个合一，可使=,则称是一个最一般合一（MostGeneralUnifier.简记MGU）。

例如，对于公式集F=P（X），P（Y）对于任意常量表达式，比如=jack/X，jack/Y，都会获得成功。

但是，不是最一般合一。

可以使用任意变量，产生更一般的合一=Z/X，Z/Y第一种置换得到的解总是受约束的，常量jack限制了最终的推理，即降低了结果的一般性。

第一部分理论基础,第六章-61,1.1置换与合一,最一般合一算法（unify）计算两个谓词演算表达式间的合一置换（当可能合一时）。

unify函数以两个谓词演算表达式为参数，返回最一般合一置换或常量FAIL（当不可能合一时）。

该函数是一个递归函数，当遇到以下两种情况中的任意一种时递归结束：

参数是一个符号（谓词、函数名、常量或变量）。

表达式的元素都已经被匹配过。

该算法用列表语法表示谓词公式语法。

例如：

p（a，b）（pab）p（f（a），g（X，Y）（p（fa）（gXY）,第一部分理论基础,第六章-66,1.1置换与合一,【例】基于谓词逻辑演算的财务顾问该财务顾问的功能是帮助用户根据个人的年收入及已存款数量决策应该继续存款还是向股票市场投资。

投资策略的标准如下：

存款数额还不充足的个体始终该把提高存款额作为他们的首选目标，无论他们的收入如何。

具有充足存款和充足收入的个体应该考虑风险较高但潜在投资收益也更高的股票市场。

收入较低并且已经具有充足存款的个体可以考虑把他们的剩余收入在存款和股票间分摊，以便既能提高存款数额又能尝试通过股票提高收入。

存款和收入的充足性可以由个体要供养的人数决定。

充足的存款：

供养一个人至少要在银行存款5000美元。

充足的收入：

收入必须是稳定的，而且年收入至少是15000美元，在加额外的给每个要供养的人4000美元。

初始逻辑系统（知识库）：

12.income（inadequate）,13.savings_account（adequate）,X,第一部分理论基础,第六章-68,1.2自然演绎推理评析,分析：

优点：

定理证明过程自然，易于理解，并且有丰富的推理规则可用。

缺点：

容易产生知识爆炸，推理过程中得到的中间结论一般按指数规律递增，对于复杂问题的推理不利，甚至难以实现。

第一部分理论基础,第六章-69,1.3推理方向,推理方向数据驱动搜索（data-drivensearch）正向追索（forwardchaining），问题求解程序从问题的给定事实和改变状态的合法移动和规则的集合入手。

然后把规则应用到事实产生新的事实，接下来新的事实又被规则用来产生更多新的事实，搜索如此进行下去，直到产生满足目标条件的一条路径。

目标驱动搜索（goal-drivensearch）反向追索（backwardchaining），从求解的目标着手。

先分析怎样使用合法的移动来产生这个目标，并求出要应用这些移动必须具备的条件。

这些条件成为要搜索的新目标（子目标）。

然后继续反向追溯相继的子目标，直至返回到问题中的事实。

这样便找到了从问题到目标的移动会规则链。

第一部分理论基础,第六章-70,1.3推理方向,【例】基于谓词逻辑演算的财务顾问基于目标驱动的带回溯的深度优先搜索,X,第一部分理论基础,第六章-71,1.3推理方向,假定某个投资个体要供养2人，有20000美元存款，30000美元稳定收入。

咨询的目标找到一种投资方案：

*失败*,财务顾问程序搜索的与/或树,成功：

X=stocks,*失败并回溯*,第一部分理论基础,第六章-73,内容,逻辑程序设计概述知识表示简介谓词演算知识的利用搜索推理自然演绎推理归结演绎推理简介鲁宾逊归结原理归结演绎推理子句集化简,第一部分理论基础,第六章-74,1.简介,归结演绎推理是一种基于鲁宾逊归结原理的机器推理技术。

鲁宾逊归结原理亦称为消解原理，是鲁宾逊于1965年在海伯伦理论的基础上提出的一种基于逻辑的“反证法”。

海伯伦理论为机器推理奠定了理论基础，鲁宾逊归结原理使定理证明的自动化成为现实。

他们的这些研究成果在人工智能的发展史上都占有很重要的历史地位。

第一部分理论基础,第六章-75,2.鲁宾逊归结原理,相关概念：

文字原子谓词公式及其否定统称为文字。

例如：

P（x）、Q（y）、P（x）、Q（y）Horn子句（归结的对象）任何文字的析取式称为子句。

例如，P（x）Q（y），P（x,f（x）Q（x,g（x）空子句不包含任何文字的子句称为空子句。

由于空子句不含有任何文字，也就不能被任何解释所满足，因此空子句是永假的，不可满足的。

空子句一般被记为或NIL。

Horn子句集由Horn子句或空子句所构成的集合。

第一部分理论基础,第六章-76,2.鲁宾逊归结原理