第三章 谓词逻辑与归结原理

1、2021-12-271第三章第三章 谓词逻辑与归结原理谓词逻辑与归结原理华北电力大学华北电力大学 计算机系计算机系 刘丽刘丽2021-12-27华北电力大学华北电力大学2第三章第三章 谓词逻辑与归结原理谓词逻辑与归结原理 归结原理概述 命题逻辑的归结法 谓词逻辑归结基础 归结原理 归结过程的控制策略 Herbrand定理2021-12-27华北电力大学华北电力大学3归结归结推理推理命题命题逻辑逻辑谓词逻谓词逻辑辑Skolem标准型、标准型、子句集子句集基本基本概念概念谓词逻辑谓词逻辑归结原理归结原理合一和置换、合一和置换、控制策略控制策略数理数理逻辑逻辑命题逻辑命题逻辑归结归结Herbrand

2、定理定理内容框架内容框架2021-12-27华北电力大学华北电力大学4第三章第三章 谓词逻辑与归结原理谓词逻辑与归结原理 归结原理概述 命题逻辑的归结法 谓词逻辑归结基础 归结原理 归结过程的控制策略2021-12-27华北电力大学华北电力大学5概述概述-推理技术推理技术 确定知识表达方法将知识表示出来并存储到计算机中利用知识来解决实际问题如专家系统、智能机器人、模式识别、自然语言理解等 按照某种策略从已有事实和知识推出结论的过程。推理是由程序实现的，称为推理机 医疗诊断专家系统 知识库中存储经验及医学常识 数据库中存放病人的症状、化验结果等初始事实 利用知识库中的知识及一定的控制策略，为病人

3、诊治疾病、开出医疗处方就是推理过程2021-12-27华北电力大学华北电力大学6概述概述 推理的分类 演绎推理、归纳推理、默认推理 确定性推理、不精确推理 单调推理、非单调推理 启发式推理、非启发式推理 2021-12-27华北电力大学华北电力大学7概述概述 从推出新判断的途径分演绎、归纳和默认推理 演绎推理 从全称判断推出特称判断或单称判断的过程，即从一般到个别的推理 演绎推理中最常用的形式是三段论法（大前提和小前提，及结论） 例如： 所有的推理系统都是智能系统一般的知识 专家系统是推理系统个体的判断 所以，专家系统是智能系统新判断没有增加新的知识2021-12-27华北电力大学华北电力大学

4、8概述概述-演绎推理、归纳推理和默认推理演绎推理、归纳推理和默认推理 归纳推理 从足够多的事例中归纳出一般性结论的推理过程，是一种 常用的归纳推理有简单枚举法和类比法 枚举法归纳推理是由已观察到的事物都有某属性，而没有观察到相反的事例，从而推出某类事物都有某属性，推理过程为：S1 是 PS2 是 P Sn 是 P (S1,S2, Sn 是S 类中的个别事物，在枚举中兼容) 2021-12-27华北电力大学华北电力大学9概述概述-演绎推理、归纳推理和默认推理演绎推理、归纳推理和默认推理 归纳推理之枚举法 枚举法归纳推理分完全归纳推理与不完全归纳推理 完全归纳推理完全归纳推理在进行归纳时考察了相应

5、事物的全部对象，并根据这些对象是否都具有某种属性，从而推出这个事物是否具有这个属性完全归纳推理是必然性推理 不完全归纳推理不完全归纳推理只考察了相应事物的部分对象，就得出了结论不完全推理得出的结论不具有必然性，属于非必然性推理2021-12-27华北电力大学华北电力大学10概述概述-演绎推理、归纳推理和默认推理演绎推理、归纳推理和默认推理 归纳推理之类比法 在两个或两类事物在许多属性上都相同的基础上，推出它们在其它属性上也相同，这就是 类比法归纳可形式化地表示为： A 具有属性a,b,c,d,e B 具有属性a,b,c,d, 类比法的可靠程度决定于两个或两类事物的相同属性与推出的那个属性之间的

6、相关程度，相关程度越高，则类比法的可靠性就越高（在机器学习部分称为归纳学习）2021-12-27华北电力大学华北电力大学11概述概述-演绎推理、归纳推理和默认推理演绎推理、归纳推理和默认推理 默认推理 又称为缺省推理，是在知识不完全的情况下假设某些条件已经具备所进行的推理 如：在条件A已成立的情况下，如果没有足够的证据能证明条件B不成立，则就默认B是成立的，并在此默认的前提下进行推理，推导出某个结论 知识不完全的情况下也能进行推理 如果到某一时刻发现原先所作的默认不正确，则要撤消所作的默认以及由此默认推出的所有结论，重新按新情况进行推理 2021-12-27华北电力大学华北电力大学12概述概述

7、 按推理时所用的知识的确定性分 确定性推理 推理中所用的知识都是精确的 归结反演、基于规则的演绎系统等都是确定性推理 不精确推理 基于不确定的推理规则进行，形成的结论也是不确定的 专家系统中主要使用的是不精确推理2021-12-27华北电力大学华北电力大学13概述概述 按推出的结论是否单调增加，或推出的结论是否越来越接近最终目标分： 单调推理 在推理过程中随着推理的向前推进及新知识的加入，推出的结论呈单调增加的趋势，并且越来越接近最终目标 非单调推理 在推理过程中随着推理的向前推进及新知识的加入，不仅没有加强已推出的结论，反而要否定它，使得推理退回到前面的某一步，重新开始 一般非单调推理是在知

