第5章基于谓词逻辑的机器推理课题.ppt

第3篇 知识与推理;概述;第5章 基于谓词逻辑的机器推理;基于谓词逻辑的机器推理也称自动推理。它是人工智能早期的主要研究内容之一。一阶谓词逻辑是一种表达力很强的形式语言，而且这种语言很适合当前的数字计算机。因而就成为知识表示的首选。基于这种语言，不仅可以实现类似于人推理的自然演绎法自动推理，而且也可实现不同于人的归结（或称消解）法自动推理。本节主要介绍基于谓词逻辑归结演绎推理。 ;5.1 一阶谓词逻辑;命题的表达;(1)８是自然数。 (2) 21世纪末，人类将住在月球。 (3) x+y=y+x (4) 只有x能被2整除， x才能被4整除。;谓词;一般的 用F(a)表示个体常项a具有性质F（F是谓词常项或谓词变项）， 用F(x)表示个体变项x具有性质F。 而用F(a, b)表示个体常项a, b具有关系F， 用F(x, y) 表示个体变项x, y具有关系F。 ;函数;我们约定：;逻辑连接词：研究单个谓词是不够的，还必须研究多个谓词之间的关系，这需要引入逻辑连接词 ?：否定词 ?A读为“非A”，当A为真时， ?A为假，当A为假时， ?A为真 ∧：合取词 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为假时， A → B为假，否则A → B为真 在A → B中，A称为前件，B称为后件 ?：等值词 A ? B读为“A等值于B”，当且仅当A和B同为真或同为假时， A ? B为真，否则A ? B为假 ;量词;存在量词 ? （ ? 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是整数，则一定还有比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 谓词公式;;谓词公式： （ 定义3） （1）原子公式是谓词公式 （2）若A、B是谓词公式，则 A∧B、A∨B、? A、A→B、A? B、 ? x A、 ? x A也是谓词公式 （3）只有有限次应用（1）、（2）生成的公式才是谓词公式 谓词公式又称为谓词逻辑中的合式公式，记为 Wff (well-formed formula) 几个概念： 辖域：紧接于量词之后被量词作用的（说明的）谓词公式称为该量词的辖域 指导变元、约束变元和自由变元 改名规则，保证一个变元或者是约束变元，或者是自由变元 例： ? x （H（x）→ G（x, y）） ∧ ? x A（x） ∧ B（x） ;量词的辖域;定义：量词后的变元如?x， ?y中的x，y成为量词的指导变元（或作用变元）。在量词?X，?X辖域内变元X的一切出现叫约束出现，称这样的X为约束变元。 ; 例：指出下列谓词公式中的自由变元和约束变元。 并指明量词的辖域 (2)?X(P(X，Y)→?YR(X，Y) ) 解：其中的P(X，Y)中的Y是自由变元，X是约束变元， R(X，Y)中的X，Y是约束变元。 ;约束变元改名规则;量化;一阶谓词：仅个体变元被量化的谓词称为一阶谓词。 二阶谓词：不仅个体变元被量化，而且函数符号和谓词符号也被量化，这样的谓词称为二阶谓词。 特别地，我们称?xA(x)为全称命题， ?xA(x)为特称命题。 当个体域为有限集时，如D={a1, a2, … , an}，对于任意的谓词A(x)，都有 ① ? x A