人工智能第2章(知识表示方法3谓词逻辑)ppt课件.ppt

《人工智能第2章(知识表示方法3谓词逻辑)ppt课件.ppt》由会员分享，可在线阅读，更多相关《人工智能第2章(知识表示方法3谓词逻辑)ppt课件.ppt（93页珍藏版）》请在三一办公上搜索。

1、人 工 智 能Artificial Intelligence (AI),第2章 知识表示方法2.1 状态空间法2.2 问题归约法2.3 谓词逻辑法,五房间问题： 1、有5栋5种颜色的房子2、每一位房子的主人国籍都不同3、这5个人只喝一个牌子的饮料，只抽一个牌子的香烟，只养一种宠物4、没有人有相同的宠物，抽相同牌子的香烟，喝相同的饮料谁养鱼？,已知条件：1、英国人住在红房子里2、瑞典人养了一条狗3、丹麦人喝茶4、绿房子在白房子左边5、绿房子主人喝咖啡6、抽PALLMALL烟的人养了一只鸟7、黄房子主人抽DUNHILL烟8、住在中间那间房子的人喝牛奶9、挪威人住在第一间房子10、抽混合烟的人住在养

2、猫人的旁边11、养马人住在DUNHILL烟的人旁边12、抽BLUEMASTER烟的人喝啤酒13、德国人抽PRINCE烟14、挪威人住在蓝房子旁边15、抽混合烟的人的邻居喝矿泉水,挪威人,牛奶,4、绿房子在白房子左边5、绿房子主人喝咖啡,咖啡,1、英国人住在红房子里,英国人,7、黄房子主人抽DUNHILL烟11、养马人住在DUNHILL烟的人旁边,DUNHILL,马,3、丹麦人喝茶12、抽BLUEMASTER烟的人喝啤酒,矿泉水,2、瑞典人养了一条狗3、丹麦人喝茶12、抽BLUEMASTER烟的人喝啤酒13、德国人抽PRINCE烟,瑞典人,BLUEMASTER,啤酒,狗,丹麦人,茶,德国人,PR

3、INCE,混合烟,PALLMALL,鸟,猫,鱼,推理的一般形式,已知： 事实一，事实二， 如果事实一，那么结论一； 如果事实二，那么结论二；得到：结论一，结论二，如果将事实和规则抽象出来，不涉及具体内容，借助一些符号来表示，推理过程可形式化为： P：某已知事实 PQ：如果P，则Q 结论：Q,自然语言不适合计算机推理 如：小王不方便接电话，他方便去了。需要一种无歧义，方便存储和表达的形式化符号表征体系,命题逻辑,谓词逻辑,如果今天不下雨，我就去你家,今天没有下雨,我去了你家,Q,P,PQ,命题逻辑核心思想：原子命题不可再分,凡人都会死,苏格拉底是人,苏格拉底会死,Man(Socrates),Mo

