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

《第3章-基于谓词逻辑的知识表示与机器推理.pptx》由会员分享，可在线阅读，更多相关《第3章-基于谓词逻辑的知识表示与机器推理.pptx（92页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2023/3/101第第3 3章章 基于基于谓词逻辑的知的知识表示表示与机器推理与机器推理2023/3/102内容内容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 基于基于规则的演的演绎推理推理2023/3/1033.1 3.1 机器推理机器推理概述概述n 机器推理机器推理 推理是人脑的一个基本功能和重要功能，几乎所有的推理是人脑的一个基本功能和重要功能，几乎所有的人工智能领域都与推理有关。因此，要实现人工智能，就人工智

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

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

4、奇数就是一半为整数的数。半为整数的数。定理的谓词公式描述：定理的谓词公式描述：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)2023/3/1053.2 3.2 谓词逻辑简介介3.2.1 3.2.1 基于命基于命题逻辑的知的知识表示表示 3.2.2 3.2.2 谓词逻辑 3.2.3 3.2.3 基于基于谓词逻辑的知的知识表示表示 2023/3/1063.2.1

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

6、果R（今天天气好）今天天气好）成立，则可以得到结论成立，则可以得到结论S（去旅游去旅游）2023/3/1073.2.13.2.1基于命基于命题逻辑的知的知识表示表示（2 2）n对于复于复杂的知的知识，命，命题符号能力不符号能力不够。n无法把所描述的客无法把所描述的客观事物的事物的结构及构及逻辑特征特征反映出来。反映出来。n无法把不同事物无法把不同事物间的共同特征表达出来。的共同特征表达出来。P：大李是小李的父亲。：大李是小李的父亲。S1：我有名字：我有名字 S2：你有名字：你有名字所有的人都有名字：所有的人都有名字：SI S2 S3 2023/3/1083.2.2 3.2.2 谓词逻辑（1 1

7、）谓词(predicate)：一般形式一般形式为P（x1,x2,xn）P为谓词名（名（谓词符号），符号），用于刻画个体的性用于刻画个体的性质、状状态或个体或个体间的关系。的关系。x1，x2，xn是是个体，个体，表示某个独立存在的表示某个独立存在的事物或者某个抽象的概念。事物或者某个抽象的概念。S(x):x是学生；是学生；P(x,y):x是是y的父亲。的父亲。个体变元的变化范围称为个体变元的变化范围称为个体域个体域。包揽一切事物的集合称为包揽一切事物的集合称为全总个体域全总个体域。2023/3/1093.2.2 3.2.2 谓词逻辑（2 2）n函数：函数：为了表达个体之了表达个体之间的的对应关系

