基于代数结构的商空间模型研究

陈林书，王加阳，杨正华，李 力

（1.中南大学信息科学与工程学院，湖南长沙410083；2.湖南科技大学计算机科学与工程学院，湖南湘潭411201；3.哈尔滨工业大学深圳研究生院，广东深圳518055）

基于代数结构的商空间模型研究

陈林书1，2，王加阳1，杨正华1，李 力3

（1.中南大学信息科学与工程学院，湖南长沙410083；2.湖南科技大学计算机科学与工程学院，湖南湘潭411201；3.哈尔滨工业大学深圳研究生院，广东深圳518055）

现有商空间模型中论域结构一般被指定为拓扑结构，问题的粒度由等价关系唯一地确定.当论域结构由拓扑结构变成应用广泛的代数结构时，引入同余关系的概念，系统地论证了两个重要结论在基于代数结构的商空间模型中依然成立，即全体同余关系构成的完备半序格和保假，保真原理的存在性.而当确定问题粒度的等价关系不是一个同余关系时，对偶地定义了上（下）同余与上（下）商，简捷地证明了它们的存在性并得出了一些重要性质，为商空间的合成与分解提供了理论依据.最后以纠错码进行传输的路由选择算法为实例，分析了基于代数结构的商空间模型在网络安全传输过程中的应用.从结构上扩展了现有商空间模型，为商空间理论与代数理论的结合提供了基础.

粒计算；商空间；同余闭包；商运算；上（下）商

1 引言

粒计算（GrC）的概念最早由T Y Lin提出，它是模糊集、区间分析、粗糙集、商空间理论等的超集［1～3］，其研究的目标在于建立粒度化问题求解的一般理论和方法［4～6］.商空间理论由张钹院士和张铃教授提出，是最主要的粒计算模型之一.它用三元组（X，f，T）描述问题，其中X表示论域，f是论域的属性函数，T表示论域的结构，用论域上的等价关系R刻画问题的粒度［7，8］.商空间理论与其他粒计算模型的一个显著区别就是引入了对空间结构的描述，这也使得它能具有更强大的描述和求解问题的能力［9～11］.张铃教授等对论域为拓扑结构的商空间模型进行了系统的研究，形成了相应的理论体系［12］，获得了两个基本结论，即粒度世界的完备性和粒度转换时的性质保留特性［13］.

事实上，结构是对象描述中最复杂的，常见的结构有拓扑，代数，逻辑推理等.如果论域结构为代数结构，那么商空间基本结论是否依然成立.本文假设商空间的论域结构为代数结构，首先利用同余关系和闭包的概念定义同余闭包并给出其重要性质.然后讨论商运算的定义及其存在性的充要条件和全体同余关系是否构成完备半序格.接下来分析了任意个同余关系之和是否仍为同余关系，即具有商运算的不同粒度世界的下确界是否仍然具有商运算.最后，利用等价关系与划分一一对应的关系以及之前所得出的一些结论进一步讨论任意商空间是否总是存在上（下）商，并研究了上（下）商的一些重要性质.

2 商运算和粒度完备性

为了简便起见把商空间模型中的三元组简化成二元组（X，。），X还是表示问题论域，。表示论域的代数结构.代数结构即运算，可能论域有多种不同的运算，这里仅讨论一个二元运算的情况.

2.1同余闭包及其性质

定义1 设R为代数（X，。）上的一个等价关系.若R在。运算下具有置换性，即当 a R b时，对∀c∈X有a。c R b。c且c。a R c。b，则称R为关于运算。的同余关系，简称R为同余关系.

根据同余关系的定义和相关概念就可很容易地得出如下两个命题.具体证明从略.

命题1 设R为代数（X，。）上一个等价关系.R是同余关系的充要条件是当［a］=［b］和［c］=［d］时有［a。c］=［b。d］.

命题2 代数（X，。）上的全等关系E和恒等关系I一定是同余关系.

引理1 代数（X，。）上任意个同余关系的交是同余关系.

