第四章 二元关系 2019/5/7

问题 现实世界的事物之间常有一定的联系，这 些联系常表现出一定顺序，如： 3<4， 张华高于李明， A是B的父亲，C是B的儿子 ....... 用两个相关元素构成的有序对来表示: (3, 4); (张华, 李明); (A, B), (B, C) 2019/5/7

关系: 事物间的多值对应,反映元素之间的联 系和性质 关系是在集合的基础上定义的，是计算机科 学中最基本的概念。 计算机科学中数据描述和信息处理最常用的 数学模型.信息检索，数据结构以及算法分析 和程序设计的描述中经常出现。 2019/5/7

N元关系 两个以上集合的元素之间也常产生某种联系： 学生姓名、学号、专业、成绩 航班的航空公司、航班号、出发地、目的地、起飞时间、到达时 间 ， 如：(国航，CA1255，北京，合肥，8：08，10：00) ） 关系型数据库 每条记录是由字段构成的n元组 一条记录可表示成一个n元关系 2019/5/7

4.1 基本概念 定义4.1.1 由两个元素x和y，按照一定的顺序组成 的二元组称为有序对/序偶，记作(x, y)，其中x是第 一元素，y是第二元素。 实例：点的直角坐标(3, 4 ) 有序对性质 （1）有序性 ( x, y )  ( y, x ) （当x  y时） （2） ( x, y ) = ( u, v )  x=u且 y=v 2019/5/7

4.1 基本概念   2019/5/7

4.1 基本概念   2019/5/7

实例 例如, A={1, 2}, 则  EA = {(1,1),(1,2),(2,1),(2,2)}  IA = {(1,1),(2,2)} 例如 A = {1, 2, 3}, 则 LA = {(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)} DA = {(1,1),(1,2),(1,3),(2,2),(3,3)} 例如 A = P(B) = {,{a},{b},{a,b}}, 则 A上的包含关系 R = {(,),(,{a}),(,{b}),(,{a,b}),({a},{a}), ({a},{a,b}),({b},{b}),({b},{a,b}),({a,b},{a,b})} 类似的还可以定义： 大于等于关系, 小于关系, 大于关系, 真包含关系等. 2019/5/7

全域关系 EA = {(x, y)| x∈A∧y∈A} = A×A 恒等关系 IA = {(x, x)| x∈A} 空关系 全域关系 EA = {(x, y)| x∈A∧y∈A} = A×A 恒等关系 IA = {(x, x)| x∈A} 2019/5/7

小于等于关系 LA = {(x, y)| x, y∈A且x≤y}, A为实数 子集 二元关系的几个常见例子 小于等于关系 LA = {(x, y)| x, y∈A且x≤y}, A为实数 子集 整除关系 DB = {(x, y)| x, y∈B且x整除y}, A为非0整数 子集 包含关系 R = {(x, y)| x, y∈A且x  y}, A是集合族. 2019/5/7

类似地可定义n元关系。若S  A1×A2×…×An，则 称S为 A1×A2×…×An 上的n元关系。 特别当A1=A2=···=An时，称S为A上的n元关系。 2019/5/7

几点说明：   2019/5/7

  2019/5/7

例 设A和B分别是学校的所有学生和所有课程的集合。假设R由所有有序对(a,b)组成，其中a是选修课程b的学生。S由所有有序对(a,b)构成，其中课程b是a的必修课。什么是关系R∪S，R∩S，RS，R-S和S-R？ 2019/5/7

RS由所有有序对(a,b)组成，其中学生a已经选修了课程b，但课程b不是a的必修课，或者课程b是a的必修课，但a没有选修它。 例 设A和B分别是学校的所有学生和所有课程的集合。假设R由所有有序对(a,b)组成，其中a是选修课程b的学生。S由所有有序对(a,b)构成，其中课程b是a的必修课。什么是关系R∪S，R∩S，RS，R-S和S-R？ 解：关系R∪S由所有的有序对(a,b)组成，其中a是一个学生，他或者选修了课程b，或者课程b是他的必修课。R∩S是所有有序对(a,b)的集合，其中a是一个学生，他选修了课程b并且课程b也是a的必修课。 RS由所有有序对(a,b)组成，其中学生a已经选修了课程b，但课程b不是a的必修课，或者课程b是a的必修课，但a没有选修它。 R-S是所有有序对(a,b)的集合，其中a已经选修了课程b但课程b不是a的必修课。 S-R是所有有序对(a,b)的集合，其中课程b是a的必修课，但a没有选它。 2019/5/7