8、识不完全的情况下进行的2021-12-27华北电力大学华北电力大学14概述概述 按推理中是否运用与问题有关的启发性知识分 启发式推理 推理过程中，运用与问题有关的启发性知识，以加快推理过程，提高搜索效率 A*、AO*等算法就属于此类推理 非启发式推理 推理过程中，不运用启发性知识，只按照一般的控制逻辑进行推理 这种方法缺乏对求解问题的针对性，所以推理效率较低，容易出现“组合爆炸”问题，如宽度优先搜索法2021-12-27华北电力大学华北电力大学15概述概述 推理的控制策略 主要是指推理方向的选择、推理时所用的搜索策略及冲突解决策略等 一般推理的控制策略与知识表达方法有关 推理方向 推理方向用于

9、确定推理的驱动方式 根据推理方向的不同，可将推理分为正向推理、反向推理和正反向混合推理 无论按哪种方式进行推理，一般都要求系统具有一个存放知识的知识库（KB）、一个存放初始事实和中间结果的数据库（DB）和一个用于推理的推理机2021-12-27华北电力大学华北电力大学16概述概述-推理的控制策略推理的控制策略 推理方向 正向推理（事实驱动推理）是由已知事实出发向结论方向的推理开始DB中是否包含问题的解？将用户提供的新事实加入DB中KB中是否有可适用的知识？把KB中所有适用的规则加入到RS中RS为空？按一定的冲突解决策略从RS中选择一条规则进行推理将推理结论加入DB中成功，退出用户可是否补充新事

10、实？失败，退出将初始事实加入数据库DB中是 否否是否是否2021-12-27华北电力大学华北电力大学17概述概述-推理的控制策略推理的控制策略 推理方向 反向推理以某个假设目标作为出发点的一种推理，又称为目标驱动推理或逆向推理在KB中找出所有能导出该假设的规则，形成适用规则集RS该假设是否是事实？该假设在数据库DB？从RS中选择一条规则，并将该规则的一个条件作为新的假设目标该假设成立有假设？退出询问用户有事实？该假设成立，并将此假设作为事实存入DB提出假设开始是否是否否是是否2021-12-27华北电力大学华北电力大学18概述概述-推理的控制策略推理的控制策略 推理方向 正反混合推理是开始进行

11、正向推理需要反向推理？以正向推理所得结果作为假设进行反向推理还需要正向推理吗？输出结果退出否是否2021-12-27华北电力大学华北电力大学19概述概述-推理的控制策略推理的控制策略 推理时，要反复用到知识库中的规则，而知识库中的规则又很多，这样就存在着如何在知识库中寻找可用规则的问题 为有效控制规则的选取，可以采用各种搜索策略 常用搜索策略：状态空间搜索（宽度优先搜索、深度优先搜索、有界深度优先搜索等）启发式搜索等（第三章）2021-12-27华北电力大学华北电力大学20概述概述-推理的控制策略推理的控制策略 冲突解决策略冲突解决策略 推理过程中，系统要不断地用数据库中的事实与知识库中的规则

12、进行匹配，当有一个以上规则的条件部分和当前数据库相匹配时，就需要有一种策略来决定首先使用哪一条规则，这就是 冲突解决策略实际上就是确定规则的启用顺序 2021-12-27华北电力大学华北电力大学21概述概述-推理的控制策略推理的控制策略 推理的控制策略推理的控制策略 (1) 专一性排序如果某一规则的条件部分规定的情况比另一规则的条件部分所规定的情况更专门，则这条规则具有较高的优先级例，有如下规则：规则1：IF A AND B AND C THEN E；规则2：IF A AND B AND C AND D THEN F；数据库中A、B、C、D均为真，这时规则1和规则2都与数据库相匹配，但因为规则

13、2的条件部分包括了更多的限制，所以具有较高的优先级 2021-12-27华北电力大学华北电力大学22概述概述-推理的控制策略推理的控制策略推理的控制策略推理的控制策略 (2) 规则排序规则编排的顺序就表示了启用的优先级 (3) 数据排序数据排序就是把规则条件部分的所有条件排序，按优先级次序编排，发生冲突时，首先使用在条件部分包含较高优先级数据的规则 (4) 就近排序把最近使用的规则放在最优先的位置。如果某一规则经常使用，则倾向于更多地使用这条规则 (5) 上下文限制上下文限制就是把产生式规则按它们所描述的上下文分组，在某种上下文条件下，只能从与其相对应的那组规则中选择可应用的规则2021-12

14、-27华北电力大学华北电力大学23概述概述-推理的控制策略推理的控制策略推理的控制策略推理的控制策略 (6) 按匹配度排序在不精确匹配中，为了确定两个知识模式是否可以进行匹配，需要计算这两个模式的相似程度，当其相似度达到某个预先规定的值时，就认为它们是可匹配的。若有几条规则均可匹配成功，则可根据它们的匹配度来决定哪一个产生式规则可优先被应用 (7) 按条件个数排序如果有多条产生式规则生成的结论相同，则要求条件少的产生式规则被优先应用，因为要求条件少的规则匹配时花费的时间较少不同的系统，可使用上述这些策略的不同组合不同的系统，可使用上述这些策略的不同组合2021-12-27华北电力大学华北电力大

15、学24概述概述 归结原理由J.A.Robinson于1965年提出 定理证明的实质就是要对给出的（已知的）前提和结论，证明此前提推导出该结论这一事实是永恒的真理 这是非常困难的，几乎是不可实现的 要证明在一个论域上一个事件是永真的： 就要证明在该域中的每一个点上该事实都成立 论域是不可数时，该问题不可能解决 即使可数，如果该轮域是无限的，问题也无法简单地解决2021-12-27华北电力大学华北电力大学25概述概述 理论基础： Herbrand采用了反证法的思想，将永真性的证明问题转化成为不可满足性的证明问题 实现方法： Robinson的归结原理使得自动定理证明得以实现 归结推理方法在人工智能

