第三章-王士同版.ppt

《第三章-王士同版.ppt》由会员分享，可在线阅读，更多相关《第三章-王士同版.ppt（127页珍藏版）》请在三一文库上搜索。

1、2019/3/12,1,第三章 谓词逻辑与归结原理,华北电力大学 计算机系 刘丽,2019/3/12,2,第三章 谓词逻辑与归结原理,归结原理概述 命题逻辑的归结法 谓词逻辑归结基础 归结原理 归结过程的控制策略,2019/3/12,3,2019/3/12,4,第三章 谓词逻辑与归结原理,归结原理概述 命题逻辑的归结法 谓词逻辑归结基础 归结原理 归结过程的控制策略,2019/3/12,5,概述-推理技术,确定知识表达方法将知识表示出来并存储到计算机中利用知识来解决实际问题 利用知识进行推理是知识利用的基础；是问题求解的主要手段 如专家系统、智能机器人、模式识别、自然语言理解等 推理 按照某种

2、策略从已有事实和知识推出结论的过程。推理是由程序实现的，称为推理机 医疗诊断专家系统 知识库中存储经验及医学常识 数据库中存放病人的症状、化验结果等初始事实 利用知识库中的知识及一定的控制策略，为病人诊治疾病、开出医疗处方就是推理过程,2019/3/12,6,概述,推理的分类 演绎推理、归纳推理、默认推理 确定性推理、不精确推理 单调推理、非单调推理 启发式推理、非启发式推理,2019/3/12,7,概述,从推出新判断的途径分演绎、归纳和默认推理 演绎推理 从全称判断推出特称判断或单称判断的过程，即从一般到个别的推理 演绎推理中最常用的形式是三段论法（大前提和小前提，及结论） 例如： 所有的推

3、理系统都是智能系统一般的知识 专家系统是推理系统个体的判断 所以，专家系统是智能系统新判断 没有增加新的知识,2019/3/12,8,概述-演绎推理、归纳推理和默认推理,归纳推理 从足够多的事例中归纳出一般性结论的推理过程，是一种从个别到一般的推理过程 常用的归纳推理有简单枚举法和类比法 枚举法归纳推理是由已观察到的事物都有某属性，而没有观察到相反的事例，从而推出某类事物都有某属性，推理过程为： S1 是 P S2 是 P Sn 是 P (S1,S2, Sn 是S 类中的个别事物，在枚举中兼容) S 都是 P,2019/3/12,9,概述-演绎推理、归纳推理和默认推理,归纳推理之枚举法 枚举法

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

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

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

7、3/12,14,概述,按推理中是否运用与问题有关的启发性知识分 启发式推理 推理过程中，运用与问题有关的启发性知识，以加快推理过程，提高搜索效率 A*、AO*等算法就属于此类推理 非启发式推理 推理过程中，不运用启发性知识，只按照一般的控制逻辑进行推理 这种方法缺乏对求解问题的针对性，所以推理效率较低，容易出现“组合爆炸”问题，如宽度优先搜索法,2019/3/12,15,概述,推理的控制策略 主要是指推理方向的选择、推理时所用的搜索策略及冲突解决策略等 一般推理的控制策略与知识表达方法有关 推理方向 推理方向用于确定推理的驱动方式 根据推理方向的不同，可将推理分为正向推理、反向推理和正反向混合

8、推理 无论按哪种方式进行推理，一般都要求系统具有一个存放知识的知识库（KB）、一个存放初始事实和中间结果的数据库（DB）和一个用于推理的推理机,2019/3/12,16,概述-推理的控制策略,推理方向 正向推理（事实驱动推理）是由已知事实出发向结论方向的推理,2019/3/12,17,概述-推理的控制策略,推理方向 反向推理以某个假设目标作为出发点的一种推理，又称为目标驱动推理或逆向推理,2019/3/12,18,概述-推理的控制策略,推理方向 正反混合推理,2019/3/12,19,概述-推理的控制策略,搜索策略 推理时，要反复用到知识库中的规则，而知识库中的规则又很多，这样就存在着如何在知

