高级人工智能PPT课件 第3章 基于谓词逻辑的机器推理

《高级人工智能PPT课件 第3章 基于谓词逻辑的机器推理》由会员分享，可在线阅读，更多相关《高级人工智能PPT课件 第3章 基于谓词逻辑的机器推理（137页珍藏版）》请在金锄头文库上搜索。

1、*1 第3章 基于谓词逻辑谓词逻辑 的机器推理 *2 内容 3.1 机器推理概述 3.2 谓词逻辑简 介 3.3 自然演绎推理 3.4 归结演绎推理 3.5 归结原理与PROLOG程序 3.6 基于规则的演绎推理 *3 3.1 机器推理概述（1） n 机器推理 推理是人脑的一个基本功能和重要功能，几乎所有的 人工智能领域都与推理有关。因此，要实现人工智能， 就必须将推理的功能赋予机器，实现机器推理。机器推 理也称为是计算机推理，或自动推理，它也是人工智能 的核心课题之一。 n自动定理证明： 是机器推理的一种重要应用，它是利用计算机证明非 数值性的结果，很多非数值领域的任务如医疗诊断、信 息检索

2、、规划制定和难题求解等方法都可以转化一个定 理证明问题。 *4 n自动定理证明的基本方法： 3.1 机器推理概述（2） 定理证明器：它是研究一切可判定问题的证明方法。 鲁滨逊 的归结原理。 自然演绎法：该方法依据推理规则从前提和公理中可 以推出许多定理，如果待证明的定理在其中则定理得 证。证明平面几何的程序。 *5 n基于归结归结 原理的自动动定理证证明过过程： 3.1 机器推理概述（3） 定理的自然语语言描述 定理的谓词谓词 公式描 述 子句集 生成子句集 定理得证证 应应用归结规则归结规则 和归结归结 策 略 自然语语言处处理生成谓词谓词 公 式 已知前提： F1：自然数都是大于零的整数。

