第3章 基于谓词逻辑的知识表示与机器推理

1、2021-7-31 第第3 3章章 基于谓词逻辑的机器推理基于谓词逻辑的机器推理 2021-7-32 内容内容 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 基于规则的演绎推理基于规则的演绎推理 2021-7-33 3.1 3.1 机器推理概述（机器推理概述（1 1） n 机器推理机器推理 推理是人脑的一个基本功能和重要功能，几乎所有的推理是人脑的一个基本功能和重要功能，几乎所有的 人工智

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

3、检索、规划制定和难题求解等方法都可以转化一个定理证 明问题明问题。 2021-7-34 n自动定理证明的基本方法：自动定理证明的基本方法： 3.1 3.1 机器推理概述（机器推理概述（2 2） 定理证明器定理证明器：它是研究一切可判定问题的证明方法。鲁：它是研究一切可判定问题的证明方法。鲁 滨逊的归结原理。滨逊的归结原理。 基于规则的演绎推理基于规则的演绎推理 ：把已知判断中的知识表示成规：把已知判断中的知识表示成规 则的形式（包括则的形式（包括F-F-规则和规则和B-B-规则），运用规则从已知判规则），运用规则从已知判 断的事实或待证明的结论出发进行推理的过程断的事实或待证明的结论出发进行推

4、理的过程 自然演绎法自然演绎法：该方法依据推理规则从前提和公理中可以：该方法依据推理规则从前提和公理中可以 推出许多定理，如果待证明的定理在其中则定理得证。推出许多定理，如果待证明的定理在其中则定理得证。 LTLT程序、证明平面几何的程序。程序、证明平面几何的程序。 人机交互进行定理证明人机交互进行定理证明：计算机作为数学家的辅助工具，：计算机作为数学家的辅助工具， 用计算机帮助人完成手工证明中的难以完成的繁杂的大用计算机帮助人完成手工证明中的难以完成的繁杂的大 量计算推理和穷举。四色定理。量计算推理和穷举。四色定理。 2021-7-35 n基于归结原理的自动定理证明过程：基于归结原理的自动定

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

6、数。 定理的谓词公式描述：定理的谓词公式描述： 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) 2021-7-36 3.2 3.2 谓词逻辑简介谓词逻辑简介 3.2.1 3.2.1 基于命题逻辑的知识表示基于命题逻辑的知识表示 3.2.2 3.2.2 谓词逻辑谓词逻辑 3.2.3 3.2.3

7、基于谓词逻辑的知识表示基于谓词逻辑的知识表示 2021-7-37 3.2.13.2.1基于命题逻辑的知识表示基于命题逻辑的知识表示（1 1） 命题（命题（propositionproposition）：）：是具有真假意义的语句。命题代表人是具有真假意义的语句。命题代表人 们进行思维时的一种判断，或者是否定，或者是肯定。们进行思维时的一种判断，或者是否定，或者是肯定。 命题可以用命题符号表示。命题可以用命题符号表示。 用命题符号可以表示简单的逻辑关系和推理。用命题符号可以表示简单的逻辑关系和推理。 R: :今天天气好今天天气好 S: :去旅游去旅游 S1 1：我有名字：我有名字 S2 2：你有名

8、字：你有名字 RS表示：如果今天天气好，就去旅游。表示：如果今天天气好，就去旅游。 此时，如果此时，如果R（今天天气好）今天天气好）成立，则可以得到结论成立，则可以得到结论S（去旅游去旅游） 2021-7-38 3.2.13.2.1基于命题逻辑的知识表示基于命题逻辑的知识表示（2 2） n对于复杂的知识，命题符号能力不够。对于复杂的知识，命题符号能力不够。 n无法把所描述的客观事物的结构及逻辑特征无法把所描述的客观事物的结构及逻辑特征 反映出来。反映出来。 n无法把不同事物间的共同特征表达出来。无法把不同事物间的共同特征表达出来。 P：大李是小李的父亲。：大李是小李的父亲。 S1：我有名字：我

9、有名字 S2：你有名字：你有名字 所有的人都有名字：所有的人都有名字： SI S2 S3 2021-7-39 3.2.2 3.2.2 谓词逻辑谓词逻辑（1 1） 谓词谓词(predicate)：一般形式为一般形式为P（x1, x2 , xn ） P为为谓词名，谓词名，用于刻画个体的性质、状态用于刻画个体的性质、状态 或个体间的关系。或个体间的关系。 x1， x2 ， xn是是个体，个体，表示某个独立存表示某个独立存 在的事物或者某个抽象的概念。在的事物或者某个抽象的概念。 S(x): x是学生；是学生； P(x,y): x是是y的父亲。的父亲。 个体变元的变化范围称为个体变元的变化范围称为个体