8、，引入数关系，引入数学中函数概念和学中函数概念和记法。用形如法。用形如f(x1 1，x2 2，xn n)来表示个体来表示个体变元元对应的个体的个体y y，并称之，并称之为n元元个体函数个体函数，简称函数、函称函数、函词或函或函词命名式。命名式。函数函数 father(x):father(x):值为值为x x的父亲。的父亲。谓词谓词D(D(fatherfather(Li Li):):表示表示x x的父亲是医生，值为真或假。的父亲是医生，值为真或假。符号约定：符号约定：谓词大写字母；谓词大写字母；P(x,y)函数小写字母；函数小写字母；f(x)变量变量 x、y、z、u、v；常量常量a、b、c.。P

9、(a,y)2023/3/10103.2.2 3.2.2 谓词逻辑（3 3）n为了表示命了表示命题中出中出现的的“全部全部”、“所有所有”、“一切一切”、“任一任一”或或“凡是凡是”等意等意义，引入，引入全称量全称量词，记为 x。n为了表示命了表示命题中出中出现的的“存在存在”、“某些某些”、“有一有一个个”等意等意义，引入，引入存在量存在量词，记为 x。如：如：“某些学生某些学生对某些某些课外活外活动感感兴趣趣”S(x)表示表示x是学生，是学生，L(y)表示表示y是是课外活外活动，I(x,y)表示表示x对y感感兴趣。趣。2023/3/10113.2.2 3.2.2 谓词逻辑（4 4）定义定义3

10、.23.2：项项（1 1）个体常元和变元都是项。个体常元和变元都是项。（2 2）f是是n元函数符号，若元函数符号，若t1 1，t2 2，tn n是项，则是项，则 f（t1 1，t2 2，tn n ）是项。）是项。（3 3）只有有限次使用（）只有有限次使用（1 1），（），（2 2）得到的符号串才是项。）得到的符号串才是项。2023/3/10123.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）称为原子谓词公式，简称原子或原）称为原子谓词公式，简称原子或原

11、子公式。子公式。2023/3/10133.2.2 3.2.2 谓词逻辑（6 6）定义定义3.43.4：谓词公式：谓词公式（1 1）原子公式是谓词公式。）原子公式是谓词公式。（2 2）若）若A、B是谓词公式，则是谓词公式，则 A，A B，A B，A B，AB，xA，xA也是谓词公式。也是谓词公式。（3 3）只有有限步应用（）只有有限步应用（1 1）（）（2 2）生成的公式才是谓词公式。）生成的公式才是谓词公式。2023/3/10143.2.2 3.2.2 谓词逻辑（7 7）n辖域域：紧接于量接于量词之后被量之后被量词作用（即作用（即说明）的明）的谓词公式称公式称为该量量词的的辖域。域。n指指导变

12、量量：量：量词后的后的变量量为量量词的指的指导变量。量。n约束束变量量：在一个量：在一个量词辖域中与域中与该量量词的指的指导变元相同的元相同的变量称量称为约束束变量。量。n自由自由变量量：谓词公式中除了公式中除了约束束变量之外的量之外的变量。量。（1）（2）（3）2023/3/10153.2.2 3.2.2 谓词逻辑（8 8）n一个一个变元在一个公式中既可以元在一个公式中既可以约束出束出现，也可以自由出也可以自由出现，为了避免混淆，通了避免混淆，通过改改名名规则改名：改名：n对需要改名的需要改名的变元，元，应同同时更改更改该变元在量元在量词及其及其辖域中的域中的所有出所有出现。n新新变元符号必

13、元符号必须是量是量词辖域内域内原先没有原先没有的，最的，最好是好是公式中公式中也也未出未出现过的。的。y F(y)D（y）x F(x)D（y）2023/3/10163.2.2 3.2.2 谓词逻辑（9 9）n谓词公式与命公式与命题的区的区别与与联系系n谓词公式是公式是命命题函数函数。n一个一个谓词公式中所有个体公式中所有个体变元被量化，元被量化，谓词公公式就式就变成了一个命成了一个命题。n从从谓词公式得到命公式得到命题的两种方法：的两种方法：给谓词中的中的个体个体变元代入个体常元；把元代入个体常元；把谓词中的个体中的个体变元元全部量化。全部量化。例：例：P（x）表示）表示“x是素数是素数”x

14、P（x），），x P（x），），P（a）都是命题都是命题2023/3/10173.2.2 3.2.2 谓词逻辑（1010）n一一阶谓词：仅个体个体变元被量化的元被量化的谓词。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)2023/3/10183.2.2 3.2.2 谓词逻辑（1111）定义定义3.53.5：合取范式（：合取范式（Conjunctive Norm

15、al FormConjunctive 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称为合取范式。称为合取范式。例例 就是一个合取范式就是一个合取范式2023/3/10193.2.2 3.2.2 谓词逻辑（1212）定义定义3.63.6：析取范式：析取范式（Disjunctive Normal FormDisjunctive Normal Form）设设A A为如

16、下形式的谓词公式：为如下形式的谓词公式：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)就是一个析取范式就是一个析取范式2023/3/10203.2.2 3.2.2 谓词逻辑（1313）定定义3.7 3.7 谓词公式的解公式的解释 设D为谓词公式公式P的个体域，若的个体域，若对P中的个体常量、函中的个体常量、函数和数和谓词按如下按如下规定

