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

1、LOGO主讲：李 辉Email：第第5 5章章基于谓词逻辑的机器推理基于谓词逻辑的机器推理 序言序言什么是知识？什么是知识？知识：人们对客观事物（包括自然的和人造的）及其规律的认识，也包括人们利用客观规律解决实际问题的方法和策略等。知识表示是指面向计算机的知识描述或表达形式和方法。机器推理概述机器推理概述n机器推理： 就是计算机推理，也称自动推理。它是人工智能的核心课题之一。推理是人脑的一个基本功能和重要功能。几乎所有的人工智能领域都与推理有关。因此，要实现人工智能，就必须将推理的功能赋予机器，实现机器推理。n自动定理证明： 是机器推理的一种重要应用，它是利用计算机证明非数值性的结果，很多非数

2、值领域的任务如医疗诊断、信息检索、规划制定和难题求解等方法都可以转化一个定理证明问题。机器推理概述机器推理概述n自动定理证明的基本方法：定理证明器：它是研究一切可判定问题的证明方法。鲁滨逊的归结原理。人机交互进行定理证明：计算机作为数学家的辅助工具，用计算机帮助人完成手工证明中的难以完成的繁杂的大量计算推理和穷举。四色定理。判定法：该方法是对一类问题找出统一的计算机上可实现的算法。数学家吴文俊教授吴氏方法。自然演绎法：该方法依据推理规则从前提和公理中可以推出许多定理，如果待证明的定理在其中则定理得证。LT程序、证明平面几何的程序。机器推理概述机器推理概述n 基于归结原理的自动定理证明过程：定理

3、的自然语言描述定理的谓词公式描述子句集生成子句集定理得证应用归结规则归结策略自然语言处理生成谓词公式已知前提：F1：自然数都是大于零的整数。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)第第5章章 基于谓词逻辑的机器推理基于谓词逻辑的机器推理 ContentsContents5.1 一阶谓词逻辑一阶谓词逻辑5.2 归结演绎推理归结演绎推理 5.3 应

4、用归结原理求取问题答案应用归结原理求取问题答案 5.4 归结策略归结策略 5.5 归结反演程序举例归结反演程序举例 5.6 Horn子句归结与逻辑程序子句归结与逻辑程序 5.7 非归结演绎推理非归结演绎推理 5.1.15.1.1谓词、函数、量词（谓词、函数、量词（1 1）命题（proposition）：是具有真假意义的语句。命题代表人们进行思维时的一种判断，或者是否定，或者是肯定。命题可以用命题符号表示。用命题符号可以表示简单的逻辑关系和推理。 P:今天天气好 Q:去旅游 S1：我有名字 S2：你有名字PQ表示：如果今天天气好，就去旅游。此时，如果P（今天天气好）成立，则可以得到结论Q（去旅游

5、）5.1.15.1.1谓词、函数、量词（谓词、函数、量词（2 2）n对于复杂的知识，命题符号能力不够。对于复杂的知识，命题符号能力不够。n无法把所描述的客观事物的结构及逻辑特征无法把所描述的客观事物的结构及逻辑特征反映出来。反映出来。n无法把不同事物间的共同特征表达出来。无法把不同事物间的共同特征表达出来。F：老李是小李的父亲。S1：我有名字 S2：你有名字所有的人都有名字： SIS2 S3 5.1.15.1.1谓词、函数、量词（谓词、函数、量词（3 3）谓词谓词(predicate)(predicate)：一般形式为一般形式为P P（x x1 1, x, x2 2 , , , x xn n）

