AI-6(本)人工智能课件

人工智能基础2.3.2归结演绎方法－归结反演、规则演绎定理的自动证明一般表示形式为：

{F1,F2,…,Fn}|=WF1,F2,…,Fn－合适公式公式间隐含合取关系，构成一个公式集（公理集、事实集）W－待证明的一个合适公式（定理、目标公式）证明的方法分二类：演绎法——直接证明F1∧F2∧…∧Fn

W为永真；从而，当公式集为真时，定理W成立。反证法——间接证明

(F1∧F2∧…∧Fn

W)为永假。*即证明F1∧F2∧…∧Fn∧

W的永假性，即{F1,F2,…,Fn}∪{

W}是一个矛盾集。2.3.2归结演绎方法海伯伦

H域(海伯伦域)和海伯伦定理——为自动定理证明奠定理论基础将合适公式标准化为子句集引入H域，从理论上给出了证明子句集(从而合适公式)永假(即不可满足)的可行性及方法鲁宾逊归结原理——使机器定理证明成为现实

1.H域和海伯伦定理

1）子句和子句集

子句——仅由文字（原子谓词公式或其取反）的析取构成的合适公式

合取范式(子句的合取)——表示为子句集，子句间隐含合取关系P(A)∧[P(y)∨

Q(A,z)∨P(z,g(z))]∧[

P(f(A,y))∨

Q(A,z)∨P(z,g(z))]

{P(A)，P(y)∨

Q(A,z)∨P(z,g(z))，

P(f(A,y))∨

Q(A,z)∨P(z,g(z))}

变量换名，保持子句间的相互独立性{P(A)，P(y1)∨

Q(A,z1)∨P(z1,g(z1))，

P(f(A,y2))∨

Q(A,2)∨P(z2,g(z2))}

1.H域和海伯伦定理

1）子句和子句集

重要性质——一个合适公式F化简为标准化的子句集S时，

S的不可满足成为F永假的充分必要条件。

S的不可满足－对于任意论域上的任意解释，S中都至少有一个子句真值为FF和S并非等价——F的化简过程中，为消除存在量词而引入了Skölem函数，使子句集S只是F的一个特例。F和S在永假性上等价——建立海伯伦定理的重要基础。

1.H域和海伯伦定理