17、定赋值：（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上的一个解上的一个解释。2023/3/10213.2.2 3.2.2 谓词逻辑（1414）例例3.13.1：设个体域个体域D1,2,1,2,求公式求公式 在在D上的解上的解释，并指出在每一种解，并指出在每一种解释

18、下下公式公式A A的真的真值。解：解：设公式公式A中中对个体常量个体常量b、函数、函数f（x）指派的真）指派的真值分分别为：b=2，f(1)=2，f(2)=1对谓词指派的真指派的真值为：P(1，1)=T，P(1，2)=T，P(2，1)=T，P(2，2)=FQ(1，2)=F，Q(2，2)=T 2023/3/10223.2.2 3.2.2 谓词逻辑（1515）在此解在此解释下，下，由于当由于当x=1时，有，有y=2，使得：，使得：所以所以 为T。当当x=2时，有有y=2，使得，使得 所以所以 为T。所以公式所以公式A在此解在此解释下真下真值为T。2023/3/10233.2.2 3.2.2 谓词逻

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

20、性。2023/3/10243.2.2 3.2.2 谓词逻辑（谓词逻辑（1717）定义定义3.93.9：谓词公式的永假：谓词公式的永假 如果如果谓词公式谓词公式P对于个体域对于个体域D上的任何一个解释都取得上的任何一个解释都取得真值真值F，则称，则称P在在D上是永假的；如果上是永假的；如果P在全总个体域上在全总个体域上永假，则称永假，则称P永假。永假。谓词公式的永假性又称不可满足性或不相容。谓词公式的永假性又称不可满足性或不相容。2023/3/10253.2.3 3.2.3 基于基于谓词逻辑的知的知识表示表示（1）用谓词表示命题时，一般取全总个体域，再采用使用用谓词表示命题时，一般取全总个体域，

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

22、有如下命题：（1）小明比他的哥哥学）小明比他的哥哥学习努力。努力。定定义谓词：x x比比y y学学习努力努力 定定义函数：函数：x x的哥哥的哥哥 谓词公式表示公式表示为：2023/3/10273.2.3 3.2.3 基于基于谓词逻辑的知的知识表示表示（3）（2）对于所有的自然数，均有于所有的自然数，均有 。定定义谓词：x是自然数是自然数 ：x大于等于大于等于y 定定义函数：函数：x与与y的和的和 谓词公式表示公式表示为：2023/3/10283.2.3 3.2.3 基于基于谓词逻辑的知的知识表示表示（4）（3）某些人）某些人对某些食物某些食物过敏。敏。定定义谓词：x是人是人 ：x是食物是食物

23、 ：x对y过敏敏 谓词公式表示公式表示为：2023/3/10293.2.3 3.2.3 基于基于谓词逻辑的知的知识表示表示（5）例例3.3 用用谓词公式表示下述命公式表示下述命题。已知前提：已知前提：F1：自然数自然数都是都是大于零大于零的的整数整数。F2：所有整数不是：所有整数不是偶数偶数就是就是奇数奇数。F3：偶数：偶数除以除以2是整数。是整数。结论：所有自然数不是奇数就是一半：所有自然数不是奇数就是一半为整数的数。整数的数。首先定义如下谓词：首先定义如下谓词：N(x):x是自然数。是自然数。I(x):x是整数。是整数。E(x):x是偶数。是偶数。O(x):x是奇数。是奇数。GZ(x):x

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

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

26、ds(Robot,Box)：机器人：机器人Robot拿着拿着Box On(Box,x)：盒子在：盒子在x上上2023/3/10323.2.3 3.2.3 基于基于谓词逻辑的知的知识表示表示（8）初始状初始状态为：目目标状状态为：2023/3/10333.2.3 3.2.3 基于基于谓词逻辑的知的知识表示表示（9）以机器人的操作以机器人的操作PICKUP(a)为例来例来说明操作明操作进行的条件和行的条件和动作：作：条件：条件：On(Box,a)At(Robot,a)Empty(Robot)删除：除：Empty(Robot)On(Box,a)增加：增加：Holds(Robot,Box)2023/3

