人工智能及其应用蔡自兴.pptx

《人工智能及其应用蔡自兴.pptx》由会员分享，可在线阅读，更多相关《人工智能及其应用蔡自兴.pptx（78页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1人工智能及其应用蔡自兴人工智能及其应用蔡自兴22.1状态空间法状态空间法（State Space Representation）n n问题求解技术主要是两个方面：问题求解技术主要是两个方面：问题求解技术主要是两个方面：问题求解技术主要是两个方面：n n问题的表示问题的表示问题的表示问题的表示n n求解的方法求解的方法求解的方法求解的方法n n状态空间法状态空间法状态空间法状态空间法n n状态状态状态状态（statestate）:表示问题解法中每一步问题状况表示问题解法中每一步问题状况表示问题解法中每一步问题状况表示问题解法中每一步问题状况的的的的数据结构数据结构数据结构数据结构n n算

2、符算符算符算符（operator):operator):把问题从一种状态变换为另一把问题从一种状态变换为另一把问题从一种状态变换为另一把问题从一种状态变换为另一种状态的种状态的种状态的种状态的手段手段手段手段n n状态空间方法状态空间方法状态空间方法状态空间方法:基于解答空间的问题表示和求解基于解答空间的问题表示和求解基于解答空间的问题表示和求解基于解答空间的问题表示和求解方法，它是以方法，它是以方法，它是以方法，它是以状态和算符状态和算符状态和算符状态和算符为基础来表示和求解为基础来表示和求解为基础来表示和求解为基础来表示和求解问题的问题的问题的问题的第1页/共78页32.1.1 问题状态描

3、述问题状态描述n n定义定义n n状态状态(State)(State)：描述某类不同事描述某类不同事物间的差别而引入的一组最少物间的差别而引入的一组最少变量变量q q0 0，q q1 1，q qn n的有序集合。的有序集合。n n算符算符(Operate)(Operate)：使问题从一种使问题从一种状态变化为另一种状态的手段状态变化为另一种状态的手段称为操作符或算符。称为操作符或算符。n n问题的状态空间问题的状态空间(State Space)(State Space)：是一个表示该问题全部可能是一个表示该问题全部可能状态及其关系的图，它包含三状态及其关系的图，它包含三种说明的集合，即三元状态

4、种说明的集合，即三元状态（S S，F F，GG）。2.1 状态空间法第2页/共78页4状态空间表示概念详释状态空间表示概念详释状态空间表示概念详释状态空间表示概念详释n n状态空间法：从某个初始状态开始，每状态空间法：从某个初始状态开始，每次加一个操作符，递增的建立起操作符次加一个操作符，递增的建立起操作符的实验序列，直到达到目标状态止。的实验序列，直到达到目标状态止。n n例如下棋、迷宫及各种游戏。例如下棋、迷宫及各种游戏。Original StateMiddleStateGoalState2.1 状态空间法第3页/共78页5例例:三数码难题三数码难题（3 puzzle problem）12

5、3123123312312312初始棋局目标棋局2.1 状态空间法第4页/共78页6n n有向图有向图 一对节点用弧线连接起来，从一个节点指向另一对节点用弧线连接起来，从一个节点指向另一个节点这种图叫做有向图。一个节点这种图叫做有向图。n n路径路径 某个节点序列（某个节点序列（ni1ni1，ni2ni2，niknik）当）当 j j=2=2，3 3，k k时，如果对于每一个时，如果对于每一个nini，j-1j-1都都有一个后继节点有一个后继节点nini，j j存在，那么就把这个节点存在，那么就把这个节点序列叫做从节点序列叫做从节点ni1ni1至节点至节点niknik的长度为的长度为k k的路

6、径的路径n n代价代价 用用c c（nini，njnj）来表示从节点）来表示从节点nini指向节点指向节点njnj的那段弧线的代价。两点间路径的代价等于连的那段弧线的代价。两点间路径的代价等于连接该路径上各节点的所有弧线代价之和接该路径上各节点的所有弧线代价之和.2.1.2 状态图示法状态图示法2.1 状态空间法AB第5页/共78页7n n图的显示说明图的显示说明 对于显式说明，各节点及其具对于显式说明，各节点及其具有代价的弧线由一张表明确给出。此表可能列有代价的弧线由一张表明确给出。此表可能列出该图中的每一节点、它的后继节点以及连接出该图中的每一节点、它的后继节点以及连接弧线的代价弧线的代价