16、推理方法中有着很重要的历史地位，是机器定理证明的主要方法2021-12-27华北电力大学华北电力大学26归结法的特点归结法的特点 归结法是一阶逻辑中，至今为止的最有效的半可判定的算法。也是最适合计算机进行推理的逻辑演算方法 半可判定半可判定 一阶逻辑一阶逻辑中任意恒真公式，使用归结原理，总可以在有限步内给以判定（证明其为永真式） 当不知道该公式是否为恒真时，使用归结原理不能得到任何结论2021-12-27华北电力大学华北电力大学27归结法基本原理归结法基本原理 采用反证法(反演推理方法) 将待证明的表达式（定理）转换成为逻辑公式（谓词公式） 然后再进行归结 归结能够顺利完成，则证明原公式（定理

17、）是正确的2021-12-27华北电力大学华北电力大学28归结法基本原理归结法基本原理例例 例：由命题逻辑描述的命题：A1、A2、A3和B，要求证明： 如果A1A2A3成立，则B成立，即：A1A2A3B是重言式（永真式） 归结法的思路 A1A2A3B是重言式等价于A1A2A3B是矛盾式，也就是永假式 反证法：证明A1A2A3B 是矛盾式（永假式） 2021-12-27华北电力大学华北电力大学29归结法和其它推理方法的比较归结法和其它推理方法的比较 语义网络、框架表示、产生式规则等知识表示方法的推理都是以逻辑推理方法为前提的 也就是说如果有了规则和已知条件，就能够依据一定的规则和公理顺藤摸瓜找到

18、结果 归结方法是在一个规则指导下，进行自动推导。多用于计算机自动推理、自动推导证明 注意：只讨论一阶谓词逻辑描述下的归结推理方法，不涉及高阶谓词逻辑问题 2021-12-27华北电力大学华北电力大学30第三章谓词逻辑与归结原理第三章谓词逻辑与归结原理 概述 命题逻辑的归结法 谓词逻辑归结基础 归结原理 归结过程的控制策略 Herbrand定理2021-12-27华北电力大学华北电力大学31第三章谓词逻辑与归结原理第三章谓词逻辑与归结原理 概述 命题逻辑的归结法 谓词逻辑归结基础 归结原理 归结过程的控制策略 Herbrand定理2021-12-27华北电力大学华北电力大学32命题命题 描述事实

19、、事物的状态、关系等性质的文字串，取值为真或假（表示是否成立）的句子称作命题命题 命题：非真即假的简单陈述句 能判断真假 陈述句 命题用小写字母p、q、r、s等表示2021-12-27华北电力大学华北电力大学33命题例命题例 命题：能判断真假（不是既真又假）的陈述句命题：能判断真假（不是既真又假）的陈述句简单陈述句描述事实、事物的状态、关系等性质简单陈述句描述事实、事物的状态、关系等性质例如：例如： 1 1+1=2 2 雪是黑色的。雪是黑色的。 3 北京是中国的首都。北京是中国的首都。 4 到冥王星去渡假。到冥王星去渡假。 判断一个句子是否是命题，有先要看它是否是陈述句，而后看它的真判断一个句

20、子是否是命题，有先要看它是否是陈述句，而后看它的真值是否唯一。以上值是否唯一。以上4个例子都是命题。个例子都是命题。例如：例如： 1 快点走吧！快点走吧！ 2 到哪儿去？到哪儿去？ 3 x+y10 都不是命题。都不是命题。2021-12-27华北电力大学华北电力大学34命题表示公式（命题表示公式（1）将陈述句转化成命题公式。将陈述句转化成命题公式。如：设“下雨”为p，“骑车上班”为q，1“只要不下雨，我骑自行车上班”。p 是 q的充分条件，因而，可得命题公式： p q2“只有不下雨，我才骑自行车上班”。p 是 q的必要条件，因而，可得命题公式：q p 2021-12-27华北电力大学华北电力大

21、学35命题表示公式（命题表示公式（2）例如： 1 “如果我进城我就去看你，除非我很累。”设：p，我进城，q，去看你，r，我很累。则有命题公式：r (p q)。 2“应届高中生，得过数学或物理竞赛的一等 奖，保送上北京大学。” 设：p，应届高中生，q，保送上北京大学上学， r，是得过数学一等奖。t，是得过物理一等奖。 则有命题公式公式：p ( r t ) q。 2021-12-27华北电力大学华北电力大学36命题逻辑基础命题逻辑基础数理逻辑的基本定义数理逻辑的基本定义 命题逻辑基础： 定义： 合取合取式：p与q，记做p q 析取析取式： p或q，记做p q 蕴含蕴含式： 如果p则q，记做p q

22、等价等价式：p当且仅当q，记做p q。归结法的基础归结法的基础2021-12-27华北电力大学华北电力大学37命题逻辑基础命题逻辑基础数理逻辑的基本定义数理逻辑的基本定义 定义： 若A无成假赋值，则称A为重言式或永真式 若A无成真赋值，则称A为矛盾式或永假式 若A至少有一个成真赋值，则称A为可满足的 析取范式：仅由有限个简单合取式组成的析取式 合取范式：仅由有限个简单析取式组成的合取式2021-12-27华北电力大学华北电力大学38命题逻辑基础命题逻辑基础基本等值式基本等值式(1) 基本等值式基本等值式24个 交换率：pq q p ； p q q p 结合率： (pq) r p(q r); (

23、p q) r p (q r) 分配率： p(q r) (pq) (p r) ； p (q r) (p q) (p r)2021-12-27华北电力大学华北电力大学39命题逻辑基础命题逻辑基础基本等值式基本等值式(2) 摩根率: (pq) p q ； (p q) p q 吸收率: p(p q ) p ； p (pq ) p 同一律: p0 p ； p1 p 蕴含等值式:p q pq 假言易位式: p q p q2021-12-27华北电力大学华北电力大学40命题逻辑基础命题逻辑基础基本等值式基本等值式(3) 双重否定律p p 零率律p 0 p; p 1 p 书P802021-12-27华北电力大

