人工智能-4经典逻辑推理.ppt

海伯伦定理 可以证明，对给定域D上的任一个解释，总能在H域上构造一个解释与它对应，如果D域上的解释能满足子句集S，则在H域上的相应解释也能满足S。 定理4.2 子句集S不可满足的充要条件是S对H域上一切解释都为假。 定理4.3(海伯伦定理) 子句集不可满足的充要条件是存在一个有限的不可满足的基子句集S`。 证明：充分性： 设子句集S有一个不可满足的基子句集S`，因为它不可满足，所以一定存在一个解释I`使S`为假。根据H域上的解释与D域上解释的对应关系，可知在D域上一定存在一个解释使S不可满足，即子句集S是不可满足的。 必要性： 设子句集S不可满足，有定例4.2可知对H域上一切解释都为假，这样必然存在一个基子句集S`，且它是不可满足的。 4.3.3 鲁滨逊归结原理 子句集中子句之间是合取关系，只要有一个子句不可满足，则子句集就不可满足。而空子句是不可满足的。所以若一个子句集中包含空子句，则这个子句集一定是不可满足的。 鲁滨逊归结原理的基本思想：检查子句集S中是否包含空子句。若包含，则S不可满足；若不包含，就在子句集中选择合适的子句进行归结，一旦通过归结能推出空子句，就说明子句集S是不可满足的。 定义4.9 若P是原子谓词公式，则称P与?P为互补文字。 命题逻辑中的归结原理 定义4.10 设C1与C2是子句集中的任意两个子句。如果C1中的文字L1与C2中文字L2互补，那么从C1和C2中分别消去L1和L2，并将两个子句中余下的部分析取，构成一个新子句C12，则称这一过程为归结。称C12为C1和C2的归结式，C1和C2为C12的亲本子句。 例4.9 设 C1=?P∨Q, C2=?Q∨R, C3=P C1与C2归结得到：C12=?P∨R C12与C3归结得到：C123=R 定理4.4 C12是其亲本子句C1与C2的逻辑结论。 证明：设 C1=L∨C`1, C2=?L∨C`2, 则C12=C`1∨C`2 推论1 设C1与C2是子句集S中的两个子句，C12是它们的归结式。若用C12代替C1和C2后得到新子句集S1，则由S1的不可满足性可推出原子句集S的不可满足性，即 S1的不可满足性＝S的不可满足性 推论2 设C1与C2是子句集S中的两个子句，C12是它们的归结式。若把C12加入S中得到新子句集S2，则S与S2在不可满足的意义上是等价的，即 S2的不可满足性＝S的不可满足性 归结原理的基本思想 为了要证明子句集S的不可满足性，只要对其中可进行归结的子句进行归结，并把归结式加入子句集S，或者用归结式替换它的亲本子句，然后对新子句集(S1或者S2)证明不可满足性就可以了。如果经过归结能得到空子句，则立即可得原子句集S是不可满足的结论。 在命题逻辑中，对不可满足的子句集S，归结原理是完备的。即，若子句集不可满足，则必然存在一个从S到空子句的归结演绎；若存在一个从S到空子句的归结演绎，则S一定是不可满足的。 对于可满足的子句集，用归结原理得不到任何结果。 谓词逻辑中的归结原理 在谓词逻辑中，由于子句中含有变元，所以不能像命题逻辑那样直接消去互补文字，而需要先用最一般合一对变元进行代换，然后才能进行归结。 例如,设有两个子句 C1=P(x)∨Q(x), C2= ?P(a)∨R(y) 由于P(x)与P(a)不同，所以C1与C2不能直接进行归结。但是若用最一般合一 σ={a/x} 对两个子句分别进行代换： C1σ =P(a)∨Q(a) C2σ = ?P(a)∨R(y) 就可对它们进行归结，得到归结式： Q(a)∨R(y) 二元归结式的定义 定义4.11 设C1与C2是两个没有相同变元的子句，L1和L2分别是C1和C2中的文字。若σ是L1和?L2的最一般合一，则称 C12=(C1σ-{L1σ})∪(C2σ-{L2σ}) 为C1和C2的二元归结式，L1和L2称为归结式上的文字。 例4.10 设 C1=P(a)∨?Q(x)∨R(x), C2=?P(y)∨Q(b) 若选L1=P(a),L2=?P(y)，则σ={a/y}是L1与?L2的最一般合一。 可得： C12 =(C1σ-{L1σ})∪(C2σ-{L2σ}) =({P(a),?Q(x),R(x)}-{P(a)})∪({?P(a),Q(b)}-{?P(a)}) =({?Q(x),R(x)})∪({Q(b)}) ={?Q(x),R(x),Q(b)} = ?Q(x)∨R(x)∨Q(b) 谓词逻辑中归结原理的定义 一般来说，若子句C中有两个或者两个以上的文字具有最一般合一σ，则称Cσ为子句C的因子。 定义4.12 子句C1和C2的归结式是下列二元归结式之一： C1与C2的二元归结式； C1与C2的因子C2σ2的二元归结式； C1的因子C1σ1与C2的二元归结式； C1的因子C1σ1与C2的因子C