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

10七月2023程序设计语言范型

ProgrammingLanguagesParadigms教师：张荣华华北电力大学计算机系软件教研室〔保定〕

逻辑程序设计语言范型逻辑程序设计理论根底第三局部第六章逻辑程序设计理论根底第六章-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子句集化简逻辑程序设计理论根底第六章-41.逻辑程序设计概述逻辑程序设计逻辑程序设计支持说明性程序设计范型根据问题的高层描述来构建程序告诉计算机“什么是真的〞和“需要做什么〞，而不是“怎样做〞。程序员把精力放在问题〔封闭的问题世界〕的描述上，而不是写一些诸如“下一步做什么〞之类的底层算法指令。Prolog是目前唯一广泛使用的逻辑程序设计语言Prolog〔ProgramminginLogic〕20世纪70年代初、法国马赛大学主要应用于人工智能〔人类智能活动的模拟〕领域相关问题的求解。易于表达人的逻辑思维逻辑程序设计理论根底第六章-51.逻辑程序设计概述【例1】：水平线与垂直线问题。使用两个谓词：vertical/2和horizontal/2vertical(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

;

nohorizontal(line(point(2,3),P)).

P

=

point(_G434,3)

;

no逻辑程序设计理论根底第六章-61.逻辑程序设计概述【例2】求解以下六个英语单词的纵横字谜问题。abalone,abandon,anagram,connect,elegant,enhance事实规那么逻辑程序设计理论根底第六章-71.逻辑程序设计概述aabloneanagramocnnectaadneeeathneaadnbonleeatngnehnecaaaoeaarmcnet查询/目标逻辑程序设计理论根底第六章-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子句集化简逻辑程序设计理论根底第六章-92.知识的表示知识阈值理论知识是一切智能行为的根底智能取决于知识的数量及其可运用的程度。要使计算机具有智能，就必须使它具有知识。知识表示方法〔知识表示语言〕谓词演算〔一阶谓词逻辑表示法〕产生式表示法语义网络表示法框架表示法脚本表示法面向对象表示法等等……逻辑程序设计理论根底第六章-102.知识的表示选择知识表示方法的重要性【例】缺角棋盘问题逻辑程序设计理论根底第六章-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子句集化简逻辑程序设计理论根底第六章-122.1谓词演算这里讨论的谓词演算⑴一阶谓词演算〔first-orderpredicatecalculus〕全称量化变量和存在量化变量仅可以指向论域中的对象，而不允许指向谓词和函数。这样的谓词演算语言称为一阶谓词演算。

⑵二值逻辑不讨论其它逻辑形态多值逻辑、多维逻辑、缺省逻辑、动态逻辑逻辑程序设计理论根底第六章-132.1谓词演算【例】用谓词表示命题P：星期二下了雨。谓词表示：weather〔tuesday，rain〕允许使用变量建立关于实体类的通用断言weather〔X，rain〕谓词演算符号〔项〕〔以Prolog语言为例〕由以下三局部组成：①英文字母，包括大写和小写。②数字0，1……9。③下划线_。以字母开始，后面可以跟这些合法字符的任意序列。逻辑程序设计理论根底第六章-142.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子句集化简逻辑程序设计理论根底第六章-162.2基于谓词演算的知识表示【例1】事实性知识：friends〔father_of(david)，father_of(kate)〕【例2】规那么性知识：“所有的教师都有自己的学生〞⑴根据所表示的知识定义谓词teacher〔X〕：表示X是教师student〔Y〕：表示Y是学生teach〔X，Y〕：表示X是Y的老师⑵用2个量词和5个连接词把这些谓词连结成语句

逻辑程序设计理论根底第六章-172.2基于谓词演算的知识表示【例3】机器人移盒子问题设在一房间里，C处有一个机器人，A和B处各有一张桌子，分别称为A桌和B桌，A桌子上有一盒子，如以下图所示。要求机器人从C处出发把盒子从A桌上拿到B桌上，然后再回到C处。请用谓词逻辑来描述机器人的行动过程。

ABCStartstateAT（robot,C）EMPTY（robot）ON（box，A）TABLE（A）TABLE（B）GoalstateAT（robot,C）EMPTY（robot）ON（box，B）TABLE（A）TABLE（B）使用规那么！操作前提条件删除list项增加list项Goto(x,y)AT（robot,x）AT（robot,x）AT（robot,y）Pickup(x)ON(box,x),TABLE(x),AT(robot,x),Empty(robot)Empty(robot),ON(box,x)HOLDS(robot,box)Setdown(x)HOLDS(robot,box)AT（robot,x),TABLE(x)HOLDS(robot,box)ON(box,x),Empty(robot)逻辑程序设计理论根底第六章-19谓词逻辑表示的应用StartStateAT（robot,c）EMPTY（robot）ON（box，A）TABLE（A）TABLE（B）GOTO(x,y)C/x,A/yState1AT(robot,A)EMPTY(robot)ON（box，A）TABLE（A）TABLE（B）State2AT(robot,A)HOLDS(robot,box)TABLE（A）TABLE（B）StartPICKUP(x)A/xGOTO(x,y)A/x,B/yState3AT(robot,B)HOLDS(robot,box)TABLE（A）TABLE（B）State4AT(robot,B)EMPTY（robot）ON（box，B）TABLE（A）TABLE（B）SETDOWN(x)B/xGOTO(x,y)B/x,C/yGoalStateAT(robot,C)EMPTY（robot）ON（box，B）TABLE（A）TABLE（B）逻辑程序设计理论根底第六章-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子句集化简逻辑程序设计理论根底第六章-212.3谓词演算推理规那么谓词公式的永真蕴含性对谓词公式P和Q，如果P→Q永真，那么称P永真蕴含Q，且称Q为P的逻辑结论，P为Q的前提，记作P=>Q。①化简式〔与消除〕：P∧Q=>P和P∧Q=>Q②附加式：P=>P∨Q和Q=>P∨Q③析取三段论：P，PVQ=>Q④取式假言推理：P，P→Q=>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子句集化简逻辑程序设计理论根底第六章-233.知识的利用知识的利用：基于对某个封闭世界已表示的知识的处理，以求解特定的问题。①搜索：根据问题的实际情况，不断寻找可利用知识，从而构造一条代价最小的推理路线，使问题得以解决的过程，称为搜索。盲目搜索：深度优先搜索、宽度优先搜索；启发式搜索：最正确优先搜索、A*算法；②推理：按照某种策略从事实出发去推出结论的过程——问题求解的过程〔思维过程〕。自然演绎推理归结演绎推理〔Prolog语言采用的推理机制，重点〕合一〔匹配〕操作；推理〔搜索〕方向：深度优先；回溯机制；逻辑程序设计理论根底第六章-24内容1.逻辑程序设计概述2.知识的表示3.知识的利用3.1搜索3.2推理3.2.1置换与合一3.2.2自然演绎推理3.2.3归结演绎推理3.2.4子句集化简逻辑程序设计理论根底第六章-253.1搜索搜索的根底是图论例：九宫游戏的状态空间图逻辑程序设计理论根底第六章-26基于图搜索的问题求解程序问题求解程序能否被赋予可靠的机制〔不犯任何错误〕穿越状态空间到达预期的目标状态，并建立解路径？回溯：系统地穿越状态空间的所有路径的一种技术。逻辑程序设计理论根底第六章-273.1搜索对假想状态空间的深度优先搜索〔回溯〕逻辑程序设计理论根底第六章-28内容1.逻辑程序设计概述2.知识的表示3.知识的利用3.1搜索3.2推理3.2.1置换与合一3.2.2自然演绎推理3.2.3归结演绎推理3.2.4子句集化简逻辑程序设计理论根底第六章-293.2.1置换与合一【例】有如下三段论：“所有人会死；苏格拉底是人，所以苏格拉底会死。〞

