人工智能原理第5章消解法.pptx

1、人工智能原理第4章 消解法,1,本章内容4.1 消解法的基本思想4.2 Herbrand定理4.3 消解法4.4 消解策略参考书目,第4章 消解法,2,4.1 消解法的基本思想,第4章 消解法,3,消解法的基本思想,从第3章逻辑系统中可知，逻辑推理必须考虑其有效性(即|=A)，即对论域中的任何赋值都能保证公式为真由可靠性定理知：逻辑系统中任何正确的推理，都要具有“如果|A则|=A”的性质，即证明推理的有效性从有效性和可满足性的关系可知，有效性等价于其否命题的不可满足性,第4章 消解法,4,消解法基本思想:反证法,这样就引出了消解法，其基本思想就是反证法 即：要证命题(理解为经典逻辑的公式)A恒

2、为真，等价于证A恒为假从语义上解释，恒为假就是不存在一个论域上的一个赋值(可称为解释)，使A为真，即对所有的论域上的所有赋值，A均为假但是，论域本身和解释有无穷多个，不可能一一验证,第4章 消解法,5,基本思想(1),Herbrand提出：从所有解释当中选出一种有代表性的解释，并严格证明一旦命题在代表性解释中为假，则在所有解释中为假Herbrand定义了这样的论域和代表性解释，称为Herbrand论域(H论域)和Herbrand解释(H解释)有定理公式A(无前束范式)是不可满足的，当且仅当A在所有Herbrand赋值下都取假值,第4章 消解法,6,基本思想(2),这样，在证假(不可满足)的意义

3、上使公式与子句集的语义解释等价、并与H解释等价，作为消解法的开端但如何找到H解释？引入语义树，让所有解释都展现在语义树上最后在改进寻找解释算法的复杂性中发现了消解式，从而构成了消解法的完整理论基础消解也叫归结，本章混用这两个称呼,第4章 消解法,7,4.2 Herbrand定理4.2.1 公式到子句集的转换 4.2.2 Herbrand论域和解释4.2.3 语义树4.2.4 Herbrand定理4.2.5 不可满足基子句集,第4章 消解法,8,证明的步骤,证明一个公式A在给定论域下恒为真，也就是要证明A恒为假将A转化为一个子句集，集合中元素为原子公式或其析取/通过其中正负原子公式的合并(此时恒

4、为真，对证假不起作用，因此消去)/最后集合为空，说明是不可满足的，即恒为假通常形式：证明(AB)为假即AB为假，也即对应子句集归结为空子句首先介绍基本术语复习和公式到子句集的转换,第4章 消解法,9,4.2.1 公式到子句集的转换,首先复习几个定义：文字(literal)：正原子公式和负原子公式称为文字，同一原子公式的正和负称为互补的。子句(clause)：文字的析取称为子句。合取范式：形如A1A2An的公式，其中A1An均为子句。前束范式：形如(Q1x1Qn xn)M(x1xn)的公式，M中不再含有量词。Skolem标准形：在前束范式中消去存在量词后得到的公式,第4章 消解法,10,消去存在

5、量词,消去存在量词的步骤：(1)若存在量词不在任何全称量词之后，则公式中被存在量词量化的变量以某个不同于公式中任何其他常量名字的常量c代替，并消去存在量词；(2)若存在量词在k个全称量词之后，则公式中被存在量词量化的变量用被前k个全称量词量化的变量x1xk的某个函数f(x1xk)的形式代替，f的名字不同于公式中任何其他函数的名字，但对函数形式没有要求；然后消去存在量词/函数f称为Skolem函数,第4章 消解法,11,公式转化为子句集的步骤(1),公式A化为子句集S，其实现步骤共9步，如下：(1)消去等价和蕴含符号：蕴含转化为析取(2)将否定符号转移到每个谓词之前：应用狄摩根定律(3)变量标准

