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

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

2、逻辑程序 基于谓词逻辑的机器推理也称自动推理。它是人工智能早期的主要研究内容之一。一阶谓词逻辑是一种表达力很强的形式语言，而且这种语言很适合当前的数字计算机。因而就成为知识表示的首选。基于这种语言，不仅可以实现类似于人推理的自然演绎法自动推理，而且也可实现不同于人的归结（或称消解）法自动推理。本节主要介绍基于谓词逻辑归结演绎推理。5.1 一阶谓词逻辑一阶谓词逻辑v5.1.1 谓词、函数、量词谓词、函数、量词 命题：凡可确定真假的陈述句称为命题。命题：凡可确定真假的陈述句称为命题。可以取值可以取值“真真”（T）或）或“假假”（F）在一定的条件下，只能取其中一个值在一定的条件下，只能取其中一个值例

3、：例：v（1）北京是中国的首都）北京是中国的首都v（2）3 + 2 10v（3）禁止吸烟）禁止吸烟 （祈使句）（祈使句） A(a1,a2,an)在谓词逻辑中就表示一个原子命题。在谓词逻辑中就表示一个原子命题。如：素数（如：素数（2），表示命题），表示命题“2是个素数是个素数”。命题的表达命题的表达 例例： 凡偶数都能被凡偶数都能被2整除，整除， 6是偶数。是偶数。 所以，所以，6能被能被2整除整除 将它们命题符号化：将它们命题符号化： p：凡偶数都能被：凡偶数都能被2整除整除 q： 6是偶数是偶数 r： 6能被能被2整除整除 则推理的形式结构符号化为：则推理的形式结构符号化为： (p q) r

4、由于上式不是重言式由于上式不是重言式（永真式），所以不能（永真式），所以不能由它判断推理的正确性。由它判断推理的正确性。为了克服命题逻辑的局为了克服命题逻辑的局限性，就应该将简单命限性，就应该将简单命题再细分，分析出个体题再细分，分析出个体词、谓词和量词，以期词、谓词和量词，以期达到表达出个体与总体达到表达出个体与总体的内在联系和数量关系，的内在联系和数量关系，这就是谓词逻辑。这就是谓词逻辑。 (1)(1)是自然数。是自然数。(2) (2) 21世纪末，人类将住在月球。世纪末，人类将住在月球。 (3) x+y=y+x (4) 只有只有x能被能被2整除，整除， x才能被才能被4整除。整除。个体词

5、个体词x,y的取值范围：复数域的取值范围：复数域a的取值范围：整数域的取值范围：整数域表示具体或特定的客体表示具体或特定的客体的个体词称作的个体词称作个体常项个体常项；常用常用a,b,c,表示。表示。表示抽象或泛指的客体表示抽象或泛指的客体的个体词称作的个体词称作个体变项个体变项；常用常用x,y,z,表示。表示。个体变项的取值范围为个体变项的取值范围为个个体域体域，个体域可以是有穷，个体域可以是有穷集合，也可以是无穷集合。集合，也可以是无穷集合。全总个体域全总个体域：由宇宙间一切事物组成的域为：由宇宙间一切事物组成的域为全总个体域全总个体域。 谓词v谓词：是用来刻画个体词的性质或个体词之间的关

6、谓词：是用来刻画个体词的性质或个体词之间的关系的词（带参量的命题叫谓词）系的词（带参量的命题叫谓词）n 元谓词，元谓词，P（x1, x2, x3, , xn）vP 是谓词符号，代表一个确定的特征（一个参量）或关系（多个是谓词符号，代表一个确定的特征（一个参量）或关系（多个参量）参量）vx1, x2, x3, , xn 称为参量或项（个体常元或个体变元）称为参量或项（个体常元或个体变元）v论述域（个体域）：个体变元的取值范围论述域（个体域）：个体变元的取值范围例：例：v北京是一个城市北京是一个城市 CITY（北京）（北京）vx 是人是人 HUMAN（x）vA是是B的兄弟的兄弟 兄弟（兄弟（A，B

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