4.1.1 关系的表示 集合表示: R={(x, y) | xRy} 矩阵表示 关系图 2019/5/7

  2019/5/7

例 设A = {2, 3, 4}, B = {2, 3, 4, 5, 6}, 定义A到B的二 元关系R: aRb当且仅当a整除b。 R={(2, 2), (2, 4), (2, 6), (3, 3), (3, 6), (4, 4)} 2 3 4 5 6 2 1 0 1 0 1 MR= 3 0 1 0 0 1 4 0 0 1 0 0 2019/5/7

例 设A = {2, 3, 4}, 定义A上的二元关系R: aRb当且仅 当a整除b。 则R=？R的关系矩阵是什么？ 2019/5/7

一个有限集合A上的关系R还可以用一个称为R的关系图来表示, 其优点是直观清晰。关系图是分析关系性质的方便形式, 但不便于进行运算。 2019/5/7

A上关系R的关系图(graph of relation) GR =〈A, R〉 是一个有向图, 其中 (2) 当且仅当xRy时, 有一条从x到y的有向弧; (3) 若xRx, 则在x处画一条自封闭的弧线。 注意: 关系图中顶点的位置, 弧或线段的长度可 任意。 2019/5/7

例 设A = {a, b, c, d}, R = {(a, d), (b, a), (b, b), (c, c)}, R的关系图GR 关系R的集合表达式、关系矩阵MR、关系图GR三者均可以唯一相互确定。 关系矩阵适合表示从A到B的关系或A上的关系（A, B为有限集）。 关系图适合表示有限集A上的关系 。 2019/5/7

例 A={1,2,3,4}上的关系 R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>}, 求R的关系矩阵MR和关系图GR。 2019/5/7

例 A={1,2,3,4}上的关系 R={(1,1), (1,2), (2,3), (2,4), (4,2)}, 求R的关系矩阵MR和关系图GR。 解： 2019/5/7

关系的性质是指集合中二元关系的性质，这些性 质扮演着重要角色，把集合上的关系进行分类 自反性 反自反性 对称性 反对称性 传递性 4.1.2 关系的性质 关系的性质是指集合中二元关系的性质，这些性 质扮演着重要角色，把集合上的关系进行分类 自反性 反自反性 对称性 反对称性 传递性 2019/5/7

A上关系R是自反的(x)(xAxRx) 关系的性质 定义4.1.3 令RA×A，若对A中每个x，都有xRx， 则称R是自反的(reflexive)，即 A上关系R是自反的(x)(xAxRx) 否则称R不是自反的, 即存在yA, 但(y,y) R 在自反的关系R中，除其他有序对外，必须包括有 全部由每个xA所组成的元素相同的有序对。 2019/5/7

R1 = {(a, a), (b, b), (c, c), (b, c)} R2 = {(a, b), (b, a)} 例 S = {a, b, c}, S上的关系 R1 = {(a, a), (b, b), (c, c), (b, c)} R2 = {(a, b), (b, a)} R3 = {(b, b), (c, c)} R4= {(a, b), (b, a), (a, c)} R1 R2 R3 R4 自反性 反自反性 对称性 反对称性 传递性 2019/5/7

R1 = {(a, a), (b, b), (c, c), (b, c)} R2 = {(a, b), (b, a)} 例 S = {a, b, c}, S上的关系 R1 = {(a, a), (b, b), (c, c), (b, c)} R2 = {(a, b), (b, a)} R3 = {(b, b), (c, c)} R4= {(a, b), (b, a), (a, c)} R1 R2 R3 R4 自反性 反自反性 对称性 反对称性 传递性 2019/5/7

