32 非单调逻辑和非单调推理

3-2非单调逻辑和非单调推理1.引言2.限定推理3.缺省逻辑4.自认识逻辑5.非单调推理中的难题6.真值维护系统3-2-0 引言经典逻辑（即单调推理、或基于谓词逻辑的推理）：以一个无矛盾的公理系统为基础，每当加入新的事实，能推出新的结论，而新的结论与原来的事实、结论和公理之间是一致而不矛盾的。

由此，使得命题为真的数目随着推理的进行而严格增加，具有这种特点的推理即单调推理(Monotonic reasoning)。

单调推理的主要特点：真命题数越来越多，不会减少；推理结果不会与已有结论、事实发生冲突或矛盾。

非单调推理：人类思维本质上是非单调的。

于对客观条件掌握的不充分，当有新的事实被认识时，可能导致原来的某些结论要被推翻。

具有这种特点的推理即非单调推理(Non-monotonic reasoning)。

最早由Minsky于1975年提出。

单调推理的主要特点：真命题数不一定越来越多；推理结果可能与已有结论、事实发生冲突或矛盾；推理结论可能推翻原来定理。

研究非单调推理的目的：为了描述和实现人的常识推理。

一个非单调逻辑和非单调推理的实例：“宋江刺配江州，路过揭阳镇时正遇病大虫薛永在使枪棒卖艺，眼见无人赏他银两，薛永惶恐。

宋江仗义赠他白银五两。

宋江此时自以为做了一件扶危济贫的事，必然会得到众人支持。

谁知没遮拦穆弘、小遮拦穆春两弟兄出言不逊，横加阻拦，弄得宋江一行在镇上连饭也吃不成。

晚上好不容易找到投宿处，以为摆脱了是非纠缠，没想到却已经一头扎进穆家，险些束手就擒，他们逃出穆家后在芦苇丛中奔走，前有大江，后有穆弘、穆春两弟兄带人追赶，自以为今番插翅难飞，必落魔掌。

此时，居然在芦花丛中出现一叶扁舟，载着他们脱离险境，并且艄公不理会岸上穆家兄弟的威胁，摇着他们直奔江心，使宋江长舒一口气，以为否极泰来，逃命有望。

正在惊魂稍定之际，忽然，艄公抽出尖刀，喝令他们交出钱财，并问宋江要吃馄饨还是吃板刀面。

真是“月黑杀人夜，风高放火天”。

宋江此时自谓必死，和押送他们的公差一起准备跳江。

危机时刻，上流驶下一条船，他的朋友李俊、童威、童猛赶到，终于使宋江转危为安。

”例如：“穆弘的干涉”推翻了宋江“好有好报”；“穆家兄弟对穆太公说的话”推翻了宋江“已经离开是非之地”；“一页扁舟的出现”推翻了“必落魔掌”；“刀板面和馄饨”推翻了“逃命有望”；“李俊等人赶到”推翻了“此命休也！”非单调推理的主要流派：(1)McCarthy的“限定”理论：“当且仅当没有事实证明事实S在更大范围内成立时，则S只在指定范围内成立”(2)Reiter的“缺省”逻辑：“当且仅当没有事实证明S不成立时，S是成立的”(3)Moore的“自认识”逻辑：“如果我知道S，且我不知道有任何其它事实与S矛盾，则S是成立的”实现非单调推理的两种方法：(1)在经典逻辑框架内增加几个公理（或元公理），由此引导非单调推理取得相应预想的结果。

（McCarthy方法）(2)定义特定的非经典逻辑。

（Reiter和Moore的方法）结论：三种方法均不完善，能解决的问题有限。

3-2-1 限定推理3-2-1-1 引入由McCarthy于1970s末提出。

没有引进新的算子，只是在经典逻辑框架内研究适合于表示非单调推理的推理方法。

因此，只称之为限定推理，而不是限定逻辑。

核心思想（“Occam 剃刀”原理）：一个句子所叙述的命题是不能作任何扩张和延伸的。

Occam 剃刀又称极小模型。

例如：“船能渡河”意味着只有船才能渡河，任何其它能渡河的工具都要被剃刀剃去。

3-2-1-2 论域限定(极小模型、子模型、真子模型、极小蕴涵)注：极小模型的限定定义可以是对论域限定，也可以是对谓词限定。

