人工智能ppt课件 第四章 确定性推理.ppt
《人工智能ppt课件 第四章 确定性推理.ppt》由会员分享,可在线阅读,更多相关《人工智能ppt课件 第四章 确定性推理.ppt(168页珍藏版)》请在三一办公上搜索。
1、2022/12/11,1,第4章 确定性推理,本章介绍: 自然演绎推理 归结演绎推理,推理就是按某种策略由已知判断推出另一判断的思维过程已知判断:包括已掌握的与求解问题有关的知识 及关于问题的已知事实 推理的结论:由已知判断推出新判断推理由程序程序实现,称为推理机,2022/12/11,2,1、演绎推理、归纳推理、默认推理推理的基本任务是从一种判断推出另一种判断按判断推出的途径来划分,可分为演绎推理、归结推理及默认推理(1)演绎推理演绎推理是从全称判断推导出特称判断或单称判断的过程演绎推理有多种形式,经常用的是三段论式三段论式包括大前提:已知的一般性知识或假设小前提:关于所研究的具体情况或个别
2、事实的判断结论:由大前提推出的适合于小前提所示情况的新判断,4.1 推理技术概述,2022/12/11,3,在任何情况下,由演绎推导出的结论都是蕴涵在大前提的一般性知识中只要大前提和小前提是正确的,则由它们推出的结论必然是正确的(2) 归纳推理归纳推理是从足够多的事例中归纳出一般性结论的推理过程,是一种从个别到一般的推理归纳推理:完全归纳推理、不完全归纳推理完全归纳推理是在进行归纳时考察了相应事物的全部对象,并根据这些对象是否都具有某种属性,从而推出这个事物是否具有这个属性不完全归纳推理是指只考察了相应事物的部分对象就得出了结论,2022/12/11,4,枚举归纳推理:若已知某类事物的有限可数
3、个具体事物都具有某种属性,则可推出该类事物都具有此属性类比推理:在两个或两类事物有许多属性都相同或相似的基础上,推出它们在其他属性上也相同或相似的一种推理(3) 默认推理又称缺省推理,它是在知识不完全的情况下假设某些条件已经具备所进行的推理摆脱了需要知道全部事实才能进行推理的需求,使得在知识不完全的情况下也能进行推理,2022/12/11,5,2、确定性推理、不确定性推理按推理时所用知识的确定性来划分,推理可分为确定性推理、不确定性推理确定性推理:推理时所用的知识都是精确的,推出的结论也是确定的,其真值或者为真,或为假,没有第三种情况出现不确定性推理:推理时所用的知识不都是精确的,推出的结论也
4、不完全是肯定的,真值位于真与假之间,命题的外延模糊不清,2022/12/11,6,3、单调推理、非单调推理按推理过程中推出的结论是否单调地增加,或推出的结论是否越来越接近目标,可分为单调推理和非单调推理单调推理:在推理过程中随着推理的向前及新知识的加入,推出的结论是呈单调增加的趋势,并且越来越接近最终目标,在推理过程中不出现反复的情况非单调推理:在推理过程中由于新知识的加入,不仅没有加强已推出的结论,反而要否定它,使得推理退回到前面的某一步,重新开始,2022/12/11,7,4.2 自然演绎推理,定义:自然演绎推理是指从一组已知的事实出发,直接运用命题逻辑或谓词逻辑中的推理规则推出结论的过程
5、。 推理规则:P规则:在推理的任何步骤上都可引入前提T规则:推理时,如果前面步骤中有一个或多个公式永真蕴涵公式S,则可把S引入推理过程中。CP规则:如果能从R和前提集合中推出S来,则可从前提集合推出 来。反证法: ,当且仅当 。即:Q为P的逻辑结论,当且仅当 是不可满足的。,2022/12/11,8,假言推理 表示:由 及P为真,可推出Q为真 拒取式推理 表示:由 为真及Q为假,可推出P为假,2022/12/11,9,避免产生两类错误:肯定后件(Q)的错误:希望通过肯定后件Q推出前件P为真否定前件(P)的错误:希望通过否定前件P推出后件Q为假,2022/12/11,10,例: 设已知事实 (1
6、)只要不怕困难的人,就会获得胜利。 (2)运动员都是不怕困难的人。 (3)王力是运动员。 求证:王力会获得胜利。,2022/12/11,11,自然演绎推理的优缺点优点: 定理证明过程自然,容易理解,而且它拥有丰富的推理规则,推理过程灵活,便于在它的推理规则中嵌入领域启发式知识。缺点: 容易产生组合爆炸,推理过程中得到的中间结论一般呈指数形式递增。,2022/12/11,12,1、合式公式的定义合式公式适合于一阶谓词逻辑遵从以下递归方式定义的逻辑语句称为合式公式单一谓词公式是合式公式;若A是合式公式,则A也是合式公式;若A和B都是合式公式,则AB、 AB、 AB和AB也都是合式公式;若A是合式公
7、式,x是约束变量,则(x)A和(x)A也都是合式公式;只有按上述规则-求得的公式,才是合式公式。连词优先级别是,、,、,但可通过括号改变优先级。,4.3 合式公式,一、合式公式,2022/12/11,13,一、合式公式,1、合式公式的定义例2、“所有人(Person)都喜欢(Like)一种游戏(Game)”谓词公式Person(x)Like(x,y)Game(y)量词(x)Person(x)表示所有人;(y)Game(y)表示一种游戏;合式公式(x)(y)Person(x)Game(y)Like(x,y),2022/12/11,14,一、合式公式,2、合式公式的解释命题逻辑不存在变量给命题中包
8、含的各个原子公式指派真值(T或F),称这种指派为命题的一个解释;解释确定后,可依据连接原子公式的连词的作用求出命题的真值(T或F)。谓词逻辑涉及变量不可能直接给原子公式指派真值;定义一个拟观察个体的可能论域;确定原子公式中变量项和函数项在论域中的取值;给原子公式指派真值。解释确定后,可依据连接原子公式的连词的作用求出合式公式的真值(T或F)。,2022/12/11,15,一、合式公式,2、合式公式的解释例3、合式公式(x)(y)P(x)Q(f(x),y)一个解释的建立。设定论域D=1,2; xD,yD对于x的每个取值函数f(x):f(1)=2,f(2)=2;对于x的每个取值原子公式P(x):P
9、(1)=T,P(2)=T;对于f(x)和y的每个取值组合(只有2个:2、1;2、2)原子公式Q(f(x),y):Q(2,1)=T, Q(2,2)=F;上述指派就确定了该合式公式的一个解释;在这个解释下,合式公式有真值T;,2022/12/11,16,一、合式公式,3、合式公式的永真性和可满足性(1)合式公式的永真性若P在某个论域D上的所有可能的解释都有真值T,则称P在D上是永真的;若P在每个可能的非空论域D上均永真,则称P是永真的。(2)合式公式的可满足性若P在某个论域D上的至少可以建立一个解释,使P有真值T,则称P在D上是可满足的;若至少有一个非空论域D使P可满足,则称P是可满足的。(3)合
10、式公式的永假性若P在某个论域D上的所有可能的解释都有真值F,则称P在D上是永假的;若P在每个可能的非空论域D上均永假,则称P是永假的。,2022/12/11,17,一、合式公式,3、合式公式的永真性和可满足性论域个数较少,每个论域较小易判断合式公式的永真性和可满足性;论域个数较多,每个论域较大,解释个数有限永真性和可满足性总是可判断的;解释个数无限不能确保可判断;不能确保在有限的时间内判断。,2022/12/11,18,一、合式公式,4、合式公式的性质合式公式优点:具有强大的形式化表示功能;合式公式缺点:包括了多种连词和量词以及它们的嵌套应用,表示形式过于复杂;不利于演绎推理系统的设计和高效运
11、作。化简合式公式到某些约定的标准形式是很有意义。合取范式析取范式合式公式的性质则为化简工作提供了依据。,2022/12/11,19,一、合式公式,4、合式公式的性质十种常用性质(1)双重否定:(P) P(2)蕴涵式转化:P Q P Q(3)狄.摩根定律:(P Q) P Q(P Q) P Q(4)分配律P (Q R) (P Q) (P R) P (Q R) (P Q) (P R)(5)交换律P Q Q PP Q Q P(6)结合律(P Q) R P (Q R)(P Q) R P (Q R),2022/12/11,20,一、合式公式,4、合式公式的性质十种常用性质(7)逆否律P Q Q P(8)量
12、词否定(x) P(x) (x) (P(x) (x) P(x) (x) (P(x) (9)量词分配(x) P(x) Q(x) (x)P(x) (x) Q(x)(x) P(x) Q(x) ( x)P(x) ( x) Q(x) (10)约束变量的虚元化约束变量名的变换不影响合式公式的真值(x) P(x) (y) P(y) (x) P(x) (y) P(y),2022/12/11,21,一、合式公式,4、合式公式的性质(9)量词分配(x) P(x) Q(x) (x)P(x) (y) Q(y)(x) P(x) Q(x) ( x)P(x) ( y) Q(y) (10)约束变量的虚元化约束变量名的变换不影响
13、合式公式的真值(x) P(x) (y) P(y) (x) P(x) (y) P(y),2022/12/11,22,二、合式公式的标准化,1、标准化需求常见的基于谓词演算的推理:归结反演、(正向/逆向)演绎推理要求以量词前束范式来表示合式公式量词前束范式形式如下:(Q1x1) (Q2x2)(Qkxk)M,其中M 母式,不包括任何量词;QixiQi可以是量词符号或;xi是量词的约束变量(i=1,2,k)归结反演(4.5.5,2.3.3)要求M标准化为合取范式,定义如下:M=W1W2 WnWi=Li1Li2 Lim(i=1,2,n)Lij=Pij|Pij:文字(Literal),是谓词公式Pij或其
14、取反,2022/12/11,23,二、合式公式的标准化,1、标准化需求常见的基于谓词演算的推理:归结反演、规则演绎要求以量词前束范式来表示合式公式量词前束范式形式如下:(Q1x1) (Q2x2)(Qkxk)M归结反演要求M标准化为合取范式,定义如下:M=W1W2 WnWi=Li1Li2 Lim(i=1,2,n)Lij=Pij|Pij:文字(Literal),是原子谓词公式Pij或其取反析取范式定义:M=W1W2WnWi=Li1Li2Lim(i=1,2,n)Lij=Pij|Pij:文字(Literal),是原子谓词公式Pij或其取反,2022/12/11,24,定义 设F为一谓词公式,如果其中的
15、所有量词均非否定地出现在公式的最前面,而它们的辖域为整个公式,则称F为前束范式(prenex normal form)。一般地,前束范式可以写成:其中 为前缀, 是一个由全称量词或存在量词组成的量词串, 为母式,它是一个不含任何量词的谓词公式。,前束标准型,在一阶逻辑中,为了简化定理证明程序需要引入所谓的“前束标准型”。,2022/12/11,25,下面是一些前束范式的例子: 为了把一个公式化为前束范式,首先看一下包含一阶逻辑特有的等价式对,如下所示。,前束标准型,2022/12/11,26,在上述等价公式对中,F(x)和 H(x)都表示含未量化变量x的公式,G表示不含未量化变量x的公式,Q1
16、,Q2 或为 或为。 对(3)和(4),要求z不出现在F(x) 中,并且符合约束变量的换名原则。,前束标准型,2022/12/11,27,使用前面定义的等价式,总可以把一个公式化为前束标准型。 变换过程如下: (1) 使用等价式中的连接词转化规律消去公式中的连接词, 。 (2) 反复使用双重否定律和德摩根律将“(或)”移到原子之前。 (3) 必要时重新命名量化的变量。 (4) 使用量词分配律和等价式,把所有量词都移到整个公式的最左边以得出一个范式。,前束标准型,2022/12/11,28,二、合式公式的标准化,2、合取范式的标准化过程应用合式公式性质将公式逐步转化的过程。转化步骤没有严格的规定
17、较合理的化简过程,分为8步:消去多余的量词(很少出现);消去蕴涵符号;内移否定符号;变量换名;消去存在量词;全称量词前束化;消去全称量词;把母式转化为合取范式。,2022/12/11,29,二、合式公式的标准化,2、合取范式的标准化过程消去多余的量词(很少出现)若一个量词的辖域内并未出现量词的约束变量,则该量词是多余的,应该删除;例,(x)P(y),则(x)可以消去,得到P(y);正常情况下,合式公式中不应出现多余的量词。消去蕴涵符号蕴涵式转化:P Q P Q;例, Q(x,y) P(y) Q(x,y) P(y)。,2022/12/11,30,二、合式公式的标准化,2、合取范式的标准化过程内移
18、否定符号使否定只出现在原子谓词公式前,构成否定文字;狄.摩根定律:(P Q) P Q(P Q) P Q双重否定:(P) P量词否定:(x) P(x) (x) (P(x) (x) P(x) (x) (P(x) 例, (y)P(y)P(f(x,y)(y)P(y)P(f(x,y)变量换名“全称量词前束化”后,同名变量的辖域无法区分,所以为避免差错,必须换名;约束变量的虚元性进行变换;(x) P(x) (y) P(y) (x) P(x) (y) P(y),2022/12/11,31,消去存在量词,Skolem标准化过程,Step1: 化成前束范式:,Step2: 使用下述方法可以消去前缀中存在的所有量
19、词: 令 是 中出现的存在量词 。,Case1: 若在 之前不出现全称量词,则选择一个与M中出现的所有常量都不相同的新常量c,用c代替M中出现的所有xr,并且由前缀中删去(Qrxr) 。,Case2: 若在 之前出现全称量词 ,则选择一个与M中出现的任一函数符号都不相同的新m元函数符号f,用 代替M中的所有xr ,并且由前缀中删去(Qrxr) 。,按上述方法删去前缀中的所有存在量词之后得出的公式称为合式公式的Skolem标准型。替代存在量化变量的常量c(视为0元函数)和函数f称为Skolem函数。,2022/12/11,32,在公式中, 的前面没有全称量词, 的前面有全称量词 和 , 在 的前
20、面有全称量词 , 和 。所以,在 中,用常数a代替x, 用二元函数f(y,z)代替u, 用三元函数g(y,z,v)代替w,去掉前缀中的所有存在量词之后得出Skolem标准型:,例题分析,例4.1 化公式,为Skolem标准型。,2022/12/11,33,二、合式公式的标准化,2、合取范式的标准化过程消去存在量词在的辖域内(z)(w)Q(x,z) P(z,w)w依赖于z,由函数w=g(z)来定义这种依赖关系;用g(z)来取代约束变量w,消去存在量词w;(z)Q(x,z) P(z,g(z)在多个的辖域内(x)(y)(z)(w)P(x,y,z,w)用多元函数g(x,y,z)来取代约束变量w,消去存
21、在量词w;(x)(y)(z)P(x,y,z,g(x,y,z)在的辖域外(w)(z) Q(x,z) P(z,w)用任意常量A取代约束变量w,消去存在量词w(z) Q(x,z) P(z,A),2022/12/11,34,二、合式公式的标准化,2、合取范式的标准化过程全称量词前束化经过“变量换名”后,所有量词的约束变量均有不同的名字;只要简单地将移到合式公式的最前面;约束变量的作用范围不会变化。消去全称量词经过“消去存在量词”后,所有变量均受的约束;简单地删除,只留下母式。把母式转化为合取范式分配律: P (Q R) (P Q) (P R),2022/12/11,35,二、合式公式的标准化,2、合取
22、范式的标准化过程例3、化简合式公式(x)P(x)(y)P(y) P(f(x,y)(y)(w)Q(x,y)P(y,w),2022/12/11,36,二、合式公式的标准化,2、合取范式的标准化过程例3、化简合式公式(x)P(x)(y)P(y) P(f(x,y)(y)(w)Q(x,y)P(y,w)消去蕴涵符号(x)P(x)(y)P(y)P(f(x,y)(y)(w)Q(x,y)P(y,w),2022/12/11,37,二、合式公式的标准化,2、合取范式的标准化过程例3、化简合式公式(x)P(x)(y)P(y)P(f(x,y)(y)(w)Q(x,y)P(y,w)内移否定符号(x)P(x)(y)P(y)P
23、(f(x,y)(y)(w)Q(x,y)P(y,w),2022/12/11,38,二、合式公式的标准化,2、合取范式的标准化过程例3、化简合式公式(x)P(x)(y)P(y)P(f(x,y)(y)(w)Q(x,y)P(y,w)变量换名(x)P(x)(y)P(y)P(f(x,y)(z)(w)Q(x,z)P(z,w),2022/12/11,39,二、合式公式的标准化,2、合取范式的标准化过程例3、化简合式公式(x)P(x)(y)P(y)P(f(x,y)(z)(w)Q(x,z)P(z,w)消去存在量词P(A)(y)P(y)P(f(A,y)(z)Q(A,z)P(z,g(z),2022/12/11,40,
24、二、合式公式的标准化,2、合取范式的标准化过程例3、化简合式公式P(A)(y)P(y)P(f(A,y)(z)Q(A,z)P(z,g(z)全称量词前束化(y)(z)P(A)P(y)P(f(A,y)Q(A,z)P(z,g(z),2022/12/11,41,二、合式公式的标准化,2、合取范式的标准化过程例3、化简合式公式(y)(z)P(A)P(y)P(f(A,y)Q(A,z)P(z,g(z)消去全称量词P(A)P(y)P(f(A,y)Q(A,z)P(z,g(z),2022/12/11,42,二、合式公式的标准化,2、合取范式的标准化过程例3、化简合式公式P(A)P(y)P(f(A,y)Q(A,z)P
25、(z,g(z)把母式转化为合取范式P(A)P(y)Q(A,z)P(z,g(z)P(f(A,y)Q(A,z)P(z,g(z),完成标准化过程!,2022/12/11,43,4.4 归结演绎推理,自动定理证明一般表示形式为:F1F2FnWF1, F2, ,Fn都是合式公式,表示公理或事实;W是合式公式,表示待证明的定理,称为目标公式;证明的方法可分两大类:演绎法直接证明F1F2FnW为永真;反证法间接证明(F1F2FnW)为永假;证明F1F2Fn W的永假即F1, F2, ,Fn W是一个矛盾集。,4.4 归结演绎推理,2022/12/11,44,4.4 归结演绎推理,海伯伦(Herbrand)提
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 人工智能ppt课件 第四章 确定性推理 人工智能 ppt 课件 第四 确定性 推理
链接地址:https://www.31ppt.com/p-1622015.html