《逻辑基础》

1、2021-4-23史忠植 逻辑基础1 第二章第二章 人工智能逻辑人工智能逻辑 第一部分第一部分 史忠植史忠植 中国科学院计算技术研究所中国科学院计算技术研究所 高级人工智能高级人工智能 2021-4-23史忠植 逻辑基础2 主要内容主要内容 逻辑简介 逻辑程序设计 非单调逻辑 默认逻辑 限定逻辑 真值维护系统 情景演算 2021-4-23史忠植 逻辑基础3 1. 逻辑简介逻辑简介 逻辑的历史 逻辑系统 命题逻辑 谓词逻辑 2021-4-23史忠植 逻辑基础4 1.1 逻辑的历史 Aristotle逻辑学 Leibnitz数理逻辑 Gottlob Frege (1848-1925)一阶谓 词演算

2、系统,符号论 20世纪30年代，数理逻辑广泛发展 2021-4-23史忠植 逻辑基础5 1.2 逻辑系统 一个逻辑系统是定义语言和它的含义的方法。 逻辑系统中的一个逻辑理论是该逻辑的语言的一 个语句集合，它包括： 逻辑符号集合逻辑符号集合：在所有该逻辑的逻辑理论中均出现的符号； 非逻辑符号集合非逻辑符号集合：不同的逻辑理论中出现的不同的符号； 语句规则语句规则：定义什么样的符号串是有意义的； 证明证明：什么样的符号串是一个合理的证明； 语义规则语义规则：定义符号串的语义。 2021-4-23史忠植 逻辑基础6 逻辑逻辑程序语言程序语言 逻辑符号保留字或者符号 非逻辑符号 用户自定义的符号(变量

3、名， 函数名等) 语句规则构造一个程序的语句规则 语义规则定义程序做什么的语句规则 推理规则、公理和证明没有 逻辑与程序语言的对比 2021-4-23史忠植 逻辑基础7 一个证明证明是一个语法结构，它由符号串根据一定 的规则组成。它包括假设和结论。 在公理化逻辑中，逻辑给出一个逻辑公理逻辑公理和推理推理 规则规则的集合。推理规则是可以从一个语句的集合得到 另一语句的集合。 公理化逻辑中的证明就是一个语句序列，使得公理化逻辑中的证明就是一个语句序列，使得 其中的每个语句要么是逻辑公理，要么是一个假设，其中的每个语句要么是逻辑公理，要么是一个假设， 要么是由前面的语句通过推理规则得到的。要么是由前

4、面的语句通过推理规则得到的。 证 明 2021-4-23史忠植 逻辑基础8 在语法上，如果存在一个从假设到的证明， 则记为 ，称由可推导出的，或可证明的可证明的。 如果在没有任何假设下是可推导出的，则记为 ，称为可证明的。 称一个假设是不协调的不协调的，如果存在一个语句 使得和的否定均可由推导得出。 称一个逻辑系统是一致的一致的，或相容的相容的(consistent)， 如果不存在逻辑系统的公式A，使得A与A同时成 立。 证 明(语法) 2021-4-23史忠植 逻辑基础9 语言的解释解释是在某个论域(domain)中定义非逻辑 符号。语句的语义是在解释下定义出语言L的真假值。 如果I是L的一

5、个解释，且在I中为真，则记为 I ，称作I满足 ，或者I 是的一个模型模型。 类似地，给定一个语句和一个语句 ，如果对 每个解释I ，有I 蕴含I ，换言之，如果I 是 的一个模型则I也是的一个模型，则记为 ，我 们称为的一个逻辑结果逻辑结果。 解 释(语义) 2021-4-23史忠植 逻辑基础10 可靠性可靠性(reliable) 一个逻辑是可靠的，如果它的证明保持真假值， 即在任何解释I下，如果I是 的模型，且可由推导 出，则I也是的一个模型。即，一个逻辑是可靠的， 如果对任何语句集合和语句 ， 蕴涵 。 可靠性和完备性 完备性完备性(complete) 一个逻辑是完备的，如果任何永真语句

