华工人工智能老师上课幻灯片第三章

1、人工智能原理第三章 归结推理方法,第三章 归结推理方法,概述 命题逻辑的归结法 谓词归结子句形 归结原理 归结过程的策略控制 Herbrand定理,人工智能原理第三章 归结推理方法,人工智能原理第三章 归结推理方法,第三章 归结推理方法,概述 命题逻辑的归结法 谓词归结子句形 归结原理 归结过程的策略控制,人工智能原理第三章 归结推理方法,概述,归结原理由J.A.Robinson由1965年提出。 与演绎法(deductive inference)完全不同，新的逻辑演算(inductive inference)算法。 一阶逻辑中，至今为止的最有效的半可判定的算法。即，一阶逻辑中任意恒真公式，使用归结原理，总可以在有限步内给以判定。 语义网络、框架表示、产生式规则等等都是以推理方法为前提的。即，有了规则已知条件，顺藤摸瓜找到结果。 而归结方法是自动推理、自动推导证明用的。（“数学定理机器证明”） 本课程只讨论一阶谓词逻辑描述下的归结推理方法，不涉及高阶谓词逻辑问题。,人工智能原理第三章 归结推理方法,第三章 归结推理方法,概述 命题逻辑的归结法 谓词归结子句形 归结原理 归结过程的策略控

2、制 Herbrand定理,人工智能原理第三章 归结推理方法,第三章 归结推理方法,概述 命题逻辑的归结法 谓词归结子句形 归结原理 归结过程的策略控制 Herbrand定理,人工智能原理第三章 归结推理方法,命题例,命题：能判断真假（不是既真又假）的陈述句。 简单陈述句描述事实、事物的状态、关系等性质。 例如：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,人工智能原理第三章 归结推理

3、方法,命题表示公式（2）,例如： 1 “如果我进城我就去看你，除非我很累。” 设：p，我进城，q，去看你，r，我很累。 则有命题公式：r (p q)。 2“应届高中生，得过数学或物理竞赛的一等 奖， 保送上北京大学。” 设：p，应届高中生，q，保送上北京大学上学， r，是得过数学一等奖。t，是得过物理一等奖。 则有命题公式公式：p ( r t ) q。,人工智能原理第三章 归结推理方法,命题逻辑的归结法,命题逻辑基础： 定义： 合取式：p与q，记做p q 析取式： p或q，记做p q 蕴含式： 如果p则q，记做p q 等价式：p当且仅当q，记做p q 。,人工智能原理第三章 归结推理方法,命题逻辑基础,定义： 若A无成假赋值，则称A为重言式或永真式； 若A无成真赋值，则称A为矛盾式或永假式； 若A至少有一个成真赋值，则称A为可满足的； 析取范式：仅由有限个简单合取式组成的析取式。 合取范式：仅由有限个简单析取式组成的合取式。,人工智能原理第三章 归结推理方法,命题逻辑基础,基本等值式24个(1) 交换率：pq q p ； p q q p 结合率： (pq) r p(q r); (p q

4、) r p (q r) 分配率： p(q r) (pq)(p r) ； p (q r) (p q) (p r),人工智能原理第三章 归结推理方法,命题逻辑基础,基本等值式（1） 摩根率: (pq) p q ； (p q) p q 吸收率: p(pq ) p ； p (pq ) p 同一律: p0 p ； p1 p 蕴含等值式:p q pq 假言易位式: p q p q,人工智能原理第三章 归结推理方法,命题逻辑的归结法,基本单元：简单命题（陈述句） 例： 命题： A1、A2、A3 和 B 求证： A1A2A3成立，则B成立， 即：A1A2A3 B 反证法：证明A1A2A3B 是矛盾式 （永假式）,人工智能原理第三章 归结推理方法,命题逻辑的归结法,建立子句集 合取范式：命题、命题和的与， 如： P（ PQ）（ PQ） 子句集S：合取范式形式下的子命题（元素）的集合 例：命题公式：P（ PQ）（ PQ） 子句集 S：S = P, PQ, PQ,人工智能原理第三章 归结推理方法,命题逻辑的归结法,归结式 消除互补对，求新子句得到归结式。 如子句：C1, C2， 归结式：R(C1, C2)

5、= C1C2 注意：C1C2 R(C1, C2) ， 反之不一定成立。,人工智能原理第三章 归结推理方法,命题逻辑的归结法,归结过程 将命题写成合取范式 求出子句集 对子句集使用归结推理规则 归结式作为新子句参加归结 归结式为空子句 ，S是不可满足的（矛盾），原命题成立。 （证明完毕） 谓词的归结：除了有量词和函数以外，其余和命题归结过程一样。,人工智能原理第三章 归结推理方法,命题逻辑归结例题（1）,例题，证明公式：(P Q) (Q P) 证明： （1）根据归结原理，将待证明公式转化成待归结命题公式： (P Q) (Q P) （2）分别将公式前项化为合取范式： P Q P Q 结论求后的后项化为合取范式： (Q P) (QP) Q P 两项合并后化为合取范式： （P Q）Q P （3）则子句集为： PQ，Q，P,人工智能原理第三章 归结推理方法,命题逻辑归结例题（2）,子句集为： PQ，Q，P （4）对子句集中的子句进行归结可得： 1. PQ 2. Q 3. P 4. Q， （1，3归结） 5. ， （2，4归结） 由上可得原公式成立。,人工智能原理第三章 归结推理方法,第三章 归结

6、推理方法,概述 命题逻辑的归结法 谓词归结子句形 归结原理 归结过程的策略控制 Herbrand定理,人工智能原理第三章 归结推理方法,第三章 归结推理方法,概述 命题逻辑的归结法 谓词归结子句形 归结原理 归结过程的策略控制 Herbrand定理,人工智能原理第三章 归结推理方法,谓词归结原理基础,一阶逻辑 基本概念 个体词：表示主语的词 谓词：刻画个体性质或个体之间关系的词 量词：表示数量的词,人工智能原理第三章 归结推理方法,谓词归结原理基础,小王是个工程师。 8是个自然数。 我去买花。 小丽和小华是朋友。 其中，“小王”、“工程师”、“我”、“花”、“8”、“小丽”、“小华”都是个体词，而“是个工程师”、“是个自然数”、“去买”、“是朋友”都是谓词。显然前两个谓词表示的是事物的性质，第三个谓词“去买”表示的一个动作也表示了主、宾两个个体词的关系，最后一个谓词“是朋友”表示两个个体词之间的关系。,人工智能原理第三章 归结推理方法,谓词归结原理基础,一阶逻辑 公式及其解释 个体常量：a,b,c 个体变量：x,y,z 谓词符号：P,Q,R 量词符号： ,人工智能原理第三章 归结推理方

7、法,谓词归结原理基础,例如：（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 ）

8、 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) 第三步，变元易名，得

《华工人工智能老师上课幻灯片第三章》由会员F****n分享，可在线阅读，更多相关《华工人工智能老师上课幻灯片第三章》请在金锄头文库上搜索。