湘潭大学 人工智能课件 知识表示方法 part2

1、Artificial Intelligence (AI)人工智能人工智能第二章：知识第二章：知识表示与推理表示与推理内容提要内容提要1.1.状态空间法状态空间法2.2.问题归约法问题归约法3.3.谓词逻辑法谓词逻辑法4.4.语义网络法语义网络法5.5.其他方法其他方法谓词逻辑法v命题逻辑与谓词逻辑命题逻辑与谓词逻辑命题逻辑与谓词逻辑是最先用于人工智能的两种逻辑，命题逻辑与谓词逻辑是最先用于人工智能的两种逻辑，对于知识的形式化表示，特别是定理的证明发挥了重对于知识的形式化表示，特别是定理的证明发挥了重要作用要作用虽然命题逻辑能够把客观世界的各种事实表示为逻辑虽然命题逻辑能够把客观世界的各种事实表

2、示为逻辑命题，但是它具有较大的局限性。命题逻辑只能进行命题，但是它具有较大的局限性。命题逻辑只能进行命题间命题间关系关系的推理，无法解决与的推理，无法解决与命题结构命题结构和和成分成分有关有关的推理问题，的推理问题，不适合表示比较复杂的问题不适合表示比较复杂的问题。谓词逻辑是在命题逻辑的基础上发展而来的，命题逻谓词逻辑是在命题逻辑的基础上发展而来的，命题逻辑可以看作是谓词逻辑的一种特殊形式。辑可以看作是谓词逻辑的一种特殊形式。谓词逻辑法v命题命题命题是具有真假意义的语句命题是具有真假意义的语句命题代表人们进行思维时的一种判断，若命题的意义命题代表人们进行思维时的一种判断，若命题的意义为真，称它

3、的真值为为真，称它的真值为“真真”，记作，记作“T”；若命题的意；若命题的意义为假，称它的真值为义为假，称它的真值为“假假”，记作，记作“F”。例如：。例如：p“长沙是湖南省省会长沙是湖南省省会”“”“10大于大于6”是真值为是真值为“T”的命题的命题p“月亮是方的月亮是方的”“”“煤炭是白的煤炭是白的”是真值为是真值为“F”的命题的命题一个命题不能同时即为真又为假，但可以在一定条件一个命题不能同时即为真又为假，但可以在一定条件下为真，在另一种条件下为假。例如：下为真，在另一种条件下为假。例如：p“1+1=10”1+1=10”在二进制情况下为真，十进制情况下为假在二进制情况下为真，十进制情况下

4、为假谓词逻辑法v命题命题没有真假意义的语句，如感叹句、疑问句等，不是命没有真假意义的语句，如感叹句、疑问句等，不是命题。题。通常用大写英文字母表示一个命题，例如：通常用大写英文字母表示一个命题，例如： p P P：西安是座古老的城市：西安是座古老的城市v命题逻辑的局限性？命题逻辑的局限性？客观事物的结构及逻辑特征？客观事物的结构及逻辑特征？不同事物间的共同特征？不同事物间的共同特征？谓词逻辑法v命题逻辑的局限性？命题逻辑的局限性？命题这种表示方法无法把它所描述的客观事物的结构命题这种表示方法无法把它所描述的客观事物的结构及逻辑特征反映出来，也不能把不同事物间的共同特及逻辑特征反映出来，也不能把

5、不同事物间的共同特征表述出来征表述出来例如，用字母例如，用字母P P表示表示“小张是老张的儿子小张是老张的儿子”这一命题，这一命题，则无法表述出老张与小张是父子关系则无法表述出老张与小张是父子关系又如，又如，“张三是学生张三是学生”，“李四是学生李四是学生”这两个命题，这两个命题，用命题逻辑表示时，无法把两者的共同特征用命题逻辑表示时，无法把两者的共同特征“都是学都是学生生”形式的表示出来形式的表示出来可否用可否用 Student（“张三张三”），）， Student（“李四李四”）表示上述命题？表示上述命题？谓词逻辑谓词逻辑谓词逻辑法v谓词谓词在谓词逻辑中，命题是用形如在谓词逻辑中，命题是用

6、形如P(x1,x2,xn)的谓词来表的谓词来表述的。一个谓词可分为述的。一个谓词可分为谓词名谓词名与与个体个体两个部分两个部分个体：个体： 是命题的主语，表示独立存在的事物或某个抽是命题的主语，表示独立存在的事物或某个抽象的概念象的概念p “x1,x2,xn”是个体，一般用小写字母表示是个体，一般用小写字母表示p 个体可以是个体常量、变元或函数个体可以是个体常量、变元或函数谓词名：谓词名：表示个体的性质、状态或个体之间的关系表示个体的性质、状态或个体之间的关系p “P”是谓词名，一般用大写字母表示是谓词名，一般用大写字母表示p 称称P 是一个是一个n元谓词。元谓词。谓词逻辑法v谓词谓词对于命题

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

