人工智能课件cumt_第二章 知识表示 2.ppt

2018/1/24,1,2.2 谓词逻辑表示法 1）谓词逻辑基本概念,1、谓词公式,Married(father(L1),x),函数符号、变量符号——小写字母的形式来表示,变量符号,函数符号,2018/1/24,2,2.2 谓词逻辑表示法 1）谓词逻辑基本概念,2、连词和量词通过引入连词和量词，可以把原子公式组合为复合谓词公式复合谓词公式也称为逻辑语句，谓词演算也称为谓词逻辑1）连词通过连词产生复合谓词公式（逻辑语句）的例子：,Inroom(Robot,R2),Isa(Liming,Student),Lives(Liming,House1),Isa(Wang,Teacher),Isa(Wang,Officer),At(Liming,School),At(Wang,School),At(Liming,School),At(Wang,School),2018/1/24,3,2.2 谓词逻辑表示法 1）谓词逻辑基本概念,2、连词和量词命题——不包含变量的谓词公式和逻辑语句；命题逻辑——基于命题的谓词逻辑称为命题逻辑，命题逻辑是谓词逻辑的子集命题逻辑缺乏有效的表达一般性概念的能力无法把每个知识单元抽象、细分；如，“条条大路通罗马”。

Lead(Road1,Roma)Lead(Road2,Roma)……谓词逻辑中引入变量和对变量进行约束的量词2）量词全称量词 存在量词,2018/1/24,4,2.2 谓词逻辑表示法 1）谓词逻辑基本概念,2、连词和量词——（2）量词全称量词符号(x)P(x)：表示对于某个论域中的所有（任意一个）个体x, 都有P(x)真值为T存在量词符号(x)P(x)：来表示某个论域中至少存在一个个体x，使P(x) 真值为T条条大路通罗马,Mary给每个人一本书,Mary给每人某个同样的东西,量词可以嵌套使用,可以有不受量词约束的变量,2018/1/24,5,2.2 谓词逻辑表示法 1）谓词逻辑基本概念,Mary给每个人一本书,Mary给每人某个同样的东西,量词可以嵌套使用,可以有不受量词约束的变量,6,2.2 谓词逻辑表示法 1）谓词逻辑基本概念,2、连词和量词——（2）量词全称量词符号(x)P(x)：表示对于某个论域中的所有（任意一个）个体x, 都有P(x)真值为T存在量词符号(x)P(x)：来表示某个论域中至少存在一个个体x，使P(x) 真值为T条条大路通罗马,所有机器人都是灰色的,2018/1/24,7,2.2 谓词逻辑表示法 1）谓词逻辑基本概念,2、连词和量词——（2）量词出现在量词中的变量，称为量词的约束变量（或变元）①取值仅在量词的辖域内有效；②不同辖域内的同名约束变量相互独立；不受量词约束的变量称为自由变量自由变量的相对性：,2018/1/24,8,2.2 谓词逻辑表示法 1）谓词逻辑基本概念,3、一阶谓词逻辑定义：若限定不允许对谓词和函数名进行量化处理，且参数项不能是谓词公式，则这样的谓词逻辑是一阶的。

谓词、函数名的出现位置不允许使用变量；参数项不能是谓词公式；(P)P(A)-谓词进行了量化；(y)Married(y(L1),Mary )-函数名进行了量化；P(x,Q(y))-参数项是谓词公式；,2018/1/24,9,2.2 谓词逻辑表示法 2）合适(式)公式,1、合式公式的定义合式公式适合于一阶谓词逻辑遵从以下递归方式定义的逻辑语句称为合式公式①单一谓词公式是合式公式；②若A是合式公式，则A也是合式公式；③若A和B都是合式公式，则A∧B、 A∨B、 AB和AB也都是合式公式；④若A是合式公式，x是约束变量，则(x)A和(x)A也都是合式公式；⑤只有按上述规则①-④求得的公式，才是合式公式连词优先级别是，∧、∨，、，但可通过括号改变优先级2018/1/24,10,2.2 谓词逻辑表示法 2）合式公式,1、合式公式的定义例2、“所有人(Person)都喜欢(Like)一种游戏(Game)”①谓词公式Person(x)Like(x,y)Game(y)②量词(x)Person(x)表示所有人；(y)Game(y)表示一种游戏；③合式公式(x)(y)[Person(x)∧Game(y)∧Like(x,y)],2018/1/24,11,4）谓词逻辑适用范围：,谓词逻辑适合于表示事物的状态、属性、概念等事实性知识，也可以用来表示事物间具有确定因果关系的规则性知识。

