第5章基于谓词逻辑的机器推理

《第5章基于谓词逻辑的机器推理》由会员分享，可在线阅读，更多相关《第5章基于谓词逻辑的机器推理（111页珍藏版）》请在金锄头文库上搜索。

1、第3篇 知识与推理,概述 第5章 基于谓词逻辑的机器推理 第6章 基于产生式规则的机器推理 第7章 几种结构化知识表示及其推理 第8章 不确定性知识的表示与推理,概述,知识及其表示 一些常用的知识表示形式： 一阶谓词逻辑、产生式规则、框架、语义网络、类和对象、模糊集合、贝叶斯网络、脚本、过程等。 机器推理 演绎推理、归纳推理和类比推理 不确定性推理和不确切性推理 约束推理、定性推理、范例推理、非单调推理,第5章 基于谓词逻辑的机器推理,主要内容 1、 一阶谓词逻辑 2、归结演绎推理 3、应用归结原理求取问题答案 4、归结策略 5、Horn子句归结与逻辑程序,基于谓词逻辑的机器推理也称自动推理。

2、它是人工智能早期的主要研究内容之一。一阶谓词逻辑是一种表达力很强的形式语言，而且这种语言很适合当前的数字计算机。因而就成为知识表示的首选。基于这种语言，不仅可以实现类似于人推理的自然演绎法自动推理，而且也可实现不同于人的归结（或称消解）法自动推理。本节主要介绍基于谓词逻辑归结演绎推理。,5.1 一阶谓词逻辑,5.1.1 谓词、函数、量词 命题：凡可确定真假的陈述句称为命题。 可以取值“真”（T）或“假”（F） 在一定的条件下，只能取其中一个值 例： （1）北京是中国的首都 （2）3 + 2 10 （3）禁止吸烟 （祈使句） A(a1,a2,an)在谓词逻辑中就表示一个原子命题。 如：素数（2）

3、，表示命题“2是个素数”。,命题的表达,例： 凡偶数都能被2整除， 6是偶数。 所以，6能被2整除 将它们命题符号化： p：凡偶数都能被2整除 q： 6是偶数 r： 6能被2整除 则推理的形式结构符号化为： (p q) r,由于上式不是重言式（永真式），所以不能由它判断推理的正确性。为了克服命题逻辑的局限性，就应该将简单命题再细分，分析出个体词、谓词和量词，以期达到表达出个体与总体的内在联系和数量关系，这就是谓词逻辑。,(1)是自然数。 (2) 21世纪末，人类将住在月球。 (3) x+y=y+x (4) 只有x能被2整除， x才能被4整除。,个体词,x,y的取值范围：复数域 a的取值范围：整

4、数域,表示具体或特定的客体的个体词称作个体常项；常用a,b,c,表示。,表示抽象或泛指的客体的个体词称作个体变项；常用x,y,z,表示。,全总个体域：由宇宙间一切事物组成的域为全总个体域。,谓词,谓词：是用来刻画个体词的性质或个体词之间的关系的词（带参量的命题叫谓词） n 元谓词，P（x1, x2, x3, , xn） P 是谓词符号，代表一个确定的特征（一个参量）或关系（多个参量） x1, x2, x3, , xn 称为参量或项（个体常元或个体变元） 论述域（个体域）：个体变元的取值范围 例： 北京是一个城市 CITY（北京） x 是人 HUMAN（x） A是B的兄弟 兄弟（A，B） x 大

5、于 y G（x，y） 不带个体变元的谓词公式叫命题，命题是谓词公式的特例,一般的 用F(a)表示个体常项a具有性质F（F是谓词常项或谓词变项）， 用F(x)表示个体变项x具有性质F。 而用F(a, b)表示个体常项a, b具有关系F， 用F(x, y) 表示个体变项x, y具有关系F。,函数,为了表达个体之间的关系，我们引入通常数学中函数的概念和记法。 例如我们用father(x)表示x的父亲，用sum(x,y)表示x和y之和，一般地，我们用如下形式： f(x1,x2, ,xn) 表示个体变元x1，x2，xn所对应的个体y，并称之为n元个体函数，简称函数（或函词、函词命名式）。有了函数的概念和