7、(举例：举例：举例：举例：邻接表，邻接矩阵邻接表，邻接矩阵)n n图的隐示说明图的隐示说明 说明节点的无限集合说明节点的无限集合si si作为作为起始节点是已知的。后继节点算符起始节点是已知的。后继节点算符（gammagamma）也是已知的，它能作用于任一节）也是已知的，它能作用于任一节点以产生该节点的全部后继节点和各连接弧线点以产生该节点的全部后继节点和各连接弧线的代价。（的代价。（举例：举例：举例：举例：棋局）棋局）n n表示方法的多样性表示方法的多样性 如十五数码难题中如十五数码难题中n n规则规则1 1：移动数码（：移动数码（15X415X4条规则）条规则）n n规则规则2 2：移动空

8、格（：移动空格（4 4条规则）条规则）第6页/共78页8产生式系统搜索过产生式系统搜索过程描述程描述n n产生式系统（production system）n n一个总数据库：一个总数据库：它含有与具体任务它含有与具体任务有关的信息随着应用情况的不有关的信息随着应用情况的不同，这些数据库可能简单，或同，这些数据库可能简单，或许复杂许复杂。n n一套规则：一套规则：它对数据库进行操作它对数据库进行操作运算。每条规则由左部鉴别规运算。每条规则由左部鉴别规则的则的适用性适用性适用性适用性或先决条件以及右或先决条件以及右部描述规则应用时所完成的部描述规则应用时所完成的动动动动作作作作。n n一个控制策略

9、：一个控制策略：它确定应该采用哪它确定应该采用哪一条适用规则，而且当数据库一条适用规则，而且当数据库的终止条件满足时，就停止计的终止条件满足时，就停止计算。算。2.1 状态空间法第7页/共78页9 状态空间表示实例状态空间表示实例（1 1）n n例：猴子和香蕉问题例：猴子和香蕉问题2.1 状态空间法第8页/共78页10解题过程解题过程n n 用一个四元表列（W，x，Y，z）来表示这个问题状态.n n W W 猴子的水平位置猴子的水平位置n nx x 当猴子在箱子顶上时取当猴子在箱子顶上时取 x x=1=1；否则取；否则取 x=0 x=0n n Y Y 箱子的水平位置箱子的水平位置n nz z

10、当猴子摘到香蕉时当猴子摘到香蕉时取取 z=1z=1；否则取；否则取 z=0z=0n n这个问题的操作（算符）如下：n n gotogoto（U U）表示）表示猴子走到水平位置猴子走到水平位置U Un n或者用产生式规则表示为或者用产生式规则表示为（W，0，Y，z）goto（U）（U，0，Y，z）2.1 状态空间法第9页/共78页11n npushbox（V）猴子把箱子推到水平位置V，即有（WW，0 0，WW，z z）pushboxpushbox（V V）（V V，0 0，V V，z z）应当注意的是，要应用算符应当注意的是，要应用算符pushboxpushbox（V V），就要求），就要求产生

11、式规则的左边，猴子与箱子必须在同一位置产生式规则的左边，猴子与箱子必须在同一位置上，并且，猴子不是箱子顶上。这种强加于操作上，并且，猴子不是箱子顶上。这种强加于操作的适用性条件，叫做产生式规则的的适用性条件，叫做产生式规则的先决条件先决条件n nclimbbox猴子爬上箱顶，即有（WW，0 0，WW，z z）climbbox climbbox （WW，1 1，WW，z z）提问提问：应用算符：应用算符climbboxclimbbox的先决条件是什么？的先决条件是什么？2.1 状态空间法第10页/共78页12n ngraspgrasp猴子摘到香蕉，即有猴子摘到香蕉，即有（c c，1 1，c c，

12、0 0）grasp grasp （c c，1 1，c c，1 1）令初始状态为令初始状态为令初始状态为令初始状态为(a(a(a(a，0 0 0 0，b b b b，0)0)0)0)。这时，。这时，。这时，。这时，goto(U)goto(U)goto(U)goto(U)是唯是唯是唯是唯一适用的操作，并导致下一状态一适用的操作，并导致下一状态一适用的操作，并导致下一状态一适用的操作，并导致下一状态(U(U(U(U，0 0 0 0，b,0)b,0)b,0)b,0)。现。现。现。现在有在有在有在有3 3 3 3个适用的操作，即个适用的操作，即个适用的操作，即个适用的操作，即goto(U)goto(U)