24、学华北电力大学41命题逻辑基础命题逻辑基础-合取范式合取范式 范式范式：公式的标准形式 合取范式合取范式：单元子句、单元子句的或（）的与（） 如：P（ PQ）（ PQ） 求合取范式的步骤 求合取范式的基本原则 利用对 例：求取P (Q R) S 的合取范式1.消去对于， ， 来说冗余的连接词2.内移或消去否定号3.利用分配律2021-12-27华北电力大学华北电力大学42命题逻辑基础命题逻辑基础-合取范式合取范式 解： P (Q R) S= （P(QR) S= P(QR) S= P(QR) S= P(QR) S= PS(QR)= (PSQ) ( PSR) 注意： 将原有的命题公式整理、转换成为

25、各个“或”语句的“与”，不然后续推导没有意义 转换是基于数理逻辑的基本等值公式进行的，“或”转换到“与”中2021-12-27华北电力大学华北电力大学43命题逻辑的推理规则命题逻辑的推理规则 逻辑结论（有效结论）：AB 如AB为重言式（永真式），则称A推结论B的推理正确。B是A的逻辑结论 称AB为由前件A推结论B的推理的形式结构 可采用真值表法、等值演算法等证明逻辑结论 逻辑结论也称为假言推理或演绎推理演绎推理 重言式表示为AB2021-12-27华北电力大学华北电力大学44命题逻辑的推理规则命题逻辑的推理规则常用的推理定律常用的推理定律 附加：A（AB） 简化：（AB）A 假言推理：（AB）

26、A ）B 拒取式：（AB）B）A 析取三段论：（AB）A）B 假言三段论：（AB）（BC）AC 等价三段论：（AB）（BC）AC 构造性二难：（AB）（CD）（AC）（BD） 2021-12-27华北电力大学华北电力大学45命题逻辑的推理规则命题逻辑的推理规则常用的推理规则常用的推理规则 前提引入规则： 在证明的任何步骤上，都可以引入前提 结论引入规则： 在证明的任何步骤上，所证明的结论都可以作为后续证明的前提 置换规则： 在证明的任何步骤上，命题公式中的任何子命题都可以用与之等值的命题公式置换 例如，可以用pq置换pq2021-12-27华北电力大学华北电力大学46命题逻辑的演绎推理命题逻辑

27、的演绎推理-例例1例3.3： 构造下列推理的证明。前提 pq，pr，st，sr，t结论 q证明：st 前提引入t 前提引入s 拒取规则sr 前提引入r 假言推理pr 前提引入p 拒取规则pq 前提引入q 析取三段论2021-12-27华北电力大学华北电力大学47命题逻辑的演绎推理命题逻辑的演绎推理-例例2例3.4 写出对应下面推理的证明。如果今天是下雨天，则要带雨伞或带雨衣。如果走路上班，则不带雨衣。今天下雨，走路上班，所以带伞。解：p：今天下雨。q：带伞。r：带雨衣。s：走路上班。前提：p（qr），sr，p，s结论：q证明：p（qr）前提引入p前提引入qr假言推理sr前提引入s前提引入r假言

28、推理q析取三段论2021-12-27华北电力大学华北电力大学48命题逻辑的归结命题逻辑的归结 演绎推理：从一系列前提得出结论 上两个例子 归结方法： 新推理方法 理论基础是Herbrand定理 将待证逻辑公式的结论，通过等值公式转换成附加前提，再证明该逻辑公式不可满足 A1A2A3B是重言式 证明A1A2A3B 不可满足 建立在子句集子句集基础上2021-12-27华北电力大学华北电力大学49命题逻辑基础命题逻辑基础-子句集子句集 命题公式的子句集S是合取范式形式下的子命题（元素）的集合 子句集是合取范式中各个合取分量的集合 生成子句集的过程可以简单地理解为将命题公式的合取范式中的与符号“”，

29、置换为逗号“，” 上例的合取范式：(PSQ) ( PSR) 其子句集为S = PSQ, PSR 命题公式：P（ PQ）（PQ） 其子句集 S：S = P, PQ, PQ2021-12-27华北电力大学华北电力大学50命题逻辑的归结命题逻辑的归结 基本单元：简单命题（陈述句）例： 命题： A1、A2、A3 和 B求证： A1A2A3成立，则B成立，即：A1A2A3 B反证法：证明A1A2A3B 是矛盾式 （永假式） 2021-12-27华北电力大学华北电力大学51命题逻辑的归结命题逻辑的归结合取范式和子句集合取范式和子句集合取范式：命题、命题或的与， 如：P （ PQ） （ PQ）q 子句集S：