9、识库中寻找可用规则的问题 为有效控制规则的选取，可以采用各种搜索策略 常用搜索策略： 状态空间搜索（宽度优先搜索、深度优先搜索、有界深度优先搜索等） 启发式搜索等（第三章）,2019/3/12,20,概述-推理的控制策略,冲突解决策略 推理过程中，系统要不断地用数据库中的事实与知识库中的规则进行匹配，当有一个以上规则的条件部分和当前数据库相匹配时，就需要有一种策略来决定首先使用哪一条规则，这就是冲突解决策略 冲突解决策略实际上就是确定规则的启用顺序,2019/3/12,21,概述-推理的控制策略,推理的控制策略 冲突解决策略 (1) 专一性排序 如果某一规则的条件部分规定的情况比另一规则的条件

10、部分所规定的情况更专门，则这条规则具有较高的优先级 例，有如下规则： 规则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都与数据库相匹配，但因为规则2的条件部分包括了更多的限制，所以具有较高的优先级 本策略是优先使用针对性较强的产生式规则,2019/3/12,22,概述-推理的控制策略,推理的控制策略 3冲突解决策略 (2) 规则排序 规则编排的顺序就表示了启用的优先级 (3) 数据排序 数据排序就是把规则条件部分的所有条件排序，按优先级次序编排，发生冲突时，首先使用在

11、条件部分包含较高优先级数据的规则 (4) 就近排序 把最近使用的规则放在最优先的位置。如果某一规则经常使用，则倾向于更多地使用这条规则 (5) 上下文限制 上下文限制就是把产生式规则按它们所描述的上下文分组，在某种上下文条件下，只能从与其相对应的那组规则中选择可应用的规则,2019/3/12,23,概述-推理的控制策略,推理的控制策略 3冲突解决策略 (6) 按匹配度排序 在不精确匹配中，为了确定两个知识模式是否可以进行匹配，需要计算这两个模式的相似程度，当其相似度达到某个预先规定的值时，就认为它们是可匹配的。若有几条规则均可匹配成功，则可根据它们的匹配度来决定哪一个产生式规则可优先被应用 (

12、7) 按条件个数排序 如果有多条产生式规则生成的结论相同，则要求条件少的产生式规则被优先应用，因为要求条件少的规则匹配时花费的时间较少 不同的系统，可使用上述这些策略的不同组合,2019/3/12,24,概述,归结原理由J.A.Robinson于1965年提出 定理证明的实质 要对给出的（已知的）前提和结论，证明此前提推导出该结论这一事实是永恒的真理 非常困难的，几乎是不可实现的 要证明在一个论域上一个事件是永真的： 就要证明在该域中的每一个点上该事实都成立 论域是不可数时，该问题不可能解决 即使可数，如果该轮域是无限的，问题也无法简单地解决,2019/3/12,25,概述,理论基础： Her

13、brand采用反证法的思想，将永真性的证明问题转化成为不可满足性的证明问题 实现方法： Robinson的归结原理使得自动定理证明得以实现 归结推理方法是机器定理证明的主要方法,2019/3/12,26,归结法的特点,归结法是一阶逻辑中，至今为止的最有效的半可判定的算法。也是最适合计算机进行推理的逻辑演算方法 半可判定 一阶逻辑中任意恒真公式，使用归结原理，总可以在有限步内给以判定（证明其为永真式） 当不知道该公式是否为恒真时，使用归结原理不能得到任何结论,2019/3/12,27,归结法基本原理,采用反证法(反演推理方法) 将待证明的表达式（定理）转换成为逻辑公式（谓词公式） 然后再进行归结

