您好、欢迎来到现金彩票网!
当前位置:如意彩票 > 非单调推理 >

第三章 谓词逻辑与确定性推理ppt

发布时间:2019-05-26 01:43 来源:未知 编辑:admin

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

  第三章 谓词逻辑与确定性推理 谓词逻辑指基于数理逻辑的表示、推理方法,一阶谓词逻辑是经典的命题逻辑。由于其表示的多为确定性知识,也多用于确定性推理。 §3-1 谓词逻辑基本概念 §3-1 谓词逻辑基本概念 §3-1 谓词逻辑基本概念 §3-1 谓词逻辑基本概念 (2)量词:用于对谓词中的个体约束或规定。分为全称量词?和存在量词? 。 ?x:表示论域中所有的 x 。 ?x:表示论域中存在 x 。 命题(?x )P(x)为真:当且仅当对于论域中的所有x ,都有P(x)为线 ∈D,使得 P(x)为假,那么(?x )P(x)就为假。 命题 (?x )P(x)为线 ∈D,使得 P(x)为真;当且仅当对于论域中的所有x ,都有P(x)为假,那么( ? x )P(x)就为假。 §3-1 谓词逻辑基本概念 定义3 . 项的规则 1)单独一个 个体词是项:t1,t2,t3,…tn 。 2)若 t1,t2,t3,…tn 是项,则函数 f(t1,t2,t3,…tn )也是项。 3)由 1)和 2)生成的表达式也是项。 定义4. 原子谓词公式 若 t1,t2,t3,…tn 是项,P是谓词符号, 则 P(t1,t2,t3,…tn ) 称为原子谓词公式。 定义5. 合式公式 (谓词公式) 1) 原子谓词公式称为合式公式; 2)由~∧∨ → ? 连接的合式公式还是合式公式; 3)由 ? ?约束的合式公式 也称为合式公式。 定义6. 自由变元与约束变元 ? 、?是有辖区的, 受 ? ?约束的变元称为约束变元。 不受它们的约束的变元称为自由变元。 (1) (? x )P(x) , x为约束变元 (2) (? x)(H(x)→ G(x,y)), y为自由变元 (3) (? x)A(x) ∧ B(x) , 只约束 A(x) , 而 B(x)中的 x 仍为自由变元。 谓词逻辑可以表示事物的状态、性质、概念,也可以表示事物之间的因果关系,即规则。 对于事实的知识用~∧∨ 连接的谓词公式表示。 对于事物的因果关系通常用蕴含→式表示。 x → y 表示“如果x , 则y” 使用谓词逻辑进行知识表示时,一般先根据题意定义谓词, 然后在根据表达的需要使用适当的连词和量词把谓词连接起来构成 谓词公式。 例3.1 所有的学生都有某教材。 STUDENT(x) :表示x是学生 HASMATERIAL(x,y):表示x有教材y 题目所表达的知识可以表示为: (? x) (?y ) (STUDENT(x)→ HASMATERIAL(x,y)) 例3.2 所有整数 不是偶数 就是 奇数。 I(x) :表示x是整数 E(x):表示x是偶数 O(x):表示x是奇数 题目所表达的知识可以表示为: (? x) (I(x)→ E(x)∨ O(x)) 如果对逻辑的某些外延扩展后,则可把大部分的知识表达成一阶谓词逻辑的形式。 例如:王是计算机系的学生,李明是王的同班同学,他们系系的学生都喜欢编程。 定义谓词: COMPUTRE(x) :x是计算机系的学生 CLASSMATE(x,y):x是y的同班同学 LIKE (x,y) : x喜欢y 。 题目的 知识表示: COMPUTRE(wang) CLASSMATE(liming,wang) (? x) (COMPUTRE(x)→ LIKE(x,programming) ) §3-2 谓词逻辑的问题表示 例 3.3 机器人要把 a 处桌子上的箱子搬到 b 处的桌子上,再回到 c 处。 谓词: TABLE(x):x是桌子 EMPTY( y ) :y手中是空的 AT ( y,z ):y在z位置附近 HOLD ( y,w ):y拿着 w ON ( w,x ):w在桌子 x上 其中 x ∈{a,b} ,y ∈ {robot} , z ∈ {a,b,c}, w ∈{box} 增加动作谓词: 1) Goto( x,y ) :从 x 走到 y 2) Pickup( x ) : 在 x 处拿起盒子 3) Setdown ( x ) : 在x处放下盒子 分别对应的条件: 1)AT(Robot,x) 2) ON(box,x),TABLE (x), AT (Robot,x),EMPTY ( Robot ) 3) AT(Robot,x) ), TABLE(x), HOLD( Robot ,x) AT(Robot,c) EMPTY(Robot ) ON(box,a) TABLE(a) TABLE(b) 表达知识形式化能够自然、明确、精确。 一阶谓词逻辑具有完备的逻辑推理算法。 不能表达不精确的、模糊的知识。 形成知识库较困难,当知识系统较大时,存在组合爆炸的问题、推理的效率底。 §3-3 推理基础 (1) 推理:由事实出发推出结论的过程 (2)推理从逻辑基础出发分:演义推理和归纳推理 演义推理:有一般到特殊,核心是三段论。 归纳推理:由特殊到一般:枚举、统计、类比。 (3)按所用的事实:确定性推理和非确定性推理。 (4)按结论的出现情况:单调性推理和非单调推理。 (5)按控制策略:正向推理、逆向推理与混合推理。 (6)按使用知识策略:启发式推理和非启发式推理。 §3-3 推理基础 §3-3 推理基础 对谓词公式中的个体变项、函数变项、谓词变项用指定的常项去替代,所得到的结果称为对谓词公式的一个解释或赋值 。 在有限个体域下,可按下列规则消去量词。如 §3-3 推理基础 §3-3 推理基础 定义8. 设P为谓词公式,对于非空个体域D上的任何解释都取得真值 T ,则称P在D上永真。如果P在任何非空个体域上均为 T ,则称P永线. 设P为谓词公式,如果至少存在D上的一个解释,使得P在该解释下取真值 T ,则称公式P在D上是可满足的。 定义10. 设P为谓词公式,对于非空个体域D上的任何解释都取得真值 F ,则称P在D上永假。如果P在任何非空个体域上均为F ,则称P永假。也称为不可满足性或不相容性。 §3-3 推理基础 §3-3 推理基础 分配率:P ∨ ( Q ∧ R ) = ( P ∨ Q )∧ ( P ∨ R ) ; P ∧ ( Q ∨ R ) = ( P ∧ Q ) ∨ ( P ∧ R ) 摩根定理: ~ ( P ∨ Q ) = ~ P ∧ ~ Q ; ~ ( P ∧ Q ) = ~ P ∨ ~ Q 补余率: ~ P ∨ P = T (永真) ; ~ P ∧ P = F (永假) 连词归化: ( P → Q ) = ~ P ∨ Q ( P ? Q ) = ( P → Q ) ∧ ( Q → P ); ( P ? Q ) = ( P ∧ Q ) ∨ ( ~ P ∧ ~ Q ) 量词转换: ~ ( ?x)P(x)= ( ?x) ~ P(x) ; ~ ( ?x)P(x) = ( ?x) ~ P(x) 量词分配: ( ?x)( P ∧ Q ) = ( ?x)P ∧ ( ?x)Q ; ( ?x)( P ∨ Q ) = ( ?x)P ∨ ( ?x)Q 2) 永线. 设 对于谓词公式 P 和 Q,如果P → Q为永真,则称P 永真蕴含 Q ,且称P 为 Q 的前提,且称Q 为 P的逻辑结论。记作: P =Q 。常用的永真蕴含式: 化简式: P ∧ Q = P ; P ∧ Q = Q 附加式: P = P ∨ Q ; Q = P ∨ Q 析取三段论: ~ P , P ∨ Q = Q 假言推理: P ,P → Q = Q 拒取式: ~ Q , P → Q = ~P 假言三段论: P → Q ,Q → R = P → R 二难推理: P ∨ Q ,P → R ,Q → R = R 全称固化:( ? x)P(x)= P(y) 存在固化:( ? x)P(x)= P(c) 3) 变元替换 一般替换:新变元、辖区不便; 1.全称固化:( ? x)P(x)= P(y) :y是个体域中的任一个体,用此永真可以消去谓词中的全称量词(US规则)。 ( ? x)P(x)= P(c) 2.存在固化:( ? x)P(x)= P(c) :c是个体域中使p(x)为真的个体。 用于消去存在量词(ES规则) 。 3.全称推广规则:P( x ) = ( ? y )P( y ) :由此引起的其他位置上的x也是不自由的(UG规则) 。 4. 存在量词附加规则 (EG规则) P( c) = ?(x)P(x) 一般:abcde表示个体常量, tuvwxyz表示变量 例8,证明 证明: ⑴ P ⑵ T ⑴ ES ⑶ P ⑷ T ⑶ US ⑸ T ⑵⑷假言推理 ⑹ T ⑸ 化简 ⑺ T ⑵⑹ 合取 ⑻ T⑺ EG 由已知事实出发,根据经典的逻辑推理规则推出结论的过程称为演绎推理。最基本的推理规则是三段论:假言推理、拒取式推理、假言三段论。 在假言推理 P ,P → Q = Q 中,说明当P → Q 为真,前件为线 已知: A,B,A→C, B ∧ C→D, D→Q 求证: Q = T(为真) 证明: A,A→C = C B,C = B ∧ C 引入合取词 B ∧ C, B ∧ C→D =D D,D→Q = Q 得证# 例3.9 已知事实: 凡是编程课,王程都喜欢; 所有程序设计语言课都是需要编程的课; C语言课是一门程序设计语言课 求证:王程喜欢C语言课 证明:定义谓词: Prog(x) x是需要编程的课 Like(x,y) x喜欢y Lang(x) x是一门程序设计语言课 事实描述: Prog(x)→ Like(Wangch ,x) (?x )( Lang(x) → Prog(x) ) Lang(C) 推理:Lang(y) → Prog(y) 全称固化 Lang(C),Lang(y)→Prog(y)= Prog(C) C需要编程 Prog(C),Prog(C)→Like(Wangch ,C) = Like(Wangch ,C ) 归结演绎推理是基于一种称为归结原理(亦称消解原理principle of resolution)的推理规则进行推理的方法。是由鲁滨逊(J.A.Robinson)于1965年在海伯伦(Herbrand)理论上建立首先提出。它是谓词逻辑中一个相当有效的机械化推理方法。被认为是自动推理,特别是定理机器证明领域的重大突破。 基本思想:根据前提 P 和结论 Q ,要证明 P→ Q 永真,对谓词逻辑来讲就要证明其在任何一个非空的个体域上永真。 要证明 P→ Q 永真,只要证明 P ∧~ Q 不可满。 连词归化: ( P → Q ) = ~ P ∨ Q 摩根定理: ~ (~ P ∨ Q ) = P ∧~ Q 范式是是公式的标准形式,公式要转换为等价的范式,方便一般性的处理。根据量词的情况分为两种:前束范式 和Skolem范式。 1)前束范式 定义12. 设M是谓词公式,如果其中所有的量词均非否定地约束整个公式,则称 P 为前束范式。一般地写成: (Q1)(…)( Qn ) M( x1 ,x2 ,…, xn ) 其中: Qi (i=1,2…n)为前缀, M( x1 ,x2 ,…, xn )为母式。 例如: (? x)(? y)( ? z ) [P(x)∧ Q(y,z )∨ R(x,z)] 2) Skolem 范式 在前束范式中,如果所有的存在量词 都在全称量词之前,则称 该谓词公式为Skolem 范式。例如: (? x)(? y)(? z ) [ P(x) ∨ Q(y,z ) ∧ R(x,z)] 可以证明:任何谓词公式均可化为Skolem 范式 推理过程中,在不同谓词公式可能出现谓词名相同,个体不同的情况,需要对个体变元使用置换(Substitution)进行替换,如果置换的结果使谓词形式一致,这个过程叫做合一 (Unify)。 例如:使用假言推理和全称固化, 由 W1(y) 和 (? x )[ W1(x) → W2 (x )] 推出 W2(y) 这里需要找到 项 y 对变元 x 的置换,即用y替换x。 1)置换 在谓词公式中变元替换的形式{t1/x1,t2/x2,… ,tn/xn}。 其中,{t1, t2, …, tn}为项, {x1, x2, …, xn}是不相同的变元。 ti/xi 表示用ti替换xi 。 ti,xi不能相同, xi不能循环出现在ti中。 例如:{a/x,c/y,f(b)/x} 是一个置换。 而在 {g(y)/x, f(x)/y} 中, x 与y 循环出现,则不能正确置换。 例3.5 一个谓词公式及其个体如下:P(x,f(y),B),分别使用置换θ1={ z/x,w/y },θ2={ q(z)/x,A/y }进行变元替换。 θ1的置换结果: P(z,f(w),B); θ2的置换结果: P( q(z),f(A),B). 定义13. 设θ= {t1/x1,t2/x2,… ,tn/xn}是一个置换,F 是一个谓词公式,用ti替换xi 后的新公式为G,则称G是公式 F 在θ置换下的例示,也是公式F的一个逻辑结论。 记作: G= Fθ 定义14. 设 θ= {t1/x1,t2/x2,… ,tn/xn}和 λ= {u1/y1,u2/y2,… ,um/ym}是两个不同的置换, 则θ与λ合成也是一个置换,记为θ·λ,可以是先用θ置换再用λ置换。也可以按照下面的方法进行置换。从集合 {t1 λ /x1,t2 λ /x2,… ,tn λ /xn , u1/y1,u2/y2,… ,um/ym} 中删除两种元素: (1)当ti λ= xi时 删去 ti λ/ xi (i=1,2,… ,n) (2)当yi ∈{x1,x2,… ,xn }时,删去uj/yj (j=1,2,… ,m) 例 3.6 θ= {f(y)/x,z/y},λ= {a/x,b/y,y/z} α= θ·λ ={t1 λ /x1,t2 λ /x2,… ,tn λ /xn , u1/y1,u2/y2,… ,um/ym} ={f(b/y)/x,(y/z)/y, a/x,b/y,y/z} ={f(b)/x,y/y, a/x,b/y,y/z} ={f(b)/x,y/z} 2)合一 定义15. 设有公式集 F= {P1,P2 ,… ,Pn},若存在一个置换θ使得 P1 θ =P2 θ= … =Pn θ ,则称θ是 F 的一个合一,称P1 , P2 , … Pn 是可合一的。 例如,对于公式集 F = {P1,P2}={ P(x,y,f(y)),P(a,g(x),z)} θ={a/x,g(a)/y,f(g(a))/z} 就是 F 的一个合一。 定义16. 设α是公式集 F的一个合一,对于 F 的任何一个合一θ,都存在一个置换λ 使得 θ = α ·λ ,则称 α 是 F 的最一般合一(Most General Unifier)。一般,一个公式集的合一不一定是唯一的,但一个公式集的最一般合一是唯一的。 使用最一般的合一去置换可合一的谓词公式集,可使它们的项变成完全一致。 3)合一算法 例如: F = { P(x,y,z)),P(x,f(a),h(b)} . 这里P1 = P(x,y,z) ,P2 = P(x,f(a),h(b)) 求最一般合一,先求分歧集(Disagreement Set)开始,从左至右分别比较P1 ,P2 的符合,直到发现第一个不同之处,构成一个分歧集 D1 = {y, f(a)},于是产生一个置换 σ1={y/ f(a)} 变量替换后 F1=F0 · σ1 下一个分歧集是D2 = {z,h(b)}。于是又产生一个置换 σ2= σ1 · {z/ h(b)} 再变量替换后 F2=F1 · σ2 … … 最后所求得的σ 即为最一般合一。 定理 3.1:设有谓词公式F,其标准子句集为S, F为不可满足(永假)的充要条件是,S为不可满足的。 要证明一个子句集是不可满足的,就要证明其中的每一个子句在任何个体论域上,都为不可满足。 Herbrand理论: Herbrand构造了一个特殊的论域,并证明了只要对子句在这个特殊域上的解释进行判定,就可知子句集是否为不可满足的。这个特殊的论域称为Herbrand域(H)。 定理 3.2 : 子句集S为不可满足的充要条件是S 的一切H解释都为假。 定理 3.3:子句集S为不可满足的充要条件是存在一个有限的不可满足的基子句集S’。 定义15. 原子谓词公式及其否定称为文字,任何文字的一个析取式称为一个子句,不含任何文字的子句称为空子句,记为或NIL。由子句或空子句构成的集合称为子句集。 例: P(x) ,~ P(x), Q(x,y) ,~ Q(x,y) 都是文字; 其中 P(x) ,~ P(x) 为互补文字。 P(x) ∨ Q(x,y) , P(x,f(x)) ∨ Q(x,g(y)) 都是子句。 一个谓词公式可以通过等价关系与推理规则化简为子句的集合。化简后子句集合称为原来谓词公式的子句集。 当谓词公式为永假时,其子句集一定是永假的,而当谓词公式为非永假时,没有这种关系。这是归结原理的主要依据。 消去蕴含连接词: → 或 ? 缩小否定词的辖区 标准化变元 化为前束范式 消去存在量词 化为Skolem 标准式 消去所有全称量词 消去合取词∧ 适当更换变元名 消去蕴含连接词: → 或 ? 反复使用: P → Q = ~ P ∨ Q P ? Q =( P ∧Q) ∨ (~ P ∧ ~ Q) 例: (?x)((?y) P(x,y)→ ~ (?y)( Q (x,y)→ R (x,y) ) ) `````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````` = (?x)(~(?y) P(x,y)∨~ (?y)(~Q (x,y)∨R (x,y) ) ) 缩小否定词的辖区,使~靠近单个谓词名 缩小否定词的辖区,使~靠近单个谓词名 使用双重否定 :~(~ P) = P 摩根定理:~ ( P ∨ Q ) = ~P ∧~ Q ; ~ ( P ∧ Q ) = ~P ∨~ Q 量词转换: ~(?x)P(x)=(?x)~ P(x) ; ~(?x)P(x)=(?x)~ P(x) 由 (?x)(~(?y) P(x,y)∨~ (?y)(~Q (x,y)∨R (x,y) ) ) =(?x)((? y) ~ P(x,y)∨ (? y)(Q (x,y)∧~R (x,y) ) ) (?x)((? y) ~ P(x,y)∨ (? y)(Q (x,y)∧~R (x,y) ) ) 标准化变元:变量换名使不同量词与被约束的变元一致。 (?x)((? y) ~ P(x,y)∨ (? z)(Q (x,z)∧~R (x,z) ) ) 化为前束范式: 前移所有量词 (?x)(? y) (? z) (~ P(x,y)∨ (Q (x,z)∧~R (x,z) ) ) 消去存在量词: 分两种情况: a.若该存在量词在所有全称量词之前,则用一个常量符号代替该存在量词辖域中的相应约束变元,这样的常量符号称为Skolem常量 b.若该存在量词在某些全称量词的辖域内,则用这些全称量词指导变元的一个函数代替该存在量词辖域中的相应约束变元,这样的函数称为Skolem函数。 (?x)(? y) (? z) (~ P(x,y)∨ (Q (x,z)∧~R (x,z) ) ) ? 由于(? y) (? z)都处于(?x)约束之内,都需要用Skolem函数来替换,分别为:f(x)和g(x)。 (?x)(~ P(x, f(x))∨ (Q (x,g(x))∧~R (x,g(x)) (?x)(~ P(x, f(x))∨ (Q (x,g(x))∧~R (x,g(x)) 化为Skolem 标准式:全称约束的子句合取范式。 可以使用: P∨(Q∧R)= (P∨Q )∧(P∨Q) (?x)((~ P(x,f(x))∨ Q (x,g(x)))∧(~ P(x,f(x))∨ ~ R (x,g(x)))) 消取全称量词,剩余的母式默认为被全称量词量化。 (~ P(x,f(x))∨ Q (x,g(x)))∧(~ P(x,f(x))∨ ~ R (x,g(x))) 消去合取词∧ ,得到子句集,其中的每一个元素都是子句。可以得到两个子句: ~ P(x,f(x))∨ Q (x,g(x)) ~ P(x,f(x))∨~ R (x,g(x)) 更换变元,使子句之间没有重复变量,因为所有变元都被全称量化,子句之间不存在相互依赖关系。 ~ P(x,f(x))∨ Q (x,g(x)) ~ P(y,f(y))∨~ R (y,g(y)) 由谓词公式转化子句集可知子句之间存在合取关系。只要证明其中的一个子句不可满足,则整个子句集就是不可满足。更为明确的是如果子句集中包含空子句,则此子句集一定是不可满足的。 归结过程的思路:先把求证的问题否定,证明其是不可满足的。证明过程是逐步扩充子句,并设法检验子句集中是否含有空子句。若不含空子句,则继续归约,直至找到空子句或不能继续归约。 1)命题逻辑的归结 定义3.16 设C1、C2是命题逻辑中的两个子句,C1中有文字L1,C2中有文字L2,且L1与L2互补,可以从C1、C2中分别删除L1,L2,再将剩余部分析取起来,构成的新子句为C12,称C12为C1、C2的归结式(或消解式),C1、C2称为其归结式的亲本子句,L1、L2称为消解基。这一过程为归结。 例 3.9 C1= ~ P∨Q , C2= ~ Q , C3= P ,求归结式C123 。 解:先归结C1 、 C2 : C12= ~ P 再归结C12 、 C3: C123= NIL 定理 3.4:归结式C12是亲本子句C1和C2的 逻辑结论。 分析:设 C1= L∨ C1’ , C2 = ~L∨ C2’ 按照定理,新子句 C12= C1’ ∨ C2’ 需要证明的是: C1∧C2 = C12 (永线’ = C1’ ∨ L = ~ C1’ → L C2 = ~L∨ C2’ = L → C2’ 假言三段论: C1∧ C2 =(~ C1’ → L )∧( L → C2’ ) = (~ C1’ → C2’ ) 又 (~ C1’ → C2’ ) = C1’ ∨ C2’ = C12 于是: C1∧ C2 = C12 §3-4归结演绎推理 定理 3.5:(归结原理的完备性定理)如果子句集 S 是不可满足的,那么必存在(当且仅当)存在一个从 S 到空子句NIL的规约过程。(该定理的证明要用到Herbrand定理,从略。) 命题逻辑的归结反演过程:由已知前提F,要证明结论为G,且F、G都是公式集的形式,只要证明 F ∧~ G 不可满足。又根据定理3.1, 公式F ∧~ G 与其子句集等价。又转化为一个含有空子句的归结过程。这样用归结原理进行的定理的自动证明也称为归结反演。 归结过程描述: 否定目标公式G,得到 ~ G ; 把~G并入到公式集F中,得到 {F,~G}; 把公式集{F,~ G}化为子句集 S; 利用归结原理对S进行归结, 若归结过程出现空子句, 则结论成立,即G为线 已知{P,(P∧Q)→R,(S∨E)→Q,E},求证 R 证:化为子句集: S= {P,~P∨~Q∨R,~S∨Q ,~E ∨Q ,E,~R} S= {P,~P∨~Q∨R,~S∨Q ,~E ∨Q ,E,~R} 的归结演绎树如下: 2)谓词逻辑的归结 基本原则:先用最一般合一对变元进行代换,然后再进行归结。 定义3.17 设C1、C2是两个无相同变元的子句(子句集化简的最后一步),L1、L2分别是C1、C2中的文字,如果L1和~L2有最一般合一σ,则子句 (C1σ-{L1σ})∪(C2σ-{L2σ}) 称作C1和C2的二元归结式(二元消解式),C1和C2称作归结式的亲本子句,L1和L2称作消解文字。 例3.11 C1= P(a)∨R(x), C2= ~ P(y) ∨ Q(b),求C12 。 解:L1= P(a), L2= ~ P(y),则L1 和L2的最一般合一为 σ = {a/y} C12 = (C1σ-{L1σ})∪(C2σ-{L2σ}) =({ P(a),R(x)} - { P(a)})∪ ({~ P(a),Q(b)} - {~ P(a)}) = {R(x)} ∪ {Q(b)} = {R(x),Q(b)} = R(x) ∨ Q(b) §3-4 归结演绎推理 例3.12 C1= P(x)∨ P(f (a)) ∨ Q(x), C2= ~ P(y) ∨ R(b),求C12 。 解:C1本身有可合一的文字P(x)和 P(f (a))其最一般的合一 σ = {f(a)/x} 置换后得到: C1σ = P(f (a)) ∨ Q( f (a)) 再把 C1σ与 C2 进行归结 ,这时, L1 =P(f (a)) , L2= ~ P(y), L1 和L2的最一般合一 σ = {f(a)/y} , 置换后,C1和C2的二元归结式: C12 = R(b) ∨ Q(f(a)) 谓词逻辑的归结反演过程与命题逻辑基本相同,只是要考虑两个亲本子句的最一般合一。 例3.13 前提:每个储蓄钱的人够获得利息; 结论:如果没有利息,那么,就没有人去储蓄钱。 证明:令S(x,y)表示 x储蓄y M(x)表示 x是钱 I(x)表示 x是利息 E(x,y)表示 x获得y 已知 F , 求证 G 是 F 的逻辑结论。 F: (? x) [ ( ? y )(S(x,y))∧ M(y) )→ ( ? y )( I(y) ∧ E(x,y) ) ] G: ~( ? x) I(x) → [ (? x) (? y) ~ (S(x,y) ∧ M(y) )] 把 G否定并入F ,得到 {F, ~ G},再把{F, ~ G}化成子句集,得到 5 个子句: F: (1) [~ S(x,y) ∨ ~ M(y) ] ∨ I (f( x) ) (2) [~ S(x,y) ∨ ~ M(y) ] ∨ E ( x, f( x) ) G: (3) ~ I ( z) (4) S(a,b) (5) M(b) 思考:快乐学生 已知:任何通过计算机考试并或奖的人都是快乐的; 任何肯学习或幸运的人都可以通过所有考试; 张不肯学习但他是幸运的人; 任何幸运的人都能获奖; 求证:张是快乐的。 自学规则演绎推理 及其他推理方法 §3-4 归结演绎推理 2.置换与合一 §3-4 归结演绎推理 §3-4 归结演绎推理 §3-4 归结演绎推理 §3-4 归结演绎推理 (1)这种情况无意义,要删去 (2)这种情况前面已经替换,也要删去。在θ中y也已被替换过。 §3-4 归结演绎推理 §3-4 归结演绎推理 §3-4 归结演绎推理 §3-4 归结演绎推理 3. Herbrand理论 §3-4 归结演绎推理 4.子句和子句集 §3-4 归结演绎推理 5. 子句集化简步骤 §3-4 归结演绎推理 §3-4归结演绎推理 §3-4 归结演绎推理 §3-4 归结演绎推理 §3-4 归结演绎推理 §3-4 归结演绎推理 §3-4 归结演绎推理 6. Robinson归结原理 §3-4 归结演绎推理 ~ P∨Q ~ Q ~ P P NIL 图3-2树形归结过程 §3-4 归结演绎推理 §3-4 归结演绎推理 假言三段论: P → Q ,Q → R = P → R §3-4 归结演绎推理 ~ P ∨ ~ Q ~E ∨ Q ~ E E NIL ~P ∨ ~Q ∨ R ~ R P ~ Q 图3-3一个命题逻辑的归结演绎树 §3-4 归结演绎推理 §3-4 归结演绎推理 §3-4 归结演绎推理 §3-4 归结演绎推理 子句 (1) 子句 (4) ~ M(b) 子句 (5) NIL 子句 (3) ~ S(x,y)∨ ~ M(y) σ = {f(x)/z} σ = {a/x , b/y} 图3-4 一个谓词逻辑的归结演绎树 §3-4 归结演绎推理 §3-4 归结演绎推理 §3-5 规则演绎推理 全称固化:y是个体域中的任一个体,用此永真可以消去谓词中的全称量词。 存在固化: y是个体域中使p(x)为真的个体。 用于消去存在量词。 * * 一阶谓词逻辑 推理基础 归结原理 自然演义推理 归结演义推理 定义1:一个陈述句称为一个断言。有真假意义的断言称为命题。 命题的意义(真假)结果称为真值,为真时记为 T , 为假时记为 F。 例如:王立是大学生;上海是全国最大的城市。 再如:当x=6,y=5时, 命题:x 大于 y 结果为 T , 命题:x 小于 y 结果为 F 。 反例:今天好冷! 几度呀? 都不是命题。 §3-1 谓词逻辑基本概念 1. 命题的线:论域是问题涉及对象的全体 构成的非空集合。集合中的元素称为个体,因此,论域也称为个体域。 谓词逻辑: 命题是用谓词来表示的,由两个部分构成即:一个谓词 = 谓词名(个体)。 其中,个体是命题的主语,表示独立的事务或抽象的概念。 谓词名是谓语,表达个体的状态、性质或个体间的关系。 定义 3 :设D是个体域,P :Dn ? { T ,F }是一个映射,其中 Dn ={(x1,x2,…,xn) x1,x2,…,xn ∈ D} 则称 P是一个 n 元谓词(n=1,2,…), 记为 P(x1,x2,…,xn)。 其中, x1,x2,…,xn为个体变元。 个体可以是常量、变量或函数。 例如:GREATER(x,6) 表示 x6 TEACHER(father(A)) 表示的父亲是教师。 其中, father(A) 是函数,小写。一般形式为 f(x1,x2…xn) ,其值在个体域中。 3. 连接词和量词 (1)连接词:是连接简单命题,构成复合命题的逻辑运算符号。 ~ :否定、对命题 “非”。 ∨:析取,对命题取“或” ∧:和取,对命题取“与” →:条件,蕴涵,表示“如果…则…” ?:双条件,表示“当且仅当”。 表2-1 谓词逻辑表 T T F F T F F F T F T T T F F F F T F F T T T T T F T T P?Q P→Q P∧Q P∨Q ~P Q P 4. 项与合式公式 §3-1 谓词逻辑基本概念 §3-2 谓词逻辑的问题表示 1. 谓词逻辑表示 §3-2 谓词逻辑的问题表示 2. 谓词逻辑应用 §3-2 谓词逻辑的问题表示 a b c 图3-1 盒子移动场景 a b c §3-2 谓词逻辑的问题表示 AT(Robot,c) EMPTY(Robot ) ON(box,b) TABLE(a) TABLE(b) AT(Robot,a) EMPTY(Robot ) ON(box,a) TABLE(a) TABLE(b) AT(Robot,a) HOLD( Robot ,box) TABLE(a) TABLE(b) AT(Robot,b) HOLD( Robot , box) TABLE(a) TABLE(b) AT(Robot,b) EMPTY(Robot ) ON(box,b) TABLE(a) TABLE(b) Goto(x,y) Pickup(x ) Goto(x,y) Setdown(x ) Goto(x,y) §3-2 谓词逻辑的问题表示 3. 谓词逻辑表示的 特点 §3-2 谓词逻辑的问题表示 定义7. 设P为谓词公式,D为其个体域,若对P中的谓词、个体常量、函数按如下定义赋值: (1)为每个个体指派D中的一个元素 (2)为每个n元函数指派一个从Dn个到D中的映射 其中: Dn = {(x1,x2,…xn) x 1,x2,x3,…∈ D} (3)为每个n 谓词指派一个从 Dn 到{T , F}的映射 则称这些指派为P在D上的一个解释。 1.谓词公式的解释 2 1 1 f(2) f(1) a 例3.4 设个体域D={1,2},求谓词公式 B= (? x) P (f(x),a)在D上的解释,并给出该解释下B的真值。 解:设个体常量a和函数 f(x)的真值指派为 : 对谓词的真值指派为 : T P(2,1) x x T P(2,2) P(1,2) P(1,1) B= (? x) P(f(x),a)= P( f(1) , a) ∧ P( f(2) , a) =P(1,1) ∧ P(2,1) =T 2.谓词公式的永线)等价关系 设 P 和 Q为D上的两个谓词公式,对于D上的任何解释P 和 Q都有相同的真值 ,则称P和 Q在D上等价。如果对于D是任意的个体域,则称P和Q等价。 常用的等价式(公理) 否定之否定: ~ (~P ) =P 交换率: P ∨ Q= Q∨P ; P ∧ Q= Q∧P 结合率:(P ∨ Q) ∨ R = P ∨ ( Q ∨ R ) ; (P ∧ Q) ∧ R = P ∧ ( Q ∧ R ) 3.谓词公式的等价与永真蕴含(命题逻辑回顾) T T F F T F F F T F T T T F F F F T F F T T T T T F T T P?Q P→Q P∧Q P∨Q ~P Q P F T P→Q F F F T P∧Q T T P→Q=Q T F F T T F F T T T P ∨Q = Q Q P 析取三段论: ~ P , P ∨ Q = Q 假言推理: P ,P → Q = Q 4 自然演绎推理 拒: ~ Q , P → Q = ~ P 三: P → Q , Q → R = P → R 4 自然演绎推理 §3-4 归结演绎推理 1.谓词公式的范式 §3-4 归结演绎推理 *

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