8、hang），其中，其中， father（Zhang）是一个函数。）是一个函数。当谓词中的变元都用特定的个体取代时，谓词就具有一个当谓词中的变元都用特定的个体取代时，谓词就具有一个确定的真值确定的真值“T”或或 “F” 。谓词逻辑法v谓词谓词在在n元谓词元谓词 P(x1,x2,xn)中，若每个个体均为常量、变中，若每个个体均为常量、变元或函数，则称它为元或函数，则称它为一阶谓词一阶谓词。如果某个个体本身又是一个一阶谓词，则称它为如果某个个体本身又是一个一阶谓词，则称它为二阶二阶谓词谓词，如此类推。，如此类推。个体变元的取值范围称为个体变元的取值范围称为个体域个体域。个体域可以是有限。个体域可以是

9、有限的，也可以是无限的。例如用的，也可以是无限的。例如用I（x）表示）表示“x是整数是整数”，则个体域为所有整数，是无限的。则个体域为所有整数，是无限的。谓词与函数不同谓词与函数不同，谓词的真值是，谓词的真值是“T”或或“F”，而函，而函数的值是个体域中的一个个体，无真值可言。数的值是个体域中的一个个体，无真值可言。谓词逻辑法v谓词演算谓词演算谓词逻辑语言的语法和语义谓词逻辑语言的语法和语义p谓词逻辑语言的基本符号：谓词逻辑语言的基本符号：- 谓词符号谓词符号- 变量符号变量符号- 函数符号函数符号- 常量符号常量符号- 括号和逗号括号和逗号谓词逻辑法v谓词演算谓词演算谓词逻辑语言的语法和语义

10、谓词逻辑语言的语法和语义p原子公式：原子公式：原子公式由若干谓词符号和项组成原子公式由若干谓词符号和项组成谓词符号谓词符号规定定义域内的一个相应关系规定定义域内的一个相应关系常量符号常量符号是最简单的项，表示论域内的物体或实体是最简单的项，表示论域内的物体或实体变量符号变量符号也是项，不明确涉及是哪一个实体也是项，不明确涉及是哪一个实体函数符号函数符号表示论域内的函数，是从论域内的一个实体表示论域内的函数，是从论域内的一个实体到另外一个实体的映射到另外一个实体的映射例如：原子公式例如：原子公式 Married father(LI) , Married father(LI) , mother(L

11、I) mother(LI) 表示表示“李（李（LILI）的父亲和他的母亲结婚）的父亲和他的母亲结婚”谓词逻辑法连词和量词连词和量词p连词连词合取：合取：符号符号“ ” ”， 表示所连结的两个命题之间表示所连结的两个命题之间具有具有“与与”的关系。的关系。析取：析取： 符号符号“ ”“ ”，表示所连结的两个命题之间，表示所连结的两个命题之间具有具有“或或”的关系的关系蕴涵：蕴涵：符号符号“ ” “ ” ，表示，表示“若若则则”的语义。的语义。PQPQ读作读作“如果如果P P，则，则Q”Q”其中，其中，P P称为条件的前件，称为条件的前件，Q Q称为条件的后件。称为条件的后件。非：非：符号符号“

12、” ”（），表示对其后面的命题的否定（），表示对其后面的命题的否定双条件：双条件：符号符号“ ” ”，表示，表示“当且仅当当且仅当”的语义。的语义。 P PQ Q读作读作“P P当且仅当当且仅当Q”Q”。谓词逻辑法连词和量词连词和量词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(

13、x)为假，为假，当且仅当至少存在论域当且仅当至少存在论域中的一个中的一个x x，使得，使得P(x)P(x)为假为假谓词逻辑法连词和量词连词和量词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，

14、都有，都有P(x)P(x)为假为假 谓词逻辑法v谓词公式谓词公式原子谓词公式：原子谓词公式：p是由谓词符号和若干项组成的谓词演算。是由谓词符号和若干项组成的谓词演算。p若若t1,t2,tn是项，是项，P是谓词，则称是谓词，则称P(t1,t2,tn)为原子为原子谓词公式。谓词公式。分子谓词公式：分子谓词公式：p可以用可以用连词连词把原子谓词公式组成复合谓词公式，并把原子谓词公式组成复合谓词公式，并把它叫做分子谓词公式。把它叫做分子谓词公式。谓词逻辑法v谓词公式谓词公式合式公式（合式公式（WFF，Well-formed Formulas）：）：通常把通常把合合式公式式公式叫做叫做谓词公式谓词公式，

15、递归定义如下：，递归定义如下：p(1) 原子谓词公式是合式公式原子谓词公式是合式公式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)求得的那些公式，才是合式求得的那些公式，才是合式公式。公式。谓词逻辑法v谓词公式谓词公式用谓词公式表示知识时，需要首先用谓词公式表示知识时，需要首先定义谓

