《第八章 人工智能基础知识精选文档.ppt》由会员分享，可在线阅读，更多相关《第八章 人工智能基础知识精选文档.ppt（60页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第八章第八章 人工智能基人工智能基础知识础知识本讲稿第一页，共六十页2本章主要内容本章主要内容8.1 知识表示知识表示 8.2 确定性推理确定性推理8.3 不确定性推理不确定性推理 本讲稿第二页，共六十页8.1 知识表示知识表示l知识与知识表示的概念知识与知识表示的概念 l一阶谓词逻辑表示法一阶谓词逻辑表示法 l产生式表示法产生式表示法 l框架表示法框架表示法 l语义网络表示法语义网络表示法 3本讲稿第三页，共六十页4知识的概念知识的概念知识：在长期的生活及社会实践中、在科学研究及实验中知识：在长期的生活及社会实践中、在科学研究及实验中积累起来的对客观世界的认识与经验。积累起来的对客观世界的认
2、识与经验。知识：把有关知识：把有关信息关联信息关联在一起所形成的信息结构。在一起所形成的信息结构。知识反映了客观世界中事物之间的关系，不同事物或者相同知识反映了客观世界中事物之间的关系，不同事物或者相同事物间的不同关系形成了不同的知识。事物间的不同关系形成了不同的知识。信息关联形式：信息关联形式：“如果如果，则则”如果大雁向南飞，则冬天就要来临了。如果大雁向南飞，则冬天就要来临了。规则规则 事实事实例如：例如：“雪是白色的雪是白色的”。“如果头痛且流涕，则有可能患了感冒如果头痛且流涕，则有可能患了感冒”。本讲稿第四页，共六十页5知识的特性知识的特性1.相对正确性相对正确性 任何知识都是在任何知
3、识都是在一定的条件及环境一定的条件及环境下产生的，在这种条件及环境下产生的，在这种条件及环境下才是正确的。下才是正确的。1+1=2（十进制）1+1=10(二进制）2.不确定性不确定性 随机性引起的不确定性随机性引起的不确定性 模糊性引起的不确定性模糊性引起的不确定性 经验引起的不确定性经验引起的不确定性 不完全性引起的不确定性不完全性引起的不确定性知识状态：知识状态：“真真”“假假”“真真”与与“假假”之间的中间状之间的中间状态态 “如果头痛且流涕，则如果头痛且流涕，则有可能有可能患了感冒患了感冒”小李小李很高很高本讲稿第五页，共六十页6知识的特性知识的特性3.可表示性与可利用性可表示性与可利
4、用性 知知识识的的可可表表示示性性:知知识识可可以以用用适适当当形形式式表表示示出出来来，如如用用语语言言、文字、图形、神经网络等。文字、图形、神经网络等。知识的可利用性知识的可利用性:知识可以被利用。知识可以被利用。本讲稿第六页，共六十页7知识的分类知识的分类 事实性知识事实性知识：有关概念、事实、事物的属性及状态等。过程性知识过程性知识：有关系统状态变化、问题求解过程的操作、演算和行动的知识。控制性知识控制性知识（深层知识或元知识）：关于如何运用已有的知识进行问题求解的知识。糖是甜的。糖是甜的。西安是一个古老的城市。西安是一个古老的城市。一年有春、夏、秋、冬四个季节。一年有春、夏、秋、冬四
5、个季节。1.按知识按知识的作用范围的作用范围2.按知识按知识的作用及表示的作用及表示 常识性知识常识性知识：通用性知识。领域性知识领域性知识：专业性的知识。1个字节由个字节由8个个“位位”构成。构成。一个扇区有一个扇区有512个个“字节字节”的数据。的数据。本讲稿第七页，共六十页8知识的分类知识的分类 例如：从北京到上海是乘飞机还是火车的问题表示如下：事实性知识事实性知识：北京、上海、飞机、时间、费用。过程性知识过程性知识：乘飞机、坐火车。控制性知识控制性知识：乘坐飞机较快、较贵；坐火车较慢、较 便宜。2.按知识的作用及表示按知识的作用及表示本讲稿第八页，共六十页9知识的分类知识的分类 确定性
6、知识确定性知识：可指出其真值为“真”或“假”的知识，是精确性的知识。不确定性知识不确定性知识：具有不精确、不完全及模糊性等特性的知识。3.按知识的结构及表现形式按知识的结构及表现形式4.按知识的确定性按知识的确定性 逻辑性知识逻辑性知识：反映人类逻辑思维过程的知识。形象性知识：形象性知识：通过事物的形象建立起来的知识。例：例：什么是树什么是树?本讲稿第九页，共六十页10知识的表示知识的表示 知识表示知识表示（knowledgerepresentation）：将人类知识形式化或者模型化。知识表示是对知识的一种描述，或者说是一组约定，一种计算机可以接受的用于描述知识的数据结构。选择知识表示方法的原
7、则：（1）充分表示领域知识。（2）有利于对知识的利用。（3）便于对知识的组织、维护与管理。（4）便于理解与实现。本讲稿第十页，共六十页11一阶谓词逻辑知识表示方法一阶谓词逻辑知识表示方法谓词公式表示知识的步骤：谓词公式表示知识的步骤：（1）定义谓词及个体。）定义谓词及个体。（2）变元赋值。）变元赋值。（3）用连接词连接各个谓词，形成谓词公式）用连接词连接各个谓词，形成谓词公式。例例如：如：用一阶谓词逻辑表示下列关系数据库。用一阶谓词逻辑表示下列关系数据库。住户住户 房间房间 电话号码电话号码 房间房间Zhang 201 491 201Li 201 492 201Wang 202 451 202
8、Zhao 203 451 203OccupantTelephone本讲稿第十一页，共六十页用一阶谓词表示：用一阶谓词表示：Occupant（Zhang，201）Occupant（Li，201）Occupant（Wang，202）Occupant（Zhao，203）Telephone（491，201）Telephone（492，201）Telephone（451，202）Telephone（451，203）12一阶谓词逻辑知识表示方法一阶谓词逻辑知识表示方法本讲稿第十二页，共六十页13一阶谓词逻辑表示法的特点一阶谓词逻辑表示法的特点优点：优点：自然性自然性 精确性精确性 严密性严密性 容易实现容
9、易实现q 应用：应用：（1）自动问答系统（）自动问答系统（Green等人研制的等人研制的QA3系统）系统）（2）机器人行动规划系统（）机器人行动规划系统（Fikes等人研制的等人研制的STRIPS系统）系统）（3）机器博弈系统（）机器博弈系统（Filman等人研制的等人研制的FOL系统）系统）（4）问题求解系统（）问题求解系统（Kowalski等设计的等设计的PS系统）系统）局限性：局限性：不能表示不确定的知识不能表示不确定的知识 组合爆炸组合爆炸 效率低效率低本讲稿第十三页，共六十页产生式表示法产生式表示法“产产生生式式”：1943年年，美美国国数数学学家家波波斯斯特特（E.Post）首首先
10、先提出。提出。1972年年，纽纽厄厄尔尔和和西西蒙蒙在在研研究究人人类类的的认认知知模模型型中中开开发发了了基于规则的产生式系统。基于规则的产生式系统。产产生生式式通通常常用用于于表表示示事事实实、规规则则以以及及它它们们的的不不确确定定性性度量，适合于表示事实性知识和规则性知识。度量，适合于表示事实性知识和规则性知识。14本讲稿第十四页，共六十页15产生式表示法产生式表示法1.确定性规则知识的产生式表示确定性规则知识的产生式表示2.不确定性规则知识的产生式表示不确定性规则知识的产生式表示 基本形式：IFPTHEN Q 或者：例如：r4：IF动物会飞AND会下蛋THEN该动物是鸟 基本形式：I
11、FPTHENQ（置信度）或者：（置信度）例如：例如：IF 发烧发烧 THEN 感冒感冒 （0.6）本讲稿第十五页，共六十页16产生式表示法产生式表示法3.确定性事实性知识的产生式表示确定性事实性知识的产生式表示4.不确定性事实性知识的产生式表示不确定性事实性知识的产生式表示 三元组表示：（对象，属性，值）（对象，属性，值）或者：（关系，对象（关系，对象1，对象，对象2）例：老李年龄是40岁：（Li，age，40）老李和老王是朋友：（friend，Li，Wang）四元组表示：（对象，属性，值，置信度）（对象，属性，值，置信度）或者：（关系，对象（关系，对象1，对象，对象2，置信度），置信度）例：
12、老李年龄很可能是40岁：（Li，age，40，0.8）老李和老王不大可能是朋友：（friend，Li，Wang，0.1）本讲稿第十六页，共六十页17产生式表示法产生式表示法产产生生式式的的形形式式描描述述及及语语义义巴巴科科斯斯范范式式BNF（backusnormalform）:=:=|:=|:=ANDAND|OROR:=(，)符号符号“:=”表示表示“定义为定义为”；符号；符号“|”表示表示“或者是或者是”；符号；符号“”表示表示“可缺省可缺省”。本讲稿第十七页，共六十页18产生式系统的例子产生式系统的例子动物识别系统动物识别系统例如：动物识别系统例如：动物识别系统识别识别虎、金钱豹、斑马、
13、长颈鹿、鸵虎、金钱豹、斑马、长颈鹿、鸵鸟、企鹅、信天翁鸟、企鹅、信天翁等七种动物的产生式系统。等七种动物的产生式系统。本讲稿第十八页，共六十页192.3.3 产生式系统的例子产生式系统的例子动物识别系统动物识别系统规则库：规则库：r1：IF 该动物有毛发该动物有毛发 THEN 该动物是哺乳动物该动物是哺乳动物r2：IF 该动物有奶该动物有奶 THEN 该动物是哺乳动物该动物是哺乳动物r3：IF 该动物有羽毛该动物有羽毛 THEN 该动物是该动物是鸟鸟r4：IF 该动物会飞该动物会飞 AND 会下蛋会下蛋 THEN 该动物是该动物是鸟鸟r5：IF 该动物吃肉该动物吃肉 THEN 该动物是该动物是
14、食肉动物食肉动物r6：IF 该动物有犬齿该动物有犬齿 AND 有爪有爪 AND 眼盯前方眼盯前方 THEN 该动物是该动物是食肉动物食肉动物r7：IF 该动物是哺乳动物该动物是哺乳动物 AND 有蹄有蹄 THEN 该动物是该动物是有蹄类动物有蹄类动物r 8：IF 该动物是哺乳动物该动物是哺乳动物 AND 是反刍动物是反刍动物 THEN 该动物是该动物是有蹄类动物有蹄类动物本讲稿第十九页，共六十页20产生式系统的例子产生式系统的例子动物识别系统动物识别系统r9：IF 该动物是哺乳动物该动物是哺乳动物 AND 是食肉动物是食肉动物 AND 是黄褐色是黄褐色 AND 身上有暗斑点身上有暗斑点 THE
15、N 该动物是该动物是金钱豹金钱豹 r10：IF 该动物是哺乳动物该动物是哺乳动物 AND 是食肉动物是食肉动物 AND 是黄褐色是黄褐色 AND 身上有黑色条纹身上有黑色条纹 THEN 该动物是该动物是虎虎 r11：IF 该动物是有蹄类动物该动物是有蹄类动物 AND 有长脖子有长脖子 AND 有长腿有长腿 AND 身上有暗斑点身上有暗斑点 THEN 该动物是该动物是长颈鹿长颈鹿 r 12：IF 该动物有蹄类动物该动物有蹄类动物 AND 身上有黑色条纹身上有黑色条纹 THEN 该动物是该动物是斑马斑马r13：IF 该动物是鸟该动物是鸟 AND 有长脖子有长脖子 AND 有长腿有长腿 AND 不会
16、飞不会飞 AND 有黑白二色有黑白二色 THEN 该动物是该动物是鸵鸟鸵鸟r14：IF 该动物是鸟该动物是鸟 AND 会游泳会游泳 AND 不会飞不会飞 AND 有黑白二色有黑白二色 THEN 该动物是该动物是企鹅企鹅 r15：IF 该动物是鸟该动物是鸟 AND 善飞善飞 THEN 该动物是该动物是信天翁信天翁本讲稿第二十页，共六十页21产生式表示法的特点产生式表示法的特点1.产生式表示法的优点产生式表示法的优点（1）自然性）自然性（2）模）模块块性性（3）有效性）有效性（4）清晰性）清晰性2.产生式表示法的缺点产生式表示法的缺点（1）效率不高）效率不高（2）不能表达结构性知识）不能表达结构性
17、知识 3.适合产生式适合产生式表示的知识表示的知识（1）领领域域知知识识间间关关系系不不密密切切，不不存在结构关系。存在结构关系。（2）经经验验性性及及不不确确定定性性的的知知识识，且且相相关关领领域域中中对对这这些些知知识识没没有有严严格、统一的理论。格、统一的理论。（3）领领域域问问题题的的求求解解过过程程可可被被表表示示为为一一系系列列相相对对独独立立的的操操作作，且且每每个个操操作作可可被被表表示示为为一一条条或或多多条条产产生生式式规则。规则。本讲稿第二十一页，共六十页22框架表示法框架表示法1975年，美国明斯基提出了框架理论：人们对现实世界中年，美国明斯基提出了框架理论：人们对现
18、实世界中各种事物的认识都是以一种类似于框架的结构存储在记忆各种事物的认识都是以一种类似于框架的结构存储在记忆中的。中的。框架表示法：一种结构化的知识表示方法，已在多种系统中框架表示法：一种结构化的知识表示方法，已在多种系统中得到应用。得到应用。本讲稿第二十二页，共六十页23用框架表示知识的例子用框架表示知识的例子 框架名：框架名：教师教师 姓名：单位（姓、名）姓名：单位（姓、名）年龄：单位（岁）年龄：单位（岁）性别：范围（男、女）性别：范围（男、女）缺省：男缺省：男 职称：范围（教授，副教授，讲师，助教）职称：范围（教授，副教授，讲师，助教）缺省：讲师缺省：讲师 部门：单位（系，教研室）部门：
19、单位（系，教研室）住址：住址：住址框架住址框架 工资：工资：工资框架工资框架 开始工作时间：单位（年、月）开始工作时间：单位（年、月）截止时间：单位（年、月）截止时间：单位（年、月）缺省：现在缺省：现在 例例1 教师框架教师框架本讲稿第二十三页，共六十页24用框架表示知识的例子用框架表示知识的例子 框架名：框架名：教师教师-1 姓名：夏冰姓名：夏冰 年龄：年龄：36 性别：女性别：女 职称：副教授职称：副教授 部门：计算机系软件教研室部门：计算机系软件教研室 住址：住址：adr-1 工资：工资：sal-1 开始工作时间：开始工作时间：1988，9 截止时间：截止时间：1996，7 例例2 教师
20、框架教师框架当把具体的信息填入槽或侧面后，就得到了相应框架的一个事例框架。事例框架。本讲稿第二十四页，共六十页25用框架表示知识的例子用框架表示知识的例子框架名：框架名：教室教室 墙数：墙数：窗数：窗数：门数：门数：座位数：座位数：前墙：前墙：墙框架墙框架 后墙：后墙：墙框架墙框架 左墙：左墙：墙框架墙框架 右墙：右墙：墙框架墙框架 门：门：门框架门框架 窗：窗：窗框架窗框架 黑板：黑板：黑板框架黑板框架 天花板：天花板：天花板框架天花板框架 讲台：讲台：讲台框架讲台框架 例例3 教室框架教室框架本讲稿第二十五页，共六十页26用框架表示知识的例子用框架表示知识的例子例例4 将将下下列列一一则则
21、地地震震消消息息用用框框架架表表示示：“某某年年某某月月某某日日，某某地地发发生生6.0级级地地震震，若若以以膨膨胀胀注注水水孕孕震震模模式式为为标标准准，则则三三项项地地震震前前兆兆中中的的波波速速比比为为0.45，水水氡氡含含量量为为0.43，地地形形改变为改变为0.60。”解：地震消息用框架如下图所示。解：地震消息用框架如下图所示。框架名：框架名：地震地震 地地 点：某地点：某地 日日 期：某年某月某日期：某年某月某日 震震 级：级：6.0 波波 速速 比：比：0.45 水氡含量：水氡含量：0.43 地形改变：地形改变：0.60 本讲稿第二十六页，共六十页27用框架表示知识的例子用框架表
22、示知识的例子本讲稿第二十七页，共六十页28框架表示法的特点框架表示法的特点（1）结构性结构性 便便于于表表达达结结构构性性知知识识，能能够够将将知知识识的的内内部部结结构构关关系系及及知知识识间的联系表示出来。间的联系表示出来。（2）继承性）继承性 框框架架网网络络中中，下下层层框框架架可可以以继继承承上上层层框框架架的的槽槽值值，也也可可以以进进行补充和修改。行补充和修改。（3）自然性）自然性 框架表示法与人在观察事物框架表示法与人在观察事物时的思维活动是一致的。时的思维活动是一致的。本讲稿第二十八页，共六十页语义网络表示法语义网络表示法语语义义网网络络最最早早是是1968年年Quillia
23、n在在他他的的博博士士论论文文中中作作为为人人类类联想记忆的一个显式心理学联想记忆的一个显式心理学模型提出的。模型提出的。语义网络是语义网络是一种采用网络形式表示人类知识的方法一种采用网络形式表示人类知识的方法。一一个个语语义义网网络络是是一一个个带带标标识识的的有有向向图图。其其中中，带带有有标标识识的的结结点点表表示问题领域中的物体、概念、事件、动作或者态势。示问题领域中的物体、概念、事件、动作或者态势。在在语语义义网网络络知知识识表表示示中中，结结点点一一般般划划分分为为实实例例结结点点和和类类结结点点两两种种类类型型。结结点点之之间间带带有有标标识识的的有有向向弧弧表表示示结结点点之之
24、间间的的语语义义联联系系，是是语义网络组织知识的关键。语义网络组织知识的关键。29本讲稿第二十九页，共六十页30语义网络表示法示例语义网络表示法示例例例5 描述桌子的语义网络。描述桌子的语义网络。本讲稿第三十页，共六十页31语义网络表示法示例语义网络表示法示例例例6 设有下图所示动物分类网络片断，现在要求证明小贝贝是灰设有下图所示动物分类网络片断，现在要求证明小贝贝是灰色的。色的。本讲稿第三十一页，共六十页32语义网络表示法的特点语义网络表示法的特点 优点优点：（1）结结构构性性：能把事物的属性及事物间的各种语义联系显式地表示出来。（2）联联想想性性：便于以联想的方式实现对系统的检索，使之具有
25、记忆心理学中的联想特性。（3）自自然然性性：便于理解，自然语言与语义网络间的转换易实现。本讲稿第三十二页，共六十页33语义网络表示法的特点语义网络表示法的特点缺点缺点：（1）非严格性）非严格性：没有公认的形式表示体系，所表达的含义依赖于处理程序如何对它进行解释。（2）处理上的复杂性）处理上的复杂性：表示形式的不一致性导致处理复杂。本讲稿第三十三页，共六十页34第3章 确定性推理方法8.2 8.2 确定性推理方法确定性推理方法本讲稿第三十四页，共六十页35推理的基本概念推理的基本概念推理的定义推理的定义推理方式及其分类推理方式及其分类推理的方向推理的方向冲突消解策略冲突消解策略本讲稿第三十五页，
26、共六十页36医疗专家系统推理的定义推理的定义推理：推理：知识知识专家的经验、医学常识专家的经验、医学常识初始初始证据证据病人的症状、化验结果病人的症状、化验结果证据证据中间结论中间结论本讲稿第三十六页，共六十页37（1）演绎推理(deductivereasoning):一般个别三段论式（三段论法）足球运动员的身体都是强壮的；高波是一名足球运动员；所以，高波的身体是强壮的。推理方式及其分类推理方式及其分类1.演绎推理、归纳推理、默认推理演绎推理、归纳推理、默认推理（大前提）（小前提）（结 论）本讲稿第三十七页，共六十页38推理方式及其分类1.演绎推理、归纳推理、默认推理演绎推理、归纳推理、默认推
27、理（2）归纳推理(inductivereasoning):个别一般完全归纳推理（必然性推理）不完全归纳推理（非必然性推理）检查全部产品合格该厂产品合格完全归纳推理检查全部样品合格该厂产品合格不完全归纳推理本讲稿第三十八页，共六十页39推理方式及其分类1.演绎推理、归纳推理、默认推理（3）默认推理（defaultreasoning，缺省推理）n知识不完全的情况下假设某些条件已经具备所进行的推理。结 论 A 成立 B 成立？（默认B成立）鸟笼要有盖子 制造鸟笼 鸟会飞？（默认成立）本讲稿第三十九页，共六十页40推理方式及其分类推理方式及其分类 2.确定性推理、不确定性推理确定性推理、不确定性推理似
28、然推理近似推理或模糊推理不确定性推理（概率论）（模糊逻辑）（1）确定性推理：推理时所用的知识与证据都是确定的，推出的结论也是确定的，其真值或者为真或者为假。（2）不确定性推理：推理时所用的知识与证据不都是确定的，推出的结论也是不确定的。本讲稿第四十页，共六十页41X：鸟 X：会飞 X:企鹅 推理方式及其分类推理方式及其分类 3.单调推理、非单调推理单调推理、非单调推理（1）单调推理单调推理：随着推理向前推进及新知识的加入，推出的结论越来越接近最终目标。（2）非单调推理非单调推理：由于新知识的加入，不仅没有加强已推出的结论，反而要否定它，使推理退回到前面的某一步，重新开始。默认推理是非单调推理
29、基于经典逻辑的演绎推理 X：不会飞X：企鹅本讲稿第四十一页，共六十页42推理方式及其分类推理方式及其分类4启发式推理、非启发式推理启发式推理、非启发式推理 启发性知识启发性知识：与问题有关且能加快推理过程、提高搜索效率的知识。目标：在脑膜炎、肺炎、流感中选择一个 产生式规则 r1：脑膜炎 r2：肺 炎 r3：流 感 启发式知识：“脑膜炎危险”、“目前正在盛行流感”。本讲稿第四十二页，共六十页43推理的方向推理的方向本讲稿第四十三页，共六十页44冲突消解策略冲突消解策略 已知事实与知识的三种匹配情况已知事实与知识的三种匹配情况：（1）恰好匹配成功（一对一）；）恰好匹配成功（一对一）；（2）不能匹
30、配成功；）不能匹配成功；（3）多种匹配成功多种匹配成功（一对多、多对一、多对多）（一对多、多对一、多对多）冲突消解本讲稿第四十四页，共六十页45冲突消解策略多种冲突消解策略：多种冲突消解策略：（1）按针对性排序）按针对性排序（2）按已知事实的新鲜性排序）按已知事实的新鲜性排序（3）按匹配度排序）按匹配度排序（4）按条件个数排序）按条件个数排序（5）按上下文限制排序）按上下文限制排序（6）按冗余限制排序）按冗余限制排序（7）根据领域问题的特点排序）根据领域问题的特点排序r1:IF A1 AND A2 THEN H1r2:IF A1 AND A2 AND A3 AND A4 THEN H2本讲稿第
31、四十五页，共六十页46确定性推理方法确定性推理方法3.1 推理的基本概念推理的基本概念 3.2 自然演绎推理自然演绎推理 3.3 谓词公式化为子句集的方法谓词公式化为子句集的方法3.4 海伯伦定理海伯伦定理3.5 鲁宾逊归结原理鲁宾逊归结原理3.6 归结反演归结反演3.7 应用归结反演求解问题应用归结反演求解问题 本讲稿第四十六页，共六十页47自然演绎推理自然演绎推理：从一组已知为真的事实出发，运用从一组已知为真的事实出发，运用经典逻辑的经典逻辑的推理规则推理规则推出结论的过程。推出结论的过程。推理规则推理规则：P规则、规则、T规则、假言推理、拒取式推理规则、假言推理、拒取式推理 确定性推理方
32、法确定性推理方法-自然演绎推理自然演绎推理n假言推理：P,PQQn“如果x是金属，则x能导电”,“铜是金属”推出“铜能导电”n拒取式推理：PQ,QPn“如果下雨，则地下就湿”,“地上不湿”推出“没有下雨”本讲稿第四十七页，共六十页48（1）如果下雨，则地上是湿的（PQ）；（2）没有下雨（P）；（3）所以，地上不湿（Q）。确定性推理方法确定性推理方法-自然演绎推理自然演绎推理错误错误1否定前件否定前件：PQ,P Q（1）如果行星系统是以太阳为中心的，则金星会显示出位相变化（PQ）；（2）金星显示出位相变化（Q）；（3）所以，行星系统是以太阳为中心（P）。错误2肯定后件：PQ,Q P本讲稿第四十八
33、页，共六十页49确定性推理方法确定性推理方法-自然演绎推理自然演绎推理 例例1 已知事实：已知事实：（1）凡是容易的课程小王凡是容易的课程小王(Wang)都喜欢；都喜欢；（2）C 班的课程都是容易的；班的课程都是容易的；（3）ds 是是 C 班的一门课程。班的一门课程。求证：小王喜欢求证：小王喜欢 ds 这门课程。这门课程。本讲稿第四十九页，共六十页50确定性推理方法确定性推理方法-自然演绎推理自然演绎推理证明：证明：定义谓词定义谓词：EASY(x)：x是容易的 LIKE(x,y)：x喜欢 yC(x)：x 是 C班的一门课程已知事实和结论用谓词公式表示：()(EASY(x)LIKE(Wang,
34、x)()(C(x)EASY(x)C(ds)LIKE(Wang,ds)本讲稿第五十页，共六十页51确定性推理方法确定性推理方法-自然演绎推理自然演绎推理 应用推理规则进行推理：应用推理规则进行推理：()（EASY(x)LIKE(Wang,x)EASY(z)LIKE(Wang,z)全称固化()(C(x)EASY(x)C(y)EASY(y)全称固化所以 C(ds),C(y)EASY(y)EASY(ds)P规则及假言推理所以 EASY(ds),EASY(z)LIKE(Wang，z)LIKE(Wang,ds)T规则及假言推理本讲稿第五十一页，共六十页52优点优点：n表达定理证明过程自然，易理解。n拥有丰
35、富的推理规则，推理过程灵活。n便于嵌入领域启发式知识。确定性推理方法确定性推理方法-自然演绎推理自然演绎推理 缺点：易产生组合爆炸，得到的中间结论一般呈指数形式递增。本讲稿第五十二页，共六十页53确定性推理方法确定性推理方法归结演绎推理归结演绎推理反证法：，当且仅当，即Q为P的逻辑结论，当且仅当是不可满足的。定理：Q 为 ，的逻辑结论，当且仅当 是不可满足的。本讲稿第五十三页，共六十页54确定性推理方法归结演绎推理思路：定理不可满足 子句集不可满足 海伯伦定理 鲁宾逊归结原理本讲稿第五十四页，共六十页553.6归结反演应用归结原理证明定理的过程称为归结反演。用归结反演证明的步骤是：（1）将已知
36、前提表示为谓词公式F。（2）将待证明的结论表示为谓词公式Q，并否定得到Q。（3）把谓词公式集F，Q化为子句集S。（4）应用归结原理对子句集S中的子句进行归结，并把每次归结得到的归结式都并入到S中。如此反复进行，若出现了空子句，则停止归结，此时就证明了Q为真。确定性推理方法确定性推理方法归结演绎推理归结演绎推理本讲稿第五十五页，共六十页56确定性推理方法确定性推理方法归结演绎推理归结演绎推理 例12某公司招聘工作人员，A，B，C 三人应试，经面试后公司表示如下想法：（1）三人中至少录取一人。（2）如果录取A而不录取B，则一定录取C。（3）如果录取B，则一定录取C。n求证：公司一定录取C。本讲稿第
37、五十六页，共六十页57确定性推理方法归结演绎推理证明：公司的想法用谓词公式表示：。把要求证的结论用谓词公式表示出来并否定，得：（1）（2）（3）（4）把上述公式化成子句集：（1）（2）（3）（4）本讲稿第五十七页，共六十页58确定性推理方法确定性推理方法归结演绎推理归结演绎推理应用归结原理进行归结：应用归结原理进行归结：（5）（1）与（2）归结（6）（3）与（5）归结（7）（4）与（6）归结 本讲稿第五十八页，共六十页59确定性推理方法归结演绎推理 例13已知：规则1：任何人的兄弟不是女性；规则2：任何人的姐妹必是女性。事实：Mary是 Bill 的姐妹。求证：Mary不是Tom 的兄弟。证明：定义谓词brother(x,y):x 是y的兄弟sister(x,y):x是y的姐妹woman(x):x 是女性本讲稿第五十九页，共六十页60确定性推理方法归结演绎推理证明：将规则与事实用谓词公式表示：把要求证的结论用谓词公式表示出来并否定，得：把上述公式化成子句集：（1）（2）（3）（4）将子句集进行归结：本讲稿第六十页，共六十页