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

1、3-2非单调逻辑和非单调推理1.引言2.限定推理3.缺省逻辑4.自认识逻辑5.非单调推理中的难题6.真值维护系统3-2-0引言经典逻辑(即单调推理、或基于谓词逻辑的推理)：以一个无矛盾的公理系统为基础，每当加入新的事实，能推出新的结论，而新的结论与原来的事实、结论和公理之间是一致而不矛盾的。由此，使得命题为真的数目随着推理的进行而严格增加，具有这种特点的推理即单调推理(Monotonicreasoning)。单调推理的主要特点：真命题数越来越多，不会减少；推理结果不会与已有结论、事实发生冲突或矛盾。非单调推理：人类思维本质上是非单调的。于对客观条件掌握的不充分，当有新的事实被认识时，可能导致原

2、来的某些结论要被推翻。具有这种特点的推理即非单调推理(Non-monotonicreasoning)o最早由Minsky于1975年提出。单调推理的主要特点：真命题数不一定越来越多；推理结果可能与已有结论、事实发生冲突或矛盾；推理结论可能推翻原来定理。研究非单调推理的目的：为了描述和实现人的常识推理。一个非单调逻辑和非单调推理的实例：“宋江刺配江州，路过揭阳镇时正遇病大虫薛永在使枪棒卖艺，眼见无人赏他银两，薛永惶恐。宋江仗义赠他白银五两。宋江此时自以为做了一件扶危济贫的事，必然会得到众人支持。谁知没遮拦穆弘、小遮拦穆春两弟兄出言不逊，横加阻拦，弄得宋江一行在镇上连饭也吃不成。晚上好不容易找到投

3、宿处，以为摆脱了是非纠缠，没想到却已经一头扎进穆家，险些束手就擒，他们逃出穆家后在芦苇丛中奔走，前有大江，后有穆弘、穆春两弟兄带人追赶，自以为今番插翅难飞，必落魔掌。此时，居然在芦花丛中出现一叶扁舟，载着他们脱离险境，并且艄公不理会岸上穆家兄弟的威胁，摇着他们直奔江心，使宋江长舒一口气，以为否极泰来，逃命有望。正在惊魂稍定之际，忽然，艄公抽出尖刀，喝令他们交出钱财，并问宋江要吃馄饨还是吃板刀面。真是“月黑杀人夜，风高放火天”。宋江此时自谓必死，和押送他们的公差一起准备跳江。危机时刻，上流驶下一条船，他的朋友李俊、童威、童猛赶到，终于使宋江转危为安。”例如：“穆弘的干涉”推翻了宋江“好有好报”；

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

5、的非经典逻辑。(Reiter和Moore的方法)结论：三种方法均不完善，能解决的问题有限。3-2-1限定推理3-2-1-1引入由McCarthy于1970s末提出。没有引进新的算子，只是在经典逻辑框架内研究适合于表示非单调推理的推理方法。因此，只称之为限定推理，而不是限定逻辑。核心思想(“Occam剃刀”原理)：一个句子所叙述的命题是不能作任何扩张和延伸的。Occam剃刀又称极小模型。例如：“船能渡河”意味着只有船才能渡河，任何其它能渡河的工具都要被剃刀剃去。3-2-1-2论域限定(极小模型、子模型、真子模型、极小蕴涵)注：极小模型的限定定义可以是对论域限定，也可以是对谓词限定。定义3-2-1

6、(参见教材)极小模型的定义：令A是一组命题的集合(称为公理集合)，m,M是A的两个模型，它们的组成如下:12M1(1)基本区域D，i1,2,.,n1i每个常量都是某个d中的元素1i每个变量都在某个D中取值1i每个j目函数都是一个映射：DxDx.xD,D气吗气nj+1每个j目谓词都是一个映射：DxDx.xD,(T,F)1i11i21ij如果存在如下关系：(1)i,DD；12iiM2基本区域D，i1,2,.,n2i每个常量都是某个D中的元素2i每个变量都在某个D中取值2i每个j目函数都是一个映射：DxDx.xD,D22j?2i.2ij+1每个j目谓词都是一个映射:DxDx.xD,(T,F)2i2i

