Cconsistent Relation)。
相容关系R只要求满足自反性与对称性，因此，等价关系必定是相容关系但反之不真。 例3.9.6 设A是由下列英文单词组成的集合，
A?{cat,teacher,cold,desk,knife,by}
定义关系：
R?{x,yx,y?A，且x和y有相同的字母}
显然，R是一个相容关系。
令x1?cat,x2?teacher,x3?cold,x4?desk,x5?knife,x6?by
R的关系图如图3-10所示。
图3-10
?111000?111110??111100???011110?010110???000001?????。 ?????R的关系矩阵为MR由于相容关系是自反和对称的，因此，其关系矩阵的对角线元素都是1，且矩阵是对称的。
为此我们可将矩阵用梯形表示。
同理，在相容关系的关系图中，每个结点处都有自环且每两个相关联的结点间的弧线都是成对出现的，为了简化图形，我们今后对相容关系图，不画自环，并用单线代替双向弧线，因此，上例的关系矩阵和关系图可简化为表3-1和图3-11。
表3-1 例3.9.8的简化关系矩阵 x2 1 x3 x4 x5 x6
1 1 1 0 x2
1 0 0 x3
1 0 x4
0 x5
1 0 0 0 x1
104
图3-11
定义3.9.5 设R是集合A上的相容关系，C?A ，如果对于C中任意两个元素 a1,a2有
a1Ra2，就称C是由相容关系R产生的相容类(Consistent Class)。
例如，上例中相容关系R可产生相容类{x1,x2},{x1,x3},{x2,x3},{x6},{x2,x4,x5}等等。 对于前三个相容类，都能加进新的元素组成新的相容类，而后两个相容类，加入任一新元素，就不再组成相容类，称它们为最大相容类(Maximal Consistent Class)。
定义3.9.6 设R是集合A上的相容关系，不能真包含在任何其它相容类中的相容类，称作最大相容类，记作CR。
若CR为最大相容类，显然它是A的子集，对于任意x?CR，x必与CR中的所有元素有相容关系。而在A?CR中没有任何元素与CR所有元素有相容关系。
根据最大相容类的定义，它可以从相容关系R的简化关系图求得，具体方法是：
（1）在相容关系R的简化关系图中，每一个最大完全多边形的顶点集合，就是一个最大相容类。所谓完全多边形(Complete Polygon)，就是其每个顶点都与其它顶点连接的多边形。例如一个三角形是完全多边形，一个四边形加上两条对角线就是完全多边形。
（2）在R的简化关系图中，每一个孤立结点的单点集合，是一个最大相容类。 （3）在R的简化关系图中，不在完全多边形中的边的两个端点的集合，是一个最大相容类。 例3.9.7 由例3.9.6中相容关系R的简化关系图3-11可得其全部最大相容类为：
{x1,x2,x3},{x2,x3,x4},{x2,x4,x5},{x6}
C是一个相容类，定理3.9.7 设R是集合A上的相容关系，那么必存在一个最大相容类CR，
使得C?CR。
证明 设A?{a1,a2,?,an}，构造相容类序列C0?C1?C2??，其中C0?C， 且Ci?1?Ci?{aj}，其中j是满足aj?Ci而 aj与Ci中各元素都有相容关系的最小下标。
由于A的元素个数A?n， 所以至多经过n?C步，就使这个过程终止，而此序列的最后一个相容类，就是所要找的最大相容类。
从定理3.9.7中可以看到，A的任一元素a，它可以组成相容类{a}，因此必包含在一个最大相容类CR中，因此，如由所有最大相容类作出一个集合，则A中每一个元素至少属于该集合的一个成员之中，所以最大相容类集合必覆盖集合A。
定义3.9.6 在集合A上给定相容关系R，其最大相容类的集合称作集合A的完全覆盖(Complete Cover)，记作CR(A)。
例3.9.8 设集合A?{a1,a2,a3,a4,a5,a6,a7}，A上二元关系
R?{a1,a1,a2,a2,a2,a3,a3,a2,a3,a3,a3,a4,a3,a5,a3,a6,
a3,a7,a4,a3,a4,a4,a4,a5,a5,a3,a5,a4,a5,a5,a5,a6, a5,a7,a6,a3,a6,a5,a6,a6,a6,a7,a7,a3,a7,a5,a7,a6,
105
a7,a7}
求A的完全覆盖CR(A)。
解 R是A上的相容关系(自反，对称)。
R的简化关系图如图3-12所示：
图3-12
{{a1},a{2a,3}a,3{a4,a5,
R的最大相容类是确定的，即{a1},{a2,a3},{a3,a4,a5},{a3,a5,a6,a7}。因此，集合
CR(A)。 是}a,{a5,a6,a,A的完全覆盖}}37R?A1?A1?A2?A2???An?An
定理3.9.8 给定集合A的覆盖{A1,A2,?,An}，由它确定的关系 是A上的相容关系。
n证明 因为 A??Ai?1i，对于任意x?A，必存在某个j?0， 使得x?Aj ，所以，
x,x?Aj?Aj，即 x,x?R， 因此，R是自反的。
其次，若有任意x,y?A，且x,y?R，则必存在某个h?0，使x,y?Ah?Ah ，故必有y,x?Ah?Ah ，即y,x?R，所以R是对称的。
因此，R是A上的相容关系。
从上述定理可以看到，给定集合A上的任意一个覆盖，必可在A上构造对应于此覆盖的一个相容关系，但是不同的覆盖却能构造相同的相容关系。
例如，设A?{1,2,3,4}，集合{{1,2,3},{3,4}}和{{1,2},{2,3},{1,3},{3,4}}都是A的覆盖，但它们可以产生相同的相容关系：
R?{1,1,1,2,1,3,2,1,2,2,2,3,3,1,3,2,3,3,3,4,4,3,4,4}
因此，相容关系与覆盖之间不是一一对应的。但是我们有： 定理3.9.9 集合A上相容关系R与完全覆盖CR(A)一一对应。
习题3.9
1．设{A1,A2,?,An}是集合A的划分，试证明{A1?B,A2?B,?,An?B}是集合A?B的划分。其中Ai?B??,1?i?n。
2．把n个元素的集合划分成两个分块，共有多少种不同的方法？ 3．已知X及其关系R如下，试说明R是等价关系，并指出其等价类。
106
（1）X：自然数集，R?{ni,njni/nj 能表示成2n形式，n为任意整数}； （2）X：正整数的序偶，R?{x,y,u,vxv?uy}；
（3）X：实数部分非零的复数全体，R?{a?bi,c?diac?0}；
（4）X：实数集，R?{x,y?x???y??0}，其中?x?表示小于或等于x的最大整数。 4．设X?{1,2,3,4,5}，试根据以下X的划分求X上相应的等价关系，并画出关系图。 （1）{{1,2},{3},{4,5}}； （2）{{1,5},{2,3,4}}； （3）{{1},{2},{3,4,5}}； （4）{{1,2,3,4,5}}.
5．证明：（1）设R是X上的关系。对于xi,xj,xk?X而言，如xiRxj且xjRxk蕴含xkRxi，则关系R称为循环的。证明R是自反的和循环的，当且仅当它是一等价关系。
（2）设R1和R2是X上的等价关系，C1,C2分别是相应于R1,R2的划分。证明：R2?R1当且仅当C1中每一个等价类包含于C2的一些等价类中。
（3）设R1和R2是X上的等价关系，其对应等价类的数目（称为等价关系的秩）分别为
r1,r2。试证R1?R2是秩至多为r1r2的X上的等价关系，但R1?R2不一定是X上的等价关系。
6．（1）试叙述根据X上的相容关系来定义一个覆盖的方法，此方法所定义的覆盖是否唯一？ （2）给定集合X的覆盖S?{A1,A2,?,An}，能否确定此覆盖对应的相容关系？ （3）若R1和R2是X上的相容关系，问R1?R2，R1?R2是不是相容关系？
3.10 偏序关系
3.10.1偏序关系的定义
在一个集合上，我们常常要考虑元素的次序关系，其中很重要的一类关系称作偏序关系。 定义3.10.1 设A是一个集合，如果A上的一个关系R，满足自反性、反对称性和传递性，则称R是A上的一个偏序关系(Partially Ordered Relation)，并把它记为“?”。序偶A,?称作偏序集(Partially Ordered Set Or Poset)。
例3.10.1 在实数集R上，小于等于关系“?”是偏序关系。因为： （1）对于任何实数a?R，有a?a成立，故?是自反的；
（2）对任何实数a,b?R，如果a?b且b?a，则必有a?b，故?是反对称的；
（3）对任何实数a,b,c?R，如果a?b，b?c，那么必有a?c，故?是传递的。 例3.10.2 设S为任意非空集合，S上的包含关系??{A,BA,B?P(S),A?B}是偏序关系。因为：
（1）对于任意A?P(S)，有A?A，所以“?”是自反的；
（2）对任意A,B?P(S)，若A?B且B?A，则A?B所以“?”是反对称的；
107
（3）对任意A,B,C?P(S)，若A?B且B?C，则A?C，所以“?”是可传递的。 例3.10.3 正整数集I?上的整除关系|?{?a,b?a,b?I?,a整除b}是偏序关系。因为： （1）对于任何正整数m?I?，有m|m成立，故“|”是自反的；
（2）对任何正整数m,n?I?，如果m|n且n|m，则必有m?n，故“|”是反对称的； （3）对任何正整数m,n,k?I?，如果m|n且n|k，那么必有mk，故“|”是传递的。 例3.10.4 （1）实数集R上的小于关系“<”不是偏序关系。
（2）任意非空集合S的幂集P(S)上的真包含关系“?”不是偏序关系。
3.10.2 偏序关系的哈斯图
为了更清楚地描述偏序集合中元素间的层次关系，我们先介绍“盖住”的概念。
定义3.10.2 在偏序集合A,?中，如果x,y?A，x?y，x?y，且没有其它元素z满足x?z，z?y，则称元素y盖住元素x。并且记
COVA?{x,yx,y?A;y盖住x}。
称covA为偏序集A,?中的盖住关系。显然covA??。
例3.10.5 设A?{1,2,3,4,6,8,12}，并设“|”为整除关系，求COVA。 解 “
”?{1,1,1,2,1,3,1,4,1,6,1,8,1,12,2,2,2,4,2,6,
2,8,2,12,3,3,3,6,3,12,4,4,4,8,4,12,6,6,6,12,8,8, 12,12}
COVA?{1,2,1,3,2,4,2,6,3,6,4,8,4,12,6,12}
对于给定偏序集A,?，它的盖住关系是唯一的，所以哈斯(Hasse)根据盖住的概念给出了偏序关系图的一种画法，这种画法画出的图称为哈斯图(Hasse Diagram)，其作图规则如下：
（1） 用小圆圈代表元素。
（2） 如果x?y且x?y，则将代表y的小圆圈画在代表x的小圆圈之上。
（3） 如果x,y?COVA，则在x与y之间用直线连接。根据这个作图规则，例 3.10.5中偏序集的一般关系图和哈斯图如图3-13所示。
图3-13
例3.10.6 设S1?{a}，S2?{a,b}，S3?{a,b,c}，S4?{a,b,c,d}，则“?”关系是
P(Si)(i?1,2,3,4)上的偏序关系，它们的哈斯图分别如图3-14的(a),(b),(c),(d)所示。
108