《人工智能逻辑教学文案》由会员分享，可在线阅读，更多相关《人工智能逻辑教学文案（92页珍藏版）》请在金锄头文库上搜索。
1、人工智能逻辑,2020/7/22,史忠植 逻辑基础,1,史忠植 中国科学院计算技术研究所,高级人工智能 第二章,主要内容,逻辑简介 逻辑程序设计 非单调逻辑 默认逻辑 限定逻辑 真值维护系统 情景演算 动态描述逻辑,2020/7/22,史忠植 逻辑基础,2,逻辑简介,逻辑的历史 逻辑系统 命题逻辑 谓词逻辑,2020/7/22,史忠植 逻辑基础,3,逻辑的历史,Aristotle逻辑学 Leibnitz数理逻辑 Gottlob Frege (1848-1925)一阶谓词演算系统,符号论 20世纪30年代，数理逻辑广泛发展,2020/7/22,史忠植 逻辑基础,4,2020/7/22,史忠植 逻
2、辑基础,6,逻辑与程序语言的对比,2020/7/22,史忠植 逻辑基础,7,一个证明是一个语法结构，它由符号串根据一定 的规则组成。它包括假设和结论。 在公理化逻辑中，逻辑给出一个逻辑公理和推理 规则的集合。推理规则是可以从一个语句的集合得到 另一语句的集合。 公理化逻辑中的证明就是一个语句序列，使得 其中的每个语句要么是逻辑公理，要么是一个假设，要么是由前面的语句通过推理规则得到的。,证 明,2020/7/22,史忠植 逻辑基础,8,在语法上，如果存在一个从假设到的证明， 则记为 ，称由可推导出的，或可证明的。 如果在没有任何假设下是可推导出的，则记为 ，称为可证明的。 称一个假设是不协调的
3、，如果存在一个语句 使得和的否定均可由推导得出。 称一个逻辑系统是一致的，或相容的(consistent)， 如果不存在逻辑系统的公式A，使得A与A同时成 立。,证 明(语法),2020/7/22,史忠植 逻辑基础,9,语言的解释是在某个论域(domain)中定义非逻辑 符号。语句的语义是在解释下定义出语言L的真假值。 如果I是L的一个解释，且在I中为真，则记为 I ，称作I满足 ，或者I 是的一个模型。 类似地，给定一个语句和一个语句 ，如果对 每个解释I ，有I 蕴含I ，换言之，如果I 是 的一个模型则I也是的一个模型，则记为 ，我 们称为的一个逻辑结果。,解 释(语义),2020/7/
4、22,史忠植 逻辑基础,10,可靠性(reliable) 一个逻辑是可靠的，如果它的证明保持真假值， 即在任何解释I下，如果I是 的模型，且可由推导 出，则I也是的一个模型。即，一个逻辑是可靠的， 如果对任何语句集合和语句 ， 蕴涵 。,可靠性和完备性,完备性(complete) 一个逻辑是完备的，如果任何永真语句是可证的。 即，对任何语句集合和语句 ， 蕴涵 。 如果一个逻辑是完备的，则该逻辑的证明系统已强到 可以推出任何永真式。 Gdel完备性定理：一阶逻辑是完备的,2020/7/22,史忠植 逻辑基础,11,可判定的 一个逻辑称为是可判定的(decidable)，如果存在 一个算法对逻辑
5、中的任一公式 A，可确定 A是否成 立。否则，称为是不可判定的(undecidable) 。 如果上述算法虽不一定存在，却有一个过程，可对该系统的定理做出肯定的判断，但对非定理的公式过程未必终止，因而未必能作出判断。这时称逻辑是半可判定的。,可判定性,一阶逻辑是不可判定的，但它是半可判定的。,现代逻辑学与计算机科学、计算语言学和人工智能的关系表 逻 辑 自然语 程序 人工 逻辑 指令与直 数据库 复杂性 智能体 未 来 展 望 言处理 控制 智能 编程 陈式语言 理论 理论 理论 时序逻辑 广泛应用 模态逻辑 非常活跃 算法证明 非单调推理 意义重大 概率和模糊 目前主流 直觉主义逻辑 主要替
6、代者 高阶逻辑，-演算 更具中心作用 经典逻辑片断 前景诱人 资源和子结构逻辑 纤维化和组合逻辑 可自我指称 谬误理论 在适当语境 逻辑动力学 动态逻辑观 论辩理论游戏 前景光明 对象层次/元层次 总起中心作用 机制:溯因 缺省 相干 逻辑的一部分 与神经网络的联系 极重要，刚开始 时间-行动-修正模型 一类新模型 加标演绎系统 逻辑学的统一框架,2020/7/22,史忠植 逻辑基础,12,命题逻辑,命题是可以确定其真假的陈述句。 Bolle提出了布尔代数。 语言: ，；公式，原子公式 公理模式: (A (B A) (A (B C) (A B) (A C) (A)(B) (B A) 推理规则:
7、分离规则(modus ponens，MP规则),2020/7/22,史忠植 逻辑基础,13,谓词逻辑(一阶逻辑),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中无自由出现) 推理规则:分离规则,2020/7/22,史忠植 逻辑基础,14,谓词逻辑与命题逻辑的区别,2020/7/22,史忠植 逻辑基础,15,谓词逻辑给出了原子语句的内部结构，将原子公式看作是事物直接的关系； 它引入了“推广
8、”(泛化)，加强了逻辑的表示能力和推理能力。这样，我们可以说某种性质对某个对象是成立的，或对所有的对象成立，或不对任何对象成立。,逻辑程序设计,归结原理(消解原理) Horn逻辑 Prolog逻辑程序设计语言,2020/7/22,史忠植 逻辑基础,16,归结原理,例： C1 = PQR C2 = PQ 则C1与C2归结后的结果为：QR 若子句集S能导出空子句(有否证)，则称S 是不可满足的。 反证法： S A iff S A ,2020/7/22,史忠植 逻辑基础,17,Horn逻辑,文字：原子公式(正文字)或原子公式的否定(负文字)。 P, Q, R 子句：若干文字的析取。PQR Horn子
9、句： 子句L1L2 Ln中如果至多只含一个正文字， 那么该子句称为Horn子句。 Horn子句P Q1 Q2 Qn通常表示为： P Q1, Q2, , Qn,2020/7/22,史忠植 逻辑基础,18,Horn子句的类型,2020/7/22,史忠植 逻辑基础,19,过程：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
10、，调用过程AT(Zhang, x)，从而 产生新目标 AT(Zhang, train)，与事实匹配，产生目 标 。因而调用成功，输出“是”。,Prolog,Prolog(Programming in logic)语言是以Horn子句逻辑为基础的高级程序设计语言。 1972年，法国马赛大学的Alain. Colmerauer提出了Prolog的雏型。 1975年，Prolog被用于问题求解系统。 此后，它在许多领域获得了应用，如关系数据库、定理证明、智能问题求解、计算机辅助设计、规划生成等领域。,2020/7/22,史忠植 逻辑基础,20,Prolog的构成,事实：关于对象性质和关系的事实语句；
11、 student(john)，married(tom,mary) 规则：关于对象性质和关系的定义规则语句； 它与事实的不同在于，规则所定义的性质、关系依 赖与其它的性质和关系，因此规则呈蕴涵语句形式。 B: A“如果A则B” bird(x) : animal(x)，has(x, feather) 问题：关于对象性质或关系的询问。 ? student(john) ? married(mary，x),2020/7/22,史忠植 逻辑基础,21,2020/7/22,史忠植 逻辑基础,22,Prolog的执行方式,搜索：在程序中自上而下地搜索事实和规则； 匹配：将目标中的项与事实和规则进行匹配； 回溯
12、：当目标中一项失败时，如果目标中有已经成功的的项(应在失败项的左边)，那末就重新调用这些成功项中最右边的一个，谋求新的成功。,2020/7/22,史忠植 逻辑基础,23,Prolog语言的基本文法,Prolog语言的最基本语言成分是项(term)，一个 项或者是常量，或者是变量，或者是一个结构。 常量：是指对象和对象之间的特定关系的名； 整数，如0，22，1586等； 原子，如John，student，likes，sister-of 变量：表示任意的对象，它与FOL中的变元相同； Prolog中变量可以用大写字母，下划线，以及由它们 开头的字母串。如X, Y, Answer, _value等。
13、 结构：是常量和变量的序列，它由一个函子(函词 或谓词)和该函子的自变量所组成。如： likes(john, X)married(mary, jack),例子,2020/7/22,史忠植 逻辑基础,24,(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)? like
14、s(X, sports), likes(X, smith),(8)? likes(bell, smith) (bell / X),(7)? likes(X, sports), likes(X, smith),(8)? likes(mary, smith) (mary / X),2020/7/22,史忠植 逻辑基础,25,Prolog的基本特点,Horn子句逻辑是Prolog的基础。 Prolog既是一种逻辑程序设计语言，又是一个逻辑系统。 Prolog是一种描述性语言，它是一种面向问题的语言，你只需要告诉它要做什么，即给出问题的形式描述，而不需要知道应该如何做。 Prolog完全依靠匹配、回溯
15、来进行搜索。Prolog的求解过程是一个寻求否证的消解过程。 Prolog也使用元语言种的谓词，有很强的描述能力。 Prolog采用统一的数据结构项，它包含控制成分，且有专门进行数值计算和符号处理的模块。,非单调逻辑,单调逻辑 非单调逻辑 区别,2020/7/22,史忠植 逻辑基础,26,单调逻辑,在现有知识的基础上，通过严密的逻辑论证和推理获得的新知识必须与已有的知识相一致。 A，AB B 推理系统的定理集合随着推理过程的进行而单调地增大。 单调性： (1) Th( ) (2) 若 1 2 ，则Th(1) Th(2) (3) Th(Th( ) Th( ) (不动点),2020/7/22,史忠植 逻辑基础,27,2020/7/22,史忠植 逻辑基础,28,非单调逻辑,推理系统的定理集合并不随着推理过程的进行而单调地增大，新推出的定理很可能会否定、改变原来的一些定理，使得原来能够解释的某些现象变得不能解释了。 新规则： (4) P (不动点),默认逻辑,1980年，Reiter提出了默认逻辑(Default Logic)。 “一般情况下鸟是会飞的” “鸵鸟不会飞”“企鹅不会飞”,2020/7/22,史忠植 逻辑基础,29,2
