西电人工智能4知识表示方法part2

1、西安电子科技大学西安电子科技大学Artificial Intelligence (AI)人工智能人工智能主讲：戚玉涛Email：qi_第二章：知识第二章：知识表示方法表示方法西安电子科技大学西安电子科技大学内容提要1.1.状态空间法状态空间法2.2.问题归约法问题归约法3.3.谓词逻辑法谓词逻辑法4.4.语义网络法语义网络法5.5.其他方法其他方法西安电子科技大学西安电子科技大学问题归约法v 问题归约（问题归约（Problem Reduction） 是另外一种是另外一种基于状态空间基于状态空间的问题描述与求解方法的问题描述与求解方法 已知问题的描述，通过一系列已知问题的描述，通过一系列变换变换

2、把此问题变为一个把此问题变为一个子问题子问题集合集合 这些子问题的解可以这些子问题的解可以直接得到（本原问题）直接得到（本原问题），从而解决了初，从而解决了初始问题始问题西安电子科技大学西安电子科技大学问题归约法v 问题归约法的组成部分问题归约法的组成部分一个初始问题描述；一个初始问题描述；一套把问题变换为子问题的一套把问题变换为子问题的操作符操作符；一套一套本原问题本原问题描述。描述。( (本原问题本原问题: :不能再分解或变换且不能再分解或变换且直接可解的子问题直接可解的子问题) )v 问题归约的实质：问题归约的实质：从目标（要解决的问题）出发从目标（要解决的问题）出发逆向推理逆向推理，建

3、立子问题，建立子问题以及子问题的子问题，直到最后把初始问题归约为以及子问题的子问题，直到最后把初始问题归约为一一个本原问题集合个本原问题集合。西安电子科技大学西安电子科技大学问题归约法v 问题归约法举例：问题归约法举例：汉诺塔问题（汉诺塔问题（ Hanoi ） p 从从1移到移到3p 每次移动一个盘子每次移动一个盘子p 大盘在下小盘在上大盘在下小盘在上123CBA初始状态（初始状态（111）目标状态（目标状态（333）CBA西安电子科技大学西安电子科技大学汉诺塔问题v 原始问题可以归约为下列原始问题可以归约为下列3 3个子问题：个子问题：子问题子问题1 1：子问题子问题2 2：子问题子问题3

4、3：西安电子科技大学西安电子科技大学汉诺塔问题v 归约过程（归约过程（3 3个圆盘）个圆盘）西安电子科技大学西安电子科技大学汉诺塔问题v 汉诺塔问题归约图汉诺塔问题归约图本原问题本原问题本原问题本原问题与或图与或图CBA西安电子科技大学西安电子科技大学问题归约法v 与或图表示：与或图表示：用一个类似于图的结构来表示把问题归约为用一个类似于图的结构来表示把问题归约为后继问题的替换集合。后继问题的替换集合。与图：与图：把一个复杂问题把一个复杂问题分解为若干个较为简单的分解为若干个较为简单的子问题，形成子问题，形成“与与”树。树。或图：或图：把原问题变换为把原问题变换为若干个较为容易求解的新若干个较

5、为容易求解的新问题，形成问题，形成“或或”树。树。西安电子科技大学西安电子科技大学问题归约法v 与或图表示：与或图表示：BCDEFGAHMBCDEFGAN子问题替代集合结构图子问题替代集合结构图与或图与或图西安电子科技大学西安电子科技大学问题归约法v 一些关于与或图的术语一些关于与或图的术语起始节点起始节点对应于原对应于原始问题描始问题描述述终叶节点对应于本原问题终叶节点对应于本原问题西安电子科技大学西安电子科技大学问题归约法v 与或图的构成规则与或图的构成规则 1 1）与或图中的每个节点代表一）与或图中的每个节点代表一个要解决的单一问题或问题集合。个要解决的单一问题或问题集合。图中所含起始节