R1 = {(a, a), (b, b), (c, c), (b, c)} R2 = {(a, b), (b, a)} 例 S = {a, b, c}, S上的关系 R1 = {(a, a), (b, b), (c, c), (b, c)} R2 = {(a, b), (b, a)} R3 = {(b, b), (c, c)} R4= {(a, b), (b, a), (a, c)} R1 R2 R3 R4 自反性 反自反性 对称性 反对称性 传递性 2019/5/7

R1 = {(a, a), (b, b), (c, c), (b, c)} R2 = {(a, b), (b, a)} 例 S = {a, b, c}, S上的关系 R1 = {(a, a), (b, b), (c, c), (b, c)} R2 = {(a, b), (b, a)} R3 = {(b, b), (c, c)} R4= {(a, b), (b, a), (a, c)} R1 R2 R3 R4 自反性 反自反性 对称性 反对称性 传递性 2019/5/7

R1 = {(a, a), (b, b), (c, c), (b, c)} R2 = {(a, b), (b, a)} 例 S = {a, b, c}, S上的关系 R1 = {(a, a), (b, b), (c, c), (b, c)} R2 = {(a, b), (b, a)} R3 = {(b, b), (c, c)} R4= {(a, b), (b, a), (a, c)} R1 R2 R3 R4 自反性 反自反性 对称性 反对称性 传递性 2019/5/7

EA IA | <  自反性 反自反性 对称性 反对称性 传递性 2019/5/7

EA IA | <  自反性 反自反性 对称性 反对称性 传递性 2019/5/7

EA IA | <  自反性 反自反性 对称性 反对称性 传递性 2019/5/7

EA IA | <  自反性 反自反性 对称性 反对称性 传递性 2019/5/7

EA IA | <  自反性 反自反性 对称性 反对称性 传递性 2019/5/7

EA IA | <  自反性 反自反性 对称性 反对称性 传递性 2019/5/7

EA IA | <  自反性 反自反性 对称性 反对称性 传递性 2019/5/7

EA IA | <  自反性 反自反性 对称性 反对称性 传递性 2019/5/7

EA IA | <  自反性 反自反性 对称性 反对称性 传递性 2019/5/7

