高级人工智能 第二章 人工智能逻辑 史忠植 中国科学院计算技术研究所 2017/9/11 史忠植 逻辑基础

主要内容 逻辑简介 逻辑程序设计 非单调逻辑 默认逻辑 限定逻辑 真值维护系统 情景演算 动态描述逻辑 2017/9/11 史忠植 逻辑基础

逻辑简介 逻辑的历史 逻辑系统 命题逻辑 谓词逻辑 2017/9/11 史忠植 逻辑基础

逻辑的历史 Aristotle——逻辑学 Leibnitz——数理逻辑 Gottlob Frege (1848-1925)——一阶谓词演算系统,《符号论》 20世纪30年代，数理逻辑广泛发展 2017/9/11 史忠植 逻辑基础

逻辑系统 一个逻辑系统是定义语言和它的含义的方法。 逻辑系统中的一个逻辑理论是该逻辑的语言的一 个语句集合，它包括： 逻辑符号集合：在所有该逻辑的逻辑理论中均出现的符号； 非逻辑符号集合：不同的逻辑理论中出现的不同的符号； 语句规则：定义什么样的符号串是有意义的； 证明：什么样的符号串是一个合理的证明； 语义规则：定义符号串的语义。 2017/9/11 史忠植 逻辑基础

逻辑与程序语言的对比 逻辑 程序语言 逻辑符号 保留字或者符号 非逻辑符号 用户自定义的符号(变量名，函数名等) 语句规则 构造一个程序的语句规则 语义规则 定义程序做什么的语句规则 推理规则、公理和证明 没有 2017/9/11 史忠植 逻辑基础

证 明 一个证明是一个语法结构，它由符号串根据一定 的规则组成。它包括假设和结论。 在公理化逻辑中，逻辑给出一个逻辑公理和推理 证 明 一个证明是一个语法结构，它由符号串根据一定 的规则组成。它包括假设和结论。 在公理化逻辑中，逻辑给出一个逻辑公理和推理 规则的集合。推理规则是可以从一个语句的集合得到 另一语句的集合。 公理化逻辑中的证明就是一个语句序列，使得 其中的每个语句要么是逻辑公理，要么是一个假设，要么是由前面的语句通过推理规则得到的。 2017/9/11 史忠植 逻辑基础

证 明(语法) 在语法上，如果存在一个从假设到的证明， 则记为 ⊢ ，称由可推导出的，或可证明的。 证 明(语法) 在语法上，如果存在一个从假设到的证明， 则记为 ⊢ ，称由可推导出的，或可证明的。 如果在没有任何假设下是可推导出的，则记为 ⊢ ，称为可证明的。 称一个假设是不协调的，如果存在一个语句 使得和的否定均可由推导得出。 称一个逻辑系统是一致的，或相容的(consistent)， 如果不存在逻辑系统的公式A，使得⊢A与⊢¬A同时成 立。 2017/9/11 史忠植 逻辑基础

解 释(语义) 语言的解释是在某个论域(domain)中定义非逻辑 符号。语句的语义是在解释下定义出语言L的真假值。 解 释(语义) 语言的解释是在某个论域(domain)中定义非逻辑 符号。语句的语义是在解释下定义出语言L的真假值。 如果I是L的一个解释，且在I中为真，则记为 I ⊨ ，称作I满足 ，或者I 是的一个模型。 类似地，给定一个语句和一个语句 ，如果对 每个解释I ，有I ⊨ 蕴含I ⊨ ，换言之，如果I 是 的一个模型则I也是的一个模型，则记为 ⊨ ，我 们称为的一个逻辑结果。 2017/9/11 史忠植 逻辑基础

可靠性和完备性 可靠性(reliable) 完备性(complete) Gődel完备性定理：一阶逻辑是完备的 一个逻辑是可靠的，如果它的证明保持真假值， 即在任何解释I下，如果I是 的模型，且可由推导 出，则I也是的一个模型。即，一个逻辑是可靠的， 如果对任何语句集合和语句 ，  ⊢蕴涵 ⊨ 。 完备性(complete) 一个逻辑是完备的，如果任何永真语句是可证的。 即，对任何语句集合和语句 ， ⊨蕴涵 ⊢ 。 如果一个逻辑是完备的，则该逻辑的证明系统已强到 可以推出任何永真式。 Gődel完备性定理：一阶逻辑是完备的 2017/9/11 史忠植 逻辑基础

可判定性 可判定的 一个逻辑称为是可判定的(decidable)，如果存在 一个算法对逻辑中的任一公式 A，可确定⊢ A是否成 立。否则，称为是不可判定的(undecidable) 。 如果上述算法虽不一定存在，却有一个过程，可对该系统的定理做出肯定的判断，但对非定理的公式过程未必终止，因而未必能作出判断。这时称逻辑是半可判定的。 一阶逻辑是不可判定的，但它是半可判定的。 2017/9/11 史忠植 逻辑基础