6、点对应于原始问图中所含起始节点对应于原始问题题A A。 2 2）对应于本原问题的节点称为）对应于本原问题的节点称为终叶节点，它没有后继节点。终叶节点，它没有后继节点。 3 3）对于把算符应用于问题）对于把算符应用于问题A A的每的每种可能情况，都把问题变换为一种可能情况，都把问题变换为一个子问题集合；有向弧线自个子问题集合；有向弧线自A A指指向后继节点表示所求得的子问题向后继节点表示所求得的子问题集合。集合。HMBCDEFGAN西安电子科技大学西安电子科技大学问题归约法v 与或图的构成规则与或图的构成规则 4 4）一般对于代表两个或两个以上）一般对于代表两个或两个以上子问题集合的每个节点，有

7、向弧子问题集合的每个节点，有向弧线从此节点指向次子问题集合中线从此节点指向次子问题集合中的各个节点。由于只有当集合中的各个节点。由于只有当集合中所有项都有解时，这个子问题的所有项都有解时，这个子问题的集合才能获得解答，所以这些子集合才能获得解答，所以这些子问题节点叫做与节点。问题节点叫做与节点。 5 5）特殊情况下，当只有一个算符）特殊情况下，当只有一个算符可应用于问题可应用于问题A A，而且这个算符产，而且这个算符产生具有一个以上子问题的某个集生具有一个以上子问题的某个集合时，由上述规则合时，由上述规则3 3）和规则）和规则4 4）所产生的图可以得到简化。所产生的图可以得到简化。MDEFAA

8、DEF简化简化西安电子科技大学西安电子科技大学问题归约法v与或图的搜索：与或图的搜索：目的在于表明起始节点是有解的。目的在于表明起始节点是有解的。v可解节点可解节点终叶节点是可解节点（对应于本原问题）。终叶节点是可解节点（对应于本原问题）。如果某个非终叶节点含有如果某个非终叶节点含有或后继节点或后继节点，那么只要当其后，那么只要当其后继节点至少有一个是可解的时，此非终叶节点才是可解继节点至少有一个是可解的时，此非终叶节点才是可解的。的。如果某个非终叶节点含有如果某个非终叶节点含有与后继节点与后继节点，那么只有当其后，那么只有当其后继节点全部为可解时，此非终叶节点才是可解的。继节点全部为可解时，

9、此非终叶节点才是可解的。西安电子科技大学西安电子科技大学问题归约法v不可解节点不可解节点没有后裔的非终叶节点为不可解节点。没有后裔的非终叶节点为不可解节点。 如果某个非终叶节点含有如果某个非终叶节点含有或后继节点或后继节点，那么只有当其，那么只有当其全全部后裔为不可解时部后裔为不可解时，此非终叶节点才是不可解的。，此非终叶节点才是不可解的。 如果某个非终叶节点含有如果某个非终叶节点含有与后继节点与后继节点，那么只要当其，那么只要当其后后裔至少有一个为不可解时裔至少有一个为不可解时，此非终叶节点才是不可解的。，此非终叶节点才是不可解的。v解树解树由可解节点所构成，并且由这些可解节点可推出初始节由

10、可解节点所构成，并且由这些可解节点可推出初始节点为可解节点的子树称为解树。点为可解节点的子树称为解树。解树中一定包含初始节点，它对应于原始问题。解树中一定包含初始节点，它对应于原始问题。西安电子科技大学西安电子科技大学问题归约法ttttttttt有解节点有解节点无解节点无解节点终叶节点终叶节点与或图例子与或图例子原始问题原始问题有一有一个以上的解个以上的解原始问题原始问题有有解解西安电子科技大学西安电子科技大学内容提要1.1.状态空间法状态空间法2.2.问题归约法问题归约法3.3.谓词逻辑法谓词逻辑法4.4.语义网络法语义网络法5.5.其他方法其他方法西安电子科技大学西安电子科技大学谓词逻辑法

11、v命题逻辑与谓词逻辑命题逻辑与谓词逻辑命题逻辑与谓词逻辑是最先用于人工智能的两种逻辑，命题逻辑与谓词逻辑是最先用于人工智能的两种逻辑，对于知识的形式化表示，特别是定理的证明发挥了重对于知识的形式化表示，特别是定理的证明发挥了重要作用要作用虽然命题逻辑能够把客观世界的各种事实表示为逻辑虽然命题逻辑能够把客观世界的各种事实表示为逻辑命题，但是它具有较大的局限性。命题逻辑只能进行命题，但是它具有较大的局限性。命题逻辑只能进行命题间命题间关系关系的推理，无法解决与的推理，无法解决与命题结构命题结构和和成分成分有关有关的推理问题，的推理问题，不适合表示比较复杂的问题不适合表示比较复杂的问题。谓词逻辑是在

