资源预览内容
第1页 / 共63页
第2页 / 共63页
第3页 / 共63页
第4页 / 共63页
第5页 / 共63页
第6页 / 共63页
第7页 / 共63页
第8页 / 共63页
第9页 / 共63页
第10页 / 共63页
亲,该文档总共63页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
人工智能逻辑,中国科学院计算技术研究所 智能信息处理重点实验室,主要内容,逻辑简介 逻辑程序设计 非单调逻辑 缺省逻辑 限定逻辑 真值维护系统 情景演算,1. 逻辑简介,逻辑的历史 逻辑系统 命题逻辑 谓词逻辑,1.1 逻辑的历史,Aristotle逻辑学 Leibnitz数理逻辑 Gottlob Frege (1848-1925)一阶谓词演算系统,符号论 20世纪30年代,数理逻辑广泛发展,1.2 逻辑系统,一个逻辑系统是定义语言和它的含义的方法。 逻辑系统中的一个逻辑理论是该逻辑的语言的一 个语句集合,它包括: 逻辑符号集合:在所有该逻辑的逻辑理论中均出现的符号; 非逻辑符号集合:不同的逻辑理论中出现的不同的符号; 语句规则:定义什么样的符号串是有意义的; 证明:什么样的符号串是一个合理的证明; 语义规则:定义符号串的语义。,逻辑与程序语言的对比,一个证明是一个语法结构,它由符号串根据一定 的规则组成。它包括假设和结论。 在公理化逻辑中,逻辑给出一个逻辑公理和推理 规则的集合。推理规则是可以从一个语句的集合得到 另一语句的集合。 公理化逻辑中的证明就是一个语句序列,使得 其中的每个语句要么是逻辑公理,要么是一个假设, 要么是由前面的语句通过推理规则得到的。,证明,在语法上,如果存在一个从假设到的证明, 则记为 ,称由可推导出的,或可证明的。 如果在没有任何假设下是可推导出的,则记为 ,称为可证明的。 称一个假设是不协调的,如果存在一个语句 使得和的否定均可由推导得出。 称一个逻辑系统是一致的,或相容的(consistent), 如果不存在逻辑系统的公式A,使得A与A同时成 立。,证 明(语法),语言的解释是在某个论语(domain)中定义非逻辑 符号。语句的语义是在解释下定义出语言L的真假值。 如果I是L的一个解释,且在I中为真,则记为 I ,称作I满足 ,或者I 是的一个模型。 类似地,给定一个语句和一个语句 ,如果对 每个解释I ,有I 蕴含I ,换言之,如果I 是 的一个模型则I也是的一个模型,则记为 ,我 们称为的一个逻辑结果。,解 释(语义),可靠性(reliable) 一个逻辑是可靠的,如果它的证明保持真假值, 即在任何解释I下,如果I是 的模型,且可由推导 出,则I也是的一个模型。即,一个逻辑是可靠的, 如果对任何语句集合和语句 , 蕴涵 。,可靠性和完备性,完备性(complete) 一个逻辑是完备的,如果任何永真语句是可证的。 即,对任何语句集合和语句 , 蕴涵 。 如果一个逻辑是完备的,则该逻辑的证明系统已强到 可以推出任何永真式。 Gdel完备性定理:一阶逻辑是完备的,可判定的 一个逻辑称为是可判定的(decidable),如果存在 一个算法对逻辑中的任一公式 A,可确定 A是否成 立。否则,称为是不可判定的(undecidable) 。 如果上述算法虽不一定存在,却有一个过程,可对该系统的定理做出肯定的判断,但对非定理的公式过程未必终止,因而未必能作出判断。这时称逻辑是半可判定的。,可判定性,一阶逻辑是不可判定的,但它是半可判定的。,1.3 命题逻辑,命题是可以确定其真假的陈述句。 Bolle提出了布尔代数。 语言: ,; 公式,原子公式 公理模式:(A (B A)(A (B C) (A B) (A C)(A)(B) (B A) 推理规则:分离规则(modus ponens,MP规则),1.4 谓词逻辑(一阶逻辑),Frege谓词演算 语言: ,(,);常元,变元,函词,谓词;公式 公理模式:(A (B A)(A (B C) (A B) (A C)(A)(B) (B A)vA Atv (t对A中变元v可代入)v(A B) (vA vB)A vA (v在A中无自由出现) 推理规则:分离规则,谓词逻辑与命题逻辑的区别谓词逻辑给出了原子语句的内部结构,将原子公式看作是事物直接的关系;它引入了“推广”(泛化),加强了逻辑的表示能力和推理能力。这样,我们可以说某种性质对某个对象是成立的,或对所有的对象成立,或不对任何对象成立。,2. 逻辑程序设计,消解原理(归结原理) Horn逻辑 Prolog逻辑程序设计语言,2.1 消解原理,例:C1 = PQR C2 = PQ 则C1与C2消解后的结果为:QR若子句集S能导出空子句(有否证),则称S 是不可满足的。 反证法: S A iff S A ,2.2 Horn逻辑,文字:原子公式(正文字)或原子公式的否定(负文字)。 P, Q, R 子句:若干文字的析取。PQR Horn子句: 子句L1L2 Ln中如果至多只含一个正文字, 那么该子句称为Horn子句。 Horn子句P Q1 Q2 Qn通常表示为: P Q1, Q2, , Qn,Horn子句的类型:过程:P Q1, Q2, , Qn事实: P 目标: Q1, Q2, , Qn空子句: ,例: 过程:AT(dog, x) AT(Zhang, x)事实:AT(Zhang, train) 目标: AT(dog, train) 首先目标中过程调用AT(dog, train)与过程名AT(dog, x) 匹配,合一为train/x,调用过程AT(Zhang, x),从而 产生新目标 AT(Zhang, train),与事实匹配,产生目 标 。因而调用成功,输出“是”。,2.3 Prolog,Prolog(Programming in logic)语言是以Horn子句逻辑为基础的高级程序设计语言。 1972年,法国马赛大学的Alain. Colmerauer提出了Prolog的雏型。 1975年,Prolog被用于问题求解系统。 此后,它在许多领域获得了应用,如关系数据库、定理证明、智能问题求解、计算机辅助设计、规划生成等领域。,Prolog的构成,事实:关于对象性质和关系的事实语句; student(john),married(tom,mary) 规则:关于对象性质和关系的定义规则语句; 它与事实的不同在于,规则所定义的性质、关系依 赖与其它的性质和关系,因此规则呈蕴涵语句形式。B: A “如果A则B” bird(x) : animal(x),has(x, feather) 问题:关于对象性质或关系的询问。? student(john)? married(mary,x),Prolog的执行方式,搜索:在程序中自上而下地搜索事实和规则;匹配:将目标中的项与事实和规则进行匹配;回溯:当目标中一项失败时,如果目标中有已经成功的的项(应在失败项的左边),那末就重新调用这些成功项中最右边的一个,谋求新的成功。,Prolog语言的基本文法,Prolog语言的最基本语言成分是项(term),一个 项或者是常量,或者是变量,或者是一个结构。 常量:是指对象和对象之间的特定关系的名;整数,如0,22,1586等;原子,如John,student,likes,sister-of 变量:表示任意的对象,它与FOL中的变元相同;Prolog中变量可以用大写字母,下划线,以及由它们 开头的字母串。如X, Y, Answer, _value等。 结构:是常量和变量的序列,它由一个函子(函词 或谓词)和该函子的自变量所组成。如: likes(john, X) married(mary, jack),例: (1) likes(bell, sports) (2) likes(mary, smith) (3) likes(mary, sports) (4) likes(jones, smith) (5) friend(john, X) : likes(X, sports), likes(X, smith) (规则) (6) ? friends(john, Y) (问题),(事实),(7)? likes(X, sports), likes(X, smith),(8)? likes(bell, smith) (bell / X),(7)? likes(X, sports), likes(X, smith),(8)? likes(mary, smith) (mary / X),Prolog的基本特点,Horn子句逻辑是Prolog的基础。 Prolog既是一种逻辑程序设计语言,又是一个逻辑系统。 Prolog是一种描述性语言,它是一种面向问题的语言,你只需要告诉它要做什么,即给出问题的形式描述,而不需要知道应该如何做。 Prolog完全依靠匹配、回溯来进行搜索。Prolog的求解过程是一个寻求否证的消解过程。 Prolog也使用元语言种的谓词,有很强的描述能力。 Prolog采用统一的数据结构项,它包含控制成分,且有专门进行数值计算和符号处理的模块。,3. 非单调逻辑,单调逻辑 非单调逻辑 区别,3.1 单调逻辑,在现有知识的基础上,通过严密的逻辑论证和推理获得的新知识必须与已有的知识相一致。 A,AB B 推理系统的定理集合随着推理过程的进行而单调地增大。单调性:(1) Th( )(2) 若 1 2 ,则Th(1) Th(2)(3) Th(Th( ) Th( ) (不动点),3.2 非单调逻辑,推理系统的定理集合并不随着推理过程的进行而单调地增大,新推出地定理很可能会否定、改变原来地一些定理,使得原来能够解释地某些现象变得不能解释了。新规则:(4) P (不动点),4. 缺省逻辑,1980年,Reiter提出了缺省逻辑(Default Logic)。“一般情况下鸟是会飞的”“鸵鸟不会飞” “企鹅不会飞”,4.1 缺省规则,一个缺省规则是如下形式的规则:,(x):称为前提条件i(x):称为缺省条件,或检验条件 (x):称为结论 为简便,通常情况下可以省略检验条件中的M。 规则的使用: 如果规则的前提条件满足,且现有的知识导不 出检验条件的否定i(x),则可以得出结论成立。,4.2 缺省理论,一个缺省理论由两个部分组成,即缺省规则 集D和公式集W,一般用二元组来表示 若D中的规则是闭规则时,则为闭缺省理论。,定义:设 为一闭缺省理论, 为关于D的 一个算子,作用于任意的命题集合S,而其值为满 足下列三个性质的最小命题集合(S):(1) W (S)(2) Th(S) = (S),其中Th(S) = A|(S) A(3) 如果D中有规则 ,且(S),1, , m S ,那么(S),4.3 缺省理论的扩充,定义:对命题集合E,如果(E) = E,则E称为关于 D的算子的不动点(fixpoint)。此时称E为缺省理论 的一个扩充(extension)。,例1:设D ,W ,计算缺省理论 的扩充。, 有唯一的扩充E Th(B, F)。,例2:设 D ,W B, CFA, AC E,计算缺省理论 的扩充。, 有三个扩充 E1 Th(WA, C) E2 Th(WA, E) E3 Th(WC, E, G),5.限定推理,
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号