现代逻辑学与计算机科学、计算语言学和人工智能的关系表 逻 辑 自然语 程序 人工 逻辑 指令与直 数据库 复杂性 智能体 未 来 展 望 言处理 控制 智能 编程 陈式语言 理论 理论 理论 时序逻辑 √ √ √ √ √ √ √ √ 广泛应用 模态逻辑 √ √ √ √ √ √ √ √ 非常活跃 算法证明 √ √ √ √ √ √ √ √ 非单调推理 √ √ √ √ √ √ √ 意义重大 概率和模糊 √ √ √ √ √ √ √ 目前主流 直觉主义逻辑 √ √ √ √ √ √ √ √ 主要替代者 高阶逻辑，λ-演算 √ √ √ √ √ √ 更具中心作用 经典逻辑片断 √ √ √ √ √ √ 前景诱人 资源和子结构逻辑 √ √ √ √ 纤维化和组合逻辑 √ √ √ √ √ √ 可自我指称 谬误理论 在适当语境 逻辑动力学 √ √ 动态逻辑观 论辩理论游戏 √ 前景光明 对象层次/元层次 √ √ 总起中心作用 机制:溯因 缺省 相干 √ √ 逻辑的一部分 与神经网络的联系 极重要，刚开始 时间-行动-修正模型 √ √ 一类新模型 加标演绎系统 √ √ √ √ √ 逻辑学的统一框架        8888 2017/9/11 史忠植 逻辑基础

命题逻辑 命题是可以确定其真假的陈述句。 Bolle提出了布尔代数。 语言: ¬，； 公式，原子公式 公理模式: 语言: ¬，； 公式，原子公式 公理模式: ◆(A (B  A)) ◆((A (B  C))  ((A  B) (A  C))) ◆(((¬A))(¬B)  (B  A)) 推理规则:分离规则(modus ponens，MP规则) 2017/9/11 史忠植 逻辑基础

谓词逻辑(一阶逻辑) 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中无自由出现) 推理规则:分离规则 2017/9/11 史忠植 逻辑基础

谓词逻辑与命题逻辑的区别 谓词逻辑给出了原子语句的内部结构，将原子公式看作是事物直接的关系； 它引入了“推广”(泛化)，加强了逻辑的表示能力和推理能力。这样，我们可以说某种性质对某个对象是成立的，或对所有的对象成立，或不对任何对象成立。 2017/9/11 史忠植 逻辑基础

逻辑程序设计 归结原理(消解原理) Horn逻辑 Prolog逻辑程序设计语言 2017/9/11 史忠植 逻辑基础

归结原理 例： C1 = ¬P∨Q∨R C2 = P∨Q 若子句集S能导出空子句⊓(有否证)，则称S 是不可满足的。 则C1与C2归结后的结果为：Q∨R 若子句集S能导出空子句⊓(有否证)，则称S 是不可满足的。 反证法： S ⊢ A iff S  ¬A ⊢ ⊓ 2017/9/11 史忠植 逻辑基础

Horn逻辑 文字：原子公式(正文字)或原子公式的否定(负文字)。 P, Q, ¬R 子句：若干文字的析取。¬P∨Q∨R Horn子句： 子句L1∨L2∨… ∨Ln中如果至多只含一个正文字， 那么该子句称为Horn子句。 Horn子句P∨ ¬Q1∨ ¬Q2∨…∨ ¬Qn通常表示为： P  Q1, Q2, …, Qn 2017/9/11 史忠植 逻辑基础

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)，与事实匹配，产生目 标⊓ 。因而调用成功，输出“是”。 2017/9/11 史忠植 逻辑基础

Prolog Prolog(Programming in logic)语言是以Horn子句逻辑为基础的高级程序设计语言。 1972年，法国马赛大学的Alain. Colmerauer提出了Prolog的雏型。 1975年，Prolog被用于问题求解系统。 此后，它在许多领域获得了应用，如关系数据库、定理证明、智能问题求解、计算机辅助设计、规划生成等领域。 2017/9/11 史忠植 逻辑基础

Prolog的构成 事实：关于对象性质和关系的事实语句； student(john)，married(tom,mary) 规则：关于对象性质和关系的定义规则语句； 它与事实的不同在于，规则所定义的性质、关系依 赖与其它的性质和关系，因此规则呈蕴涵语句形式。 B:— A “如果A则B” bird(x) :— animal(x)，has(x, feather) 问题：关于对象性质或关系的询问。 ?— student(john) ?— married(mary，x) 2017/9/11 史忠植 逻辑基础

Prolog的执行方式 搜索：在程序中自上而下地搜索事实和规则； 匹配：将目标中的项与事实和规则进行匹配； 回溯：当目标中一项失败时，如果目标中有已经成功的的项(应在失败项的左边)，那末就重新调用这些成功项中最右边的一个，谋求新的成功。 2017/9/11 史忠植 逻辑基础

likes(john, X) married(mary, jack) Prolog语言的基本文法 Prolog语言的最基本语言成分是项(term)，一个 项或者是常量，或者是变量，或者是一个结构。 常量：是指对象和对象之间的特定关系的名； 整数，如0，22，1586等； 原子，如John，student，likes，sister-of 变量：表示任意的对象，它与FOL中的变元相同； Prolog中变量可以用大写字母，下划线，以及由它们 开头的字母串。如X, Y, Answer, _value等。 结构：是常量和变量的序列，它由一个函子(函词 或谓词)和该函子的自变量所组成。如： likes(john, X) married(mary, jack) 2017/9/11 史忠植 逻辑基础