6、是可证的。 即，对任何语句集合和语句 ， 蕴涵 。 如果一个逻辑是完备的，则该逻辑的证明系统已强到 可以推出任何永真式。 G Gdeldel完备性定理：完备性定理：一阶逻辑是完备的一阶逻辑是完备的 2021-4-23史忠植 逻辑基础11 可判定的可判定的 一个逻辑称为是可判定的可判定的(decidable)，如果存在 一个算法对逻辑中的任一公式 A，可确定 A是否成 立。否则，称为是不可判定的不可判定的(undecidable) 。 如果上述算法虽不一定存在，却有一个过程，可对该 系统的定理做出肯定的判断，但对非定理的公式过 程未必终止，因而未必能作出判断。这时称逻辑是 半可判定的半可判定的。

7、 可判定性 一阶逻辑是不可判定的，但它是半可判定的。一阶逻辑是不可判定的，但它是半可判定的。 2021-4-23史忠植 逻辑基础12 现代逻辑学与计算机科学、计算语言学和人工智能的关系表现代逻辑学与计算机科学、计算语言学和人工智能的关系表 逻逻 辑辑 自然语自然语 程序程序 人工人工 逻辑逻辑 指令与直指令与直 数据库数据库 复杂性复杂性 智能体智能体 未未 来来 展展 望望 言处理言处理 控制控制 智能智能 编程编程 陈式语言陈式语言 理论理论 理论理论 理论理论 时序逻辑时序逻辑 广泛应用广泛应用 模态逻辑模态逻辑 非常活跃非常活跃 算法证明算法证明 非单调推理非单调推理 意义重大意义重大

8、 概率和模糊概率和模糊 目前主流目前主流 直觉主义逻辑直觉主义逻辑 主要替代者主要替代者 高阶逻辑，高阶逻辑，-演算演算 更具中心作用更具中心作用 经典逻辑片断经典逻辑片断 前景诱人前景诱人 资源和子结构逻辑资源和子结构逻辑 纤维化和组合逻辑纤维化和组合逻辑 可自我指称可自我指称 谬误理论谬误理论 在适当语境在适当语境 逻辑动力学逻辑动力学 动态逻辑观动态逻辑观 论辩理论游戏论辩理论游戏 前景光明前景光明 对象层次对象层次/ /元层次元层次 总起中心作用总起中心作用 机制机制: :溯因溯因 缺省缺省 相干相干 逻辑的一部分逻辑的一部分 与神经网络的联系与神经网络的联系 极重要，刚开始极重要，刚