3、 F2：所有整数不是偶数就是奇数。 F3：偶数除以2是整数。 结论结论 G：所有自然数不是奇数就是 一半为为整数的数。 定理的谓词谓词 公式描述： F1: x (N(x)GZ(x) I(x) F2: x (I(x)(E(x) O(x) F3: x (E(x) I(s(x) G: x (N(x)(I(s(x) O(x) 3.1 机器推理概述（4） *6 n 基于规则规则 的演绎绎推理 把已知判断中的知识表示成规则的形式（包括F-规 则和B-规则），运用规则从已知判断的事实或待证明 的结论出发进行推理的过程 . 3.2 谓词逻辑简谓词逻辑简 介 n3.2.1 基于命题逻辑 的知识表示 n3.2.2

4、 谓词逻辑 n3.2.3 基于谓词逻辑 的知识表示 *7 *8 3.2.1 基于命题逻辑题逻辑 的知识识表示（1） 命题题（proposition）：是具有真假意义义的语语句。命题题代表人 们进们进 行思维时维时 的一种判断，或者是否定，或者是肯定。 命题题可以用命题题符号表示。 用命题题符号可以表示简单简单 的逻辑逻辑 关系和推理。 P:今天天气好 Q:去旅游 S1：我有名字 S2：你有名字 PQ表示：如果今天天气好，就去旅游。 此时时，如果P（今天天气好）成立，则则可以得到结论结论 Q（去旅游） *9 3.2.1 基于命题逻辑题逻辑 的知识识表示（2） n对于复杂的知识，命题符号能力不够。

5、 n无法把所描述的客观事物的结构及逻辑特征反映出 来。 n无法把不同事物间的共同特征表达出来。 F：老李是小李的父亲。 S1：我有名字 S2：你有名字 所有的人都有名字： SIS2 S3 *10 3.2.2 谓词逻辑谓词逻辑 （1） 谓词(predicate)：一般形式为P（x1, x2 , xn ） P为谓词名，用于刻画个体的性质、状态 或个体间的关系。 x1， x2 ， xn是个体，表示某个独立存 在的事物或者某个抽象的概念。 S(x): x是学生； P(x,y): x是y的父亲。 个体变变元的变变化范围围称为为个体域。 包揽揽一切事物的集合称为为全总总个体域。 *11 3.2.2 谓词逻

6、辑谓词逻辑 （2） n函数：为了表达个体之间的对应关系，引入 数学中函数概念和记法。用形如f(x1，x2， ，xn)来表示个体变元对应的个体y，并称之为 n元个体函数，简称函数。 函数 father(x): 值为值为 x的父亲亲。 谓词谓词 D(father(Li):表示x的父亲亲是医生，值为值为 真或假。 *12 3.2.2 谓词逻辑谓词逻辑 （3） n为了表示命题中出现的“全部”、“所有”、“一切” 、“任一”或“凡是”等意义，引入全称量词，记 为x 。 n为了表示命题中出现的“存在”、“某些”、“有一 个”等意义，引入存在量词，记为x 。 如：“某些学生对某些课外活动感兴趣” S(x)表

7、示x是学生，L(y)表示y是课外活动， I(x,y)表示x对y感兴趣。 *13 3.2.2 谓词逻辑谓词逻辑 （4） 定义义3.2：项项 （1）个体常元和变变元都是项项。 （2）f是n元函数符号，若t1，t2，tn是项项，则则 f（ t1，t2， tn ）是项项。 （3）只有有限次使用（1），（2）得到的符号串才是项项。 *14 3.2.2 谓词逻辑谓词逻辑 （5） 定义义3.3：原子公式 设设P为为n元谓词谓词 符号， t1，t2，tn为项为项 ， P（t1，t2，tn）称为为原子谓词谓词 公式，简简称原子或原 子公式。 *15 3.2.2 谓词逻辑谓词逻辑 （6） 定义义3.4：谓词谓词

8、公式 （1）原子公式是谓词谓词 公式。 （2）若A、B是谓词谓词 公式，则则 A，A B，A B，A B， AB， xA， xA也是谓词谓词 公式。 （3）只有有限步应应用（1）（2）生成的公式才是谓词谓词 公式。 谓词谓词 公式亦称为谓词逻辑为谓词逻辑 中的合适（式）公式，记为记为 Wff。 符号约约定：谓词谓词 大写字母； P(x,y) 函数小写字母；f(x) 变变量 x、y、z、u、v； 常量a、b、c.。 P(a,y) *16 3.2.2 谓词逻辑谓词逻辑 （7） n辖域：紧接于量词之后被量词作用（即说明 ）的谓词公式称为该量词的辖域。 n指导变量：量词后的变量为指导变量。 n约束变量

9、：在一个量词辖域中与该量词的指 导变元相同的变量称为约束变量。 n自由变量：谓词公式中除了约束变量之外的 变量。 （1） （2） （3） *17 3.2.2 谓词逻辑谓词逻辑 （8） n一个变元在一个公式中既可以约束出现，也可 以自由出现，为了避免混淆，通过改名规则 改名： n对需要改名的变元，应同时更改该变元在量词及 其辖域中的所有出现。 n新变元符号必须是量词辖域内原先没有的，最好是 公式中也未出现过的。 x G(x) P（x） x G(x) P（y） *18 3.2.2 谓词逻辑谓词逻辑 （9） n谓词公式与命题的区别与联系 n谓词公式是命题函数。 n一个谓词公式中所有个体变元被量化，谓

10、词公式 就变成了一个命题。 n从谓词公式得到命题的两种方法：给谓词 中的个 体变元代入个体常元；把谓词中的个体变元全部量 化。 例：P（x）表示“x是素数” x P（x）， x P（x）， P（a）都是命题题 *19 3.2.2 谓词逻辑谓词逻辑 （10） n全称命题： x P(x)等价于P (a1)P(a2) P(an) n特称命题 x P(x)等价于P (a1)P(a2) P (an) n一阶谓词 ：仅个体变元被量化的谓词。 n二阶谓词 ：个体变元被量化，函数符号和谓 词符号也被量化。 P x P（x） *20 3.2.2 谓词逻辑谓词逻辑 （11） 定义义3.5：合取范式（Conjunc

11、tive Normal Form） 设设A为为如下形式的谓词谓词 公式： B1 B2 Bn 其中Bi（i=1,2,，n）形如L1 L2 Lm，Lj（j=1， 2,，m）为为原子公式或其否定，则则A称为为合取范式。 例 就是一个合取范式 *21 3.2.2 谓词逻辑谓词逻辑 （12） 定义义3.6：析取范式（Disjunctive Normal Form） 设设A为为如下形式的谓词谓词 公式： B1 B2 Bn 其中Bi（i=1,2,，n）形如L1 L2 Lm，Lj（j=1， 2,，m）为为原子公式或其否定，则则A称为为析取范式。 例如 就是一个析取范式 *22 3.2.2 谓词逻辑谓词逻辑 （

12、13） 定义3.7 谓词公式的解释 设D为谓词 公式P的个体域，若对P中的个体常量、函 数和谓词按如下规定赋值： （1）为每个个体常量指派D中的一个元素； （2）为每个n元函数指派一个从Dn到D的映射，其中 Dn(x1,x2,xn)/x1,x2,xn D （3）为每个n元谓词指派一个从Dn到F,T的映射。 则称这些指派为公式P在D上的一个解释。 *23 3.2.2 谓词逻辑谓词逻辑 （14） 例：设个体域D1,2, 求公式 在D上的解 释，并指出在每一种解释下公式A的真值。 解：设公式A中对个体常量b、函数f（x）指派的真值分 别为： 对谓词 指派的真值为： *24 3.2.2 谓词逻辑谓词逻

13、辑 （15） 在此解释下， 由于当x=1时，有y=2，使得： ： 所以 为T。 当x2时，有y=2，使得 所以 为T。 所以公式A在此解释下真值为T。 *25 3.2.2 谓词逻辑谓词逻辑 （16） 定义义3.8：谓词谓词 公式的永真 如果谓词公式P对个体域D上的任何一个解释都 取得真值T，则称P在D上是永真的；如果P在全总个 体域上永真，则称P永真。 *26 3.2.2 谓词逻辑谓词逻辑 （17） 定义义3.9：谓词谓词 公式的可满满足性 对于谓词公式P，如果在个体域D上至少存在一 个解释使得公式P在此解释下的真值为T，则称公式P 在D上是可满足的。 *27 3.2.2 谓词逻辑谓词逻辑 （

14、18） 定义义3.9：谓词谓词 公式的永假 如果谓词公式P对于个体域D上的任何一个 解释都取得真值F，则称P在D上是永假的；如 果P在全总个体域上永假，则称P永假。 *28 3.2.3 基于谓词逻辑谓词逻辑 的知识识表示（1） 知识表示的步骤： n分析定理中的对象、对象的属性及对象之间的关系， 定义谓词和函数。 n定理中的事实通常用谓词公式的与或型表示，规则用 蕴含式表示，据此定义谓词公式。 n注意：用谓词表示命题时，一般取全总个体域，再采 用使用限定谓词的方法来指出每个个体变元的个体域 。对量词的处理按下述原则： (2)对对存在量词词，把限定词词作为为一个合取项项加入。即 x(P(x) (1

15、)对对全称量词词，把限定词词作为蕴为蕴 含式之前件加入。 即 x （P（x） ） *29 3.2.3 基于谓词逻辑谓词逻辑 的知识识表示（2） 表示“对对个体域中所有的（或任一个）个体” 。记为记为 x全称量词词 表示“在个体域中存在个体”。记为记为 x存在量词词 如：“凡是人都有名字” 用M（x）表示“x是人”，N（x）表示“x有名字” x（M（x） N（x） 如：“存在不是偶数的整数” 用G（x）表示“x是整数”，E（x）表示“x是偶数” x（G（x） E（x） *30 3.2.3 基于谓词逻辑谓词逻辑 的知识识表示（2） 例 3.2 设有如下命题： （1）小明比他的哥哥学习努力。 定义谓

16、词 ： ：x比y学习努力 定义函数： ：x的哥哥 谓词公式表示为： *31 3.2.3 基于谓词逻辑谓词逻辑 的知识识表示（3） （2）对于所有的自然数，均有 。 定义谓词 ： ：x是自然数 ：x大于等于y 定义函数： ：x与y的和 谓词公式表示为： *32 3.2.3 基于谓词逻辑谓词逻辑 的知识识表示（4） （3）某些人对某些食物过敏。 定义谓词 ： ：x是人 ：x是食物 ：x对y过敏定义函数： 谓词公式表示为： *33 3.2.3 基于谓词逻辑谓词逻辑 的知识识表示（5） 例3.3 用谓词公式表示下述命题。 已知前提： F1：自然数都是大于零的整数。 F2：所有整数不是偶数就是奇数。 F3：偶数除以2是整数。 结论：所有自然数不是奇数就是一半为整数的数。 首先定义如下谓词： N(x):x是自然数。 I(x):x是整数。 E(x):x是偶数。 O(x):x是奇数。 GZ(x):x大于零。 定义函数s(x):x除以2。 *34 3.2.3 基于谓词逻辑谓词逻辑 的知识识表示（6） 将上述各语句翻译成谓词公式： F1：自然数都是大于零的整数。 x (N(x)GZ(x) I(x) F2：