《谓词逻辑与归结原理课件》由会员分享，可在线阅读，更多相关《谓词逻辑与归结原理课件（140页珍藏版）》请在金锄头文库上搜索。
1、谓词逻辑与归结原理,推理,前面介绍了知识及其表示，但为了使计算机具有智能，只有知识还不够，还必须使它具有思维能力，即能运用知识进行推理，求解问题。因此，关于推理及其方法的研究就成为人工智能的一个重要研究课题 本章将介绍经典逻辑推理，包括命题逻辑推理和为此逻辑推理 下一章介绍不确定和非单调推理,人工智能,主要内容,概述 命题逻辑的归结法 谓词归结子句形 归结原理 归结过程的策略控制 Herbrand定理,人工智能,概述,什么是推理 推理方式的分类 推理的控制策略,人工智能,什么是推理,推理就是按照某种策略由已知判断推出另一判断的思维过程 一般来说，推理包括两种判断：一种是已知的判断，包括已掌握的
2、与求解问题有关的知识及关于问题的已知事实；另一种是由已知判断推出的新判断，即推理的结论 在AI系统中，推理是由程序实现的，称为推理机,人工智能,推理方式的分类,按推理途径 演绎推理：从一般到具体的推理。例：人都要吃饭，张三是人，所以张三要吃饭 归纳推理：从多个具体实例中归纳出一般性结论的推理。例：张三要吃饭，李斯要吃饭，然后得出结论：人都是要吃饭的 归纳推理可分为完全归纳和不完全归纳，大多数归纳推理是不完全归纳 缺省推理（默认推理）：在知识不完全的情况下，默认某些条件已经具备而进行的推理,人工智能,推理方式的分类,按知识的精确性 确定性推理：推理所用的知识是精确的，结论也是确定的，要么真要么假
3、 不确定性推理：推理所用的知识是不精确的，结论也不能完全肯定是否正确,人工智能,推理方式的分类,按结论是否越来越接近目标 单调推理：在推理过程中随着新知识的加入，推出的结论越来越接近最终的目标，不会由于新知识的加入而否定前面推出的结论 非单调推理：在推理过程中随着新知识的加入，不仅没有加强已推出的结论，反而要否定已有结论，使得推理回退，重新开始,人工智能,非单调推理,非单调推理多时再知识不完全的情况下发生的。由于知识不完全，要使推理进行下去，就得先做一些假设，并在假设的基础上推理，当以后由于新知识的加入而发现原假设不正确时，就要推翻该假设及以该假设为基础的推理结论，再用新知识重新推理 非单调性
4、概念是Minsky在1975年提出的，他举了“鸟会飞”的例子。 常识上大多数鸟会飞，若x是鸟，则推出“x会飞”。但若又得到一条新知识“x是企鹅”，则必须修正“x会飞”的结论,人工智能,推理的控制策略,推理方向 正向推理、逆向推理、混合推理 搜索策略 盲目搜索、启发式搜索 冲突消解策略 若同时出现多条可匹配知识时，系统必须按一定策略解决冲突，从中挑选出一条知识用于当前推理 求解策略 求单个解，还是求所有解或最优解 限制策略 为了防止无限推理及控制推理复杂性，而对推理增加的各种限制条件,人工智能,主要内容,概述 命题逻辑的归结法 谓词归结子句形 归结原理 归结过程的策略控制 Herbrand定理,
5、人工智能,归结原理,归结原理由J.A.Robinson由1965年提出。 与演绎法(deductive inference)完全不同，新的逻辑演算(inductive inference)算法。 一阶逻辑中，至今为止的最有效的半可判定的算法。即，一阶逻辑中任意恒真公式，使用归结原理，总可以在有限步内给以判定。 语义网络、框架表示、产生式规则等等都是以推理方法为前提的。即，有了规则已知条件，顺藤摸瓜找到结果。 而归结方法是自动推理、自动推导证明用的。（“数学定理机器证明”） 本课程只讨论一阶谓词逻辑描述下的归结推理方法，不涉及高阶谓词逻辑问题。,人工智能,命题逻辑的归结法,命题逻辑基础： 定义：
6、 合取式：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) r p (q r) 分配率： p(q r) (pq)(p r) ； p (
7、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,人工智能,命题例,命题：能判断真假（不是既真又假）的陈述句。 简单陈述句描述事实、事物的状态、关系等性质。 例如：1 1+1=2 2 雪是黑色的。 3 北京是中国的首都。 4 到冥王星去渡假。 判断一个句子是否是命题，有先要看它是否是陈述句，而后看它的真值是否唯一。以上的例子都是陈述句，第4句的真值现在是假，随着人类科学的发展，
8、有可能变成真，但不管怎样，真值是唯一的。因此，以上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“应届高中生，得过数学或
9、物理竞赛的一等 奖， 保送上北京大学。” 设：p，应届高中生，q，保送上北京大学上学， r，是得过数学一等奖。t，是得过物理一等奖。 则有命题公式公式：p ( r t ) q。,人工智能,命题公式的解释,解释（指派、赋值） 命题公式A中出现n个不同的命题变元P1Pn ，对这n个命题变元给定一组真值（0或1），称为这个公式的一个解释（或称为指派、赋值） 若赋值使A的真值为1（真），则称该赋值为A的成真赋值 若赋值使A的真值为0（假），则称该赋值为A的成假赋值 把命题公式A的所有赋值情况列为一个表，称为真值表,人工智能,命题逻辑的反演归结法,基本单元：简单命题（陈述句） 例： 设有命题： A1、A
10、2、A3 和 B， 要证： A1A2A3成立，则B成立， 即：要证 A1A2A3 B 永真 反证法：证明A1A2A3B 是矛盾式（永假式）,人工智能,反演归结推理方法,归结推理方法就是从A1A2A3B 出发，使用归结推理规则来寻找矛盾，最后证明A1A2A3 B 成立，这种方法可称作反演归结推理方法 反演归结推理是采用反证法思想 把结论的否定作为合取项，与前提合取，然后再证这个合取式的不可满足性，则结论B成立；若这个合取式可满足，则结论B不成立,人工智能,子句集,在命题逻辑中，命题变元及其否定统称为文字。 例：P、 P、 Q、 Q 任何文字的析取式，称为子句。 例：PQ、PQ、 PQ 不包含任何
11、文字的子句，称为空子句 空子句不含有文字 它不能被任何解释满足 空子句是永假的不可满足的 由子句构成的集合，称为子句集,人工智能,命题逻辑的归结法,为了要使用归结法证明A1A2A3B成立，首先要化成子句集的标准形式 建立子句集 首先把命题公式化为合取范式，如： P（PQ）（PQ） 然后将合取范式写成子句集，用逗号代替， 例：命题公式：P（PQ）（PQ） 写成子句集形式：S=P,PQ,PQ,人工智能,命题逻辑的归结法,定义：设有两个子句C1= PC1,C2= PC2， 则R（C1，C2）=C1C2称为子句C1，C2的归结式 即归结式是从两个子句中消去一个互补对而得到的 注1：没有互补对的两个子句
12、没有归结式 注2：一次只能消去一个互补对 例： C1= PQ,C2=PQ 则 C1，C2的归结式R（C1，C2）= QQ=T 注意 C1，C2不能归结出空子句,人工智能,归结原理（消解原理）,定理：归结式是原两个子句的逻辑推论，即C1C2R(C1,C2) ， 反之不一定成立。 即：在某种指派下，C1,C2 为真，则它们的归结式在该解释下也必为真 推论：子句集S=C1,C2 ,Cn与子句S=C,C1,C2 ,Cn的不可满足性是相同的，其中C是C1和C2的归结式,人工智能,归结过程,从子句集S出发，只对S的子句进行归结，并将所得归结式仍放入S中，再对新子句集进行归结，重复下去，直到得到空子句为止，
13、说明S是不可满足的，从而说明S对应的问题A1A2A3B不可满足（或产生矛盾），所以A1A2A3B是永真的（成立的）,人工智能,命题逻辑的归结法,归结过程 将命题写成合取范式 求出子句集 对子句集使用归结推理规则 归结式作为新子句参加归结 归结式为空子句 ，S是不可满足的（矛盾），原命题成立。 （证明完毕）,人工智能,命题逻辑归结例题（1）,例题，证明公式：(P Q) (Q P) 证明： （1）根据归结原理，将待证明公式转化成待归结命题公式： (P Q) (Q P) （2）分别将公式前项化为合取范式： P Q P Q 结论求后的后项化为合取范式： (Q P) (QP) Q P 两项合并后化为合取
14、范式： （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归结） 由上可得原公式成立。,人工智能,思考题,以下推理正确否？（用归结法证明） 若天气凉，则小王就不去游泳。天气凉，所以小王没去游泳 如果我上街，我一定去书店。我没上街，所以我没去书店 如果我上街，我一定去书店。我没去书店，所以我没上街,人工智能,人工智能,主要内容,概述 命题逻辑的归结法 谓词归结子句形 归结原理 归结过程的策略控制 Herbrand定理,人工智
15、能,谓词归结原理基础,一阶逻辑 基本概念 个体词：表示主语的词 谓词：刻画个体性质或个体之间关系的词 量词：表示数量的词,人工智能,谓词归结原理基础,小王是个工程师。 8是个自然数。 我去买花。 小丽和小华是朋友。 其中，“小王”、“工程师”、“我”、“花”、“8”、“小丽”、“小华”都是个体词，而“是个工程师”、“是个自然数”、“去买”、“是朋友”都是谓词。显然前两个谓词表示的是事物的性质，第三个谓词“去买”表示的一个动作也表示了主、宾两个个体词的关系，最后一个谓词“是朋友”表示两个个体词之间的关系。,人工智能,谓词归结原理基础,一阶逻辑 公式及其解释 个体常量：a,b,c 个体变量：x,y
16、,z 谓词符号：P,Q,R 量词符号： ,人工智能,谓词归结原理基础,例如：（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（
