《【计算机】aai02人工智能逻辑》由会员分享，可在线阅读，更多相关《【计算机】aai02人工智能逻辑（63页珍藏版）》请在金锄头文库上搜索。
1、人工智能逻辑,中国科学院计算技术研究所 智能信息处理重点实验室,主要内容,逻辑简介 逻辑程序设计 非单调逻辑 缺省逻辑 限定逻辑 真值维护系统 情景演算,1. 逻辑简介,逻辑的历史 逻辑系统 命题逻辑 谓词逻辑,1.1 逻辑的历史,Aristotle逻辑学 Leibnitz数理逻辑 Gottlob Frege (1848-1925)一阶谓词演算系统,符号论 20世纪30年代，数理逻辑广泛发展,1.2 逻辑系统,一个逻辑系统是定义语言和它的含义的方法。 逻辑系统中的一个逻辑理论是该逻辑的语言的一 个语句集合，它包括： 逻辑符号集合：在所有该逻辑的逻辑理论中均出现的符号； 非逻辑符号集合：不同的逻
2、辑理论中出现的不同的符号； 语句规则：定义什么样的符号串是有意义的； 证明：什么样的符号串是一个合理的证明； 语义规则：定义符号串的语义。,逻辑与程序语言的对比,一个证明是一个语法结构，它由符号串根据一定 的规则组成。它包括假设和结论。 在公理化逻辑中，逻辑给出一个逻辑公理和推理 规则的集合。推理规则是可以从一个语句的集合得到 另一语句的集合。 公理化逻辑中的证明就是一个语句序列，使得 其中的每个语句要么是逻辑公理，要么是一个假设， 要么是由前面的语句通过推理规则得到的。,证明,在语法上，如果存在一个从假设到的证明， 则记为 ，称由可推导出的，或可证明的。 如果在没有任何假设下是可推导出的，则
3、记为 ，称为可证明的。 称一个假设是不协调的，如果存在一个语句 使得和的否定均可由推导得出。 称一个逻辑系统是一致的，或相容的(consistent)， 如果不存在逻辑系统的公式A，使得A与A同时成 立。,证 明(语法),语言的解释是在某个论语(domain)中定义非逻辑 符号。语句的语义是在解释下定义出语言L的真假值。 如果I是L的一个解释，且在I中为真，则记为 I ，称作I满足 ，或者I 是的一个模型。 类似地，给定一个语句和一个语句 ，如果对 每个解释I ，有I 蕴含I ，换言之，如果I 是 的一个模型则I也是的一个模型，则记为 ，我 们称为的一个逻辑结果。,解 释(语义),可靠性(re
4、liable) 一个逻辑是可靠的，如果它的证明保持真假值， 即在任何解释I下，如果I是 的模型，且可由推导 出，则I也是的一个模型。即，一个逻辑是可靠的， 如果对任何语句集合和语句 ， 蕴涵 。,可靠性和完备性,完备性(complete) 一个逻辑是完备的，如果任何永真语句是可证的。 即，对任何语句集合和语句 ， 蕴涵 。 如果一个逻辑是完备的，则该逻辑的证明系统已强到 可以推出任何永真式。 Gdel完备性定理：一阶逻辑是完备的,可判定的 一个逻辑称为是可判定的(decidable)，如果存在 一个算法对逻辑中的任一公式 A，可确定 A是否成 立。否则，称为是不可判定的(undecidable
5、) 。 如果上述算法虽不一定存在，却有一个过程，可对该系统的定理做出肯定的判断，但对非定理的公式过程未必终止，因而未必能作出判断。这时称逻辑是半可判定的。,可判定性,一阶逻辑是不可判定的，但它是半可判定的。,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
6、 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能导出空
7、子句(有否证)，则称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, t
8、rain) 首先目标中过程调用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被用于问题求解系统。 此后，它在许多领域获得了应用，如关系数据库、定理证明、智能问题求解、计算机辅助设
9、计、规划生成等领域。,Prolog的构成,事实：关于对象性质和关系的事实语句； student(john)，married(tom,mary) 规则：关于对象性质和关系的定义规则语句； 它与事实的不同在于，规则所定义的性质、关系依 赖与其它的性质和关系，因此规则呈蕴涵语句形式。B: A “如果A则B” bird(x) : animal(x)，has(x, feather) 问题：关于对象性质或关系的询问。? student(john)? married(mary，x),Prolog的执行方式,搜索：在程序中自上而下地搜索事实和规则；匹配：将目标中的项与事实和规则进行匹配；回溯：当目标中一项失败
10、时，如果目标中有已经成功的的项(应在失败项的左边)，那末就重新调用这些成功项中最右边的一个，谋求新的成功。,Prolog语言的基本文法,Prolog语言的最基本语言成分是项(term)，一个 项或者是常量，或者是变量，或者是一个结构。 常量：是指对象和对象之间的特定关系的名；整数，如0，22，1586等；原子，如John，student，likes，sister-of 变量：表示任意的对象，它与FOL中的变元相同；Prolog中变量可以用大写字母，下划线，以及由它们 开头的字母串。如X, Y, Answer, _value等。 结构：是常量和变量的序列，它由一个函子(函词 或谓词)和该函子的自
11、变量所组成。如： 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) (
12、bell / X),(7)? likes(X, sports), likes(X, smith),(8)? likes(mary, smith) (mary / X),Prolog的基本特点,Horn子句逻辑是Prolog的基础。 Prolog既是一种逻辑程序设计语言，又是一个逻辑系统。 Prolog是一种描述性语言，它是一种面向问题的语言，你只需要告诉它要做什么，即给出问题的形式描述，而不需要知道应该如何做。 Prolog完全依靠匹配、回溯来进行搜索。Prolog的求解过程是一个寻求否证的消解过程。 Prolog也使用元语言种的谓词，有很强的描述能力。 Prolog采用统一的数据结构项，它包
13、含控制成分，且有专门进行数值计算和符号处理的模块。,3. 非单调逻辑,单调逻辑 非单调逻辑 区别,3.1 单调逻辑,在现有知识的基础上，通过严密的逻辑论证和推理获得的新知识必须与已有的知识相一致。 A，AB B 推理系统的定理集合随着推理过程的进行而单调地增大。单调性：(1) Th( )(2) 若 1 2 ，则Th(1) Th(2)(3) Th(Th( ) Th( ) (不动点),3.2 非单调逻辑,推理系统的定理集合并不随着推理过程的进行而单调地增大，新推出地定理很可能会否定、改变原来地一些定理，使得原来能够解释地某些现象变得不能解释了。新规则：(4) P (不动点),4. 缺省逻辑,198
14、0年，Reiter提出了缺省逻辑(Default Logic)。“一般情况下鸟是会飞的”“鸵鸟不会飞” “企鹅不会飞”,4.1 缺省规则,一个缺省规则是如下形式的规则：,(x):称为前提条件i(x):称为缺省条件，或检验条件 (x):称为结论 为简便，通常情况下可以省略检验条件中的M。 规则的使用： 如果规则的前提条件满足，且现有的知识导不 出检验条件的否定i(x)，则可以得出结论成立。,4.2 缺省理论,一个缺省理论由两个部分组成，即缺省规则 集D和公式集W，一般用二元组来表示 若D中的规则是闭规则时，则为闭缺省理论。,定义：设 为一闭缺省理论， 为关于D的 一个算子，作用于任意的命题集合S
15、，而其值为满 足下列三个性质的最小命题集合(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.限定推理,