证明 设｛Rα｝α为代数（X，。）上若干个同余关系的集合，记R*=∩αRα.先证一方面，对有于是，从而可知另一方面，对有从而即，亦即因此

现在证明R*是同余关系.设和由于，则因此若，则有.同理又因Rα是同余关系，且，于是因此，R*为同余关系.综上所述，引理得证.

闭包概念在数学上被广泛运用，下面定义的同余闭包是本文为了从关系的角度更为简捷地讨论商运算存在性以及上（下）商的存在性而特意引入的.

定义2 设R为代数（X，。）上的一个等价关系，若存在同余关系c（R）⊇R，且对任意同余关系R′⊇R都有c（R）⊆R′，则称c（R）为R的同余闭包.

一言以蔽之，等价关系R的同余闭包就是包含R的最小同余关系.

下面给出同余闭包的一些重要性质.

定理1 代数（X，。）上任意非空等价关系都存在同余闭包.

证明 设R是（X，。）上任意非空等价关系，令｛Rα｝α为X上包含R的全体同余关系.设R*=∩αRα.因为全等关系 E⊇R且一定是同余关系，故｛Rα｝α≠Φ.又∀α，R*⊆Rα，从而若要c（R）=R*，只需证得R*为同余关系.由引理1可知R*为同余关系，因此c（R）= R*，命题得证.

若设C（R）为代数（X，。）上的全体同余关系，则根据定理1的证明过程可进一步得出

定理2 代数（X，。）上任意非空等价关系R是同余关系当且仅当c（R）=R.

证明 若c（R）=R，显然R是同余关系.另一方面，若R是同余关系，且令｛Rα｝α为（X，。）上包含R的全体同余关系，则R∈｛Rα｝α.于是R⊇∩αRα=c（R），又R⊆c（R），因此c（R）=R.

定理3 设R1，R2是代数（X，。）上的两个非空等价关系，若R1⊆R2，则c（R1）⊆c（R2）.

证明 因为R2⊆c（R2），且 R1⊆R2，故R1⊆c（R2）.又由于c（R2）是同余关系，故由同余闭包的定义可知c（R1）⊆c（R2）.

2.2商运算的定义，存在性及其粒度完备性

有了以上的铺垫就可以比较简捷地研究商运算的存在性问题了.给定代数（X，。）的一个等价关系 R，等价于给定了X的一个划分，从粒计算的角度而言也就相当于给定了X的一个粒度，那么自然就会关注在新的粒度世界X/R上是否可导出一种代数结构，即定义一种运算并且新的代数结构能与原代数结构同态.代数（X，。）在保持同态性下的颗粒化是粒计算的本质要求，因为一方面可减小求解问题的规模，另一方面可使得新的结构继承原来结构的一些重要性质，从而有助于在新结构上计算和推理.因此，研究这种运算的存在性成为了构造粒度世界，用粒度的观点和方法求解问题的关键.

定义3 设R是代数（X，。）上一个等价关系，p：X →X/R为投影.若在商空间X/R上存在运算。′，使得p是同态映射，即对∀x，y∈X都有p（x。y）=p（x）。′p（y），则称。′为商空间X/R上的商运算，简称商运算.

对于具有多个算子的代数系统只需对每个算子而言投影都是同态映射即可.定义3同时说明了，如果商运算存在，那么商空间与原空间同态.从而当a。x=b有解时，可得［a］。′［x］=［a。x］=［b］，因此［a］。′［x］=［b］也有解；当［a］。′［x］=［b］无解时，也就是说［a］。′［x］=［a。x］≠［b］，则a。x=b一定无解.这说明在具有代数结构的商空间中保假原理依然成立.下面开始讨论商运算的存在性.

定理4 R是代数（X，。）上的非空等价关系，则商空间X/R存在商运算的充要条件是c（R）=R.

