（计算机科学与技术专业论文）扩展的加权约束逻辑程序及其在产品配置中的应用.pdf

j，i 独创性声明 删i iiii i iii ii i ii iilit 、t17 8 7 7 12 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：鸯醚导师签名：墨= = 主查日期：二堡垒兰型 摘要 摘要 当前，逻辑程序设计已经成为人工智能领域知识表示和推理的一种重要工具。 其中回答集编程是一种描述性的问题解决框架，是国际上一个非常活跃的研究方 向。加权约束逻辑程序是回答集程序的一种重要形式。 s o i n i n e n 等人提出了配置规则语言c r l 和加权约束逻辑程序语言，并将其 应用于产品配置问题。但该方法具有一定的局限性，比如它无法描述多约束可选 的情况。因此，本文在加权约束逻辑程序的基础上，提出了一种新的扩展的加权 约束逻辑程序语言，并给出了其稳定模型语义。新程序将规则的头部扩展为析取 约束的形式，进一步增强了知识描述和推理的能力，语法更加丰富，应用范围更 加广泛，但计算复杂度并未增加。同时，本文以电脑配置为例，说明了新语言在 产品配置问题中的应用。 进一步的，产品配置问题以客户需求为主要的约束条件。但是由于领域知识 的专业性，客户需求极有可能出现不合理情况，此时程序将无法给出合理的配置 解。针对这一问题，本文提出了一种加权定量的产品配置解优化方法。该方法可 以在客户需求不合理的情况下，通过对客户需求加权，求得满足最大客户需求权 重的配置解，作为对客户的反馈和建议。 最后，本文以s m o d e l s 为基础，实现了新的扩展的加权约束逻辑程序的稳定 模型语义求解系统。 关键词回答集语义；加权约束逻辑程序；产品配置；加权定量方法 北京工业大学_ 学硕士学位论文 a b s t l 8 c t a b s t r a c t c u r r e n t l y , l o g i cp r o g r a m m i n gh a sb e c o m ea l li m p o r t a n tt o o lo fk n o w l e d g e r e p r e s e n t a t i o na n dr e a s o n i n gi na i e s p e c i a l l y ，a n s w e rs e tp r o g r a m m i n g ，w h i c hi sa v e r ya c t i v ei n t e r n a t i o n a lr e s e a r c hd i r e c t i o n , i sad e c l a r a t i v ep r o b l e ms o l v i n gp a r a d i g m t h ew e i g h tc o n s t r a i n tl o g i cp r o g r a m m i n gi sa ni m p o r t a n tf o r m a to ft h ea s e s o i n i n e na n dh i sc o m p a n i o n sp r o p o s e dc o n f i g u r a t i o nr u l el a n g u a g ec r la n d w e i g h tc o n s t r a i n tl o g i cp r o g r a m m i n gl a n g u a g ea n da p p l yt op r o d u c tc o n f i g u r a t i o n h o w e v e r ，t h i sm e t h o dh a ss o m el i m i t a t i o n s f o re x a m p l e ，i tc a n td e s c r i b et h e s i t u a t i o no fo p t i o n a lm u l t i p l ec o n s t r a i n t s i nt h i st h e s i san e we x t e n d e dw e i g h t c o n s t r m n tl o g i cp r o g r a m m i n gl a n g u a g ei sp r o p o s e d ，w h i c hi sb a s e do nw e i g h t c o n s t r a i n tl o g i cp r o g r a m ，a n di t ss t a b l em o d e ls e m a n t i ci sd i s c u s s e s t h en e wl o g i c p r o g r a me x t e n d st h eh e a do fw e i g h tc o n s t r a i n tr u l ew i t hd i s j u n c t i v ec o n s t r m n t s i t e n h a n c e st h ea b i l i t yo fk n o w l e d g er e p r e s e n t a t i o na n dr e a s o n i n g ，a n dh a sd c h e rs y n t a x a n db r o a d e rr a n g eo fa p p l i c a t i o n s ；h o w e v e ri t s c o m p u t a t i o n a lc o m p l e x i t yi sn o t i n c r e a s i n g m e a n w h i l e ，w ei l l u s t r a t et h i sn e wl a n g u a g ei np r o d u c tc o n f i g u r a t i o nw i t h c o m p u t e rc o n f i g u r a t i o n f u r t h e r , c u s t o m e rr e q u i r e m e n t sa r et h em a i nc o n s t r a i n ti np r o d u c tc o n f i g u r a t i o n b e c a u s eo ft h ep r o f e s s i o n a l i s mo fd o m a i nk n o w l e d g e ，c u s t o m e rr e q u i r e m e n t sa r e h i g h l yl i k e l yu n r e a s o n a b l e ，t h e nv a l i ds o l u t i o nc a n n o tb eg o t t os o l v et h i sp r o b l e m ， a no p t i m i z e dm e t h o dw e i g h tf o re v e r yr e q u i r e m e n ti sp r o p o s e d t h i sm e t h o dc a ns e e k t h ec o n f i g u r a t i o ns o l u t i o nw h i c hc a nf u l f i l lt h em a x i m u md e m a n dw e i g h to fc u s t o m e r b yw e i g h t i n gt h ec u s t o m e rr e q u i r e m e n ti n t h ec a s eo fu n r e a s o n a b l ed e m a n do f c u s t o m e r t h i ss o l u t i o nc a nb eu s e da sf e e d b a c ka n ds u g g e s t i o nf o rc u s t o m e r a tl a s t ，as t a b l em o d e ls e m a n t i c ss o l v i n gs y s t e m ，s u p p o r t i n gt h ee x t e n d e dw e i g h t c o n s 仃a i n tl o g i cp r o g r a m ，i si m p l e m e n t e db a s e do ns o m d e l ss y s t e m k e y w o r d sa n s w e rs e ts e m a n t i c ；w e i g h t c o n s t r a i n t l o g i cp r o g r a m ；p r o d u c t c o n f i g u r a t i o n ；w e i g h tq u a n t i t a t i v em e t h o d 北京t 业大学t 学硕上学位论文 目录 目录 摘要i a b s t r a c t i i i 第l 章绪论1 1 1 研究背景1 1 2 发展现状3 1 2 1 理论研究。3 1 2 2 编程系统4 1 2 3 应用研究。5 1 3 研究内容。5 1 4 论文组织结构6 第2 章逻辑程序理论基础7 2 1 基础逻辑程序7 2 2h e r b r a n d 模型9 2 3 回答集语义l o 2 3 1 稳定模型语义。l l 2 3 2 回答集语义1 2 2 4 本章小结1 3 第3 章扩展的加权约束逻辑程序1 5 3 1 加权约束逻辑程序1 5 3 2 扩展的加权约束逻辑程序1 6 3 3 复杂度分析。1 8 3 4 扩展的加权约束逻辑程序在产品配置中的应用1 9 3 4 1 产品配置介绍。1 9 3 4 2 扩展的加权约束逻辑程序在产品配置问题中的应用2 1 3 5 本章小结2 3 第4 章基于加权定量方法的产品配置解优化2 5 4 1 相关领域研究2 5 4 1 1 加权约束逻辑程序的优化语句。2 5 4 1 2 基于a s o 程序的产品配置解的优化2 6 4 2 基于加权定量方法的产品配置解优化2 7 4 3 本章小结2 8 第5 章扩展的加权约束逻辑程序稳定模型语义实现2 9 5 1s m o d e l 系统。2 9 5 1 1s m o d e l 系统介绍2 9 5 1 2 文字类型3 0 5 1 3 规则类型3 2 5 1 4l p a r s e 命令行3 3 5 2 扩展的加权约束逻辑程序稳定模型语义的实现3 3 5 2 1 规则特性分析3 4 5 2 2 系统设计方案。3 4 v 北京工业大学工学硕士学位论文 5 3 本章小结3 9 结论4l 参考文献4 3 攻读硕士学位期间所发表的学术论文4 7 致谢。4 9 第1 章绪论 1 1 研究背景 第1 章绪论 逻辑程序【1 1 作为知识描述和推理的有力工具 2 1 ，发展于二十世纪七十年代初 期，以经典逻辑和自动定理证明，特别是r o b i n s o n 提出的归结原理为基础，并 随着p r o l o g 发展而逐渐繁荣起来。 1 9 7 2 年k o w a l s k i 提出“逻辑可以作为程序设计语言”的基本思想，并于1 9 7 4 年首次提出了“逻辑程序刀的概念。与传统的过程式( p r o c e d u r a l ) 编程语言不同， 逻辑程序是描述性的( d e c l a r a t i v e ) ，体现了k o w a l s k i 所一贯倡导的“算法= 逻辑+ 控制”的思想。 1 9 7 2 年，c o l m e r a u e r 与他的研究小组在马赛( m a r s e i l l e ) 大学实现了第一个逻 辑程序设计语言p m l o g ，后用f o r t r a n 语言改写，从而使逻辑程序迈向了可用 阶段。此时的p r o l o g 系统采用解释的方法，执行速度很慢，一度遭到人们的非 议。8 0 年代初期，d h dw a r r e n 提出w a r r e n 抽象机w a m ，采用编译的方法大 大提高了逻辑程序的时空效率。与最初的解释方法相比，编译的方法使p r o l o g 的执行速度提高了一个数量级之多，逻辑程序迈向了实用阶段【3 】。 与此同时，计算机领域的知识研究成果表明，经典逻辑不能完全满足人类思 维的推理方式。计算机领域主要涉及常识推理，具有很强的非单调性。非单调推 理的研究由此展开，相继出现了r e i t e r 的缺省逻辑 4 1 ( d e f a u l tl o g i c ) 、m c c a r t h y 的 限定论【5 ( c i r c u m s c r i p t i o n ) 、m o o r e 的非单调模态逻辑 6 , 7 ( n o n m o n o t o n i cm o d a l l o g i c ) 等非单调推理系统。 初期的逻辑程序是基于h o r n 子句的，称为h o r n 程序1 8 】，可看作一种谓词演 算子系统，具有单调性( m o n o t o n i c ) ，其s l d 消解也只能推导出肯定结果( p o s i t i v e c o n c l u s i o n ) ，所以不具备非单调推理的能力。也就是说，h o r n 程序不能应用于 计算机领域涉及的常识推理。 为了更好的适用于常识推理，逻辑程序也及时的引入了非单调推理因素。 1 9 7 8 年，k c l a r k 将“失败即否赳9 l ”( n e g a t i o na sf a i l u r e ) 概念引入逻辑程序， 并提出了c l a r k 完备化( c l a r kc o m p l e t i o n ) ，为包含否定知识的h o r n 程序建立了合 理的语义理论，使得逻辑程序与非单调推理的研究紧密结合了起来。逻辑程序的 研究进入非单调逻辑程序编程阶段【l o 】。 1 9 8 8 年，v a ng e l d e r 等人为非单调编程提出了另一种重要的模型语义 w e l l f o u n d e d 模型语义1 1 1 l ( w e l l f o u n d e dm o d e ls e m a n t i c s ) ；同年，m g e l f o n d 和 v l i f s c h i t z 共同提出了稳定模型语义【1 2 ( s t a b l em o d e ls e m a n t i c ) ，并于1 9 9 1 年扩 北京t 业大学工学硕士学位论文 展到包含逻辑否定( l o g i cn e g a t i o n ) 和缺省否定( d e f a u l tn e g a t i o n ) 的析取逻辑程序， 并更名为回答集语义【1 3 ( a n s w e rs e ts e m a n t i c s ) 。其中，逻辑否定也称为经典否定 ( c l a s s i c a ln e g a t i o n ，经典非) 或强否定( s t r o n gn e g a t i o n ) ，而缺省否定也称为弱否 定( w e a kn e g a t i o n ) ，表示为n a f f n e g a t i o na sf a i l u r e ，缺省非) 。 回答集语义一经提出，即成为国际上研究热点。 以此为核心，出现了大量的对回答集程序的扩展。这些扩展旨在增强程序的 形式化表达能力，或者为特定问题提供更方便的建模架构。s o i i l i n e n 于1 9 9 9 年 首次使用回答集程序【1 4 1 ( a n s w e rs e tp r o g r a m m i n g ，简称a s p ) 这一术语，应用回 答集语义解决说明性问题的方法发展为回答集框架【1 5 ( a n s w e rs e tp a r a d i g m ) 。它 相比传统的逻辑程序，具有如下优势： ( 1 ) a s p 是纯说明性语言，摆脱了传统逻辑程序的操作性问题，如子旬之间 的顺序问题等； ( 2 ) a s p 避免了类似非终止计算等问题； ( 3 ) a s p 语法简单，且具有高效的实现算法； ( 4 ) a s p 具有比命题逻辑和一阶逻辑更强的表达能力，可以方便的对因果关 系和传递闭包进行编码； ( 5 ) a s p 具有比其他知识描述语言更大的结构框架，为程序的系统化发展奠 定了基础。 经过数十年的发展，回答集框架已经成功应用于大型推理系统的建立，如数 据整合、产品配置、w e b 服务以及关于行为的推理等许多方面【1 6 1 。 本文关注逻辑程序，特别是回答集程序在产品配置领域的应用研究。 1 9 9 9 年s o i n i n e n 等人针对产品配置提出了一种配置规则语言c r l t l 4 1 ，该语 言很好的解决了产品配置中最普遍的知识形式选择；2 0 0 0 年，他和s i m o n s 一起对c r l 进行扩展，针对更多的实际问题，提出了更具实用价值的加权约束 逻辑程序【1 7 9 1 ，并在2 0 0 1 年基于产品配置问题的本体论定义给出了产品配置问 题的加权约束逻辑程序表示方法【2 0 1 。这种知识表示方法使配置的表示具有紧凑、 简单和积木式的特点，知识库维护方便，推理能力强，但也具有一定的局限性， 无法描述多约束可选的情况。例如，在个人电脑的产品配置中，如用户痴迷于网 络游戏，就要求p c 机安装独立显卡，或者集成显卡共享显存大于5 1 2 m ，这种 情况是无法使用一般的加权约束规则来描述的。 针对这一问题，本文旨在提出一种新的扩展的加权约束逻辑程序语言，使其 更加直观的描述上述多约束可选的知识类型，讨论其稳定模型语义( 回答集语义) 。 并进一步研究新程序在产品配置问题中的应用。 2 第1 章绪论 1 2 发展现状 回答集编程【2 1 l 是当前逻辑程序最活跃的研究领域。基本思想是：通过一个非 单调逻辑程序来描述特定问题，而该问题实例的解决方案则由程序预期的模型来 表示，这个模型被称为回答集或者稳定模型。其描述问题以及问题解决方案的基 本元素是规则和约束，而不是具体的算法。即给定一个问题实例i 和与其对应的 逻辑程序p 的表示形式，则逻辑程序p 的模型即可认为是问题i 的解决方案瞄2 4 1 。 这一思想为问题求解提供了一个新的模式，图形表示如图1 1 ： p r o b l e m m o d e l f s ile n c o d i n g ： e n c o d i n g ： i n s t a n c ei p r o g r a mp p r o g r a mps o l u t i o n ( , 图l l 用a s p 进行问题编码 f i g1 - 1e n c o d i n go fp r o b l e m si na s p 求解步骤： 1 、) 对问题实例i 进行编码，形成非单调逻辑程序p ，则p 的模型对应于i 的 解决方案； 2 ) 选择合适的a s p 求解器，计算p 的模型m ； 3 ) 根据m 得到i 的确切解决方案。 根据不同的实际问题，我们可能会计算不止一个模型，进而获得问题实例i 的多个，甚至全部解决方案。 这种特定的编程方式，非常适用于对涉及常识推理的问题进行建模，并自动 求解，已经成为逻辑编程与非单调推理领域的研究重点和热点。最具代表性的事 件是：19 9 9 年在美国得克萨斯州e ip a s o 举行的l p n m r 会议( s t hi n t e r n a t i o n a l c o n f e r e n c eo nl o g i cp r o g r a m m i n ga n dn o n - m o n o t o n i cr e a s o n i n g ) ，以及人工智能 ( a r t i f i c i a li n t e l l i g e n c e ) 杂志在2 0 0 2 年特发v 0 1 1 3 8 号专刊【2 佣于收录a s p 相关的 研究。2 0 0 1 年，一个专门的a s p 系列研讨会1 2 5 】成立；著名学者b a r a l 2 6 1 也专门 写书阐述并推广这一思想。2 0 0 8 年举行的i l p c ( i n t e r n a t i o n a ll o g i cp r o g r a m m i n g c o n f e r e n c e ) 会议专门开辟了一个环节，讨论稳定模型语义在逻辑程序领域的影响， 会议说明：回答集编程作为一个非常活跃的研究领域，尽管其优势和发展已经在 过去的几年中有了很多研究成功，仍然存在很多具有挑战性的研究问题。 下面本文将从理论研究、编程系统、应用研究三个方面介绍回答集编程的研 究现状【2 。 1 2 1 理论研究 回答集编程方面的理论研究，主要包括语法特性以及计算复杂性、偏好回答 3 北京工业大学1 = 学硕士学位论文 集语义( p r e f e r r e da n s w e rs e ts e m a n t i c s ) 、与非单调逻辑以及w e l l f o u n d e d 模型语 义等其它非单调逻辑编程理论的关系三个方面。 ( 1 ) 回答集逻辑程序的语法越来越复杂，例如可以表达约束【协1 9 1 、概率【2 8 , 2 9 1 、模 糊【3 0 , 3 1 】等概念的逻辑程序，主要是为了增强逻辑程序的表达能力，使之可以表达 更丰富的知识。例如，r i t e r 等提出的析取逻辑程序、s o i n i n e n 以产品配置为基础 提出的加权约束逻辑程序，王洁等提出了概率逻辑程序，以及模糊逻辑程序、有 序【1 0 】的逻辑程序、具有优先关系【3 2 1 的逻辑程序等。最近，开始出现了带有函数 符号【3 3 】的稳定模型语义的可判定性研究和原型实现。将函数符号作为一种建模结 构的思想也引起了更加广泛的关注。 计算复杂性与逻辑程序的语法特性有着密切关系，如不包含函数的h o r n 程 序的推理只可能是多项式的，而一旦需要完成非单调推理，很多问题已经成为 n p 难或者n p 完全问题。g g o t t l o b 和t e i t e r 在这方面研究甚多，文献【2 】系统 的介绍了他们的研究成果。 ( 2 ) 偏好( p r e f e r e n c e ) 处理已被认为是知识表示( k n o w l e d g er e p r e s e n t a t i o n ) 不可 或缺的能力。在关于规则的严格偏序优先级前提假设之下，g b r e w k a 和t e i t e r 提出了一种不同于经典回答集的偏好回答集语义；并提出了弱偏好回答集 ( w e a k l yp r e f e r r e da n s w e rs e t ) 以解决优先级与回答集条件之间的不一致问题。另 外，还存在基于有序析取 3 4 ( o r d e r e dd i s j u n c t i o n ) 的定义、基于继承层次 ( i n h e r i t a n c eh i e r a r c h y ) 的有序逻辑编程 3 5 , 3 6 ( o r d e r e dl o g i cp r o g r a m m i n g ) 定义等多 种偏好模型。 ( 3 ) 与非单调逻辑以及w e l l f o u n d e d 模型语义等其它非单调逻辑编程理论的 关系的研究一直在进行，但相对比较复杂。 1 2 2 编程系统 在回答集语义理论提出后，研究人员就开始寻找有效的回答集计算方法为编 程系统的实施奠定理论基础。同时，涌现出大量的回答集求解系统，这些系统为 问题建模提供了一系列的架构和要素，帮助用户以一种更加自然和易理解的方式 得到问题的形式化表示。 目前存在以下三种具有代表性的方法： ( 1 ) 在结合w f s 和极小h e r b r a n d 模型的基础上，n l e o n e 等d t l 人提出了种 用于产生析取逻辑程序回答集的递归算子以及相应算法，该算法与相应的回答集 检测算法结合即可完成回答集计算；该方法的代表系统是d l v 系统。 ( 2 ) 通过一种建立在基本约束规贝i j ( b a s i cc o n s t r a i n tr u l e ) 之上的回答集搜索算 法，e s i m o n s 有效地完成了加权约束程序的回答集计算；代表系统是e s i m o n s 等 人研发的s m o d e l s 系统。 4 第1 章绪论 ( 3 ) 林方真和赵玉亭【3 8 j 提出了一种利用可满足性求解器( s a ts o l v e r ) 完成回答 集计算的方法，代表系统是a s s a t ( a n s w e rs e t sb ys a ts o l v e r s ) 。该方法的核心 思想是：首先完成填充程序的c l a r k 完备并将结果转化为子句集，随后利用满足 性求解器完成回答集的产生与检测。只要能够确保可满足性求解器的可靠性和完 备性，该方法就是可靠和完备的。 随着a s p 理论的不断发展，及其应用的不断扩展，要想将a s p 应用达到工 业规模，仍然需要很大的努力。下一代的回答集求解系统必须对实际问题的需求 提供更好的支持。 1 2 3 应用研究 逻辑程序以一阶谓词为基础，将逻辑推理对应于计算，具有丰富的表达能力、 非确定性等特点，已经成功的应用于很多领域，如：诊断、信息集成、约束满足、 推理的行动( 包括规划) 、路由和调度、安全分析、产品配置、计算机辅助核查、 医疗保健、生物医学和生物学、语义网1 3 9 - 4 1j 、知识管理、文本挖掘和分类、问题 解答等。例如，m g e r b s e r 等【4 2 】人建立的增长型模型建立方法，主要关注于现实 的演变过程，针对演变过程的每一步进行描述。 2 0 0 7 年p a o l of e r r a r i s ，j o o h y u n gl e e 和v l a d i m i rl i f s e h i t z 等人将稳定模型语 义扩展到了一阶的情况1 4 3 】，并对各种语义结果做了对比，为逻辑程序的发展树立 了又一个里程碑。在此基础上，以上三个方面的研究将成为进一步的研究重点。 1 3 研究内容 为了进一步增强知识描述和推理的能力，本课题旨在提出一种新的扩展的加 权约束逻辑程序语言。新的逻辑程序是将一般加权约束规则的头部扩展为析取约 束的形式，使其更加适用于多约束可选知识的表示。并以此为基础展开一系列的 研究工作： 1 、提出一种新的扩展的加权约束逻辑程序语言。将一般加权约束逻辑程序 规则的头部扩展为析取约束的形式，使其更适用于多约束可选知识的表示；同时， 对加权约束逻辑程序稳定模型语义进行扩展，讨论新程序的稳定模型语义；并举 例说明新逻辑程序在产品配置问题中的具体应用。 2 、研究客户需求不合理情况下，产品配置系统无解的问题，寻求一种高效 的方法，为客户提供最优解。根据领域知识求得的配置解都是合理的，但只有符 合用户需求的配置解才是有效的。在实际问题中，由于客户专业知识的匮乏，其 提出的需求往往带有一定的不合理性，或者不确定性。这种情况下，求解系统将 给出无有效配置解的结论。本文提出一种加权定量的计算方法，为客户的每个需 5 北京t 业大学工学硕士学位论文 求进行加权处理，以求得满足最大客户需求度的合理配置解，作为对客户的反馈 和建议。 3 、基于s m o d e l s 系统实现新逻辑程序的稳定模型语义。s m o d e l s 系统是以 加权约束逻辑程序为基础建立的一个回答集求解系统，但它不适用于本文提出的 新程序。为了为新程序提供一个快速的求解器，方便其应用于实际问题，本文通 过分析新程序的语法和语义，以s m o d e l s 系统为基础，设计了新程序稳定模型语 义的求解系统。 1 4 论文组织结构 本文整体内容安排如下： 第1 章：绪论。介绍逻辑程序和产品配置问题的发展过程，详细阐述本课题 的来源及研究意义，并介绍本课题的研究内容。 第2 章：逻辑程序理论基础。介绍逻辑程序的各种不同形式，及其理论基础， 并详细介绍了回答集逻辑程序框架及其语义。 第3 章：扩展的加权约束逻辑程序。简要介绍加权约束逻辑程序，在此基础 上提出扩展的加权约束逻辑程序，详细阐述其语法和语义，并对其复杂度进行分 析。最后，简要介绍产品配置问题的基本概念，并介绍扩展的加权约束逻辑程序 在产品配置中的应用。 第4 章：针对需求不合理时，系统无解的情况，分析对产品配置解方案的优 化研究，提出新的加权定量优化方法，使得系统可以求得最接近解。 第5 章：扩展的加权约束逻辑程序稳定模型语义的实现。简要介绍s m o d c l s 系统，详细阐述以s m o d e l s 系统为核心的，扩展的加权约束逻辑程序稳定模型语 义的实现思想及算法。 结论，对全文工作进行小结，并对本文工作中存在的一些不足提出了可能的 改进思路和对今后工作的展望。 6 第2 章逻辑程序理论基础 第2 章逻辑程序理论基础 本章内容是后续章节的理论基础。研究逻辑程序，首先要了解逻辑程序的理 论基础，包括基本语法、语义，以及推理机制，本章将对一阶逻辑、基础逻辑程 序，以及当前应用最为广泛的回答集语义进行简要介绍，只有在了解这些知识的 基础上，才能深入理解回答集编程的思想。 2 1 基础逻辑程序 一个逻辑程序由规则组成，而一个规则由头部h e a d 和体部肋咖两部分组 成。如果6 d 方非空，则我们用一符号隔开头部和体部，表示“如果b o d y 成立， 则h e a d 成立”，一般形式为： h e a d + _ b o d y( 2 一1 ) 逻辑程序的基本语句属于一阶谓词演算的一个子集，h o r n 子句集。为了更 好的理解其基本语法，先了解一阶谓词演算中的相关术语： 定义2 1 1 项的定义： 1 ) 常量、变量是项； 2 ) 若厂是疗元函数，t l ，t n 是项，n f ( t l ，如) 是项。 定义2 1 2 合式公式( w f 0 的定义： 1 ) 若p 是拧元谓词，h ，“是项，贝i j p ( t l ，如) 是合式公式( 称为原子) ； 2 ) 若f 、g 是合式公式，则一f 、f v g 、f a g 、f _ g 、fhg 都是合式公式； 3 ) 若f 是合式公式，贝u v x f 、jx f 也是合式公式。 定义2 1 3 文字的定义： 原子( 正原子) 或原子的非( 负原子) 称为文字。 定义2 1 4 子句是如下形式的合式公式( w f f ) - v x z v x ( l i v v k ) ( 2 - 2 ) 其中每个l i 是文字( 原子或原子的非) ，x j 是出现e _ l i 中的所有变量。 上述子旬可等价变换为： a t v w m v - 1 b z v v 1 霸 ( 2 - 3 ) 其中a 1 ，4 m ，b 1 ，晶为原予。进一步等价为： a t v v a m + - b i a 人 ( 2 4 ) 称为子句的简写形式。 定义2 1 5 一个程序子旬的一般形式 以- 口1 ，( 2 5 ) 定义2 1 6 一个无条件子句是形式为a - 的子句，即体部为空的程序子句。 定义2 1 7 一个逻辑程序是一个有限的程序子句集。 7 北京工业大学1 = 学硕士学位论文 定义2 1 8 一个目标子句具有如下形式 卜b 1 ，岛( 2 6 ) 即一个头部为空的程序子句，其中每个b i ( f = 1 ，n ) 被称为该目标子句的 子目标。 定义2 1 9 空子句是头部和体部均为空的子句，用口表示。 定义2 1 1 0 一个h o r n 子句，或者是一个程序子句，或者是一个目标子句。 可见，h o r n 子句集是一阶逻辑公式的子集。其一般形式为： a - 日1 ，晶( 2 - 7 ) 其中a ，b ( 1 ，n ) 是原子，分别代表结论和前提。前提部分是各原子的合 取式，构成子句体，结论部分最多只有一个原子，称为子旬头。由此可将h o r n 子句分成两个基本类型： ( 1 ) 有头h o r n 子旬( 用来代表一条规则) ，例如， g r a n d f a t h e r ( x ，z ) 一f a t h e r ( x ，y ) ，f a t h e r ( y ，z ) 代表：x 是y 的父亲且y 是z 的父亲，则x 是z 的祖父。有头无体的h o r n 子旬是一断言( 用来代表一个事实) 。例如，f a t h e r ( a ，b ) 代表：a 是b 的父亲， f a t h e r ( b ，c ) 代表：b 是c 的父亲。 ( 2 ) 无头h o r n 子句，称为目标语句( 用来代表结论的否定式) ，例如， - - g r a n d f a t h e r ( a ，c ) 代表：a 不是c 的祖父。 逻辑学家a h o r n 对这类子句性质作了详尽的研究，h o r n 子句即因此得名。 学者们也将由h o r n 子句构成的逻辑程序称为基础逻辑程序( b a s i cl o g i cp r o g r a m ) 。 定义2 1 1 1 解释的定义 设论域d 是非空的集合，d 上的解释就是对谓词表达式中的每个常量、变 量、谓词和函数的指派，具体的： 1 ) 把每个常量指派为d 中的一个元素。 2 ) 把每个变量指派为d 中的一个非空子集。 3 ) 把每个元数为m 的函数f 定义在d 的m 个参数之上，并定义一种从d m 到d 的映射。 4 ) 把每个元数为n 的谓词p 定义在d 的n 个参数之上，并定义一种从d n 到 t r u e ，f a l s e 的映射。 定义2 1 1 2 模型的定义 对于公式f ，公式集s 和解释i ： 1 ) 在解释i 下，如果公式f 为真，则i 是f 的一个模型。 2 ) 在解释i 下，如果公式集s 中各公式均为真，则i 是s 的一个模型。 如果s 有模型，则称s 是可满足的；如果s 无模型，则称s 是不可满足的； 如果s 的任一模型都是f 的模型，则称f 是s 的逻辑推论，记为s i = f 。 预证公式集s 不可满足，需要证明公式集s 的任何解释i 都不是s 的模型， 8 第2 章逻辑程序理论基础 这显然太困难了。但是在逻辑程序中，公式集s 中的w f f 都是子句，而对于子句 集而言，只需证明一小类特殊的解释( h e r b r a n d 解释) 不是它的模型就能保证它是 不可满足的。 2 2h e r b r a n d 模型 1 9 3 6 年t u r i n g 和c h u r c h 互相独立地证明了：“没有一般的方法使得在有限 步内判定一阶逻辑的公式是否是永真( 或永假) 。但是如果公式本身是永真( 或者永 假) 的，那么就能在有限步内判定它是永真( 或永假) 。对于非永真( 或永假) 的公式 就不一定能在有限步内得到结论。判定的过程将可能是不停止的。” 要证明一个公式是永假的，采用反证法的思想( 归结原理) ，就是要寻找一个 已给的公式是真的解释。然而，如果所给定的公式的确是永假的，就没有这样的 解释存在，并且算法在有限步内停止。 因为量词是全称量词，所讨论的个体变量域是任意的，所以解释的个数是无 限、不可数的，要找到所有的解释是不可能的。h e r b r a n d 思想是寻找一个已给的 公式是真的解释。然而，如果所给定的公式的确是永假的，就没有这样的解释存 在，并且算法在有限步内停止。h e r b r a n d 定理是将证明问题转化成了命题逻辑问 题，给出一阶逻辑的半可判定算法，即仅当被证明定理是成立时，使用该算法可 以在有限步得证。而当被证定理并不成立时，使用该算法得不出任何结论。它简 化了讨论域，建立了一个比较简单、特殊的域，使得只要在这个论域上( 此域称 为h 域) ，原谓词公式仍是不可满足的，即保证了不可满足的性质不变。 定义2 2 1h e r b r a n d 论域设s 是一个子句集合，是s 的所有子句所含的 全体常量的集合。若s 中子句都不含常量，则任选一个常量a ，并令u o = a ，对i 1 ， 令u i = 仉一1u 眠( t l ，t ) l n 1 ，厶是s 中秩为7 l 的函数，t l ，仉一1 ) ；称仉 为s 的f 阶常量集。令u s - - u 峨( f 0 ) ，称魄为s 的h e r b r a n d 论域( h 一域) ，魄的元 素称为基项。 例2 1s = 伽( 力，q ( 厂( n ) ) v 1 r 0 ( 6 ) ) ) ，求h - 域。 u o = ( 口，6 ) 以= v o u f f ( a ) ，厂( 6 ) ，目( 口) ，夕( 6 ) ) = ( c 0 6 ，厂( 口) ，厂( 6 ) ，日( 口) ，目( 6 ) ) 巩= 叽ub e ( a ) ，厂( 6 ) ，厂( 厂( 口) ) ，厂( 厂) ) ，口( ，g ( 6 ) ，g ( 厂( n ) ) ， g ( f ( 6 ) ) ，厂( 夕( 口) ) ，厂( 目( 6 ) ) ，夕( 9 ( 口) ) ，g ( 目( 6 ) ) ) 魄= ( 口力) u 矿( c ) ，f ( d ) l c ，de 阢，i 0 ) 定义2 2 2h e r b r a n d 基( 1 i 基)设s 是一个子句集，以为s 的h 域，则s 的 h e r b r a n d 基毋定义为： = 仞( c l ，t ) l p 是s t 秩为7 l 的谓词，7 i 1 ，t ieu s ，1 f n ) 9 北京t 业大学工学硕士学位论文 风中的元素称为基原子。 例2 1 中s 的h 一基为p c a ) ，q c a ) ，r ( 口) ，p ) ，q c o ) ，r c b ) ，p ( f c a ) ) ，q ( 厂( 口) ) ， r ( f ( 口) ) ，p c f ( b ) ) ，q ( f c b ) ) ，r ( 厂( 6 ) ) ，】 定义2 2 3h e r b r a n d 解释子句集s 的h e r b r a n d 解释由下列基本部分组成： 1 ) 基本论域v s ： 2 ) s 的每个常数c 对应于魄中的同一个c ； 3 ) s 的每个变量x 都在魄中取值； 4 ) s 中的每个秩为，z 的函数厂n 对应于一个映射u s u s 一( 左边甩个 魄) ，使得对于任意一组基项( h ，“) 的映射为厂n ( 以，k ) 5 ) s 中的每个秩为刀的谓词p n 对应于一个映射u