第3章 集合与关系
学习目标：
1．深刻理解序偶、笛卡尔积、关系、集合的划分与覆盖、等价关系、等价类、商集、相容关系、（最大）相容类、偏序关系、极大元、极小元、上（下）界、上（下）确界、最大（小）元、全序关系、良序关系等概念；
2．掌握集合的交、并、差、补、对称差的运算及其运算规律； 3．掌握关系的交、并、逆、复合运算、闭包运算及其性质； 4．掌握关系的矩阵表示和关系图；
5．深刻理解关系的自反性、反自反性、对称性、反对称性和传递性，掌握其判别方法；
6．掌握集合的覆盖与划分的联系与区别；
7．掌握偏序关系的判别及其哈斯图的画法；会求偏序集中给定集合的极大元、极小元、上（下）界、上（下）确界、最大（小）元。
主要内容：
1．集合的基本概念及其运算 2．序偶与笛卡尔积 3．关系及其表示
4．关系的性质及其判定方法 5．复合关系和逆关系 6．关系的闭包运算 7．等价关系与相容关系 8．偏序关系 重点：
1．关系的性质及其判别； 2．关系的复合运算及其性质；
3．等价关系与等价类、等价关系与集合的划分的联系；
4．偏序关系判别及其哈斯图的画法、偏序集中特异位置元素的理解。 难点：
1．关系的传递性及其判别； 2．等价关系的特性；
3．偏序关系的哈斯图的画法；偏序集中特异位置元素的求法。
教学手段：
通过多个实例的精讲帮助同学理解重点和难点的内容，并通过大量的练习使同学们巩固和掌握关系的性质及其判别、关系的复合运算及其性质、等价关系的特性、偏序关系的哈斯图的画法及偏序集中特异位置元素的求法。 习题：
习题3.1：4，6；习题3.2：3（8），4（12），6（m）；习题3.4：1 （2）、(4)，3；
74
习题3.5：1，4；习题3.6：2，5，6；习题3.7：2，5，6；习题3.8：1（1）-（6）；习题3.9：3（2）、（4），4（3）；习题3.10：1 ，4，5。
3.1 集合的基本概念
集合(set)（或称为集）是数学中的一个最基本的概念。所谓集合，就是指具有共同性质的或适合一定条件的事物的全体，组成集合的这些“事物”称为集合的元素。
集合常用大写字母表示，集合的元素常用小写字母表示。若A是集合，a是A的元素，则称a属于A，记作a?A；若a不是A的元素，则称a不属于A，记作。若组成集合的元素个数是有限的，则称该集合为有限集(Finite Set)，否则称为无限集(Infinite Set)。
常见集合专用字符的约定：
N—自然数集合(非负整数集) I (或Z)—整数集合(I?，I?)
Q—有理数集合(Q?，Q?) F—分数集合(F?，F?)
R—实数集合(R?，R?)
脚标+和-是对正、负的区分
P—素数集合 E—偶数集合
C—复数集合 O—奇数集合
幂集
定义3.1.1 对于每一个集合A，由A的所有子集组成的集合，称为集合A的幂集(Power
ASet)，记为 P(A)或2．即P(A)?{BB?A}。
例如：A?{a,b,c}, P(A)?{?,{a},{b},{c},{a,b},{b,c},{a,c},{a,b,c}}。 定理3.1.1 如果有限集A有n个元素，则其幂集P(A)有2个元素。 证明 A的所有由k个元素组成的子集数为从n个元素中取k个的组合数。
Cn?knn(n?1)(n?2)?(n?k?1)k!
nnkn另外，因??A，故P(A)的元素个数N可表示为
N?1?Cn?Cn???Cn???Cn?n12k?Ck?0
又因 (x?y)?令 x?y?1
nn?Ck?0knknxykn?k
得 2?n?Ck?0
n故P(A)的元素个数是2。
人们常常给有限集A的子集编码，用以表示A的幂集的各个元素。具体方法是：
设A?{a1,a2,?,an}，则A子集B按照含ai记1、不含ai记0(i?1,2,?,n)的规定依次写成一个n位二进制数，便得子集B的编码。
例如，若B?{a1,an}，则B的编码是100?01，当然还可将它化成十进制数。如果n?4，那么这个十进制数为9，此时特别记B?{a1,a4}为B9。
75
3.2 集合的对称差运算
定义3.2.1 设A、B是两个集合，要么属于A，要么属于B，但不能同时属于A和B的所有元素组成的集合，称为A和B的对称差集，记为A?B。即
A?B?(A?B)?(B?A)??xx?A?x?B?
例如，若A?{1,2,c,d}，B?{1,b,3,d}，则A?B?{2,c,b,3}。 对称差的定义如图3-1所示。
图3-1
由对称差的定义容易推得如下性质： （1）A?B?B?A （2）A???A （3）A?A??
（4）A?B?(A?B)?(A?B) （5）(A?B)?C?A?(B?C) 证明 （5）(A?B)?C
?[(A?B)?C]?(A?B?C)
?{[(A?B)?(A?B)]?C}?[(A?B)?(A?B)?C] ?(A?B?C)?(A?B?C)?{[(A?B)?(A?B)]?C}
但 [(A?B)?(A?B)]?C
={[(A?B)?A]?[(A?B)?B]}?C
?[(A?A)?(A?B)?(A?B)?(B?B)]?C ?[??(A?B)?(A?B)??]?C ?(A?B?C)?(A?B?C)
故 (A?B)?C
?(A?B?C)?(A?B?C)?(A?B?C)?(A?B?C)
又 A?(B?C)
?(A?B?C)?[A?(B?C)]
?[A?(B?C)?(B?C)]?{A?[(B?C)?(B?C)]} ?{A?[(B?C)?(B?C)]}?[(A?B?C)?(A?B?C)]
因为 A?[(B?C)?(B?C)]
?A?[(B?B)?(B?C)?(C?B)?(C?C)] ?A?[(B?C)?(C?B)]
76
?(A?B?C)?(A?C?B) 故 A?(B?C)
?(A?B?C)?(A?B?C)?(A?B?C)?(A?B?C)
因此 (A?B)?C?A?(B?C)
对称差运算的结合性亦可用图3-2说明。
A?B B?C
(A?B)?C?A?(B?C)图3-2 对称差运算的结合性
从文氏图3-3亦可以看出以下关系式成立。
A?B?(A?B)?(B?A)?(A?B) ? ?(A?B)?(AB ) 图3-3 A?B
3.4 序偶与笛卡尔积
3.4.1 序偶
在日常生活中，有许多事物是成对出现的，而且这种成对出现的事物，具有一定的顺序。
例如，上，下；1?2；男生9名而女生6；中国地处亚洲；平面上点的坐标等。一般的说，两个具有固定次序的客体组成一个序偶(Ordered Pair)，记作x,y。上述各例可分别表示为〈上，下〉；1,2；9,6；〈中国，亚洲〉；a,b等。
序偶可以看作是具有两个元素的集合，但它与一般集合不同的是序偶具有确定的次序。在集合中，?a,b???b,a?，但对序偶，当a?b时，a,b?b,a。
77
定义3.4.1 两个序偶相等，x,y?u,v，当且仅当x?u,y?v。
这里指出：序偶a,b中两个元素不一定来自同一个集合，它们可以代表不同类型的事物。例如，a代表操作码，b代表地址码，则序偶a,b就代表一条单地址指令；当然亦可将a代表地址码，b代表操作码，a,b仍代表一条单地址指令。但上述这种约定，一经确定，序偶的次序就不能再予以变化了。在序偶a,b中，a称第一元素，b称第二元素。
序偶的概念可以推广到有序三元组的情况。
有序三元组是一个序偶，其第一元素本身也是一个序偶，可形式化表示为序偶相等的定义，可以知道
x,y,z?u,v,w当且仅当x,y?x,y,z。由
u,v,z?x,y,zw，即
x?u,y?v,z?w，我们约定有序三元组可记作x,y,z。注意：x,y,z?，因
为x,y,z不是有序三元组。同理，有序四元组被定义为一个序偶，其第一元素为有序三元
x,y,z,w，可记作x,y,z,w，且 ?x?p?y?q?z?r?w?s
组，故有序四元组有形式为
x,y,z,w?p,q,r,s这样，有序n元组(Ordered n-tuple)定义为
x1,x2,?,xn?y1,y2,?,ynx1,x2,?,xn?1,xn，记作x1,x2,?,xn?1,xn，且
?x1?y1?x2?y2???xn?yn
一般地，有序n元组x1,x2,?,xn中的xi称作有序n元组的第i个坐标。
3.4.2 笛卡尔积
定义3.4.2 设A和B是任意两个集合，若序偶的第一个成员是A的元素，第二个成员是B的元素，所有这样的序偶集合，称为集合A和B的笛卡尔乘积或直积(Cartesian Product)，记作A?B。即
A?B?{x,yx?A?y?B}
例3.4.1 若A?{1,2},B?{a,b,c}, 求A?B,B?B以及(A?B)?(B?A) 解 A?B?{1,a,1,b,1,c,2,a,2,b,2,c}
B?B?{a,a,a,b,a,c,b,a,b,b,b,c,c,a,c,b,c,c} B?A?{a,1,a,2,b,1,b,2,c,1,c,2} (A?B)?(B?A)??
显然，我们有：
（1）A?B?B?A；
（2）如果A?m,B?n，则A?B?B?A?AB?mn。 我们约定：若A??或B??，则A?B??。 由笛卡尔积定义可知：
(A?B)?C?{x,y,zx,y?A?B?z?C}
{x,y,zx?A?y?B?z?C}
A?(B?C)?{x,y,zx?A?y,z?B?C}
由于x,y,z不是三元组，所以
78