第2章 关 系
2.1 笛卡儿积与关系
2.1.1 基本知识点
基本概念：笛卡尔积，关系，二元关系，关系的性质
基本理论：关系的定义及表示；关系的性质(自反性、反自反性，对称性、反对称性、可传递性)
基本计算：关系的表示；关系与关系的交、并、补、差运算。
2.1.2 重点与难点 笛卡尔积：设A1,A2,称为A1,A2,,An是任意的集合，所有有序n元组(a1,a2,?An?{(a1,a2,,an)的集合，
,n}
,An的笛卡尔积，用A1?A2?即：A1?A2?,an?An，
?An表示，其中,an)|ai?Aii?1,2,a1?A1,a2?A2,关系：笛卡尔积A1?A2??An的任意一个子集称为n元关系，它是个集合，其
元素是n元组；当n?2时，称为A1到A2上二元关系。当A1?A2时称为集合A上的二元关系，简称关系。若(a,b)??，也可记作a?b，称a与b有关系?。若
(a,b)??，则记作a??b。
特殊及常见的关系 (1) 空关系：?；
(2) 集合A上的普遍关系：UA?{(ai,aj)|ai,aj?A}； (3) 集合A上的恒等关系：IA?{(ai,ai)|ai?A}
(4) 整数集合I上的整除关系：|?{(x,y)|?x,y?I,x整除y} (5) 整数集合I上的同余关系：{(x,y)|?x,y?I,x?y?km,k?I} (6) 实数集R上的小于关系：{(x,y)|?x,y?R,x?y} (7) 幂集合上的包含关系:??{(x,y)|?x,y?2A,x?y}
关系的表示方法
(1) 集合表示法：列举法和描述法；
(2) 矩阵表示法：用矩阵表示由有限集A到有限集B的关系； (3) 关系图表示法：用有向图来表示有限集合A上的关系； (4) 次序图：用无向图来特定地表示有限集A上的偏序关系。
关系的集合运算
关系是集合，因此关系的交、并、差、补运算与集合的运算一致；另一方面关
6
系与关系矩阵一一对应，因此可以用关系矩阵的布尔运算代替关系的运算。
2.2 关系的复合、关系的逆、关系的性质、闭包运算
2.2.1 基本知识
基本概念：关系的复合，关系的逆，关系的性质与关系的闭包 基本性质： (1) 关系复合的性质
(1)设?1:A?B，?2:B?C，?3:C?D，则有
(?1?2)?3??1(?2?3)
?1(?2??3)?(?1?2)?(?1?3)
(?1??2)?3?(?1?3)?(?2?3)
?1(?2??3)?(?1?2)?(?1?3)
(?1??2)?3?(?1?3)?(?2?3)
(2) 设?:A?A，则：?m?n??m?n，(?m)n??mn，这里m,n?N (3) 关系的逆运算具有以下性质：
(??1)?1??，(??r)?1???1?r?1，(?r)?1?r?1??1，(??r)?1???1?r?1 (4) 设?是集合A上的二元关系，则关系的性质可以描述为： (i)?具有自反性?IA?? (ii)?具有对称性?????1 (iii)?具有反对称性?????1?IA (iv) ?具有传递性??2??
2.2.2重点与难点
关系的闭包运算及关系性质的判断。 典型题解：
例1：设A?{a,b,c,d}
(1) 判断下列关系是否是自反关系
?1?{(a,b),(b,c)}
?2?{(a,a),(b,b),(c,c),(d,a)} ?3?{(a,a),(a,b),(d,d),(c,c),(b,b)} ?4?{(a,a),(b,b),(c,c),(d,d)}
(2) 判断下列关系是否是对称关系或者反对称关系
?5?{(a,b),(a,a),(b,a),(b,c),(c,b)}
?6?{(a,b),(a,a),(b,c),(d,c)}
7
?7?{(c,b),(a,a),(d,c),(c,d)} ?8?{(b,b),(d,d)}
(3) 判断下列关系是否可传递关系
?9?{(b,c),(c,c),(c,d),(b,d)} ?10?{(b,c),(c,b),(b,b),(a,d)} ?11?{(b,c),(d,a),(d,c)}
解：(1) ?1不是自反关系，因为对于所有的x?A，(x,x)均不在?1中； ?2是自反关系，但不是恒等关系； ?3是自反关系，但不是恒等关系； ?4是自反关系，也是恒等关系；
(2) ?5是对称关系，它不是反对称关系，因为a?b，但是(a,b)和(b,a)均出
现在?5中；
?6不是对称关系，因为(a,b)??6，(b,a)??6，?6是反对称关系； ?7不是对称关系，因为(c,b)??7，但是(b,c)??7，它也不是反对称关
系，因为c?d，但是(c,d),(d,c)均在?7中。
?8既是对称关系也是反对称关系。
(3) ?9是可传递关系，?10不是可传递关系，因为(c,b)??10，(b,c)??10，但
是(c,c)??10，?11是可传递关系。
例2用构造关系图的方法来求传递闭包t(?)。
设A?{a,b,c,d,e}，A上的关系?定义为??{(a,b),(b,a),(a,c),(求关c,e),(d,b)}系?的传递闭包t(?)。 解：先构造?的关系图，如下：
在?的关系图中，对每一个结点x，找出从x出发能到达所有结点，从结点a出
发能分别到达a,b,c,e，从结点b出发可分别到达结点a,b,c,e，从结点c出发可到达结点
e，从结点d出发可分别达到a,b,c,e
构造t(?)的关系图，如下图：
根据t(?)的关系图可得到相应的序偶：
t(?)?{(a,a),(a,b),(a,c),(a,e),(b,a),(b,b),(b,c)
(b,e),(c,e),(d,a),(d,b),(d,c),(d,e)}
2.3 集合的划分与等价关系
2.3.1基本知识点
基本概念：集合的划分，等价关系，等价类，商集
8
基本理论：
(1) 设?1和?2是非空集合A上的两个划分，若?1细分?2，且?2细分?1，则?1等于?2。
(2) 设?是集合A上的等价关系，则对任意a,b?A，或者[a]??[b?]或者
[a]??[b?]??。
基本计算
求有限集合所有划分的数目；求等价关系中元素的等价类集合、商集、生成的划分；求集合的划分诱导的等价关系。
2.3.2 重点与难点
(1)覆盖划分：划分一定是覆盖，覆盖不一定是划分。
(2)等价关系：设R是集合A上的关系，如果R具有自反性、对称性和传递性，则称R是A上的等价关系。此时若a,b?A且aRb，则称a等价于b。不难验证，普遍关系、恒等关系、模k同余关系都是等价关系。
2.4偏序关系
2.4.1基本知识点
基本概念：偏序关系、偏序集、哈斯图，极大远、极小元、最大元、最小元、上界、下界、上确界、下确界、全序、良序。 基本理论：
(1) 偏序关系的哈斯图表示
(2) 偏序集的某子集若存在最大元(最小元)，那么它一定是唯一的；极大元(极小
元)一定存在，但是不唯一
(3) 上界(下界)可能存在，也可能不存在，如果存在上界(下界)，上界(下界)可能
在该子集中，也可能不在该子集中，且不一定唯一； (4) 良序集一定是全序集；任一个有限的全序集一定是良序集 基本计算：求偏序关系的哈斯图；求偏序集合中的特殊元素。
2.4.2重点和难点
偏序关系的次序图：为形象直观的表示偏序关系，对偏序关系的关系图进行简化得到的图形为次序图。对哈斯图加上自回路、边的方向、传递后的有向边就得到了偏序关系的关系图
偏序集中的特殊元素：设?A,??是一偏序集合，B是A的子集，子集B的极大元是指B中没有比它更大的元素，是一种局部性质；最大元是指比B中所有元素
9
都大(可以相等)的元素，是全局性质。子集B的上界是指A中比B中所有元素都大(可以相等)的元素，在哈斯图中即B中的所有元素向上的路径都能共同到达的元素，有可能存在也有可能不存在，即使存在也可能不唯一；上确界是B的所有上界的最小者，有可能有多个上界但是无上确界。对于极小元、最小元、下界和下确界都可以这样类似去理解。
典型题解
例1 设A?{a,b},B?{1,2,3},C?{p,q}，求A?B,B?A,A?(B?C),A?B?C。 解： A?B?{(a,1),(a,2),(a,3),(b,1),(b,2),(b,3)}； B?A?{(1,a),(a2,),a(3,b),(1b,), (b2
A?B?C?{(a,1,p),(a,1,q),(a,2,p),(a,2,q),(a,3,p),(a,3,q),(b,1,p),(b,1,q),(b,2,p),(b,2,q),(b,3,p),(b,3,q)} A?(B?C)?{(a,(1,p)),(a,(1,q)),(a,(2,p)),(a,(2,q)),(a,(3,p)),(a,(3,q)), (b,(1,p)),(b,(1,q)),(b,(2,p)),(b,(2,q)),(b,(3,p)),(b,(3,q))}
例2 下列各式成立吗？说明理由。 (1) (A?B)?(C?D)?(A?C)?(B?D)； (2) (A?B)?(C?D)?(A?C)?(B?D)； (3) (A?B)?(C?D)?(A?C)?(B?D)； (4) (A?B)?C?(A?C)?(B?C) 解：(1)不成立。反例：
设A?{1},B?{2},C?{3},D?{4}，则(A?B)?(C?D)?{(1,3),(1,4),(2,3),(2,4)}，而(A?C)?(B?D)?{(1,3),(2,4)}。
(2)不成立。反例：设A?{1},B?{2},，则(A?B)?(C?D)??，而C?D?{2}。 (A?C)?(B?D)?{(1,2)}(3)不成立。反例：设A?B?{1},C?{3},D?{4}，则(A?B)?(C?D)??，而
(A?C)?(B?D)?{(1,3),(1,4)}。
(4) 成立。
例3假设A?{1,2,B3?,4},定义A到B上的二元关系，
??{(x,y)|x?y是3的倍数}，用例举法表示关系?，并写出关系矩阵。
解：??{(1,5),(3,3),(3,6),(4,5)}，?的关系矩阵M?如下：
?01?00?M???110 0??010??0?1??0?