人工智能第四章经典逻辑推理.ppt

4.3.2 归结原理 鲁滨逊归结原理基本思想 首先把欲证明问题的结论否定，并加入子句集，得到一个扩充的子句集S‘。然后设法检验子句集S’是否含有空子句，若含有空子句，则表明S‘是不可满足的； 若不含有空子句，则继续使用归结法，在子句集中选择合适的子句进行归结，直至导出空子句或不能继续归结为止。 鲁滨逊（Robinson）归结原理包括 命题逻辑归结原理 谓词逻辑归结原理 * 第六十一页，共九十五页，2022年，8月28日 一、命题逻辑的归结原理 归结推理的核心是求两个子句的归结式 (1) 归结式的定义及性质 定义3.9 若P是原子谓词公式，则称P与﹁P为互补文字。 定义3.10 设C1和C2是子句集中的任意两个子句，如果C1中的文字L1与C2中的文字L2互补，那么可从C1和C2中分别消去L1和L2，并将C1和C2中余下的部分按析取关系构成一个新的子句C12，则称这一过程为归结，称C12为C1和C2的归结式，称C1和C2为C12的亲本子句。 4.3.2 归结原理 * 第六十二页，共九十五页，2022年，8月28日 例3.5 设C1=P∨Q∨R，C2=﹁P∨S，求C1和C2的归结式C12。 解：这里L1=P，L2=﹁P，通过归结可以得到 C12= Q∨R∨S 例3.6 设C1=﹁Q，C2=Q，求C1和C2的归结式C12。 解：这里L1=﹁Q，L2=Q，通过归结可以得到 C12= NIL 4.3.2 归结原理 * 第六十三页，共九十五页，2022年，8月28日 例3.7 设C1 =﹁P ∨ Q ， C2=﹁Q，C3=P，求C1、C2、C3的 归结式C123。 解：若先对C1、C2归结，可得到 C12=﹁P 然后再对C12和C3归结，得到 C123=NIL 如果改变归结顺序，同样可以得到相同的结果，即其归结过程是不唯一的。 其归结过程可用右图来表示，该树称为归结树。 ﹁P ∨ Q ﹁Q ﹁P P NIL ﹁P ∨ Q P Q ﹁Q NIL 4.3.2 归结原理 * 第六十四页，共九十五页，2022年，8月28日 定理3.2 归结式C12是其亲本子句C1和C2的逻辑结论。 证明：（按定义）设C1=L∨C1 ’ ，C2=﹁L∨C2’关于解释I为真，则只需证明C12= C1 ’ ∨C2’关于解释I也为真。 对于解释I，L和﹁L中必有一个为假。 若L为假，则必有C1为真，不然就会使C1为假，这将与前提假设C1为真矛盾，因此只能有C1为真。 同理，若﹁L为假，则必有C2为真。 因此，必有C12= C1∨C2关于解释I也为真。即C12是C1和C2的逻辑结论。 4.3.2 归结原理 * 第六十五页，共九十五页，2022年，8月28日 上述定理是归结原理中的一个重要定理，由它可得到以下两个推论： 推论1：设C1和C2是子句集S中的两个子句，C12是C1和C2的归结式，若用C12代替C1和C2后得到新的子句集S1，则由S1的不可满足性可以推出原子句集S的不可满足性。即： S1的不可满足性 ? S的不可满足性 推论2：设C1和C2是子句集S中的两个子句，C12是C1和C2的归结式，若把C12加入S中得到新的子句集S2，则S与S2的不可满足性是等价的。即： S2的不可满足性?S的不可满足性 4.3.2 归结原理 * 第六十六页，共九十五页，2022年，8月28日 上述两个推论说明，为证明子句集S的不可满足性，只要对其中可进行归结的子句进行归结，并把归结式加入到子句集S中，或者用归结式代替他的亲本子句，然后对新的子句集证明其不可满足性就可以了。 如果经归结能得到空子句，根据空子句的不可满足性，即可得到原子句集S是不可满足的结论。 在命题逻辑中，对不可满足的子句集S，其归结原理是完备的。 这种不可满足性可用如下定理描述： 定理3.3 子句集S是不可满足的，当且仅当存在一个从S到空子句的归结过程。 4.3.2 归结原理 * 第六十七页，共九十五页，2022年，8月28日 二、谓词逻辑的归结原理 在谓词逻辑中，由于子句集中的谓词一般都含有变元，因此不能象命题逻辑那样直接消去互补文字。而需要先用一个最一般合一对变元进行代换，然后才能进行归结。可见，谓词逻辑的归结要比命题逻辑的归结麻烦一些。 谓词逻辑的归结原理 谓词逻辑中的归结式可用如下定义来描述： 定义3.11 设C1和C2是两个没有公共变元的子句，L1和L2分别是C1和C2中的文