例子 Y = mary，John与Mary是朋友 (7)?— likes(X, sports), likes(X, smith) (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) Y = mary，John与Mary是朋友 2017/9/11 史忠植 逻辑基础

Prolog的基本特点 Horn子句逻辑是Prolog的基础。 Prolog既是一种逻辑程序设计语言，又是一个逻辑系统。 2017/9/11 史忠植 逻辑基础

非单调逻辑 单调逻辑 非单调逻辑 区别 2017/9/11 史忠植 逻辑基础

单调逻辑 在现有知识的基础上，通过严密的逻辑论证和推理获得的新知识必须与已有的知识相一致。 A，AB B 推理系统的定理集合随着推理过程的进行而单调地增大。 单调性： (1)  ∈ Th( ) (2) 若 1 ⊆ 2 ，则Th(1) ⊆ Th(2) (3) Th(Th( )) ＝ Th( ) (不动点) 2017/9/11 史忠植 逻辑基础

非单调逻辑 推理系统的定理集合并不随着推理过程的进行而单调地增大，新推出的定理很可能会否定、改变原来的一些定理，使得原来能够解释的某些现象变得不能解释了。 新规则： (4)  ⊬ ¬ P (不动点) 2017/9/11 史忠植 逻辑基础

默认逻辑 1980年，Reiter提出了默认逻辑(Default Logic)。 “一般情况下鸟是会飞的” “鸵鸟不会飞” “企鹅不会飞” 2017/9/11 史忠植 逻辑基础

默认规则 规则的使用： 一个默认规则是如下形式的规则： (x):称为前提条件 i(x):称为默认条件，或检验条件 为简便，通常情况下可以省略检验条件中的M。 规则的使用： 如果规则的前提条件满足，且现有的知识导不 出检验条件的否定¬i(x)，则可以得出结论成立。 2017/9/11 史忠植 逻辑基础

默认理论 一个默认理论由两个部分组成，即默认规则 集D和公式集W，一般用二元组来表示 ＝ <D,W > 一个算子，作用于任意的命题集合S，而其值为满 足下列三个性质的最小命题集合(S)： (1) W  (S) (2) Th((S)) = (S)，其中Th((S)) = {A|(S) ⊢ A} (3) 如果D中有规则 ， 且∈(S)，¬1, …, ¬m ∉ S ，那么∈(S) 2017/9/11 史忠植 逻辑基础

默认理论的扩充 定义：对命题集合E，如果(E) = E，则E称为关于 D的算子的不动点(fixpoint)。此时称E为默认理论 ＝ <D,W >的一个扩充(extension)。 例1：设D ＝ { }，W ＝ ，计算默认 理论＝ <D,W >的扩充。 ＝ <D,W >有唯一的扩充E ＝ Th({¬B, ¬F})。 2017/9/11 史忠植 逻辑基础

默认理论的扩充 例2：设 D ＝ { }， W ＝ {B, CF∨A, A∧C  ¬E}，计算默认理论 E1 ＝ Th(W{A, C}) E2 ＝ Th(W{A, E}) E3 ＝ Th(W{C, E, G}) 2017/9/11 史忠植 逻辑基础

限定推理 1980年，McCarthy提出了一种非单调的推理—— 限定推理(Circumscription)。 基本思想：从某些事实A出发能够推出具有某一性质的P的对象就是满足性质P的全部对象。只有当发现其它对象也具有该性质时，才修改这种看法。 2017/9/11 史忠植 逻辑基础

限定逻辑 极小模型定义的命题限定出发，给出限定的基本定义, 进 而给出一阶限定的基本结果，并将它推广。 限定逻辑CIRC是一种极小化逻辑。下面，从一个基于 极小模型定义的命题限定出发，给出限定的基本定义, 进 而给出一阶限定的基本结果，并将它推广。 定义 2.1 设L0是一个命题语言，p1,p2是在命题语言L0 中 的两个赋值。称p1小于p2 ，记为p1  p2, 当且仅当对任一 命题变元x, 如果p1(x) = l, 则p2(x) = l。 2017/9/11 史忠植 逻辑基础

限定逻辑 的，当且仅当不存在A的其它赋值p'使得 p'  p。 定义 2.2 设A 是一个公式，称A的一个赋值p是极小 的，当且仅当不存在A的其它赋值p'使得 p'  p。 显然, 是一个偏序关系。p1  p2表示p1包含的真命题比p2 少。极小赋值包含的真命题极小。 定义 2.3 极小后承M。 设A, B是两个公式，A M B 当且仅当B在所有A 的极小模型中都为真。 极小模型是非单调的，它以命题的极小化作为优先模型的准则。 2017/9/11 史忠植 逻辑基础

限定逻辑 定义 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。 2017/9/11 史忠植 逻辑基础

限定逻辑 包含命题集的公式，  是一个公式，A P  当且仅 当 在所有A的 p- 极小赋值中都为真。 定义 2.5 命题限定P 或 CIRC(A,P)。设A是一个 包含命题集的公式，  是一个公式，A P  当且仅 当 在所有A的 p- 极小赋值中都为真。 定理 2.1 A p 当且仅当A P  2017/9/11 史忠植 逻辑基础