4、rtal(Socrates),x(Man(x)Mortal(x),2.3 谓词逻辑法数理逻辑（符号逻辑）是用数学方法研究形式逻辑的一个分支。它通过符号系统来表达客观对象以及相关的逻辑推理。常用的是命题逻辑和谓词逻辑,谓词逻辑是数理逻辑的基本形式，是基于谓词分析的一种形式化（数学）语言人工智能中的谓词逻辑法是指用一阶谓词来描述问题求解和定理证明（限于本课程）,2.3.0 命题逻辑的复习,1、命题逻辑的基本概念命题 是能够判断真或假的陈述句通常用大写字母来表示，如A, B, P, Q等命题的真假值一般用 T 或 F 来表示,例：雪是白的。（陈述句，T）雪是蓝的。（陈述句，F）雪是黑的。（陈述句，F

5、）他是学生。（陈述句，他泛指，无法判断真假）你今天上课没有？（疑问句）去北校区，请坐校车！（祈使句）,命题逻辑是研究命题及命题之间关系的符号逻辑系统。在命题逻辑中，表示单一意义的命题，称之为原子命题。原子命题通过 “联结词” 构成 复合命题。,五个联结词：, “” 表示 “非”复合命题P为真，当且仅当P为假。, “” 表示 “合取”复合命题“PQ”为真，当且仅当P和Q都为真。, “” 表示 “蕴含”复合命题“PQ”为假，当且仅当P为真且Q为假。, “” 表示 “析取”复合命题“PQ”为真，当且仅当P、Q两者之一为真。, “” 表示 “等价”复合命题“PQ”为真，当且仅当P、Q同时为真、或者同时

6、为假。,联接词的优先顺序：非 、合取 、析取 、蕴含 、等价注：可以用括号表示优先级,真值表,命题变元：用符号P、Q等表示的不具有固定、具体含义的命题。它可以表示具有“真”、“假”含义的各种命题。命题变元可以利用联结词构成所谓的合适公式。,合适公式的定义若P为原子命题，则P为合适公式，称为原子公式。若P是合适公式，则P也是一个合适公式。,若P和Q是合适公式，则PQ、 PQ 、PQ 、PQ都是合适公式。经过有限次使用规则1、2、3，得到的由原子公式、联结词和园括号所组成的符号串，也是合适公式。,对于合适公式，规定下列运算优先级： 逻辑联结词的运算优先次序为： 、 、 、 同级联结词按出现顺序优先

7、运算,在命题逻辑中，主要研究推理的有效性。即：能否根据一些合适公式（前提）推导出新的合适公式（结论）。,一些合适公式（前提条件）,合适公式（结论）,？,在命题逻辑中，最基本的单元是命题，它是作为一个不可分割的整体。例如：雪是黑的命题逻辑具有较大的局限性，不合适于表达比较复杂的问题。,例：所有科学都是有用的（假设1）。数理逻辑是科学（假设2）。所以，数理逻辑是有用的（结论）。很明显，我们无法用两个假设推断出结论。,谓词逻辑是命题逻辑的扩充和发展。它将一个原子命题分解成客体和谓词两个组成部分。例如： 雪 是黑的 客体 谓词本课程主要介绍一阶谓词逻辑。,2.3.1 谓词演算,1、语法与语义谓词逻辑的

8、基本组成部分谓词变量函数常量圆括号、方括号、花括号和逗号,例“机器人（Robot）在第一个房间（Room1）内”，可以表示为： INROOM（ROBOT，r1）其中 INROOM是谓词 ROBOT和r1是常量,谓词是指个体（客体）所具有的性质或者若干个体之间的关系。用大写字母来表示。 个体是可以具体的（如: 小张、3、5）也可以是抽象的（如: x, y）。,例：小明是学生，A表示是“是学生”，x表示“小明”，记作A(x)。x大于y，G表示“大于”，记作G（x, y）。,论域：由个体组成的集合。（个体）变量：定义在某一个论域上的变量。用x, y, z 来表示。函数（或函词）：以个体为变量，以个体

9、为值的函数。一般用小写字母来表示，例如 f(x), f(x,a)。,如果谓词有 n 个变量，称之为 n 元谓词，并约定 0 元谓词就是命题（谓词的特例）。如果函数有 n 个个体，称之为 n 元函数，并约定 0 元函数就是常量。常量习惯上用小写字母来表示，如a, b, c。,项的定义：常量是项变量是项如果 f 是n元函数，且t1 , tn(n1)是项，则 f (t1 , tn)也是项所有的项都必须是有限次应用上述规则产生的,项的例子：常量：a变量：x函数：f(x,a) g(f(x,a),原子（谓词）公式的（递归）定义：原子命题是原子公式如果t1,tn(n1)是项，P是谓词，则P(t1,tn)是原

10、子公式其它表达式都不是原子公式,原子公式的例子1、原子公式：P（原子命题）2、项：x, a, f(x, a)，谓词：P 原子公式：P(x, a, f(x,a),2、连词和量词,联结词（连词）就是命题逻辑中的五个，它们的含义也是一样的。,两个量词：全称量词，记作“x”,含义是 “对每一个x” 或“对一切x”。存在量词，记作“x”，含义是 “存在某个x” 、“有一个x” 或者 “某些x”。,All,A,Exist,E,例1：“所有的机器人都是灰色的”，用谓词逻辑可以表示成： （x）ROBOT(x) COLOR(x，gray),例2： “一号房间里有一个物体”，可以表示成 （x）INROOM（x ,

11、 r1）,我们称 x 是被量化了的变量，称为约束变量。否则称之为自由变量。一阶谓词：只允许对变量施加量词，不允许对谓词和函数施加量词。,2.3.2 谓词公式,1、谓词公式的定义,利用连词和量词可以将原子（谓词）公式组成复合谓词公式，称之为分子谓词公式、谓词合适公式、谓词公式、合适公式。,（谓词）合适公式 的（递归）定义：原子（谓词）公式是合适公式。若 A 是合适公式，则 A 也是合适公式。若 A 和 B 是合适公式，则 AB 、AB 、AB 、AB 也是合适公式。,若 A 是合适公式， x 为 A 的自由变元（变量），则（x）A 和（x）A 都是合适公式。只有按上述规则求得的公式才是合适公式。

12、,例：任何整数或者为正或者为负。数学表达：对于所有的 x，如果 x 是整数，则 x 或者为正、或者为负。记作： I(x)：“ x 是整数”。 P(x)：“ x 是正数”。 N(x)：“ x 是负数”。谓词公式： （x）（I(x) (P(x) N(x)）,2、合适公式的性质,如果 P 和 Q 是合适公式，则由这两个合适公式构成的合适公式的真值表与前面介绍的真值表相同。,如果两个合适公式的真值表相同，则我们称这两个合适公式是等价的，可以用“”来表示。,对于命题合适公式和谓词合适公式有下列等价关系：,否定之否定： （P） 等价于 P PQ 等价于 PQ狄.摩根定律 （PQ）等价于 PQ （PQ）等价

13、于 PQ,分配律 P(QR) 等价于 (PQ)(PR) P(QR) 等价于 (PQ)(PR)交换律 PQ 等价于 QP PQ 等价于 QP,结合律 (PQ)R 等价于 P(QR) (PQ)R 等价于 P(QR)逆否律 PQ 等价于 QP,说明：上述等价关系对命题合适公式、谓词合适公式都成立。,对于谓词合适公式有下列等价关系：, (x)P(x) 等价于 (x)P(x) (x)P(x) 等价于 (x)P(x) (x)P(x)Q(x) 等价于 (x)P(x)(x)Q(x) (x)P(x)Q(x) 等价于 (x)P(x) (x)Q(x), (x)P(x) 等价于 (y)P(y) (x)P(x) 等价于

14、 (y)P(y),注释：这两个关系说明，在一个量化的表达式中的约束变量是一类虚元，它们可以用任何不在表达式中出现的其它变量来代替。,2.3.3 置换与合一,1、置换,置换的定义：形如 t1 / v1 , , tn / vn 的集合，称为一个置换，其中 vi 是不同的变量，ti 是与 vi 不同的项。,例或例子的定义：设 t1/v1 , , tn/vn 为一个置换，E是一个原子谓词公式。则E表示将E中的 vi 同时用 ti（i=1,n）代入后所得到的结果，E称为E的一个例子。,例：表达式（原子谓词公式）Px,f(y),B的四个置换及其对应的四个例子 （B是常量）,s1=z/x, w/ys2=A/

15、y s3=q(z)/x, A/ys4=c/x, A/y,Px, f(y), Bs1=Pz, f(w), BPx, f(y), Bs2=Px, f(A), B Px, f(y), Bs3=Pq(z), f(A), BPx, f(y), Bs4=Pc, f(A), B,Px,f(y),B,置换的合成：设t1/x1, ,tn/xn和s1/y1, ,sm/ym是两个置换，则和的合成是如下置换： t1/x1 , ti/xi , tn/xn, s1/y1, , sm/ym 其中，若yj 是 x1,xn 之一者消去，对于任何 tj=xj 者消去，并记成。,如何求 ti :s1/y1 , , sm/ym如果

16、ti 出现 y1, ., ym中的变量 yi ， 则用其对应的项 si 来代替。,例： = t1/x1 , t2/x2f(y)/x , z/y = s1/y1 , s2/y2 , s3/y3 = a/x , b/y , y/z =t1/x1 , t2/x2 , s1/y1 , s2/y2 , s3/y3 =f(b)/x , y/y , a/x , b/y , y/z =f(b)/x , y/z,注意：置换的合成满足结合律，不满足交换律。 (s1s2)s3 = s1(s2s3) (满足结合律） s1s2 s2s1 （不满足交换律）,例： s1=z/x , w/y s2=A/y s1s2=z/x

17、, w/y , A/y=z/x , w/y s2s1=A/y, z/x , w/y=A/y , z/x,2、合一,当某一个置换 s 作用于表达式集合 Ei 的每一个元素，此时我们用 Eis 来表示置换例子的集合。如果存在一个置换 s ，使得 E1s = E2s = = Eis = 则我们称表达式集合 Ei 是可合一的，并称 s 为Ei 的合一者。原因是它的作用是使集合 Ei 成为单一形式。 其中，Ei 是原子谓词公式。,例：表达式集合Px , f(y) , B , Px , f(B) , B的合一者为是 s = A/x , B/y Px , f(y) , Bs = PA , f(B) , B

18、Px , f(B) , Bs = PA , f(B) , B,如果 s 是 Ei 的任意一个合一者，又存在某一个 s，使得 s = g s 或者 Ei s = Ei g s则 称 g 是 Ei 的最通用（最一般）的合一者，记作mgu。,例：s = A/x , B/y 是表达式集合 Px , f(y) , B , Px , f(B) , B的一个合一者，该集合的最一般的合一者是： g = B/y,3、合一算法,分歧集（或不一致集合）的定义。设有一非空有限公式集合 F = F1 , , Fn，从 F中各个公式的第一个符号同时向右比较，直到发现第一个彼此不尽相同的符号为止，从 F 中的各个公式中取出

19、那些以第一个不一致符号开始的最大的子表达式为元素，组成一个集合 D ，称为 F 的分歧集（不一致集合）。 其中，F i ( i=1 , , n)是原子谓词公式,例：公式集：F=P(x , g( f(y , z) , x) , y), P(x , g( a , b) , b) , P(x , g( g(h(x) , a) , y) , h(x)分歧集为： D=f(y , z) , a , g(h(x) , a),设 F 为非空有限表达式集合，则可以按下列步骤求出 mgu： 置 k=0 ，Fk = F ,k=(空置换，即不含元素的置换)。 若 Fk 只有一个表达式，则算法终止，其中k就是要求的mg

20、u。 找出 Fk 的分歧集 Dk 。,合一算法：,若 Dk 中存在元素 ak 和 tk ，其中 ak 是变元，tk是项，且 ak 不在 tk 中出现，则置： k+1 =k tk / ak Fk+1 = Fk tk / ak k = k+1然后转向。否则，继续。算法终止，F的 mgu 不存在。,合一算法的流程图,k=0, Fk=F,k=,|Fk|1？,求得mgu、结束,求出不一致集合,有置换？,求出新置换；更新公式集合与旧置换，k+,无解、结束,说明：1、合一算法是消解原理的基础。2、合一算法中的公式集就是从谓词合适公式化成的子句集。,例：求F= P(a , x , f(g(y), P(z ,

21、h(z , u) , f(u)的最一般的合一者。解：我们根据合一算法一步一步地求出mgu。,第一步：k = 0, F0= F, 0= F0的分歧集合D0=a , z 置换：a/z 1 =0a/z = a/z F1 = F0 a/z = P(a , x , f(g(y), P(a , h(a , u) , f(u) k=1 F1 不是单一表达式,F=P(a,x,f(g(y)， P(z,h(z,u),f(u),第二步：D1x , h(a,u) 置换：h(a , u)/x 21h(a , u)/x=a/z , h(a , u)/x F2=F1h(a , u)/x =P(a , h(a , u) ,

22、f(g(y), P(a , h(a , u) , f(u) k=2,F=P(a,x,f(g(y)， P(a,h(a,u),f(u),第三步：D2g(y) , u 置换：g(y)/u 32g(y)/u=a/z , h(a,g(y)/x , g(y)/u F3=F2g(y)/u=P(a , h(a , g(y) , f(g(y) k=3,F=P(a, h(a,u), f(g(y)， P(a, h(a,u), f(u),F3是单一表达式，所以 3a/z , h(a , g(y)/x , g(y)/u是 F 的最一般合一者,例：F=Q(f(a) , g(x) , Q(y , y)是否可合一？,第一步：

23、k=0, F0=F, 0= F0的分歧集合D0=f(a) , y 置换：f(a)/y 10f(a)/y= f(a)/y F1=F0 f(a)/y =Q(f(a) , g(x) , Q(f(a) , f(a) k=1 F1不是单一表达式,第二步：D1g(x), f(a) 不存在着变量，所以不可合一。,F1=Q(f(a),g(x), Q(f(a),f(a),练习：求公式集 W= Q(x , y, z) , Q(a , f(b) , a) 的最一般的合一者? 其中，x, y, z为变量，a为常量，f 为函数,第一步：k=0, W0=W, 0= W0的分歧集合D0=a , x 置换： a / x 10

24、a/x= a / x W1=W0 a / x =Q(a , y, z) , Q(a , f(b) , a) k=1 W1不是单一表达式, Q(x , y, z) , Q(a , f(b) , a) ,第二步：W1的分歧集合D1=f(b) ，y 置换： f(b) / y 21 f(b) / y = a / x , f(b) / y W2=W1 f(b) / y =Q(a , f(b), z) , Q(a , f(b) , a) k=2 W2不是单一表达式, Q(a , y, z) , Q(a , f(b) , a) ,第三步：W2的分歧集合D0=a , z 置换： a / z 32 a / z

25、= a / x , f(b) / y , a / z W3=W2 a / z =Q(a , f(b), a) k=3 W3是单一表达式，mgu= 3 = a / x , f(b) / y , a / z, Q(a , f(b), z) , Q(a , f(b) , a) ,谓词的一致性，P()与Q()， 不可以常量的一致性，P(a, )与P(b,.)， 不可以；变量，P(a, .)与P(x, )， 可以变量与函数，P(a, x, .)与P(x, f(x), )，不可以；但P(a, x, )与P(x, f(y), )，可以是不能同时消去两个互补对，PQ与PQ的空，不可以先进行内部简化（置换、合并

26、）,置换和合一的注意事项：,例如假设用下列定义P（x, a） 表示某人x的职业为a；A（y, b） 表示Y的年龄为b；GE（x,y） 表示 x yS（z, c） 表示z的性别为c；W（w, d） 表示w的工龄为d；E（u，e） 表示u的文化程度为e；R（t） 表示t已退休。,（1）事实知识的描述,应用举例：,以下事实可以用谓词逻辑表示为：,王的职业是教师： P（Wang, Teacher）张是工程师： P（Zhang, Engineer） 王是男性： S（Wang，Male）赵是男性： S（Zhao，Male）张是女性： S（Zhang，Female）赵70岁： A（Zhao，70）张工龄38

27、年： W（Zhang，38）王工龄30年： W（Wang，30）,（2） 规则知识的描述,所有教师或工程师都具有高等教育学历，或者说：如果是教师或工程师那么都具有高等教育学历，可以描述为：,所有具有高等教育学历的人，年龄一般大于或等于25岁。,任何一位工龄为u的教师或工程师Z ，其年龄一般大于或等于u+25。,其中ADD表示两数相加的谓词 任何男性职工年龄超过60岁退休。,任何女性职工年龄超过55岁退休,这些知识可以用于推理。例如：问赵的年龄多大：可以得到 70原因是知识库中有事实性知识: A（Zhao，70）。如果要问张的年龄，知识库中没有直接的答案需要经过推理过程.,从事实知识中可以匹配到

28、：P（Zhang，Engineer）根据规则 （1)，,可以的到：张受过高等教育E(zhang,hight)用zhang 置换公式中的x。,即张受过高等教育。,继续在规则库中匹配，可以匹配规则 (2)匹配方法是,用已知事实与规则的左边比较(前项比较) ,与公式(2)的 前项比较,只要将E(y,hight)的y用zhang 置换，则与E（zhang,hingt) 匹配，从该公式,可以得到：,即张的年龄大于或等于25岁。,这是否已得到结论？,如果没有新的事实。我们可以认为已得到结论了。现在我们还需要检验是否还有新的事实。通过检查事实知识，发现还有一条事实：张的工龄是38年： W（Zhang，38）

29、显然，以上结论虽然没有错，但太不精确，不合理，这样我们需要继续利用事实和规则进行推理。可以利用已知事实： P(zhang ,engineer) 和 W(zhang,38)它与规则（3）的左边匹配,规则3的前项是两个项的析取（或）表达式，只要任何一个项匹配就认为匹配成功。,任何一位工程师z,如z的工龄为u，则它的年龄w 大于或等于 u+25,即张的年龄 大于或等于63岁。这比前面的推理显然更合理。,还能继续往下推理吗？看还有没有新的事实！检索事实知识库，没有发现新的知识。,本章小结三种基本的知识表达方法：状态空间法（状态、操作符、图表示）问题归约法（原始问题、本原问题、操作符、与或图表示）谓词逻辑法（谓词公式、置换、合一算法）,