2基本的推理方法(归结反演系统).ppt

3、基本的推理方法 经典推理－－－归结反演 2目标公式中含有全称量词的情况 当目标公式含有全称量词量化的变量时，目标公式的否定式中会出现Skolem函数，结果会与要求不符。 例2已知事实为 1）对所有的x,x是p(x)的孩子。 （?x）C(x,p(x)) 2)对所有的x, y,如果x是y的孩子。则y是x的父辈。（?x）(?y)[C(x,y)?p(y,x)] 解答问题： 3）对任何一个x,谁是x的父辈？ （?x）(?y)P(y,x) 目标公式的否定为（?x）(?y)[?P(y,x)] 目标公式的否定式的子句形式为?P(w,A) 其中A为没有自变量的Skolem函数（即常量）。此例的修改证明树如下图所示。解答语句为P(p(A),A)。解答中出现的常量A与问题中的“任何一个x”不符。事实上证明，在解答提取过程中，可以用新变量代替来自目标公式否定式的子句中的Skolem函数。这些新变量经过替换过程仍会出现在解答语句中。在本例中，经过用新变量代替后的修改证明树如下图所示，最后的解答为P(p(t),t). 3、基本的推理方法 经典推理－－－归结反演 ?C(x,y)?P(y,x) ?P(w,A) ?C(A,w) C(z,p(z)) NIL 例2的反演树 3、基本的推理方法 经典推理－－－归结反演 ?C(x,y)?P(y,x) ?P(w,A)?P(w,A) ?C(A,w)?P(w,A) C(z,p(z)) P(p(A),A) 例2的修改证明树 3、基本的推理方法 经典推理－－－归结反演 ?C(x,y)?P(y,x) ?P(w,t)?P(w,t) ?C(t,w)?P(w,t) C(z,p(z)) P(p(t),t) 例2中变量替换后的修改证明树 设有如下关系： （１）如果ｘ是ｙ的父亲，ｙ又是ｚ的父亲，则ｘ是ｚ的祖父。 （?x）(?y)[P(x,y)?P(y,z)?G(x,z)] （２）老李是大李的父亲 P(Laoli,Dali) （３）大李是小李的父亲 P(Dali,Xiaoli) 问：上述人员中谁和谁是祖孙关系？ (?x)(?y)G(x,y) 习题： 已知:张和李是同班同学，如果x和y是同班同学，则x的教室也是y的教室。现在张在J1-3上课，问李在哪里上课 习题： 已知:张和李是同班同学，如果x和y是同班同学，则x的教室也是y的教室。现在张在J1-3上课，问李在哪里上课 C(x，y)，x和y是同班同学 At(x,u)x在u教室上课 前提：C（Zhang,Li） ?x?y?u(C(x,y)?At(x,u)?At(y,u)) At(Zhang,J1-3) 目标：?vAt（Li，v） 前提：C（Zhang,Li） ?C(x,y)? ? At(x,u)?At(y,u) At(Zhang,J1-3) ?At（Li，v） ?C(x,y)? ? At(x,u)?At(y,u) C（Zhang,Li） ? At(Zhang,u)?At(Li,u) At(Zhang,J1-3) At(Li,J1-3) ?At（Li，v） NIL ?At（Li，v）? At（Li，v） At（Li，J1-3） 已知：John是賊 Paul喜欢酒（Wine） 如果Paul喜欢某物，则John也喜欢 如果某人是贼，而且喜欢某物，则他就可能偷窃该物。 求证：John可能会偷窃了什么？ 已知：John是賊 T(John) Paul喜欢酒（Wine）L(Paul,Wine) 如果Paul喜欢某物，则John也喜欢 如果某人是贼，而且喜欢某物，则他就可能偷窃该物。 求证：John可能会偷窃了什么？ 3、基本的推理方法 经典推理－－－归结反演 合成具有下列性质： （Es1）s2=E s1 s2, 即置换s1和 s2依次作用于E相当于其合成s1 s2作用于E。 (s1 s2)s3=s1 （s2s3），合成满足结合律 s1s2?s2s1，不满足交换律 例如：s1={A/x},s2={x/y}E=P(x,y) Es1s2=P(A,x),Es2s1=P(A,A) 3、基本的推理方法 经典推理－－－归结反演 合成具有下列性质： （Es1）s2=E s1 s2, 即置换s1和 s2依次作用于E相当于其合成s1 s2作用于E。 (s1 s2)s3=s1 （s2s3），合成满足结合律，不满足交换律 把置换s作用于集合｛Ei｝中的每一个公式得到的例的集合用｛Ei｝s表示。如果存在一个置换s，使E1s=E2s=E3s,则称公式集｛Ei｝是可合一的，置换s称为｛Ei｝的合一者。合一者不是唯一的，存在最简合一者mgu(Most General Unifier)。如果对公式集｛Ei｝所有的合一者S，都存在一个置换s’,使｛Ei｝s=｛Ei｝gs’,则称g为公式集｛Ei｝的最