限定逻辑 定义 2.6 令L是一个一阶语言，T是一个L的公式，它 包含谓词元组集。设M[T]和 M*[T]是公式T的两个模型。 定义M*[T]优先于M[T], 记为M*[T]  M[T]，当且仅当 (1) M和M*有相同的对象域， (2) 除外，公式T中所有的其它关系和函数常数 在M和M*都有相同的解释， (3) 在M*中的外延是在M中的子集。 2017/9/11 史忠植 逻辑基础

限定逻辑 其它模型M'使得M'  M。 定义 2.7 Mm是的最小模型，当且仅当 M  Mm , M = Mm 一个理论T的模型M称为优先的，当且仅当不存在T的 其它模型M'使得M'  M。 定义 2.7 Mm是的最小模型，当且仅当 M  Mm , M = Mm 2017/9/11 史忠植 逻辑基础

限定逻辑 例如 设论域 D={1,2} T=xy(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 2017/9/11 史忠植 逻辑基础

真值维护系统TMS 1979年，Doyle提出了一种非单调推理系统—— 真值维护系统(Truth Maintenance System) 真值维护系统是大型推理系统的的一个子系统， 实现知识库中信念(belief)的修改与维护。其基本问 题有： 必须在不完全的、有限的信息基础上作出假设的决策，使得该假设成为知识库的信念； 当这些决策的结论被以后的事实证明为错误时，如何对其信念进行修正。 2017/9/11 史忠植 逻辑基础

真值维护系统TMS 基本数据结构: 结点：表示信念 理由：表示信念的原因 信念既包括已知的知识，也包括假设的知识。 基本操作： 新结点的形成——将信念赋予该结点； 新理由的加入——把某个信念与该结点联接起来 实现过程： 默认假设的形成； 相关性回溯过程。 2017/9/11 史忠植 逻辑基础

信念知识表示 每一个命题或规则均称为结点，它分为两类： IN-结点：相信为真 OUT-结点：不相信为真，或无理由相信为真， 或当前没有任何有效的理由。 每个结点附有理由表，表示具体结点的有效性： 支持表SL：所在结点的信念的原因，理由； 条件证明CP：出现矛盾的原因。 2017/9/11 史忠植 逻辑基础

(SL(<IN-结点表>)(<OUT-结点表>)) 信念知识表示 （1）支持表SL (SL(<IN-结点表>)(<OUT-结点表>)) IN-结点表中的IN-结点表示知识库中的已知知识; OUT-结点表中的OUT-结点表示这些结点的否定。 例1: (1) 现在是夏天 (SL( )( )) (2) 天气很潮湿 (SL(1)( )) 　　结点(1)不依赖于任何别的结点中的当前信念或 默认信念,因而这种结点称为前提; 　　结点(2)则依赖于当前结点(1)的信念. 　　所以，与一阶逻辑不同的是,TMS可以撤消前提, 并可以对知识库作适当修改. 2017/9/11 史忠植 逻辑基础

信念知识表示 例2: (1) 现在是夏天 (SL( )( )) (2) 天气很潮湿 (SL(1)(3)) (3) 天气很干燥 若结点(1)是IN,结点(3)是OUT,则结点(2)才为IN. 若在某个时刻出现结点(3)的证据,则结点(2)就变为 OUT,因为它不再有一个有效的证实.象结点(2)这样 的结点称为假设,它与非空的OUT结点表的SL证实有 关.OUT结点(3)是结点(2)的证实的一部分.但如果结 点(3)不存在,就不能这样表示了. 　　在TMS中,它仅利用证实来维持一个相容的信念 数据库,而它本身并不产生证实. 2017/9/11 史忠植 逻辑基础

(CP <结论> <IN-假设> <OUT-假设>) 信念知识表示 （2）条件证明CP (CP <结论> <IN-假设> <OUT-假设>) 如果结论结点为IN-结点,以及下列条件成立: (1) IN假设中的每个结点都是IN-结点; (2) OUT-假设中的每个结点都是OUT-结点. 那么条件证明CP是有效的. 　　一般说来,OUT-假设总是空集.TMS要求假设集划 分成两个不相交的子集,分别为不导致矛盾的假设和 导致矛盾的假设. 　　通常只要在IN-假设中的结点为IN,OUT-假设中 的结点为OUT,则结论结点为IN. 2017/9/11 史忠植 逻辑基础

(SL(G)(F1, …, Fi-1 , Fi+1, …, Fn)) 默认假设 　　令{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.但如果接收到一 个有效的理由支持某个其它的侯选Fj,则Fj就为IN, 而导致Fi的假设失败而变为OUT. 2017/9/11 史忠植 逻辑基础

相关回溯 当知识库中出现不一致时,TMS将寻找并删除已 做的一个不正确的默认逻辑,恢复一致性.它包括三 个步骤: (1) 从产生的矛盾结点开始,回溯跟踪该矛盾结点 的理由充足的支持以寻找矛盾的假设集,并从中去掉 至少一个假设信念以消除矛盾. (2) 构造一个结点记录矛盾产生的原因. (3) 从S中选取假设A(即不合理假设),并证实列在 其理由充足的支持条件中的一个OUT-结点. 2017/9/11 史忠植 逻辑基础

相关回溯 例3: (1) 会议日期为星期三 (SL( )(2)) (4) 矛盾 (SL(1,3)( )) (2) 会议日期不应是星期三 (3) 会议时间为14:00 (SL(32,40,61)()) (4) 矛盾 (SL(1,3)( )) (周三14:00没有空会议室) (5) 不相容 (CP4 (1,3)( )) (2) 会议日期不应是星期三 (SL(5)( )) 结点(2)与结点(5)为IN,就引起结点(1)为OUT,因为 结点(1)的证实依赖于结点(2)是OUT.结点(4)现在也 变成OUT.进而矛盾就消除了. 2017/9/11 史忠植 逻辑基础

do(putdown(A)), do(walk(L)), do(pickup(A)) 情景演算 情景演算是一种一阶逻辑语言，主要是用来表示动态 变化的世界的。世界的所有变化过程都是“动作”的结果。 一个可能世界历史可以简单表示为动作的序列，它是通过 称之为情景的一阶项所表示的。 常量S0表示初始情景，即动作还没有发生时的情景。 do(, s)表示在情景s中执行动作之后的后继情景。 do(put(A, B), s)表示当世界状态为s时，将A放到B上的结果这种情景。 do(putdown(A)), do(walk(L)), do(pickup(A)) 是一种表示世界历史由动作序列[pickup(A), walk(L), putdown(A)]所组成的，它们按照从右到左的方式组织。 2017/9/11 史忠植 逻辑基础

D = ∑ ⋃ Dss ⋃ Dap ⋃ Duna ⋃ DSo 情景演算 定义1 定义Lsitcalc语言的动作理论D为如下形式： D = ∑ ⋃ Dss ⋃ Dap ⋃ Duna ⋃ DSo 其中： ∑：基础的、针对情景演算的独立于领域的公理。 Dap：动作前提条件公理； Dss：后续状态公理； Duna：针对原子动作的唯一命名公理； DSo：描述初始情形的公理。 2017/9/11 史忠植 逻辑基础

情景演算 基于情景演算的一些基本理论和方法，我们利用它们来刻画主体的复杂动作和过程，将主体的各个部件加以描述。 <1> 原子动作 Do(a, s, s) Poss(a[s], s) ∧ s = do(a[s], s) def ＝ <2> 检验动作 Do(φ?, s, s) φ[s] ∧ s = s def ＝ <3> 顺序动作 Do([δ1, δ2], s, s) (∃s* ). Do([δ1], s, s* ) ∧ Do([δ2], s*, s) def ＝ 2017/9/11 史忠植 逻辑基础

情景演算 ＝ ＝ ＝ <4> 两个动作的不确定选择 <5> 动作参数的不确定选择 <6> 不确定反复 Do((δ1 | δ2), s, s) (∃s* ). Do(δ1, s, s) ∨ Do(δ2, s, s) def ＝ <5> 动作参数的不确定选择 Do((πx) δ(x), s, s) (∃x). Do(δ(x), s, s) def ＝ <6> 不确定反复 Do(δ*, s, s) (∀P). {(∀s1)P(s1, s1) ∧(∀s1, s2, s3) [P(s1, s2) ∧Do(δ, s2, s3) ⊃ P(s1, s3)]} ⊃ P(s, s) def ＝ 2017/9/11 史忠植 逻辑基础

动作理论与情景演算的研究 ◆ MaCarthy针对动态领域中的问题求解和逻辑程序设计 提出了情景演算。 ◆ Reiter， Fangzhen Lin，Pirria，Lifschitz等人主要将 情景演算进行了一些扩充，对状态约束、动作理论、 动态关系等方面进行了深入的研究，并以数据库、机 器人等动态领域为背景，做了一些逻辑程序设计以及 应用等研究。 ◆ Levesque和Reiter提出了一种新的动态逻辑设计语言 Golog / ConGolog ◆ Baral等人重点对状态的描述、动作的表示与推理以及 动态领域中的知识表示等方面做了一些工作，提出了 一种逻辑程序设计语言 A-Prolog， 2017/9/11 史忠植 逻辑基础

描 述 逻 辑 Description Logics ◆ 什么是描述逻辑？ ◆ 为什么用描述逻辑？ ◆ 描述逻辑的研究进展 ◆ 描述逻辑的体系结构 ◆ 描述逻辑的构造算子 ◆ 描述逻辑的推理问题 ◆ 我们的工作 2017/9/11 史忠植 高级人工智能

什么是描述逻辑(DL)？ 一种基于对象的知识表示的形式化， 也叫概念表示语言或术语逻辑。 建立在概念和关系(Role)之上 －概念解释为对象的集合 －关系解释为对象之间的二元关系 源于语义网络和KL-ONE 是一阶逻辑FOL的一个可判定的子集 具有合适定义的语义(基于逻辑) 2017/9/11 史忠植 高级人工智能

描述逻辑的特点 ◆是以往表示工具的逻辑重构和统一形式化 － 框架系统 (Frame-based systems) － 语义网络 (Semantic Networks) － 面向对象表示 (OO representation) － 语义数据模型 (Semantic data models) － 类型系统 (Type systems) － 特征逻辑 (Feature Logics) ◆ 具有很强的表达能力 ◆ 是可判定的，总能保证推理算法终止 2017/9/11 史忠植 高级人工智能

描述逻辑的应用 ◆ 概念建模 ◆ 查询优化和视图维护 ◆ 自然语言语义 ◆ 智能信息集成 ◆ 信息存取和智能接口 ◆ 工程的形式化规范 ◆ 术语学和本体论 ◆ 规划 ◆ … 2017/9/11 史忠植 高级人工智能

为什么用描述逻辑？ 若直接使用一阶逻辑，而不附加任何约束，则： ◆ 知识的结构将被破坏，这样就不能用来驱动推理 ◆ 对获得可判定性和有效的推理问题来说，其表达 能力太高，（也许是太抽象了） ◆ 对兴趣表达，但仍然可判定的理论，其推理能力太低。 DL的重要特征是： ◆ 很强的表达能力； ◆ 可判定性，它能保证推理算法总能停止，并返回正确的结果。 2017/9/11 史忠植 高级人工智能

为什么用描述逻辑？ 在众多知识表示的形式化方法中，描述逻辑在十多 年来受到人们的特别关注，主要原因在于以下三点 : ◆ 它们有清晰的模型-理论机制; ◆ 它们很适合于通过概念分类学来表示应用领域； ◆ 它们提供了很用的推理服务。 它们可以被认为是从基于框架的表示形式化向着 精确的语义特征方向发展。此外，描述逻辑将分类 学中表示和推理（专业推理）与在分类学中项的事 实或实例的表示和推理（断言推理）区别开来。 2017/9/11 史忠植 高级人工智能

描述逻辑的研究进展 ◆ 描述逻辑的基础研究 研究描述逻辑的构造算子、表示和推理的基本问题， 如可满足性、包含检测、一致性、可判定性等。 一般都在最基本的ALC的基础上在扩展一些构造算子， 如数量约束、逆关系、特征函数、关系的复合等。 TBox和Abox上的推理问题、包含检测算法等。 Schmidt-Schaub 和 Smolka首先建立了基于描述逻辑 ALC的Tableau算法，该算法能在多项式时间内判断描述 逻辑ALC概念的可满足性问题。 2017/9/11 史忠植 高级人工智能

描述逻辑的扩展研究 A.Artale和E.Franconi (1998)提出了一个知识表示系统， 用时间约束的方法将状态、动作和规划的表示统一起来。 为了能让描述逻辑处理模态词，F.Baader将模态操作 引入描述逻辑，证明了该描述逻辑公式的可满足性问题 是可判定的。 Wolter等对具有模态算子的描述逻辑进行了深入系统 的调查分析，并证明在恒定的领域假设下多种认知和时序 描述逻辑是可判定的。 另外如时序扩展(Artale, Wolter)、模糊扩展(Straccia)等。 2017/9/11 史忠植 高级人工智能

描述逻辑的应用研究 描述逻辑在许多领域中被作为知识表示的工具，如 信息系统（Catarci,1993） 数据库（Borgida,1995; Bergamaschi 1992; Sheth, 1993） 软件工程(Devambu, 1991) 网络智能访问（Levy， 1996； Blanco，1994） 规划（Seida, 1992）等 Horrocks对表达能力较强的描述逻辑进行了研究， 并建立了一些逻辑框架和系统，如FaCT，SHIQ等。他 和Dieter Fensel等人将描述逻辑、语义网和DAML结合 起来，提出了DAML+OIL，其中以描述逻辑作为核心的 表示和推理基础。并在XML及其RDF上面进行了扩展， 用描述逻辑来研究语义网络和本体论。 2017/9/11 史忠植 高级人工智能

研究背景 语义Web [Bemers-Lee 1998, 2006] OWL Full OWL DL OWL SHIF(D) Lite 不可判定 SHOIN(D) SHIF(D) 语义Web是当前信息技术研究热点和研究前沿之一。旨在Web上实现数据这个粒度的链接，为这些数据赋予语义信息，使得计算机能够理解和自动处理。 语义Web层次模型：技术及标准。 为了实现这些数据在知识级上的充分共享和在语义上的互操作，本体是实现Web上知识共享和语义互操作的根本途径。 描述逻辑：本体语言OWL的逻辑基础 [Horrocks, 2003]，是语义Web的重要支撑。 描述逻辑：OWL的逻辑基础[Horrocks 2003] 特点：描述能力 + 可判定；有效的判定算法和推理机制。 局限：不能处理动态领域中与动作相关的知识。

描述逻辑的体系结构 一个描述逻辑系统包含四个基本组成部分： 1）表示概念和关系（Role）的构造集 2）Tbox——关于概念术语的断言 3）Abox——关于个体的断言 4）Tbox和Abox上的推理机制。 2017/9/11 史忠植 高级人工智能

DL的基本元素——概念和关系 ◆ 概念 ——解释为一个领域的子集 ◆ 关系(Roles) ——属性(二元谓词，关系) 例子：所有在校学习的人员的集合构成“学生”概念 又如：孩子，已婚的，哺乳动物等概念 {x | Student(x) } ，{x | Married(x) } ◆ 关系(Roles) ——属性(二元谓词，关系) 例子：朋友，爱人， {<x,y> | Friend(x,y) } ，{<x,y> | Loves(x,y) } 2017/9/11 史忠植 高级人工智能

知 识 库 TBox(模式) Abox(数据) 推理系统 接口 Man ≐ Human ⊓ Male Happy-father ≐ Human ⊓ ∃ Has-child.Female⊓ … Abox(数据) John: Happy-father <John,Mary> : Has-child 推理系统 接口 2017/9/11 史忠植 高级人工智能

TBox语言 TBox语言是描述领域结构的公理的集合 定义: 引入概念的名称 A ≐ C, A ⊑ C Father ≐ Man ⊓ ∃ has-child.Human Human ⊑ Animal ⊓ Biped 包含：声明包含关系的公理 C ⊑ D ( C ≐ D  C ⊑ D ，D ⊑ C) ∃ has-degree.Masters ⊑ ∃ has-degree.Bachelors 一个解释I满足： C ≐ D iff CI = DI C ⊑ D iff CI ⊆ DI 一个解释I满足TBox T iff 它满足T中的每个公理(I⊨T) 2017/9/11 史忠植 高级人工智能

ABox语言 ABox语言是描述具体情形的公理的集合 ◆ 概念断言 ——表示一个对象是否属于某个概念 a:C 例如：Tom是个学生，表示为 Tom : Student 或者 Student(Tom) John : Man ⊓ ∃ has-child.Female ◆ 关系断言 ——表示两个对象是否满足一定的关系 <a,b>:R 例如：John有个孩子叫Mary <John, Mary> : has-child 2017/9/11 史忠植 高级人工智能

<a,b>:R iff <aI, bI > ∈ RI 语义解释 一个解释I满足： a : C iff aI ∈ CI <a,b>:R iff <aI, bI > ∈ RI 一个解释I满足ABox A iff 它满足A中的每个公理记为： I ⊨ A 一个解释I满足知识库 =< T, A > iff 它满足T和A 记为： I ⊨  2017/9/11 史忠植 高级人工智能

语法和语义 构造算子 语法 语义 例子 原子概念 A AI ⊆ △I Human 原子关系 R RI ⊆△I  △I has-child 对概念C,D和关系(role)R 合取 C⊓ D CI∩ DI Human ⊓ Male 析取 C⊔ D CI ⋃ DI Doctor ⊔ Lawyer 非 ¬ C △I \C ¬ Male 存在量词 ∃ R.C {x| ∃ y.<x,y>∈ RI∧y ∈ CI} ∃ has-child.Male 全称量词 ∀ R.C {x| ∀ y.<x,y>∈ RI  y ∈ CI} ∀ has-child.Doctor 2017/9/11 史忠植 高级人工智能

DL中的构造算子 一般地，描述逻辑依据提供的构造算子，在简单的 概念和关系上构造出复杂的概念和关系。 通常DL至少包含以下算子： ◆ 合取(⊓ )，吸取(⊔ )，非(¬ ) ◆ 量词约束：存在量词( ∃ )，全称量词(∀) 最基本的DL称之为ALC 例如，ALC中概念Happy-father定义为： Man ⊓ ∃ has-child.Male ⊓ ∃ has-child.Female ⊓ ∀has-child.(Doctor ⊔ Lawyer) 2017/9/11 史忠植 高级人工智能

DL中的其它算子 另外，有两个类似于FOL中的全集(true)和空集(false)的算子 构造算子 语法 语义 例子 数量约束 ≥n R . C {x| | {y|<x,y>∈ RI ,y ∈ CI} | ≥n} ≥3 has-child .Male ≤ n R . C {x| | {y|<x,y>∈ RI ,y ∈ CI} | ≤ n} ≤ 3 has-child .Male 逆 R - {<y,x>|<x,y>∈ RI } has-child- 传递闭包 R* (RI )* has-child* 另外，有两个类似于FOL中的全集(true)和空集(false)的算子 top T △I Male ⊔ ¬ Male Bottom   Man ⊓ ¬ Man 2017/9/11 史忠植 高级人工智能

DL中添加算子 一般地，在描述逻辑中添加不同的算子，则得到不同 表达能力的描述逻辑，其复杂性问题也不尽相同。 例如，在ALC的基础上添加逆( - )算子，则构成ALCI 若再加上数量约束算子(≥n , ≤ n )，则构成ALCIQ。 若在描述逻辑中添加时序算子，则构成为时序描述 逻辑(Temporal Description Logic)，例如，可以添加： Until算子 U： C U D Since算子 S： C S D 还可以加入其它算子，如模态算子□ ，◇ ，○ 等。 2017/9/11 史忠植 高级人工智能

描述逻辑中的推理 1) 一致性（协调性consistency） 2) 可满足性(satisfiability) 3) 包含检测（subsumption） 4) 实例检测 (instance checking) 5) Tableaux算法 6）可判定性 7）计算复杂性 2017/9/11 史忠植 高级人工智能

