对“相容关系与覆盖”的再认识

摘 要：本文对左孝凌等编写的《离散数学》教材“相容关系”一节作深入剖析后提出，重新定义完全覆盖使之合理化，相容关系与完全覆盖不是一一对应的关系。

关键词：相容关系；等价关系；完全覆盖；划分

中图分类号：O158 文献标识码：A 文章编号：1003-2851（2012）02-0201-01

左孝凌等编写的《离散数学》教材在国内外享有盛誉，被许多院校采用作为离散数学课程的经典教材。然而，笔者在讲授相容关系一节时，发现有一些内容是值得商榷的。特别是，教材中“相容关系与完全覆盖存在一一对应”的结论，我认为值得怀疑，需要进一步重新认识。

一、“完全覆盖”概念需要合理化

谈到完全覆盖概念，首先要了解覆盖的含义。教材中对覆盖明确定义是[1，p128]。

定义1 令A为给定非空集合，S={S1,S2,…,Sn}，其中Si?哿A,Si≠?覬(i=1,2,…,n)，且■Si=A，集合S称为集合A的覆盖。

对于完全覆盖，教材中给出的定义是（[1，p138]）

定义2 在集合A上给定相容关系R，其最大相容类的集合称为集合A的完全覆盖，记作CR(A)。

对比覆盖和完全覆盖的概念，不免会产生许多疑惑。

其一：在相容关系给定的前提下，才会有完全覆盖的概念？从定义来看，的确如此。因为只有给出了相容关系，我们才能找出最大相容类，得到完全覆盖。由最大相容类的定义，如果给定了集合A上的一个相容关系，就能确定唯一的的完全覆盖。反过来，如果给定了a的一个完全覆盖，能否确定a上的一个相容关系呢？显然，讨论这样的问题没有意义。因为没有相容关系，完全覆盖就无从谈起。可见，在讨论相容关系与完全覆盖的对应时就只能考虑其中的一个对应，因此这样定义完全覆盖是有缺陷的。

另外，单从定义来看，很难看出覆盖和完全覆盖有什么联系。然而，经过证明可得，集合a的完全覆盖一定是覆盖，覆盖未必是完全覆盖。既然这对概念之间有很密切的联系，所以在定义完全覆盖时，就应该充分体现出它与覆盖的关系。

鉴于完全覆盖概念的不合理性，应该考虑将其重新定义。参考[2，p32]。

定义3 S={S1,S2,…,Sn}是集合A的覆盖，且对于S中任意元素Si，不存在S中的其他元素Sj，使得Si是Sj的子集，则称S为集合A的完全覆盖。

由定义易得，集合A的完全覆盖是集合A的覆盖，而覆盖未必是完全覆盖。利用最大相容类的定义和性质证明可得，集合A上相容关系R所产生的最大相容类的集合是集合A的一个完全覆盖。这和定义2的内容是完全一致的。可见，定义3充分体现了覆盖和完全覆盖这对概念之间的联系，并且与原来定义内容是保持一致的。因此，定义3较定义2更为合理，更具有一般性。

二、“相容关系与覆盖”关系需要重新认识

在相容关系中，等价关系无疑是最重要的一类。

定义4 给定集合A上的关系R，若R是自反的，对称的，则称R是相容关系。

定义5 设R为定义在集合A上的一个关系，若R是自反的，对称的和传递的，则称R为等价关系。

由定义知，等价关系是满足传递性的相容关系。在等价关系一节中，讨论了它与集合划分的对应关系。集合的划分定义为

定义6 令A为给定非空集合，S={S1,S2,…,Sn}，其中，且其中Si?哿A,Si≠?覬(i=1,2,…,n)，且■Si=A，Si∩Sj≠?覬(i=1,2,…,n)集合S称为集合A的划分。

等价关系与集合的划分有结论（[1，2]）：集合A上的一个等价关系R，能确定A的一个划分，该划分就是商集A/R；反过来，集合A上的一个划分S能确定A上的一个等价关系R，且S就是A/R。因此

定理1 集合A上的等价关系R与划分S存在一一对应。

比较等价关系与相容关系，集合的划分与覆盖两对概念，会产生联想：集合A上的相容关系R与覆盖（或完全覆盖）S是否也存在一一对应？教材中给出了肯定的回答。然而，经过仔细分析后知，上述结论却是不成立的。

显然，给定集合A上的相容关系R，能够确定A的一个完全覆盖，即最大相容类的集合CR(A)。反过来，给定A的一个完全覆盖S，也能够确定A上的一个相容关系R，但R的最大相容类的集合CR(A)却未必是S。

例 A={1,2,3}，集合S={1,2},{1,3},{2,3},{3,4}是A的一个完全覆盖，它所确定的相容关系

R={(1,1),(1,2),(2,1),(2,2),(3,3),(3,4),(4,3),(4,4)}

但R的最大相容类的集合却是CR(A)={(1,2,3),{3,4}}。

上例说明，利用相容关系确定完全覆盖与利用完全覆盖构造相容关系这两个“对应法则”不存在“互逆”的关系，因此就不能说相容关系与完全覆盖是一一对应的。由于等价关系与划分一一对应，所以在本质上它们是“一样的”，所以对集合上的等价关系不易研究时，常常可以转化成对集合划分的研究。但是，对于相容关系却不能这样做，因为相容关系与（完全）覆盖在本质上是“不同的”。

参考文献

[1]左孝凌，李为鉴，刘永才.离散数学[M].上海：上海科学技术文献出版社，1982.

[2]邵学才，蒋强荣，石嘉明，张秀珍.离散数学[M].北京：清华大学出版社，2001.

推荐访问:再认 相容 覆盖 关系