13、goto(U)goto(U)，pushbox(V)pushbox(V)pushbox(V)pushbox(V)和和和和climbbox(climbbox(climbbox(climbbox(若若若若U=b)U=b)U=b)U=b)。把所有适用的操作继续应用于。把所有适用的操作继续应用于。把所有适用的操作继续应用于。把所有适用的操作继续应用于每个状态，我们就能够得到状态空间图，如下图所每个状态，我们就能够得到状态空间图，如下图所每个状态，我们就能够得到状态空间图，如下图所每个状态，我们就能够得到状态空间图，如下图所示。从图不难看出，把该示。从图不难看出，把该示。从图不难看出，把该示。从图不难看出

14、，把该初始状态变换为目标状态初始状态变换为目标状态初始状态变换为目标状态初始状态变换为目标状态的操作序列的操作序列的操作序列的操作序列为为为为 goto(b),push box(c),climbbox,grasp2.1 状态空间法第11页/共78页13(b，1，b，0)（U，0，b，0）（V，0，V，0）（c，1，c，0）（U，0，V，0）（c，1，c，1）（a，0，b，0）目标状态目标状态goto（U）goto（U）U=b，climbboxgoto（U）U=bpushbox（V）猴子和香蕉问题的状态空间图猴子和香蕉问题的状态空间图goto（U）U=V2.1 状态空间法第12页/共78页14猴

15、子和香蕉问题自猴子和香蕉问题自动演示：动演示：猴子猴子香蕉香蕉箱子箱子 猴子猴子香蕉香蕉箱子箱子 Ha!Ha!2.1 状态空间法第13页/共78页15状态空间表示实例（状态空间表示实例（2 2）n n推销员旅行问题推销员旅行问题一个推销员计划出访推销产品。他从一个城市一个推销员计划出访推销产品。他从一个城市(如如 A)A)出发出发 ,访问每访问每个城市一次个城市一次 ,且最多一次且最多一次 ,然后然后 A A返回城市返回城市 A A。要求寻找最短路要求寻找最短路线线 ,如图如图 2.3 2.3 所示。为了确定这个问题所示。为了确定这个问题 ,作如下规定作如下规定 :(1)(1)总数据库是到目前

16、为止所访问过的城市表总数据库是到目前为止所访问过的城市表 .初始数据库被描述为初始数据库被描述为表表 (A)(A)。不允许目录表中任一城市出现多于一次不允许目录表中任一城市出现多于一次 ,只有城市只有城市 A A 例例外外 ,但也只有当所有其他城市均已出现之后但也只有当所有其他城市均已出现之后 ,才能才能 再次出现再次出现 A A。(2)(2)规规则则对对应应于于决决策策 :即即下下一一步步走走向向城城市市 A;A;下下一一步步走走向向城城市市 B;B;下下一一步步走走向向城城市市E E。一一条条规规则则除除非非能能够够把把某某个个数数据据库库变变为为一一个个合合法法数数据据库库 ,否否则则就

17、就不不适适用用于于这这个个数数据据 库库。例例如如 ,应应用用 下下一一步步走走向向城城市市 A A 这这条条规规则则就就不不适适用用于于尚尚未未出出现现所所有有其其他他城城市市的的任任一一 数据库。数据库。(3)(3)任一以任一以 A A 为起点和终点为起点和终点,并出现所有其他城市的总数据库并出现所有其他城市的总数据库,都满都满足终止条件。可以使用足终止条件。可以使用下下图的距离图表来计算任一旅程的总距图的距离图表来计算任一旅程的总距离。提出作为解答的任一旅程离。提出作为解答的任一旅程,必须是具有最短距离的旅程。必须是具有最短距离的旅程。2.1 状态空间法第14页/共78页16ABDE(A

18、CDEBA)推销员旅行问题状态空间图(A)起始节点2.1 状态空间法第15页/共78页172.2 问题归约法问题归约法（Problem Reduction Representation）问题归约法思想问题归约法思想问题归约法思想问题归约法思想 先把问题分解为子问题及子先把问题分解为子问题及子先把问题分解为子问题及子先把问题分解为子问题及子-子问题，然后解决较小子问题，然后解决较小子问题，然后解决较小子问题，然后解决较小的问题。对该问题的某个具体子集的解答就意味着对原的问题。对该问题的某个具体子集的解答就意味着对原的问题。对该问题的某个具体子集的解答就意味着对原的问题。对该问题的某个具体子集的解

19、答就意味着对原始问题的一个解答始问题的一个解答始问题的一个解答始问题的一个解答子问题子问题1子问题子问题n原始问题原始问题子问题集本本原原问问题题第16页/共78页18n n 问题归约表示的组成部分：n n（1 1）一个初始问题描述；）一个初始问题描述；n n（2 2）一套把问题变换为子）一套把问题变换为子问题的操作符；问题的操作符；n n（3 3）一套本原问题描述。）一套本原问题描述。n n问题归约的实质：n n从目标从目标(要解决的问题要解决的问题)出发出发逆向推理，建立子问题以逆向推理，建立子问题以及子问题的子问题，直至及子问题的子问题，直至最后把初始问题归约为一最后把初始问题归约为一个