8、个体函数，简称函数（或函词、函词命名式）。有了函数的概念和记法，谓词的表达能力就更强了。例如，Doctor(father(Li)表示“小李的父亲是医生）。我们约定：我们约定：（1）用大写应为字母作为谓词符号；）用大写应为字母作为谓词符号；（2）用小写字母）用小写字母f，g，h等表示函数符号；等表示函数符号；（3）用小写字母）用小写字母x，y，z等作为个体变元符号；等作为个体变元符号；（4）用小写字母）用小写字母a，b，c等作为个体常元符号。等作为个体常元符号。v逻辑连接词：研究单个谓词是不够的，还必须研究逻辑连接词：研究单个谓词是不够的，还必须研究多个谓词之间的关系，这需要引入逻辑连接词多个谓

9、词之间的关系，这需要引入逻辑连接词：否定词v A读为“非A”，当A为真时， A为假，当A为假时， A为真：合取词vA B读为“A并且B”，当且仅当A和B都为真时， A B为真，否则A B为假：析取词vA B读为“A或者B”，当且仅当A和B都为假时， A B为假，否则A B为真：蕴涵词vA B读为“若A则B”，当且仅当A为真，且B为假时， A B为假，否则A B为真v在A B中，A称为前件，B称为后件：等值词vA B读为“A等值于B”，当且仅当A和B同为真或同为假时， A B为真，否则A B为假量词量词v有些陈述句包含表示数量的词，如“所有”、“任一”、“存在”、“至少有一个”等，为了表示这样的

10、陈述句，需引入新的符号，称为量词。全称量词全称量词 v（ x ）表示 “ 对于所有的 x ”v例：凡是人都有名字 （ x ）（M （x） N（x）v（ x ）A（x） A（a1） A（a2） A（an），若论域为有限集合， 且a1、 a2、 、an是论域中的所有个体。存在量词存在量词 v（ x ）表示 “ 对于某个 x ”v例：存在不是偶数的整数 （ x ）（G （x） E（x）v（ x ）A（x） A（a1） A（a2） A（an）v不同的个体变元，可能有不同的个体域。为了方便和统一起不同的个体变元，可能有不同的个体域。为了方便和统一起见，我们用谓词表示命题时，一般见，我们用谓词表示命题时，

11、一般总取全总个体域总取全总个体域，然后再，然后再采取使用采取使用限定谓词限定谓词的办法来指出每个个体变元的个体域。具的办法来指出每个个体变元的个体域。具体来讲，有下面两条：体来讲，有下面两条： （1）对全称量词，把限定谓词作为蕴含式之前件加入，即x（p（x）。 （2）对于存在量词，把限定谓词作为一个合取项加入，即x（p（x）。v例：不存在最大的整数 分析：命题中“不存在最大的”显然是对所有的整数而言，所以可理解为“对所有的x，如果x是整数，则一定还有比x大的整数”； 再具体点，即“对所有的x如果x是整数，则一定存在y，y也是整数，并且y比x大”。则可以翻译成如下形式： x（G（x） y（G（y

12、）D（x，y）或 x（G（x） y（G（y）D（y，x）v例：对于所有的自然数，均有x+yx x y（N(x) N(y）S(x，y，x）v例：某些人对某些食物过敏 x y（M（x）F（y）G（x，y）5.1.2 谓词公式谓词公式v用谓词、量词及真值联结词可以表达相当复杂的命题。抽象的来看，我们把命题的这种符号表达式称为谓词公式。v项：项： （ 定义定义1）（1）个体常元和个体变元都是项（2）f 是 n 元函数，若 t1, t2, , tn 是项，则f (t1, t2, , tn)是项，（3）只有有限次使用（1）、（2）得到的符号串才是项v原子公式：原子公式： （ 定义定义2）设设 P 为为 n

13、 元谓词符号，元谓词符号， t1, t2, , tn 是项，则是项，则 P（ t1, t2, , tn ）称为原子谓词公式，简称原子称为原子谓词公式，简称原子公式公式v谓词公式：谓词公式： （ 定义定义3）（1）原子公式是谓词公式）原子公式是谓词公式（2）若）若A、B是谓词公式，则是谓词公式，则 AB、AB、 A、AB、A B、 x A、 x A也是谓词公式也是谓词公式（3）只有有限次应用（）只有有限次应用（1）、（）、（2）生成的公式才是谓词）生成的公式才是谓词公式公式v谓词公式又称为谓词逻辑中的合式公式，记为谓词公式又称为谓词逻辑中的合式公式，记为 Wff (well-formed for

14、mula)v几个概念：几个概念：辖域：紧接于量词之后被量词作用的（说明的）谓词公式称为该量辖域：紧接于量词之后被量词作用的（说明的）谓词公式称为该量词的辖域词的辖域指导变元、约束变元和自由变元指导变元、约束变元和自由变元 改名规则，保证一个变元或者是约束变元，或者是自由变元改名规则，保证一个变元或者是约束变元，或者是自由变元例：例： x （H（x） G（x, y） x A（x） B（x）量词的辖域量词的辖域v定义定义:量词的辖域量词的辖域是邻接量词之后的最小子公式，故是邻接量词之后的最小子公式，故除非辖域是个原子公式，否则应在该子公式的两端除非辖域是个原子公式，否则应在该子公式的两端有括号。有

15、括号。 例：例： 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辖域内变元辖域内变元X X的一切出现叫的一切出现叫约约束出现束出现，称这样的，称这样的X X为为约束变元约束变元。 变元的非约束出现称为变元的非约束出现称为自由出现自由出现, ,称这样的变元为称这样的变元为自由变元自由变元。例：例：指出下列谓词公式中的自由变元和约束变元，并指明量词

16、指出下列谓词公式中的自由变元和约束变元，并指明量词的辖域的辖域 （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)(2) X(P(XX(P(X，Y)Y) YR(XYR(X，Y) )Y) ) 解：其中的解：其中的P(XP(X，Y)Y)中的中的Y Y是自由变元，是自由变元，X X是约束变元，是

17、约束变元， R(XR(X，Y)Y)中的中的X X，Y Y是约束变元。是约束变元。 注：在一个公式中，一个变元既可以约束出现，又可以注：在一个公式中，一个变元既可以约束出现，又可以 自由出现。为避免混淆可用改名规则对变元改名。自由出现。为避免混淆可用改名规则对变元改名。约束变元改名规则约束变元改名规则（1）对需改名的变元，应同时更改该变元在量词及其辖域中的所有出现。（2）新变元符号必须事量词辖域内原先没有的，最好是公式中也未出现过的。 例如公式xP(x)Q(x)可改为yP(y)Q(x)，二者意义相同。量化量化v在谓词前加上量词，称作谓词中相应的个体变元被量化，例如xA(x)中的x被量化。v如果一

18、个谓词中的所有个体变元都被量化，则这个谓词就变成了一个命题。v这样，我们就有两种从谓词得到命题的方法： （1）给谓词中的个体变元代入个体常元。 （2）把谓词中的个体变元全部量化。v一阶谓词一阶谓词：仅个体变元被量化的谓词称为一阶谓词。v二阶谓词二阶谓词：不仅个体变元被量化，而且函数符号和谓词符号也被量化，这样的谓词称为二阶谓词。 v特别地，我们称xA(x)为全称命题， 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)这实际上是将谓词逻辑中命

19、题公式转化为命题逻辑中的命题公式问题。合取范式：合取范式： （ 定义定义4）vA为合取范式，为合取范式，B1 B2 B n ,其中其中 Bi 形如形如L1 L2 Lm, L j为原子公式或其否定为原子公式或其否定例例：（：（P（x） Q（y） （ P（x） Q（y） R（x，y） 任一谓词公式均可化为与之等价的合取范式，但一般不任一谓词公式均可化为与之等价的合取范式，但一般不唯一唯一析取范式：析取范式： （ 定义定义5）vA为析取范式，为析取范式，B1 B2 B n ,其中其中 Bi 形如形如L1 L2 Lm, L j为原子公式或其否定为原子公式或其否定例例：（：（P（x） Q（y） （ P（

20、x） Q（y） R（x，y） 任一谓词公式均可化为与之等价的析取范式，但一般不任一谓词公式均可化为与之等价的析取范式，但一般不唯一唯一定义6v设P为谓词公式，D为其个体域，对于D中的任一解释I： （1）若P恒为真，则称P在D上永真（或有效）或是D上的永真式。 （2）若P恒为假，则称P在D上永假（或不可满足）或是D上的永假式。 （3）若至少有一个解释，可使P为真，则称P在D上可满足或是D上的可满足式。定义7v设P为谓词公式，对于任何个体域： （1）若P都永真，则称P为永真式。 （2）若P都永假，则称P为永假式。 （3）若P都可满足，则称P为可满足式。5.1.3 谓词逻辑中的形式演绎推理v谓词公式

21、之间的关系谓词公式之间的关系常用逻辑等价式常用逻辑等价式 表表5.1v注意注意与与的区别，的区别，是等价符号，说明两个谓词公是等价符号，说明两个谓词公式之间的等价性，式之间的等价性，是逻辑连接词，是谓词公式的组是逻辑连接词，是谓词公式的组成部分成部分 常用逻辑蕴涵式常用逻辑蕴涵式 表表5.2v注意注意与与的区别，的区别， 是推导符号，说明由是推导符号，说明由左边的左边的谓词公式可以推导出谓词公式可以推导出右边的谓词公式，右边的谓词公式， 是逻辑连是逻辑连接词，是谓词公式的组成部分接词，是谓词公式的组成部分 v自然演绎推理：自然演绎推理：（1）将自然语言命题转化为谓词公式）将自然语言命题转化为谓

22、词公式（2）利用上面的逻辑等价式和逻辑蕴涵式，可）利用上面的逻辑等价式和逻辑蕴涵式，可以进行推理，得出一些隐含在谓词公式中的结论以进行推理，得出一些隐含在谓词公式中的结论v利用一阶谓词逻辑的这种形式语言，就可以把关于利用一阶谓词逻辑的这种形式语言，就可以把关于自然语言的逻辑推理问题，转换为这种符号表达式自然语言的逻辑推理问题，转换为这种符号表达式的推演变换。的推演变换。v例例5.4 设有前提设有前提： （1）凡是大学生都学过计算机； （2）小王是大学生。试问：小王学过计算机吗？ 解：令S(x)：x是大学生；M(x)：x学过计算机；a：小王。则上面两个命题可用谓词公式表示为（1） x(S(X)

23、M(x)（2）S(a)问题：M(a)是否成立？v形式推理如下：形式推理如下： （1）x(S(X) M(x) 前提 （2）S(a) M(x) (1)，US （3）S(a) 前提 （4）M(a) （2），（3），I3v例例5.5 证明证明P(a，b)是是 x y（P(x，y) W（x，y）和和W（a，b）的逻辑结果。）的逻辑结果。 证： （1）x y（P(x，y) W（x，y） 前提 （2）y（P(a，y) W（a，y） (1),US （3）（P(a，b) W（a，b） (2),US （4） W（a，b） 前提 （5） P(a，b) (3),(4),I4v例例5.6 证明证明 x(P(x) Q(x

24、) x(R(x) Q(x) x(R(x) (P(x) )。 证： （1） x(P(x) Q(x) 前提 （2） P(y) Q(y) (1),US （3） Q(y) P(y) (2),E24 （4） x(R(x) Q(x) 前提 （5） R(y) Q(y) (3),US （6） R(y) P(y) (3),(5),I6 （7） x(R(x) (P(x) )v上述推理过程完全是一个符号变换过程。类似于人们用自然语言推理的思维过程，因而成为自然演绎推理。这种推理实际上已几乎与谓词公式所表示的含义完全无关，而是一种形式推理。于是，可将这种推理方法引入机器推理。v自然演绎推理实施困难，推理规则太多、应用

25、规则需要很强的模式识别能力、中间结论呈指数增长v引入新的推理技术归结演绎推理技术归结消解（Resolution），由Robinson于1965年提出，大大推动了自动定理证明的发展5.2 归结演绎推理v5.2.1 子句集子句集 定义定义1 1 原子谓词公式及其否定称为文字，若干个文字的一个析取式称为一个子句，由r个文字组成的子句叫r文字子句，1文字子句叫单元子句，不含任何文字的子句称为空子句，记为或NIL。 例： PQR P(x,y) Q(x) 定义定义2 2 对一个谓词公式G，通过以下步骤所得的子句集合S，称为G的子句集。 (1)消去蕴含词和等值词。 (2)缩小否定词的作用范围，直到其仅作用于

26、原子公式。 (3)适当改名，使量词间不含同名指导变元和约束变元。 (4)消去存在量词。 (5)消去所有全称量词。 (6)化公式为合取范式。 (7)适当改名，使子句间无同名变元。 (8)消去合取词，以子句为元素组成集合S。(1)消去蕴含词和等值词v使用逻辑等价式A B A B E14A B (A B) (B A) E15（2）缩小否定词的作用范围，直到其仅作用于原子公式v使用逻辑等价式： (A) A E1 (A B) A B E12 (A B) A B E13 xp(x) x P(X) E29 x P(X) xp(x) E30(4)消去存在量词消去存在量词时，同时还要进行变元替换。变元替换分两种

27、情况：若该存在量词在某些全称量词的辖域内，则用这些全称量词指导变元的一个函数代替该存在量词辖域中的相应约束变元，这样的函数称为Skolem函数。若该存在量词不在任何全称量词的辖域内，则用一个常量符号代替该存在量词辖域中的相应约束变元，这样的常量符号称为Skolem常量。(6)化公式为合取范式v可使用逻辑等价式： A (BC) (A B) (A C) (AB) C (A C) (B C)例5.7 求下面谓词公式的子句集 xyP(x,y) yQ(x,y) R(x,y)v解：由步(1)得 x yP(x,y) y Q(x,y) R(x,y) 消去蕴含词由步(2)得 xy P(x,y) yQ(x,y)

28、R(x,y) 缩小否定词范围由步(3)得 xy P(x,y) zQ(x,z) R(x,z) 改名由步(4)得 x P(x,f(x) Q(x,g(x) R(x,g(x) 消存在量词，标准型由步(5)得 P(x,f(x) Q(x,g(x) R(x,g(x) 消全称量词，US由步(6)得 P(x,f(x) Q(x,g(x) P(x,f(x) R(x,g(x) E9由步(7)得 P(x,f(x) Q(x,g(x) P(y,f(y) R(y,g(y) 改名由步(8)得 P(x,f(x) Q(x,g(x) , P(y,f(y) R(y,g(y) 消去合取词或 P(x,f(x) Q(x,g(x) P(y,f

29、(y) R(y,g(y)Skolem标准型v上述步骤步（4）所得式子就是Skolem标准型： 把所有全称量词都依次移到整个式子的最左边（或者先把所有量词都依次移到整个最左边，再消去存在量词），再将右部的式子化为合取范式，这时所得的式子称为原公式的Skolem标准型。v消去Skolem标准型左部的全称量词和合取词，即得公式的子句集。例5.8 设G= x y z uv w(P(x,y,z) Q(u,v,w)v那么，用a替代x，用f(y,z)替代u，用g(y,z,v)代替w，则得G的Skolem标准型 y z v(P(a,y,z) Q(f(y,z),v,g(y,z,v) 那么可以得到G的子句集为 P

30、(a,x,y), Q(f(u,v), w, g(u,v,w) 由此例得出，一个公式的子句集也可以通过先求前束范式，再求Skolem标准型而得到。量词在最前面，后面不含量词的式子注意：注意：v引入Skolem函数，是由于存在量词在全称量词的辖域内，其约束变元的取值则完全依赖于全称量词的取值。Skolem函数反应了这种依赖关系。vSkolem标准型与原公式一般并不等价，所以经过变经过变换后的子句集换后的子句集 S ，与谓词公式，与谓词公式 G 不等价不等价。定理1 谓词公式G不可满足当且仅当其子句集S不可满足。 把证明G的不可满足转化为证明子句集S的不可满足。定义3 子句集S是不可满足的，当且仅当

31、其全部子句的合取式是不可满足的。5.2.2 命题逻辑中的归结原理命题逻辑中的归结原理v定义定义4 设L为一个文字，则称L与L为互补文字。v定义定义5 设C1,C2是命题逻辑中的两个子句，C1中有文字L1，C2中有文字L2，且L1与L2互补，从C1,C2中分别删除L1,L2，再将剩余部分析取起来，记构成的新子句为C12，则称C12为C1,C2的归结式(或消解式)，C1,C2称为其归结式的亲本子句， L1,L2称为消解基。例例5.9 设C1= PQR, C2= QS, 则C1,C2的归结式为 PRS定理2 归结式是其亲本子句的逻辑结果。v证明： 设C1=L C1,C2= L C2,C1,C2都是文

32、字的析取式，则C1,C2的归结式为C1 C2,因为 C1=C1 L= C1 L C2= L C2=L C2所以 C1C2=(C1L)(L C2)C1C2=C1C2I6 假言三段论v由定理2即得推理规则： C1C2 (C1-L1)(C2-L2) 其中C1,C2是两个子句，L1,L2分别是C1,C2中的文字，且L1,L2互补。 此规则就是命题逻辑中的归结原理。 例5.10 用归结原理验证分离规则和拒取式 A(AB) B (AB) B A 解 A(AB) A( AB) B (AB) B ( AB)( B) Av类似可以验证其他推理规则也都可以经消解原理推出。v如果两个互否的单元子句进行归结，则归结式

33、为空子句，即 L L= 并且 L L= F 所以，空子句恒为假，即 Fv有了空子句，那么我们就可以用归结原理来推导空子句，反向证明。v求出要证的命题的否定式的子句集；v对子句集进行消解，寻找空子句，若存在，则子句集不可满足，从而原否定式不可满足，那么原公式是永真的。v即，否定式子句集S假，则S为真，要证命题为真。推论推论 设C1,C2是子句集S的两个子句，C12是它们的归结式，则：v（1）若用C12代替C1,C2，得到新子句集S1，则由S1的不可满足可推出原子句集S的不可满足。即 S1不可满足S不可满足v（2）若把C12加入到S中，得到新子句集S2，则S2与原S的不可满足等同。即 S2不可满足

34、S不可满足例5.11 证明子句集 PQ,P,Q 是不可满足的。证 (1)PQ (2)P (3)Q (4)Q 由(1),(2) (5) 由(3),(4)所以，子句集S不可满足。例5.12 用归结原理证明R是 P,(PQ)R,(SU)Q,U的逻辑结果。证 由所给条件得到子句集 S=P, P QR, SQ, UQ,U, R 然后对该子句集施行归结，归结过程用下面的归结演绎树表示（见图51）。由于最后推出了空子句，所以子句集S不可满足，即命题公式 P( P QR)( SQ)( UQ)U R 不可满足，从而R是题设前提的逻辑结果。图51 例5.12归结演绎树 5.2.3 5.2.3 替换与合一替换与合一

35、v一阶谓词逻辑中含有个体变元，因此应用消解原理不像命题逻辑中那样简单，寻找含互否文字的子句对的操作比较复杂。例：例： C1=P(x)Q(x) C2=P(a)R(y) 若用a替换C1中的x，则得到 C1=P(a)Q(a) C2=P(a)R(y)v则消解式为 C3=C1C2=Q(a)R(y) 结论：要在谓词逻辑中应用消解原理，则一般需要对个体变元作适当的替换。定义定义6 一个替换(Substitution)是形如t1/x1,t2/x2,tn/xn的有限集合，其中t1,t2,tn是项，称为替换的分子；x1,x2,xn是互不相同的个体变元，称为替换的分母；ti不同于xi，xi也不循环地出现在tj(i,

36、j=1,2,n)中；ti/xi表示用ti替换xi。若t1,t2,tn都是不含变元的项（称为基项）时，该替换称为基替换；没有元素的替换称为空替换，记作，它表示不作替换。例如： a a/ /x x, , g g( (y y)/)/y y , ,f f(g(g(b b)/)/z z 就是一个替换，而 g g( (y y)/)/x x, , f f( (x x)/)/y y 则不是一个替换,因为x与y出现了循环替换。v下面我们将项、原子公式、文字、子句等统称为表达式，没有变元的表达式称为基表达式，出现在表达式E中的表达式称为E的子表达式。v定义7 设= =t t1 1/ /x x1 1,t tn n/

37、 /x xn n是一个替换，E是一个表达式，把对E施行替换，即把E中出现的个体变元xj(1jn)都用tj替换，记为E，所得的结果称为E在下的例(instance)。例如，若=a/x,f(b)/y,c/z,=a/x,f(b)/y,c/z,则G=P(a,f(b),c)G=P(a,f(b),c)。v定义定义8 设= =t t1 1/ /x x1 1,t tn n/ /x xn n， =u1/y1,，um/ym是两个替换，则将集合 t1/x1，tn/xn， u1/y1,，um/ym中凡符合下列条件的元素删除： （1） ti/xi 当当ti=xi （2） ui/yi 当当yi?x1，xi 这样得到的集合

38、仍然是一个替换，该替换称为与的复合或乘积，记为。v例5.13 设 =f(y)/x,z/y=f(y)/x,z/y =a/x,b/y,y/z =a/x,b/y,y/z于是， t1/x1，t2/x2， u1/y1，u2/y2， u3/y3 =f(b)/x,y/y,a/x,b/y,y/z =f(b)/x,y/y,a/x,b/y,y/z可以证明，替换的乘积满足结合律，即可以证明，替换的乘积满足结合律，即 () u=(u)定义定义9 设S=F1,F2,Fn是一个原子谓词公式集，若存在一个替换，可使F1=F2=Fn，则称为S的一个合一(Unifier)，称S为可合一的。定义定义10 设是原子公式集S的一个合

39、一，如果对S的任何一个合一，都存在一个替换，使得 =则称为S的最一般合一(MostGeneralUnifier)，简称MGU。 例5.14 设S=P(u,y,g(y),P(x,f(u),z)，S有一个最一般合一 =u/x,f(u)/y,g(f(u)/z 对S的任一合一，例如： =a/x,f(a)/y,g(f(a)/z,a/u 存在一个替换 =a/u 使得 =v得出结论：如果能够找到一个公式集的合一，特别是最一般合一，则可使互否文字的形式结构完全一致起来，进而达到消解的目的。v怎么求一个公式集的最一般合一？有一个算法可以求出，为了解该算法，先引入差异集。v 定义定义11 设S是一个非空的具有相同

40、谓名词的原子公式集，从S中各公式的左边第一项开始，同时向右比较，知道发现第一个不都相同的项为止，用这些项的差异部分组成一个集合，这个集合就是原公式集S的一个差异集。v例例 5.15 设S=P(x,y,z),P(x,f(a),h(b),则不难看出，S有两个差异集 D1=y,f(a) D2=z,h(b)合一算法合一算法v步步1 1 置k=0，Sk=S，k=。v步步2 2 若Sk只含有一个谓词公式，则算法停止， k就是要求的最一般合一。v步步3 3 求Sk的差异集Dk。v步步4 4 若Dk中存在元素xk和tk，其中xk是变元，tk是项且xk不在tk中出现，则置Sk+1=Sktk/xk, k+1= k

41、tk/xk,k=k+1,然后转步2。v步步5 5 算法停止，S的最一般合一不存在。例例 5.16 求公式集S=P(a,x,f(g(y),P(z,h(z,u),f(u)的最一般合一。v解：k=0：S0=S, 0=, S0不是单元集，求得D0=a，z，其中z是变元，且不在a中出现，所以有 1= 0a/z= a/z= a/z S1=S0 a/z= P(a,x,f(g(y),P(a,h(a,u),f(u)k=1:S1不是单元集, D1=x，h(a,u),所以 2= 1h(a, u)/x= a/z h(a, u)/x= a/z,h(a, u)/x S2=S1 h(a, u)/x= P(a,h(a,u),

42、f(g(y),P(a,h(a,u),f(u)只含有一个谓词公式k=2:S2不是单元集, D2=g(y)，u，所以 3= 2g(y)/u= a/z,h(a, u)/x g(y)/u= a/z,h(a, g(y)/u S3=S2 g(y)/u= P(a,h(a,g(y),f(g(y),P(a,h(a,g(y),f(g(y) = P(a,h(a,g(y),f(g(y)k=3:S3是单元集，所以3就是S的最一般合一。例例 5.17 判定S=P(x,x),P(y,f(y)是否可合一？v解：k=0：S0=S, 0=, S0不是单元集，求得D0=x,y 1= 0y/x= y/x= y/x S1=S0 y/x

43、= P(y,y),P(y,f(y)k=1：S1不是单元集，求得D1=y,f(y)，变元y在项f(y)中出现，所以算法停止，不存在最一般合一。两个都是变元，所以有两种替换方法，因此最一般合一可能不唯一。v定理定理3 （合一定理）如果S是一个非空有限可合一公式集，则合一算法总是在步2停止，且最后的k即是S的最一般合一。5.2.45.2.4 谓词逻辑中的归结原理定义12 设C1,C2是两个无相同变元的子句，L1,L2分别是C1,C2中的两个文字，如果L1和L2有最一般合一，则子句 (C1-L1)(C2-L2)称作C1和C2的二元归结式(二元消解式)，C1和C2称作归结式的亲本子句，L1和L2称作消解

44、文字。例例5.185.18 设C1=P(x)Q(x),C2=P(a)R(y)，求C1,C2的归结式。解 取L1=P(x),L2=P(a),则L1与 L2的最一般合一=a/x，于是, (C1-L1)(C2-L2) =(P(a),Q(a)-P(a) (P(a),R(y)-P(a) =Q(a),R(y) = Q(a)R(y) 所以，Q(a)R(y)是C1和C2的二元归结式。 例例5.195.19 设C1=P(x,y)Q(a),C2=Q(x)R(y),求C1,C2的归结式。 解 由于C1,C2中都含有变元x,y，所以需先对其中一个进行改名,方可归结（归结过程是显然的，故从略）。 还需说明的是，如果在参

45、加归结的子句内部含有可合一的文字，则在进行归结之前，也应对这些文字进行合一，从而使子句达到最简。例如，设有两个子句： C1=P(x)P(f(a)Q(x) C2= P(y)R(b)定义定义1313 如果子句C中，两个或两个以上的文字有一个最一般合一，则C称为C的因子，如果C是单元子句，则C称为C的单因子。例例5.205.20 设C=P(x)P(f(y)Q(x), 令=f(y)/x，于是 C=P(f(y)Q(f(y)是C的因子。 定义14 子句C1,C2的消解式，是下列二元消解式之一： (1) C1和C2的二元消解式; (2) C1和C2的因子的二元消解式; (3) C1的因子和C2的二元消解式;

46、 (4) C1的因子和C2的因子的二元消解式。定理4 谓词逻辑中的消解式是它的亲本子句的逻辑结果。 由此定理我们即得谓词逻辑中的推理规则： C1C2 (C1-L1)(C2-L2) 其中C1,C2是两个无相同变元的子句，L1,L2分别是C1,C2中的文字，为L1与L2的最一般合一。 此规则称为谓词逻辑中的消解原理（或归结原理）。 例例5.215.21 求证G是A1和A2的逻辑结果。 A1: x(P(x)(Q(x)R(x) A2: x(P(x)S(x) G: x(S(x)R(x) 证 我们用反证法，即证明A1A2G不可满足。首先求得子句集S： (1) P(x)Q(x) (2) P(y)R(y) (

47、3) P(a) (4) S(a) (5) S(z) R(z)( G) 然后应用消解原理，得 (6)R(a) (2),(3),1=a/y (7)R(a) (4),(5),2=a/z (8) (6),(7)所以S是不可满足的，从而G是A1和A2的逻辑结果。(A1) (A2) S例 5.22 设已知： (1)能阅读者是识字的； (2)海豚不识字； (3)有些海豚是很聪明的。试证明：有些聪明者并不能阅读。 证 首先，定义如下谓词： R(x)：x能阅读。 L(x)：x识字。 I(x)：x是聪明的。 D(x)：x是海豚。 然后把上述各语句翻译为谓词公式：(1) x(R(x)L(x)(2) x(D(x) L

48、(x) 已知条件(3) x(D(x)I(x)(4) x(I(x)R(x) 需证结论 求题设与结论否定的子句集，得(1) R(x)L(x)(2) D(y) L(y)(3)D(a)(4)I(a)(5) I(z)R(z) 归结得 (6) R(a) (5)，(4)，a/z (7) L(a) (6)，(1)，a/x (8) D(a) (7), (2), a/y (9) (8), (3)这个归结过程的演绎树如图52所示。 图5-2 例5.22 归结演绎树 定理5 （归结原理的完备性定理）如果子句集S是不可满足的，那么必存在一个由S推出空子句的消解序列。 (该定理的证明要用到Herbrand定理，故从略。)

49、 5.3 应用归结原理求取问题答案应用归结原理求取问题答案v例例 5.23 已知：（1）如果x和y是同班同学，则x的老师也是y的老师。（2）王先生是小李的老师。（3）小李和小张是同班同学。 问：小张的老师是谁？解解： 定义谓词： T(x,y)：x是y的老师； C(x,y)：x，y是同班同学 改写已知条件为谓词公式： F1： x y z(C(x,y) T(z,x) T(z,y) F2：T(Wang, Li) F2：C(Li, Zhang)为了得到问题的答案，我们先证明小张的老师是存在的，即证明公式： G： xT(x, Zhang)反证法：求F1 F2 F3 G的子句集：（1） C(x,y) T(

50、z,x) T(z,y) （2）T(Wang, Li)（3）C(Li, Zhang)（4） T(u, Zhang)归结演绎，得（5） C(Li,y) T(Wang, Li) 由(1),(2),Wang/z, Li/x（6） C(Li,Zhang) 由(4),(5),Wang/u, Zhang/y（7） 由(3),(6)G为真，小张的老师存在，为了寻找该老师，给原来求证谓词的子句增加一个谓词ANS(u)。于是有：（4） T(u, Zhang) ANS(u)用（4）替换（4），则可得到结果（7） ANS(Wang)v归结原理求取问题的方法归结原理求取问题的方法:（1）寻找问题的合适求证目标谓词；（2

51、）增配（析取形式）一个辅助谓词（辅助谓词中变元与目标谓词变元一致）；（3）归结，直至归结式刚好剩下辅助谓词，即得问题答案。 5.4 归结策略v问题：问题： 前面用归结方法是人工的，这不是最终目的，人工智能要实现的是机器的推理，那么就需要自动推理。 这样，怎样让机器去自动归结子句就成为一个需要考虑的重要方面。 自动推理就是需要把算法用程序表示，让计算机运行。 算法如下：v步1 将子句集S置入CLAUSES表。v步2 若空子句NIL在CLAUSES中，则归结成功，结束。v步3 若CLAUSES表中存在可归结的子句对，则将归结式并入CLAUSES表，转步2。v步4 归结失败，退出。该怎样选择参与消解的子句？v穷举式归结方式 1、让所有子句两两进行归结，产生归结式集合S1，S1并入原CLAUSES中，记为S1。 2、让新CLAUSES中子句，即集合S1与S1中子句两两归结，产生归结式集合S2，S2并入S1中，记为S2。 3、以此类推，直至。 例5.25 设有如下的子句集S，我们用上述的穷举算法归结如下：S： (1) PQ (2) PQ (3) PQ (4) PQS1：(5) Q (1),(2) (6) P (1),(3) (7) Q