27、/10343.33.3自然演自然演绎推理（推理（1 1）n自然演自然演绎推理推理 利用一利用一阶谓词推理推理规则的符号表示形式，可以把关于的符号表示形式，可以把关于自然自然语言的言的逻辑推理推理问题，转化化为符号表达式的推演符号表达式的推演变换。这种推理十分种推理十分类似于人似于人们用自然用自然语言推理的思言推理的思维过程，因而称程，因而称为自然演自然演绎推理。推理。n常用常用逻辑等价式等价式n常用推理定律常用推理定律 2023/3/1035常用常用逻辑等价式（等价式（1 1）2023/3/1036常用常用逻辑等价式（等价式（2 2）2023/3/1037常用推理定律常用推理定律2023/3/

28、10383.33.3自然演自然演绎推理（推理（2 2）例例3.5 3.5 设有前提：设有前提：（1 1）有些病人相信所有的医生。）有些病人相信所有的医生。（2 2）病人都不相信骗子。）病人都不相信骗子。求证：所有的医生都不是骗子。求证：所有的医生都不是骗子。证明：定义谓词：证明：定义谓词：P(x)：x是病人是病人：x是医生是医生：x是骗子是骗子：x相信相信y将前提和要证明的结论转化为谓词公式：将前提和要证明的结论转化为谓词公式：前提：前提：（1 1）（2 2）结论：结论：2023/3/10393.33.3自然演自然演绎推理（推理（3 3）（2 2）（1 1），存在指定规则），存在指定规则（3

29、3）（2 2），简化律），简化律（4 4）前提引入前提引入（5 5）（4 4），全称指定规则），全称指定规则（6 6）（3 3）（）（5 5），假言推理），假言推理（7 7）（1 1）前提引入前提引入 （6 6），全称指定规则），全称指定规则 2023/3/10403.33.3自然演自然演绎推理（推理（4 4）（8 8）（7 7），逆反律），逆反律 （9 9）（2 2），化简规则），化简规则 （1010）（9 9），全称指定规则），全称指定规则（1111）（8 8）（）（1010），假言三段论），假言三段论（1212）（1111），全称推广规则），全称推广规则 endn本周本周暂无作无作业n大

30、家好好复大家好好复习课件件2023/3/10412023/3/1042这个例子个例子说明了人明了人对倒倒过来的人来的人脸的表情的的表情的识别能力很差。能力很差。长期的期的进化化过程中，我程中，我们对正着的人正着的人脸造成了造成了过拟合，正着的信息合，正着的信息变得不是很得不是很重要。上面的重要。上面的图出出现错觉的原因是，的原因是，虽然人然人脸是倒着的，我是倒着的，我们却用正着却用正着的思路的思路观察察图片中眼睛，而眼睛的片中眼睛，而眼睛的线条走向条走向给了我了我们表情信息：表情信息：2023/3/1043中中间的条的条带其其实没有没有渐变造成造成这个个错觉的原因是，的原因是，对了了对应自然界

31、中阴影自然界中阴影对颜色色识别的副作用，我的副作用，我们大大脑擅自减去了阴影擅自减去了阴影对颜色的影响。在色的影响。在进化中，我化中，我们正如火正如火鸡一一样，觉得得每天上午十一点，就有食物降每天上午十一点，就有食物降临；同；同样的，我的，我们觉得把阴影得把阴影对颜色的干色的干扰消除掉，就能消除掉，就能识别得更好，得更好，这成成为了我了我们的准定律。然而，上面的的准定律。然而，上面的错觉图中，要求我中，要求我们比比较 A 和和 B 的的颜色，就好似感恩色，就好似感恩节对火火鸡一一样，我，我们大大脑仍然仍然不听不听话地擅自改地擅自改变颜色，色，导致我致我们在在这个极其特殊的个极其特殊的问题上判断