证明 根据定理2的结论，可知原命题等价于商空间X/R存在商运算当且仅当R是同余关系.下面证明这一命题是成立的.一方面，若R是同余关系，则可定义X/R上的二元运算。′，满足对∀x，y∈X，［x］。′［y］= ［x。y］.上述定义是良定的，因为：若［x1］=［x2］且［y1］=［y2］，由于R是同余关系，故［x1。y1］=［x2。y2］.因此，［x1］。′［y1］=［x1。y1］=［x2。y2］=［x2］。′［y2］.显然p满足同态性，故。′是商运算.另一方面，若商空间X/R上存在商运算。′，则对∀x，y，w，z∈X，当［x］= ［y］，［w］=［z］时，有［x。w］=p（x。w）=p（x）。′p（w）=［x］。′［w］=［y］。′［z］=［y。z］，因此，R是同余关系.综上所述，命题得证.

在商空间理论中，不同粒度世界的全体构成一个完备半序格.那么对于存在商运算的不同商空间的全体是否也构成一个完备半序格呢？下面讨论这一问题.

定义4 设R1，R2为X上的两个非空等价关系.若R1⊆R2，则称R1比R2细，或R1细于R2，记为R2≤R1或R1≥R2.

在商空间理论中用等价关系来刻画问题的粒度，因此研究不同粒度世界之间的关系就可以从不同等价关系间的联系入手.下面的命题给出了不同粒度世界之间的关系.

命题3［13］设R为X上全体非空等价关系，则在定义4的偏序”≤”下，（R，≤）是一个完备半序格.

命题3是商空间理论中最基本的也是最重要的定理，它为研究不同粒度世界之间的转换，分解，合成等运算提供了理论依据.本文把全体同余关系作为研究对象也得出了类似结论，即全体同余关系构成一个完备半序格.为此，先给出如下引理.

根据等价关系的定义可很容易地得出引理2的结论.具体证明从略.引理2说明元素在算子。下的置换性具有传递性.

引理2 设R是代数（X，。）上的等价关系，a，b，c∈X，（a，c），（c，b）∈R.若对∀x∈X，（x。a，x。c），（a。x，c。x）∈R而且（x。c，x。b），（c。x，b。x）∈R，则有（x。a，x。b），（a。x，b。x）∈R.

引理3 设C（R）是代数（X，。）上的全体同余关系，非空集合｛Rα｝α⊆C（R），则t（∪αRα）∈C（R）.

证明 对∀x1，x2∈t（∪αRα），由于t（∪αRα）是∪αRα的 传 递闭包，因 此 若（x1，x2）∈∪αRα，则∃Rα0∈｛Rα｝α使得（x1，x2）∈Rα0.由于Rα0是同余关系，必定满足对∀x∈X，（x。x1，x。x2），（x1。x，x2。x）∈Rα0⊆t（∪αRα）；否则（x1，x2）∉∪αRα，由传递闭包的定义可知，∃y1=x1，y2，…，ym=x2∈X，使得（yi，yi+1）∈∪αRα，i=1，2，…，m-1，故对每个i，∃Ri∈｛Rα｝α，使得对∀x ∈X，（x。yi，x。yi+1），（yi。x，yi+1。x）∈t（∪αRα）再由引理2可知，对∀x∈X，（x。x1，x。x2），（x1。x，x2。x）∈t（∪αRα）.因此t（∪αRα）为同余关系，命题得证.

定理5 设（X，。）是代数，C（R）为X上全体同余关系，则在定义4的偏序”≤”下，（C（R），≤）构成一个完备半序格.

证明 先证明∩αRα是｛Rα｝α的上确界.由引理1可知，∩αRα是同余关系.由于对∀α，Rα≤∩αRα，故∩αRα是｛Rα｝α的上界.又对∀R′∈C（R）且∀α，R′≥Rα，即R′⊆Rα，则R′⊆∩αRα，即∩αRα≤R′，因此∩αRα为｛Rα｝α的上确界.

再证明t（∪αRα）是｛Rα｝α的下确界.由引理3知t（∪αRα）是同余关系，又对∀α，Rα⊆t（∪αRα），即t（∪αRα）≤Rα，故t（∪αRα）是｛Rα｝α的下界.又对于∀R′为｛Rα｝α的下界，即∀α，R′≤Rα，有∪αRα⊆R′.由传递闭包的性质可知，t（∪αRα）⊆t（R′）=R′，即R′≤t（∪αRα），因此t（∪αRα）为｛Rα｝α的下确界.综上所述，命题得证.