14、 归结能够顺利完成，则证明原公式（定理）是正确的,2019/3/12,28,归结法基本原理例,例：由命题逻辑描述的命题：A1、A2、A3和B，要求证明： 如果A1A2A3成立，则B成立，即：A1A2A3B是重言式（永真式） 归结法的思路 A1A2A3B是重言式等价于A1A2A3B是矛盾式，也就是永假式 反证法：证明A1A2A3B 是矛盾式（永假式）,2019/3/12,29,第三章谓词逻辑与归结原理,概述 命题逻辑的归结法 谓词逻辑归结基础 归结原理 归结过程的控制策略 Herbrand定理,2019/3/12,30,第三章谓词逻辑与归结原理,概述 命题逻辑的归结法 谓词逻辑归结基础 归结原理

15、 归结过程的控制策略 Herbrand定理,2019/3/12,31,命题,描述事实、事物的状态、关系等性质的文字串，取值为真或假（表示是否成立）的句子称作命题 命题：非真即假的简单陈述句 能判断真假 陈述句 命题用小写字母p、q、r、s等表示,2019/3/12,32,命题例,命题：能判断真假（不是既真又假）的陈述句 简单陈述句描述事实、事物的状态、关系等性质 例如： 1 1+1=2 2 雪是黑色的。 3 北京是中国的首都。 4 到冥王星去渡假。 判断一个句子是否是命题，有先要看它是否是陈述句，而后看它的真值是否唯一。以上4个例子都是命题。 例如： 1 快点走吧！ 2 到哪儿去？ 3 x+y

16、10 都不是命题。,2019/3/12,33,命题表示公式（1）,将陈述句转化成命题公式。 如：设“下雨”为p，“骑车上班”为q， 1“只要不下雨，我骑自行车上班”。p 是 q的充分条件，因而，可得命题公式： p q 2“只有不下雨，我才骑自行车上班”。p 是 q的必要条件，因而，可得命题公式：q p,2019/3/12,34,命题表示公式（2）,例如： 1 “如果我进城我就去看你，除非我很累。” 设：p，我进城，q，去看你，r，我很累。 则有命题公式：r (p q)。 2“应届高中生，得过数学或物理竞赛的一等 奖， 保送上北京大学。” 设：p，应届高中生，q，保送上北京大学上学， r，是得过

17、数学一等奖。t，是得过物理一等奖。 则有命题公式公式：p ( r t ) q。,2019/3/12,35,命题逻辑基础数理逻辑的基本定义,命题逻辑基础： 定义： 合取式：p与q，记做p q 析取式： p或q，记做p q 蕴含式： 如果p则q，记做p q 等价式：p当且仅当q，记做p q 。,归结法的基础,2019/3/12,36,命题逻辑基础数理逻辑的基本定义,定义： 若A无成假赋值，则称A为重言式或永真式 若A无成真赋值，则称A为矛盾式或永假式 若A至少有一个成真赋值，则称A为可满足的 析取范式：仅由有限个简单合取式组成的析取式 合取范式：仅由有限个简单析取式组成的合取式,2019/3/12