1）对事实性知识：可以使用谓词公式中的析取符号与合取符号连接起来的谓词公式来表示，如对下面句子： 张三是一名计算机系的学生，他喜欢编程序可以用谓词公式表示为 Computer(张三)∧Like(张三,programming)其中:Computer(x)表示x是计算机系的学生, Like(x,y)表示x喜欢y,都是谓词2018/1/24,12,2.3.1 产生式系统,1. 产生式规则通常用于表示事物间的因果关系；【基本形式】IF P then Q 或 P  Q，其中P表示规则的条件（或称前提）；谓词、多元组、常量、变量、关系运算……Q表示规则激活时应该执行的动作（或得到的结论）；激活——规则条件P满足；【规则分类】①前提-结论型②条件-动作型,谓词逻辑的蕴含关系只是产生式规则的特殊形式,2018/1/24,13,2.3.1 产生式系统,3. 应用实例——八数码游戏综合数据库规则库冲突解决策略,2018/1/24,14,2.3.1 产生式系统,3. 应用实例——八数码游戏综合数据库——描述问题状态3×3的一个矩阵S表示棋盘布局；矩阵元素Sij∈{0,1,2,3,4,5,6,7,8},其中1≤i,j≤3 数字0表示空格 数字1-8表示相应的棋牌；,,2018/1/24,15,2.3.1 产生式系统,3. 应用实例——八数码游戏规则库：R1: j0>1  Si0j0:= Si0(j0-1) ∧ Si0(j0-1) := 0空格左移 R2: i0>1  Si0j0:= S(i0-1)j0 ∧ S(i0-1)j0 := 0空格上移R3: j0<3  Si0j0:= Si0(j0+1) ∧ Si0(j0+1) := 0空格右移R4: i0<3  Si0j0:= S(i0+1)j0 ∧ S(i0+1)j0 := 0空格下移,,i0表示空格所在行 j0表示空格所在列,i0=1，j0=2,,,,,,Si0(j0-1),Si0j0,2018/1/24,16,2.3.1 产生式系统,3. 应用实例——八数码游戏冲突解决策略：使用激活规则移动空格后，⒈错位的棋牌个数最少；⒉错位棋牌在不受阻拦的情况下，移动到目标状态相应位置所需走步（移动次数）的总和最小。