在商空间理论中不同粒度世界对应着不同等价关系，因此可知具有商运算的不同粒度世界也构成一个完备半序格.

3 上（下）商的定义，存在性及其性质

代数（X，。）的商空间 X/R存在商运算当且仅当R是同余关系.但是，并非任意的等价关系都是同余关系，从而并非代数（X，。）的任何商空间都存在商运算.假如X的商空间X1不存在商运算，是否可以给出一个与X1近似的且存在商运算的商空间.显然，有两种近似方法［13］：（1）在比X1细的所有存在商运算的商空间中是否存在最粗的商空间；（2）在比X1粗的所有存在商运算的商空间中是否存在最细的商空间X？如果有这么一个近似对（X，）存在，那么就可用它来近似描述商空间X1.可以证明这种近似对是唯一存在的.由于论域X上的一个等价关系与X的一个划分是一一对应的，因此可以从等价关系的角度来研究上述近似对的存在性.下面先定义上（下）同余的概念，然后以此为基础来讨论这种近似对的存在性.

定义5 设R是代数（X，。）上的非空等价关系.若存在同余关系¯R≥R，且对任意同余关系R′≥R都有R′≥¯R，则称¯R为R的上同余.

定义6 设R是代数（X，。）上的非空等价关系.若存在同余关系≤R，且对任意同余关系R′≤R都有≤，则称为R的下同余.

实际上，R的上同余¯R就是比R细的所有同余关系中最粗的同余关系，而R的下同余R是比R粗的所有同余关系中的最细的同余关系.可以证明代数（X，。）上任意等价关系R都存在上（下）同余.

定理6 设C（R）为代数（X，。）上的全体同余关系，则（X，。）的任意非空等价关系R都存在上（下）同余，且

根据定理6的结论，再结合定理2和定理4，很容易得出如下推论.具体证明从略.

推论1 代数（X，。）上任一非空等价关系R是同余关系的充要条件是

推论2 代数（X，。）在等价关系R下存在商运算的充要条件是R=¯R和 R=R.

根据等价关系和商集的一一对应性，再结合以上结论就可以很简洁地讨论上（下）商运算的存在性了.

定义7 设X1是代数（X，。）的一个商空间.若存在X的商空间，满足X1≤且上存在商运算，并且对任意X′≥X1上存在商运算，都有≤X′，则称为X的上商，相应的商运算为X1的上商运算.

定义8 设 X1是代数（X，。）的一个商空间.若存在X的商空间上存在商运算，并且对任意′≤X1上存在商运算，都有X′≤X，则称，满足且为X的下商，相应的商运算为X1的下商运算.

根据等价关系与划分的一一对应关系，我们很容易得出代数（X，。）的任意商空间必然存在上（下）商的结论.下面以定理的形式给出，证明从略.

定理7 设X1是代数（X，。）的任意一个商空间，X1对应的等价关系为R，则X1的上（下）商均存在，且商空间X/为X1的下商，商空间X/¯R为R1的上商.

根据定理7的结论，可以在论域的全体等价关系上定义一对上（下）同余算子，也就是说可以在全体粒度世界上定义一对上（下）商算子.上（下）商算子可看成粒度世界中的一对近似算子，它可以把不具商代数结构的商空间近似成具有商代数结构的商空间.这为利用粒计算的思想，近似求解具有代数结构的问题提供了理论基础.下面将给出上（下）同余算子（或商算子）的一些重要性质.

定理8 设R1，R2是代数（X，。）上的两个非空等价关系.若R1≤R2，则

证明 （1）由于R1≤R2，则R2⊆R1，于是R2=，因此

