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

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

发布时间:2019-05-15 13:57 来源:未知 编辑:admin

  第三章谓词逻辑与确定性推理谓词逻辑指基于数理逻辑的表示、推理方法,一阶 谓词逻辑是经典的命题逻辑。由于其表示的多为确定性 知识,也多用于确定性推理。 一阶谓词逻辑 推理基础 归结原理 自然演义推理 归结演义推理 定义1:一个陈述句称为一个断言。有真假意义的断言称为命题。 命题的意义(真假)结果称为真值,为真时记为 命题:x大于 命题:x小于 反例:今天好冷!几度呀? 都不是命题。 3-1 谓词逻辑基本概念 命题的线 谓词逻辑基本概念 论域和谓词定义2:论域是问题涉及对象的全体 构成的非空集 合。集合中的元素称为个体,因此,论域也称为个 谓词逻辑:命题是用谓词来表示的,由两个部 分构成即:一个谓词 谓词名(个体)。其中,个体是命题的主语,表示独立的事务或抽 象的概念。 谓词名是谓语,表达个体的状态、性质 或个体间的关系。 定义3 ={(x1,x2,…,xn)x1,x2,…,xn 元谓词(n=1,2,…),记为 P(x1,x2,…,xn)。 其中,x1,x2,…,xn为个体变元。 个体可以是常量、变量或函数。 例如:GREATER(x,6) 表示x

  6 TEACHER(father(A))表示的父亲是教师。 其中, father(A)是函数,小写。一般形式为 f(x1,x2…xn) ,其值在个体域中。 3-1 谓词逻辑基本概念 3-1 谓词逻辑基本概念 连接词和量词(1)连接词:是连接简单命题,构成复合命题的逻辑运算符号。 ~:否定、对命题“非”。 :析取,对命题取“或” :条件,蕴涵,表示“如果…则…”:双条件,表示“当且仅当”。 表2-1 谓词逻辑表 (2)量词:用于对谓词中的个体约束或规定。分为全称量词和存在量词。 x:表示论域中所有的x 命题(x)P(x)为真:当且仅当对于论域中的所有x ,都有 P(x)为真;只要有一个x P(x)就为假。命题(x )P(x)为真:只要有一个x 当且仅当对于论域中的所有x,都有P(x)为假,那么(x P(x)就为假。3-1 谓词逻辑基本概念 定义3 项的规则1)单独一个 个体词是项:t )也是项。3)由1)和2)生成的表达式也是项。 定义4. 原子谓词公式 称为原子谓词公式。3-1 谓词逻辑基本概念 项与合式公式定义5. 合式公式(谓词公式) 1)原子谓词公式称为合式公式; 约束的合式公式也称为合式公式。定义6. 自由变元与约束变元 、是有辖区的,受约束的变元称为约束变元。不受它们 的约束的变元称为自由变元。 仍为自由变元。3-1 谓词逻辑基本概念 谓词逻辑可以表示事物的状态、性质、概念,也可 以表示事物之间的因果关系,即规则。 对于事实的知识用~连接的谓词公式表示。 对于事物的因果关系通常用蕴含式表示。 使用谓词逻辑进行知识表示时,一般先根据题意定义谓词, 然后在根据表达的需要使用适当的连词和量 词把谓词连接起来构成谓词公式。 3-2 谓词逻辑的问题表示 谓词逻辑表示例3.1 所有的学生都有某教材。 STUDENT(x) :表示x是学生 HASMATERIAL(x,y):表示x有教材y 题目所表达的知识可以表示为: (STUDENT(x)HASMATERIAL(x,y)) 例3.2 所有整数 不是偶数 就是 奇数。 :表示x是整数E(x):表示x是偶数 O(x):表示x是奇数 题目所表达的知识可以表示为: 3-2谓词逻辑的问题表示 如果对逻辑的某些外延扩展后,则可把大部分的知识表达成一阶 谓词逻辑的形式。 例如:王是计算机系的学生,李明是王的同班同学,他们系系的 学生都喜欢编程。定义谓词: COMPUTRE(x) :x是计算机系的学生 CLASSMATE(x,y):x是y的同班同学 LIKE :x喜欢y。题目的知识表示: COMPUTRE(wang) CLASSMATE(liming,wang) 谓词逻辑应用3-2 谓词逻辑的问题表示 例3.3 机器人要把a 处桌子上的箱子搬到b 处的桌子上,再回 谓词:TABLE(x):x是桌子EMPTY(y ):y手中是空的 ):y在z位置附近HOLD ):w在桌子x上其中x 3-2谓词逻辑的问题表示 图3-1 盒子移动场景 增加动作谓词: 1)Goto(x,y 走到y2)Pickup(x 处拿起盒子3)Setdown ):在x处放下盒子分别对应的条件: 1)AT(Robot,x) 3-2谓词逻辑的问题表示 AT(Robot,c) EMPTY(Robot ON(box,a)TABLE(a) TABLE(b) 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-2 谓词逻辑的问题表示 推理:由事实出发推出结论的过程(2)推理从逻辑基础出发分:演义推理和归纳推理 演义推理:有一般到特殊,核心是三段论。 归纳推理:由特殊到一般:枚举、统计、类比。 (3)按所用的事实:确定性推理和非确定性推理。 (4)按结论的出现情况:单调性推理和非单调推理。 (5)按控制策略:正向推理、逆向推理与混合推理。 (6)按使用知识策略:启发式推理和非启发式推理。 3-3 推理基础 定义7. 设P为谓词公式,D为其个体域,若对P 中的谓词、个体常量、函数按如下定义赋值: (1)为每个个体指派D中的一个元素 (2)为每个n元函数指派一个从D (3)为每个n谓词指派一个从D F}的映射则称这些指派为P在D上的一个解释。 3-3 推理基础 1.谓词公式的解释 对谓词公式中的个体变项、函数变项、谓 词变项用指定的常项去替代,所得到的结果称 为对谓词公式的一个解释或赋值 3-3推理基础 3-3 推理基础 例3.4设个体域D={1,2},求谓词公式B= (f(x),a)在D上的解释,并给出该解释下B的真值。解:设个体常量a和函数f(x)的真值指派为: 对谓词的线) =P(1,1)P(2,1) 定义8.设P为谓词公式,对于非空个体域D上的任何解释 都取得真值 ,则称P在D上永真。如果P在任何非空个体域上均为 定义9.设P为谓词公式,如果至少存在D上的一个解释, 使得P在该解释下取线.设P为谓词公式,对于非空个体域D上的任何解 释都取得真值 ,则称P在D上永假。如果P在任何非空个体域上均为F ,则称P永假。也称为不可满足性或 不相容性。 3-3 推理基础 2.谓词公式的永线)等价关系 和Q都有相同的真值,则称P和Q在D上等价。如果对 于D是任意的个体域,则称P和Q等价。 常用的等价式(公理) 否定之否定: 3.谓词公式的等价与永线 推理基础 分配率:P 3-3推理基础 2)永线. 设对于谓词公式P P的逻辑结论。记作:P=

  Q 。常用的永真蕴含式: 化简式:P 变元替换一般替换:新变元、辖区不便; 1.全称固化:( P(y):y是个体域中的任一个体,用此永真可以消去谓词中的全称量词(US规 P(c):c是个体域中使p(x)为真的个体。用于消去存在量词(ES规则) ):由此引起的其他位置上的x也是不自由的(UG规则) 存在量词附加规则(EG规则) 一般:abcde表示个体常量,tuvwxyz表示变量例8,证明 证明: 由已知事实出发,根据经典的逻辑推理规则推出结论的过程称为演绎推理。最基本的推理规则是三段论:假言推理、拒取式推 理、假言三段论。 在假言推理 例3.7已知: 例3.9已知事实: 凡是编程课,王程都喜欢; 所有程序设计语言课 都是需要编程的课; C语言课是一门程序设计语言课 求证:王程喜欢C语言课 证明:定义谓词: Prog(x) x是需要编程的课 Like(x,y) x喜欢y Lang(x) x是一门程序设计语言课 事实描述: Prog(x) Like(Wangch Lang(C)推理:Lang(y) Prog(y)全称固化 Lang(C),Lang(y)Prog(y)=

  Prog(C) C需要编程 Prog(C),Prog(C)Like(Wangch 自然演绎推理归结演绎推理是基于一种称为归结原理(亦称消解原理 principle resolution)的推理规则进行推理的方法。是由鲁滨逊(J.A.Robinson)于1965年在海伯伦(Herbrand)理论上建立 首先提出。它是谓词逻辑中一个相当有效的机械化推理方法。被 认为是自动推理,特别是定理机器证明领域的重大突破。 基本思想:根据前提 谓词逻辑来讲就要证明其在任何一个非空的个体域上永真。要证明 不可满。连词归化:(P 3-4归结演绎推理 范式是是公式的标准形式,公式要转换为等价的范式, 方便一般性的处理。根据量词的情况分为两种:前束范式 和Skolem范式。 1)前束范式 定义12. 设M是谓词公式,如果其中所有的量词均非否 定地约束整个公式,则称P 为前束范式。一般地写成: 1.谓词公式的范式3-4 归结演绎推理 例如: Skolem范式 在前束范式中,如果所有的存在量词 都在全称量词之 该谓词公式为Skolem范式。例如: 可以证明:任何谓词公式均可化为Skolem范式 3-4 归结演绎推理 推理过程中,在不同谓词公式可能出现谓词名相同,个体 不同的情况,需要对个体变元使用臵换(Substitution)进行替 换,如果臵换的结果使谓词形式一致,这个过程叫做合一 (Unify)。 例如:使用假言推理和全称固化, 3-4归结演绎推理 3-4归结演绎推理 例3.5 一个谓词公式及其个体如下:P(x,f(y),B),分 别使用臵换θ }进行变元替换。 在θ臵换下的例示,也是公式F的一个逻辑结论。记作: 3-4归结演绎推理 定义14. }是两个不同的臵换,则θ与λ合成也是一个臵换,记为θλ,可以是先用θ臵换 再用λ臵换。也可以按照下面的方法进行臵换。从集合 3-4归结演绎推理 (1)这种情况无意义,要删去 (2)这种情况前 面已经替换,也要 删去。在θ中y也 已被替换过。 3-4 归结演绎推理 2)合一 定义15. 设有公式集 },若存在一个臵换θ使得 是可合一的。例如,对于公式集 的一个合一。3-4 归结演绎推理 定义16. 设α是公式集 F的一个合一,对于 任何一个合一θ,都存在一个臵换λ使得 的最一般合一(MostGeneral Unifier)。一般,一个公式集的合一不一定是唯一的, 但一个公式集的最一般合一是唯一的。 使用最一般的合一去臵换可合一的谓词公式集,可 使它们的项变成完全一致。 3-4 归结演绎推理 3)合一算法 例如: 一般合一,先求分歧集(DisagreementSet)开始,从左至右 分别比较P 的符合,直到发现第一个不同之处,构成一个分歧集 最后所求得的σ即为最一般合一。3-4 归结演绎推理 定理3.1:设有谓词公式F,其标准子句集为S,F为不可满 足(永假)的充要条件是,S为不可满足的。 要证明一个子句集是不可满足的,就要证明其中的每一个子 句在任何个体论域上,都为不可满足。 Herbrand理论: Herbrand构造了一个特殊的论域,并证明 了只要对子句在这个特殊域上的解释进行判定,就可知子句集 是否为不可满足的。这个特殊的论域称为Herbrand域(H)。 定理3.2 子句集S为不可满足的充要条件是S的一切H解释 都为假。 定理3.3:子句集S为不可满足的充要条件是存在一个有限 的不可满足的基子句集S’。 Herbrand理论3-4 归结演绎推理 定义15. 原子谓词公式及其否定称为文字,任何文字的 一个析取式称为一个子句,不含任何文字的子句称为空子句, 记为或NIL。由子句或空子句构成的集合称为子句集。 都是文字;其中 都是子句。一个谓词公式可以通过等价关系与推理规则化简为子句的 集合。化简后子句集合称为原来谓词公式的子句集。 当谓词公式为永假时,其子句集一定是永假的,而当谓词 公式为非永假时,没有这种关系。这是归结原理的主要依据。 4.子句和子句集 3-4 归结演绎推理 化为Skolem标准式 子句集化简步骤3-4 归结演绎推理 缩小否定词的辖区,使~靠近单个谓词名3-4归结演绎推理 缩小否定词的辖区,使~靠近单个谓词名使用双重否定 3-4归结演绎推理 化为前束范式:前移所有量词 消去存在量词:分两种情况: a.若该存在量词在所有全称量词之前,则用一个常量符号 代替该存在量词辖域中的相应约束变元,这样的常量符号称为 Skolem常量 3-4 归结演绎推理 b.若该存在量词在某些全称量词的辖域内,则用这些全 称量词指导变元的一个函数代替该存在量词辖域中的相应 约束变元,这样的函数称为Skolem函数。 z)都处于(x)约束之内,都需要用Skolem函数来替换,分别为:f(x)和g(x)。 3-4归结演绎推理 化为Skolem标准式:全称约束的子句合取范式。 可以使用: 3-4归结演绎推理 消去合取词,得到子句集,其中的每一个元素 都是子句。可以得到两个子句: 更换变元,使子句之间没有重复变量,因为所有变元都被全称量化,子句之间不存在相互依赖关系。 3-4归结演绎推理 由谓词公式转化子句集可知子句之间存在合取关系。只 要证明其中的一个子句不可满足,则整个子句集就是不可满 足。更为明确的是如果子句集中包含空子句,则此子句集一 定是不可满足的。 归结过程的思路:先把求证的问题否定,证明其是不可 满足的。证明过程是逐步扩充子句,并设法检验子句集中是 否含有空子句。若不含空子句,则继续归约,直至找到空子 句或不能继续归约。 Robinson归结原理3-4 归结演绎推理 1)命题逻辑的归结 定义3.16 中有文字L 中分别删除L 称为其归结式的亲本子句,L 称为消解基。这一过程为归结。例3.9 ,求归结式C123 再归结C12 NIL图3-2树形归结过程 3-4 归结演绎推理 定理 3.4:归结式C 12 是亲本子句C 逻辑结论。分析:设 12于是: 123-4 归结演绎推理 假言三段论:P 定理3.5:(归结原理的完备性定理)如果子句集 子句NIL的规约过程。(该定理的证明要用到Herbrand定理,从略。) 命题逻辑的归结反演过程:由已知前提F,要证明结论 为G,且F、G都是公式集的形式,只要证明 不可满足。又根据定理3.1, 公式F 与其子句集等价。又转化为一个含有空子句的归结过程。这样用归结原理进 行的定理的自动证明也称为归结反演。 3-4归结演绎推理 归结过程描述: 把公式集{F,~G}化为子句集 利用归结原理对S进行归结,若归结过程出现空子句, 则结论成立,即G为线一个命题逻辑的归结演绎树3-4 归结演绎推理 2)谓词逻辑的归结 基本原则:先用最一般合一对变元进行代换,然后再进行归结。 定义3.17 是两个无相同变元的子句(子句集化简的最后一步),L 称作归结式的亲本子句,L 称作消解文字。3-4 归结演绎推理 例3.11 3-4归结演绎推理 3-4 归结演绎推理 例3.12 解:C1本身有可合一的文字P(x)和P(f(a))其最一般的合一 谓词逻辑的归结反演过程与命题逻辑基本相同,只是要考虑两个亲本子句的最一般合一。 例3.13 前提:每个储蓄钱的人够获得利息; 结论:如果没有利息,那么,就没有人去储蓄钱。 证明:令S(x,y)表示 x储蓄y M(x)表示 I(x)表示x是利息 E(x,y)表示 x获得y 已知 3-4归结演绎推理 G否定并入F,得到 G},再把{F,~G}化成子句集,得到 子句(1)子句(4) NIL子句(3) 图3-4一个谓词逻辑的归结演绎树 3-4 归结演绎推理 思考:快乐学生 已知:任何通过计算机考试并或奖的人都是快乐的; 任何肯学习或幸运的人都可以通过所有考试; 张不肯学习但他是幸运的人; 任何幸运的人都能获奖; 求证:张是快乐的。 3-4 归结演绎推理 自学规则演绎推理及其他推理方法 3-5 规则演绎推理

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