这种寻找项对变量的置换，使谓词一致的过程叫做合一的过程〔合一算法〕项：常量、函数或其他变量公式集F={man(X)，man(socrates)}中的两个公式是可合一的，置换θ=scorates/X是该公式集的一个合一。为了应用推理规那么进行推理，推理机必须能够判断两个表达式是否相同〔匹配〕。逻辑程序设计理论根底第六章-303.2.1置换与合一合一算法unify〔E1，E2〕计算两个谓词演算公式间的合一置换。返回合一置换或常量FAIL〔当不可能合一时〕【例】使用用列表语法表示谓词公式语法。E：p〔f〔a〕，g〔X，Y〕〕〔p〔fa〕〔gXY〕〕逻辑程序设计理论根底第六章-34内容1.逻辑程序设计概述2.知识的表示3.知识的利用3.1搜索3.2推理3.2.1置换与合一3.2.2自然演绎推理3.2.3归结演绎推理3.2.4子句集化简逻辑程序设计理论根底第六章-35

3.2.2自然演绎推理自然演绎推理从一组为真的事实出发，直接运用经典逻辑中的推理规那么推出结论的过程。①化简式〔与消除〕：P∧Q=>P和P∧Q=>Q②附加式：P=>P∨Q和Q=>P∨Q③析取三段论：P，PVQ=>Q④取式假言推理：P，P→Q=>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美元。minsavings(X)≡5000*Xminincome(X)≡15000+(4000*X)其中：初始逻辑系统〔知识库〕：12.income(inadequate)13.savings_account(adequate)X逻辑程序设计理论根底第六章-38