定理8表明上（下）同余算子具有保序性，也就是说粒度细的商空间其上（下）商空间也细，或者说粒度粗的商空间其上（下）商空间也粗.由于不同商空间的全体构成一个完备格，因此可以在全体商空间上定义一对格算子.下面给出一对格算子的定义，并在此格上讨论上（下）商算子的一些重要性质.这些性质为进一步研究粒度世界之间的转换关系和粒度世界的结构特性提供了数学基础.

定义9 设Q（X）是代数（X，。）上的全体商空间构成的集合，商空间X1，X2∈Q（X），记X1∧X2，X1∨X2分别为X1，X2的下确界和上确界.

从划分的角度来看，X1∧X2即为X1与X2的和划分，X1∨X2为X1与X2的积划分.因此，若X1，X2对应的等价关系分别为R1，R2，则X1∧X2对应的等价关系为t （R1∪R2），X1∨X2对应的等价关系为R1∩R2.

定理9 设X1，X2是代数（X，。）上的两个商空间，则

证明 设X1，X2对应的等价关系分别为R1，R2，C（R）为代数（X，。）上的全体同余关系构成的集合.

（2）由于对应的等价关系为c（R1∩R2），则命题等价于c（R1∩R2）⊆c（R1）∩c（R2）.现在开始证明，因为R1∩R2⊆R1，R1∩R2⊆R2，由定理3知c（R1∩R2）⊆c（R1），c（R1∩R2）⊆c（R2），则c（R1∩R2）⊆c（R1）∩c（R2），因此对应的等价关系为t（c（R1）∪c（R2））.X1∧X2对应的等价关系为t（R1∪R2），故

（3）易知对应的等价关系为c（t（R1∪R2））.于是命题等价于c（t（R1∪R2））⊇t（c（R1）∪（R2））.现在开始证明，因为R1⊆t（R1∪R2），R2⊆t（R1∪R2），由定理3知c（R1）⊆c（t（R1∪R2）），c（R2）⊆c（t（R1∪R2）），则c（R1）∪c（R2）⊆c（t（R1∪R2））.由传递闭包定义的极小性可知，关系c（R1）∪c（R2）的传递闭包t（c（R1）∪c（R2））是包含c（R1）∪c（R2）且满足传递性的最小关系，又显然 c（t（R1∪R2））满足传递性且c（R1）∪c（R2）⊆c（t（R1∪R2）），故t（c（R1）∩c（R2））⊆c（t（R1∪R2）），因此

再证t（A∩B）⊆t（A）∩t（B），其中A，B为二元关系.A∩B⊆A，A∩B⊆B，则易知t（A∩B）⊆t（A），t（A∩B）⊆t（B），故t（A∩B）⊆t（A）∩t（B）.现令A=于是可得结论成立.

5）先证t（A）∪t（B）⊆t（A∪B），其中A，B为二元关系.A⊆A∪B，B⊆A∪B，则易知t（A）⊆t（A∪B），t（B）⊆t（A∪B），故t（A）∪t（B）⊆t（A∪B）.现令A=于是可得结论成立.

若X1，X2是代数（X，。）上两个存在商运算的商空间，则易知商空间X1，X2的合成X3=X1∨X2也存在商运算.设X1，X2对应的等价关系为R1，R2，则X3对应的等价关系为R3=R1∩R2.若代数方程［a］1。1［x］1= ［b］1和［a］2。2［x］2=［b］2在各自的论域上有解（［x］i表示x关于Ri的等价类，i=1，2），又［a］3。3［x］3= ［a。x］3=［a。x］1∩［a。x］2=［b］1∩［b］2=［b］3，（其中。j表示Xj上的商运算，j=1，2，3），则可知合成空间X3=X1∨X2也有解.从而在具有代数结构的商空间中保真原理依然成立.

4 代数商空间模型在网络安全传输过程中的应用

作为最重要的粒度计算模型之一，商空间模型在图形图像处理，海量数据挖掘和复杂问题求解等领域应用广泛.而作为商空间模型的一种重要论域结构，代数系统在计算机科学中同样应用广泛，如群理论和有限域理论是编码理论的数学基础；半群理论和格理论在自动机理论和形式语言中发挥了重要作用；关系代数理论成为最流行的数据库的理论模型；格和布尔代数是电子线路设计，电子计算机硬件设计和通讯系统设计的重要工具［17］.