12、命题逻辑的基础上发展而来的，命题逻谓词逻辑是在命题逻辑的基础上发展而来的，命题逻辑可以看作是谓词逻辑的一种特殊形式。辑可以看作是谓词逻辑的一种特殊形式。西安电子科技大学西安电子科技大学谓词逻辑法v命题命题命题是具有真假意义的语句命题是具有真假意义的语句命题代表人们进行思维时的一种判断，若命题的意义命题代表人们进行思维时的一种判断，若命题的意义为真，称它的真值为为真，称它的真值为“真真”，记作，记作“T”；若命题的意；若命题的意义为假，称它的真值为义为假，称它的真值为“假假”，记作，记作“F”。例如：。例如：p“西安是陕西省省会西安是陕西省省会”“”“10大于大于6”是真值为是真值为“T”的命题

13、的命题p“月亮是方的月亮是方的”“”“煤炭是白的煤炭是白的”是真值为是真值为“F”的命题的命题一个命题不能同时即为真又为假，但可以在一定条件一个命题不能同时即为真又为假，但可以在一定条件下为真，在另一种条件下为假。例如：下为真，在另一种条件下为假。例如：p“1+1=10”1+1=10”在二进制情况下为真，十进制情况下为假在二进制情况下为真，十进制情况下为假西安电子科技大学西安电子科技大学谓词逻辑法v命题命题没有真假意义的语句，如感叹句、疑问句等，不是命没有真假意义的语句，如感叹句、疑问句等，不是命题。题。通常用大写英文字母表示一个命题，例如：通常用大写英文字母表示一个命题，例如： p P P：

14、西安是座古老的城市：西安是座古老的城市v命题逻辑的局限性？命题逻辑的局限性？客观事物的结构及逻辑特征？客观事物的结构及逻辑特征？不同事物间的共同特征？不同事物间的共同特征？西安电子科技大学西安电子科技大学谓词逻辑法v命题逻辑的局限性？命题逻辑的局限性？命题这种表示方法无法把它所描述的客观事物的结构命题这种表示方法无法把它所描述的客观事物的结构及逻辑特征反映出来，也不能把不同事物间的共同特及逻辑特征反映出来，也不能把不同事物间的共同特征表述出来征表述出来例如，用字母例如，用字母P P表示表示“小张是老张的儿子小张是老张的儿子”这一命题，这一命题，则无法表述出老张与小张是父子关系则无法表述出老张与

15、小张是父子关系又如，又如，“张三是学生张三是学生”，“李四是学生李四是学生”这两个命题，这两个命题，用命题逻辑表示时，无法把两者的共同特征用命题逻辑表示时，无法把两者的共同特征“都是学都是学生生”形式的表示出来形式的表示出来可否用可否用 Student（“张三张三”），）， Student（“李四李四”）表示上述命题？表示上述命题？谓词逻辑谓词逻辑西安电子科技大学西安电子科技大学谓词逻辑法v谓词谓词在谓词逻辑中，命题是用形如在谓词逻辑中，命题是用形如P(x1,x2,xn)的谓词来表的谓词来表述的。一个谓词可分为述的。一个谓词可分为谓词名谓词名与与个体个体两个部分两个部分个体：个体： 是命题的主

16、语，表示独立存在的事物或某个抽是命题的主语，表示独立存在的事物或某个抽象的概念象的概念p “x1,x2,xn”是个体，一般用小写字母表示是个体，一般用小写字母表示p 个体可以是个体常量、变元或函数个体可以是个体常量、变元或函数谓词名：谓词名：表示个体的性质、状态或个体之间的关系表示个体的性质、状态或个体之间的关系p “P”是谓词名，一般用大写字母表示是谓词名，一般用大写字母表示p 称称P 是一个是一个n元谓词。元谓词。西安电子科技大学西安电子科技大学谓词逻辑法v谓词谓词对于命题对于命题“张三是学生张三是学生” ，用谓词可以表示为：，用谓词可以表示为：Student（“张三张三”）。其中，）。其

