我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:2019跑狗图高清彩图 > 语义树 >

人工智能原理消解法

归档日期:08-07       文本归类:语义树      文章编辑:爱尚语录

  人工智能原理消解法_高三语文_语文_高中教育_教育专区。人工智能原理消解法

  人工智能原理 第4章 消解法 第4章 消解法 本章内容 4.1 消解法的基本思想 4.2 Herbrand定理 4.3 消解法 4.4 消解策略 参考书目 第4章 消解法 4.1 消解法的基本思想 第4章 消解法 消解法的基本思想 ? 从第3章逻辑系统中可知,逻辑推理必须 考虑其有效性 ( 即 ∑=A) ,即对论域中的 任何赋值都能保证公式为真 ? 由可靠性定理知:逻辑系统中任何正确 的推理,都要具有“如果 ∑—A 则 ∑=A” 的性质,即证明推理的有效性 ? 从有效性和可满足性的关系可知,有效 性等价于其否命题的不可满足性 4 第4章 消解法 消解法基本思想:反证法 ? 这样就引出了消解法,其基本思想就是 反证法 ? 即:要证命题 (理解为经典逻辑的公式 )A 恒为真,等价于证﹁A恒为假 ? 从语义上解释,恒为假就是不存在一个 论域上的一个赋值 (可称为解释 ),使﹁A 为真,即对所有的论域上的所有赋值, ﹁A均为假 ? 但是,论域本身和解释有无穷多个,不 可能一一验证 5 第4章 消解法 基本思想(1) ? Herbrand提出:从所有解释当中选出一种 有代表性的解释,并严格证明一旦命题 在代表性解释中为假,则在所有解释中 为假 ? Herbrand定义了这样的论域和代表性解释, 称为Herbrand论域(H论域)和Herbrand解 释(H解释) ? 有定理—公式A(无?前束范式)是不可满 足的,当且仅当A在所有Herbrand赋值下 都取假值 6 第4章 消解法 基本思想(2) ? 这样,在证假(不可满足)的意义上使公 式与子句集的语义解释等价、并与H解释 等价,作为消解法的开端 ? 但如何找到H解释?引入语义树,让所有 解释都展现在语义树上 ? 最后在改进寻找解释算法的复杂性中发 现了消解式,从而构成了消解法的完整 理论基础 ? 消解也叫归结,本章混用这两个称呼 7 第4章 消解法 4.2 Herbrand定理 4.2.1 公式到子句集的转换 4.2.2 Herbrand论域和解释 4.2.3 语义树 4.2.4 Herbrand定理 4.2.5 不可满足基子句集 第4章 消解法 证明的步骤 ? 证明一个公式A在给定论域下恒为真,也 就是要证明﹁A恒为假 ? 将﹁A转化为一个子句集,集合中元素为原 子公式或其析取 / 通过其中正负原子公式的 合并 ( 此时恒为真,对证假不起作用,因此 消去) / 最后集合为空,说明是不可满足的, 即恒为假 ? 通常形式:证明﹁(A→B) 为假即 A∧﹁B 为 假,也即对应子句集归结为空子句 ? 首先介绍基本术语复习和公式到子句集 的转换 9 第4章 消解法 4.2.1 公式到子句集的转换 ? 首先复习几个定义: ? 文字(literal):正原子公式和负原子公式称为 文字,同一原子公式的正和负称为互补的。 ? 子句(clause):文字的析取称为子句。 ? 合取范式:形如A1∧A2∧…∧An的公式,其 中A1~An均为子句。 ? 前束范式:形如 (Q1x1…Qn xn)M(x1…xn)的公 式,M中不再含有量词。 ? Skolem标准形:在前束范式中消去存在量词 后得到的公式 10 第4章 消解法 消去存在量词 ? 消去存在量词的步骤: (1) 若存在量词不在任何全称量词之后,则公式 中被存在量词量化的变量以某个不同于公式 中任何其他常量名字的常量 c代替,并消去存 在量词; (2)若存在量词在k个全称量词之后,则公式中被 存在量词量化的变量用被前 k个全称量词量化 的变量 x1~ xk 的某个函数 f(x1 ~ xk) 的形式代替, f的名字不同于公式中任何其他函数的名字, 但对函数形式没有要求;然后消去存在量词 / 函数f称为Skolem函数 11 第4章 消解法 公式转化为子句集的步骤(1) ? 公式 A 化为子句集 S ,其实现步骤共 9 步, 如下: (1)消去等价和蕴含符号:蕴含转化为析取 (2)将否定符号转移到每个谓词之前:应用 狄摩根定律 (3)变量标准化:约束变量各不相同 (4)消去存在量词:存在量词不受全称量词 约束,则变量用常量替换/如果存在量词 受全称量词约束,则使用Skolem函数替 换相应变量——得到Skolem标准形 12 第4章 消解法 公式转化为子句集的步骤(2) (5) 公式化为前束型:全部全称量词移到公 式的最前面 / 得到的两部分称为前缀和母 式 (6) 母式化为合取范式:外层连接符全部是 合取,里层连接符全部为析取 (7)去掉所有全称量词 (8) 母式化为子句集:每个合取项间的合取 符号(∧)用逗号代替,即得子句集 (9)子句变量标准化:每个子句中的变量各 不相同 13 第4章 消解法 公式与子句集的等价 ? 实现消解法的基础是把参与推理的每个公式 都转化为子句集 / 通过逐步对消子句集合中 互补的文字(即L和﹁L)而最终得到一个空子 句□,证明原来的公式是不可满足的 ? 反证法定理:给定公式 A 及相应的子句集 S , 则A是不可满足的当且仅当S是不可满足的 ? 使用子句集进行消解法推理,其过程是完备 的—即如果公式X是子句集S的逻辑推论, 则X可以从S中推出 14 第4章 消解法 4.2.2 Herbrand论域和解释 ? Herbrand论域定义 ? Herbrand 论域 (H 论域 ) : 设 S 为子句集, H0 是 S 中 子句所含的全体常量集,若S中子句不含常量,则任 选一常量a令H0={a}。 对i≥1令Hi=Hi-1∪{f(t1,…tn) n≥1 f 是S中的任一函数符号,t1,…tn是Hi-1中的元素 H? ? ? Hi i ?0 则Hi 称为S的i阶常量集,H∞称为S的Herbrand论域, 其元素称为基项。 15 第4章 消解法 H论域例子 例1:S={P(a), ﹁P(a)∨P(f(x))} 根据定义有 H0={a} / H1={a}∪{f(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, b}∪{f(c), g(d)c, d? H∞} ★ 16 第4章 消解法 Herbrand原子集 ? Herbrand原子集定义 ? Herbrand 基 (原子集 ):设 S为子句集, H∞是其 H论域,则 H ? {P(t1?tn) n ? 1, ti ? 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))…} ★ 17 第4章 消解法 Herbrand解释(1) ? Herbrand解释是一种语义结构 ? Herbrand解释:子句集S的H解释由下列基本 部分组成: (1)基本区域H∞(H论域对应U) (2)S的每个常量c对应H域中的同一c (3)S的每个变量在H域中取值 (4)S中每个函数fn对应于一个映射 H∞×H∞×…×H∞(n个)→H∞,使得对于 (t1,t2,…tn) ?H∞则f(t1,t2,…tn)?H∞ 18 第4章 消解法 Herbrand解释(2) ? 该定义表明,一旦给定一个子句集,其 H 解释基本就确定了 / 唯一留下的自由度是 由谓词 P 代表的映射即 ~H 到 {T, F} 的映射。 ? ~H可以分解如下:~H=~H1∪~H2 ?h?~H1,v(h)=T;?h?~H2,v(h)=F 这样,一旦给出~H1或~H2,则H解释就完全确 定了,通常是给出~H1 (5)S中的每个谓词Pn对应于一个映射 H∞×H∞×…×H∞(n个)→{T, F} 19 第4章 消解法 H解释例子 ? 例子: ? 在例2中设含有常量a的谓词都为T,含有常 量b的谓词都为F,则S的H解释={P(a), Q(a), R(a), P(f(a)), Q(f(a)), R(f(a)), P(f(f(a))…}★ ? 显然,如果子句集 S 的 H 基 ( 原子集 ) 有 n 个元素 ( 谓词 ) ,则谓词取不同线.2.3 语义树 ? 语义树的表示:要寻找S的H解释的不可满 足性质,可以把所有H解释展现在一棵语义 树上,然后观察S对应的各个原子公式的真 假值。这是一种很直观的研究方式,称为语 义树方法 ? 设S={P, Q, R},则H∞={a},~H={P(a), Q(a), R(a)} (只有一个常量a,在语义树中可省略) ? 因为是二值逻辑,研究每个基原子(即S的原 子公式)的取值可以通过原子及其否定(即文 字)来观察 / 构造如下二叉形式的语义树 21 第4章 消解法 语义树示例 ? 通常用 I(Ni) 表示从根节点到节点 Ni 分枝上所标 记的所有文字的并集。如: I(N22)={P, ?Q},I(N35)={?P, Q, R} ?N0 P N11 ? ? N12 Q ?Q Q ?Q N21 ? N22 ? N23 ? ? N24 R ?R ? ? ? ? ? ? ? ? N31 N32 N33 N34 N35 N36 N37 N38 ?P 22 第4章 消解法 语义树定义(1) ? 子句集S语义树的定义 ? [定义 ]设子句集 S,对应H基为~H,S的语义树 ST 定义如下: (1)ST是一棵树; (2)ST的节点均不带标记,而边的标记是基原子且不 包含其中的变量(边的标记可能不止一个,用逗号 分割); (3) 从每个非叶节点只生成有限个边 L1?Ln ,令 Qi 是 每个Li的标记的合取,则Q1?Q2?…?Qn为永线)从根节点到任一叶子节点的路径上,所有边的标 记的并集中不含重复的基原子,也不含互补的基 原子 23 第4章 消解法 语义树定义(2) ? [定义]规范语义树:如果一棵语义树的 每条边的标记均为一个原子公式 ? [定义]完备语义树:如果一棵语义树从 根节点到任一叶节点的路径上所有边标 记的并集中包含子句集中每个原子或其 负原子,则该语义树称为完备的(完全的) 24 第4章 消解法 语义树定义(3) ? 对于给定的S,其语义树一般都不唯一。 下图中语义树和前图中的语义树对应于 同一个 H 基。这两个图的语义树都是完 备的 P,R ? Q ? ?Q ? Q,R ? ?P ? ?R ? P ? Q ? ?Q ? ?P ? Q ? ?R ? ? R ?R Q ?Q ? ? ? ? ? ?Q ?Q ? 25 第4章 消解法 语义树定义(4) ? 因为一般H基是个无穷集合,所以其对应 的语义树也是无限的 ? 因为在完备语义树的每一条路径上都有S 的全部原子(或负原子),所以对这些原子 公式的真值判定就能决定S的一个解释 ? 对于有限完备语义树来说,如果N是一个 叶节点,则I(N)便是S的一个解释 / 这样, S的不可满足性就与完备语义树路径的线章 消解法 语义树定义(5) [定义]基例:如果S的某个子句C中所有变量符 号均以S的H域的元素(常量)代入时,所得的 子句C’称为C的一个基例 [定义]否节点:如果语义树节点N的从根节点 到N的路径I(N)使S的某个子句的某个基例为 假,而其父辈节点不能判断此事实(即I(N) 是使基例为假的最小路径),则称N为否节 点(或失败节点) [定义]封闭语义树:如果一棵完全语义树的每 个分枝上都有一个否节点,则称为封闭语义 27 树 第4章 消解法 封闭语义树例子(1) ? 例:设子句集S={﹁P(x)∨Q(x),P(f(x)), ﹁Q(f(x))} 则H∞={a, f(a), f(f(a)), …}={P(a), Q(a), P(f(a)), Q(f(a)), …} ? 包括3个子句: ﹁P(x)∨Q(x), P(f(x), ﹁ Q(f(x)) ? 其封闭语义树如下图所示 28 第4章 消解法 封闭语义树例子(2) ● N0 P(a) ﹁P(a) ● N1/1 ● N1/2 Q(a) ﹁Q(a) Q(a) ﹁Q(a) ●N2/1 ★N2/2 ● N2/3 ● N2/4 P(f(a)) P(f(a)) ●N3/1 ★N3/2 ● N3/5 ★N3/6● N3/7 ★ N3/8 Q(f(a)) Q(f(a)) ★ ★ ★ ★ ★ ★ N4/1 N4/2 N4/9 N4/10 N4/13 N4/14 29 第4章 消解法 封闭语义树例子(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的某个子句 为假,因此再扩充路径仍然只能使同一子句为 假,所以没有扩充、延伸的必要 □ 30 第4章 消解法 有限封闭语义树 ? 上例说明,从不可满足的角度来说,对于 无限完备语义树只需搜索到一个否节点, 则该分枝即被证明为不可满足。这样实际 上构成的是一个有限树 ? 所以就有 Herbrand 定理:子句集 S 不可满 足,当且仅当它所对应的每棵完备语义树 均包含一个有限的封闭子树(封闭语义树) 31 第4章 消解法 4.2.4 Herbrand定理 ? Herbrand定理有两种形式 ? Herbrand定理I:子句集S不可满足,当且 仅当它所对应的每棵完备语义树均包含 一个有限的封闭子树(封闭语义树) ? 证明: ? [充分性]设S是不可满足的,T是S的一株完备 语义树。设B是T的任意一个分支路径,则IB是 对应该分支上S的一个解释 由S的不可满足性知IB使S的某子句的某个基例 为假。则B上有节点N且N是T的否节点 32 第4章 消解法 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是不可满足的 ★ 33 第4章 消解法 Herbrand定理II(1) ? Herbrand定理II:S是不可满足的,当且 仅当存在S的一个不可满足的有限基例集 ? 证明: ? [充分性]设S是不可满足的,及T是S的一个 完备语义树。由Herbrand定理I知存在T的有 限封闭子树T’。T’存在有限路径和末端否节 点,即使S的某个子句的某基例为假。 将基例加起来,即得一 个不可满足的有限 基例集 34 第6章 消解法 Herbrand定理II(2) ? [必要性]设S’?S且不可满足的有限基例集。 设I是S的任一解释,应有S’的解释I’?I,已 知I’使S’的某个基例为假,于是I使其为假, 即使S为假,故S不可满足 ★ ? 如同语义树的结构不唯一,不可满足 的有限基子句集也不唯一 ? 从自动证明的角度,定理II是基础 35 第4章 消解法 4.2.5 不可满足基子句集 ? 不可满足基子句集的生成:可通过逐 步测试基子句集中各有限子集的方法 来找出,此为Gilmore算法(算法略,参 见陆著) / 当S不可满足时,该算法一定 结束(半可判定) ? 但该算法具有指数复杂性,为此提出 了改进规则,改进的规则称为DavisPutnam预处理 36 第4章 消解法 Davis-Putnam预处理(1) ? Davis-Putnam预处理: (1) 重言式 ( 永真式 ) 删除规则:删去所有重言式子 句,因为与不可满足性无关; (2)单文字(单句节)删除规则:如果S中包含一个单 文字子句 L( 即只有一个原子公式 ) ,则从 S 中删 去所有含 L 的子句,从 S 中删去所有子句中的 ﹁L文字。经过如此处理的子句集为 S’,若S’为 空,则 S 是可满足的,若 S’ 非空,则 S’ 与 S 同是 不可满足的; (3)纯文字删除规则:如果S中只包含文字L而不包 含﹁L,则删去所有包含L的子句; 37 第4章 消解法 Davis-Putnam预处理(2) (4)分离规则(分裂规则):如果 S=(L∨A1)∧…∧(L∨Am)∧(﹁L∨B1)∧…∧ (﹁L∨Bn)∧R 其中Ai、Bj、R皆不包含L或﹁L, 则令 S1= A1∧…∧Am∧R S2= B1∧…∧Bn∧R S是不可满足的等价于S1∨S2是不可满足的(即S1、 S2同时不可满足)。经过Davis-Putnam预处理以后 的子句集与原子句集在不可满足性上等价 38 第4章 消解法 4.3 消解法 4.3.1 置换与合一 4.3.2 消解式 4.3.3 消解法的实施 第4章 消解法 消解法的形式 ? 进一步推广Davis-Putnam规则,就得到了 消解法。例如设 ?P S ?? ??P ? Q ? 此时只要使用单文字删除规则就可以推 出结论Q。但是如果子句中包含变量,则 常常必须经过变量置换才能进行消解 ? 本节的内容:置换与合一 / 合一算法 / 子 句化简与消解式 / 消解法实施 / 消解法合 理性和完备性 40 第4章 消解法 4.3.1 置换与合一 ? [定义]置换(或代换):设x1~xn是n个变 量,且各不相同,t1~tn是n个项(常量、 变量、函数),ti≠xi,则有限序列{t1/x1, t2/x2 …tn/xn}称为一个置换 ? 置换可以作用于谓词公式,也可以作 用于项。置换θ={t1/x1, t2/x2 …tn/xn}作 用于谓词公式E就是将E中变量xi均以ti 代替,其结果用E?表示 / 作用于项的 含义相同 41 第4章 消解法 关于置换 ? 例:?={a/x, f(b)/y, u/z} E=P(x, y, z) E?=P(a, f(b), u) t=g(x, y) t?=g(a, f(b)) ? ? [ 定义 ] 置换乘积 ( 合成 ) :设 ? 和 ? 是 2 个 置换,则先 ? 后 ? 作用于公式或项,称 为置换乘积,用???表示(E???) ? 一般来说,置换乘积的结合律成立, 即(???)??=??(???),但交换律不成立 42 第4章 消解法 合一置换 ? [定义]合一置换:设有一组谓词公式{E1~ Ek}和置换?,使E1?=E2?=…=Ek?,则?称为 合一置换,E1~Ek称为可合一的。合一置换 也叫通代 ? [定义]最一般合一置换(最广通代):如果? 和?都是公式组{E1~Ek}的合一置换,且有 置换?存在,使得?=???,则?称为公式组 {E1~Ek}的最一般合一置换,记为mgu (most general unification) 43 第4章 消解法 分歧集 ? 在介绍mgu求解算法之前,首先说明什么是 分歧集 / 合一的过程就是消除分歧 ? [定义]分歧集(不一致集):设W是一个非空谓 词集,从左至右逐个比较W中的符号,如果在 第i(i?1)个符号处W中各谓词第一次出现分歧 (即至少存在Ej和Ek在第i个符号处不一样,而在 i之前各谓词符号均一样),则全体谓词的第i个 符号构成了W的分歧集D。 ? 分歧集性质:分歧集的出现处一定是谓词或 项的开始处 / 求最广合一置换只考察项的分 歧 44 第6章 消解法 mgu求解算法 ? 求mgu算法(合一算法) ? 设W是谓词组,? 表示空置换(即置换序列为空),则 算法如下: (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=?k?{t k/x k},Wk+1= Wk{t k/x k}; (5)k=k+1,转(2) 45 第4章 消解法 mgu存在条件 ? mgu存在的条件:如果有限谓词组W是 可合一的,则上述算法一定成功结束 并给出其存在 ? 求mgu的预置条件:应把所有谓词中的 变量换成不同名字的变量。 (不过,这 在将公式化为子句集时已经完成。) 46 第4章 消解法 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=?0?{a/z}={a/z},W1= W0?1={P(a, x, f(g(y))), P(a, f(a), f(u))},D1={x, f(a)} (3)?2=?1?{f(a)/x}={a/z, f(a)/x},W2= W1?2= {P(a, f(a), f(g(y))), P(a, f(a), f(u))},D2={g(y), u} (4)?3=?2?{g(y)/u}={a/z, f(a)/x, g(y)/u} , W3= W2?3= {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)/u} ★ 47 第4章 消解法 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不存在。★ 48 第4章 消解法 4.3.2 消解式 ? [ 定义 ] 文字合并规则:若子句 C 含有 n(n1) 个相同的文字(也称为句节),则删去其中的 n-1个,结果以[C]表示。 ? [ 定义 ] 因子:若子句 C 中的多个文字具有 mgu ,则 [C?] 称为 C 的一个因子。当 [C?] 为 单文字时称为C的单因子 ? 通过取因子可以简化一个子句。这是因为取 因子之后,子句C中可能出现相同的文字, 而根据文字合并规则就可以删除重复部分 49 第4章 消解法 二元消解式 ? 例子: 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)=[(C1??L1?)∨(C2??L2?)] 称为C1和C2的二元消解式,其中(C1??L1?)和 (C2??L2?)分别表示从C1?、C2?删去L1?、L2?所 余部分。L1和 L2称为被消解的文字,C1、C2称 为父子句 50 第4章 消解法 二元消解式例子 ? 例子: 设C1=P(x)∨Q(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的逻辑结果了 51 第4章 消解法 子句的二元消解式 ? 子句的二元消解式:以下4种二元消解 式都是子句C1和C2的二元消解式: (1)C1和C2的二元消解式; (2)C1的一个因子(即经过取因子处理)和C2的 二元消解式; (3)C1和C2的一个因子的二元消解式; (4)C1 的一个因子和 C2 的一个因子的二元消 解式 52 第4章 消解法 4.3.3 消解法的实施 ? 消解法的实施:为证 ├A→B ,则建立 G=A∧﹁B(﹁(A→B)) ,再求出 G 对应 的子句集 S ,进而只需证明 S 是不可满 足的 ? 为证 S 的不可满足,只要对 S 中可以消 解的子句求消解式,并将消解式 (新子 句 ) 加入 S 中,反复进行这样的消解过 程直到产生一个空子句□ 53 第4章 消解法 子句的推导 ? 子句的推导定义: ? 给定子句集S,如果存在一个有限的子句 序列 C1,C2,…,Ck ,使得每个 Ci 或者属于 S , 或者是C1?Ci-1的某些子句的消解式,且C k=C,则从S可以推导出子句C,称此子句 序列为 C的推导。当C为空子句□时,也 称该序列为S的一个否证。 54 第4章 消解法 消解法的合理性 ? [合理性定理]若从子句集S可以推导出子句C, 则C是S的逻辑推论(或S逻辑蕴含C)。 ? [推论]若S是可满足的,则S推导出的任一子 句也是可满足的,即不能推出空子句。 ? 其逆否形式:若S推导出空子句□,则S是 不可满足的。 ? 此为消解原理的合理性定理。即只要找出一 个推出空子句的过程,则S就不可满足 55 第4章 消解法 消解法的完备性(1) ? [完备性定理]子句集S是不可满足的,当 且仅当从S可推导出空子句□ ? 为了说明完备性定理的证明过程,需要 说明消解过程与语义树倒塌之间的联 系: ? 从S的语义树T出发,必有两个否节点所对应 的子句可作归结,将归结式放入S,则否节 点的位置提升,即原来两个否节点的父节点 成为否节点。从而使新否节点下面的语义树 分支无必要存在,即引起语义树的倒塌 56 第4章 消解法 消解法的完备性(2) ? 重复上述语义树的倒塌过程,直到语义树仅由 树根组成为止。此时树根是否节点,则I(N0)= ?,即已归结为空子句□。 ? 举例如下:S={P, ? P∨Q, ? P∨? Q} T P Q N21 N11 ? Q N22 N23 N0 ? P N12 Q N24 N21 T* N0 P N11 ? Q N22 57 T*1 ? P N12 N0 N11 N12 第4章 消解法 提升引理 ? 归结过程与语义树的倒塌过程是一致的 ? 进一步推广:由基例间(语义树对应的形 式)可作归结,到实现子句间可作归结: 即常量子句到变量子句的归结 / 于是得到 提升引理 ? [提升引理]若C1’和C2’分别是子句C1和C2的 例子句,C’是C1’和C2’的归结式,则存在C1 和C2的一个归结式C,使得C’是C的例子句 58 第4章 消解法 消解法完备性定理(1) ? 简述完备性定理的证明过程: (1)必要性:存在S到□的归结过程,□是S的逻辑 推论,由合理性定理知S是不可满足的 (2)充分性: S不可满足,由Herbrand定理知存在 有限封闭语义树,必有二叉树中2个兄弟节点均 为否节点,即使某2个S的基例为假 该2个基例必可作归结(有互补原子),则归结式 使其父节点成为否节点(使归结式为假) 59 第4章 消解法 消解法完备性定理(2) ? 将归结式并入S,则该父节点是并集的否 节点,因此引起语义树的倒塌 ? 重复上述过程至语义树倒塌为只剩根节 点且为否节点,说明S∪{R’,...}有限集必 包含□。即存在S到□的基例归结过程 ? 由提升引理知必存在S到□的子句归结过 程 ★ ? 关于消解法完备性的一个证明(Robinson) 见教材p230~231 60 第4章 消解法 4.4 消解策略 4.4.1 常用消解策略 4.4.2 支持集消解 4.4.3 有序消解策略 4.4.4 消解法举例 第4章 消解法 消解过程的计算复杂性 ? 定理证明的过程就是在子句集 S中不断求消 解式,直到生成一个空子句□。现在涉及到 求消解式的计算复杂性问题。通常不考虑任 何消解策略的盲目消解具有指数级的计算量: 对于有n个子句的子句集,如果进行i次求消 解式后得到空子句,则计算复杂性是O(n2i) ? 所以要研究加快消解速度、提高效率的各种 消解策略 62 第4章 消解法 4.4.1 常用消解策略 ? 本节介绍相关的消解策略,主要内容包 括: ? 删除无用的子句—永真式和隐含子句 ? 求隐含关系—归类算法 ? 禁止无用子句产生 —限制参加消解的子句 / 限制被消解的文字 / 限制消解方式 ? 第1种策略:支持集策略和动态支持集策略 ? 常用动态支持集策略—线性消解 / 输入消解 / 单元消解 ? 第2种策略—有序消解 ? 消解法例子 63 第4章 消解法 删除策略 ? 最直观的一种策略就是删除对消解没有任何贡 献的子句,减少进行消解的子句数量,从而提 高效率。这就是删除策略 ? 删除哪些子句?有2类:永线类是重言式(永真式),即包含﹁P∨P形式的 子句,因为它是永远被满足的,对判定不可满 足性没有作用 ? Davis-Putnam 预处理中的重言式删除规则也说明了 这一点。这时,只要判断子句或子句的消解式中是 否包含互补对即可。如果消解式中包含互补对,则 从子句集中删除新生成的消解式及其父子句 64 第4章 消解法 隐含关系 ? 另一类是被子句集中其他子句所隐含的子句 ? 首先定义隐含关系 ? [定义]设C1、C2是2个子句,lit(Ci)表示Ci中 各个文字的集合,如果存在置换?,使 lit(C1)??lit(C2),则称C1隐含C2 (C2被C1隐 含),或称C1把C2归类 ? [定理]如果S中的子句C1隐含C2,则S是不可 满足的当且仅当S ?{C2}是不可满足的 65 第4章 消解法 归类算法(1) ? 为了说明求隐含关系的算法 (也称归类算法), 首先说明求隐含关系也化为消解问题 ? 给定子句 C 、 D , x1?xn 是 D 中所有变量, a1?an 是C、D中均未出现的常量,令?={ a1/x1…an/xn} ? 设D=L1∨…∨Lm,令﹁D?=﹁L1?∧…∧﹁Lm?, 则求隐含关系就成为C?与W={﹁L1?, …﹁Lm?} 消解为空子句的过程 66 第4章 消解法 归类算法(2) ? 归类算法: ? 给定子句 C 、 D ,并令 W={﹁L1?, …﹁Lm?} , 其中?如上述定义 (1)设i=0,U0={C} (2)如果Uk包含□,则C隐含D,算法停止 (3)令Uk+1={R(C1, C2) C1∈Uk, C2∈W} (4)如果Uk+1=Φ,则C不隐含D,算法停止 (5)i=i+1,转(2)。 67 第4章 消解法 归类算法(3) ? 注意: Uk+1=Φ 表明 Uk 和 W 中已不存在可消 解的子句,所以没有R(C1, C2),其中C1∈Uk, C2∈W ? 算法工作前,让D中变量均以常量置换,是 隐含关系定义所要求的:因为根据定义,置 换 ? 只能对 C 实行,当算法进行中又要作消 解,即 D 的部分 (W 中文字 ) 要作消解,则必 然要作置换,所以只能先把D中变量全部置 换为常量后才能阻止消解中对D的置换 68 第4章 消解法 归类算法举例 ? 例子:C=﹁P(x)∨Q(f(x), a) D=﹁P(h(y))∨Q(f(h(y)), a)∨P(z) ? 首先作?={b/y, c/z},则W={P(h(b)),﹁ Q(f(h(b)), a),﹁P(c)}={W1, W2, W3} (1)U0={C}={﹁P(x)∨Q(f(x), a)} (2)U0 不包含□,则 U1={R(C, W)}={Q(f(h(b)), a), ﹁ P(h(b))} ,其中 Q(*) 是 U0 与 W1 的消解式,﹁P(*) 是 U0与W2的消解式,U1不空继续 (3)U2显然包含□,因为Q(f(h(b)), a)∈U1而﹁Q(f(h(b)), a)∈W 可 消 解 为 □ , 同 样 ﹁P(h(b))∈U1 而 P(h(b))∈W可消解为□。★ 69 第4章 消解法 禁止无用子句产生 ? 禁止无用子句的产生:删去重言式和被隐含 子句的策略提示我们,如果不让无用子句产 生,其效率会更高。因为检查哪些子句是无 用的也要花费时间。 ? 禁止无用子句的产生可以通过下述三个方面 来进行: (1)限制参加消解的子句; (2)限制子句中被消解的文字; (3)限制消解的方式。 ? 主要介绍第 1种策略,即对每次参加消解的 子句作出规定 70 第4章 消解法 4.4.2 支持集消解 ? 一般来说,消解法常常用来证明 C1∧C2∧…∧Cn∧﹁C 不 可 满 足 , 此 即 C1∧C2∧…∧Cn→C ? 因为前提子句集合 {Ci} 应该是可满足 的,所以消解不应在各个 Ci 间进行, 而应在Ci和﹁C之间或﹁C内部进行 ? 支持集策略:推广此想法,限定消解 双方不能都取自子句集的某个子集 71 第4章 消解法 支持集消解(2) ? [ 定义 ] 支持集消解:设 S 为子句集, S’ 为其 子集,若S―S’是可满足的,则称S’是S的一 个支持集。如果限定消解双方不能都取自 S ―S’,则此消解称为支持集消解 ? 给定S’之后,若每一步消解都是支持集消解, 则此推导称为支持集推导,其结果为空子句 时称为支持集否证。 ? 注意:这里只要说明 S―S’ 可满足即可,并 未指明S’不可满足,但此时必然指定某种线章 消解法 支持集消解例子 ? [定理]支持集消解是完备的,即S是不可满足的当且 仅当存在一个以S’为支持集的否证,其中S’是S的子 集,S―S’是可满足的。 ? 例1:S={P∨Q,﹁P∨Q, P∨﹁Q, ﹁P∨﹁Q},则 S’ ={﹁P∨﹁Q}是S的支持集(当P、Q取真值时S―S’ 可满足)。其消解过程可由下图说明 ○﹁P∨Q S’ ○﹁P∨﹁Q ○ ﹁P ○ P∨Q ○ Q ○ □ 73 ○ P∨﹁Q S’ ○﹁P∨﹁Q ○﹁Q 第4章 消解法 动态支持集消解 ? 判断S―S’是否可满足,需要花费时间,所以要寻 找更好的策略。支持集消解的进一步改进就得到 了动态支持集消解 ? [定义]动态支持集消解:设S是子句集,S0=S, Sn=Sn-1 ∪{Cn},其中Cn是Sn中两个子句的消解式, 如果有一种根据子句的语法结构划分子句集的统 一方法,使每个Sn都划分为Sn1和Sn2两部分,且在 消解时限定双方不能都取自Sn1 ,则称Sn2是Sn的一 个动态支持集,此消解称为动态支持集消解。同 时亦定义动态支持集推导、动态支持集否证。 74 第4章 消解法 常用动态支持集消解策略 ? 常用的动态支持集消解有下列几种策略: (1)线)单元消解 ? [线性消解定义]在动态支持集消解定义中令 Sn2={Cn },则此策略称为线性消解策略。Cn 称为消解时的中心子句,另一方称为边子句 ? 线章 消解法 线性消解 ? 注意:在现行消解过程中,初始中心句的选取 很重要,不能任意选择。 ? 例2:S={ P∨Q,﹁P∨Q, P∨﹁Q, ﹁P∨﹁Q }, 其线性消解过程可由下图说明。★ S2 ○ P∨Q Q ○ P ○ ﹁Q ○ □ ○ 76 ○ ﹁P∨Q ○ P∨﹁Q ○ ﹁P∨﹁Q ○ Q 第4章 消解法 输入消解 ? [输入消解定义]在动态 支持集消解定义中令Sn2 =S,则此策略称为输入 消解策略。因为每次消 解必须有原子句集S中的 子句参加(即输入子句) 由此得名 ? 例 3 : S={﹁P, P∨﹁Q, Q∨﹁R, R },其消解过 程如图所示。★ ﹁P ○ ﹁Q ○ ﹁R ○ □ ○ S2 ○ P∨﹁Q ○Q∨﹁R ○R 77 第4章 消解法 单元消解 ? [单元消解定义]在动态 支持集消解定义中令Sn n 中所有单子句和 ={S 2 单因子},则此策略称 为单元消解策略(也叫 单项消解) / 这样,每次 参加消解的一方总有一 个是单项 ? 例 4 : S={P∨Q,﹁P∨R, ﹁Q∨R,﹁R} , 其 消 解 过程如图所示。★ S2 ﹁R ○ ﹁Q ○ P ○ R ○ □ ○ ○﹁Q∨R ○ P∨ Q ○﹁P∨R ○﹁R 78 第4章 消解法 输入消解和单元消解的关系 ? 可以证明如下定理:输入消解和单元消解是 等价的,即一个子句集S可以用输入消解来 否证,当且仅当S可以用单元消解来否证。 ? 输入消解和单元消解都不是完备的。但是, 如果把子句集加以限制,就可以使这两种消 解成为完备的。 ? 只含Horn子句的集合称为Horn子句集。 ? [定理]输入消解和单元消解对于Horn子句集 都是完备的 79 第4章 消解法 4.4.3 有序消解策略 ? 有序消解策略:对子句中被消解的文 字加以限制(第2种策略),通常要对子 句中的文字进行排序。这就是有序消 解策略。 ? 有序消解一般和其他消解策略连用, 以提高效率。这里只介绍一种有序谓 词消解和简单语义消解连用的策略 80 第4章 消解法 有关定义(1) ? [两分法消解定义]设S是子句集,S0=S,Sn=Sn-1 {Cn} ,其中 Cn是 Sn中两个子句的消解式,如果 有一种统一划分子句集的方法,使每个 Sn都划 分为Sn1和Sn2两部分,且在消解时限定双方从Sn n 中各出一个父子句,则此消解称为两分 和 S 1 2 法消解。 ? [简单语义消解定义]设HI是子句集S的一个H解 释,Sn(n=0, 1, …)定义如前,Sn1和Sn2分别为HI 解释中取真值和假值的子句集。按此规定划分 的两分法消解称为简单语义消解(因为由HI解 释控制) 81 第4章 消解法 有关定义(2) ? 简单语义消解是不完备的 ? [有序谓词消解定义]把子句集S中出现的谓词 按照名字排成全序(即按字母排序),并规定在 消解时只有父子句中排序最大(即按字母序最 前)的谓词文字被消解,则此策略称为有序谓 词消解。 ? [有序谓词语义消解定义]如果规定每次消解时 必须同时满足有序谓词消解和简单语义消解的 定义,且规定中的子句(HI解释取假值)以排序 最大的谓词进行消解,则此消解称为有序谓词 语义消解 82 第4章 消解法 有序谓词语义消解例子 ? 例5:设S={P, Q,﹁P∨ ﹁Q∨R, M,﹁R∨﹁ M∨﹁P},规定HI解释 为使正原子为线 ={ P, Q,﹁P∨﹁Q ∨R, M }, S02 ={﹁R ∨﹁M∨﹁P } ? 谓词排序为MPQR ? 其消解过程如图所示 S1 ○ M ○ P S2 ○﹁R∨﹁M∨﹁P ○﹁R∨﹁P ○﹁P∨﹁Q∨R ○﹁R ○ P ○ Q ○﹁P∨﹁Q ○﹁Q ○□ 83 第4章 消解法 4.4.4 消解法举例 ? 例 “快乐学生”问题 ? 假设:任何通过计算机考试并获奖的人 都是快乐的,任何肯学习或幸运的人都 可以通过所有考试,张不肯学习但他是 幸运的,任何幸运的人都能获奖。求证: 张是快乐的。 84 第4章 消解法 解:先将问题谓词表示如下: “任何通过计算机考试并获奖的人都是快乐的” (? x)( Pass( x, com puter ) ? Win ( x, prize)) ? Happy ( x)) “任何肯学习或幸运的人都可以通过所有考试” ? (? x)(? y )(Study( x) ) Lucky( x) ? Pass( x, y )) “张不肯学习但他是幸运的” ¬ Stusy( zhang) ? Lucky( zhang) “张不肯学习但他是幸运的” (? x)( Lucky ( x) ? Win ( x, prize)) 结论“张是快乐的”的否定 ( zhang) ¬ Happy 85 第4章 消解法 将上述谓词公式转化为子句集如下: ) ? ¬ Win ( x, prize) ? Happy( x) (1)¬ Pass( x, com puter (2)¬ Study( y ) ? Pass( y, z ) (3)¬ Lucky(u ) ? Pass(u , v) ( zhang) (4)¬ Study (5) Lucky( zhang) (6)¬ Lucky( w) ? Win ( w, prize) ( zhang) (7)¬ Happy (本子句为结论的否定) 按谓词逻辑的归结原理对此子句进行归结, 其归结反演过程如下图所示。 由于归结出 86 了子句,这就证明了张是快乐的。 第4章 消解法 ¬ Pass( x, computer ) ? ¬ Win ( x, prize) ? Happy ( x) Lucky(w) ? Win (w, prize) {w/x} ) ? Happy( w) ? ¬ Lucky(w) ¬ Pass( w, computer ( zhang) ¬ Happy {zhang/w} Lucky( zhang) ) ? ¬ Lucky( zhang) ¬ Pass( zhang, computer ) ¬ Pass( zhang, computer {zhang/u,computer/v} ¬ Lucky( zhang) ¬ Lucky(u) ? Pass(u, v) Lucky( zhang) 用的是什么消解策略? NIL “快乐学生”问题的归结反演树 87 第4章 消解法 参考书目 ? Stuart Russell / Peter Norvig: AIMA 第9章 ? 陆汝钤 编著: 人工智能(下册) 第17章 ? 石纯一、黄昌宁、王家[广钦],人工智能 原理,清华大学出版社,1993年10月第1 版 ? 田盛丰、黄厚宽,人工智能与知识工程, 中国铁道出版社,1999年8月第1版,第5章 88

本文链接:http://furymagazine.com/yuyishu/226.html