9、开始 时间时间- -行动行动- -修正模型修正模型 一类新模型一类新模型 加标演绎系统加标演绎系统 逻辑学的统一框架逻辑学的统一框架 2021-4-23史忠植 逻辑基础13 1.3 命题逻辑 命题是可以确定其真假的陈述句。 Bolle提出了布尔代数。 语言语言: ，；公式，原子公式 公理模式公理模式: : (A(BA) (A(BC) (AB)(AC) (A)(B) (BA) 推理规则推理规则: :分离规则(modus ponens，MP规则) B BAA, 2021-4-23史忠植 逻辑基础14 1.4 谓词逻辑(一阶逻辑) Frege谓词演算 语言语言: ，(，)；常元，变元，函词，谓词；公

10、式 公理模式公理模式: : (A(BA) (A(BC) (AB)(AC) (A)(B) (BA) vA Atv (t对A中变元v可代入) v(A B) (vA vB) A vA (v在A中无自由出现) 推理规则推理规则: :分离规则 B BAA, 2021-4-23史忠植 逻辑基础15 谓词逻辑与命题逻辑的区别谓词逻辑与命题逻辑的区别 谓词逻辑给出了原子语句的内部结构，将原子 公式看作是事物直接的关系； 它引入了“推广”(泛化)，加强了逻辑的表示 能力和推理能力。这样，我们可以说某种性质 对某个对象是成立的，或对所有的对象成立， 或不对任何对象成立。 2021-4-23史忠植 逻辑基础16 2

11、. 2. 逻辑程序设计逻辑程序设计 消解原理(归结原理) Horn逻辑 Prolog逻辑程序设计语言 2021-4-23史忠植 逻辑基础17 2.1 归结原理归结原理 例： C1 = PQR C2 = PQ 则C1与C2归结后的结果为：QR 若子句集S能导出空子句 (有否证)，则称S 是不可满足的。 反证法：S A iff S A Q QPP, Q QPP, 2021-4-23史忠植 逻辑基础18 2.2 Horn逻辑 文字文字：原子公式(正文字)或原子公式的否定(负文字)。 P, Q, R 子句子句：若干文字的析取。PQR Horn子句子句： 子句L1L2 Ln中如果至多只含一个正文字， 那

12、么该子句称为Horn子句。 Horn子句P Q1 Q2 Qn通常表示为： P Q1, Q2, , Qn 2021-4-23史忠植 逻辑基础19 HornHorn子句的类型：子句的类型： 过程：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)，与

13、事实匹配，产生目 标 。因而调用成功，输出“是”。 2021-4-23史忠植 逻辑基础20 2.3 Prolog Prolog(Programminginlogic)语言是以Horn子句 逻辑为基础的高级程序设计语言。 1972年，法国马赛大学的Alain. Colmerauer提出 了Prolog的雏型。 1975年，Prolog被用于问题求解系统。 此后，它在许多领域获得了应用，如关系数据库、 定理证明、智能问题求解、计算机辅助设计、规 划生成等领域。 2021-4-23史忠植 逻辑基础21 Prolog的构成的构成 事实：关于对象性质和关系的事实语句； student(john)，mar

14、ried(tom,mary) 规则：关于对象性质和关系的定义规则语句； 它与事实的不同在于，规则所定义的性质、关系依 赖与其它的性质和关系，因此规则呈蕴涵语句形式。 B: A“如果A则B” bird(x): animal(x)，has(x,feather) 问题：关于对象性质或关系的询问。 ? student(john) ? married(mary，x) 2021-4-23史忠植 逻辑基础22 Prolog的执行方式的执行方式 搜索：在程序中自上而下地搜索事实和规则； 匹配：将目标中的项与事实和规则进行匹配； 回溯：当目标中一项失败时，如果目标中有已经 成功的的项(应在失败项的左边)，那末就

15、重新调 用这些成功项中最右边的一个，谋求新的成功。 2021-4-23史忠植 逻辑基础23 Prolog语言的基本文法语言的基本文法 Prolog语言的最基本语言成分是项(term)，一个 项或者是常量，或者是变量，或者是一个结构。 常量：是指对象和对象之间的特定关系的名； 整数整数，如0，22，1586等； 原子原子，如John，student，likes，sister-of 变量：表示任意的对象，它与FOL中的变元相同； Prolog中变量可以用大写字母，下划线，以及由它们 开头的字母串。如X, Y,Answer,_value等。 结构：是常量和变量的序列，它由一个函子(函词 或谓词)和该

16、函子的自变量所组成。如： likes(john,X)married(mary,jack) 2021-4-23史忠植 逻辑基础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)?likes(X,sports),likes(X,smith) (8)? likes(bell,smith)(bell/

17、X) (7)?likes(X,sports),likes(X,smith) (8)? likes(mary,smith)(mary/X) Y = mary，John与与Mary是朋友是朋友 2021-4-23史忠植 逻辑基础25 Prolog的基本特点的基本特点 Horn子句逻辑是Prolog的基础。 Prolog既是一种逻辑程序设计语言，又是一个逻辑 系统。 Prolog是一种描述性语言，它是一种面向问题的语 言，你只需要告诉它要做什么，即给出问题的形式 描述，而不需要知道应该如何做。 Prolog完全依靠匹配、回溯来进行搜索。Prolog的 求解过程是一个寻求否证的消解过程。 Prolog

18、也使用元语言种的谓词，有很强的描述能力。 Prolog采用统一的数据结构项，它包含控制成 分，且有专门进行数值计算和符号处理的模块。 2021-4-23史忠植 逻辑基础26 3. 非单调逻辑非单调逻辑 单调逻辑 非单调逻辑 区别 2021-4-23史忠植 逻辑基础27 3.1 单调逻辑 在现有知识的基础上，通过严密的逻辑论证和 推理获得的新知识必须与已有的知识相一致。 A，AB B 推理系统的定理集合随着推理过程的进行而单 调地增大。 单调性：单调性： (1) Th( ) (2) 若 12，则Th(1)Th(2) (3) Th(Th( )Th( )(不动点) 2021-4-23史忠植 逻辑基础

19、28 3.2 非单调逻辑 推理系统的定理集合并不随着推理过程的进行 而单调地增大，新推出的定理很可能会否定、 改变原来的一些定理，使得原来能够解释的某 些现象变得不能解释了。 新规则： (4) P(不动点) 2021-4-23史忠植 逻辑基础29 4. . 默认逻辑默认逻辑 1980年，Reiter提出了默认逻辑(Default Logic)。 “一般情况下鸟是会飞的” “鸵鸟不会飞” “企鹅不会飞” )( )(: )( xfly xMflyxBird 会飞 会飞”与系统不矛盾“是鸟 x xx: 2021-4-23史忠植 逻辑基础30 4.1 默认规则 一个默认规则是如下形式的规则： )( )

20、(,),(: )( 1 x xMxMx n (x):称为前提条件 i(x):称为默认条件，或检验条件 (x):称为结论 为简便，通常情况下可以省略检验条件中的M。 规则的使用：规则的使用： 如果规则的前提条件满足，且现有的知识导不 出检验条件的否定i(x)，则可以得出结论成立。 2021-4-23史忠植 逻辑基础31 4.2 默认理论 一个默认理论由两个部分组成，即默认规则 集D和公式集W，一般用二元组来表示 若D中的规则是闭规则时，则为闭默认理论。 定义：设为一闭默认理论，为关于关于D的的 一个算子一个算子，作用于任意的命题集合S，而其值为满 足下列三个性质的最小命题集合(S)： (1)W

21、(S) (2)Th(S)=(S)，其中Th(S)=A|(S)A (3)如果D中有规则， 且(S)，1, , m S ，那么(S) n MM,: 1 2021-4-23史忠植 逻辑基础32 4.3 默认理论的扩充 定义：对命题集合E，如果(E)=E，则E称为关于 D的算子的不动点(fixpoint)。此时称E为默认理论 的一个扩充(extension)。 例1：设D，W，计算默认 理论的扩充。 F C C B B A : , : , : 有唯一的扩充E Th(B,F)。 2021-4-23史忠植 逻辑基础33 例2：设 D， WB, CFA, AC E，计算默认理论 的扩充。 G AFAEC E

22、 EAF C CB A A,: , : , : , : 有三个扩充 E1 Th(WA,C) E2 Th(WA,E) E3 Th(WC,E, G) 2021-4-23史忠植 逻辑基础34 5. .限定推理限定推理 1980年，McCarthy提出了一种非单调的推理 限定推理限定推理(Circumscription)。 基本思想基本思想：从某些事实A出发能够推出具有某一性质 的P的对象就是满足性质P的全部对象。只有当发 现其它对象也具有该性质时，才修改这种看法。 2021-4-23史忠植 逻辑基础35 限定逻辑限定逻辑 限定逻辑CIRC是一种极小化逻辑。下面，从一个基于 极小模型定义的命题限定出发

23、，给出限定的基本定义, 进 而给出一阶限定的基本结果，并将它推广。 定义 2.1 设L0是一个命题语言，p1,p2是在命题语言L0 中 的两个赋值。称p1小于p2 ，记为p1 p2, 当且仅当对任一 命题变元x, 如果p1(x) = l, 则p2(x) = l。 2021-4-23史忠植 逻辑基础36 限定逻辑限定逻辑 定义 2.2 设A 是一个公式，称A的一个赋值p是极小 的，当且仅当不存在A的其它赋值p使得 p p。 显然, 是一个偏序关系。p1 p2表示p1包含的真命题 比p2 少。极小赋值包含的真命题极小。 定义 2.3 极小后承M。 设A, B是两个公式，A M B 当且仅当B在所有

24、A 的极小模型中都为真。 极小模型是非单调的，它以命题的极小化作为优先模 型的准则。 2021-4-23史忠植 逻辑基础37 限定逻辑限定逻辑 定义 2.4 设A是一个包含命题集 P = p1,p2,. , pn 的公式，一个A的赋值p称为 Z-极小赋值，当且仅 当不存在A的其它赋值p使得p p, 定义如下：设p1, p2 是两个赋值， p1 Z- p2 当且仅当对任一z Z, 若p1 (Z) = l, 则 p2 (Z)= l。 2021-4-23史忠植 逻辑基础38 限定逻辑限定逻辑 定义 2.5 命题限定P 或 CIRC(A,P)。设A是一个 包含命题集的公式， 是一个公式，A P 当且仅

25、 当 在所有A的 p- 极小赋值中都为真。 定理 2.1 A p 当且仅当A P 2021-4-23史忠植 逻辑基础39 限定逻辑限定逻辑 定义 2.6 令L是一个一阶语言，T是一个L的公式，它 包含谓词元组集。设MT和 M*T是公式T的两个模型。 定义M*T优先于MT, 记为M*T MT，当且仅当 (1) M和M*有相同的对象域， (2) 除外，公式T中所有的其它关系和函数常数 在M和M*都有相同的解释， (3) 在M*中的外延是在M中的子集。 2021-4-23史忠植 逻辑基础40 限定逻辑限定逻辑 一个理论T的模型M称为优先的，当且仅当不存在T的 其它模型M使得M M。 定义 2.7 M

26、m是的最小模型，当且仅当 M Mm , M = Mm 2021-4-23史忠植 逻辑基础41 限定逻辑限定逻辑 例如 设论域 D=1,2 T=xy(P(y)Q(x,y) =(P(1) Q(1,1) (P(2) Q(1,2) (P(1) Q(2,1) (P(2) Q(2,2) M: P(1) P(2) Q(1,1) Q(1,2) Q(2,1) Q(2,2) T T F T F T M*: P(1) P(2) Q(1,1) Q(1,2) Q(2,1) Q(2,2) F T F T F T 2021-4-23史忠植 逻辑基础42 6. .真值维护系统真值维护系统TMSTMS 1979年，Doyle提

27、出了一种非单调推理系统 真值维护系统真值维护系统(Truth Maintenance System) 真值维护系统是大型推理系统的的一个子系统， 实现知识库中信念(belief)的修改与维护。其基本问 题有： 必须在不完全的、有限的信息基础上作出假设的决 策，使得该假设成为知识库的信念； 当这些决策的结论被以后的事实证明为错误时，如 何对其信念进行修正。 2021-4-23史忠植 逻辑基础43 基本数据结构基本数据结构: 结点结点：表示信念 理由理由：表示信念的原因 信念既包括已知的知识，也包括假设的知识。 基本操作基本操作： 新结点的形成新结点的形成将信念赋予该结点； 新理由的加入新理由的加

28、入把某个信念与该结点联接起来 实现过程实现过程： 默认假设的形成； 相关性回溯过程。 2021-4-23史忠植 逻辑基础44 6.1 信念知识表示 每一个命题或规则均称为结点，它分为两类： IN-IN-结点结点：相信为真 OUT-OUT-结点结点：不相信为真，或无理由相信为真， 或当前没有任何有效的理由。 每个结点附有理由表，表示具体结点的有效性： 支持表支持表SLSL：所在结点的信念的原因，理由； 条件证明条件证明CPCP：出现矛盾的原因。 2021-4-23史忠植 逻辑基础45 (SL()() IN-结点表中的IN-结点表示知识库中的已知知识; OUT-结点表中的OUT-结点表示这些结点的

29、否定。 例例1 1: (1) 现在是夏天(SL( )( ) (2) 天气很潮湿(SL(1)( ) 结点(1)不依赖于任何别的结点中的当前信念或 默认信念,因而这种结点称为前提; 结点(2)则依赖于当前结点(1)的信念. 所以，与一阶逻辑不同的是,TMS可以撤消前提, 并可以对知识库作适当修改. （1）支持表SL 2021-4-23史忠植 逻辑基础46 例例2 2: (1) 现在是夏天(SL( )( ) (2) 天气很潮湿(SL(1)(3) (3) 天气很干燥 若结点(1)是IN,结点(3)是OUT,则结点(2)才为IN. 若在某个时刻出现结点(3)的证据,则结点(2)就变为 OUT,因为它不再

30、有一个有效的证实.象结点(2)这样 的结点称为假设,它与非空的OUT结点表的SL证实有 关.OUT结点(3)是结点(2)的证实的一部分.但如果结 点(3)不存在,就不能这样表示了. 在TMS中,它仅利用证实来维持一个相容的信念 数据库,而它本身并不产生证实. 2021-4-23史忠植 逻辑基础47 (CP (CP ) 如果结论结点为IN-结点,以及下列条件成立: (1) IN假设中的每个结点都是IN-结点; (2) OUT-假设中的每个结点都是OUT-结点. 那么条件证明CP是有效的. 一般说来,OUT-假设总是空集.TMS要求假设集划 分成两个不相交的子集,分别为不导致矛盾的假设和 导致矛盾

31、的假设. 通常只要在IN-假设中的结点为IN,OUT-假设中 的结点为OUT,则结论结点为IN. （2）条件证明CP 2021-4-23史忠植 逻辑基础48 6.2 默认假设 令F1,F2,Fn表示所有可能的侯选的默认假 设结点集,G表示选择默认假设的原因的结点,即由G 引起在F1,Fn中进行默认选择.这样我们结合结 点Node(Fi)以如下理由: (SL(G)(F1,Fi-1 ,Fi+1,Fn) 而选取Fi为默认假设. 如果不存在任何其它关于如何进行选择的信息， 则可以认为除Fi之外其它任何时候选都不是可信 的 这样Fi为IN,其它Fj(i j)均为OUT.但如果接收到一 个有效的理由支持某

32、个其它的侯选Fj,则Fj就为IN, 而导致Fi的假设失败而变为OUT. 2021-4-23史忠植 逻辑基础49 6.3 相关回溯 当知识库中出现不一致时,TMS将寻找并删除已 做的一个不正确的默认逻辑,恢复一致性.它包括三 个步骤: (1) 从产生的矛盾结点开始,回溯跟踪该矛盾结点 的理由充足的支持以寻找矛盾的假设集,并从中去掉 至少一个假设信念以消除矛盾. (2) 构造一个结点记录矛盾产生的原因. (3) 从S中选取假设A(即不合理假设),并证实列在 其理由充足的支持条件中的一个OUT-结点. 2021-4-23史忠植 逻辑基础50 (4) 矛盾(SL(1,3)( ) (周三14:00没有空

33、会议室) 例例3 3: (1) 会议日期为星期三(SL( )(2) (2) 会议日期不应是星期三 (3) 会议时间为14:00(SL(32,40,61)() (5) 不相容(CP4 (1,3)( ) (2) 会议日期不应是星期三(SL(5)( ) 结点(2)与结点(5)为IN,就引起结点(1)为OUT,因为 结点(1)的证实依赖于结点(2)是OUT.结点(4)现在也 变成OUT.进而矛盾就消除了. 2021-4-23史忠植 逻辑基础51 7 情景演算 情景演算是一种一阶逻辑语言，主要是用来表示动态 变化的世界的。世界的所有变化过程都是“动作”的结果。 一个可能世界历史可以简单表示为动作的序列，它是通过 称之为情景的一阶项所表示的。 常量S0表示初始情景，即动作还没有发生时的情景。 do(,s)表示在情景s中执行动作之后的后继情景。 do(put(A,B