32、失上判断失误2023/3/1044按照一定距离按照一定距离观察察这幅幅图，会，会让我我们觉得得产生了生了缠绕或者扭曲。或者扭曲。实际上上这些就是一个个同心些就是一个个同心圆。产生生错觉的原因是，大的原因是，大脑给我我们脑补了很多了很多倾斜斜边（这些方些方块是是倾斜的，并且采用了不同的斜的，并且采用了不同的颜色加色加强边的效果）的效果），这些些边的形状不同于它的形状不同于它们的排列方向，因此会的排列方向，因此会觉得得缠绕。如果我。如果我们到了到了这样的的图案居多的世界中，我案居多的世界中，我们的的现在在视觉系系统将将难以正常工作。以正常工作。2023/3/10453.43.4归结演演绎推理推理3

33、.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 归结策略策略2023/3/10463.4.1 3.4.1 子句集子句集(1)(1)原子谓词公式及其否定称为原子谓词公式及其否定称为文字文字原子谓词公式称为原子谓词公式称为正文字正文字原子谓词公式的否定称为原子谓词公式的否定称为负文字负文字定义定义3.11 3.11 任何文字的任何文字的析取析取称为一个称为一个子句。子句。由由n n个文字

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

35、y)谓词公式与子句集有哪些区别？谓词公式与子句集有哪些区别？“”作用原子谓词作用原子谓词没有量词没有量词(、)合取范式合取范式元素之间变元不同元素之间变元不同定义定义3.123.12：对一个谓词公式：对一个谓词公式G，通过以下步骤所得的子句集，通过以下步骤所得的子句集 S，称为，称为G的的子句集（子句集（clausesclauses）。集合形式集合形式没有蕴含词、等值词没有蕴含词、等值词2023/3/10483.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)问题问

36、题:蕴含式蕴含式 y P(x，y)y Q(x,y)R(x,y)的前件是？的前件是？1 1：y P(x，y)2 2：P(x，y)1 1、消蕴含词和等值词消蕴含词和等值词理论根据理论根据：AB A B A B (A B)(B A)蕴含等价式蕴含等价式2023/3/10493.4.1 3.4.1 子句集子句集(4)(4)n子句集的特征子句集的特征“”作用原子谓词作用原子谓词没有量词没有量词(、)合取范式合取范式元素之间变元不同元素之间变元不同集合形式集合形式没有蕴含词、等值词没有蕴含词、等值词2023/3/10503.4.1 3.4.1 子句集子句集(5)(5)x y P(x，y)y Q(x,y)R

37、(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)2023/3/10513.4.1 3.4.1 子句集子句集(6)(6)n子句集的特征子句集的特征“”作用原子谓词作用原子谓词没有量词没有量词(、)合取范式合取范式元素之间变元不同元