一致性检测(Consistency) ◆ C关于Tbox T是协调的吗？ 即检测是否有T的模型 I 使得 C ≠  ？ ◆知识库<T, A>是协调的吗？ 即检测是否有<T, A>的模型 (解释) I ？ 2017/9/11 史忠植 高级人工智能

概念可满足性(Satisfiablity) 对一个概念C，如果存在一个解释I使得CI是非空的，则称概念C是可满足的，否则是不可满足的。 检验一个概念的可满足性，实际上就是看是否有解释使得这个概念成立。例如：概念Male ⊓ Female，即需要检测是否有性别既是男的又是女的这样的人。若确实是没有这种两性人，则我们断言，这个概念是不可满足的。 又如概念： student ⊓ worker，它是可满足的。即代表那些在职学生的集合。 定理：概念C是可满足的，当且仅当C不包含于。 2017/9/11 史忠植 高级人工智能

概念包含(Subsumption) ◆在知识库中检测： C ⊑ D？ 即检测 CI ⊆ DI 是否在所有的解释中成立？ ◆在Tbox中检测： 即检测 CI ⊆ DI 是否在Tbox T的所有解释中成立？ 例如： bird ⊑ animal computer ⊑ equipment 2017/9/11 史忠植 高级人工智能

包含与可满足性的关系 C ⊑ D iff C ⊓ ¬D是不可满足的。 C ⊑T D iff C ⊓ ¬D关于T是不可满足的。 C 关于T是一致的 iff C ⊑T A ⊓ ¬A ¬ D D C C ⊓ ¬D ＝  2017/9/11 史忠植 高级人工智能

