（逻辑学专业论文）回答集最优化逻辑程序研究.pdf

本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内 容外，本论文不包含任何其他个人或集体已经发表或撰写过 的作品成果。对本文的研究作出重要贡献的个人和集体，均 已在文中以明确方式标明。本人完全意识到本声明的法律结 果由本人承担。 学位论文作者签名：凑讫晦 日期：叫d 年舌月日。 本人完全了解中山大学有关保留、使用学位论文的规定，即： 学校有权保留学位论文并向国家主管部门或其指定机构送 交论文的电子版和纸质版，有权将学位论文用于非赢利目的 的少量复制并允许论文进入学校图书馆、院系资料室被查阅， 有权将学位论文的内容编入有关数据库进行检索，可以采用 复印、缩印或其他方法保存学位论文。 学位论文作者签名：葫孙鸟导师签名：丝 日期：珈加年f ) 月；日日期：加l d 年6 月弓日 回答集最优化逻辑程序研究 逻辑学 朱江峰 熊卫副教授 摘要 一个回答集最优化( a n s w e rs e to p t i m i z a t i o n ，以下简称a s o ) 逻 辑程序是一个二元组( p g e n ，p p 他f ) ，生成程序p g 。n 生成描绘可能解决 方案的回答集，偏好程序p p 陀f 表达使用者的偏好。p p 他f 中的偏好规则 构造出可能解决方案的一个偏好序列，用于比较p g e n 生成的回答集。 我们证明b r e w k a 的a s o 逻辑程序会出现不相关问题，找出不相关问 题的成因。为了消除不相关问题，我们提出新概念8 等价，以重新定 义偏好关系对回答集的满足度。相应地，我们定义了回答集的四种偏 好关系，并在此基础上构建出回答集的层级结构，提出获得最优解的 新方法。结合事例，我们在新的定义和技术的帮助下消除了不相关问 题。 关键词：逻辑程序回答集最优化等价性不可比性 o na n s w e rs e to p t i m i z a t i o np r o g r a m l o g i c z h u j i a n g f e n g x i o n gw e i a b s t r a c t a na n s w e rs e to p t i m i z a t i o n ( a s o ) p r o 猡r a mi sap a i r ( p g e n ，p p 他f ) t h e g e n e r a t i n gp r o g r a mp g e np r o d u c e sa n s w e r s e t sr e p r e s e n t i n gp o s s i b l e s o l u t i o n s t h ep r e f e r e n c ep r o g r a m p p r c fe x p r e s s e su s e rp r e f e r e n c e s i t i n d u c e sap r e f e r e n c er e l a t i o no nt h ea n s w e rs e t so f p g 蚰b a s e d o nt h e d e g r e et ow h i c hr u l e sa r es a t i s f i e d w ep r o o f t h a tb r e w k a sa s o p r o g r a mi n d u c e si r r e l e v a n c ep r o b l e m a n dw ef i n do u t t h er e a s o nf o ri t i no r d e rt oe l i m i n a t ei r r e l e v a n c ep m b l e m ，w ep r o p o s et h en e w c o n c e p t 一e q u i v a l e n c e t or e d e f i n es a t i s f a c t i o nd e g r e eo fap r e f i e r e n c em l ei na n a n s w e rs e t c o r r e s p o n d i n g l y ，w ed e f i n ef o u r 妙p e so f p r e f e r e n c er e l a t i o n b e t w e e nm oa n s w e rs e t s a n dw eb u i l dah i e r a r c h ys t r u c t u r eo nt h e a n s w e rs e t st of i n do u tan e w w a y t oo b t a i nt h eo p t i m a lm o d e l w i t ht h e h e l po fn e w d e f i n i t i o no fs a t i s f a c t i o nd e g r e ea n dn e w t e c h n i q u e st oo b t a i n o p t i m a lm o d e l ，w ed e m o n s t r a t et h a ti 1 1 r e l e v a n c ep r o b l e mi se l i m i n a t e d k e y w o r d s ：l o g i cp r o g r a m ，a n s w e rs e to p t i m i z a t i o n ， e q u l v a l e n c v 1 n c o m d a r a b l l l t v r lr 4 目录 弓i 言6 第1 章a s o 逻辑程序8 1 1 扩充逻辑程序和回答集语义8 1 2a s o 逻辑程序9 1 3a s o 逻辑程序的特点和优点1 4 第2 章不相关问题1 6 2 1 不相关问题1 6 2 2 例子l8 第3 章消除不相关问题2 0 3 1 出现不相关问题的原因2 0 3 2 等价和不相关21 3 3 回答集的四种偏好关系2 2 3 4 回答集的层级结构和最优解选择2 4 3 5 例子2 6 结语2 9 参考文献。3 0 中英文对照表一3 3 j 舌记：；z i 引言 逻辑程序是重要的知识表达和推理的工具。但是与经典逻辑相比，普通逻辑 程序并不允许我们直接处理不完全信息1 。为了克服这个局限，g e i f o n d 和l i f s c h i t z 在规则中加入经典否定“一 ，得到扩充逻辑程序和稳定模型语义( 1 9 8 8 ) ，接 着又提出了回答集语义( 1 9 9 0 ，1 9 9 1 ) 。此后十多年的时间里，带稳定模型语义 的逻辑程序成为了陈述性的逻辑程序技术应用的新范式( m a r e ka n dt r u s z c z y l l s k ， 1 9 9 9 ；n i e m e 吼1 9 9 9 ) 。为了郑重其事，l i f s c h i t z ( 1 9 9 9 ) 首次提出了“回答集逻 辑程序 的说法。使用回答集逻辑程序解决一个问题，就是通过设计一个逻辑程 序，使得这个程序的稳定模型能提供问题的答案。回答集逻辑程序被广泛应用到 解决诸如组合论、图论和规划问题( b u c c a f u r r i ，l e o n ea n dr u l l o ，1 9 9 7 ；e i t e r ， g o t t i o ba n dm a n n i l a ，1 9 9 7 ；l i f 夸c h i t z ，1 9 9 9 ，2 0 0 2 ；m a r e ka n dt r u s z c z y s k i ，1 9 9 9 ； n i e m e i 荟，1 9 9 9 ；s o na n dp o n t e i ，2 0 0 4 ) o 回答集逻辑程序成为一个流行的知识表达工具，有四方面的原因( b r e w k a ， n i e m e l 各a n dt r u s z c z y l l s k i ，2 0 0 3 ) ： 1 ) 逻辑程序有足够强的表达力来处理人工智能中大部分的知识表达问题。 尤其是，在逻辑程序的规则体中可以存在弱否定2 ，这使得逻辑程序可以表达可 废止的信息。 2 ) 对于行动、规划、诊断、信念修正和产品配置等的推理的大部分问题， 逻辑程序都能给出让人满意的解决方案( l i f s c h i t z ，2 0 0 2 ；s o i n i n e n ，2 0 0 0 ；b a r a i ， 2 0 0 3 ) 。 1 在一个致的经典理论中，一个句子要么是可证明的，要么是可反驳的，要么是不可判定的。而在一个 逻辑程序中，对一个基本询问的回答要么是肯定的，要么是否定的由于普通逻辑程序的陈述性语义对所 有谓词自动应用封闭世界假设，并假设每一个不由程序得出的原子公式的真值为假。而逻辑程序对不成功 的查询都赋值为假。对于在经典理论中表达不完全信息的不可判定的句子，在逻辑程序中没有对应物。n e w g e n e r a t l o nc o m p u t j n g ，9 1 1 9 9 1 ) 3 6 5 - 3 6 6 ，0 h m s h a ，l t d a n ds p r i n g e r - v e r i a g 2 弱否定，n e g a t i o n a s f a i u r e ，简称n a f ，是逻辑程序设计中的一个非单调推理规则如果未能得到p ，那 么得到n o tp ，也就足说，假定p 1 i 成立。丝巳；碰宝凸：蜘k i 鳇垡匦q 【臣剑j z 丛壁g a ! 瞳凸i 剑! 女监，2 0 1 0 0 2 - 2 4 6 3 ) 从编程语义的直观性上看，回答集的语义是十分直观的，能避免p r o l o g 的陷阱。例如，回答集的语义独立于规则的书写顺序，因此能正确处理循环。 4 ) 逻辑程序的语法允许快速执行，并且研究者发展了一系列高效的求解系 统。其中最著名的有s m o d e i s ( n i e m e i 百a n ds i m o n s ，1 9 9 7 ) 和d l v ( e i t e r ，l e o n e ， m a t e i s ，p f e i f e ra n ds c a r c e o ，1 9 9 8 ) 。 为了提高逻辑程序在知识表达中的易用性，研究者们还对基本的形式化进行 了扩充。其中广为人知的例如有带基数和权值约束的逻辑程序( s i m o n s ，n i e m e i 置 a n ds o i n i n e n ，2 0 0 2 )。 逻辑系统还在偏好的表达和推理领域中得到广泛应用。研究者们对程序规则 间的偏好( s c h a u ba n dw a n 2 0 0 1 ) ，程序字母间的偏好( s a k a m aa n di n o u e ，2 0 0 0 ) 进行了研究。另外，b r e w k a ( 2 0 0 2 ) 提出的l p o d ( l o g i cp r o g r a m m i n g w i t ho r d e r e d d i s j u n c t j o n ，带有序析取的逻辑程序) 与本文讨论的重点a s o 逻辑程序( b r e w k a ， n i e m e i 若a n dt r u s z c z y f l s k ，2 0 0 3 ) 是一脉相承的。 a s o 逻辑程序结合了回答集逻辑程序和定性最优解技术，主要应用于偏好的 表达和推理。由于a s o 逻辑程序采取了独特的技术手段，它能把一个复杂的任 务分成两个相互独立的子任务来处理偏好问题，使回答集的偏好序列的获得变得 更容易。但是，我们发现b r e w k a 的a s o 逻辑程序存在不相关问题，一个个体在 使用a s o 逻辑程序的时候可能会得到违反直观的结果。所谓不相关问题就是， 如果一个最大满足偏好规则的文字集和一个跟偏好规则毫不相关的文字集都是 一个a s o 逻辑程序的回答集，那么这两个回答集都是最优解。把毫不相关的文 字集作为最优解，这个结果并不令人满意。 我们在第1 章将介绍b r e w k a 的a s o 逻辑程序的技术细节。在第二章将证明 不相关问题的普遍存在性，并在第三章探讨不相关问题的成因和解决方法。 7 第1 章a s o 逻辑程序 a s o 逻辑程序结合了回答集逻辑程序和定性最优化技术。我们首先介绍回答 集逻辑程序，然后介绍a s o 逻辑程序的语法和语义，最后讨论a s o 逻辑程序的 特点和优点。 1 1 扩充逻辑程序和回答集语义 一个普通逻辑程序是一组具有以下形式的规则r 的有限集： a 0 一a 1 ，a m ，n o ta m + l ，n o ta n ， 其中n m 0 ，每一个a i 是一个原子公式，“n o t ”是弱否定，箭头左边称为规 则头，记作h e a d ( r ) ，右边称为规则体，记作b o d y ( r ) 。 g e i f o n d 和l i f s c h i t z ( 1 9 9 0 ，1 9 9 1 ) 指出，与经典逻辑相比，普通逻辑程序并 不允许我们直接处理不完全信息。为了克服这个局限，他们在规则中引入经典否 定“一 ，得到扩充逻辑程序，并提出回答集语义。 定义1 1 令a = a 1 一，a 。 是一个原子公式集。我们给出一个文字i 的归纳定 义： ( i ) a i 是文字，其中i 1 ； ( i i ) 一a i 是文字，其中i 1 ； ( j j j )所有的文字都由( j ) 和( j j ) 生成。口 定义1 2 一个扩充逻辑程序p 是一组具有以下形式的规则的有限集： l o i l ，i m ，n o ti m 儿，n o ti n ， ( 1 ) 其中n m 0 ，每一个i i 是一个文字。 口 8 我们注意到，扩充逻辑程序的原子是文字，文字能明确表达否定信息。在扩 充逻辑程序的语言中，我们能区分一个查询失败是在查询不成功的意义上的查询 失败，还是在这个查询的否定查询成功的意义上的查询失败。 扩充逻辑程序的语义是普通逻辑程序的稳定模型语义( g e i f o n da n dl f s c h i t z ， 1 9 8 8 ) 的扩充。一个普通逻辑程序的稳定模型语义定义一组原子公式集是这个逻 辑程序的稳定模型。一个一致的逻辑程序恰好有一个稳定模型，一个查询a 是否 属于稳定模型，决定了查询a 的回答是“是 还是“否 。对于一个扩充的逻辑 程序，我们定义一组文字集是这个逻辑程序的回答集。 定义1 3 我们通过两个步骤得到p 的回答集： 步骤一，令p 不包含变量和“n o t ”，l i t 是所有文字的集合。p 的回答集是 l i t 的最小子集s ，使得( i ) 对于p 在的任意规则l o i “，i m ，如果1 1 ，i m s ，那么i o s ；( i i ) 如果s 含有一组互补文字3 ，那么s = l i t 。 步骤二，令p 不包含变量。对任意的scl i t 。p 5 是一个回答集逻辑程序，我 们通过以下方法得到p 5 ：( i ) 从p 中删除每一个规则r ，如果l s ，且n o ti 出 现在b o d y ( r ) 中；( i i ) 删除剩余的规则中在规则头中出现的所有形如n o tl 的公式。 显然，p 5 不包含“n o t ，我们可以通过步骤一得到p 5 的回答集。如果这个回答 集跟s 是一致的，那么我们说s 是p 的回答集。口 1 2a s 0 逻辑程序 一个a s o 逻辑程序由两部分组成，生成程序p g e n 和偏好程序p p r e f 。p g e n 生成 表示可能解决方案的回答集。p p r e f 表达使用者的偏好。我们通过比较p g 鲫生成的 回答集对偏好规则的满足度向量得到回答集之间的偏好关系。 3i ，一i 是一组互补文字 9 1 2 1 生成程序p g e n p g 。可以是任意类型的逻辑程序。为了使表达更简洁、更可读，我们采用了 基数约束( s i m o n s ，n i e m e i i ia n ds o i n i n e n ，2 0 0 2 ) 定义p g 。n 。基数约束是权值约束 的特例。 定义1 4 一个权值约束c 具有以下形式： k i l = w 1 ，i m = w m s 比 ( 2 ) 其中m 0 ，每一个i 。是一个文字，w 。是对应的权值，l 和眇是约束的下界和上 界。权值、上下界都是实数。 口 定义1 s 一个权值约束规则程序是具有以下形式的规则的有限集： c o c 1 ，c n ， ( 3 ) 其中每一个c t 都是一个权值约束。 口 定义1 6 一个文字集s 满足一个权值约束c ，记作s c ，当且仅当kw ( c ， s ) s 比其中w ( c ，s ) = l t s w i ，i 1 一，m 。 口 定义1 7 我们说一个权值约束c 是一个基数约束，如果每一个w l = 1 ，其中 1sism ，也就是说k i l = 1 ，i m = 1 ) s 比简记为： l 1 1 ，i m ) 比 ( 4 )口 由定义1 6 和1 7 我们可以得到，一个文字集满足一个形式( 4 ) 的规则， 如果这个文字集最少包含z ，个且最多包含协个规则中的文字。 1 2 2 偏好程序p p r e f 偏好规则的规则头是布尔组合的偏好序列。一个原子公式集a 上的一个布尔 组合是由原子公式的合取“八 、析取“v 、经典否定“一”和弱否定“n o t ” 组成的公式，其中经典否定“一 只能出现在原子公式之前，弱否定“n o t 只 能出现在文字之前。我们可以给出基于文字集的布尔组合的定义。 定义1 8 令s = i l ，i 。) 是一个文字集。我们给出一个布尔组合b 的归纳定 义： ( i )i i 是一个布尔组合，其中i 1 ； ( 1 j ) n o ti i 是一个布尔组合，其中i 1 ； ( i i i ) 令b 1 、b 2 是布尔组合，那么b 1 八b 2 是布尔组合； ( i v ) 令b 3 、b 4 是布尔组合，那么b 1vb 2 是布尔组合。 口 布尔组合可以表示选项存在的某种性质，不存在的某种性质( n o t ) ，性质 的合取( 八) ，性质的析取( v ) 。 定义1 9s 是一个文字集。一个布尔组合b 在s 中满足，记作s b ，那么： s i ( i 是文字) i 仟 i s s n o t1仟 i 萑s s b 1 人b 2 i f f s b 1a n ds b 2 s 净b 1 vb 2i 仟sbb lo rsbb 2口 定义1 1 0 令a 是一个原子公式集。a 上的一个偏好程序p p ，e f 是具有以下形 式的规则的有限集： b l b k 1 1 ，i m ，n o ti m 礼，n o ti n ， ( 5 ) 其中n m 芝o ，每一个i i 是一个文字，每一个b i 是一个布尔组合。 口 ( 5 ) 的直观含义是，如果一个回答集s 含有1 1 ，l m ，并且不包含i m + “，i 。， 那么b l 优于b 2 ，b 2 优于b 3 如此类推。 1 2 - 3 最优化程序( p g e n ，p p r e f ) 定义1 1 1 一个a s o 逻辑程序是一个二元组( p 卵。，p p r e f ) ，p g e 。是一个回答 集逻辑程序，称为生成程序，p p 耐是一个偏好程序。 口 1 1 上文我们已经给出了生成程序p g 。的一种形式定义和偏好程序p p r e f 的定义； 关键问题是：p p r e f 是如何决定p g 。的回答集的偏好序列的? b r e w k a 首先定义p p 他f 的规则r i 对p g 朝的回答集s j 的满足度和关于满足度的预序，从而生成每一个s j 在p 。陀f 中的满足度向量，然后通过比较满足度向量得到p g e n 的回答集的偏好序列， 最后给出最优化模型的定义，从而得到最优解。 定义1 1 2s 是一个文字集。一个形式( 5 ) 的规则r 在s 中满足，记作s r ， 如果： ( i ) s 卜b o d y ( r ) ，即b o d y ( r ) 在s 中满足，也就是说每一个i 1 ，m ) ， s i i ，每一个j m + 1 ，n ) ，s n o tl j ；并且 ( i i ) s h e a d ( r ) ，即h e a d ( r ) 在s 中满足，也就是说至少有一个b i ，s b i 。 r 在s 中不满足，记作s 垮r ，如果： ( i ) s 垮b o d y ( r ) ，即b o d y ( r ) 在s 中不满足，也就是说要么存在一个i 1 ，m ) ，s 峰i i ，要么存在一个j m + 1 ，n ) ，s 净i j ；或者 ( i i ) s 垮h e a d ( r ) ，即h e a d ( r ) 在s 不中满足，也就是说没有一个b i 使得s b i 。 口 定义1 1 3 一个形式( 5 ) 的规则r 对一个文字集s 的满足度v s ( r ) ： ( i ) v s ( r ) = m i n ：s b i ，如果s 卜r ； ( i i ) v s ( r ) = i ，如果s 卢r 。 口 也就是说，如果一个规则在一个回答集中满足，那么这个规则对这个回答集的满 足度是最先得到满足的性质的序数；如果一个规则在一个回答集中不满足，我们 认为这个规则与这个回答集是不相关的，赋予其满足度i 。 特别地，b r e w k a 、n l e m e 惜和t r u s z c z y s k i ( 2 0 0 3 ) 规定，满足度i 和1 是 同样好的( i 1 ，且1 i ) ，并且优于其他满足度。这样我们可以得到关 于满足度的偏序4 ，如图1 1 ： 图1 1 ：关于满足度的偏序 4 一个集合p 上的二元关系是偏序，如果它是自反的、传递的和反对称的，也就是说，对p 中任意元素a 、 b 、c 。我们有l ( 1 ) 自反性。a a ；( 2 ) 传递性。如果a b 且b c 。那么a c ；( 3 ) 反对称性a b 且b a ，蕴涵a - b 。b 丛乜；碰皇n ：蠼幽鳇璺鱼q “丛凶z 皇q 型金 2 0 1 0 - 0 5 - 1 4 1 2 容易地，我们可以证明也是所有满足度的集合上的一个全序。对于任意满 足度v l ，v 2 ，要么v l v 2 ，要么v 2 v l 。 定义1 1 4 令偏好程序p p r e f = r l ，r n ，p 辨。的回答集s 的满足度向量v s = ( v s ( r 1 ) ，v s ( r n ) ) 。 口 定义1 1 s 令s 和s 是两个回答集。s 不次于s ，记作s s ，如果v s ， 也就是说，v s ( r ) v s ，( r i ) ，对于每一个i 1 一，n ) 。s 优于s ，记作s s ， 如果v s v s ，并且存在i 1 ，n ，v s ( r i ) v s ，( r i ) 。 口 定义1 1 6 一个文字集s 是一个a s o 逻辑程序( p g e n ，p p r e f ) 的最优模型，如 果s 是p g 。的一个回答集，并且不存在p g 。的其他回答集s ，使得s s 。 口 1 2 4 例子 我们通过一个简单的例子看a s o 逻辑程序是如何运作的。 例1 个体a 从红、蓝、绿三种颜色中选取一种颜色作为天花，红色与蓝色 相比，a 更喜欢红色。 口 根据上述情况，我们得到一个a s o 逻辑程序( p 鹊。，p p r e f ) ，p g e n = 1 r e d ，b l u e ， g r e e n ) 1 ，p p r e f = r ：r e d b i u e 一) 。p g e n 有三个回答集，s 1 = r e d ，s 2 = b i u e ) ， s 3 = g r e e n 。它们的满足度向量分别为：v s ，( r ) = ( 1 ) ，v s 2 ( r ) = ( 2 ) ， v s 3 ( r ) = ( i ) 。我们可以得到一个偏好序列，如图1 2 ： 图1 2 ：三种颜色的偏好序列 四。口 回 四 根据定义1 1 6 ，s 1 ，s 3 都是( p 鹊。，p p 陀f ) 的最优解。也就是说，对a 而言，选择 红色或者绿色都是最优选择。 1 3a s o 逻辑程序的特点和优点 引言中提及的其他应用与偏好表达和推理的逻辑程序，都是在单一的逻辑程 序中描述规则或者文字之间的偏好关系。与之相比，a s o 逻辑程序的最大特点是 使用两个不同的逻辑程序，p 鲫生成表示可能解决方案的回答集，p p 他f 表达使用 者的偏好。另外，采用布尔组合来描述可能解决方案的某些性质，使得a s o 逻 辑程序的使用者可以通过建立不同性质之间的偏好关系来获得不同可能解决方 案的偏好序列。 在实际应用中，什么是可能的往往由客观条件决定，例如可用资源、环境 约束、产品在设计和工程学学上的限制等等：至于偏爱什么、优先选择什么，与 客观条件是相互独立的，而是由不同的用户、顾客等等决定的。因此，回答集的 生成和比较相分离主要有两个优点：其一，比较回答集的方法独立于生成程序 p 鲫的类型，p 黔。可以是任意类型的逻辑程序，只要定义清晰、明确，我们可以 得到所有可能解决方案：其二，p p ，e f 中的偏好规则独立于p g e 。，偏好处理的任务 被细分为回答集的生成和比较两个相互独立的子任务，这使我们能更容易获得可 能解决方案的偏好序列。 然而，回答集的生成和比较相分离也带来了一个新课题：如何处理偏好规则 与回答集不相关的情况? p g e n 罗列了所有表达可能解决方案的回答集，而在实际 1 4 应用中，有些回答集和偏好规则是不相关的，严重影响到回答集的比较。b r e w k a 等( 2 0 0 3 ) 认为，如果不能证明满足度i 优于1 且不能证明1 优于i ，那么规定 满足度i 不次于1 且1 不次于i ，即i 1 ，且1 i ，其中是一个偏序。 这样得到了满足度集合上的全序，使我们能够更容易得到最优解。但是不能证明 满足度i 优于1 且不能证明1 优于i ，并不一定意味着1 不次于i 且i 不次于1 ， 而且满足度之间不一定存在偏序关系。根据b o o t ( 2 0 0 7 ) 的3 n t 原则，不能证 明满足度i 优于真满足度5 n ，不能证明n 优于i ，且不能证明i 与n 是无差别的， 那么i 与n 是不可比的。我们将在第2 章和第3 章论证排除了不相关满足度i 的 不可比性所带来的问题，并探讨解决问题的方法。 5 真满足度指所有以自然数赋值的满足度 第2 章不相关问题 在这一章，我们将证明b r e w k a 的a s o 逻辑程序会导致不相关问题，并通过 例子说明不相关问题给我们带来的影响。 2 1 不相关问题 上文提到，回答集的生成和比较相分离也带来了一个新课题：如何处理偏好 规则与回答集不相关的情况? b r e w k a 规定满足度i 与1 是等价的且优于其他满 足度，这样做使我们避免了不相关即不可比的情况，得到了一个完整的关于满足 度的预序，从而更容易得到最优解。 但是，从1 1 4 我们可以观察到，规定了满足度i 与1 是等价的且优于其他 满足度之后，一个与偏好规则毫不相关的回答集一定是最优解。这与我们制定规 则的初衷是相违背的：一般地，我们希望通过规则找到可选行为的偏好序列，并 选出最大满足偏好关系的回答集作为最优解。 就例1 而言，个体a 认为红色优于蓝色，绿色与a 的偏好是不相关的。对 此a 可以有两种观点：其一，如果一个选项与自己的偏好是不相关，那么这个选 项跟其他选项是不可比的；其二，不相关的回答集没有违背自己的偏好，因而不 相关的回答集优于违背偏好的回答集。就观点一而言，绿色跟红色和蓝色都是不 可比的，绿色仅仅是a 的一个可选行为，而红色才是符合a 的偏好的可选行为。 因此我们认为a 的最优选择只有红色。就观点二而言，选择绿色没有违背偏好， 但也没有满足偏好，认为绿色与红色同样好是不合理的。因此我们依然认为a 的最优选择只有红色。 1 6 对于不相关的情况，a s o 逻辑程序得到的结果与我们的直观不符：一个与偏 好规则毫不相关的回答集一定是最优解。我们称这个问题为不相关问题。接下来 我们证明不相关问题在a s o 逻辑程序中是普遍存在的。 令( s 1 ，s m ) 6 ， ，r n ) ) 是一个a s o 逻辑程序。 定义2 1s 是一个不相关回答集，记作l r r ，如果每一个j 1 一，nl ， v s ( r j ) = l 。s 是一个极大满足回答集，记作m a x ，如果每一个j 1 ，n ) ， v s ( r j ) = 1 。 口 定理2 1 一个极大满足回答集m a x ，如果m a x s “，s m ，那么m a x 是 最优解。 证明根据定义2 1 ，v m 。= ( 1 ，1 ) 。令s s “，s m ，v s = ( v 1 ， v n ) 。根据定义1 1 5 ，1 v j ，即v m 。( r i ) v s ( r ) ，v m 毅v s ，m a x s 。s 是任意回答集，根据定义1 1 6 ，不存在其他回答集s ，使得s m a x ，所以m a 是最优解。 口 定义2 2 两个文字集s ，s s “，s m ) 。我们说s 与s 是i 等价的，如果 对于每一个j 1 ，n ，j i ，v s ( r j ) = v s ( r j ) 。 口 引理2 2 如果m a 与s 是i 等价的，那么m a x 与s 是同样好的。 证明v m 。= ( 1 一，1 ) ，v s = ( 1 ，i ，1 ) ，根据定义1 1 5 ，m a s ， s m a x ，m a x = s 。口 定理2 3 一个不相关回答集i r r ，如果l r r s b ，s m ) ，那么i r r 是最优解。 证明令s o ，s 1 ，s “是一组文字序列，其中s o = m a x ，且s 与s h 是i 等价 的，v s l ( r i ) = i 。如果s n s “，s m ，那么s “是i r r 。根据引理2 2 ，i r r = m a x 。 根据定义1 1 6 ，如果f r r s 1 ，s m ，那么l r r 是最优解。 口 定理2 1 和定理2 3 表明，只要m a x 和i r r 都是一个a s o 逻辑程序的回答集， 那么它们都是最优解。 6 为了讨论的方便，我们直接给出p 面生成的回答集的集合 轧，s - - ，以下类同 1 7 _ _ _ 2 2 例子 我们借用经典的晚餐例子( b r e w k a ，2 0 0 2 ；b r e w k a ，n i e m e i 各a n dt r u s z c z y s k ， 2 0 0 3 ) 来进一步说明不相关问题对我们的影响。 例2 个体a 要从菜单中选择主菜、饮品和甜品。主菜有鱼肉和牛肉，饮品 有红酒、白酒和啤酒，甜品有馅饼和雪糕。每一个类别仅选择一个品种。a 只有 一个要求，如果主菜选择鱼肉，那么在饮品的选择上最优是白酒，其次红酒，再 次啤酒。 口 显然，对于a 来说最优选择是鱼肉、白酒、馅饼( 或者雪糕) 。然而如果我 们采用a s o 逻辑程序来处理这个问题，会得到另一个结果。 根据上述情况，我们得到个a s o 逻辑程序( p g 。，p p r e f ) 。p g e 。= 1 f i s h ，b e e f ) 1 ， 1 r e d ，w h i t e ，b e e r 1 ，1 p 峨i c e c r e a m ) 1 ) ，p p r e f = r ：w h i t e r e d b e e r f i s h 。 p g 。有1 2 个回答集： s 1 = f i s h ，r e d ，p i e ，s 2 = f i s h ，r e d ，i c e - c r e a m ) ， s 3 = 饷s h ，w h i t e ，p i e ) ，s 4 = s h ，w h i t e ，i c e c r e a m ， s s = f i s h ，b e e r ，p i e ，s 6 = f i s h ，b e e r ，i c e - c r e a m ) ， s 7 = b e e cr e d ，p i e ，s 8 = b e e cr e d ，i c e - c r e a m ) ， s 9 = b e e cw h i t e ，p i e ，s 1 0 = b e e cw h i t e ，j c e - c r e a m ) ， s 1 i = b e e cb e e r ，p i e ，s 1 2 = b e e cb e e r ，i c e - c r e a m 。 满足度向量为( 1 ) 的回答集有2 个：s 3 和s 4 ； 满足度向量为( i ) 的回答集有6 个：s 7 、s 8 、s 9 、s l o 、s 1 1 、s 1 2 ； 满足度向量为( 2 ) 的回答集有2 个：s 1 、s 2 ； 满足度向量为( 3 ) 的回答集有2 个：s s 、s 6 。 根据定理2 1 和定理2 3 ，s 3 、s 4 、s 7 、s 8 、s 9 、s l o 、s l l 、s 1 2 都是a 的最优 解。 一个a s o 逻辑程序( p g e 。，p p 陀f ) ，如果m a x 和i r r 都是它的回答集，那么根 据定理2 1 和定理2 3 ，m a 和i r r 都是最优解。也就是说，一个满足所有要求的 解决方案和一个跟要求毫不相关的可能解决方案，都是最优解决方案。下一章我 们将讨论出现不相关问题的原因和消除不相关问题的方法。 第3 章消除不相关问题 在这一章，我们首先探讨b r e w k a 的a s o 逻辑程序出现不相关问题的原因； 其次提出新概念e 等价，完善了b r e w k a 对满足度的定义；接着探讨了回答集的 四种偏好关系；然后根据回答集的偏好关系构建起回答集的层次结构，并提出获 得最优解的新方法；最后我们回顾两个例子，看看不相关问题是如何被消除的。 3 1 出现不相关问题的原因 在a s o 逻辑程序中，回答集的生成和比较是相分离的。b r e w k a 提出满足度 的概念来建立生成程序p g 。和偏好程序p p 陀f 的关系。他指出，一个回答集s 与偏 好规则r 有三种关系： ( i ) s r ： ( i i )b o d y ( r ) 在s 中满足，但h e a d ( r ) 在s 中不满足，即没有一个b i 在s 中 满足； ( i i i ) b o d y ( r ) 在s 中不满足。 如果s 是一个a s o 逻辑程序( p g 。，p p 陀f ) 的回答集，相应地我们可以得到 一个偏好规则r 对s 的满足度。情况( i ) 我们可以顺利得到真满足度v s ( r ) ；( i i ) ( i i i ) 是两种不同的不相关情况，在第1 章中我们统一令v s ( r ) = i 。然而，这两 种情况是有区别的。 在情况( i i ) 中，b o d y ( r ) 在s 中满足，也就是说r 已被激活，但是我们无法 赋予v s i r ) 一个真满足度，是由于没有一个b - 在s 中满足。在前提条件达到的情况 下，我们关于偏好的信息是不完备的。这类似于例1 的情况，个体a 认为红色 优于蓝色，绿色与a 的偏好是不相关的。我们已经讨论过选择红色是最优解，蓝 色是退一步的选择。选择绿色也是满足前提条件的可能解决方案之一( 在例1 中前提条件缺省) ，选择绿色没有违背偏好，但也没有满足偏好；在选择红色依 然是可能解决方案的时候，我们不会选择绿色；但如果由于客观条件的改变，我 们不能选择红色的时候，我们会选择绿色，而不会选择蓝色。因此，即使a 没有 明确提出含有绿色的偏好序列，但红色 绿色 蓝色这个偏好序列是被应用 到a 的缺省推理中的。 至于情况( i i i ) ，b o d y ( r ) 在s 中不满足，也就是说r 未被激活，那么无论h e a d ( r ) 在s 在满足还是不满足，我们都将不会使用规则r 。规则r 与s 是不相关的，r 不决定s 的满足度。这类似于例2 的情况，个体a 只要求在有鱼肉的情况下白酒 是最优选择。那么偏好规则在含有牛肉的所有回答集中都不满足。我们无法得到 这些回答集的满足度向量，我们认为这些回答集与含有鱼肉的回答集是不可比的。 对于情况( i i ) 、( ) ，b r e w k a 统一令v s ( r ) = i ，且规定满足度i 与1 是同 样好的且优于其他满足度。我们可以看到，这种不加区别的处理方法是不合理的， 情况( i i ) 中满足度被放大，一些在缺省推理中并非是最优的选项被认为是最优 解之一；情况( i i i ) 中，一些不可比的情况被认为是可比的。实际上，b r e w k a 认为关于满足度的二元关系“”是一个偏序，不存在两个满足度是不可比的情 况，因此他规定i 与1 是同样好的并且优于其他满足度。这导致了不相关问题。 我们已经找到问题的症结所在，只要对症下药问题就能迎刃而解。我们需要 对情况( i l ) 和情况( i i i ) 区别对待，为这两种情况寻找合适的满足度赋值，对 关于满足度的二元关系重新定义，并对整个最优化程序进行重建。 3 2e 等价和不相关 定义3 1r ：b 1 b k l ，i m ，n o ti m 灿，n o ti n 是一个偏好规则。r 对一个文字集s 的满足度v s ( r ) ： ( i ) v s ( r ) = m i n ：s b i ，如果sbr 。 ( i i ) 咐( r ) = 1 + ，其中是一个接近于o 的正数，如果b o d y ( r ) 在s 中满 足，但是h e a d ( r ) 在s 中不满足。这时我们说v s ，( r ) 与v s ( r ) 是一等价的。 2 ， ( i i i ) v s ( r ) = i ，如果h e a d ( r ) 在s 在不满足，也就是说存在i 1 ，m ) ， s 卜n o ti l ，或者存在j m + 1 ，n ) ，s i j 。口 正如我们在3 1 中讨论的，对于前提条件满足但可能解决方案的某些性质不 在我们的偏好序列之中，我们认为这些性质仅次于最优性质，而优于比其他性质。 我们用e 一等价来表达这个意思。而对于前提条件不满足的情况，我们认为偏好 规则与回答集是不相关的，因此我们规定i 与其他满足度是不可比的。 这样我们得到含有一等价的满足度预序，如图3 1 ： 图3 1 ：含有一等价的满足度预序 日 定义3 2 令s 与s 是两个文字集，v s ( r ) i ，v s ，( r ) i ： ( i ) v s ( r ) 优于v s ，( r ) ，记作v s ( r ) v s ，( r ) ，如果v s ( r ) o ； ( i i ) c h ( o ) = o 是理性禁止的，即不理性的，如果o o ； ( i i i ) c h ( 0 ) = o 是理性无差别的，如果o = o ； ( i v ) c h ( 0 ) = o 是理性不可解决的，如果o o 不是真的，o o 不是 真的，o = o 不是真的，我们说。与o 是不可比的9 。 口 ( i ) ( i i ) ( i i i ) 三种情形下我们都可以在理性指导下作出选择。但在情况( i v ) 下，两个选项是不可比的，但是我们依然可以作出选择。我采用b o o t ( 2 0 0 9 ，