![第四章 确定性推理_第1页](http://file3.renrendoc.com/fileroot_temp3/2021-12/16/03f0eec6-0f92-4e26-bad5-a498ee9f3234/03f0eec6-0f92-4e26-bad5-a498ee9f32341.gif)
![第四章 确定性推理_第2页](http://file3.renrendoc.com/fileroot_temp3/2021-12/16/03f0eec6-0f92-4e26-bad5-a498ee9f3234/03f0eec6-0f92-4e26-bad5-a498ee9f32342.gif)
![第四章 确定性推理_第3页](http://file3.renrendoc.com/fileroot_temp3/2021-12/16/03f0eec6-0f92-4e26-bad5-a498ee9f3234/03f0eec6-0f92-4e26-bad5-a498ee9f32343.gif)
![第四章 确定性推理_第4页](http://file3.renrendoc.com/fileroot_temp3/2021-12/16/03f0eec6-0f92-4e26-bad5-a498ee9f3234/03f0eec6-0f92-4e26-bad5-a498ee9f32344.gif)
![第四章 确定性推理_第5页](http://file3.renrendoc.com/fileroot_temp3/2021-12/16/03f0eec6-0f92-4e26-bad5-a498ee9f3234/03f0eec6-0f92-4e26-bad5-a498ee9f32345.gif)
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、2022-4-191o 推理就是按某种策略从已有事实和知识推出结论的过推理就是按某种策略从已有事实和知识推出结论的过程;程;o 已知知识和事实(已知判断):包括已掌握的与求解已知知识和事实(已知判断):包括已掌握的与求解问题有关的知识及关于问题的已知事实;问题有关的知识及关于问题的已知事实; 推理的结论:由已知判断推出新判断;推理的结论:由已知判断推出新判断;o 推理是由程序实现的,称为推理机。推理是由程序实现的,称为推理机。2022-4-1921、演绎推理、归纳推理、默认推理、演绎推理、归纳推理、默认推理推理的基本任务是从一种判断推出另一种判断推理的基本任务是从一种判断推出另一种判断按判断推
2、出的途径来划分,可分为按判断推出的途径来划分,可分为演绎推理、归纳推理演绎推理、归纳推理及默认推理及默认推理(1)演绎推理)演绎推理演绎推理是从全称判断推导出特称判断或单称判断的过程演绎推理是从全称判断推导出特称判断或单称判断的过程演绎推理有多种形式,经常用的是三段论式演绎推理有多种形式,经常用的是三段论式三段论式包括三段论式包括大前提:已知的一般性知识或假设大前提:已知的一般性知识或假设小前提:关于所研究的具体情况或个别事实的判断小前提:关于所研究的具体情况或个别事实的判断结论:由大前提推出的适合于小前提所示情况的新判断结论:由大前提推出的适合于小前提所示情况的新判断2022-4-193n
3、在任何情况下,由演绎推导出的结论都是蕴涵在大前在任何情况下,由演绎推导出的结论都是蕴涵在大前提的一般性知识中(提的一般性知识中(没有增加新知识没有增加新知识)n 只要大前提和小前提是正确的,则由它们推出的结论只要大前提和小前提是正确的,则由它们推出的结论必然是正确的。必然是正确的。(2) 归纳推理归纳推理归纳推理是从足够多的事例中归纳出一般性结论的推归纳推理是从足够多的事例中归纳出一般性结论的推理过程,是一种从个别到一般的推理理过程,是一种从个别到一般的推理归纳推理:完全归纳推理、不完全归纳推理归纳推理:完全归纳推理、不完全归纳推理完全归纳推理是在进行归纳时考察了相应事物的全部完全归纳推理是在
4、进行归纳时考察了相应事物的全部对象,并根据这些对象是否都具有某种属性,从而推对象,并根据这些对象是否都具有某种属性,从而推出这个事物是否具有这个属性出这个事物是否具有这个属性不完全归纳推理是指只考察了相应事物的部分对象就不完全归纳推理是指只考察了相应事物的部分对象就得出了结论得出了结论2022-4-194n 枚举归纳推理:若已知某类事物的有限可数个具体事枚举归纳推理:若已知某类事物的有限可数个具体事物都具有某种属性,则可推出该类事物都具有此属性物都具有某种属性,则可推出该类事物都具有此属性n 类比推理:在两个或两类事物有许多属性都相同或相类比推理:在两个或两类事物有许多属性都相同或相似的基础上
5、,推出它们在其他属性上也相同或相似的似的基础上,推出它们在其他属性上也相同或相似的一种推理一种推理(3) 默认推理默认推理又称缺省推理,它是在知识不完全的情况下假设某些又称缺省推理,它是在知识不完全的情况下假设某些条件已经具备所进行的推理条件已经具备所进行的推理摆脱了需要知道全部事实才能进行推理的需求,使得摆脱了需要知道全部事实才能进行推理的需求,使得在知识不完全的情况下也能进行推理在知识不完全的情况下也能进行推理2022-4-1952 2、确定性推理、不确定性推理、确定性推理、不确定性推理按推理时所用知识的确定性来划分,推理可分为确定按推理时所用知识的确定性来划分,推理可分为确定性推理、不确
6、定性推理性推理、不确定性推理确定性推理:推理时所用的知识都是精确的,推出的确定性推理:推理时所用的知识都是精确的,推出的结论也是确定的,其真值或者为真,或为假,没有第结论也是确定的,其真值或者为真,或为假,没有第三种情况出现三种情况出现不确定性推理:推理时所用的知识不都是精确的,推不确定性推理:推理时所用的知识不都是精确的,推出的结论也不完全是肯定的,真值位于真与假之间,出的结论也不完全是肯定的,真值位于真与假之间,命题的外延模糊不清命题的外延模糊不清2022-4-1963 3、单调推理、非单调推理、单调推理、非单调推理按推理过程中推出的结论是否单调地增加,或推出的按推理过程中推出的结论是否单
7、调地增加,或推出的结论是否越来越接近目标,可分为单调推理和非单调结论是否越来越接近目标,可分为单调推理和非单调推理推理单调推理:在推理过程中随着推理的向前推进及新知单调推理:在推理过程中随着推理的向前推进及新知识的加入,推出的结论是呈单调增加的趋势,并且越识的加入,推出的结论是呈单调增加的趋势,并且越来越接近最终目标,在推理过程中不出现反复的情况来越接近最终目标,在推理过程中不出现反复的情况非单调推理:在推理过程中由于新知识的加入,不仅非单调推理:在推理过程中由于新知识的加入,不仅没有加强已推出的结论,反而要否定它,使得推理退没有加强已推出的结论,反而要否定它,使得推理退回到前面的某一步,重新
8、开始。该推理一般是在知识回到前面的某一步,重新开始。该推理一般是在知识不完全的情况下进行的。不完全的情况下进行的。2022-4-1972022-4-1974 4、启发式推理、非启发式推理、启发式推理、非启发式推理按推理过程中是否运用启发式知识分类:按推理过程中是否运用启发式知识分类:启发式推理:在推理过程中运用了与问题有关启发式启发式推理:在推理过程中运用了与问题有关启发式知识,即解决问题的策略、技巧和经验,加快了推理知识,即解决问题的策略、技巧和经验,加快了推理过程,提高了搜索效率。过程,提高了搜索效率。非启发式推理:在推理过程中只按照一般的控制逻辑非启发式推理:在推理过程中只按照一般的控制
9、逻辑进行推理。缺乏对求解问题的针对性,推理效率较低,进行推理。缺乏对求解问题的针对性,推理效率较低,容易出现组合爆炸问题。容易出现组合爆炸问题。2022-4-1982022-4-198推理的控制策略推理的控制策略o 推理过程是一个思维过程,即推理过程是一个思维过程,即求解问题的过程求解问题的过程o 推理的控制策略主要包括推理方向、搜索策略、推理的控制策略主要包括推理方向、搜索策略、冲突消解策略、求解策略及限制策略等冲突消解策略、求解策略及限制策略等1 1、推理方向、推理方向n 推理方向用于确定推理的驱动方式,分为正向推理方向用于确定推理的驱动方式,分为正向推理、逆向推理、混合推理及双向推理四种
10、推理、逆向推理、混合推理及双向推理四种知识库知识库综合数据库综合数据库推理机推理机2022-4-199推理的控制策略推理的控制策略 正向推理正向推理 正向推理是从初始状态出发,使用规则,正向推理是从初始状态出发,使用规则,到达目标状态。又称为数据驱动推理、前向链到达目标状态。又称为数据驱动推理、前向链推理、模式制导推理及前件推理。推理、模式制导推理及前件推理。 逆向推理逆向推理 逆向推理是以某个假设目标为出发点的逆向推理是以某个假设目标为出发点的一种推理,又称为目标驱动推理、逆向链推理一种推理,又称为目标驱动推理、逆向链推理、目标制导推理及后件推理。、目标制导推理及后件推理。2022-4-19
11、10正、逆向推理比较正、逆向推理比较 项项 目目正向推理正向推理逆向推理逆向推理驱动方式驱动方式数据驱动数据驱动目标驱动目标驱动推理方法推理方法从一组数据出发向前推导结论从一组数据出发向前推导结论从可能的解出发向后推理验证解答从可能的解出发向后推理验证解答启动方法启动方法从一个事件启动从一个事件启动由询问关于目标状态的一个问题启动由询问关于目标状态的一个问题启动透明程度透明程度不能解释其推理过程不能解释其推理过程可解释其推理过程可解释其推理过程推理方向推理方向由底向上推理由底向上推理由顶向下推理由顶向下推理典型系统典型系统CLIPSCLIPS,OPSOPSPROLOGPROLOG2022-4-
12、1911推理的控制策略推理的控制策略混合推理混合推理o已知的事实不充分。通过正向推理先把其运用条件不能已知的事实不充分。通过正向推理先把其运用条件不能完全匹配的知识都找出来,并把这些知识可导出的结论完全匹配的知识都找出来,并把这些知识可导出的结论作为假设,然后分别对这些假设进行逆向推理。作为假设,然后分别对这些假设进行逆向推理。o由正向推理推出的结论可信度不高。由正向推理推出的结论可信度不高。o希望得到更多的结论。希望得到更多的结论。o推理的形式:推理的形式:n先正向再逆向先正向再逆向,通过正向推理,即从已知事实演绎出,通过正向推理,即从已知事实演绎出部分结果,然后再用逆向推理证实该目标或提高
13、部分结果,然后再用逆向推理证实该目标或提高 其其可信度可信度n先逆向再正向先逆向再正向,先假设一个目标进行逆向推理,然后,先假设一个目标进行逆向推理,然后再利用逆向推理中得到的信息进行正向推理,以推出再利用逆向推理中得到的信息进行正向推理,以推出更多的结论更多的结论2022-4-1912推理的控制策略推理的控制策略 双向推理双向推理双向推理是指正向推理与逆向推理同时进行,且在双向推理是指正向推理与逆向推理同时进行,且在推理过程中的某一步骤上推理过程中的某一步骤上“碰头碰头”的一种推理。的一种推理。正向推理所得的中间结论恰好是逆向推理此时要求正向推理所得的中间结论恰好是逆向推理此时要求的证据的证
14、据2 2、求解策略、求解策略 推理是只求一个解还是求所有解以及最优解等推理是只求一个解还是求所有解以及最优解等3 3、限制策略、限制策略 对推理的深度、宽度、时间、空间等进行限制对推理的深度、宽度、时间、空间等进行限制2022-4-19134 4、冲突消解策略 o 在推理过程中,匹配会出现三种情况在推理过程中,匹配会出现三种情况已知事实不能与知识库中的任何知识匹配成功已知事实不能与知识库中的任何知识匹配成功已知事实恰好只与知识库中的一个知识匹配成功已知事实恰好只与知识库中的一个知识匹配成功已知事实可与知识库中的多个知识匹配成功;或者有已知事实可与知识库中的多个知识匹配成功;或者有多个(组)已知
15、事实都可与知识库中某一知识匹配成多个(组)已知事实都可与知识库中某一知识匹配成功;或者有多个(组)已知事实可与知识库中的多个功;或者有多个(组)已知事实可与知识库中的多个知识匹配成功知识匹配成功出现冲突的情况出现冲突的情况对正向推理而言,如果有多条产生式规则的前件都和对正向推理而言,如果有多条产生式规则的前件都和已知的事实匹配成功;或者有多组不同的已知事实都已知的事实匹配成功;或者有多组不同的已知事实都与同一条产生式规则的前件匹配成功;或者两种情况与同一条产生式规则的前件匹配成功;或者两种情况同时出现同时出现推理的控制策略推理的控制策略2022-4-1914推理的控制策略推理的控制策略对逆向推
16、理而言,如果有多条产生式的后件都和同一对逆向推理而言,如果有多条产生式的后件都和同一假设匹配成功,或者有多条产生式后件可与多个假设假设匹配成功,或者有多条产生式后件可与多个假设匹配成功。匹配成功。按就近原则排序按就近原则排序l该策略把最近被使用过的规则赋予较高的优先级。该策略把最近被使用过的规则赋予较高的优先级。 按已知事实的新鲜性排序按已知事实的新鲜性排序 l一般我们认为新鲜事实是对旧知识的更新和改进,比一般我们认为新鲜事实是对旧知识的更新和改进,比老知识更有效,即后生成的事实比先生成的事实具有老知识更有效,即后生成的事实比先生成的事实具有较大的优先性。较大的优先性。 2022-4-1915
17、推理的控制策略推理的控制策略按匹配度排序按匹配度排序 l在不确定推理时,匹配度不仅可确定两个知识模式是在不确定推理时,匹配度不仅可确定两个知识模式是否可匹配,还可用于冲突消解。根据匹配程度来决定否可匹配,还可用于冲突消解。根据匹配程度来决定哪一个产生式规则优先被应用。哪一个产生式规则优先被应用。按领域问题特点排序按领域问题特点排序 l该方法按照求解问题领域的特点将知识排成固定的次该方法按照求解问题领域的特点将知识排成固定的次序。序。 按上下文限制排序按上下文限制排序l该策略将知识按照所描述的上下文分成若干组,在推该策略将知识按照所描述的上下文分成若干组,在推理过程中根据当前数据库中的已知事实与
18、上下文的匹理过程中根据当前数据库中的已知事实与上下文的匹配情况,确定选择某组中的某条知识。配情况,确定选择某组中的某条知识。 2022-4-1916推理的控制策略推理的控制策略按条件个数排序按条件个数排序l多条规则生成的结论相同的情况下,由于条件个多条规则生成的结论相同的情况下,由于条件个数较少的规则匹配所花费的时间较少而且容易实数较少的规则匹配所花费的时间较少而且容易实现,所以将条件少的规则赋予较高的优先级,优现,所以将条件少的规则赋予较高的优先级,优先被启用。先被启用。 按规则的次序排序按规则的次序排序 l该策略是以知识库中预先存入规则的排列顺序作该策略是以知识库中预先存入规则的排列顺序作
19、为知识排序的依据,排在前面的规则具有较高的为知识排序的依据,排在前面的规则具有较高的优先级。优先级。 2022-4-1917o 定义:定义:自然演绎推理是指从一组已知的事实出发,直接运用自然演绎推理是指从一组已知的事实出发,直接运用命题逻辑或谓词逻辑中的推理规则推出结论的过程命题逻辑或谓词逻辑中的推理规则推出结论的过程。 o 推理规则:推理规则:n P规则:在推理的任何步骤上都可引入前提规则:在推理的任何步骤上都可引入前提n T规则:推理时,如果前面步骤中有一个或多个公式永规则:推理时,如果前面步骤中有一个或多个公式永真蕴涵公式真蕴涵公式S,则可把,则可把S引入推理过程中。引入推理过程中。n
20、CP规则:如果能从规则:如果能从R和前提集合中推出和前提集合中推出S来,则可从前来,则可从前提集合推出提集合推出 来。来。n 反证法:反证法: ,当且仅当,当且仅当 。即:。即:Q为为P的逻辑结论,当且仅当的逻辑结论,当且仅当 是不可满足的。是不可满足的。SR QP FQPQP2022-4-1918o 假言推理假言推理 表示:由表示:由 及及P为真,可推出为真,可推出Q为真为真 o 拒取式推理拒取式推理 表示:由表示:由 为真及为真及Q为假,可推出为假,可推出P为假为假 QQPP,QP PQQP,QP 2022-4-1919n 肯定后件肯定后件(Q)(Q)的错误:当的错误:当PQPQ为真时为真
21、时, ,希望通过肯希望通过肯定后件定后件Q Q推出前件推出前件P P为真为真, ,这是不允许的这是不允许的. .n 否定前件否定前件(P)(P)的错误:当的错误:当PQPQ为真时为真时, ,希望通过否希望通过否定前件定前件P P推出后件推出后件Q Q为假为假, ,这也是不允许的这也是不允许的. .n避免产生两类错误:避免产生两类错误:2022-4-1920n 如果行星系统是以太阳为中心的如果行星系统是以太阳为中心的, ,则金星会显示则金星会显示出位相变化。出位相变化。 n 金星会显示出位相变化。金星会显示出位相变化。n 所以,行星系统是以太阳为中心的。所以,行星系统是以太阳为中心的。n如伽利略
22、在论证哥白尼的日心说时如伽利略在论证哥白尼的日心说时, ,曾使用曾使用了下列推理:了下列推理:这就是使用了肯定后件的推理,违反了经典逻辑的逻辑规则,他为此曾遭到非难。2022-4-1921n 如果上网,则能知道新闻。如果上网,则能知道新闻。 n 没有上网。没有上网。 n 所以,不知道新闻。所以,不知道新闻。n又如下列推理:又如下列推理:这就是使用了否定前件的推理,违反了逻辑规则,显然是不正确的,因为通过收听广播、看电视等,也会知道新闻。2022-4-1922o 例: 设已知事实 (1)只要不怕困难的人,就会获得胜利。 (2)运动员都是不怕困难的人。 (3)王力是运动员。 求证:王力会获得胜利。
23、 2022-4-1923o 自然演绎推理的优缺点自然演绎推理的优缺点n 优点:优点: 定理证明过程自然,容易理解,而且它拥有丰富的定理证明过程自然,容易理解,而且它拥有丰富的推理规则,推理过程灵活,便于在它的推理规则推理规则,推理过程灵活,便于在它的推理规则中嵌入领域启发式知识。中嵌入领域启发式知识。n 缺点:缺点: 容易产生组合爆炸,推理过程中得到的中间结论一容易产生组合爆炸,推理过程中得到的中间结论一般呈指数形式递增。般呈指数形式递增。2022-4-1924 人的问题求解行为更像是一个人的问题求解行为更像是一个解答识别解答识别过程而非过程而非解答搜索解答搜索过程过程 识别解答或部分解答依赖
24、于应用领域特有的知识,识别解答或部分解答依赖于应用领域特有的知识, 符号推理则成为基于知识来求解问题的主要手段。符号推理则成为基于知识来求解问题的主要手段。 符号推理的重要方式是演绎推理符号推理的重要方式是演绎推理 它的基础为谓词演算它的基础为谓词演算一种一种形式语言形式语言 将各种陈述性(说明性)的描述以将各种陈述性(说明性)的描述以形式化形式化的方式表示,以的方式表示,以便对它们便对它们 作处理。作处理。 谓词演算谓词演算人工智能系统最常用的知识表示方法,人工智能系统最常用的知识表示方法, 广泛地应用于各种人工智能系统的设计。广泛地应用于各种人工智能系统的设计。 谓词演算(或更广义地,形式
25、逻辑)是人工智能研究的重要基础谓词演算(或更广义地,形式逻辑)是人工智能研究的重要基础之一。之一。 主要内容:主要内容: 谓词演算谓词演算 H H域和海伯伦定理域和海伯伦定理 归结演绎归结演绎 归结反演归结反演 归结演绎推理归结演绎推理 2022-4-1925o 1、谓词公式、谓词公式n “谓词公式谓词公式”的一般形式:的一般形式:o P(x1,x2,xn),其中,其中,o P谓词符号谓词符号(简称谓词);(简称谓词);o Xi(i=1,2,n)参数项参数项(简称项),项可以(简称项),项可以是常量是常量、变量变量或或函数函数;o P(x1,x2,xn)n元谓词公式;元谓词公式;n “谓词公式
26、谓词公式”的基本组成:的基本组成:o 谓词符号谓词符号、常量符号常量符号、变量符号变量符号、函数符号函数符号;o 用用括号括号和和逗号逗号隔开,隔开,表示论域内的关系表示论域内的关系。n “谓词公式谓词公式是谓词逻辑的基本单元,也称为是谓词逻辑的基本单元,也称为原子公式原子公式。2022-4-1926o2、连词和量词、连词和量词n通过引入通过引入连词连词和和量词量词,可以把,可以把谓词公式(原子公式)谓词公式(原子公式)组合为组合为复合谓词复合谓词公式公式。n复合谓词公式复合谓词公式也称为也称为逻辑语句逻辑语句。o(1)连词)连词(非)加在(非)加在谓词公式谓词公式前面,称为否定,或取反。前面
27、,称为否定,或取反。(与)连接(与)连接谓词公式谓词公式,称为,称为合取合取;产生的产生的逻辑语句逻辑语句称为称为合取式合取式,每个成分成为,每个成分成为合取项。合取项。(或)连接(或)连接谓词公式谓词公式,称为,称为析取析取;产生的产生的逻辑语句逻辑语句称为称为析取式析取式,每个成分成为,每个成分成为析取项。析取项。(蕴涵)连接(蕴涵)连接谓词公式谓词公式产生产生蕴涵式蕴涵式;左部称为左部称为前项前项,右部称为,右部称为后项后项。(等价)连接(等价)连接谓词公式谓词公式产生产生等价式等价式;正、逆向蕴涵式的合取。;正、逆向蕴涵式的合取。2022-4-19o 2、连词和量词、连词和量词n通过引
28、入连词和量词,可以把通过引入连词和量词,可以把原子公式原子公式组合为组合为复合谓词公式复合谓词公式。n复合谓词公式也称为复合谓词公式也称为逻辑语句逻辑语句。o (1)连词)连词n通过连词产生的复合谓词公式(逻辑语句)的通过连词产生的复合谓词公式(逻辑语句)的真值表真值表:PQ PPQPQP QP QTTFTTTTFTTFTTFTFFFTFFFFTFFTT2022-4-1928o 2、连词和量词、连词和量词n 命题命题不包含不包含变量变量的的谓词公式谓词公式和和逻辑语句逻辑语句;n 命题逻辑命题逻辑基于基于命题命题的的谓词逻辑谓词逻辑称为称为命题逻辑命题逻辑,命题逻辑是谓词逻辑的子集命题逻辑是谓
29、词逻辑的子集。n 命题逻辑命题逻辑缺乏有效的表达缺乏有效的表达一般性概念一般性概念的能力的能力o 无法把每个知识单元抽象、细分;无法把每个知识单元抽象、细分;o 如,如,“条条大路通罗马条条大路通罗马”。o Lead(Road1,Roma)o Lead(Road2,Roma)n谓词逻辑谓词逻辑中引入中引入变量变量和对变量进行约束的和对变量进行约束的量词量词。o (2)量词)量词n全称量词全称量词存在量词存在量词 2022-4-1929o 2、连词和量词、连词和量词(2)量词)量词n全称量词全称量词o 符号符号( x)P(x):表示对于某个论域中的:表示对于某个论域中的所有(任意一所有(任意一个
30、)个)个体个体x, 都有都有P(x)真值为真值为T。n存在量词存在量词 o 符号符号( x)P(x):来表示某个论域中:来表示某个论域中至少存在一个至少存在一个个体个体x,使,使P(x) 真值为真值为T),()()(RomaxLeadxRoadx条条大路通罗马条条大路通罗马),()()()(yxMaryGiveyBookxPersonyxMary给每个人一本书给每个人一本书),()()(yxMaryGivexPersonxMary给每人某个同样的东西给每人某个同样的东西量词可以嵌套使用量词可以嵌套使用可以有不受量词约束的变量可以有不受量词约束的变量2022-4-1930o 2、连词和量词、连词
31、和量词(2)量词)量词n全称量词全称量词o 符号符号( x)P(x):表示对于某个论域中的:表示对于某个论域中的所有(任意一所有(任意一个)个)个体个体x, 都有都有P(x)真值为真值为T。n存在量词存在量词 o 符号符号( x)P(x):来表示某个论域中:来表示某个论域中至少存在一个至少存在一个个体个体x,使,使P(x) 真值为真值为T),()()(RomaxLeadxRoadx条条大路通罗马条条大路通罗马),()()(GrayxColorxRobotx所有机器人都是灰色的所有机器人都是灰色的2022-4-1931o 一阶谓词逻辑一阶谓词逻辑n 定义:定义:若限定若限定不允许不允许对对谓词谓
32、词和和函数名函数名进行进行量化量化处理,且处理,且参数项参数项不能是不能是谓词公式谓词公式,则这样的谓,则这样的谓词逻辑是词逻辑是一阶一阶的。的。o 谓词、函数名谓词、函数名的出现位置的出现位置不允许使用变量不允许使用变量;o 参数项参数项不能是不能是谓词公式谓词公式;n ( P)P(A)-谓词进行了量化;谓词进行了量化;n ( y)Married(y(L1),Mary )-函数名进行了量化;函数名进行了量化;n P(x,Q(y)-参数项是谓词公式;参数项是谓词公式;2022-4-1932o 1、合式公式的定义、合式公式的定义n合式公式合式公式适合于适合于一阶谓词逻辑一阶谓词逻辑n遵从以下递归
33、方式定义的遵从以下递归方式定义的逻辑语句逻辑语句称为称为合式公式合式公式n单一谓词公式是合式公式;单一谓词公式是合式公式;n若若A A是合式公式,则是合式公式,则 A A也是合式公式;也是合式公式;n若若A A和和B B都是合式公式,则都是合式公式,则A AB B、 A AB B、 A AB B和和A AB B也都是合式公式;也都是合式公式;n若若A A是合式公式,是合式公式,x x是约束变量,则是约束变量,则( ( x x)A)A和和( ( x x)A)A也也都是合式公式;都是合式公式;n只有按上述规则只有按上述规则- -求得的公式,才是合式公式。求得的公式,才是合式公式。n连词优先级别连词
34、优先级别是是 ,、,、,但可通过,但可通过括号括号改改变优先级。变优先级。 一、合式公式一、合式公式2022-4-1933一、合式公式一、合式公式o 1、合式公式的定义、合式公式的定义n例例2 2、“所有人所有人(Person)(Person)都喜欢都喜欢(Like)(Like)一种游戏一种游戏(Game)”(Game)”o 谓词公式谓词公式n Person(x)Person(x)n Like(x,y)Like(x,y)n Game(y)Game(y)o 量词量词n ( ( x x)Person(x)Person(x)表示表示所有所有人;人;n ( ( y)y)Game(y)Game(y)表示
35、表示一种一种游戏;游戏;o 合式公式合式公式n ( ( x x)()( y)Person(x)y)Person(x)Game(y)Game(y)Like(x,y)Like(x,y) 2022-4-1934一、合式公式一、合式公式o2、合式公式的解释、合式公式的解释n命题逻辑命题逻辑不存在变量不存在变量o给命题中包含的给命题中包含的各个原子公式指派真值各个原子公式指派真值(T或或F),称这种指派为),称这种指派为命题命题的一个的一个解释解释;o解释确定后,可依据连接原子公式的解释确定后,可依据连接原子公式的连词连词的作用求出命题的真值的作用求出命题的真值(T或或F)。)。n谓词逻辑谓词逻辑涉及变
36、量涉及变量o不可能直接给原子公式指派真值不可能直接给原子公式指派真值;o定义一个拟观察个体的可能定义一个拟观察个体的可能论域论域;o确定原子公式中确定原子公式中变量项变量项和和函数项函数项在论域中的在论域中的取值取值;o给原子公式给原子公式指派真值指派真值。o解释确定后,可依据连接原子公式的解释确定后,可依据连接原子公式的连词连词的作用求出合式公式的的作用求出合式公式的真值(真值(T或或F)。)。2022-4-1935一、合式公式一、合式公式o 2、合式公式的解释、合式公式的解释n例例3 3、合式公式、合式公式( ( x x)()( y)P(x)y)P(x)Q(f(x),y)Q(f(x),y)
37、一个解释的一个解释的建立。建立。n设定论域设定论域D=1,2; D=1,2; x xD,yD,yD Dn对于对于x x的每个取值的每个取值o 函数函数f(x)f(x):f(1)=2,f(2)=2;f(1)=2,f(2)=2;n对于对于x x的每个取值的每个取值o 原子公式原子公式P(x)P(x):P(1)=T,P(2)=TP(1)=T,P(2)=T;n对于对于f(x)f(x)和和y y的每个取值组合的每个取值组合( (只有只有2 2个:个:2 2、1 1;2 2、2)2)o 原子公式原子公式Q(f(x),y)Q(f(x),y):Q(2,1)=TQ(2,1)=T, Q(2,2)=F, Q(2,2
38、)=F;n上述上述指派指派就确定了该合式公式的就确定了该合式公式的一个解释一个解释;n在在这个解释这个解释下,合式公式有下,合式公式有真值真值T T;2022-4-1936一、合式公式一、合式公式o 3、合式公式的永真性和可满足性、合式公式的永真性和可满足性n(1)(1)合式公式的永真性合式公式的永真性o 若若P P在某个论域在某个论域D D上的上的所有所有可能的解释都有真值可能的解释都有真值T T,则称,则称P P在在D D上是上是永真的永真的;o 若若P P在在每个每个可能的非空论域可能的非空论域D D上均永真,则称上均永真,则称P P是是永真的永真的。n(2)(2)合式公式的可满足性合式
39、公式的可满足性o 若若P P在某个论域在某个论域D D上的上的至少至少可以建立一个解释,使可以建立一个解释,使P P有真值有真值T T,则称则称P P在在D D上是上是可满足的可满足的;o 若若至少至少有一个非空论域有一个非空论域D D使使P P可满足,则称可满足,则称P P是是可满足的可满足的。n(3)(3)合式公式的永假性合式公式的永假性o 若若P P在某个论域在某个论域D D上的上的所有所有可能的解释都有真值可能的解释都有真值F F,则称,则称P P在在D D上是上是永假的永假的;o 若若P P在在每个每个可能的非空论域可能的非空论域D D上均永假,则称上均永假,则称P P是是永假的永假
40、的。2022-4-1937一、合式公式一、合式公式o 4、合式公式的性质、合式公式的性质n合式公式合式公式优点优点:o 具有强大的形式化表示功能;具有强大的形式化表示功能;n合式公式合式公式缺点缺点:o 包括了多种连词和量词以及它们的嵌套应用,包括了多种连词和量词以及它们的嵌套应用,表示形式过表示形式过于复杂于复杂;o 不利于演绎推理系统的设计和高效运作不利于演绎推理系统的设计和高效运作。n化简合式公式化简合式公式到某些约定的标准形式是很有意义。到某些约定的标准形式是很有意义。o 合取范式合取范式o 析取范式析取范式n合式公式的性质合式公式的性质则为化简工作提供了依据。则为化简工作提供了依据。
41、2022-4-1938一、合式公式一、合式公式o4、合式公式的性质、合式公式的性质n十种常用性质十种常用性质n(1)双重否定:双重否定:o ( P) Pn(2)蕴涵式转化:蕴涵式转化:oP Q P Qn(3)狄狄.摩根定律:摩根定律:o (P Q) P Qo (P Q) P Qn(4)分配律分配律oP (Q R) (P Q) (P R) oP (Q R) (P Q) (P R)n(5)交换律交换律oP Q Q PoP Q Q Pn(6)结合律结合律o(P Q) R P (Q R)o(P Q) R P (Q R)2022-4-1939一、合式公式一、合式公式o4、合式公式的性质、合式公式的性质n
42、十种常用性质十种常用性质n(7)逆否律逆否律o P Q Q Pn(8)量词否定量词否定o ( x) P(x) ( x) ( P(x) o ( x) P(x) ( x) ( P(x) n(9)量词分配量词分配o ( x) P(x) Q(x) ( x)P(x) ( x) Q(x)o ( x) P(x) Q(x) ( x)P(x) ( x) Q(x) n(10)约束变量的虚元化约束变量的虚元化o 约束变量名的变换不影响合式公式的真值约束变量名的变换不影响合式公式的真值o ( x) P(x) ( y) P(y) o ( x) P(x) ( y) P(y) 2022-4-1940一、合式公式一、合式公式
43、o4、合式公式的性质、合式公式的性质n(9)量词分配量词分配o ( x) P(x) Q(x) ( x)P(x) ( y) Q(y)o ( x) P(x) Q(x) ( x)P(x) ( y) Q(y) n(10)约束变量的虚元化约束变量的虚元化o 约束变量名的变换不影响合式公式的真值约束变量名的变换不影响合式公式的真值o ( x) P(x) ( y) P(y) o ( x) P(x) ( y) P(y) 2022-4-1941 二、合式公式的标准化二、合式公式的标准化o 1、标准化需求、标准化需求n常见的基于谓词演算的推理:常见的基于谓词演算的推理:归结反演归结反演、(正向正向/逆向逆向)演绎
44、推理演绎推理o要求以要求以量词前束范式量词前束范式来表示合式公式来表示合式公式n量词前束范式量词前束范式形式如下:形式如下:o(Q1x1) (Q2x2)(Qkxk)M,其中,其中oM 母式,不包括任何量词;母式,不包括任何量词;oQixiQi可以是可以是量词量词符号符号 或或 ;xi是量词的是量词的约束变量约束变量(i=1,2,k)n归结反演归结反演要求要求M标准化为标准化为合取范式合取范式,定义如下:,定义如下:o M=W1W2 Wno Wi=Li1Li2 Lim(i=1,2,n)o Lij=Pij| Pij:文字(文字(Literal),是,是谓词公式谓词公式Pij或或其取反其取反2022
45、-4-1942 二、合式公式的标准化二、合式公式的标准化o 1、标准化需求、标准化需求n常见的基于谓词演算的推理:常见的基于谓词演算的推理:归结反演归结反演、规则演绎规则演绎o要求以要求以量词前束范式量词前束范式来表示合式公式来表示合式公式n量词前束范式量词前束范式形式如下:形式如下:o(Q1x1) (Q2x2)(Qkxk)Mn归结反演归结反演要求要求M标准化为标准化为合取范式合取范式,定义如下:,定义如下:o M=W1W2 Wno Wi=Li1Li2 Lim(i=1,2,n)o Lij=Pij| Pij:文字(文字(Literal),是原子谓词公式,是原子谓词公式Pij或其取反或其取反n析取
46、范式析取范式定义:定义:o M=W1W2Wno Wi=Li1Li2Lim(i=1,2,n)o Lij=Pij| Pij:文字(文字(Literal),是原子谓词公式,是原子谓词公式Pij或其取反或其取反2022-4-1943o 定义定义 设设F F为一谓词公式,如果其中的所有量词均非否为一谓词公式,如果其中的所有量词均非否定地出现在公式的最前面,而它们的辖域为整个公式,定地出现在公式的最前面,而它们的辖域为整个公式,则称则称F F为为前束范式前束范式(prenex normal form)(prenex normal form)。一般地,一般地,前束范式可以写成前束范式可以写成: :其 中其
47、中 为为 前 缀前 缀 , 是一个由全称量词或存在量词组成的是一个由全称量词或存在量词组成的量词串量词串, 为为母式母式,它是一个不含任何量词的谓词公,它是一个不含任何量词的谓词公式。式。111()()(,.,)nnnQ xQ xM xx(1,2,., )iQ in1 1()()nnQ xQ x1( ,.,)nM xx前束标准型前束标准型n在一阶逻辑中,为了简化定理证明程序需要引入所在一阶逻辑中,为了简化定理证明程序需要引入所谓的谓的“前束标准型前束标准型”。2022-4-1944 下面是一些前束范式的例子:下面是一些前束范式的例子: 为了把一个公式化为前束范式,首先看一下包含为了把一个公式化
48、为前束范式,首先看一下包含一阶逻辑特有的等价式对,如下所示。一阶逻辑特有的等价式对,如下所示。 ()()( ( , )( )()()( , )( )()()()( ( , )( )xyP x yQ yxyP x yQ yxyzP x yQ z前束标准型前束标准型2022-4-1945(1) ()( )()( )Qx F xGQxF xG(2) ()( )()( )Qx F xGQxF xG1212(3)() ( )()( )()()( ( )( )Qx F xQ x H xQx Q z F xH z1212(4) () ( )()( )()()( ( )( )Q x F xQ x H xQ x
49、 Q z F xH z 在上述等价公式对中在上述等价公式对中,F(x)和和 H(x)都表示含未都表示含未量化变量量化变量x的公式的公式,G表示不含未量化变量表示不含未量化变量x的公的公式,式,Q1,Q2 或为或为 或为或为 。 对对(3)和和(4),要求要求z不出现在不出现在F(x) 中,并且符合约中,并且符合约束变量的换名原则。束变量的换名原则。 前束标准型前束标准型2022-4-1946 使用前面定义的等价式,总可以把一个公式化为使用前面定义的等价式,总可以把一个公式化为前束标准型。前束标准型。 变换过程如下:变换过程如下: (1) (1) 使用等价式中的连接词转化规律消去公式中的使用等价
50、式中的连接词转化规律消去公式中的连接词连接词, , 。 (2) (2) 反复使用双重否定律和德反复使用双重否定律和德摩根律将摩根律将“( (或或) )”移到原子之前。移到原子之前。 (3) (3) 必要时重新命名量化的变量。必要时重新命名量化的变量。 (4) (4) 使用量词分配律和等价式,把所有量词都移到使用量词分配律和等价式,把所有量词都移到整个公式的最左边以得出一个范式。整个公式的最左边以得出一个范式。 前束标准型前束标准型2022-4-1947 二、合式公式的标准化二、合式公式的标准化o 2、合取范式的标准化过程、合取范式的标准化过程n应用应用合式公式性质合式公式性质将公式逐步转化的过
51、程。将公式逐步转化的过程。n转化步骤没有严格的规定转化步骤没有严格的规定n较合理的化简过程,分为较合理的化简过程,分为8步:步:o 消去多余的量词(很少出现);消去多余的量词(很少出现);o 消去蕴涵符号;消去蕴涵符号;o 内移否定符号;内移否定符号;o 变量换名;变量换名;o 消去存在量词;消去存在量词;o 全称量词前束化;全称量词前束化;o 消去全称量词;消去全称量词;o 把把母式母式转化为转化为合取范式合取范式。2022-4-1948 二、合式公式的标准化二、合式公式的标准化o 2、合取范式的标准化过程、合取范式的标准化过程o 消去多余的量词(很少出现)消去多余的量词(很少出现)n若若一
52、个量词的辖域内并未出现量词的约束变量一个量词的辖域内并未出现量词的约束变量,则该量词是多,则该量词是多余的,应该删除;余的,应该删除;n例,例,( x)P(y),则,则( x)可以消去,得到可以消去,得到P(y);n正常情况下,合式公式中不应出现多余的量词。正常情况下,合式公式中不应出现多余的量词。o 消去蕴涵符号消去蕴涵符号n蕴涵式转化蕴涵式转化:P Q P Q;n例,例, Q(x,y) P(y) Q(x,y) P(y)。2022-4-1949 二、合式公式的标准化二、合式公式的标准化o2、合取范式的标准化过程、合取范式的标准化过程o内移否定符号内移否定符号n使否定只出现在原子谓词公式前,构
53、成使否定只出现在原子谓词公式前,构成否定文字否定文字;n狄狄.摩根定律:摩根定律:o (P Q) P Qo (P Q) P Qn双重否定:双重否定: ( P) Pn量词否定:量词否定:o ( x) P(x) ( x) ( P(x) o ( x) P(x) ( x) ( P(x) n例,例, ( y) P(y)P(f(x,y)( y)P(y) P(f(x,y)o变量换名变量换名n“全称量词前束化全称量词前束化”后,同名变量的辖域无法区分,所以为避免差错,后,同名变量的辖域无法区分,所以为避免差错,必须换名;必须换名;n约束变量的虚元性约束变量的虚元性进行变换;进行变换;o( x) P(x) (
54、y) P(y) o( x) P(x) ( y) P(y)2022-4-1950o消去存在量词消去存在量词Skolem标准化过程111().()(,.,)nnnQ xQ x M xxStep1: 化成前束范式化成前束范式:Step2: 使用下述方法可以消去前缀中存在的所有量词:使用下述方法可以消去前缀中存在的所有量词: 令令 是是 中出现的存在量词中出现的存在量词 。rQ1 1().()n nQ xQ x(1)r n Case1: 若在若在 之前不出现全称量词,则选择一个与之前不出现全称量词,则选择一个与M中出现的所有常量都不相同的新常量中出现的所有常量都不相同的新常量c,用,用c代替代替M中出
55、中出现的所有现的所有xr,并且由前缀中删去,并且由前缀中删去(Qrxr) 。rQCase2: 若在若在 之前出现全称量词之前出现全称量词 ,则选择一,则选择一个与个与M中出现的任一函数符号都不相同的新中出现的任一函数符号都不相同的新m元函数符元函数符号号f,用,用 代替代替M中的所有中的所有xr ,并且由前缀中,并且由前缀中删去删去(Qrxr) 。rQ1,.,ssmQQ1(,.,)ssmf xx 按上述方法删去前缀中的所有存在量词之后得出的公式称为按上述方法删去前缀中的所有存在量词之后得出的公式称为合式公式的合式公式的Skolem标准型标准型。替代存在量化变量的常量。替代存在量化变量的常量c(
56、视为视为0元元函数函数)和函数和函数f称为称为Skolem函数。函数。2022-4-1951( , , , , ,)x y z u v wP x y z u v w 在公式中在公式中, 的前面没有全称量词的前面没有全称量词, 的前面有全称量的前面有全称量词词 和和 , 在在 的前面有全称量词的前面有全称量词 , 和和 。所。所以,在以,在 中,用常数中,用常数a代替代替x, 用二元函数用二元函数f(y,z)代代替替u, 用三元函数用三元函数g(y,z,v)代替代替w,去掉前缀中的所有存在量词之去掉前缀中的所有存在量词之后得出后得出Skolem标准型标准型:()y()w()y() z()v( ,
57、 , , , ,)P x y z u v w(z)()u() x例题分析例例4.1 化公式化公式为为Skolem标准型。标准型。),(,),(,(vzygvzyfzyavPzy2022-4-1952 二、合式公式的标准化二、合式公式的标准化o2、合取范式的标准化过程、合取范式的标准化过程o消去存在量词消去存在量词n 在在 的辖域内的辖域内o ( z)( w) Q(x,z) P(z,w)o w依赖于依赖于z,由函数,由函数w=g(z)来定义这种依赖关系;来定义这种依赖关系;o 用用g(z)来取代约束变量来取代约束变量w,消去存在量词,消去存在量词 w;o ( z) Q(x,z) P(z,g(z)
58、n 在在多个多个 的辖域内的辖域内o ( x)( y)( z)( w)P(x,y,z,w)o 用多元函数用多元函数g(x,y,z)来取代约束变量来取代约束变量w,消去存在量词,消去存在量词 w;o ( x)( y)( z)P(x,y,z,g(x,y,z)n 在在 的辖域外的辖域外o ( w)( z) Q(x,z) P(z,w)o 用用任意常量任意常量A取代约束变量取代约束变量w,消去存在量词,消去存在量词 wo ( z) Q(x,z) P(z,A)前两种叫前两种叫Skolem函数,第三函数,第三种叫种叫Skolem常量常量2022-4-1953总结:总结:Skolem函数和函数和Skolem常
59、量常量 在消去存在量词的过程中,需要用到在消去存在量词的过程中,需要用到Skolem函数或函数或Skolem常量。若常量。若存在量词是在全称量词的辖域内存在量词是在全称量词的辖域内,用用Skolem函数消去存在量词函数消去存在量词。 Skolem函数所使用函数所使用的函数符号必须是的函数符号必须是新的新的,即不允许是公式中已经出现,即不允许是公式中已经出现过的函数符号。过的函数符号。 若要消去的若要消去的存在量词不在任何一个全称量词的辖域内存在量词不在任何一个全称量词的辖域内,用不含变量的,用不含变量的Skolem函数即函数即Skolem常量消去存常量消去存在量词在量词。所使用的常量符号必须是
60、。所使用的常量符号必须是新的新的,它未曾在公,它未曾在公式其他地方使用过。式其他地方使用过。 Skolem变换变换不是等价变换,但变换前后的值永假性不是等价变换,但变换前后的值永假性保持不变保持不变。2022-4-1954 二、合式公式的标准化二、合式公式的标准化o 2、合取范式的标准化过程、合取范式的标准化过程o 全称量词前束化全称量词前束化n经过经过“变量换名变量换名”后,所有量词的约束变量均有不同的后,所有量词的约束变量均有不同的名字;名字;n只要简单地将只要简单地将 移到合式公式的最前面;移到合式公式的最前面;n约束变量的作用范围不会变化。约束变量的作用范围不会变化。o 消去全称量词消
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 小学新学期开学计划-开学工作计划小学三年级班级计划
- 有关五年级班主任计划024 五年级班主任计划下
- 20某年社区矫正工作计划 社区矫正工作计划
- 2024质管部的年度工作计划
- 四年级下册数学课程教学计划-四年级下册数学教学计划
- 七年级教学教学计划
- 2024年上学期幼儿园安全教育工作计划表
- 企业公司2024年工作总结及2024年工作计划
- 业务培训工作总结计划
- 小学春季德育工作计划
- 【MOOC】中药药理学-学做自己的调理师-暨南大学 中国大学慕课MOOC答案
- 教育培训机构教师合同模板
- 2015-2016学年第二学期《电工电子技术》学科授课教案
- 2023年国家公务员录用考试《行测》真题(行政执法)及答案解析
- 精益-大学生创新与创业学习通超星期末考试答案章节答案2024年
- 运维保障年终总结
- 公司管理制度完整版
- 深圳2020-2024年中考英语真题专题07 书面表达(解析版)
- 纪检监察业务知识试题库及答案
- GB/T 44735-2024野生动物保护繁育朱鹮
- 幼儿园中班健康活动《情绪温度计》课件
评论
0/150
提交评论