定义3-2-1 （参见教材P76）极小模型的定义：令~A 是一组命题的集合（称为公理集合），21,M M 是~A 的两个模型，它们的组成如下：1M 2M (1) 基本区域i D 1，n i ,...,2,1=(2) 每个常量都是某个i D 1中的元素(3) 每个变量都在某个i D 1中取值(4) 每个j 目函数都是一个映射： 11111...21+→⨯⨯⨯j i i i i D D D D j(5) 每个j 目谓词都是一个映射： ),(...11121F T D D D j i i i →⨯⨯⨯(1) 基本区域i D 2，n i ,...,2,1= (2) 每个常量都是某个i D 2中的元素 (3) 每个变量都在某个i D 2中取值 (4) 每个j 目函数都是一个映射： 12222...21+→⨯⨯⨯j i i i i D D D D j (5) 每个j 目谓词都是一个映射： ),(...22221F T D D D j i i i →⨯⨯⨯如果存在如下关系：(1) i i D D i 21,⊆∀； (2) 同一常量α相对于1M 和2M ，取某个i D 1中的同一元素为其值(3) 1M 的每个函数1ϕ是2M 的一个函数2ϕ在1ϕ定义域上的一个限制，即对每组变元),...,(1j a a j i i D D D i 111...21⨯⨯⨯∈（即1ϕ的定义域），有),...,(),...,(21211a a a a j ϕϕ=(4) 1M 的每个谓词1p 是的一个谓词2p 在1p 定义域上的一个限定。

即对每组变元),...,(1j a a ji i i D D D 111...21⨯⨯⨯∈（即1p 的定义域），有),...,(),...,(1211j j a a p a a p = 则称1M 为2M 的一个子模型，以21M M ≤表示。

如果至少有一个i ，使得i D 2真包含i D 1，即i i D D 21⊂，则称1M 为2M 的一个真子模型，以21M M <表示。

没有真子模型的模型被称为极小模型。

定义3-2-2 （参见教材P77）极小蕴涵的定义：若命题C 被公理系统~A 的所有极小模型所蕴涵，则称~A 极小蕴涵C ，以C A m =|~表示。

实例：自然数公理系统的极小模型（参见陆汝钤《人工智能（下）》P620-621）(1) )(,x Z x ∃(2) ])()([,y x y Z x Z xy =→∧∀(3) ),(,,y x S y x ∃∀(4) )](~),([,y Z y x S xy →∀(5) ]),(),([,z y z x S y x S xyz =→∧∀(6) ]),(),([,z x y z S y x S xyz =→∧∀(7) )],,()([,x y x A y Z xy →∀(8) )],,(),(),(),,([,v u x A v z S u y S z y x A xyzuv →∧∧∀(9) )],,()([,y y x P y Z xy →∀(10) )],,(),,(),(),,([,v u x P v x z A u y S z y x P xyzuv →∧∧∀如果将)(x Z 解释成0；),(y x S 解释成1+=x y ；),,(z y x A 解释成y x z +=；),,(z y x P 解释成xy z =；则可得一个标准的算术模型，即全体自然数的集合。

注：它是上述公理系统的唯一极小模型。

3-2-1-3 谓词限定由McCarthy 提出的限定推理的一种形式化方法，是领域限定的拓广。

(1) 单谓词限定设A 是一个命题或一阶逻辑子句，其中含有一个谓词),...,(1n x x P ，用)(i x P 表示，用)/(P A φ表示以谓词表达式φ替换P 在A 中的所有出现，)(φA 表示这种替换后的结果。

则定义谓词P 在)(P A 中的限制是如下子模式：)}()(){()}()(){()(i i i i i i x x P x x P x x A φφφ→∀→→∀∧ )123(--其中，)(φA 表示：谓词表达式φ满足所有条件；)}()(){(i i i x P x x →∀φ表示：满足φ的事物都满足P 的事物之集合；)}()(){(i i i x x P x φ→∀表示：P 和φ必须是一致的。

另外，n i ,...,3,2,1=。

则谓词限定表示：只有同时满足命题A 的那些参量组i x 才能满足谓词P 。

例如：积木世界中命题A ：)()()(c block is b block is a block is -∧-∧-表示c b a ,,都是积木。

即谓词block is -被限定在c b a ,,范围内。

则由(3-2-1)得：)}()(){()}()(){()()()(x x block is x x block is x x c b a φφφφφ→-∀→-→∀∧∧∧ 令)()()()(c x b x a x x =∨=∨==φ代入上式，由命题定义，可得出上式的右边如下：))}()()(()(){(c x b x a x x block is x =∨=∨=→-∀。

即如果把谓词block is -限定在命题A 所限定的范围内，则c b a ,,就是所有的积木。

(2) 多个谓词的限定例如：对谓词P 和Q ，有如下限定：)}()(){()}()(){(),(i i i i i i y Q y y x P x x A →∀∧→∀∧ϕφϕφ)}()(){()}()(){(i i i i i i y y Q y x x P x ϕφ→∀∧→∀→3-2-1-4 公式限定 (略)功能强大，但本质上是一个二阶逻辑推理问题，没有有效的方法进行限定。

3-2-1-5 平行限定 (略)由Lifschitz 提出，可以平行地对多个谓词进行限定3-2-1-6 小结一． 限定理论的两个主要问题：(1) McCarthy 引入的用于描述谓词限定和论域限定的极小模型并不总是存在的。

(2) 在谓词限定方面，他没有指出应当对哪些谓词作限定，使得对谓词的不同限定会得到不同的推理结果。

二．限定推理的几种方式（参见陆汝钤《人工智能（下）》P620-630）(1)论域限定(2)谓词限定(3)公式限定平行限定三．可以进行常识推理3-2-2 缺省逻辑(Default Logic)3-2-2-1 缺省逻辑实例计算机程序设计活动中的缺省：如果程序员不显式地指出某种要求，则系统将按约定（缺省）章程行事。

(1)程序设计语言中，不给数值型变量给初值，则其变量的值为0。

(2)一个框架中，如果一个槽设计了缺省值，则程序运行到此时，用户不给值则系统采用默认值。

如人的体温默认为37o。

(3)分程序结构中，内、外层的标识符相同时，内层标识的缺省就是外层的标识符，除非内层另有说明。

(4)……。

宋江例子中的缺省：(1)宋江在滔滔大江边时，没有船或其它渡江手段时，此江在缺省意义下是不能渡的。