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

1、Artificial Intelligence (AI)人工智能人工智能第二章：知识第二章：知识表示与推理表示与推理内容提要1.1.推理的基本概念推理的基本概念2.2.搜索策略搜索策略3.3.自然演绎推理自然演绎推理4.4.消解演绎推理消解演绎推理5.5.基于规则的演绎推理基于规则的演绎推理自然演绎推理从一组已知为真的事实出发，直从一组已知为真的事实出发，直接运用经典逻辑中的推理规则推出结论的过程称接运用经典逻辑中的推理规则推出结论的过程称为自然演绎推理。为自然演绎推理。假言推理假言推理 拒取式拒取式假言三段论假言三段论自然演绎推理 P, PQ Q表示：表示：由由PQ 以及以及P为真，可以推出

2、为真，可以推出Q为真为真例如：例如：由由“如果如果x是金属，则是金属，则x能导电能导电”，以及，以及“铜是铜是金属金属”，可以推出，可以推出“铜能导电铜能导电”。PQ, Q P表示：表示：由由PQ 为真以及为真以及Q为假，可以推出为假，可以推出P为假为假例如：例如：由由“如果下雨，则地上会湿如果下雨，则地上会湿”，以及，以及“地上不地上不湿湿”，可以推出，可以推出“没有下雨没有下雨”。PQ, QR PR自然演绎推理当当PQ为真时，希望通过肯定后为真时，希望通过肯定后件件Q为真来推出前件为真来推出前件P为真，这是不允许的。为真，这是不允许的。p例如：例如：伽利略在论证哥白尼的日心说时，曾使用了伽

3、利略在论证哥白尼的日心说时，曾使用了如下推理：如下推理：(1)如果行星系统是以太阳为中心的，则金星会显示如果行星系统是以太阳为中心的，则金星会显示出位相变化；出位相变化；(2)金星显示出位相变化；金星显示出位相变化；(3)所有，行星系统是以太阳为中心的所有，行星系统是以太阳为中心的p这就是使用了肯定后件的推理，违反了经典逻辑的这就是使用了肯定后件的推理，违反了经典逻辑的逻辑规则。逻辑规则。自然演绎推理当当PQ为真时，希望通过否定前为真时，希望通过否定前件件P来推出后件来推出后件Q为假，这也是不允许的。为假，这也是不允许的。p例如：例如：(1)如果下雨，则地上会湿如果下雨，则地上会湿(2)没有下

4、雨没有下雨(3)所有，地上不湿所有，地上不湿p事实上，如果向地上洒水，地上也是会湿的。这就事实上，如果向地上洒水，地上也是会湿的。这就是使用了否定前件的推理，违反了经典逻辑的逻辑是使用了否定前件的推理，违反了经典逻辑的逻辑规则。规则。自然演绎推理A, B, AC, BCD, DQQ为真。为真。p因为因为 A, AC C 假言推理假言推理pB, C BC 引入合取词引入合取词pBC，BCD D 假言推理假言推理pD, DQ Q 假言推理假言推理p因此，因此，Q为真为真自然演绎推理 (1) 只要是需要编程序的课，王程都喜欢。只要是需要编程序的课，王程都喜欢。 (2) 所有的程序设计语言课都是需要编