6、化：约束变量各不相同(4)消去存在量词：存在量词不受全称量词约束，则变量用常量替换/如果存在量词受全称量词约束，则使用Skolem函数替换相应变量得到Skolem标准形,第4章 消解法,12,公式转化为子句集的步骤(2),(5)公式化为前束型：全部全称量词移到公式的最前面/得到的两部分称为前缀和母式(6)母式化为合取范式：外层连接符全部是合取，里层连接符全部为析取(7)去掉所有全称量词(8)母式化为子句集：每个合取项间的合取符号()用逗号代替，即得子句集(9)子句变量标准化：每个子句中的变量各不相同,第4章 消解法,13,公式与子句集的等价,实现消解法的基础是把参与推理的每个公式都转化为子句集

7、/通过逐步对消子句集合中互补的文字(即L和L)而最终得到一个空子句，证明原来的公式是不可满足的反证法定理：给定公式A及相应的子句集S，则A是不可满足的当且仅当S是不可满足的使用子句集进行消解法推理，其过程是完备的即如果公式X是子句集S的逻辑推论，则X可以从S中推出,第4章 消解法,14,4.2.2 Herbrand论域和解释,Herbrand论域定义Herbrand论域(H论域)：设S为子句集，H0是S中子句所含的全体常量集，若S中子句不含常量，则任选一常量a令H0=a。对i1令Hi=Hi-1f(t1,tn)|n1f 是S中的任一函数符号，t1,tn是Hi-1中的元素则Hi 称为S的i阶常量集

