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

人工智能ArtificialIntelligence(AI)许建华[e-mail]南京师范大学计算机科学与技术学院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为假。②“∧”表示“合取”复合命题“P∧Q”为真，当且仅当P和Q都为真。④“”表示“蕴含”复合命题“PQ”为假，当且仅当P为真且Q为假。③“∨”表示“析取”复合命题“P∨Q”为真，当且仅当P、Q两者之一为真。⑤“”表示“等价”复合命题“PQ”为真，当且仅当P、Q同时为真、或者同时为假。联接词的优先顺序：非～、合取∧、析取∨、蕴含、等价注：可以用括号表示优先级真值表PQ～PP∧QP∨QPQPQFFTFFTTFTTFTTFTFFFTFFTTFTTTT命题变元：用符号P、Q等表示的不具有固定、具体含义的命题。它可以表示具有“真”、“假”含义的各种命题。命题变元可以利用联结词构成所谓的合适公式。合适公式的定义①若P为原子命题，则P为合适公式，称为原子公式。②若P是合适公式，则～P也是一个合适公式。③若P和Q是合适公式，则P∧Q、P∨Q、PQ、PQ都是合适公式。④经过有限次使用规则1、2、3，得到的由原子公式、联结词和园括号所组成的符号串，也是合适公式。对于合适公式，规定下列运算优先级：①逻辑联结词的运算优先次序为：～、∧、∨、、②同级联结词按出现顺序优先运算在命题逻辑中，主要研究推理的有效性。即：能否根据一些合适公式（前提）推导出新的合适公式（结论）。一些合适公式（前提条件）合适公式（结论）？在命题逻辑中，最基本的单元是命题，它是作为一个不可分割的整体。例如：雪是黑的命题逻辑具有较大的局限性，不合适于表达比较复杂的问题。例：所有科学都是有用的（假设1）。数理逻辑是科学（假设2）。所以，数理逻辑是有用的（结论）。很明显，我们无法用两个假设推断出结论。谓词逻辑是命题逻辑的扩充和发展。它将一个原子命题分解成客体和谓词两个组成部分。例如：雪是黑的客体谓词本课程主要介绍一阶谓词逻辑。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,z来表示。函数（或函词）：以个体为变量，以个体为值的函数。一般用小写字母来表示，例如f(x),f(x,a)。如果谓词有n个变量，称之为n元谓词，并约定0元谓词就是命题（谓词的特例）。如果函数有n个个体，称之为n元函数，并约定0元函数就是常量。常量习惯上用小写字母来表示，如a,b,c。项的定义：①常量是项②变量是项③如果f是n元函数，且t1,…,tn(n≥1)是项，则f(t1,…,tn)也是项④所有的项都必须是有限次应用上述规则产生的项的例子：常量：a变量：x函数：f(x,a)g(f(x,a))原子（谓词）公式的（递归）定义：①原子命题是原子公式②如果t1,…,tn(n≥1)是项，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”。AllAExistE例1：“所有的机器人都是灰色的”，用谓词逻辑可以表示成：（x）[ROBOT(x)COLOR(x，gray)]例2：“一号房间里有一个物体”，可以表示成（x）INROOM（x,r1）我们称x是被量化了的变量，称为约束变量。否则称之为自由变量。一阶谓词：只允许对变量施加量词，不允许对谓词和函数施加量词。2.3.2谓词公式1、谓词公式的定义利用连词和量词可以将原子（谓词）公式组成复合谓词公式，称之为分子谓词公式、谓词合适公式、谓词公式、合适公式。（谓词）合适公式的（递归）定义：①原子（谓词）公式是合适公式。②若A是合适公式，则～A也是合适公式。③若A和B是合适公式，则A∧B、A∨B、AB、AB也是合适公式。④若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）等价于P②P∨Q等价于～PQ③狄.摩根定律～（P∨Q）等价于～P∧～Q～（P∧Q）等价于～P∨～Q④分配律P∧(Q∨R)等价于(P∧Q)∨(P∧R)P∨(Q∧R)等价于(P∨Q)∧(P∨R)⑤交换律P∧Q等价于Q∧PP∨Q等价于Q∨P⑥结合律(P∧Q)∧R等价于P∧(Q∧R)(P∨Q)∨R等价于P∨(Q∨R)⑦逆否律PQ等价于～Q～P说明：上述等价关系对命题合适公式、谓词合适公式都成立。对于谓词合适公式有下列等价关系：⑧～(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的一个例子。例：表达式（原子谓词公式）P[x,f(y),B]的四个置换及其对应的四个例子（B是常量）s1={z/x,w/y}s2={A/y}s3={q(z)/x,A/y}s4={c/x,A/y}P[x,f(y),B]s1=P[z,f(w),B]P[x,f(y),B]s2=P[x,f(A),B]P[x,f(y),B]s3=P[q(z),f(A),B]P[x,f(y),B]s4=P[c,f(A),B]P[x,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/x2}＝{f(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,w/y,A/y}={z/x,w/y}s2s1={A/y,z/x,w/y}={A/y,z/x}2、合一当某一个置换s作用于表达式集合{Ei}的每一个元素，此时我们用{Ei}s来表示置换例子的集合。如果存在一个置换s，使得E1s=E2s=…=Eis=…则我们称表达式集合{Ei}是可合一的，并称s为{Ei}的合一者。原因是它的作用是使集合{Ei}成为单一形式。其中，Ei是原子谓词公式。例：表达式集合{P[x,f(y),B],P[x,f(B),B]}的合一者为是s={A/x,B/y}P[x,f(y),B]s=P[A,f(B),B]P[x,f(B),B]s=P[A,f(B),B]如果s是{Ei}的任意一个合一者，又存在某一个s’，使得s=gs’或者{Ei}s={Ei}gs’则称g是{Ei}的最通用（最一般）的合一者，记作mgu。例：s={A/x,B/y}是表达式集合{P[x,f(y),B],P[x,f(B),B]}的一个合一者，该集合的最一般的合一者是：g={B/y}3、合一算法分歧集（或不一致集合）的定义。设有一非空有限公式集合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的