您好、欢迎来到现金彩票网!
当前位置:刘伯温四肖中特料 > 推理子句 >

人工智能之谓词演算ppt

发布时间:2019-08-25 18:57 来源:未知 编辑:admin

  1.本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的反悔问题本站不予受理。

  第2讲 基于谓词逻辑的机器推理 一阶谓词逻辑 归结演绎推理 归结原理的应用 Horn子句与Prolog程序设计 第一节 一阶谓词逻辑 命题:凡可确定真假的陈述句称为命题 可以取值“真”(T)或“假”(F) 在一定的条件下,只能取其中一个值 例: (1)北京是中国的首都√ (2)3 + 2 10× (3)1 + 11 = 100(根据制数) (4)禁止吸烟 (祈使句) (5)本命题是假的 (悖论) 谓词:是用来刻画个体词的性质或个体词之间的关系的词(带参量的命题叫谓词) n 元谓词,P(x1, x2, x3, …, xn) P 是谓词符号,代表一个确定的特征(一个参量)或关系(多个参量) x1, x2, x3, …, xn 称为参量或项(个体常元或个体变元) 论述域(个体域):个体变元的取值范围 例: 北京是一个城市 —— CITY(北京) x 是人 —— HUMAN(x) A是B的兄弟 ——兄弟(A,B) x 大于 y —— G(x,y) 不带个体变元的谓词公式叫命题,命题是谓词公式的特例 逻辑连接词:研究单个谓词是不够的,还必须研究多个谓词之间的关系,这需要引入逻辑连接词 ?:否定词 ?A读为“非A”,当A为真时, ?A为假,当A为假时, ?A为真 ∧:合取词 A ∧B读为“A并且B”,当且仅当A和B都为真时, A ∧B为真,否则A ∧B为假 ∨:析取词 A ∨ B读为“A或者B”,当且仅当A和B都为假时, A ∨ B为假,否则A ∨ B为真 →:蕴涵词 A → B读为“若A则B”,当且仅当A为真,且B为假时, A → B为假,否则A → B为真 在A → B中,A称为前件,B称为后件 ?:等值词 A ? B读为“A等值于B”,当且仅当A和B同为真或同为假时, A ? B为真,否则A ? B为假 量词:有些陈述句包含表示数量的词,如“所有”、“任一”、“存在”、“至少有一个”等,为了表示这样的陈述句,需引入新的符号,称为量词 全称量词 ? ( ? x )表示 “ 对于所有的 x … ” 例: 凡是人都有名字 —— ( ? x )(M (x) → N(x)) ( ? x )A(x)? A(a1)∧ A(a2) ∧… ∧ A(an),若论域为有限集合, 且a1、 a2、 … 、an是论域中的所有个体 存在量词 ? ( ? x )表示 “ 对于某个 x … ” 例: 存在不是偶数的整数 —— ( ? x )(G (x) ∧ ? E(x)) ( ? x )A(x)? A(a1)∨ A(a2)∨… ∨ A(an) 例:见P56例1—3 项: ( P64 定义1) (1)个体常元和个体变元都是项 (2)f (t1, t2, …, tn)是项,f 是 n 元函数, t1, t2, …, tn 是项 (3)只有有限次使用(1)、(2)得到的符号串才是项 原子公式: ( P64 定义2) 设 P 为 n 元谓词符号, t1, t2, …, tn 是项,则P( t1, t2, …, tn )称为原子谓词公式,简称原子公式 谓词公式: ( P56 定义3) (1)原子公式是谓词公式 (2)若A、B是谓词公式,则 A∧B、A∨B、? A、A→B、A? B、 ? x A、 ? x A也是谓词公式 (3)只有有限次应用(1)、(2)生成的公式才是谓词公式 谓词公式又称为谓词逻辑中的合式公式,记为 Wff (well-formed formula) 几个概念: 辖域(P57):紧接于量词之后被量词作用的(说明的)谓词公式称为该量词的辖域 指导变元、约束变元和自由变元 ( P57) 改名规则( P57),保证一个变元或者是约束变元,或者是自由变元 例: ? x (H(x)→ G(x, y)) ∧ ? x A(x) ∧ B(x) 合取范式: ( P58定义4) A为合取范式,B1 ∧ B2 ∧ … ∧ B n ,其中 Bi 形如L1 ∨ L2 ∨ … ∨ Lm, L j为原子公式或其否定 例:(P(x) ∨ Q(y)) ∧ ( ? P(x) ∨ Q(y) ∨ R(x,y)) ∧… 任一谓词公式均可化为与之等价的合取范式,但一般不唯一 析取范式: ( P66 定义5) A为析取范式,B1 ∨ B2 ∨ … ∨ B n ,其中 Bi 形如L1 ∧ L2 ∧ … ∧ Lm, L j为原子公式或其否定 例:(P(x) ∧ Q(y)) ∨ ( ? P(x) ∧ Q(y) ∧ R(x,y)) ∨ … 任一谓词公式均可化为与之等价的析取范式,但一般不唯一 谓词公式的永真(有效)、永假(不可满足)、可满足: ( P58定义6、7) 与个体域有关 谓词公式之间的关系 常用逻辑等价式 P59表3.1 注意?与?的区别,?是等价符号,说明两个谓词公式之间的等价性,?是逻辑连接词,是谓词公式的组成部分 常用逻辑蕴涵式 P60 表3.2 注意?与?的区别, ?是推导符号,说明由?左边的谓词公式可以推导出?右边的谓词公式, ?是逻辑连接词,是谓词公式的组成部分 自然演绎推理: (1)将自然语言命题转化为谓词公式 (2)利用上面的逻辑等价式和逻辑蕴涵式,可以进行推理,得出一些隐含在谓词公式中的结论 例:P61 例4-6 自然演绎推理实施困难,推理规则太多、应用规则需要很强的模式识别能力、中间结论呈指数增长 引入新的推理技术——归结演绎推理技术 归结——消解(Resolution),由Robinson于1965年提出,大大推动了自动定理证明的发展 练习: 1、设已知以下事实: A B A→C B∧C→D D→Q 求证:Q为真。 证明: 因为 A,A→C ? C B,C ? B ∧C B∧C,B∧C→D ? D D,D→Q ? Q 所以 Q为线、设已知如下事实: (1)凡是容易的课程小王都喜欢。 (2)C班的课程都是容易的。 (3)ds 是C班的一门课程。 求证:小王喜欢 ds 这门课程。 证明: 事实 ? x ( EASY(x)→LIKE(Wang,x)) ? x (C(x)→ EASY(x)) C(ds) LIKE(Wang,ds) 因为 ? x (C(x)→ EASY(x)) 所以 C(ds)→ EASY(ds) 所以 C(ds), C(ds)→ EASY(ds)? EASY(ds) 因为 ? x ( EASY(x)→LIKE(Wang,x) ) 所以 EASY(ds) →LIKE(Wang,ds) 所以 EASY(ds), EASY(ds)→LIKE(Wang,ds) ? LIKE(Wang,ds) 第二节 归结演绎推理 建立子句集 文字、子句、空子句 (P62 定义1) 建立谓词公式 G 的子句集合 (P62定义2) 例:P62例3.7 例:P63 例2 有关消去存在量词 子句集中各子句的关系是 合取 ∧ 经过变换后的子句集 S ,与谓词公式 G 并不等价 子句集的不可满足 (P64 定义3) G不可满足当且仅当S不可满足(P64 定理1),即G永假是S永假的充分必要条件 练习: P93 1、 (1){p(x,y),Q(u,v)} (2){?p(x,y)∨Q(x,y)} (3){P(x,f(x))∨ ?Q(x,f(x))∨R (x,f(x))} (4){?P(x,z)∨Q(x,y)∨R(x,y)} (5){P(a,b,z,f(z),v,g(z,v)), Q(a,b,f(t),s,g(t,s))∨ ? R(a,t,g(t,s))} 命题逻辑中的归结原理 在定理证明系统中,已知一公式集F1,F2,…,Fn,要证明W(定理)是否成立,即要证明W是公式集的逻辑结果,有两种方法: 1、证明 F1 ∧ F2 ∧ … ∧ Fn →W 为永线 ∧ … ∧ Fn ∧ ? W 永假,即要证明对应子句集永假(不可满足) 几个概念:(P64 定义4、5)互补文字、归结式(消解式)、亲本子句、消解基 例:例3.9 归结式是其亲本子句的逻辑结果 P64 定理2 单向推导关系 归结原理: C1 ∧ C2 ? (C1-{L1})∨ (C2-{L2}) 互补文字进行归结得空子句(L ∧ ? L =?),另L ∧ ? L = F(假),故空子句即永假子句 关于消解前后子句集的可满足性 —— P65 推论 (证明略) 故:要证明一子句集永假,可以通过对子句集应用消解原理得到空子句来证明 运用归结原理证明定理的例子:P65 例11、12 * 归结过程可以用一棵 归结演绎树 表示 替换与合一 为了对谓词逻辑的子句集运用消解原理,即在子句集合中寻找含互补文字的子句对,必须对子句进行替换合一操作 替换:P66 定义6 {t1/x1, t2/x2,… ,t n /x n} 对表达式的替换过程 P66 定义7 表达式—— 项、原子公式、文字、子句 两个替换的乘积 P66-67 定义8 一部分仍是θ的替换对,只是θ的项被λ作了替换;另一部分是λ中与θ不同的那些变量对 例:例3.13 替换的乘积满足结合律 合一:P67 定义9 θ是 S 的一个合一 其中S 是一个原子谓词公式集, θ是一个替换 满足 F1θ = F2θ = …=Fnθ 一个公式集的合一一般不唯一 最一般的合一:P67 定义10 σ是 S 的一个合一 对于S 的任何一个合一θ,存在替换λ,使 θ= σ? λ 称σ为S 的最一般(最普通、最简单)合一 MGU 例:例3.14 MGU 的替换限制最少,所产生的例更一般化,这有利于归结过程的灵活使用 一个公式集的最一般合一也可不唯一,如{ P(x),P(y)},{y/x}、 {x/y}都是它的最一般合一 差异集:P67 定义11 针对具有相同谓词名的原子公式集 例:例3.15 合一算法:求非空有限具有相同谓词名的原子公式集的最一般合一 P67-68 合一算法是解决两个表达式匹配的问题,两个表达式都可以含有变量,通过算法求得 MGU 并进行替换后就可以得到匹配的例 例:例16、17 合一定理: P68-69 定理3 可合一公式集一定存在最一般合一,用上述合一算法求得 谓词逻辑中的归结原理 归结过程: 若S 中的两子句间有相同互补文字的谓词,但它们的项不同,则必须找出对应的不一致项 进行变量替换合一操作,使它们的对应项一致 求归结式看能否导出空子句 几个概念:(P69 定义12)谓词逻辑中的二元归结式(二元消解式)、亲本子句、消解文字 例:例18、19 子句用文字的集合表示,各文字之间的关系是 析取 ∨ 首先对子句内部的可合一文字进行合一 因子、单因子 ( P69 定义13) 例:例14 子句的归结(消解)式 ( P69 定义14) 定理:谓词逻辑中的消解式是它的亲本子句的逻辑结果 谓词逻辑中的归结原理:C1 ∧ C2 ? (C1σ- {L1 σ })∪( C2 σ- {L2 σ }) 关于消解前后子句集的可满足性 —— P70 (同命题逻辑) 故:要证明F1 ∧ F2 ∧ … ∧ Fn →W 为永线 ∧ … ∧ Fn ∧ ? W 永假,这又可以通过对对应子句集应用消解原理得到空子句来证明(同命题逻辑) 例:例15、16 定理:归结原理的完备性 ( P71) 练习: P93 3、(1)-(5) 第三节 归结原理的应用 例3.23:P71 例3.24:P72 练习: P94 5、6、 归结策略 计算机实现归结原理的一般算法: 1.将子句集S置入CLAUSES表; 2.若空子句NIL在CLAUSES中,则归结成功,结束。 3.若CLAUSES中存在可归结子句对,则归结之,并将归结式放入CLAUSES中; 4.归结失败,退出。 归结策略的完备性 策略:删除策略、支持集策略、线性归结策略、输入归结策略、单元归结策略、祖先过滤形策略。 归结举例 第四节 Horn子句与Prolog程序设计 子句的蕴含表示 P90 (3-1)—— (3-4、4’、4’’) 蕴含型子句的归结 P90-91 正、负文字归结(在→的两头去找) Horn子句 定义:P91 定义1 蕴含型Horn子句的三种类型:P91 蕴含型Horn子句的归结 例:P91 例1 注意归结顺序 Prolog 程序设计 P30 Prolog 程序的语句均是 Horn 子句 事实——无条件子句 规则——条件子句 问题——目标子句 Prolog 程序 P31-33 Prolog 程序的运行机制 P33-35 SLD归结: 从目标子句开始进行归结 归结顺序是从左到右 控制策略是深度优先 有回溯机制 Prolog 语言的优缺点: 优点:Prolog 语言是一种描述性语言,用 Prolog 语言进行程序设计时,只需要描述待求解问题中的对象以及对象之间的关系的事实和变换规则。从这种意义上说,只需告诉计算机“做什么”,而不是“如何做”,大大提高了程序设计的效率。 缺点: Prolog 语言的解释系统或编译系统都是建立在适合于冯·诺依曼计算机环境下的,最终仍然要转化为纯过程性的机器指令序列来执行。因此显著地增加了软件开销,使其处理速度难以大幅度提高,从而限制了它们的应用范围。 *** 上机环境 Visual Prolog 5.2 * * Sam、Clyde和Oscar是大象。关于它们,我们知道以下事实: 1)Sam是粉红色的; 2)Clyde是灰色的且喜欢Oscar; 3)Oscar是粉红色或者是灰色(但不是两种颜色)且喜欢Sam。 用归结法证明一个灰色大象喜欢一个粉红色大象。 即证明:?x ? y[Gray(x) ∧ Pink(y) ∧ Likes(x,y)] ? ? ? ∧ ? ∨ 谓词: Gray(x), Pink(x), Like(x,y) 事实: 1)Pinky(Sam) 2)Gray(Clyde) ∧Like(Clyde,Oscar) 3)(Gray(Oscar) ∨Pink(Oscar))∧Likes(Oscar,Sam) 子句集:1)Pink(Sam) 2)Gray(Clyde) 3)Like(Clyde,Oscar) 4)Gray(Oscar) ∨Pink(Oscar) 5)Likes(Oscar,Sam) 6) ? Gray(x) ∨ ? Pink(y) ∨ ? Likes(x,y) 归结: 7) ? Gray(Oscar) ∨ ? Pink (Sam ) 5,6得 8) ? Gray(Clyde) ∨ ? Pink(Oscar) 3,6得 9) Pink(Oscar) ∨ ? Pink (Sam ) 4,7得 10) ? Pink(Oscar) 8,2得 11 )? Pink (Sam ) 9,10得 12)NIL 1,10得 ? ? ? ∧ ? ∨ *

http://mojdzwonek.com/tuiliziju/545.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有