《知识表示方法part人工智能西电.pptx》由会员分享，可在线阅读，更多相关《知识表示方法part人工智能西电.pptx（48页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、内容提要第二章：知识表示方法第二章：知识表示方法第二章：知识表示方法第二章：知识表示方法1.1.状态空间法状态空间法2.2.问题归约法问题归约法3.3.谓词逻辑法谓词逻辑法4.4.语义网络法语义网络法5.5.其他方法其他方法第1页/共48页问题归约法问题归约（问题归约（Problem Reduction）是另外一种是另外一种基于状态空间基于状态空间的问题描述与求解方法的问题描述与求解方法已知问题的描述，通过一系列已知问题的描述，通过一系列变换变换把此问题变为一个把此问题变为一个子问题集合子问题集合这些子问题的解可以这些子问题的解可以直接得到（本原问题）直接得到（本原问题），从而解决了初始问题，
2、从而解决了初始问题第2页/共48页问题归约法问题归约法的组成部分问题归约法的组成部分一个初始问题描述；一个初始问题描述；一套把问题变换为子问题的一套把问题变换为子问题的操作符操作符；一套一套本原问题本原问题描述。描述。(本原问题本原问题:不能再分解或变换且直接可解的子问不能再分解或变换且直接可解的子问题题)问题归约的实质：问题归约的实质：从目标（要解决的问题）出发从目标（要解决的问题）出发逆向推理逆向推理，建立子问题以及子问题的子，建立子问题以及子问题的子问题，直到最后把初始问题归约为问题，直到最后把初始问题归约为一个本原问题集合一个本原问题集合。第3页/共48页问题归约法问题归约法举例：问题
3、归约法举例：汉诺塔问题（汉诺塔问题（Hanoi）p 从从1移到移到3p 每次移动一个盘子每次移动一个盘子p 大盘在下小盘在上大盘在下小盘在上123CBA初始状态（初始状态（111）目标状态（目标状态（333）CBA第4页/共48页汉诺塔问题原始问题可以归约为下列原始问题可以归约为下列3 3个子问题：个子问题：子问题子问题1 1：移动圆盘移动圆盘移动圆盘移动圆盘A A和和和和 B B至柱子至柱子至柱子至柱子2 2（借助柱子（借助柱子（借助柱子（借助柱子3 3）子问题子问题2 2：移动圆盘移动圆盘移动圆盘移动圆盘C C至柱至柱至柱至柱子子子子3 3子问题子问题3 3：把圆盘把圆盘把圆盘把圆盘A A
4、和和和和B B移至移至移至移至柱子柱子柱子柱子3 3（借助柱子（借助柱子（借助柱子（借助柱子1 1）第5页/共48页汉诺塔问题归约过程（归约过程（3 3个圆盘）个圆盘）第6页/共48页汉诺塔问题汉诺塔问题归约图汉诺塔问题归约图本原问题本原问题本原问题本原问题与或图与或图CBA第7页/共48页问题归约法与或图表示：与或图表示：用一个类似于图的结构来表示把问题归约为后继问题的替换集合。用一个类似于图的结构来表示把问题归约为后继问题的替换集合。与图：与图：把一个复杂问题把一个复杂问题分解为若干个较为简单的分解为若干个较为简单的子问题，形成子问题，形成“与与”树。树。或图：或图：把原问题变换为把原问题
5、变换为若干个较为容易求解的新若干个较为容易求解的新问题，形成问题，形成“或或”树。树。第8页/共48页问题归约法与或图表示：与或图表示：BCDEFGAHMBCDEFGAN子问题替代集合结构图子问题替代集合结构图与或图与或图第9页/共48页问题归约法一些关于与或图的术语一些关于与或图的术语起始节点起始节点对应于原对应于原始问题描始问题描述述终叶节点对应于本原问题终叶节点对应于本原问题第10页/共48页问题归约法与或图的构成规则与或图的构成规则1 1）与或图中的每个节点代表一个要解决）与或图中的每个节点代表一个要解决的单一问题或问题集合。图中所含起始节的单一问题或问题集合。图中所含起始节点对应于原
6、始问题点对应于原始问题A A。2 2）对应于本原问题的节点称为终叶节点，）对应于本原问题的节点称为终叶节点，它没有后继节点。它没有后继节点。3 3）对于把算符应用于问题）对于把算符应用于问题A A的每种可能的每种可能情况，都把问题变换为一个子问题集合；情况，都把问题变换为一个子问题集合；有向弧线自有向弧线自A A指向后继节点表示所求得的指向后继节点表示所求得的子问题集合。子问题集合。HMBCDEFGAN第11页/共48页问题归约法与或图的构成规则与或图的构成规则4 4）一般对于代表两个或两个以上子问题集）一般对于代表两个或两个以上子问题集合的每个节点，有向弧线从此节点指向次子合的每个节点，有向
7、弧线从此节点指向次子问题集合中的各个节点。由于只有当集合中问题集合中的各个节点。由于只有当集合中所有项都有解时，这个子问题的集合才能获所有项都有解时，这个子问题的集合才能获得解答，所以这些子问题节点叫做与节点。得解答，所以这些子问题节点叫做与节点。5 5）特殊情况下，当只有一个算符可应用于）特殊情况下，当只有一个算符可应用于问题问题A A，而且这个算符产生具有一个以上子，而且这个算符产生具有一个以上子问题的某个集合时，由上述规则问题的某个集合时，由上述规则3 3）和规则）和规则4 4）所产生的图可以得到简化。）所产生的图可以得到简化。MDEFAADEF简化简化第12页/共48页问题归约法与或图
8、的搜索：与或图的搜索：目的在于表明起始节点是有解的。目的在于表明起始节点是有解的。可解节点可解节点终叶节点是可解节点（对应于本原问题）。终叶节点是可解节点（对应于本原问题）。如果某个非终叶节点含有如果某个非终叶节点含有或后继节点或后继节点，那么只要当其，那么只要当其后继节点至少有一个是可解的时，此非终叶节点才是后继节点至少有一个是可解的时，此非终叶节点才是可解的。可解的。如果某个非终叶节点含有如果某个非终叶节点含有与后继节点与后继节点，那么只有当其，那么只有当其后继节点全部为可解时，此非终叶节点才是可解的。后继节点全部为可解时，此非终叶节点才是可解的。第13页/共48页问题归约法不可解节点不可
9、解节点没有后裔的非终叶节点为不可解节点。没有后裔的非终叶节点为不可解节点。如果某个非终叶节点含有如果某个非终叶节点含有或后继节点或后继节点，那么只有当，那么只有当其其全部后裔为不可解时全部后裔为不可解时，此非终叶节点才是不可解，此非终叶节点才是不可解的。的。如果某个非终叶节点含有如果某个非终叶节点含有与后继节点与后继节点，那么只要当，那么只要当其其后裔至少有一个为不可解时后裔至少有一个为不可解时，此非终叶节点才是，此非终叶节点才是不可解的。不可解的。解树解树由可解节点所构成，并且由这些可解节点可推出初由可解节点所构成，并且由这些可解节点可推出初始节点为可解节点的子树称为解树。始节点为可解节点的
10、子树称为解树。解树中一定包含初始节点，它对应于原始问题。解树中一定包含初始节点，它对应于原始问题。第14页/共48页问题归约法ttttttttt有解节点有解节点无解节点无解节点终叶节点终叶节点与或图例子与或图例子原始问题原始问题有一有一个以上的解个以上的解原始问题原始问题有有解解第15页/共48页内容提要第二章：知识表示方法第二章：知识表示方法第二章：知识表示方法第二章：知识表示方法1.1.状态空间法状态空间法2.2.问题归约法问题归约法3.3.谓词逻辑法谓词逻辑法4.4.语义网络法语义网络法5.5.其他方法其他方法第16页/共48页谓词逻辑法命题逻辑与谓词逻辑命题逻辑与谓词逻辑命题逻辑与谓词
11、逻辑是最先用于人工智能的两种逻辑，对于知识的形命题逻辑与谓词逻辑是最先用于人工智能的两种逻辑，对于知识的形式化表示，特别是定理的证明发挥了重要作用式化表示，特别是定理的证明发挥了重要作用虽然命题逻辑能够把客观世界的各种事实表示为逻辑命题，但是它具虽然命题逻辑能够把客观世界的各种事实表示为逻辑命题，但是它具有较大的局限性。命题逻辑只能进行命题间有较大的局限性。命题逻辑只能进行命题间关系关系的推理，无法解决与的推理，无法解决与命题结构命题结构和和成分成分有关的推理问题，有关的推理问题，不适合表示比较复杂的问题不适合表示比较复杂的问题。谓词逻辑是在命题逻辑的基础上发展而来的，命题逻辑可以看作是谓谓词
12、逻辑是在命题逻辑的基础上发展而来的，命题逻辑可以看作是谓词逻辑的一种特殊形式。词逻辑的一种特殊形式。第17页/共48页谓词逻辑法命题命题命题是具有真假意义的语句命题是具有真假意义的语句命题代表人们进行思维时的一种判断，若命题的意义为真，称它的真命题代表人们进行思维时的一种判断，若命题的意义为真，称它的真值为值为“真真”，记作，记作“T”；若命题的意义为假，称它的真值为；若命题的意义为假，称它的真值为“假假”，记作记作“F”。例如：。例如：p“西安是陕西省省会西安是陕西省省会”“10大于大于6”是真值为是真值为“T”的命题的命题p“月亮是方的月亮是方的”“煤炭是白的煤炭是白的”是真值为是真值为“
13、F”的命题的命题一个命题不能同时即为真又为假，但可以在一定条件下为真，在另一一个命题不能同时即为真又为假，但可以在一定条件下为真，在另一种条件下为假。例如：种条件下为假。例如：p“1+1=10”1+1=10”在二进制情况下为真，十进制情况下为假在二进制情况下为真，十进制情况下为假第18页/共48页谓词逻辑法命题命题没有真假意义的语句，如感叹句、疑问句等，不是没有真假意义的语句，如感叹句、疑问句等，不是命题。命题。通常用大写英文字母表示一个命题，例如：通常用大写英文字母表示一个命题，例如：p P P：西安是座古老的城市：西安是座古老的城市命题逻辑的局限性？命题逻辑的局限性？客观事物的结构及逻辑特
14、征？客观事物的结构及逻辑特征？不同事物间的共同特征？不同事物间的共同特征？第19页/共48页谓词逻辑法命题逻辑的局限性？命题逻辑的局限性？命题这种表示方法无法把它所描述的客观事物的结构及逻辑特征反映命题这种表示方法无法把它所描述的客观事物的结构及逻辑特征反映出来，也不能把不同事物间的共同特征表述出来出来，也不能把不同事物间的共同特征表述出来例如，用字母例如，用字母P P表示表示“小张是老张的儿子小张是老张的儿子”这一命题，则无法表述出老这一命题，则无法表述出老张与小张是父子关系张与小张是父子关系又如，又如，“张三是学生张三是学生”，“李四是学生李四是学生”这两个命题，用命题逻辑表这两个命题，用
15、命题逻辑表示时，无法把两者的共同特征示时，无法把两者的共同特征“都是学生都是学生”形式的表示出来形式的表示出来可否用可否用 Student（“张三张三”），），Student（“李四李四”）表示上述命题表示上述命题？谓词逻辑谓词逻辑第20页/共48页谓词逻辑法谓词谓词在谓词逻辑中，命题是用形如在谓词逻辑中，命题是用形如P(x1,x2,xn)的谓词来表述的。一个谓的谓词来表述的。一个谓词可分为词可分为谓词名谓词名与与个体个体两个部分两个部分个体：个体：是命题的主语，表示独立存在的事物或某个抽象的概念是命题的主语，表示独立存在的事物或某个抽象的概念p “x1,x2,xn”是个体，一般用小写字母表示
16、是个体，一般用小写字母表示p 个体可以是个体常量、变元或函数个体可以是个体常量、变元或函数谓词名：谓词名：表示个体的性质、状态或个体之间的关系表示个体的性质、状态或个体之间的关系p“P”是谓词名，一般用大写字母表示是谓词名，一般用大写字母表示p 称称P 是一个是一个n元谓词。元谓词。第21页/共48页谓词逻辑法谓词谓词对于命题对于命题“张三是学生张三是学生”，用谓词可以表示为：，用谓词可以表示为：Student（“张三张三”）。其中，）。其中，Student是谓词名，是谓词名，“张三张三”是个体，是个体，Student刻画了刻画了“张三张三”是个学生这一特征。是个学生这一特征。在谓词中，个体可
17、以是常量，也可以是变元，还可在谓词中，个体可以是常量，也可以是变元，还可以是一个函数。例如，对于命题以是一个函数。例如，对于命题“x10”可以表示可以表示为为more（x,10），其中），其中x是变元。又如，命题是变元。又如，命题“小张小张的父亲是老师的父亲是老师”，可以表示为，可以表示为Teacher（father（Zhang），其中，），其中，father（Zhang）是一个函数。）是一个函数。当谓词中的变元都用特定的个体取代时，谓词就具当谓词中的变元都用特定的个体取代时，谓词就具有一个确定的真值有一个确定的真值“T”或或“F”。第22页/共48页谓词逻辑法谓词谓词在在n元谓词元谓词 P(
18、x1,x2,xn)中，若每个个体均为常量、变元或函数，则中，若每个个体均为常量、变元或函数，则称它为称它为一阶谓词一阶谓词。如果某个个体本身又是一个一阶谓词，则称它为如果某个个体本身又是一个一阶谓词，则称它为二阶谓词二阶谓词，如此类推。，如此类推。个体变元的取值范围称为个体变元的取值范围称为个体域个体域。个体域可以是有限的，也可以是无。个体域可以是有限的，也可以是无限的。例如用限的。例如用I（x）表示）表示“x是整数是整数”，则个体域为所有整数，是无限，则个体域为所有整数，是无限的。的。谓词与函数不同谓词与函数不同，谓词的真值是，谓词的真值是”T“或或”F“，而函数的值是个体域，而函数的值是个
19、体域中的一个个体，无真值可言。中的一个个体，无真值可言。第23页/共48页谓词逻辑法谓词演算谓词演算谓词逻辑语言的语法和语义谓词逻辑语言的语法和语义p基本符号：基本符号：谓词符号、变量符号、函数符号、常量符号、括号和逗号谓词符号、变量符号、函数符号、常量符号、括号和逗号p原子公式：原子公式：原子公式由若干谓词符号和项组成原子公式由若干谓词符号和项组成谓词符号谓词符号规定定义域内的一个相应关系规定定义域内的一个相应关系常量符号常量符号是最简单的项，表示论域内的物体或实体是最简单的项，表示论域内的物体或实体变量符号变量符号也是项，不明确涉及是哪一个实体也是项，不明确涉及是哪一个实体函数符号函数符号
20、表示论域内的函数，是从论域内的一个实体到另外一个实体的映射表示论域内的函数，是从论域内的一个实体到另外一个实体的映射例如：原子公式例如：原子公式 Married father(LI),mother(LI)表示表示“李（李（LILI）的父）的父亲和他的母亲结婚亲和他的母亲结婚”第24页/共48页谓词逻辑法连词和量词连词和量词p连词连词合取：合取：符号符号“”，表示所连结的两个命题之间具有表示所连结的两个命题之间具有“与与”的关系。的关系。析取：析取：符号符号“”，表示所连结的两个命题之间具有，表示所连结的两个命题之间具有“或或”的关系的关系蕴涵：蕴涵：符号符号“”，表示，表示“若若则则”的语义。
21、的语义。PQPQ读作读作“如果如果P P，则，则QQ”其中，其中，P P称为条件的前件，称为条件的前件，QQ称为条件的后件。称为条件的后件。非：非：符号符号“”，表示对其后面的命题的否定，表示对其后面的命题的否定双条件：双条件：符号符号“”，表示，表示“当且仅当当且仅当”的语义。的语义。P PQQ读作读作“P P当且仅当当且仅当QQ”。第25页/共48页谓词逻辑法p量词量词全称量词：全称量词：符号符号“”，意思是意思是“所有的所有的”、“任一任一个个”x x读作读作“对一切对一切x x”,或或“对每一对每一x x”，或，或“对任一对任一x x”。命题命题(x)P(x)x)P(x)为真，当且仅当
22、对论域中的所有为真，当且仅当对论域中的所有x x，都有，都有P(x)P(x)为为真真命题命题(x)P(x)x)P(x)为假，当且仅当至少存在论域中的一个为假，当且仅当至少存在论域中的一个x x，使得，使得P(x)P(x)为假为假存在量词：存在量词：符号符号“”，意思是意思是“至少有至少有”、“存在存在”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)为假，当且仅当
23、对论域中的所有为假，当且仅当对论域中的所有x x，都有，都有P(x)P(x)为假为假 第26页/共48页谓词逻辑法谓词公式谓词公式原子谓词公式：原子谓词公式：是由谓词符号和若干项组成的谓词演算。是由谓词符号和若干项组成的谓词演算。分子谓词公式：分子谓词公式：可以用可以用连词连词把原子谓词公式组成复合谓词公式，把原子谓词公式组成复合谓词公式，并把它叫做分子谓词公式。并把它叫做分子谓词公式。合式公式（合式公式（WFF，Well-formed Formulas）：）：通常把通常把合式公合式公式式叫做叫做谓词公式谓词公式，递归定义如下：，递归定义如下：p(1)原子谓词公式是合式公式原子谓词公式是合式公
24、式p(2)若若A为合式公式，则为合式公式，则 A也是一个合式公式也是一个合式公式p(3)若若A,B是合式公式，则是合式公式，则AB，AB，AB，AB也都是合式公式也都是合式公式p(4)若若A是合式公式，是合式公式，x为为A中的自由变元，则中的自由变元，则(x)A和和(x)A都是都是合式公式合式公式p(5)只有按上述规则只有按上述规则(1)至至(4)求得的那些公式，才是合式公式。求得的那些公式，才是合式公式。第27页/共48页谓词逻辑法谓词公式谓词公式用谓词公式表示知识时，需要首先用谓词公式表示知识时，需要首先定义谓词定义谓词，然后再用，然后再用连接连接词把有关的谓词连接起来，形成一个谓词词把有
25、关的谓词连接起来，形成一个谓词公式表达一个完整的意义。公式表达一个完整的意义。例例1：设有下列知识设有下列知识刘欢比他父亲出名。刘欢比他父亲出名。高扬是计算机系的一名学生，但他不喜欢编程高扬是计算机系的一名学生，但他不喜欢编程。任何整数或者为正或者为负。任何整数或者为正或者为负。为了用谓词公式表示上述知识，首先需要定义谓词：为了用谓词公式表示上述知识，首先需要定义谓词：FAMOUS(x,y):x比比y出名出名COMPUTER(x):x 是计算机系的是计算机系的LIKE(x,y):x 喜欢喜欢 y第28页/共48页谓词逻辑法I(x)表示表示“x是整数是整数”P(x)表示表示“x是正数是正数”N(
26、x)表示表示“x是负数是负数”此时可用谓词公式把上述知识表示为此时可用谓词公式把上述知识表示为:刘欢比他父亲出名刘欢比他父亲出名:FAMOUS(liuhuan,father(liuhuan)高扬是计算机系的一名学生，但他不喜欢编程高扬是计算机系的一名学生，但他不喜欢编程:COMPUTER(gaoyang)LIKE(gaoyang,programing)任何整数或者为正或者为负任何整数或者为正或者为负:(x)(I(x)(P(x)N(x)第29页/共48页谓词逻辑法谓词公式谓词公式例例2：用谓词逻辑描述右图中的房子的概念用谓词逻辑描述右图中的房子的概念p个体个体：A,Bp谓词谓词：SUPPORT(
27、x,y)：表示：表示 x 被被 y支撑着支撑着 WEDRE(x)：表示：表示 x 是楔形块是楔形块 BRICK(y)：表示：表示 y 是长方块是长方块 p其中其中 x,y是个体变元，它们的个体域是个体变元，它们的个体域A,Bp房子的概念可以表示成一组合式谓词公式的合取式：房子的概念可以表示成一组合式谓词公式的合取式：SUPPORT(A,B)WEDGE(A)BRICK(B)第30页/共48页谓词逻辑法合式公式的性质合式公式的性质若若P、Q是两个合式公式，则由这两个合式公式所组成的复合表达式可是两个合式公式，则由这两个合式公式所组成的复合表达式可由下列真值表给出。由下列真值表给出。PQPPQPQP
28、QPQTTFTTTTTFFTFFFFTTTFTFFFTFFTT第31页/共48页谓词逻辑法合式公式的性质合式公式的性质如果两个合式公式，无论如何解释，其真值表都是相同的，那么我们就称此两合式公式是如果两个合式公式，无论如何解释，其真值表都是相同的，那么我们就称此两合式公式是等价的等价的。应用上述真值表可以确立下列等价关系：应用上述真值表可以确立下列等价关系：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 R)=(P Q)(P R
29、)P (Q R)=(P Q)(P R)第32页/共48页谓词逻辑法p（5）交换律：）交换律：P Q=Q PP Q=Q Pp（6）结合律：）结合律：P (Q R)=(P Q)RP (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第33页/共48页谓词逻辑法此外还可以确立下列等价关系：此外还可以确立下列等价关系：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
30、)=(x)P(x)(x)Q(x)p(x)P(x)=(y)P(y)p(x)P(x)=(y)P(y)第34页/共48页谓词逻辑法置换与合一置换与合一置换置换p 推理规则：推理规则：用合式公式的集合产生新的合式公式用合式公式的集合产生新的合式公式假元推理假元推理全称化推理全称化推理综合推理综合推理 W2W1 W1 W2 W(A)(x)W(x)任意常量任意常量A W2(A)W1(A)(x)W1(x)W2(x)寻找寻找A对对x的的置置换换，使，使W1(A)与与W1(x)一致一致第35页/共48页谓词逻辑法置换与合一置换与合一置换（置换（SubstitutionSubstitution）p置换的定义：置换
31、的定义：置换是用置换是用变元、常量、函数变元、常量、函数来替换来替换变元变元，使该变元不使该变元不在公式中出现在公式中出现。p置换是形如置换是形如 t1/x1,t2/x2,，tn/xn的有限集合。的有限集合。t1，t2，tn是项是项x1，x2，xn是互不相同的变元是互不相同的变元ti/xi表示用表示用ti项替换变元项替换变元xi，不允许，不允许ti和和xi相同，也不允许变元相同，也不允许变元xi循环地出现在另一个循环地出现在另一个tj中中第36页/共48页谓词逻辑法置换与合一置换与合一置换（置换（SubstitutionSubstitution）p例如例如a/x,f(b)/y，w/z 是一个置
32、换是一个置换g(y)/x,f(x)/y 不是一个置换不是一个置换g(a)/x,f(x)/y 不是一个置换不是一个置换第37页/共48页谓词逻辑法置换与合一置换与合一置换（置换（SubstitutionSubstitution）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(
33、y),B s2=Px,f(A),B Px,f(y),B s3=Pq(z),f(A),B Px,f(y),B s4=Pc,f(A),B 第38页/共48页谓词逻辑法置换与合一置换与合一置换（置换（SubstitutionSubstitution）p置换是可结合的置换是可结合的用用s1s2表示两个置换表示两个置换s1和和s2的的合成合成，L表示一个表达式，则有表示一个表达式，则有（Ls1）s2 =L（s1s2）即用即用s1和和s2相继作用于表达式相继作用于表达式L是与用是与用s1s2作用于作用于L一样的一样的进一步推广：（进一步推广：（s1s2）s3 =s1（s2s3）p一般说来，置换是不可交换的
34、，即一般说来，置换是不可交换的，即 s1s2 s2s1第39页/共48页谓词逻辑法置换与合一置换与合一合一（合一（UnificationUnification）p合一的定义：合一的定义：寻找项对变量的寻找项对变量的置换置换，以使，以使两表达式一致两表达式一致。p如果一个置换如果一个置换s作用于表达式集合作用于表达式集合Ei的每个元素，用的每个元素，用Eis表示置换的集。称表表示置换的集。称表达式达式Ei是是可合一可合一的，如果存在一个置换的，如果存在一个置换s使得：使得：E1s=E2s=E3s=那么，称此那么，称此s为为Ei的的合一者合一者（unifier），因为），因为s的作用是使集合的作用
35、是使集合Ei成为单一成为单一形式。形式。p例如，设有公式集例如，设有公式集 E=P(x,y,f(y),P(a,g(x),z)则下式是它的一个合一：则下式是它的一个合一：s=a/x,g(a)/y,f(g(a)/z第40页/共48页谓词逻辑法谓词逻辑法举例：谓词逻辑法举例：猴子和香蕉问题猴子和香蕉问题描述状态的谓词：描述状态的谓词：pAT(x,y)：x在在y处处pONBOX：猴子在箱子上猴子在箱子上pHB：猴子得到香蕉猴子得到香蕉个体域：个体域：px：monkey,box,bananapy：a,b,c问题的初始状态问题的初始状态pAT(monkey,a)pAT(box,b)p ONBOX p HB
36、问题的目标状态问题的目标状态pAT(monkey,c)pAT(box,c)pONBOX pHB第41页/共48页猴子和香蕉问题描述操作的谓词描述操作的谓词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(monk
37、ey,w)，AT(box,w)pClimbbox：猴子爬上箱子猴子爬上箱子条件：条件：ONBOX，AT(monkey,w)，AT(box,w)动作动作：删除表：删除表：ONBOX；添加表：；添加表：ONBOXpGrasp：猴子摘取香蕉猴子摘取香蕉条件：条件：ONBOX，AT(box,c)动作：动作：删除表：删除表：HB；添加表：；添加表：HB第42页/共48页猴子和香蕉问题猴子和香蕉问题求解过程：猴子和香蕉问题求解过程：初始状态初始状态AT(monkey,a)AT(box,b)ONBOX HBGoto(a,b)状态状态1AT(monkey,b)AT(box,b)ONBOX HBPushbox(
38、b,c)状态状态2AT(monkey,c)AT(box,c)ONBOX HBClimbbox状态状态3AT(monkey,c)AT(box,c)ONBOX HB目标状态目标状态AT(monkey,c)AT(box,c)ONBOX HBGrasp第43页/共48页谓词逻辑法主要优点主要优点自然：自然：一阶谓词逻辑是一种接近于自然语言的形式语言系统，谓词逻辑表示法接近于人们对问题的直一阶谓词逻辑是一种接近于自然语言的形式语言系统，谓词逻辑表示法接近于人们对问题的直观理解观理解明确：明确：有一种标准的知识解释方法，因此用这种方法表示的知识明确、易于理解有一种标准的知识解释方法，因此用这种方法表示的知
39、识明确、易于理解精确：精确：谓词逻辑的真值只有谓词逻辑的真值只有“真真”与与“假假”，其表示、推理都是精确的，其表示、推理都是精确的灵活：灵活：知识和处理知识的程序是分开的，无须考虑处理知识的细节知识和处理知识的程序是分开的，无须考虑处理知识的细节模块化：模块化：知识之间相对独立，这种模块性使得添加、删除、修改知识比较容易进行知识之间相对独立，这种模块性使得添加、删除、修改知识比较容易进行第44页/共48页谓词逻辑法主要缺点主要缺点知识表示能力差：知识表示能力差：只能表示确定性知识，而不能表示非确定性知识、过程性知识和启发式知识只能表示确定性知识，而不能表示非确定性知识、过程性知识和启发式知识
40、知识库管理困难：知识库管理困难：缺乏知识的组织原则，知识库管理比较困难缺乏知识的组织原则，知识库管理比较困难存在组合爆炸：存在组合爆炸：由于难以表示启发式知识，因此只能盲目地使用推理规则，这样当系统知识量较大时，由于难以表示启发式知识，因此只能盲目地使用推理规则，这样当系统知识量较大时，容易发生组合爆炸容易发生组合爆炸系统效率低：系统效率低：它把推理演算与知识含义截然分开，抛弃了表达内容中所含有的语义信息，往往使推理它把推理演算与知识含义截然分开，抛弃了表达内容中所含有的语义信息，往往使推理过程冗长，降低了系统效率过程冗长，降低了系统效率第45页/共48页内容提要第二章：知识表示方法第二章：知识表示方法第二章：知识表示方法第二章：知识表示方法1.1.状态空间法状态空间法2.2.问题归约法问题归约法3.3.谓词逻辑法谓词逻辑法4.4.语义网络法语义网络法5.5.其他方法其他方法第46页/共48页第47页/共48页感谢您的欣赏第48页/共48页