（基础数学专业论文）lukasiewicz逻辑系统中的模糊推理及模糊概念格的属性约简.pdf

l u k a s i e w i c z 逻辑系统中的模糊推理及模糊概念格的属性约简 李立峰 摘要在模糊理论的发展过程中，蕴涵算子在其中起着重要作用，比如，在建立 多值逻辑的语义理论方面，不同的逻辑系统涉及不同的蕴涵算子在知识发现( 比 如模糊概念格) 方面，蕴涵算子也起着非常重要的作用本文主要就模糊推理在 l u k a s i e w i c z 逻辑系统中的实现问题以及基于g s d e l 蕴涵算子的模糊概念格的属 性约简理论展开探讨，取得了一些有意义的成果 为了给模糊推理在逻辑语义方面建立严格的逻辑基础，王国俊教授通过将 赋值取为逻辑公式中的变元的方法在经典二值逻辑中建立了f m p 问题的推理模 式，提出了( ，) 型三i 解，并把这种方法推广到了l u k a s i e w i c z 三值系统中，这 时所谓赋值决定公式问题( v a l u a t i o n a l l yd e c i d e df o r m u l aq u e s t i o n ，简称v d f 问 题) 起着至关重要的作用本文在第二章首先给出了v d f 问题的合理性条件，并 且基于对赋值决定公式的原理和单原子逻辑公式所诱导的m c n a u g h t o n 函数结 构的分析，研究了赋值域为有限集、可数无限集以及具有连续统势的无限集时的 模糊m p 推理的逻辑基础，证明了模糊推理可以在任意l u k a s i e w i c z 多值逻辑系 统中得到实现 1 9 8 2 年，w i l l r 提出了概念格理论，它是依据对象与属性之间的二元关系基 于g a l o i s 联络而建立起的一种概念层次结构由于概念格理论在软件工程、数据 结构分析、信息工程等方面有着重要的作用，有关概念格的研究目前十分活跃 在现实生活中对象与属性的关系大多是不确定的模糊关系，因此，许多类型所谓 的模糊概念也纷纷被提出本文的第三章分析由s e l l o u m i 所提出在6 o ，1 】水 平上的模糊概念的定义，选用g i d e l 蕴含算子建立一种模糊概念格并且讨论了该 类模糊概念格的属性约简理论，提供了几种判断属性约简的方法，从而为知识约 简提供了一种方法 关键词：模糊推理赋值决定公式问题l u k a s i e w i c z 多值系统模糊概念格属 性约简 f u z z yr e a s o n i n gi nl u k a s i e w i c z r e d u c a t i o ni nf u z z y l o g i cs y s t e m sa n da t t r i b u t e c o n c e p tl a t t i c e s l i l i f e n g a b s t r a c t i m p l i c a t i o no p e r a t o r sp l a yav e r yi m p o r t a n tr o l ei nt h ed e v e l o p - m e n to ff u z z ys e tt h e o r y f o re x a m p l e ，i nt h ea s p e c to fb u i l d i n gu pt h es e m a n t i c s o fm a n y - v a l u e dl o g i c ，d i f f e r e n tl o g i cs y s t e m si n v o l v ed i f f e r e n ti m p l i c a t i o no p e r a t o r s ， a n di nt h et h e o r yo fk n o w l e d g ed i s c o v e r y ( s u c ha st h et h e o r yo ff u z z yc o n c e p tl a t t i c e s ) ，i m p l i c a t i o no p e r a t o r sa l s op l a ya ni m p o r t a n tr o l e t h es o l u t i o no ff u z z y m o d u sp o n e n si nl u k a s i e w i c zl o g i cs y s t e ma n da t t r i b u t er e d u c t i o nb a s e do nt h e g s d e li m p l i c a t i o no p e r a t o ra r ei n v e s t i g a t e di nt h i sa r t i c l e ，a n dw eo b t a i ns o m e m e a n i n 豇u lr e s u l t s i no r d e rt ob u i l du pas o l i dl o g i c a lf o u n d a t i o nf o rt h el o g i c a ls e m a n t i c so ft h e f u z z yr e a s o n i n g ，p r o f e s s o rg u 叫n nw a n gp r o p o s e dt h er e a s o n i n gm o d e lo ff m p i n c l a s s i c a ll o g i c ，w i t ht h em e t h o do fu s i n gt h es y m b o la ( u ) t od e n o t e ( a ) ，w h e r e ni sa ne v a l u a t i o na n da f ( s ) i sal o g i cf o r m u l a f u r t h e r m o r e ，t h et r i p l e i s o l u t i o nw a so b t a i n e d w h e nt h i sm e t h o di su s e di nl u k a s i e w i c z3 一v a l u e dn o r m a l s ”t e m s ，t h ep r o b l e m - v a l u a t i o n a l l yd e c i d e df o r m u l aq u e s t i o n ( a b b r e v i a t e da st h e v d fp r o b l e m ) ，p l a y sac r u c i a lr o l ei nt h em a t t e r i nc h a p t e r2 ，t h er e a s o n a b l e c o n d i t i o no fv d fi ss t u d i e df i r s t ，a n db a s e do nt h ea n a l y s i so nt h ep r i n c i p l e so f v d fa n dt h es t r u c t u r eo fm c n a n g h t o nf u n c t i o ni n d u c e db yt h es i n g l ea t o ml o g i c f o r m u l a ，t h el o g i cf o u n d a t i o no ff m p ，w h o s ee v a l u a t i o nf i l e di sf i n i t es e t s ，c o u n t a b l e i n f i n i t es e t so rt h eu n i ti n t e r v a lr e s p e c t i v e l y , i ss u r v e y e d m o r e o v e r lw ep r o v et h a t f u z z yr e a s o n i n gc a nb ea c h i e v e di na n yl u k a s i e w i c zm a n y v a l u e dl o g i cs y s t e m i n1 9 8 2 ，a c c o r d i n gt ot h ec r i s pr e l a t i o nb e t w e e no b j e c ts e ta n da t t r i b u t es e t ， w i u re s t a b l i s h e dat h e o r yo fc o n c e p tl a t t i c e sw h i c hi sak i n do fc o n c e p th i b e r a r c h y b a s e do nt h ef o u n d a t i o no fg a l o i sc o n n e c t i o n s i n c et h i st h e o r yp l a y sac r u c i a lr o l e i ns o f t w a r ee n g i n e e r i n g ，d a t aa n a l y s i sa n di n f o r m a t i o ne n g i n e e r i n g ，m a n yr e s e a r c h e r s s h o wg r e a ti n t e r e s ti ni tr e c e n t l y i nr e a l i s t i cl i f e ，g e n e r a l l y , t h er e l a t i o nb e t w e e n o b j e c t sa n da t t r i b u t e s i sf u z z y , a n ds om a n yk i n d so ff u z z yc o n c e p t sh a v eb e e n p r o p o s e db a s e do nd i f f e r e n tb a c k g r o u n d s ，i nc h a p t e r3 ，t h ef u z z yc o n c e p t a tt h e l e v e l6 0 ，1 】，w h i c hw a sp r o p o s e db ys e l l o u m i ，i sf u r t h e r l ya n a l y z e d ，a n da n e wf u z z yc o n c e p tl a t t i c e sw i t hr e s p e c tt og s d e li m p l i c a t i o no p e r a t o ri sb u i l tu p i i f u r t h e r m o r e ，b a s e do i lt h es t u d yo fi t sa t t r i b u t er e d u c t i o nt h e o r y , s e v e r a lm e t h o d s a b o u ta t t r i b u t er e d u c t i o na r ep r o p o s e d t h u st h i sd i s e r t a t i o no f f e r san e wt o o lt o d e a lw i t hk n o w l e d g er e d u c t i o n s k e y w o r d s ：f u z z yr e a s o n i n g ；t h ev a l u a t i o n a l l yd e e d e df o r m u l aq u e s t i o n ； l u k a s i e w i c zl o g i cs y s t e m ；f u z z yc o n c e p t ；a t t r i b u t er e d u c a t i o n i i i 学位论文独创性声明 y 900 7 毒0 本入声明所壁交的学位论文是我在导师的指导下进行的研究工作及取得的研 究成果。尽我所知，除文中已经注明引用的内容外，论文中不包含其他个人已经 发表或撰写过的研究成果，也不包含为获得陕蹰j i i l l 范大学或其它教育机构的学位 或莲书面使用过的材斟。对本文的研究徽般重要贡献孵个人和集体，均邑在文孛 作了嚼确说哽并表示谢意 作者签名；蕉立喹目期：趔。三 学位论文使用授权声明 本人同意研究生在校攻读学位期闯论文工作的知识产权单位属陕西娜范大 学。本人保证毕业离校蜃，发表本论文或使用本论文成果时署名单位仍兔陕谣癖 范大学。学校有权保留学位论文并向量家主管部眩曦其它指定机构送交论文的毫 子舨帮纸质舨；有权将学位论文用于非赢利曩的的少量复制并允许论文逃入学校 篷书| 嚷、院系资料室被查嬲；有权将学链论文的蠹容编入有关数据痒进行检索； 有权将学链论文的标惩藕摘要汇编密舨。 作者签名。堇塞童 碧簸御歹，r 黧絮：竺堕! 前言 模糊系统理论的创始人z a d e hl a 于提出模糊集理论后不久就提出了模糊 推理的m p 规则( 以下简称f m p ) 并给出了著名的c r i 算法队f m p 及其c r i 算法一经提出就受到了广泛的关注，并被众多的工程技术人员用于各类模糊控 制问题之中，取得了很大的成功 2 - 4 j ，同时模糊推理的理论研究也纷纷被提出 5 - 1 4 】，至今模糊推理的理论与应用仍保持着强劲的进展势头但是另一方面， 模糊推理的逻辑基础却受到质疑，1 9 9 3 年e l k e nc 在美国第1 1 届人工智能年会 上作了题为“模糊逻辑的似是而非的成功”的报告，引起了一场轩然大波此后 虽有1 5 位专家撰文批驳e l k e n 的观点，但e l k e n 并未被完全说服，他又以“关于 模糊逻辑的似是而非的争论”作答 1 9 9 5 年，w a t k i n sfa 又撰文说“双方都 错了”( 参看文献【i 5 2 0 ) 由此可见模糊推理方法的理论基础问题的确是值得商 榷的为了尝试为模糊推理建立严格的逻辑基础，王国俊教授在分析了c r i 算 法在推理机制上的不足之后，提出了基于逻辑语义中重言式概念的求解f m p 的 三i 方法 2 1 - 2 2 1 ，这一方法引起了学者的广泛关注并在各个不同的方面得到了发 展【2 3 _ 4 “此后又进一步基于三i 算法的思想分别在经典的二值逻辑系统c 和多 值逻辑系统e 中提出了根的理论，并从而从语构的角度为模糊推理奠定了完全 严格的理论基础 4 3 - 4 5 值得注意的是，王国俊教授同时还从逻辑语义的角度通 过将赋值取为逻辑公式的变元的方法在经典的二值逻辑中建立了f m p 的推理模 式，提出了( ，) 型三i 解，虽然这里作为论域的为有限集，但由于无限论 域总可以用充分大的有限论域去近似表达，所以这种方法仍不失其有效性这种 ( ，) 型三i 解还被推广到了l u k a s i e w i c z 三值系统中，这时所谓赋值决定公式 问题( v a l u a t i o n a l l yd e c i d e df o r m u l aq u e s t i o n ，简称v d f 问题) 起着至关重要的作 用下面将看到，只要在某多值系统中v d f 问题可解，就可以在该系统中建立 f m p 问题的逻辑版本如f 4 4 1 所指出的，在多值逻辑系统中v d f 问题一般不可 解，只有合理的v d f 问题是可解的宋玉靖在【4 6 1 中就p + 1 值l u k a s i e w i c z 逻 辑系统的情形给出了v d f 问题可解的条件，这里p 为素数值得注意的是，在 一般l u k a s i e w i e z 逻辑系统中的v d f 的可解性问题十分复杂，这从文献【4 4 中就 三值l u k a s i e w i e z 系统和【4 6 1 中就p + 1 值l u k a s i e w i c z 系统中关于v d f 问题的 讨论就可以看出其一斑然而其重要性在于：只要在某l u k a s i e w i c z 多值系统中合 理的v d f 问题能够解决，模糊推理也就在该逻辑系统中得以实现本文的目的 正是要针对一般的l u k a s i e w i c z 多值逻辑的赋值系统瓦研究合理的v d f 问题的 求解方法，这里乩可以代表n 值l u k a s i e w i c z 系统l 。、可数值l u k a s i e w i c z 系 统o ( 赋值域为q n o ，圯q 是有理数集) 或连续值l u k a s i e w i c z 系统厶( 赋值域为 【0 ，1 1 ) 我们将针对不同的情况分析v d f 问题合理性的表现形式，然后基于含有 单个原子的逻辑公式所诱导的m c n a u g h t o n 函数 4 7 - 4 8 】的结构求解v d f 问题 我们证明了在任意的l u k a s i e w i c z 多值系统l 中合理的v d f 问题均可解，从而 证明了模糊推理可以在任意l u k a s i e w i c z 多值逻辑系统中得到实现 概念格，又称g a l o i s 格，是w i u r 于1 9 8 2 年提出的 s l l ，它是由一个三元组 ( g 吖，) 构成，其中，g 为对象集，m 为属性集，j 是g m 上的二元关系 概念格是根据数据集中对象与属性之间的二元关系建立的一种概念层次结构作 为知识分类的一个有力工具，概念格被广泛应用于数据结构分析、知识获取、自 动分类等领域1 5 2 - 5 6 1 至今，关于概念格的理论与应用研究仍然十分活跃i s t - 5 9 】 然而，现实中的对象与属性的并非都是确定的二元关系，更多的是不确定的模糊 关系，因此，各种类型的所谓的模糊概念与构造模糊概念格的方法也纷纷被提出 陋“3 i ，并且这些模糊概念在模糊分类和模糊决策中有着成功的应用【6 4 】 另外，随着信息时代的到来，人们所能获得的信息会越来越多在这种情况 下，如何从众多的信息中挑选重要的对自己有用的信息，即知识约简，就显得十分 重要，至今，也有一些方法讨论关于知识的约简问题，比如，利用r o u g h 集与概 率的方法来约简信息【6 5 】，利用概念格来约简信息的文章也有出现( 6 6 , 6 7 1 本文基 于g f d e l 蕴含算子构造一类模糊概念格，并建立了模糊概念格的属性约简理论， 这里所谓的属性约简是指寻找最小的属性集，它能够完全确定模糊形式背景下的 模糊概念及其层次结构它使得模糊形式背景中隐含的知识的发现更加容易本 文我们首先在s e h o u m i 所提出的模糊概念( 在6 0 ，1 】水平上) 【6 1 】的基础上建 立了基于g s d e l 蕴含算子生成的模糊概念格并给出了模糊概念格的属性约简理论 ( 在d 【0 ，1 1 水平上) ，其次，还给出了判断属性约简( 在6 0 ，1 】水平上) 的方 法，由于不同的属性在约简中所起的作用不同，我们将属性集( 在6 【0 ，1 】水平 上1 分为三部分并给出了他们的判定方法 2 第一章预备知识 本章首先介绍了m v 代数以及l u k a s i e w i c z 多值逻辑系统，然后介绍了经典 的g a l o i s 联络与概念格，为本文的后续部分做好准备 1 1m v 代数 m v 代数理论是与l u k a s i e w i c z 逻辑系统相配套的代数理论，为证明l u k a s i e w i c z 逻辑系统的完备性，c h a n gc c 于1 9 5 8 年提出了m v 代数理论，其定义为 定义1 1 1m v 代数是一个( 2 ，l ，0 ) 型代数( x ，o ，0 ) 满足条件 ( i ) ( x ，o ，0 ) 是以0 为单位的交换半群； ( i i ) x 00 = o ； ( i i i ) ( z ) = z ； ( i v ) ( z o 可) oy = ( y7 0 z ) 7 0 z 设( x ，o ，0 ) 为m v 代数，则( x ，! ) 是一个格，这里z y 由z oy = 0 定 义其实还可以利用0 和在格x 上定义伴随对( + ，一) 命题1 1 2设( x ，o ，7 ，0 ) 为m v 代数，在x 上定义二元运算 与一如 下： ，x + y = ( 茁0 可) ， z 。y = zoy 则( x ，o ，1 ) 是以1 为单位的交换半群，且下面的伴随条件成立： z y s 。当且仅当z sy 。z 这里1 = 0 命题1 1 3在m v 代数中以下性质成立 ( i ) 1 _ z = 茁，x _ 0 = x ，0 x = o ； ( i i ) z y = l 当且仅当x ； ( i i i ) x y = y 一x i ； ( i v ) x 一( y z ) = y 一扛一z ) ； ( v ) z ( y vz ) = ( z + y ) v ( x z ) ； ( v i ) z y az = ( x y ) a ( z z ) ； 3 ( v i i ) 茁ay = z ( x 一可) ； ( v i i i ) 扛一y ) v ( y x ) = 1 ； ( i x ) ( x y ) 一y = x vy ； ( x ) z 一( y vz ) = 江一y ) v 扛一2 ) ； ( x i ) 扛a y ) 一z = ( z 一。) v ( y z ) ； ( x i i ) 扛vy ) 一z = 一z ) a ( y 一。) 例1 1 4 设x = 【0 ，1 ，在x 上规定： zo y = ( z + y ) a1 ，石1 = 1 一x ，z ，y 0 ，1 】 则易证该结构为m v 代数，下称此m v 代数为m v 单位区间 例1 1 1 5 设l 。= o ，击，箬，1 ) ，l q = q n o ，1 ，在k ，l q 定义运算 。0y = + y ) a1 ，。= 1 z ，则l 。，l q 也构成m v 代数 定义1 1 6设x = z 1 ，x 2 ，) u o ，1 ) ，o 与分别是二元与一元运算， 是由x 生成的( o ，) 型自由代数，即 ( i ) xc ； ( i i ) 若，卢 ，则，a ，o z o 卢 ； ( i i i ) 中的元均可由( i ) 与( i i ) 在有限步之内得出 则称 为x 生成的自由m v 代数 c h a n g c c 证明了如下的m v 代数的完备性定理 命题1 1 7一个m v 等式在每个m v 代数中成立当且仅当它在m v 单位 区间中成立 5 1 2l u k a s i e w i c z 多值逻辑系统 l u k a s i e w i c z 形式系统的符号表与公式集分别和二值命题逻辑系统l 的符号 表与公式集相同，推理规则也相同，即为m p 规则其中的公理由以下形式的公 式组成： ( l u l ) a 一( b a ) ( l u 2 ) ( a 日) 一( ( b g ) 一( a e ) ) ( l u 3 ) ( ( a b ) 一b ) 一( ( b a ) 一a ) ( l u 4 ) ( 一a ，、b ) * ( b + a ) 定义1 2 1设fcf ( s ) ，a f ( s ) ，从r 到a 的推演是一个公式的有限 序列a 1 ，a 2 ，a 。满足条件a 。= a ，且对每个公式a i ( i n ) ，a t 是公理或者 4 a f ，或者存在工k 3 ( n n ) 时v d f 的合理性问题，将上述条件改为更一般 的形式，给出了l u k a s i e w i c z 逻辑系统k 中的v d f 同题的合理性定义： 定义2 1 3设= u 1 ，u 一，) cn ，i l 。，i = 1 ，2 ，q ，l 。中的 v d f 问题是合理的，如果以下条件成立i 存在a i f ( s ) ，使得e ( a ) = 啦( 2 1 1 1 ) 4 6 1 中举出反例说明当n 3 时，条件( 2 1 1 1 ) 不可改为条件( 2 1l o ) 并在 此条件下证明了如下结论： 命题2 1 4l ”- ( p 是素数) 中的v d f 问题是可解的当且仅当它是合理的 我们知道，对任意的a f ( s ) ，( ) 的值完全由对每个原子公式的赋值 所确定，而我们的问题是给定了u ；，a i ，问在l 。系统中是否存在公式a ，使得 饥( a i ) = 如基于此考虑，我们自然要从u f 在各个原子公式处的赋值与吼的关系 来考虑v d f 问题的合理性条件了 为在一般的多值系统中求解v d f 问题作技术上的准备，我们撤如下约定： v a l ，啦，a 。k ( 这里l 可以是k 、k 或厶，以下不再声明) ，以 记由g , i ，n 。通过、，一生成的m v 代数即乩中包台 m ，目2 ，一，的最小的m v 代数 4 9 1 如在岛中 = = 0 ，i 1 ，j 1 ，；，1 ) 设m ，n n ，以下分别用( m ，n ) ，【m ，n 1 表示m ，n 的最大公约数和最小公倍数显 9 然，设a ( p a 一，p 。) f ( s ) ，则“。) ，下面 我们给出一般的l u k a s i e w i c z 逻辑系统l 中的v d f 问题的合理性定义 定义2 1 5设e = u 1 ，u 2 ，) cn 啦l 。，t = 1 ，2 ，q ，乩中的 v d f 问题称为合理的，如果以下条件成立； 存在阳，p i 2 ，p l i ( oes ，使得啦 ( 21 1 2 ) 从条件( 2 1 1 0 ) 和( 2 1 1 2 ) 的比较来看，条件( 2 1 1 0 ) 为条件( 2 1 1 2 ) 在n = 3 时 的特例 下面的例子说明了在l 。中，只要通过m 在原子公式处的赋值就很容易利用 ( 2 1 1 2 ) 判断出是否存在公式a 使得蛳( a ；) = a f ， 倒2 1 6 在l u k a s i e w i c z 逻辑系统l 9 中，设= ( “1 ，u 2 ，0 1 = i ，a 2 = j ， 且u l ，地满足v p s ，u l ( p ) = i 1 ，u d p ) = i 1 因为 = ( o i 1 ，；，i ，1 ，l 为映射 “i ：f ( s ) _ ，所以v a f ( s ) ，札1 ( 4 ) ，而口l 隹 ，故不存在公式 a ，使得n 1 ( ) = a l 对于啦，a 2 而言，“2 ( p ) = 5 1 ，； = ( o ， ，一，j 1 ) 取 公式b = ，( 1 p p ) ，则b 满足u 2 ( b ) = 0 , 2 对于l 。和k 而言，由有限多个数生成的子m v 代数的结构比较清楚，结 合初等数论的知识，条件( 2 1 1 2 ) 在k 和l o 中有更直观的表述，我们约定：下 文工。和l o 中的分数都是既约分数下面的定义在后面要用到 定义2 1 7设e = u l ，“2 ，u q ) cn ，口，= l 。，i = 1 ，2 ，q ， k ( l o ) 中的v d f 问题称为合理的，如果以下条件成立： 存在p i l ，p v 2 ，p i f ( i ) s 使得u d p i j ) = 盟m o l n ，满足条件【7 1 l i l ，t t v | i 2 ，m i f o ) 】_ s ；“= l ，2 ，q ；j = 1 ，2 ，( i ) ；觑n ) 如前所述。本章的目的是解决一般系统。中的v d f 问题，从而使得f m p 问 题在l u k a s i e w i c z 逻辑系统中得以实现为此我们在下一节给出有关m c n a u g h t o n 函数的若干引理和一个定理 5 2 2 有关m c n a u g h t o n 函数的若干引理和一个定理 以f ( p ) 记仅由一个原子公式p 生成且满足如下条件的公式的最小集合 ( 1 ) p f ( 此 ( 2 ) 若a ，日f ( p ) ，则1 4 ，a b f ) ； ( 3 ) f ( p ) 中的元都可通过( 1 ) ，( 2 ) 在有限步之内生成 设a ，b f 临) ，在l u k a s i e w i c z 形式逻辑系统中规定 1 0 ao b ：= ( 4 ， 茸) ，a0b ：= 1 a * 口，4 m a o o a 、_ - _ 。_ 。i j m 相应地，在赋值系统l 中有： a b ：= ，( n 、6 ) ，a ob ：= 一o ，b ， 。”：2g 望! ：望哆，m 。：2 9 旦竺：里曼 设a ( p l ，p 2 ，p t ) f ( s ) ，r 是l u k a s i e w i c z 蕴涵算子，“：r ( s ) 一 0 ，1 是 关于r 而言的赋值则u ( a ) = 7 沁( p - ) ，u ( p z ) ，u ( v 。) ) ，这里7 ( u ( p 1 ) ，u ( p 2 ) ，u ( p 。) ) 是通过一与一等将u 1 ) ，u ( m ) ，u ( a ) 连接而成，其方式恰如a 通过，与一 等将p 1 ，p 2 ，p c 所连接的方式由于慨) ( 1 i 茎t ) 可以取f 0 ，l 】中的任何值， 所以当u 在q r 中变化时就有一与a 对应的t 元函数7 ： 0 ，1 一【0 ，1 】为简化 符号起见，以下用页记7 ，则页为a 所诱导的m c n a u g h t o n 函数1 4 8 定义2 2 1 1 4 8 设( a ，b ) n 2 , ：，学【0 ，1 对于公式a ( p ) p ( p ) ，若当 z 0 ，：1 时有再( 。) = 0 ，当z 【警，1 】时有再( z ) = l ，则称公式a ( p ) 分隔i b 和 b + _ l ；如果才( z ) 还满足当茁( ：，警) 时，再( z ) = a x b ，则称公式a ( p ) 严格分 隔和半 f 0 ， 茁【o ，扎 注2 2 2 如果给定了：和i b + l ，虽然由了( z ) = a x b ，z ( ；，：訾) ； l 1 ， z 【世，l 】a 所描述的函数是唯一的，但是与之对应的公式却不唯一，如当a = 3 ，b = 0 时，取 公式a ，b f ( s ) ，其中a = 3 p ，b = 3 p v2 p ( 在l u k a s i e w i c z 形式逻辑系统中， av 日= ( a b ) 一b ，a b = 一( 一av b ) ，下同) a ，b 显然不等，但是可以 f0 ，z = o ； 验证五( 茁) = 百( 。) = 3 x ，z ( 0 ， ) ；成立 【1 ，z 【；，1 】 f 4 7 j 中提出了公式集m = 雒a ( p ) f ( p ) 旧 o ；a ，b n ，并且证明了公式 瑚a ( p ) 严格分隔：和警，即，有如下命题成立： 引理2 2 3 设：q n o ，1 ( o ，b n ，b q ) ，则存在公式禽( p ) m 使相 应的m c n a u g h t o n 函数满足条件： f0 ， 瑶( z ) = a x 【1 ， z o ，：】； b ，z ( i b ，等) z 【警，1 - 显然，当z 乩时下面命题成立： 引理2 2 4 设：q n o ，l 】( ，be n ，b n ) ，则存在公式椰( p ) m 使相应 的m c n a u g h t o n 函数满足条件： 耻隆，ii 辚b ，魁l ； 这里l 为k 或l o 引理2 2 5 1 5 叫设a f ( s ) ，则u ( k a ) = k u ( a ) a1 , u ( 一k a ) = ( 1 一自u ( 4 ) ) v o ，七= 1 ，2 ，- 一，u q 、 又，在厶和三。中，有如下命题成立： 引理2 2 6设u n ，如果存在公式b f ( s ) ，满足u ( b ) = 去( o t 仇) 且( t ，m ) = 1 _ 则存在公式c f ( s ) ，使得“( c ) = 示1 证明 令南= 仉，t l = t ，因为( t ，m ) = 1 ，由辗转相除法知存在8 0 ，s l ，8 k - 1 ( s f n ，i = 0 ，1 ，七一1 ) 使得如下个等式成立： t o = s o t + t 2 ，0 t 2 t 1 ， t k 一2 = 8 k 一2 t k 一1 + t k ，0 “ 一l ， t k 一1 = 8 k l t k + 1 其中0 ”j ( p ) 设u ( p ) = o 墨l ，u j ( p ) = b o ，则存在。n q n o ，1 ) 使得b 鬲n 警曼 o l ，取公式a 甜= a 嚣( p ) ，a j i = 一a 署( p ) ，由引理2 2 4 知： f 0 ， z 【o ，而n nl 。( l o ) ； 瓦( z ) = 礼。一m ，z ( _ i n 等) n l 。( k ) ； 【1 ，z 掣 ，1 n l n ( l q ) 所以札f ( 4 玎) = 1 ，l ( a j i ) = 0 且q ( a j , ) = i ，u j ( a 0 ) = 0 有了以上准备，下面我们给出本章的一个主要结果： 定理2 3 2l 。和l o 中的v d f 问题是可解的当且仅当它是合理的 证明必要性显然成立，只需证明充分性与定理2 2 7 不同的是，这里应 当构造出一个固定的逻辑公式a ，它不随着i 而变，恒有u t ( a ) = a i ( i = l ，2 ，q ) 设= 扣l ，u 2 ，u q cq ，a t l 。( l q ) ，i = l ，2 ，q ，且满足v d f 问 题的合理性定义2 1 7 ，由定理2 2 7 知，对于1 墨i 曼q ，存在公式a ，使得 u i ( a ) = o t ，因为当i j 时钍l q ，由引理2 3 1 知，存在公式a 玎，a 州使得 1 4 “ ( a i j ) = 1 ，u i ( a j i ) = 0 且嘶( 如1 ) = 1 ，u j ( a i j ) = 0 令 a = ( a 1 a a l 2 a a 1 q ) v ( a 2 a a 2 1 a a 2 3 a _ a a 2 q ) v v ( a q a a 9 1 a - 一a a 一1 ) 又因为v u i ，u i ( a i ) = a i ，让t ( a l j ) = 1 ，所以u d a iaa i la a a i i 一1aa i i + l a a 幻) = o t ，当i j 时，u j ( a aa na a a i i laa i t + l aa 幻) = 0 ，因此， 眦( a ) = 啦0 = l ，2 ，q ) 例2 3 3在l 3 l 中，设= a 1 ，u 2 ) cq ，a l = 丽7 ，a 2 = 击，且u l ，“2 满足u l ( p 1 ) = 嘉=