（应用数学专业论文）非经典逻辑代数的粗糙性研究.pdf

西南交通大学研究生硕士学位论文第1 页 摘要 粗糙集理论是波兰科学家z p a w l a k 于1 9 8 2 年提出的一种数据分析理论， 目前已发展成为一种处理模糊和不确定性信息的数学理论，井且成功地应用 于机器学习、模式识别、决策支持、数据挖掘、过程控制等领域 粗糙集理论在数据库知识发现中的应用成功推动了粗糙集理论的研究， 粗糙集的代数结构分析是粗糙集理论研究中最活跃的研究分支之一由于粗 糙集代数具有基本的逻辑代数结构，若能建立粗糙集代数和逻辑代数的联系， 就可以借助已有的逻辑系统的研究结果来讨论粗糙逻辑并深入研究粗糙集的 结构 本文研究粗糙集代数与非经典逻辑代数的关系，将粗糙集理论应用于m v - 代数和代数，讨论其滤子的粗糙性并研究同态映射之下滤子的性质主要 取得了如下的研究结果： 1 从粗糙集的偶序对( ) 表示入手，通过定义偶序对 的基本运算，从而构造出相应的粗代数，进而找到能够抽象刻画偶序对性质 的一般代数结构，比如剩余格，b l 代数，m v - 代数，r o 代数 2 滤子是非经典逻辑代数中的一个基本结构，对于相应逻辑系统的研究 具有重要意义本文将租糙集理论应用于滤子理论，引入了上、下粗糙滤子 的概念，讨论它的基本性质，推广了非经典逻辑代数中滤子的相关性质 3 对于一代数上的同态映射厂，引入了厂的对偶核的概念，并证明了对偶 核是一个滤子 关键词粗糙集；粗糙集代数：非经典逻辑代数；剩余格；滤子 西南交通大学研究生硕士学位论文第页 a b s t r a c t r o u 曲s e tt h e o r yi san e wt h e o r yo fd a t aa n a l y s i s ，i tw a sf i r s tp u tf o r w a r db y p o l a n ds c i e n t i s tz p a w l a k a tp r e s e n ti th a sb e e nd e v e l o p e dt ob ean e w m a t h e m a t i c a lt o o lt od e a lw i t hv a g u e n e s sa n du n c e r t a i n t y i th a sb c e l la p p l i e dt o m a n ya r e a ss u c c e s s f u u yi n c l u d i n gm a c h i n el e a r n i n g ，p a t t e r nr e c o g n i t i o n ，d e c i s i o n s u p p o r t ，d a t am i n i n ga n dp r o c e s sc o n t r 0 1 t h es u c c e s s f u la p p l i c a t i o no fr o u g hs e tt h e o r yt ok n o w l e d g ed i s c o v e r yi n d a t a b a s ep r o m o t e st h es t u d yo f r o u g hs e tt h e o r y a l g e b r a i ca n a l y s i so f r o u g hs e ti s o n eo ft h em o s ta c t i v eb r a n c h e si nt h er e s e a r c ho fr o u g hs e tt h e o r y i ft h er e l a t i o n b e t w e e nr o u g ha l g e b r aa n dl o s i ca l g e b r aw a sg i v e n ，w ec o u l dr e s e a r c ht h er o u g h i o g i cu s i n gt h ec o n c l u s i o no f l o s i cs y s t e ma n ds t u d yt h es t r u c t u r eo f r o u g h s e t 刚sp a d e rs t u d i e st h er e l a t i o n s h i pb e t w e e nr o u g hs e ta l g e b r aa n dn o n c l a s s i c a l l o g i ca l g e b r a , a n da p p l y sr o u g hs e tt h e o r yt om v - a l g e b r aa n dr o - a l g e b r a n ” r o u g h n e s so f f i l t e ri ss t u d i e d t h em a i nc o n c l u s i o n sa r ea sf o l l o w i n g ： 1 b a s e do nt h ed e s c r i p t i o no ft h e p a i r s ( ) o fr o u g hs e t ，w e d e f i n es o m eb a s i c o p e r a t o r s o nt h e a p p r o x i m a t i o np a i r sa n dc o n s t r u c ts o m er o u g ha l g e b r a s s o m eg e n e r a la l g e b r a s s t r u c t u r ew e r es e l e c t e dt od e s e r i b l et h ep a i r so fr o u g hs e t ，f o re x a m p l e ，r e s i d u a t e d l a t t i c e ，b l - a l g e b r a , m v - a l g e b r aa n dr o - a l g e b r a 2 i nn o n - c l a s s i c a li o s i ca l g e b r a sf i l t e ri sab a s i cs t r u c t u r ea n di tp l a y sa n i m p o r t a n tr o l ei nt h er e s e a r c ho f r e l a t i v el o s i cs y s t e m i nt h i sp a d e r , t h en o t i o n so f u p p e ra n dl o w e rr o u g hf i l t e r sw e r ei n t r o d u c e d w i t ht h e i rb a s i cp r o p e r t i e sb e i n g d i s c u s s e d 3 f o rh o m o m o r p h i s mo f r 0 a l g e b r a , w ei n t r o d u c et h en o t i o no fd u a lk e r n e la n d h a v ep r o v e dt h a te a c hd u a lk e r n e li sa 丘l t e r k e y w o r d s ：r o u g hs e t ；r o u g hs e ta l g e b r a ；n o n c l a s s i c a ll o g i ca l g e b r a s ；r e s i d u a t e d l a t t i c e ；f i l t e r 西南交通大学硕士研究生学位论文第1 页 第1 章绪论 本章将介绍本文的写作背景并简要介绍本文的主要研究工作 1 1 粗糙集理论概述 二十世纪七十年代初，波兰科学学院、华沙大学的学者组成了研究小组， 开始了对信息系统逻辑特性的长期基础性研究针对从实验中得到的以数据 形式表述的不精确、不确定、不完整的信息和知识进行分析，这一研究成为粗 糙集理论产生的基础1 9 8 2 年z p a w l a k 发表了经典论文r o u g hs e 印，宣告了 粗糙集理论的诞生由于最初的研究大多是以波兰文发表的，因此在当时并 未引起国际学术界的重视，研究地域局限于东欧各国，到了八十年代末，这一 理论终于引起了各国学术界的注意，许多数学家、逻辑学家和计算机研究人员 对粗糙集理论和应用产生极大兴趣并做了大量研究工作，1 9 9 1 年z p a w l a k 出 版的专著”r o u g hs e t ”f l q 成为粗糙集理论研究的第一个里程碑1 9 9 2 年应用专 著f 2 1 的出版对这一时期的工作成果作了极好的总结，也进一步促进了粗糙集 理论的应用扩展1 9 9 2 年，第一届关于粗糙集理论的国际学术会议在波兰召 开；1 9 9 5 年，a c mc o m m u n i z a t i o n 将其列为新浮现的计算机科学的研究课题； 1 9 9 8 年，国际信息科学杂志( i n f o r m a t i o ns c i e n c e s ) 还为粗糙集理论的研究出 了一期专辑这些表明了粗糙集理论与应用的研究有着广泛的发展前景 对于粗糙集的概念，目前研究者从不同的角度来定义：一种就是原始的 p a w l a k 1 意义下的，也有由上、下近似构成的一对集合来命名的【z j ，还有以下 近似和上近似构成的区间集( 集合类) 来定义的【2 ”，定义观点的不同往往带 来研究的侧重面的不同目前，对粗糙集理论的研究主要集中在：粗糙集的 模型的推广，问题的不确定的研究，与其他处理不确定性，模糊性问题的数学 理论的关系与互补，纯粹的数学理论方面的研究，粗糙集的算法研究等这些 研究有的是受应用的推动而产生，有的是纯理论的 1 1 1 粗糙集模型的推广 p a w l a k 粗糙集模型的推广一直是粗糙集理论研究的主流方向为了拓广 粗糙集的应用范围，人们提出了各种形式的推广模型，如一股二元关系下的 粗糙集模型、变精度粗糙集模型、模糊粗糙集模型、概率粗糙集模型等 1 1 2 不确定性问题的理论研究 粗糙集理论中知识的不确定性主要由两个原因产生：一个原因是直接来 自于论域上的二元关系及产生的知识模块，即近似空间本身从这个角度看， 西南交通大学硕士研究生学位论文第2 页 处理知识的不确定方法往往用信息熵来刻画，知识的粗糙性实质上是其所含 信息多少的更深层次的刻画，不少学者在这方面做了研究工作【1 嵋粗糙集 理论中知识不确定性的另一个原因来自于给定论域里粗糙近似的边界，当边 界为空集时知识是完全确定的，边界越大知识就越粗糙或越模糊，一些学者 引进了粗糙熵e ( x ) 的概念来刻画x 的不确定性【】6 j 寻求一个合适的度量来刻画知识的不确定性也是粗糙集理论研究的一个 重要方向 1 1 3 粗糙集与其他处理不确定性理论的关系 粗糙集理论与其他处理模糊性或不确定性方法的关系研究，主要集中在 它与概率统计、模糊数学、d s 证据理论和信息论的相互渗透与补充 在信息系统中，知识库的知识的类型一般有两类：一类是知识库中所有对 象的描述是完全已知的，p a w l a k 粗糙集模型和一般关系下的粗糙集模型就是 属于这一类；另一类是知识库中的对象的描述只有部分是已知的，只能通过训 练样本所提供的信息类刻画概念，抽取样本时应符合统计规律性，因此概率 统计与粗糙集理论的结合就显得非常自然 模糊集理论和粗糙集理论在处理不确定性和不精确性问题方面都推广了 经典集合论具有一定的相容性和相似性，然而它们的侧重面不同模糊集通 过对象关于集合的隶属程度来近似描述，而粗糙集通过一个集合关于某个可 利用的知识库的一对上、下近似来描述；模糊集强调边界的不分明性，而粗糙 集强调对象间的不可分辨性；模糊集研究的是不同对象间的隶属关系，粗糙集 研究的是不同类中的对象组成的集合关系；模糊集的隶属函数大多是由专家 凭经验给出。带有很强的主观性，而粗糙集的粗糙隶属函数的计算是从被分 析的数据中直接获得的，相对客观目前所见的模糊粗糙集模型垆，6 ，1 4 j 和粗糙 模糊集模型是二者结合的成功范例 粗糙集理论与d s 证据理论在处理不确定性问题时方法是不同的，但却 有某种相容性粗糙集理论中的下近似和上近似的概率恰好分别是d s 证 据理论中的信任函数和似然函数【2 “，然而生成信任函数和似然函数的基本概 率分配函数( 即1 l a s s 函数) 方法是不同的，前者来自于系统中数据本身，比 较客观，而后者往往来自于专家的经验，带有很强的主观性，粗糙集理论与 d s 证据理论有很强的互补性 1 1 4 算法研究 粗糙集理论中有效算法研究是粗糙集在人工智能领域研究的一个主要方 向粗糙集理论在人工智能的应用上主要有两大类：一类是无决策的分析，内 容主要包括数据压缩、约简、聚类与机器学习等；另一类是有决策分析，内容 主要包括决策分析、规则提取等，也涉及对原始数据的预处理，如数据压缩与 约简等目前，粗糙集理论中有效算法研究主要集中在导出规则的增量式算 西南交通大学硕士研究生学位论文 第3 页 法，约简的启发式算法，粗糙集基本并行算法，以及与粗糙集有关的神经网络 与遗传算法等【8 】这些研究的成功应用有的已经获得了商业价值 1 1 5 租糙集与其他数学理论的联系 随着对粗糙集理论研究的不断深入，它与其他数学分支的联系也更加紧 密例如，从算子的观点看粗糙集理论，它与拓扑空间、数理逻辑、模态逻辑、 格与布尔代数、算子代数等联系较为紧密；从构造性和集合的观点来看，它与 概率论、模糊数学、证据理论、图论、信息论等联系较为密切粗糙集理论研 究不但需要以这些理论作为基础，同时也相应地带动这些理论的发展 目前，数学理论与粗糙集理论结合起来进行研究已有文章出现，如“粗糙 逻辑” 1 1 , 1 3 “粗糙理想”、“粗糙半群”【1 0 】等等随着粗糙结构与代数结构，拓 扑结构，序结构等各种结构的不断整合，必将涌现出新的富有生机的研究方 向 作为人工智能和认知科学中新的研究热点，粗糙集理论的有效性己被计 算机学科的基础研究人员所认可目前，粗糙集理论已经在机器学习、知识 获取、决策分析、数据库知识发现、专家系统、决策支持系统 1 2 , 3 8 , 2 1 】、归纳 推理、模式识别、智能控制等领域得到了广泛应用到目前为止，关于粗糙集 理论与应用方面的文章很多，有关书籍也正在陆续出版一些粗糙集理论与 应用综述方面的文章详细介绍了粗糙集理论在各个阶段理论研究与应用研究 方面的成果 1 2 本文的写作动机 在粗糙集的理论研究中，粗糙集的代数结构分析是最为活跃的研究分支 之一粗糙集在数据库知识发现中的成功应用推动了粗糙集理论的研究，许 多学者用代数的方法对粗糙集理论进行了研究【1 0 那挪】，主要有以下两种方 法一种是将近似算子作为基本概念，在一些代数结构中定义出两个近似算 子并用公理进行刻画加拿大学者y a o 3 6 将粗糙集理论解释为集论的扩展， 即把近似算子看成集论上添加的一元算子，即在集合代数系统( 2 “，n ，u ， ) 上 引入近似算子工和日，从而构造出称为粗糙集代数的系统( 2 ”，n ，u ， ，l 日) ， 这种解释与将模态逻辑解释为在经典逻辑上增加两个一元算子是一致的进 一步的，将集合代数抽象成布尔代数，挪威学者j a r v i n e n 基于原子布尔代数， 通过原子定义了下近似与上近似9 1 ，文献 2 3 】还将分子格引入到粗糙集研究 中，构造了基于分子格的粗近似结构，从而实现了对粗糙集的进一步推广；另 西南交通大学硕士研究生学位论文第4 页 一种方法则是从粗糙集的偶序对( 下近似集，上近似集) 表示入手，通过定义偶 序对的基本运算，从而构造出相应粗代数，并寻找能够抽象刻画偶序对性质 的一般代数结构如波兰学者p o m y k a l a 等人的s t o n e 代数【2 8 1 ，c o m e r 的正则 双s t o n e 代数【捌，印度学者b a n e r j e e 的预粗代数【3 2 1 ，意大利学者p a g l i a n l i 的 半单n e l s o n 代数t 3 1 等 非经典逻辑代数研究是人工智能基础理论研究的一个热门方向人们基于 不同的角度提出了多种形式的非经典逻辑代数并对相应的逻辑系统进行了深 入研究由于粗糙集代数具有基本的逻辑代数结构，若能建立粗糙集代数和 逻辑代数的联系，就可以用已有的逻辑系统的研究结果来讨论粗糙逻辑并深 入研究粗糙集的结构秦克云【4 8 】将粗糙集代数构造成格蕴涵代数，其主要结 论是在适当选取蕴涵算子和余运算之后粗糙集代数成为格蕴涵代数另外， 文献 3 5 】将粗糙集理论和格蕴涵代数结合，讨论了格蕴涵代数中滤子的粗糙性 问题 剩余格是一种有着广泛应用的逻辑代数，具有丰富的运算和良好的性质， 另外，其它的一些逻辑代数，如次b l 代数，b l 代数，m t l - 代数，m v - 代数等 都可以通过在剩余格上附加一些条件后得到，即，它们是特殊的剩余格因 此，粗糙集代数与剩余格的关系研究具有特殊意义本文打算首先研究粗糙 集代数和剩余格的关系，并进而讨论粗糙集代数和其它一些逻辑代数的联系 以及非经典逻辑代数中的粗糙性问题 1 3 本文的研究结果 本文研究粗糙集代数与非经典逻辑代数的关系，将粗糙集理论应用于m v - 代数，讨论其滤子的粗糙性并研究同态映射之下滤子的性质：主要取得了如 下的研究结果： 王 l 从粗糙集的偶序对代下近似集，q 近似集 ) 表示入手，通过定义偶序对 的基本运算，从而构造出相应的粗代数，进而找到能够抽象刻画偶序对性质 的一般代数结构，比如剩余格，b l 代数，m v _ 代数，代数 2 滤子是非经典逻辑代数中的一个基本结构，对于相应逻辑系统的研究 具有重要意义本文将粗糙集理论应用于滤子理论，引入了上、下粗糙滤子 的概念，讨论它的基本性质，推广了非经典逻辑推代数中滤子的相关性质 3 对于 v i v v ：- 代数和r o - 代数上的同态映射厂，引入了厂的对偶核的概念，并 证明了对偶核是一个滤子 西南交通大学硕士研究生学位论文第5 页 第二章粗糙集基本知识 本章介绍p a w l a k 标准粗糙集理论的基本概念与基本结论，作为后面各章 节的基础 2 1 p a w ia k 粗糙集模型及知识约简 p a w l a k 的基于等价关系的粗糙集模型是粗糙集理论的基础，其它模型都 是在该模型的基础上进行推广得到的；知识约简是在保持知识库分类能力不 变的条件下，删除其中不相关或不重要的知识，它是粗糙集理论的核心内容 之一，本节介绍p a w l a k 粗糙集模型的基本概念与基本结论 2 1 1 知识与知识库 粗糙集理论认为知识是对对象进行分类的能力，设所讨论的对象的集合为 u ，称( ，为论域若x u ，则称x 为一概念( 形式概念) 若干概念构成 的集合称为一个知识以下仅讨论对论域u 形成划分的知识，因此，一个知 识就是u 上的一个等价关系称二元组k = ( u ，r ) 为一个知识库，其中u 为 论域，r 是u 上的若干等价关系构成的集合 对于知识库k = ( u ，r ) ，若p r 且p a ，则n p 称为p 上的不可区分 关系，记为删( p ) ，即i n d ( p ) = n p 对于x u ，r r ，记i x 口= 抄u ；( x ，y ) g r ) 为x 在r 之下的等价类商 集u r = 扛k ；善中元素称为r 初等概念对于尸r ，显然有 【明w ( ，) = 0 陋k ，商集u 砌( p ) 称为【，关于p 的基本知识，也称为p 基本集， 其中元素称为p 基本概念 设k = ，p ) ，k = ( u ，q ) 是【，上的两个知识库，若i n d ( p ) c i n d ( q ) ，则 西南交通大学硕士研究生学位论文第6 页 称p 比q 细，或q 比p 粗此时，每一个q 等价类是若干p 等价类之并若 i n d ( p 1 = i n d ( q ) ，则称足与k 等价，记为k 兰k 2 1 2 约简与相对约简的概念 设k = ，r ) 是一知识库，p 酞称p p 为p 中不必要的，若 i n d ( p ) = i n d ( p 一 办) ；否则称p 为p 中必要的若任一p p 是p 中必要的， 则称p 为独立的，否则称p 为依赖的 定理2 1 2 1 若尸是独立的，q p ，则q 是独立的 若o c _ p ，且q 是独立的，砌( p ) = i n d ( q ) ，则称q 为p 的一个约简于 是，q c _ p 为尸的约简当且仅当q 是满足i n d ( p ) = i n d ( q ) 的极小集p 的所有 约简构成的集合记为r e d ( p ) p 中所有必要元素构成的集合记为c o r e ( p ) ，称 为p 的核 定理2 1 2 2 c o r e ( p ) ：n r e d ( p ) 由此定理，核这个概念有以下两个特点：首先，它可以作为所有约简的 计算基础因为核包含在所有约简中；其次，可解释为在知识约简时，它是 不能消去的知识特征集合 例2 2 设k = ，r ) 是一知识库，其中u = 1 1 s i 8 ) ， r = r if l i 3 ) 满足u 届= “，x 4 ，墨) ， 而，毛 ， 而) ， 矗，而 ， u 恐= 五，而，x s ， 氏) ， 而，x 4 ，x 7 ，) ， 【厂马= “五，墨， 气， 而，x 7 ，黾) ， 玛，五) ) 于是u i n d ( r ) = 而，墨) ， x 2 ，黾 ， 而) ， - ， ， 而 ) 而 u i n a ( e k ，马 ) = “五，墨 ， 恐，而，魄 ， 而) ， ， u i n d ( r ) ， 西南交通大学硕士研究生学位论文第7 页 u i n , t ( 佩，恐) ) = u 砌( 蜀，是) ) = u 砌( r ) 故r e d ( r ) = f 蜀，是) ， 墨，玛) ) ，c o r e ( r ) = 墨) 在应用中，一个分类相对于另一个分类的关系十分重要，因此我们将介 绍知识的相对约简( r e l a t i v er e d u c t ) 和相对核( r e l a t i v ec o r e ) 的概念 首先定义一个分类相对于另一个分类的正域 令p 和q 为等价关系族，q 的户正域记为p o s ，( q ) ，即 p o s p ( q ) = u 丛 x s u ，q q 的p 正域是u 中所有根据分类u p 的信息可以准确地划分到关系q 的等价类中去的对象集合 令p 和q 为等价关系族，r p ，如果 p o ( ，) ( i n d ( q ) ) = p o s i 耐( p - 异 ) ( 折j ( q ) ) ， 则称只为p 中q 不必要的；否则r 为p 中q 必要的 为简单起见，我们也用p 傩，( q ) 代替p 傩。( 尸) ( 加d ( q ” 如果尸中的每个r 都为q 必要的，则称p 为q 独立的( 或p 相对于q 独 立) 设s p ，s 为尸的q 约简当且仅当s 是p 的q 独立子族且 p o s 。( q ) = p o s ，( q ) p 的q 约简简称为相对约简 p 中所有q 必要的原始关系构成的集合称为p 的q 核，简称为相对核， 记为c o r e a ( p ) 定理2 1 2 3 删c o r e o ( e ) = n r e d q ( p ) ，其中r e d e ( ? ) 是所有p 的q 约简 构成的集合 西南交通大学硕士研究生学位论文第8 页 定理2 1 2 4i 殳p , q 是u 上的等价关系族，则s p 是p 的q 2 2 9 简当且 仅当s 是p 的q 独立子集且对于任意x e u q 有互x ) = 墨( x ) 2 2p a w ia k 粗糙集模型上、下近似的定义及相关性质 设u 是一个集合，r 是u 上的个等价关系，称( u ，r ) 为以p a w l a k 近似 空间对于任意x u ，x 关于近似空间( u ，r ) 的上、下近似分别定义为： _ n x = 川i x 月研“， n ( x ) = x i 【x k n x a ) 令。表示空集，x 表示u 中x 的补集那么下面是p a w l a k 粗糙集的 一些性质： ( 1 l ) 星( 【，) = u ，( 1 h ) r ( = u ；( 2 l ) 凰o ) = o ，( 2 h ) r ( o ) = o ； ( 3 l ) 型x ) x ，( 3 h ) x r ( x ) ；( 4 l ) 墨( x ny ) = 互x ) n 星( y ) ， ( 4 1 i ) n ( xu1 3 = n ( x ) ur ( y ) ；( 5 l ) 墨( 显( j ) ) = 星( x ) ，( 5 t t ) r ( r ( x ) ) = r ( x ) ； ( 6 ) 点( 柳一尺( z ) ，r 卜石) 一星) ； ( 7 l ) x y 型x ) 豇】，) ，( 7 h ) x y j r ( x ) r ( y ) ： ( 8 l ) 星( ( x ) ) = 一旦( x ) ，( 8 h ) r ( r ( x ) ) = r ( x ) ： ( 9 l ) v k e u r ，墨( k ) = k ，( 9 h ) v k u r ，r ( k ) = k 容易看出，( 3 l ) ，( 4 l ) 和( 8 l ) 是下近似的基本性质，( 3 h ) ，( 4 h ) 和( 8 h ) 是 上近似的基本性质 定理2 2 1 ”1 ( 1 ) x 为r 可定义集骨墨( x ) = r ( x ) ； ( 2 ) x 为r 不可定义集型x ) r ( x ) 西南交通大学硕士研究生学位论文第9 页 集合( 范畴) 的不精确性是由于边界域的存在而引起的集合的边界域 越大，其精确性越低，为了更精确地表达这一点，我们引入精度地概念由 等价关系r 定义地集合z 的近似精度为 = 矧， 其中x a ，l x i 表示集合x 的基数 精度叫z ) 用来反映我们对于了解j 的知识的完全程度显然，对每一个 r 和x u 有0 烈x ) 1 当烈x ) = 1 时，x 的r 边界域为空集，集合x 为r 可定义的；当烈x ) 1 时，集合x 有非空r 边界域，集合x 为r 不可定义的x 的r 粗糙度p ( x ) = i - 似石) ，它表示集合x 的知识的不完全程度 定理2 2 2 设，r ) 构成了p a w l a k 近似空间，石y u ，则 ( 1 ) 星( x u l ，) = 星y u 掣甘墨( ( z 一星y ) u 0 - 星功) = o ， ( 2 ) 页( y n 】，) = 页x n 页i ，车事星( ( 夏x x ) u i 夏l ，一】，) ) = a 证明( 1 ) ( 仁) 坛星( z u y ) 有i x 。x u y ，假设 工】 旺x 且 i x 旺y ，v 嘲r x u r ，贝l j y e z 或y e y ，又因为【y 】 = m r 旺x ， y k = x k 旺y ，所以y 芒_ r x j l y e _ r r ，从而y 石一些或y y 一掣，由y 的任意性知 x 】。( x 一鱼) u ( 】，一鱼r ) ，矛盾所i x 。x 或吲。y ，那 么工丛或x e 秽，则x 墅u 矽，从而星( 石u 】，) 躺u 秽， 又因为 星( x ur ) 2 星y u 掣，故星( x u 】，) = 星x u 矽 ( ) 假设( x 一星r ) u ( y 一含有等价类】。，则 【】月( x 一_ r x ) u ( y 一鱼l l ，) ，由此可知 kex u y ，那么x 。堡( x uy ) ， 西南交通大学硕士研究生学位论文 第1 0 页 又假设x o 丝，那么】a _ r x ，则 粕】 n ( x 一些) = f 2 j ，又因为 i x 。】。( x 一星j o u ( z - l 2 a 9 ，则 粕】。y 一矽，事实上，y - 掣不含有等 价类，矛盾因此正_ r x ；同理仨_ r y 所以芒p d c u _ 盯，又因为 x 。_ r ( x u r ) ，这与星( 工u 功= 酗u 掣矛盾 因此墨( ( x 一：6 ) u ( y 一：6 ) = 0 ( 2 ) 证明类似于( 1 ) 的证明 文献 3 给出粗糙集不等式： p ( x uy ) l r x u e o 悔p ( x ) l r x l + p ( n i 盯l - p ( x n r ) i 兄r n 魁1 规定瓦r = a 时，p ( 们= 0 上述不等式两边取等号的充要条件为： p ( x uy ) l r x u r r l _ p ( x ) i r x l + p ( y ) l r 】，i p ( 彳n 聊l r x n e d 铮 l 丛髟卜i a ( 删y ) h 面n 盈嘴i 墨x x n n r y ) ) l f 1 ) 定理2 2 3 设( u ，r ) 构成了p a w l a k 近似空间，五y b r ，若 g ( x u l 0 = _ r x u _ e d 砸( x n y ) = 面n 盈，则( 1 ) 式中等号成立 证明( 1 ) 式左边= i 些i + l 掣卜i 丝u 拶 = i 丛l + i 矽l i 丛l l 斟l 十i 星( x n 】，) i 爿星( x n 】，) i ， ( 1 ) 式右边= i 砑n 面1 边，证毕 熙：l 面n 盈l 1 贰x n i f ) i 。! 垡墨哩! ：i _ r ( x n y ) i ：左 l r x n r y i 西南交通大学硕士研究生学位论文第11 页 第三章粗糙集代数与非经典逻辑代数 粗糙集理论在数据库知识发现中的成功应用推动了粗糙集理论的研究，粗 糙集的代数结构分析是粗糙集理论研究中最活跃的一个分支，许多学者用代 数的方法对粗糙集模型进行了研究若能建立粗糙集理论与逻辑代数的联系， 就可用已有的关于非经典逻辑的研究结果讨论粗糙逻辑，文献【4 8 】建立了粗糙 集代数与格蕴涵代数之间的联系，本章试图研究粗糙集代数与其他的非经典 逻辑代数的联系 3 1 粗糙集代数的概念与性质 3 1 1 构造性方法中的粗糙集代数 在粗糙集理论中，下近似与上近似并非最基本的概念，它们被论域u 上 的二元关系，论域的划分或覆盖，对象的邻域及偏序，格，布尔代数等等更 为基本的概念所刻画，我们称沿着这条技术路线研究粗糙集的方法为构造性 方法下面给出构造性方法中粗糙集代数的定义 定义3 1 1 1 【2 7 】算子厶h ：2 “- 2 “称为是对偶的，如果对w u ， ( 厶) l 4 = h a ， ( 三毛) h a = l a 定义3 1 1 2 2 7 】设r 是u 上的二元关系，下面的等式定义了一对对偶近似 算子r 和r r x = 扛l v y e x r y jj ，朋) = 扛i 墨( 工) x r x = 缸f 3 y x r y ，y 柳 = 缸f 足( 工) n x 彩 西南交通大学硕士研究生学位论文第12 页 称系统( 2 “，n u ，足月) 为一个粗糙集代数，这里n ，u 和分别指集合 的交，并和补运算 3 1 2 公理化方法中的粗糙集代数 粗糙集的公理化方法把下近似和上近似算子视为最基本的概念，将注意 力放在研究粗糙集时产生的代数系统上，利用一个公理集来刻画上、下近似 算子，揭示公理集与此条件下所产生的代数系统之间的联系下面给出公理 化方法中的粗糙集代数的定义 定理3 12l 【2 7 】设厶h ：2 u _ 2 “是一对对偶的一元算子，则存在一个【厂上 的二元关系r 使得埘= r x ，h x = r x 对任意集x e 【，都成立的充分必要 条件是上和日满足性质： ( 三1 ) l u = u ( 厶) l ( x r 、d = 必n 三y ( 羁) 日o = o ( 皿) h ( x uy ) = h x u 唧 定义3 1 2 2 1 2 7 设厶h ：2 “一2 ”是一对对偶算子，如果三满足公理( 厶) 和( 厶) ，或者等价地，日满足( 蜀) 和( h d ，则系统( ，n u ，厶日) 称为一 个粗糙集代数，l ，日称为近似算子 在粗糙集的公理化方法中，基本概念是系统( 2 ”，n ，u ，l ，日) ，这里 ( ，n ，u ， ) 是集代数，厶h ：2 ”- 2 ”是两个一元算子，它们被一些公理所定 义而非联系于二元关系 3 2 粗糙集代数与基于剩余格的非经典逻辑代数 剩余格是当今较为流行的一种非经典逻辑代数，是j p a v e l k a 为了研究模 西南交通大学硕士研究生学位论文第13 页 糊逻辑而提出的，另外，次b l - 代数，b l - 代数，m v 一代数，弱r 0 - 代数和一 代数等都是特殊的剩余格，因此，若能建立粗糙集代数与剩余格以及基于剩 余格的非经典逻辑代数之间的联系，就可以借助已有的关于非经典逻辑代数 的研究结果讨论粗糙集代数等价关系在粗糙集代数中起着关键作用，其近 似算子完全由相应的等价关系确定，论域上并无其他附加结构，因此，在非 经典逻辑代数上可以通过常规方法构造粗糙集代数本节研究由粗糙集代数 构造基于剩余格的非经典逻辑代数的方法，证明了在适当选取算子之后，粗 糙集代数就成为某一种非经典逻辑代数 下面给出剩余格的概念与性质 定义3 2 1 5 l j 设工为偏序集，固与- 为工上的二元运算，如果满足条件： ( 冠)固：l x l - l 关于两个变量都是单增的； ( j 屯) x o y z 幸争工y z ， x ，y ，z l ； ( 恐) * l x l _ 关于第一变量不增，关于第二变量不减 则称固与_ 互为伴随，( 固，- ) 称为三上的伴随对 定义3 2 2 【5 1 】设，v ， ，o 1 ) 为有界格，固与一为l 上的二元运算， ( l ，v ，a ，固，_ ，0 ，1 ) 叫剩余格，如果下列条件成立： ( 兄) ( 厶o ，1 ) 是以l 为单位元的交换半群； ( 兄) ( o ，) 是上上的伴随对 定义3 2 3 【5 1 1 设( 厶v ，a ，o ，- ，0 ，1 ) 为剩余格，定义上的一元运算如下： ( 见) 一= x 一0 ，工l 称为上的伪补运算，剩余格三称为正则的，如果下述条件成立： ( 马) x n = ( 功与【，x l 设u 是一论域( 非空有限集) ，其幂集布尔代数( 以u ) ，u ，n ，9 ，u ) 的任 意子代数a = ( 4 ，u ，n ，a ，u ) 称为近似代数4 的原子集( 记为a t o m ( a ) ) 恰 西南交通大学硕士研究生学位论文第14 页 好构成论域u 的划分，令 s = u 循：e a t o m ( a ) ，i e 卢1 ) ； 个s = x ：x a ，x 2 s 设口是4 上的如下定义的同余关系：对于任意x ，y a ，嬲7 当且仅当， 存在z 个s ，使得x n z = y n z ，于是有，x 鲫当且仅当x 2 s ，令 p ( 一) = ( x 1 ，x 2 ) ：x 1 ，x 2 a ，x tn x 2 = o ，x lu x 2 鲫 称( ( 4 ) ，v ，a ，_ ，1 ，1 ，o ) 为粗糙集代数，其中： ，v ，_ 为n o ( 4 ) 上的二 元运算，、为 0 ( 彳) 上的一元运算；l = 口，o ) ，0 = ( a ，u ) ，运算的定义如下： 对于任意( x ，x ：) ，( 五，e ) 。( 4 ) ， ( x 。，鼍) v ( k ，e ) = ( x l u k ，x 2 n e ) ； ( 墨，砭) ( k ，k ) = ( 五n x ，五u e ) ； ( 五，五) _ ( x ，e ) = 卜五u k ，五n 墨) ； 弋墨，x ：) = ( 蜀，x 。) ； ( 置，置) = ( x ：，x 。) 容易验证上述定义的合理性，且( 以( 4 ) ，v ，a ，l ，o ) 是一个有界分配格在此 格中序关系为( x ，五) ( k ，e ) ，当且仅当 蜀量】j ；，墨x 2 对于近似代数a = o ，u ，n ，o ，u ) ，由a t o m ( a ) 确定了u 上的一个等价关 系r a ，可以证明，( 墨，置) k ( 4 ) 当且仅当存在x u 使得墨= 也( x ) ， 西南交通大学硕士研究生学位论文第15 页 五= r 。( x ) 因此，坼似) 为e 之下所有粗糙集的集合 为构造剩余格，在此格中定义二元运算j ，固和一元运算如下： a j b = 0 - 6 ) ( b - 口) ：a 0 6 = j 加：d a 可以验证： ( 五，五) j ( x ，墨) = ( 卜u k ) n ( e u 五) ，k n k ) ： ( x i ，五) 固( x ，砭) = ( 五n i ，( 五u k ) n ( k u 五) ) 定理3 2 1 在( ( 彳) v ， ，o ，j ，0 中，下列性质成立： ( 1 ) x y 蕴涵石j y = 1 ； ( 2 ) j y ) j y = j 功j 工； ( 3 )若x ，y ，z x ，r x 尸( x ) 如下： v s 尸( x ) ，反( s ) = 工x r x p s ，p ( s ) = x x ie x p n s a ) ，称n ( s ) 为s 的下近似集，称p 为占的上近似集，如果a c p ( d ，则 p ( s ) = ( 成( s ) ，p ( s ) ) 称为p ( 工) p ( x ) 上的相对于p 的粗糙集 如果s x ，并且a ( s ) = p ( s ) ，则称s 为可定义的，偶序对( z ，p ) 称为 近似空间 定理4 1 2 1 t 1 1 设p 和五是x 上的同余关系，那么： ( i ) ( p ( z ) ) ，以( 刃f e p + ( 刃) ； ( 2 ) ( v f ，g 尸+ ( x ) ) ，( p + ( f u g ) = p ( f ) w p ( 鳓 ( 3 ) ( v f ，g 尸( j = i ) ) ，( 反( ，n 回= a ( f ) n a ( g ) ) ( 4 ) ( v ，g p ( x ) ) ，( f e g j a ( f ) a ( g ) ) ( 5 ) ( v f ，g p ( x ) ) ，旷g ：，户( ，) p + ( g ) ) ( 6 ) ( v f ，g 尸( x ) ) ，( n ( ，) u 肛( g ) a ( ，u g ) ) ( 7 ) 尸，g p ( x ) ) ，( p ( f c 、g ) = ( f ) c a p ( g ” ( 8 ) ( v p 尸( 工) ) ，( a c p = ，丑( ，) 吨( ，”，p 。( ，) ( f ) 推论4 1 2 2 如果p 与丑为石上的同余关系，那么： ( ，( 彳) )“p n 句旷) = 伊) n 五) ) 西南交通大学硕士研究生学位论文第2 5 页 ( ( v f j r ( x ”( p o ( f ) n 五( g ) ( p n 名) ( f ) ) 证明：由定理4 1 2 1 立即可得 对于任何v f ，g p ( z ) ，我们定义f g = a b i a ef b g 定理4 1 2 3 如果p 为上的同余关系，那么： ( r e ，g f ( x d ( ( p ( ，) ) o ( p ) ( g ) p ( 尸o g ” 证明：设c e ( 户( ，) ) o ( g ) ，那么存在d e 矿( f ) ，6 e p ( g ) 满足 c = o b ，由此可得有工，y x ，使得x e l n f ，y 【6 ln g 因而 一o y ( 吐) o 【6 k = k 0 6 l ，x $ y e f s g ，功；即f o y e b p n ( f o g ) ，这样就有c = d $ b ep ( p e g ) ，故p + ( f ) ) o ( g ) 户( f o g ) 定理4 1 2 4 如果p 是z 上的同余关系，那么： ( v f ，g ep ( x ) ) ( p ( p e g ) 0 j ( n ( d ) o a