湘潭大学-人工智能课件-确定性推理-part-6.ppt

1、Artificial Intelligence (AI)人工智能人工智能第二章：知识第二章：知识表示与推理表示与推理内容提要1.1.推理的基本概念推理的基本概念2.2.搜索策略搜索策略3.3.自然演绎推理自然演绎推理4.4.消解演绎推理消解演绎推理5.5.基于规则的演绎推理基于规则的演绎推理消解演绎推理子句集及其化简子句集及其化简鲁滨逊消解原理鲁滨逊消解原理消解反演推理的消解策略消解反演推理的消解策略用消解反演求取问题的答案用消解反演求取问题的答案鲁滨逊消解原理命题逻辑的消解命题逻辑的消解谓词逻辑的消解谓词逻辑的消解命题逻辑的消解v命题逻辑的消解反演：命题逻辑的消解反演：在命题逻辑中，已知在命

2、题逻辑中，已知F，证，证明明G为真的消解反演过程如下：为真的消解反演过程如下：否定目标公式否定目标公式G，得，得G;把把G并入到公式集并入到公式集F中，得到中，得到F，G；把把F，G化为子句集化为子句集S。 应用消解原理对子句集应用消解原理对子句集S中的子句进行消解，并中的子句进行消解，并把每次得到的消解式并入把每次得到的消解式并入S中。如此反复进行，若中。如此反复进行，若出现出现空子句空子句，则停止消解，则停止消解，此时就证明了此时就证明了G为真为真。鲁滨逊消解原理命题逻辑的消解命题逻辑的消解谓词逻辑的消解谓词逻辑的消解谓词逻辑的消解v 在谓词逻辑中，由于子句集中的谓词一般都含有在谓词逻辑中

3、，由于子句集中的谓词一般都含有变元变元，因，因此不能象命题逻辑那样直接消去互补文字。此不能象命题逻辑那样直接消去互补文字。v 对于谓词逻辑，需要先用一个最一般对于谓词逻辑，需要先用一个最一般合一合一对变元进行对变元进行置换置换，然后才能进行消解。然后才能进行消解。设设C1和和C2是两个是两个没有公共变元没有公共变元的子句，的子句，L1和和L2分别是分别是C1和和C2中的文字。如果中的文字。如果 是是L1和和 L2存在存在最一般合一最一般合一，则称：则称： C12=(C1- L1)( C2- L2) 为为C1和和C2的的二元消解式二元消解式，L1和和L2为为消解式上的文字消解式上的文字。谓词逻辑