6、 P P为为谓词名，谓词名，用于刻画个体的性质、状态或用于刻画个体的性质、状态或个体间的关系。个体间的关系。 x x1 1，x x2 2， x xn n是是个体，个体，表示某个独立存表示某个独立存在的事物或者某个抽象的概念。在的事物或者某个抽象的概念。 S(x): x是学生； P(x,y): x是y的父亲。个体变元的变化范围称为个体域。包揽一切事物的集合称为全总个体域。5.1.15.1.1谓词、函数、量词（谓词、函数、量词（4 4）n函数：函数：为了表达个体之间的对应关系，引入数为了表达个体之间的对应关系，引入数学中函数概念和记法。用形如学中函数概念和记法。用形如f(xf(x1 1，x x2

7、2，x xn n) )来表示个体变元对应的个体来表示个体变元对应的个体y y，并称之为，并称之为n元个体函数元个体函数，简称函数。，简称函数。函数 father(x): 值为x的父亲。谓词D(father(Li):表示x的父亲是医生，值为真或假。符号约定：谓词大写字母； P(x,y) 函数小写字母；f(x) 变量 x、y、z、u、v； 常量a、b、c.。 P(a,y)5.1.15.1.1谓词、函数、量词（谓词、函数、量词（5 5）我们把“所有”、“一切”、“任一”、“全体”、“凡是”等词统称为全称量词, 记为x; 把“存在”、“有些”、“至少有一个”、 “有的”等词统称为存在量词, 记为x。

8、5.1.15.1.1谓词、函数、量词（谓词、函数、量词（5 5）表示“对个体域中所有的（或任一个）个体” 。记为x全称量词 表示“在个体域中存在个体”。记为x存在量词 如：“凡是人都有名字” 用M（x）表示“x是人”，N（x）表示“x有名字” x（M（x） N（x） 如：“存在不是偶数的整数”用G（x）表示“x是整数”，E（x）表示“x是偶数” x（G（x） E（x） 5.1.15.1.1谓词、函数、量词（谓词、函数、量词（6 6）用谓词表示命题时，一般取全总个体域，再采用使用限定谓词的方法来指出每个个体变元的个体域。(2)对存在量词，把限定词作为一个合取项加入。即 x(P(x)例5.2：对于

9、所有的自然数，均有x+yx x y（ N （x） N（y） S(x,y,x)）例5.3：某些人对某些食物过敏 x y(M(x) N(y) G（x，y）(1)对全称量词，把限定词作为蕴含式之前件加入。 即 x （P（x） ）例5.2：对于所有的自然数，均有x+yx 也可以用函数h（x，y）来表示x与y的和 x y（ N （x） N（y） G(h(x,y),x)）5.1.15.1.1谓词、函数、量词（谓词、函数、量词（7 7）例5.1：不存在最大的整数，我们可以把它表示为： x(G(x) y（G（y） D（x，y） x(G(x) y（G（y） D（y，x）用谓词表示命题时，形式并不是固定的。5.1

10、.15.1.1谓词、函数、量词（谓词、函数、量词（8 8）练习：用谓词公式表示下述命题。练习：用谓词公式表示下述命题。已知前提：已知前提：（1）自然数自然数都是都是大于零大于零的的整数整数。（2）所有整数不是）所有整数不是偶数偶数就是就是奇数奇数。（3）偶数）偶数除以除以2是整数。是整数。结论：所有自然数不是奇数就是一半为整数的数。结论：所有自然数不是奇数就是一半为整数的数。首先定义如下谓词： N(x):x是自然数。 I(x):x是整数。 E(x):x是偶数。 O(x):x是奇数。 GZ(x):x大于零。 s(x):x除以2。5.1.15.1.1谓词、函数、量词（谓词、函数、量词（9 9）将上

11、述各语句翻译成谓词公式：将上述各语句翻译成谓词公式：（1）自然数自然数都是都是大于零大于零的的整数整数。F1: F1: x (N(x)x (N(x)GZ(x) GZ(x) I(x) I(x)（2）所有整数不是）所有整数不是偶数偶数就是就是奇数奇数。F2: F2: x (I(x)x (I(x)(E(x) (E(x) O(x) O(x) （3）偶数）偶数除以除以2是整数。是整数。F3:F3: x (E(x) x (E(x) I(s(x) I(s(x)所有自然数不是奇数就是一半为整数的数。所有自然数不是奇数就是一半为整数的数。G: G: x (N(x)x (N(x)(I(s(x) (I(s(x) O

12、(x)O(x) 5.1.2 谓词公式谓词公式 定义1：项（1）个体常元和变元都是项。（2）f是n元函数符号，若t1，t2，tn是项，则 f（ t1，t2， tn ）是项。（3）只有有限次使用（1），（2）得到的符号串才是项。用谓词、量词及真值连结词可以表达相当复杂的命题，我们把命题的这种符号表达式称为谓词公式。从原子谓词公式出发，通过命题联结词和量词，可以组成复合谓词公式。下面给出谓词公式的严格定义，即谓词公式的生成规则。5.1.2 谓词公式谓词公式 定义2：原子公式 设P为n元谓词符号， t1，t2，tn为项， P（t1，t2，tn）称为原子谓词公式，简称原子或原子公式。5.1.2 谓词公式

13、谓词公式 定义3：谓词公式（1）原子公式是谓词公式。（2）若A、B是谓词公式，则A，A B，A B，A B， AB， xA， xA也是谓词公式。（3）只有有限步应用（1）（2）生成的公式才是谓词公式。谓词公式亦称为谓词逻辑中的合适（式）公式，记为Wff。 由项的定义，当t1，t2，tn全为个体常元时，所得的原子谓词公式就是原子命题公式（命题符号）。所以全体命题公式也是谓词公式。 5.1.2 谓词公式谓词公式 n辖域辖域：紧接于量词之后被量词作用（即说明）：紧接于量词之后被量词作用（即说明）的谓词公式称为该量词的辖域。的谓词公式称为该量词的辖域。n指导变元指导变元：量词后的变元为指导变元。：量词

14、后的变元为指导变元。n约束变元约束变元：在一个量词辖域中与该量词的指导：在一个量词辖域中与该量词的指导变元相同的变元称为约束变元。变元相同的变元称为约束变元。n自由变元自由变元：谓词公式中除了约束变元之外的变：谓词公式中除了约束变元之外的变元。元。 （1） x P（x） （2） y（G（y） D（x，y） （3） x G(x) P（x） 指导变元约束变元约束变元约束变元自由变元自由变元5.1.2 谓词公式谓词公式 n一个变元在一个公式中既可以约束出现，一个变元在一个公式中既可以约束出现，也可以自由出现，为了避免混淆，通过也可以自由出现，为了避免混淆，通过改名规则改名规则改名：改名：n对需要改名

15、的变元，应对需要改名的变元，应同时更改同时更改该变元在量该变元在量词及其辖域中的词及其辖域中的所有出现所有出现。n新变元符号必须是量词辖域内新变元符号必须是量词辖域内原先没有原先没有的，的，最好是最好是公式中公式中也也未出现未出现过的。过的。 x G(x) P（x） x G(x) P（y）5.1.2 谓词公式谓词公式 n谓词公式与命题的区别与联系谓词公式与命题的区别与联系n谓词公式是谓词公式是命题函数命题函数。n一个谓词公式中所有个体变元被量化，谓词一个谓词公式中所有个体变元被量化，谓词公式就变成了一个命题。公式就变成了一个命题。n从谓词公式得到命题的两种方法：给谓词中从谓词公式得到命题的两种

16、方法：给谓词中的个体变元代入个体常元；把谓词中的个体的个体变元代入个体常元；把谓词中的个体变元全部量化。变元全部量化。例：P（x）表示“x是素数” x P（x）， x P（x）， P（a）都是命题5.1.2 谓词公式谓词公式 n一阶谓词一阶谓词：仅个体变元被量化的谓词。：仅个体变元被量化的谓词。n二阶谓词二阶谓词：个体变元被量化，函数符号和谓词：个体变元被量化，函数符号和谓词符号也被量化。符号也被量化。 p x P（x）n全称命题：全称命题： x P(x)x P(x)等价于等价于P P (a (a1 1) ) P P(a(a2 2) ) P P(a(an n) ) n特称命题特称命题 x G(

17、x)x G(x)等价于等价于P P (a(a1 1) ) P P(a(a2 2) ) P P (a (an n) )5.1.2 谓词公式谓词公式 定义4：合取范式（Conjunctive Normal Form） 设A为如下形式的谓词公式： B1 B2 Bn其中Bi（i=1,2,，n）形如L1 L2 Lm，Lj（j=1，2,，m）为原子公式或其否定，则A称为合取范式。例 (P(x) Q(y) ( P(x) Q(y) R(x,y) ( Q(x) R(x,y) ) 就是一个合取范式5.1.2 谓词公式谓词公式 定义5：析取范式（Disjunctive Normal Form）设A为如下形式的谓词公

18、式： B1 B2 Bn其中Bi（i=1,2,，n）形如L1 L2 Lm，Lj（j=1，2,，m）为原子公式或其否定，则A称为析取范式。例 (P(x)Q(y)R(x,y)(P(x)Q(y)(P(x)R(x,y) ) 就是一个析取范式5.1.2 谓词公式谓词公式 谓词公式的解释谓词公式的解释 设设D D为谓词公式为谓词公式P P的个体域，若对的个体域，若对P P中的个体常量、函数中的个体常量、函数和谓词按如下规定赋值：和谓词按如下规定赋值： （1 1）为）为每个个体常量每个个体常量指派指派D D中的一个元素；中的一个元素； （2 2）为）为每个每个n n元函数元函数指派一个从指派一个从D Dn n

19、到到D D的映射，其中的映射，其中 D Dn n(x(x1 1,x,x2 2,x,xn n)/x)/x1 1,x,x2 2,x,xn n DD （3 3）为）为每个每个n n元谓词元谓词指派一个从指派一个从D Dn n到到F,TF,T的映射。的映射。 则称这些指派为公式则称这些指派为公式P P在在D D上的一个解释。上的一个解释。5.1.2 谓词公式谓词公式 例：设个体域例：设个体域D D1,2,1,2,求公式求公式A A x x yP yP（x x，y y）在）在D D上的解释，并指出在每一种解释下公式上的解释，并指出在每一种解释下公式A A的真值。的真值。解：公式里没有个体常量和函数，所以

20、直接为解：公式里没有个体常量和函数，所以直接为谓词指派谓词指派真值真值，设为，设为 P（1，1）T P（1，2）F P（2，1）T P（2，2）F 这就是这就是A A在在D D上的一个解释。上的一个解释。在此解释下：在此解释下： 当当x x1 1时有时有y y1 1使使P P（x x，y y）的真值为）的真值为T T； 当当x x2 2时有时有y y1 1使使P P（x x，y y）的真值为）的真值为T T；即对于即对于D D中的所有中的所有X X都有都有y y1 1使使P P（x x，y y）的真值为）的真值为T T，所以在此解释下公式所以在此解释下公式A A的真值为的真值为T T。5.1.

21、2 谓词公式谓词公式 例：设个体域例：设个体域D D1,2,1,2, 求公式求公式A A x x P P（x x） Q Q（f(x),bf(x),b）在在D D上的解释，上的解释，并指出在每一种解释下公式并指出在每一种解释下公式A A的真值。的真值。解：解：为为个体常量个体常量b b指派指派D D中的值：中的值： b=1 b=1 为为函数函数f(x)f(x)指派指派D D中的值中的值 f(1)=2,f(2)=1f(1)=2,f(2)=1 对对谓词谓词指派真值为：指派真值为： P(1)=F, P(2)=T,Q(1,1)=T, Q(2,1)=FP(1)=F, P(2)=T,Q(1,1)=T, Q(

22、2,1)=F 5.1.2 谓词公式谓词公式 在此解释下，在此解释下， 当当x1时有：时有： P(1)=F, Q(f(1),1)=Q(2,1)=FP(1)=F, Q(f(1),1)=Q(2,1)=F 所以所以P P（x x） Q Q（f(x),bf(x),b）为）为T T。 当当x x2 2时有时有 P(2)=T, Q(f(2),1)=Q(1,1)=TP(2)=T, Q(f(2),1)=Q(1,1)=T 所以所以P P（x x） Q Q（f(x),bf(x),b）为）为T T。 即对个体域即对个体域D D中的所有中的所有x x均有均有P P（x x） Q Q（f(x),bf(x),b），所），所

23、以公式以公式B B在此解释下的真值为在此解释下的真值为T T。5.1.2 谓词公式谓词公式 定义6：谓词公式在个体域上的永真、永假、可满足设P为谓词公式，D为其个体域，对于D中的任一解释I：（1）若P恒为真，则称P在D上永真或是D上的永真式。（2）若P恒为假，则称P在D上永假或是D上的永假式。（3）若至少有一个解释，可是P为真，则称P在D上是可满足式。5.1.2 谓词公式谓词公式 定义7：谓词公式全个体域上的永真、永假、可满足设P为谓词公式，对于任何个体域：（1）若P都永真，则称P为永真式。（2）若P都永假，则称P为永假式。（3）若P都可满足，则称P为可满足式。谓词公式的真值与个体域及真值有关

24、，考虑到个体域的数目和个体域中元素数目无限的情形，所以要通过算法判断一个谓词公式永真是不可能的，所以称一阶谓词逻辑是不可判定的（但它是半可判定的）。 5.1.3 谓词逻辑中的形式演绎推理谓词逻辑中的形式演绎推理n自然演绎推理自然演绎推理 利用一阶谓词推理规则的符号表示形式，可以把关利用一阶谓词推理规则的符号表示形式，可以把关于自然语言的逻辑推理问题，转化为符号表达式的推于自然语言的逻辑推理问题，转化为符号表达式的推演变换。这种推理十分类似于人们用自然语言推理的演变换。这种推理十分类似于人们用自然语言推理的思维过程，因而称为自然演绎推理。思维过程，因而称为自然演绎推理。n常用逻辑等价式常用逻辑等

25、价式n常用逻辑蕴含式常用逻辑蕴含式 常用逻辑等价式常用逻辑等价式(1)常用逻辑等价式常用逻辑等价式(2)常用逻辑等价式常用逻辑等价式(3)常用逻辑等价式常用逻辑等价式(4)常用逻辑蕴含式常用逻辑蕴含式(1)常用逻辑蕴含式常用逻辑蕴含式(2) 5.1.3 谓词逻辑中的形式演绎推理谓词逻辑中的形式演绎推理例5.4 设有前提： （1）凡是大学生都学过计算机； （2）小王是大学生。 试问：小王学过计算机吗？)x(M)x(S(x)(1)a(S)(2)a(M)a(S)(2)a(S)(3)a(M)(4解：令S（x）：x是大学生M（x）：x学过计算机；a：小王上面命题用谓词公式表示为：)x(M)x(S(x)(

26、1前提(1),US前提(2),(3),I3我们进行形式推理：M(a)，即小王学过计算机。xA(x)=A(y)y是个体域中任一确定元素(A B) A = B 5.1.3 谓词逻辑中的形式演绎推理谓词逻辑中的形式演绎推理例5.5 证明 是 和 的逻辑 结果。)b, a(P )y, x(W)y, x(P(yx )b, a(W )y, a(W)y, a(P(y)( 2)b,a(W)b,a(P)(3)b, a(P)( 5证：)y, x(W)y, x(P(yx)( 1前提(1),US(2),US)b, a(W)( 4前提(3),(4),I4(A B) B = A 拒取式 5.1.3 谓词逻辑中的形式演绎推

27、理谓词逻辑中的形式演绎推理例5.6 证明 )x(P)x(R(x)x(Q)x(R(x)x(Q)x(P(x 证：)x(Q)x(P(x)( 1前提(1),US(2),E24(3),(5),I6)y(Q)y(P)(2)()()3(yPyQ)y(Q)y(R)( 5)y(P)y(R)( 6)x(P)x(R(x)( 7)x(Q)x(R(x)( 4前提(4),US(6),UGAB = B A 逆反律(AB) (BC) = A B 假言三段论A(y) = xA(x) 全称推广规则5.2 归结演绎推理归结演绎推理-5.2.1子句集子句集(1)定义1：原子谓词公式及其否定称为文字 若干个文字的一个析取式称为一个子句

28、 由r个文字组成的子句叫r-文字子句 1-文字子句叫单元子句 不含任何文字的子句称为空子句，记为或NIL。例如： D(y) I(a) P Q R I(z)R(z) 5.2.1子句集子句集(2)n谓词公式例谓词公式例 xx yP(x,y)yP(x,y) yQ(x,y)yQ(x,y)R(x,y)R(x,y)n子句集例子句集例 P(x,f(x) P(x,f(x) Q(x,g(x), Q(x,g(x), P(y,f(y) P(y,f(y) R(y,g(y) R(y,g(y)谓词公式与子句集有哪些区别？“”作用原子谓词没有量词( 、 )合取范式元素之间变元不同定义2：对一个谓词公式G，通过以下步骤所得的

29、子句集 S，称为G的子句集（clauses）。 集合形式没有蕴含词、等值词5.2.1子句集子句集(3)例5.7：x y P(x，y) yQ(x,y) R(x,y)由第一步可得： x y P(x，y) y Q(x,y) R(x,y)1、消蕴含词和等值词理论根据：AB A B A B (A B) ( B A)蕴含等价式问题:蕴含式 y P(x，y) yQ(x,y)R(x,y)的前件是？1 ： y P(x，y) 2 ：P(x，y) 5.2.1子句集子句集(4)n子句集的特征子句集的特征“”作用原子谓词没有量词( 、 )合取范式元素之间变元不同集合形式没有蕴含词、等值词5.2.1子句集子句集(5)x

30、y P(x，y) y Q(x,y) R(x,y) 2、移动否定词作用范围，使其仅作用于原子公式理论根据： (A) A (A B) A B (A B) A B xP(x) xP(x) xP(x) xP (x)双重否定律摩根定律量词转换定律= x y P(x，y) y Q(x,y) R(x,y) = x y P(x，y) y ( Q(x,y) R(x,y)= x y P(x，y) y Q(x,y) R(x,y)5.2.1子句集子句集(6)n子句集的特征子句集的特征“”作用原子谓词没有量词( 、 )合取范式元素之间变元不同集合形式没有蕴含词、等值词5.2.1子句集子句集(7)= x y P(x，y)

31、 zQ(x,z) R(x,z)3、适当改名，使变量标准化即：对于不同的约束，对应于不同的变量x y P(x，y) y Q(x,y) R(x,y)问题:不同辖域的相同变元对应的约束相同吗?5.2.1子句集子句集(8)4、 消去存在量词 (Skolem化）,同时进行变元替换 原则： 若该存在量词不在任何全称量词的辖域内，则用一 个常量符号代替该存在量词辖域内的相应约束变元， 这个常量叫Skolem常量； 若该存在量词在全称量词的辖域内，则用这些全 称量词指导变元的一个函数代替该存在量词辖域 内的相应约束变元，这样的函数称为Skolem函数。理论依据： xA（x）=A（y）y是个体域中某一确定的元素

32、。 存在指定规则 5.2.1子句集子句集(9)问题:为什么受全称量词约束的要用Skolem函数替换? 而不能用常量替换？x yM（y，x）：对任意一个人x，都存在一个y，y是x的妈妈。若去掉存在量词用常量a代替y，则变为：x M（a，x）：a是所有人的妈妈。实际上，引入Skolem函数，是由于存在量词在全称量词的辖域之内，其约束变元的取值完全依赖于全称变量的取值。而Skolem函数反映了这种依赖关系。5.2.1子句集子句集(10)x y P(x，y) zQ(x,z) R(x,z)= x P(x，f(x) Q(x，g(x) R(x，g(x)= P(x，f(x) Q(x,g(x) R(x,g(x)

33、5、消去所有全称量词。理论依据： xA（x）=A（y） y是个体域中任一确定的元素。 全称指定规则 5.2.1子句集子句集(11)n子句集的特征子句集的特征“”作用原子谓词没有量词( 、 )合取范式元素之间变元不同集合形式没有蕴含词、等值词5.2.1子句集子句集(12)= P(x，f(x) Q(x,g(x) P(x，f(x) R(x,g(x)6、化公式为合取范式 理论依据： A（B C） （A B） （A C） （ A B ） C （A C） （B C） P(x，f(x) Q(x,g(x) R(x,g(x) 分配律 5.2.1子句集子句集(13)n子句集的特征子句集的特征“”作用原子谓词没有量

34、词( 、 )合取范式元素之间变元不同集合形式没有蕴含词、等值词5.2.1子句集子句集(14)= P(x，f(x) Q(x,g(x) P(y，f(y) R(y,g(y)7、适当改名，使子句间无同名变元= P(x，f(x) Q(x,g(x) , P(y，f(y) R(y,g(y)8、消去合取词，以子句为元素组成一个集合S= P(x，f(x) Q(x,g(x) R(x,g(x)5.2.1子句集子句集(15)消去蕴含词和等值词使否定词仅作用于原子公式使量词间不含同名指导变元消去存在量词消去全称量词化公式为合取范式子句间无同名变元组成一个集合“”作用原子谓词没有量词( 、 )合取范式元素之间变元不同集合

35、形式没有蕴含词、等值词蕴含等价式双重否定律、摩根定律、量词转换律存在指定、依赖关系全称指定分配律5.2.1子句集子句集(16)练习：用谓词公式表示下述命题。练习：用谓词公式表示下述命题。已知前提：已知前提：（1）自然数都是大于零的整数。）自然数都是大于零的整数。（2）所有整数不是偶数就是奇数。）所有整数不是偶数就是奇数。（3）偶数除以）偶数除以2是整数。是整数。结论：所有自然数不是奇数就是一半为整数的数。结论：所有自然数不是奇数就是一半为整数的数。化化F1 F1 F2 F2 F3 F3 GG的的子句集。子句集。 F1: F1: x (N(x)x (N(x)GZ(x) GZ(x) I(x) I(

36、x) F2: F2: x (I(x)x (I(x)(E(x) (E(x) O(x) O(x) F3: F3: x (E(x) x (E(x) I(s(x) I(s(x) G: G: x (N(x)x (N(x)(I(s(x) (I(s(x) O(x)O(x)5.2.1子句集子句集(17)解：解：F1 F1 F2 F2 F3 F3 G G的子句集为的子句集为（1 1） N(x) N(x) GZ(x) GZ(x)（2 2） N(y) N(y) I(y) I(y)（3 3） I(z) I(z) E(z) E(z) O(z)O(z)（4 4） E(u) E(u) I(s(u) I(s(u)（5 5）N

37、(a)N(a)（6 6） O(a) O(a) （7 7） I(s(a)I(s(a)5.2.1子句集子句集(18)Skolem标准型 在求子句集的过程中，消去存在量词之后，把所有全称量词都依次移到式子的最左边（或者把所有的量词都依次移到式子最左边，再消去存在量词），再将右部的式子化为合取范式，这样得到的式子就是Skolem标准型。x y P(x，y) zQ(x,z) R(x,z)= x P(x，f(x) Q(x,g(x) R(x,g(x) = x P(x，f(x) Q(x,g(x) P(x，f(x) R(x,g(x) P(x，f(x) Q(x,g(x) , P(y，f(y) R(y,g(y)消去

38、合取词和全称量词，就得到了原公式的子句集5.2.1子句集子句集(19)例5.8设)w, v,u(Q)z, y, x(P(wvuzyxG 消去存在量词 用a代替x 用f（y，z）代替u 用g（y，z，v）代替w得到G的Skolem标准型( ( , , )( ( , ), , ( , , )y z v P a y zQ f y z v g y z v 进而得G的子句集为： ( , , ),( ( , ), , ( , , )P a x yQ f u v w g u v w5.2.1子句集子句集(20) 引入Skolem函数，是由于存在量词在全称量词的辖域内，其约束变元的取值完全依赖于全称量词的取值

39、。Skolem反映了这种依赖关系。 但Skolem标准型与原公式一般并不等价。 有公式： G xP(x) 它的Skolem标准型是 G P(a) 我们给出如下的解释I： D0,1, a/0, P(0)/F, P(1)/T 在此解释下，GT,G F5.2.1子句集子句集 题目：题目：把下面的表达式转换成子句形式。把下面的表达式转换成子句形式。)()()()()()()(xQxPxxQxxPx)()()()(xQxPxxxQxxP)()()()(zQzPzyQyxPx)()()()(zQzPyQxPzyx),(),()(),(),()(yxfQyxfPyQyxfQyxfPxP),(),()(),(

40、),()(yxfQyxfPyQyxfQyxfPxP参考解答：5.2.1子句集子句集 题目：题目：把下面的表达式转换成子句形式。（把下面的表达式转换成子句形式。（2 2）参考解答：),()(),()()()(zyxRzzxQzxxPx),(),()(tybRzbQaP),(),()(zyxzRzxzQxxxP),(),()(zyxzRzxzQxxPx),(),()(zyuzRzuzQuxPx),(),()(tyuRzuQxPtzux),(),()(tybRzbQaPtz注意：常元一般用a,b,c，变元用字母表后面的字母5.2.1子句集子句集(21)定理定理1：谓词公式：谓词公式G不可满足当且仅当

41、其子句集不可满足当且仅当其子句集S不可满不可满 足。足。定义定义3：子句集：子句集S是不可满足的，当且仅当其全部子句的是不可满足的，当且仅当其全部子句的 合取式是不可满足的。合取式是不可满足的。5.2.2 命题逻辑中的归结原理命题逻辑中的归结原理(1)n归结原理的提出归结原理的提出 归结原理归结原理(principle of resolution)(principle of resolution)又称消解原又称消解原理理,1965,1965年鲁滨逊（年鲁滨逊（J.A.RobinsonJ.A.Robinson）提出，从理论上解）提出，从理论上解决了定理证明问题。决了定理证明问题。归结原理提出的是

42、一种证明子句归结原理提出的是一种证明子句集不可满足性，从而实现定理证明的一种理论及方法集不可满足性，从而实现定理证明的一种理论及方法。定义定义4 设L为一个文字，则称L与乛L为互补文字。 定义定义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的归结式为乛PRS5.2.2 命题逻辑中的归结原理命题逻辑中的归结原

43、理(2)5.2.2 命题逻辑中的归结原理命题逻辑中的归结原理(3)定理定理2 归结式是其亲本子句的逻辑结果。归结式是其亲本子句的逻辑结果。证明：设证明：设C C1 1=L=L C C1 1， C C2 2 = = L L C C2 2 其中其中C C1 1 、 C C2 2 都是文字的析取式。都是文字的析取式。 C C1 1 C C2 2的归结式为的归结式为C C1 1 C C2 2 C C1 1 C C2 2的逻辑结果为：的逻辑结果为： C C1 1= C= C1 1 L= L= C C1 1 L L C2= C2= L L C C2 2= = L L C C2 2 由假言三段论可得：由假言

44、三段论可得： C C1 1 C C2 2 = = （ C C1 1 L L） （L LC C2 2） = C= C1 1 C C2 2= C= C1 1 C C2 2命题逻辑中的归结原理：命题逻辑中的归结原理：)L(C)L(CCC221121例例5.10 用归结原理验证分离规则和拒取式用归结原理验证分离规则和拒取式 A(AB) B (AB) B A 解解 A(AB) A( AB) B (AB) B ( AB)( B) A 5.2.2 命题逻辑中的归结原理命题逻辑中的归结原理(4)n类似的可以验证其他推理规则。这说明，归结原理可类似的可以验证其他推理规则。这说明，归结原理可以代替其他所有的推理规

45、则，而且推理步骤比较机械，以代替其他所有的推理规则，而且推理步骤比较机械，为机器推理提供了方便。为机器推理提供了方便。n由归结原理可知由归结原理可知 ：L L L L NILNIL 另外我们知道：另外我们知道：L L L L F F（假），（假）， 也就是也就是 NIL FNIL F5.2.2 命题逻辑中的归结原理命题逻辑中的归结原理(5)补充：补充： 定理1 G为F1, F2, ，Fn的逻辑结论，当且仅当 （F1 F2 Fn）=G 定理2 G为F1, F2, ，Fn的逻辑结论，当且仅当 (F1 F2 Fn)G 是不可满足的。n利用归结原理证明命题公式的思路利用归结原理证明命题公式的思路n先求

46、出要证明的命题公式的否定式的子句集先求出要证明的命题公式的否定式的子句集S S；n然后对子句集然后对子句集S S（一次或者多次）使用归结原理；（一次或者多次）使用归结原理；n若在某一步推出了空子句，即推出了矛盾，则说明若在某一步推出了空子句，即推出了矛盾，则说明子句集子句集S S是不可满足的，从而原否定式也是不可满是不可满足的，从而原否定式也是不可满足的，进而说明原公式是永真的。足的，进而说明原公式是永真的。5.2.2 命题逻辑中的归结原理命题逻辑中的归结原理(6)n推出空子句就说明子句集不可满足，原因是：推出空子句就说明子句集不可满足，原因是：n空子句就是空子句就是F，推出空子句就是推出了，

47、推出空子句就是推出了F。n归结原理是正确的推理形式，由正确的推理形式推归结原理是正确的推理形式，由正确的推理形式推出了出了F，则说明前提不真，即归结出空子句的两个，则说明前提不真，即归结出空子句的两个亲本子句至少有一个为假。亲本子句至少有一个为假。n而这两个亲本子句如果都是原子句集而这两个亲本子句如果都是原子句集S中的子句则中的子句则S不可满足。不可满足。n如果这两个亲本子句不是或不全是如果这两个亲本子句不是或不全是S中的子句，那中的子句，那么它们必定是某次归结的结果。么它们必定是某次归结的结果。n同样的道理向上回溯，一定会推出原子句集中至少同样的道理向上回溯，一定会推出原子句集中至少有一个子

48、句为假，从而说明有一个子句为假，从而说明S不可满足。不可满足。5.2.2 命题逻辑中的归结原理命题逻辑中的归结原理(7)5.2.2 命题逻辑中的归结原理命题逻辑中的归结原理(8)推论推论 设设C C1 1， C C2 2是子句集是子句集S S的两个子句，的两个子句，C C1 21 2是是 它们的归结式，则它们的归结式，则（1 1）若用）若用C C1 21 2来代替来代替C C1 1， C C2 2 ，得到新的子句集，得到新的子句集S S1 1 ，则由，则由S S1 1不可满不可满足性可以推出原子句集足性可以推出原子句集S S的不可满足性。即的不可满足性。即 （2 2）若用）若用C C1 21

49、2加入到加入到S S中，得到新的子句集中，得到新的子句集S S2 2 ，则，则S S2 2与原与原S S的同不的同不可满足。即可满足。即S1的不可满足性的不可满足性= S不可满足不可满足S2的不可满足性的不可满足性 S不可满足不可满足例例5.12 设公理集：设公理集：P, (P Q) R, (S T) Q, T求证：求证：R 化子句集：化子句集： (P(P Q) Q) R R= (P= (P Q)Q) R R= P= P QQ R R (S (S T) T) Q Q= (S= (S T)T) Q Q= (S= (S T)T) Q Q= (S= (S Q) Q) (T(T Q)Q)= S= S

50、Q, TQ, T QQ子句集：子句集：(1) P(1) P(2) (2) P P Q Q R R(3) (3) S S Q Q(4) (4) T T Q Q(5) T(5) T(6) (6) R R（目标求反）（目标求反） 5.2.2 命题逻辑中的归结原理命题逻辑中的归结原理(9)子句集：子句集：(1) P(1) P(2) (2) P P Q Q R R(3) (3) S S Q Q(4) (4) T T Q Q(5) T(5) T(6) (6) R R（目标求反）（目标求反）归结：归结：(7) (7) P P Q (2, 6)Q (2, 6)(8) (8) Q Q (1, 7) (1, 7)

51、 (9) (9) T (4, 8)T (4, 8) (10)NIL (5, 9) (10)NIL (5, 9)P Q RRP QPQT QTTNIL5.2.2 命题逻辑中的归结原理命题逻辑中的归结原理(10)例例5.11 5.11 证明子句集证明子句集 P P Q, Q, P, P, Q Q 是不可满足。是不可满足。5.2.2 命题逻辑中的归结原理命题逻辑中的归结原理(11)5.2.3 5.2.3 替换与合一替换与合一(1)(1)n问题问题 在一阶谓词中应用消解原理，无法直接找到互否文字在一阶谓词中应用消解原理，无法直接找到互否文字的子句对的子句对 例如：例如： P(P(x x) ) Q(z)

52、Q(z), , P( P(f(y)f(y) ) R(y)R(y) P(P(x x) ) Q(y)Q(y), , P( P(a a) ) R(z)R(z)n解决方法解决方法 对个体变元做适当替换对个体变元做适当替换 例如：例如： P(P(f(y)f(y) ) Q(z)Q(z), , P(f(y) P(f(y) R(y)R(y) P(P(a a) ) Q(y)Q(y), , P(a) P(a) R(z)R(z)5.2.3 5.2.3 替换与合一替换与合一(2)(2)定义6 一个替换（Substitution）是形如 t1/x1, t2/x2, , tn/xn的有限集合，其中t1, t2, , tn

53、是项，称为替换的分子；x1, x2, , xn是互不相同的个体变元，称为替换的分母；ti, xi不同， xi不循环出现在tj中；ti/xi 表示用ti替换xi 。若其中t1, t2, , tn是不含变元的项（称为基项）时，该替换为基替换；没有元素的替换称为空替换，记作，表示不作任何替换。a/x,g(a)/y,f(g(b)/z就是一个替换g(y)/x,f(x)/y就不是一个替换，x与y出现了循环替换 表达式：项、原子公式、文字、子句的统称。 基表达式：没有变元的表达式。 子表达式：出现在表达式E中的表达式称为E的子表达式。定义7 设=t1/x1,t2/x2, ,tn/xn是一个替换，E是一个表达

54、式，对公式E实施替换，即把E中出现的个体变元xj都是tj的替换，记为E ， 所得的结果称为E在下的例（instance）。例如：若= a/x,f(b)/y,c/z,G=P(x,y,z) G = P(a,f(b),c)5.2.3 5.2.3 替换与合一替换与合一(3)(3)5.2.3 5.2.3 替换与合一替换与合一(4)(4)定义8 设 t1/x1, t2/x2, , tm/xm， u1/y1, u2/y2, , un/yn是两个替换，则将 t1/x1,t2/x2,tm/xm ,u1/y1,u2/y2,un/yn 中符合下列条件的元素删除 （1） ti /xi 当ti xi （2） ui/yi

55、 当yi x1, xn 这样得到的集合为 与 的复合或乘积，记为 。例5.13：设= f(y)/x,z/y, =a/x,b/y,y/z t1 /x1, t2 /x2, u1/y1, u2/y2, u3/yn =f(b)/x，y/y，a/x，b/y，y/z 从而 =f(b)/x， y/z定义定义9 9 设设S SFF1 1,F,F2 2, ,F,Fn n 是一个原子谓词公式集，若是一个原子谓词公式集，若存在一个替换存在一个替换，可使，可使 F F1 1 =F=F2 2 = =F=Fn n ，则称，则称为为S S的一个的一个合一合一，称，称S S为为可合一可合一的。的。 例：例： P(x, f(y

56、), B), P(z, f(B), B) 替换替换s=A/x, B/y, A/z是一个合一是一个合一, 因为：因为： P(x, f(y), B)s= P(A, f(B), B) P(z, f(B), B)s= P(A, f(B), B)替换替换s=z/x, B/y和替换和替换s=x/z, B/y也都是合一。也都是合一。一个公式的合一一般不唯一一个公式的合一一般不唯一5.2.3 5.2.3 替换与合一替换与合一(5)(5)5.2.3 5.2.3 替换与合一替换与合一(5)(5)定义定义10 10 设设是原子公式集是原子公式集S S的一个合一，如果对的一个合一，如果对S S的任何的任何一个合一一个

57、合一都存在一个替换都存在一个替换，使得，使得 则称则称为为S S的的最一般合一最一般合一( (Most General UnifierMost General Unifier),),简称简称MGUMGU。一个公式集的一个公式集的MGU也是不唯一的。也是不唯一的。例：例： 设设SP(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 使得使得 5.2.4 5.2.4 谓词逻辑中的归结原理谓词逻辑中

58、的归结原理(1)(1)例例5.21求证求证G是是A1和和A2的逻辑结果。的逻辑结果。 A1： ( x)(P(x)(Q(x) R(x) A2 ：( x)(P(x) S(x) G：( x)(S(x) R(x)证：利用归结反演法，先证明证：利用归结反演法，先证明A1 A2 G是不可满足的。是不可满足的。 求子句集：求子句集： (1) P(x) Q(x) (2) P(y) R(y) (3)P(a) (4)S(a) (5) S(z) R(z) (G)A A2 2A A1 1S S5.2.4 5.2.4 谓词逻辑中的归结原理谓词逻辑中的归结原理(2)(2)应用消解原理，得：应用消解原理，得： (6)R(a

59、) (2),(3), 1=a/y (7) R(a) (4),(5), 2 =a/z (8)Nil (6),(7)所以所以S是不可满足的，从而是不可满足的，从而G是是A1和和A2的逻辑结果的逻辑结果。子句集子句集S (1) P(x) Q(x) (2) P(y) R(y) (3)P(a) (4)S(a) (5) S(z) R(z)例例5.22 设已知：设已知： （1）能阅读者是识字的；）能阅读者是识字的； （2）海豚不识字；）海豚不识字； （3）有些海豚是很聪明的。）有些海豚是很聪明的。 试证明：有些聪明者并不能阅读。试证明：有些聪明者并不能阅读。证证 首先定义如下谓词：首先定义如下谓词： R(x

60、):x能阅读。能阅读。 L(x):x能识字。能识字。 I(x):x是聪明的。是聪明的。 D(x):x是海豚。是海豚。将上述各语句翻译成谓词公式：将上述各语句翻译成谓词公式： (1) ( x)(R(x)L(x) (2) ( x)(D(x)L(x) 已知条件已知条件 (3) ( x) (D(x) I(x) (4) ( x) (I(x) R(x) 需证结论需证结论5.2.4 5.2.4 谓词逻辑中的归结原理谓词逻辑中的归结原理(3)(3)5.2.4 5.2.4 谓词逻辑中的归结原理谓词逻辑中的归结原理(4)(4)用归结反演法来证明，求题设与结论否定的子句集，得：用归结反演法来证明，求题设与结论否定的