我要投搞

标签云

收藏小站

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

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

人工智能 第3章 谓词逻辑与归结原理ppt

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

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

  子句集S求取过程 1、消去蕴涵符号 2、减少否定符号的辖域 3、对变量标准化 4、消去存在量词 5、化为前束范式 6、把母式化为合取式 7、消去全称量词 8、消去“” 9、更换名称变量 第3章 谓词逻辑与归结原理 命题逻辑 谓词逻辑基础 谓词逻辑归结原理 Herbrand定理 Herbrand定理 问题: 一阶逻辑公式的永真性(永假性)的判定是否能在有限步内完成? Herbrand定理 1936年图灵(Turing)和邱吉(Church)互相独立地证明了: “没有一般的方法使得在有限步内判定一阶逻辑的公式是否是永真(或永假)。但是如果公式本身是永真(或永假)的,那么就能在有限步内判定它是永真(或永假)。对于非永真(或永假)的公式就不一定能在有限步内得到结论。判定的过程将可能是不停止的。” Herbrand定理 Herbrand的思想 定义: 公式G永真:对于G的所有解释,G都为真。 思想: 寻找一个已给的公式是真的解释。然而,如果所给定的公式的确是永假的,就没有这样的解释存在,并且算法在有限步内停止。 Herbrand定理(H域) 基本方法: 因为量词是任意的,所讨论的个体变量域D是任意的,所以解释的个数是无限、不可数的 。 简化讨论域。建立一个比较简单、特殊的域,使得只要在这个论域上,该公式是不可满足的。 此域称为H域。 D域 H域 H域与D域关系示意图 H域例题 例3.19 设子句集S={P(x),Q(y)∨R(z)},求H域。 H0={a} H1=H0={a} …… H∞ = H1∪H2∪H3………={a} 例3.20 设子句集S={P(a),Q(x)∨R(f(x))},求H域。 H0={a} H1=H0={a,f(a)} H2={a,f(a),f(f(a))} …… H∞ = H1∪H2∪H3………={a,f(a),f(f(a))} 例3.21 设子句集S={P(a),Q(b)∨R(f(x))},求H域。 此题中有两个常量a,b H0={a,b} H1=H0={a,b,f(a),f(b)} H2={a,b,f(a),f(b),f(f(a)),f(f(b))} …… H∞ = H1∪H2∪H3………={a,b,f(a),f(b),f(f(a)),f(f(b)),…} H域例题 H域例题 例3.22 设子句集S = { P(x), Q(y,f(z,b)),R(a)},求H域 解: H0 = {a, b}为子句集中出现的常量 H1 = {a, b, f(a,b), f(a,a), f(b,a), f(b,b)} H2 = { a, b, f(a,b), f(a,a), f(b,a), f(b,b), f(a,f(a,b)), f(a,f(a,a)), f(a, f(b,a)), f(a, f(b,b)), f(b,f(a,b)), f(b,f(a,a)), f(b, f(b,a)), f(b,f(b,b)), f(f(a,b),f(a,b)), f(f(a,b),f(a,a)), f(f(a,b), f(b,a)), f(f(a,b), f(b,b)), f(f(a,a),f(a,b)), f(f(a,a),f(a,a)), f(f(a,a), f(b,a)), f(f(a,a), f(b,b)), f(f(b,a),f(a,b)), f(f(b,a),f(a,a)), f(f(b,a), f(b,a)), f(f(b,a), f(b,b)), f(f(b,b),f(a,b)), f(f(b,b),f(a,a)), f(f(b,b), f(b,a)), f(f(b,b), f(b,b))} ……… H∞ = H1∪H2∪H3……… H域例题 例3.23 设子句集S={P(c),Q(f(x),R(g(x)))},求H域。 此题中有常量c,函数f(x),g(x) H0={c} H1=H0={c,f(c),g(c)} H2={c,f(c),g(c),f(f(c)),f(g(c)),g(f(c)),g(g(c))} …… H∞ = H1∪H2∪H3………={c,f(c),g(c),f(f(c)),f(g(c)), g(f(c)),g(g(c))},…} Herbrand定理(H域) 原子集A:公式中的谓词取H域中的元素组成的集合。如 A = {所有形如 P(t1, t2, …tn)的元素} 即把H中的东西填到S的谓词里去。 S中的谓词是有限的、可数的,H域中的元素是可数的,因此,A中的元素也是可数的。 原子集例题 上例题的原子集为: A = { P(a), Q(a, a), R(a), P(b), Q(b, a), Q(b, b), Q(a, b), R(b), P( f(a,b)), Q(f(a, b), f(a, b)), R(f(a, b), P(f(a,a)), P(f(b,a)), P(f(b,b)),……) 一旦原子集内真值确定好(规定好),则S在H上的真值可确定。成为可数问题。 论域D上公式G或者说其子句集S的H域的建立,仅仅依赖于S中出现的几个函数和D的几个常量,或D中任意的一个常量,而且这些都是可数的,这就是H域比一般论域D简单的原因。 因此,如果能够将谓词逻辑公式的不可满足性问题的讨论从D转换到H域,其复杂程度将得到相应地减少,使得不可解的问题成为可解的问题。 Herbrand定理(H解释) 解释I:谓词公式G在论域D上任何一组真值的指定称为一个解释。 H解释:子句集S在的H域上的解释称为H解释。 基例:子句集S中某子句C中所有变元符号均以S的H域中的元素代入后,所得的基子句C’称为C的一个基例。 例如:S={P(x),Q(f(y))∨R(y),Z(f(y))} H={a,f(a),f(f(a)),…} P(a),P(f(a))为子句C=P(x)的基例 Q(f(a))∨R(a),Q(f(f(a)))∨R(f(a))都是Q(f(y))∨R(y)的基例 问题: 对于所有的解释,全是假才可判定。因为所有解释代表了所有的情况,如可穷举,问题便可解决 。 例3.24 S={P(x)∨Q(x),R(f(y))},求其一个H解释I* 解: S的H域为:{a,f(a),f(f(a)),……} S的原子集A为:{P(a),Q(a),R(a),P(f(a)),Q(f(a)),R(f(a)),……} I1*={P(a),Q(a),R(a),P(f(a)),Q(f(a)),R(f(a)),……} I2*={~P(a),~Q(a),~R(a),~P(f(a)),Q(f(a)),R(f(a)),……} I3*={P(a),~Q(a),~R(a),P(f(a)),Q(f(a)),~R(f(a)),……} 原子集A中各元素真假值的一个具体设定或对S中出现的常量、函数及谓词的一次取值就构成S的一个H解释。 Herbrand定理(H解释) 如下三个定理保证了归结法的正确性: 定理1: 设I是S的论域D上的解释,存在对应于I的H解释I*,使得若有SI = T,必有 SI* = T。 定理2: 子句集S是不可满足的,当且仅当所有的S的H解释下为假。 定理3: 子句集S是不可满足的,当且仅当对每一个解释I下,至少有S的某个子句的某个基例为假。 Herbrand定理(H解释) 若某个子句的某个基例为假,则此H解释为假。 一般来说,D是无穷不可列的,因此,子句集S也是无穷不可列的。但S确定后H是无穷可列的。不过在H上证明S的不可满足性仍然是不可能的。 解决问题的方法:语义树 Herbrand定理(语义树) 构成方法 原子集A中所有元素逐层添加的一棵二叉树。将元素的是与非分别标记在两侧的分枝上(可不完全画完) 。 特点 一般情况H是可数集,S的语义树是无限树。 N0 P(a) N12 Q(a) P(f(a)) N24 N31 N38 无限语义树 N11 ~P(a) ~Q(a) Q(a) ~Q(a) ~P(f(a)) N21 S={~P(x)∨Q(x),P(f(y)),~Q(f(y))} H域 H={a,f(a),f(f(a)),……} 原子集A={P(a),Q(a),P(f(a)),Q(f(a)),……} Herbrand定理(语义树) 意义 S ? H ? A ?语义树 语义树可以理解为H域的图形解释。 讨论的对象从无限、不可数论域D渐渐转换成为可数的、有序的二叉语义树。 建立语义树的目的:把每个解释都摊开。语义树中包含原子集的全部元素。因此,语义树是完全的。每一个直到叶子节点的分支对应S的一个解释。可以通过对语义树每一个分支来计算S的真值。如果每个基例都为假,则可认为是不可满足的。 几个概念 1、完全语义树:对于子句集S,如果有N个叶节点的语义树包含了S的原子集A中的所有元素Ai或~Ai,则说S的语义树是完全的。 2、失败结点: 当(由上)延伸到点N时,I(N)已表明了S的某子句的某基例假,但N以前尚不能判断这事实,就称N为失败结点。 3、封闭语义树: 如果S的完全语义树的每个分枝上都有一个失败结点,就称它是一棵封闭语义树。 几个概念 N0 P(a) N1,2 Q(a) P(f(a)) N2,4 N3,1 N3,8 N1,1 N4,2 N4,1 N2,1 N3,2 N2,2 N3,6 N4,9 N4,10 N4,13 N4,14 封闭语义树 Q(f(a)) S={~P(x)∨Q(x),P(f(y)),~Q(f(y))} ~P(a) ~Q(a) ~P(f(a)) ~Q(f(a)) ~Q(a) Q(a) P(f(a)) ~P(f(a)) P(f(a)) ~P(f(a)) Q(f(a)) Q(f(a)) ~Q(f(a)) ~Q(f(a)) Herbrand定理(结论) Herbrand定理: 子句集S是不可满足的,当且仅当对应于S的完全语义树是棵有限封闭树。 子句集S是不可满足的,当且仅当存在不可满足的S的有限基例集。 Herbrand定理(结论) 定理的意义 Herbrand定理已将证明问题转化成了命题逻辑问题。 由此定理保证,可以放心的用机器来实现自动推理了。(归结原理) 注意 Herbrand定理给出了一阶逻辑的半可判定算法,即仅当被证明定理是成立时,使用该算法可以在有限步得证。而当被证定理并不成立时,使用该算法得不出任何结论。 但是 ? ? ? ? ? ? ? ? ? ? ? ? ? Herbrand定理(结论) 仍存在的问题: 基例集序列元素的数目随子句基的元素数目成指数地增加。 因此,Herbrand定理是30年代提出的,始终没有显著的成绩。 ??? 直至1965年Robinson提出了归结原理。 归结原理与Herbrand定理 归结原理是语义树的一个倒塌过程 例如:有子句集S={P,~P∨Q,~P∨~Q} 原子集为A={P,Q},其封闭语义树和语义树倒塌过程如图示: N0 P N12 Q N11 ~P ~Q N21 N22 N0 P N12 Q N11 ~P ~Q N21 N22 最后归结出空,就是剩一个根节点,就说明语义树是有限封闭的,证明结束。 从子句集S的语义树必有两个失败结点相对应的子句可以归结,将归结式放入S,就会是的语义树T倒塌。 不可满足的子句集S必有一棵封闭的语义树,经过归结的倒塌过程,一定能使得根节点成为失败结点,也就是可以得到空子句。 作业 3.16(2) 3.18(3) 3.19(2)(3) 3.21(2) 3.22 3.23 定理3.1推广 G = G1 ∧ G2 ∧ G3 ∧ … ∧ Gn 的子句形 G的子句集可以分解成几个单独处理。 SG = S1 U S2 U S3 U …U Sn SG 与 S1 U S2 U S3 U …U Sn在不可满足的意义上是一致的。 SG 不可满足 = S1 U S2 U S3 U …U Sn不可满足 求子句集例子 例3.13:对所有的x,y,z来说,如果y是x的父亲,z又是y的父亲,则z是x的祖父。又知每个人都有父亲,试问对某个人来说谁是它的祖父? 求:用一阶逻辑表示这个问题,并建立子句集。 解:这里我们首先引入谓词: P(x, y) 表示y是x的父亲 Q(x, y) 表示y是x的祖父 ANS(x) 表示问题的解答 求子句集例子 1、对于第一个条件,“如果x是y 的父亲, y又是z 的父亲,则x是z 的祖父”,一阶逻辑表达式如下: A1:(?x)(?y)(?z)(P(x, y)∧P(y, z)→Q(x, z)) S A1:~P(x ,y)∨~P(y, z)∨Q(x, z) 2、对于第二个条件:“每个人都有父亲”,一阶逻辑表达式: A2:(?x)(?y)P(x, y) S A2:P(x,f(x)) 3、对于结论:某个人是他的祖父 B:(?x)(?y)Q(x, y) 否定后得到子句: ~( (?x)(?y)Q(x, y))∨ANS(y) S~B:~Q(x, y)∨ANS(y) 则得到的相应的子句集为:{ S A1,S A2,S~B }= {~P(x ,y)∨~P(y, z)∨Q(x, z), P(x,f(x)), ~Q(x, y)∨ANS(y)} 置换与合一 由于含有个体变量与函数,一阶谓词逻辑的归结比命题逻辑的归结复杂得多。 方法: 合一和置换,即对个体变量作适当替换。 置换 置换:可以简单的理解为是在一个谓词公式中用置换项去置换变量。 定义: 置换是形如{t1/x1, t2/x2, …, tn/xn}的有限集合。其中,x1, x2, …, xn是互不相同的变量,t1, t2, …, tn是不同于xi的项(常量、变量、函数);ti/xi表示用ti置换xi,并且要求ti与xi不能相同,而且xi不能循环地出现在另一个ti中。 例如 {a/x,c/y,f(b)/z}是一个置换。 {g(y)/x,f(x)/y}不是一个置换。 置换的合成 设?={t1/x1, t2/x2, …, tn/xn}, ?={u1/y1, u2/y2, …, un/yn},是两个置换。 则?与?的合成也是一个置换,记作?·?。 它是从集合 {t1·?/x1, t2·?/x2, …, tn·?/xn, u1/y1, u2/y2, …, un/yn } 中删去以下两种元素: 当ti?=xi时,删去ti?/xi (i = 1, 2, …, n); 当yi?{x1,x2, …, xn}时,删去uj/yj (j = 1, 2, …, m) 最后剩下的元素所构成的集合。 合成即是对ti先做?置换然后再做?置换,置换xi 置换的合成 例3.14: 设:?={f(y)/x, z/y},?={a/x, b/y, y/z},求?与?的合成。 解: 1、先求出集合 {f(b/y)/x, (y/z)/y, a/x, b/y, y/z}={f(b)/x, y/y, a/x, b/y, y/z} 其中,f(b)/x中的f(b)是置换?作用于f(y)的结果;y/y中的y是置换?作用于z的结果。 2、在该集合中,y/y满足定义中的条件i,需要删除;a/x,b/y满足定义中的条件ii,也需要删除。最后得 ?·?={f(b)/x,y/z} 合一 合一可以简单地理解为“寻找相对变量的置换,使两个谓词公式一致”。 定义:设有公式集F={F1,F2,…,Fn},若存在一个置换?,可使F1?=F2?=…= Fn?,则称?是F的一个合一。同时称F1,F2,... ,Fn是可合一的。 ?例3.15: 设有公式集F={P(x, y, f(y)), P(a,g(x),z)},则?={a/x, g(a)/y, f(g(a))/z}是它的一个合一。 注意:一般说来,一个公式集的合一不是唯一的。 求公式集F={P(x),P(f(y))}的合一 ?1={f(a)/x,a/y}, ?2={f(y)/x}都是F1F2的合一。 差异集(不一致集) S是一个非空的具有相同谓词名的原子公式集,从S各公式的左边第一项开始,同时向右比较,直到发现第一个不都相同的项为止,用这些项的差异部分组成S的一个差异集。 差异集(不一致集)的求法 设公式集{F1,F2}, F1=P(x,y,z),F2=P(x,f(a),h(b)) 解:从左到右进行比较, 1、首先两公式第一个元素,发现相同; 2、接着比较第二个元素,不同,则构成差异集 D1={y,f(a)}; 3、再比较第三个元素,不同,构成差异集D2={z,h(b)}。 最一般合一 设σ是谓词公式集F的一个合一,如果对F的任意一个合一θ都存在一个置换λ,使得θ= σ·λ ,则称σ是一个最一般合一(mgu)。 最一般合一的求取方法 最一般合一是唯一的(除了字母变化外) F={P(x),P(y)} {y/x}、{x/y}都是F1F2的mgu 例3.16 求mgu W={P(a,x,f(g(y))),P(z,f(a),f(u))},其中F1= P(a,x,f(g(y))),F2= P(z,f(a),f(u))。求F1和F2的mgu 由算法 1、W={P(a,x,f(g(y))),P(z,f(a),f(u))} 2、W0=W, σ0=ε 3、W0未合一,从左到右找不一致集,有D0={a,z} 4、取v0=z,t0=a 5、令σ1= σ0·{t0/v0} = {a/z} W1=W0 σ1 ={P(a,x,f(g(y))),P(a,f(a),f(u))} 3’、W1未合一,从左到右找不一致集,有D1={x,f(a)} 4’、取v1=x,t1=f(a) 5’、令σ2= σ1·{t1/v1} = {a/z} ·{f(a)/x}={a/z,f(a)/x} W2=W1 σ2 ={P(a,f(a),f(g(y))),P(a,f(a),f(u))} 3’’、W2未合一,从左到右找不一致集,有D2={g(y),u} 4’’、取v2=u,t2=g(y) 5’’、令σ3= σ2·{t2/v2} = {a/z,f(a)/x}·{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)))} 3’’’、W3已合一 σ3= {a/z,f(a)/x,g(y)/u}是F1和F2的mgu。 谓词逻辑的归结式 归结式求取方法 归结的注意事项: 1、谓词的一致性,P()与~ Q(), 不可以 2、常量的一致性, P(a, …)与~ P(b,….), 不可以 P(a, ….)与~ P(x, …), 可以 3、变量与函数, P(x, x, ….)与~ P(x, f(x), …),不可以 P(x, x, ….)与~ P(x, f(y), …),可以 4、不能同时消去两个互补对, P∨Q与~P∨~Q,不可以 5、先进行内部简化(置换、合并) 例3.17 求C1C2的归结式 设C1=P(y)∨P(f(x))∨Q(g(x)), C2=~P(f(g(a)))∨Q(b) 解: 对C1取最一般合一σ={f(x)/y},得C1的因子, C1σ= P(f(x))∨Q(g(x)) 对C1的因子和C2进行归结,得归结式 Q(g(g(a)))∨Q(b) , {g(a)/x} 1、F1=B(x),F2=~B(x)∨C(x) 2、F1=P(x)∨Q(x),F2=~Q(f(y)) 3、F1=P(x,f(y))∨Q(x)∨R(f(a),y),F2=~P(f(f(a)),z)∨R(z,w) 谓词逻辑的归结过程 1、写出谓词关系公式 2、用反演法写出谓词表达式 3、化为SKOLEM标准形 4、求取子句集S 5、对S中可归结的子句做归结 6、归结式仍放入S中,反复归结过程 7、得到空子句 8、?命题得证 例3.18 假设任何通过计算机考试并获奖的人都是快乐的,任何肯学习或幸运的人都可以通过所有的考试,张不肯学习但他是幸运的,任何幸运的人都能获奖。求证:张是快乐的。 ?解:一、先将问题用谓词表示如下: R1:“任何通过计算机考试并获奖的人都是快乐的” (?x)((Pass(x, computer)∧Win(x, prize))→Happy(x)) R2:“任何肯学习或幸运的人都可以通过所有考试” (?x)(?y)(Study(x)∨Lucky(x)→Pass(x, y)) R3:“张不肯学习但他是幸运的” ~Study(zhang)∧Lucky(zhang) R4:“任何幸运的人都能获奖” (?x)(Luck(x)→Win(x,prize)) 结论:“张是快乐的”的否定 ~Happy(zhang) 二、将每一个表示逻辑条件的谓词子句转换为Skolem标准型 由R1及逻辑转换公式:P∧W→H=~(P∧W)∨ H ,可得 (1)~Pass(x, computer)∨~Win(x, prize)∨Happy(x) 由R2: (2)~Study(y)∨Pass(y,z) (3)~Lucky(u)∨Pass(u,v) 由R3: (4)~Study(zhang) (5)Lucky(zhang) 由R4: (6)~Lucky(w)∨Win(w,prize) 由结论: (7)~Happy(zhang) (结论的否定) (8)~Pass(w, computer)∨Happy(w)∨~Luck(w) (1)(6),{w/x} (9)~Pass(zhang, computer)∨~Lucky(zhang) (8)(7),{zhang/w} (10)?~Pass(zhang, computer) (9)(5) (11)??~Lucky(zhang) (10)(3),{zhang/u, computer/v} (12)??? (11)(5)? 归结原理 归结法的实质: 归结法是仅有一条推理规则的推理方法。 归结过程是一个语义树倒塌的过程。 归结法的问题 子句中有等号或不等号时,完备性不成立。 通过对谓词公式的否定式的子句集使用消解法归结,若在某一步时推导出空字句,即推导出了矛盾,则说子句集是不可满足的,从而原谓词公式也是不可满足的 归结方法是完备的,即对于正确的逻辑公式,使用该方法可以在有限步内得到结论。 归结过程的控制策略 要解决的问题: 归结方法的知识爆炸。 控制策略的目的 归结点尽量少 控制策略的原则 删除不必要的字句,或对参加归结的子句加以限制 给出控制策略,以便仅选择合适的子句对其做归结,避免多余的、不必要的归结式出现。 控制策略的方法(1) 删除策略 = 完备 归类:设有两个子句C和D,若有置换?使得C? ? D成立,则称子句C把子句D归类。 由于小的可以代表大的,所以小的吃掉了大的。 若对S使用归结推理过程中,当归结式Cj是重言式(永真式)和Cj被S中子句和子句集的归结式Ci(ij)所归类时,便将Cj删除。这样的推理过程便称做使用了删除策略的归结过程。 归结过程在寻找可归结子句时,子句集中的子句越多,需要付出的代价就会越大。如果在归结时能把子句集中无用的子句删除掉,就会缩小搜索范围,减少比较次数,从而提高归结效率。 缩短归结过程 判别是否可被删除的计算量 删除策略的归结推理是完备的 并非所有可归结的谓词公式都可采用删除策略 删除策略的主要思想 控制策略的方法(2) 采用支撑集 = 完备 支撑集:设有不可满足子句集S的子集T,如果S-T是可满足的,则称T是S的支撑集。 ? S T 可满足 支撑集示意图 采用支撑集策略时,从开始到得到?的整个归结过程中,只选取不同时属于S-T的子句,在其间进行归结。就是说,至少有一个子句来自于支撑集T或由T导出的归结式。 ? 例如:A1∧A2∧A3∧~B中的~B可以作为支撑集使用。要求每一次参加归结的亲本子句中,只要应该有一个是有目标公式的否定(~B)所得到的子句或者它们的后裔。 思想:尽量避免在可满足的子句集中进行归结,因为从中推导不出空子句。 可将支撑集策略理解为目标指导的反向推力。 支撑集策略的归结是完备的,同样,所有可归结的谓词公式都可以用采用支撑集策略达到加快归结速度的目的。 问题是如何寻找合适的支撑集。一个最容易找到的支撑集是目标子句的非,即S~B。 例如 S={P∨Q,~P∨R,~Q∨R,~R},取T={~R} 支撑集归结过程为: ⑤~P ②④ ⑥~Q ③④ ⑦Q ①⑤ ⑧P ①⑥ ⑨R ③⑦ ⑩? ④⑨ 控制策略的方法(3) 语义归结 = 完备 语义归结策略是将子句S按照一定的语义分成两部分,约定每部分内的子句间不允许作归结。同时还引入了文字次序,约定归结时其中的一个子句的被归结文字只能是该子句中“最大”的文字。 例如 S={~P∨~Q∨R,P∨R,Q∨R,~R} 1、规定顺序为PQR 2、用S的一个解释I={~P,~Q,~R} 把S分为两部分 S1={P∨R,Q∨R},S2={~P∨~Q∨R,~R} 语义归结策略的归结是完备的,同样,所有可归结的谓词公式都可以用采用语义归结策略达到加快归结速度的目的。 问题是如何寻找合适的语义分类方法,并根据其含义将子句集两个部分中的子句进行排序。 归结过程如下: ①~P∨~Q∨R ? S2 ②P∨R ? S1 ③Q∨R ? S1 ④~R ? S2 ⑤~Q∨R ②①, ? S2 ⑥~P∨R ③①, ? S2 ⑦R ②⑥,? S1 ⑧R ③⑤,? S1 ⑨? ④⑦ 控制策略的方法(4) 线性归结 = 完备 线性归结策略首先从子句集中选取一个称作顶子句的子句C0开始作归结。归结过程中所得到的归结式Ci立即同另一子句Bi进行归结得归结式Ci+1。而Bi属于S或是已出现的归结式Cj(ji)。 C0 B1 B2 Bn C1 C2 空 线性归结策略示意图 线性归结是完备的 所有可归结的谓词公式都可以采用线性归结策略达到加快归结速度的目的。 如果能搞找到一个较好的顶子句,可以式归结顺利进行。否则也可能事与愿违。 控制策略的方法(5) 单元归结 = 完备 单元归结策略要求在归结过程中,每次归结都有一个子句是单元子句(只含一个文字的子句)或单元因子。显而易见,此种方法可以简单地削去另一个非单子句中的一个因子,使其长度减少,构成简单化,归结效率较高。 不是所有可以归结的谓词公式集合都可以采用单元归结策略进行归结。初始子句集中没有单元子句时,单元归结策略无效。 控制策略的方法(6) 输入归结 = 完备 与单元归结策略相似,输入归结策略要求在归结过程中,每一次归结的两个子句中必须有一个是S的原始子句。这样可以避免归结出的不必要的新子句加入归结,造成恶性循环。可以减少不必要的归结次数。 如同单元归结策略,不是所有的可归结谓词公式的最后结论都是可以从原始子句集中的得到的。 简单的例子,归结结束时,即最后一个归结式为空子句的条件是,参加归结的双方必须是两个单元子句。原始子句集中没有单元子句的谓词公式一定不能采用输入归结策略。 换名规则:将量词辖域中出现的某个约束出现的个体变量及相应的指导变量,改成另一个此辖域中未曾出现过的个体变量符号,公式中其余部分不变。 替代规则:对某自由出现的个体变量用与原公式中所有个体变量符号不同的变量符号去替代,且处处替代。 换名规则、替代规则在谓词逻辑归结的子句集求取过程中不可缺少,只有进行适当的换名和替代才能够正确得到前束范式和Skolem标准型。 谓词公式的解释 对谓词公式中的各种变量制定特殊的常量去替代,就构成了一个谓词的解释。 在使用一个解释I,解释一个谓词公式A时,将A中的个体常量用I中特定常量代替,函数和谓词用I中特定函数和谓词代替。 解释是一个集合的概念 解释的例子 例3.8,给定解释I如下: 个体域DI={2,3}; 函数f(x)为f(2)=3,f(3)=2; 谓词P(x)为P(2)=0,P(3)=1; Q(x,y)为Q(i,j)=1,i,j=2,3; R(x,y)为R(2,2)=R(3,3)=1,R(2,3)=R(3,2)=0。 求(1)在解释I下,?x(P(f(x))∧Q(x,f(x)))的线)在解释I下,? x?yR(x,y)的线) ?x(P(f(x))∧Q(x,f(x)))的真值为 = (P(f(2))∧Q(2,f(2)))∨(P(f(3))∧Q(3,f(3))) = (P(3)∧Q(2,3))∨(P(2)∧Q(3,2)) = (1∧1)∨(0∧1) = 1 (2) ? x?yR(x,y)的真值为 = (R(2,2)∨R(2,3)) ∧ (R(3,3)∨R(3,2)) = (1∧1) = 1 约束出现的变量取值关系与量词的性质有关。 谓词公式是永真的 谓词公式是不可满足的 谓词逻辑的归结推理方法,即归结原理,就是将对谓词公式的正确性推理证明转换成为该谓词公式的不可满足性证明 谓词演算等值公式 约束变项换名规则: (Qx ) P(x) = (Qy ) P(y) (Qx ) P(x,z) =(Qy ) P(y,z) 量词否定等值式: ~(? x ) P(x) = ( ? y ) ~P(y) ~(? x ) P(x) = ( ? y ) ~ P(y) 量词分配等值式: (? x )( P(x)∧ Q(x)) = (? x ) P(x) ∧ (? x ) Q(x) (? x )( P(x)∨ Q(x)) = (? x ) P(x) ∨ (? x ) Q(x) 消去量词等值式:设个体域为有穷集合(a1, a2, …an) (? x ) P(x) = P( a1 ) ∧ P( a2 ) ∧ … ∧ P( an ) (? x )P(x) = P( a1 ) ∨ P( a2 ) ∨ … ∨ P( an ) 谓词演算等值公式 量词辖域收缩与扩张等值式: (? x )( P(x) ∨ Q) = (? x ) P(x) ∨ Q (? x )( P(x) ∧ Q) = (? x ) P(x) ∧ Q (? x )( P(x) → Q) = (? x ) P(x) → Q (? x )(Q → P(x)) =Q → (? x ) P(x) (? x )( P(x) ∨ Q) = (? x ) P(x) ∨ Q (? x )( P(x) ∧ Q) = (? x ) P(x) ∧ Q (? x )( P(x) → Q) = (? x ) P(x) → Q (? x )(Q → P(x) ) =Q → (? x ) P(x) 前束范式 谓词公式P如果具有以下形式,即把所有的量词都提到最左端去 (Q1X1)(Q2X2)…(QnXn) P(x1,x2,…,xn) 称为P的前束范式 任何谓词公式的前束范式都是存在的 前束范式不唯一 前束范式例子 例3.9 求(?xP(x,y)→?yQ(y))→?xR(x,y)的前束范式 解: (?xP(x,y)→?yQ(y))→?xR(x,y) = (?xP(x,z)→?yQ(y))→?xR(x,z) = (?xP(x,z)→?yQ(y))→?tR(t,z) = ?x(P(x,z)→?yQ(y))→?tR(t,z) = ?x?y(P(x,z)→Q(y))→?tR(t,z) = ?x?y((P(x,z)→Q(y))→?tR(t,z)) = ?x?y?t((P(x,z)→Q(y))→R(t,z)) 谓词推理 量词的削去和引入的基本思想是任意量词可以削去,用变量和常量表示,存在量词可以用常量表示。 削去和引入量词的规则: (1)?xP(x) = P(y) , ?xP(x) = P(c) (2)? xP(x) = P(c) (3)P(y) = ?xP(x) (4)P(c) = ? xP(x) 谓词推理例子 例3.10 20世纪70年代的漫画都是日本漫画家创作的,这幅漫画是20世纪70年代的作品,因此,这幅漫画是日本漫画家的作品。 解: 设P(X):20世纪70年代的漫画; Q(y):日本漫画家的作品; a:一幅漫画。 前提: ?xP(x) →Q(x),P(a) 结论:Q(a) 证明:① ?xP(x) →Q(x) ② P(a) ③ P(a) →Q(a) ④ Q(a) 以上推理为演绎推理 演绎推理的局限性 谓词知识表示 谓词可以用来表达人工智能需要处理的知识。 谓词逻辑的基本组成部分是谓词符号、变量符号、函数符号和常量符号,并用括号隔开,以表示论域内的关系。 例如:INROOM(ROBOT,r1) PLAY(Zhang,Li,tennis) 用连接词构成合式公式 ~INROOM(ROBOT,r2) LIKE(I,MUSIC) ∧ LIKE(I,PAINING) PLAYS(LIMING,BASKETBALL) ∨PLAYS(LIMING,FOOTBALL) OWNS(HEPING,BOOK) → COLOR(BOOK,BLUE) (?x)[ROBOT(X)→COLOR(x,GRAY)] (?x)INROOM(x,HOUSE1) 谓词表示知识的步骤 用对象、函数、关系将知识概念化 构造谓词表达式 写出概念化知识的谓词公式 谓词逻辑法比命题逻辑法更加细致 谓词逻辑法应用广泛的原因 逻辑表示法的缺点 机器人搬弄积木块问题的谓词逻辑表示 例3.11 一个房间里,有一个机器人Robot,一个积木块Box,两个桌子A和B,开始时机器人Robot在桌子A旁边,两手空空的,桌子A上放着积木块Box,桌子B上是空的,Robot将Box从桌子A转移到桌子B上,并回到桌子A旁边。 怎样用逻辑法描述从初始状态到目标状态的机器人操作过程? 第一步:定义谓词如下 Table(x):x是桌子 EmptyHanded(x):x双手是空的 At(x,y):x在y旁边 Holds(y,w):y拿着w On(w,x):w在x上 EmptyTable(x):桌子x上是空的 第二步:题目涉及的个体定义为 机器人Robot、积木块Box、桌子A、桌子B 第三步:描述问题的初始状态和目标状态 初始状态:EmptyHanded(Robot) ∧On(Box,A) ∧Table(A) ∧Table(B) ∧EmptyTable(B) 目标状态:EmptyHanded(Robot) ∧On(Box,B) ∧Table(A) ∧Table(B) ∧EmptyTable(A) 第四步:对问题求解。实际上是寻找一组机器人可进行的操作,实现一个由初始状态到目标状态的机器人操作过程 机器人要执行的动作有: GOTO(x,y):从x出走到y处 PICK_UP(x):在x处拿起积木块 SET_DOWN(x):在x处放下积木块 可进行的操作一般分为先决条件和动作两部分,这3个操作表示如下: (1)GOTO(x,y) 条件:At(Robot,x) 动作:删除 At(Robot,x) 增加 At(Robot,y) (2)PICK_UP(x) 条件:On(Box,x)∧Table(x)∧At(Robot,x)∧EmptyHanded(Robot) 动作:删除 On(Box,x)∧EmptyHanded(Robot) 增加 Holds(Robot,Box) (3)SET_DOWN(x) 条件:Table(x) ∧At(Robot,x) ∧Holds(Robot,Box) 动作:删除 Holds(Robot,Box) 增加 On(Box,x) ∧EmptyHanded(Robot) 机器人在执行每一操作之前需要检查所需先决条件是否满足,只有条件满足以后,才执行相应的操作。 操作过程如下: PICK_UP(A) GOTO(A,B) SET_DOWN(B) GOTO(B,A) 第3章 谓词逻辑与归结原理 命题逻辑 谓词逻辑基础 谓词逻辑归结原理 Herbrand定理 归结原理概述 谓词逻辑归结方法和命题逻辑归结方法基本原理是一样的。 谓词逻辑归结在生成子句集之前要将逻辑公式转化为Skolem标准型,然后再进行归结。 Herbrand采用反证法思想,将永真性的证明问题转化为不可满足性的证明问题。而Robinson的归结原理使得自动定理证明得以实现。 归结法的基本原理是采用反证法将待证明的表达式转换为逻辑公式(谓词公式),然后再进行归结,归结能够顺利完成,则证明公式是正确的。 Skolem 标准型 前束范式中消去所有的量词,称这种形式的谓词公式为Skolem标准型。 任何一个谓词公式都可化为与之对应的Skolem标准型,但不唯一。 Skolem标准型的转化过程:依据约束变量换名规则,把公式变型为前束范式,然后依照量词消去原则或者略去所有量词。 量词消去原则 一、消去存在量词“?” 注意:左边有全称量词的存在量词,消去时该变量改写成为全称量词的函数;如没有,改写成为常量。 二、略去全称量词“?” 例3.12:将下式化为Skolem标准型 ~(?x)(?y)P(a, x, y) →(?x)(~(?y)Q(y, b)→R(x)) 解: 第一步,消去→号,得: ~(~(?x)(?y)P(a, x, y)) ∨(?x) (~~(?y)Q(y, b)∨R(x)) 第二步,~深入到量词内部,得: (?x)(?y)P(a, x, y) ∨(?x) ((?y)Q(y, b)∨R(x)) 第三步,变元易名,得 (?x)(?y)P(a, x, y) ∨(?u) (? v)(Q(v, b) ∨R(u)) 第四步,存在量词左移,直至所有的量词移到前面,得: (?x)(?y)(?u)(?v)(P(a, x, y) ∨Q(v, b) ∨R(u)) 由此得到前束范式 第五步,消去“?”(存在量词),略去“?”全称量词 消去(?y),因为它左边只有(?x),所以使用x的函数f(x)代替之,这样得到: (?x) (?u) (?v) P(a, x, f(x)) ∨(Q(v, b) ∨R(u)) 消去(?u),同理使用g(x)代替之,这样得到: (?x) (?v) ( P(a, x, f(x)) ∨Q(v, b) ∨R(g(x))) 略去全称变量,原式的Skolem标准形为: P(a, x, f(x)) ∨Q(v, b) ∨R(g(x)) Skolem定理 谓词逻辑的任意公式都可以化为与之等价的前束范式,但其前束范式不唯一。 Skolem标准形定义: 消去量词后的谓词公式。 注意: 谓词公式G的Skolem标准形同G并不等值。 子句集 文字:不含任何连接词的谓词公式。 子句:一些文字的析取。 子句集S的求取: G → 前束范式 → 消去存在量词、略去任意量词,生成 Skolem标准型(必须满足合取范式条件) → 以“,”取代“∧”,并表示为集合形式 。 练习:求谓词公式的子句集 (?x){ P(x) → {(?y)[P(y) →P(f(x,y))] ∧ ~ (?y)[Q(x,y) →P(y)]}} 定理3.1 谓词公式G是不可满足的,当且仅当其子句集S是不可满足的 G与S不等价,但在不可满足得意义下是一致的。 注意:G真不一定S真,而S真必有G真。 即: S = G 智力题:五个房子,五个人,五种宠物,五种饮料,五种香烟 1、有5栋5种颜色的房子 2、每一位房子的主人国籍都不同 3、这5个人只喝一个牌子的饮料,只抽一个牌子的香烟,只养一种宠物 4、没有人有相同的宠物,抽相同牌子的香烟,喝相同的饮料 谁养鱼? 已知条件: 1、英国人住在红房子里 2、瑞典人养了一条狗 3、丹麦人喝茶 4、绿房子在白房子左边 5、绿房子主人喝咖啡 6、抽PALLMALL烟的人养了一只鸟 7、黄房子主人抽DUNHILL烟 8、住在中间那间房子的人喝牛奶 9、挪威人住在第一间房子 10、抽混合烟的人住在养猫人的旁边 11、养马人住在DUNHILL烟的人旁边 12、抽BLUEMASTER烟的人喝啤酒 13、德国人抽PRINCE烟 14、挪威人住在蓝房子旁边 15、抽混合烟的人的邻居喝矿泉水 推理的一般形式 已知:实事一,实事二,… 如果实事一,那么结论一; 如果实事二,那么结论二;… 得到:结论一,结论二,… 如果将实事和规则抽象出来,不涉及具体内容,借助一些符号来表示,推理过程可形式化为: P:某已知实事 P→Q:如果P,则Q 结论:Q 逻辑 经典逻辑: 命题逻辑、谓词逻辑 非经典逻辑: 不确定性推理、非单调性推理 第3章 谓词逻辑与归结原理 归结 推理 命题 逻辑 谓词 逻辑 Skolem标准形、 子句集 基本 概念 谓词逻辑 归结原理 合一和置换、 控制策略 数理 逻辑 命题逻辑 归结 Herbrand 定理 第3章 谓词逻辑与归结原理 命题逻辑 谓词逻辑基础 谓词逻辑归结原理 Herbrand定理 命题例子 命题:能判断真假(不是既真又假)的陈述句。 简单陈述句描述事实、事物的状态、关系等性质。 例如: 1.? 1+1=2 2.? 雪是黑色的。 3.? 北京是中国的首都。 4.? 到冥王星去渡假。 例如: 1.? 快点走吧! 2.? 到那去? 3.? x+y10 命题公式 基本联结词 否定、合取、析取、蕴含、等价 命题公式的联结词的组合仍然是命题公式 合取式:p与q,记做p ∧ q 析取式:p或q,记做p ∨ q 蕴含式:如果p则q,记做p ? q 等价式:p当且仅当q,记做p ? q 将陈述句转化成命题公式 如:设“下雨”为p,“骑车上班”为q,, 1.“只要不下雨,我骑自行车上班”。~p 是 q的充分条件, 因而,可得命题公式: ~p → q 2.“只有不下雨,我才骑自行车上班”。~p 是 q的必要条件, 因而,可得命题公式:q → ~p 1、认真分析蕴含式的前件和后件的关系 2、注意同一命题的各种等价说法 1.? “如果我进城我就去看你,除非我很累。” 设:p,我进城,q,去看你,r,我很累。 则有命题公式:~r → (p → q)。 2.“应届高中生,得过数学或物理竞赛的一等 奖,保送上北京大学。” 设:p,应届高中生,q,保送上北京大学上学, r,是得过数学一等奖。t,是得过物理一等奖。 则有命题公式公式:p ∧ ( r ∨t ) → q。 给出事件的命题公式的基本步骤: 符号化、适当联结词 几个概念 命题公式的解释 真值表 公式的分类 若A无成假赋值,则称A为重言式或永真式 若A无成真赋值,则称A为矛盾式或永假式 若A至少有一个成真赋值,则称A为可满足的 等值式 基本等值式 交换律:A ∨B = B ∨A A ∧ B = B ∧ A 结合律: (A∨B) ∨ C= A∨(B∨C) (A ∧ B) ∧ C= A ∧(B ∧C) 分配律: A∨(B ∧ C) = (A∨B) ∧(A ∨C) A ∧(B ∨ C) = (A ∧B) ∨(A ∧C) 双重否定律: A = ~~A 等幂律: A = A ∨ A; A = A ∧ A 若等价式A ? B 是重言式,则称A和B等值,记作A = B 摩根律:~(A∨B) = ~A ∧ ~B ~(A ∧B) = ~A∨ ~B 吸收律:A∨(A ∧B) = A A ∧(A∨B) = A 同一律: A∨0 = A ;A ∧1 = A 零律: A∨1 = 1; A ∧0 = 0 排中律: A∨~A = 1 矛盾律: A ∧ ~A = 0 蕴含等值式:A → B = ~A∨B 等价等值式:A ? B = ( A → B ) ∧ ( B → A ) 假言易位式: A → B = ~B → ~A 等价否定等值式: A ? B = ~A ? ~B 归谬论: (A → B) ∧ (A → ~B) = ~A 等值演算 置换规则 联结词的优先顺序 范 式 简单合取范式 简单析取范式 合取范式:仅由有限个简单析取式组成的合取式。 析取范式:仅由有限个简单合取式组成的析取式。 主合取范式 主析取范式 范式存在定理 求合取范式的基本步骤 例3.1 例3.2 命题逻辑的意义 给计算机、智能体建模的过程就是对知识进行描述,应用知识进行推理得到结论,并将结论用人能够接受理解的形式显示的过程。 知识可以用公式表示为对特征值的约定。 知识用特征描述后可以用于推理。 命题逻辑有数理逻辑作为坚实的理论支柱,同时又是谓词逻辑的基础,对于人工智能知识表示与推理研究有着重要的意义。 命题逻辑的推理规则 逻辑结论 推理规则 常用推理定律 证明中常用的推理规则 例3.3 例3.4 命题逻辑的归结法 归谬法 例: 命题: A1、A2、A3 和 B 求证: A1 ∧ A2 ∧ A3成立,则B成立, 即:A1 ∧ A2 ∧ A3 → B 反证法:证明A1 ∧ A2 ∧ A3 ∧ ~B 是矛盾式 (永假式) 归结原理 依赖于一个单一的规则: 如p∨q和~q∨r都为真,则p∨r为真。 基本思想:将待证明逻辑公式的结论,通过等值公式转换成附加前提,再证明该逻辑公式是不可满足的。 子句 建立子句集 合取范式:命题、命题和的与, 如: P∧(P∨Q)∧(~P∨Q) 子句集S:合取范式形式下的子命题(元素)的集合 例:命题公式:P∧(P∨Q)∧(~P∨Q) 子句集 S:S = {P, P∨Q, ~P∨Q} 例3.5 例3.6 归结式 消除互补对,求新子句→得到归结式。 如子句:C1, C2 归结式:C12 = C1’∨ C2’ C1, C2为C12的亲本子句。 ? 注意:C1∧C2 → C12 , 反之不一定成立。 归结式的性质 :归结式是亲本子句的逻辑结论。 归结法证明过程 归结方法推理过程步骤: 1、建立待归结命题公式,根据反证法将所求证的问题转化为命题公式,求证其是矛盾式 2、求取合取范式 3、建立子句集 4、对子句集中的子句使用归结推理规则 归结式作为新子句参加归结 归结式为空子句□ ,停止 S是不可满足的(矛盾),原命题成立。 ? (证明完毕) 命题逻辑归结例题 例题3.7:证明公式:(P → Q) → (~Q → ~P) 证明: (1)根据归结原理,将待证明公式转化成待归结命题公式: (P → Q) ∧~(~Q → ~P) (2)分别将公式前项化为合取范式: P → Q = ~P ∨ Q 结论求~后的后项化为合取范式: ~(~Q → ~P)= ~(Q∨~P) = ~Q ∧ P 两项合并后化为合取范式: (~P ∨ Q)∧~Q ∧ P (3)则子句集为: { ~P∨Q,~Q,P} 子句集为: { ~P∨Q,~Q,P} (4)对子句集中的子句进行归结可得: 1.????? ~P∨Q 2.????? ~Q 3.????? P 4.????? Q, (1,3归结) 5.????? ?, (2,4归结) 由上可得原公式成立。 第3章 谓词逻辑与归结原理 命题逻辑 谓词逻辑基础 谓词逻辑归结原理 Herbrand定理 谓词逻辑基础 一阶谓词逻辑中,简单命题被分解成个体词和谓词两部分。 基本概念 个体词:表示主语的词 谓词:刻画个体性质或个体之间关系的词 量词:表示数量的词 例子 小王是个工程师。 8是个自然数。 我去买花。 小丽和小华是朋友。 其中:“小王”、“工程师”、“我”、“花”、“8”、“小丽”、“小华”都是个体词,而“是个工程师”、“是个自然数”、“去买”、“是朋友”都是谓词。 显然前两个谓词表示的是事物的性质,第三个谓词“去买”表示的一个动作也表示了主、宾两个个体词的关系,最后一个谓词“是朋友”表示两个个体词之间的关系。 基本定义 个体常量:a,b,c 个体变量:x,y,z 个体域:D 谓词常量:P,Q,R 谓词变量:P(x),Q(x,y),R(x,b) n元谓词:P(x1,x2,…,xn) 一阶谓词 任意量词:? 存在量词:? 例子 例如:(1)所有的人都是要死的。 (2)有的人活到一百岁以上。 在个体域D为人类集合时,可符号化为: (1)?xP(x),其中P(x)表示x是要死的。 (2)?xQ(x), 其中Q(x)表示x活到一百岁以上。 在个体域D是全总个体域时, 引入特殊谓词R(x)表示x是人,可符号化为: (1)?x(R(x) → P(x)), 其中,R(x)表示x是人;P(x)表示x是要死的。 (2)?x(R(x) ∧ Q(x)), 其中,R(x)表示x是人;Q(x)表示x活到一百岁以上。 使用量词时需注意的事项 一阶谓词公式 原子公式 谓词公式 指导变量 辖域 约束出现 自由出现 谓词公式: ?x(P(x)→?yQ(x,y))

  “原创力文档”前称为“文档投稿赚钱网”,本网站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有【成交的100%(原创)】

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