非单调逻辑和非单调推理

2006-2007年度第1 学期研究生《人工智能》教案----详案 3-2 非单调逻辑和非单调推理 真值维护系统3-2-0 引言 经典逻辑（即单调推理、或基于谓词逻辑的推理）：以一个无矛盾的公理系 统为基础，每当加入新的事实，能推出新的结论，而新的结论与原来的事实、结 论和公理之间是一致而不矛盾的。由此，使得命题为真的数目随着推理的进行而 严格增加，具有这种特点的推理即单调推理(Monotonic reasoning)。 单调推理的主要特点：真命题数越来越多，不会减少；推理结果不会与已有 结论、事实发生冲突或矛盾。 非单调推理：人类思维本质上是非单调的。于对客观条件掌握的不充分，当 有新的事实被认识时，可能导致原来的某些结论要被推翻。具有这种特点的推理 即非单调推理(Non-monotonic reasoning)。最早由Minsky 于1975 年提出。 单调推理的主要特点：真命题数不一定越来越多；推理结果可能与已有结论、 事实发生冲突或矛盾；推理结论可能推翻原来定理。 研究非单调推理的目的：为了描述和实现人的常识推理。 一个非单调逻辑和非单调推理的实例： “宋江刺配江州，路过揭阳镇时正遇病大虫薛永在使枪棒卖艺，眼见无人赏 他银两，薛永惶恐。宋江仗义赠他白银五两。宋江此时自以为做了一件扶危济 贫的事，必然会得到众人支持。谁知没遮拦穆弘、小遮拦穆春两弟兄出言不逊， 横加阻拦，弄得宋江一行在镇上连饭也吃不成。晚上好不容易找到投宿处，以 为摆脱了是非纠缠，没想到却已经一头扎进穆家，险些束手就擒，他们逃出穆 家后在芦苇丛中奔走，前有大江，后有穆弘、穆春两弟兄带人追赶，自以为今 番插翅难飞，必落魔掌。此时，居然在芦花丛中出现一叶扁舟，载着他们脱离 险境，并且艄公不理会岸上穆家兄弟的威胁，摇着他们直奔江心，使宋江长舒 一口气，以为否极泰来，逃命有望。正在惊魂稍定之际，忽然，艄公抽出尖刀， 喝令他们交出钱财，并问宋江要吃馄饨还是吃板刀面。真是“月黑杀人夜，风 高放火天”。宋江此时自谓必死，和押送他们的公差一起准备跳江。危机时刻， 上流驶下一条船，他的朋友李俊、童威、童猛赶到，终于使宋江转危为安。” 例如： “穆弘的干涉”推翻了宋江“好有好报”； “穆家兄弟对穆太公说的话”推翻了宋江“已经离开是非之地”； “一页扁舟的出现”推翻了“必落魔掌”； “刀板面和馄饨”推翻了“逃命有望”； “李俊等人赶到”推翻了“此命休也！” 非单调推理的主要流派： (1)McCarthy 的“限定”理论：“当且仅当没有事实证明事实S 在更大范围内 2006-2007 年度第1 学期研究生《人工智能》教案----详案 成立时，则S 只在指定范围内成立” (2)Reiter 的“缺省”逻辑：“当且仅当没有事实证明S 不成立时，S 是成立的” (3)Moore 的“自认识”逻辑：“如果我知道 S，且我不知道有任何其它事实 矛盾，则S是成立的” 实现非单调推理的两种方法： 在经典逻辑框架内增加几个公理（或元公理），由此引导非单调推理取得相应预想的结果。（McCarthy 方法） 定义特定的非经典逻辑。（Reiter和Moore 的方法） 结论：三种方法均不完善，能解决的问题有限。 3-2-1 限定推理 3-2-1-1 引入 由McCarthy 于1970s 末提出。没有引进新的算子，只是在经典逻辑框架内研 究适合于表示非单调推理的推理方法。因此，只称之为限定推理，而不是限定逻 核心思想（“Occam剃刀”原理）：一个句子所叙述的命题是不能作任何扩张和延伸的。Occam剃刀又称极小模型。 例如：“船能渡河”意味着只有船才能渡河，任何其它能渡河的工具都要被剃 3-2-1-2论域限定(极小模型、子模型、真子模型、极小蕴涵) 注：极小模型的限定定义可以是对论域限定，也可以是对谓词限定。 定义 3-2-1 （参见教材 P76）极小模型的定义：令 是一组命题的集合（称为公理集合）， 每个j目函数都是一个映射： 每个j目谓词都是一个映射： 每个j目函数都是一个映射： 每个j目谓词都是一个映射： 2006-2007年度第1 学期研究生《人工智能》教案----详案 表示。如果至少有一个i，使得 表示。没有真子模型的模型被称为极小模型。 定义 3-2-2 （参见教材 P77）极小蕴涵的定义：若命题 表示。实例：自然数公理系统的极小模型（参见陆汝钤《人工智能（下）》P620-621） 2006-2007年度第1 学期研究生《人工智能》教案----详案 解释成xy ；则可得一个标准的算术模型，即全体自然数的集合。注：它是上述公理系统的唯一极小模型。 3-2-1-3 谓词限定 由McCarthy 提出的限定推理的一种形式化方法，是领域限定的拓广。 表示以谓词表达式替换P 表示这种替换后的结果。则定义谓词P 表示：谓词表达式满足所有条件； 表示：满足 的事物都满足P 的事物之集合； 必须是一致的。另外， 则谓词限定表示：只有同时满足命题A的那些参量组 都是积木。即谓词block 代入上式，由命题定义，可得出上式的右边如下： 。即如果把谓词block 定在命题A所限定的范围内，则 多个谓词的限定例如：对谓词P 2006-2007年度第1 学期研究生《人工智能》教案----详案 3-2-1-4 公式限定 功能强大，但本质上是一个二阶逻辑推理问题，没有有效的方法进行限定。3-2-1-5 平行限定 由Lifschitz提出，可以平行地对多个谓词进行限定 3-2-1-6 小结 McCarthy引入的用于描述谓词限定和论域限定的极小模型并不总是存在 在谓词限定方面，他没有指出应当对哪些谓词作限定，使得对谓词的不同限定会得到不同的推理结果。 可以进行常识推理3-2-2 缺省逻辑(Default Logic) 3-2-2-1 缺省逻辑实例 计算机程序设计活动中的缺省：如果程序员不显式地指出某种要求，则系统 将按约定（缺省）章程行事。 (1)程序设计语言中，不给数值型变量给初值，则其变量的值为0。 (2)一个框架中，如果一个槽设计了缺省值，则程序运行到此时，用户不给值 则系统采用默认值。如人的体温默认为37 (3)分程序结构中，内、外层的标识符相同时，内层标识的缺省就是外层的标识符，除非内层另有说明。 宋江跨上小船时，如果船家没有异样表现，则缺省意义下，靠此船渡过江去是可行的。 当张横喝问宋江“吃馄饨还是刀板面？”时，如果没有救星，缺省意义下，宋江自任“此命休也！”。 3-2-2-2 运用缺省推理的原因及基本思想 引入原因：人们在推理时所能获得的信息往往是不完备的，往往也不能等到 收集完信息才进行推理。因此，缺省是表达非单调推理的有力手段。 Reiter 引入缺省推理的基本思想： 传统逻辑：从已知事实出发推出新事实。 非单调逻辑推理：知识库不够丰富，难以支持所需推理。因此，需要扩充知 2006-2007 年度第1 学期研究生《人工智能》教案----详案 识库中的知识，即缺省知识（它们并非绝对可靠）。则原来的知识称为不完备理 论。而扩充的知识称为对原来理论的完备化。由不完备理论加缺省知识一起推出 的结论事实，称为对现实世界的一种猜测。 缺省逻辑：为缺省推理提供一组元公理系统后的逻辑系统。 缺省推理前提：在没有证据证明某命题不成立时，则承认其成立。因此又称 为默认推理。 3-2-2-3 对不完备理论的扩充定义 不完备的理论：即原来的知识库。也即当前已知的知识。 对不完备理论的扩充：“想当然”地对知识库进行扩充，即增加缺省知识。 定义3-2-2-1 缺省逻辑的合适公式和缺省命题。 是命题的结论，M是缺省 算子。 赋值程序中为 是数值型变量 过不了河过不了河 河边没有船 BIRD定义3-2-2-2 都是闭的合适公式，则定义3-2-2-1的缺省 命题称为闭缺省命题。 构成，其中，D是一组缺省命题，W 如果D中缺省命题都是闭的，则缺省理论 成为是闭的。注1：一般的缺省命题不是闭的。下面命题是闭缺省命题： 2006-2007 年度第1 学期研究生《人工智能》教案----详案 彭祖是要死的 彭祖是人 凡人都是要死的 的参量可以省去。 注3：缺省命题虽然可以表示许多模糊量词，如“几乎”、“大多数”、“一般” 等，但它不涉及模糊逻辑。 4：对缺省逻辑的进一步研究和讨论（参见陆汝钤《人工智能（下）》P630-641）。 3-2-2-4 缺省规则或命题的分类 非规范缺省命题除前面两类之外的其它形式的缺省命题。 其它分类情形如果缺省命题不含自由变量，则称为封闭的或闭的；如果先决条件为空，则 称为重言式；如果默认条件为空，则退化成演绎规则。 3-2-2-5 小结 缺省逻辑主要用于常识性推理。 缺省逻辑的困难： Reiter建立的完整性维护系统工作过程复杂，实际运用有困难。 3-2-3 自认识逻辑 McCarthy 限定推理和Reiter 缺省逻辑共同特点：给定前提下进行似然推理。 Moore 观点：非单调性是由于推理者所具有的知识的局限性所造成。其思想 可描述为：我相信某些事实 是什么？由此，Moore引入两个算子 表示可接受命题A或命题A 与推理者当前的知 识不矛盾。其关系是： 2006-2007年度第1 学期研究生《人工智能》教案----详案 定义3-2-3-1 自认识逻辑系统AE 的合适公式（只考虑命题逻辑）： 普通命题逻辑的合适公式是AE系统的合适公式； 也是合适公式。定义3-2-3-2 自认识逻辑系统AE 的命题真假值的取值规定： 普通逻辑中的推理规则于此皆适用。定义3-2-3-3 如果自认识逻辑系统AE 中命题的真值指派满足以下规则，则称 其为稳定的自认识逻辑系统AE。 自认识理论：一个具体的AE系统的全部命题之集合。它包括了一个推理 者所有的全部信念之集合。 自认识理论的一个解释：对一个自认识理论中的全部命题进行真值指派。其真值指派符合普通命题逻辑中的所有真值指派规则。且对 形式的命题指派除不违背上述规则外，可以是任意的。 自认识理论的一个（普通命题逻辑意义下的）模型：设I为自认识理论下 的一个解释，则解释中全体被指派为真的命题构成自认识理论的一个模型。 自认识理论的一个自认识解释：设I是自认识理论的一个解释，如果命题A 被指派为真，当且仅当命题 自认识模型：设I是自认识理论的一个解释，则解释中的全体被指派为真 的命题构成自认识理论的一个自认识模型。 定义3-2-3-5 是健康的：当且仅当：如果T的一个自认识解释 是公里集A 在普通命题逻辑意义下的模型，则它也是T 的一个模型。 有自认识模型中皆为真的命题，则A本身包含在T 结论：稳定的自认识理论保证了系统的健康性，是否健康仅取决于自认识理论中不 的命题（Moore称其为客观命题）。 稳定的自认识理论被Moore 比喻为一个理想的推理者，他在已有的公理下是 2006-2007 年度第1 学期研究生《人工智能》教案----详案 无所不知的，且所知必真。 3-2-4 非单调推理中的难题 3-2-4-1 McDermott 的耶鲁射击问题 还活着吗？McDermott 引入了情况演算：将时间轴分成一个个时间区间（见时序推理部分！）， 如果在一个时间区间内所有命题都不发生变化，则连同时间区间在内称其为一个 情况。 3-2-4-2 与非单调推理相关的悖论 彩票悖论：为筹集资金，某单位发行一百万张彩票，并事先宣布：只有一个特等奖：一辆Audi 轿车。统计学家立即知获此奖的机会是百万分之一。 悖论：购买任一张彩票获特等奖的希望几乎是为零，即几乎没有希望。该结 论适合于每张彩票，因此，1000000 张彩票并置起来的结论是：所有彩票都是没 有希望的。但开奖结果，却总有一张是大有希望的。因此，有： 无希望彩票 有希望彩票 反例悖论：McCarthy的限定推理中，说“某种鸟会飞”，则极小模型告诉 我们：只有这中鸟会飞。因此， 只要同时指出一个反例，则上述 结论就会动摇。 用缺省逻辑也有类似的不合 常理的推理结论问题。如，“野猪 是唯一不能飞的鸟”（实例参见陆 汝钤《人工智能（下）》P655-656）。 反常悖论：（实例参见陆汝钤《人工智能（下）》P656-657）。 3-2-5 真值维护系统(Truth maintenance system--TMS) 基本思想：用非单调推理的思想来维护知识库。是非单调推理的核心技术之 一。用来维持推理的一致性。 基本构成：非单调推理的基本构成可由两部分构成，即 基本信念集，A为假设集，是对 的尝试性扩充。由于推理系统中， 图3-2-5-1真值维护系统 推理机 真值维护系统 知识库 论据变化 2006-2007年度第1 学期研究生《人工智能》教案----详案 分，因此，推理产生的不一致性，可以看成是由不同的假设A 引起的。 TMS：最早由Doyle 建立(1979 年)，其作用在于协助问题求解系统维护推理 过程的正确性、一致性和相容性，而不是产生新的推理行为或过程。 TMS 的基本原理：TMS 中每个命题或规则均称为节点，且任一节点有IN（相 信为真）或OUT（不相信为真或无理由相信为真或当前没有为真的可信的理由） 状态。 每一个节点附有一证实表，表中每一项表示一种确定节点是否有效的方法。 有两种方式证实一个节点的有效性依赖于其它节点的有效性： (1)支持表 (SL (IN-节点) (OUT-节点)) 条件证明(CP (结论) (IN-假设) (OUT-假设)) 支持表实例分析(Support List)： 现在是冬天(SL 天气是寒冷的(SL 和OUT均为空，表明它不依赖任何其它节点中的当前信念或 缺少信念（称为前提）；而节点2 中的IN(1)表明，节点2 要求相信节点1 的信念 作为前提。 现在是冬天(SL 天气是寒冷的(SL 天气是温暖的节点1 为真，且节点3 不相信为真时，节点2 状态。条件证明的实例分析(Condition Proving)： 即有前提的论点。只要IN 假设中的节点为IN，OUT 假设中的节点为OUT， 则结论节点往往为IN。 日期(会议)=星期三(SL() 星期三表示 “没有相信会议不在星期三举行的理由，则会议将安排在星期三”。 如经过一些推理又得到如下节点集合： 日期(会议)=星期三 (SL() 时刻(会议)=14:00(SL (57,103,45) 矛盾(SL (1,3) 表示“会议要安排在星期三的下午2:00 举行”，但如果节点 同时满足时，又会出现矛盾。比如，此时没有空的房间供会议使用等原因。 此时，将通过回溯技术继续寻找新的假设条件或证据，以便消除矛盾。如产 生一个不相容节点： 日期(会议)=星期三 (SL() 时刻(会议)=14:00(SL (57,103,45) 矛盾(SL (1,3) 不相容N-1(CP 其中，(4)和(1,3)是不相容的，因此，可选择不相容节点中的任一个，如选择节点1。然后，使节点1 的OUT 表中的节点变成IN，使节点1 成为OUT 节点。 2006-2007 年度第1 学期研究生《人工智能》教案----详案 所以有： 日期(会议)=星期三 (SL() 星期三(SL(5) 时刻(会议)=14:00(SL (57,103,45) 矛盾(SL (1,3) 不相容N-1(CP 为IN，导致节点1为OUT，进而节点4 也为OUT。从而 消除了矛盾，即节点1-5 均不相互矛盾！