20、平凡的本原问题集合。个平凡的本原问题集合。2.2 问题规约法第17页/共78页192.2.1 问题归约描述问题归约描述（Problem Reduction Description）n n梵塔难题123CBA2.2 问题规约法思考：用状态空间法有多少个节点？为什么？第18页/共78页20解题过程解题过程n n将原始问题归约为一个较简单问题集合n n将原始梵塔难题归约（简化）为下列子难题n n移动圆盘移动圆盘移动圆盘移动圆盘A A A A和和和和B B B B至柱子至柱子至柱子至柱子2 2 2 2的双圆盘难题的双圆盘难题的双圆盘难题的双圆盘难题n n移动圆盘移动圆盘移动圆盘移动圆盘C C C C至

21、柱子至柱子至柱子至柱子3 3 3 3的单圆盘难题的单圆盘难题的单圆盘难题的单圆盘难题n n移动圆盘移动圆盘移动圆盘移动圆盘A A A A和和和和B B B B至柱子至柱子至柱子至柱子3 3 3 3的双圆盘难题的双圆盘难题的双圆盘难题的双圆盘难题n n详细过程参看下图详细过程参看下图详细过程参看下图详细过程参看下图第19页/共78页21解题过程（解题过程（3个圆盘个圆盘问题）问题）1231231231231231231232.2 问题规约法123第20页/共78页22梵塔问题归约图梵塔问题归约图2.2 问题规约法第21页/共78页23多圆盘梵塔难题思考？多圆盘梵塔难题思考？多圆盘梵塔难题思考？多

22、圆盘梵塔难题思考？2.2 问题规约法第22页/共78页24问题归约的描述问题归约的描述n n问题归约方法应用算符把问题描述转化为子问题描述，可以采用各种数据结问题归约方法应用算符把问题描述转化为子问题描述，可以采用各种数据结构：表列、树、字符串、矢量、数组等；构：表列、树、字符串、矢量、数组等；n n例如梵塔问题的表示：包含两个数列的表列：例如梵塔问题的表示：包含两个数列的表列：(113),(333)(113),(333)n n也可以用状态空间表示法的三元组（也可以用状态空间表示法的三元组（S S，F F，GG）表示；其子问题描述规定了）表示；其子问题描述规定了最后解答路径将要通过的中间状态；

23、最后解答路径将要通过的中间状态；n n可以把问题归约发看成比状态空间法更通用的问题求解方法；其核心实现是可以把问题归约发看成比状态空间法更通用的问题求解方法；其核心实现是不断简化问题，直至问题成为本原问题（已知问题、易解问题）；不断简化问题，直至问题成为本原问题（已知问题、易解问题）；2.2 问题规约法第23页/共78页252.2.2与或图表示与或图表示n n1.与图、或图、与或图 一般，我们用一个似图结构来表示把问题归约为一般，我们用一个似图结构来表示把问题归约为后继问题的替换集合，这一似图结构叫做问题归后继问题的替换集合，这一似图结构叫做问题归约图，或叫与或图。如下所示约图，或叫与或图。如

24、下所示2.2 问题规约法ABCD与图ABC或图第24页/共78页262.2 问题规约法BCDEFGAHMBCDEFGAN与或图与或图增加附加节点后的规范化与或图表示：第25页/共78页272.一些关于与或图的一些关于与或图的术语术语2.2 问题规约法HMBCDEFGAN父节点与节点弧线或节点子节点终叶节点第26页/共78页28一些关于与或图的一些关于与或图的术语术语n n父节点、子（后继）节点、弧线父节点、子（后继）节点、弧线n n起始节点起始节点n n终叶节点终叶节点：对应于原问题的本原节点：对应于原问题的本原节点n n或节点或节点：只要解决某个问题就可解决其父辈问题的节点集合，如：只要解决

25、某个问题就可解决其父辈问题的节点集合，如（MM，NN，HH）。）。n n与节点与节点：只有解决所有子问题，才能解决其父辈问题的节点集合，：只有解决所有子问题，才能解决其父辈问题的节点集合，如（如（B B，C C）和（）和（DD，E E，F F）。各个节点之间用一端小圆弧连接标）。各个节点之间用一端小圆弧连接标记。记。n n与或图与或图：由与节点及或节点组成的结构图。：由与节点及或节点组成的结构图。2.2 问题规约法第27页/共78页293.定义定义可解节点的一般定义：可解节点的一般定义：终叶节点是可解节点终叶节点是可解节点(因为它们与本原问题相关连因为它们与本原问题相关连)。：。：如果某个非终

