精品大学课件--人工智能导论-马少平(清华)--人工智能27217.pptx
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《精品大学课件--人工智能导论-马少平(清华)--人工智能27217.pptx》由会员分享,可在线阅读,更多相关《精品大学课件--人工智能导论-马少平(清华)--人工智能27217.pptx(48页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第四章 谓词演算及应用是一种形式语言,具有严密的理论体系是一种常用的知识表示方法例:City(北京)City(上海)Age(张三,23)(x)(y)(z)(F(x,y)F(y,z)GF(x,z)4.1 归结原理归结原理是一种定理证明方法,1965年由Robinson提出,从理论上解决了定理证明问题。子句集无量词约束元素只是文字的析取否定符只作用于单个文字元素间默认为和取例:I(z)R(z),I(A),R(x)L(x),D(y)化子句集的方法例:(z)(x)(y)(P(x)Q(x)R(y)U(z)1,消蕴涵符理论根据:a b=a b(z)(x)(y)(P(x)Q(x)R(y)U(z)2,移动否定
2、符理论根据:(a b)=a b (a b)=a b(x)P(x)=(x)P(x)(x)P(x)=(x)P(x)(z)(x)(y)(P(x)Q(x)R(y)U(z)化子句集的方法(续1)3,变量标准化即:对于不同的约束,对应于不同的变量(x)A(x)(x)B(x)=(x)A(x)(y)B(y)4,量词左移(x)A(x)(y)B(y)=(x)(y)A(x)B(y)5,消存在量词(skolem化)原则:对于一个受存在量词约束的变量,如果他不受全程量词约束,则该变量用一个常量代替,如果他受全程量词约束,则该变量用一个函数代替。(z)(x)(y)(P(x)Q(x)R(y)U(z)=(x)(P(x)Q(x
3、)R(f(x)U(a)化子句集的方法(续2)6,化为合取范式即(ab)(cd)(ef)的形式 (x)(P(x)Q(x)R(f(x)U(a)=(x)(P(x)Q(x)R(f(x)U(a)=(x)P(x)R(f(x)U(a)Q(x)R(f(x)U(a)7,隐去全程量词 P(x)R(f(x)U(a)Q(x)R(f(x)U(a)化子句集的方法(续3)8,表示为子句集 P(x)R(f(x)U(a),Q(x)R(f(x)U(a)9,变量标准化(变量换名)P(x1)R(f(x1)U(a),Q(x2)R(f(x2)U(a)定理:若S是合式公式F的子句集,则F永假的充要条件是S不可满足。S不可满足:若nilS,
4、则S不可满足。证明的思路:目标的否定连同已知条件一起,化为子句集,并给出一种变换的方法,使得 S S1 S2.Sn同时保证当Sn不可满足时,有S不可满足。4.2 归结方法(命题逻辑)设子句:C1=LC1C2=(L)C2则归结式C为:C=C1 C2定理:子句集S=C1,C2,Cn与子句集S1=C,C1,C2,Cn的不可满足性是等价的。其中,C是C1和C2的归结式。归结的例子设公理集:P,(PQ)R,(ST)Q,T求证:R子句集:(1)P(2)PQR(3)SQ(4)TQ(5)T(6)R(目标求反)化子句集:(PQ)R=(PQ)R=PQR(ST)Q=(ST)Q=(ST)Q=(SQ)(TQ)=SQ,T
5、Q子句集:(1)P(2)PQR(3)SQ(4)TQ(5)T(6)R(目标求反)归结:(7)PQ (2,6)(8)Q (1,7)(9)T (4,8)(10)nil (5,9)4.3 谓词逻辑的归结原理问题:如何找归结对例:P(x)Q(y),P(f(y)R(y)P(A)Q(y),P(f(y)R(y)基本概念置换s=t1/v1,t2/v2,tn/vn对公式E实施置换s后得到的公式称为E的例,记作Es。例:s1=z/x,Ay,则:Px,f(y),Bs=Pz,f(A),B合一如果存在一个S置换,使得Ei中 E1s=E2s=E3s=Ens,则称Ei是可合一的。S为Ei的合一者。例:P(x,f(y),B),
6、P(z,f(B),B)置换s=A/x,B/y,A/z是一个合一者,因为:P(x,f(y),B)s=P(A,f(B),B)P(z,f(B),B)s=P(A,f(B),B)置换s=z/x,B/y和置换s=x/z,B/y也都是合一者。结论:合一者不唯一。最一般合一者(mgu)置换最少,限制最少,产生的例最具一般性。如前面的例子:P(x,f(y),B),P(z,f(B),B)对于置换A/x,B/y,A/z,产生的例是:P(A,f(B),B)对于置换=z/x,B/y,产生的例是:P(z,f(B),B)mgu也不是唯一的。合一算法例:P(x,x,B),P(f(y),f(B),y)前缀表示:(P x x z
7、)(P(f y)(f B)y)置换:(f y)/x(P(f y)(f y)z)(P(f y)(f B)y)置换:B/y,并使得(f B)/x(P(f B)(f B)z)(P(f B)(f B)B)置换:B/z得到置换:(f B)/x,B/y,B/z置换后的结果:(P(f B)(f B)B)谓词逻辑的归结方法对于子句C1L1和C2L2,如果L1与L2可合一,且s是其合一者,则(C1C2)s是其归结式。例:P(x)Q(y),P(f(z)R(z)=Q(y)R(z)归结举例设公理集:(x)(R(x)L(x)(x)(D(x)L(x)(x)(D(x)I(x)求证:(x)(I(x)R(x)化子句集:(x)(
8、R(x)L(x)=(x)(R(x)L(x)=R(x)L(x)(1)(x)(D(x)L(x)=(x)(D(x)L(x)=D(x)L(x)(2)(x)(D(x)I(x)=D(A)I(A)=D(A)(3)I(A)(4)目标求反:(x)(I(x)R(x)=(x)(I(x)R(x)=(x)(I(x)R(x)=I(x)R(x)(5)换名后得字句集:R(x1)L(x1)D(x2)L(x2)D(A)I(A)I(x5)R(x5)例题得归结树R(x1)L(x1)D(x2)L(x2)D(A)I(A)I(x5)R(x5)I(A)I(x5)R(x5)R(A)A/x5 R(x1)L(x1)L(A)A/x1 D(x2)L(
9、x2)D(A)A/x2 D(A)nil4.4 基于归结的问答系统例:已知:(x)AT(John,x)AT(Fido,x)AT(John,School)求证:(x)AT(Fido,x)子句集:AT(John,x1)AT(Fido,x1)AT(John,School)AT(Fido,x2)AT(Fido,x2)AT(John,x1)AT(Fido,x1)子句集:AT(John,x1)AT(Fido,x1)AT(John,School)AT(Fido,x2)AT(John,x2)x2/x1AT(John,School)nilSchool/x2AT(Fido,x2)AT(Fido,x2)AT(Fido
10、,School)提取回答的过程先进行归结,证明结论的正确性;用重言式代替结论求反得到的子句;按照证明过程,进行归结;最后,在原来为空的地方,得到的就是提取的回答。修改后的证明树称为修改证明树例:猴子摘香蕉问题c问题的表示已知:1,ON(s0)2,(x)(s)(ON(s)AT(box,x,push(x,s)3,(s)(ON(climb(s)4,(s)(ON(s)AT(box,c,s)HB(grasp(s)5,(x)(s)(AT(box,x,s)AT(box,x,climb(s)求解:(s)HB(s)问题的子句集1,ON(s0)2,ON(s1)AT(box,x1,push(x1,s1)3,ON(c
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 精品 大学 课件 人工智能 导论 马少平 清华 27217
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内