（基础数学专业论文）缺省逻辑的扩充.pdf

缺省逻辑的扩充 傅丽 摘要r e i t e r 酊缺省逻辑是最受关注的非单调推理理论之一，它已被广泛 应用于人工智能的各个领域，其中缺省逻辑的扩充是研究的热点缺省逻辑的扩 充要求添加可以接受的事实或( 与原有的事实不矛盾，并且彼此相容的缺省规则 的) 结论以求达到某种完备性由于事实集与缺省规则集均可能具有较为复杂多 样的形式，而且已有的计算缺省理论扩充的方法都不是构造性的，因此完成扩充 在计算上是困难的， 本文首先从一种形式上较为简单的有限的无前提正规闭缺省理论入手，讨论 了其相容扩充的分类与性质等然后讨论了映省逻辑的表示性，研究了如何用和 它具有相同扩充，但语构上较为简单的缺省逻辑来表示原缺省逻辑的问题；又， 为便于计算扩充，本文讨论了在计算具体的缺省理论的扩充前如何对缺省规则进 行适当的简化和分类的问题，给出了相应的简化和分类原则本文还系统地研究 了为修正缺省逻辑的缺陷而提出的r o o s 扩充以及累积缺省逻辑的扩充问题最 后，本文讨论了统计缺省逻辑扩充的性质与计算，并定义和研究了闭正规的统计 缺省逻辑的性质及其证明理论全文共分五章 第一章是本文所用到基本知识 第二章较系统地研究了有限的无前提正规闭缺省理论的相容扩充首先，对 相容扩充进行了分类；其次。给出了相容扩充的特征刻画；再次，建立了一种制 作相容扩充的准构造性方法；最后，对缺省规则固定时。缺省理论可能有的不同 相容扩张的个数进行了估计 第三章首先运用缺省理论的扩充集来研究缺省理论的表示性讨论了缺省理 论的等价性；证明有无限点式不相容扩充的缺省理论可由( 无前提) ( 半) 正规缺省 理论表示任一缺省理论( d ，w ) 均可由一个含空事实集的缺省理论( d ，w = 韬) 来表示，我们将指出w = o 也可以放宽同时，给出一些例子作了进一步的说 明；其次。从缺省理论扩充的定义出发，在求扩充前根据缺省规则的特征，把对 计算扩充没有影响的规则不予考虑，同时把具有不相容判断的规则分开考虑，也 即就是在求扩充前对缺省规则进行适当的简化和分类，并通过分析讨论给出了若 干简化和分类的原则，从面使计算得以简化；最后。针对r o o s 为了克服r e i t e r 缺 省理论不能分情形推理的缺陷提出的r o o s 扩充，我们讨论了r o o s 扩充与r e i t e r 扩充的一些相似的性质，发现r e i t e r 扩充的某些性质对r o o s 扩充不再成立。如 r o o s 一不相容扩充可能不唯一我们指出了它们之间的不同，并举例作了说明 第四章将g r i g o r i sa n t o n i o n 的语义算子理论算法及v w m a r e k 和m f r u s z c y u s k i 的语构算法用于计算累积缺省逻辑( c d l ) 的扩充，系统地讨论了c d l 及其新 变种c a d l 与q d l 理论的扩充问题，从而使得具有累积性的缺省逻辑扩充的计 算问题得以系统化，我们还指出邀两种方法可用于其他类型的缺省理论扩充的计 算，并以优先缺省理论的扩充为例说明这一点 第五章讨论了统计缺省理论的扩充，它是经典缺省逻辑( 即r e i t e r 的缺省) 的推广，它借助错误参数e ，允许我们在标准的推理统计中模型化普遍的推理模 式由于统计缺省扩充不具备封闭性，在其对应的r e i t e r 扩充存在时。它的扩充 可能不存在；甚至可能出现正规的统计缺省理论没有扩充然而，在给出一定的 限制条件下，即如果我们除了要求缺省规则中出现的公式是闭公式外，同时还要 求所有“可适用缺省规则”在内是封闭的，也即同时满足条件q = + b f ， 则可以克服这一缺陷，此时统计缺省逻辑的扩充也具有如r e i t e r 扩充一样的很好 的性质在文中我们也给出两种计算方法来求统计缺省扩充同时，定义并讨论 了闭正规的统计缺省理论的扩充的性质和证明 关键词：( 正规) 缺省理论；无前提；相容扩充；个数估计；缺省规则；判断； 简化原则；分类原则；累积缺省逻辑；断言缺省逻辑；支持；表示性；统计扩充； 统计缺省逻辑；约束句子；c - 约束；半单调性 i i e x t e n s i o n so ft h ed e f a u l tl o g i c f u l i a b s t r a c tr e i t e r 7 sd e f a u l tl o g i ci so n eo ft h em o s tp o p u l a rf o r m a l i s mf o rd e s c r i b i n g n o n - m o n o t o n i cr e a s o n i n ga n di se x t e n s i v ei n v e s t i g a t e db yt h ec o m m u n i t yo fl o g i c a l f o u n d a t i o n so fa r t i f i c i a li n t e l l i g e n c e ，p a r t i c u l a r l y , d e f a u l te x t e n s i o ni st h eh o ti s s u e i ns y m b o l ，t oa c h e i v es o m ec o m p l e t e n e s s ，t h ee x t e n s i o n so fd e f a u l tt h e o r yr e a l i z e t oe x p a n dt h es e two fw o r l d s ，u s i n gd e f a u l tr u l e sa d ds o m ea c c e p t a b l eo rb e l i e v e w o r l d so rc o n c l u s i o n st ot h es e to fw o r l d s ，a n di tr e q u i r e st h e mc o n s i s t e n te a c ho t h e r ， a n dh a v en oc o n t r a d i c tw i t ht h eo r i g i n a lw o r l d s ，( o t h e r w i s e ，i t 7 si n c o n s i s t e n t ，i tt h e r e e x i s t sw i t hi n c o n s i s t e n te x t e n s i o n ，a n dt h i si n c o n s i s t e n te x t e n s i o ni st h eo n l yo n e ) t h a ti s ，w eo n l yc o n s i d e rt h o s ea d d i n gw o r l d so rc o n c l u s i o n sa r ec o n s i s t e n tw i t h t h eo r i g i n a lk n o w l e d a g eb a s e h o w e v e r ，w ek n o wt h es e to fw o r l d sa n dt h es e to f d e f a u l tr u l e sa l la r ec o m p l e xa n dv a r i e d a n da l lm e t h o d so fc o m p u t i n ge x t e n s i o n s a r eq u a s i - c o n s t r u c t i v e ，s ot h ep r o b l e mo fc o m p u t i n ge x t e n s i o n si sh a r d i nt h i sp a p e r ，f r o mt h es i m p l es y n a t i cc l o s e dn o r m a ld e f a u l tt h e o r i e sw i t h o u t p r e q u i s i t e ，w ef i r s td i s c u s st h ec l a s s i f i c a t i o n sa n dp r o p e r t i e se t co fi t sc o n s i s t e n te x t e n s i o n ，t h e nw er e s p e c t i v e l yd i s c u s st h er e p r e s e n t a t i o no d e f a u l tl o g i c ，t h a ti s ，w e c a nu s et h ed e f a u l tt h e o r yt h a th a st h es a m ee x t e n s i o n sw i t hi t ，b u ti ss i m p l e ri n s y n a t i ct or e p r e s e n ti t ；t os m p l i f yc o m p u t i o n ，w ec a nc l a s s i f ya n ds i m p l i f yp r o p e r l y d e f a u l tr u l e sb e f o r ec o m p u t i n ge x t e n s i o n sa n dc o n c l u d et h ec o r r e s p o n d i n gs i m p l i c a t i o na n dc l a s s i f i c a t i o np r i n i c i p l e w es y s t e m a t i c a l l yi n v e s t i g a t e st h ep r o p e r t i e s o fr o o s - e x t e n s i o n st h a ti sm o d i f i e dt h ed e f e c to fd e f a u l tl o g i c ，a n dt h ep r o p e r t i e s ，c o m p u t i o no ft h ee x t e n s i o no fc u m u l a t i v ed e f a u l tl o g i c ( c d l ) a tl a s t ，w ed i s c u s s t h ep r o p e r t i e sa n dc o m p u t a t i o no ft h es t a t i s t i c a ld e f a u l tl o g i c ，a tt h es a m e t i m e ，w e d e f i n ea n ds t u d yt h ep r o p e r t i e sa n dp r o o ft h e o r yo ft h en o r m a ls t a t i s t i c a ld e f a u l t l o g i c t h e r ea r ef i v ec h a p t e r si nt h i sp a p e r c h a t c e rli st h eb a s i ck n o w l e d a g et h a ti su s e di nt h i sp a p e r c h a p t e r2s y s t e m a t i c a l l yi n v e s t i g a t e st h ec o n s i s t e n te x t e n s i o n so ft h ef i n i t e c l o s e dn o r m a ld e f a u l tt h e o r i e sw i t h o u tp r e r e q u i s i t e f i r s t ，ac l a s s i f i c a t i o nt h e o r e m o fc o n s i s t e n te x t e n s i o n si s p r o v e n ；s e c o n d ，c e r t a i nc h a r a c t e r i z a t i o nt h e o r e m sf o r i i i e x t e n s i o n sa r ep r o v i d e d ；t h i r d ，aq u a s i c o n s t r u c t i v em e t h o d f o rc o n s t r u c t i n ge x t e n s i o n si sp r o p o s e d ；m o r e o v e r ，p o s s i b l en u m b e r so fd i f f e r e n te x t e n s i o n so fad e f a u l t t h e o r yi se s t i m a t e d i nc h a p t e r3 f i r s t ，w eu s et h es e to fd e f a u l te x t e n s i o n so fd e f a u l tt h e o r y t oi n v e s t i g a t et h er e p r e s e n t a b i l i t yo ft h e o r i e sa st h es e to fe x t e n s i o n so fad e f a u l t t h e o r y w eg i v es o m ep r o p e r t i e so fe q u i v a l e n c eo fd e f a u l tt h e o r i e s ；w es h o wt h e d e f a u l tt h e o r i e so f h a v i n gf i n i t ep a i r w i s ei n c o n s i s t e n te x t e n s i o n sc a nb er e p r e s e n t e d b ya ( p r e r e q u i s i t e - f r e e ) ( s e m i ) n o r m a ld e f a u l tt h e o r y a l s ot h e r e i sr e s u l tt h a te v e r y d e f a u l tt h e o r y = ( d ，w ) i sr e p r e s e n t a b l ei nt h ec l a s so fd e f a u l tt h e o r i e sa = ( d ，w = 0 ) ，w ew i l lp o i n tw = 0 i sn o tn e c e s s a r y a tt h es a m et i m e ，w eg i v es o m e e x a m p l e sf o rf u r t h e re x p l a i n i n gt h i s ，s e c o n d ，i nt h i sp r e s e n tp a p e r ，b yt h ed e f i n i t i o n o fd e f a u l te x t e n s i o n s ，s o m ed e f a u l tr u l e sc a nn o tb ec o n s i d e r e dt h a th a v en oe f f e c t t oc o m p u t ee x t e n s i o na n dc a nb ec l a s s i f i e dw h o s ej u s t i f i c a t i o na r ei n c o n s i s t e n te a c h o t h e rb e f o r ec o m p u t i n gt h ee x t e n s i o n so fd e f a u l tt h e o r y t h a ti s ，t h i sp a p e rc l a s s i f i e s a n ds i m p l i f i e sp r o p e r l yd e f a u l tr u l e sb e f o r ec o m p u t i n ge x t e n s i o n ，a n dg i v e ss o m e c l a s s i f i c a t i o na n d s i m p l i f i c a t i o np r i n c i p l e s f i n a l l y , o n ei m p o r t a n td e f e c to fr e i t e r 7 s d e f a u l tl o g i ci s i n a b i l i t yt o r e a s o nb yc a s e s ，t oo v e r c o m et h ed e f e c td e f i n i t i o no f r e i t e r se x t e n s i o n r o o sp r e s e n t sam o d i f i e dd e f i n i t i o no fad e f a u l te x t e n s i o nt h a t s o l v e st h ep r o b l e m i nt h i sc h a p t e r ，w ew i l ld i s c u s st h ep r o p e r t i e so fr o o s - e x t e n s i o n t h a ts i m i l a rt or e i t e r - e x t e n s i o n ，a n dw i l lf i n ds o m ep r o p e r t i e so fr e i t e r - e x t e n s i o n c a r ln o ts t i l lc o r r e c tt or o o s - e x t e n s i o n ，f o re x a m p l e ，r o o s i n c o n s i s t e n te x t e n s i o n s m a yb en o tt h eo n l yo n e w ep o i n to u tt h ed i 能r e n c eo ft h e ma n de x p l a i nt h e s e u s i n ge x a m p l e s c h a p t e r4u s i n gc r i g o r i sa n t o n i o n ss e m a n t i co p e r t i o n a lt h e o r ya l g o r i t h m s a n dv w m a r e k m f r u s z c y u s k i ss y n a t i ca l g o r i t h m st oc o m p u t et h ee x t e n s i o n s o fc u m u l a t i v ed e f a u l tl o g i c ( c d l ) a n ds y s t e m i c a l l yd i s c u s s e st h ee x t e n s i o n so fc d l a n di t st w on e wv a r i a r i t sc a d l ，q d l a sar e s u l t ，i ts y s t e m a t r i e st h ee x t e n s i o n so f c u m u l a t i v ed e f a u l tl o g i c ，a n dp o i n t st h e s et w om e t h o d sc a nb eu s e dt oc o m p u t e e x t e n s i o n so fo t h e r sd e f a u l tt h e o r i e s ，w i t h o u tg e n e r a l i t y ，w eu s et h e s et w om e t h o d s f o rt h ee x t e n s i o n so ft h ep r i o r i t i e dd e f a u l tt h e o r i e s c h a p t e r5d i s c u s s e ss t a t i s t i c a le x t e n s i o n so fs t a t i s t i c a ld e f a u l tl o g i c ，a l le x p a n s i o no f c l a s s i c a l ( i e r e i t e r s ) d e f a u l tl o g i ct h a ta l l o w su st om o d e lc o m m o ni n f e r e n c e p a t t e r n sf o u n di ns t a n d a r di n f e r e n t i a ls t a t i s t i c s ，w h i c hi sa ne x p a n s i o nb ym e a n s i v o fe r r o r p a r a m e t e re a n b o u n df o rs h o r t w ef i r s tp o i n ti t h a sn oc l o s e d p r o p - e r t y ，s o ，i t sc o r r e s p o n d i n gr e i t e rd e f a u l tt h e o r yc a nh a v ee x t e n s i o n s ，b u t i tc a l lh a v e n oa n ys - e x t e n s i o n s ，e v e ni ft h en o r m a ls t a t i s t i c a ld e f a u l tt h e o r yc a nh a v en oa n y s e x t e n s i o n s ，t o o h o w e v e r ，i fg i v e ns o m el i m i t e dc o n d i t i o n s ，t h a ti s ，w er e q u i r et h e f o r m u l a so fd e f a u l tr u l e sa r ec l o s e df o r m u l a s ，a tt h es a i t l et i m e ，t h e ym u s ts a t i s f y t h ec o n d i t i o n 白。e a + 岛e ，t h e nw ec a no v e r c o m et h i sd e f e c t ，a n da tt h i st i m e ， t h es e x t e n s i o n so ft h es t a t i s i t i c a ld e f a u l tl o g i ch a v et h es a m ep r o p e r t i e sw i t ht h e r e i t e r se x t e n s i o n s i nt h i sp a p e r ，w ea l s og i v et w om e t h o d st oc o m p u t es - e x t e n s i o n w ed e f i n ea n dd i s c u s st h ep r o p e r t i e sa n dp r o o fo ft h ec l o s e dn o r m a lc l o s e dn o r m a l 8 t a t i s t i c a ld e f a u l tt h e o r i e s k e y w o r d s ( n o r m a l ) d e f a u l tt h e o r y ；p r e r e q u i s i t e - f r e e ；c o n s i s t e n te x t e n s i o n ；n u m b e r e s t i m a t i o n ；r e p r e s e n t a b i l i t y ；d e f a u l tr u l e ；j u s t i f i c a t i o n ；s i m p l i f i c a t i o np r i n c i p l e ；c l a s - s i f i c a t i o np r i n c i p l e ；c u m u l a t i v ed e f a u l tl o g i c ；a s s e r t i o n a ld e f a u l tt h e o r y ；s u p p o r t ；s t a - t i s t i c a le x t e n s i o n ：8 t a t i s t i c a ld e f a u l t l o g i c ；b o u n d e ds e n t e n c e ；e - b o u n d ；s e m i m o n o t o n i c i t y v 学位论文独创性声明 y 7 2 8 3 6 4 本人声明所呈交的学位论文是我在导师的指导下进行的研究工作及取得的 研究成果尽我所知，除文中已经注明引用的内容外，论文中不包含其他个人 已经发表或撰写过的研究成果，也不包含为获得陕西师范大学或其它教育机构 的学位或证书而使用过的材料。对本文的研究做出重要贡献的个人和集体，均 已在文中作了明确说明并表示谢意。 作者签名：醒歪目日期：2 生丛： 学位论文使用授权声明 本人同意研究生在校攻读学位期间论文工作的知识产权单位属陕西师范大 学本人保证毕业离校后，发表本论文或使用本论文成果时署名单位仍为陕西 师范大学。学校有权保留学位论文并向国家主管部门或其它指定机构送交论文 的电子版和纸质版；有权将学位论文用于非赢利目的的少量复制并允许论文进 入学校图书馆、院系资料室被查阅；有权将学位论文的内容编入有关数据库进 行检索；有权将学位论文的标题和摘要汇编出版。 作者签名： 前言 传统的推演逻辑总是单调的( m o n o t o n i c ) ，增加新假设不会破坏原有的结论， 等价地说，结论集随着假设集单调地增加，形式地说：“一种逻辑是单调的”当 且仅当“它的可证关系满足：对任一假设集s 与，由s 可推出f af s 卜_ a ) als 卜a 卜事实上，在人类的推理中，有许多逻辑系统不满足单调性， 许多时候原有的结论随着新信息的增加不再成立，借用人工智能的术语来说，在 逻辑系统中存在许多非单调推理( n d 佗一m o n o t o n i cr e a s o n i n g ) 形式第一个试图 系统地形式化非单调推理的是s a n d e w a l l ( 1 9 7 2 ) ，而“非单调”这一术语最初是由 m i n s k y 在1 9 7 5 年提出的现在，非单调推理巳成为人工智能和信息科学中活跃 的研究领域之一它在数据挖掘，智能控制，机器学习，知识获取，医疗诊断，专 家系统，人工神经网络，数据库知识发现，机械故障诊断，财政与市场分析等领 域有广泛的应用r e i t e r ( 1 9 8 0 ) 1 】的缺省逻辑是最成功的非单调推理形式之一， 已被广泛应用于人工智能的各个领域，而缺省扩充又是研究的主要热点缺省逻 辑的扩充要求加入的是可以接受事实或( 彼此相容，且与原有的事实不矛盾的缺 省规则的) 结论以求得到某种完备性，也就是说，在实际的应用中，我们仅需要 考虑那些可适用的缺省规则的结论，研究它们是否与我们已有的知识体系相容 但由于事实集与缺省规则集均可能具有较为复杂多样的形式，而且已有的计算缺 省理论扩充的方法都不是构造性的，似乎是从未知到未知”，因此实际计算扩充 是困难的 本文首先从形式上较为简单的有限的无前提正规闭缺省理论入手，较系统 地研究了有限的无前提正规闭缺省理论的相容扩充对相容扩充进行了分类；给 出了相容扩充的特征刻画；而且，建立了一种制作相容扩充的准构造性方法；同 时，对缺省规则固定时，缺省理论可能有的不同相容扩张的个数进行了估计 在命题逻辑和谓词逻辑中，常考虑公式的标准表示问题，例如，对每一个命 题公式妒，存在一个合取范式型的公式妒，使得妒和妒有相同的模型( 即逻辑等 价) ，事实上，存在一种简单的算法从妒构造妒类似地，缺省逻辑也存在表示 性问题，其主要特征是缺省逻辑的表示理论可由某一确定的有相同扩充集的缺省 理论表示已有的一些结论表明缺省理论可由语构上较简单的具有相同扩充的缺 省理论来表示，有关缺省逻辑表示理论已有一些有意义的结果( 例如可参阅文献 1 7 - 3 1 ) ，然而关于无限的，非正规缺省理论在这些结果中并没有考虑到，这是一 个较难的公开问题苏开乐教授在文献 2 2 】中针对“无推理( i n f e r e n c e f r e e ) ”，即 无前提正规缺省理论讨论了这一问题在本文中，我们将证明无前提不是必要的 条件，并且有有限点式不相容扩充的缺省理论可由半正规缺省理论表示；还有结 论表明任一缺省理论，w ) 均可由一个含空事实集的缺省理论( d ，w = 0 ) 来 表示，我们将指出w = 0 也可以放宽 关于缺省理论的扩充的求法较为系统的有g r i g o r i sa n t o n i o u 从缺省逻辑的算 子语义出发，通过建立“进程树”来求扩充的语义方法和v w m a r k ，m t r u s c z y n s k i 从语构角度出发，根据缺省规则结论及其特点引入良序而构造性地求扩充的语构 方法这两种方法对有限缺省规则而言在理论上都是可行的，但是在实际计算时 如果缺省规则比较多，这些方法特别是语构方法情形较为复杂，显得相当繁琐， 给计算造成了很大困难我们知道，缺省理论的扩充存在两大弊端，其一是无法 描述缺省规则间固有的逻辑关系，即没有累积性( c u m u l a t i v i t y ) 3 4 - 6 2 ，其二是无法 描述结论与验证式之间的逻辑依赖关系，它不要求所有可应用的缺省的判断是相 容的事实上，为了描述结论与验证式之间的逻辑依赖关系和简化算法，张明义 先生已经提出了自相容缺省理论在考虑规则判断的相容性时，我们发现有些规 则对求扩充没有影响，而且可以把具有不相容判断的缺省规则分开讨论，这与自 相容缺省理论的思想是符合的，在实际上也是可行的所以，为便于计算扩充， 本文指出了在计算具体的缺省理论的扩充前，可以对缺省规则进行适当的简化和 分类也正是基于此种想法，本文通过具体的示例分别讨论了缺省规则的分类问 题和简化问题，给出了分类和简化的基本原则，从而明显地简化了准构造性地求 扩充的计算 r e i t e r 的缺省逻辑存在的一些缺陷，如它有时会导出某些非直觉的结果， 往往使得缺省规则间的相互作用引起悖论，起原因在于，它不能分情形来进行推 理，而实践中很多时候是需要分情形进行推理的为了克服这一缺陷，近年来，修 正缺省逻辑的研究十分活跃，这要求缺省逻辑不只是能分情形进行推理，而且应 该不引起某些缺省规则间的矛盾在缺省逻辑的研究中已经提出了几种关于分情 形推理 1 6 , 2 4 - - 3 6 , 3 9 , 4 5 - - 删的方法如m o i n a r d 在文献1 3 6 】中分析了这些问题，并且 提出缺省扩充的修正定义以解决这一问题的方法，他证明了缺省规则的一种简单 的转化可以使得运用r e i t e r 最初的扩充定义进行分情形推理成为可能相应的， v o o r b r a a k 在文献 5 7 】中提出了一种相似的转化，然而当分情形推理不可能时， 这种转化就忽略了可适用缺省规则的结论，从而就将可能的解忽略掉为了克服 这些缺陷，r o o s 在文献 5 9 】中修正了r e i t e r - 扩充的定义，提出了r o o s 一扩充的 问题，并且讨论了这两种扩充之间的关系张明义教授在文献【4 5 ，5 1 5 3 ，5 8 】已 经研究和讨论了如何借助句子型缺省逻辑如何计算缺省逻辑的r o o s 扩充，并且 2 得到一些好的结论许道云教授等在文献 5 4 5 5 】中讨论了句子形缺省逻辑中的 分情形推理，他们提出了一种“树”的方法来研究缺省逻辑中的分情形推理，并 提出了一种算法来计算取自句子集的文字的最小集合，并且运用这种方法来计算 r d o s _ 扩充，得到与r e i t e r - 扩充相类似的一些结论本文在已有结论的基础上， 没有借助“句子型”缺省规则，讨论和证明了r o o s - 扩充与r e i t e r 一扩充相区别的 一些性质 近年来，鉴于r e i t e r 的缺省理论d l 存在一些不足之处，如有时它会导出一 些非直觉的结果，d l 不是积累的，且不承诺预设( c o m m i t t oa s s u r a p t i o n ) 等，为修 正这一缺陷，b r e w k a 1 8 , a 4 提出了一种具有累积性的缺省逻辑( c u m u l a t i v ed e f a u l t l o g i c ( c d l ) ) ，c d l 具有累积性且承诺假设，同时具有半单调性，只是半单调性破 坏了非正规缺省理论的附加表达( a d d i t i o n a le x p r e s s i o n e s s ) ，从而使得缺省之间的 优先性表示成为不可能为此，c i o r d a n o 在文献【3 5 1 ，m a k i n s o n 在文献【3 9 ，4 2 】中 提出了两个新变种，c a d l ( c o m m i t m e n t t oa s s u m p t i o n sd e f a u l tl o g i c ) 与q d l ( q u a s id e f a u l tl o g i c ) ，它们都具有累积性，但不具有半单调性然而所有这些理论 的扩充都没有一种具体可行的方法，只有从定义出发去求扩充，似乎是“从未知 求未知”，在计算上几乎是不可能的，更多的只是验证其扩充的存在性本文借助 o r i g o r i sa n t o n i o n 1 6 l 的语义算子理论方法以及v w m a r e k 和m f r u s z c u y s k i z 8 , 5 7 1 的语构方法，将其用于求c d l 的扩充，这使计算成为可能同时，我们也指出， 本节所用到的这两种方法也适用于其它形式的d l 变种，如约束的( c o n s t r a i n e d ) 和验证的( j u s t i f i e d ) 缺省理论等。并且这两种方法在使用时只是在具体的形式中 可能略有差异，我们以优先缺省逻辑( p r i o r i t i e dd e f a u l td e f a u l t ( p d l ) ) 为例说明这 一点 统计的概念自提出后已被广泛应用于各个领域，对缺省的研究也不例外( 参 阅文献【6 3 9 2 】) g r e g o r yr w h e e l e r 在文献【7 2 】中最先提出统计缺省，它是经典 缺省逻辑的推广，它允许我们在标准的推理统计中模型化普遍的推理模式这一 理论是由经典的k e i t e r 缺省规则带上单位区间中的实数作为约束的缺省规则之集 和带有约束的事实之集构成的集合序对所组成这个实数是可用缺省规则的结论 能够被接受的错误概率的u p p e r l b o u n d 极限在r e i t e r 标准形式中，缺省扩充是 递归闭的，并且扩充在缺省理论的缺省集下是封闭的然而，这些性质对统计缺 省并不成立，对统计推理的错误概率的约束在推理中不必保证其错误概率不变， 也就是说，统计缺省扩充不是递归闭的，这将使得一些好的性质，如半单调性等 不在成立但是，如果我们在计算统计扩充时限制统计缺省理论是封闭的，并且 对错误参数e 给出一定的限制，也即除了要求缺省规则中出现的公式均为闭公式 3 外，还需要满足条件q = 屯+ bs ；，情况将不一样，本文在此基础上讨论了闭 的统计缺省理论扩充的一些好的性质；同时，在本章我们介绍了两种计算扩充的 方法一是运用统计缺省的结论，另一种是从算子语义的角度出发运用进程树 ”来计算；而且，定义闭的正规统计缺省理论，并系统地讨论了它的扩充，给出 了如半单调性，正交性等一些好的性质，而且讨论了闭的正规统计缺省的证明理 论 4 第一章引言和预备知识 传统的推演逻辑总是单调的( m o n o t o n i c ) ，增加新假设不会破坏原有的结论， 等价地说，结论集随着假设集单调地增加，形式地说：“一种逻辑是单调的” 当 且仅当“它的可证关系满足：对任一假设集s 与，由s s 可推出 al s 卜 a ) ais 卜 ) i 然而，在人类的推理中，有许多逻辑系统不满足单调性， 许多时候原有的结论随着新信息的增加不在成立，借用人工智能的术语，在逻辑 系统中存在许多非单调推理( n o n m o n o t o n i cr e a s o n i n g ) 形式，第一个试图系 统地形式化非单调推理的是s a n d e w a l l ( 1 9 7 2 ) ，这一术语最初是由m i n s k y 在1 9 7 5 年提出现在，非单调推理已成为人工智能和信息科学中较为活跃的研究领域之 一在数据挖掘，智能控制。机器学习，知识获取，医疗诊断，专家系统，人工 神经网络，数据库知识发现，机械故障诊断，财政与市场分析等领域有广泛的应 用其中，以r e i t e r 的缺省逻辑尤为活跃，在此基础上，诸多学者对其进行深入 的研究，得到一些其它的非单调推理形式，如约束( c r i c m u s c r i p e ) 逻辑，自认知 ( a u t o e p i s t e m i c ) 逻辑等 1 1缺省逻辑的背景和主要形式 1 1 1 非单调逻辑的类型 非单调逻辑是由于增加新豹信息会使原有的结论不在成立，在人类的普遍 推理和人工智能领域广泛应用非单调推理也是普遍推理固有的特征，也即较大 的最初的假设集”未必能够得到较大的“结论集”，也正是为了模型化这种非 标准形式系统，提出了非单调逻辑，它借助模态算子“m ，表示湘容地相信” 例如，叙述“在缺少相反信息的情况下”，假使大象是灰色的，用模态非单调规则 可表示为：大象( 茁) am 灰色( z ) 3 灰色( ) 。解释为对任一个个体z ，若 。是大象，且相容地相信。是灰色的，则假设它是灰色的”这一理论最初是由 m c d e r m o t t d o y l e 在文献【9 3 中提出的，接下来，由m c d e r m o t t 在文献【9 4 中 进一步讨论了较强的形式；m o o r e ( 1 9 8 3 ) 在文献 9 5 ，9 6 】中讨论较弱的形式一“择 一的非单调逻辑”其后，有g a b b a y s 在文献【9 7 】中和t u r n e r s 在文献 9 8 】中基 子更异常的情形，直觉逻辑和k l e e n e 7 st h r e e - v a l u e dl o g i c 研究了其它另外两种形 式现在，经常运用的非单调推理形式有： 5 ( i ) 约束( c r i c u m s c r i p t i o n ) 逻辑，这是由j o h nm c c a r t h y 在文献( 9 9 ，1 0 0 l 中 提出的一种有力的非单调推理形式由m c c a r t h y 在文献【1 0 1 】中进一步推广其 基本思想是：证明满足确定谓词的目标( o b j e c t ) 是唯一的，也即给定公理集瓦和 n 元谓词符号p p 在t 中的约束是考虑p 的扩充是极小的 ( i i ) 自认知( a u t o e p i s t e m i c ) 逻辑，这是r o b e r tm o o r e 在文献 7 7 ，9 5 9 t 的 基础上进一步研究的结果，借助模态算子工( 可以相信) ，m ( 相容相信) ( m 是，l ， 的缩写) 提出的例如，考虑：v ( z ) 孩子( 。) 有父母( 茹) ) 有父母( $ ) 解释为 “对任一个体茁，若嚣是孩子，且相容的相信z 有父母，则2 7 有父母 ( i i i ) 闭w o r l d 假设( c l o s e dw o r l da s s u m p t i o n ) ，这是最早的非单调推理形式 之一( r e i t e r l 9 7 8 ) ，指若理论w p p ，则得到叩，表示为：! 终 ( i v ) 缺省逻辑，这是r e i t e r 在1 9 8 0 年提出的，这一非单调形式是本