（运筹学与控制论专业论文）命题逻辑中广义mp问题的合理解及新型反向三i算法.pdfVIP

f i r e a s o n a b l es o l u t i o nf o rg e n e r a l i z a dm pp r o b l e m si np r o p o s i t i o n a l l o g i ca n dn e w r e v e r s et r i p l eim e t h o d b y l ic a i h o n g b s ( h a n d a nc o l l e g e ) 2 0 0 8 at h e s i ss u b m i t t e di np a r t i a ls a t i s f a c t i o no ft h e r e q u i r e m e n t sf o rt h ed e g r e eo f m a s t e ro fs c i e n c e i n o p e r a t i o n sr e s e a r c ha n dc y b e r n e t i c s i nt h e g r a d u a t es c h o o l o f l a n z h o uu n i v e r s i t yo ft e c h n o l o g y s u p e r v i s o r a s s o c i a t ep r o f e s s o rl ij u n j u n e ，2 0 1 1 兰州理工大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献 的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律 后果由本人承担。 作者签名：套私炙 日期：腓6 月g 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学 校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅。本人授权兰州理工大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位论文。同时授权中国科学技术信息研究所将本学位论文收录 到中国学位论文全文数据库，并通过网络向社会公众提供信息服务。 作者签名：孝芬多次 导师签泓 日期：) 库乡月吕日 日期游月8 日 i 目录 摘要i a b s t r a c t i i i 第1 章引言1 1 1 课题的研究意义和国内外研究现状l 1 2 本论文研究的内容2 第2 章预备知识3 2 1 二值命题逻辑系统l 3 2 1 1 逻辑系统己中的基本概念3 2 1 2 逻辑系统l 中命题的真度4 2 1 3 逻辑系统中的相似度，伪距离和支持度5 2 2f u z z y 推理的三算法及反向三i 算法7 2 2 1 三i 算法8 2 2 2 反向三i 算法8 2 3 三角模与蕴涵算子9 第3 章命题逻辑中广义m p 问题的合理解1 4 3 1 公式的真度1 5 3 2 基于支持度理论的g m p 问题的合理解1 5 第4 章基于尺。蕴涵算子的一种新型反向三i 算法1 8 4 1 反向三i 算法的基本思想1 8 4 2 蕴涵算子的选择1 9 4 3 一种新型的反向三i ( f m p ) 算法2 0 4 4 一种新型的反向三i ( f m t ) 算法2 3 结论与展望j 2 7 参考文献2 8 致谢3 1 附录a 攻读学位期间攻读硕士学位期间的研究成果3 2 - 摘要 众所周知，数理逻辑的特点在于形式化与符号化，它和计算数学有着截然不 同的风格：前者注重形式推理而后者重视数值计算；前者强调严格论证而后者允 许近似求解逻辑推理方法在诸如定理的自动证明、知识推理、逻辑程序设计等 多个领域得到了广泛的应用：数值计算则似乎是远离形式推理的完全不同的方法 但由于人脑的思维模式与推理方法带有不确定性，导致推理不是精确地，而是近 似的，因此很有必要将数值计算引入到数理逻辑系统中从而使数理逻辑具有某种 灵活性并进而扩大其可能的应用范围正是出于此目的，王国俊教授提出了计量 逻辑学理论，给出了一个公式的可靠程度的描述一公式真度，进而给出了两个公式 间相似度，伪距离的概念并由此提出了理论的发散度，相容度等内容，为常见的命 题逻辑系统建立了一套完整的近似推理机制，给出了区分不同理论相容度的办 法 此外为了将模糊推理纳入逻辑的框架并从语构和语义两个方面为模糊推理 奠定严格的逻辑基础，通过将模糊推理形式化的方法移植到经典命题逻辑系统中， 把f m p 问题转化为g m p ，并在各命题逻辑中利用命题的真度引入命题之间的支 持度，利用支持度的思想引入广义m p 问题的一种新型求解机制，并证明了合理 解的存在性，这是本文研究的问题之一 随后王国俊又提出了模糊推理作为已知条件的推理前件“过半可信 原则， 并建立了一种f m p 问题的新型三i 算法，为将命题演算范围内的模糊推理引入人 工智能领域奠定了初步的基础宋士吉从如何设计模糊系统，使得在给定精度下 模糊规则库中元素最小的角度出发，提出了反向三i 算法本文在上述工作的基础 上，利用模糊推理中推理前件“过半可信 的原则，为f m p 问题建立了一种新型 反向三i 算法 本文的主要工作： 1 在经典命题逻辑中基于公式的真度概念提出了公式间的支持度，利用支 持度的思想引入了广义m p 问题的一种新型合理求解机制，并证明了合理解的存 在性 2 在模糊推理中利用推理前件“过半可信”原则，给出了基于r 蕴涵算子模 糊推理的一种新型反向三i 算法 关键词：真度；支持度：g m p 问题；合理解；过半可信原则；新型反向三i 算法 n a b s t r a c t a si sk n o w nt oa l l ，t h ec h a r a c t e r i s t i c so fm a t h e m a t i c a ll o g i cl i e si nf o r m a l i z a t i o n a n ds y m b o l i z a t i o n m a t h e m a t i c a ll o g i ca n dc o m p u t a t i o n a lm a t h e m a t i c sh a v ev e r y d i f f e r e n ts t y l e t h ef o r m e re m p h a s i z e sf o r m a li n f e r e n c e ，b u tt h el a t t e rp a y sm o r e a t t e n t i o nt on u m e r i cc a l c u l a t i o n t h ef o r m e re m p h a s i z e ss t r i c ta r g u m e n t ，b u tt h el a t t e r a l l o w sa p p r o x i m a t ea n a l y s i s w h i l et h el o g i c a lr e a s o n i n gm e t h o d sh a v eb e e nw i d e l y u s e di nm a n yf i e l d ss u c ha st h ea u t o m a t i cp r o o fo ft h e o r e m s ，r e a s o n i n ga b o u t k n o w l e d g ea n dl o g i c a lp r o g r a md e s i g n ，t h en u m e r i c a l c a l c u l a t i o ns e e m st ob ea m e t h o dt h a tl o o k ss od i f f e r e n tf o r mt h ef o r m a li n f e r e n c e b e c a u s eh u m a nb r a i na n d i n f e r e n c em e t h o d sh a v eu n c e r t a i n t yw h i c hl e a di n f e r e n c et ob ea p p r o x i m a t e ，t h e i n t r o d u c t i o no fn u m e r i c a lc a l c u l a t i o nf o rt h em a t h e m a t i c a ll o g i cs y s t e m sw h i c hc a n m a k ei th a v es o m ef l e x i b i l i t yi sv e r yn e c e s s a r y t ot h em a t h e m a t i c a ll o g i cs y s t e m s ， t h i s f l e x i b i l i t y a l s oe n l a r g e si t sp o s s i b l er a n g eo fa p p l i c a t i o n s f o rt h i sp u r p o s e ， p r o f e s s o rw a n gh a se s t a b l i s h e dq u a n t i t a t i v el o g i ct h e o r y i nt h i st h e o r y , p r o f e s s o r w a n gp r o p o s e dt h ec o n c e p to ft r u t hd e g r e e so ff o r m u l a sw h i c hc a nd e s c r i b e t h e d e g r e eo faf o r m u l a sr e l i a b i l i t y , a n d t h e nh ef u r t h e rp u tf o r w a r dt w oc o n c e p t s ： s i m i l a r i t yd e g r e eb e t w e e nt w of o r m u l a sa n dp s e u d o - d i s t a n c e b a s e do nt h e s e ，b o t h d i v e r g e n c yd e g r e ea n dc o n s i s t e n c yd e g r e eo ft h e o r i e sw e r ep r o p o s e d ，p r o f e s s o rw a n g s u c c e s s f u l l yc r e a t i v eac o m p l e t ek i n do fa p p r o x i m a t er e a s o n i n gm e c h a n i s ma n dp o i n t s o u tt h ew a yo fd i s t i n g u i s hd i f f e r e n tc o n s i s t e n c ed e g r e e so ft h e o r i e s i no r d e rt ot a k ef u z z yr e a s o n i n gi n t ol o g i c a lf r a m e w o r ka n dl a yt h es t r i c tl o g i c a l f o u n d a t i o nf o ri tf r o ms y n t a c t i ca n ds e m a n t i c ，t h i st h e s i sn o to n l yt r a n s f o r m e dt h e p r o b l e m f r o mf m pi n t og m pb yt h et r a n s p l a n t a t i o no f f u z z yr e a s o n i n g s f o r m a l i z a t i o nw h i c ho c c u r r e di nt h ec l a s s i c a lp r o p o s i t i o n a ll o g i cs y s t e m s ，b u ta l s o p r o v e dr e a s o n a b l es o l u t i o n s e x i s t e n c eo fan e wg m ps o l v i n gm e c h a n i s mw h i c h i n t r o d u c e db ys u s t e n t a t i o nd e g r e et h a tc o m e sf r o mt r u t hd e g r e eo fp r o p o s i t i o ni n p r o p o s i t i o n a ll o g i c t h i si so n e o ft h ep r o b l e m ss t u d i e di nt h i sp a p e r s o o na f t e r w a r d s ，p r o f e s s o rw a n gp r o p o s e dt h ep r i n c i p l et h a ti ft h es u p p o r t a t i o n d e g r e ef r o mp r e m i s et oc o n c l u s i o ne x c e s s e s0 5 ，t h e nt h e ya r ea d v i s a b l ea sf o rf u z z y i i i i n t e l l i g e n c e a s ap u r p o s ef o rd e s i g n i n g f u z z yr e a s o n i n gs y s t e m ，s o n gs h i j i g e n e r a l i z e dt r i p l e - i m e t h o di n t or e v e r s e d t r i p l e - im e t h o d b a s e dw a n g s h a l f a d v i s a b i l i t yp r i n c i p l e ，t h i sp a p e rp r o p o s e dan e wr e v e r s e dt r i p l e im e t h o df o rs o l v i n g f m p p r o b l e m s t h em a i nw o r ko ft h i sp a p e ri n c l u d e s ： 1 b ym e a n so f t r u t hd e g r e e so ff o r m u l a s ，t h i sp a p e rp u t sf o r w a r dan e wc o n c e p t o fs u s t e n t a t i o nd e g r e ea m o n gf o r m u l a si nc l a s s i c a lp r o p o s i t i o n a ll o g i c r e a s o n a b l e s o l u t i o nb a s e do nt h ei d e ao fs u s t e n t a t i o nd e g r e ef o rp r o b l e m so fg e n e r a l i z e dm o d u s p o n e n si si n t r o d u c e d ，a n dt h ee x i s t e n c et h e o r e mo fr e a s o n a b l es o l u t i o n si sp r o v e d 2 i ti sp r o v e dt h a t e , o t r i a n g u l a rn o r ms a t i s f i e st h ew a n g sp r i n c i p l eo fc r e d i t b e y o n dh a l f t h ec o r r e s p o n d i n gn e wt r i p l eim e t h o db a s e d o n e , 0i m p l i c a t i o no p e r a t o r o f f u z z yr e a s o n i n g i sg i v e n k e yw o r d s ：t r u t hd e g r e e s ；s u s t e n t a t i o nd e g r e e ；g m pp r o b l e m ；r e a s o n a b l e s o l u t i o n ； p r i n c i p l eo fc r e d i tb e y o n dh a l f ；n e wr e v e r s et r i p l eim e t h o d i v 一_一 第1 章引言 1 1 课题的研究意义和国内外研究现状 1 9 6 5 年，美国加利福尼亚大学z a d e h 教授发表了论文( f u z z ys e t s ，并由此 开创了模糊逻辑的历史继论文( f u z z ys e t s 之后，z a d e h 教授又于1 9 7 3 年首次 提出了基于模糊集合理论和模糊逻辑的近似推理理论，即著名的c r i 算法，用以 解决f m p 和f m t 问题乜1 不久，模糊推理方法被应用于智能控制技术中，并取得 了举世瞩目的成功现在，模糊推理已经成为信息科学中进行模糊信息处理和实 现机器智能的重要工具，同时也成为计算机学科，控制科学和人文决策等学科的 重要研究课题 然而，作为模糊控制理论核心部分的模糊推理却被指出缺乏严格的逻辑基础 在1 9 9 3 年第十一届人工智能年会上，e l k a n 博士做出了题为“模糊逻辑似是而非 的成功”的报告这次报告在模糊逻辑界甚至整个人工智能界引起了强烈的反应， 并由此引发了关于模糊逻辑的必然性的一场国际性争论这场争论澄清了若干对 于模糊逻辑的不正确看法，由于c r i 算法推理机制缺乏严格的逻辑基础而受到质 疑口吲为了弥补c r i 推理方法的若干缺陷和不足，王国俊n 钔教授首次推出了模糊 推理全蕴涵三i 算法，全蕴涵三i 算法有效地改进了经典的c r i 算法，并将之纳 入到了模糊逻辑的框架之中从此，在模糊逻辑、模糊推理和模糊控制领域掀起了 模糊推理三i 算法的研究热潮，并得到了很多的研究成果n 眦引 王国俊教授通过将基本逻辑概念程度化的方法提出了计量逻辑学理论，近年 来关于程度化推理的研究受到了广泛的关注乜4 。3 羽那么，可否将计量逻辑学理论 中提出的程度化推理机制和三i 算法的思想融合到一起，并在多值逻辑中给出和 模糊推理相应的求解机制，进一步为模糊推理奠定严格的逻辑基础呢? 文献 3 3 - 3 5 已经分别在经典命题逻辑和甩值r 命题逻辑中，利用命题的真度概念引 入了公式之间的支持度，并基于支持度给出g m p 问题以及集体广义m p 问题的 一种新的求解算法，从语构和语义相结合的角度为模糊推理奠定了逻辑基础 这些研究从语义和语构两个方面入手，一方面因为逻辑系统的语构理论的 形式化推理非常明显，这样也就不容易利用程度化的方法来研究；另一方面，由于 三i 算法成为模糊控制等领域的一个研究热点并有着极为广泛的应用州2 1 王国俊h 2 1 教授在模糊推理中提出了“过半可信 原则，并证明了r l 型三角模 恰为可实现这一原则的三角模在此基础上，将模糊推理中的大、小前提作了修 正从而摒弃了不可信的推理成分，推出了一种新型的三i 算法研究了逻辑系统 r 中形式推理机制，基于根的理论为新型三i 算法奠定了严格的逻辑基础文献 3 8 提出了基于g 6 d e l 蕴涵算子的新型反向三i 算法本文将在上述工作的基础 上，基于r i 蕴涵算子建立一种新型的反向三i 算法 1 2 本论文研究的内容 本文的内容如下： 第l 章引言，主要描述了模糊逻辑的意义和国内外研究现状最后说明论文 研究内容，并安排了本文的主要结构 第2 章预备知识，本章主要介绍二值命题逻辑系统中的基本性质、模糊推理 的三i 算法及反向三i 算法的基本思想和三角模与蕴涵算子，为本文后续部分做 好准备 第3 章在经典命题逻辑中基于公式的真度概念提出了公式之间的支持度， 利用支持度的思想引入了广义m p 问题的一种新型合理求解机制，并证明了合理 解的存在性 第4 章在模糊推理中利用推理前件“过半可信 原则，知r 型三角模是恰可 实现这一原则的三角模，给出了基于尺d 蕴涵算子模糊推理的一种新型反向三i 算 法 2 第2 章预备知识 2 1 二值命题逻辑系统l 2 1 1 逻辑系统中的基本概念 定义2 1 1 渊设s ； p 。，p 2 ，作f ) 如下： ( i ) p l ，p ：，e f ( s ) ； ( i i ) 若a ，b e f ( s ) ，则一彳，a * b e f ( s ) ； ( i i i ) f ( s ) 中是s 生成的( 一，一) 型的自由代数s 中的元叫做原子命题，命题 或原子公式，f ( s ) 中的元叫命题或合式公式，简称公式 逻辑连接词v 和a 用一和呻表达，规定： avb 是一a _ 曰的简写 aab 一即一一b ) 的简写 定义2 1 2 隆5 1i 发f ( s ) 0 1 是映射，若，是( 一，一) 型的同态，即 ，( 一彳) 一一v ( a ) ，v ( a b ) - v ( a ) - - v ( b ) 称 ，为， ) 的赋值， ，似) 也叫做公式4 的赋值f ( s ) 的全体赋值之集记作q 命题2 1 1 伍5 1 设 ，：f ( s ) 呻 o ，1 ) 是赋值，l i j v 保持f ( s ) 中运算v 和 即 v ( avb ) 一，o ) vv ( b ) ，v ( aa 曰) = ，0 ) ，( 曰) 定义2 1 3 乜翻设爿，b f ( s ) ( i ) 若对每个 ，q ，均有，( 彳) = 1 ，则称a 为重言式，记作卜彳若对每个 ，q ，均有，( 爿) 一0 ，则称彳为矛盾式 ( f f ) 若对每个 ，q ，均有，( 彳) a ，( b ) ，则称彳与b 逻辑等价，记作4 - b 在l = 0 ，q 中规定：- , 0 = 1 ，- - , i 一0 ，口一b = 0 当且仅当a 一1r b 一0 ， 3 命题逻辑中广义m p 问题的合理解及新型反向三l 算法 贝j j o ，q 成为一个( 一，- ) 型代数 定义2 1 4 乜叼函数厂： o ，1 4 - - o ，1 ) 叫做b o o l ei 撇( n e n ) 通俗地讲，胆元b o o l e 函数就是以长度为，l 的0 - 1 序列为变元，并在 o ，1 ) 取值的以 元函数 例2 1 1 由i ( 0 ，1 ) 一fo , o ) 一o ，f ( 1 , 1 ) = i ( o ，0 ) = 1 所表示的函数就是一个 二元b o o l e 函数 定义2 1 5 陵5 1 设a ( p l ，p ：，见) 是含有n 个命题变元的合式公式，它由 p l ，p ：，见通过逻辑连接词，呻，v ， 等连接而成设( _ ，x ：，_ ) o ，1 ) 4 分别 用_ ，x 2 ，毛取代彳( p 1 ，p ：，见) 中的p l ，p 2 ，见，则得一个，l 元函数，记作 彳( _ ，x 2 ，) ，叫做由公式a 诱导出的b o o l e 函数 1 歹02 1 2 若彳- - ( p 。一p ：) vp 3 ，则j ( 置，x ：，z ，) = ( 一呻石：) v 屯 命题2 1 2 伍任意一个b o o l e 函数都可由某个合式公式导出 2 1 2 逻辑系统中命题的真度 设a ( p l ，p ：，见) 是系统中含有n 个原子命题的公式，则由定义2 1 5 知a 确定一个万元b o o l e 函数j ： o ，廿“- - o ，畸对于a ，p ：，的某些赋值，a 的赋值 等于1 上述赋值的个数用函数j 表示就是i j _ 1 ( 1 ) i 又，n ，p ：，p 。的各种赋值的 总数就是n 维0 - 1 向量的总数，总共有z 个所以从计算概率的角度出发，可以给 出如下的定义： 定义2 1 6 乜叼设彳瓴，p ：，以) 是命题逻辑系统中含有以个命题变元的合 式公式，则彳的真度f ( 爿) 定义如下： z ( 彳) 。掣 例2 1 3 求公式p lvp 2 ，n _ 办v 岛的真度 4 硕上学位论文 解( f ) 对于公式p 。vp 2 而言，其诱导的b o o l e 函数为a = 五vx 2 ，彳( 五，t ) 在点 ( 1 ，o ) ，( 1 ，1 ) ，( o ，1 ) 处的值为l ，在( o ，o ) 处的值为o ，所以f ( p l v p 2 ) 一三 ( i i ) 公式n p ：vp 3i 黼3 元b o o l e 函数为而- - 3 x 2 v x 3 ，在( l o ，o ) 处值为 o ，而在其它各点处都为l ，所以z ( n 呻p 2 v p 3 ) = 吾 性质2 1 1 删在二值命题逻辑系统中，设4 ，b ，c f ( s ) ，则 ( i ) 若卜4 _ 丑，则f ( 彳) sz ( b ) ： ( i i ) f ( 彳) - z - ( a b ) + f ( 彳 一b ) ； ( i i i ) f ( 彳vb ) = f ( 彳) + f ( 曰) 一z ( 彳 b ) ； ( i v ) 若卜彳呻b ，f ( 彳) = f ( b ) ，则4 - b ； ( y ) f ( 彳) = 1 - v ( - , a ) ； ( v i ) 若f ( 彳) 口，f ( 彳- - b ) 芑，则f ( b ) 口+ 一1 ： ( v i i ) 若f ( 爿_ 曰) a , v ( b _ c ) 2 ，则f ( 4 - - , c ) 苫a + 一1 我们只证明( i v ) ，其它的可参看文献 3 6 证明 当卜a b 时，不妨设彳，b 含有相同的原子公式，则 v y q ，v ( a ) g ，( 曰) 所以v ( a ) = 1 时 ，( b ) = 1 ，而当v ( a ) = 0 时，v ( 口) = 0 ，否则 使b 赋值为1 的赋值映射的个数就会大于使a 赋值为1 的赋值映射的个数，从而 f ( 彳) 1 c2 ， 证明以( 如) 为例进行证明式中的。满足定义2 3 i 中的( f ) ，( i i i ) 并i i ( i v ) 比 较明显，以下只证。满足条件( f f ) 设口+ 6 1 6 + c 1 ，口+ c 1 ，贝0 ( 口 b ) + c 1 所以 ( 口0 6 ) o c - - ( a 6 ) c = ( 口 6 ) a ca 口 ( b c ) = 口 ( b ( d c ) = 口 ( 6 0 c ) 设上面不等式之一不成立，比如，设a + 6s1 ，则由式( 2 1 ) 得： ( 口 6 ) c = o g c - 0 又，由口+ ( 6o c ) s 口+ 6 s 1 和式( 2 1 ) 得口o ( 6o c ) ao 所以仍有 ( 4 0 6 ) c = 口o ( 6 0 c ) 本例中的三角模都是常见的三角模，从( i ) 至a j ( i v ) 依次称为l u k a s i e w i c z ：_ 角模，g s d e l 三角模，乘积三角模和心三角模，并分别把它们记为 吼，晚，吼 定义2 3 2 1 设 是 o ，1 上的f 一模，尺： o ，1 2 呻【o ，1 是 o ，1 上的二元函 数若 a bs c当且仅当 口sr ( 6 ，c ) ，口，b ，cs o ，1 1 0 硕卜学位论文 则称r 为与 相伴随的蕴涵算子，称( o ，r ) 为伴随对 例2 3 2 以下4 个蕴涵算子分别是r l ，砖和r 。分别与 ，o g ，瓯和 瓯构成伴随对( 设口，b e o ，1 ) ： ( i ) r ( 口，b ) = ( 1 - a + 6 ) 1 ； ( f f ) ( 口，6 ) 2 眇1 , a b 6 ； f 1 a 一0 ( i i i ) b ( 咖) 2k 1 ，口 o ； la ( i v ) r o ( 口，6 ) 2 1 1 ( , 1 a 一 6 ( 2 2 ) 我们以( i v ) 为例进行验证，其余可参考文献 2 5 证明对于r 。蕴涵算子用 表示吼，用口呻6 表示尺。a ，b ) 设口0 6 s c ， 应证明asb - c 由式( 2 2 ) 知当bsc 时6 _ c 一1 ，得as6 _ c 所以可设6 c ， 从而b c 一( 1 - b ) vc 如果口+ 6 1 ，则由以0 6s c 和式( 2 1 ) 知a bsc ，再由 b c 得asc ，所以asb 呻c 如果a + 6s1 ，仍有as 1 一bs6 一c 反过来，设 口s6 _ c 女日果6 c ，贝0 口0 6 口 cs1 0 c c 如果6 c ，贝0 由口s ( 1 - b ) vc 知 口s1 一b ，从而由a + 6s1 知a0 6 = 0sc ，或asc ，从而a0 6sa0 1 = asc 所以 ( o 。，尺d ) 是伴随对 定义2 3 3 嘲三角模。叫左连续的，如果对每个口 o ，1 ， 厂口( 兰岛) = 兰丘( 包) 无( 工) ；口 工 命题2 3 1 嘲设 是 o ，1 上的左连续三角模在 o ，1 上定义二元运算呻如 1 1 则 命题逻辑中广义m p 问题的合理解及新型反向三i 算法 b - p c v x l x bsc ，x , b ，c e o ，1 ( i ) 一是与。相伴随的蕴涵算子，即 a bsc 当且仅当asb c ； ( i i ) b 呻c l 当且仅当6s c ； ( i i i ) 口s6 一c 当且仅当6 s 口- c ： ( i v ) ( ，) 口一( 6 呻c ) = 6 一( 口呻c ) ； 1 _ c = c ： ( 订) 6 一念c f i 台( b - * c i ) ，( 兰包) 一c = 台( 包呻c ) ； ( v i i ) b c 关于c 单调递增，关于6 单调递减 ( 2 3 ) ( 2 4 ) ( 2 5 ) ( 2 6 ) 证明 ( i ) 设a b sc ，则由式( 2 3 ) 立即得出口s6 呻c 反之，设 口ab 呻c = v x lx o b s c ) ，则由 的单调性以及左连续性得 ao b 一6 口s 6 0 ( 6 一c ) 一v b xl x o b s c ) s c ( i i ) 设b c ；1 ，则1 - ：b 呻c ，从而由( i ) 得b 一1 6s c ，反之，设bsc ，即 l o bsc ，所以由式( 2 4 ) 得1sb c ，从而b - c 一1 ( i i i ) 由式( 2 4 ) 得口墨6 呻c 当且仅当ao b sc 当且仅当b asc 当且仅当 bs a _ c 所以式( 2 5 ) 成立 ( i v ) i ves 口一( b - - * c ) ，贝, l je o a s 6 一c ，从而( e o 口) 0 6 sc 由 的可换性 和结合性知( e 0 6 ) o 口sc 1 i f i 以( e o b ) ca - - c ，es6 一( 口呻c ) 又，以上推理是 可逆的，且e 可取为口一( b 呻c ) 或6 - - , ( a 呻c ) ，所以口- - ( b c ) = 6 - ( 口一c ) ( v ) 1 - * ca v x l x o l , c ) 一v z i zs c ) = c ( v i ) 由( 呻) 是伴随对知 asb 呻ac i 当且仅当a 6saq ， l t = xi t d 1 2 硕i j 学位论文 当且仅当v i e i ，a 0 6s c ， 当且仅当v i e l ，ag b _ c ， 当且仅当口s 台( 6 呻c ；) ， 所以b 呻ac ；一a ( b _ c ；) 又，由 左连续得 目i e ! 、 口s ( 兰包) _ c 当且仅当口。兰包s c ， 当且仅当兰( 口 包) s c ， d 当且仅当v i e i ，a 包s c ， 当且仅当v i e l ，as 岛一c ， 当且仅当口s 会( 包 所以( 兰包) 一c 一台( 岛_ c ) 呻c ) ， ( v i i ) 设c 1s c 2 ，则c 1 = c 1a c 2 ，所以由式( 2 6 ) 得 b _ c la6 c 。ac ：一( b 呻c ，) ( b c ：) 由此可知6 c ls6 呻c 2 又，设饥sb = ，贝, l j b e = 轨v 如，所以由式( 2 6 ) 得 - c - b , vb , - - - - c 一( 岛一c ) a ( b 2 呻c ) 由此可知如呻c s 2 j l 呻c 1 3 第3 章命题逻辑中广义m p 问题的合理解 经典命题逻辑学中最基本的推理规则是m p 规则：由a _ 口和a 可得口 即，a 可以从a 呻口中把b 分离出来，也正因如此m p 还有一个名字叫“分离规 则 ，这时a 以外的公式不能把口从a 呻b 中分离出来如果问：“从a _ 曰与a 可推出什么? ，则答案是“不知道 ，甚至这一问题会被认为是“病态问题 ， 这是因为从形式化演绎推理的角度看，由公式集f = 翻_ 曰，彳。 出发可以推出许 许多多的结论来，比如，a a ( a b ) ，a v ( a - 召) 以及全体定理等等都是f 的 结论这些结论形式各异，且从语义的角度看，有些结论是重言式，有些则不是，差 别很大那么能否给出一个尺度来评判某个公式作为r 一结论的合理性呢? 具体 地讲，就是能否根据某个评判尺度，从众多的r 一结论中挑选出相对于该尺度而言 最合适的结论呢? 这正是本章的研究目的值得指出的是，为了给f m p 奠定严格 的逻辑基础，文献 2 4 中将“彳一曰与a + 可推出什么”这一问题称为广义m p 问 题( 以下简称为g m p 问题) ，可写为如下形式： 已知a 呻曰 给定a ( 3 1 ) 求8 这里说：求8 其实应当是“定义b 。，因为a ，b ，a + 都是纯形式化的逻辑公式 为此文献 2 4 中引入了一族逻辑公式的根的概念，g m p 问题中的b 就定义为 a b ，彳 的根 另外，为了将数值计算有机地融入到形式化逻辑推理中，近年来关于程度化 推理的研究得到了广泛的关注，本部分将把文献 1 8 中所提出的命题逻辑的程度 化方法和模糊推理三i 算法的思想融入到g m p 问题的求解中，利用命题的真度引 入公式之间的支持度，并基于支持度给出g m p 问题一种合理解的评判标准，并研 究合理解的存在性 1 4 硕 ：学位论文 3 1 公式的真度 设s 一扣，p ：，) 是原子公式集，f ( s ) 是由s 生成的( 一，一) 型自由代数其 中，是一元连接词，是二元连接词设rcf ( s ) ，a e f ( s ) ，从r 到彳的一个 推理是一个公式的有限序列： 4 ，4 ，以 其中，4 - - a ，r v is 历，或者4e f u t ，或者存在，七 f ，使4 是由a j 和4 运 用m p 规则而得到的结果，其中t 代表全体定理之集，称a 为r 一结论，记作：r 卜 a f 为空集时，称彳为定理，简记为：f a 下文用d ( r ) 来记全体r 一结论之集 定义3 1 1i 受a ( p ，p ：，p 。) 是f ( s ) 中含有m 个原子公式的逻辑公式，则彳 的真度r ( 彳) 定义如下： 摊学 3 2 基于支持度理论的g m p 问题的合理解 本部分将从语义和语构相结合的角度为g m p 问题给出一种基于支持度理论 的合理求解机制，并证明合理解的存在性 定义3 2 1 广义m p 问题基于支持度的解b 是满足下式： s u s t ( a - b ，彳_ b ) ；1 ( 3 2 ) 并且使得s u s t ( a _ 曰，彳呻b ) 取值最大的o ( r ) 中的公式，其中 f ； 彳_ b ，彳】_ 注1 定义3 2 1 给出的基于支持度的解b 要满足三个条件，首先要求a 呻b 最大程度支持a - b 使s u s t ( a 呻b ，a _ 曰) = 1 其次要求a - b 也要最大可 能支持a 呻b ，最后，还要求b 是d ( r ) 中的公式因为我们给定了 命题逻辑中广义m p 问题的合理解及新型反向三i 算法 r = 掣呻j e i ，a 】的前提下来求b 的，因此把b 作为r 一结论是合理的 定理3 2 1( 解的存在性定理) 由定义3 2 1 给出的g m p 问题( 3 1 ) 的合 理解b 一定存在 ， 证明只需验证b = 么ao - 曰) 是g m p 问题( 3 1 ) 的合理解 首先b d ( r ) 是显然的，其次，容易验证下面的可证等价式： a + 一( ( 彳- - b ) aa ) ( 彳- - , ( 1 4 呻曰) ) a - - - , a ) 再注意到a 呻4 是重言式，则由命题2 1 i i 可得： s “s t ( a _ 口，a 一曰) 窀淞f ( 彳一曰，彳- , ( t t b ) 彳) 习“s t ( ( a _ b ，) 彳呻( 彳- - b ) ) = f - - b ) ) - - ( a + - - ( a 呻b ) ) ) 一l 最后，证明在所有满足式( 3 2 ) 的公式当中，b 。= 彳a ( a _ b ) 使得 s u s t ( a 一b ，彳一b ) 的取值最大设c + 是d ( r ) 中满足_ s u s t ( a 呻曰，彳呻c ) = l 的任一公式，下证： 事实上， s u s t ( a 呻b + ，彳_ b ) 芑s u s t ( a _ c 。，a 呻b ) ( 3 3 ) s “5 t ( a + 呻c ，a - - * b ) = f ( ( 彳呻c ) 呻( 彳一b ) ) ， 再由定义3 2 1 ，命题2 1 1 以及彳_ ( 彳 ( 彳呻曰) ) 一( 彳_ ( 彳呻b ) ) 易得 娜t ( a 呻矿a - - * b ) = f ( ( 彳一彳。 ( a - - b ) ) - - ( a - - b ) ) = f ( ( 彳_ ( 彳_ b ) ) 呻( 彳一b ) ) ( 3 4 ) 因为c d ( r ) ，其中r ；纠_ b ，a ，即f 卜c ，由演绎定理得不难证明： i - a a 似- - b ) 呻c 成立，从