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

1、人 工 智 能Artificial Intelligence(AI),许建华南京师范大学计算机科学与技术学院2011年秋季,第2章 知识表示方法2.1 状态空间法2.2 问题归约法2.3 谓词逻辑法,2.3 谓词逻辑法数理逻辑（符号逻辑）是用数学方法研究形式逻辑的一个分支。它通过符号系统来表达客观对象以及相关的逻辑推理。常用的是命题逻辑和谓词逻辑,谓词逻辑是数理逻辑的基本形式，是基于谓词分析的一种形式化（数学）语言人工智能中的谓词逻辑法是指用一阶谓词来描述问题求解和定理证明（限于本课程）,2.3.0 命题逻辑的复习,1、命题逻辑的基本概念命题 是能够判断真或假的陈述句通常用大写字母来表示，如A

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

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

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

5、绍一阶谓词逻辑。,2.3.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,

6、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

7、是谓词，则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”。,All,A,Exist,E,例1：“所有的机器人都是灰色的”，用谓词逻辑可以表示成：（x）ROBOT(x)COLOR(x，gray),例2：“一号房间里有一个物体”，可以表示成（x）INROOM（x,r

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

9、数或者为正或者为负。数学表达：对于所有的 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）等价于 PQ,分配律 P(QR)等价于(P

10、Q)(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)等价于(y)P(y),注释：这两个关系说明，在一个量化的表达式中的约束变量是一类虚元，它们可以

11、用任何不在表达式中出现的其它变量来代替。,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/y s3=q(z)/x,A/ys4=c/x,A/y,Px,f(y),Bs1=Pz,f(w),BPx,f(y),Bs2=

12、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,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/

13、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,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 为E

14、i 的合一者。原因是它的作用是使集合 Ei 成为单一形式。其中，Ei 是原子谓词公式。,例：表达式集合Px,f(y),B,Px,f(B),B的合一者为是 s=A/x,B/y Px,f(y),Bs=PA,f(B),B 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、合一算法,分歧集（或不一致集合）的定义。设有

15、一非空有限公式集合 F=F1,Fn，从 F中各个公式的第一个符号同时向右比较，直到发现第一个彼此不尽相同的符号为止，从 F 中的各个公式中取出那些以第一个不一致符号开始的最大的子表达式为元素，组成一个集合 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 只有一个

16、表达式，则算法终止，其中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(

17、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),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(

18、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)是否可合一？,第一步：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

19、 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 10a/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=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),本章小结三种基本的知识表达方法：状态空间法（状态、操作符、图表示）问题归约法（原始问题、本原问题、操作符、与或图表示）谓词逻辑法（谓词公式、置换、合一算法）,