10、域个体域。 包揽一切事物的集合称为包揽一切事物的集合称为全总个体域全总个体域。 2021-7-310 3.2.2 3.2.2 谓词逻辑谓词逻辑（2 2） n函数：函数：为了表达个体之间的对应关系，引入数为了表达个体之间的对应关系，引入数 学中函数概念和记法。用形如学中函数概念和记法。用形如f( (x1 1，x2 2， xn n) )来表示个体变元对应的个体来表示个体变元对应的个体y y，并称之为，并称之为n 元个体函数元个体函数，简称函数、函词或函词命名式。，简称函数、函词或函词命名式。 函数函数 father(x):father(x): 值为值为x x的父亲。的父亲。 谓词谓词D(D(fat

11、herfather( (Li Li):):表示表示x x的父亲是医生，值为真或假。的父亲是医生，值为真或假。 符号约定：符号约定：谓词大写字母；谓词大写字母； P( (x, ,y) ) 函数小写字母；函数小写字母；f( (x) ) 变量变量 x、y、z、u、v； 常量常量a、b、c. .。 P( (a, ,y) ) 2021-7-311 3.2.2 3.2.2 谓词逻辑谓词逻辑（3 3） n为了表示命题中出现的为了表示命题中出现的“全部全部”、“所有所有”、“一一 切切”、“任一任一”或或“凡是凡是”等意义，引入等意义，引入全称量词全称量词， 记为记为 x 。 n为了表示命题中出现的为了表示命

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

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

14、词公式：谓词公式 （1 1）原子公式是谓词公式。）原子公式是谓词公式。 （2 2）若）若A、B是谓词公式，则是谓词公式，则 A，A B，A B， A B，AB， xA， xA也是谓词公式。也是谓词公式。 （3 3）只有有限步应用（）只有有限步应用（1 1）（）（2 2）生成的公式才是谓词公式。）生成的公式才是谓词公式。 谓词公式亦称为谓词逻辑中的合适（式）公式，记为谓词公式亦称为谓词逻辑中的合适（式）公式，记为WffWff。 2021-7-315 3.2.2 3.2.2 谓词逻辑谓词逻辑（7 7） n辖域辖域：紧接于量词之后被量词作用（即说明）：紧接于量词之后被量词作用（即说明） 的谓词公式称

15、为该量词的辖域。的谓词公式称为该量词的辖域。 n指导变量指导变量：量词后的变量为量词的指导变量。：量词后的变量为量词的指导变量。 n约束变量约束变量：在一个量词辖域中与该量词的指导：在一个量词辖域中与该量词的指导 变元相同的变量称为约束变量。变元相同的变量称为约束变量。 n自由变量自由变量：谓词公式中除了约束变量之外的变：谓词公式中除了约束变量之外的变 量。量。 （1） （2） （3） ( , )xS x y ( )( )yF yD y ( )( )( , )x y W xL xP x y 2021-7-316 3.2.2 3.2.2 谓词逻辑（谓词逻辑（8 8） n一个变元在一个公式中既可以

16、约束出现，一个变元在一个公式中既可以约束出现， 也可以自由出现，为了避免混淆，通过也可以自由出现，为了避免混淆，通过 改名规则改名规则改名：改名： n对需要改名的变元，应对需要改名的变元，应同时更改同时更改该变元在量该变元在量 词及其辖域中的词及其辖域中的所有出现所有出现。 n新变元符号必须是量词辖域内新变元符号必须是量词辖域内原先没有原先没有的，的， 最好是最好是公式中公式中也也未出现未出现过的。过的。 x F( (y) ) D（y） x F( (x) ) D（y） 2021-7-317 3.2.2 3.2.2 谓词逻辑（谓词逻辑（9 9） n谓词公式与命题的区别与联系谓词公式与命题的区别与

17、联系 n谓词公式是谓词公式是命题函数命题函数。 n一个谓词公式中所有个体变元被量化，谓词一个谓词公式中所有个体变元被量化，谓词 公式就变成了一个命题。公式就变成了一个命题。 n从谓词公式得到命题的两种方法：给谓词中从谓词公式得到命题的两种方法：给谓词中 的个体变元代入个体常元；把谓词中的个体的个体变元代入个体常元；把谓词中的个体 变元全部量化。变元全部量化。 例：例：P（x）表示）表示“x是素数是素数” x P（x），）， x P（x），）， P（a）都是命题都是命题 2021-7-318 3.2.2 3.2.2 谓词逻辑（谓词逻辑（1010） n一阶谓词一阶谓词：仅个体变元被量化的谓词。：仅

18、个体变元被量化的谓词。 n二阶谓词二阶谓词：个体变元被量化，函数符号和谓词：个体变元被量化，函数符号和谓词 符号也被量化。符号也被量化。 P x P（x） n全称命题：全称命题： x P( (x) )等价于等价于P ( (a1 1) ) P( (a2 2) ) P( (an n) ) n特称命题特称命题 x G( (x) )等价于等价于P ( (a1 1) ) P( (a2 2) ) P( (an n) ) 2021-7-319 3.2.2 3.2.2 谓词逻辑谓词逻辑（1111） 定义定义3.53.5：合取范式（：合取范式（Conjunctive Normal FormConjunctive

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

20、FormDisjunctive Normal Form） 设设A A为如下形式的谓词公式：为如下形式的谓词公式： B1 1 B2 2 Bn n 其中其中B Bi i（i=1,2,i=1,2,，n n）形如）形如L1 1 L2 2 Lm m， ，Lj j（j j=1=1， 2,2,，m）为原子公式或其否定，则）为原子公式或其否定，则A称为析取范式称为析取范式。 例如例如( D(y) L(a,y) ( P(x) C(z) ( P(u) L(u,v) 就是一个析取范式就是一个析取范式 2021-7-321 3.2.2 3.2.2 谓词逻辑（谓词逻辑（1313） 定义定义3.7 3.7 谓词公式的解释

21、谓词公式的解释 设设D为谓词公式为谓词公式P的个体域，若对的个体域，若对P中的个体常量、函中的个体常量、函 数和谓词按如下规定赋值：数和谓词按如下规定赋值： （1 1）为）为每个个体常量每个个体常量指派指派D中的一个元素；中的一个元素； （2 2）为）为每个每个n n元函数元函数指派一个从指派一个从Dn n到到D的映射，其中的映射，其中 Dn n(x1 1, ,x2 2,xn n)/)/x1 1, ,x2 2,xn n D （3 3）为）为每个每个n元谓词元谓词指派一个从指派一个从Dn n到到F,TF,T的映射。的映射。 则称这些指派为公式则称这些指派为公式P在在D上的一个解释。上的一个解释。

22、 2021-7-322 3.2.2 3.2.2 谓词逻辑（谓词逻辑（1414） 例例3.13.1：设个体域：设个体域D1,2,1,2, 求公式求公式 在在D上的解释，上的解释， 并指出在每一种解释下公式并指出在每一种解释下公式A A的真值。的真值。 解：设公式解：设公式A中对个体常量中对个体常量b、函数、函数f（x）指派的真值分）指派的真值分 别为：别为： b=2，f(1)=1，f(2)=2 对谓词指派的真值为：对谓词指派的真值为： P(1，1)=T，P(1，2)=T ， P(2，1)=T ， P(2，2)=F Q(1，2)=F ， Q(2，2)=T ( ( , )( ( ), )Ax y P

23、 x yQ f x b 2021-7-323 3.2.2 3.2.2 谓词逻辑（谓词逻辑（1515） 在此解释下，在此解释下， 由于当由于当x=1时，有时，有y=2，使得：，使得： ： 所以所以 为为T。 当当x=2时，时，有有y=2，使得，使得 所以所以 为为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 x 2021-7-324 3.2.2 3.2.2 谓词逻辑（谓词逻辑（161

24、6） 定义定义3.83.8：谓词公式的永真：谓词公式的永真 如果谓词公式如果谓词公式P对个体域对个体域D上的上的任何一个任何一个解释都解释都 取得真值取得真值T，则称，则称P在在D上是永真的；如果上是永真的；如果P在全总个在全总个 体域上永真，则称体域上永真，则称P永真。永真。 定义定义3.93.9：谓词公式的可满足性：谓词公式的可满足性 对于谓词公式对于谓词公式P，如果在个体域，如果在个体域D上上至少至少存在存在一一 个个解释使得公式解释使得公式P在此解释下的真值为在此解释下的真值为T ，则称公式，则称公式 P在在D上是可满足的。上是可满足的。 谓词公式的可满足性又称相容性。谓词公式的可满足

25、性又称相容性。 2021-7-325 3.2.2 3.2.2 谓词逻辑（谓词逻辑（1717） 定义定义3.93.9：谓词公式的永假：谓词公式的永假 如果谓词公式如果谓词公式P对于个体域对于个体域D上的任何一个上的任何一个 解释都取得真值解释都取得真值F，则称，则称P在在D上是永假的；如上是永假的；如 果果P在全总个体域上永假，则称在全总个体域上永假，则称P永假。永假。 谓词公式的永假性又称不可满足性或不相容。谓词公式的永假性又称不可满足性或不相容。 2021-7-326 3.2.3 3.2.3 基于谓词逻辑的知识表示基于谓词逻辑的知识表示（1） 表示表示“对个体域中所有的（或任一个）个体对个体

26、域中所有的（或任一个）个体” 。记为。记为 x x全称量词全称量词 表示表示“在个体域中存在个体在个体域中存在个体”。记为。记为 x x存在量词存在量词 如：如：“凡是人都有名字凡是人都有名字” 用用M M（x x）表示）表示“x x是人是人”，N N（x 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） 2021-7-327 3.2.3 3.2.3 基于谓词逻辑的知

27、识表示基于谓词逻辑的知识表示（1） 用谓词表示命题时，一般取全总个体域，再采用使用用谓词表示命题时，一般取全总个体域，再采用使用 限定谓词的方法来指出每个个体变元的个体域。限定谓词的方法来指出每个个体变元的个体域。 (2)(2)对存在量词，把限定词作为一个合取项加入。即对存在量词，把限定词作为一个合取项加入。即 x(P(x) x(P(x) (1)(1)对全称量词，把限定词作为蕴含式之前件加入。对全称量词，把限定词作为蕴含式之前件加入。 即即 x x （P P（x x） ） 用谓词表示命题：用谓词表示命题： 先定义谓词、函数先定义谓词、函数 事实用谓词公式与或形表示事实用谓词公式与或形表示 规则

28、用蕴含式表示规则用蕴含式表示 2021-7-328 3.2.3 3.2.3 基于谓词逻辑的知识表示基于谓词逻辑的知识表示（2） 例例 3.2 设有如下命题：设有如下命题： （1）小明比他的哥哥学习努力。）小明比他的哥哥学习努力。 定义谓词：定义谓词： ：x x比比y y学习努力学习努力 定义函数：定义函数： ：x x的哥哥的哥哥 谓词公式表示为：谓词公式表示为： ( , )StudyHarder x y brother x( ) StudyHarder a brother a( ,( ) 2021-7-329 3.2.3 3.2.3 基于谓词逻辑的知识表示基于谓词逻辑的知识表示（3） （2）对

29、于所有的自然数，均有）对于所有的自然数，均有 。 定义谓词：定义谓词： ：x是自然数是自然数 ：x大于等于大于等于y 定义函数：定义函数： ：x与与y的和的和 谓词公式表示为：谓词公式表示为： xyx ( )Nature x ( , )GE x y ( , )sum x y ( )( )( , ), )x y Nature xNature yGE sum x yy 2021-7-330 3.2.3 3.2.3 基于谓词逻辑的知识表示基于谓词逻辑的知识表示（4） （3）某些人对某些食物过敏。）某些人对某些食物过敏。 定义谓词：定义谓词： ：x是人是人 ：x是食物是食物 ：x对对y过敏过敏 谓词公

30、式表示为：谓词公式表示为： ( )M x ( )F x ( , )S x y ( )( )( , )x y M xF yS x y 2021-7-331 3.2.3 3.2.3 基于谓词逻辑的知识表示基于谓词逻辑的知识表示（5） 例例3.3 用谓词公式表示下述命题。用谓词公式表示下述命题。 已知前提：已知前提： F1：自然数自然数都是都是大于零大于零的的整数整数。 F2：所有整数不是：所有整数不是偶数偶数就是就是奇数奇数。 F3：偶数：偶数除以除以2是整数。是整数。 结论：所有自然数不是奇数就是一半为整数的数。结论：所有自然数不是奇数就是一半为整数的数。 首先定义如下谓词：首先定义如下谓词：

31、N(x):x是自然数。是自然数。 I(x):x是整数。是整数。 E(x):x是偶数。是偶数。 O(x):x是奇数。是奇数。 GZ(x):x大于零。大于零。 定义函数定义函数s(x):x除以除以2。 2021-7-332 3.2.3 3.2.3 基于谓词逻辑的知识表示基于谓词逻辑的知识表示（6） 将上述各语句翻译成谓词公式：将上述各语句翻译成谓词公式： F1：自然数自然数都是都是大于零大于零的的整数整数。 x ( (N( (x) )GZ( (x) ) I(x) F2：所有整数不是：所有整数不是偶数偶数就是就是奇数奇数。 x ( (I( (x) )( (E( (x) ) O(x) ) F3：偶数：

32、偶数除以除以2是整数。是整数。 x ( (E( (x) ) I( (s( (x) 所有自然数不是奇数就是一半为整数的数。所有自然数不是奇数就是一半为整数的数。 G: G: x ( (N( (x) )( (I( (s( (x) ) O( (x) 2021-7-333 3.2.3 3.2.3 基于谓词逻辑的知识表示基于谓词逻辑的知识表示（7） 例例 3.4 设在一个房间里，设在一个房间里，a和和b是两张桌子，是两张桌子，a处桌子上处桌子上 放有一个盒子放有一个盒子box，c处有一个机器人处有一个机器人Robot，为了让机，为了让机 器人从器人从c处出发把盒子从处出发把盒子从a处拿到处拿到b处的桌子

33、上，然后再处的桌子上，然后再 回到回到c处，用谓词逻辑描述从初始状态到目标状态的机处，用谓词逻辑描述从初始状态到目标状态的机 器人操作过程。器人操作过程。 解：定义谓词解：定义谓词 Table(x)：表示：表示x是桌子是桌子 Empty(Robot)：表示机器人：表示机器人Robot手是空的手是空的 At(Robot,x)：表示机器人：表示机器人Robot在在x处处 Holds(Robot,Box) ：机器人：机器人Robot拿着拿着Box On(Box,x) ：盒子在：盒子在x上上 2021-7-334 3.2.3 3.2.3 基于谓词逻辑的知识表示基于谓词逻辑的知识表示（8） 初始状态为：

34、初始状态为： 目标状态为：目标状态为： ()Empty Robot ( )Table a ( )Table b (, )On Box a ( )Table a ( )Table b (, )On Box b 2021-7-335 3.2.3 3.2.3 基于谓词逻辑的知识表示基于谓词逻辑的知识表示（9） 以机器人的操作以机器人的操作PICKUP(a)为例来说明操作进行的条件为例来说明操作进行的条件 和动作：和动作： 条件：条件： On(Box,a) At(Robot,a) Empty(Robot) 删除：删除： Empty(Robot) On(Box,a) 增加：增加： Holds(Robot

35、,Box) 2021-7-336 3.33.3自然演绎推理（自然演绎推理（1 1） n自然演绎推理自然演绎推理 利用一阶谓词推理规则的符号表示形式，可以把关利用一阶谓词推理规则的符号表示形式，可以把关 于自然语言的逻辑推理问题，转化为符号表达式的推于自然语言的逻辑推理问题，转化为符号表达式的推 演变换。这种推理十分类似于人们用自然语言推理的演变换。这种推理十分类似于人们用自然语言推理的 思维过程，因而称为自然演绎推理。思维过程，因而称为自然演绎推理。 n常用逻辑等价式常用逻辑等价式 n常用推理定律常用推理定律 2021-7-337 常用逻辑等价式（常用逻辑等价式（1 1） 2021-7-338

36、 常用逻辑等价式（常用逻辑等价式（2 2） 2021-7-339 常用推理定律常用推理定律 2021-7-340 3.33.3自然演绎推理（自然演绎推理（2 2） 例例3.5 3.5 设有前提：设有前提： （1 1）有些病人相信所有的医生。）有些病人相信所有的医生。 （2 2）病人都不相信骗子。）病人都不相信骗子。 求证：所有的医生都不是骗子。求证：所有的医生都不是骗子。 ( )D x ( )C x ( , )B x y 证明：定义谓词：证明：定义谓词： P(x)：x是病人是病人 ：x是医生是医生 ：x是骗子是骗子 ：x相信相信y ( ( )( )( , )x P xy D yB x y (

37、( )( ( )( , )x P xy C yB x y ( )( )x D xC x 将前提和要证明的结论转化为谓词公式：将前提和要证明的结论转化为谓词公式： 前提：前提： （1 1） （2 2） 结论：结论： 2021-7-341 3.33.3自然演绎推理（自然演绎推理（3 3） ( ( )( )( , )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

38、y （2 2） （1 1），存在指定规则），存在指定规则 （3 3） （2 2），简化律），简化律 （4 4） 前提引入前提引入 （5 5） （4 4），全称指定规则），全称指定规则 （6 6） （3 3）（）（5 5），假言推理），假言推理 （7 7） （1 1） 前提引入前提引入 （6 6），全称指定规则），全称指定规则 2021-7-342 3.33.3自然演绎推理（自然演绎推理（4 4） ( , )( )B a yC y ( )( , )y D yB a y ( )( , )D yB a y ( )( )D yC y ( )( )x D xC x （8 8） （7 7），逆反律），逆反

39、律 （9 9） （2 2），化简规则），化简规则 （1010） （9 9），全称指定规则），全称指定规则 （1111） （8 8）（）（1010），假言三段论），假言三段论 （1212） （1111），全称推广规则），全称推广规则 2021-7-343 3.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 利用归结原理求解问题利用归结原理求解问题 3.4.6 3.4.6 归

40、结策略归结策略 2021-7-344 3.4.1 3.4.1 子句集子句集(1)(1) 原子谓词公式及其否定称为原子谓词公式及其否定称为文字文字 原子谓词公式称为原子谓词公式称为正文字正文字 原子谓词公式的否定称为原子谓词公式的否定称为负文字负文字 定义定义3.113.11 任何文字的析取称为一个任何文字的析取称为一个子句。子句。 由由n n个文字组成的子句叫个文字组成的子句叫n n文字子句文字子句； 1-1-文字子句叫文字子句叫单元子句单元子句； 不含任何文字的子句称为空子句，记为或不含任何文字的子句称为空子句，记为或NILNIL。 由子句构成的集合称为由子句构成的集合称为子句集子句集。 子

41、句集中子句和子句之间的关系是合取关系，所以，子句子句集中子句和子句之间的关系是合取关系，所以，子句 集就是一个合取范式集就是一个合取范式。 2021-7-345 3.4.1 3.4.1 子句集子句集(2)(2) n谓词公式例谓词公式例 x yP( (x, ,y) ) y Q( (x, ,y) )R( (x, ,y) n子句集例子句集例 P( (x, ,f( (x) Q( (x, ,g( (x),), P( (y, ,f( (y) R( (y, ,g( (y) 谓词公式与子句集有哪些区别？谓词公式与子句集有哪些区别？ “”作用原子谓词作用原子谓词 没有量词没有量词( ( 、 ) ) 合取范式合取

42、范式 元素之间变元不同元素之间变元不同 定义定义3.123.12：对一个谓词公式：对一个谓词公式G，通过以下步骤所得的子句集，通过以下步骤所得的子句集 S，称为，称为G的的子句集（子句集（clausesclauses）。 集合形式集合形式 没有蕴含词、等值词没有蕴含词、等值词 2021-7-346 3.4.1 3.4.1 子句集子句集(3)(3) 例例3.6： x y P(x，y) yQ(x,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) (

43、B A) 蕴含等价式蕴含等价式 问题问题: :蕴含式蕴含式 y P(x，y) ) y Q( (x, ,y) )R( (x, ,y)的前件是？的前件是？ 1 1 ： y P( (x，y) 2 2 ：P( (x，y) ) 2021-7-347 3.4.1 3.4.1 子句集子句集(4)(4) n子句集的特征子句集的特征 “”作用原子谓词作用原子谓词 没有量词没有量词( ( 、 ) ) 合取范式合取范式 元素之间变元不同元素之间变元不同 集合形式集合形式 没有蕴含词、等值词没有蕴含词、等值词 2021-7-348 3.4.1 3.4.1 子句集子句集(5)(5) x y P( (x，y) ) y Q

44、( (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 y P( (x，y) ) 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) 2021

45、-7-349 3.4.1 3.4.1 子句集子句集(6)(6) n子句集的特征子句集的特征 “”作用原子谓词作用原子谓词 没有量词没有量词( ( 、 ) ) 合取范式合取范式 元素之间变元不同元素之间变元不同 集合形式集合形式 没有蕴含词、等值词没有蕴含词、等值词 2021-7-350 3.4.1 3.4.1 子句集子句集(7)(7) = = x y P( (x，y) ) z z Q( (x, ,z z) ) R( (x, ,z z) 3、适当改名，使变量标准化适当改名，使变量标准化 即：对于不同的约束，对应于不同的变量即：对于不同的约束，对应于不同的变量 x y P( (x，y) ) y Q

46、( (x, ,y) ) R( (x, ,y) 问题问题: :不同辖域的相同变元对应的约束相同吗不同辖域的相同变元对应的约束相同吗? ? 2021-7-351 3.4.1 3.4.1 子句集子句集(8)(8) 4 4、 消去存在量词消去存在量词 (Skolem (Skolem化）化）, ,同时进行变元替换同时进行变元替换 原则：原则： 若该存在量词若该存在量词不在任何全称量词的辖域内，不在任何全称量词的辖域内，则用一则用一 个个常量符号常量符号代替该存在量词辖域内的相应约束变元，代替该存在量词辖域内的相应约束变元， 这个常量叫这个常量叫SkolemSkolem常量；常量； 若该存在量词若该存在量

47、词在全称量词的辖域内，在全称量词的辖域内，则用这些全则用这些全 称量词指导变元的一个称量词指导变元的一个函数函数代替该存在量词辖域代替该存在量词辖域 内的相应约束变元，这样的函数称为内的相应约束变元，这样的函数称为SkolemSkolem函数函数。 理论依据：理论依据： xA（x）=A（y）y是个体域中某一确定的元素。是个体域中某一确定的元素。 存在指定规则存在指定规则 2021-7-352 3.4.1 3.4.1 子句集子句集(9)(9) 问题问题: :为什么受全称量词约束的要用为什么受全称量词约束的要用SkolemSkolem函数替换函数替换? ? 而不能用常量替换？而不能用常量替换？ x

48、 yM（y，x）：）： 对任意一个人对任意一个人x，都存在一个，都存在一个y，y是是x的妈妈。的妈妈。 若去掉存在量词用常量若去掉存在量词用常量a代替代替y y，则变为：，则变为： x M（a，x）：）：a是所有人的妈妈。是所有人的妈妈。 实际上，引入实际上，引入SkolemSkolem函数，是由于存在量词在全称量词函数，是由于存在量词在全称量词 的辖域之内，其约束变元的取值完全依赖于全称变量的的辖域之内，其约束变元的取值完全依赖于全称变量的 取值。而取值。而SkolemSkolem函数反映了这种依赖关系。函数反映了这种依赖关系。 2021-7-353 3.4.1 3.4.1 子句集子句集(1

49、0)(10) x y P( (x，y) ) z Q( (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) 5、消去所有全称量词。、消去所有全称量词。 理论依据：理论依据： xA（x）=A（y） y是个体域中任一确定的元素。是个体域中任一确定的元素。 全称指定规则全称指定规则 2021-7-354 3.4.1 3.4.1 子句集子句集(11)(11) n子句集的特征子句集的特征 “”作用原子谓词作用原子谓词 没有量词没有量词( ( 、 ) ) 合取

50、范式合取范式 元素之间变元不同元素之间变元不同 集合形式集合形式 没有蕴含词、等值词没有蕴含词、等值词 2021-7-355 3.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、化公式为合取范式、化公式为合取范式 理论依据：理论依据： 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) 分配律分配律 2021-7-356 3.4.1 3.4.1 子句集子句集(13)(13) n子句集的特征子句集的特征 “”作用原子谓词作用原

51、子谓词 没有量词没有量词( ( 、 ) ) 合取范式合取范式 元素之间变元不同元素之间变元不同 集合形式集合形式 没有蕴含词、等值词没有蕴含词、等值词 2021-7-357 3.4.1 3.4.1 子句集子句集(14)(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 S = P( (x，f( (x) ) Q( (x, ,g( (x) ) R

52、( (x, ,g( (x) 2021-7-358 3.4.1 3.4.1 子句集子句集(15)(15) 消去蕴含词和等值词消去蕴含词和等值词 使否定词仅作用于原子公式使否定词仅作用于原子公式 使量词间不含同名指导变元使量词间不含同名指导变元 消去存在量词消去存在量词 消去全称量词消去全称量词 化公式为合取范式化公式为合取范式 子句间无同名变元子句间无同名变元 组成一个集合组成一个集合 “”作用原子谓词作用原子谓词 没有量词没有量词( ( 、 ) ) 合取范式合取范式 元素之间变元不同元素之间变元不同 集合形式集合形式 没有蕴含词、等值词没有蕴含词、等值词 蕴含等价式蕴含等价式 双重否定律、双重

53、否定律、 摩根定律、摩根定律、 量词转换律量词转换律 存在指定、存在指定、 依赖关系依赖关系 全称指定全称指定 分配律分配律 2021-7-359 3.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) 消去合取词和全称量词，就得到了原公式的子句集消去合取词和全称量词，就得到了原公式的子句集 2021-7-360 3.4.1 3.4.1 子句集子句集(17)(17) 引入引入SkolemSkolem函数，是由于存在量词在全称量词的辖函数，是由于存在量词在全称量词的辖 域内，其约束变元的

55、取值完全依赖于全称量词的取值。域内，其约束变元的取值完全依赖于全称量词的取值。 SkolemSkolem反映了这种依赖关系。反映了这种依赖关系。 但但SkolemSkolem标准型与原公式一般并不等价。标准型与原公式一般并不等价。 有公式：有公式： G= = x y P(x，y) 它的它的SkolemSkolem标准型是标准型是 G= x P(x，f(x) 我们给出如下的解释我们给出如下的解释I I： D=0，1，f(0)=1，f(1)=1，P(0，0)=T，P(0，1)=F， P(1，0)=T， P(1，1)=F 在此解释下，在此解释下，GT,G F 2021-7-361 3.4.1 3.4

56、.1 子句集子句集(18)(18) 定理定理3.1 谓词公式谓词公式G不可满足当且仅当其子句集不可满足当且仅当其子句集S不可满不可满 足。足。 定义定义3.133.13 公式公式G是公式是公式F1 1、F2 2 、 、Fn n的逻辑结论（的逻辑结论（ 推论），当且仅当对每一个解释推论），当且仅当对每一个解释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

57、 = = G 定理定理3.33.3 G是公式是公式F1 1、F2 2、Fn n的逻辑结论，当且仅当的逻辑结论，当且仅当 F1 1 F2 2 Fn n G 是不相容的。是不相容的。 2021-7-362 3.4.1 3.4.1 子句集子句集(19)(19) 例例3.8 化子句集化子句集 已知前提：已知前提： （1）自然数都是大于零的整数。）自然数都是大于零的整数。 （2）所有整数不是偶数就是奇数。）所有整数不是偶数就是奇数。 （3）偶数除以）偶数除以2是整数。是整数。 结论：所有自然数不是奇数就是一半为整数的数。结论：所有自然数不是奇数就是一半为整数的数。 化化F1 1 F2 2 F3 3 G的

58、的子句集。子句集。 F1 1: : x ( (N( (x) )GZ( (x) ) I( (x) F2 2: : x ( (I( (x) )( (E( (x) ) O( (x) ) F3 3: : x ( (E( (x) )I( (s( (x) G: : x ( (N( (x) )( (I( (s( (x) O( (x) 2021-7-363 3.4.1 3.4.1 子句集子句集(20)(20) 解：解：F1 1 F2 2 F3 3 G的子句集为的子句集为 （1 1） N( (x) ) GZ( (x) ) （2 2） N( (y) ) I( (y) ) （3 3） I( (z) ) E( (z)

59、 ) O( (z) ) （4 4） E( (u) ) I( (s( (u) （5 5）N( (a) ) （6 6） O( (a) ) （7 7） I( (s( (a) 2021-7-364 3.4.2 3.4.2 命题逻辑中的归结原理命题逻辑中的归结原理(1)(1) n归结原理的提出归结原理的提出 归结原理归结原理(principle of resolution)(principle of resolution)又称消解原又称消解原 理理,1965,1965年鲁滨逊（年鲁滨逊（J.A.RobinsonJ.A.Robinson）提出，从理论上解）提出，从理论上解 决了定理证明问题。归结原理提出的

60、是一种证明子句决了定理证明问题。归结原理提出的是一种证明子句 集不可满足性，从而实现定理证明的一种理论及方法。集不可满足性，从而实现定理证明的一种理论及方法。 2021-7-365 3.4.2 3.4.2 命题逻辑中的归结原理命题逻辑中的归结原理(2)(2) 定义定义3.143.14 设设L为一个文字，则为一个文字，则L与与L为为互补文字互补文字。 定义定义3.153.15 设设C1 1， C2 2是命题逻辑中的两个子句，是命题逻辑中的两个子句， C1 1中有文字中有文字L1 1 ，C2 2中有文字中有文字L2 2 ，且，且L1 1与与L2 2互补，互补， 从从C1 1 、 、 C2 2中分别