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

对“相容关系与覆盖”的再认识摘要：本文对左孝凌等编写的《离散数学》教材“相容关系”一节作深入剖析后提出，重新定义完全覆盖使之合理化，相容关系与完全覆盖不是一一对应的关系。关键词：相容关系；等价关系；完全覆盖；划分左孝凌等编写的《离散数学》教材在国内外享有盛誉，被许多院校采用作为离散数学课程的经典教材。然而，笔者在讲授相容关系一节时，发现有一些内容是值得商榷的。特别是，教材中“相容关系与完全覆盖存在一一对应”的结论，我认为值得怀疑，需要进一步重新认识。一、“完全覆盖”概念需要合理化谈到完全覆盖概念，首先要了解覆盖的含义。教材中对覆盖明确定义是[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]。定义3s={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.