26、叶节点含有或后继节点，那么只要当如果某个非终叶节点含有或后继节点，那么只要当其后继节点至少有一个是可解的时，此非终叶节点其后继节点至少有一个是可解的时，此非终叶节点才是可解的。才是可解的。如果某个非终叶节点含有与后继节点，那么只有当如果某个非终叶节点含有与后继节点，那么只有当其后继节点全部为可解时，此非终叶节点才是可解其后继节点全部为可解时，此非终叶节点才是可解的。的。2.2 问题规约法第28页/共78页30不可解节点的一般定义：不可解节点的一般定义：n n没有后裔的非终叶节点为不可解节点。没有后裔的非终叶节点为不可解节点。n n全部后裔为不可解的非终叶节点且含有或后继节点，全部后裔为不可解的

27、非终叶节点且含有或后继节点，此非终叶节点才是不可解的。此非终叶节点才是不可解的。n n后裔至少有一个为不可解的非终叶节点且含有与后继后裔至少有一个为不可解的非终叶节点且含有与后继节点，此非终叶节点才是不可解的。节点，此非终叶节点才是不可解的。2.2 问题规约法第29页/共78页31如图所示如图所示2.2 问题规约法与或图例子与或图例子ttttttttt（a）（b）有解节点无解节点终叶节点第30页/共78页32与或图构成规则与或图构成规则n n（1 1）与或图中的每个节点代表一个要解决的单一问题或问题）与或图中的每个节点代表一个要解决的单一问题或问题集合。起始节点对应于原始问题。集合。起始节点对

28、应于原始问题。n n（2 2）对应于本原问题的节点，叫做终叶节点）对应于本原问题的节点，叫做终叶节点n n（3 3）对于把算符应用于问题）对于把算符应用于问题A A的每种可能情况，都把问题变换的每种可能情况，都把问题变换为一个子问题集合；有向弧线自为一个子问题集合；有向弧线自A A指向后继节点，表示所求得指向后继节点，表示所求得的子问题集合，只要其中任意一个有解，问题的子问题集合，只要其中任意一个有解，问题A A就可解，所有就可解，所有这些子问题节点称为或节点；这些子问题节点称为或节点；n n（4 4）一般对于代表两个或两个以上子问题集合的每个节点，）一般对于代表两个或两个以上子问题集合的每个

29、节点，有向弧线从此节点指向此子问题集合中的各个节点有向弧线从此节点指向此子问题集合中的各个节点,只有所有子只有所有子问题都有解，这个子问题的集合才有解，所有这些子问题节点问题都有解，这个子问题的集合才有解，所有这些子问题节点叫做与节点。这些具有共同父节点的与节点用小圆弧连接，以叫做与节点。这些具有共同父节点的与节点用小圆弧连接，以表示与或节点的区别；表示与或节点的区别；n n（5 5）在特殊情况下，当只有一个算符可应用于问题）在特殊情况下，当只有一个算符可应用于问题A A，而且这，而且这个算符产生具有一个以上子问题的某个集合时，由上述规则个算符产生具有一个以上子问题的某个集合时，由上述规则3

30、3和规则和规则4 4所产生的图可以得到简化。（即不增加附加节点的情所产生的图可以得到简化。（即不增加附加节点的情况下）况下）2.2 问题规约法第31页/共78页33梵塔问题归约图梵塔问题归约图（113113）（123123）（111111）（113113）（123123）（122122）（111111）（333333）（122122）（322322）（111111）（122122）（322322）（333333）（321321）（331331）（322322）（321321）（331331）（333333）2.2 问题规约法数据结构介数据结构介绍绍思考题：四圆盘问题思考题：四圆盘问题第32页/

31、共78页342.3 谓词逻辑法谓词逻辑法(Predicate Logic)n n逻辑语句：一种形式语言，它能够把逻辑论证符号逻辑语句：一种形式语言，它能够把逻辑论证符号化，并用于证明定理，求解问题。化，并用于证明定理，求解问题。n n形式语言：严格地按照相关领域的特定规则，以数形式语言：严格地按照相关领域的特定规则，以数学符号（符号串）形式描述该领域有关客体的表达学符号（符号串）形式描述该领域有关客体的表达式式2.3.1 2.3.1 谓词演算谓词演算n n 语法与语义n n基本符号：谓词符号、变量符基本符号：谓词符号、变量符号、函数符号、号、函数符号、常量符号、括常量符号、括号和逗号号和逗号n

