AI-5(本)人工智能课件.ppt

人工智能基础人工智能基础2.3 2.3 基于归结的演绎推理基于归结的演绎推理1 1谓词演算谓词演算 1)一阶谓词演算的基本概念一阶谓词演算的基本概念n符号和符号结构符号和符号结构n符号符号符号结构的组成成分符号结构的组成成分n物理符号系统，纽厄尔和西蒙物理符号系统，纽厄尔和西蒙n可将符号表示为字符串，作为事物的标识可将符号表示为字符串，作为事物的标识n符号结构符号结构描述事物间的相关方式描述事物间的相关方式 Inroom(Robot,R1)n谓词谓词公式公式n形如形如Inroom(RobotInroom(Robot，R1)R1)的符号结构称为谓词公式。的符号结构称为谓词公式。n一般形式：一般形式：P(xP(x1 1,x,x2 2,x xn n)nP P谓词谓词符号符号(简简称称谓词谓词)，nx xi i(i(i=1,2,=1,2,n)n)参数参数项项(简简称称项项)，项项可以是常量、可以是常量、变变量或函数。量或函数。nP(xP(x1 1,x,x2 2,x xn n)表示了一个表示了一个n n元元谓词谓词公式公式nInroom(Robot，R1)Married(father(L1),x)1 1谓词演算谓词演算 1)一阶谓词演算的基本概念一阶谓词演算的基本概念n为避免混淆、增加表示的清晰性，规定：为避免混淆、增加表示的清晰性，规定：n谓词和常量谓词和常量首字母大写的形式表示，首字母大写的形式表示，n函数和变量函数和变量小写字母的形式表示。小写字母的形式表示。n变量值均取定时，每个谓词公式均有一个确定的真值：变量值均取定时，每个谓词公式均有一个确定的真值：T T或或F F。n谓词公式是谓词演算的基本单元，也称谓词公式是谓词演算的基本单元，也称原子公式原子公式。n连词和量词连词和量词n通过引入连词和量词，可以把原子公式组合为复合谓词公式。通过引入连词和量词，可以把原子公式组合为复合谓词公式。n复合谓词公式复合谓词公式称为逻辑语句，谓词演算也称为谓词逻辑。称为逻辑语句，谓词演算也称为谓词逻辑。n连词连词 (非非)、(与与)、(或或)、(蕴涵，蕴涵，)、(等价，等价，)n连词连词例：例：Inroom(RobotInroom(Robot,R2),R2)Isa(LimingIsa(Liming,Student)Lives(LimingStudent)Lives(Liming,House-1)Color(House-1,House-1)Color(House-1,White)White)Isa(WangIsa(Wang,Teacher),Teacher)Isa(WangIsa(Wang,Officer),Officer)At(LimingAt(Liming,School),School)At(WangAt(Wang,School),School)At(LimingAt(Liming,School),School)At(WangAt(Wang,School),School)1)一阶谓词演算的基本概念一阶谓词演算的基本概念n连词相关的术语：连词相关的术语：n否定否定取反，取反，谓词公式前面加连词谓词公式前面加连词；n合取合取用用连词连接谓词公式，产生的逻辑语句称为合取式，其每个成连接谓词公式，产生的逻辑语句称为合取式，其每个成份称为合取项；份称为合取项；n析取析取 ，析取式，析取，析取式，析取项项；n蕴蕴涵式涵式 ，连词左部称左部称为为前前项项，右部称，右部称为为后后项项；n等价式等价式用连词用连词连接二个谓词公式而产生，视为正、逆向二个蕴涵式连接二个谓词公式而产生，视为正、逆向二个蕴涵式的合取。的合取。1)一阶谓词演算的基本概念一阶谓词演算的基本概念n命题命题不包含变量的谓词公式和逻辑语句不包含变量的谓词公式和逻辑语句n命题演算命题演算基于命题的谓词演算，谓词演算的子集基于命题的谓词演算，谓词演算的子集n缺乏有效的表达能力去表示一般性概念，如缺乏有效的表达能力去表示一般性概念，如“条条大路通罗马条条大路通罗马”。n为扩大命题演算能力，就需要引入变量和有关的表示方式。为扩大命题演算能力，就需要引入变量和有关的表示方式。n量词量词表示对变量的处理：表示对变量的处理：n全全称称量量词词以以符符号号(x)P(xx)P(x)来来表表示示对对于于某某个个论论域域中中的的所所有有(任任意一个意一个)个体个体x,x,都有都有P(xP(x)真值为真值为T T。n存存在在量量词词以以符符号号(x x)P(x)P(x)来来表表示示某某个个论论域域中中至至少少存存在在一一个个个个体体x x，使使P(xP(x)真值为真值为T T。P(xP(x)是任意逻辑语句是任意逻辑语句,也称作量词的管辖范围也称作量词的管辖范围(简称辖域简称辖域,使用使用界定界定)。n量词量词例：例：1)一阶谓词演算的基本概念一阶谓词演算的基本概念 (x x)Robot(x)Robot(x)Color(xColor(x,Gray),Gray),所有机器人都是灰色的；所有机器人都是灰色的；(x x)Road(x)Road(x)Lead(xLead(x,Roma),Roma),条条大路通罗马；条条大路通罗马；(x x)Isa(x)Isa(x,Robot),Robot)Inroom(xInroom(x,R1),R1),至少有一个机器人在房间至少有一个机器人在房间R1R1中；中；(x x)()(y y)Person(x)Person(x)Book(yBook(y)Give(Mary,x,yGive(Mary,x,y)，MaryMary给每个人一本书。给每个人一本书。(x x)Person(x)Person(x)Give(MaryGive(Mary,x,y),Mary,x,y),Mary给每人某个同样的东西。给每人某个同样的东西。n量量词词的的约约束束变变量量(或或称称变变元元)，其其取取值值仅仅在在量量词词的的辖辖域域内内有有效效；不不同同辖域内的同名约束变量相互独立。辖域内的同名约束变量相互独立。n自由变量，相对性：自由变量，相对性：(y y)P(y)P(y)(x x)Q(x,y)Q(x,y)n一阶谓词演算一阶谓词演算n若限定不允许对谓词、连词、量词和函数名进行量化处理，且参数项若限定不允许对谓词、连词、量词和函数名进行量化处理，且参数项不能是谓词公式，则这样的谓词演算是一阶的。不能是谓词公式，则这样的谓词演算是一阶的。n一阶谓词演算不允许在谓词、连词、量词和函数名的出现位置上使用一阶谓词演算不允许在谓词、连词、量词和函数名的出现位置上使用变量。变量。(P P)P P(A)(A)、Married(Married(y y(L1),Mary)(L1),Mary)、P(x,P(x,Q(yQ(y)n内容内容2.3.1谓词演算谓词演算2.合适公式合适公式定义定义 n递归方式的定义：递归方式的定义：1)单一谓词公式单一谓词公式(即原子公式即原子公式)是合适公式；是合适公式；2)若若A是合适公式，则是合适公式，则 A也都是合适公式；也都是合适公式；3)若若A和和B都是合适公式，则都是合适公式，则AB、AB、AB和和AB也都是合适公式；也都是合适公式；4)若若A是是合合适适公公式式，x是是约约束束变变量量，则则(x)A和和(x)A也也都都是是合合适适公公式式;5)只有按上述规则只有按上述规则(1)至至(4)求得的公式，才是合适公式。求得的公式，才是合适公式。n连词优先级别连词优先级别：，、，、，可通过括号改变优先级。，可通过括号改变优先级。n形式化表示符号推理所需的知识形式化表示符号推理所需的知识 所有人都喜欢一种游戏所有人都喜欢一种游戏(x)(y)Person(x)Game(y)Like(x,y)2.合适公式合适公式解释解释 n命题命题不包含变量、量词的合适公式不包含变量、量词的合适公式n命题的一个解释命题的一个解释给命题中包含的各个原子公式指派真值给命题中包含的各个原子公式指派真值(T或或F)求出命题的真值求出命题的真值(T或或F)依据连接原子公式的连词的作用依据连接原子公式的连词的作用n谓词逻辑谓词逻辑涉及变量、函数，不能直接给原子公式指派真值涉及变量、函数，不能直接给原子公式指派真值n定义一个拟观察个体的可能论域定义一个拟观察个体的可能论域n确定原子公式中变量项和函数项在论域中的取值确定原子公式中变量项和函数项在论域中的取值n给原子公式指派真值给原子公式指派真值 2.合适公式合适公式解释解释 例：合适公式例：合适公式(x x)()(y y)P(x)P(x)Q(f(x),yQ(f(x),y)的一个解释的一个解释n设定一个论域：设定一个论域：D=1D=1，22n对于对于x x的每个取值的每个取值,指派指派f(1)=2,f(2)=2,P(1)=T,P(2)=Tf(1)=2,f(2)=2,P(1)=T,P(2)=T；对于对于f(xf(x)和和y y的每个取值组合的每个取值组合(只有只有2 2个：个：2,12,1；2,2)2,2)指派指派 Q(2,1)=T,Q(2,2)=FQ(2,1)=T,Q(2,2)=F。n这些指派就确定了该合适公式的一个解释这些指派就确定了该合适公式的一个解释 在此解释下，合适公式有真值在此解释下，合适公式有真值T T 谓词逻辑谓词逻辑定义一个拟观察个体的可能论域定义一个拟观察个体的可能论域确定原子公式中变量项和函数项在论域中的取值确定原子公式中变量项和函数项在论域中的取值给原子公式指派真值给原子公式指派真值2.合适公式合适公式永真性和可满足性永真性和可满足性n永真性永真性若某合适公式若某合适公式P P对于某论域对于某论域D D上的所有可能的解释都有真值上的所有可能的解释都有真值T T，则称则称P P在在D D上是永真的上是永真的；若；若P P在每个可能的非空论域上均永真，则称在每个可能的非空论域上均永真，则称P P是永真的是永真的。n可可满满足性足性对于合适公式对于合适公式P P，若在论域若在论域D D上至少可以建立一个解释，使上至少可以建立一个解释，使P P有真值有真值T T，则称则称P P在在D D上是可上是可满满足的足的；若至少有一个；若至少有一个论论域使域使P P可可满满足，足，则则称称P P是可是可满满足的足的。n永假性永假性若某合适公式若某合适公式P P对于论域对于论域D D上的所有可能的解释都有真值上的所有可能的解释都有真值F F，则称则称P P在在D D上是永上是永假的假的(即不可即不可满满足的足的)；若；若P P在每个可能的非空在每个可能的非空论论域上均永假，域上均永假，则则称称P P是永是永假的假的。n论域个数较少，每个论域较小，易判定；论域个数较少，每个论域较小，易判定；n论域个数较多，每个论域较大，且解释的个数有限时，可以判定；论域个数较多，每个论域较大，且解释的个数有限时，可以判定；n解释的个数无限时，不能确保解释的个数无限时，不能确保(在有限的时间内在有限的时间内)可以判定可以判定。2.合适公式合适公式性质性质化简合适公式到某些约定的标准形式化简合适公式到某些约定的标准形式 3.合适公式的标准化合适公式的标准化标准化需求标准化需求 基于谓词演算的推理基于谓词演算的推理(归结反演、规则演绎归结反演、规则演绎)n量量词词前束范式前束范式:(Q(Q1 1x x1 1)(Q)(Q2 2x x2 2)()(Q Qk kx xk k )M)M M M 母式母式，不包括任何量，不包括任何量词词，量词量词前束前束 Q Qi i 量词符号量词符号 或或 x xi i 量词的约束变量。量词的约束变量。n归结反演归结反演要求母式要求母式M M标准化为标准化为合取范式合取范式：M=WM=W1 1WW2 2W Wn n W Wi i=L=Li1i1LLi2i2LLimim (i=1,2,n)(i=1,2,n)L Lijij=P Pijij|P Pijij (j=1,2,m)(j=1,2,m)L Lijij文字文字n析取范式析取范式(与合取范式与合取范式对对偶偶)：M=WM=W1 1WW2 2W Wn n W Wi i=L=Li1i1LLi2i2LLimim (i=1,2,n)(i=1,2,n)L Lijij=P Pijij|P Pijij (j=1,2,m)(j=1,2,m)3.合适公式的标准化合适公式的标准化n合取范式的标准化过程合取范式的标准化过程n应用合适公式性质将公式逐步转化应用合适公式性质将公式逐步转化n转化过程步骤转化过程步骤,遵从一个合理顺序可降低化简的困难、减少差错遵从一个合理顺序可降低化简的困难、减少差错n一个较合理的化简过程，分一个较合理的化简过程，分8 8个步骤个步骤：例：例：合取范式的标准化过程合取范式的标准化过程:(1)消去多余的量词消去多余的量词 (x)P(y),(x)可以消去可以消去(2)消去蕴涵符号消去蕴涵符号 Q(x,y)P(y)Q(x,y)P(y)蕴涵式转化蕴涵式转化(3)内移否定符号内移否定符号使其只出现在原子谓词公式前面，构成否定文字。使其只出现在原子谓词公式前面，构成否定文字。(y)P(y)P(f(x,y)(y)P(y)P(f(x,y)双重否定、狄双重否定、狄.摩根定律、量词摩根定律、量词否定否定(4)变量换名变量换名使所有量词都具有不同的约束变量名。使所有量词都具有不同的约束变量名。约束变量的虚元性约束变量的虚元性(y)(w)Q(x,y)P(y,w)(z)(w)Q(x,z)P(z,w)(5)消去存在量词消去存在量词 分二种情况：存在量词出现在全称量词的辖域内和不在辖域内分二种情况：存在量词出现在全称量词的辖域内和不在辖域内 (z)(w)Q(x,z)P(z,w)(w)在在(z)辖域内辖域内 (x)P(x)(x)不出现在全称量词辖域内不出现在全称量词辖域内设设w=g(z)，用，用Sklem函数函数g(z)取代约束变量取代约束变量w，消去存在量词，消去存在量词(w)(z)Q(x,z)P(z,g(z)(x)(y)(z)(w)P(x,y,z,w)(x)(y)(z)P(x,y,z,g(x,y,z)Sklem常量常量：任设一常量：任设一常量A，取代约束变量，取代约束变量x，而取消存在量词，而取消存在量词(x)：P(A)(6)全称量词前束化全称量词前束化将量词移动到合适公式的最前面集中存放。将量词移动到合适公式的最前面集中存放。(7)消去全称量词消去全称量词假设所有变量均受全称量词的约束，删去全称量词，只留下母式。假设所有变量均受全称量词的约束，删去全称量词，只留下母式。(8)把母式转化为合取范式把母式转化为合取范式 分配律分配律 P(y)P(f(A,y)Q(A,z)P(z,g(z)P(y)Q(A,z)P(z,g(z)P(f(A,y)Q(A,z)P(z,g(z)3.合适公式的标准化合适公式的标准化合取范式的标准化过程合取范式的标准化过程例：例：(x)P(x)(y)P(y)P(f(x,y)(y)(w)Q(x,y)P(y,w)1.(x)P(x)(y)P(y)P(f(x,y)(y)(w)Q(x,y)P(y,w)2.(x)P(x)(y)P(y)P(f(x,y)(y)(w)Q(x,y)P(y,w)3.(x)P(x)(y)P(y)P(f(x,y)(z)(w)Q(x,z)P(z,w)4.P(A)(y)P(y)P(f(A,y)(z)Q(A,z)P(z,g(z)5.(y)(z)P(A)P(y)P(f(A,y)Q(A,z)P(z,g(z)6.P(A)P(y)P(f(A,y)Q(A,z)P(z,g(z)7.P(A)P(y)Q(A,z)P(z,g(z)P(f(A,y)Q(A,z)P(z,g(z)1.消去多余的量词消去多余的量词 2.消去蕴涵符号消去蕴涵符号 3.内移否定符号内移否定符号4.变量换名变量换名 5.消去存在量词消去存在量词Sklem函数函数、Sklem常量常量6.全称量词前束化全称量词前束化 7.消去全称量词消去全称量词 8.把母式转化为合取范式把母式转化为合取范式