我要投搞

标签云

收藏小站

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

当前位置:2019跑狗图高清彩图 > 约束推理 >

子句和子句集ppt

归档日期:07-13       文本归类:约束推理      文章编辑:爱尚语录

  1.本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的反悔问题本站不予受理。

  4.4.2与/或形逆向演绎推理 1. 目标公式的与/或形变换 逆向系统中的目标公式采用与/或形表示,其化简采用与正向系统中对事实表达式处理的对偶形式。 即要用存在量词约束变元的Skolem函数来替换由全称量词约束的相应变元,消去全称量词,再消去存在量词,并进行变元换名,使主析取元之间具有不同的变元名。 例如,有如下目标公式: (?y) (?x)(P(x)→(Q(x)∧?(R(x)∧S(y)))) Skolem化后为 ?P(f(y))∨(Q(f(y), y)∧(?R(f(y))∨?S(y))) 变元换名后为 ?P(f(z))∨(Q(f(y), y)∧(?R(f(y))∨?S(y))) * 4.4.2与/或形逆向演绎推理 2. 目标公式的与/或树表示 目标公式的与/或形也可用与/或树表示出来,其表示方法与正向演绎推理中事实的与或树表示略有不同。它规定: 子表达式之间的析取关系用单一连接符连接,表示称或的关系; 子表达式之间的合取关系则用k线连接符连接,表示为与的关系。 例如,对上述目标公式的与/或形,可用如下的与/或树表示。 * * ?P(f(z))∨Q(f(y), y)∧(?R(f(y))∨?S(y)) ?P(f(z)) Q(f(y), y)∧(?R(f(y))∨?S(y)) Q(f(y), y) ?R(f(y))∨?S(y) ?R(f(y)) ?S(y) 在目标公式的与/或树中,若把叶节点用它们之间的合取及析取关系连接起来,就可得到原目标公式的三个子目标: ?P(f(z)) Q(f(y), y)∧? R(f(y)) Q(f(y), y)∧? S(y) 即:子目标是文字的合取式 4.4.2与/或形逆向演绎推理 3. B规则和已知事实的表示形式 B规则的表示形示形式 W→L 其中,前项W为任一与/或形公式,后项L为一单文字。 当B规则为W→L1∧L2时,则可化件为两条规则W→L1和W→L2进行处理。 已知事实的表示形式 反向演绎系统的事实表达式限制为文字合取形式,如 F1∧F2∧ …∧Fn 其中,每个Fi(i=1,2,…,n)都为单文字,且都可单独起作用,因此可表示为如下集合形式 { F1∧F2∧ …∧Fn } * 4.4.2与/或形逆向演绎推理 5.与/或形逆向演绎推理过程(一) 规则逆向演绎推理过程 从目标公式的与/或树出发,不断用B规则的右部和与/或树的叶节点进行匹配,并将匹配成功的B规则用表有最一般合一匹配弧加入到与或树中,直到产生某个终止在事实节点上的一致解图为止。 一致解图是指在推理过程中所用到的置换应该是一致的。 例: 设有如下事实: f1: DOG(Fido) Fido是一只狗 f 2: ?BARKS(Fido) Fido是不叫的 f 3: WAGS-TAIL(Fido) Fido摇尾巴 f 4: MEOWS(Myrtle) 猫咪的名字叫Myrtle * 4.4.2与/或形逆向演绎推理 5.与/或形逆向演绎推理过程(二) 规则:r1: (WAGS-TAIL(x1)∧DOG(x1)→FRIENDLY(x1) 摇尾巴的狗是温顺的狗 r2: (FRIENDLY(x2)∧?BARKS(x2)→AFRAID(y2, x2) 温顺又不叫的东西是不值得害怕的 r3: DOG(x3)→ANIMAL(x3) 狗为动物 r4: CAT(x4)→ANIMAL(x4) 猫为动物 r5: MEOWS(x5)→CAT(x5) 猫咪是猫 问题:是否存在这样的一只猫和一条狗,使得这只猫不害怕这只狗? 该问题的目标公式为 (?x) (?y) (CAT(x)∧DOG(y)∧?AFRAID(x, y)) 改目标公式经变换后得到 CAT(x)∧DOG(y)∧ ? AFRAID(x, y) 用逆向推理求解该问题的演绎过程如下图所示: * * CAT(x)∧DOG(y)∧?AFRAID(x,y) CAT(x) DOG(y) ?AFRAID(x,y) CAT(x5) MEOWS(x) MEOWS(Myrtle) DOG(Fido) ?AFRAID(y2,x2) ?BARKS(y) ?BARKS(Fido) FRIENDLY(y) FRIENDLY(x1) WAGS-TAIL(y) DOG(y) WAGS-TAIL(Fido) DOG(Fido) 该图有8条匹配弧,每条弧上都有一置换。其中终止在事实节点上的置换为{Myrtle/x}和{Fido/y}。把它们应用到目标公式,就得到该问题的解: CAT({Myrtle}∧DOG(Fido)∧?AFRAID({Myrtle, Fido} {Fido/y} {x5/x} {y2/x , x2/y} r5 r2 r1 {Myrtle/x} {Fido/y} {x1/y} {Fido/y} {Fido/y} * 今日作业 P154: 4.17 要求: 写出归结演绎推理过程(归结图)。 时间: 两周。 提交方式: EMAIL或者课堂当面提交。 4.3.3 归结演绎推理的归结策略 1. 广度优先策略(2/3) * ﹁I(x)∨R(x) I(a) ﹁R(y)∨L(y) ﹁L(a) R(a) ﹁I(x) ∨L(x) ﹁R(a) L(a) L(a) ﹁I(a) ﹁I(a) NIL S S1 S2 4.3.3 归结演绎推理的归结策略 1. 广度优先策略(3/3) 从这个例子可以看出,宽度优先策略归结出了许多无用的子句,既浪费事间,又浪费空间。但是,这种策略由一个有趣的特性,就是当问题有解时保证能找到最短归结路径。 因此,它是一种完备的归结策略。宽度优先对大问题的归结容易产生组合爆炸,但对小问题却仍是一种比较好的归结策略。 * 4.3.3 归结演绎推理的归结策略 2. 支持集策略(1/3) 支持集策略是沃斯(Wos)等人在1965年提出的一种归结策略。它要求每一次参加归结的两个亲本子句中,至少应该有一个是由目标公式的否定所得到的子句或它们的后裔。可以证明支持集策略是完备的,即当子句集为不可满足时,则由支持集策略一定能够归结出一个空子句。也可以把支持集策略看成是在宽度优先策略中引入了某种限制条件,这种限制条件代表一种启发信息,因而有较高的效率 例:设有如下子句集: S={﹁I(x)∨R(x), I(a),﹁ R(y)∨L(y), ﹁L(a) } 其中,﹁I(x)∨R(x)为目标公式的否定。用支持集策略证明S为不可满足。 * 4.3.3 归结演绎推理的归结策略 2. 支持集策略(2/3) * ﹁I(x)∨R(x) I(a) ﹁ R(y)∨L(y) ﹁L(a) R(a) ﹁I(x)∨L(x) L(a) L(a) ﹁I(a) NIL 4.3.3 归结演绎推理的归结策略 2. 支持集策略(3/3) 从上述归结过程可以看出,各级归结式数目要比宽度优先策略生成的少,但在第二级还没有空子句。就是说这种策略限制了子句集元素的剧增,但会增加空子句所在的深度。此外,支持集策略具有逆向推理的含义,由于进行归结的亲本子句中至少有一个与目标子句有关,因此推理过程可以看作是沿目标、子目标的方向前进的。 * 4.3.5 归结演绎推理的归结策略 3. 删除策略(1/3) 主要想法是:归结过程在寻找可归结子句时,子句集中的子句越多,需要付出的代价就会越大。如果在归结时能把子句集中无用的子句删除掉,这就会缩小搜索范围,减少比较次数,从而提高归结效率。 常用的删除方法有以下几种(纯文字、重言式、包孕) 纯文字删除法 如果某文字L在子句集中不存在可与其互补的文字﹁L,则称该文字为纯文字。 在归结过程中,纯文字不可能被消除,用包含纯文字的子句进行归结也不可能得到空子句,因此对包含纯文字的子句进行归结是没有意义的,应该把它从子句集中删除。 对子句集而言,删除包含纯文字的子句,是不影响其不可满足性的。例如,对子句集 S={P∨Q∨R, ﹁Q∨R, Q, ﹁R} 其中P是纯文字,因此可以将子句P∨Q∨R从子句集S中删除。 * 4.3.3 归结演绎推理的归结策略 3. 删除策略(2/3) 重言式删除法 如果一个子句中包含有互补的文字对,则称该子句为重言式。例如 P(x)∨﹁P(x), P(x)∨Q(x)∨﹁P(x) 都是重言式,不管P(x)的真值为真还是为假,P(x)∨﹁P(x)和P(x)∨Q(x)∨﹁P(x)都均为真。 重言式是真值为真的子句。对一个子句集来说,不管是增加还是删除一个真值为真的子句,都不会影响该子句集的不可满足性。因此,可从子句集中删去重言式。 * 4.3.3 归结演绎推理的归结策略 3. 删除策略(3/3) 包孕删除法 设有子句C1和C2,如果存在一个置换σ,使得C1σ?C2,则称C1包孕于C2。例如 P(x) 包孕于 P(y)∨Q(z) σ={y/x} P(x) 包孕于 P(a) σ={a/x} P(x) 包孕于 P(a)∨Q(z) σ={a/x} P(x) ∨Q(a) 包孕于 P(f(a))∨Q(a)∨R(y) σ={f(a)/x} P(x) ∨Q(y) 包孕于 P(a)∨Q(u)∨R(w) σ={a/x, u/y} 对子句集来说,把其中包孕的子句删去后,不会影响该子句集的不可满足性。因此,可从子句集中删除哪些包孕的子句。 * 4.3.3 归结演绎推理的归结策略 4. 单文字子句策略(1/2) 如果一个子句只包含一个文字,则称此子句为单文字子句。单文字子句策略是对支持集策略的进一步改进,它要求每次参加归结的两个亲本子句中至少有一个子句是单文字子句。 例: 设有如下子句集: S={﹁I(x)∨R(x), I(a), ﹁R(y)∨L(y), ﹁L(a) } 用单文字子句策略证明S为不可满足。 采用单文字子句策略,归结式包含的文字数将少于其亲本子句中的文字数,这将有利于向空子句的方向发展,因此会有较高的归结效率。但这种策略是不完备的,即当子句集为不可满足时,用这种策略不一定能归结出空子句。 * 4.3.3 归结演绎推理的归结策略 4. 单文字子句策略(2/2) * ﹁I(x)∨R(x) I(a) ﹁R(y)∨L(y) ﹁L(a) R(a) ﹁R(a) NIL 4.3.3 归结演绎推理的归结策略 5. 祖先过滤策略(1/2) 这种策略与线性输入策略有点相似,但是,放宽了对子句的限制。每次参加归结的两个亲本子句,只要满足以下两个条件中的任意一个就可进行归结: (1) 两个亲本子句中至少有一个是初始子句集中的子句。 (2) 如果两个亲本子句都不是初始子句集中的子句,则一个子句应该是另一个子句的先辈子句。所谓一个子句(例如C1)是另一个子句(例如C2)的先辈子句是指C2是由C1与别的子句归结后得到的归结式。 例:设有如下子句集: S={﹁Q(x)∨﹁P(x), Q(y)∨﹁P(y),﹁Q(w)∨P(w) , Q(a)∨P(a) } 用祖先过滤策略证明S为不可满足 证明:从S出发,按祖先过滤策略归结过程如下图所示。 可以证明祖先过滤策略也是完备的。 上面分别讨论了几种基本的归结策略,但在实际应用中,还可以把几种策略结合起来使用。总之,在选择归结反演策略时,主要应考虑其完备性和效率问题。 * 4.3.3 归结演绎推理的归结策略 5. 祖先过滤策略(2/2) * ﹁Q(x)∨ ﹁P(x) Q(y)∨﹁P(y) ﹁ P(x) ﹁ Q(w)∨P(w) ﹁ Q(w) Q(a)∨P(a) P(a) NIL 4.3.4 用归结反演求取问题的答案 (1/4) 归结原理出了可用于定理证明外,还可用来求取问题答案,其思想与定理证明相似。其一般步骤为: (1) 把问题的已知条件用谓词公式表示出来,并化为相应的子句集; (2) 把问题的目标的否定用谓词公式表示出来,并化为子句集; (3) 对目标否定子句集中的每个子句,构造该子句的重言式(即把该目标否定子句和此目标否定子句的否定之间再进行析取所得到的子句),用这些重言式代替相应的目标否定子句式,并把这些重言式加入到前提子句集中,得到一个新的子句集; (4) 对这个新的子句集,应用归结原理求出其证明树,这时证明树的根子句不为空,称这个证明树为修改的证明树; (5) 用修改证明树的根子句作为回答语句,则答案就在此根子句中。 * 4.3.4 用归结反演求取问题的答案 (2/4) 下面再通过一个例子来说明如何求取问题的答案。 例: 已知:“张和李是同班同学,如果x和y是同班同学,则x的教室也是y的教室,现在张在302教室上课。” 问:“现在李在哪个教室上课?” 解:首先定义谓词: C(x, y) x和y是同班同学; At(x, u) x在u教室上课。 把已知前提用谓词公式表示如下: C(zhang, li) (?x) (?y) (?u) (C(x, y)∧At(x, u)→At(y,u)) At(zhang, 302) 把目标的否定用谓词公式表示如下: ﹁(?v)At(li, v) * 4.3.4 用归结反演求取问题的答案 (3/4) 把上述公式化为子句集: C(zhang, li) ﹁C(x, y)∨﹁At(x, u)∨At(y, u) At(zhang, 302) 把目标的否定化成子句式,并用重言式 ﹁At(li,v) ∨At(li,v) 代替之。 把此重言式加入前提子句集中,得到一个新的子句集,对这个新的子句集,应用归结原理求出其证明树。其求解过程如下图所示。 该证明树的根子句就是所求的答案,即“李明在302教室”。 * 4.3.4 用归结反演求取问题的答案 (4/4) * ﹁At(li,v)∨At(li,v) ﹁C(x, y)∨﹁At(x, u)∨At(y, u) At(li,v)∨﹁ C(x, li)∨﹁At(x, v) C(zhang, li) ﹁ At(zhang,v)∨At(li, v) At(zhang, 302) At(li, 302) {li/y,v/u} {Zhang/x} {302/v} 4.4 与/或形演绎推理 上一节讨论了归结演绎推理,它需要把谓词公式化为子句形,尽管这种转化在逻辑上是等价的,但是原来蕴含在谓词公式中的一些重要信息却会在求取子句形的过程中被丢失。例如,下面的几个蕴含式 ﹁A∧﹁B→C, ﹁A∧﹁C→B, ﹁A→B∨C, ﹁B→A∨C, 都与子句 A∨B∨C 等价。但在A∨B∨C中,是根本得不到原逻辑公式中所蕴含的哪些超逻辑的含义的。况且,在不少情况下人们多希望使用那种接近于问题原始描述的形式来进行求解,而不希望把问题描述化为子句集。 规则是一种比较接近于人们习惯的问题描述方式,按照这种问题描述方式进行求解的系统称为基于规则的系统,或者叫做基于规则的演绎系统。 规则演绎系统的推理可分为正向演绎推理、逆向演绎推理三种形式。 * 4.4.1与/或形正向演绎推理 与/或形正向演绎和前面所讨论过的正向推理相对应。 它是从已知事实出发,正向使用规则,直接进行演绎,直至到达目标为止的一种证明方法。一个直接演绎系统不一定比反演系统更有效,但其演绎过程容易被人们所理解。 * 4.4.1 与/或形演绎推理 1. 事实表达式的与/或形变换(1/2) 在一个基于规则的正向演绎系统中,其前提条件中的事实表达式是作为系统的初始综合数据库来描述的。对事实的化简,只须转换成不含蕴含符号“→”的与/或形表示即可,而不必化成子句集。把事实表达式化为非蕴含形式的与/或形的主要步骤如下: (1) 利用连接词化规律“P→Q?﹁P∨Q”,消去蕴含符号。事实上,在事实表达式中很少有含蕴含符号“→”出现,因为可把蕴含式表示成规则。 (2) 利用狄.摩根定律及量词转换率把“﹁”移到紧靠谓词的位置,直到每个否定符号的辖域最多只含一个谓词为止。 (3) 对所得到的表达式进行前束化。 (4) 对全称量词辖域内的变量进行改名和标准化,对存在量词量化的变量用skolem函数代替,使不同量词约束的变元有不同的名字。 (5) 消去全称量词,而余下的变量都被认为是全程量词量化的变量。 (6) 对变量进行换名,使主合取元具有不同的变量名。 * 4.4.1与/或形演绎推理 1. 事实表达式的与/或形变换(2/2) 例如,有如下表达式 (?x) (?y)(Q(y, x)∧﹁((R(y)∨P(y))∧S(x, y))) 可把它转化为: Q(z, a)∧((﹁R(y)∧﹁P(y))∨﹁S(a, y)) 这就是与/或形表示。 * 4.4.1与/或形演绎推理 2. 事实表达式的与/或树表示(1/3) 事实表达式的与/或形可用一棵与/或树表示出来。例如,对上例所给出的与/或式,可用如下与/或树来表示。 * Q(z, a)∧((﹁R(y)∧﹁P(y))∨﹁S(a, y)) Q(z, a) ((﹁R(y)∧﹁P(y))∨﹁S(a, y)) ﹁R(y)∧﹁P(y) ﹁S(a, y) ﹁R(y) ﹁P(y) 4.4.1与/或形演绎推理 2. 事实表达式的与/或树表示(2/3) 在该图中,每个节点表示该事实表达式的一个子表达式,子表达式之间的与、或关系规定如下: 当某个表达式为k个子表达式的析取时,例如E1∨E2∨…∨Ek,其中的每个子表达式 Ei 均被表示为 E1∨E2∨…∨Ek 的后继节点,并由一个k线连接符将这些后继节点都连接到其父节点,即表示成与的关系。 当某个表达式为k个子表达式的合取时,例如E1∧E2∧…∧Ek,其中的每个子表达式 Ei 均被表示成 E1∧E2∧…∧Ek 的一个单一的后继节点,并由一个单一连接符连接到其父节点,即表示成或的关系。 这样,与/或树的根节点就是整个事实表达式,端节点均为事实表达式中的一个文字。有了与/或树的表示,就可以求出其解树(结束于文字节点上的子树)集。并且可以发现,事实表达式的子句集与解树集之间存在着一一对应关系,即解树集中的每个解树都对应着子句集中的一个子句。其对应方式为:解树集中每个解树的端节点上的文字的析取就是子句集中的一个子句。 例如,上图所示的与/或树有3个解树,分别对应这以下3个子句: Q(z, a) ﹁R(y)∨ ﹁ S(a, y) ﹁P(y)∨ ﹁ S(a, y) * 4.4.1与/或形演绎推理 2. 事实表达式的与/或树表示(3/3) 与/或树的这个性质很重要,它可以把与/或树看作是对子句集的简洁表示。不过,表达式的与/或树表示要比子句集表示的通用性差一些,原因是与/或树中的合取元没有进一步展开,因此不能象在子句形中那样对某些变量进行改名,这就限制了与/或树表示的灵活性。例如,上面的最后一个子句,在子句集中其变量y可全部改名为x,但却无法在与/或树中加以表示,因而失去了通用性,并且可能带来一些困难。 * 4.4.1与/或形演绎推理 3. 规则的与/或形变换(1/2) 在与/或形正向演绎系统中,是以正向方式使用规则(F规则)对综合数据库中的与/或树结构进行变换的。为简化这种演绎过程,通常要求F规则应具有如下形式: L→W 其中,L为单文字,W为与/或形公式。假定出现在蕴含式中的任何变量全都受全称量词的约束,并且这些变量已经被换名,使得他们与事实公式和其他规则中的变量不同。 如果领域知识的规则表示形式与上述要求不同,则应将它转换成要求的形式。其变换步骤如下: * 4.4.1与/或形演绎推理 3. 规则的与/或形变换(2/2) (1) 暂时消去蕴含符号“→”。设有如下公式: (?x)(((?y) (? z)P(x, y,z))→(?u)Q(x, u)) 运用等价关系“P→Q?﹁P∨Q”,可将上式变为: (?x)(﹁((? y) (?z)P(x, y,z))∨(?u)Q(x, u)) (2) 把否定符号“﹁”移到紧靠谓词的位置上,使其作用域仅限于单个谓词。通过使用狄.摩根定律及量词转换率可把上式转换为: (? x)( (?y) (?z)﹁P(x, y,z))∨ (?u)Q(x, u)) (3) 引入Skolem函数,消去存在量词。消去存在量词后,上式可变为: (? x)( (?y) (﹁P(x, y,f(x,y)))∨(?u)Q(x, u)) 化成前束式,消去全部全称量词。消去全称量词后,上式变为: ﹁P(x, y,f(x,y))∨Q(x, u) 此公式中的变元都被视为受全称量词约束的变元。 (5) 恢复蕴含式表示。利用等价关系“﹁P∨Q?P→Q”将上式变为: P(x, y,f(x,y))→Q(x, u) 在上述对F规则的要求中,之所以限制其前件为单文字,是因为在进行正向演绎推理时要用F规则作用于表示事实的与/或树,而该与/或树的叶节点都是单文字,这样就可用F规则的前件与叶节点进行简单匹配。对非单文字情况,若形式为L1∨L2→W,则可将其转换成与之等价的两个规则L1→W与 L2→W进行处理。 * 4.4.1与/或形演绎推理 4. 目标公式的表示形式 与/或树正向演绎系统要求目标公式用子句形表示。如果目标公式不是子句形,则需要化成子句形。把一个目标公式转化为子句形的步骤与第3节所述的化简子句形的步骤类似,但Skolem化的过程不同。目标公式的Skolem化过程是化简子句形的Skolem过程的对偶形式,即把目标公式中属于存在量词辖域内的全称变量用存在量词量化变量的Skolem函数来代替,使经Skolem化目标公式只剩下存在量词,然后再对析取元作变量替换,最后把存在量词消掉。 例如:设目标公式为 (?y) (?x) (P(x, y)∨Q(x, y)) 用Skolem函数消去全称量词后有 (?y)(P(f(y), y)∨Q(f(y), y)) 进行变量换名,使每个析取元具有不同的变量符号,于是有 (?y)P(f(y), y)∨(?z)Q(f(z), z) 最后,消去存在量词得 P(f(y), y)∨Q(f(z), z) 这样,目标公式中的变量都假定受存在量词的约束 * 4.4.1与/或形演绎推理 5. 规则正向演绎系统(1/5) 规则正向演绎推理过程是从已知事实出发,不断运用F规则,推出欲证明目标公式的过程。即先用与/或树把已知事实表示出来,然后再用F规则的前件和与或树的叶节点进行匹配,并通过一个匹配弧把匹配成功的F规则加入到与/或树中,依此使用F规则,直到产生一个含有以目标节点为终止节点的解图为止。 下面分命题逻辑和谓词逻辑两种情况来讨论规则正向演绎过程。 * 4.4.1与/或形演绎推理 5. 规则正向演绎系统(2/5) 命题逻辑的规则演绎过程 由于命题逻辑中的公式不含变元,因此其规则演绎过程比较简单。 例: 设已知事实为:A∨B F规则为: r1: A→C∧D r2: B→E∧G 目标公式为:C∨G 证明:先将已知事实用与/或树表示出来,然后再用匹配弧把r1和r2分别连接到事实与/或树中与r1和r2前件匹配的两个不同端节点,由于出现了以目标节点为终节点的解树,故推理过程结束。这一证明过程可用下图表示。 * 4.4.1与/或形演绎推理 5. 规则正向演绎系统(3/5) 在该图中,双箭头表示匹配弧,它相当于一个单线连接符。 * C G C D E G A B A B A∨B 目标 匹配 匹配 F规则 已知事实 r1 r2 4.4.1与/或形演绎推理 5. 规则正向演绎系统(4/5) 为了验证上述推理的正确性,下面再用归结演绎推理给于证明。由已知事实、规则及目标的否定可得到如下子句集: {A∨B, ﹁A∨C, ﹁A∨D, ﹁B∨E, ﹁B∨G, ﹁C, ﹁G} 其归结过程如下图所示。 可见,用归结演绎推理对已知事实、F规则集目标的否定所过程的子句集进行归结,得到了空子句NIL,从而证明了目标公式。它与正向演绎推理所得到的结果是一致的。 * ﹁A∨C ﹁C ﹁B∨G ﹁G A∨B ﹁A ﹁B B NIL 4.4.1与/或形演绎推理 5. 规则正向演绎系统(5/5) 在谓词逻辑情况下,由于事实、F规则及目标中均含有变元,因此,其规则演绎过程还需要用最一般合一对变进行置换。 例:设已知事实的与/或形表示为:P(x, y)∨(Q(x)∧R(v, y)) F规则为: P(u, v)→(S(u)∨N(v)) 目标公式为:S(a)∨N(b)∨Q(c) 其推理过程如下图所示。 * S(a) N(b) Q(c) S(u) N(v) P(u, v) P(x, y) Q(x) R(v, y) Q(x)∧R(v, y) P(x, y)∨(Q(x)∧R(v, y)) {a/u} {b/v} {c/x} {u/x,v/y} 4.4.2与/或形演绎推理 与/或形逆向演绎推理过程是从目标公式的与/或树出发,反向使用规则(B规则),对目标公式的与/或树进行变换,直到得出含有事实节点一致解图为止。包括: 目标公式的与/或形变换 目标公式的与/或树表示 B规则的表示形式 规则逆向演绎推理过程 * 4.3 归结演绎推理 归结演绎推理是一种基于鲁宾逊(Robinson)归结原理的机器推理技术。鲁宾逊归结原理亦称为消解原理,是鲁宾逊于1965年在海伯伦(Herbrand)理论的基础上提出的一种基于逻辑的“反证法”。 在人工智能中,几乎所有的问题都可以转化为一个定理证明问题。定理证明的实质,就是要对前提P和结论Q,证明P→Q永真。 要证明P→Q永真,就是要证明P→Q在任何一个非空的个体域上都是永真的。这将是非常困难的,甚至是不可实现的。 为此,人们进行了大量的探索,后来发现可以采用反证法的思想,把关于永真性的证明转化为关于不可满足性的证明。 即要证明P→Q永真,只要能够证明P∧﹁Q是不可满足的就可以了(原因是﹁ (P→Q) ? ﹁(﹁ P∨Q) ? P∧﹁ Q 。 这方面最有成效的工作就是鲁宾逊归结原理。它使定理证明的机械化成为现实。 * 4.3.1 子句集及其化简 1. 子句和子句集 鲁滨逊归结原理是在子句集的基础上讨论问题的。因此,讨论归结演绎推理之前,需要先讨论子句集的有关概念。 子句和子句集 定义1 原子谓词公式及其否定统称为文字。 例如,P(x)、Q(x)、﹁ P(x)、 ﹁ Q(x)等都是文字。 定义2 任何文字的析取式称为子句。 例如,P(x)∨Q(x),P(x,f(x))∨Q(x,g(x))都是子句。 定义3 不含任何文字的子句称为空子句。 由于空子句不含有任何文字,也就不能被任何解释所满足,因此空子句是永假的,不可满足的。 空子句一般被记为NIL。 定义4 由子句或空子句所构成的集合称为子句集。 * 4.3.1 子句集及其化简 2. 子句集的化简(1/6) 在谓词逻辑中,任何一个谓词公式都可以通过应用等价关系及推理规则化成相应的子句集。其化简步骤如下: (1) 消去连接词“→”和“?” 反复使用如下等价公式: P→Q ?﹁ P∨Q P?Q ? (P∧Q)∨(﹁P∧﹁Q) 即可消去谓词公式中的连接词“→”和“?”。 例如公式 (?x)((?y)P(x,y)→﹁ (?y)(Q(x,y)→R(x,y))) 经等价变化后为 (?x)(﹁(?y)P(x,y)∨﹁ (?y)(﹁Q(x,y)∨R(x,y))) * 4.3.1 子句集及其化简 2. 子句集的化简(2/6) (2) 减少否定符号的辖域 反复使用双重否定率 ﹁(﹁P) ? P 摩根定律 ﹁(P∧Q) ?﹁P∨﹁Q ﹁(P∨Q) ?﹁P∧﹁Q 量词转换率 ﹁ (?x)P(x) ? (?x) ﹁P(x) ﹁ (?x)P(x) ? (?x)¬P(x) 将每个否定符号“﹁”移到仅靠谓词的位置,使得每个否定符号最多只作用于一个谓词上。 例如,上式经等价变换后为 (?x)((?y)﹁P(x,y)∨(?y)( Q(x,y) ∧﹁R(x,y))) * 4.3.1 子句集及其化简 2. 子句集的化简(3/6) (3) 对变元标准化 在一个量词的辖域内,把谓词公式中受该量词约束的变元全部用另外一个没有出现过的任意变元代替,使不同量词约束的变元有不同的名字。 例如,上式经变换后为 (?x)((?y)﹁P(x,y)∨(?z)( Q(x,z) ∧﹁R(x,z))) (4) 化为前束范式 化为前束范式的方法:把所有量词都移到公式的左边,并且在移动时不能改变其相对顺序。由于第(3)步已对变元进行了标准化,每个量词都有自己的变元,这就消除了任何由变元引起冲突的可能,因此这种移动是可行的。 例如,上式化为前束范式后为 (?x)(?y) (?z)(﹁P(x,y)∨( Q(x,z) ∧﹁R(x,z))) * 4.3.1 子句集及其化简 2. 子句集的化简(4/6) (5) 消去存在量词 消去存在量词时,需要区分以下两种情况: 若存在量词不出现在全称量词的辖域内(即它的左边没有全称量词),只要用一个新的个体常量替换受该存在量词约束的变元,就可消去该存在量词。 若存在量词位于一个或多个全称量词的辖域内,例如 (?x1)…(?xn) (?y)P(x1,x2 ,…, xn ,y) 则需要用Skolem函数f(x1,x2 ,…, xn)替换受该存在量词约束的变元y,然后再消去该存在量词。 例如,上步所得公式中存在量词(?y)和(?z)都位于(?x)的辖域内,因此都需要用Skolem函数来替换。设替换y和z的Skolem函数分别是f(x)和g(x),则替换后的式子为 (?x)(﹁P(x,f(x))∨(Q(x,g(x))∧﹁R(x,g(x)))) * 4.3.1 子句集及其化简 2. 子句集的化简(5/6) (6) 化为Skolem标准形 Skolem标准形的一般形式为 (?x1)…(?xn) M(x1,x2,……,xn) 其中, M(x1,x2,……,xn)是Skolem标准形的母式,它由子句的合取所构成。 把谓词公式化为Skolem标准形需要使用以下等价关系 P∨(Q∧R) ? (P∨Q)∧(P∨R) 例如,前面的公式化为Skolem标准形后为 (?x)((﹁P(x,f(x))∨Q(x,g(x))∧(﹁P(x,f(x))∨﹁R(x,g(x)))) (7) 消去全称量词 由于母式中的全部变元均受全称量词的约束,并且全称量词的次序已无关紧要,因此可以省掉全称量词。但剩下的母式,仍假设其变元是被全称量词量化的。 例如,上式消去全称量词后为 (﹁P(x,f(x))∨Q(x,g(x)) ∧(﹁P(x,f(x))∨﹁R(x,g(x))) * 4.3.1 子句集及其化简 2. 子句集的化简(6/6) (8) 消去合取词 在母式中消去所有合取词,把母式用子句集的形式表示出来。其中,子句集中的每一个元素都是一个子句。 例如,上式的子句集中包含以下两个子句 ﹁P(x,f(x))∨Q(x,g(x)) ﹁P(x,f(x))∨﹁R(x,g(x)) (9) 更换变量名称 对子句集中的某些变量重新命名,使任意两个子句中不出现相同的变量名。由于每一个子句都对应着母式中的一个合取元,并且所有变元都是由全称量词量化的,因此任意两个不同子句的变量之间实际上不存在任何关系。这样,更换变量名是不会影响公式的真值的。 例如,对前面的公式,可把第二个子句集中的变元名x更换为y,得到如下子句集 ﹁P(x,f(x))∨Q(x,g(x)) ﹁P(y,f(y))∨﹁R(y,g(y)) * 4.3.1 子句集及其化简 3. 子句集的应用(1/4) 在上述化简过程中,由于在消去存在量词时所用的Skolem函数可以不同,因此化简后的标准子句集是不唯一的。 这样,当原谓词公式为非永假时,它与其标准子句集并不等价。但当原谓词公式为永假(或不可满足)时,其标准子句集则一定是永假的,即Skolem化并不影响原谓词公式的永假性。 这个结论很重要,是归结原理的主要依据,可用定理的形式来描述。 定理4.1 设有谓词公式F,其标准子句集为S,则F为不可满足的充要条件是S为不可满足的。 要证明一个谓词公式是不可满足的,只要证明其相应的标准子句集是不可满足的就可以了。至于如何证明一个子句集的不可满足性,由下面的海伯伦理论和鲁宾逊归结原理来解决。 * 4.3.2 鲁滨逊归结原理 1. 基本思想 注意以下两个关键 第一,子句集中的子句之间是合取关系。因此,子句集中只要有一个子句为不可满足,则整个子句集就是不可满足的; 第二,空子句是不可满足的。因此,一个子句集中如果包含有空子句,则此子句集就一定是不可满足的。 鲁滨逊归结原理基本思想 首先把欲证明问题的结论否定,并加入子句集,得到一个扩充的子句集S。然后设法检验子句集S是否含有空子句,若含有空子句,则表明S是不可满足的;若不含有空子句,则继续使用归结法,在子句集中选择合适的子句进行归结,直至导出空子句或不能继续归结为止。 鲁滨逊归结原理包括 命题逻辑归结原理 谓词逻辑归结原理 * 4.3.2 鲁滨逊归结原理 2. 命题逻辑的归结(1/8) 归结推理的核心是求两个子句的归结式 (1) 归结式的定义及性质 定义1 若P是原子谓词公式,则称P与﹁P为互补文字。 定义2 设C1和C2是子句集中的任意两个子句,如果C1中的文字L1与C2中的文字L2互补,那么可从C1和C2中分别消去L1和L2,并将C1和C2中余下的部分按析取关系构成一个新的子句C12,则称这一过程为归结,称C12为C1和C2的归结式,称C1和C2为C12的亲本子句。 例4.7 设C1=P∨Q∨R,C2=﹁P∨S,求C1和C2的归结式C12。 解:这里L1=P,L2=﹁P,通过归结可以得到 C12= Q∨R∨S 例4.8 设C1=﹁Q,C2=Q,求C1和C2的归结式C12。 解:这里L1=﹁Q,L2=Q,通过归结可以得到 C12= NIL * 4.3.2 鲁滨逊归结原理 2. 命题逻辑的归结(2/8) 例4.9 设设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 鲁滨逊归结原理 2. 命题逻辑的归结(3/8) 定理4.4 归结式C12是其亲本子句C1和C2的逻辑结论。 证明:(按定义)设C1=L∨C1 ’ ,C2=﹁L∨C2’关于解释I为线’关于解释I也为真。 对于解释I,L和﹁L中必有一个为假。 若L为假,则必有C1为线为假,这将与前提假设C1为线为真。 同理,若﹁L为假,则必有C2为线关于解释I也为线. 命题逻辑的归结(4/8) 上述定理是归结原理中的一个重要定理,由它可得到以下两个推论: 推论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 鲁滨逊归结原理 2. 命题逻辑的归结(5/8) 上述两个推论说明,为证明子句集S的不可满足性,只要对其中可进行归结得子句进行归结,并把归结式加入到子句集S中,或者用归结式代替他的亲本子句,然后对新的子句集证明其不可满足性就可以了。 如果经归结能得到空子句,根据空子句的不可满足性,即可得到原子句集S是不可满足的结论。 在命题逻辑中,对不可满足的子句集S,其归结原理是完备的。 这种不可满足性可用如下定理描述: 不可满足性: 子句集S是不可满足的,当且仅当存在一个从S到空子句的归结过程。 * 4.3.2 鲁滨逊归结原理 2. 命题逻辑的归结(6/8) (2) 命题逻辑的归结反演 归结原理:假设F为已知前提,G为欲证明的结论,归结原理把证明G为F的逻辑结论转化为证明F∧﹁G为不可满足。 再根据定理3.1,在不可满足的意义上,公式集F∧﹁G与其子句集是等价的,即把公式集上的不可满足转化为子句集上的不可满足。 应用归结原理证明定理的过程称为归结反演。 在命题逻辑中,已知F,证明G为真的归结反演过程如下: ①否定目标公式G,得﹁G; ②把﹁G并入到公式集F中,得到{F,﹁G}; ③把{F,﹁G}化为子句集S。 ④ 应用归结原理对子句集S中的子句进行归结,并把每次得到的归结式并入S中。如此反复进行,若出现空子句,则停止归结,此时就证明了G为线) 例 : 设已知的公式集为{P, (P∧Q)→R, (S∨T)→Q, T},求证结论R。 解:假设结论R为假, 将﹁R加入公式集,并化为子句集 S={P,﹁P∨﹁Q∨R, ﹁S∨Q, ﹁T∨Q, T, ﹁R} 其归结过程如右图的归结演绎树所示。该树根为空子句。 其含义为:先假设子句集S中的所有子句均为真,即原公式集为真,﹁R也为真;然后利用归结原理,对子句集进行归结,并把所得的归结式并入子句集中;重复这一过程,最后归结出了空子句。 根据归结原理的完备性,可知子句集S是不可满足的,即开始时假设﹁R为真是错误的,这就证明了R为真。 * ﹁P ∨﹁Q∨R ﹁ R ﹁P ∨﹁Q P ﹁Q ﹁T ∨Q ﹁T T NIL 4.3.2 鲁滨逊归结原理 3. 谓词逻辑的归结(1/16) 在谓词逻辑中,由于子句集中的谓词一般都含有变元,因此不能象命题逻辑那样直接消去互补文字。而需要先用一个最一般合一对变元进行代换,然后才能进行归结。可见,谓词逻辑的归结要比命题逻辑的归结麻烦一些。 谓词逻辑的归结原理 谓词逻辑中的归结式可用如下定义来描述: 定义4.11 设C1和C2是两个没有公共变元的子句,L1和L2分别是C1和C2中的文字。如果L1和L2存在最一般合一σ,则称 C12=({C1σ}-{ L1σ})∪({ C2σ}-{ L2σ}) 为C1和C2的二元归结式,而L1和L2为归结式上的文字。 * 4.3.2 鲁滨逊归结原理 3. 谓词逻辑的归结(2/16) 例: 设C1=P(a)∨R(x),C2=﹁P(y)∨Q(b),求 C12 解:取L1= P(a), L2=﹁P(y),则L1和L2的最一般合一是σ={a/y}。根据定义可得 C12=( {C1σ}-{L1σ}) ∪ ({C2σ}-{L2σ}) =({P(a), R(x)}-{P(a)})∪({﹁P(a), Q(b)}-{﹁P(a)}) =({R(x)})∪({Q(b)})= {R(x), Q(b)} =R(x)∨Q(b) 例: 设C1=P(x)∨Q(a),C2=﹁P(b)∨R(x) ,求 C12 解:由于C1和C2有相同的变元x,不符合定义4.11的要求。为了进行归结,需要修改C2中变元x的名字为,令C2=﹁P(b)∨R(y)。此时L1= P(x), L2 =﹁P(b),L1和L2的最一般合一是σ={b/x}。则有 C12=( {C1σ}-{L1σ})∪ ({C2σ}-{L2σ}) =({P(b), Q(a)}-{P(b)}) ∪ ({﹁P(b), R(y)}-{﹁P(b)}) =({Q(a)}) ∪ ({R(y)})= {Q(a), R(y)} =Q(a)∨R(y) * 4.3.2 鲁滨逊归结原理 3. 谓词逻辑的归结(4/16) 例: 设C1=P(x)∨﹁Q(b),C2=﹁P(a)∨Q(y)∨R(z) 解:对C1和C2通过最一般合一(σ={a/x, b/y})的作用,可以得到两个互补对。 注意:求归结式不能同时消去两个互补对,这样的结果不是二元归结式。如在σ={a/x, b/y}下,若同时消去两个互补对,所得的R(z)不是C1和C2的二元归结式。 例: 设C1=P(x)∨P(f(a))∨Q(x) ,C2=﹁P(y)∨R(b),求C12 解:对参加归结的某个子句,若其内部有可合一的文字,则在进行归结之前应先对这些文字进行合一。本例的C1中有可合一的文字P(x)与P(f(a)),若用它们的最一般合一σ={f(a)/x}进行代换,可得到 C1σ=P(f(a))∨Q(f(a)) 此时可对C1σ与C2进行归结。选L1= P(f(a)), L2 =﹁P(y),L1和L2的最一般合一是σ={f(a)/y},则可得到C1和C2的二元归结式为 C12=R(b)∨Q(f(a)) 我们把C1σ称为C1的因子。一般来说,若子句C中有两个或两个以上的文字具有最一般合一σ,则称Cσ为子句C的因子。如果Cσ是一个单文字,则称它为C的单元因子。 应用因子概念,可对谓词逻辑中的归结原理给出如下定义: * 4.3.2 鲁滨逊归结原理 3. 谓词逻辑的归结(5/16) 定义4.12若C1和C2是无公共变元的子句,则 ① C1和C2的二元归结式; ② C1和C2的因子C2σ2的二元归结式; ③ C1的因子C1σ1和C2的二元归结式; ④ C1的因子C1σ1和C2的因子C2σ2的二元归结式。 这四种二元归结式都是子句C1和C2的二元归结式,记为C12。 例:设C1=P(y)∨P(f(x))∨Q(g(x)) ,C2=﹁P(f(g(a)))∨Q(b),求C12。 解:对C1 ,取最一般合一σ={f(x)/y},得C1的因子 C1σ=P(f(x))∨Q(g(x)) 对C1的因子和C2归结(σ={g(a)/x }),可得到C1和C2的二元归结式 C12=Q(g(g(a)))∨Q(b) * 4.3.2 鲁滨逊归结原理 3. 谓词逻辑的归结(6/16) 谓词逻辑的归结反演 谓词逻辑的归结反演过程与命题逻辑的归结反演过程相比,其步骤基本相同,但每步的处理对象不同。例如,在步骤(3)化简子句集时,谓词逻辑需要把由谓词构成的公式集化为子句集;在步骤(4)按归结原理进行归结时,谓词逻辑的归结原理需要考虑两个亲本子句的最一般合一。 例4.12 已知 F: (?x)((?y)(A(x, y)∧B(y))→(?y)(C(y)∧D(x, y))) G: ﹁(?x)C(x)→(?x)(?y)(A(x, y)→﹁B(y)) 求证G是F的逻辑结论。 证明:先把G否定,并放入F中,得到的{F, ﹁G}为 {(? x)((? y)(A(x,y)∧B(y))→(? y)(C(y)∧D(x,y))), ﹁(﹁(? x)C(x)→(? x)(? y)(A(x,y)→﹁ B(y)))} * 4.3.2 鲁滨逊归结原理 3. 谓词逻辑的归结(7/16) 再把{F,﹁G}化成子句集,得到 (1) ﹁A(x,y)∨﹁ B(y) ∨C(f(x)) (2) ﹁ A(u,v)∨﹁ B(v) ∨D(u,f(u)) (3) ﹁ C(z) (4) A(m,n) (5) B(k) 其中,(1)、(2)是由F 化出的两个子句,(3)、(4)、(5)是由﹁G化出的3个子句。 最后应用谓词逻辑的归结原理对上述子句集进行归结,其过程为 (6) ﹁ A(x,y)∨ ﹁ B(y) 由(1)和(3)归结,取σ={f(x)/z} (7) ﹁ B(n) 由(4)和(6)归结,取σ={m/x,n/y} (8) NIL 由(5)和(7)归结,取σ={n/k} 因此,G是F 的逻辑结论。 上述归结过程可用如下归结树来表示 * 4.3.2 鲁滨逊归结原理 3. 谓词逻辑的归结(8/16) * ﹁A(x,y)∨﹁ B(y)∨C(f(x)) ﹁ C(z) ﹁A(x,y)∨﹁ B(y) A(m,n) ﹁ B(n) B(k) NIL {f(x)/z} {m/x,n/y} {n/k} 4.3.2 鲁滨逊归结原理 3. 谓词逻辑的归结(13/16) 为了进一步加深对谓词逻辑归结的理解,下面再给出一个经典的归结问题 例:“激动人心的生活”问题 假设:所有不贫穷并且聪明的人都是快乐的,那些看书的人是聪明的。李明能看书且不贫穷,快乐的人过着激动人心的生活。 求证:李明过着激动人心的生活。 解:先定义谓词: Poor(x) x是贫穷的 Smart(x) x是聪明的 Happy(x) x是快乐的 Read(x) x能看书 Exciting(x) x过着激动人心的生活 * 4.3.2 鲁滨逊归结原理 3. 谓词逻辑的归结(14/16) 再将问题用谓词表示如下: “所有不贫穷并且聪明的人都是快乐的” (?x)((﹁Poor(x)∧Smart(x))→Happy(x)) “那些看书的人是聪明的” (?y) (Read(y) → Smart(y)) “李明能看书且不贫穷” Read(Liming)∧﹁Poor(Liming) “快乐的人过着激动人心的生活” (?z) (Happy(z)→Exciting(z)) 目标“李明过着激动人心的生活”的否定 ﹁Exciting(Liming) * 4.3.2 鲁滨逊归结原理 3. 谓词逻辑的归结(15/16) 将上述谓词公式转化为子句集如下: (1) Poor(x)∨﹁Smart(x)∨Happy(x) (2) ﹁Read(y)∨Smart(y) (3) Read(Liming) (4) ﹁Poor(Liming) (5) ﹁Happy(z)∨Exciting(z) (6) ﹁Exciting(Liming) (结论的否定) * 4.3.2 鲁滨逊归结原理 3. 谓词逻辑的归结(16/16) * ﹁Exciting(Liming) ﹁Happy(z)∨Exciting(z) ﹁Happy(Liming) Poor(x))∨﹁Smart(x)∨Happy(x) Poor(Liming)∨﹁Smart(Liming) ﹁Read(y)∨Smart(y ) Poor(Liming)∨﹁Read(Liming) ﹁Poor(Liming) ﹁Read(Liming) Read(Liming) NIL {Liming/z} {Liming/x} {Liming/y} 4.3.3 归结演绎推理的归结策略 归结演绎推理实际上就是从子句集中不断寻找可进行归结的子句对,并通过对这些子句对的归结,最终得出一个空子句的过程。由于事先并不知道哪些子句对可进行归结,更不知道通过对哪些子句对的归结能尽快得到空子句,因此就需要对子句集中的所有子句逐对进行比较,直到得出空子句为止。这种盲目的全面进行归结的方法,不仅会产生许多无用的归结式,更严重的是会产生组核爆炸问题。因此,需要研究有效的归结策略来解决这些问题。 目前,常用的归结策略可分为两大类,一类是删除策略,另一类是限制策略。删除策略是通过删除某些无用的子句来缩小归结范围;限制策略是通过对参加归结的子句进行某些限制,来减少归结的盲目性,以尽快得到空子句。为了说明选择归结策略的重要性,在讨论各种常用的归结策略之前,还是先提一下广度优先策略。 * 4.3.3 归结演绎推理的归结策略 1. 广度优先策略(1/3) 广度优先是一种穷尽子句比较的复杂搜索方法。设初始子句集为S0,广度优先策略的归结过程可描述如下: (1) 从S0出发,对S0中的全部子句作所有可能的归结,得到第一层归结式,把这些归结式的集合记为S1; (2) 用S0中的子句与S1中的子句进行所有可能的归结,得到第二层归结式,把这些归结式的集合记为S2; (3) 用S0和S1中的子句与S2中的子句进行所有可能的归结,得到第三层归结式,把这些归结式的集合记为S3; 如此继续,知道得出空子句或不能再继续归结为止。 例: 设有如下子句集: S={﹁I(x)∨R(x), I(a), ﹁R(y)∨L(y), ﹁L(a) } 用宽度优先策略证明S为不可满足。 宽度优先策略的归结树如下: *

本文链接:http://ksbuilders1.com/yueshutuili/258.html