7、2i12j(2)同一常量相对于M和M，取某个D中的同一元素为其值121i(3)M的每个函数e是M的一个函数e在e定义域上的一个限制即对每11221组变元(a,1.a.).年D，Dj1i11i2,D1ij(即e的定义域)，有1e(aa)e(a，a)11j212M的每个谓词p是的一个谓词p在p定义域上的一个限定。即对每组1121变元(aa)eD,D,.,D(即p的定义域)，有p(a,.,a)p(a,.,a)1j1i11i111j21ji1i2ij则称M为M的一个子模型，以MM表示。如果至少有一个i，使得D真12122i包含D，即DuD，则称M为M的一个真子模型，以MM表示。没有1121212iii

8、真子模型的模型被称为极小模型。定义3-2-2(参见教材)极小蕴涵的定义：若命题C被公理系统A的所有极小模型所蕴涵，则称A极小蕴涵C,以右c表示。m实例：自然数公理系统的极小模型(参见陆汝钤人工智能(下)xy,Z(x)aZ(y)Txyxyz,S(x,y)aS(x,z)Tyzxyz,S(x,y)aS(z,y)txzxy，Z(y)TA(x,y,x)xyzuv,A(x,y,z)aS(y,u)aS(z,v)TA(x,u,v)xy,Z(y)TP(x,y,y)yzuv,P(x,y,z)aS(y,u)aA(z,x,v)TP(x,u,v)如果将Z(x)解释成0S(x,y)解释成yx+1；A(x,y,z)解释成z

9、x+y；P(x,y,z)解释成zxy；则可得一个标准的算术模型，即全体自然数的集合。注：它是上述公理系统的唯一极小模型。3-2-1-3谓词限定由提出的限定推理的一种形式化方法，是领域限定的拓广。(1单)谓词限定设A是一个命题或一阶逻辑子句，其中含有一个谓词P(xx)，用P(x)表1ni示，用A3/P)表示以谓词表达式替换P在A中的所有出现，A3)表示这种替换后的结果。则定义谓词p在a(p)中的限制是如下子模式：A()(Vx)(x),P(x),(Vx)P(x),(x)(3一2一1)iiiiii其中，A()表示：谓词表达式满足所有条件；(Vx)(x),P(x)表示：iii满足的事物都满足p的事物之

10、集合；(Vx)P(x),(x)表示：P和必须是iii一致的。另外，i1,2,3,.,n。则谓词限定表示：只有同时满足命题A的那些参量组x才能满足谓词P。i例如：积木世界中命题A：is一block(a)is一block(b)is一block(c)表示a,b,c都是积木。即谓词is-block被限定在a,b,c范围内。则由得：(a)(b)(c)(Vx)(x),isblock(x),(Vx)isblock(x),(x)令(x)(xa)v(xb)v(xc)代入上式，由命题定义，可得出上式的右边如下：(Vx)is一block(x),(x=a)v(x=b)v(x=c)。即如果把谓词is一block限定在命

11、题A所限定的范围内，贝Ua,b,c就是所有的积木。(2多)个谓词的限定例如：对谓词P和Q，有如下限定：A(,9)(Vx)(x),P(x)(Vy)9(y),Q(y)iiiiii，(Vx)P(x),(x)(Vy)Q(y),9(y)iiiiii3-2-1-4公式限定(略)功能强大，但本质上是一个二阶逻辑推理问题，没有有效的方法进行限定。3-2-1-5平行限定(略)由提出，可以平行地对多个谓词进行限定3-2-1-6小结限定理论的两个主要问题：引入的用于描述谓词限定和论域限定的极小模型并不总是存在的。(2在)谓词限定方面，他没有指出应当对哪些谓词作限定，使得对谓词的不同限定会得到不同的推理结果。限定推理