下面以纠错码进行传输的路由选择算法为实例，分析基于代数结构的商空间模型在网络安全传输过程中的应用.

二进制数字信号在网络传输过程中，由于存在着各种干扰，可能会产生失真现象.其中一个常用的解决途径就是采用纠错码传输，使得二进制数码一旦在传递过程中出错，接收端的纠错码就能立即发现错误，并将其纠正.

定义10 由0和1组成的串称为字，一些字的集合称为编码，编码中的字称为码字，不在编码中的字称为废码，编码中的每个二进制信号0或1称为码元.

下面通过实例分析来了解编码发现错误和纠正错误的能力.设有长度为2的字，当选取编码S2=｛00，01，10，11｝时，S2中的任何一个码字发生错误后还是一个码字，故编码S2不具有发现错误的能力.而当选取编码C2=｛01，10｝时，因为00和11均为废码，当01在传递过程中第一个码元由0变为1，即整个字成为11时，由于11是废码，故发现了错误，即编码C2具有发现错误的能力，但它不具有纠正错误的能力.

设有长度为3字，选取编码C3=｛101，010｝，则编码C3既具有发现错误又具有纠正错误的能力.因为码字101出现单个错误后将变为：001，111，100；而码字010出现错误后将变为110，000，011.故如码字101在传递过程中任何一个码元出现了错误，整个码字只会变为111，100或001，但是都可知其原码为101.但显然，C3仅能发现单个错误.

定义11 设Sn是长度为n的字集，即Sn=｛a1a2…an|ai=0或1，i=1，2，…，n｝，其中X，Y∈Sn，X=x1x2…xn，Yn=y1y2…yn，则在Sn上定义二元运算。为：Z=X。Y =z1z2…zn，其中zi=xi+2yi（i=1，2，…，n），运算符+2为模2加运算（即0+21=1+20=1，0+20=1+21= 0），称运算。为按位加运算.

显然，＜Sn，。＞是一个代数系统.并且运算 。满足结合律，它的幺元为00…0，每个元素的逆元都是它自身，因此，＜Sn，。＞是一个群.事实上，在纠错码理论中还有描述两个编码之间相似度的汉明距离的公式表示，一个编码发现单个错误和多个错误能力的充要条件的论证等，在此不再赘述.

以上分析说明，以纠错码进行传输的数据，其数据之间是一种如定义11所示的代数结构，即按位加运算.

随着网络的不断增大和动态更新，路由器路由选择表会急速增大，路由器之间路由表及其更新信息的传输量也会急速增大，且传输过程中数据容易出错［18，20］.因此，文中对路由表信息的编码采用纠错码，对路由的选择也不得不引入分级（不同粒度）的概念.

对于互联网这样的网络，仅分两级是不够的，有必要将区域分组.目前常用的做法是先形成簇，簇又分成区，区再分成组，以此法继续下去（见图1）.这种分组法正是商空间模型应用的典型实例.在分组法的不同粒度世界中，簇的粒度最粗，组的粒度最细.

对一个庞大的网络，不同粒度的簇，区和组的确定方法有所不同.因为路由表信息是由具有代数结构的纠错码表示，为了保持不同粒度之间转换时的保假，保真原理成立，在确定其粒度层次时，我们必须以具有特定属性的同余关系来划分等价类.那么，一个大型网络，到底需要分为几种粒度呢.这可引用Kamoun和Kleinrock的结论［16］，他们发现有N个路由器的子网的最优级数为lnN，其中每个路由器需要的表项总数为elnN.

从上述的讨论可知，复杂网络中的路由可归结为粒计算理论中具有代数结构的商空间模型的应用.

5 结论