2）H域(海伯伦域）证明子句集的不可满足性的困难若能构造一个简单的特殊论域，只需证明子句集在该域不可满足…H域的迭代构造：S－子句集，D－S的某个论域

(1)令H0是S中出现的所有常量的集合，若S中未出现常量，就任取常量a

D,并令H0={a}。

(2)令Hi+1=Hi∪{出现于S中的函数在Hi上的所有实例},i=1,2,…；

形如f(x1,x2,…,xn)的函数的实例通过让xj=kj∈Hi来形成(j=1,2,…,n)

Hi可以迭代扩展到H∞，称H∞为海伯伦域，简称H域(一个可数无穷集)

2）H域(海伯伦域）

H域的迭代构造：

(1)令H0

是S中出现的所有常量的集合，若S中未出现常量，就任取常量a

D,并令H0={a}。

(2)令Hi+1=Hi∪{出现于S中的函数在Hi上的所有实例},Hi迭代扩展到H∞1.子句集S={

P(x)∨R(f(x)),Q(y,g(y))}，有：

H0={a},任取一常量a∈D；

H1={a，f(a),g(a)}H2={a，f(a),g(a),

f(f(a)),f(g(a)),g((f(a)),g(g(a))}…2.子句集S={P(a)∨Q(b),R(f(z,y))},有：

H0={a,b}H1={a,b,f(a,a),f(a,b),f(b,a),f(b,b)}H2={a,b,f(a,a),f(a,b),f(b,a),f(b,b),

f(a,f(a,a)),f(a,f(a,b)),f(a,f(b,a)),f(a,f(b,b)),f(b,f(a,a)),…}…3.子句集S={P(x),Q(y)∨R(z)},有

H0=H1=…=H∞={a}2）H域(海伯伦域）－子句集的永假性H域上的原子谓词公式实例集A:

A={所有出现于S中原子谓词公式的实例}。原子公式是命题(不含变量)——其实例就是其本身；P(t1,t2,…,tm)——其实例通过让ti=ki∈H(即H∞)来形成；例：子句集S={

P(x)∨R(f(x)),Q(y,g(y))}

H={a，f(a),g(a),f(g(a)),g((f(a)),f(f(a)),g(g(a))),…}

A={P(a),R(f(a)),Q(a,g(a)),P(f(a)),R(f(f(a))),…}；基原子——A中的元素，是原子命题

A－基原子集

2）H域(海伯伦域）I*——子句集在H域上的一个解释建立：给基原子集中的每个基原子指派一个真值(T或F)基原子自身－取真值T，

基原子－F

例：子句集S={

P(x)∨R(f(x)),Q(y,g(y))}

A={P(a),R(f(a)),Q(a,g(a)),P(f(a)),R(f(f(a))),…}；

I1*={P(a),R(f(a)),Q(a,g(a)),P(f(a)),R(f(f(a)))…}

TI2*={

P(a),R(f(a)),Q(a,g(a)),P(f(a)),R(f(f(a)))…}TI3*={P(a),

R(f(a)),Q(a,g(a)),P(f(a)),R(f(f(a)))…}F

…S真值

对于子句集S的任一可能论域D上的任一解释I,总能在S的H域上构造一个相应的解释I*,使子句集具有相同的真值。确定子句集S在H域上的所有解释都不满足－>子句集不可满足2.H域和海伯伦定理

3）H域上解释的语义树

用语义树描述子句集在H域上的可能解释命题集——基原子集是有限集:每个基原子只可能有二个真值（T或F)，易画出完整的语义树例：包含原子命题公式P、Q和R的子句集基原子集A={P、Q、R}，语义树如图：

从树根节点n0到叶子节点n的路径指示一个解释——I(n)，其表示为路径上标记的集合，每个标记是一个文字。I(n32)={P,Q,

R}对语义树指示的每个解释判断>子句集的真假性判断>永真性、可满足性一般的子句集，H是可数无穷集，语义树可能成为一棵无穷树。

3）H域上解释的语义树例:子句集S={P(x)∨Q(f(x)),

P(a),

Q(y)}H={a,f(a),f(f(a)),…}A={P(a),Q(a),P(f(a)),Q(f(a)),…}

封闭语义树的生成：封闭语义树——子句集不可满足时，语义树有穷，不必无限扩展，即可确定语义树上的所有路径都分别对应一个导致子句集不满足的解释。3）H域上解释的语义树基子句——变量用H域中元素取代后的子句，即基文字(基原子或其取反)或基文字的析取。

x=a时，从子句P(x)∨Q(f(x))生成基子句P(a)∨Q(f(a))

语义树中每一导致子句集S不满足的路径(相应于H域上一解释)都至少引起一个基子句真值为F。

I(n42)={

P(a),

Q(a),P(f(a)),

Q(f(a))}

引起基子句P(a)∨Q(f(a)真值为F建立一棵封闭语义树时，也即建立了一个由有限个不可同时满足的基子句构成的集合S‘

4）海伯伦定理海伯伦定理－子句集S不可满足的充要条件是存在一个有限的不可满足的基子句集S‘。子句集S不可满足(永假)<——封闭语义树——有限的不可满足的基子句集S‘基于海伯伦定理法的自动定理证明的主要困难：子句集的不可满足性是不可判的依据H域上的每个解释判别不满足的基子句，计算量过大

3归结原理H域(海伯伦域)和海伯伦定理，为自动定理证明奠定了理论基础为提高判定子句集不可满足的有效性归结(Resolution)原理(消解原理)－鲁宾逊，1965简单易行，便于计算机实现和执行使定理的机器自动证明成为现实，人工智能技术实用化的一次重要突破

基本思路：通过归结方法不断扩充待判定的子句集,并设法使其包含进指示矛盾的空子句空子句是不可满足(永假)的子句子句集中子句间隐含着合取关系，出现空子句即判定子句集不可满足3归结原理

1）归结方法归结式C=C1’∨C2’由二个子句C1=L∨C1’,C2=

L∨C2’归结而成从C1和C2中消去互补文字L和

L，并通过析取将C1和C2的剩余部分组成新的子句例：P(A)∨Q(x)∨R(f(x))，

P(A)∨Q(y)∨R(y)的归结式：

Q(x)∨R(f(x))∨Q(y)∨R(y)归结式性质定理：二个子句C1和C2

的归结式C是C1和C2的逻辑推论。在任一使子句C1和C2为真的解释I下，必有归结式C为真。推论：设C1和C2是子句集S中的两个子句，并以C作为它们的归结式，则通过往S中加入C而产生的扩展子句集S’与子句集S在不可满足的意义上是等价的，即：S’的不可满足

S的不可满足空子句C=□由C1=L和C2=

L归结而成空子句是不可满足的子句，指示C1

和C2

是一对矛盾子句，成为用归结原理判定子句集不可满足的成功标志。3归结原理

2）归结推理过程命题逻辑中的归结推理过程：子句中文字为原子命题公式或其取反无变量，易判别包含互补文字的子句对。归结过程表示为归结演绎树：例：S={

P∨Q,P∨R,

Q,

R}

S’={

P∨Q,P∨R,

Q,

R,Q∨R,R,□}

S’不可满足<=>S不可满足谓词逻辑中的归结推理过程：子句中含变量，不能直接发现和消去互补文字需对潜在的互补文字先作变量置换和合一处理2）归结推理过程－变量置换变量置换—用置换项取代公式中的变量,置换项可以是变量、常量或函数服务于合一处理的一个置换——表示为包含若干置换元素（形如t/v）的集合

t/v——置换项/变量例：潜在的互补文字：P(x,y,x,g(x)),

P(A,B,A,z)置换：S1={A/x,B/y,g(x)/z}

S2={f(w)/x,z/y,C/z}S3={B/x,f(w)/y,y/z}置换结果：{P(x,y,x,g(x)),

P(A,B,A,z)}S1

={P(A,B,A,g(A)),

P(A,B,A,g(A))}

{P(x,y,x,g(x)),

P(A,B,A,z)}S2

={P(f(w)),z,f(w),g(f(w)),

P(A,B,A,C)}{P(x,y,x,g(x)),

P(A,B,A,z)}S3

={P(B,f(w),B,g(B)),

P(A,B,A,y)}通过变量置换，使相应于两个潜在互补文字的原子谓词公式同一化2）归结推理过程匹配过程：(1)二个公式必须具有相同的谓词和参数项个数；(2)从左到右逐个检查对应参数项的可同一性：

若一对参数项中有一个变量v，并初次出现，则这对参数项可同一，并以另一参数t为置换项，与该变量一起构成一个置换元素t/v；

若该变量出现过，则已建立相应的置换元素，就取其置换项，代替该变量，检查是否与另一参数同一；若不能同一，则合一处理失败。

若一对参数项中没有一个是变量，则它们应是相同常量，否则合一处理失败。(3)若每对参数项都可同一，则合一处理成功，并构成用于实现合一的置换。对潜在互补文字的合一处理——通过变量置换，使相应于这两个文字的原子谓词公式同一化的过程。归结演绎过程中只须对原子谓词公式作合一处理，通过一个匹配过程去检查两个原子谓词公式的可合一性，并同时建立用于实现合一的置换。P(x,y,x,g(x)),

P(A,B,A,z)2）归结推理过程对原子谓词公式作合一处理，通过一个匹配过程去检查两个原子谓词公式的可合一性，并同时建立用于实现合一的置换。匹配过程：（1）二个公式必须具有相同的谓词和参数项个数；（2）从左到右逐个检查对应参数项的可同一性：

若一对参数项中有一个变量v，并初次出现，则这对参数项可同一，并以另一参数t为置换项，与该变量一起构成一个置换元素t/v；

若该变量出现过，则已建立相应的置换元素，就取其置换项，代替该变量，检查是否与另一参数同一；若不能同一，则合一处理失败。

若一对参数项中没有一个是变量，则它们应是相同常量，否则合一处理失败。（3）若每对参数项都可同一，则合一处理成功，并构成用于实现合一的置换。例：P(x,y,x,g(x)),

P(A,B,A,z)可合一，实现合一的置换S1={A/x,B/y,g(x)/z}

2）归结推理过程－谓词逻辑中子句归结例：C1=P(x,y)∨Q(x,f(x))∨R(x,f(y))C2=

P(A,B)∨

Q(z,f(z))∨R(z,g(z))令L11=P(x,y),L21=

P(A,B),L11和

L21可合一L11和L21是互补文字置换S1={A/x,B/y}变量的置换必须在整个子句对范围内进行归结式：Q(A,f(A))∨R(A,f(B))∨

Q(z,f(z))∨R(z,g(z))两个子句可以有多于一对的互补文字另一对互补文字：L12=Q(x,f(x)),L22=

Q(z,f(z))置换S2={z/x}归结式：P(z,y)∨R(z,f(y))∨

P(A,B)∨R(z,g(z))2）谓词逻辑中的归结推理过程给定子句集：(1)

R(x,y)∨

Q(y)∨P(f(x))(2)

R(z,y)∨

Q(y)∨W(x,f(x))(3)

P(z)(4)R(A,B)(5)Q(B)对这些子句进行归结：（6）

R(x,y)∨

Q(y),（1）与（3）归结，{f(x)/z}；（7）

Q(B)，（6）与（4）归结，{A/x,B/y}；（8）口，（7）与（5）归结。归结过程生成的归结演绎树：

3）归结演绎的完备性基于归结的演绎方法是完备的若子句集S不可满足，就必定存在一个从S到空子句的归结演绎;若存在一个从S到空子句的归结演绎，则S必定是不可满足的。归结原理不能用于解决子句集不可满足性的不可判问题

(永真、可满足)2.3.3归结反演－应用归结演绎方法的定理证明

1.归结反演系统定理的自动证明－反证法归结反演的基本思路：要从作为事实的公式集F证明目标公式W为真，可以先将W取反，加入公式集F，标准化F为子句集S，再通过归结演绎证明S不可满足，并由此得出W为真的结论.归结反演系统：标准化部件——将每条事实和取反的目标公式分别标准化为子句集，再合并为子句集S；归结演绎部件——遵从归结演绎方法，控制定理证明的全过程例：食物问题形式化－标准化－归结演绎－归结反演树归结反演系统－形式化1）形式化确定谓词－Like、Food、Eat、Alive由于Killed和Alive是反义词，以Alive取代¬Killed上述事实的形式化表示如下：

(∀x)[Food(x)=>Like(Wang,x)]

Food(Apples)

(∀x)(∀y)[Eat(y,x)∧Alive(y)=>Food(x)]

Eat(Li,Peanuts)∧Alive(Li)

(∀x)[Eat(Li,x)=>Eat(Zhang,x)

目标形式化表示为：Like(Wang,Peanuts)已知下列事实为真：王（Wang）喜欢（Like）所有种类的食物（Food）.苹果（Apples）是食物。

任何一个东西，若任何人吃了(Eat)它都不会被害死(Killed)，则该东西是食物。李（Li）吃花生（Peanuts）且仍然活着（Alive）。张（zhang）吃任何李吃的东西。证明：王喜欢花生。1.归结反演系统－归结演绎、归结反演树子句集S:

(1)¬Food(x1)∨Like(Wang,x1)

(2)Food(Apples)

(3)¬Eat(y,x2)∨¬Alive(y)∨Food(x2)

(4)Eat(Li,Peanuts)

(5)Alive(Li)

(6)¬Eat(Li,x3)∨Eat(Zhang,x3)

(7)¬Like(Wang,Peanuts)3)归结演绎应用归结演绎方法不断生成归结式以扩展子句集S，直到生成空子句。此时目标公式得以证明，即王确实喜欢花生.

归结演绎过程的演绎树(归结反演树)：2.3.3归结反演

2.归结策略归结反演－－大子句集引起演绎效率问题选择有利于导致快速产生空子句的子句对进行归结删除策略：删除无用子句限制策略：设置选用条件支持集、线性输入、单文字子句优先、祖先过滤等策略…归结反演技术未在定理自动证明以外的领域得到广泛应用。2.3.3归结反演

3.提取问题回答问题回答系统目标公式往往是受存在量词约束的，形如（

x）W(x)

证明目标公式为真，并给出使W(x)为真的个体实例，即x的某个取值——回答提取问答系统的运作：归结反演回答提取：（1）对于标准化取反的目标公式而产生的子句(目标子句)G,建立其重言式G∨

G；（2）以G∨

G取代G,重复已进行过的归结演绎过程,建立修改证明树

归结反演树的树根为

G,且G中的变量已为其置换项取代,实现了回答提取3.提取问题回答

食物问题例：张吃什么食物？目标公式取反并标准化为子句:(

x)[Food(x)]∧Eat(Zhang,x)(8)

Food(x4)∨

Eat(Zhang,x4)进行归结反演并生成归结反演树:进行回答提取,建立(8)式的重言式:

Food(x4)∨

Eat(Zhang,x4)∨[Food(x4)∧Eat(Zhang,x4)]用其取代(8)式重复已进行过的归结演绎过程，产生修正的归结反演树－修改证明树:(下页图2.28)(1)Food(x1)∨Like(Wang,x1)(2)Food(Apples)(3)Eat(y,x2)∨

Alive(y)∨Food(x2)(4)Eat(Li,Peanuts)(5)Alive(Li)(6)Eat(Li,x3)∨Eat(Zhang,x3)