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

1、2022-3-11第第3 3章章 基于谓词逻辑的机器推理基于谓词逻辑的机器推理2022-3-12内容内容3.1 3.1 机器推理概述机器推理概述3.2 3.2 谓词逻辑简介谓词逻辑简介3.3 3.3 自然演绎推理自然演绎推理3.4 3.4 归结演绎推理归结演绎推理3.5 3.5 归结原理与归结原理与PROLOGPROLOG程序程序3.6 3.6 基于规则的演绎推理基于规则的演绎推理2022-3-133.1 3.1 机器推理概述（机器推理概述（1 1）n 机器推理机器推理 推理是人脑的一个基本功能和重要功能，几乎所有的推理是人脑的一个基本功能和重要功能，几乎所有的人工智能领域都与推理有关。因此，

2、要实现人工智能，就人工智能领域都与推理有关。因此，要实现人工智能，就必须将推理的功能赋予机器，实现机器推理。机器推理也必须将推理的功能赋予机器，实现机器推理。机器推理也称为是计算机推理，或自动推理，它也是人工智能的核心称为是计算机推理，或自动推理，它也是人工智能的核心课题之一。课题之一。 n自动定理证明：自动定理证明： 是机器推理的一种重要应用，它是利用计算机证明非是机器推理的一种重要应用，它是利用计算机证明非数值性的结果，很多非数值领域的任务如医疗诊断、信息数值性的结果，很多非数值领域的任务如医疗诊断、信息检索、规划制定和难题求解等方法都可以转化一个定理证检索、规划制定和难题求解等方法都可以

3、转化一个定理证明问题明问题。2022-3-14n自动定理证明的基本方法：自动定理证明的基本方法：3.1 3.1 机器推理概述（机器推理概述（2 2）定理证明器：定理证明器：它是研究一切可判定问题的证明方法。它是研究一切可判定问题的证明方法。鲁滨逊的归结原理。鲁滨逊的归结原理。自然演绎法自然演绎法：该方法依据推理规则从前提和公理中可以：该方法依据推理规则从前提和公理中可以推出许多定理，如果待证明的定理在其中则定理得证。推出许多定理，如果待证明的定理在其中则定理得证。LTLT程序、证明平面几何的程序。程序、证明平面几何的程序。2022-3-15n基于归结原理的自动定理证明过程：基于归结原理的自动定

4、理证明过程：3.1 3.1 机器推理概述（机器推理概述（3 3）定理的自然语言描述定理的自然语言描述定理的谓词公式描述定理的谓词公式描述子句集子句集生成子句集生成子句集定理得证定理得证应用归结规则和归结策略应用归结规则和归结策略自然语言处理生成谓词公式自然语言处理生成谓词公式已知前提：已知前提：F F1 1：自然数都是大于零的整数。：自然数都是大于零的整数。F F2 2：所有整数不是偶数就是奇数。：所有整数不是偶数就是奇数。F F3 3：偶数除以：偶数除以2 2是整数。是整数。结论结论G G：所有自然数不是奇数就是一：所有自然数不是奇数就是一半为整数的数。半为整数的数。定理的谓词公式描述：定理