实例检测(Instance checking) 概念的实例： Student (John)，或者表示为 John:Student 关系的实例： Father(John, Mary) 实例检索：检索属于某个概念的所有实例的集合 2017/9/11 史忠植 高级人工智能

可满足性检测算法——Tableaux算法 1) ⊓规则: S→⊓ { x:C1, x:C2}⋃S，若x:C1⊓ C2在S中，且x:C1和x:C2不在S中同时出现。 2) ⊔规则: S→⊔ {x:D}⋃S，若x:C1⊔C2在S中，x:C1和x:C2都不在S中，且D= C1或者D= C2。 3) ∃规则: S→∃ {xP1y,…,xPky, y:C}⋃S，若x:∃R.C在S中，R= P1⊓…⊓Pk，没有z使得xRz在S中成立，且z:C在S中，y为一个新变量。 4) ∀规则: S→∀ {y:C}⋃S，若x:∃R.C在S中，xRy在S中成立，且y:C不在S中。 2017/9/11 史忠植 高级人工智能

检测概念的可满足性 例子：检测概念的可满足性： (∀has-child.Male) ⊓ (∃has-child.¬Male)， 其检测过程为： ((∀has-child.Male) ⊓ (∃has-child.¬Male))(x) (∀has-child.Male)(x) ⊓规则 (∃has-child.¬Male)(x) ⊓规则 has-child (x, y) ∃规则 ¬Male (y) ∃规则 Male (y) ∀规则  矛盾 所以这个概念是不可满足的。 2017/9/11 史忠植 高级人工智能

