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

人工智能第三章归结推理方法

发布时间:2019-07-10 03:13 来源:未知 编辑:admin

  人工智能第三章归结推理方法_工学_高等教育_教育专区。人工智能第三章归结推理方法

  第三章 归结推理方法 ? ? ? ? ? ? 概述 命题逻辑的归结法 谓词归结子句形 归结原理 归结过程的策略控制 Herbrand定理 《人工智能原理》第三章 归结推理方法 归结 推理 命题 逻辑 谓词逻 辑 Herbrand 定理 数理 逻辑 命题逻辑 归结 基本 概念 谓词逻辑 归结原理 Skolem标准形、 子句集 合一和置换、 控制策略 《人工智能原理》第三章 归结推理方法 第三章 归结推理方法 ? ? ? ? ? 概述 命题逻辑的归结法 谓词归结子句形 归结原理 归结过程的策略控制 《人工智能原理》第三章 归结推理方法 概述 ? 归结原理由J.A.Robinson由1965年提出。 – 与演绎法(deductive inference)完全不同,新的逻辑 演算(inductive inference)算法。 – 一阶逻辑中,至今为止的最有效的半可判定的算法。 即,一阶逻辑中任意恒真公式,使用归结原理,总 可以在有限步内给以判定。 – 语义网络、框架表示、产生式规则等等都是以推理 方法为前提的。即,有了规则已知条件,顺藤摸瓜 找到结果。 而归结方法是自动推理、自动推导证明 用的。(“数学定理机器证明”) ? 本课程只讨论一阶谓词逻辑描述下的归结推理 方法,不涉及高阶谓词逻辑问题。 《人工智能原理》第三章 归结推理方法 第三章 归结推理方法 ? ? ? ? ? ? 概述 命题逻辑的归结法 谓词归结子句形 归结原理 归结过程的策略控制 Herbrand定理 《人工智能原理》第三章 归结推理方法 第三章 归结推理方法 ? ? ? ? ? ? 概述 命题逻辑的归结法 谓词归结子句形 归结原理 归结过程的策略控制 Herbrand定理 《人工智能原理》第三章 归结推理方法 3.1 命题逻辑 ? 定义 能够分辨真假的语句称作命题。 ? 定义 一个语句如果不能再进一步分解成更简 单的语句,并且又是一个命题,则称此命题为 原子命题。 ? 原子命题是命题中最基本的单位。我们一般 用P、Q、R、…大写拉丁字母表示命题,而命 题的真与假分别用“T‖与“F‖表示。 ? 用大写英文字母表示的命题既可以是一个特 定的命题,也可以是一个抽象的命题。前者称 为命题常量,后者称为命题变量。对于命题变 量而言,只有把确定的命题代入后,它才可能 有明确的逻辑值(T或F)。 《人工智能原理》第三章 归结推理方法 3.1.1 命题 ? 命题:能判断真假(不是既真又假)的陈述句。 简单陈述句描述事实、事物的状态、关系等性质。 例如:1. 1+1=2 ? 2. 雪是黑色的。 ? 3. 北京是中国的首都。 ? 4. 到冥王星去渡假。 判断一个句子是否是命题,有先要看它是否是陈述句,而后看它的 真值是否唯一。以上的例子都是陈述句,第4句的真值现在是假, 随着人类科学的发展,有可能变成真,但不管怎样,真值是唯一 的。因此,以上4个例子都是命题。 而例如:1. 快点走吧! 2. 到那去? 3. x+y10 等等句子,都不是命题。 《人工智能原理》第三章 归结推理方法 3.1.2 命题公式 ? ? ? ? ? ? ? ? ? ? ? 定义 命题公式 1. 连接词 ~:称为“非”或“否定”。 ∨:称为“析取”。 ∧:称为“合取”。 →:称为“条件”或者“蕴含”。 ?:称为“双条件”。P ? Q表示“P当且仅当Q‖。 命题公式的缺点: 无法把所描述的客观事物的结构和逻辑特征反映出来 不能把不同事物的共同特征反映出来 P:―张三是李四的老师”;仅用字母P看不出张三和李 四之间的师生关系。 《人工智能原理》第三章 归结推理方法 命题表示公式(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。 《人工智能原理》第三章 归结推理方法 命题公式的解释p79 ? 定义: ? 设公式A含有n个命题变项p,p,…,p,给p,p,…, p各指定一个值,称为对A的一个赋值或解释。若指 定的一组值使A的线,则称这组值为A的成真赋 值,若使A的真值为假,则称这组值为A的成假赋值。 – – – – – 若A无成假赋值,则称A为重言式或永真式; 若A无成真赋值,则称A为矛盾式或永假式; 若A至少有一个成真赋值,则称A为可满足的; 析取范式:仅由有限个简单合取式组成的析取式。 合取范式:仅由有限个简单析取式组成的合取式。 《人工智能原理》第三章 归结推理方法 P T T F F Q ~P T F F F T T F T 公式逻辑真值表 P∨Q T T T F P∧Q T F F F P→Q T F T T P Q T F F T 《人工智能原理》第三章 归结推理方法 求下列公式的真值表,并求成真赋值和成 假赋值: ┐p∧q)→┐r 《人工智能原理》第三章 归结推理方法 命题逻辑基础 ? 基本等值式24个 p80 ? 交换率: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) 《人工智能原理》第三章 归结推理方法 命题逻辑基础 ? 基本等值式 p80 – 摩根率: ~ (p∨q) = ~ p Λ ~ q ; ~ (p Λq) = ~ p ∨ ~ q – 吸收率: p∨(pΛq ) = p ; p Λ(p∨q ) = p – 同一律: p∨0 = p ; pΛ1 = p – 蕴含等值式:p → q = ~ p∨q – 假言易位式: p → q = ~ p → ~ q 《人工智能原理》第三章 归结推理方法 – 析取范式:仅由有限个简单合取式组成的析取式。 – 合取范式:仅由有限个简单析取式组成的合取式。 范式的性质: 析取范式是矛盾式,当且仅当每个简单合取式是矛 盾式。 合取范式是永真式,当且仅当每个简单析取式是永 真式。 《人工智能原理》第三章 归结推理方法 存在定理:任何命题公式都存在着与之等值的析 取范式和合 取范式。 求合取范式的步骤: (1)消去多余的{∨,∧}以及→联结词 (2)去掉否定~符号 (3)利用分配率 例:3.1,3.2 《人工智能原理》第三章 归结推理方法 例3.2:求的((P∨Q)→R)→P合取范式 解: ((P∨Q)→R)→P = (~(P∨Q)∨R)→P = ~ (~(P∨Q)∨R)∨P = ((P∨Q)∧~R)∨P =(P∨Q∨P)∧(~R∨P) =(P∨Q)∧(~R∨P) 《人工智能原理》第三章 归结推理方法 命题证明方法1 (自然演绎推理) ---P83 逻辑结论:对于A→B,如果永真,则称B是A的逻辑结论, 即A推出B的结论正确,A为真则B为真,记为A=B。 常用推理定律: ? 附加: A=(A∨B) ? 简化: (A∧B)=A ? 析取三段论:┓A,A∨B?B ? 假言三段论:A→B ,B→C?A→C ? 等价三段论:A? B ,B? C?A? C ? 构造性二难 :A→C ,B→D,A∨B?C∨D ? 假言推理:A→B?B ? 拒取式: ┓B ,A→B?┓A ? P84/例3.3 《人工智能原理》第三章 归结推理方法 常用的推理规则: (1)前提引入规则 (2)结论引入规则 (3)置换规则:等价的可以置换 例3.4:证明:如果今天是下雨天,则要带伞或带雨衣。如果走路上 班,则不带雨衣。今天下雨,走路上班,所以带雨伞。 解:把题目用命题公式表示: 今天下雨p, 带伞q, 带雨衣r, 走路上班s 前提: p→(q ∨r), s →~r, p, s 要证的结论: q 证明: ①p→(q ∨r)② p ③(q ∨r) ④ s ⑤s →~r ⑥~ r ⑦ q 前提引入 假言推理 前提引入 假言推理 析取三段论 《人工智能原理》第三章 归结推理方法 请用如下前提推出结论。 前提:如果马会飞或者羊吃草,则母鸡就会是飞鸟; 如果母鸡是飞鸟,那么烤熟的鸭子还会跑; 烤熟的鸭子不会跑。 结论:羊不吃草。 ? ? ? ? ? ? ? ? ? ? ? ? 解:首先进行符号化: p:马会飞 q:羊吃草 r:母鸡是飞鸟 s:烤熟的鸭子会跑 然后我们可以将前提符号化: 如果马会飞或者羊吃草,则母鸡就会是飞鸟:p∨q→r 如果母鸡是飞鸟,那么烤熟的鸭子还会跑:r→s 烤熟的鸭子不会跑: ┓s 下面,我们正式开始推理: (1)┓s 前提引入 (2)r→s 前提引入 (3)┓r 由(1)(2)根据 12.拒取式 所得 (4)p∨q→r 前提引入 (5)┓(p∨q) 由(3)(4)根据 12.拒取式 所得,注意:这 里把p∨q作为一个整体 ? (6)┓p∧┓q 德摩根定律 ? (7)┓q 由(6)根据 重言蕴含式1. 所得 ? 《人工智能原理》第三章 归结推理方法 由此我们得出了结论 ┓q:羊不吃草 什么叫归结 ? 归结式:对任意两个子句C1和C2,若C1中有一个文字 L1,而C2中有一个与L1成互补的文字L2,则分别从C1、 C2中删去L1和L2,并将其剩余部分组成新的析取式, 则称这个新子句为归结式或预解式。 ? 这里的□表示空的意思,有时用NIL表示。如果子 句集中出现了空,则表示该子句集存在矛盾,是不 可满足的。 ? 例:设两个子句C1=L∨C1′,C2=(~L)∨C2′,则 归结式C=C1′∨C2′。当C1′=C2′=□时,C=□。 《人工智能原理》第三章 归结推理方法 命题证明方法2--命题逻辑的归结 反演法 ? 基本单元:简单命题(陈述句) 归结法基本方法: 例如:命题: A1、A2、A3 和 B 求证: A1ΛA2ΛA3成立,则B成立, 即:A1ΛA2ΛA3 → B 归结反演即采用反证法(或归谬法)p85 : 证明A1ΛA2ΛA3Λ~B 是矛盾式(永假式) 《人工智能原理》第三章 归结推理方法 例:前提: p→(~(r∧s)→q), p, ~s 要证的结论: q 证明: ① p→(~(r∨s)→q) ② p ③ ~(r∨s)→q ④ ~q ⑤ (r∧s) ⑥~ s ⑦ s ⑧~ s ∧s 永假矛盾。 前提引入 假言推理 引入否定结论 拒取式 前提引入 简化⑤ ⑥ ⑦合取 《人工智能原理》第三章 归结推理方法 命题逻辑的归结法 ? 建立子句集(例如P86/3.5 3.6) ? 合取范式:命题、命题和的与, 如: PΛ( P∨Q)Λ( ~P∨Q) ? 子句集S:合取范式形式下的子命题(元 素)的集合 例:命题公式:PΛ( P∨Q)Λ( ~P∨Q) 子句集 S:S = {P, P∨Q, ~P∨Q} 《人工智能原理》第三章 归结推理方法 ? 归结式 设C1, C2是子句集中的两个子句,如果C1中的文字L1与 C2中文字L2互补,则可以从C1和 C2中分别消去文字L1 和文字L2,并将中余下的部分按析取关系构成一个新 子句C12,这个过程就叫归结。 如子句:C1=P∨Q, C2=~P∨W , 归结式: C12 = W∨Q 性质:归结式 C12 是亲本子句C1和 C2逻辑结论。 C1ΛC2 → C12 ,注意:反之不一定成立。 《人工智能原理》第三章 归结推理方法 命题逻辑的归结法 ? 归结过程 p87 – – – – – 将命题写成合取范式 求出子句集 对子句集使用归结推理规则 归结式作为新子句参加归结 归结式为空子句□ ,S是不可满足的(矛盾),原 命题成立。 ? (证明完毕) ? 谓词的归结:除了有量词和函数以外,其余和 命题归结过程一样。 《人工智能原理》第三章 归结推理方法 命题逻辑归结例题(1) ? p87例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} 《人工智能原理》第三章 归结推理方法 命题逻辑归结例题(2) 子句集为: { ~P∨Q,~Q,P} (4)对子句集中的子句进行归结可得: ? 1. ~P∨Q ? 2. ~Q ? 3. P ? 4. Q, (1,3归结) ? 5. ? , (2,4归结) 由上可得原公式成立。 《人工智能原理》第三章 归结推理方法 ? P123/3.16--1 ? P123/3.18—1,3 《人工智能原理》第三章 归结推理方法 第三章 归结推理方法 ? ? ? ? ? ? 概述 命题逻辑的归结法 谓词归结子句形 归结原理 归结过程的策略控制 Herbrand定理 《人工智能原理》第三章 归结推理方法 第三章 归结推理方法 ? ? ? ? ? ? 概述 命题逻辑的归结法 谓词归结子句形 归结原理 归结过程的策略控制 Herbrand定理 《人工智能原理》第三章 归结推理方法 3.2 谓词逻辑基础 一阶逻辑 ? 3.2.1 基本概念 – 个体词:表示主语的词 – 谓词:刻画个体性质或个体之间关系 的词 – 量词:表示数量的词 《人工智能原理》第三章 归结推理方法 谓词归结原理基础 ? 小王是个工程师。 ? 8是个自然数。 ? 我去买花。 ? 小丽和小华是朋友。 其中,“小王”、“工程师”、“我”、“花”、“8‖、 “小丽”、“小华”都是个体词,而“是个工程师”、 “是个自然数”、“去买”、“是朋友”都是谓词。 显然前两个谓词表示的是事物的性质,第三个谓词 “去买”表示的一个动作也表示了主、宾两个个体词 的关系,最后一个谓词“是朋友”表示两个个体词之 间的关系。 《人工智能原理》第三章 归结推理方法 谓词归结原理基础 3.2.2 一阶谓词逻辑 ? 公式及其解释 – 个体常量:a,b,c – 个体变量:x,y,z – 谓词符号:P,Q,R – 谓词:由谓词符号和个体(项)组成。例P(x,y) 一阶谓词:谓词中不含有谓词。 – n元谓词:就是有n个项。 – 量词符号: ? ,? 《人工智能原理》第三章 归结推理方法 谓词归结原理基础 ? 例如:(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活到一百岁以上。 《人工智能原理》第三章 归结推理方法 3.2.2一阶谓词逻辑 1谓词公式 原子公式:单个谓词就是原子公式。 谓词公式:简单说就是由原子公式、连接词、否定符号以及量 词构成的式子。 指导变量:量词后面的变量称为指导变量。?x 、?y 辖域:就是量词管辖的区域。 约束出现:在辖域内,受量词约束的变量是约束出现。 自由出现:在辖域内,不受量词约束的变量是约束出现。 换名规则:将量词辖域中某个约束出现的个体变量改成在此辖域 中未出现过的个体变量符号。 ?xP(x,y)∧R(x,y) 《人工智能原理》第三章 归结推理方法 《人工智能原理》第三章 归结推理方法 约束变元与自由变元 ? 指出下列各式量词的辖域及变元的约束 情况: ? (1)?x(F(x,y)→ G(x,z)) ? (2)?x(P(x)→?y R(x,y)) ? (3)?x(F(x)→ G(y))→ ?y(H (x)∧M(x,y,z)) 《人工智能原理》第三章 归结推理方法 ? ? ? ? ? ? ? ? ? ? 解 (1)对于?x的辖域是A=(F(x,y)→ G(x,z)),在A 中,x是约束出现的,而且约束出现两次,y,z均为自由出现, 而且各自由出现一次。 (2)对于?x的辖域是(P(x)→?y R(x,y)),?y的辖域是 R(x,y),x,y均是约束出现的。 (3)对于?x的辖域是(F(x)→ G(y)),其中x是约束出现 的,而y是自由出现的。对?y的辖域是(H(x)∧M(x,y, z)),其中y是约束出现的,而x,z是自由出现的。在整个公式 中,x约束出现一次,自由出现两次,y约束出现一次,自由出现 一次,z仅自由出现一次。 《人工智能原理》第三章 归结推理方法 替换规则:对某个自由变量用与原公式中所有个体变量 符号不同的变量去替代,且处处替代。 ?xP(x,y)∧R(x,y)替换?xP(x,z)∧R(x,z) 2.谓词公式的解释 对谓词公式的各变量常量去替代,就构成了一个谓词 公式的解释。 当存在解释能使谓词公式为真时,则称这个解释满足谓词公式。 这个解释就是这个谓词公式的模型。 两个谓词公式等价,当且仅当所有的解释下两个谓词公式的值 是相同的。 永真式 不可满足式 归结原理就是对谓词公式的正确性证明转化为不可满足性证明。 《人工智能原理》第三章 归结推理方法 ? ? ? ? ? ? ? ? ? 2.约束变元的换名与自由变元的代入 例 对公式?x(P(x)→ R(x,y))∧Q(x,y)进行换名。 解 对约束变元x换名为t后为 ?t(P(t)→ R(t,y))∧Q(x,y) 同理,对公式中的自由变元也可以更改,这种更改称作代入。自 由变元的代入规则是: (1)对于谓词公式中的自由变元,可以代入,此时需要对公式 中出现该自由变元的每一处进行代入。 (2)用以代入的变元与原公式中所有变元的名称都不能相同 《人工智能原理》第三章 归结推理方法 替换规则——将公式中的自由变项(所有出现)更换成公式 中未出现的变项。 例如: 换成 《人工智能原理》第三章 归结推理方法 ? ? (1) 解: 量词否定等值式 换名规则 量词辖域的扩张 《人工智能原理》第三章 归结推理方法 谓词公式的解释 ? P92/例子3.8 给出如下的解释I: 1. 非空个体域D={2,3} 2. D中特定的元素a=2 3. 函数f(x)为: f(2)=3, f(3)=2 4. 谓词P(x)为: P(2)=0, P(3)=1 G(x, y)为: G(i, j)=1,i, j=2,3 求出?x(P(f(x))∧G(x, f (x))在此解释下的真值 ? 解: ? B? (P(f(2)) ∧ G(2, f(2))) ∨ (P(f(3)) ∧ G(3, f(3))) ? ? (P(3) ∧G(2,3)) ∨(P(2)∧G(3,2)) ? ? (1∧1) ∨ (0∧1)? 1 ? 结论:在解释I下, ?x(P(f(x))∧G(x, f (x))为真。 《人工智能原理》第三章 归结推理方法 例子 ? ?x(F(x)∧G(x, a) 解:给出如下的解释I: 1.非空个体域D={2,3} 2. D中特定的元素a=2 3. 函数f(x)为: f(2)=3, f(3)=2 4. 谓词F(x)为: F(2)=0, F(3)=1 G(x, y)为: G(i, j)=1,i,j=2,3 ? A? (F(2)∧G(2,2))∧ (F(3)∧G(3,2)) ? ? 0∧1∧1∧0 ? ?0 ? 结论:在解释I下, ?x(F(x)∧G(x, a)为假。 《人工智能原理》第三章 归结推理方法 3.2.3谓词归结原理基础 量词否定等值式: –~(? 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 ) 谓词归结原理基础 量词辖域收缩与扩张等值式p93: –(? 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) 《人工智能原理》第三章 归结推理方法 量词扩展证明 ?x(A(x)→ B)? ?x(? A(x)∨B) ? ?x? A(x)∨ B ? ??x A(x)∨B ? ?x A(x)→ B 《人工智能原理》第三章 归结推理方法 量词分配定律。 《人工智能原理》第三章 归结推理方法 前束范式的定义 p93 定义 一个公式,如果量词均在全式的开头且它们的辖域 都延伸到整个公式的末尾,则该公式称为前束范式。 根据定义,前束范式的一般形式为: (Q1x1)(Q2x2)…(Qnxn)P(x1,x2,…,xn)。 其中, Qi (1≤i≤n) 或为 ? 或为 ?, xi 是个体变元。 没有量词的谓词公式称为平凡的前束范式。 《人工智能原理》第三章 归结推理方法 【例】 (?x)(?y)A(x, y) (?x)(?y)(?z)(A(x)?B(y, z)) A(x, y) 都是前束范式, 但 (?x)P(x)?(?x)Q(x) 不是前束范式。 定理 对于任一谓词公式,都存在着与它等价的前束范式。 证明略。 《人工智能原理》第三章 归结推理方法 将一谓词公式转换为与之等价的前束范式的步骤: 第一步:消去冗余量词且对给定的谓词公式的所有约束变元 换名,使之和所有的自由变元都不同名,但要保持自由变 元不动。 第二步:利用等价公式 (A?B) ? (A?B)∧(B?A) 及 (A?B) ? ﹁A∨B 将公式中的联结词 ? 和 ? 去掉。 《人工智能原理》第三章 归结推理方法 第三步:利用等价公式 ﹁﹁A ? A ﹁(A∨B) ? ﹁ A∧﹁B ﹁(A∧B) ? ﹁A∨﹁B ﹁(?x)P(x) ? (?x)﹁P(x) ﹁(?x)P(x) ? (?x)﹁P(x) 进行否定深入,将﹁号深入到命题变元和原子谓词公式 的前面。 第四步:将所有的量词移到全式的最前面。(量词辖域的扩张 与收缩) 《人工智能原理》第三章 归结推理方法 ? 例 求下列谓词公式的前束范式。 ? (1)?x ?y(?z A(x,z)∧A(x,z))→?t B(x,y,t) ? 解 (1)?x ?y(?z A(x,z)∧A(x,z))→ ?t B(x,y,t) ? ?﹁?x ?y(?z A(x,z)∧A(x,z))∨?t B(x,y,t) ? ??x ?y(?z﹁A(x,z)∨﹁A(x,z))∨?t B(x,y,t) ? (量词转化) ? ??x ?y(?w﹁A(x,w)∨﹁A(x,z))∨?t B(u,v,t) ? (改名及代入规则) ? ??x ?y ?w ?t(﹁A(x,w)∨﹁A(x,z)∨B(u,v,t)) ? (量词辖域扩张) 《人工智能原理》第三章 归结推理方法 【例】将公式 (?x)(?y)((?z)(P(x,z)∧P(y,z)) ? (?v)Q(x, y, v)) 化成前缀范式。 解: (?x)(?y)((?z)(P(x,z)∧P(y,z)) ? (?v)Q(z,y,v)) ?(?x)(?y)(﹁(?z)(P(x,z)∧P(y,z))∨(?v)Q(x,y,v)) ?(?x)(?y)((?z)(﹁P(x,z)∨﹁P(y,z))∨(?v)Q(x,y,v)) ?(?x)(?y)(?z)(?v)((﹁P(x,z)∨﹁P(y,z))∨Q(x,y,v)) 《人工智能原理》第三章 归结推理方法 谓词推理 ? P94/3.9 ? 谓词推理涉及量词的消去和引入。 ? (?x) P(x)==》 P(y) ? (? x) P(x)==》 P(c) ? 例:p94/3.10 《人工智能原理》第三章 归结推理方法 P94谓词推理 ? 谓词推理中除了运用命题逻辑相同的推理规则外,还 要进行量词的削去和引入。 ? P95/3.10 解:设P(x):x是20世纪70年代的漫画 Q(y):y日本漫画家的作品 a: 一幅漫画 前提 ?x(P(x) → Q(x)) ,P(a) 结论 Q(a) 证明① ?x(P(x) → Q(x)) ② P(a) ③ P(a) → Q(a) ④ Q(a) 《人工智能原理》第三章 归结推理方法 谓词推理 要运用与命题逻辑相同的推理规则和量词的消去和引入。 任意量词可以消去,用变量或常量表示,存在量词可以用 常量表示。 对于任意量词,x为自由变量,y为不在P中约束出现的 个体变量时: ?xP(x)=P(y) c为常量 ?xP(x)=P(c) 对于存在量词, ?xP(x)=P(c) 对于变量引入量词: P(y)=?xP(y) 要求y在P(y)中自由出现,且为真,x不在P(y) 中约束出现。 P(c)=?xP(x) 要求c是特定常量,取代c的x不能在P(c)中出现。 《人工智能原理》第三章 归结推理方法 3.2.4 谓词知识表示 ? 谓词可用来表示知识 ? 知识:是人们在认识、改造世界中经验的总结或者实 事的描述。 ? 使用逻辑法表示知识,将自然语言描述的知识,通过 谓词、函数加以描述,获得逻辑谓词公式,进而利用 计算机进行处理。 ? 例:校长与小李打网球。可以表示为: 定义: Play(x ,y,z)表示,x和y打z这种球 Play(zhang ,li,tennis) 清华是个大学 定义:Univ(x)表示x是大学 Univ(qinghua) 《人工智能原理》第三章 归结推理方法 常用的可以用蕴含代表规则: 人人都受法律管制: Human(x)→Lawed(x) 如果x犯罪则被惩罚 Commit(x)→Punished(x) (Human(x)→Lawed(x)) → (Commit(x)→Punished(x)) 应用谓词表示知识应用广泛: (1)易于用数据库存贮知识 (2)谓词具有完备逻辑推理方法 (3)表达的知识具有科学严密性 (4)逻辑推理具有知识的一致性 《人工智能原理》第三章 归结推理方法 3.3 谓词逻辑归结原理 3.3.1 归结原理 命题: A1、A2、A3 和 B 求证: A1ΛA2ΛA3成立,则B成立, 反证法:证明A1ΛA2ΛA3Λ~B 是矛盾式 (永假式) 3.3.2 Skolem 标准形 1.前束范式 2. Skolem 标准形 Skolem 标准形=前束范式中消去所有量词的公式 《人工智能原理》第三章 归结推理方法 谓词归结子句形( Skolem 标准形) 即: 把所有的量词都提到前面去,然 后消掉所有量词 (Q1x1)(Q2x2)…(Qnxn)M(x1,x2,…,xn) 约束变项换名规则: –(Qx ) M(x) = (Qy ) M(y) –(Qx ) M(x,z) = (Qy ) M (y,z) 《人工智能原理》第三章 归结推理方法 谓词归结子句形( Skolem 标准形) ? ? ? ? ? ? ? ? ? ? ? ? ? –量词消去原则: (1)消去存在量词“?”,用常量a,b代替。 (2)略去全程量词“?”。 注意:左边有全程量词的存在量词,消去时 该变量改写成为全程量词的函数;如没有,改 写成为常量。 《人工智能原理》第三章 归结推理方法 谓词归结子句形( Skolem 标准形) ? ? ? ? ? ? ? ? ? ? ? ? ? –Skolem定理p100: 谓词逻辑的任意公式都可以化为与之 等价的前束范式,但其前束范式不唯 一。 –SKOLEM标准形定义: 消去量词后的谓词公式。 注意:谓词公式G的SKOLEM标准形同G 并不等值。 《人工智能原理》第三章 归结推理方法 谓词归结子句形( Skolem 标准形) P100/例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)) 由此得到前束范式 《人工智能原理》第三章 归结推理方法 谓词归结子句形( Skolem 标准形) – 第五步,消去“?”(存在量词),略去“?”全 称量词 消去(?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))) 《人工智能原理》第三章 归结推理方法 3.3.3 子句与子句集 –文字:不含任何连接词的谓词公式。 –子句:一些文字的析取(谓词的和)。 –子句集S的求取: G → SKOLEM标准形 → 消去存在变量 → 以“,”取代“Λ‖,并表示为集合形 式。 《人工智能原理》第三章 归结推理方法 谓词归结子句形 ? 定理3.1 G是不可满足的= S是不可满足的 – G与S不等价,但在不可满足得意义下是一致的。 – 定理: 若G是给定的公式,而S是相应的子句集,则G是不 可满足的= S是不可满足的。 注意:G真不一定S真,而S真必有G真。 即: S = G 《人工智能原理》第三章 归结推理方法 谓词归结子句形 ? 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) P102/例3.13: 对所有的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定理 《人工智能原理》第三章 归结推理方法 归结原理 ? 归结原理正确性的根本在于,找到 矛盾可以肯定不真。 ? 方法: – 和命题逻辑一样。 – 但由于有函数,所以要考虑合一和置 换。 《人工智能原理》第三章 归结推理方法 3.3.4 置换 ? 问题的引入:~P(x) ∨Q(y)与~P(a) ∨Q(z)可否归结, 只要x取a即可。 ? 置换:可以简单的理解为是在一个谓词公式中用置换 项去置换变量。 ? 定义: 置换是形如{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· 1, t2· 2, …, tn· n, u1/y1, u2/y2, …, un/yn } ?/x ?/x ?/x 中删去以下两种元素: – 当ti?=xi时,删去ti?/xi (i = 1, 2, …, n); – 当yi?{x1,x2, …, xn}时,删去uj/yj (j = 1, 2, …, m) 最后剩下的元素所构成的集合。 合成即是对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}是它的一个合一。 注意:一般说来,一个公式集的合一不是唯一的。 《人工智能原理》第三章 归结推理方法 最一般合一: 设δ 是谓词公式集F,如果对F的任意一个合一θ 都存在一个 置换λ 使得θ =δ ·λ ,则称δ 是一个最一般的合一mgu. 最一般合一求取方法:逐一比较找出不一致,并做合一置换 算法:对于F1和F2 ①令W={F1,F2} ②令k=0,W0=W, δ 0=ε ③如果Wk已合一,停止,δ k=mgu ,,否则找不一致集Dk ④若Dk中存在元素vk和tk,其中vk不出现于tk中,转⑤,否则不可 合一 ⑤令δ k+1=δ k·{tk/vk}, Wk+1=Wk·{tk/tk} =Wδ k+1 ⑥k=k+1转③。 可证明若F1和F2可合一,算法必停于③ 《人工智能原理》第三章 归结推理方法 ? 一个公式集的最一般合一也可不唯一,如{ P (x),P(y)},{y/x}、 {x/y}都是它的最一般 合一 《人工智能原理》第三章 归结推理方法 最一般合一置换的求取算法 ? 例:设有两个谓词公式: ? E1:P(x,y,z); E2:P(x,f(a),g(b)) 分别从E1与E2的第一个符号开始逐个向右比较,此 时发现E1中的y与E2中的f(a)不同,则它们构成了 一个不一致集: D1={y,f(a)} 当继续向右比较时,又发现中E1中的z与E2中g(b)不 同,则又得到一个不一致集: D2={z,g(b)} 最一般合一置换的结果:σ={f(a)/y, g(b)/z} 例:设E1=P(a,v,f(g(y))),E2=P(z,f(a),f(u)),求E1 和 E2的最一般合一置换。 答案为:σ= {a/z ,f(a)/v,g(y)/u} 合一的其他例子p105/3.16 《人工智能原理》第三章 归结推理方法 ?说明下列文字集不能合一的理由: (1){P(f(x,x),A),P(f(y,f(y,A))A)} (2){~P(A),P(x)} (3){P(f(A),x),P(x,A)} ?答: (1){P(f(x,x),A),P(f(y,f(y,A)),A)} 在合一时,f(x,x)要与f(y,f(y,a))进行合一,x置换成 y后,y要与f(y,a)进行合一,出现了嵌套的情况,所以不 能进行合一。 ? ? (2){~P(A),P(x)} 一个是谓词P,一个是P的反,不能合一。 (3){P(f(A),x),P(x,A)} 在合一的过程中,x置换为f(A),而f(A)与A不能合 一。 《人工智能原理》第三章 归结推理方法 3.3.5 归结式 ? P106 谓词归结的注意事项: 1. 谓词的一致性,P()与Q(), 不可以归结 2. 常量的一致性,P(a, …)与P(b,….), 不可以 归结,P(a, ….)与P(x, …), 可以归结 3. 变量与函数,P(a, x, ….)与P(x, f(x), …), 不可以; 4. 是不能同时消去两个互补对,P∨Q与~P∨~Q 的空,不可以 5. 先进行内部简化(置换、合并) 《人工智能原理》第三章 归结推理方法 3.3.6 归结过程 写出谓词关系公式 →用反演法写出谓词表达 式→ SKOLEM标准形 → 子句集S →对S中可 归结的子句做归结 →归结式仍放入S中,反 复归结过程 → 得到空子句 ?得证 《人工智能原理》第三章 归结推理方法 P108/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) 《人工智能原理》第三章 归结推理方法 例题“快乐学生”问题 ? ? ? ? ? ? ? ? ? ? ? ? ? 由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) 《人工智能原理》第三章 归结推理方法 设子句集S={?P∨Q,?Q∨R,P,?R∨T }, 则其归结过程如图,归结结果为T ?P ∨Q ?P ∨R ? Q∨R P R T ? R∨T 《人工智能原理》第三章 归结推理方法 【例题 】 已知: A: (?x)((? y)(P(x,y)∧Q(y))→(? y)(R(y)∧T(x,y))) B: ~(? x)R(x)→(? x)(? y)(P(x,y)→~Q(y)) 求证:B是A的逻辑结论。 证明 首先将A和~B化为子句集 (1)~P(x,y)∨~Q(y) ∨R(f(x)) (2)~P(x,y)∨~Q(y) ∨T(x,f(x)) //(1)(2)为A (3)~R(z) (4)P(a,b) (5)Q(b) //(3)(4)(5)为B (6) ~P(x,y)∨~Q(y) (1)与(3)归结,ζ={f(x)/z} (7) ~Q(b) (4)与(6)归结,ζ={a/x,b/y} (8) NIL(空子句) (5)与(7)归结 所以B是A的逻辑结论。 《人工智能原理》第三章 归结推理方法 课堂练习 ? P123/ ? 3.19—(1)(2) ? 3.21—(1)(2) 《人工智能原理》第三章 归结推理方法 用归结方法 ? 【例题】 判断下列子句集中哪些是不可满足 的: ? {? P∨Q, ? P, ? Q, P} ? { P∨Q , ? P∨Q, P∨? ? Q, P∨? } Q ? { P(y)∨Q(y) , ? P(f(x))∨R(a)} ? {? P(x)∨Q(x) , ? P(y)∨R(y), P(a), S(a), ? S(z)∨? R(z)} ? {? P(x)∨Q(f(x),a) , ? P(h(y))∨Q(f(h(y)), a)∨? P(z)} ? {P(x)∨Q(x)∨R(x) , ? P(y)∨R(y), ? Q(a), ? R(b)} 《人工智能原理》第三章 归结推理方法 归结原理总结 ? 归结法的实质: –归结法是仅有一条推理规则的推理方法。 –归结的过程是一个语义树倒塌的过程。 ? ※ Herbrand定理的不实用性引出了可实 用的归结法。 《人工智能原理》第三章 归结推理方法 第三章 归结推理方法 ? ? ? ? ? ? 概述 命题逻辑的归结法 谓词归结子句形 归结原理 归结过程的策略控制 Herbrand定理 《人工智能原理》第三章 归结推理方法 第三章 归结推理方法 ? ? ? ? ? ? 概述 命题逻辑的归结法 谓词归结子句形 归结原理 归结过程的策略控制 Herbrand定理 《人工智能原理》第三章 归结推理方法 3.3.7 归结过程的控制策略 ? 要解决的问题: – 归结方法的知识爆炸。 ? 控制策略的目的 – 归结点尽量少 ? 控制策略的原则 – 给出控制策略,以使仅对选择合适的子 句间方可做归结。避免多余的、不必要 的归结式出现。或者说,少做些归结仍 能导出空子句。 《人工智能原理》第三章 归结推理方法 控制策略的方法(1) 删除策略 = 完备 –名词解释:归类:设有两个子句C和D,若有置 换?使得C? ? D成立,则称子句C把子句D归类。 由于小的可以代表大的,所以小的吃掉大的了。 例如:C=P(X),D=P(a)VQ(y) ?={a/x} ,C ?=P(a) ?{P(a)VQ(y)},事实上, P(a) 成立时, P(a)VQ(y)一定成立,所以小的吃掉大 的了。 《人工智能原理》第三章 归结推理方法 –删除策略 –1。含有永线。被子句集中其他子句归类的子句 《人工智能原理》第三章 归结推理方法 例子参考 现在讨论归类算法。 给了子句C,D。令 θ={a1/ ,…,an/ } 其中 ,…, 是出现于D中的所有变量。a1,…,an是C, D中未出现的常量。 设 D =L1∨…∨Lm Dθ=L1θ∨…∨Lmθ 是基子句了。 ~Dθ=~L1θ∧…∧~Lmθ 《人工智能原理》第三章 归结推理方法 ? 归类问题本是Cσ与D中部分文字合一的问题,作了 上述准备,便化成了Cσ与~Dθ的归结问题了。由于依 归类的定义,不允许D的变量做置换的,所以先将D中 元素以常量代入,为用归结法自然要将Dθ取否定。 归类算法 (1) 令W={~L1θ,…,~Lmθ} (2) 令K=0,U0={C} (3) 如果Uk包含□,停止,这时C把D归类。否则 令UR+1={ C1,C2 的归结式│ C1∈Uk, C2∈W} (4) 如果Uk+1是空集,停止,这时C不能把D归类。 否则K+1→K转(3) 《人工智能原理》第三章 归结推理方法 删除归结 ? 例: C =~P(x) ∨(Q(f(x),a) D =~P(h(y))∨(Q(f(h(y)),a)∨P(z) 使用归类算法可知C 把D归类 先作θ={b/y,c/z} Dθ=~P(h(b)) ∨Q(f(h(b)),a)∨ P(c) ~Dθ={P(h(b)),~Q(f(h(b)),a),~P(c)} (1)W={ P(h(b)),~Q(f(h(b)),a),~P(c)} (2)U0={C}={~P(x) ∨Q(f(x),a)} (3)U0不包含□,作 U1={Q(f(h(b)),a),~P(h(b))} (4)U1不空□ (5)U2含□ 从而C把D归类。 《人工智能原理》第三章 归结推理方法 控制策略的方法(2) 采用支撑集 =完备 支撑集:设有不可满足子句集S的子集T,如果S-T是可满足 的,则T是支持集。 采用支撑集策略时,从开始到得到? 的整个归结过程中, 只选取不同时属于S-T的子句,在其间进行归结。就是说, 至少有一个子句来自于支撑集T或由T导出的归结式。 例如:A1ΛA2ΛA3Λ~B中的~B可以作为支撑集使用。要 求每一次参加归结的亲本子句中,只要应该有一个是有 目标公式的否定(~B)所得到的子句或者它们的后裔。 – 支撑集策略的归结是完备的,同样,所有可归结的谓词 公式都可以用采用支撑集策略达到加快归结速度的目的。 问题是如何寻找合适的支撑集。一个最容易找到的支撑 集是目标子句的非,即S~B。参考p111/例子 《人工智能原理》第三章 归结推理方法 支撑集:设有不可满足子句集S的子集T,如果S-T是可 满足的,则T是支持集。 S T 可满足 支撑集示意图 《人工智能原理》第三章 归结推理方法 ? 想法是简单,想要证明 A1∧A2 ∧A3 →B 成立 或 A1∧A2 ∧A3 ∧~B 不可满足 分析一下出现矛盾的原因,不会在A1 , A2 ,A3 间发生,自然是出于~B的引入,于 是不必在找不到矛盾的A1 ,A2 ,A3 间做归 结了。 《人工智能原理》第三章 归结推理方法 采用支撑集 ? S={P∨Q,~P∨R,~Q∨R,~R} 取T={~R} 支持集归结过程 (1) P∨Q (2) ~P∨R (3) ~Q∨R (4) ~R (5) ~P (2)(4) (6) ~Q (3)(4) (7) Q (1)(5) (8) P (1)(6) (9) R (3)(7) (10) □ (6)(7) 这是采用了支持集策略的全面归结过程。 《人工智能原理》第三章 归结推理方法 控制策略的方法(3) 语义归结 = 完备 语义归结策略是将子句S按照一定的语义分成两部 分,约定每部分内的子句间不允许作归结。同时还引 入了文字次序,约定归结时其中的一个子句的被归结 文字只能是该子句中“最大”的文字。 语义归结策略的归结是完备的,同样,所有可归 结的谓词公式都可以用采用语义归结策略达到加快归 结速度的目的。问题是如何寻找合适的语义分类方法, 并根据其含义将子句集两个部分中的子句进行排序。 P111/例子 《人工智能原理》第三章 归结推理方法 语义归结例子(1) ? 例: S={~P∨~Q∨R,P∨R,Q∨R,~R} 我们先规定S中出现的文字的次序,如依次为P,Q, R或记作PQR。再选取S的一个解释I,如令 I={~P,~Q,~R} 用它来将S分成两个部分。规定在I下为假的子句放 入S1中,在I下为线;={P∨R,Q∨R} S2={~P∨~Q∨R,~R} 规定S1内部的子句不允许归结,S1与S2子句间的归 结必须是S 中的最大文字方可进行。这样所得的归结 式,仍按I来放入S 或S2。 《人工智能原理》第三章 归结推理方法 语义归结例子(2) ? 归结过程 (1) ~P∨~Q∨ R ∈S2 (2) P∨R ∈S1 (3) Q∨R ∈S1 (4) ~R ∈S2 (5) ~Q∨R (2)(1)归结 ∈S2 (6) ~P∨R (3)(1)归结 ∈S2 (7) R (2)(6)归结 ∈S1 (8) R (3)(5)归结 ∈S1 (9) □ (7)(4)归结 《人工智能原理》第三章 归结推理方法 控制策略的方法(4) 线性归结 =完备 线性归结策略首先从子句集中选取一个称作顶子 句的子句C0开始作归结。归结过程中所得到的归结式 Ci立即同另一子句Bi进行归结得归结式Ci+1。而Bi属于S 或是已出现的归结式Cj(ji)。即,如下图所示归结得 到的新子句立即参加归结。 线性归结是完备的,同样,所有可归结的谓词公 式都可以采用线性归结策略达到加快归结速度的目的。 如果能搞找到一个较好的顶子句,可以式归结顺利进 行。否则也可能事与愿违。 《人工智能原理》第三章 归结推理方法 C0 B0 B1 Bn C1 C2 空 线性归结策略示意图 《人工智能原理》第三章 归结推理方法 线性归结例子 ? S={P∨Q ,~P∨Q,P∨~Q,~P∨~Q} 选取顶子句C0=P∨Q。 线) ~P∨~Q (5) Q (1)(2) (6) P (5)(3) (7) ~Q (6)(4) (8) □ (7)(5) 顶子句的选择直接影响着归结的效率。如可选得C0 使S-{C0}是可满足的。 《人工智能原理》第三章 归结推理方法 控制策略的方法(5) 单元归结 = 完备 单元归结策略要求在归结过程中,每次归结都 有一个子句是单元子句(只含一个文字的子句) 或单元因子。显而易见,词中方法可以简单地削 去另一个非单子句中的一个因子,使其长度减少, 构成简单化,归结效率较高。 初始子句集中没有单元子句时,单元归结策略 无效。所以说“反之不成立”,即此问题不能采 用单元归结策略。 《人工智能原理》第三章 归结推理方法 单元归结例子 ? S={P∨Q ,~P∨R,~Q∨ R,~R} 单元归结过程 (1) P∨Q (2) ~P∨R (3) ~Q∨R (4) ~R (5) ~P (4)(2) (6) ~Q (4)(3) (7) Q (5)(1) (8) P (6)(1) (9) R (7)(3) (10) □ (7)(6) 在归结过程中,对两子句所做的每一次归 结,其中必须有一个是S的子句时,便称作输入归结。这种归结 也是效率较高的。 单元归结与输入归结是一致的。即有从S到□的输入归结的 充分必要条件是有从S到□的单元归结。它们都是不完备的归结 方法。 《人工智能原理》第三章 归结推理方法 控制策略的方法(6) 输入归结 = 完备 与单元归结策略相似,输入归结策略要求在归 结过程中,每一次归结的两个子句中必须有一个是S 的原始子句。这样可以避免归结出的不必要的新子 句加入归结,造成恶性循环。可以减少不必要的归 结次数。 如同单元归结策略,不是所有的可归结谓词公 式的最后结论都是可以从原始子句集中的得到的。 简单的例子,归结结束时,即最后一个归结式为空 子句的条件是,参加归结的双方必须是两个单元子 句。原始子句集中没有单元子句的谓词公式一定不 能采用输入归结策略。 《人工智能原理》第三章 归结推理方法 输入归结例子 ? S={P∨Q ,~P∨R,~Q∨ R,~R} 输入归结过程 (1) P∨Q (2) ~P∨R (3) ~Q∨R (4) ~R (5) Q∨R (1)(2) (6) R (3)(5) (7) □ (4)(6) 前两个例子的子句集是相同的,分别采用了单元 归结和输入归结的推理过程。 《人工智能原理》第三章 归结推理方法 用归结反演求取问题的答案(1/4) ? ? ? ? ? ? 归结原理出了可用于定理证明外,还可用来求取问题答案, 其思想与定理证明相似。其一般步骤为: (1) 把问题的已知条件用谓词公式表示出来,并化为相应的子 句集; (2) 把问题的目标的否定用谓词公式表示出来,并化为子句集; (3) 对目标否定子句集中的每个子句,构造该子句的重言式 (即把该目标否定子句和此目标否定子句的否定之间再进行析取 所得到的子句),用这些重言式代替相应的目标否定子句式,并 把这些重言式加入到前提子句集中,得到一个新的子句集; (4) 对这个新的子句集,应用归结原理求出其证明树,这时证 明树的根子句不为空,称这个证明树为修改的证明树; (5) 用修改证明树的根子句作为回答语句,则答案就在此根子 句中。 《人工智能原理》第三章 归结推理方法 用归结反演求取问题的答案(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) 《人工智能原理》第三章 归结推理方法 用归结反演求取问题的答案(3/4) ? 把上述公式化为子句集: ? C(zhang, li) ? ﹁C(x, y)∨﹁At(x, u)∨At(y, u) ? At(zhang, 302) ? 把目标的否定化成子句式,并用重言式 ? ﹁At(li,v) ∨ANS(v)代替之。 ? 把此重言式加入前提子句集中,得到一个新的 子句集,对这个新的子句集,应用归结原理求出 其证明树。其求解过程如下图所示。 ? 该证明树的根子句就是所求的答案,即“李明 在302教室”。 《人工智能原理》第三章 归结推理方法 用归结反演求取问题的答案(4/4) ﹁At(li,v)∨ ANS( v) {li/y,v/u} ANS( v) ∨﹁ C(x, li)∨﹁At(x, v) ﹁C(x, y)∨﹁At(x, u)∨At(y, u) C(zhang, li) {Zhang/x} ﹁ At(zhang,v)∨ANS( v) {302/v} ANS(302) At(zhang, 302) 《人工智能原理》第三章 归结推理方法 ? 假设张被盗,公安局派出5个人去调查。案情 分析时,侦查员A说:“赵与钱中至少有一个 人作案”,侦查员B说:“钱与孙中至少有一 个人作案”,侦查员C说:“孙与李中至少有 一个人作案”,侦查员D说:“赵与孙中至少 有一个人与此案无关”,侦查员E说:“钱与 李中至少有一个人与此案无关”。如果这5个 侦察员的话都是可信的,使用归结演绎推理求 出谁是盗窃犯。 《人工智能原理》第三章 归结推理方法 第三章 归结推理方法 ? ? ? ? ? ? 概述 命题逻辑的归结法 谓词归结子句形 归结原理 归结过程的策略控制 Herbrand定理 《人工智能原理》第三章 归结推理方法 第三章 归结推理方法 ? ? ? ? ? ? 概述 命题逻辑的归结法 谓词归结子句形 归结原理 归结过程的策略控制 Herbrand定理 《人工智能原理》第三章 归结推理方法 3.4 Herbrand定理 ?问题: 一阶逻辑公式的永真性 (永假性)的判定是否 能在有限步内完成? 《人工智能原理》第三章 归结推理方法 Herbrand定理 ? 1936年图灵(Turing)和邱吉(Church)互相 独立地证明了: ―没有一般的方法使得在有限步内判定一阶逻 辑的公式是否是永真(或永假)。但是如果公 式本身是永真(或永假)的,那么就能在有限 步内判定它是永真(或永假)。对于非永真 (或永假)的公式就不一定能在有限步内得到 结论。判定的过程将可能是不停止的。” 《人工智能原理》第三章 归结推理方法 Herbrand定理 ? Herbrand的思想 – 定义: 公式G永真:对于G的所有解释,G都为真。 – 思想: 寻找一个已给的公式是真的解释。然而,如 果所给定的公式的确是永假的,就没有这样 的解释存在,并且算法在有限步内停止。 《人工智能原理》第三章 归结推理方法 Herbrand定理 ? H域 ? H解释 ? 语义树 ? 结论:Herbrand定理 《人工智能原理》第三章 归结推理方法 Herbrand定理 ? H域 ? H解释 ? 语义树 ? 结论:Herbrand定理 《人工智能原理》第三章 归结推理方法 Herbrand定理(H域) ? 基本方法: – 因为量词是任意的,所讨论的个体变量域D 是任意的,所以解释的个数是无限、不可数 的。 – 简化讨论域。建立一个比较简单、特殊的域, 使得只要在这个论域上,该公式是不可满足 的。 H i ? H i ?1 ? { f (t1 ,...,t n )} – 此域称为H域。 《人工智能原理》第三章 归结推理方法 D域 H域 H域与D域关系示意图 《人工智能原理》第三章 归结推理方法 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,a),f(a,b)), f(f(a,a),f(a,a)), f(f(a,a), f(b,a)), f(f(b,a),f(a,b)), f(f(b,a),f(a,a)), f(f(b,a), f(b,a)), f(f(b,b),f(a,b)), f(f(b,b),f(a,a)), f(f(b,b), f(b,a)), ? ……… ? H∞ = H1∪H2∪H3……… f(f(a,b), f(f(a,a), f(f(b,a), f(f(b,b), f(b,b)), f(b,b)), f(b,b)), f(b,b))} 《人工智能原理》第三章 归结推理方法 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解释) ? 如下三个定理保证了归结法的正确性: – 定理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的语义树是无 限树。 《人工智能原理》第三章 归结推理方法 N0 P(a) ~P(a) N11 Q(a) ~Q(a) N12 Q(a) ~Q(a) N21 P(f(a)) ~P(f(a)) N24 N31 无限语义树 N38 S={~P(x)∨Q(x),P(f(y)),~Q(f(y))} 《人工智能原理》第三章 归结推理方法 Herbrand定理(语义树) ? 意义 – S ? H ? A ?语义树 –可以理解语义树为H域的图形解释。 目的:把每个解释都摊开。语义树中包 含原子集的全部元素。因此,语义树是 完全的。每一个直到叶子节点的分支对 应S的一个解释。可以通过对语义树每一 个分支来计算S的真值。如果每个基例都 为假,则可认为是不可满足的。 《人工智能原理》第三章 归结推理方法 Herbrand定理(语义树) ? 几个概念 –失败结点: 当(由上)延伸到点N时,I(N)已表明了S的某 子句的某基例假。但N以前尚不能判断这事实。 就称N为失败结点。 –封闭语义树: 如果S的完全语义树的每个分枝上都有一个失 败结点,就称它是一棵封闭语义树。 《人工智能原理》第三章 归结推理方法 N0 P(a) Q(a) N1,1 N2,2 N1,2 N2,4 P(f(a)) N2,1 Q(f(a)) N3,1 N3,2 N3,6 N4,9 封闭语义树 N4,10 N4,13 N4,14 N3,8 N4,1 N4,2 S={~P(x)∨Q(x),P(f(y)),~Q(f(y))} 《人工智能原理》第三章 归结推理方法 Herbrand定理 ? H域 ? H解释 ? 语义树 ? 结论:Herbrand定理 《人工智能原理》第三章 归结推理方法 Herbrand定理 ? H域 ? H解释 ? 语义树 ? 结论:Herbrand定理 《人工智能原理》第三章 归结推理方法 Herbrand定理(结论) Herbrand定理: 1. 子句集S是不可满足的,当且仅当对应 于S的完全语义数是棵有限封闭树。 2. 子句集S是不可满足的,当且仅当存在 不可满足的S的有限基例集。 《人工智能原理》第三章 归结推理方法 Herbrand定理(结论) ? 定理的意义 –Herbrand定理已将证明问题转化成了命题逻辑问题。 –由此定理保证,可以放心的用机器来实现自动推理 了。(归结原理) ? 注意 –Herbrand定理给出了一阶逻辑的半可判定算法,即 仅当被证明定理是成立时,使用该算法可以在有限 步得证。而当被证定理并不成立时,使用该算法得 不出任何结论。 但是 ? ? ? ? ? ? ? ? ? ? ? ? ? 《人工智能原理》第三章 归结推理方法 Herbrand定理(结论) ? 仍存在的问题: 基例集序列元素的数目随子句基的元素数目成 指数地增加。 ? 因此,Herbrand定理是30年代提出的, 始终没有显著的成绩。 ??? 直至1965年Robinson提出了归结原理。 《人工智能原理》第三章 归结推理方法 归结原理与Herbrand定理 ? 归结原理是语义树的一个倒塌过 程 ? 最后归结出空,就是剩一个根节 点,就说明语义树是有限封闭的, 证明结束。 《人工智能原理》第三章 归结推理方法 ? 问题22: 什么是置换?置换是可交换的吗? 回答: 通常用有序对的集合s={t1/v1,t2/v2,…,tn/vn}来表示任一置换, 置换集的元素ti/vi的含义是表达式中的变量vi处处以项ti来替换,用s对表达 式E作置换后的例简记为Es。 一般来说,置换是不可交换的,即两个置换合成的结果与置换使用的次序 有关。 ? 问题23: 什么是合一?什么是合一者? 回答: 若存在一个置换s使得表达式集{Ei}中每个元素经置换后的例有: E1s=E2s=E3s=…,则称表达式集{Ei}是可合一的,这个置换s称作{Ei}的 合一者。 ? 问题24: 什么是归结? 回答: 对于子句C1∨L1和C2∨L2,其中L1、L2是单文字。如果L1与~L2 可合一,且s是其合一者,则(C1∨C2)s是其归结式。这一过程称作归结。 ? 问题25: 简述用归结法证明定理的过程。 回答: (1)将已知条件化作子句集;(2)将结论的否定化作子句集; (3)从所有子句集中选取两个可归结的子句进行归结;(4)重复过程 (3),直到出现空子句NIL为止。这时,就证明了在所给已知条件下结论 成立。 ? 问题26: 简述基于归结法的问题提取回答:的过程。 回答: (1)首先用归结法证明结论成立,并画出归结树;(2)找出结论 的否定所对应的子句s在归结树中的位置,用重言式s ~s代替s,并参予归结 树中所有的置换,得到修改证明树;(3)在原来归结树中空子句所在位置 得到一个子句,该子句即为问题的回答:。 《人工智能原理》第三章 归结推理方法 ? 问题27: 简述基于规则的正向演绎系统的使用条件 回答: (1)事实表达式是任意形式; (2)规则形式为: L→W 或L1∨L2→W 其中L为单文字,W为任意形式。 (3)目标公式为文字析取形。 ? 问题28: 简述基于规则的逆向演绎系统的使用条件 回答: (1)事实表达式是文字合取形式 (2)规则形式为: W→L 或W→L1∧L2 其中L为单文字,W为任意形式。 (3)目标公式是任意形式 ? 问题29: 简述基于规则的正向演绎系统对事实、规则和目标的化简 过程。 回答: (1)用Skolem函数消去事实表达式中的存在量词,化简 的公式受全称量词的约束 (2)对规则的处理同(1) (3)用Skolem函数(对偶形)消去目标公式中的全称量词,化 简的公式受存在量词约束 《人工智能原理》第三章 归结推理方法 第三章 归结推理方法 The End. 《人工智能原理》第三章 归结推理方法

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