5、的谓词公式描述： F F1 1: : x (N(x)x (N(x)GZ(x) GZ(x) I(x) I(x) F F2 2: : x (I(x)x (I(x)(E(x) (E(x) O(x) O(x) F F3 3: : 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)2022-3-16基于规则的演绎推理基于规则的演绎推理 ：把已知判断中的知识表示成规：把已知判断中的知识表示成规则的形式（包括则的形式（包括F-F-规则和规则和B-B-规则），运用规则从已知判规则），运用规则从已知判断的事实或待证

6、明的结论出发进行推理的过程断的事实或待证明的结论出发进行推理的过程 . .3.1 3.1 机器推理概述（机器推理概述（4 4）2022-3-173.2 3.2 谓词逻辑简介谓词逻辑简介3.2.1 3.2.1 基于命题逻辑的知识表示基于命题逻辑的知识表示 3.2.2 3.2.2 谓词逻辑谓词逻辑 3.2.3 3.2.3 基于谓词逻辑的知识表示基于谓词逻辑的知识表示 2022-3-183.2.13.2.1基于命题逻辑的知识表示基于命题逻辑的知识表示（1 1）命题（命题（propositionproposition）：）：是具有真假意义的语句。命题代表人是具有真假意义的语句。命题代表人们进行思维时的

7、一种判断，或者是否定，或者是肯定。们进行思维时的一种判断，或者是否定，或者是肯定。命题可以用命题符号表示。命题可以用命题符号表示。用命题符号可以表示简单的逻辑关系和推理。用命题符号可以表示简单的逻辑关系和推理。 P:P:今天天气好今天天气好 Q:Q:去旅游去旅游 S1S1：我有名字：我有名字 S2S2：你有名字：你有名字P PQ Q表示：如果今天天气好，就去旅游。表示：如果今天天气好，就去旅游。此时，如果此时，如果P P（今天天气好）今天天气好）成立，则可以得到结论成立，则可以得到结论Q Q（去旅游去旅游）2022-3-193.2.13.2.1基于命题逻辑的知识表示基于命题逻辑的知识表示（2

8、2）n对于复杂的知识，命题符号能力不够。对于复杂的知识，命题符号能力不够。n无法把所描述的客观事物的结构及逻辑特征无法把所描述的客观事物的结构及逻辑特征反映出来。反映出来。n无法把不同事物间的共同特征表达出来。无法把不同事物间的共同特征表达出来。F：老李是小李的父亲。：老李是小李的父亲。S1：我有名字：我有名字 S2：你有名字：你有名字所有的人都有名字：所有的人都有名字： SI S2 S3 2022-3-1103.2.2 3.2.2 谓词逻辑谓词逻辑（1 1）谓词谓词(predicate)：一般形式为一般形式为P（x1, x2 , xn ） P为为谓词名，谓词名，用于刻画个体的性质、状态用于刻

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

10、x x2 2，x xn n) )来表示个体变元对应的个体来表示个体变元对应的个体y y，并称之为，并称之为n元个体函数元个体函数，简称函数。，简称函数。函数函数 father(x):father(x): 值为值为x x的父亲。的父亲。谓词谓词D(D(fatherfather( (Li Li):):表示表示x x的父亲是医生，值为真或假。的父亲是医生，值为真或假。2022-3-1123.2.2 3.2.2 谓词逻辑谓词逻辑（3 3）n为了表示命题中出现的为了表示命题中出现的“全部全部”、“所有所有”、“一切一切”、“任一任一”或或“凡是凡是”等意义，引入等意义，引入全称量词，记为全称量词，记为

11、x 。n为了表示命题中出现的为了表示命题中出现的“存在存在”、“某些某些”、“有一个有一个”等意义，引入存在量词，记为等意义，引入存在量词，记为 x 。 如：如：“某些学生对某些课外活动感兴趣某些学生对某些课外活动感兴趣” S(x)表示表示x是学生，是学生，L(y)表示表示y是课外活动，是课外活动， I(x,y)表示表示x对对y感兴趣。感兴趣。 x( ( )( )()x y S xL yI xy ，2022-3-1133.2.2 3.2.2 谓词逻辑谓词逻辑（4 4）定义定义3.23.2：项：项（1 1）个体常元和变元都是项。个体常元和变元都是项。（2 2）f f是是n n元函数符号，若元函数

12、符号，若t t1 1，t t2 2，t tn n是项，则是项，则 f f（ t t1 1，t t2 2， t tn n ）是项。）是项。（3 3）只有有限次使用（）只有有限次使用（1 1），（），（2 2）得到的符号串才是项。）得到的符号串才是项。2022-3-1143.2.2 3.2.2 谓词逻辑谓词逻辑（5 5）定义定义3.33.3：原子公式：原子公式 设设P P为为n n元谓词符号，元谓词符号， t t1 1，t t2 2，t tn n为项，为项， P P（t t1 1，t t2 2，t tn n）称为原子谓词公式，简称原子或原）称为原子谓词公式，简称原子或原子公式。子公式。2022-3

13、-1153.2.2 3.2.2 谓词逻辑谓词逻辑（6 6）定义定义3.43.4：谓词公式：谓词公式（1 1）原子公式是谓词公式。）原子公式是谓词公式。（2 2）若）若A A、B B是谓词公式，则是谓词公式，则 A A，A A B B，A A B B，A A B B， A AB B， xAxA， xAxA也是谓词公式。也是谓词公式。（3 3）只有有限步应用（）只有有限步应用（1 1）（）（2 2）生成的公式才是谓词公式。）生成的公式才是谓词公式。谓词公式亦称为谓词逻辑中的合适（式）公式，记为谓词公式亦称为谓词逻辑中的合适（式）公式，记为WffWff。符号约定：符号约定：谓词大写字母；谓词大写字母

14、； P(x,y)P(x,y) 函数小写字母；函数小写字母；f(x)f(x) 变量变量 x x、y y、z z、u u、vv； 常量常量a a、b b、c.c.。 P(a,y)P(a,y)2022-3-1163.2.2 3.2.2 谓词逻辑谓词逻辑（7 7）n辖域辖域：紧接于量词之后被量词作用（即说明）：紧接于量词之后被量词作用（即说明）的谓词公式称为该量词的辖域。的谓词公式称为该量词的辖域。n指导变量指导变量：量词后的变量为指导变量。：量词后的变量为指导变量。n约束变量约束变量：在一个量词辖域中与该量词的指导：在一个量词辖域中与该量词的指导变元相同的变量称为约束变量。变元相同的变量称为约束变量

15、。n自由变量自由变量：谓词公式中除了约束变量之外的变：谓词公式中除了约束变量之外的变量。量。 （1） （2） （3）( , )xS x y( )( )yF yD y( )( )( , )x y W xL xP x y 2022-3-1173.2.2 3.2.2 谓词逻辑（谓词逻辑（8 8）n一个变元在一个公式中既可以约束出现，一个变元在一个公式中既可以约束出现，也可以自由出现，为了避免混淆，通过也可以自由出现，为了避免混淆，通过改名规则改名规则改名：改名：n对需要改名的变元，应对需要改名的变元，应同时更改同时更改该变元在量该变元在量词及其辖域中的词及其辖域中的所有出现所有出现。n新变元符号必须

16、是量词辖域内新变元符号必须是量词辖域内原先没有原先没有的，的，最好是最好是公式中公式中也也未出现未出现过的。过的。 x G(x) x G(x) P P（x x） x G(x) x G(x) P P（y y）2022-3-1183.2.2 3.2.2 谓词逻辑（谓词逻辑（9 9）n谓词公式与命题的区别与联系谓词公式与命题的区别与联系n谓词公式是谓词公式是命题函数命题函数。n一个谓词公式中所有个体变元被量化，谓词一个谓词公式中所有个体变元被量化，谓词公式就变成了一个命题。公式就变成了一个命题。n从谓词公式得到命题的两种方法：给谓词中从谓词公式得到命题的两种方法：给谓词中的个体变元代入个体常元；把谓

17、词中的个体的个体变元代入个体常元；把谓词中的个体变元全部量化。变元全部量化。例：例：P P（x x）表示）表示“x x是素数是素数” x P（x），）， x P（x），）， P P（a a）都是命题都是命题2022-3-1193.2.2 3.2.2 谓词逻辑（谓词逻辑（1010）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(x)x G(x)等价于等价于P P (a(a1 1) ) P P(a(a2 2) ) P P (a (an n) )n一阶谓词一阶谓词：仅个体变

18、元被量化的谓词。：仅个体变元被量化的谓词。n二阶谓词二阶谓词：个体变元被量化，函数符号和谓词：个体变元被量化，函数符号和谓词符号也被量化。符号也被量化。 P x P（x）2022-3-1203.2.2 3.2.2 谓词逻辑谓词逻辑（1111）定义定义3.53.5：合取范式（：合取范式（Conjunctive Normal FormConjunctive Normal Form） 设设A A为如下形式的谓词公式：为如下形式的谓词公式： B B1 1 B B2 2 B Bn n其中其中B Bi i（i=1,2,i=1,2,，n n）形如）形如L L1 1 L L2 2 L Lm m，L Lj j（

19、j=1j=1，2,2,，m m）为原子公式或其否定，则）为原子公式或其否定，则A A称为合取范式。称为合取范式。例例 就是一个合取范式就是一个合取范式( ( )( )( )( )( )( )P xQ xQ yR yP zS z 2022-3-1213.2.2 3.2.2 谓词逻辑（谓词逻辑（1212）定义定义3.63.6：析取范式：析取范式（Disjunctive Normal FormDisjunctive Normal Form）设设A A为如下形式的谓词公式：为如下形式的谓词公式： B B1 1 B B2 2 B Bn n其中其中B Bi i（i=1,2,i=1,2,，n n）形如）形如

20、L L1 1 L L2 2 L Lm m，L Lj j（j=1j=1，2,2,，m m）为原子公式或其否定，则）为原子公式或其否定，则A A称为析取范式称为析取范式。例如例如 就是一个析取范式就是一个析取范式( )()(D yL ayP xC zP uL uv ，（( )( )( )( ， )2022-3-1223.2.2 3.2.2 谓词逻辑（谓词逻辑（1313）定义定义3.7 谓词公式的解释谓词公式的解释 设设D D为谓词公式为谓词公式P P的个体域，若对的个体域，若对P P中的个体常量、函数中的个体常量、函数和谓词按如下规定赋值：和谓词按如下规定赋值： （1 1）为）为每个个体常量每个个

21、体常量指派指派D D中的一个元素；中的一个元素； （2 2）为）为每个每个n n元函数元函数指派一个从指派一个从D Dn n到到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上的一个解释。上的一个解释。2022-3-1233.2.2 3.2.2 谓词逻辑（谓词逻辑（1414）例：设个体域例：设个体域D D1,2,1,2, 求公式求公式 在在D

22、D上的解上的解释，并指出在每一种解释下公式释，并指出在每一种解释下公式A A的真值。的真值。解：设公式解：设公式A中对个体常量中对个体常量b、函数、函数f（x）指派的真值分）指派的真值分别为：别为： 对谓词指派的真值为：对谓词指派的真值为： 2(1)1(2)2bff，( ( , )( ( ), )Ax y P x yQ f x b (11)(12)(2,1)(2,2)PTPTPTPF，(1,2),(2,2)QF QT2022-3-1243.2.2 3.2.2 谓词逻辑（谓词逻辑（1515）在此解释下，在此解释下，由于当由于当x=1时，有时，有y=2，使得：，使得： ：所以所以 为为T T。 当

23、当x x2 2时，时，有有y=2，使得，使得 所以所以 为为T T。所以公式所以公式A在此解释下真值为在此解释下真值为T。 (1,2)( (1),2)(2,2)PTQ fQT，( , )( ( ),2)P x yQ f x(2,2)( (2),2)(1,2)PFQ fQF，( , )( ( ),2)P x yQ f x2022-3-1253.2.2 3.2.2 谓词逻辑（谓词逻辑（1616）定义定义3.83.8：谓词公式的永真：谓词公式的永真 如果谓词公式如果谓词公式P对个体域对个体域D上的任何一个解释都上的任何一个解释都取得真值取得真值T，则称，则称P在在D上是永真的；如果上是永真的；如果P

24、在全总个在全总个体域上永真，则称体域上永真，则称P永真。永真。 2022-3-1263.2.2 3.2.2 谓词逻辑（谓词逻辑（1717）定义定义3.93.9：谓词公式的可满足性：谓词公式的可满足性 对于谓词公式对于谓词公式P，如果在个体域，如果在个体域D上至少存在一上至少存在一个解释使得公式个解释使得公式P在此解释下的真值为，则称公式在此解释下的真值为，则称公式P在在D上是可满足的。上是可满足的。 2022-3-1273.2.2 3.2.2 谓词逻辑（谓词逻辑（1818）定义定义3.93.9：谓词公式的永假：谓词公式的永假 如果谓词公式如果谓词公式P对于个体域对于个体域D上的任何一个上的任何

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

26、词，把限定词作为一个合取项加入。即 x(P(x) x(P(x)(1)(1)对全称量词，把限定词作为蕴含式之前件加入。对全称量词，把限定词作为蕴含式之前件加入。 即即 x x （P P（x x） ）2022-3-1293.2.3 3.2.3 基于谓词逻辑的知识表示基于谓词逻辑的知识表示（2）表示表示“对个体域中所有的（或任一个）个体对个体域中所有的（或任一个）个体” ” 。记为。记为 x x全称量词全称量词 表示表示“在个体域中存在个体在个体域中存在个体”。记为。记为 x x存在量词存在量词 如：如：“凡是人都有名字凡是人都有名字” 用用M M（x x）表示）表示“x x是人是人”，N N（x

27、x）表示）表示“x x有名字有名字” ” x x（M M（x x） N N（x x） 如：如：“存在不是偶数的整数存在不是偶数的整数”用用G G（x x）表示）表示“x x是整数是整数”，E E（x x）表示）表示“x x是偶数是偶数” x x（G G（x x） E E（x x） 2022-3-1303.2.3 3.2.3 基于谓词逻辑的知识表示基于谓词逻辑的知识表示（2）例例 3.2 设有如下命题：设有如下命题：（1）小明比他的哥哥学习努力。）小明比他的哥哥学习努力。 定义谓词：定义谓词： ：x x比比y y学习努力学习努力 定义函数：定义函数： ：x x的哥哥的哥哥 谓词公式表示为：谓词公

28、式表示为： ( , )StudyHarder x ybrother x( )StudyHarder a brother a( ,( )2022-3-1313.2.3 3.2.3 基于谓词逻辑的知识表示基于谓词逻辑的知识表示（3）（2）对于所有的自然数，均有）对于所有的自然数，均有 。 定义谓词：定义谓词： ：x x是自然数是自然数 ：x x大于等于大于等于y y 定义函数：定义函数： ：x x与与y y的和的和 谓词公式表示为：谓词公式表示为： xyx( )Nature x( , )GE x y( , )sum x y( )( )( , ), )x y Nature xNature yGE s

29、um x yy 2022-3-1323.2.3 3.2.3 基于谓词逻辑的知识表示基于谓词逻辑的知识表示（4）（3）某些人对某些食物过敏。）某些人对某些食物过敏。 定义谓词：定义谓词： ：x x是人是人 ：x x是食物是食物 ：x x对对y y过敏定义函数：过敏定义函数： 谓词公式表示为：谓词公式表示为：( )M x( )F x( , )S x y( )( )( , )x y M xF yS x y 2022-3-1333.2.3 3.2.3 基于谓词逻辑的知识表示基于谓词逻辑的知识表示（5）例例3.3 用谓词公式表示下述命题。用谓词公式表示下述命题。已知前提：已知前提：F1：自然数自然数都是

30、都是大于零大于零的的整数整数。F2：所有整数不是：所有整数不是偶数偶数就是就是奇数奇数。F3：偶数：偶数除以除以2是整数。是整数。结论：所有自然数不是奇数就是一半为整数的数。结论：所有自然数不是奇数就是一半为整数的数。首先定义如下谓词：首先定义如下谓词： N(x):x是自然数。是自然数。 I(x):x是整数。是整数。 E(x):x是偶数。是偶数。 O(x):x是奇数。是奇数。 GZ(x):x大于零。大于零。 定义函数定义函数s(x):x除以除以2。2022-3-1343.2.3 3.2.3 基于谓词逻辑的知识表示基于谓词逻辑的知识表示（6）将上述各语句翻译成谓词公式：将上述各语句翻译成谓词公式

31、：F1：自然数自然数都是都是大于零大于零的的整数整数。 x (N(x)x (N(x)GZ(x) GZ(x) I(x) I(x)F2：所有整数不是：所有整数不是偶数偶数就是就是奇数奇数。 x (I(x)x (I(x)(E(x) (E(x) O(x) O(x) F3：偶数：偶数除以除以2是整数。是整数。 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) 2022-3-1353.2.3 3.2.3 基于谓词逻辑的知识表示基于谓

32、词逻辑的知识表示（7） 例例 3.4 设在一个房间里，设在一个房间里，a和和b是两张桌子，是两张桌子，a处桌子上处桌子上放有一个盒子放有一个盒子box，c处有一个机器人处有一个机器人Robot，为了让机，为了让机器人从器人从c处出发把盒子从处出发把盒子从a处拿到处拿到b处的桌子上，然后再处的桌子上，然后再回到回到c处，用谓词逻辑描述从初始状态到目标状态的机器处，用谓词逻辑描述从初始状态到目标状态的机器人操作过程。人操作过程。解：定义谓词解：定义谓词 ：表示：表示x是桌子是桌子 ：表示机器人：表示机器人Robot手是空的手是空的 ：表示机器人：表示机器人Robot在在x处处 ：机器人：机器人Ro

33、bot拿着拿着Box ：积木块在：积木块在x上上()Empty Robot( )Table x(, )At Robot x(,)Holds Robot Box(, )On Box x2022-3-1363.2.3 3.2.3 基于谓词逻辑的知识表示基于谓词逻辑的知识表示（8）初始状态为：初始状态为：目标状态为：目标状态为：()Empty Robot( )Table a( )Table b(, )On Box a( )Table a( )Table b(, )On Box b2022-3-1373.2.3 3.2.3 基于谓词逻辑的知识表示基于谓词逻辑的知识表示（9）以机器人的操作以机器人的操作

34、PICKUP(a)为例来说明操作进行的条件为例来说明操作进行的条件和动作：和动作：条件：条件：删除：删除：增加：增加：(, )On Box a(, )At Robot a()Empty Robot ()Empty Robot(, )On Box a(,)Holds Robot Box2022-3-1383.33.3自然演绎推理（自然演绎推理（1 1）n自然演绎推理自然演绎推理 利用一阶谓词推理规则的符号表示形式，可以把关利用一阶谓词推理规则的符号表示形式，可以把关于自然语言的逻辑推理问题，转化为符号表达式的推于自然语言的逻辑推理问题，转化为符号表达式的推演变换。这种推理十分类似于人们用自然语言

35、推理的演变换。这种推理十分类似于人们用自然语言推理的思维过程，因而称为自然演绎推理。思维过程，因而称为自然演绎推理。n常用逻辑等价式常用逻辑等价式n常用推理定律常用推理定律 2022-3-139常用逻辑等价式（常用逻辑等价式（1 1）2022-3-140常用逻辑等价式（常用逻辑等价式（2 2）2022-3-141常用推理定律常用推理定律2022-3-1423.33.3自然演绎推理（自然演绎推理（2 2）例例 设有前提：设有前提： （1 1）凡是大学生都学过计算机；）凡是大学生都学过计算机； （2 2）小王是大学生。）小王是大学生。 试问：小王学过计算机吗？试问：小王学过计算机吗？)x(M)x(

36、S(x)( 1)a(S)(2)a(M)a(S)(2)a(S)(3)a(M)(4解：令解：令S S（x x）：x x是大学生是大学生M M（x x）：x x学过计算机；学过计算机；a a：小王小王上面命题用谓词公式表示为：上面命题用谓词公式表示为：)x(M)x(S(x)( 1前提前提(1),US前提前提(2),(3),I3我们进行形式推理：我们进行形式推理：M(a)，即小王学过计算机。，即小王学过计算机。xA(x)=A(y)y是个体域中任一确定元素是个体域中任一确定元素(A B) A = B2022-3-1433.33.3自然演绎推理（自然演绎推理（3 3）例例3.5 3.5 设有前提：设有前提

37、： （1 1）有些病人相信所有的医生。）有些病人相信所有的医生。（2 2）病人都不相信骗子。）病人都不相信骗子。求证：所有的医生都不是骗子。求证：所有的医生都不是骗子。( )P x( )D x( )C x( , )B x y证明：定义谓词：证明：定义谓词：x x是病人是病人：x x是医生是医生：x x是骗子是骗子：x x相信相信y y( ( )( )( , )x P xy D yB x y( ( )( ( )( , )x P xy C yB x y ( )( )x D xC x 将前提和要证明的结论转化为谓词公式：将前提和要证明的结论转化为谓词公式：前提：前提：（1 1）（2 2）结论：结论：

38、2022-3-1443.33.3自然演绎推理（自然演绎推理（4 4）( ( )( )( , )x P xy D yB x y( )( )( , )P ay D yB a y( )P a( ( )( ( )( , )x P xy C xB x y ( )( ( )( , )P ay C yB a y ( ( )( , )y C yB a y ( )( , )C yB a y （2 2） （1 1），存在指定规则），存在指定规则 （3 3） （2 2），简化律），简化律 （4 4） 前提引入前提引入 （5 5） （4 4），全称指定规则），全称指定规则 （6 6） （3 3）（）（5 5），假言推

39、理），假言推理 （7 7）（1 1） 前提引入前提引入 （6 6），全称指定规则），全称指定规则 2022-3-1453.33.3自然演绎推理（自然演绎推理（5 5）( , )( )B a yC y ( )( , )y D yB a y( )( , )D yB a y( )( )D yC y( )( )x D xC x （8 8） （7 7），逆反律），逆反律 （9 9） （2 2），化简规则），化简规则 （1010） （9 9），全称指定规则），全称指定规则 （1111） （8 8）（）（1010），假言三段论），假言三段论 （1212） （1111），全称推广规则），全称推广规则 2022

40、-3-1463.43.4归结演绎推理归结演绎推理3.4.1 3.4.1 子句集子句集3.4.2 3.4.2 命题逻辑中的归结原理命题逻辑中的归结原理3.4.3 3.4.3 替换与合一替换与合一3.4.4 3.4.4 谓词逻辑中的归结原理谓词逻辑中的归结原理3.4.5 3.4.5 利用归结原理求解问题利用归结原理求解问题2022-3-1473.4.1 3.4.1 子句集子句集(1)(1)原子谓词公式及其否定称为原子谓词公式及其否定称为文字文字定义定义3.113.11 任何文字的析取称为一个任何文字的析取称为一个子句。子句。 由由n n个文字组成的子句叫个文字组成的子句叫n n文字子句；文字子句；

41、1-1-文字子句叫单元子句；文字子句叫单元子句；不含任何文字的子句称为空子句，记为不含任何文字的子句称为空子句，记为或或NILNIL。由子句构成的集合称为子句集。子句集中子句和子句之间由子句构成的集合称为子句集。子句集中子句和子句之间的关系是合取关系，所以，子句集就是一个合取范式。的关系是合取关系，所以，子句集就是一个合取范式。2022-3-1483.4.1 3.4.1 子句集子句集(2)(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

42、), P(y,f(y) P(y,f(y) R(y,g(y) R(y,g(y)谓词公式与子句集有哪些区别？谓词公式与子句集有哪些区别？“”作用原子谓词作用原子谓词没有量词没有量词( ( 、 ) )合取范式合取范式元素之间变元不同元素之间变元不同定义定义3.123.12：对一个谓词公式：对一个谓词公式G G，通过以下步骤所得的子句集，通过以下步骤所得的子句集 S S，称为，称为G G的的子句集（子句集（clausesclauses）。 集合形式集合形式没有蕴含词、等值词没有蕴含词、等值词2022-3-1493.4.1 3.4.1 子句集子句集(3)(3)例例3.6： x y P(x，y) yQ(x

43、,y) R(x,y)由第一步可得：由第一步可得： x y P(x，y) y Q(x,y) R(x,y)1 1、消蕴含词和等值词、消蕴含词和等值词理论根据理论根据：AB A B A B (A B) ( B A)蕴含等价式蕴含等价式问题问题: :蕴含式蕴含式 y P(x y P(x，y)y) yQ(x,y)yQ(x,y)R(x,y)R(x,y)的前件是？的前件是？1 1 ： y P(x y P(x，y) y) 2 2 ：P(xP(x，y)y) 2022-3-1503.4.1 3.4.1 子句集子句集(4)(4)n子句集的特征子句集的特征“”作用原子谓词作用原子谓词没有量词没有量词( ( 、 ) )

44、合取范式合取范式元素之间变元不同元素之间变元不同集合形式集合形式没有蕴含词、等值词没有蕴含词、等值词2022-3-1513.4.1 3.4.1 子句集子句集(5)(5) x x y P(x y P(x，y) y) y Q(x,y) y Q(x,y) R(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 x y y P(x P(x，y) y) y y

45、 Q(x,y) Q(x,y) R(x,y)R(x,y) = x x y P(x y P(x，y) y) y y ( Q(x,y)Q(x,y) R(x,y) R(x,y)= x x y P(x y P(x，y) y) y Q(x,y) y Q(x,y) R(x,y) R(x,y)2022-3-1523.4.1 3.4.1 子句集子句集(6)(6)n子句集的特征子句集的特征“”作用原子谓词作用原子谓词没有量词没有量词( ( 、 ) )合取范式合取范式元素之间变元不同元素之间变元不同集合形式集合形式没有蕴含词、等值词没有蕴含词、等值词2022-3-1533.4.1 3.4.1 子句集子句集(7)(7

46、)= = x x y P(x y P(x，y) y) z zQ(x,Q(x,z z) ) R(x, R(x,z z)3、适当改名，使变量标准化适当改名，使变量标准化即：对于不同的约束，对应于不同的变量即：对于不同的约束，对应于不同的变量 x x y P(x y P(x，y) y) y Q(x,y) y Q(x,y) R(x,y) R(x,y)问题问题: :不同辖域的相同变元对应的约束相同吗不同辖域的相同变元对应的约束相同吗? ?2022-3-1543.4.1 3.4.1 子句集子句集(8)(8)4 4、 消去存在量词消去存在量词 ( (SkolemSkolem化）化）, ,同时进行变元替换同时

47、进行变元替换 原则：原则： 若该存在量词若该存在量词不在任何不在任何全称量词全称量词的辖域内，的辖域内，则则用一用一 个个常量符号常量符号代替该存在量词辖域内的相应约束变元，代替该存在量词辖域内的相应约束变元， 这个常量叫这个常量叫SkolemSkolem常量常量； 若该存在量词若该存在量词在在全称量词全称量词的辖域内，的辖域内，则则用这些全用这些全 称量词指导变元的一个称量词指导变元的一个函数函数代替该存在量词辖域代替该存在量词辖域 内的相应约束变元，这样的函数称为内的相应约束变元，这样的函数称为SkolemSkolem函数函数。理论依据：理论依据： xA（x）=A（y）y y是个体域中某一

48、确定的元素。是个体域中某一确定的元素。 存在指定规则存在指定规则 2022-3-1553.4.1 3.4.1 子句集子句集(9)(9)问题问题: :为什么受全称量词约束的要用为什么受全称量词约束的要用SkolemSkolem函数替换函数替换? ? 而不能用常量替换？而不能用常量替换？ x x yM yM（y y，x x）：）：对任意一个人对任意一个人x x，都存在一个，都存在一个y y，y y是是x x的妈妈。的妈妈。若去掉存在量词用常量若去掉存在量词用常量a a代替代替y y，则变为：，则变为： x Mx M（a a，x x）：）：a a是所有人的妈妈。是所有人的妈妈。实际上，引入实际上，引

49、入SkolemSkolem函数，是由于存在量词在全称量词函数，是由于存在量词在全称量词的辖域之内，其约束变元的取值完全依赖于全称变量的的辖域之内，其约束变元的取值完全依赖于全称变量的取值。而取值。而SkolemSkolem函数反映了这种依赖关系。函数反映了这种依赖关系。2022-3-1563.4.1 3.4.1 子句集子句集(10)(10) x x y P(x y P(x，y) y) zQ(x,z) zQ(x,z) R(x,z) R(x,z)= x P(x，f(x) Q(x，g(x) R(x，g(x)= P(x P(x，f(x) f(x) Q(x,g(x) Q(x,g(x) R(x,g(x)

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

51、、化公式为合取范式、化公式为合取范式 理论依据：理论依据： 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) 分配律分配律 2022-3-1593.4.1 3.4.1 子句集子句集(13)(13)n子句集的特征子句集的特征“”作用原子谓词作用原子谓词没有量词没有量词( ( 、 ) )合取范式合取范式元素之间变元不同元素之间变元不同集合形式集合形式没有蕴含词、等值词没有蕴含词、等值词2022-3-1603.4.1 3.4.1 子句集子句集(14)(14)= P(x，f(x) Q(x,g(x) P(y，f(y)

52、 R(y,g(y)7、适当改名，使子句间无同名变元适当改名，使子句间无同名变元= P(x，f(x) Q(x,g(x) , P(y，f(y) R(y,g(y)8、消去合取词，以子句为元素组成一个集合消去合取词，以子句为元素组成一个集合S S= P(x P(x，f(x) f(x) Q(x,g(x) Q(x,g(x) R(x,g(x) R(x,g(x)2022-3-1613.4.1 3.4.1 子句集子句集(15)(15)消去蕴含词和等值词消去蕴含词和等值词使否定词仅作用于原子公式使否定词仅作用于原子公式使量词间不含同名指导变元使量词间不含同名指导变元消去存在量词消去存在量词消去全称量词消去全称量词

53、化公式为合取范式化公式为合取范式子句间无同名变元子句间无同名变元组成一个集合组成一个集合“”作用原子谓词作用原子谓词没有量词没有量词( ( 、 ) )合取范式合取范式元素之间变元不同元素之间变元不同集合形式集合形式没有蕴含词、等值词没有蕴含词、等值词蕴含等价式蕴含等价式双重否定律、双重否定律、摩根定律、摩根定律、量词转换律量词转换律存在指定、存在指定、依赖关系依赖关系全称指定全称指定分配律分配律2022-3-1623.4.1 3.4.1 子句集子句集(16)(16)SkolemSkolem标准型标准型 在求子句集的过程中，消去存在量词在求子句集的过程中，消去存在量词之后，把所有之后，把所有全称

54、量词全称量词都依次移到式子的最左边（或者都依次移到式子的最左边（或者把所有的量词都依次移到式子最左边，再消去存在量把所有的量词都依次移到式子最左边，再消去存在量词），再将右部的式子化为合取范式，这样得到的式词），再将右部的式子化为合取范式，这样得到的式子就是子就是SkolemSkolem标准型。标准型。 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)消去合取词和全称量词，就得到

55、了原公式的子句集消去合取词和全称量词，就得到了原公式的子句集2022-3-1633.4.1 3.4.1 子句集子句集(17)(17) 引入引入SkolemSkolem函数，是由于存在量词在全称量词的辖函数，是由于存在量词在全称量词的辖域内，其约束变元的取值完全依赖于全称量词的取值。域内，其约束变元的取值完全依赖于全称量词的取值。SkolemSkolem反映了这种依赖关系。反映了这种依赖关系。 但但SkolemSkolem标准型与原公式一般并不等价。标准型与原公式一般并不等价。 有公式：有公式： 它的它的SkolemSkolem标准型是标准型是 我们给出如下的解释我们给出如下的解释I I： D

56、D=0=0，11，f f(0)=1(0)=1，f f(1)=1(1)=1，P P(0(0，0)=0)=T T，P P(0(0，1)=1)=F F， P P(1(1，0)=0)=T T， P P(1(1，1)=1)=F F 在此解释下，在此解释下，G GT,G T,G F F( , )Gx yP x y ( ,( )GxP x f x 2022-3-1643.4.1 3.4.1 子句集子句集(18)(18)定理定理3.1 谓词公式谓词公式G不可满足当且仅当其子句集不可满足当且仅当其子句集S不可满足。不可满足。定义定义3.133.13 公式公式G是公式是公式F1 1、F2 2 、 、Fn n的逻辑

57、结论（推的逻辑结论（推论），当且仅当对每一个解释论），当且仅当对每一个解释I，如果，如果F1 1、F2 2 、 、Fn n都为真，则都为真，则G也为真。这时称也为真。这时称F1 1、F2 2 、 、Fn n为为G的前的前提。提。 定理定理3.23.2 G是公式是公式F1 1、F2 2、Fn n的逻辑结论，当且仅当的逻辑结论，当且仅当 F1 1 F2 2 Fn n = G定理定理3.33.3 G是公式是公式F1 1、F2 2、Fn n的逻辑结论，当且仅当的逻辑结论，当且仅当 F1 1 F2 2 Fn n G 是不相容的。是不相容的。12()nFFFG，12()nFFFG 2022-3-1653.

58、4.1 3.4.1 子句集子句集(19)(19)例例3.8 化子句集化子句集已知前提：已知前提：（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(x) F2: F2: x (I(x)x (I(x)(E(x) (E(x) O(x) O(x) F3: F3:

59、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)2022-3-1663.4.1 3.4.1 子句集子句集(20)(20)解：解：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(a)N(a)（6 6） O(a) O(a) （7 7） I(s(a

60、)I(s(a)2022-3-1673.4.2 3.4.2 命题逻辑中的归结原理命题逻辑中的归结原理(1)(1)n归结原理的提出归结原理的提出 归结原理归结原理(principle of resolution)(principle of resolution)又称消解原又称消解原理理,1965,1965年鲁滨逊（年鲁滨逊（J.A.RobinsonJ.A.Robinson）提出，从理论上解）提出，从理论上解决了定理证明问题。归结原理提出的是一种证明子句决了定理证明问题。归结原理提出的是一种证明子句集不可满足性，从而实现定理证明的一种理论及方法。集不可满足性，从而实现定理证明的一种理论及方法。202