17、中， Student是谓词名，是谓词名， “张张三三”是个体，是个体， Student刻画了刻画了“张三张三”是个学生这一特是个学生这一特征。征。在谓词中，个体可以是常量，也可以是变元，还可以在谓词中，个体可以是常量，也可以是变元，还可以是一个函数。例如，对于命题是一个函数。例如，对于命题“x10”可以表示为可以表示为more（x,10），其中），其中x是变元。又如，命题是变元。又如，命题“小张的父亲是小张的父亲是老师老师”，可以表示为，可以表示为Teacher（father（Zhang），其），其中，中， father（Zhang）是一个函数。）是一个函数。当谓词中的变元都用特定的个体取代时

18、，谓词就具有当谓词中的变元都用特定的个体取代时，谓词就具有一个确定的真值一个确定的真值“T”或或 “F” 。西安电子科技大学西安电子科技大学谓词逻辑法v谓词谓词在在n元谓词元谓词 P(x1,x2,xn)中，若每个个体均为常量、变中，若每个个体均为常量、变元或函数，则称它为元或函数，则称它为一阶谓词一阶谓词。如果某个个体本身又是一个一阶谓词，则称它为如果某个个体本身又是一个一阶谓词，则称它为二阶二阶谓词谓词，如此类推。，如此类推。个体变元的取值范围称为个体变元的取值范围称为个体域个体域。个体域可以是有限。个体域可以是有限的，也可以是无限的。例如用的，也可以是无限的。例如用I（x）表示）表示“x是

19、整数是整数”，则个体域为所有整数，是无限的。则个体域为所有整数，是无限的。谓词与函数不同谓词与函数不同，谓词的真值是，谓词的真值是”T“或或”F“，而函数，而函数的值是个体域中的一个个体，无真值可言。的值是个体域中的一个个体，无真值可言。西安电子科技大学西安电子科技大学谓词逻辑法v谓词演算谓词演算谓词逻辑语言的语法和语义谓词逻辑语言的语法和语义p基本符号：基本符号：谓词符号、变量符号、函数符号、常量符号、谓词符号、变量符号、函数符号、常量符号、括号和逗号括号和逗号p原子公式：原子公式：原子公式由若干谓词符号和项组成原子公式由若干谓词符号和项组成 谓词符号谓词符号规定定义域内的一个相应关系规定定

20、义域内的一个相应关系 常量符号常量符号是最简单的项，表示论域内的物体或实体是最简单的项，表示论域内的物体或实体 变量符号变量符号也是项，不明确涉及是哪一个实体也是项，不明确涉及是哪一个实体 函数符号函数符号表示论域内的函数，是从论域内的一个实体到另表示论域内的函数，是从论域内的一个实体到另外一个实体的映射外一个实体的映射 例如：原子公式例如：原子公式 Married father(LI) , mother(LI) 表示表示“李（李（LI LI）的父亲和他的母亲结婚）的父亲和他的母亲结婚”西安电子科技大学西安电子科技大学谓词逻辑法连词和量词连词和量词p连词连词 合取：合取：符号符号“ ”， 表示

21、所连结的两个命题之间具有表示所连结的两个命题之间具有“与与”的关系。的关系。 析取：析取： 符号符号“ ”，表示所连结的两个命题之间具有，表示所连结的两个命题之间具有“或或”的关系的关系 蕴涵：蕴涵：符号符号“ ” ，表示，表示“若若则则”的语义。的语义。PQPQ读读作作“如果如果P P，则，则QQ”其中，其中，P P称为条件的前件，称为条件的前件，QQ称为条件称为条件的后件。的后件。 非：非：符号符号“ ”，表示对其后面的命题的否定，表示对其后面的命题的否定 双条件：双条件：符号符号“ ”，表示，表示“当且仅当当且仅当”的语义。的语义。 P PQQ读作读作“P P当且仅当当且仅当QQ”。西安