18、,37,命题逻辑基础基本等值式(1),基本等值式24个 交换率：pq q p ； p q q p 结合率： (pq) r p(q r); (p q) r p (q r) 分配率： p(q r) (pq) (p r) ； p (q r) (p q) (p r),2019/3/12,38,命题逻辑基础基本等值式(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 q,2019/3/12,39,命题逻辑基础基本等值式(3),双重否定律p p 零率律p 0

19、p; p 1 p 书P80,2019/3/12,40,命题逻辑基础-合取范式,范式：公式的标准形式 合取范式：单元子句、单元子句的或（）的与（） 如：P（ PQ）（ PQ） 求合取范式的步骤 求合取范式的基本原则 利用对的分配律 例：求取P (Q R) S 的合取范式,1.消去对于， ， 来说冗余的连接词 2.内移或消去否定号 3.利用分配律,2019/3/12,41,命题逻辑基础-合取范式,解： P (Q R) S = （P(QR) S = P(QR) S = P(QR) S = P(QR) S = PS(QR) = (PSQ) ( PSR) 注意： 将原有的命题公式整理、转换成为各个“或”

20、语句的“与”，否则后续推导没有意义 转换基于数理逻辑的基本等值公式，“或”转换到“与”中,2019/3/12,42,命题逻辑的推理规则,逻辑结论（有效结论）：AB 如AB为重言式（永真式），则称A推结论B的推理正确。B是A的逻辑结论 称AB为由前件A推结论B的推理的形式结构 可采用真值表法、等值演算法等证明逻辑结论 逻辑结论也称为假言推理或演绎推理 重言式表示为AB,2019/3/12,43,命题逻辑的推理规则常用的推理定律,附加：A（AB） 简化：（AB）A 假言推理：（AB）A ）B 拒取式：（AB）B）A 析取三段论：（AB）A）B 假言三段论：（AB）（BC）AC 等价三段论：（AB）

21、（BC）AC 构造性二难：（AB）（CD）（AC）（BD）,2019/3/12,44,命题逻辑的推理规则常用的推理规则,前提引入规则： 在证明的任何步骤上，都可以引入前提 结论引入规则： 在证明的任何步骤上，所证明的结论都可以作为后续证明的前提 置换规则： 在证明的任何步骤上，命题公式中的任何子命题都可以用与之等值的命题公式置换 例如，可以用pq置换pq,2019/3/12,45,命题逻辑的演绎推理-例1,例3.3： 构造下列推理的证明。 前提 pq，pr，st，sr，t 结论 q 证明： st 前提引入 t 前提引入 s 拒取规则（AB）B）A sr 前提引入 r 假言推理（AB）（BC）A

22、C pr 前提引入 p 拒取规则 pq 前提引入 q 析取三段论（AB）A）B,2019/3/12,46,命题逻辑的演绎推理-例2,例3.4 写出对应下面推理的证明。 如果今天是下雨天，则要带雨伞或带雨衣。如果走路上班，则不带雨衣。今天下雨，走路上班，所以带伞。 解：p：今天下雨。q：带伞。r：带雨衣。s：走路上班。 前提：p（qr），sr，p，s 结论：q 证明： p（qr） 前提引入 p 前提引入 qr 假言推理 sr 前提引入 s 前提引入 r 假言推理 q 析取三段论,2019/3/12,47,命题逻辑的归结,演绎推理：从一系列前提得出结论 上两个例子 归结方法： 新推理方法 理论基础

23、是Herbrand定理 将待证逻辑公式的结论，通过等值公式转换成附加前提，再证明该逻辑公式不可满足 A1A2A3B是重言式 证明A1A2A3B 不可满足 建立在子句集基础上,2019/3/12,48,命题逻辑基础-子句集,命题公式的子句集S 合取范式形式下的子命题（元素）的集合 是合取范式中各个合取分量的集合 生成子句集的过程简单地理解为 将命题公式合取范式中的与“”，置换为逗号“，” 上例的合取范式：(PSQ) ( PSR) 其子句集为 S = PSQ, PSR 命题公式：P（ PQ）（PQ） 其子句集 S：S = P, PQ, PQ,2019/3/12,49,命题逻辑的归结,基本单元：简单

24、命题（陈述句） 例： 命题： A1、A2、A3 和 B 求证： A1A2A3成立，则B成立， 即：A1A2A3 B 反证法：证明A1A2A3B 是矛盾式 （永假式）,2019/3/12,50,命题逻辑的归结合取范式和子句集,合取范式：命题、命题或的与， 如： P （ PQ） （ PQ） 子句集S：合取范式形式下的子命题（元素）的集合 例：命题公式：P （ PQ） （ PQ） 子句集 S：S = P, PQ, PQ,2019/3/12,51,命题逻辑的归结法归结式,归结式归结法的核心 设C1和C2是子句集中的任意两个子句，如果C1中的文字L1与C2中的文字L2互补，那么可从C1和C2中分别消去L

25、1和L2，并将C1和C2中余下的部分按析取关系构成一个新子句C12，则称这一个过程为归结，称C12为C1和C2的归结式，称C1和C2为C12的亲本子句 消去互补文字，用析取连接剩余部分 例如：有子句：C1PC1 ， C2PC2 ，存在互补对 P和P，则可得归结式：C12 = C1C2,2019/3/12,52,命题逻辑的归结法归结式性质,归结式性质： 归结式C12 是亲本子句C1和C2的逻辑结论 C1C2 C12 任一使C1,C2 为真的解释I下必有归结式C12为真 注意：C1C2 C12，反之不一定成立。 C1PC1 ， C2PC2 ， C12 = C1C2 因为存在一个使C1C2为真的解释

26、I，不妨设C1为真，C2为假。若P为真，则PC2就为假了。因此反之不一定成立,2019/3/12,53,命题逻辑的归结法归结过程,建立待归结命题公式：根据反证法将所求证的问题转化成为命题公式，求证其是矛盾式（永假式） 求取合取范式 建立子句集 归结 对子句集中的子句使用归结规则 归结式作为新子句加入子句集参加归结 归结式为空子句为止(说明子句集不可满足，即定理成立)。 归结完毕 谓词归结：除有量词和函数以外，其余和命题归结一样,2019/3/12,54,命题逻辑归结例题（1）,例题，证明公式：(P Q) (Q P) 证明： （1）根据归结原理，将待证明公式转化成待归结命题公式： (P Q) (

27、Q P) （2）分别将公式前项化为合取范式： P Q P Q 结论求后的后项化为合取范式： (Q P) (QP) Q P 两项合并后化为合取范式： （P Q）Q P （3）则子句集为： PQ，Q，P,2019/3/12,55,命题逻辑归结例题（2）,子句集为： PQ，Q，P （4）对子句集中的子句进行归结可得： 1. PQ 2. Q 3. P 4. Q， （1，3归结） 5. ， （2，4归结） 由上可得原公式成立。,2019/3/12,56,第三章谓词逻辑与归结原理,概述 命题逻辑的归结法 谓词逻辑归结基础 归结原理 归结过程的控制策略 Herbrand定理,2019/3/12,57,第三章

28、谓词逻辑与归结原理,概述 命题逻辑的归结法 谓词逻辑归结基础 归结原理 归结过程的控制策略 Herbrand定理,2019/3/12,58,谓词逻辑归结基础基本概念,一阶逻辑逻辑的基本定义 基本概念 个体词：表示主语的词 个体常量：具体的或特定的个体 个体变量：抽象的或泛指的个体 谓词：刻画个体性质或个体之间关系的词 谓词常量：具体性质或关系的谓词 谓词变量：抽象或泛指的谓词 量词：表示数量的词 量词符号：全称、存在量词,2019/3/12,59,谓词逻辑归结基础基本概念-例,小王是个工程师。 8是个自然数。 我去买花。 小丽和小华是朋友。 个体词：“小王”、“工程师”、“我”、“花”、“8”

29、、“小丽”、“小华” 谓词：“是个工程师”、“是个自然数”、“去买”、“是朋友”都是谓词 前两个谓词表示的是事物的性质 第三个谓词“去买”表示的一个动作也表示了主、宾两个个体词的关系 最后一个谓词“是朋友”表示两个个体词之间的关系,2019/3/12,60,谓词逻辑归结基础基本概念,一阶逻辑逻辑：以谓词的形式来表示动作的主体、客体 公式及其解释 个体常量：a,b,c 个体变量：x,y,z 谓词常量：P,Q,R 谓词变量： P(x),Q(x,y),R(x,b) 量词符号： , xP(x) ,xP(x),2019/3/12,61,谓词逻辑归结基础基本概念,原子公式：设P(x1,x2,xn)是任意n

30、元谓词，t1，t2，tn是项，则P(t1,t2,tn)为原子公式 谓词公式： 原子公式是谓词公式 若A是谓词公式，则(A)也是谓词公式 若A、B是谓词公式，则(AB)、(AB)、(AB)、(AB)也是谓词公式 若A是谓词公式，则xA ,xA也是谓词公式 只有有限次的应用构成的符号串才是谓词公式,2019/3/12,62,谓词逻辑归结基础基本概念,指导变量： xA ,xA中的x为指导变量 辖域： xA ,xA中的A成为相应量词的辖域 约束出现： 在辖域（A）中，x的所有出现称为约束出现 自由出现： 在辖域（A）中，不是约束出现的其他变量的出现，称为自由出现,2019/3/12,63,谓词逻辑归结

31、基础基本概念-例,例如： （1）所有的人都是要死的。 （2） 有的人活到一百岁以上。 在个体域D为人类集合时，可符号化为： （1）xP(x)，其中P(x)表示x是要死的。 （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活到一百岁以上。,2019/3/12,64,谓词逻辑归结基础谓词公式等值式,量词否定等值式： ( x ） M（x） （ y ） M（y）

32、( x ） M（x） （ y ） M（y） 量词分配等值式： ( x ）( P（x） Q（x）) ( x ） P（x） ( x ） 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 ）,2019/3/12,65,谓词逻辑归结基础谓词公式等值式,量词辖域收缩与扩张等值式： ( x ）( P（x） Q) ( x ） P（x） Q ( x ）( P（x） Q) ( x ）

33、 P（x） Q ( x ）( P（x） Q) ( x ） P（x） Q ( x ）(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）,2019/3/12,66,Skolem 标准型前束范式,SKolem标准型是在前束范式的基础上进行变量映射的 前束范式 如果A中的一切量词都位于该公式的最左边（不含否定词），且这些量词的辖域都延伸到公式的末端，则公式A是一个前束范式， (Q1x1)

34、(Q2x2)(Qnxn)M(x1,x2,xn) 量词提到公式最前端时存在约束变量换名问题，要严守约束变元的换名规则 (Qx ) M（x） （Qy ） M（y） (Qx ) M（x,z） （Qy ） M（y,z） 例题,Qi：量词，M：母式,2019/3/12,67,(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),2019/3/12,68,Skolem 标准型,前束范式中消去所有量词后形成的谓词公式为Skole

35、m标准型 Skolem标准型必须满足合取范式的条件 任何一个谓词公式都可以化成与之对应的Skolem标准型。但注意：Skolem标准型不唯一,2019/3/12,69,Skolem 标准型转化过程,将谓词公式G转换成为前束范式 消去量词 量词消去原则： 消去存在量词“” 如果存在量词左边没有任何全称量词，则只将其改写成为常量（a, b等） 如果是左边有全称量词的存在量词，消去时该变量改写成为全称量词的函数(f(x), g(y)等) 略去全称量词“”，简单地省略掉该量词,2019/3/12,70,Skolem 标准型例,将下式化为Skolem标准型： (x)(y)P(a, x, y) (x)(y

36、)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)(y)(Q(y, b)R(x) =(x)(y)P(a, x, y)(z)(Q(z, b)R(x)

37、 =(x)(y) (z)(P(a, x, y)(Q(z, b)R(x) 由此得到前述范式,2019/3/12,71,Skolem 标准型例,上页：(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)R(x) 略去全称变量，原式的Skolem标准型为： P(a, x, f(x) Q(g(x), b)R(x)

38、 例2： (x)p(x)(x)Q(x)(x)(p(x) Q(x),2019/3/12,72,Skolem定理,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,2019/3/12,73,子句集定义,子句与子句集 文字：不含任何连接词的谓词公式 子句：一些文字的析取（谓词的和） 空子

39、句：不含任何文字的子句， 子句集：所有子句的集合 对于任一个公式G，都可以通过Skolem标准型，标准化建立起一个子句集与之相对应,2019/3/12,74,子句集求取步骤,子句集S的求取：通过Skolem标准型求取 G 前束范式 消去量词生成Skolem标准型 将Skolem标准型中的子句提出，表 示为集合形式 ，即以“，”取代”， 并表示为集合形式 注意 Skolem标准型必须满足合取范式的条件,2019/3/12,75,P119 例4.1,(“x)P(x)Q(x)($ y)S(x,y)Q(x)(“x)P(x)B(x)化成子句集 (1) 蕴含等值式 (“x)P（x）Q(x)($ y)S(x

40、，y)Q(x)(“x)P（x）B（x） (2)否定内移 (“x)P（x）Q(x)($ y)S(x，y)Q(x)(“x)P（x）B（x） (3)全称量词对的分配律 (“x)P（x）Q(x)($ y)S(x，y)Q(x) P（x）B（x） (4)量词辖域的扩张等值 (“x) ($ y) )P（x）Q(x) S(x，y)Q(x) P（x）B（x） (5)分配律，朝合取范式进行 (“x) ($ y) P(x)S(x，y)Q(x)Q(x)S(x，y)Q(x)P（x）B（x） (6)利用吸收率 p(p q ) p ； p (pq ) p (“x) ($ y) P(x)S(x，y)Q(x)Q(x) P（x）

41、B（x） (“x) ($ y) P(x)S(x，y)P(x)Q(x)Q(x) P（x）B（x） (“x) ($ y) P(x)S(x，y)Q(x) P（x）B（x） (7)去掉量词 P(x)S(x，f(x)Q(x) P（x）B（x） (8) 子句变量标准化后，最终的子句集为： P(x) S(x,f(x),Q(y),P(w) B（w）,2019/3/12,76,子句集与谓词公式的不可满足性,G是不可满足的 S是不可满足的 G与S不等价，但在不可满足的意义下是一致的 定理3.1： 若G是给定的公式，而S是相应的子句集，则G是不可满足的，当且仅当S是不可满足的。 注意：G真不一定S真，而S真必有G真

42、 即： S = G,2019/3/12,77,子句集与谓词公式的不可满足性 定理3.1的推广,谓词公式G = G1G2G3Gn，G的子句集S的求取可以分解成几个部分单独处理。如果Gi的子句集为Si，则有： S= S1S2S3Sn。 G的子句集不为S，但可以证明： SG与S 在不可满足的意义上是一致的。 SG不可满足 S1S2S3Sn不可满足,2019/3/12,78,求取子句集例(1),例：对所有的x,y,z来说，如果y是x的父亲，z又是y的父亲，则z是x的祖父。又知每个人都有父亲，试问对某个人来说谁是它的祖父？ 求：用一阶逻辑表示这个问题，并建立子句集。 解：这里我们首先引入谓词： P(x,

43、 y) 表示x是y的父亲 Q(x, y) 表示x是y的祖父 ANS(x) 表示问题的解答,2019/3/12,79,求取子句集例(2),对第一个条件，“如果x是y 的父亲， y又是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：

44、Q(x, y)ANS(x) 则得到的相应的子句集为： S A1，S A2，SB ,2019/3/12,80,第三章谓词逻辑与归结原理,概述 命题逻辑的归结法 谓词逻辑归结基础 归结原理 归结过程的控制策略 Herbrand定理,2019/3/12,81,第三章谓词逻辑与归结原理,概述 命题逻辑的归结法 谓词逻辑归结基础 归结原理 归结过程的控制策略 Herbrand定理,2019/3/12,82,归结原理,方法： 和命题逻辑一样 但由于有函数，所以要考虑合一和置换,2019/3/12,83,置换,置换：在一个谓词公式中用置换项去置换变量 定义： 置换是形如t1/x1, t2/x2, , tn/

45、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不是一个置换,2019/3/12,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),2019/3/12,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先做置换然后再做置换，置换xi,2019/3/12,86,置换的合成,例：设f(y)/x, z/y，a/x, b/y, y/z，求与的合成。