32、 n谓词演算的解释：谓词演算的解释：n n谓词符号谓词符号对应关系，对应关系，n n常量符号常量符号论域实体，论域实体，n n函数符号函数符号对应函数；对应函数；第33页/共78页35n n原子公式：由若干谓词符号和项组成的谓词演原子公式：由若干谓词符号和项组成的谓词演算。原子公式是谓词演算基本积木块。项包括算。原子公式是谓词演算基本积木块。项包括常量符号、变量符号、函数符号等。定义原子常量符号、变量符号、函数符号等。定义原子公式为真值或假值就表示了某种公式为真值或假值就表示了某种语义语义语义语义。n n无变量的原子公式取值确定，包含变量的原子无变量的原子公式取值确定，包含变量的原子公式取值不

33、定。公式取值不定。n n例如：例如：n nINROOMINROOM（ROBOTROBOT，r1r1）为真为真n nINROOMINROOM（ROBOTROBOT，r2r2）为假）为假n nMARRIEDfather(wang),mother(wang)MARRIEDfather(wang),mother(wang)2.3 谓词逻辑法第34页/共78页36n n连词和量词(Connective&Quantifiers)n n连词连词 与、合取与、合取（conjunction)conjunction)：用连词用连词把几个公式连接起来而构成的公式。合取项是合取式的每个把几个公式连接起来而构成的公式。

34、合取项是合取式的每个组成部分组成部分。例：例：LIKE(ILIKE(I，MUSIC)MUSIC)LIKE(ILIKE(I，PAINTING)PAINTING)（我喜爱音乐和绘画。）（我喜爱音乐和绘画。）或、析取或、析取（disjunctiondisjunction）：用连词：用连词把几个把几个公式连接起来而构成的公式。析公式连接起来而构成的公式。析取项是析取式的每个组成部分取项是析取式的每个组成部分例：例：PLAYS(LILIPLAYS(LILI，BASKETBALL)BASKETBALL)PLAYS(LILIPLAYS(LILI，FOOTBALL)FOOTBALL)（李力打篮球或踢足（李力打

35、篮球或踢足球。）球。）蕴涵蕴涵（ImplicationImplication）:“=”:“=”表示表示“如果如果那么那么”（IFTHENIFTHEN）关系，其所）关系，其所构成的公式叫做蕴涵。构成的公式叫做蕴涵。非非（NotNot）表示否定，、表示否定，、均可表示均可表示2.3 谓词逻辑法第35页/共78页37n n量词 全称量词（全称量词（Universal QuantifierUniversal Quantifier）：若一个原子公：若一个原子公式式P P（x x），对于所有可能变量），对于所有可能变量 x x都具有都具有T T值，值，则用则用 （x x）P P（x x）表示）表示例如例如

36、:所有的机器人都是灰色的所有的机器人都是灰色的（x x）ROBOT(x)=COLOR(x,GRAY)ROBOT(x)=COLOR(x,GRAY)约束变元约束变元全程量词作用域全程量词作用域存在量词（Existential Quantifier）若一个原子公式P（x），至少有一个变元x，可使P （x）为T值，则用（x）P（x）表示。例：(x)INROOM(x,r1)（1号房间内有个物体）第36页/共78页382.3.2 2.3.2 谓词公式谓词公式n n原子公式的的定义：原子公式的的定义：n n用用P(xP(x1 1，x x2 2，x xn n)表示一个表示一个n n元谓词公式，元谓词公式，其中

37、其中P P为为n n元谓词，元谓词，x x1 1,x,x2 2,，x xn n为客体变量或为客体变量或变元。通常把变元。通常把P(xP(x1 1,x,x2 2,x,xn n)叫做谓词演算的叫做谓词演算的原原原原子公式子公式子公式子公式，或，或原子谓词公式原子谓词公式原子谓词公式原子谓词公式。n n分子谓词公式分子谓词公式n n可以用连词把原子谓词公式组成复合谓词公可以用连词把原子谓词公式组成复合谓词公式，并把它叫做式，并把它叫做分子谓词公式分子谓词公式分子谓词公式分子谓词公式。2.3 谓词逻辑法第37页/共78页39n n合式公式（WFF，well-formed formulas）n n合式公

38、式的递归定义合式公式的递归定义(1)(1)原子谓词公式是原子谓词公式是合式合式公式。公式。(2)(2)若若A A为合适公式，则为合适公式，则A A也是也是一个一个合式合式公式。公式。(3)(3)若若A A和和B B都是都是合式合式公式，则公式，则(AB)(AB)，(AB)(AB)，(A(AB)B)和和(AB)(AB)也都是也都是合式合式公式。公式。(4)(4)若若A A是是合式合式公式，公式，x x为为A A中的中的自由变元，则自由变元，则(x)Ax)A和和(x)Ax)A都是都是合式合式公式。公式。(5)(5)只有按上述规则只有按上述规则(1)(1)至至(4)(4)求得求得的那些公式，才是的那