30、合取范式形式下的子命题（元素）的集合例：命题公式：P （ PQ） （ PQ） 子句集 S：S = P, PQ, PQ2021-12-27华北电力大学华北电力大学52命题逻辑的归结法命题逻辑的归结法归结式归结式n 归结式归结法的核心设C1和C2是子句集中的任意两个子句，如果C1中的文字L1与C2中的文字L2互补，那么可从C1和C2中分别消去L1和L2，并将C1和C2中余下的部分按析取关系构成一个新子句C12，则称这一个过程为归结，称C12为C1和C2的归结式，称C1和C2为C12的亲本子句消去互补文字，用析取连接剩余部分例如：有子句：C1PC1 ， C2PC2 ，存在互补对 P和P，则可得归结式

31、：C12 = C1C2 2021-12-27华北电力大学华北电力大学53命题逻辑的归结法命题逻辑的归结法归结式性质归结式性质 归结式性质： 归结式C12 是亲本子句C1和C2的逻辑结论 C1C2 C12 任一使C1,C2 为真的解释I下必有归结式C12为真 注意：C1C2 C12，反之不一定成立。 C1PC1 ， C2PC2 ， C12 = C1C2 因为存在一个使C1C2为真的解释I，不妨设C1为真，C2为假。若P为真，则PC2就为假了。因此反之不一定成立2021-12-27华北电力大学华北电力大学54命题逻辑的归结法命题逻辑的归结法归结过程归结过程 q建立待归结命题公式：根据反证法将所求证

32、的问题转化成为命题公式，求证其是矛盾式（永假式）q求取合取范式 q建立子句集 q归结 对子句集中的子句使用归结规则 归结式作为新子句加入子句集参加归结 归结式为空子句为止(说明子句集不可满足，即定理成立)。q归结完毕谓词归结：除有量词和函数以外，其余和命题归结一样2021-12-27华北电力大学华北电力大学55命题逻辑归结例题（命题逻辑归结例题（1） 例题，证明公式：(P Q) (Q P) 证明：（1）根据归结原理，将待证明公式转化成待归结命题公式：）根据归结原理，将待证明公式转化成待归结命题公式：(P Q) (Q P)（2）分别将公式前项化为合取范式：）分别将公式前项化为合取范式：P Q P

33、 Q结论求后的后项化为合取范式：结论求后的后项化为合取范式：(Q P) (QP) Q P两项合并后化为合取范式：两项合并后化为合取范式：（P Q）Q P（3）则子句集为：）则子句集为： PQ，Q，P2021-12-27华北电力大学华北电力大学56命题逻辑归结例题（命题逻辑归结例题（2） 子句集为： PQ，Q，P（4）对子句集中的子句进行归结可得：1. PQ2. Q3. P4. Q，（1，3归结）5. ，（2，4归结）由上可得原公式成立。2021-12-27华北电力大学华北电力大学57第三章谓词逻辑与归结原理第三章谓词逻辑与归结原理 概述 命题逻辑的归结法 谓词逻辑归结基础 归结原理 归结过程的

34、控制策略 Herbrand定理2021-12-27华北电力大学华北电力大学58第三章谓词逻辑与归结原理第三章谓词逻辑与归结原理 概述 命题逻辑的归结法 谓词逻辑归结基础 归结原理 归结过程的控制策略 Herbrand定理2021-12-27华北电力大学华北电力大学59谓词逻辑归结基础谓词逻辑归结基础基本概念基本概念一阶逻辑逻辑的基本定义 基本概念 个体词：表示主语的词 个体常量：具体的或特定的个体 个体变量：抽象的或泛指的个体 谓词：刻画个体性质或个体之间关系的词 谓词常量：具体性质或关系的谓词 谓词变量：抽象或泛指的谓词 量词：表示数量的词 量词符号：全称、存在量词2021-12-27华北电

35、力大学华北电力大学60谓词逻辑归结基础谓词逻辑归结基础基本概念基本概念-例例小王是个工程师。小王是个工程师。8是个自然数。是个自然数。我去买花。我去买花。小丽和小华是朋友。小丽和小华是朋友。 个体词：“小王”、“工程师”、“我”、“花”、“8”、“小丽”、“小华” 谓词：“是个工程师”、“是个自然数”、“去买”、“是朋友”都是谓词 前两个谓词表示的是事物的性质 第三个谓词“去买”表示的一个动作也表示了主、宾两个个体词的关系 最后一个谓词“是朋友”表示两个个体词之间的关系2021-12-27华北电力大学华北电力大学61谓词逻辑归结基础谓词逻辑归结基础基本概念基本概念 一阶逻辑逻辑：以谓词的形式来

36、表示动作的主体、客体 公式及其解释 个体常量：a,b,c 个体变量：x,y,z 谓词常量：P,Q,R 谓词变量： P(x),Q(x,y),R(x,b) 量词符号： , xP(x) ,xP(x)2021-12-27华北电力大学华北电力大学62谓词逻辑归结基础谓词逻辑归结基础基本概念基本概念原子公式：设P(x1,x2,xn)是任意n元谓词，t1，t2，tn是项，则P(t1,t2,tn)为原子公式谓词公式谓词公式：q 原子公式是谓词公式q 若A是谓词公式，则(A)也是谓词公式q 若A、B是谓词公式，则(AB)、(AB)、(AB)、(AB)也是谓词公式q 若A是谓词公式，则xA ,xA也是谓词公式 只

37、有有限次的应用构成的符号串才是谓词公式2021-12-27华北电力大学华北电力大学63谓词逻辑归结基础谓词逻辑归结基础基本概念基本概念 指导变量： xA ,xA中的x为指导变量 辖域： xA ,xA中的A成为相应量词的辖域 约束出现： 在辖域（A）中，x的所有出现称为约束出现 自由出现： 在辖域（A）中，不是约束出现的其他变量的出现，称为自由出现2021-12-27华北电力大学华北电力大学64谓词逻辑归结基础谓词逻辑归结基础基本概念基本概念-例例例如： （1）所有的人都是要死的。 （2） 有的人活到一百岁以上。在个体域D为人类集合时，可符号化为：（1）xP(x)，其中P(x)表示x是要死的。（