16、词定义谓词，然后再，然后再用用连接连接词把有关的谓词连接起来，形成一个谓词公式词把有关的谓词连接起来，形成一个谓词公式表达一个完整的意义。表达一个完整的意义。 例例1：设有下列知识设有下列知识 刘欢比他父亲出名。刘欢比他父亲出名。 高扬是计算机系的一名学生，但他不喜欢编程高扬是计算机系的一名学生，但他不喜欢编程 。 任何整数或者为正或者为负。任何整数或者为正或者为负。为了用谓词公式表示上述知识，首先需要定义谓词：为了用谓词公式表示上述知识，首先需要定义谓词： FAMOUS (x, y) : x比比y出名出名 COMPUTER ( x ) : x 是计算机系的是计算机系的 LIKE (x, y

17、) : x 喜欢喜欢 y谓词逻辑法 I(x)表示表示“x是整数是整数” P(x)表示表示“x是正数是正数” N(x)表示表示“x是负数是负数” 此时可用谓词公式把上述知识表示为此时可用谓词公式把上述知识表示为: 刘欢比他父亲出名刘欢比他父亲出名: FAMOUS ( liuhuan, father ( liuhuan ) 高扬是计算机系的一名学生，但他不喜欢编程高扬是计算机系的一名学生，但他不喜欢编程 : COMPUTER(gaoyang)LIKE(gaoyang, programing) 任何整数或者为正或者为负任何整数或者为正或者为负: ( x)(I(x) (P(x) N(x)谓词逻辑法v谓

18、词公式谓词公式例例2：用谓词逻辑描述右图中的房子的概念用谓词逻辑描述右图中的房子的概念p个体个体 ：A , Bp谓词谓词 ：SUPPORT( x,y )：表示：表示 x 被被 y支撑着支撑着 WEDGE ( x )：表示：表示 x 是楔形块是楔形块 BRICK( y )：表示：表示 y 是长方块是长方块 p其中其中 x , y是个体变元，它们的个体域是个体变元，它们的个体域A,Bp房子的概念可以表示成一组合式谓词公式的合取式：房子的概念可以表示成一组合式谓词公式的合取式： SUPPORT(A,B) WEDGE( A ) BRICK( B )谓词逻辑法v合式公式的性质合式公式的性质若若P、Q是两

19、个合式公式，则由这两个合式公式所组成是两个合式公式，则由这两个合式公式所组成的复合表达式可由下列真值表给出。的复合表达式可由下列真值表给出。PQPPQPQPQPQTTFTTTTTFFTFFFFTTTFTFFFTFFTT谓词逻辑法v合式公式的性质合式公式的性质如果两个合式公式，无论如何解释，其真值表都是相如果两个合式公式，无论如何解释，其真值表都是相同的，那么我们就称此两合式公式是同的，那么我们就称此两合式公式是等价的等价的。应用上述真值表可以确立下列等价关系：应用上述真值表可以确立下列等价关系：p（1）否定之否定：）否定之否定： ( P ) = Pp（2）( P Q ) = ( P Q ) 或

20、者或者 ( P Q ) = ( P Q ）p（3）狄）狄 摩根定律：摩根定律： ( P Q ) = P Q ( P Q ) = P Q谓词逻辑法p（4）分配律：）分配律： P ( Q 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

21、P F = F , P T = T p（9）互余律：）互余律： P P = T, P P = F此外还可以确立下列等价关系：此外还可以确立下列等价关系：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 推理规则：推理规则：用合式公式的集合产生新的合式公式用合式

22、公式的集合产生新的合式公式 假元推理假元推理 全称化推理全称化推理 综合推理综合推理 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的有限集合。的有限集

23、合。 t1，t2， ， tn是项是项 x1，x2， ， 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置换与合一置换与合一置换（置换（Substitutio

24、nSubstitution）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 s4 = Pc,

25、 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谓词逻辑法v置换与合一置换与合一合一（合一（Unification

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

27、ication）p例如，设有公式集例如，设有公式集 E= P( x, y, f(y), P( a, g(x), z) 则下式是它的一个合一：则下式是它的一个合一： s=a/x, g(a)/y, f(g(a)/z猴子和香蕉问题描述操作的谓词描述操作的谓词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)，

28、AT(box, v) 动作：动作：删除表：删除表：AT(monkey, v)，AT(box, v) 添加表：添加表：AT(monkey, w)，AT(box,w)pClimbbox：猴子爬上箱子猴子爬上箱子 条件：条件： ONBOX ，AT(monkey, w)，AT(box,w) 动作动作：删除表：删除表： ONBOX；添加表：；添加表：ONBOXpGrasp：猴子摘取香蕉猴子摘取香蕉 条件：条件：ONBOX，AT(box, c) 动作：动作：删除表：删除表： HB；添加表：；添加表：HB猴子和香蕉问题v 猴子和香蕉问题求解过程：猴子和香蕉问题求解过程：初始状态初始状态AT(monkey, a) AT(box, b) ONBOX H