22、电子科技大学西安电子科技大学谓词逻辑法p量词量词 全称量词：全称量词：符号符号“ ”，意思是意思是“所有的所有的”、“任一个任一个” x x读作读作“对一切对一切x x”, ,或或“对每一对每一x x”，或，或“对任一对任一x x”。命题命题( ( x)P(x)x)P(x)为真，当且仅当对论域中的所有为真，当且仅当对论域中的所有x x，都有，都有P(x)P(x)为真为真命题命题( ( x)P(x)x)P(x)为假，当且仅当至少存在论域中的一个为假，当且仅当至少存在论域中的一个x x，使得使得P(x)P(x)为假为假 存在量词：存在量词：符号符号“ ”，意思是意思是“至少有至少有”、“存在存在”

23、 x x读作读作“存在一个存在一个x x”, ,或或“对某些对某些x x”，或，或“至少有一至少有一x x”。命题命题( ( x)P(x)x)P(x)为真，当且仅当至少存在论域中的一个为真，当且仅当至少存在论域中的一个x x，使得使得P(x)P(x)为真为真命题命题( ( x)P(x) x)P(x)为假，当且仅当对论域中的所有为假，当且仅当对论域中的所有x x，都有，都有P(x)P(x)为假为假 西安电子科技大学西安电子科技大学谓词逻辑法v谓词公式谓词公式 原子谓词公式：原子谓词公式：是由谓词符号和若干项组成的谓词演算。是由谓词符号和若干项组成的谓词演算。 分子谓词公式：分子谓词公式：可以用可

24、以用连词连词把原子谓词公式组成复合谓词公式，把原子谓词公式组成复合谓词公式，并把它叫做分子谓词公式。并把它叫做分子谓词公式。 合式公式（合式公式（WFF，Well-formed Formulas）：）：通常把通常把合式公式合式公式叫叫做做谓词公式谓词公式，递归定义如下：，递归定义如下：p(1) 原子谓词公式是合式公式原子谓词公式是合式公式p(2) 若若A为合式公式，则为合式公式，则 A也是一个合式公式也是一个合式公式p(3) 若若A,B是合式公式，则是合式公式，则AB，AB，AB，AB也都是合式公也都是合式公式式p(4) 若若A是合式公式，是合式公式，x为为A中的自由变元，则中的自由变元，则

25、( x)A和和( x)A都是合式都是合式公式公式p(5) 只有按上述规则只有按上述规则(1)至至(4)求得的那些公式，才是合式公式。求得的那些公式，才是合式公式。西安电子科技大学西安电子科技大学谓词逻辑法v谓词公式谓词公式 用谓词公式表示知识时，需要首先用谓词公式表示知识时，需要首先定义谓词定义谓词，然后再用，然后再用连接连接词把有关的谓词连接起来，形成一个谓词公式表达一个完整词把有关的谓词连接起来，形成一个谓词公式表达一个完整的意义。的意义。 例例1：设有下列知识设有下列知识 刘欢比他父亲出名。刘欢比他父亲出名。 高扬是计算机系的一名学生，但他不喜欢编程高扬是计算机系的一名学生，但他不喜欢编

