人工智能第2章(知识表示方法3-谓词逻辑)7433453.pptx

人人 工工 智智 能能ArtificialIntelligence(AI)许建华许建华南京师范大学计算机科学与技术学院南京师范大学计算机科学与技术学院2011年秋季年秋季第第2章章知识表示方法知识表示方法2.1状态空间法状态空间法2.2问题归约法问题归约法2.3谓词逻辑法谓词逻辑法2.3谓词逻辑法谓词逻辑法数理逻辑数理逻辑（符号逻辑）是用数学方法研究形式逻（符号逻辑）是用数学方法研究形式逻辑的一个分支。辑的一个分支。它它通过符号系统来表达客观对象通过符号系统来表达客观对象以及相关的逻辑推理。常用的是以及相关的逻辑推理。常用的是命题逻辑命题逻辑和和谓谓词逻辑词逻辑谓谓词词逻逻辑辑是是数数理理逻逻辑辑的的基基本本形形式式，是是基基于于谓谓词词分析的一种形式化（数学）语言分析的一种形式化（数学）语言人工智能中的谓词逻辑法人工智能中的谓词逻辑法是指用一阶谓词是指用一阶谓词来描述问题求解和定理证明（来描述问题求解和定理证明（限于本课程限于本课程）2.3.0命题逻辑的复习命题逻辑的复习 1、命题逻辑的基本概念命题逻辑的基本概念命题命题 是能够判断是能够判断真真或或假假的的陈述句陈述句通常用通常用大写字母大写字母来表示，如来表示，如A,B,P,Q等等命题的真假值一般用命题的真假值一般用 T或或 F来表示来表示 例例：雪是白的。（陈述句，雪是白的。（陈述句，T）雪是蓝的。（陈述句，雪是蓝的。（陈述句，F）雪是黑的。（陈述句，雪是黑的。（陈述句，F）他他是学生。（陈述句，他泛指，无法判断真假）是学生。（陈述句，他泛指，无法判断真假）你今天上课没有？（疑问句）你今天上课没有？（疑问句）去北校区，请坐校车！（祈使句）去北校区，请坐校车！（祈使句）命题逻辑命题逻辑是研究是研究命题命题及及命题之间命题之间关系的符关系的符号逻辑系统。号逻辑系统。在命题逻辑中，表示单一意义的命题，称之为在命题逻辑中，表示单一意义的命题，称之为原原子命题子命题。原子命题通过原子命题通过“联结词联结词”构成构成 复合命题复合命题。五个联结词五个联结词：“”表示表示 “非非”复合命题复合命题P为真，当且仅当为真，当且仅当P为假。为假。“”“”表示表示“合取合取”复合命题复合命题“PQ”为真，当且仅当为真，当且仅当P和和Q都为真。都为真。“”表示表示“蕴含蕴含”复合命题复合命题“PQ”为假，当且仅当为假，当且仅当P为真且为真且Q为假。为假。“”“”表示表示“析取析取”复合命题复合命题“PQ”为真，当且仅当为真，当且仅当P、Q两者之两者之一为真。一为真。“”表示表示“等价等价”复合命题复合命题“PQ”为真，当且仅当为真，当且仅当P、Q同时为真、同时为真、或者同时为假。或者同时为假。联接词的联接词的优先顺序优先顺序：非非、合取合取、析取析取、蕴含蕴含、等价等价注注：可以用括号表示优先级：可以用括号表示优先级真值表真值表 PQPPQPQPQPQFFTFFTTFTTFTTFTFFFTFFTTFTTTT命题变元命题变元：用符号：用符号P、Q等表示的不具有固定、具等表示的不具有固定、具体含义的命题。它可以表示具有体含义的命题。它可以表示具有“真真”、“假假”含含义的各种命题。义的各种命题。命题变元可以利用联结词构成所谓的命题变元可以利用联结词构成所谓的合适公式合适公式。合适公式的定义合适公式的定义若若P为为原原子子命命题题，则则P为为合合适适公公式式，称称为为原原子子公公式。式。若若P是合适公式，则是合适公式，则P也是一个合适公式。也是一个合适公式。若若P和和Q是是合合适适公公式式，则则PQ、PQ、PQ、PQ都是合适公式。都是合适公式。经经过过有有限限次次使使用用规规则则1、2、3，得得到到的的由由原原子子公公式式、联联结结词词和和园园括括号号所所组组成成的的符符号号串串，也也是是合合适适公式。公式。对于合适公式，规定下列对于合适公式，规定下列运算优先级运算优先级：逻辑联结词的运算优先次序为：逻辑联结词的运算优先次序为：、同级联结词按出现顺序优先运算同级联结词按出现顺序优先运算在命题逻辑中，主要研究推理的有效性。在命题逻辑中，主要研究推理的有效性。即：能否根据一些合适公式（即：能否根据一些合适公式（前提前提）推导出新的）推导出新的合适公式（合适公式（结论结论）。）。一些合适公式一些合适公式（前提条件）（前提条件）合适公式合适公式（结论）（结论）？在在命命题题逻逻辑辑中中，最最基基本本的的单单元元是是命命题题，它它是是作为一个不可分割的整体。作为一个不可分割的整体。例如：例如：雪是黑的雪是黑的命命题题逻逻辑辑具具有有较较大大的的局局限限性性，不不合合适适于于表表达达比较复杂的问题。比较复杂的问题。例例：所有科学都是有用的所有科学都是有用的（假设（假设1）。数理逻辑是科学数理逻辑是科学（假设（假设2）。所以，数理逻辑是有用的所以，数理逻辑是有用的（结论）（结论）。很明显，我们无法用很明显，我们无法用两个假设两个假设推断出推断出结论结论。谓词逻辑谓词逻辑是命题逻辑的扩充和发展。它将一个原是命题逻辑的扩充和发展。它将一个原子命题分解成子命题分解成客体客体和和谓词谓词两个组成部分。两个组成部分。例如：例如：雪雪 是黑的是黑的 客体客体 谓词谓词本课程主要介绍一阶谓词逻辑。本课程主要介绍一阶谓词逻辑。2.3.1谓词演算谓词演算1 1、语法与语义、语法与语义谓词逻辑的基本组成部分谓词逻辑的基本组成部分谓词谓词变量变量函数函数常量常量园括号园括号、方括号、花括号和逗号、方括号、花括号和逗号例例“机机器器人人（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来表示。来表示。函数函数（或函词）（或函词）：以个体为变量，以个体为值的：以个体为变量，以个体为值的函数。一般用小写字母来表示，例如函数。一般用小写字母来表示，例如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)是原子公式是原子公式其它表达式都不是原子公式其它表达式都不是原子公式原子公式的例子原子公式的例子1、原子公式：、原子公式：P（原子命题）原子命题）2、项：、项：x,a,f(x,a)，谓词：谓词：P原子公式：原子公式：P(x,a,f(x,a)2、连词和量词、连词和量词联结词（连词）联结词（连词）就是命题逻辑中的五个，它们的就是命题逻辑中的五个，它们的含义也是一样的。含义也是一样的。两个量词两个量词：全全称称量量词词，记记作作“x x”,”,含含义义是是“对对每每一一个个x x”或或“对一切对一切x x”。存存在在量量词词，记记作作“x x”，含含义义是是“存存在在某某个个x x”、“有一个有一个x x”或者或者“某些某些x x”。AllAExistE例例1：“所所有有的的机机器器人人都都是是灰灰色色的的”，用用谓谓词词逻逻辑辑可以表示成：可以表示成：（x）ROBOT(x)COLOR(x，gray)例例2：“一号房间里有一个物体一号房间里有一个物体”，可以表示成，可以表示成（x）INROOM（x,r1）我我们们称称x是是被被量量化化了了的的变变量量，称称为为约约束束变变量量。否则称之为否则称之为自由变量自由变量。一一阶阶谓谓词词：只只允允许许对对变变量量施施加加量量词词，不不允允许许对对谓词和函数施加量词。谓词和函数施加量词。2.3.2谓词公式谓词公式1、谓词公式的定义谓词公式的定义利用连词和量词可以将原子（谓词）公式组成复利用连词和量词可以将原子（谓词）公式组成复合谓词公式，称之为分子谓词公式、谓词合适公合谓词公式，称之为分子谓词公式、谓词合适公式、式、谓词公式谓词公式、合适公式、合适公式。（谓词）（谓词）合适公式合适公式的（递归）定义：的（递归）定义：原子（谓词）公式是合适公式。原子（谓词）公式是合适公式。若若A是合适公式，则是合适公式，则A也是合适公式。也是合适公式。若若A和和B是是合合适适公公式式，则则AB、AB、AB、AB也是合适公式。也是合适公式。若若A是是合合适适公公式式，x为为A的的自自由由变变元元（变变量量），则，则（x）A和和（x）A都是合适公式。都是合适公式。只有按上述规则求得的公式才是合适公式。只有按上述规则求得的公式才是合适公式。例：任何整数或者为正或者为负。例：任何整数或者为正或者为负。数数学学表表达达：对对于于所所有有的的x，如如果果x是是整整数数，则则x或或者为正、或者为负。者为正、或者为负。记作记作：I(x)：“x是整数是整数”。P(x)：“x是正数是正数”。N(x)：“x是负数是负数”。谓词公式谓词公式：（x）（）（I(x)(P(x)N(x)）2、合适公式的性质、合适公式的性质如果如果 P和和 Q是合适公式，则由这两个合适公式是合适公式，则由这两个合适公式构成的合适公式的构成的合适公式的真值表真值表与前面介绍的与前面介绍的真值表真值表相同。相同。如果两个合适公式的真值表相同，则我们称这如果两个合适公式的真值表相同，则我们称这两个合适公式是等价的两个合适公式是等价的，可以用，可以用“”来表示。来表示。对于命题合适公式和谓词合适公式有下列等价关系：对于命题合适公式和谓词合适公式有下列等价关系：否定之否定否定之否定：（P）等价于等价于PPQ等价于等价于PQ狄狄.摩根定律摩根定律（PQ）等价于等价于PQ（PQ）等价于等价于PQ分配律分配律P(QR)等价于等价于(PQ)(PR)P(QR)等价于等价于(PQ)(PR)交换律交换律PQ等价于等价于QPPQ等价于等价于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)等价于等价于(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/ys3=q(z)/x,A/ys4=c/x,A/yPx,f(y),Bs1=Pz,f(w),BPx,f(y),Bs2=Px,f(A),BPx,f(y),Bs3=Pq(z),f(A),BPx,f(y),Bs4=Pc,f(A),BPx,f(y),B置置换换的的合合成成：设设t1/x1,tn/xn和和s1/y1,sm/ym是两个置换，则是两个置换，则和和的合成是如下置换：的合成是如下置换：t1/x1,ti/xi,tn/xn,s1/y1,sn/ym其其中中，若若yj 是是x1,xn之之一一者者消消去去，对对于于任任何何tj=xj 者消去，并记成者消去，并记成。如何求如何求ti:s1/y1,sm/ym如如果果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/yy/y,a/a/x x,b/y y,y/z=f(b)/x,y/z注意注意：置换的合成满足结合律，不满足交换律。置换的合成满足结合律，不满足交换律。(s1s2)s3=s1(s2s3)(满足满足结合律结合律）s1s2s2s1（不不满足满足交换律交换律）例例：s1=z/x,w/ys2=A/ys1s2=z/x,w/y,A/y=z/x,w/ys2s1=A/y,z/x,w/y=A/y,z/x2、合一、合一当当某某一一个个置置换换s作作用用于于表表达达式式集集合合Ei的的每每一一个个元元素素，此此时时我我们们用用Eis来来表表示示置置换换例例子子的的集集合合。如如果存在一个置换果存在一个置换s，使得使得E1s=E2s=Eis=则则我我们们称称表表达达式式集集合合 Ei是是可可合合一一的的，并并称称 s为为Ei的的合合一一者者。原原因因是是它它的的作作用用是是使使集集合合 Ei成成为为单一形式。单一形式。其中，其中，Ei 是原子谓词公式。是原子谓词公式。例例：表表达达式式集集合合Px,f(y),B,Px,f(B),B的的合合一一者为是者为是s=A/x,B/yPx,f(y),Bs=PA,f(B),BPx,f(B),Bs=PA,f(B),B如如果果s是是Ei的的任任意意一一个个合合一一者者，又又存存在在某某一一个个s，使得使得s=gs或者或者Eis=Eigs则则 称称 g是是 Ei的的最最通通用用（最最一一般般）的的合合一一者者，记作记作mgu。例例：s=A/x,B/y是表达式集合是表达式集合Px,f(y),B,Px,f(B),B的一个合一者，该集合的的一个合一者，该集合的最一般的合一者最一般的合一者是：是：g=B/y3、合一算法、合一算法分歧集（或不一致集合）的定义分歧集（或不一致集合）的定义。设有一非空有限公式集合设有一非空有限公式集合 F=F1,Fn，从从 F中各个公式的第一个符号同时向右比较，直到发现中各个公式的第一个符号同时向右比较，直到发现第一个彼此不尽相同的符号为止，从第一个彼此不尽相同的符号为止，从 F中的各个中的各个公式中取出那些以第一个不一致符号开始的公式中取出那些以第一个不一致符号开始的最大的最大的最大的最大的子表达式子表达式子表达式子表达式为元素，组成一个集合为元素，组成一个集合 D，称为称为 F的分的分歧集（不一致集合）。歧集（不一致集合）。其中，其中，Fi (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就就是是要求的要求的mgu。找出找出 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,h(z,u),f(u)的最一般的合一者。的最一般的合一者。解解：我们根据合一算法一步一步地求出：我们根据合一算法一步一步地求出mgu。第一步第一步：k=0,F0=F,0=F0的分歧集合的分歧集合D0=a,z 置换置换：a/z1=0a/z=a/zF1=F0a/z=P(a,x,f(g(y),P(a,h(a,u),f(u)k=1F1不是单一表达式不是单一表达式F=P(a,x,f(g(y)，P(z,h(z,u),f(u)第二步第二步：D1x,h(a,u)置换置换：h(a,u)/x21h(a,u)/x=a/z,h(a,u)/xF2=F1h(a,u)/x=P(a,h(a,u),f(g(y),P(a,h(a,u),f(u)k=2F=P(a,x,f(g(y)，P(a,h(a,u),f(u)第三步第三步：D2g(y),u置换置换：g(y)/u32g(y)/u=a/z,h(a,g(y)/x,g(y)/uF3=F2g(y)/u=P(a,h(a,g(y),f(g(y)k=3F=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)是否可合一？是否可合一？第一步第一步：k=0,F0=F,0=F0的分歧集合的分歧集合D0=f(a),y 置换置换：f(a)/y10f(a)/y=f(a)/yF1=F0 f(a)/y=Q(f(a),g(x),Q(f(a),f(a)k=1F1不是单一表达式不是单一表达式第二步：第二步：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/x10a/x=a/xW1=W0a/x=Q(a,y,z),Q(a,f(b),a)k=1W1不是单一表达式不是单一表达式Q(x,y,z),Q(a,f(b),a)第二步第二步：W1的分歧集合的分歧集合D1=f(b)，y 置换置换：f(b)/y21f(b)/y=a/x,f(b)/yW2=W1f(b)/y=Q(a,f(b),z),Q(a,f(b),a)k=2W2不是单一表达式不是单一表达式Q(a,y,z),Q(a,f(b),a)第三步第三步：W2的分歧集合的分歧集合D0=a,z 置换置换：a/z32a/z=a/x,f(b)/y,a/zW3=W2a/z=Q(a,f(b),a)k=3W3是单一表达式是单一表达式，mgu=3=a/x,f(b)/y,a/zQ(a,f(b),z),Q(a,f(b),a)本章小结本章小结三种基本的知识表达方法：三种基本的知识表达方法：状态空间法状态空间法（状态、操作符、图表示）（状态、操作符、图表示）问题归约法问题归约法（原始问题、本原问题、操作符、（原始问题、本原问题、操作符、与或图表示）与或图表示）谓词逻辑法谓词逻辑法（谓词公式、置换、合一算法）（谓词公式、置换、合一算法）