您好、欢迎来到现金彩票网!
当前位置:刘伯温四肖中特料 > 推理子句 >

人的工智能导论_第3章ppt

发布时间:2019-08-09 08:07 来源:未知 编辑:admin

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

  第三章 归结推理方法 概述 命题逻辑的归结法 谓词归结子句形 归结原理 归结过程的策略控制 Herbrand定理 第三章 归结推理方法 概述 命题逻辑的归结法 谓词归结子句形 归结原理 归结过程的策略控制 概述 归结原理由J.A.Robinson由1965年提出。 与演绎法(deductive inference)完全不同,新的逻辑演算(inductive inference)算法。 一阶逻辑中,至今为止的最有效的半可判定的算法。即,一阶逻辑中任意恒真公式,使用归结原理,总可以在有限步内给以判定。 语义网络、框架表示、产生式规则等等都是以推理方法为前提的。即,有了规则已知条件,顺藤摸瓜找到结果。 而归结方法是自动推理、自动推导证明用的。(“数学定理机器证明”) 本课程只讨论一阶谓词逻辑描述下的归结推理方法,不涉及高阶谓词逻辑问题。 第三章 归结推理方法 概述 命题逻辑的归结法 谓词归结子句形 归结原理 归结过程的策略控制 Herbrand定理 第三章 归结推理方法 概述 命题逻辑的归结法 谓词归结子句形 归结原理 归结过程的策略控制 Herbrand定理 命题逻辑的归结法 命题逻辑(Propositional Logic)基础: 定义:对于命题p,q 命题的非: ~ p 命题与(合取式):p与q,记做p ? q 命题或(析取式): p或q,记做p ? q 蕴含式: 如果p则q,记做p ? q 等价式:p当且仅当q,记做p ? q 命题逻辑基础:公式 在命题逻辑中,我们将命题成为原子公式(Atomic Formula),简称原子。 定义:公式 原子是公式; 若G,H是公式,则(~G)、(G?H )、 (G ? H )、 (G ? H )、 (G ? H )是公式; 所有公式都是有限次使用(1)、(2)得到的符号串。 命题逻辑基础:真值表(解释) 命题逻辑基础 定义:对于公式A 若A在它的所有解释I(Interpretation)下,其真值都为T(真),则称A为重言式或恒真式; 若A在它的所有解释I下,其真值都为F(假),则称A为不可满足的(Unsatisfiable,或永假式); 若至少存在一个解释I,使得A为真,则称A为可满足的(Satisfiable); 逻辑蕴涵:公式G,H,如果(G ? H)是恒真的,记为G ? H 。 逻辑等价:公式G,H,如果(G ? H)是恒真的,记为G ? H 。 命题逻辑基础:范式 析取范式:公式G为析取范式,如果: G = L1 ? L2 ? … ? Ln 其中Li(i = 1, 2, …, n)是原子或原子的非的合取式。 合取范式:公式G为合取范式,如果: G = L1 ? L2 ? … ? Ln 其中Li(i = 1, 2, …, n)是原子或原子的非的惜取式。 任何一个公式在等价的意义下,都可转化成析取范式或者合取范式。 文字(Literal):一个原子或原子的非。 子句(Clause):文字的析取式。 空子句:不含文字的空集合。 命题逻辑基础:基本等值式 基本等值式24个(1) 交换率:p∨q ? q ∨p ; p Λ q ? q Λp 结合率: (p∨q) ∨ r ? p∨(q ∨r); (p Λ q) Λ r ? p Λ(q Λ r) 分配率: p∨(q Λ r) ?(p∨q)Λ(p ∨r) ; p Λ(q ∨ r) ?(p Λ q) ∨(p Λ r) 命题逻辑基础:基本等值式 基本等值式(1) 摩根率: ~ (p∨q) ? ~ p Λ ~ q ; ~ (p Λq) ? ~ p ∨ ~ q 吸收率: p∨(pΛq ) ? p, p Λ(p∨q ) ? p ; 泛界律: p∨F ? p , pΛT ? p, p ΛF ? F , pΛT ? T 互余律:G ∨~G ? T(恒真), G Λ ~G ? F(恒假) 蕴含等值式:p → q ? ~ p∨q 假言易位式: p → q ? ~q → ~p 命题例 命题:能判断真假(不是既真又假)的陈述句。 简单陈述句描述事实、事物的状态、关系等性质。 例如:1.? 1+1=2 2.? 雪是黑色的。 3.? 北京是中国的首都。 4.? 到冥王星去渡假。 判断一个句子是否是命题,有先要看它是否是陈述句,而后看它的真值是否唯一。以上的例子都是陈述句,第4句的真值现在是假,随着人类科学的发展,有可能变成真,但不管怎样,真值是唯一的。因此,以上4个例子都是命题。 而例如:1.? 快点走吧! 2.? 到那去? 3.? x+y10 等等句子,都不是命题。 命题表示公式(1) 将陈述句转化成命题公式。 如:设“下雨”为p,“骑车上班”为q,, 1.“只要不下雨,我骑自行车上班”。~p 是 q的充分条件, 因而,可得命题公式: ~p → q 2.“只有不下雨,我才骑自行车上班”。~p 是 q的必要条件, 因而,可得命题公式:q → ~p 命题表示公式(2) 例如: 1.? “如果我进城我就去看你,除非我很累。” 设:p,我进城,q,去看你,r,我很累。 则有命题公式:~r → (p → q)。 2.“应届高中生,得过数学或物理竞赛的一等 奖, 保送上北京大学。” 设:p,应届高中生,q,保送上北京大学上学, r,是得过数学一等奖。t,是得过物理一等奖。 则有命题公式公式:p ∧ ( r ∨t ) → q。 命题逻辑的归结法 基本单元:简单命题(陈述句) 例: 命题: A1、A2、A3 和 B 求证: A1ΛA2ΛA3成立,则B成立, 即:A1ΛA2ΛA3 → B 反证法:证明A1ΛA2ΛA3Λ~B 是矛盾式 (永假式) 命题逻辑的归结法 建立子句集 合取范式:命题、命题和的与, 如: PΛ( P∨Q)Λ( ~P∨Q) 子句集S:合取范式形式下的子命题(元素)的集合 例:命题公式:PΛ( P∨Q)Λ( ~P∨Q) 子句集 S:S = {P, P∨Q, ~P∨Q} 命题逻辑的归结法 归结式 消除互补对,求新子句→得到归结式。 如子句:C1, C2, 归结式:R(C1, C2) = C1ΛC2 ? 注意:C1ΛC2 → R(C1, C2) , 反之不一定成立。 命题逻辑的归结法 归结过程 将命题写成合取范式 求出子句集 对子句集使用归结推理规则 归结式作为新子句参加归结 归结式为空子句□ ,S是不可满足的(矛盾),原命题成立。 ? (证明完毕) 谓词的归结:除了有量词和函数以外,其余和命题归结过程一样。 命题逻辑归结例题(1) 例题,证明公式:(P → Q) → (~Q → ~P) 证明: (1)根据归结原理,将待证明公式转化成待归结命题公式: 欲证结论的否: ~((P → Q) → (~Q → ~P)) = ~( ~(P → Q) ∨ (~Q → ~P) = (P → Q) ∧ ~(~Q → ~P) (2)分别将公式前项化为合取范式: P → Q = ~P ∨ Q 结论求~后的后项化为合取范式: ~(~Q → ~P)= ~(Q∨~P) = ~Q ∧ P 两项合并后化为合取范式: (~P ∨ Q)∧~Q ∧ P (3)则子句集为: { ~P∨Q,~Q,P} 命题逻辑归结例题(2) 子句集为: { ~P∨Q,~Q,P} (4)对子句集中的子句进行归结可得: 1.????? ~P∨Q 2.????? ~Q 3.????? P 4.????? Q, (1,3归结) 5.????? ?, (2,4归结) 由上可得原公式成立。 第三章 归结推理方法 概述 命题逻辑的归结法 谓词归结子句形 归结原理 归结过程的策略控制 Herbrand定理 第三章 归结推理方法 概述 命题逻辑的归结法 谓词归结子句形 归结原理 归结过程的策略控制 Herbrand定理 谓词归结原理基础 一阶逻辑(First-Order Logic ) 为什么需要一阶逻辑? 命题A:人都是要死的。命题B:秦始皇是人。 命题C:秦始皇是要死的。 如何有A、B推出C呢? 基本概念 个体词:表示主语的词 谓词:刻画个体性质或个体之间关系的词 量词:表示数量的词 谓词归结原理基础 小王是个工程师。 8是个自然数。 我去买花。 小丽和小华是朋友。 其中,“小王”、“工程师”、“我”、“花”、“8”、“小丽”、“小华”都是个体词,而“是个工程师”、“是个自然数”、“去买”、“是朋友”都是谓词。显然前两个谓词表示的是事物的性质,第三个谓词“去买”表示的一个动作也表示了主、宾两个个体词的关系,最后一个谓词“是朋友”表示两个个体词之间的关系。 谓词归结原理基础 一阶逻辑 公式及其解释 个体常量:a,b,c 个体变量:x,y,z 谓词符号:P,Q,R 函数符号:f, g, h 量词符号: ? ,? 谓词归结原理基础:项与原子 定义:谓词逻辑中的项(term): 常量符号是项; 变量符号是项; 若f是n元函数符号,t1, t2, …, tn是项, 则f(t1, t2, …, tn)是项; 所有项都是有限次使用(1)-(3)生成的符号串。 定义:谓词逻辑中的原子: 若P(x1, x2, …, xn)是n元谓词符号, t1, t2, …, tn是项,则P (t1, t2, …, tn)是原子。 谓词归结原理基础:公式 定义:谓词逻辑中的公式 原子是公式; 若G,H是公式,则(~G)、(G?H )、 (G ? H )、 (G ? H )、 (G ? H )是公式; 若G是公式,x 是G中的自由变量,则(?x)G,(?x)G是公式; 所有公式都是有限次使用(1)-(3)得到的符号串。 谓词归结原理基础:解释 定义:公式G的一个解释I,是由非空区域D和下列对G中的常量符号、谓词符号、函数符号的一组指定组成: 对每个常量符号,指定D中一个元素; 对每个n元函数符号,指定一个函数,即指定Dn到D的一个映射; 对每个m元谓词符号,指定一个谓词,即指定Dm到{T, F}的一个映射。 谓词归结原理基础:解释举例 给出如下两个公式: (?x)(P(f(x)) ? Q(x, f(a))). (?x)(P(x) ? Q(x, a)). 给出如下的解释I: D={1, 2} a/1, f(1)/2, f(2)/1 P(1)/F, P(2)/T, Q(1, 1)/T, Q(1,2)/T, Q(2,1)/F, Q(2,2)/T 于是公式(1)在I下取T值,公式(2)在I下取F值。 谓词归结原理基础 例如:(1)所有的人都是要死的。 (2) 有的人活到一百岁以上。 在个体域D为人类集合时,可符号化为: (1)?xP(x),其中P(x)表示x是要死的。 (2)?x Q(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 ) M(x) ? ( ? y ) ~ M(y) ~(? x ) M(x) ? ( ? y ) ~ M(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) 谓词归结子句形( Skolem 标准形) SKOLEM标准形 前束范式 定义:说公式A是一个前束范式,如果A中的一切量词都位于该公式的最左边(不含否定词),且这些量词的辖域都延伸到公式的末端。 谓词归结子句形( Skolem 标准形) 即: 把所有的量词都提到前面去,然后消掉所有量词 (Q1x1)(Q2x2)…(Qnxn)M(x1,x2,…,xn) 约束变项换名规则: (Qx ) M(x) ? (Qy ) M(y) (Qx ) M(x,z) ? (Qy ) M(y,z) 谓词归结子句形( Skolem 标准形) ? ? ? ? ? ? ? ? ? ? ? ? ? 量词消去原则: 消去存在量词“?”,略去全程量词“?”。 注意:左边有全程量词的存在量词,消去时该变量改写成为全程量词的函数;如没有,改写成为常量。 谓词归结子句形( Skolem 标准形) ? ? ? ? ? ? ? ? ? ? ? ? ? Skolem定理: 谓词逻辑的任意公式都可以化为与之等价的前束范式,但其前束范式不唯一。 SKOLEM标准形定义: 消去量词后的谓词公式。 注意:谓词公式G的SKOLEM标准形同G并不等值。 谓词归结子句形( Skolem 标准形) 例:将下式化为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)) 由此得到前述范式 谓词归结子句形( Skolem 标准形) 第五步,消去“?”(存在量词),略去“?”全称量词 消去(?y),因为它左边只有(?x),所以使用x的函数f(x)代替之,这样得到: (?x)(?z)( P(a, x, f(x)) ∧~Q(z, b)∧~R(x)) 消去(?z),同理使用g(x)代替之,这样得到: (?x) ( P(a, x, f(x)) ∧~Q(g(x), b)∧~R(x)) 则,略去全称变量,原式的Skolem标准形为: P(a, x, f(x)) ∧~Q(g(x), b)∧~R(x) 谓词归结子句形 子句与子句集 文字:不含任何连接词的谓词公式。 子句:一些文字的析取(谓词的和)。 子句集S的求取: G → SKOLEM标准形 → 消去存在变量 → 以“,”取代“Λ”,并表示为集合形式 。 谓词归结子句形 G是不可满足的? S是不可满足的 G与S不等价,但在不可满足的意义下是一致的。 定理: 若G是给定的公式,而S是相应的子句集,则G是不可满足的? S是不可满足的。 注意:G真不一定S真,而S真必有G真。 即: S ?G 例:G = (? x)P(x), S = P(a). 令G和S 的解释I如下:D={1, 2} a: 1, P(1): F, P(2): T 显然I满足G,但I弄假S。 谓词归结子句形 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不可满足 求取子句集例(1) 例:对所有的x,y,z来说,如果y是x的父亲,z又是y的父亲,则z是x的祖父。又知每个人都有父亲,试问对某个人来说谁是它的祖父? 求:用一阶逻辑表示这个问题,并建立子句集。 解:这里我们首先引入谓词: P(x, y) 表示x是y的父亲 Q(x, y) 表示x是y的祖父 ANS(x) 表示问题的解答 求取子句集例(2) 对于第一个条件,“如果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) 对于第二个条件:“每个人都有父亲”,一阶逻辑表达式: A2:(?y)(?x)P(x, y) S A2:P(f(y), y) 对于结论:某个人是它的祖父 B:(?x)(?y)Q(x, y) 否定后得到子句: ~( (?x)(?y)Q(x, y)) ∨ANS(x) S~B:~Q(x, y)∨ANS(x) 则得到的相应的子句集为:{ S A1,S A2,S~B } 第三章 归结推理方法 概述 命题逻辑的归结法 谓词归结子句形 归结原理 归结过程的策略控制 Herbrand定理 第三章 归结推理方法 概述 命题逻辑的归结法 谓词归结子句形 归结原理 归结过程的策略控制 Herbrand定理 归结原理 归结原理正确性的根本在于,找到矛盾可以肯定不真。 方法: 和命题逻辑一样。 但由于有函数,所以要考虑合一和置换。 置换 置换:可以简单的理解为是在一个谓词公式中用置换项去置换变量。 定义: 置换是形如{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, …, um/ym},是两个置换。 则?与?的合成也是一个置换,记作?·?。它是从集合 {t1·?/x1, t2·?/x2, …, tn·?/xn, u1/y1, u2/y2, …, um/ym } 中删去以下两种元素: 当yi?{x1,x2, …, xn}时,删去ui/yi (i = 1, 2, …, m) 当ti?=xi时,删去ti?/xi (i = 1, 2, …, n); 最后剩下的元素所构成的集合。 合成即是对ti先做?置换然后再做?置换,置换xi 置换的合成 例: 设:?={f(y)/x, z/y},?={a/x, b/y, y/z},求?与?的合成。 解:先求出集合 {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的结果。在该集合中,y/y满足定义中的条件i,需要删除;a/x,b/y满足定义中的条件ii,也需要删除。最后得 ?·?={f(b)/x,y/z} 合一 合一可以简单地理解为“寻找相对变量的置换,使两个谓词公式一致”。 定义:设有公式集F={F1,F2,…,Fn},若存在一个置换?,可使F1?=F2?=…= Fn?,则称?是F的一个合一。同时称F1,F2,... ,Fn是可合一的。 ?例: 设有公式集F={P(x, y, f(y)), P(a,g(x),z)},则?={a/x, g(a)/y, f(g(a))/z}是它的一个合一。 注意:一般说来,一个公式集的合一不是唯一的。 表达式集合 {F1,F2,…,Fn}的合一?称为是最一般合一(most general unigier, mgu)当且仅当对此集合的每一个合一?,都存在置换?:使得? = ? · ?。 归结原理 归结的注意事项: 谓词的一致性,P()与Q(), 不可以 常量的一致性,P(a, …)与P(b,….), 不可以 变量,P(a, ….)与P(x, …), 可以 变量与函数,P(a, x, ….)与P(x, f(x), …),不可以; 是不能同时消去两个互补对,P∨Q与~P∨~Q的空,不可以 先进行内部简化(置换、合并) 归结原理 归结的过程 写出谓词关系公式 → 用反演法写出谓词表达式→ SKOLEM标准形 → 子句集S → 对S中可归结的子句做归结 → 归结式仍放入S中,反复归结过程 → 得到空子句 ?得证 归结原理的完备性:归结式 定义:归结式:设C1,C2是两个无公共变量的两个子句,L1、L2分别是C1、C2中的两个文字。如果L1、~L2有最一般合一?,则子句 (C1 ? - L1 ? ) ? (C2 ? - L2 ?) 称为C1和C2的二元归结式, L1和L2称为归结文字。 例如: C1=P(x) ∨Q(x), C2 = ~P(a) ∨R(x)。将C2中的x改为y。取L1=P(x),L2=~P(a), ?= {a/x},于是(C1 ? - L1 ? ) ? (C2 ? - L2 ?) =Q(a) ∨R(y). 归结原理的完备性 设S是子句集,从S推出子句C的一个演绎是如下一个有限子句序列: C1,C2,…,Ck 其中Ci或者是S中的子句,或者是Cj和Cr的归结式(ji, ri);并且Ck = C. 从S推出空子句?的演绎称为一个反驳,或称为S的一个证明。 定理:如果子句集S是不可满足的,则存在从S推出空子句的归结演绎。 例题“快乐学生”问题 假设任何通过计算机考试并获奖的人都是快乐的,任何肯学习或幸运的人都可以通过所有的考试,张不肯学习但他是幸运的,任何幸运的人都能获奖。求证:张是快乐的。 ?解:先将问题用谓词表示如下: 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) 例题“快乐学生”问题 由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)? Schubert’s Steamroller Problem 1978年Alberta大学的L. Schubert教授提出了以下具有挑战性的、著名的人工智能问题[18]: 狼(wolves)、狐狸(foxes)、鸟(birds)、毛虫(caterpillars)及蛇(snails)都是动物(animals),且存在着这些动物。同时也存在着一些谷物(grains),且谷物是一种植物(plants)。每一种动物喜欢吃所有的植物或所有那些比本身小且喜欢吃某些植物的动物。毛虫和蛇比鸟小,鸟又比狐狸小,狐狸又比狼小。狼不喜欢吃狐狸和谷物,鸟喜欢吃毛虫而不喜欢吃蛇,毛虫与蛇喜欢吃某些植物。因此,有一种动物喜欢吃某种喜欢吃谷物的动物。 归结原理 归结法的实质: 归结法是仅有一条推理规则的推理方法。 归结的过程是一个语义树倒塌的过程。 归结法的问题 子句中有等号或不等号时,完备性不成立。 ※ Herbrand定理的不实用性引出了可实用的归结法。 第三章 归结推理方法 概述 命题逻辑的归结法 谓词归结子句形 归结原理 归结过程的策略控制 Herbrand定理 第三章 归结推理方法 概述 命题逻辑的归结法 谓词归结子句形 归结原理 归结过程的策略控制 Herbrand定理 归结过程的控制策略 要解决的问题: 归结方法的知识爆炸。 控制策略的目的 归结点尽量少 控制策略的原则 给出控制策略,以使仅对选择合适的子句间方可做归结。避免多余的、不必要的归结式出现。或者说,少做些归结仍能导出空子句。 控制策略的方法(1) 删除策略 = 完备 名词解释:归类:设有两个子句C和D,若有置换?使得C? ? D成立,则称子句C把子句D归类。 由于小的可以代表大的,所以小的吃掉大的了。 若对S使用归结推理过程中,当归结式Cj是重言式(永真式)和Cj被S中子句和子句集的归结式Ci(ij)所归类时,便将Cj删除。这样的推理过程便称做使用了删除策略的归结过程。 主要思想:归结过程在寻找可归结子句时,子句集中的子句越多,需要付出的代价就会越大。如果在归结时能把子句集中无用的子句删除掉,就会缩小搜索范围,减少比较次数,从而提高归结效率。删除策略对阻止不必要的归结式的产生来缩短归结过程是有效的。然而要在归结式Cj产生后方能判别它是否可被删除,这部分计算量是要花费的,只是节省了被删除的子句又生成的归结式。尽管使用删除策略的归结,少做了归结但不影响产生空子句,就是说删除策略的归结推理是完备的。 控制策略的方法(2) 采用支撑集 =完备 支撑集:设有不可满足子句集S的子集T,如果S-T是可满足的,则T是支持集。 ? 采用支撑集策略时,从开始到得到?的整个归结过程中,只选取不同时属于S-T的子句,在其间进行归结。就是说,至少有一个子句来自于支撑集T或由T导出的归结式。 ?例如:A1ΛA2ΛA3Λ~B中的~B可以作为支撑集使用。要求每一次参加归结的亲本子句中,只要应该有一个是有目标公式的否定(~B)所得到的子句或者它们的后裔。 支撑集策略的归结是完备的,同样,所有可归结的谓词公式都可以用采用支撑集策略达到加快归结速度的目的。问题是如何寻找合适的支撑集。一个最容易找到的支撑集是目标子句的非,即S~B。 控制策略的方法(3) 语义归结 = 完备 语义归结策略是将子句S按照一定的语义分成两部分,约定每部分内的子句间不允许作归结。同时还引入了文字次序,约定归结时其中的一个子句的被归结文字只能是该子句中“最大”的文字。 语义归结策略的归结是完备的,同样,所有可归结的谓词公式都可以用采用语义归结策略达到加快归结速度的目的。问题是如何寻找合适的语义分类方法,并根据其含义将子句集两个部分中的子句进行排序。 控制策略的方法(4) 线性归结 =完备 线性归结策略首先从子句集中选取一个称作顶子句的子句C0开始作归结。归结过程中所得到的归结式Ci立即同另一子句Bi进行归结得归结式Ci+1。而Bi属于S或是已出现的归结式Cj(ji)。即,如下图所示归结得到的新子句立即参加归结。 线性归结是完备的,同样,所有可归结的谓词公式都可以采用线性归结策略达到加快归结速度的目的。如果能搞找到一个较好的顶子句,可以使归结顺利进行。否则也可能事与愿违。 控制策略的方法(5) 单元归结 = 完备 单元归结策略要求在归结过程中,每次归结都有一个子句是单元子句(只含一个文字的子句)或单元因子。显而易见,词中方法可以简单地削去另一个非单子句中的一个因子,使其长度减少,构成简单化,归结效率较高。 初始子句集中没有单元子句时,单元归结策略无效。所以说“反之不成立”,即此问题不能采用单元归结策略。 控制策略的方法(6) 输入归结 = 完备 与单元归结策略相似,输入归结策略要求在归结过程中,每一次归结的两个子句中必须有一个是S的原始子句。这样可以避免归结出的不必要的新子句加入归结,造成恶性循环。可以减少不必要的归结次数。 如同单元归结策略,不是所有的可归结谓词公式的最后结论都是可以从原始子句集中的得到的。简单的例子,归结结束时,即最后一个归结式为空子句的条件是,参加归结的双方必须是两个单元子句。原始子句集中没有单元子句的谓词公式一定不能采用输入归结策略。 第三章 归结推理方法 概述 命题逻辑的归结法 谓词归结子句形 归结原理 归结过程的策略控制 Herbrand定理 第三章 归结推理方法 概述 命题逻辑的归结法 谓词归结子句形 归结原理 归结过程的策略控制 Herbrand定理 Herbrand定理 问题: 一阶逻辑公式的永真性(永假性)的判定是否能在有限步内完成? Herbrand定理 1936年图灵(Turing)和邱吉(Church)互相独立地证明了: Herbrand定理 Herbrand的思想 定义: 公式G永真:对于G的所有解释,G都为真。 思想: 寻找一个已给的公式是真的解释。然而,如果所给定的公式的确是永假的,就没有这样的解释存在,并且算法在有限步内停止。 Herbrand定理 H域 H解释 语义树 结论:Herbrand定理 Herbrand定理 H域 H解释 语义树 结论:Herbrand定理 Herbrand定理(H域) 基本方法: 因为量词是任意的,所讨论的个体变量域D是任意的,所以解释的个数是无限、不可数的 。 简化讨论域。建立一个比较简单、特殊的域,使得只要在这个论域上,该公式是不可满足的。 此域称为H域。 H域例题 设子句集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∞ 称为S的Herbrand域,简称H域。 Herbrand定理(H域) 几个基本概念 f(tn):f为子句集S中的所有函数变量。t1, t2, …tn为S的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上的真值可确定。成为可数问题。 Herbrand定理 H域 H解释 语义树 结论:Herbrand定理 Herbrand定理 H域 H解释 语义树 结论:Herbrand定理 Herbrand定理(H解释) 解释I:谓词公式G在论域D上任何一组真值的指定称为一个解释。 H解释:子句集S在的H域上的解释称为H解释。 问题: 对于所有的解释,全是假才可判定。因为所有解释代表了所有的情况,如可穷举,问题便可解决 。 Herbrand定理:H解释 定义:设S是子句集,H是S的H域,I是S在H上的一个解释。称I为S的一个H解释,如果I满足以下条件: I映射S中的每个常量符号到自身; 若f是S中n元函数符号,h1,…, hn是H中元素,则I指定映射 (h1,…, hn)?f (h1,…, hn); 由定义可以看出,S的H解释对于S中n原谓词符号的指定没有约束。 Herbrand定理:H解释 设A={A1,…, Sn, …}是S的原子集。于是S的一个H解释I可方便地表示为如下一个集合: I={m1, m2, …, mn, …} 其中 Herbrand定理:H解释 例 S={P(x) ? Q(x), R(f(y))},于是, 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)), …} 下面的解释就是S的H解释: I1={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)), …} Herbrand定理:H解释 当然,子句集S的一个解释不是必须定义在H域上,即使定义在H域上,也不一定是一个H解释: 例如S={P(x), Q(y, f(y,a))},令S的一个解释I如下: D ={1,2},a/2, f(1,1)/1, f(1,2)/2, f(2,1)/2, f(2,2)/1, P(1)/T, P(2)/F, Q(1,1)/F, Q(1,2)/F, Q(2,1)/F, Q(2,2)/T. Herbrand定理(H解释) 如下三个定理保证了归结法的正确性: 定理1: 设I是S的论域D上的解释,存在对应于I的H解释I*,使得若有SI = T,必有 SI* = T。 定理2: 子句集S是不可满足的,当且仅当S 在所有的H解释下为假。 定理3: 子句集S是不可满足的,当且仅当对每一个解释I下,至少有S的某个子句的某个基例为假。 Herbrand定理(H解释) 基例 S中某子句中所有变元符号均以S的H域中的元素代入时,所得的基子句C’称为C的一个基例。 一般来说,D是无穷不可列的,因此,子句集S也是无穷不可列的。但S确定后H是无穷可列的。不过在H上证明S的不可满足性仍然是不可能的。 解决问题的方法:语义树 Herbrand定理 H域 H解释 语义树 结论:Herbrand定理 Herbrand定理 H域 H解释 语义树 结论:Herbrand定理 Herbrand定理(语义树) 构成方法 原子集中所有元素逐层添加的一棵二叉树。将元素的是与非分别标记在两侧的分枝上(可不完全画完) 。 特点 一般情况H是可数集,S的语义树是无限树。 Herbrand定理(语义树) 设S是子句集,A是S的原子集。关于S的语义树是一个向下生长的树T,在其中每一节上都以如下方式附着A中一些原子或原子否定的有限集合: (1)对于每一个节点N,只能向下引出有限的直接的节L1, L2, …, Ln。设Qi是附着在Li上所有文字的合取i=1, …, n.则Q1? Q2 ? … ? Qn是一个恒线)对每一个节点N,设I(N)是树T由向下到节点N并包含N的一个分枝的所有节上附着文字的并集,则I(N)不包含任意的互补对。 Herbrand定理(语义树) 设A={A1,…, An, …}是子句集S的原子集。S的一个语义树是完全的,当且仅当对于语义树种每一个尖端节点N(亦即从N不再生出节的那种节点),都有I(N)包含着Ai或~Ai。 S 的任一解释都对应S的完全语义树中的一个分枝。 子句集S的一个完全语义树对应S的所有解释。 Herbrand定理(语义树) Herbrand定理(语义树) 意义 S ? H ? A ?语义树 可以理解语义树为H域的图形解释。 目的:把每个解释都摊开。语义树中包含原子集的全部元素。因此,语义树是完全的。每一个直到叶子节点的分支对应S的一个解释。可以通过对语义树每一个分支来计算S的真值。如果每个基例都为假,则可认为是不可满足的。 Herbrand定理(语义树) 几个概念 失败结点: 当(由上)延伸到点N时,I(N)已表明了S的某子句的某基例假。但N以前尚不能判断这事实。就称N为失败结点。 封闭语义树: 如果S的完全语义树的每个分枝上都有一个失败结点,就称它是一棵封闭语义树。 Herbrand定理 H域 H解释 语义树 结论:Herbrand定理 Herbrand定理 H域 H解释 语义树 结论:Herbrand定理 Herbrand定理(结论) Herbrand定理: 子句集S是不可满足的,当且仅当对应于S的完全语义树是棵有限封闭树。 子句集S是不可满足的,当且仅当存在不可满足的S的有限基例集S?。 Herbrand定理(结论) 定理的意义 Herbrand定理已将证明问题转化成了命题逻辑问题。 由此定理保证,可以放心的用机器来实现自动推理了。(归结原理) Gilmore。 注意 Herbrand定理给出了一阶逻辑的半可判定算法,即仅当被证明定理是成立时,使用该算法可以在有限步得证。而当被证定理并不成立时,使用该算法得不出任何结论。 DP算法 (1)Tautology规则:对于子句集S,删去S中的重言式后得到S?,则S不可满足当且仅当S?不可满足。 (2)单文字规则:对于单文字L,删去S中所有含有文字L的子句,若子句集为空,则S可满足;再从含有~L的子句中删去~L,若得到空子句,则S不可满足。 (3)纯文字规则:对于纯文字L,删去所有含有L的子句,若子句集为空,则S可满足。 (4)分裂规则 S=(A1 ? L)? … ? (Am ? L) ? … ? (B1 ? ~ L)? … ? (Bn ? ~ L) ?R 设S1= A1 ? … ? Am ? R, S2= B1 ? … ? Bn ? R 则S不可满足当且仅当S1、S2同时不可满足 Herbrand定理(结论) 仍存在的问题: 基例集序列元素的数目随子句基的元素数目成指数地增加。 因此,Herbrand定理是30年代提出的,始终没有显著的成绩。 ??? 直至1965年Robinson提出了归结原理。 归结原理与Herbrand定理 归结原理是语义树的一个倒塌过程 最后归结出空,就是剩一个根节点,就说明语义树是有限封闭的,证明结束。 第三章 归结推理方法 The End. 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))} P Q ~P,~Q Q R ~Q,~R R ~P ~R Q ~Q P R R ~R ~R ~R R 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))} S T 可满足 支撑集示意图 C0 C1 C2 C3 C4 C5 空 线性归结策略示意图 “没有一般的方法使得在有限步内判定一阶逻辑的公式是否是永真(或永假)。但是如果公式本身是永真(或永假)的,那么就能在有限步内判定它是永真(或永假)。对于非永真(或永假)的公式就不一定能在有限步内得到结论。判定的过程将可能是不停止的。” D域 H域 H域与D域关系示意图 《人工智能原理》第三章 归结推理方法 归结 推理 命题 逻辑 谓词逻 辑 Skolem标准形、 子句集 基本 概念 谓词逻辑 归结原理 合一和置换、 控制策略 数理 逻辑 命题逻辑 归结 Herbrand 定理 0 1 1 0 ~P P 0 0 1 0 1 0 1 1 1 0 0 0 P ? Q P Q 1 0 1 1 1 0 1 1 1 0 0 0 P ? Q P Q 1 0 1 0 1 0 1 1 1 1 0 0 P ? Q P Q 0 0 1 0 1 0 1 1 1 1 0 0 P ? Q P Q ?

http://mojdzwonek.com/tuiliziju/489.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有