39、些公式，才是合式合式公式。公式。例题：例题：试把下列命题表示为谓试把下列命题表示为谓词公式：任何整数，或者为词公式：任何整数，或者为整数或者为负数。整数或者为负数。2.3 谓词逻辑法第38页/共78页40n n合式合式公式的性质公式的性质n n合式合式公式的真值公式的真值n n等价（等价（Equivalence)Equivalence)如果两个如果两个合式合式公式，无论如何解释，其真值表都是相公式，无论如何解释，其真值表都是相同的，那么我们就称此两同的，那么我们就称此两合式合式公式是等价的。公式是等价的。T F T F F F表表2-1 真值表真值表P Q PQ P Q PQ PT T T T

40、 T FF T T F T TF F F F T T2.3 谓词逻辑法第39页/共78页41等价关系等价关系n n(1(1 否定之否定否定之否定(P)P)等价于等价于 P Pn n(2)P(2)P Q Q 等价于等价于 P=QP=Qn n(3)(3)狄狄 摩根定律摩根定律(P P Q)Q)等价于等价于 P P Q Q(P(P Q)Q)等价于等价于 P P Q Qn n(4(4 分配律分配律P P(Q(Q R)R)等价于等价于(P P Q)Q)(P (P R)R)P P (Q (Q R)R)等价于等价于(P P Q)Q)(P (P R)R)n n(5)(5)交换律交换律P P Q Q 等价于等价

41、于 Q Q P PP P QQ 等价于等价于 QQ P P 2.3 谓词逻辑法第40页/共78页42n n6)6)结合律结合律(P P Q)Q)R R 等价于等价于 P P(Q(Q R)R)(P(P Q)Q)R R 等价于等价于 P P (Q (Q R)R)n n(7)(7)逆否律逆否律P=Q P=Q 等价于等价于 Q=PQ=Pn n(8)(8)(x)P(x)x)P(x)等价于等价于(x)P(x)x)P(x)(x)P(x)x)P(x)等价于等价于(x)P(x)x)P(x)n n(9)(9)(x)P(x)x)P(x)Q(x)Q(x)等价于等价于(x)P(x)x)P(x)(x)Q(x)x)Q(x)

42、(x)P(x)x)P(x)Q(x)Q(x)等价于等价于(x)P(x)x)P(x)(x)Q(x)x)Q(x)n n(10(10 (x)P(x x)P(x 等价于等价于(y)P(y)y)P(y)(x)P(x)x)P(x)等价于等价于(y)P(y)y)P(y)第41页/共78页432.3.3 置换与合一置换与合一n n谓词逻辑的推理谓词逻辑的推理谓词逻辑的推理谓词逻辑的推理n n将推理规则应用于一定的合式将推理规则应用于一定的合式将推理规则应用于一定的合式将推理规则应用于一定的合式公式（集），以产生新的合式公式（集），以产生新的合式公式（集），以产生新的合式公式（集），以产生新的合式公式。公式。公式

43、。公式。n n假元推理假元推理假元推理假元推理n n全称化推理全称化推理全称化推理全称化推理n n综合推理综合推理综合推理综合推理n n思考：推理规则中存在项的变换与同一问题，思考：推理规则中存在项的变换与同一问题，思考：推理规则中存在项的变换与同一问题，思考：推理规则中存在项的变换与同一问题，如何实施？如何实施？如何实施？如何实施？2.3 谓词逻辑法W1W1W2 W2（x）W（x）W（A）任意变量任意变量约束变元约束变元(x)W1(x)W2(x)W1（A）W2（A）第42页/共78页44n n置换置换(Substitution)：n n在表达式中用置换项置换变量，例如用项在表达式中用置换项置

44、换变量，例如用项在表达式中用置换项置换变量，例如用项在表达式中用置换项置换变量，例如用项（A A）替换函数表达式中的变量（）替换函数表达式中的变量（）替换函数表达式中的变量（）替换函数表达式中的变量（x x）。一个表）。一个表）。一个表）。一个表达式达式达式达式E E（ExpressionExpression）用一个置换）用一个置换）用一个置换）用一个置换S S（SubstitutionSubstitution）而得到的表达式的置换，记）而得到的表达式的置换，记）而得到的表达式的置换，记）而得到的表达式的置换，记为为为为ESES。n n例题：表达式例题：表达式例题：表达式例题：表达式E E：P