i0表示空格所在行 j0表示空格所在列,2018/1/24,17,R1,i0=1，j0=2,R1左移; j0>1  Si0j0:= Si0(j0-1) ∧ Si0(j0-1) := 0,R3,R3右移; j0<3  Si0j0:= Si0(j0+1) ∧ Si0(j0+1) := 0,R4,R4下移; i0<3  Si0j0:= S(i0+1)j0 ∧ S(i0+1)j0 := 0,冲突,⒈错位的棋牌个数最少,2018/1/24,18,R4,R4下移; i0<3  Si0j0:= S(i0+1)j0 ∧ S(i0+1)j0 := 0,i0=2，j0=2,2018/1/24,19,R1左移; j0>1  Si0j0:= Si0(j0-1) ∧ Si0(j0-1) := 0,R3右移; j0<3  Si0j0:= Si0(j0+1) ∧ Si0(j0+1) := 0,R4,R4下移; i0<3  Si0j0:= S(i0+1)j0 ∧ S(i0+1)j0 := 0,i0=2，j0=2,R1,R3,R4,冲突,⒈错位的棋牌个数最少,⒉（移动次数）的总和最小,5,3,2018/1/24,20,R4,R4下移; i0<3  Si0j0:= S(i0+1)j0 ∧ S(i0+1)j0 := 0,R4,i0=3，j0=2,2018/1/24,21,R1左移; j0>1  Si0j0:= Si0(j0-1) ∧ Si0(j0-1) := 0,R3右移; j0<3  Si0j0:= Si0(j0+1) ∧ Si0(j0+1) := 0,R4,i0=3，j0=2,R4,R1,R3,冲突,2018/1/24,22,R2上移; i0>1  Si0j0:= S(i0-1)j0 ∧ S(i0-1)j0 := 0,R4,i0=3，j0=1,R4,R1,R2,2018/1/24,23,R4,i0=2，j0=1,R4,R1,R2,R2,R2上移; i0>1  Si0j0:= S(i0-1)j0 ∧ S(i0-1)j0 := 0,R3右移; j0<3  Si0j0:= Si0(j0+1) ∧ Si0(j0+1) := 0,R3,冲突,2018/1/24,24,R4,i0=2，j0=2,R4,R1,R2,R3右移; j0<3  Si0j0:= Si0(j0+1) ∧ Si0(j0+1) := 0,R3,2018/1/24,25,2.3.2 控制策略,1、二阶梵塔问题：①综合数据库L{小盘位置,大盘位置}②规则库（ 2类，6条）为大、小盘的搬动各设计一类规则：⑴小盘移动规则：由于小盘必定在大盘上，所以任何场合均可搬动小盘R1：If L(1) ≠ 1 then L(1)=1; R2：If L(1) ≠ 2 then L(1)=2; R3：If L(1) ≠ 3 then L(1)=3; 简化为：R1(n)：If L(1) ≠ n then L(1)=n; (n=1,2,3)表示把小盘移到n号柱子上；,2018/1/24,26,2.3.2 控制策略,1、二阶梵塔问题：①综合数据库L{小盘位置,大盘位置}②规则集（ 2类，6条）为大、小盘的搬动各设计一类规则：⑴小盘移动规则：由于小盘必定在大盘上，所以任何场合均可搬动小盘R1(n)：If L(1) ≠ n then L(1)=n; n=1,2,3【冲突解法】⑴目的柱的按优先次序1、2、3排列,R1(2) ：If L(1) ≠ 2 then L(1)=2,R1(3) ：If L(1) ≠ 3 then L(1)=3,,,综合数据库L{1,1}：L(1)=1,,综合数据库L{2,1}：L(1)=2,2018/1/24,27,2.3.2 控制策略,1、二阶梵塔问题：①综合数据库L(小盘位置,大盘位置)②规则集（ 2类，6条）为大、小盘的搬动各设计一类规则⑵大盘移动规则：仅小盘不在大盘上时可搬大盘，这时小盘必在另一柱子上，故大盘只能搬到剩下的无盘柱子上。

R4：If L(2) ≠L(1), L(1) ≠ 1, L(2) ≠ 1 then L(2)= 1R5：If L(2) ≠L(1), L(1) ≠ 2, L(2) ≠ 2 then L(2)= 2R6：If L(2) ≠L(1), L(1) ≠ 3, L(2) ≠ 3 then L(2)= 3简化为：R2(n)：表示把大盘移到n号柱子上；If L(2) ≠L(1), L(1) ≠ n, L(2) ≠ n then L(2)= n,2018/1/24,28,2.3.2 控制策略,1、二阶梵塔问题：①综合数据库L(小盘位置,大盘位置)②规则集（ 2类，6条）为大、小盘的搬动各设计一类规则⑵大盘移动规则：仅小盘不在大盘上时可搬大盘，这时小盘必在另一柱子上，故大盘只能搬到剩下的无盘柱子上R2(n)：表示把大盘移到n号柱子上；If L(2) ≠L(1), L(1) ≠ n, L(2) ≠ n then L(2)= n【冲突解法】⑵数码小的柱子上的盘优先搬;,。