4、的消解设设C1=P(a)R(x)，C2=P(y)Q(b)，求，求 C12解：解：取取L1= P(a), L2=P(y)，则，则L1和和L2的最的最一般合一是一般合一是=a/y。因此：。因此： C12= ( C1-L1) (C2-L2) = (P(a), R(x)-P(a)(P(a), Q(b)-P(a) = (R(x)(Q(b) = R(x), Q(b) = R(x)Q(b)谓词逻辑的消解设设C1=P(x)Q(a)，C2=P(b)R(x) ，求，求 C12解：解：由于由于C1和和C2有相同的变元有相同的变元x，不符合定义的要，不符合定义的要求。为了进行消解，需要修改求。为了进行消解，需要修改C

5、2中变元的名字。令中变元的名字。令C2=P(b)R(y)，此时，此时L1= P(x), L2 =P(b)，L1和和L2的最一般合一是的最一般合一是 =b/x。则有。则有: C12= ( C1-L1) (C2-L2) = (P(b), Q(a)-P(b) (P(b), R(y)-P(b) = (Q(a) (R(y) = Q(a), R(y) = Q(a)R(y)谓词逻辑的消解设设 C1=P(a)Q(x) R(x) C2=P(y)Q(b) 求求C12对对C1和和C2通过最一般合一（通过最一般合一（=b/x, a/y）的作用，）的作用，可以得到可以得到两个互补对两个互补对。注意：求消解式不能同时消去

6、两个互补对注意：求消解式不能同时消去两个互补对，这样的，这样的结果不是二元消解式。如在结果不是二元消解式。如在=b/x, a/y下，若同时下，若同时消去两个互补对，所得的消去两个互补对，所得的R(b)不是不是C1和和C2的二元消的二元消解式。解式。谓词逻辑的消解设设 C1=P(a)Q(x) R(x) C2=P(y)Q(b) 求求C12解解1：取取L1= P(a), L2=P(y)，则，则=a/y是是L1与与L2的最一般合一。此时：的最一般合一。此时： C12= Q(x) R(x) Q(b)解解2：取取L1= Q(x) ，L2=Q(b) ，则，则=b/x是是L1与与L2的最一般合一。此时：的最一

7、般合一。此时： C12= P(a) R(b) P(y)谓词逻辑的消解设设 C1=P(x)P(f(a)Q(x) ，C2=P(y)R(b)求求C12解：解：对参加消解的某个子句，若对参加消解的某个子句，若其内部有可合一的文其内部有可合一的文字字，则在进行消解之前应先对这些文字进行合一。，则在进行消解之前应先对这些文字进行合一。本例的本例的C1中有可合一的文字中有可合一的文字P(x)与与P(f(a)，若用它们的，若用它们的最一般合一最一般合一=f(a)/x进行代换，可得到进行代换，可得到 ： C1=P(f(a)Q(f(a)此时对此时对C1与与C2进行消解。选进行消解。选L1= P(f(a), L2

8、=P(y)，L1和和L2的最一般合一是的最一般合一是=f(a)/y，则可得到，则可得到C1和和C2的的二元消解式为：二元消解式为： C12=R(b)Q(f(a)谓词逻辑的消解设设 C1=P(y)P(f(x)Q(g(x) C2=P(f(g(a)Q(b) 求求C12解：解：对对C1 ，取最一般合一，取最一般合一 =f(x)/y，得，得C1的因子的因子 C1=P(f(x)Q(g(x) 对对C1的因子和的因子和C2消解（消解（=g(a)/x ），可得：），可得： C12=Q(g(g(a)Q(b)谓词逻辑的消解v 我们把我们把C1称为称为C1的的因子因子。一般来说，若子句。一般来说，若子句C中有两个中有

9、两个或两个以上的文字具有最一般合一或两个以上的文字具有最一般合一，则称，则称C为子句为子句C的的因子因子。如果。如果C是一个单文字，则称它为是一个单文字，则称它为C的的单元因子单元因子。应。应用因子概念，可对谓词逻辑中的消解原理给出如下定义：用因子概念，可对谓词逻辑中的消解原理给出如下定义：v若若C1和和C2是无公共变元的子句，则是无公共变元的子句，则子句子句C1和和C2的消解的消解式是下列二元消解式之一式是下列二元消解式之一： C1和和C2的二元消解式的二元消解式; C1的因子的因子C11和和C2的二元消解式；的二元消解式； C1和和C2的因子的因子C22的二元消解式；的二元消解式； C1的

10、因子的因子C11和和C2的因子的因子C2的二元消解式。的二元消解式。v命题逻辑的消解反演：命题逻辑的消解反演：在命题逻辑中，已知在命题逻辑中，已知F，证，证明明G为真的消解反演过程如下：为真的消解反演过程如下：否定目标公式否定目标公式G，得，得G;把把G并入到公式集并入到公式集F中，得到中，得到F，G；把把F，G化为子句集化为子句集S。 应用消解原理对子句集应用消解原理对子句集S中的子句进行消解，并中的子句进行消解，并把每次得到的消解式并入把每次得到的消解式并入S中。如此反复进行，若中。如此反复进行，若出现出现空子句空子句，则停止消解，则停止消解，此时就证明了此时就证明了G为真为真。谓词逻辑的

11、消解谓词逻辑的消解谓词逻辑的消解反演过程与命题逻辑的消解反谓词逻辑的消解反演过程与命题逻辑的消解反演过程相比，其步骤基本相同，但每步的处理演过程相比，其步骤基本相同，但每步的处理对象不同。对象不同。在步骤在步骤(3)化简子句集时，谓词逻辑需要把由谓化简子句集时，谓词逻辑需要把由谓词构成的公式集化为子句集。词构成的公式集化为子句集。在步骤在步骤(4)按消解原理进行消解时，按消解原理进行消解时，谓词逻辑的谓词逻辑的消解原理需要考虑两个亲本子句的最一般合一消解原理需要考虑两个亲本子句的最一般合一。谓词逻辑的消解已知已知F: (x)(y)(A(x, y)B(y)(y)(C(y)D(x, y)G: (x

12、)C(x)(x)(y)(A(x, y)B(y)求证求证G是是F的逻辑结论。的逻辑结论。证明：证明：先把先把G否定，并放入否定，并放入F中，得到的中，得到的F, G： ( x)( y)(A(x,y)B(y)( y)(C(y)D(x,y), ( x)C(x)( x)( y)(A(x,y) B(y)再把再把F,G化成子句集，得到化成子句集，得到谓词逻辑的消解p (1) A(x,y) B(y) C(f(x)p (2) A(u,v) B(v) D(u,f(u)p (3) C(z)p (4) A(m,n)p (5) B(k)最后应用谓词逻辑的消解原理对上述子句集进行消最后应用谓词逻辑的消解原理对上述子句集

13、进行消解，其过程为：解，其过程为：p(6) A(x,y) B(y) p(7) B(n)p(8) NILF G(1)和和(3)消解，取消解，取=f(x)/z(4)和和(6)消解，取消解，取=m/x,n/y(5)和和(7)消解，取消解，取=n/k谓词逻辑的消解因此，因此，G是是F 的逻辑结论。的逻辑结论。上述消解过程可用如下消解树来表示上述消解过程可用如下消解树来表示A(x,y) B(y)C(f(x) C(z)A(x,y) B(y)A(m,n) B(n)B(k)NILf(x)/zm/x,n/yn/k谓词逻辑的消解假设：假设：任何通过计算机考试并获奖的人都是快乐的，任任何通过计算机考试并获奖的人都是

14、快乐的，任何肯学习或幸运的人都可以通过所有考试，张不肯学习何肯学习或幸运的人都可以通过所有考试，张不肯学习但他是幸运的，任何幸运的人都能获奖。但他是幸运的，任何幸运的人都能获奖。求证：求证：张是快乐的。张是快乐的。解：解：先定义谓词：先定义谓词：p Pass(x, y)：x可以通过可以通过y考试考试p Win(x, prize)：x能获得奖励能获得奖励p Study(x) ：x肯学习肯学习p Happy(x)：x是快乐的是快乐的p Lucky(x) ：x是幸运的是幸运的谓词逻辑的消解再将问题用谓词表示如下：再将问题用谓词表示如下：p“任何通过计算机考试并奖的人都是快乐的任何通过计算机考试并奖的

15、人都是快乐的” (x)(Pass(x, computer)Win(x, prize)Happy(x)p “任何肯学习或幸运的人都可以通过所有考试任何肯学习或幸运的人都可以通过所有考试” (x) ( y) (Study(x)Lucky(x)Pass(x, y)p“张不肯学习但他是幸运的张不肯学习但他是幸运的” Study(zhang)Lucky(zhang)p“任何幸运的人都能获奖任何幸运的人都能获奖” (x) (Lucky(x)Win(x, prize)p结论结论“张是快乐的张是快乐的”的的否定否定 Happy(zhang)谓词逻辑的消解将上述谓词公式转化为子句集如下：将上述谓词公式转化为子句

16、集如下：p(1) Pass(x, computer)Win(x, prize)Happy(x)p(2) Study(y)Pass(y, z)p(3) Lucky(u)Pass(u, v)p(4) Study(zhang)p(5) Lucky(zhang)p(6) Lucky(w)Win(w, prize)p(7) Happy(zhang) (结论的否定结论的否定)按消解原理进行消解，消解树如下：按消解原理进行消解，消解树如下：谓词逻辑的消解Pass(x, computer)Win(x, prize)Happy(x)Lucky(w)Win(w, prize)Pass(w, Computer)Ha

17、ppy(w) Lucky(w) Happy(zhang)Lucky(zhang)Pass(zhang, Computer)Lucky(zhang)Pass(zhang, Computer)Lucky(u)Pass(u, v)Lucky(zhang)Lucky(zhang) NILw/xzhang/wzhang/u, computer/v消解演绎推理子句集及其化简子句集及其化简鲁滨逊消解原理鲁滨逊消解原理消解反演推理的消解策略消解反演推理的消解策略用消解反演求取问题的答案用消解反演求取问题的答案消解反演推理的消解策略v 在消解演绎推理中，由于事先并不知道哪些子句对可进行在消解演绎推理中，由于事先

18、并不知道哪些子句对可进行消解，更不知道通过对哪些子句对的消解能尽快得到空子消解，更不知道通过对哪些子句对的消解能尽快得到空子句，因此就需要对子句集中的所有子句逐对进行比较，直句，因此就需要对子句集中的所有子句逐对进行比较，直到得出空子句为止。到得出空子句为止。v 这种这种盲目的全面进行消解盲目的全面进行消解的方法，不仅会产生许多无用的的方法，不仅会产生许多无用的消解式，更严重的是会产生组核爆炸问题。因此，需要研消解式，更严重的是会产生组核爆炸问题。因此，需要研究有效的消解策略来解决这些问题。究有效的消解策略来解决这些问题。限制策略：限制策略：通过限制参加消解的子句减少盲目性通过限制参加消解的子

19、句减少盲目性删除策略：删除策略：通过删除某些无用的子句缩小消解范围通过删除某些无用的子句缩小消解范围消解演绎推理子句集及其化简子句集及其化简鲁滨逊消解原理鲁滨逊消解原理消解反演推理的消解策略消解反演推理的消解策略用消解反演求取问题的答案用消解反演求取问题的答案用消解反演求取问题的答案v 消解原理出了可用于定理证明外，还可用来求取问题答案，消解原理出了可用于定理证明外，还可用来求取问题答案，其思想与定理证明相似。其一般步骤为：其思想与定理证明相似。其一般步骤为： (1) 把问题的已知条件用谓词公式表示出来，并化为子句集；把问题的已知条件用谓词公式表示出来，并化为子句集； (2) 把问题的目标的否

20、定用谓词公式表示出来，并化为子句集；把问题的目标的否定用谓词公式表示出来，并化为子句集； (3) 对目标否定子句集中的每个子句，构造该子句的重言式（即把对目标否定子句集中的每个子句，构造该子句的重言式（即把该目标否定子句和此目标否定子句的否定之间再进行析取所得到该目标否定子句和此目标否定子句的否定之间再进行析取所得到的子句），用这些重言式代替相应的目标否定子句式，并把这些的子句），用这些重言式代替相应的目标否定子句式，并把这些重言式加入到前提子句集中，得到一个新的子句集；重言式加入到前提子句集中，得到一个新的子句集； (4) 对这个新的子句集，应用消解原理求出其证明树，这时对这个新的子句集，应

21、用消解原理求出其证明树，这时证明树证明树的根子句不为空的根子句不为空，称这个证明树为，称这个证明树为修改的证明树修改的证明树； (5) 用修改证明树的根子句作为用修改证明树的根子句作为回答语句回答语句，则答案就在此根子句中。，则答案就在此根子句中。用消解反演求取问题的答案 已知：已知：“张和李是同班同学，如果张和李是同班同学，如果x和和y是同班同学，则是同班同学，则x的的教室也是教室也是y的教室，现在张在的教室，现在张在302教室上课。教室上课。” 问：问：“现在李在哪个教室上课？现在李在哪个教室上课？” 解：解：首先定义谓词首先定义谓词 C(x, y)：x和和y是同班同学是同班同学 At(x

22、, u)：x在在u教室上课。教室上课。 把已知前提用谓词公式表示如下：把已知前提用谓词公式表示如下： C(zhang, li) (x) (y) (u) (C(x, y)At(x, u)At(y,u) At(zhang, 302) 用消解反演求取问题的答案 把目标的把目标的否定否定用谓词公式表示如下：用谓词公式表示如下： (v)At(li, v) 把上述公式化为子句集：把上述公式化为子句集： 把目标的否定化成子句式，并用下面的重言式代替：把目标的否定化成子句式，并用下面的重言式代替： At(li,v) At(li,v) 把此重言式加入前提子句集中，得到一个新的子句集，把此重言式加入前提子句集中，

23、得到一个新的子句集， 对这个新的子句集，应用消解原理求出其证明树。对这个新的子句集，应用消解原理求出其证明树。 C(zhang, li) C(x, y)At(x, u)At(y, u) At(zhang, 302)用消解反演求取问题的答案 求解过程如下图所示。该证明树的根子句就是所求的答案，求解过程如下图所示。该证明树的根子句就是所求的答案，即即“李明在李明在302教室教室”。At(li,v)At(li,v)C(x, y)At(x, u)At(y, u)At(li,v) C(x, li)At(x, v)C(zhang, li) At(zhang,v)At(li, v)At(zhang, 302

24、)At(li, 302)li/y,v/uZhang/x302/v用消解反演求取问题的答案已知：已知：A,B,C三人中有人从不说真话，也有人从不说假三人中有人从不说真话，也有人从不说假话。某人向这三人分别提出同一个问题：谁是说谎者？话。某人向这三人分别提出同一个问题：谁是说谎者？ A答：答：“B和和C都是说谎者都是说谎者”； B答：答：“A和和C都是说谎者都是说谎者”； C答：答：“A和和B中至少有一个是说谎者中至少有一个是说谎者”。问：问：求谁是老实人，谁是说谎者？求谁是老实人，谁是说谎者？解：解：首先定义谓词首先定义谓词 T(x)：表示表示x说真话说真话用消解反演求取问题的答案把已知前提用谓

25、词公式表示如下：把已知前提用谓词公式表示如下：有人从不说真话：有人从不说真话：T(C)T(A)T(B)有人从不说假话：有人从不说假话：T(C)T(A)T(B) 根据根据“A答：答：B和和C都是说谎者都是说谎者”，则则 若若A说真话：说真话：T(A)T(B)T(C) 若若A说假话：说假话： T(A)T(B)T(C)同理：同理：根据根据“B答：答：A和和C都是说谎者都是说谎者”，则，则 T(B)T(A)T(C) T(B)T(A)T(C) 根据根据“C答：答：A和和B中至少有一个是说谎者中至少有一个是说谎者”，则则 T(C)T(A)T(B) T(C)T(A)T(B)用消解反演求取问题的答案把上述公式

26、化成子句集，得到前提子句集把上述公式化成子句集，得到前提子句集S：T(A)T(B)T(A)T(C)T(C)T(A)T(B)T(B)T(C)T(C)T(A)T(B)T(A)T(C)T(B)T(C)先求谁是老实人，结论的否定为：先求谁是老实人，结论的否定为： (x)T(x)用消解反演求取问题的答案把目标的否定化成子句式，并用下面的重言式代替：把目标的否定化成子句式，并用下面的重言式代替： T(x)T(x)把此重言式加入前提子句集把此重言式加入前提子句集S，得到一个新子句集，得到一个新子句集，对这个新的子句集，应用消解原理求出其证明树。对这个新的子句集，应用消解原理求出其证明树。T(A)T(B)T(

27、B)T(C) T(A)T(C)T(A)T(C) T(C)T(x)T(x) T(C)C/xC是老实人是老实人用消解反演求取问题的答案下面证明下面证明A不是老实人，结论的否定为：不是老实人，结论的否定为： T(A)将结论的否定将结论的否定 (T(A) 加入并入前提子句集加入并入前提子句集S中，中，应用消解原理对新的子句集进行消解：应用消解原理对新的子句集进行消解：T(A)T(B)T(B)T(C) T(A)T(C)T(A)T(C) T(A) T(A) NIL得证。得证。A不是不是是老实人是老实人同理可证同理可证B不不是老实人是老实人消解演绎推理简单，便于在计算机上实现。简单，便于在计算机上实现。必须把逻辑公式化成子句集。必须把逻辑公式化成子句集。不便于阅读与理解：不便于阅读与理解：P(x)Q(x)没有没有P(x)Q(x)直观。直观。可能丢失控制信息，如下列逻辑公式：可能丢失控制信息，如下列逻辑公式：(AB)C A(BC)(AC)B B(AC)(CB)A C(BA)化成子句后都是化成子句后都是: ABC