可判定性 描述逻辑中的可满足性问题是可判定的。 其它推理问题基本上可以归结为可满足性问题。 2017/9/11 史忠植 高级人工智能

计算复杂性 描述逻辑中的推理问题其计算复杂性一般是多项式时间的。但通常由于构造的不同，其复杂性也有一定的差异。 2017/9/11 史忠植 高级人工智能

带缺省的描述逻辑 定义 一个缺省规则是形如 这样的表达式， ◆带缺省的描述逻辑 定义 一个缺省规则是形如 这样的表达式， 其中C、D、E为概念名，x是一个变元。C(x)称为前提条件，D(x)称为检验条件(缺省)，E(x)称为缺省的结论。 定义1.2 一个知识库是一个三元组<T, A, D>，其中T为Tbox，A为Abox，D为缺省规则集。 2017/9/11 史忠植 高级人工智能

动态描述逻辑 ＋ 描述逻辑最开始只是用来表示静态知识的。 描述逻辑 动态描述逻辑 动态逻辑 为了考虑在时间上的变化，或者在一定动作下的 变化，以及保持其语言的相对简单性，很自然地 我们需要通过相应的模态算子来扩展它，以保留 其命题模态状态。 提出动态描述逻辑，描述动态知识以及行为, 进行推理。 描述逻辑 动态行为 动态描述逻辑 ＋ 动态逻辑 2017/9/11 史忠植 高级人工智能

