人工智能逻辑-智能科学.ppt

人工智能逻辑 2020 4 12 史忠植逻辑基础 1 史忠植中国科学院计算技术研究所 高级人工智能第二章 主要内容 逻辑简介逻辑程序设计非单调逻辑默认逻辑限定逻辑真值维护系统情景演算动态描述逻辑 2020 4 12 史忠植逻辑基础 2 逻辑简介 逻辑的历史逻辑系统命题逻辑谓词逻辑 2020 4 12 史忠植逻辑基础 3 逻辑的历史 Aristotle 逻辑学Leibnitz 数理逻辑GottlobFrege 1848 1925 一阶谓词演算系统 符号论 20世纪30年代 数理逻辑广泛发展 2020 4 12 史忠植逻辑基础 4 逻辑系统 一个逻辑系统是定义语言和它的含义的方法 逻辑系统中的一个逻辑理论是该逻辑的语言的一个语句集合 它包括 逻辑符号集合 在所有该逻辑的逻辑理论中均出现的符号 非逻辑符号集合 不同的逻辑理论中出现的不同的符号 语句规则 定义什么样的符号串是有意义的 证明 什么样的符号串是一个合理的证明 语义规则 定义符号串的语义 2020 4 12 史忠植逻辑基础 5 2020 4 12 史忠植逻辑基础 6 逻辑与程序语言的对比 2020 4 12 史忠植逻辑基础 7 一个证明是一个语法结构 它由符号串根据一定的规则组成 它包括假设和结论 在公理化逻辑中 逻辑给出一个逻辑公理和推理规则的集合 推理规则是可以从一个语句的集合得到另一语句的集合 公理化逻辑中的证明就是一个语句序列 使得其中的每个语句要么是逻辑公理 要么是一个假设 要么是由前面的语句通过推理规则得到的 证明 2020 4 12 史忠植逻辑基础 8 在语法上 如果存在一个从假设 到 的证明 则记为 称 由 可推导出的 或可证明的 如果在没有任何假设下 是可推导出的 则记为 称 为可证明的 称一个假设 是不协调的 如果存在一个语句 使得 和 的否定均可由 推导得出 称一个逻辑系统是一致的 或相容的 consistent 如果不存在逻辑系统的公式A 使得 A与 A同时成立 证明 语法 2020 4 12 史忠植逻辑基础 9 语言的解释是在某个论域 domain 中定义非逻辑符号 语句的语义是在解释下定义出语言L的真假值 如果I是L的一个解释 且 在I中为真 则记为I 称作I满足 或者I是 的一个模型 类似地 给定一个语句 和一个语句 如果对每个解释I 有I 蕴含I 换言之 如果I是 的一个模型则I也是 的一个模型 则记为 我们称 为 的一个逻辑结果 解释 语义 2020 4 12 史忠植逻辑基础 10 可靠性 reliable 一个逻辑是可靠的 如果它的证明保持真假值 即在任何解释I下 如果I是 的模型 且 可由 推导出 则I也是 的一个模型 即 一个逻辑是可靠的 如果对任何语句集合 和语句 蕴涵 可靠性和完备性 完备性 complete 一个逻辑是完备的 如果任何永真语句是可证的 即 对任何语句集合 和语句 蕴涵 如果一个逻辑是完备的 则该逻辑的证明系统已强到可以推出任何永真式 G del完备性定理 一阶逻辑是完备的 2020 4 12 史忠植逻辑基础 11 可判定的一个逻辑称为是可判定的 decidable 如果存在一个算法对逻辑中的任一公式A 可确定 A是否成立 否则 称为是不可判定的 undecidable 如果上述算法虽不一定存在 却有一个过程 可对该系统的定理做出肯定的判断 但对非定理的公式过程未必终止 因而未必能作出判断 这时称逻辑是半可判定的 可判定性 一阶逻辑是不可判定的 但它是半可判定的 现代逻辑学与计算机科学 计算语言学和人工智能的关系表逻辑自然语程序人工逻辑指令与直数据库复杂性智能体未来展望言处理控制智能编程陈式语言理论理论理论时序逻辑 广泛应用模态逻辑 非常活跃算法证明 非单调推理 意义重大概率和模糊 目前主流直觉主义逻辑 主要替代者高阶逻辑 演算 更具中心作用经典逻辑片断 前景诱人资源和子结构逻辑 纤维化和组合逻辑 可自我指称谬误理论在适当语境逻辑动力学 动态逻辑观论辩理论游戏 前景光明对象层次 元层次 总起中心作用机制 溯因缺省相干 逻辑的一部分与神经网络的联系极重要 刚开始时间 行动 修正模型 一类新模型加标演绎系统 逻辑学的统一框架 2020 4 12 史忠植逻辑基础 12 命题逻辑 命题是可以确定其真假的陈述句 Bolle提出了布尔代数 语言 公式 原子公式公理模式 A B A A B C A B A C A B B A 推理规则 分离规则 modusponens MP规则 2020 4 12 史忠植逻辑基础 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 4 12 史忠植逻辑基础 14 谓词逻辑与命题逻辑的区别 2020 4 12 史忠植逻辑基础 15 谓词逻辑给出了原子语句的内部结构 将原子公式看作是事物直接的关系 它引入了 推广 泛化 加强了逻辑的表示能力和推理能力 这样 我们可以说某种性质对某个对象是成立的 或对所有的对象成立 或不对任何对象成立 逻辑程序设计 归结原理 消解原理 Horn逻辑Prolog逻辑程序设计语言 2020 4 12 史忠植逻辑基础 16 归结原理 例 C1 P Q RC2 P Q则C1与C2归结后的结果为 Q R 若子句集S能导出空子句 有否证 则称S是不可满足的 反证法 S AiffS A 2020 4 12 史忠植逻辑基础 17 Horn逻辑 文字 原子公式 正文字 或原子公式的否定 负文字 P Q R子句 若干文字的析取 P Q RHorn子句 子句L1 L2 Ln中如果至多只含一个正文字 那么该子句称为Horn子句 Horn子句P Q1 Q2 Qn通常表示为 P Q1 Q2 Qn 2020 4 12 史忠植逻辑基础 18 Horn子句的类型 2020 4 12 史忠植逻辑基础 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 调用过程AT Zhang x 从而产生新目标 AT Zhang train 与事实匹配 产生目标 因而调用成功 输出 是 Prolog Prolog Programminginlogic 语言是以Horn子句逻辑为基础的高级程序设计语言 1972年 法国马赛大学的Alain Colmerauer提出了Prolog的雏型 1975年 Prolog被用于问题求解系统 此后 它在许多领域获得了应用 如关系数据库 定理证明 智能问题求解 计算机辅助设计 规划生成等领域 2020 4 12 史忠植逻辑基础 20 Prolog的构成 事实 关于对象性质和关系的事实语句 student john married tom mary 规则 关于对象性质和关系的定义规则语句 它与事实的不同在于 规则所定义的性质 关系依赖与其它的性质和关系 因此规则呈蕴涵语句形式 B A 如果A则B bird x animal x has x feather 问题 关于对象性质或关系的询问 student john married mary x 2020 4 12 史忠植逻辑基础 21 2020 4 12 史忠植逻辑基础 22 Prolog的执行方式 搜索 在程序中自上而下地搜索事实和规则 匹配 将目标中的项与事实和规则进行匹配 回溯 当目标中一项失败时 如果目标中有已经成功的的项 应在失败项的左边 那末就重新调用这些成功项中最右边的一个 谋求新的成功 2020 4 12 史忠植逻辑基础 23 Prolog语言的基本文法 Prolog语言的最基本语言成分是项 term 一个项或者是常量 或者是变量 或者是一个结构 常量 是指对象和对象之间的特定关系的名 整数 如0 22 1586等 原子 如John student likes sister of变量 表示任意的对象 它与FOL中的变元相同 Prolog中变量可以用大写字母 下划线 以及由它们开头的字母串 如X Y Answer value等 结构 是常量和变量的序列 它由一个函子 函词或谓词 和该函子的自变量所组成 如 likes john X married mary jack 例子 2020 4 12 史忠植逻辑基础 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 X 7 likes X sports likes X smith 8 likes mary smith mary X 2020 4 12 史忠植逻辑基础 25 Prolog的基本特点 Horn子句逻辑是Prolog的基础 Prolog既是一种逻辑程序设计语言 又是一个逻辑系统 Prolog是一种描述性语言 它是一种面向问题的语言 你只需要告诉它要做什么 即给出问题的形式描述 而不需要知道应该如何做 Prolog完全依靠匹配 回溯来进行搜索 Prolog的求解过程是一个寻求否证的消解过程 Prolog也使用元语言种的谓词 有很强的描述能力 Prolog采用统一的数据结构 项 它包含控制成分 且有专门进行数值计算和符号处理的模块 非单调逻辑 单调逻辑非单调逻辑区别 2020 4 12 史忠植逻辑基础 26 单调逻辑 在现有知识的基础上 通过严密的逻辑论证和推理获得的新知识必须与已有的知识相一致 A A B B推理系统的定理集合随着推理过程的进行而单调地增大 单调性 1 Th 2 若 1 2 则Th 1 Th 2 3 Th Th Th 不动点 2020 4 12 史忠植逻辑基础 27 2020 4 12 史忠植逻辑基础 28 非单调逻辑 推理系统的定理集合并不随着推理过程的进行而单调地增大 新推出的定理很可能会否定 改变原来的一些定理 使得原来能够解释的某些现象变得不能解释了 新规则 4 P 不动点 默认逻辑 1980年 Reiter提出了默认逻辑 DefaultLogic 一般情况下鸟是会飞的 鸵鸟不会飞 企鹅不会飞 2020 4 12 史忠植逻辑基础 29 2020 4 12 史忠植逻辑基础 30 默认规则 一个默认规则是如下形式的规则 x 称为前提条件 i x 称为默认条件 或检验条件 x 称为结论为简便 通常情况下可以省略检验条件中的M 规则的使用 如果规则的前提条件满足 且现有的知识导不出检验条件的否定 i x 则可以得出结论成立 2020 4 12 史忠植逻辑基础 31 默认理论 一个默认理论 由两个部分组成 即默认规则集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 2020 4 12 史忠植逻辑基础 32 默认理论的扩充 定义 对命题集合E 如果 E E 则E称为关于D的算子 的不动点 fixpoint 此时称E为默认理论 的一个扩充 extension 例1 设D W 计算默认理论 的扩充 有唯一的扩充E Th B F 默认理论的扩充 2020 4 12 史忠植逻辑基础 33 例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 2020 4 12 史忠植逻辑基础 34 限定推理 1980年 McCarthy提出了一种非单调的推理 限定推理 Circumscription 基本思想 从某些事实A出发能够推出具有某一性质的P的对象就是满足性质P的全部对象 只有当发现其它对象也具有该性质时 才修改这种看法 限定逻辑 2020 4 12 史忠植逻辑基础 35 限定逻辑CIRC是一种极小化逻辑 下面 从一个基于极小模型定义的命题限定出发 给出限定的基本定义 进而给出一阶限定的基本结果 并将它推广 定义2 1设L0是一个命题语言 p1 p2是在命题语言L0中的两个赋值 称p1小于p2 记为p1 p2 当且仅当对任一命题变元x 如果p1 x l 则p2 x l 限定逻辑 2020 4 12 史忠植逻辑基础 36 定义2 2设A是一个公式 称A的一个赋值p是极小的 当且仅当不存在A的其它赋值p 使得p p 显然 是一个偏序关系 p1 p2表示p1包含的真命题比p2少 极小赋值包含的真命题极小 定义2 3极小后承 M 设A B是两个公式 A MB当且仅当B在所有A的极小模型中都为真 极小模型是非单调的 它以命题的极小化作为优先模型的准则 限定逻辑 2020 4 12 史忠植逻辑基础 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 限定逻辑 2020 4 12 史忠植逻辑基础 38 定义2 5命题限定 P或CIRC A P 设A是一个包含命题集的公式 是一个公式 A P 当且仅当 在所有A的 p 极小赋值中都为真 定理2 1A p 当且仅当A P 限定逻辑 2020 4 12 史忠植逻辑基础 39 定义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中的子集 限定逻辑 2020 4 12 史忠植逻辑基础 40 一个理论T的模型M称为优先的 当且仅当不存在T的其它模型M 使得M M 定义2 7Mm是 的最小模型 当且仅当M Mm M Mm 限定逻辑 2020 4 12 史忠植逻辑基础 41 例如设论域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 TTFTFTM P 1 P 2 Q 1 1 Q 1 2 Q 2 1 Q 2 2 FTFTFT 2020 4 12 史忠植逻辑基础 42 真值维护系统TMS 1979年 Doyle提出了一种非单调推理系统 真值维护系统 TruthMaintenanceSystem 真值维护系统是大型推理系统的的一个子系统 实现知识库中信念 belief 的修改与维护 其基本问题有 必须在不完全的 有限的信息基础上作出假设的决策 使得该假设成为知识库的信念 当这些决策的结论被以后的事实证明为错误时 如何对其信念进行修正 2020 4 12 史忠植逻辑基础 43 基本数据结构 结点 表示信念理由 表示信念的原因信念既包括已知的知识 也包括假设的知识 基本操作 新结点的形成 将信念赋予该结点 新理由的加入 把某个信念与该结点联接起来 实现过程 默认假设的形成 相关性回溯过程 真值维护系统TMS 2020 4 12 史忠植逻辑基础 44 信念知识表示 每一个命题或规则均称为结点 它分为两类 IN 结点 相信为真OUT 结点 不相信为真 或无理由相信为真 或当前没有任何有效的理由 每个结点附有理由表 表示具体结点的有效性 支持表SL 所在结点的信念的原因 理由 条件证明CP 出现矛盾的原因 2020 4 12 史忠植逻辑基础 45 SL IN 结点表中的IN 结点表示知识库中的已知知识 OUT 结点表中的OUT 结点表示这些结点的否定 例1 1 现在是夏天 SL 2 天气很潮湿 SL 1 结点 1 不依赖于任何别的结点中的当前信念或默认信念 因而这种结点称为前提 结点 2 则依赖于当前结点 1 的信念 所以 与一阶逻辑不同的是 TMS可以撤消前提 并可以对知识库作适当修改 1 支持表SL 信念知识表示 2020 4 12 史忠植逻辑基础 46 例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中 它仅利用证实来维持一个相容的信念数据库 而它本身并不产生证实 信念知识表示 2020 4 12 史忠植逻辑基础 47 CP 如果结论结点为IN 结点 以及下列条件成立 1 IN假设中的每个结点都是IN 结点 2 OUT 假设中的每个结点都是OUT 结点 那么条件证明CP是有效的 一般说来 OUT 假设总是空集 TMS要求假设集划分成两个不相交的子集 分别为不导致矛盾的假设和导致矛盾的假设 通常只要在IN 假设中的结点为IN OUT 假设中的结点为OUT 则结论结点为IN 2 条件证明CP 信念知识表示 2020 4 12 史忠植逻辑基础 48 默认假设 令 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 2020 4 12 史忠植逻辑基础 49 相关回溯 当知识库中出现不一致时 TMS将寻找并删除已做的一个不正确的默认逻辑 恢复一致性 它包括三个步骤 1 从产生的矛盾结点开始 回溯跟踪该矛盾结点的理由充足的支持以寻找矛盾的假设集 并从中去掉至少一个假设信念以消除矛盾 2 构造一个结点记录矛盾产生的原因 3 从S中选取假设A 即不合理假设 并证实列在其理由充足的支持条件中的一个OUT 结点 2020 4 12 史忠植逻辑基础 50 4 矛盾 SL 1 3 周三14 00没有空会议室 例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 进而矛盾就消除了 相关回溯 2020 4 12 史忠植逻辑基础 51 情景演算 情景演算是一种一阶逻辑语言 主要是用来表示动态变化的世界的 世界的所有变化过程都是 动作 的结果 一个可能世界历史可以简单表示为动作的序列 它是通过称之为情景的一阶项所表示的 常量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 所组成的 它们按照从右到左的方式组织 2020 4 12 史忠植逻辑基础 52 定义1定义Lsitcalc语言的动作理论D为如下形式 D Dss Dap Duna DSo其中 基础的 针对情景演算的独立于领域的公理 Dap 动作前提条件公理 Dss 后续状态公理 Duna 针对原子动作的唯一命名公理 DSo 描述初始情形的公理 情景演算 2020 4 12 史忠植逻辑基础 53 基于情景演算的一些基本理论和方法 我们利用它们来刻画主体的复杂动作和过程 将主体的各个部件加以描述 原子动作Do a s s Poss a s s s do a s s 检验动作Do s s s s s 顺序动作Do 1 2 s s s Do 1 s s Do 2 s s def def def 情景演算 2020 4 12 史忠植逻辑基础 54 两个动作的不确定选择Do 1 2 s s s Do 1 s s Do 2 s s def 动作参数的不确定选择Do x x s s x Do x s s def 不确定反复Do s s P s1 P s1 s1 s1 s2 s3 P s1 s2 Do s2 s3 P s1 s3 P s s def 情景演算 2020 4 12 史忠植逻辑基础 55 动作理论与情景演算的研究 MaCarthy针对动态领域中的问题求解和逻辑程序设计提出了情景演算 Reiter FangzhenLin Pirria Lifschitz等人主要将情景演算进行了一些扩充 对状态约束 动作理论 动态关系等方面进行了深入的研究 并以数据库 机器人等动态领域为背景 做了一些逻辑程序设计以及应用等研究 Levesque和Reiter提出了一种新的动态逻辑设计语言Golog ConGolog Baral等人重点对状态的描述 动作的表示与推理以及动态领域中的知识表示等方面做了一些工作 提出了一种逻辑程序设计语言A Prolog 2020 4 12 史忠植高级人工智能 56 描述逻辑DescriptionLogics 什么是描述逻辑 为什么用描述逻辑 描述逻辑的研究进展 描述逻辑的体系结构 描述逻辑的构造算子 描述逻辑的推理问题 我们的工作 2020 4 12 史忠植高级人工智能 57 什么是描述逻辑 DL 一种基于对象的知识表示的形式化 也叫概念表示语言或术语逻辑 建立在概念和关系 Role 之上 概念解释为对象的集合 关系解释为对象之间的二元关系源于语义网络和KL ONE是一阶逻辑FOL的一个可判定的子集具有合适定义的语义 基于逻辑 2020 4 12 史忠植高级人工智能 58 描述逻辑的特点 是以往表示工具的逻辑重构和统一形式化 框架系统 Frame basedsystems 语义网络 SemanticNetworks 面向对象表示 OOrepresentation 语义数据模型 Semanticdatamodels 类型系统 Typesystems 特征逻辑 FeatureLogics 具有很强的表达能力 是可判定的 总能保证推理算法终止 2020 4 12 史忠植高级人工智能 59 描述逻辑的应用 概念建模 查询优化和视图维护 自然语言语义 智能信息集成 信息存取和智能接口 工程的形式化规范 术语学和本体论 规划 2020 4 12 史忠植高级人工智能 60 为什么用描述逻辑 若直接使用一阶逻辑 而不附加任何约束 则 知识的结构将被破坏 这样就不能用来驱动推理 对获得可判定性和有效的推理问题来说 其表达能力太高 也许是太抽象了 对兴趣表达 但仍然可判定的理论 其推理能力太低 DL的重要特征是 很强的表达能力 可判定性 它能保证推理算法总能停止 并返回正确的结果 2020 4 12 史忠植高级人工智能 61 在众多知识表示的形式化方法中 描述逻辑在十多年来受到人们的特别关注 主要原因在于以下三点 它们有清晰的模型 理论机制 它们很适合于通过概念分类学来表示应用领域 它们提供了很用的推理服务 它们可以被认为是从基于框架的表示形式化向着精确的语义特征方向发展 此外 描述逻辑将分类学中表示和推理 专业推理 与在分类学中项的事实或实例的表示和推理 断言推理 区别开来 为什么用描述逻辑 描述逻辑的研究进展 2020 4 12 史忠植高级人工智能 62 描述逻辑的基础研究研究描述逻辑的构造算子 表示和推理的基本问题 如可满足性 包含检测 一致性 可判定性等 一般都在最基本的ALC的基础上在扩展一些构造算子 如数量约束 逆关系 特征函数 关系的复合等 TBox和Abox上的推理问题 包含检测算法等 Schmidt Schaub和Smolka首先建立了基于描述逻辑ALC的Tableau算法 该算法能在多项式时间内判断描述逻辑ALC概念的可满足性问题 描述逻辑的扩展研究 2020 4 12 史忠植高级人工智能 63 A Artale和E Franconi 1998 提出了一个知识表示系统 用时间约束的方法将状态 动作和规划的表示统一起来 为了能让描述逻辑处理模态词 F Baader将模态操作引入描述逻辑 证明了该描述逻辑公式的可满足性问题是可判定的 Wolter等对具有模态算子的描述逻辑进行了深入系统的调查分析 并证明在恒定的领域假设下多种认知和时序描述逻辑是可判定的 另外如时序扩展 Artale Wolter 模糊扩展 Straccia 等 2020 4 12 史忠植高级人工智能 64 描述逻辑在许多领域中被作为知识表示的工具 如信息系统 Catarci 1993 数据库 Borgida 1995 Bergamaschi1992 Sheth 1993 软件工程 Devambu 1991 网络智能访问 Levy 1996 Blanco 1994 规划 Seida 1992 等Horrocks对表达能力较强的描述逻辑进行了研究 并建立了一些逻辑框架和系统 如FaCT SHIQ等 他和DieterFensel等人将描述逻辑 语义网和DAML结合起来 提出了DAML OIL 其中以描述逻辑作为核心的表示和推理基础 并在XML及其RDF上面进行了扩展 用描述逻辑来研究语义网络和本体论 描述逻辑的应用研究 研究背景 语义Web Bemers Lee1998 2006 描述逻辑 OWL的逻辑基础 Horrocks2003 特点 描述能力 可判定 有效的判定算法和推理机制 局限 不能处理动态领域中与动作相关的知识 SHIF D SHOIN D 不可判定 2020 4 12 史忠植高级人工智能 66 描述逻辑的体系结构 一个描述逻辑系统包含四个基本组成部分 1 表示概念和关系 Role 的构造集2 Tbox 关于概念术语的断言3 Abox 关于个体的断言4 Tbox和Abox上的推理机制 2020 4 12 史忠植高级人工智能 67 概念 解释为一个领域的子集例子 所有在校学习的人员的集合构成 学生 概念又如 孩子 已婚的 哺乳动物等概念 x Student x x Married x 关系 Roles 属性 二元谓词 关系 例子 朋友 爱人 Friend x y Loves x y DL的基本元素 概念和关系 2020 4 12 史忠植高级人工智能 68 知识库 TBox 模式 Man Human MaleHappy father Human Has child Female Abox 数据 John Happy father Has child 推理系统 接口 TBox语言 2020 4 12 史忠植高级人工智能 69 TBox语言是描述领域结构的公理的集合 定义 引入概念的名称A C A CFather Man has child HumanHuman Animal Biped包含 声明包含关系的公理C D C D C D D C has degree Masters has degree Bachelors一个解释I满足 C DiffCI DIC DiffCI DI一个解释I满足TBoxTiff它满足T中的每个公理 I T 2020 4 12 史忠植高级人工智能 70 概念断言 表示一个对象是否属于某个概念a C例如 Tom是个学生 表示为Tom Student或者Student Tom John Man has child Female 关系断言 表示两个对象是否满足一定的关系 R例如 John有个孩子叫Mary has child ABox语言是描述具体情形的公理的集合 ABox语言 语义解释 2020 4 12 史忠植高级人工智能 71 一个解释I满足 a CiffaI CI Riff RI一个解释I满足ABoxAiff它满足A中的每个公理记为 I A一个解释I满足知识库 iff它满足T和A记为 I 2020 4 12 史忠植高级人工智能 72 语法和语义 2020 4 12 史忠植高级人工智能 73 一般地 描述逻辑依据提供的构造算子 在简单的概念和关系上构造出复杂的概念和关系 通常DL至少包含以下算子 合取 吸取 非 量词约束 存在量词 全称量词 最基本的DL称之为ALC例如 ALC中概念Happy father定义为 Man has child Male has child Female has child Doctor Lawyer DL中的构造算子 2020 4 12 史忠植高级人工智能 74 DL中的其它算子 另外 有两个类似于FOL中的全集 true 和空集 false 的算子 2020 4 12 史忠植高级人工智能 75 DL中添加算子 一般地 在描述逻辑中添加不同的算子 则得到不同表达能力的描述逻辑 其复杂性问题也不尽相同 例如 在ALC的基础上添加逆 算子 则构成ALCI若再加上数量约束算子 n n 则构成ALCIQ 若在描述逻辑中添加时序算子 则构成为时序描述逻辑 TemporalDescriptionLogic 例如 可以添加 Until算子U CUDSince算子S CSD还可以加入其它算子 如模态算子 等 2020 4 12 史忠植高级人工智能 76 描述逻辑中的推理 1 一致性 协调性consistency 2 可满足性 satisfiability 3 包含检测 subsumption 4 实例检测 instancechecking 5 Tableaux算法6 可判定性7 计算复杂性 2020 4 12 史忠植高级人工智能 77 一致性检测 Consistency 知识库是协调的吗 即检测是否有的模型 解释 I C关于TboxT是协调的吗 即检测是否有T的模型I使得C 2020 4 12 史忠植高级人工智能 78 概念可满足性 Satisfiablity 对一个概念C 如果存在一个解释I使得CI是非空的 则称概念C是可满足的 否则是不可满足的 检验一个概念的可满足性 实际上就是看是否有解释使得这个概念成立 例如 概念Male Female 即需要检测是否有性别既是男的又是女的这样的人 若确实是没有这种两性人 则我们断言 这个概念是不可满足的 又如概念 student worker 它是可满足的 即代表那些在职学生的集合 定理 概念C是可满足的 当且仅当C不包含于 2020 4 12 史忠植高级人工智能 79 在知识库中检测 C D 即检测CI DI是否在所有的解释中成立 概念包含 Subsumption 例如 bird animalcomputer equipment 在Tbox中检测 C D 即检测CI DI是否在TboxT的所有解释中成立 2020 4 12 史忠植高级人工智能 80 C DiffC D是不可满足的 C TDiffC D关于T是不可满足的 C关于T是一致的iffC TA A 包含与可满足性的关系 C D 2020 4 12 史忠植高级人工智能 81 实例检测 Instancechecking 概念的实例 Student John 或者表示为John Student关系的实例 Father John Mary 实例检索 检索属于某个概念的所有实例的集合 2020 4 1