45、x,f(y),BPx,f(y),B；置换：；置换：；置换：；置换：s1=z/x,w/y,s2=A/y,s1=z/x,w/y,s2=A/y,s3=q(z)/x,A/y,s4=c/x,A/ys3=q(z)/x,A/y,s4=c/x,A/yn nSolution:Solution:ES1=Pz,f(w),B;ES2=Px,f(A),B;ES1=Pz,f(w),B;ES2=Px,f(A),B;ES3=Pq(z),f(A),B;ES3=Pq(z),f(A),B;ES4=ES4=Pc,f(A),B;Pc,f(A),B;ES1S2=Pz,f(w),B;ES2S1=Pz,f(A),BES1S2=Pz,f(w)

46、,B;ES2S1=Pz,f(A),B思考：思考：思考：思考：(1)ES4S1(1)ES4S1，ES3S2ES3S2？(2)(2)置换的运算规则？置换的运算规则？置换的运算规则？置换的运算规则？2.3 谓词逻辑法第43页/共78页45n n置换的性质置换的性质n n可结合律可结合律可结合律可结合律:（LS1LS1）S2 =LS2 =L（S1S2S1S2）（S1S2S1S2）S3=S1S3=S1（S2S3S2S3）问题：请举例说明？问题：请举例说明？问题：请举例说明？问题：请举例说明？n n不可交换律不可交换律不可交换律不可交换律:S1S2=S2S1 S1S2=S2S1问题：请举例说明？问题：请举

47、例说明？问题：请举例说明？问题：请举例说明？思考：什么置换是谓词逻辑推理所需要思考：什么置换是谓词逻辑推理所需要思考：什么置换是谓词逻辑推理所需要思考：什么置换是谓词逻辑推理所需要的？的？的？的？2.3 谓词逻辑法/第44页/共78页46n n合一（合一（合一（合一（Unification)Unification)：n n合一：合一：合一：合一：寻找项对变量的置换，寻找项对变量的置换，寻找项对变量的置换，寻找项对变量的置换，以使多个表达式一致的操作称以使多个表达式一致的操作称以使多个表达式一致的操作称以使多个表达式一致的操作称为为为为合一合一合一合一。如果一个置换。如果一个置换。如果一个置换。

48、如果一个置换s s作用作用作用作用于表达式集于表达式集于表达式集于表达式集 E Ei i 的每个元素，的每个元素，的每个元素，的每个元素，则我们用则我们用则我们用则我们用 E Ei i s s来表示置换例来表示置换例来表示置换例来表示置换例的集。的集。的集。的集。n n可合一：可合一：可合一：可合一：如果存在置换如果存在置换如果存在置换如果存在置换s s使得使得使得使得表达式集表达式集表达式集表达式集 E Ei i 置换后有：置换后有：置换后有：置换后有：E E1 1S S E E2 2S S E E3 3S S,则我们称表达式则我们称表达式则我们称表达式则我们称表达式集集集集 E Ei i

49、是是是是可合一的可合一的可合一的可合一的，s s 称为称为称为称为 E Ei i 的的的的合一者合一者合一者合一者。n n例题：表达式集例题：表达式集例题：表达式集例题：表达式集 P P x,f(y),x,f(y),BB,P,P x,f(x,f(B B),),B B 的的的的合一者：合一者：合一者：合一者：s s A/A/x x,B/,B/y y n n说明：说明：说明：说明：P P x x,f f(y y),B),Bs s P P x x,f f(B),B(B),Bs s P PA,A,f f(B),B(B),B思考：还有其他合一者吗？思考：还有其他合一者吗？思考：还有其他合一者吗？思考：还

50、有其他合一者吗？2.3 谓词逻辑法第45页/共78页47n n最通用的合一者：最通用的合一者：如果对表达式集如果对表达式集如果对表达式集如果对表达式集 E Ei i 的任一合一者的任一合一者的任一合一者的任一合一者s s，都存在某一，都存在某一，都存在某一，都存在某一s s，使得，使得，使得，使得 E Ei i s s E Ei i gsgs，则称，则称，则称，则称g g为为为为 E Ei i 的最通用合一的最通用合一的最通用合一的最通用合一者。者。者。者。n n问题：上例题中，最通用的合一者是什么？问题：上例题中，最通用的合一者是什么？问题：上例题中，最通用的合一者是什么？问题：上例题中，最