动态描述逻辑推理机

思 考 描述逻辑与语义Web有何区别与联系？ 描述逻辑与Prolog有何区别与联系？ 描述逻辑可以在哪些方面进行扩展与完善？ 2017/9/11 史忠植 高级人工智能

参考文献 史忠植，《高级人工智能》，科学出版社，2011。 陆钟万，《面向计算机科学的数理逻辑》，科学出版社，2000。 王元元，《计算机科学中的逻辑学》，科学出版社，1989。 2017/9/11 史忠植 逻辑基础

参考文献 http://dl.kr.org/ http://www.cs.man.ac.uk/~horrocks/Slides/index.html http://www.cs.man.ac.uk/~franconi/dl/course/ 史忠植 董明楷 蒋运承 张海俊. 语义Web 的逻辑基础. 中国科学 E 辑 信息科学 2004, 34(10): 1123-1138 Liang Chang, Zhongzhi Shi, Tianlong Gu, Lingzhong Zhao: A Family of Dynamic Description Logics for Representing and Reasoning About Actions. J. Autom. Reasoning 49(1): 1-52 (2012). 2017/9/11 史忠植 高级人工智能

Question! Thank You http://www.intsci.ac.cn/ NN 1 10-00 2017/9/11 史忠植 智能科学 Elene Marchiori