8、，H称为S的Herbrand论域，其元素称为基项。,第4章 消解法,15,H论域例子,例1：S=P(a),P(a)P(f(x)根据定义有H0=a/H1=af(a)=a,f(a)H2=a,f(a)f(a),f(f(a)=a,f(a),f(f(a)H=a,f(a),f(f(a)例2：S=P(x),Q(f(a)R(g(b)H0=a,b/H1=a,b,f(a),f(b),g(a),g(b)H2=a,b,f(a),f(b),g(a),g(b),f(f(a),f(f(b),f(g(a),H=a,bf(c),g(d)|c,d H,第4章 消解法,16,Herbrand原子集,Herbrand原子集定义Her

9、brand基(原子集)：设S为子句集，H是其H论域，则称为S的H基，H中元素称为基原子/此为S中所有原子公式取H论域上所有可能值的集合对于例1，其H=P(a),P(f(a),P(f(f(a),对于例2，其H=P(a),Q(a),R(a),P(b),Q(b),R(b),P(f(a),Q(f(a),R(f(a),P(f(b),第4章 消解法,17,Herbrand解释(1),Herbrand解释是一种语义结构Herbrand解释：子句集S的H解释由下列基本部分组成：(1)基本区域H(H论域对应U)(2)S的每个常量c对应H域中的同一c(3)S的每个变量在H域中取值(4)S中每个函数fn对应于一个映

10、射HHH(n个)H，使得对于(t1,t2,tn)H则f(t1,t2,tn)H,第4章 消解法,18,Herbrand解释(2),(5)S中的每个谓词Pn对应于一个映射HHH(n个)T,F该定义表明，一旦给定一个子句集，其H解释基本就确定了/唯一留下的自由度是由谓词P代表的映射即H到T,F的映射。H可以分解如下：H=H1H2hH1，v(h)=T；hH2，v(h)=F这样，一旦给出H1或H2，则H解释就完全确定了，通常是给出H1,第4章 消解法,19,H解释例子,例子：在例2中设含有常量a的谓词都为T，含有常量b的谓词都为F，则S的H解释=P(a),Q(a),R(a),P(f(a),Q(f(a),

11、R(f(a),P(f(f(a)显然，如果子句集S的H基(原子集)有n个元素(谓词)，则谓词取不同真值的组合有2n种，也即2n不同种解释,第4章 消解法,20,4.2.3 语义树,语义树的表示：要寻找S的H解释的不可满足性质，可以把所有H解释展现在一棵语义树上，然后观察S对应的各个原子公式的真假值。这是一种很直观的研究方式，称为语义树方法设S=P,Q,R，则H=a，H=P(a),Q(a),R(a)(只有一个常量a，在语义树中可省略)因为是二值逻辑，研究每个基原子(即S的原子公式)的取值可以通过原子及其否定(即文字)来观察/构造如下二叉形式的语义树,第4章 消解法,21,语义树示例,通常用I(Ni

12、)表示从根节点到节点Ni分枝上所标记的所有文字的并集。如：I(N22)=P,Q，I(N35)=P,Q,R,第4章 消解法,22,语义树定义(1),子句集S语义树的定义定义设子句集S，对应H基为H，S的语义树ST定义如下：(1)ST是一棵树；(2)ST的节点均不带标记，而边的标记是基原子且不包含其中的变量(边的标记可能不止一个，用逗号分割)；(3)从每个非叶节点只生成有限个边L1Ln，令Qi是每个Li的标记的合取，则Q1Q2Qn为永真；(4)从根节点到任一叶子节点的路径上，所有边的标记的并集中不含重复的基原子，也不含互补的基原子,第4章 消解法,23,语义树定义(2),定义规范语义树：如果一棵语

13、义树的每条边的标记均为一个原子公式定义完备语义树：如果一棵语义树从根节点到任一叶节点的路径上所有边标记的并集中包含子句集中每个原子或其负原子，则该语义树称为完备的(完全的),第4章 消解法,24,语义树定义(3),对于给定的S，其语义树一般都不唯一。下图中语义树和前图中的语义树对应于同一个H基。这两个图的语义树都是完备的,第4章 消解法,25,语义树定义(4),因为一般H基是个无穷集合，所以其对应的语义树也是无限的因为在完备语义树的每一条路径上都有S的全部原子(或负原子)，所以对这些原子公式的真值判定就能决定S的一个解释对于有限完备语义树来说，如果N是一个叶节点，则I(N)便是S的一个解释/这

14、样，S的不可满足性就与完备语义树路径的真值计算联系起来,第4章 消解法,26,语义树定义(5),定义基例：如果S的某个子句C中所有变量符号均以S的H域的元素(常量)代入时，所得的子句C称为C的一个基例定义否节点：如果语义树节点N的从根节点到N的路径I(N)使S的某个子句的某个基例为假，而其父辈节点不能判断此事实(即I(N)是使基例为假的最小路径)，则称N为否节点(或失败节点)定义封闭语义树：如果一棵完全语义树的每个分枝上都有一个否节点，则称为封闭语义树,第4章 消解法,27,封闭语义树例子(1),例：设子句集S=P(x)Q(x),P(f(x),Q(f(x)则H=a,f(a),f(f(a),=P

15、(a),Q(a),P(f(a),Q(f(a),包括3个子句:P(x)Q(x),P(f(x),Q(f(x)其封闭语义树如下图所示,第4章 消解法,28,封闭语义树例子(2),第4章 消解法,29,封闭语义树例子(3),封闭语义树中每个否节点用表示在上图中，每个否节点的路径为：I(N2/2)=P(a),Q(a)，使(P(a)Q(a)=F；I(N3/2)=P(a),Q(a),P(f(a)，使P(f(a)=F；I(N4/9)=P(a),Q(a),P(f(a),Q(f(a)，使Q(f(a)=F如此等等上述每个路径所代表的解释已经使S的某个子句为假，因此再扩充路径仍然只能使同一子句为假，所以没有扩充、延伸

16、的必要,第4章 消解法,30,有限封闭语义树,上例说明，从不可满足的角度来说，对于无限完备语义树只需搜索到一个否节点，则该分枝即被证明为不可满足。这样实际上构成的是一个有限树所以就有Herbrand定理：子句集S不可满足，当且仅当它所对应的每棵完备语义树均包含一个有限的封闭子树(封闭语义树),第4章 消解法,31,4.2.4 Herbrand定理,Herbrand定理有两种形式Herbrand定理I：子句集S不可满足，当且仅当它所对应的每棵完备语义树均包含一个有限的封闭子树(封闭语义树)证明：充分性设S是不可满足的，T是S的一株完备语义树。设B是T的任意一个分支路径，则IB是对应该分支上S的一

17、个解释由S的不可满足性知IB使S的某子句的某个基例为假。则B上有节点N且N是T的否节点,第4章 消解法,32,Herbrand定理I的证明,因为S中子句的个数有限，每个子句所含的文字也有限，则IB中的文字个数也有限，因此否节点N离T的根节点只有有限步。因为T是二叉树且每个节点只有两个子节点，由B的任意性可知，T所有分支上的否节点所构成的封闭语义树必是有限的。必要性已知S存在有限的封闭语义树T。设I是S的任一解释，则其落在T的某个分支B上，B上必有否节点N存在可知I(N)使S的某子句的某个基例C为假。由I(N)I及任意性，可知S是不可满足的,第4章 消解法,33,Herbrand定理II(1),

18、Herbrand定理II：S是不可满足的，当且仅当存在S的一个不可满足的有限基例集证明：充分性设S是不可满足的，及T是S的一个完备语义树。由Herbrand定理I知存在T的有限封闭子树T。T存在有限路径和末端否节点，即使S的某个子句的某基例为假。将基例加起来，即得一 个不可满足的有限基例集,第4章 消解法,34,Herbrand定理II(2),必要性设SS且不可满足的有限基例集。设I是S的任一解释，应有S的解释II，已知I使S的某个基例为假，于是I使其为假，即使S为假，故S不可满足如同语义树的结构不唯一，不可满足的有限基子句集也不唯一从自动证明的角度，定理II是基础,第6章 消解法,35,4.

19、2.5 不可满足基子句集,不可满足基子句集的生成：可通过逐步测试基子句集中各有限子集的方法来找出，此为Gilmore算法(算法略，参见陆著)/当S不可满足时，该算法一定结束(半可判定)但该算法具有指数复杂性，为此提出了改进规则，改进的规则称为Davis-Putnam预处理,第4章 消解法,36,Davis-Putnam预处理(1),Davis-Putnam预处理：(1)重言式(永真式)删除规则：删去所有重言式子句，因为与不可满足性无关；(2)单文字(单句节)删除规则：如果S中包含一个单文字子句L(即只有一个原子公式)，则从S中删去所有含L的子句，从S中删去所有子句中的 L文字。经过如此处理的子

20、句集为S，若S为空，则S是可满足的，若S非空，则S与S同是不可满足的；(3)纯文字删除规则：如果S中只包含文字L而不包含L，则删去所有包含L的子句；,第4章 消解法,37,Davis-Putnam预处理(2),(4)分离规则(分裂规则)：如果 S=(LA1)(LAm)(LB1)(LBn)R其中Ai、Bj、R皆不包含L或L，则令 S1=A1AmR S2=B1BnRS是不可满足的等价于S1S2是不可满足的(即S1、S2同时不可满足)。经过Davis-Putnam预处理以后的子句集与原子句集在不可满足性上等价,第4章 消解法,38,4.3 消解法4.3.1 置换与合一4.3.2 消解式4.3.3 消

21、解法的实施,第4章 消解法,39,消解法的形式,进一步推广Davis-Putnam规则，就得到了消解法。例如设此时只要使用单文字删除规则就可以推出结论Q。但是如果子句中包含变量，则常常必须经过变量置换才能进行消解本节的内容：置换与合一/合一算法/子句化简与消解式/消解法实施/消解法合理性和完备性,第4章 消解法,40,4.3.1 置换与合一,定义置换(或代换)：设x1xn是n个变量，且各不相同，t1tn是n个项(常量、变量、函数)，tixi，则有限序列t1/x1,t2/x2 tn/xn称为一个置换置换可以作用于谓词公式，也可以作用于项。置换=t1/x1,t2/x2 tn/xn作用于谓词公式E就

22、是将E中变量xi均以ti代替，其结果用E表示/作用于项的含义相同,第4章 消解法,41,关于置换,例：=a/x,f(b)/y,u/zE=P(x,y,z)t=g(x,y)E=P(a,f(b),u)t=g(a,f(b)定义置换乘积(合成)：设和是2个置换，则先后作用于公式或项，称为置换乘积，用表示(E)一般来说，置换乘积的结合律成立，即()=()，但交换律不成立,第4章 消解法,42,合一置换,定义合一置换：设有一组谓词公式E1Ek和置换，使E1=E2=Ek，则称为合一置换，E1Ek称为可合一的。合一置换也叫通代定义最一般合一置换(最广通代)：如果 和都是公式组E1Ek的合一置换，且有置换存在，使

23、得=，则称为公式组E1Ek的最一般合一置换，记为mgu(most general unification),第4章 消解法,43,分歧集,在介绍mgu求解算法之前，首先说明什么是分歧集/合一的过程就是消除分歧定义分歧集(不一致集)：设W是一个非空谓词集，从左至右逐个比较W中的符号，如果在第i(i1)个符号处W中各谓词第一次出现分歧(即至少存在Ej和Ek在第i个符号处不一样，而在i之前各谓词符号均一样)，则全体谓词的第i个符号构成了W的分歧集D。分歧集性质：分歧集的出现处一定是谓词或项的开始处/求最广合一置换只考察项的分歧,第4章 消解法,44,mgu求解算法,求mgu算法(合一算法)设W是谓词

24、组，表示空置换(即置换序列为空)，则算法如下：(1)k=0，W0=W，0=；(2)如果Wk中各谓词完全一样，则算法结束，k是W的mgu，否则求Wk的分歧集Dk；(3)若Dk含变量x k以及项t k的首符号且x k在t k中不出现，则继续执行算法，否则W的mgu不存在，算法停止；(4)令k+1=kt k/x k，Wk+1=Wkt k/x k；(5)k=k+1，转(2),第6章 消解法,45,mgu存在条件,mgu存在的条件：如果有限谓词组W是可合一的，则上述算法一定成功结束并给出其存在求mgu的预置条件：应把所有谓词中的变量换成不同名字的变量。(不过，这在将公式化为子句集时已经完成。),第4章

25、消解法,46,mgu求解例子(1),例1：求W=P(a,x,f(g(y),P(z,f(a),f(u)的mgu(1)0=，W0=W，D0=a,z(2)1=0a/z=a/z，W1=W01=P(a,x,f(g(y),P(a,f(a),f(u)，D1=x,f(a)(3)2=1f(a)/x=a/z,f(a)/x，W2=W12=P(a,f(a),f(g(y),P(a,f(a),f(u)，D2=g(y),u(4)3=2g(y)/u=a/z,f(a)/x,g(y)/u，W3=W23=P(a,f(a),f(g(y),P(a,f(a),f(g(y),D3=此时W已合一，mgu=3=a/z,f(a)/x,g(y)/

26、u,第4章 消解法,47,mgu求解例子(2),例2：求W=P(x,x),P(x,f(x)的mgu首先换名：W=P(x,x),P(y,f(y)(1)0=，W0=W，D0=x,y(2)1=x/y，W1=P(x,x),P(x,f(x)，D1=x,f(x)(3)2不存在，因为f(x)中含有变量x。故W的mgu不存在。,第4章 消解法,48,4.3.2 消解式,定义文字合并规则：若子句C含有n(n1)个相同的文字(也称为句节)，则删去其中的n-1个，结果以C表示。定义因子：若子句C中的多个文字具有mgu，则C称为C的一个因子。当C为单文字时称为C的单因子通过取因子可以简化一个子句。这是因为取因子之后，

27、子句C中可能出现相同的文字，而根据文字合并规则就可以删除重复部分,第4章 消解法,49,二元消解式,例子：C=P(x,a)P(b,y)Q(x,y,c)，=b/x,a/y则C=P(b,a)P(b,a)Q(b,a,c)=P(b,a)Q(b,a,c)定义二元消解式：设C1、C2是无公共变量的子句，分别含文字L1、L2，而L1和L2有mgu，则子句R(C1,C2)=(C1L1)(C2L2)称为C1和C2的二元消解式，其中(C1L1)和(C2L2)分别表示从C1、C2删去L1、L2所余部分。L1和 L2称为被消解的文字，C1、C2称为父子句,第4章 消解法,50,二元消解式例子,例子：设C1=P(x)Q

28、(x),C2=P(g(y)Q(b)R(x)，则C1和C2有2个二元消解式(一个消P，一个消Q)如果取=g(y)/x，得R(C1,C2)=Q(g(y)Q(b)R(g(y)如果取=b/x，得R(C1,C2)=P(b)P(g(y)R(b)注意：求消解式不能同时消去2个互补对文字，如同时消去P和P、Q和Q，那样所得结果就不是C1,C2的逻辑结果了,第4章 消解法,51,子句的二元消解式,子句的二元消解式：以下4种二元消解式都是子句C1和C2的二元消解式：(1)C1和C2的二元消解式；(2)C1的一个因子(即经过取因子处理)和C2的二元消解式；(3)C1和C2的一个因子的二元消解式；(4)C1的一个因子

29、和C2的一个因子的二元消解式,第4章 消解法,52,4.3.3 消解法的实施,消解法的实施：为证AB，则建立G=AB(AB)，再求出G对应的子句集S，进而只需证明S是不可满足的为证S的不可满足，只要对S中可以消解的子句求消解式，并将消解式(新子句)加入S中，反复进行这样的消解过程直到产生一个空子句,第4章 消解法,53,子句的推导,子句的推导定义：给定子句集S，如果存在一个有限的子句序列C1,C2,Ck，使得每个Ci或者属于S，或者是C1Ci-1的某些子句的消解式，且Ck=C，则从S可以推导出子句C，称此子句序列为C的推导。当C为空子句时，也称该序列为S的一个否证。,第4章 消解法,54,消解

30、法的合理性,合理性定理若从子句集S可以推导出子句C，则C是S的逻辑推论(或S逻辑蕴含C)。推论若S是可满足的，则S推导出的任一子句也是可满足的，即不能推出空子句。其逆否形式：若S推导出空子句，则S是不可满足的。此为消解原理的合理性定理。即只要找出一个推出空子句的过程，则S就不可满足,第4章 消解法,55,消解法的完备性(1),完备性定理子句集S是不可满足的，当且仅当从S可推导出空子句为了说明完备性定理的证明过程，需要说明消解过程与语义树倒塌之间的联系：从S的语义树T出发，必有两个否节点所对应的子句可作归结，将归结式放入S，则否节点的位置提升，即原来两个否节点的父节点成为否节点。从而使新否节点下

31、面的语义树分支无必要存在，即引起语义树的倒塌,第4章 消解法,56,消解法的完备性(2),重复上述语义树的倒塌过程，直到语义树仅由树根组成为止。此时树根是否节点，则I(N0)=，即已归结为空子句。举例如下：S=P,PQ,PQ,第4章 消解法,57,提升引理,归结过程与语义树的倒塌过程是一致的进一步推广：由基例间(语义树对应的形式)可作归结，到实现子句间可作归结：即常量子句到变量子句的归结/于是得到提升引理提升引理若C1和C2分别是子句C1和C2的例子句，C是C1和C2的归结式，则存在C1和C2的一个归结式C，使得C是C的例子句,第4章 消解法,58,消解法完备性定理(1),简述完备性定理的证明

32、过程：(1)必要性：存在S到的归结过程，是S的逻辑推论，由合理性定理知S是不可满足的(2)充分性：S不可满足，由Herbrand定理知存在有限封闭语义树，必有二叉树中2个兄弟节点均为否节点，即使某2个S的基例为假该2个基例必可作归结(有互补原子)，则归结式使其父节点成为否节点(使归结式为假),第4章 消解法,59,消解法完备性定理(2),将归结式并入S，则该父节点是并集的否节点，因此引起语义树的倒塌重复上述过程至语义树倒塌为只剩根节点且为否节点，说明SR,.有限集必包含。即存在S到的基例归结过程由提升引理知必存在S到的子句归结过程关于消解法完备性的一个证明(Robinson)见教材p23023

33、1,第4章 消解法,60,4.4 消解策略4.4.1 常用消解策略4.4.2 支持集消解4.4.3 有序消解策略4.4.4 消解法举例,第4章 消解法,61,消解过程的计算复杂性,定理证明的过程就是在子句集S中不断求消解式，直到生成一个空子句。现在涉及到求消解式的计算复杂性问题。通常不考虑任何消解策略的盲目消解具有指数级的计算量：对于有n个子句的子句集，如果进行i次求消解式后得到空子句，则计算复杂性是O(n2i)所以要研究加快消解速度、提高效率的各种消解策略,第4章 消解法,62,4.4.1 常用消解策略,本节介绍相关的消解策略，主要内容包括：删除无用的子句永真式和隐含子句求隐含关系归类算法禁止无用子句产生限制参加消解的子句/限制被消解的文字/限制消解方式第1种策略：支持集策略和动态支持集策略常用动态支持集策略线性消解/输入消解/单元消解第2种策略有序消解消解法例子,第4章 消解法,63,