38、2）x Q(x), 其中Q(x)表示x活到一百岁以上。在个体域D是全总个体域时，引入特殊谓词R(x)表示x是人，可符号化为：（1）x（R(x) P(x)）,其中，R(x)表示x是人；P(x)表示x是要死的。（2）x（R(x) Q(x)）其中，R(x)表示x是人；Q(x)表示x活到一百岁以上。2021-12-27华北电力大学华北电力大学65谓词逻辑归结基础谓词逻辑归结基础谓词公式等值式谓词公式等值式量词否定等值式： ( x ） M（x） （ y ） M（y） ( x ） M（x） （ y ） M（y）量词分配等值式分配等值式： ( x ）( P（x） Q（x）) ( x ） P（x） ( x ）

39、 Q（x） ( x ）( P（x） Q（x）) ( x ） P（x） ( x ） Q（x）消去量词等值式：设个体域为有穷集合（a1, a2, an） ( x ） P（x） P（ a1 ） P（ a2 ） P（ an ） ( x ）P（x） P（ a1 ） P（ a2 ） P（ an ）2021-12-27华北电力大学华北电力大学66谓词逻辑归结基础谓词逻辑归结基础谓词公式等值式谓词公式等值式量词辖域收缩与扩张等值式： ( x ）( P（x） Q) ( x ） P（x） Q ( x ）( P（x） Q) ( x ） P（x） Q ( x ）( P（x） Q) ( x ） P（x） Q ( x ）

40、(Q P（x） ) Q ( x ） P（x） ( x ）( P（x） Q) ( x ） P（x） Q ( x ）( P（x） Q) ( x ） P（x） Q ( x ）( P（x） Q) ( x ） P（x） Q ( x ）(Q P（x） ) Q ( x ） P（x）2021-12-27华北电力大学华北电力大学67Skolem 标准型标准型前束范式前束范式 SKolem标准型是在前束范式的基础上进行变量映射的 前束范式定义：说公式A是一个前束范式，如果A中的一切量词都位于该公式的最左边（不含否定词），且这些量词的辖域都延伸到公式的末端。 (Q1x1)(Q2x2)(Qnxn)M(x1,x2,xn

41、) 将量词提到公式最前端时存在约束变量换名问题。要严守约束变元的换名规则 (Qx ) M（x） （Qy ） M（y） (Qx ) M（x,z） （Qy ） M（y,z） 例题Qi：量词，：量词，M：母式：母式2021-12-27华北电力大学华北电力大学68例例( w)P(w)( x)( y)( z)(P(x,y,z)( u)R(x,y,z,u)( w)P(w)( x)( y)( z)(P(x,y,z)( u)R(x,y,z,u)( w)( x)( y)( z)( u)(P(w)P(x,y,z)R(x,y,z,u)2021-12-27华北电力大学华北电力大学69Skolem 标准型标准型 前束范

42、式中消去所有的量词，则称这种形式的谓词公式为Skolem标准型 Skolem标准型必须满足合取范式的条件 任何一个谓词公式都可以化成与之对应的Skolem标准型。但Skolem标准型不唯一2021-12-27华北电力大学华北电力大学70Skolem 标准型标准型转化过程转化过程n将谓词公式G转换成为前束范式n消去量词量词消去原则： 消去存在量词“” 如果存在量词左边没有任何全称量词，则只将其改写成为常量（a, b等） 如果是左边有全称量词的存在量词，消去时该变量改写成为全称量词的函数(f(x), g(y)等) 略去全称量词“”，简单地省略掉该量词2021-12-27华北电力大学华北电力大学71

43、Skolem 标准型标准型例例将下式化为Skolem标准型：(x)(y)P(a, x, y) (x)(y)Q(y, b)R(x)解：第一步，消去号，得：(x)(y)P(a, x, y) (x) (y)Q(y, b)R(x)第二步，深入到量词内部，得： (x)(y)P(a, x, y) (x) (y)Q(y, b)R(x) = (x)(y)P(a, x, y) (x) (y) Q(y, b) R(x)第三步，任意量词左移，利用分配律，得到 (x)(y)P(a, x, y)(y)(Q(y, b)R(x)第四步，变元易名，存在量词左移，直至所有的量词移到前面，得： (x)(y)P(a, x, y)(

44、y)(Q(y, b)R(x) =(x)(y)P(a, x, y)(z)(Q(z, b)R(x) =(x)(y) (z)(P(a, x, y)(Q(z, b)R(x) 由此得到前述范式2021-12-27华北电力大学华北电力大学72Skolem 标准型标准型例例上页：(x)(y) (z)(P(a, x, y)(Q(z, b)R(x)第五步，消去“”，略去“”消去(y)，因为它左边只有(x)，所以使用x的函数f(x)代替之，这样得到：(x)(z)( P(a, x, f(x) Q(z, b)R(x)消去(z)，同理使用g(x)代替之，这样得到：(x) ( P(a, x, f(x) Q(g(x), b

45、)R(x)略去全称变量，原式的Skolem标准型为： P(a, x, f(x) Q(g(x), b)R(x) 例2： (x)p(x)(x)Q(x)(x)(p(x) Q(x)2021-12-27华北电力大学华北电力大学73Skolem定理定理 SKOLEM标准型定义：消去量词后的前束范式 Skolem定理：谓词逻辑的任意公式都可以化为与之等价的前束范式，但其前束范式不唯一注意： 谓词公式G的SKOLEM标准型同G并不等值例如有谓词公式G= (x)p(x)，其skolem标准型G=P(a) 解释I：个体域DI=0,1,常数a=0，谓词P(x)为P(0)=F，P(1)=T，则在解释I下G=T,G=F

46、 2021-12-27华北电力大学华北电力大学74子句集子句集定义定义 子句与子句集 文字：不含任何连接词的谓词公式 子句：一些文字的析取（谓词的和） 空子句：不含任何文字的子句， 子句集：所有子句的集合 对于任一个公式G，都可以通过Skolem标准型，标准化建立起一个子句集与之相对应 2021-12-27华北电力大学华北电力大学75子句集子句集求取步骤求取步骤 子句集S的求取：通过Skolem标准型求取 G 前束范式 消去量词生成Skolem标准型 将Skolem标准型中的子句提出，表 示为集合形式 ，即以“，”取代”， 并表示为集合形式 注意 Skolem标准型必须满足合取范式的条件202

47、1-12-27华北电力大学华北电力大学76子句集与谓词公式的不可满足性子句集与谓词公式的不可满足性 G是不可满足的 S是不可满足的 G与S不等价，但在不可满足的意义下是一致的 定理3.1：若G是给定的公式，而S是相应的子句集，则G是不可满足的，当且仅当S是不可满足的。 注意：G真不一定S真，而S真必有G真即： S = G2021-12-27华北电力大学华北电力大学77子句集与谓词公式的不可满足性子句集与谓词公式的不可满足性定理定理3.1的推广的推广 谓词公式G = G1G2G3Gn，G的子句集S的求取可以分解成几个部分单独处理。如果Gi的子句集为Si，则有： S = S1S2S3Sn。 虽然G

48、的子句集不为S，但是可以证明：SG与S 在不可满足的意义上是一致的。 即SG不可满足 S1S2S3Sn不可满足2021-12-27华北电力大学华北电力大学78求取子句集例求取子句集例(1)例：对所有的x,y,z来说，如果y是x的父亲，z又是y的父亲，则z是x的祖父。又知每个人都有父亲，试问对某个人来说谁是它的祖父？求：用一阶逻辑表示这个问题，并建立子句集。解：这里我们首先引入谓词：P(x, y) 表示x是y的父亲Q(x, y) 表示x是y的祖父ANS(x) 表示问题的解答2021-12-27华北电力大学华北电力大学79求取子句集例求取子句集例(2)对于第一个条件，“如果x是y 的父亲， y又是

49、z 的父亲，则x是z 的祖父”，一阶逻辑表达式如下：A1：(x)(y)(z)(P(x, y)P(y, z)Q(x, z)S A1：P(x ,y)P(y, z)Q(x, z)对于第二个条件：“每个人都有父亲”，一阶逻辑表达式：A2：(y)(x)P(x, y)S A2：P(f(y), y)对于结论：某个人是他的祖父B：(x)(y)Q(x, y)否定后得到子句： (x)(y)Q(x, y) ANS(x)SB：Q(x, y)ANS(x)则得到的相应的子句集为： S A1，S A2，SB 2021-12-27华北电力大学华北电力大学80第三章谓词逻辑与归结原理第三章谓词逻辑与归结原理 概述 命题逻辑的归

50、结法 谓词逻辑归结基础 归结原理 归结过程的控制策略 Herbrand定理2021-12-27华北电力大学华北电力大学81第三章谓词逻辑与归结原理第三章谓词逻辑与归结原理 概述 命题逻辑的归结法 谓词逻辑归结基础 归结原理 归结过程的控制策略 Herbrand定理2021-12-27华北电力大学华北电力大学82归结原理归结原理 归结原理正确性的根本在于，如果在子句集中找到矛盾可以肯定命题是不可满足的（不真） 方法： 和命题逻辑一样 但由于有函数，所以要考虑合一和置换 2021-12-27华北电力大学华北电力大学83置换置换 置换：在一个谓词公式中用置换项去置换变量 定义：置换是形如t1/x1,

51、 t2/x2, , tn/xn的有限集合。其中，x1, x2, , xn是互不相同的变量，t1, t2, , tn是不同于xi的项（常量、变量、函数）；ti/xi表示用ti置换xi，并且要求ti与xi不能相同，而且xi不能循环地出现在另一个ti中。例如a/x，c/y，f(b)/z是一个置换g(y)/x，f(x)/y不是一个置换2021-12-27华北电力大学华北电力大学84置换置换 定义： 设是一个置换，E是一个表达式，把对E施行置换 ，即把E中出现的个体变元xi用ti替换，记为E例： =a/x,f(b)/y,c/z,G=P(x,y,z),求G G =P(a,f(b),c)2021-12-27

52、华北电力大学华北电力大学85置换的合成置换的合成 设t1/x1, t2/x2, , tn/xn， u1/y1, u2/y2, , um/ym，是两个置换。 则与的合成也是一个置换，记作。它是从集合t1/x1, t2/x2, , tn/xn, u1/y1, u2/y2, , um/ym 中删去以下两种元素： 当ti=xi时，删去ti/xi (i = 1, 2, , n) 当yix1,x2, , xn时，删去uj/yj (j = 1, 2, , m)最后剩下的元素所构成的集合合成即是对ti先做置换然后再做置换，置换xi2021-12-27华北电力大学华北电力大学86置换的合成置换的合成例：设：f(

53、y)/x, z/y，a/x, b/y, y/z，求与的合成解：先求出集合f(b/y)/x, (y/z)/y, a/x, b/y, y/zf(b)/x, y/y, a/x, b/y, y/z其中，f(b)/x中的f(b)是置换作用于f(y)的结果；y/y中的y是置换作用于z的结果。 在该集合中，y/y满足定义中的条件i，需要删除；a/x，b/y满足定义中的条件ii，也需要删除。 最后得f(b)/x，y/z2021-12-27华北电力大学华北电力大学87合一合一 合一可以简单地理解为“寻找相对变量的置换，使两个谓词公式一致”定义： 设有公式集FF1，F2，Fn，若存在一个置换，可使F1F2= Fn

54、，则称是F的一个合一。同时称F1，F2，. ，Fn是可合一的2021-12-27华北电力大学华北电力大学88合一合一例子例子例：设有公式集FP(x, y, f(y), P(a,g(x),z)，则a/x, g(a)/y, f(g(a)/z是它的一个合一。 注意：一般说来，一个公式集的合一不是唯一的注意：一般说来，一个公式集的合一不是唯一的2021-12-27华北电力大学华北电力大学89最一般合一最一般合一 定义定义：最一般合一设是公式集F的一个合一，如果对F的任意一个合一都存在一个置换，使得，则称是一个最一般合一（Most General Unifier，简记为mgu）2021-12-27华北电

55、力大学华北电力大学90最一般合一最一般合一 一个公式集的最一般合一是唯一的一个公式集的最一般合一是唯一的 若用最一般合一去置换那些可合一的谓词公式，可使它们变成完全一致的谓词公式（用途） mgu的求取方法 对于给定谓词公式F1和F2，采用逐一比较找出不一致，并作出相应的合一置换，可求得mgu2021-12-27华北电力大学华北电力大学91mgu求取方法求取方法n令w=F1,F2n令k=0，w0=w，0=n如果wk已合一，停止，k=mgu，否则，找不一致集Dkn若Dk中存在元素vk和tk，其中vk不出现于tk中，转5，否则，不可合一n令k+1=ktk/vk, wk+1= wktk/vk=wk+1

56、nk=k+1,转3若F1和F2可合一，算法必停止与32021-12-27华北电力大学华北电力大学92mgu的例子的例子 例：W=P(a,x,f(g(y),P(z,f(a),f(u), 其中F1=P(a,x,f(g(y),F2=P(z,f(a),f(u) 求F1和F2的最一般合一。2021-12-27华北电力大学华北电力大学93mgu的例子的例子2021-12-27华北电力大学华北电力大学94mgu的例子的例子2021-12-27华北电力大学华北电力大学95归结式归结式 和命题逻辑一样消去互补对，但要考虑变量的合一与置换 设C1、C2是两个无公共变量的子句，L1和L2分别是C1和C2的文字，如果

57、L1、L2有最一般合一，则 R=（ C1 - L1 ）（ C2 - L2 ） 称作子句C1、C2的一个二元归结式，而L1和L2为被归结的文字 例子2021-12-27华北电力大学华北电力大学96n P(x)Q(x,y)与与P(a)R(b,z)的归结式的归结式n Q(a,y)R(b,z) =a/xn P(x,y)Q(x)R(x)与与P(a,z)Q(b)的归结式的归结式 Q(a)R(a)Q(b) =a/x,y/z P(b,y)R(b)P(a,z) =b/x归结式归结式-例例2021-12-27华北电力大学华北电力大学97归结原理归结原理归结的注意事项归结的注意事项n谓词的一致性，P()与Q()，

58、不可以n常量的一致性，P(a, )与 P(b, .)， 不可以；变量，P(a, .)与P(x, )， 可以n变量与函数， P(x, x, .)与P(x, f(x), )，不可以； P(x, x, .)与P(x, f(y), )，可以；n不能同时消去两个互补对，PQ与PQ得空，不可以n先进行内部简化（置换、合并） 例子2021-12-27华北电力大学华北电力大学98归结原理归结原理归结的过程归结的过程 归结的过程写出谓词关系公式 用反演法写出谓词表达式 SKOLEM标准型 子句集S 对S中可归结的子句做归结 归结式仍放入S中，反复归结过程 得到空子句 得证2021-12-27华北电力大学华北电力

59、大学99例题例题“快乐学生快乐学生”问题问题 假设任何通过计算机考试并获奖的人都是快乐的，任何肯学习或幸运的假设任何通过计算机考试并获奖的人都是快乐的，任何肯学习或幸运的人都可以通过所有的考试，张不肯学习但他是幸运的，任何幸运的人都人都可以通过所有的考试，张不肯学习但他是幸运的，任何幸运的人都能获奖。求证：张是快乐的。能获奖。求证：张是快乐的。证明：先将问题用谓词表示如下：证明：先将问题用谓词表示如下：R1:“任何通过计算机考试并获奖的人都是快乐的任何通过计算机考试并获奖的人都是快乐的”( x)(Pass(x, computer)Win(x, prize)Happy(x)R2:“任何肯学习或幸

60、运的人都可以通过所有考试任何肯学习或幸运的人都可以通过所有考试”( x)( y)(Study(x)Lucky(x)Pass(x, y)R3:“张不肯学习但他是幸运的张不肯学习但他是幸运的”Study(zhang)Lucky(zhang)R4:“任何幸运的人都能获奖任何幸运的人都能获奖”( x)(Luck(x)Win(x,prize)结论：结论：“张是快乐的张是快乐的”的否定的否定Happy(zhang)2021-12-27华北电力大学华北电力大学100例题例题“快乐学生快乐学生”问题问题由R1及逻辑转换公式:PWH = （PW） H ，可得 (1)Pass(x, computer)Win(x,