12、的几种方式(参见陆汝钤人工智能(下)-(1论)域限定谓词限定公式限定平行限定三可以进行常识推理3-2-2缺省逻辑(DefaultLogic)3-2-2-1缺省逻辑实例计算机程序设计活动中的缺省：如果程序员不显式地指出某种要求，则系统将按约定(缺省)章程行事。程序设计语言中，不给数值型变量给初值，则其变量的值为0。一个框架中，如果一个槽设计了缺省值，则程序运行到此时，用户不给值则系统采用默认值。如人的体温默认为37。分程序结构中，内、外层的标识符相同时，内层标识的缺省就是外层的标识符，除非内层另有说明。宋江例子中的缺省：宋江在滔滔大江边时，没有船或其它渡江手段时，此江在缺省意义下是不能渡的。宋江

13、跨上小船时，如果船家没有异样表现，则缺省意义下，靠此船渡过江去是可行的。当张横喝问宋江“吃馄饨还是刀板面？”时，如果没有救星，缺省意义下，宋江自任“此命休也！”。3-2-2-2运用缺省推理的原因及基本思想引入原因：人们在推理时所能获得的信息往往是不完备的，往往也不能等到收集完信息才进行推理。因此，缺省是表达非单调推理的有力手段。Reiter引入缺省推理的基本思想：传统逻辑：从已知事实出发推出新事实。非单调逻辑推理：知识库不够丰富，难以支持所需推理。因此，需要扩充知识库中的知识，即缺省知识(它们并非绝对可靠)。则原来的知识称为不完备理论。而扩充的知识称为对原来理论的完备化。由不完备理论加缺省知识

14、一起推出的结论事实，称为对现实世界的一种猜测。缺省逻辑：为缺省推理提供一组元公理系统后的逻辑系统。缺省推理前提：在没有证据证明某命题不成立时，则承认其成立。因此又称为默认推理。3-2-2-3对不完备理论的扩充定义不完备的理论：即原来的知识库。也即当前已知的知识。对不完备理论的扩充：“想当然”地对知识库进行扩充，即增加缺省知识。定义3-2-2-1缺省逻辑的合适公式和缺省命题。一阶谓词合适公式是缺省逻辑的合适公式。缺省逻辑(DL)系统的缺省命题形式为：a:M卩(QM卩”或,(x):陋卩(x),.,M卩(x)tW(x)，其中，x是由多1mW(x)个x构成的参数向量。，(x)是命题的前提，W(x)是命

15、题的结论，M是缺省i算子M卩(x),.,M卩(x)是缺省要求。读成：如果没有信息表明卩(x),.,卩(x)1m1m中任何一项不成立，则从前提，(x)可以推出结论W(x)。例如：x是数值型变量：M程序中为x赋值x0河边没有船：M过不了河过不了河BIRD(x):MFLY(x)FLY(x)定义3-2-2-2一个不含自由变量的合适公式称为是闭的或封闭的。若,(x)，卩(x),.,卩(x)，W(x)都是闭的合适公式，J则定义3-2-2-1的缺省1m命题称为闭缺省命题。一个缺省理论由一个二元组(D,W)构成，其中，D是一组缺省命题，W是一组闭的合适公式。如果D中缺省命题都是闭的，则缺省理论(d,W)成为是

16、闭的。注1：一般的缺省命题不是闭的。下面命题是闭缺省命题：凡人都是要死的：M彭祖是人彭祖是要死的注2:一般只考虑闭缺省命题。因此，a(x)，卩(x卩(x)，W(x)的参量可1m以省去。注3:缺省命题虽然可以表示许多模糊量词，如“几乎”、“大多数”、“一般”等，但它不涉及模糊逻辑。注4:对缺省逻辑的进一步研究和讨论(参见陆汝钤人工智能(下)。3-2-2-4缺省规则或命题的分类规范缺省命题A(x)：MB(x):由A(x)一般可推出C(x)。B(x)半规范缺省命题A(x):M(C(x)八D(x):除(x)外，由A(x)一般可推出c(x)。C(x)非规范缺省命题除前面两类之外的其它形式的缺省命题。其它

17、分类情形如果缺省命题不含自由变量，则称为封闭的或闭的；如果先决条件为空，则称为重言式；如果默认条件为空，则退化成演绎规则。3-2-2-5小结缺省逻辑主要用于常识性推理。缺省逻辑的困难：(1)增加一条新的缺省规则时，能否保证推理结果的一致性；(1)Reiter建立的完整性维护系统工作过程复杂，实际运用有困难。3-2-3自认识逻辑限定推理和缺省逻辑共同特点：给定前提下进行似然推理。观点：非单调性是由于推理者所具有的知识的局限性所造成。其思想可描述为：我相信某些事实A是真的，我没有根据相信另外一些事实B是假ij的，则我期待C是什么？由此，Moore引入两个算子l和M。若A是一个命k题，则LA表示相信

18、命题A，MA表示可接受命题A或命题A与推理者当前的知识不矛盾。其关系是：MALA。定义3-2-3-1自认识逻辑系统的合适公式(只考虑命题逻辑)：(1)普通命题逻辑的合适公式是AE系统的合适公式；若A是合适公式，则LA和MA也是合适公式；若A，B是合适公式，则A,AvB,A,B,AB和A三B也是合适公式。定义3-2-3-2自认识逻辑系统的命题真假值的取值规定：不含L和M的命题按普通命题逻辑的真值指派原则进行；若a,b是真假值已知的合适公式，贝Ua，avB，A,B，AtB和A三B真假值按普通逻辑的语义定义。普通逻辑中的推理规则于此皆适用。定义3-2-3-3如果自认识逻辑系统中命题的真值指派满足以下

19、规则，则称其为稳定的自认识逻辑系统。若a为真，则la也为真;若A为假，则la也为假。定义3-2-3-4自认识理论：一个具体的AE系统的全部命题之集合。它包括了一个推理者所有的全部信念之集合。自认识理论的一个解释：对一个自认识理论中的全部命题进行真值指派。其真值指派符合普通命题逻辑中的所有真值指派规则。且对LA形式的命题指派除不违背上述规则外，可以是任意的。自认识理论的一个(普通命题逻辑意义下的)模型：设i为自认识理论下的一个解释，则解释中全体被指派为真的命题构成自认识理论的一个模型。自认识理论的一个自认识解释：设I是自认识理论的一个解释，如果命题A被指派为真，当且仅当命题LA被指派为真。(5)

20、自认识模型：设i是自认识理论的一个解释，则解释中的全体被指派为真的命题构成自认识理论的一个自认识模型。定义3-2-3-5(1)自认识理论T对公理集A是健康的：当且仅当：如果t的一个自认识解释是公里集A在普通命题逻辑意义下的模型，则它也是T的一个模型。一个自认识理论T称为是语义完备的：当且仅当：如果A是一个在T的所有自认识模型中皆为真的命题，则A本身包含在T中。结论：稳定的自认识理论保证了系统的健康性，是否健康仅取决于自认识理论中不含L和M的命题(称其为客观命题)。稳定的自认识理论被比喻为一个理想的推理者，他在已有的公理下是无所不知的，且所知必真。3-2-4非单调推理中的难题3-2-4-1McD

21、ermott的耶鲁射击问题某甲在时刻t是活着的；1（2）某乙在时刻tt把子弹装进枪膛；21某乙在时刻tt举枪对准某甲射击；32问题：某甲在时刻tt还活着吗？43McDermott引入了情况演算：将时间轴分成一个个时间区间（见时序推理部分！）,如果在一个时间区间内所有命题都不发生变化，则连同时间区间在内称其为一个情况。3-2-4-2与非单调推理相关的悖论（1）彩票悖论：为筹集资金，某单位发行一百万张彩票，并事先宣布：只有一个特等奖：一辆Audi轿车。统计学家立即知获此奖的机会是百万分之一。悖论：购买任一张彩票获特等奖的希望几乎是为零，即几乎没有希望。该结论适合于每张彩票，因此，1000000张彩

22、票并置起来的结论是：所有彩票都是没有希望的。但开奖结果，却总有一张是大有希望的。因此，有：，x,彩票（x）T无希望（x）x,彩票（x）A有希望（x）反例悖论：McCarthy的限定推理中，说“某种鸟会飞”则极小模型告诉我们：只有这中鸟会飞。因此，只要同时指出一个反例，则上述结论就会动摇。用缺省逻辑也有类似的不合常理的推理结论问题。如，“野猪是唯一不能飞的鸟”（实例参见陆汝钤人工智能（下）。（3）反常悖论：（实例参见陆汝钤人工智能（下）。325真值维护系统（Truthmaintenancesystem-TMS）基本思想：用非单调推理的思想来维护知识库。是非单调推理的核心技术之一。用来维持推理的一

23、致性。基本构成：非单调推理的基本构成可由两部分构成，即S二A。其中，为基本信念集，A为假设集，是对的尝试性扩充。由于推理系统中，为永真部分，因此，推理产生的不一致性，可以看成是由不同的假设a引起的。TMS:最早由Doyle建立(1979年)，其作用在于协助问题求解系统维护推理过程的正确性、一致性和相容性，而不是产生新的推理行为或过程。TMS的基本原理：TMS中每个命题或规则均称为节点，且任一节点有IN(相信为真)或OUT(不相信为真或无理由相信为真或当前没有为真的可信的理由)状态。每一个节点附有一证实表，表中每一项表示一种确定节点是否有效的方法。有两种方式证实一个节点的有效性依赖于其它节点的有效性：支持表(SL(IN-节点)(OUT-节点)(3)条件证明(CP(结论)(IN-假设)(OUT-假设)支持表实例分析(SupportList):现在是冬天(SL()()天气是寒冷的(SL(1)(2)