3.2.2自然演绎推理推理方向①数据驱动搜索〔data-drivensearch〕正向追索〔forwardchaining〕，问题求解程序从问题的给定事实和改变状态的合法移动和规那么的集合入手。然后把规那么应用到事实产生新的事实，接下来新的事实又被规那么用来产生更多新的事实，搜索如此进行下去，直到产生满足目标条件的一条路径。②目标驱动搜索〔goal-drivensearch〕反向追索〔backwardchaining〕，从求解的目标着手。先分析怎样使用合法的移动来产生这个目标，并求出要应用这些移动必须具备的条件。这些条件成为要搜索的新目标〔子目标〕。然后继续反向追溯相继的子目标，直至返回到问题中的事实。这样便找到了从问题到目标的移动规那么链。逻辑程序设计理论根底第六章-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子句集化简逻辑程序设计理论根底第六章-433.2.3归结演绎推理归结演绎推理是一种基于鲁宾逊归结原理的机器推理技术，使机器定理证明的自动化成为现实。鲁宾逊归结原理亦称为消解原理，是鲁宾逊于1965年在海伯伦理论的根底上提出的一种基于逻辑的“反证法〞。逻辑程序设计理论根底第六章-443.2.3归结演绎推理相关概念： 文字原子谓词公式及其否认统称为文字。例如：P(x)、Q(y)、P(x)、Q(y)子句〔归结的对象〕任何文字的析取式称为子句。例如，P(x)∨Q(y)，P(x,f(x))∨Q(x,g(x))空子句不包含任何文字的子句称为空子句。由于空子句不含有任何文字，也就不能被任何解释所满足，因此空子句是永假的，不可满足的。空子句一般被记为□或NIL。子句集由Horn子句或空子句所构成的集合。逻辑程序设计理论根底第六章-453.2.3归结演绎推理鲁宾逊归结原理如果存在某个公理

和，那么

在逻辑上成立。称是和的消解式。归结演绎推理〔反证法〕的步骤：①将前提和公理转化为子句的形式。②将要证明的结论取反，并转化为子句形式，与第①步形成的子句共同构成子句集。③利用鲁宾逊归结原理归结这些子句，生成可以从逻辑上推导出的新子句。④通过生成空子句得出矛盾。【例】①Fido是狗②所有的狗都是动物③所有的动物都会死证明：Fido会死。证明一〔自然演绎推理〕①所有的狗都是动物：②Fido是狗：③取式假言推理和{fido/X}：④所有的动物都会死：⑤取式假言推理和{fido/Y}：证明二〔归结反驳推理〕①②③④谓词形式子句形式逻辑程序设计理论根底第六章-473.2.3归结演绎推理子句集“死狗〞问题的归结证明□逻辑程序设计理论根底第六章-48内容1.逻辑程序设计概述2.知识的表示3.知识的利用3.1搜索3.2推理3.2.1置换与合一3.2