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

第四章二元关系 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

实例例如, 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)} MR= 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)
关系的性质定义令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

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

A上关系R是非自反的(x)((xA┐(xRx))
定义令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)}

(x)(y)(x,yA∧xRy→yRx)
定义令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)}

(x)(y)((x,yA∧xRy∧x≠y→┐(yRx))
定义令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)}

有些关系既是对称的又是反对称的，如相等关系；有些关系是对称的但不是反对称的，如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)
定义令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)}

显然，上述提到的关系中，，=和≤，(，=都是传递的；在直线的集合中，平行关系是传递的，但垂直关系不是传递的。
显然，上述提到的关系中，，=和≤，(，=都是传递的；在直线的集合中，平行关系是传递的，但垂直关系不是传递的。 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

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

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

等价关系定义设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

[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

[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

[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

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

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

Similar presentations

Presentation on theme: "第四章二元关系 2019/5/7."— Presentation transcript:

Similar presentations

About project

反馈

请登录

Auth with social network:

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

Similar presentations

Presentation on theme: "第四章 二元关系 2019/5/7."— Presentation transcript:

Similar presentations

About project

反馈

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

Presentation on theme: "第四章二元关系 2019/5/7."— Presentation transcript: