知识的一阶谓词逻辑表示法课件.ppt
《知识的一阶谓词逻辑表示法课件.ppt》由会员分享,可在线阅读,更多相关《知识的一阶谓词逻辑表示法课件.ppt(161页珍藏版)》请在三一办公上搜索。
1、人工智能中的谓词演算及应用,人工智能中的谓词演算及应用,1 学习目标:了解一阶谓词演算的基本体系,掌握命题逻辑和谓词逻辑的归结方法,以及基于归结的提取问题回答的方法,掌握基于规则的正向演绎方法和逆向演绎方法。2 学习指南:本章内容是在一阶谓词逻辑的基础上介绍有关的方法,假定读者已经学习过一阶谓词逻辑的有关内容。在学习的同时,自己尝试重新做一遍例题,将有助于你的学习。在有条件的情况下,可以尝试用程序实现本章介绍的一些主要方法,不过有一定的难度。,人工智能中的谓词演算及应用,3 难重点:命题逻辑的归结方法,谓词逻辑的归结方法,基于归结的问题回答方法,基于规则的正向演绎方法和基于规则的逆向演绎方法。
2、,4.1一阶谓词逻辑基本理论,一、命题与联结词定义4-1 具有确定真值的陈述句,称为命题。 命题若是简单的陈述句,不能分解成更简单的句子,我们称这样的命题为简单命题或原子命题。可以用英文字母P,Q,R,或是带有下标的大写英文字母Pi等表示简单命题,将命题用合适的符号表示,称为命题符号化。 对于简单命题来说,它的真值是确定的,因而又称为命题常项或命题常元。 真值可以变化的简单陈述句称为命题变项或命题变元。,2、联结词(1)“否定”联结词,当命题P为真时,则P为假,反之为真。(2) :“析取”联结词,它表示两个命题存在“或”的关系。(3):“合取”联结词,它表示两个命题之间具有“与”关系。(4):
3、“蕴含”、“单条件”,PQ表示“如果P,则Q”。其中P为前件,Q为后件。(5) :“等价”、“双条件”,P Q表示“P当且仅当Q”。,4.1一阶谓词逻辑基本理论(续),4.1一阶谓词逻辑基本理论(续),二、个体词与谓词1. 个体词定义4-2 个体 (个体词)是指所研究对象中可以独立存在的具体事物、状态或个体之间的关系。在谓词逻辑中,个体可以是常量也可以是变量(变元)。个体常量:表示具体的或特定的个体,用a,b,c,d表示;个体变量:表示抽象的或泛指的个体,用x,y,z表示;个体域(论域):个体变量的(取值范围)值域,常用D表示。个体域可以是有限的也可以是无限的,4.1一阶谓词逻辑基本理论(续)
4、,2. 谓词定义4-3 用于刻画个体的性质、状态或个体之间的关系,称为谓词。谓词一般也用P,Q,R等大写字母表示。3. 函数符号函数符号,又称函词,是从若干个思维对象到某个思维对象的映射的符号。n元函数f(x1,x2,xn)规定为一个映射:f: Dn D,4.1一阶谓词逻辑基本理论(续),谓词与函数的区别:1、谓词的真值是真和假,而函数无真值可言,其值是个体域中的某个个体。2、谓词实现的是从个体域中的个体到T或F的映射,而函数实现的是同一个个体域中从一个个体到另一个个体的映射。3、在谓词逻辑中,函数本身不能单独使用,它必须嵌入到谓词中。,4.1一阶谓词逻辑基本理论(续),4. 谓词(谓词填式)
5、定义4-4 将表示谓词的符号和表示个体的符号组合成一个函词,就称谓词填式,简称谓词。如果没有特殊说明,以后我们提到的谓词均指谓词填式。与命题逻辑相似,谓词逻辑中也有谓词常项和谓词变项之分。含有个体变元的谓词没有真值,但当谓词中的变元都用指定的个体取代时,谓词就有了特定的值T或F。,4.1一阶谓词逻辑基本理论(续),n元谓词:含有n个个体符号的谓词P(x1,x2,xn),它表示一个映射:P:Dn T,F或是(D1D2Dn)T,F谓词的语义是由使用者根据需要人为定义的。谓词中包含的个体数目称为谓词的元数,如:Q(x)是一元谓词,P(x, a)是二元谓词,A(x1,x2,xn)是n元谓词。若X是个体
6、常元、变元或函数,谓词称为一阶谓词;如果某个X本身又是一个一阶谓词,则谓词称为二阶谓词。依次类推。与谓词联系着的n个个体的出现顺序不是任意的。同一谓词的个体变元取值于不同个体域时,所得命题真假值可以不同。,4.1一阶谓词逻辑基本理论(续),三、量词设谓词P(x)表示x是正数,F(x,y)表示x与y是好朋友,则: (x)P(x):表示个体域中所有个体x都是正数。 (x) (y)F(x,y):表示在个体域中所有个体x,都存在个体y,x与y是好朋友。,4.1一阶谓词逻辑基本理论(续),四、 谓词公式项:单独一个个体符号(包括常量和变量)是项;若t1,tn是项,则f(t1,tn)是项;所有项由上述两规
7、则生成。原子公式:若t1,tn是项,P是n元谓词符号,则单独一个谓词P(t1,tn)称为原子谓词公式;n=0时退化为原子命题公式。简称原子,4.1一阶谓词逻辑基本理论(续),定义4-5 下述规则得到谓词演算的合式公式:(1) 单个谓词是合式公式,称为原子谓词公式;(2) 若A是谓词公式,则 A也是合式公式;(3) 若A,B都是合式公式,则AB,AB,AB,A B也都是合式公式;(4) 若A是合式公式,x是任一个体变元,则 (x)A,(x)A也都是合式公式。,4.1一阶谓词逻辑基本理论(续),2. 公式的解释在命题逻辑中,对命题公式中各个命题变元的一次真值指派称为命题公式的一个解释。一旦解释确定
8、,根据各联结词的定义就可求出命题公式中真值(T或F)。定义4-6 解释I有四个要素:(1) 给出非空论域D;(2) 对公式G,对每个常量指派D中的一个元素;(3) 对公式G,对每个n元谓词指派一个Dn T,F的映射;(4) 对公式G,对每个n元函数指派一个Dn D的映射。,4.1一阶谓词逻辑基本理论(续),5 谓词公式的永真性与可满足性定义4-7 如果谓词公式P对于个体域上的任何一个解释都取得真值,则称P在D上是永真的,换句话说,P在每一个非空个体域上均永真,则称P永真。定义4-8 对于谓词公式P,在个体域D中,至少存在一个解释使得公式P在此解释下真值为T,则公式P是可满足的或相容的。定义4-
9、9 如果谓词公式P对个体域D上任何一个解释都取得真值F,则称P在D上永假的,又称为不可满足性或不相容性的。,4.1一阶谓词逻辑基本理论(续),定义4-10 若公式G在解释I下为T,即取值为真,则称解释I满足公式G,或称解释I是G的一个模型。对于公式集,可以看成是其中的每个公式G的合取,即=G1G2Gn,若G1,G2,Gn皆为真,则其合取亦为真,故定义在公式G上的定义都可推广到公式集,也是适用的。,4.1一阶谓词逻辑基本理论(续),6 谓词公式的等价性与永真蕴含性 推理规则(1) P规则:在推理的任何步骤上都可以引入前提。(2) T规则:推理时,如果前面步骤中有一个或多个公式永真蕴含公式S,则可
10、以把S引入推理过程中。(3) CP规则:如果能从R和前提集合中推出S来,则可以从前提集合推出RS来。(4) 反证法:P Q,当且仅当,P Q F ,即Q为P的逻辑结论,当且仅当P Q是不可满足的。定理4-1 为P1,P2,Pn的逻辑结论,当且仅当(P1P2P3Pn)是不可满足的。,4.1一阶谓词逻辑基本理论(续),定义1:谓词公式X是谓词公式A的一部分,则称X为A的子公式。若子公式为( X)P(X)或 ( X)P(X),则称X为指导变元,P(X)为相应量词的作用域或辖域。在辖域中X的所有出现称为X在公式A中的约束出现(即X为相应量词的指导变元所约束),A中不是约束出现的其它变元称为自由变元。定
11、义2:设X是谓词合式公式A的一个个体变元,若以y代替x后不产生变元的新的约束出现,则称 A(X)关于y是自由的。,4.1一阶谓词逻辑基本理论(续),定理1:设X是谓词公式A的一个个体变元,A的论域为D,A(x)关于y是自由的,则 (x)P(x)=P(y) 特例: (x)P(x)=P(X) 上述公式称为全称固化。 定理2:设X是谓词公式A的一个个体变元,A的论域为D,A(x)关于y是自由的,则 (x)P(x)=P(y),其中y是个体域中某一个可使P(y)为真的个体。,4.1一阶谓词逻辑基本理论(续),6 谓词公式的等价性与永真蕴含性定义4-11 设P与Q是两个谓词公式,D是它们共同的个体域,若对
12、于D上的任何解释,P和Q都有相同的真值,则称P与Q在个体域D上是等价的,如果D是任意个体域,则称P和Q是等价的,记作 P Q。 定义4-12 对于谓词公式P和Q,如果PQ永真,则称P永真蕴含Q,且称Q为P的逻辑结论,称P为Q的前提,记作P Q。,4.1一阶谓词逻辑基本理论(续),例:证明(PQ)R)(RP)(SP) T,4.1一阶谓词逻辑基本理论(续),7 谓词公式的范式(1). 前束范式定义4-13 设F为一谓词公式,如果其中的所有量词均非否定地出现在公式的最前面,且它们的辖域为整个公式,则称F为前述范式。一般地,前束范式可写成(Q1x1)(Qnxn)M(x1,xn)其中,Qi(i1,2,n
13、)为前缀,它是一个由全称量词或存在量词组成的量词串,M(x1,xn)为母式,它是一个不含任何量词的谓词公式。,4.1一阶谓词逻辑基本理论(续),(2). Skolem范式定义4-14 如果前束范式中所有的存在量词都在全称量词之前,则称这种形式的谓词公式为Skolem范式。求该范式方法:把公式变换成等价的前束范式;把不含量词的母式变换成等价的合取范式;消去所有存在量词:若不受全称量词约束,用母式中没有的常量符号代换;若受全称量词约束,用母式中没有的函数来代换;,4.1一阶谓词逻辑基本理论(续),3. 范式的求解对任一合式公式可通过以下步骤化成前束范式:(1) 消去多余的前束(量词)。这在化简过程
14、都要随时注意到,因为可能出现母式中没有其前束中相对应的约束变元,因而这个前束是多余的,应及时消去。(2) 消去蕴涵符号(“”联结词)。反复使用具有“”联结词的等值公式,把公式中所有的“”都消去。(3) 内移否定词“”的辖域范围。反复使用摩根定律和量词互换式,把否定词标到只作用于原子公式为止。(4) 变量标准化。对变量作必要的换名,使每一量词只约束一个唯一的变量名。由于变量名可任意设定,因而该过程不影响合式公式的真值。(5) 把所有量词都集中到公式左面,移动时不要改变其相对顺序。,4.1一阶谓词逻辑基本理论(续),置换(substitution):,一个有序对的集合s=ti/vi(i=1, 2,
15、 n)称为代换。其中vi(i=1, 2, . n)是互不相同的变量,ti(i=1, 2, . n)是不同于vi的项,可以是常量、函数,或者其他的变量。当ti都是基项时,代换称为基代换。不含任何元素的代换称为空代换。它是一个空集,记作。,置换s表示将公式(表达式)中的所有变量vi用项ti代替。对公式E施以置换s,记作Es。Es称作公式E的代换实例。一个公式的任何代换实例都是原公式的逻辑结论。例:设有置换s=z/x, a/y,则:Px, f(y), bs=Pz, f(a), b。这里x被换成了z,y被换成了a。,定义:设=t1/x1,t2/x2,tn/xn,=u1/y1,u2/y2um/ym是两个
16、代换。与的复合代换,记作,是由下列集合t1/x1,t2/x2,tn/xn,u1/y1,u2/y2 um/ym 删除所有满足ti=xi的元素以及所有yi出现在x1,x2,xn中的元素得到的集合。例:设=f(y)/x,z/y, =a/x,b/y,y/z复合代换一般不满足交换律。,合一(Unify):,设有公式的集合Ei(i=1, 2, ., m),如果存在一个置换s,使得这m个公式被施以s以后,变得完全一样了,则称这m个公式是可合一的,置换s是它们的合一者。例:设有公式集P(x, f(y), b), P(z, f(b), b)和置换s1=a/x, b/y, a/z,由于:P(x, f(y), b)
17、s=P(a, f(b), b)P(z, f(b), b)s=P(a, f(b), b)所以公式集P(x, f(y), b), P(z, f(b), b)是可合一的,置换s1=a/x, b/y, a/z是它们的合一者。,最一般合一者(mgu):,一般来说,一个公式集的合一者不是唯一的。如s2=z/x, b/y和s3=x/z, b/y都是公式集P(x, f(y), b), P(z, f(b), b)的合一者。对于一个公式集来说,如果存在几个合一者,则其中置换数最少、限制最少、产生的例最具一般性的置换称为最一般合一者(mgu)。如在上例中,置换s1=a/x, b/y, a/z产生的例为P(a, f(
18、b), b),置换s2=z/x, b/y产生的例为P(z, f(b), b)。对于置换s1,置换数为3,而置换s2的置换数为2。相对于例P(a, f(b), b)来说,例P(z, f(b), b)含有一个变量,因此更具一般性。实际上置换s2就是上例公式集的最一般合一者,即mgu。置换s3=x/z, b/y也是该公式集的mgu。可见mgu也同样不是唯一的。,一致化算法,定义:设E=E1,E2,Ek是非空表达式的集合。从E中的各表达式的第一个符号起同时向右比较,直至发现第一个彼此不尽相同的符号止。再从各表达式的这一符号开始,取出相应表达式的最大子表达式,以这些不尽相同的最大子表达式为元素组成的集合
19、称为E的分歧集。例:计算E=P(x,f(y,z),P(x,f(g(a),h(b)的分歧集。,一致化算法: 设E是需要一致化的表达式集合,W是用来记录E或E的代换实例集,D用来记录W的分歧集,用来记录代换。1、置W=E,=。2、若W中只有一个表达式,则算法终止, 就是E的最广通代;否则求出W的分歧集D。3、若D中存在两个元素v和t,其中v是变量,t是项且t中不出现v,则转第4步;否则算法终止,E的通代不存在,即不可一致化。4、置= t/v; 置W=W t/v。转第2步,4.2 确定性推理,推理是指按照某种策略从已知事实出发去推出结论的过程。推理所用的事实可分为两种情况,一种是与求解问题有关的初始
20、证据,另一种是推理过程中所得到的中间结论。通常,智能系统的推理过程是通过推理机来完成的。所谓推理机就是智能系统中用来实现推理的那些程序。,二 推理方法及分类1. 按推理的逻辑基础分类 (1) 演绎推理 演绎推理是从已知的一般性知识出发,去推出蕴含在这些已知知识中的适合于某种个别情况的结论。它是一种由一般到个别的推理方法,其核心是三段论,即假言推理、拒取式和假言三段论。,4.2 确定性推理 (续),常用的三段论是由一个大前提、一个小前提和一个结论三部分组成的。其中,大前提是已知的一般性知识或推理过程得到的判断;小前提是关于某种具体情况或某个具体实例的判断;结论是由大前提推出的,并且适合于小前提的
21、判断。,4.2 确定性推理 (续),(2) 归纳推理 归纳推理是从一类事物的大量特殊事例出发,去推出该类事物的一般性结论。它是一种由个别到一般的推理方法。归纳推理的基本思想是:先从已知事实中猜测出一个结论,然后对这个结论的正确性加以证明确认,数学归纳法就是归纳推理的一种典型例子。 对于归纳推理,如果按照所选事例的广泛性可分为完全归纳推理和不完全归纳推理;如果按照推理所使用的方法可分为枚举归纳推理、类比归纳推理、统计归纳推理和差异归纳推理等。,4.2 确定性推理 (续),所谓完全归纳推理是指在进行归纳时需要考察相应事物的全部对象,并根据这些对象是否都具有某种属性,来推出该类事物是否具有此属性。
22、所谓不完全归纳推理是指在进行归纳时只考察了相应事物的部分对象,就得出了关于该事物的结论。 所谓枚举归纳推理是指在进行归纳时,如果已知某类事物的有限可数个具体事物都具有某种属性,则可推出该类事物都具有此种属性。所谓类比推理是指在两个或两类事物有许多属性都相同或相似的基础上,其它属性上也相同或相似的一种归纳推理。,4.2 确定性推理 (续),(3) 默认推理 默认推理是在知识不完全的情况下假设某些条件已经具备所进行的推理,因此也称为缺省推理。在推理过程中如果发现原先的假设不正确,就撤销原来的假设以及由此假设所推出的所有结论,重新按新情况进行推理。,4.2 确定性推理 (续),(4) 演绎推理与归纳
23、推理的区别演绎推理与归纳推理是两种完全不同的推理。演绎推理是在已知领城内的一般性知识的前提下,通过演绎求解一个具体问题或来证明一个结论的正确性。它所得出的结论实际上早已蕴含在一般性知识的前提中,演绎推理只不过是将已有事实揭示出来,因此它不能增殖新知识。在归纳推理中,所推出的结论是没有包含在前提内容中的。这种由个别事物或现象推出一般性知识的过程,是增殖新知识的过程。,4.2 确定性推理 (续),2. 按所用知识的确定性分类 按所用知识的确定性,推理可分为确定性推理和不确定性推理。 所谓确定性推理是指推理所使用的知识和推出的结论都是可以精确表示的,其真值要么为真,要么为假,不会有第三种情况出现。
24、所谓不确定性推理是指推理时所用的知识不都是确定的,推出的结论也不完全是确定的,其真值会位于真与假之间。,4.2 确定性推理 (续),三、推理的控制策略及分类 推理的控制策略又可分为推理策略和搜索策略。其中,推理策略主要解决推理方向、冲突消解等问题,搜索策略主要解决推理线路、推理效果、推理效率等问题。,4.2 确定性推理 (续),四、推理的冲突消解策略在推理的某一步,如果知识库中有多条知识可用,则称发生了冲突。 此时,需要按照某种策略从这多条知识中选择一条最佳知识用于推理,称这种解决冲突的过程为冲突消解。冲突消解所用的策略则称为冲突消解策略。,4.2 确定性推理 (续),常用的冲突消解策略有以下
25、: 1. 特殊知识优先2. 新鲜知识优先3. 差异性大的知识优先4. 领域特点优先5. 上下文关系优先6. 前提条件少者优先,4.2 确定性推理 (续),4.3 自然演绎推理,从一组已知为真的事实出发,直接运用经典逻辑中的推理规则推出结论的过程称为自然演绎推理。在这种推理中,最基本的推理规则是三段论推理,它包括假言推理、拒取式推理、假言三段论等。,例:设已知下述事实和规则A BACBCDDQ求证:Q为真,4.3 自然演绎推理,例:设已知如下事实:1)凡是容易的课程小王(wang)都喜欢2)C班的课程都是容易的3)ds是C班的一门课程证明:小王喜欢ds这门课程。,4.3 自然演绎推理(续),4.
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 知识 一阶 谓词 逻辑 表示 课件
链接地址:https://www.31ppt.com/p-1585320.html