在基于商空间的粒计算模型中粒度构造是通过等价关系（划分）来完成的，所以不同的等价关系就对应着问题的不同粒度［14］，从而可以通过分析不同等价关系间的联系来研究不同粒度世界间的关系.因此，从等价关系的角度来研究具有代数结构的商空间模型就十分自然，也比较简便［19］.对于具有代数结构的问题（X，。），给定其上一个等价关系R，并不一定可以得到它的一个商空间，因为这个等价关系没有考虑到问题的结构.要想获得原问题的一个商空间就必须考虑问题的结构，即对等价关系加以约束.由此也可看出结构因素是非常重要的，它在商空间模型中扮演着重要的角色［15］，一方面它增强了商空间的表达能力，另一方面也增添了问题粒化的复杂性.在具有代数结构的商空间模型中与问题粒度一一对应的不是一般的等价关系，而是比等价关系更强的同余关系.由于全体同余关系仍然构成一个完备半序格，因此在具有代数结构的商空间模型中粒度世界的结构仍然具有完备性.另外，由于此处在商空间的构造中本身就遵循了同态原则，因此保假，保真原理在具有代数结构的商空间模型中依然成立.这些结论说明了在具有代数结构的商空间模型中商空间理论的基本结论依然成立.本文还从关系的角度引入了对应于上（下）商概念的上（下）同余，从论证的过程可以看出从关系的角度来证明上（下）商的存在性相比文献［13］中的方式更为简捷.在现有商空间模型中问题描述模式（X，f，T）的T一般指定为拓扑结构，而代数结构也是一种常见的和十分重要的论域结构，因此从这个角度而言，本文扩展了现有商空间模型，也为商空间理论和相关代数理论的结合奠定了基础.

［1］Yao Y Y.Granular computing［A］.Proceedings of the 4th Chinese National Conference on Rough Sets and Soft Computing［C］.Chongqing：Computer Science，2004.1-5.

［2］Pedrycz W.Granular computing-the emerging paradigm ［J］.Journal of Uncertain Systems，2007，1（1）：38-61.

［3］Yao Y Y.The rise of granular computing［J］.Journal of Chongqing University of Posts and Telecommunications （Natural Science Edition），2008，20（3）：299-306.

［4］F Deng，H Pan.Research of intrusion detection system model based on granular computing［J］.Modern Electronics Technique，2011，34（10）：115-117.

［5］王国胤，张清华，胡军.粒计算研究综述［J］.智能系统学报，2007，2（6）：8-26. Wang GuoYing，Zhang QingHua，Hu Jun.An overview of granular computing［J］.CAAI Transactions on Intelligent Systems，2007，2（6）：8-26.（in Chinese）

［6］Zhang Xianyong，Miao Duoqian.Quantitative information architecture，granular computing and rough set models in the double-quantitative approximation space of precision and grade［J］.Information Sciences，2014，6（268）：147 -168.

［7］Yao Yiyu.Granular computing：past，present and future ［A］.Proc of the IEEE International Conference on Granular Computing［C］.Hangzhou，China，2008.80-85.

［8］张燕平，张铃，吴涛.不同粒度世界的描述法-商空间法［J］.计算机学报，2004，27（3）：328-333. Zhang YanPing，Zhang Ling，Wu Tao.The representation of different granular worlds-a quotient space［J］.Chinese Journal of Computers，2004，27（3）：328-333.（in Chinese）

［9］李道国，等.粒度计算研究综述［J］.计算机科学，2005，32 （9）：1-12. Li DaoGuo，et al.An overview of granular computing［J］. Computer Science，2005，32（9）：1-12.（in Chinese）

［10］王向阳，张燕平.粒度计算中的商结构［J］.计算机技术与发展，2008，18（1）：111-118. Wang Xiang-Yang，Zhang Yan-Ping.The quotient structure in granule computing［J］.Computer Technology and Development，2008，18（1）：111-118.（in Chinese）

［11］Wang J，Zhou J.Research of reduct features in the variable precision rough set model［J］.Neurocomputing，2009，72 （10）：2643-2648.

［12］Jing Tao Yao，Vasilakos A V，Pedrycz W.Granular computing：perspectives and challenges［J］.IEEE Transactions on Cybernetics，2013，43（6）：1977-1989.