6、记法，谓词的表达能力就更强了。例如，Doctor(father(Li)表示“小李的父亲是医生）。,我们约定：,（1）用大写应为字母作为谓词符号； （2）用小写字母f，g，h等表示函数符号； （3）用小写字母x，y，z等作为个体变元符号； （4）用小写字母a，b，c等作为个体常元符号。,逻辑连接词：研究单个谓词是不够的，还必须研究多个谓词之间的关系，这需要引入逻辑连接词 ：否定词 A读为“非A”，当A为真时， A为假，当A为假时， A为真 ：合取词 A B读为“A并且B”，当且仅当A和B都为真时， A B为真，否则A B为假 ：析取词 A B读为“A或者B”，当且仅当A和B都为假时， A B为假

7、，否则A B为真,：蕴涵词 A B读为“若A则B”，当且仅当A为真，且B为假时， A B为假，否则A B为真 在A B中，A称为前件，B称为后件 ：等值词 A B读为“A等值于B”，当且仅当A和B同为真或同为假时， A B为真，否则A B为假,量词,有些陈述句包含表示数量的词，如“所有”、“任一”、“存在”、“至少有一个”等，为了表示这样的陈述句，需引入新的符号，称为量词。 全称量词 （ x ）表示 “ 对于所有的 x ” 例： 凡是人都有名字 （ x ）（M （x） N（x） （ x ）A（x） A（a1） A（a2） A（an），若论域为有限集合， 且a1、 a2、 、an是论域中的所有个

8、体。,存在量词 （ x ）表示 “ 对于某个 x ” 例： 存在不是偶数的整数 （ x ）（G （x） E（x） （ x ）A（x） A（a1） A（a2） A（an）,不同的个体变元，可能有不同的个体域。为了方便和统一起见，我们用谓词表示命题时，一般总取全总个体域，然后再采取使用限定谓词的办法来指出每个个体变元的个体域。具体来讲，有下面两条： （1）对全称量词，把限定谓词作为蕴含式之前件加入，即x（p（x）。 （2）对于存在量词，把限定谓词作为一个合取项加入，即x（p（x）。,例：不存在最大的整数 分析：命题中“不存在最大的”显然是对所有的整数而言，所以可理解为“对所有的x，如果x是整数，则

9、一定还有比x大的整数”； 再具体点，即“对所有的x如果x是整数，则一定存在y，y也是整数，并且y比x大”。则可以翻译成如下形式： x（G（x） y（G（y）D（x，y） 或 x（G（x） y（G（y）D（y，x） 例：对于所有的自然数，均有x+yx x y（N(x) N(y）S(x，y，x） 例：某些人对某些食物过敏 x y（M（x）F（y）G（x，y）,5.1.2 谓词公式,用谓词、量词及真值联结词可以表达相当复杂的命题。抽象的来看，我们把命题的这种符号表达式称为谓词公式。 项： （ 定义1） （1）个体常元和个体变元都是项 （2）f 是 n 元函数，若 t1, t2, , tn 是项，则f

10、 (t1, t2, , tn)是项， （3）只有有限次使用（1）、（2）得到的符号串才是项,原子公式： （ 定义2） 设 P 为 n 元谓词符号， t1, t2, , tn 是项，则 P（ t1, t2, , tn ）称为原子谓词公式，简称原子公式,谓词公式： （ 定义3） （1）原子公式是谓词公式 （2）若A、B是谓词公式，则 AB、AB、 A、AB、A B、 x A、 x A也是谓词公式 （3）只有有限次应用（1）、（2）生成的公式才是谓词公式 谓词公式又称为谓词逻辑中的合式公式，记为 Wff (well-formed formula) 几个概念： 辖域：紧接于量词之后被量词作用的（说明的

11、）谓词公式称为该量词的辖域 指导变元、约束变元和自由变元 改名规则，保证一个变元或者是约束变元，或者是自由变元 例： x （H（x） G（x, y） x A（x） B（x）,量词的辖域,定义:量词的辖域是邻接量词之后的最小子公式，故除非辖域是个原子公式，否则应在该子公式的两端有括号。 例：XP(X)Q(X) X的辖域是P(X) X(P(X,Y)Q(X，Y) ) P(Y,Z) X的辖域是P(X，Y)Q(X，Y),定义：量词后的变元如x， y中的x，y成为量词的指导变元（或作用变元）。在量词X，X辖域内变元X的一切出现叫约束出现，称这样的X为约束变元。,变元的非约束出现称为自由出现,称这样的变元为

12、自由变元。,例：指出下列谓词公式中的自由变元和约束变元，并指明量词的辖域 （1）X(P(X) R(X) )XP(X) Q(X) 解：表达式中的X(P(X)R(X)中X的辖域是 P(X) R(X),其中的X是约束出现 Q(X)中的X是自由变元,例：指出下列谓词公式中的自由变元和约束变元。 并指明量词的辖域 (2)X(P(X，Y)YR(X，Y) ) 解：其中的P(X，Y)中的Y是自由变元，X是约束变元， R(X，Y)中的X，Y是约束变元。,注：在一个公式中，一个变元既可以约束出现，又可以 自由出现。为避免混淆可用改名规则对变元改名。,约束变元改名规则,（1）对需改名的变元，应同时更改该变元在量词及

13、其辖域中的所有出现。 （2）新变元符号必须事量词辖域内原先没有的，最好是公式中也未出现过的。 例如公式xP(x)Q(x)可改为yP(y)Q(x)，二者意义相同。,量化,在谓词前加上量词，称作谓词中相应的个体变元被量化，例如xA(x)中的x被量化。 如果一个谓词中的所有个体变元都被量化，则这个谓词就变成了一个命题。 这样，我们就有两种从谓词得到命题的方法： （1）给谓词中的个体变元代入个体常元。 （2）把谓词中的个体变元全部量化。,一阶谓词：仅个体变元被量化的谓词称为一阶谓词。 二阶谓词：不仅个体变元被量化，而且函数符号和谓词符号也被量化，这样的谓词称为二阶谓词。 特别地，我们称xA(x)为全称

14、命题， xA(x)为特称命题。 当个体域为有限集时，如D=a1, a2, , an，对于任意的谓词A(x)，都有 x A(x) A(a1) A(a2) A(an) x A(x) A(a1) A(a2) A(an) 这实际上是将谓词逻辑中命题公式转化为命题逻辑中的命题公式问题。,合取范式： （ 定义4）,A为合取范式，B1 B2 B n ,其中 Bi 形如L1 L2 Lm, L j为原子公式或其否定 例：（P（x） Q（y） （ P（x） Q（y） R（x，y） 任一谓词公式均可化为与之等价的合取范式，但一般不唯一,析取范式： （ 定义5）,A为析取范式，B1 B2 B n ,其中 Bi 形如L

15、1 L2 Lm, L j为原子公式或其否定 例：（P（x） Q（y） （ P（x） Q（y） R（x，y） 任一谓词公式均可化为与之等价的析取范式，但一般不唯一,定义6,设P为谓词公式，D为其个体域，对于D中的任一解释I： （1）若P恒为真，则称P在D上永真（或有效）或是D上的永真式。 （2）若P恒为假，则称P在D上永假（或不可满足）或是D上的永假式。 （3）若至少有一个解释，可使P为真，则称P在D上可满足或是D上的可满足式。,定义7,设P为谓词公式，对于任何个体域： （1）若P都永真，则称P为永真式。 （2）若P都永假，则称P为永假式。 （3）若P都可满足，则称P为可满足式。,5.1.3 谓词逻辑中的形式演绎推理,谓词公式之间的关系 常用逻辑等价式 表5.1 注意与的区别，是等价符号，说明两个谓词公式之间的等价性，是逻辑连接词，是谓词公式的组成部分 常用逻辑蕴涵式 表5.2 注意与的区别， 是推导符号，说明由左边的谓词公式可以推导出右边的谓词公式， 是逻辑连接词，是谓词公式的组成部分,自然演绎推理： （1）将自然语言命题转化为谓词公式 （2）利用上面的