38、素之间变元不同集合形式集合形式没有蕴含词、等值词没有蕴含词、等值词2023/3/10523.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(x,y)R(x,y)问题问题:不同辖域的相同变元对应的约束相同吗不同辖域的相同变元对应的约束相同吗?2023/3/10533.4.1 3.4.1 子句集子句集(8)(8)4 4、消去存在量词消去存在量词(Skolem(Skolem化）化）,同时进行变元

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

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

41、在量词在全称量词的辖域之内，其约束变元的取值完全依赖于全称变量的的辖域之内，其约束变元的取值完全依赖于全称变量的取值。而取值。而SkolemSkolem函数反映了这种依赖关系。函数反映了这种依赖关系。2023/3/10553.4.1 3.4.1 子句集子句集(10)(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是个体域中任一确定的元素。是个体域中任一确定的元素。全称指定规则全称指定规则 2023/3

42、/10563.4.1 3.4.1 子句集子句集(11)(11)n子句集的特征子句集的特征“”作用原子谓词作用原子谓词没有量词没有量词(、)合取范式合取范式元素之间变元不同元素之间变元不同集合形式集合形式没有蕴含词、等值词没有蕴含词、等值词2023/3/10573.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)分配律分配律 2023/3/10583.4.

43、1 3.4.1 子句集子句集(13)(13)n子句集的特征子句集的特征“”作用原子谓词作用原子谓词没有量词没有量词(、)合取范式合取范式元素之间变元不同元素之间变元不同集合形式集合形式没有蕴含词、等值词没有蕴含词、等值词2023/3/10593.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(

44、x)R(x,g(x)2023/3/10603.4.1 3.4.1 子句集子句集(15)(15)过程小程小结消去蕴含词和等值词消去蕴含词和等值词使否定词仅作用于原子公式使否定词仅作用于原子公式使量词间不含同名指导变元使量词间不含同名指导变元消去存在量词消去存在量词消去全称量词消去全称量词化公式为合取范式化公式为合取范式子句间无同名变元子句间无同名变元组成一个集合组成一个集合“”作用原子谓词作用原子谓词没有量词没有量词(、)合取范式合取范式元素之间变元不同元素之间变元不同集合形式集合形式没有蕴含词、等值词没有蕴含词、等值词蕴含等价式蕴含等价式双重否定律、双重否定律、摩根定律、摩根定律、量词转换律量

45、词转换律存在指定、存在指定、依赖关系依赖关系全称指定全称指定分配律分配律2023/3/10613.4.1 3.4.1 子句集子句集(16)(16)SkolemSkolem标准型标准型 在求子句集的过程中，消去存在量词在求子句集的过程中，消去存在量词之后，把所有之后，把所有全称量词全称量词都依次移到式子的最左边（或者都依次移到式子的最左边（或者把所有的量词都依次移到式子最左边，再消去存在量把所有的量词都依次移到式子最左边，再消去存在量词），再将右部的式子化为合取范式，这样得到的式词），再将右部的式子化为合取范式，这样得到的式子就是子就是SkolemSkolem标准型。标准型。x y P(x，y)

46、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)消去合取词和全称量词，就得到了原公式的子句集消去合取词和全称量词，就得到了原公式的子句集2023/3/10623.4.1 3.4.1 子句集子句集(17)(17)引入引入SkolemSkolem函数，是由于存在量词在全称量词的函数，是由于存在量词在全称量词的辖域辖域内内，其其约束变元的取值完全依赖于全称量词的取值约束变元的取值完全依赖于全称量词的取值。SkolemSkolem反映反

47、映了这种依赖关系了这种依赖关系。但但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 F2023/3/10633.4.1 3.4.1 子句集子句集(18)(18)定理定理3.1 谓词公式公式G不可不可满足当且足当且仅当其子句集当其子句集S不可不可满足。足。定定义3.

48、13 3.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=G定理定理3.3 3.3 G是公式是公式F1 1、F2 2、Fn n的的逻辑结论，当且，当且仅当当 F1 1 F2 2 Fn n G 是不相容的。是不相容的。2023/3/10643.4.1 3.4.1 子句集

49、子句集(19)(19)例例3.8 化子句集化子句集已知前提：已知前提：（1）自然数都是大于零的整数。）自然数都是大于零的整数。（2）所有整数不是偶数就是奇数。）所有整数不是偶数就是奇数。（3）偶数除以）偶数除以2是整数。是整数。结论：所有自然数不是奇数就是一半：所有自然数不是奇数就是一半为整数的数。整数的数。化化F1 1 F2 2 F3 3 G的的子句集。子句集。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)2023/3/10653.4.1 3.4.1 子句集子句集(20)(20)解：解：

50、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)O(z)（4 4）E(u)I(s(u)（5 5）N(a)（6 6）O(a)（7 7）I(s(a)2023/3/10663.4.2 3.4.2 命命题逻辑中的中的归结原理原理(1)(1)n归结原理的提出原理的提出 归结原理原理(principle of resolution)(principle of resolution)又称消解原又称消解原理理,1965,1965年年鲁滨逊（J.A.RobinsonJ.A.Robinson）提出，从理）提出，从理论上解决上解决了定