26、程 。 任何整数或者为正或者为负。任何整数或者为正或者为负。为了用谓词公式表示上述知识，首先需要定义谓词：为了用谓词公式表示上述知识，首先需要定义谓词： FAMOUS (x, y) : x比比y出名出名 COMPUTER ( x ) : x 是计算机系的是计算机系的 LIKE (x, y ) : x 喜欢喜欢 y西安电子科技大学西安电子科技大学谓词逻辑法 I(x)表示表示“x是整数是整数” P(x)表示表示“x是正数是正数” N(x)表示表示“x是负数是负数” 此时可用谓词公式把上述知识表示为此时可用谓词公式把上述知识表示为: 刘欢比他父亲出名刘欢比他父亲出名: FAMOUS ( liuhua

27、n, father ( liuhuan ) 高扬是计算机系的一名学生，但他不喜欢编程高扬是计算机系的一名学生，但他不喜欢编程 : COMPUTER(gaoyang)LIKE(gaoyang, programing) 任何整数或者为正或者为负任何整数或者为正或者为负: ( x)(I(x) (P(x) N(x)西安电子科技大学西安电子科技大学谓词逻辑法v谓词公式谓词公式 例例2：用谓词逻辑描述右图中的房子的概念用谓词逻辑描述右图中的房子的概念p个体个体 ：A , Bp谓词谓词 ：SUPPORT( x,y )：表示：表示 x 被被 y支撑着支撑着 WEDRE ( x )：表示：表示 x 是楔形块是楔

28、形块 BRICK( y )：表示：表示 y 是长方块是长方块 p其中其中 x , y是个体变元，它们的个体域是个体变元，它们的个体域A,Bp房子的概念可以表示成一组合式谓词公式的合取式：房子的概念可以表示成一组合式谓词公式的合取式： SUPPORT(A,B) WEDGE( A ) BRICK( B )西安电子科技大学西安电子科技大学谓词逻辑法v合式公式的性质合式公式的性质若若P、Q是两个合式公式，则由这两个合式公式所组成是两个合式公式，则由这两个合式公式所组成的复合表达式可由下列真值表给出。的复合表达式可由下列真值表给出。PQPPQPQPQPQTTFTTTTTFFTFFFFTTTFTFFFTF

29、FTT西安电子科技大学西安电子科技大学谓词逻辑法v合式公式的性质合式公式的性质 如果两个合式公式，无论如何解释，其真值表都是相同的，如果两个合式公式，无论如何解释，其真值表都是相同的，那么我们就称此两合式公式是那么我们就称此两合式公式是等价的等价的。 应用上述真值表可以确立下列等价关系：应用上述真值表可以确立下列等价关系：p（1）否定之否定：）否定之否定： ( P ) = Pp（2）( P Q ) = ( P Q ) ，或者，或者( P Q ) = ( P Q ）p（3）狄）狄 摩根定律：摩根定律： ( P Q ) = P Q ( P Q ) = P Qp（4）分配律：）分配律： P ( Q

30、R ) = ( P Q ) ( P R ) P ( Q R ) = ( P Q ) ( P R )西安电子科技大学西安电子科技大学谓词逻辑法p（5）交换律：）交换律： P Q = Q P P Q = Q Pp（6）结合律：）结合律： P ( Q R ) = ( P Q ) R P ( Q R ) = ( P Q ) Rp（7）逆否率：）逆否率： ( P Q ) = ( Q P ) p（8）泛界律：）泛界律： P F = P , P T = P P F = F , P T = T p（9）互余律：）互余律： P P = T, P P = F西安电子科技大学西安电子科技大学谓词逻辑法此外还可以确立

31、下列等价关系：此外还可以确立下列等价关系：p ( x) P(x) = ( x) P(x) p ( x) P(x) = ( x) P(x) p ( x) P(x) Q(x) = ( x) P(x) ( x) Q(x)p ( x) P(x) Q(x) = ( x) P(x) ( x) Q(x) p ( x) P(x) = ( y) P(y) p ( x) P(x) = ( y) P(y) 西安电子科技大学西安电子科技大学谓词逻辑法v置换与合一置换与合一置换置换p 推理规则：推理规则：用合式公式的集合产生新的合式公式用合式公式的集合产生新的合式公式 假元推理假元推理 全称化推理全称化推理 综合推理综

32、合推理 W2W1 W1 W2 W(A)( x) W(x) 任意常量任意常量A W2(A) W1(A)( x) W1(x) W2(x)寻找寻找A对对x的的置置换换，使，使W1(A)与与W1(x)一致一致西安电子科技大学西安电子科技大学谓词逻辑法v置换与合一置换与合一置换（置换（SubstitutionSubstitution）p置换的定义：置换的定义：置换是用置换是用变元、常量、函数变元、常量、函数来替换来替换变变元元，使该变元不在公式中出现使该变元不在公式中出现。p置换是形如置换是形如 t1/x1, t2/x2, ， tn/xn的有限集合。的有限集合。 t1，t2， ， tn是项是项 x1，x

33、2， ， xn是互不相同的变元是互不相同的变元 ti/xi表示用表示用ti项替换变元项替换变元xi，不允许，不允许ti和和xi相同，也相同，也不允许变元不允许变元xi循环地出现在另一个循环地出现在另一个tj中中西安电子科技大学西安电子科技大学谓词逻辑法v置换与合一置换与合一置换（置换（SubstitutionSubstitution）p例如例如 a/x , f(b)/y ，w/z 是一个置换是一个置换 g(y)/x , f(x)/y 不是一个置换不是一个置换 g(a)/x , f(x)/y 不是一个置换不是一个置换西安电子科技大学西安电子科技大学谓词逻辑法v置换与合一置换与合一置换（置换（Su

34、bstitutionSubstitution）p例例2.2（P40），表达式），表达式 Px, f(y), B的置换为的置换为 s1= z/x, w/y； s2= A/y；s3= q(z)/x , A/y； s4= c/x , A/y 用用Es表示一个表达式表示一个表达式E用置换用置换s所得到的表达式的置所得到的表达式的置换。于是，换。于是，Px, f(y), B的的4个置换如下：个置换如下： Px, f(y), B s1 = Pz, f(w), B Px, f(y), B s2 = Px, f(A), B Px, f(y), B s3 = Pq(z), f(A), B Px, f(y), B

35、 s4 = Pc, f(A), B 西安电子科技大学西安电子科技大学谓词逻辑法v置换与合一置换与合一置换（置换（SubstitutionSubstitution）p置换是可结合的置换是可结合的用用s1s2表示两个置换表示两个置换s1和和s2的的合成合成，L表示一个表达表示一个表达式，则有式，则有 （Ls1）s2 = L（s1s2 ） 即用即用s1和和s2相继作用于表达式相继作用于表达式L是与用是与用s1s2作用于作用于L一样的一样的进一步推广：（进一步推广：（s1s2）s3 = s1（s2s3 ）p一般说来，置换是不可交换的，即一般说来，置换是不可交换的，即 s1s2 s2s1西安电子科技大学

36、西安电子科技大学谓词逻辑法v置换与合一置换与合一合一（合一（UnificationUnification）p合一的定义：合一的定义：寻找项对变量的寻找项对变量的置换置换，以使，以使两表达式一致两表达式一致。p如果一个置换如果一个置换s作用于表达式集合作用于表达式集合Ei的每个元素，用的每个元素，用Eis表表示置换的集。称表达式示置换的集。称表达式Ei是是可合一可合一的，如果存在一个置换的，如果存在一个置换s使使得：得： E1s = E2s = E3s = 那么，称此那么，称此s为为Ei的的合一者合一者（unifier），因为），因为s的作用是使集的作用是使集合合Ei成为单一形式。成为单一形式。

37、p例如，设有公式集例如，设有公式集 E= P( x, y, f(y), P( a, g(x), z) 则下式是它的一个合一：则下式是它的一个合一： s=a/x, g(a)/y, f(g(a)/z西安电子科技大学西安电子科技大学谓词逻辑法v 谓词逻辑法举例：谓词逻辑法举例：猴子和香蕉问题猴子和香蕉问题描述状态的谓词：描述状态的谓词：pAT(x, y)：x在在y处处pONBOX：猴子在箱子上猴子在箱子上pHB：猴子得到香蕉猴子得到香蕉个体域：个体域：px ：monkey, box, bananapy：a, b, c问题的初始状态问题的初始状态pAT(monkey, a) pAT(box, b)p

38、ONBOX p HB问题的目标状态问题的目标状态pAT(monkey, c) pAT(box, c)pONBOX pHB西安电子科技大学西安电子科技大学猴子和香蕉问题描述操作的谓词描述操作的谓词p Goto(u, v)：猴子从猴子从u处走到处走到v处处 条件：条件：ONBOX ，AT(monkey, u) 动作动作：删除表：删除表：AT(monkey, u)；添加表：；添加表：AT(monkey, v)pPushbox(v, w)：猴子推着箱子从猴子推着箱子从v处移到处移到w处处 条件：条件： ONBOX ，AT(monkey, v)，AT(box, v) 动作：动作：删除表：删除表：AT(monkey, v)，AT(box, v) 添加表：添加表：AT(monkey, w)，AT(box,w)pClimbbox：猴子爬上箱子猴子爬上箱子 条件：条件： ONBOX ，AT(monkey, w)，AT(box,w) 动作动作：删除表：删除表： ONBOX；添加表：；