5、程序的课。所有的程序设计语言课都是需要编程序的课。 (3) C是一门程序设计语言课。是一门程序设计语言课。王程喜欢王程喜欢C C这门课。这门课。首先定义谓词首先定义谓词 Prog(x)：x是需要编程序的课。是需要编程序的课。 Like(x, y): x喜欢喜欢y。 Lang(x): x是一门程序设计语言课是一门程序设计语言课自然演绎推理把已知事实及待求解问题用谓词公式表示如下：把已知事实及待求解问题用谓词公式表示如下： Prog(x)Like(Wang , x) (x)( Lang(x)Prog(x) Lang(C)应用推理规则进行推理：应用推理规则进行推理： Lang(y)Prog(y) 全

6、称固化全称固化 Lang(C)，Lang(y)Prog(y) Prog(C) 假言推理假言推理 C/y Prog(C), Prog(x)Like(Wang , x) Like(Wang , C) 假假言推理言推理 C/x因此，王程喜欢因此，王程喜欢C这门课。这门课。自然演绎推理定理证明过程自然，易于理解，并且有定理证明过程自然，易于理解，并且有丰富的推理规则可用。丰富的推理规则可用。是容易产生知识爆炸，推理过程中得到是容易产生知识爆炸，推理过程中得到的中间结论一般按指数规律递增，对于复杂问的中间结论一般按指数规律递增，对于复杂问题的推理不利，甚至难以实现。题的推理不利，甚至难以实现。内容提要1

7、.1.推理的基本概念推理的基本概念2.2.搜索策略搜索策略3.3.自然演绎推理自然演绎推理4.4.消解演绎推理消解演绎推理5.5.基于规则的演绎推理基于规则的演绎推理消解演绎推理是一种基于鲁滨逊（是一种基于鲁滨逊（Robinson）消解原理的机器推理技术。消解原理的机器推理技术。鲁滨逊消解原理亦称为鲁滨逊消解原理亦称为消解原理消解原理，是鲁滨逊于，是鲁滨逊于1965年在年在海伯伦（海伯伦（Herbrand）理论的基础上提出的一种基于逻）理论的基础上提出的一种基于逻辑的辑的“反证法反证法”。在人工智能中，几乎所有的问题都可以转化为一个定理在人工智能中，几乎所有的问题都可以转化为一个定理证明问题。

8、证明问题。定理证明的实质，就是要对前提定理证明的实质，就是要对前提P和结论和结论Q，证明证明PQ永真。永真。要证明要证明PQ永真，就是要证明永真，就是要证明PQ在任何一个非空的在任何一个非空的个体域上都是永真的。这将是非常困难的，甚至是不可个体域上都是永真的。这将是非常困难的，甚至是不可实现的。实现的。消解演绎推理鲁滨逊消解原理把鲁滨逊消解原理把永真性永真性的证明转化为关于的证明转化为关于不可满足不可满足性性的证明。的证明。要证明要证明PQ永真永真，只需证明，只需证明PQ不可满足不可满足p因为：因为： (PQ) ( PQ) P Q海伯伦海伯伦(Herbrand)定理为自动定理证明奠定了理论基础

9、。定理为自动定理证明奠定了理论基础。鲁滨逊鲁滨逊(Robinson)提出的消解原理使机器定理证明成为提出的消解原理使机器定理证明成为现实。现实。消解演绎推理子句集及其化简子句集及其化简鲁滨逊消解原理鲁滨逊消解原理消解反演推理的消解策略消解反演推理的消解策略用消解反演求取问题的答案用消解反演求取问题的答案消解演绎推理子句集及其化简子句集及其化简鲁滨逊消解原理鲁滨逊消解原理消解反演推理的消解策略消解反演推理的消解策略用消解反演求取问题的答案用消解反演求取问题的答案子句集及其化简v鲁滨逊消解原理是在鲁滨逊消解原理是在子句集子句集的基础上讨论问题的。的基础上讨论问题的。因此，讨论消解演绎推理之前，需要

10、先讨论子句因此，讨论消解演绎推理之前，需要先讨论子句集的有关概念。集的有关概念。原子谓词公式及其否定统称为原子谓词公式及其否定统称为文字文字。p例如例如: P(x)、Q(x)、 P(x)、 Q(x)等都是文字。等都是文字。任何任何文字文字的的析取式析取式称为称为子句子句。p例如，例如，P(x)Q(x)，P(x，f(x)Q(x，g(x)都是子都是子句。句。子句集及其化简不含任何文字的子句称为不含任何文字的子句称为空子句空子句。p由于空子句不含有任何文字，也就不能被任何解释由于空子句不含有任何文字，也就不能被任何解释所满足，因此空子句是所满足，因此空子句是永假的永假的，不可满足的不可满足的。p空子

11、句一般被记为空子句一般被记为NIL。由子句或空子句所构成的集合称为由子句或空子句所构成的集合称为子句集子句集。p在子句集中，子句之间是在子句集中，子句之间是合取关系合取关系p子句集中的子句集中的变元受全称量词的约束变元受全称量词的约束p任何谓词公式都可通过等价关系及推理规则化为相任何谓词公式都可通过等价关系及推理规则化为相应的子句集应的子句集子句集及其化简1： 利用等价关系消去利用等价关系消去“”和和“”p反复使用如下等价公式：反复使用如下等价公式： PQ PQ PQ (PQ)(PQ) 即可消去谓词公式中的连接词即可消去谓词公式中的连接词“”和和“”。p例如：例如： (x)(y)P(x,y)

12、(y)(Q(x,y)R(x,y) 经等价变化后为：经等价变化后为： (x)(y)P(x,y) (y)(Q(x,y)R(x,y)子句集及其化简2：利用等价关系把利用等价关系把“”移到紧靠谓词的位置上移到紧靠谓词的位置上p反复使用反复使用 双重否定率：双重否定率：(P) P 摩根定律：摩根定律： (PQ) PQ (PQ) PQ 量词转换率：量词转换率： (x)P(x) (x) P(x) (x)P(x) (x) P(x) 使得每个否定符号最多只作用于一个谓词上。使得每个否定符号最多只作用于一个谓词上。p例如：例如：上式上式(x)(y)P(x,y) (y)(Q(x,y)R(x,y) 经等价变换后为经等

13、价变换后为 (x)(y)P(x，y)(y)( Q(x，y) R(x，y)子句集及其化简3：重新命名变元，使不同量词约束的变元有不同重新命名变元，使不同量词约束的变元有不同的名字的名字p例如：例如：上式经重新命名变换后为上式经重新命名变换后为 (x)(y)P(x，y)(z)( Q(x，z) R(x，z)消去存在量词。消去存在量词时，需要区分以消去存在量词。消去存在量词时，需要区分以下两种情况：下两种情况：p1）存在量词不出现在全称量词的辖域内，只要用一）存在量词不出现在全称量词的辖域内，只要用一个新的个体常量替换受该存在量词约束的变元，就个新的个体常量替换受该存在量词约束的变元，就可消去该存在量

14、词。例如：可消去该存在量词。例如： (x)P(x) 可化为可化为P(A) p2）存在量词位于一个或者多个全称量词的辖域内）存在量词位于一个或者多个全称量词的辖域内子句集及其化简 如下面的谓词公式：如下面的谓词公式： (x1)(xn) (y)P(x1，x2 , xn ,y) 则需要用则需要用Skolem函数函数f(x1，x2 , xn)替换受该存在量替换受该存在量词约束的变元词约束的变元y，然后再消去该存在量词。，然后再消去该存在量词。p例如：例如：继续上面的例子继续上面的例子 (x)(y)P(x，y)(z)( Q(x，z) R(x，z) 式子中存在量词式子中存在量词( y)及及( z)都位于都

15、位于( x)的辖域内，所的辖域内，所以需要用以需要用Skolem函数替换，设替换函数替换，设替换y和和z的的Skolem函函数分别是数分别是f(x)和和g(x)，则替换后得到：，则替换后得到： (x)(P(x , f(x)(Q(x , g(x)R(x , g(x)子句集及其化简把全称量词全部移到公式的左边把全称量词全部移到公式的左边p上式中由于只有一个全称量词，而且它位于公式的上式中由于只有一个全称量词，而且它位于公式的最左边，所以这里不需要做任何工作。最左边，所以这里不需要做任何工作。p如果在公式内部有全称量词，就需要把它们都移到如果在公式内部有全称量词，就需要把它们都移到公式的左边。公式的

16、左边。利用等价关系利用等价关系 P (QR) (PQ) (PR) 把公式化为把公式化为Skolem标准形标准形pSkolem标准形的一般形式为标准形的一般形式为 (x1)(xn) M(x1,x2,xn)p其中，其中， M(x1,x2,xn)是是Skolem标准形的母式，它标准形的母式，它由子句的由子句的合取合取所构成。所构成。子句集及其化简p例如：例如：前面的公式化为前面的公式化为Skolem标准形后为标准形后为 (x)( (P(x , f(x)Q(x , g(x) (P(x , f(x) R(x , g(x) )消去全称量词。由于母式中的全部变元均受全消去全称量词。由于母式中的全部变元均受全

17、称量词的约束，并且全称量词的次序已无关紧要，因此称量词的约束，并且全称量词的次序已无关紧要，因此可以省掉全称量词。可以省掉全称量词。p例如：例如：上式消去全称量词后为上式消去全称量词后为 (P(x , f(x)Q(x , g(x) (P(x , f(x)R(x , g(x)对变元更名，对变元更名，使不同子句中的变元不同名使不同子句中的变元不同名p例如：例如：上式经更名后得到上式经更名后得到 (P(x , f(x)Q(x , g(x) (P(y , f(y)R(y , g(y)子句集及其化简消去合取词，就得到消去合取词，就得到子句集子句集。p例如：例如：消去合取词后，上式消去合取词后，上式(P(

18、x , f(x)Q(x , g(x) (P(y , f(y)R(y , g(y) 就变为下述子句集就变为下述子句集P(x , f(x)Q(x , g(x)P(y , f(y)R(y , g(y)子句集及其化简在上述化简过程中，由于在消去存在量词时所用的在上述化简过程中，由于在消去存在量词时所用的Skolem函数可以不同，因此函数可以不同，因此化简后的标准子句集是不化简后的标准子句集是不唯一的唯一的。因此，当原谓词公式为因此，当原谓词公式为非永假非永假时，时，它与其标准子句集它与其标准子句集并不等价并不等价。但当原谓词公式为永假（或不可满足）时，。但当原谓词公式为永假（或不可满足）时，其标准子句

19、集则一定是永假的，其标准子句集则一定是永假的，即即Skolem化并不影响化并不影响原谓词公式的永假性原谓词公式的永假性。对于对于任意论域中的任意一个解任意论域中的任意一个解释释，S中的子句不能同时取得真值中的子句不能同时取得真值T。子句集及其化简设有谓词公式设有谓词公式F，其子句集为，其子句集为S，则，则F不可满不可满足的充要条件是足的充要条件是S不可满足不可满足。由此定理可知，要证明一个谓词公式是不可满足的，只由此定理可知，要证明一个谓词公式是不可满足的，只要证明其相应的标准子句集是不可满足的就可以了。要证明其相应的标准子句集是不可满足的就可以了。由于子句集中的子句之间是合取关系，子句集中只

20、要有由于子句集中的子句之间是合取关系，子句集中只要有一个子句为不可满足，则整个子句集就是不可满足的。一个子句为不可满足，则整个子句集就是不可满足的。空子句是不可满足的。因此，一个子句集中如果包含有空子句是不可满足的。因此，一个子句集中如果包含有空子句，则此子句集就一定是不可满足的。空子句，则此子句集就一定是不可满足的。这个结论是这个结论是鲁滨逊消解原理的主要依据。鲁滨逊消解原理的主要依据。消解演绎推理子句集及其化简子句集及其化简鲁滨逊消解原理鲁滨逊消解原理消解反演推理的消解策略消解反演推理的消解策略用消解反演求取问题的答案用消解反演求取问题的答案鲁滨逊消解原理首先把欲证明问题的结论首先把欲证明

21、问题的结论否定否定，并加入子句集，得到，并加入子句集，得到一个扩充的子句集一个扩充的子句集S；然后设法检验子句集然后设法检验子句集S是否含有空子句，若含有空子句，是否含有空子句，若含有空子句，则表明则表明S是不可满足的；若不含有空子句，则继续使用是不可满足的；若不含有空子句，则继续使用消解法，在子句集中选择合适的子句进行消解，消解法，在子句集中选择合适的子句进行消解，直至直至导出空子句或不能继续消解为止导出空子句或不能继续消解为止。命题逻辑的消解命题逻辑的消解谓词逻辑的消解谓词逻辑的消解命题逻辑的消解v消解推理的核心是求两个子句的消解推理的核心是求两个子句的消解式消解式若若P是原子谓词公式，则

22、称是原子谓词公式，则称P与与P为为互补文字互补文字设设C1和和C2是子句集中的任意两个子句，如果是子句集中的任意两个子句，如果C1中的中的文字文字L1与与C2中的中的文字文字L2互补互补，那么可从，那么可从C1和和C2中中分别消去分别消去L1和和L2，并将，并将C1和和C2中中余下的余下的部分按析取关系构成一个新的子句部分按析取关系构成一个新的子句C12，则称这，则称这一过程为一过程为消解消解，称，称C12为为C1和和C2的的消解式消解式，称，称C1和和C2为为C12的的亲本子句亲本子句。命题逻辑的消解设设C1=PQR，C2=PS，求，求C1和和C2的消的消解式解式C12。解：解：这里这里L1

23、=P，L2=P，通过消解可以得到，通过消解可以得到p C12= QRS设设C1=Q，C2=Q，求，求C1和和C2的消解式的消解式C12。解：解：这里这里L1=Q，L2=Q，通过消解可以得到，通过消解可以得到p C12= NIL命题逻辑的消解设设设设C1 =P Q ，C2=Q，C3=P，求，求C1、C2、C3的消解式的消解式C123。解：若先对解：若先对C1、C2消解，可得到消解，可得到p C12=P然后再对然后再对C12和和C3消解，得到消解，得到p C123=NIL如果改变消解顺序，同样可以得到如果改变消解顺序，同样可以得到相同的结果，即其消解过程是不唯相同的结果，即其消解过程是不唯一的。一

24、的。其消解消解过程可用右图来表示，其消解消解过程可用右图来表示，该树称为该树称为消解树消解树。P QQP P NILP Q P QQ NIL命题逻辑的消解v定理：定理：消解式消解式C12是其亲本子句是其亲本子句C1和和C2的逻辑结论。的逻辑结论。v证明：证明：设设C1=LC1 ，C2=LC2关于解释关于解释I为真，则为真，则只需证明只需证明C12= C1 C2关于解释关于解释I也为真。也为真。对于解释对于解释I，L和和L中必有一个为假。中必有一个为假。若若L为假为假，则必有，则必有C1为真，不然就会使为真，不然就会使C1为假，这将为假，这将与前提假设与前提假设C1为真矛盾，因此只能有为真矛盾，

25、因此只能有C1为真。为真。同理，同理，若若L为假为假，则必有，则必有C2为真。为真。因此，必有因此，必有C12= C1C2关于解释关于解释I也为真。即也为真。即C12是是C1和和C2的逻辑结论。的逻辑结论。命题逻辑的消解v推论推论1：设设C1和和C2是子句集是子句集S中的两个子句，中的两个子句，C12是是C1和和C2的消解式，若的消解式，若用用C12代替代替C1和和C2后得到新的子句后得到新的子句集集S1，则由，则由S1的不可满足性可以推出原子句集的不可满足性可以推出原子句集S的不可的不可满足性。即：满足性。即： S1的不可满足性的不可满足性S的不可满足性的不可满足性v推论推论2：设设C1和和

26、C2是子句集是子句集S中的两个子句，中的两个子句，C12是是C1和和C2的消解式，若的消解式，若把把C12加入加入S中得到新的子句集中得到新的子句集S2，则则S与与S2的不可满足性是等价的。即：的不可满足性是等价的。即： S2的不可满足性的不可满足性S的不可满足性的不可满足性命题逻辑的消解v上述两个推论说明，为证明子句集上述两个推论说明，为证明子句集S的不可满足性，的不可满足性，只要对其中可进行消解得子句进行消解，只要对其中可进行消解得子句进行消解，并把消并把消解式加入到子句集解式加入到子句集S中，或者用消解式代替他的亲中，或者用消解式代替他的亲本子句本子句，然后对新的子句集证明其不可满足性就

27、，然后对新的子句集证明其不可满足性就可以了。可以了。v如果经消解能得到空子句，根据空子句的不可满如果经消解能得到空子句，根据空子句的不可满足性，即可得到原子句集足性，即可得到原子句集S是不可满足的结论。是不可满足的结论。v在命题逻辑中，对不可满足的子句集在命题逻辑中，对不可满足的子句集S，其消解原，其消解原理是完备的。即：理是完备的。即：子句集子句集S S是不可满足的，当且仅是不可满足的，当且仅当存在一个从当存在一个从S S到空子句的消解过程。到空子句的消解过程。 命题逻辑的消解v命题逻辑的消解反演命题逻辑的消解反演消解原理：消解原理：假设假设F为已知前提，为已知前提，G为欲证明的结为欲证明的

28、结论，消解原理把证明论，消解原理把证明G为为F的逻辑结论转化为证的逻辑结论转化为证明明FG为不可满足为不可满足。再根据上述定理，在不可满足的意义上，公式再根据上述定理，在不可满足的意义上，公式集集FG与其子句集是等价的，即把公式集上与其子句集是等价的，即把公式集上的不可满足的不可满足转化为子句集上的不可满足转化为子句集上的不可满足。应用消解原理证明定理的过程称为应用消解原理证明定理的过程称为消解反演消解反演。命题逻辑的消解v命题逻辑的消解反演：命题逻辑的消解反演：在命题逻辑中，已知在命题逻辑中，已知F，证，证明明G为真的消解反演过程如下：为真的消解反演过程如下：否定目标公式否定目标公式G，得，

29、得G;把把G并入到公式集并入到公式集F中，得到中，得到F，G；把把F，G化为子句集化为子句集S。 应用消解原理对子句集应用消解原理对子句集S中的子句进行消解，并中的子句进行消解，并把每次得到的消解式并入把每次得到的消解式并入S中。如此反复进行，若中。如此反复进行，若出现出现空子句空子句，则停止消解，则停止消解，此时就证明了此时就证明了G为真为真。命题逻辑的消解v例如：例如：设已知的公式集为设已知的公式集为 P, (PQ)R, (ST)Q, T ，求证，求证结论结论R。解：解：假设结论假设结论R为假为假, 将将R加加入公式集，并化为子句集：入公式集，并化为子句集： S=P,PQR, SQ, TQ, T, R其消解过程如右图的消解演绎其消解过程如右图的消解演绎树所示。该树根为空子句树所示。该树根为空子句。子句集子句集S不可满足，即假设不可满足，即假设R为真是错误的，于是为真是错误的，于是R为真。为真。P QR RP QPQT QTTNIL