［13］张铃，张钹.问题题求解理论及应用（第二版）［M］.北京：清华大学出版社，2007. Zhang Lin，Zhang Bo.Theory and Applications of Problem Solving（Second edition）［M］.Beijing：Tsinghua University Press，2007.（in Chinese）

［14］Zhang Ling，Zhang Bo.The quotient space theory of problem solving［J］.Fundamenta Informatcae，2004，59（2）：287-298.

［15］Zhao LiQuan，et al.Research in quotient space theory based on structure［A］.Proceeding of IEEE International Conference on Cognitive Informatics［C］.Beijing，2006. 309-313.

［16］Kamoun D，Kleimrock L.Stockastic Performance Evaluation of Hierarchical Routing for Large Networks［M］. Computer Networks，1979，3（5）：337-353.

［17］Wang Shengsheng，LIU Dayou.An effcient method for calculating qualitative spatial relations［J］.Chinese Journal of Electronics，2009，18（1）：42-46.

［18］Wang Chengyao，Zheng Xuefeng.Service oriented dynamic coordination method based on role for multi-level hierarchical information systems［J］.Chinese Journal of Electronics，2013，22（2）：253-257.

［19］王加阳，杨正华.两种结构的商空间模型比较研究［J］.电子学报，2013，41（11）：2262-2269. Wang Jiayang，Yang Zhenghua.A comparative study of quotient space model with two structures［J］.Acta Electronica Sinica，2013，41（11）：2262-2269.（in Chinese）

［20］贾杰，等.无线传感器网络中联合路由优化的高能效链路调度［J］.电子学报，2014，42（6）：1118-1124. Jia Jie，et al.Energy-Efficient link scheduling combined with routing optimization in wireless sensor network［J］. Acta Electronica Sinica，2014，42（6）：1118-1124.（in Chinese）

陈林书 男，1981年生，湖南平江人.讲师，博士研究生.2007年于中南大学计算机应用专业硕士毕业，后进入湖南科技大学计算机学院工作，主要研究方向为粒计算与智能信息处理.

E-mail：chen-lin-shu@163.com

王加阳 男，1963年出生于湖南长沙，中南大学信息科学与工程学院教授，博士生导师，主要研究方向为智能计算与信息融合.

E-mail：csuwjy@163.com

A Study for Quotient Space Model Based on Algebraic Structure

CHEN Lin-shu1，2，WANG Jia-yang1，YANG Zheng-hua1，LI Li3

（1.School of Information Science and Engineering，Central South University，Changsha，Hunan 410083，China）2.School of Computer Science and Engineering，Hunan University of Science and Technology，Xiangtan，Hunan 411201，China；3.Harbin Institute of Technology Shenzhen Graduate School，Shenzhen，Guangdong 518055，China）

The domain structure in the existing QSM（quotient space model）is usually a topology，and a granule is uniquely determined by an equivalence relation.However，when the domain structure is assumed as a widely used algebra instead of a topology，it introduces the concept of congruence relation，and systematically demonstrates the existence of two basic conclusions in QSM based on algebraic structure—all the congruence relations forming a complete semi-order lattice and the principles of falsity preserving and truth preserving.And when the equivalence relation determining a granule is not a congruence relation，it defines the concepts of least upper（greatest lower）congruence and least upper（greatest lower）quotient in antithesis，proves their existence for simplicity，and discusses some of their important properties which are the theoretical basis for the composition and decomposition of different granularities.Finally，based on the routing algorithm transmitting as error correcting codes，it analyzes the application of QSM based on algebraic structure during network secure transmission.The paper extends the theory of QSM from structure，and provides theoretical basis for the combination of quotient space theory and algebraic theory.

granular computing；quotient space；congruence closure；quotient operation；least upper（greatest lower）quotient

TP18

A

0372-2112（2016）04-0952-07

电子学报URL：http：//www.ejournal.org.cn 10.3969/j.issn.0372-2112.2016.04.028

2014-07-15；

2014-12-08；责任编辑：李勇锋

国家自然科学基金（No.61173052）；湖南省自然科学基金（No.14JJ4007）