A上关系R是非自反的(x)((xA┐(xRx)) 定义4.1.4 令RA×A，若对于A中每个x，有 ┐(xRx)，则称R是非自反的(irreflexive) ，即 A上关系R是非自反的(x)((xA┐(xRx)) 否则称R不是非自反的, 即存在yA, 但(y,y) R 一个非自反的关系R中，不应包括有任何相同元 素的有序对。 2019/5/7

R1 = {(a, a), (b, b), (c, c), (b, c)} R2 = {(a, b), (b, a)} 例 S = {a, b, c}, S上的关系 R1 = {(a, a), (b, b), (c, c), (b, c)} R2 = {(a, b), (b, a)} R3 = {(b, b), (c, c)} R4= {(a, b), (b, a), (a, c)} R1 R2 R3 R4 自反性 反自反性 对称性 反对称性 传递性 2019/5/7

R1 = {(a, a), (b, b), (c, c), (b, c)} R2 = {(a, b), (b, a)} 例 S = {a, b, c}, S上的关系 R1 = {(a, a), (b, b), (c, c), (b, c)} R2 = {(a, b), (b, a)} R3 = {(b, b), (c, c)} R4= {(a, b), (b, a), (a, c)} R1 R2 R3 R4 自反性 反自反性 对称性 反对称性 传递性 2019/5/7

EA IA | <  自反性 反自反性 对称性 反对称性 传递性 2019/5/7

EA IA | <  自反性 反自反性 对称性 反对称性 传递性 2019/5/7

(x)(y)(x,yA∧xRy→yRx) 定义4.1.5 令RA×A，对于A中每个x和y，若xRy， 则yRx，称R是对称的(symmetric)，即 A上关系R是对称的 (x)(y)(x,yA∧xRy→yRx) 在表示对称的关系R的有序对集合中，若有有序 对(x, y)，则必定还会有有序对(y, x)。 2019/5/7

R1 = {(a, a), (b, b), (c, c), (b, c)} R2 = {(a, b), (b, a)} 例 S = {a, b, c}, S上的关系 R1 = {(a, a), (b, b), (c, c), (b, c)} R2 = {(a, b), (b, a)} R3 = {(b, b), (c, c)} R4= {(a, b), (b, a), (a, c)} R1 R2 R3 R4 自反性 反自反性 对称性 反对称性 传递性 2019/5/7

R1 = {(a, a), (b, b), (c, c), (b, c)} R2 = {(a, b), (b, a)} 例 S = {a, b, c}, S上的关系 R1 = {(a, a), (b, b), (c, c), (b, c)} R2 = {(a, b), (b, a)} R3 = {(b, b), (c, c)} R4= {(a, b), (b, a), (a, c)} R1 R2 R3 R4 自反性 反自反性 对称性 反对称性 传递性 2019/5/7

EA IA | <  自反性 反自反性 对称性 反对称性 传递性 2019/5/7

EA IA | <  自反性 反自反性 对称性 反对称性 传递性 2019/5/7

(x)(y)((x,yA∧xRy∧x≠y→┐(yRx)) 定义4.1.6 令RA×A，对于A中每个x和y，若xRy 且yRx，则x=y，称R是反对称的(antisymmetric)，即： A上关系R是反对称的 (x)(y)((x,yA∧xRy∧x≠y→┐(yRx)) 在表示反对称关系R的有序对集合中，若存在有 序对(x, y)和(y, x)，则必定是x=y。或者说，在R中 若有有序对(x, y)，则除非x=y，否则必定不会出现 (y, x)。即 xRy和yRx至多只有一个出现。 2019/5/7

R1 = {(a, a), (b, b), (c, c), (b, c)} R2 = {(a, b), (b, a)} 例 S = {a, b, c}, S上的关系 R1 = {(a, a), (b, b), (c, c), (b, c)} R2 = {(a, b), (b, a)} R3 = {(b, b), (c, c)} R4= {(a, b), (b, a), (a, c)} R1 R2 R3 R4 自反性 反自反性 对称性 反对称性 传递性 2019/5/7

R1 = {(a, a), (b, b), (c, c), (b, c)} R2 = {(a, b), (b, a)} 例 S = {a, b, c}, S上的关系 R1 = {(a, a), (b, b), (c, c), (b, c)} R2 = {(a, b), (b, a)} R3 = {(b, b), (c, c)} R4= {(a, b), (b, a), (a, c)} R1 R2 R3 R4 自反性 反自反性 对称性 反对称性 传递性 2019/5/7

EA IA | <  自反性 反自反性 对称性 反对称性 传递性 2019/5/7

EA IA | <  自反性 反自反性 对称性 反对称性 传递性 2019/5/7

有些关系既是对称的又是反对称的，如相等关系； 有些关系是对称的但不是反对称的，如Z中的“绝对 值相等”； 还有的关系既不是对称的又不是反对称的，例如， A={a, b, c}中的关系R4= {(a, b), (b, a), (a, c)}。 2019/5/7

(x)(y)(z)(x,y,zA∧xRy∧yRz→xRz) 定义4.1.7 令RA×A，对于A中每个x, y, z，若xRy 且yRz，则xRz，称R是传递的(transitive),否则R是不 可传递的(nontransitive)。 即：A上关系R是传递的 (x)(y)(z)(x,y,zA∧xRy∧yRz→xRz) 该定义表明了，在表示可传递关系R的有序对集合 中，若有有序对(x, y)和(y, z)，则必有有序对(x, z)。 2019/5/7

R1 = {(a, a), (b, b), (c, c), (b, c)} R2 = {(a, b), (b, a)} 例 S = {a, b, c}, S上的关系 R1 = {(a, a), (b, b), (c, c), (b, c)} R2 = {(a, b), (b, a)} R3 = {(b, b), (c, c)} R4= {(a, b), (b, a), (a, c)} R1 R2 R3 R4 自反性 反自反性 对称性 反对称性 传递性 2019/5/7

R1 = {(a, a), (b, b), (c, c), (b, c)} R2 = {(a, b), (b, a)} 例 S = {a, b, c}, S上的关系 R1 = {(a, a), (b, b), (c, c), (b, c)} R2 = {(a, b), (b, a)} R3 = {(b, b), (c, c)} R4= {(a, b), (b, a), (a, c)} R1 R2 R3 R4 自反性 反自反性 对称性 反对称性 传递性 2019/5/7

EA IA | <  自反性 反自反性 对称性 反对称性 传递性 2019/5/7

EA IA | <  自反性 反自反性 对称性 反对称性 传递性 2019/5/7

显然，上述提到的关系中，，=和≤，(，=都是传 递的；在直线的集合中，平行关系是传递的，但垂 直关系不是传递的。 显然，上述提到的关系中，，=和≤，(，=都是传 递的；在直线的集合中，平行关系是传递的，但垂 直关系不是传递的。 2019/5/7

例 在集合S = {a, b, c, d}上的关系 R＝ {(b, c), (c, c), (c, d), (d, c)}, 判断R的性质。 2019/5/7

例 在集合S = {a, b, c, d}上的关系 R＝ {(b, c), (c, c), (c, d), (d, c)}, 判断R的性质。 解 R不是自反的； (c, c)R，所以R不是非自反的； (b, c)R, 但 (c, b)R, 所以R不是对称的； (c, c)R，所以R不是非对称的； c  d, 但 (c, d)R且(d, c)R, 所以R不是反对称的； (b, c)R, (c, d)R, 但 (b, d)R, 所以R不是可传递的。 2019/5/7

4.1.3 关系的运算 集合运算: 交、并、补、差、对称差、幂集、积等 映射运算： 定义域、值域、合成、逆等 闭包运算 2019/5/7

R的定义域(domain)： dom(R)={x|(y)(xRy)} R的值域(domain)： ran(R)={y|(x)(xRy)} 关系的定义域与值域 令RA×B，则 R的定义域(domain)： dom(R)={x|(y)(xRy)} R的值域(domain)： ran(R)={y|(x)(xRy)} R的域(domain)： fld(R)=dom(R)∪ran(R) dom(R)A，ran(R)B。 2019/5/7

关系R = {(2, a), (2, b), (3, b), (4, d), (6, d)}, 例 设A = {1, 2, 3, 4, 5, 6}, B = {a, b, c, d}, 关系R = {(2, a), (2, b), (3, b), (4, d), (6, d)}, 则 dom(R)、ran(R)}、fld(R)分别是什么？ 2019/5/7

关系R = {(2, a), (2, b), (3, b), (4, d), (6, d)}, 则 例 设A = {1, 2, 3, 4, 5, 6}, B = {a, b, c, d}, 关系R = {(2, a), (2, b), (3, b), (4, d), (6, d)}, 则 dom(R) = {2, 3, 4, 6}, ran(R) = {a, b, d}, fld(R)={2, 3, 4, 6, a, b, d}。 2019/5/7

  2019/5/7

  2019/5/7

    2019/5/7

合成运算 没有交换律 有结合律 合成关系的关系矩阵 2019/5/7

幂运算   2019/5/7

S = {(a, d), (b, c), (b, d), (c, b)}。 这次求 R2 和 S2。 再看前例： 设A = {a, b, c, d}, A上的关系 R = {(a, a), (a, b), (b, d)}, S = {(a, d), (b, c), (b, d), (c, b)}。 这次求 R2 和 S2。 解: R2 = {(a,a), (a, b), (a, d)}； S2 = {(b, b), (c, c), (c, d)}。 幂运算是一种特殊的复合运算。 思考：用关系矩阵、关系图怎么计算Rn ? 2019/5/7

  2019/5/7

  2019/5/7

  2019/5/7

  2019/5/7

  2019/5/7

R-1={(y, x)|(x, y)R} 或者 xRyy R-1x 逆运算 设R是从A到B的二元关系，由关系R得到一个新的 从B到A的关系，记为R-1，称R-1为R的逆运算，亦称 R-1为R的逆关系。形式地表为 R-1={(y, x)|(x, y)R} 或者 xRyy R-1x 由定义可知，-1=，(A×B)-1=B×A 逆关系的关系矩阵　MR-1 =(MR)T 2019/5/7

只要将R的每一个有序对中元素次序颠倒, 就得到逆关系R–1的所有有序对。 例 设A = {a, b, c, d, 1, 2, 3, 4}, A上的关系 R = {(a, 2), (b, 2), (b, 3), (d, 4)}, 则 R–1 = {(2, a), (2, b), (3, b), (4, d)}。 2019/5/7

  2019/5/7

运算与性质的关系 自反性 反自反性 对称性 反对称性 传递性 R11 √ R1∩R2 R1∪R2 × R1R2 R1∘R2

对于这几个性质之间的关系，有如下定理： 定理 设R在A上是非自反和可传递的, 则R必是反 对称的。 证明 对任意的x, yA, 假设xRy且yRx, 因为R是可传递的, 所以有xRx, 这与已知R是非自 反矛盾。 由x, y的任意性, 所以R必是反对称的。▎ 2019/5/7

上节课 内容回顾 关系的性质 自反性、反自反性、对称性、反对称性、传 递性 关系的运算 集合运算、关系的合成、逆关系 2019/5/7

关系的闭包运算是关系上的一元运算，是包含该 关系且具有某种性质的最小关系。 非空集合A上的关系R不一定具有前面的5种性质 中的某些性质, 本节讨论构造最小的包含R的关系 c(R), 使之具有所要求的性质, 这就是关系的闭包。 关系的闭包运算是关系上的一元运算，是包含该 关系且具有某种性质的最小关系。 2019/5/7

例：设A={1,2,3},A上的关系R＝{(1,2)}，显然不是自反的， R1＝{(1,1),(2,2),(3,3),(1,2)}是自反的，且RR1， 同样， R2＝{(1,1),(2,2),(3,3),(1,2),(1,3)}也是自反的，且RR2, 包含R的并且是自反的关系有无数个，其中，R1是最小的一个。我们R1称为R的自反闭包。 2019/5/7

定义4.1.8 设R是A上的二元关系，则R的自反（对称、传 递）闭包(closure)是一个满足下列条件关系R1： ② RR1 ③ 对任何自反的（对称的、传递的）关系R2，若RR2， 则R1R2。 R的自反(reflexive) 、对称(symmetric)和传递(transitive) 的闭包分别记为r(R)、s(R)和t(R)。 r(R) (s(R), t(R))是包含R的最小自反(对称, 传递)关系。 2019/5/7

定理 若RA×A，则 ① R是自反的 r(R)=R ② R是对称的 s(R)=R ③ R是传递的 t(R)=R 2019/5/7

闭包的构造方法 定理 令RA×A，则 ① r(R)=R∪IA 依次检查A中各元素a, 若(a, a)R, 就把它加入到R中去, 由此即得r(R)。 ② s(R)=R∪R-1 依次检查R中各元素(a, b), 若ab且(b, a) R, 就把(b, a)加入到R中去, 由此即得s(R)。 ③ t(R)= = R1∪R2∪R3∪… 这个求并集的过程是有限的。 t(R)= R1∪R2∪R3∪… ∪Rn , 其中 n=|A|。 2019/5/7

例 设A={a, b, c}上的关系R={(a, b), (b, c), (c, a)}，试求R的自反、对称、传递闭包。   2019/5/7

说明：   2019/5/7

4.2 等价关系 等价关系 等价类 商集 划分 2019/5/7

4.2.1 等价关系 定义4.2.1 设R是集合A上二元关系，若R是自反 的、对称的和传递的，则称R为A上的等价关系。若 (a,b)R，或aRb，称a与b等价。 由于R是对称的，a等价b即b等价a，反之亦然，a 与b彼此等价。 空集上的二元关系是等价关系，是一种平凡情形， 因此，一般讨论非空集合上的等价关系。 等价关系是事物之间存在同一性，一致性的反映。 它使得用有限的，抽象的逻辑方法，理解无穷的， 纷繁复杂的具体事物成为可能。 2019/5/7

等价关系的例子 数集中的相等关系，集合间的相等关系 整数集合中的同余关系 命题演算中的等价关系 平面上的三角形集合中，三角形相似关系是 等价关系 合肥市的居民集合中，住在同一区的关系 2019/5/7

4.2.2 等价类 定义4.2.2 设R为非空集合A上的等价关系，对 aA，令 [a]R={x|xA∧aRx} 称[a]R为a关于R的等价类，简称a的等价类，简记 为[a]。 2019/5/7

例 A = {1, 2, 3, 4, 5, 6, 7}, R是A上的模3同余关系。显然R是A上的等价关系, A中各元素关于R的等价类分别是: 2019/5/7

例 A = {1, 2, 3, 4, 5, 6, 7}, R是A上的模3同余关系。显然R是A上的等价关系, A中各元素关于R的等价类分别是: [1]R = {1, 4, 7}, [4] R= {1, 4, 7}, [7] R= {1, 4, 7} [2] R = {2, 5}, [5] R = {2, 5}, [3] R = {3, 6}, [6] R = {3, 6}。 2019/5/7

例 A = {1, 2, 3, 4, 5, 6, 7}, R是A上的模3同余关系。显然R是A上的等价关系, A中各元素关于R的等价类分别是: [1]R = {1, 4, 7}, [4] R= {1, 4, 7}, [7] R= {1, 4, 7} [2] R = {2, 5}, [5] R = {2, 5}, [3] R = {3, 6}, [6] R = {3, 6}, 可以看出, 彼此等价的元素其等价类是相同的, 所以不同的等价类仅有3个, 它们是[1] R, [2] R和[3] R。 2019/5/7

等价类的性质   2019/5/7

4.2.3 商集 定义4.2.3 设R是非空集合A上的等价关系，记 A/R={[a]R|aA} 则称A/R为A对R的商集。 A/R读作A模R。 商集A/R是以R的所有等价类为元素的集合。 2019/5/7

例 A = {1, 2, 3, 4, 5, 6, 7}, R是A上的模3同余关系。显然R是A上的等价关系, A中各元素关于R的等价类分别是: [1]R = {1, 4, 7}=[4] R= [7] R [2] R = {2, 5}=[5] R [3] R = {3, 6}=[6] R 商集 A/R = {{1, 4, 7}, {2, 5}, {3, 6}} 2019/5/7

4.2.4 集合的划分 定义4.2.4 设A是非空集合，若B={A1,A2,···,An}，① Ai， ② Ai∩Aj=，ij， 则称B是A的划分, 称B中元素为A的划分块。 2019/5/7

等价关系与划分 集合A上的等价关系与集合A的划分一一对应 商集A/R就是A的一个划分，并且不同的商集对应于不同的划分。 任给A的一个划分，B={A1,A2,···,An}，如下 定义A上的关系R= {(a, b)|(Ai)(AiB且a, bAi)} R是A上的等价关系，且A/R就是划分B。 2019/5/7

{{0},{1},{2}} {{0,1},{2}} {{0},{1,2}} {{0,2},{1}} {{0,1,2}} 例 集合A={0,1,2}上所有的不同划分 A上所有的不同划分 {{0},{1},{2}} {{0,1},{2}} {{0},{1,2}} {{0,2},{1}} {{0,1,2}} 2019/5/7

{{0},{1},{2}} {{0,1},{2}} {{0},{1,2}} {{0,2},{1}} {{0,1,2}} 例 集合A={0,1,2}上所有的不同划分 A上所有的不同划分 A上所有的等价关系 {{0},{1},{2}} {{0,1},{2}} {{0},{1,2}} {{0,2},{1}} {{0,1,2}} {(0,0),(1,1),(2,2)} 2019/5/7

{{0},{1},{2}} {{0,1},{2}} {{0},{1,2}} {{0,2},{1}} {{0,1,2}} 例 集合A={0,1,2}上所有的不同划分 A上所有的不同划分 A上所有的等价关系 {{0},{1},{2}} {{0,1},{2}} {{0},{1,2}} {{0,2},{1}} {{0,1,2}} {(0,0),(1,1),(2,2)} {(0,0),(1,1),(2,2),(0,1),(1,0)} 2019/5/7

{{0},{1},{2}} {{0,1},{2}} {{0},{1,2}} {{0,2},{1}} {{0,1,2}} 例 集合A={0,1,2}上所有的不同划分 A上所有的不同划分 A上所有的等价关系 {{0},{1},{2}} {{0,1},{2}} {{0},{1,2}} {{0,2},{1}} {{0,1,2}} {(0,0),(1,1),(2,2)} {(0,0),(1,1),(2,2),(0,1),(1,0)} {(0,0),(1,1),(2,2),(1,2),(2,1)} 2019/5/7

{{0},{1},{2}} {{0,1},{2}} {{0},{1,2}} {{0,2},{1}} {{0,1,2}} 例 集合A={0,1,2}上所有的不同划分 A上所有的不同划分 A上所有的等价关系 {{0},{1},{2}} {{0,1},{2}} {{0},{1,2}} {{0,2},{1}} {{0,1,2}} {(0,0),(1,1),(2,2)} {(0,0),(1,1),(2,2),(0,1),(1,0)} {(0,0),(1,1),(2,2),(1,2),(2,1)} {(0,0),(1,1),(2,2),(0,2),(2,0)} 2019/5/7

{{0},{1},{2}} {{0,1},{2}} {{0},{1,2}} {{0,2},{1}} {{0,1,2}} 例 集合A={0,1,2}上所有的不同划分 A上所有的不同划分 A上所有的等价关系 {{0},{1},{2}} {{0,1},{2}} {{0},{1,2}} {{0,2},{1}} {{0,1,2}} {(0,0),(1,1),(2,2)} {(0,0),(1,1),(2,2),(0,1),(1,0)} {(0,0),(1,1),(2,2),(1,2),(2,1)} {(0,0),(1,1),(2,2),(0,2),(2,0)} {(0,0),(1,1),(2,2 ),(0,1),(1,0) , (1,2), (2,1),(0,2),(2,0)} 2019/5/7

  2019/5/7

4.3 序关系 部分序关系 哈斯Hasse图 极大元与极小元 最大元与最小元 上界与下界 2019/5/7

4.3.1 部分序关系   2019/5/7

  2019/5/7

  2019/5/7

  2019/5/7

4.3.2 哈斯图   2019/5/7

4.3.3 极大元与极小元   2019/5/7

  2019/5/7

4.3.4最大元与最小元   2019/5/7

例 若A = {2, 3, 4, 6, 8},部分序关系是整除关系，则A中 既没有最小元, 也没有最大元。 因为 2不能整除A中所有元素(如2不能整除3), 所以2不是A的最小元，显然其余元素也不是。同理，8 也不能被A中所有元素所整除，所以8不是A的最大元。 实际上，A中所有元素的(最大)公约数1和(最小)公倍数 24均不属于A, 所以A中既没有最小元, 也没有最大元。 又如B = {2, 4, 6, 8},部分序关系是整除关系,则B 的最小元是2,没有最大元。 又如C= {2, 4, 8},部分序关系是整除关系,则C的 最小元是2,最大元是8。 2019/5/7

最小元与极小元的区别 最小元是B中最小的元素，与B中其他元素都可比； 极小元不一定与B中元素都可比，只要没有比它小的元素，它就是极小元。 最小元不一定存在，若存在则必唯一。 类似地可讨论极大元与最大元之间区别。 2019/5/7

  2019/5/7

4.3.5 上界与下界   2019/5/7

最小上界与最大下界   2019/5/7