二元关系和函数.ppt_三一文库31doc.com

资源描述

《二元关系和函数.ppt》由会员分享，可在线阅读，更多相关《二元关系和函数.ppt（164页珍藏版）》请在三一文库上搜索。

1、第四章二元关系和函数,基本要求：了解关系与集合之间的联系, 序偶与笛卡尔积, 二元关系的定义, 掌握关系图和关系矩阵, 关系的性质, 等价关系、相容关系及序关系的概念及其相互间的区别, 掌握集合的覆盖与划分及等价类的概念, 掌握关系的合成运算、逆运算和闭包运算。掌握函数的定义, 函数与关系之间的关系, 函数的性质, 复合函数与逆函数, 几个重要的函数。,重点：序偶与笛卡尔积, 关系的性质, 等价关系和等价类与集合划分的概念及其求证, 关系的合成、闭包运算, 相容关系和序关系。掌握函数的基本性质, 复合函数与反函数运算。难点：正确地掌握关系的自反性、反自反性、对称性、反对称性和传递性, 等价

2、关系及其证明方法, 传递闭包的正确运算及证明。相容关系与序关系的相互区分。双射函数, 复合函数与反函数。,第四章二元关系和函数,4.1 集合的笛卡尔积与二元关系 4.2 关系的运算 4.3 关系的性质 4.4 关系的闭包 4.5 等价关系和偏序关系 4.6 函数的定义和性质 4.7 函数的复合和反函数,4.1 集合的笛卡儿积与二元关系,一、有序对定义4.1 由两个元素 x 和 y (允许 x=y )按一定的顺序排列成的二元组叫做一个有序对(也称序偶), 记作, 其中 x 是它的第一元素, y 是它的第二元素。例：平面直角坐标系中点的坐标,有序对的性质： 1. 有序性：当 xy 时, 。

3、2. 的充分必要条件是,例： = , 求 x, y。解：3y 4 = 2, x+5 = y y = 2, x = 3,= x=u y=v,定义4.2 一个有序 n 元组(n3)是一个有序对, 其中第一个元素是一个有序 n-1元组, 一个有序 n元组记作：, 即 , xn 例：空间直角坐标系中点的坐标 , 等, 都是有序3元组。 n 维空间中点的坐标或 n 维向量都是有序n元组。,二、笛卡尔积,定义4.3 设A, B为集合, 用A中元素为第一元素, B中元素为第二元素, 构成有序对, 所有这样的有序对组成的集合叫做A和B的笛卡儿积, 记作AB。符号化表示为 AB| xA y B 例：Aa, b

4、, B0, 1, 2, 则 AB, , , , , BA, , , , , ,问：如果A中有m个元素, B中有n个元素, 则 AB 和 BA 中都有多少个元素? 答：mn 个若AB, 则有 xA 和 yB。若AB, 则有 xA 或者 y B.,笛卡儿积运算的性质,1. 若A, B中有一个空集, 则它们的笛卡儿积是空集, 即 BA 2. 当AB且A, B都不是空集时, 有 ABBA 所以, 笛卡儿积运算不适合交换律。 3. 当A, B, C都不是空集时, 有 (AB)CA(BC) 所以, 笛卡儿积运算不适合结合律。,性质的证明,证明： A(BC)=(AB) (AC) 证：任取 A(BC) x

5、AyBC xA(yByC) (xAyB)(xAyC) ABAC (AB)(AC) A(BC) = (AB)(AC),例题,解： (1) 任取 AC xA yC xB yD BD,例： (1) 证明 A=B C=D AC=BD (2) AC=BD是否推出 A=B C=D ? 为什么？,(2) 不一定。反例如下： A=1, B=2, C=D=, 则 AC=BD 但是 AB。,笛卡儿积运算的性质,4. 笛卡儿积运算对或运算满足分配律, 即 A(BC) (AB)(AC)； (BC)A (BA)(CA)； A(BC) (AB)(AC)； (BC)A (BA)(CA)。,证明 A(BC)(AB)(AC)

6、证：对于任意的, A(BC) xAyBC xA(yByC) (xAyB)(xAyC) ABAC (AB)(AC). A(BC)(AB)(AC)。,例4.1 设A=1, 2, 求: (A)A 解：(A)A , 1, 2, 1, 21, 2 , , , , , , , ,例4.2 设A, B, C, D为任意集合, 判断以下等式是否成立, 说明为什么。 (1) (AB)(CD)(AC)(BD)； (2) (AB)(CD)(AC)(BD)； (3) (AB)(CD)(AC) (BD)； (4) (AB) (CD) (AC) (BD)。,解：(1) 成立。因为对于任意的 , (AB)(CD) xAB

7、 yCD xAxB yCyD AC BD (AC)(BD) (2) 不成立。举一反例如下：若AD, BC1 则有：(AB)(CD)BC, (AC)(BD)。 (3) 和 (4) 都不成立,例4.3 设A, B, C, D为任意集合, 判断以下命题的真假。 (1) 若AC且BD, 则有ABCD。 (2) 若ABCD, 则有AC且BD. 解 (1) 命题为真。请思考：为什么？ (2) 命题为假。当AB时, 或者A且B时, 该命题的结论是成立的。但是当A和B之中仅有一个为时, 结论不一定成立, 例如, 令ACD, B1, 这时ABCD, 但 BD。,定义4.4 设A1, A2, , An是集合(n

8、2), 它们的n阶笛卡儿积, 记作A1A2An, 其中 AlA2An | x1Alx2A2xnAn 例: A=a, b, 则 A3=, , , , , , , ,三、二元关系的定义,所谓二元关系就是在集合中两个元素之间的某种相关性。例：甲、乙、丙三个人进行乒乓球比赛, 如果任何两个人之间都要赛一场, 那么共要赛三场。假设三场比赛的结果是乙胜甲、甲胜丙、乙胜丙, 这个结果可以记作 , , , 其中表示 x 胜 y 。它表示了集合甲, 乙, 丙中元素之间的一种胜负关系。,例：有A, B, C三个人和四项工作, , , , 已知A可以从事工作, , B可以从事工作, C可以从事工作, 。那么人和工

9、作之间的对应关系可以记作 R, , , , 这是人的集合A, B, C 到工作的集合, , , 之间的关系。,定义4.5 如果一个集合为空集或者它的元素都是有序对, 则称这个集合是一个二元关系, 一般记作R。对于二元关系R, 如果R, 可记作 xRy；如果R, 可记作 x y。,四、从A到B的关系与A上的关系,定义4.6 设A, B为集合, AB的任何子集所定义的二元关系称作从A到B的二元关系, 特别当AB时, 则叫做A上的二元关系。关系 RAB, R 是从A到B的二元关系关系 RAA, R 是A上的二元关系计数 A上有多少个不同的二元关系? |A|=n |AA|=n2 |P(AA

10、)|=2n2 每一个子集代表一个A上的关系, 共 2n2个关系。,A上重要关系的特例,对于任何集合A, 空集是AA的子集, 叫做A上的空关系。定义4.7 对任意集合A, 定义： EA=| xAyA =AA 全域关系 IA=| xA 恒等关系,例：A=0, 1, 2, 则 EA, , , , , , , , IA, , 。,集合A上的常见关系,小于或等于关系：LA=|x, yAxy。其中：AR 整除关系：DB=|x, yBx整除y, 其中：BZ* , Z*是非零整数集包含关系：R|x, yAxy, 其中：A是集合族。,例：设 A=1, 2, 3, Ba, b 则 LA=, , , , ,

11、DA=, , , , ,例4.4 设Aa, b, R是P(A)上的包含关系, R|x, yP(A)xy 则有 P(A), a, b, A 。 R, , , , , , , , ,例：设A=1, 2, 3, 4, 下面各式定义的R都是A上的关系, 试用列元素法表示R。 (1) R= | x是y的倍数 (2) R= | (x-y)2A (3) R= | x/y是素数 (4) R= | xy,解： (1) R = , (2) R = , , (3) R = , , (4) R = EAIA = , , , , , , ,关系的表示,表示方式：关系的集合表达式、关系矩阵、关系图关系矩阵：若A=x1,

12、 x2, , xm, B=y1, y2, , yn, R是从A到B的关系, R的关系矩阵是布尔矩阵 MR = rij mn, 其中 rij = 1 R。,关系图：若A= x1, x2, , xm, R是从A上的关系, R 的关系图是GR=, 其中 A为结点集, R 为边集, 如果属于关系R, 在图中就有一条从 xi 到 xj 的有向边。注意：A, B为有穷集关系矩阵适于表示从 A 到 B 的关系或者 A上的关系关系图适于表示 A 上的关系,关系图GR,例：设A1, 2, 3, 4, A上的关系 R, , , , 求：R的关系矩阵MR和关系图GR 解：关系矩阵MR,4.2 关系的运算,一、

13、关系的基本运算 1、关系的定义域、值域和域定义4.8 设 R XY, (1) R的定义域： dom R = x | y(R) X (2) R值域：ran R = y | x(R) Y (3) R的域：fld R = dom Rran R XY,dom R 是R的所有序偶的第一个元素构成的集合 ran R 是R的所有序偶的第二个元素构成的集合。例：实数集R上的关系 S=|x,yRx2+y2=1, dom S = ran S = fld S = -1, 0,1。,例4.5 下列关系都是整数集Z上的关系, 分别求出它们的定义域和值域,(1) R1x, yZ xy； (2) R2x, yZ x2+

14、y2=1； (3) R3x, yZ y2x； (4) R4x, yZ x y=3。解 (1) dom R1 ran R1Z。 (2) R2, , , dom R2ran R2 0, 1, -1。 (3) domR3Z ranR32z | zZ, 即偶数集 (4) domR4ranR4-3, 3。,从 A 到 B 的某些关系 R 的图解方法(不是R的关系图) 1. 用封闭的曲线表示 R的定义域(或集合A)和值域 (或集合B)。 2. 从 x 到 y 画一个箭头, 如果 R,R2,R3,2、关系的逆与合成、限制和象,定义4.9 F, G为任意的关系, A为集合, 则 (1) F的逆记作 F-1,

16、 , , , (2) FG = |z (GF) = | z (z = x +1 y = z2 ) = | x,yNy = (x +1)2,(3) GF = | z(FG) = | x,yN y = x2 +1 (4) F1,2=, (5) F1,2= ran (F1,2) = 1,4 注：合成运算不满足交换律, 即对任何关系F、G, 有 FGGF,定理4.1 设F、G、H是任意的关系, 则有 (1) (F1)1 = F (2) dom F1 = ran F, ran F1 = dom F (3) (FG)HF(GH) (4) (FG)1 = G1F1 如何证明 ?,二、关系运算的性质,证：(1

17、) 任取 , 由逆的定义有 (F1)1 F1 F (F1)1 =F (2) 任取 x, xdom F1 y(F1) y(F) xran F dom F1 = ran F 。同理可证 ran F1 = dom F 。,(3) 任取, (FG)H t(H FG) t (Hs (G)F) ) t s (H GF) s (Ft (HG) s (FGH) F (G H) (FG)H =F(GH),(4) 任取, (FG)1 (FG) t (GF) t (F1G1) G1F1 (FG)1= G1F1 #,定理设R为A上的关系, 则有 RIA = IAR = R 证：任取, RIA t ( IA R)

18、t ( IA x=t R) R RIA = IAR = R #,定理4.2 设F、G、H为任意的关系, 则有 (1) F(GH) = FGFH (2) (GH)F = GFHF (3) F(GH) FGFH (4) (GH)F GFHF 注：对不满足分配律如何证明 ?,证：(1) 任取 F(GH) z ( (GH)F) z (GH)F) z (GF)(HF) z (FG) z (FH) FGFH FGFH F (GH) = F GF H 同理可证 (2) (FG) H = F GF H,(3) 任取 F(GH) t (GH) F ) t (G) F ) t (GF) (HF) ) t(GF

19、) t(HF) FG FH FGFH F (GH) F GF H 同理可证 (4) (FG) H F GF H #,三、A上关系的幂运算,定义4.10 设 R 为A上的关系, n为自然数, 则 R 的n次幂规定如下： (1) R0=| xA (2) Rn=Rn-1R, n1 由定义知：对A上的任何关系R1, R2都有: R10=R20=IA 对A上的任何关系R恒有: R1=R0R=RR0=R,例4.8 设 A = a, b, c, d, R = , , , , 求：R的各次幂。,关系幂Rn的求法,有穷集A上给定关系 R, 如何求 Rn ? 1. 集合运算：逐个计算R2=RR, R3= R2R

20、, 2. 关系矩阵：设R的关系矩阵为 M , 计算关系矩阵的积 M*M, 在两个矩阵相乘时, 第 i 行第 j 列的元素 rij 满足下式(i, j=1, 2, 3, 4) rij = ri1 r1j + ri2 r2j + ri3 r3j + ri4 r4j 此处 + 是逻辑加, 即 0+0=0, 0+1=1, 1+0=1, 1+1=1,关系幂Rn的求解方法,3. 关系图：对R的关系图G中的任何一个结点x, 考虑从 x 出发的长为 n 的路径, 如果路径的终点是 y , 则在Rn的关系图中有一条从 x 到 y 的有向边。即： Rn,例4.8 设 A = a, b, c, d, R = , ,

21、 , , 求：R的各次幂。解：R与R2的关系矩阵分别为,同理, R0=IA, R3和R4的矩阵分别是：,显然, M4=M2, 即 R4=R2。因此：R2=R4=R6=, R3=R5=R7= 对于有穷集A, A上关系 R 的不同幂只有有限个。,R0, R1, R2, R3, 的关系图如下图所示,四、幂运算的性质,定理设A为n元集, R是A上的关系, 则存在自然数 s, t , 使得 Rs=Rt。证：R为A上的关系, 由|A|=n, A上的不同关系只有2n2个。当列出R的各次幂：R0, R1, R2, R2n2, 必然存在自然数 s, t 使得 Rs=Rt。 # 对于有穷集合A上的关系R

22、, R的不同幂只有有限个。,四、幂运算的性质,定理4.3 设 RAA, 且m, nN, 则 (1) RmRn = Rm+n, (2) (Rm)n = Rm n。证：用归纳法证明,证：(1) 对于任意给定的 mN, 对 n 进行归纳若 n=0, 则有：RmR0= RmIA= Rm=Rm+0 假设 n=n 时成立, 即RmRn = Rm+n, 则当 n=n+1时, 有 RmRn+1 = Rm (RnR) = (RmRn) R = Rm+n R = Rm+n+1 由归纳法知, 对一切 m, nN 有 RmRn = Rm+n (2) 对于任意给定的 mN, 对 n 进行归纳若 n=0, 则有：(

23、Rm)0= IA= R0= Rm0 假设 n=n 时成立, 即(Rm)n = Rm n, 则当 n=n+1时, 有 (Rm)n+1 = (Rm)nRm = (Rm n) Rm = Rm n+m = Rm(n+1) 由归纳法知, 对一切m, nN有 (Rm)n = Rm n。,关系是集合, 故第三章所定义的集合运算对关系都适用。规定关系运算中逆运算优先于其它运算所有的关系运算都优先于集合运算,运算的优先顺序,4.3 关系的性质,关系的性质是指集合中二元关系的性质, 这些性质扮演着重要角色, 下面将定义这些性质, 并给出它的关系矩阵和关系图的特点。设R是A上的关系, R的性质主要有以下5种

24、：自反性、反自反性、对称性、反对称性、传递性,一、关系性质的定义,令RAA, 则 R是自反的 (x)( xAR ) R是反自反的 (x)( xAR ) R是对称的 (x)(y) ( x, yARR ) R是反对称的 (x)(y) (x, yARRx=y) 关系R是传递的 (x)(y)(z) (x, y, zARRR,例：设A=1, 2, 3, R1, R2, R3是A上的关系, 其中 R1, R2, , , R3 问：R1, R2和R3是否为A上的自反或反自反关系？解： R2是自反的; R3是反自反的; R1既不是自反的也不是反自反的。自反与反自反关系的关系矩阵、关系图有何特点？,注意

25、：任何一个不是自反的关系, 未必是反自反的；反之, 任何一个不是反自反的关系, 未必是自反的。存在既不是自反的也不是反自反的二元关系。,例：设A1,2,3, R1, R2, R3和R4都是A上的关系, 其中 R1, , R2, , R3, , R4, , 问：R1, R2, R3和R4是否为A上对称和反对称的关系? 解：R1既是对称也是反对称的。 R2是对称的但不是反对称的。 R3是反对称的但不是对称的。 R4既不是对称的也不是反对称的。对称与反对称关系的关系矩阵、关系图有何特点？,例：设A1, 2, 3, R1, R2, R3是A上的关系, 其中 R1, , R2, , R3 问：R1,

26、 R2和R3是否为A上的传递关系? 解：R1 和 R3 是A上的传递关系, R2 不是A上的传递关系。,二、关系的性质与关系矩阵、关系图的关系,通过上面几个实例, 看出：若A上关系R是自反的, 则MR中主对角线上元素全为1(rii=1), 而GR中每个结点都有环; 反之亦然。若A上关系R是反自反的, 则MR中主对角线上元素全为0(rii=0), 而GR中每个结点都无环; 反之亦然。, 若A上关系R是对称的, 则MR是对称矩阵(rij=rji), 而GR中任何两结点若有弧必成对出现; 反之亦然。若A上关系R是反对称的, 则MR中以主对角线为对称元素不能同时为1(若rij=1(ij), 则有

27、rji=0), 而GR中若两结点间有弧不成对出现; 反之亦然。, 若A上关系R是传递的, 则MR中若rij=rjk=1, 则 rik=1, 而GR中若有弧和则必有弧; 反之亦然。上述是正确的, 但不易从MR和GR中判定关系R传递性。, 任何集合上的相等关系是自反的、对称的, 反对称的和传递的, 但不是反自反的。整数集合Z中, 关系是自反的、反对称的和传递的, 但不是反自反的和对称的。关系是反自反的, 反对称的和传递的, 但不是自反的和对称的。,常见关系的性质, 非空集合上的空关系是反自反的, 对称的, 反对称的和传递的, 但不是自反的。空集合上的空关系则是自反的, 反自反的, 对称的,

28、反对称的和传递的。非空集合上的全域关系是自反的, 对称的和传递的, 但不是反自反的和反对称的。,例：设A=1, 2, 3, 判断下列关系的性质。 R1=, , , R2=, , R3=, R4=, , R5= R6=, , 解：R1自反, 传递。 R2 对称, 反自反, 不传递。 R3 不自反, 不反自反, 对称, 反对称, 传递。 R4 反对称, 反自反。 R5 对称, 反对称, 传递。 R6 不对称, 不反对称, 反自反, 不传递。,设R1和R2是集合A上的关系, 它们具有某些性质, 那么, 在它们经过、等运算后得到的新关系是否具有原来的性质呢？可以证明以下结论：,三、集合运算对关

29、系性质影响,可以证明以下结论：,1. R1、R2为A上的自反关系, 则 R1R2、R1R2仍为A上的自反关系。 2. R1、R2为A上的反自反关系, 则 R1R2、R1R2、R1R2仍是A上的反自反关系。 3. R1、R2为A上的对称关系, 则 R1R2、R1R2、R1R2仍保持其对称性。 4. R1、R2为A上的反对称关系, 则 R1R2、R1R2仍保持其反对称性, 但R1R2则不一定。 5. R1、R2是上的传递关系, 则 R1R2仍为A上的传递关系。,对于保持关系性质的运算, 都可以经过命题演算的方法给出一般的证明。对于不保持关系性质的运算, 都可举一反例说明。,例：设R1、R2为A上

30、的对称关系, 证明：R1R2也是A上的对称关系。证：对任意的, R1R2 R1R2 R1R2 ( R1, R2对称) R1R2 R1R2是A上的对称关系。,四、关系性质的等价描述,定理设R为A上的关系, 则 (1) R在A上自反的当且仅当 IAR (2) R在A上反自反的当且仅当 RIA= (3) R在A上对称的当且仅当 R=R-1 (4) R在A上反对称的当且仅当 RR-1IA (5) R在A上传递的当且仅当 RRR,(1) R在A上自反的当且仅当 IAR,必要性。设R是自反的, 证 IAR 任取, R是A上自反的, 必有： IA x, y A x=y R 从而证明了 IAR

31、充分性。设 IAR, 证R是自反的任取x, 有: xA IA R 因此 R 在A上是自反的。,(2) R在A上反自反的当且仅当 RIA=,必要性。设 R是反自反的, 证 RIA= 用反证法。设RIA, 必存在RIA 。由于IA是A上的恒等关系, 从而推出 xAR。这与R在A上是反自反的相矛盾。充分性。设 RIA= , 证 R是反自反的任取x, 则有: xA IA R 从而证明了R在A上是反自反的。,(3) R在A上对称的当且仅当 R=R-1,必要性。设R是对称, 证 R=Rc 。任取, 有： R R （ R对称） R-1 R=R-1 充分性。设 R=R-1 , 证R是对称的。

32、任取, R=R-1 R R-1 R R在A上是对称的。,关系的性质三种等价条件,4.4 关系的闭包,闭包运算是关系运算中一种比较重要的特殊运算, 是对原关系的一种扩充。在实际应用中, 有时会遇到这样的问题, 给定的某个关系不具有某种性质, 要使其具有该性质, 就需对原关系进行扩充。闭包运算是关系上的一元运算, 其目的是构造一个新关系是包含该关系且具有某种性质的最小关系。,定义4.11 设R是A(A)上的二元关系, R 的自反 ( 对称、传递 ) 闭包是A上的关系R, 且R 满足以下条件： R是自反的（对称的、传递的） R R 对任何自反(对称、传递)的关系 R , 若 R” R, 则 R

33、” R。将R的自反、对称和传递闭包分别记为: r(R)、 s(R) 和 t(R) 。,一、闭包的定义,二、闭包的构造方法,定理4.4 设 R 是 A(A)上的二元关系, 则 r(R) = RIA s(R) = RR-1 t(R) = RR2 R3 P89 例 4.10,例设A = a, b, c, d , R = , , , , 则R和r(R), s(R), t(R)的关系图如下图所示。,用关系图、关系矩阵求闭包的一般方法,1. 关系矩阵MR (1) Mr(R)= MR+E（E为单位矩阵, +为逻辑加） (2) Ms(R)= MR+ MR（MR的转置矩阵） (3) Mt(R)= MR+ M

34、R2+ MR3+ 注意：在上述等式中矩阵的元素相加时使用逻辑加。,用关系图、关系矩阵求闭包的一般方法,2. 关系图GR r(R)的关系图：检查GR的每个顶点, 哪个结点上没有环就添加上一个环即可。 s(R)的关系图：将GR中的单向边全部改为双向边即可。 t(R)的关系图：依次检查R的关系图GR的每个结点 x, 把从 x 出发的长度不超过 n (|A|=n)的所有路径的终点找到。如果x到该结点无边, 就加上一条边即可。,定理1 设R是非空集合A上的关系, 则 R是自反的当且仅当 r(R)=R R是对称的当且仅当 s(R)=R R是传递的当且仅当 t(R)=R,三、闭包的主要性质,证：只证明,

35、余下自证。若R是自反的, 则由定义可知, R具有对R所要求的性质, 故 r(R)=R；反之, 若r(R)=R, 则由前面定义知, R 是自反的。 # 由闭包的定义可以知道, 构造关系R的闭包方法就是向R中加入必要的有序对, 使其具有所希望的性质。下面定理体现了这一点,定理2 设R1和R2是非空集合A上的关系, 且 R1R2, 则 1. r(R1) r(R2) 2. s(R1) s(R2) 3. t(R1) t(R2) 证： 1. 由闭包的定义 (1)、(2) 知：r(R2)是自反的, 且R2r(R2)。 R1R2, R1 r(R2) 又由闭包定义 (3) 知：r(R1) r(R2)。类

36、似地可证明2和3。,定理3 设 RAA, 则 1. 若R是自反的, 则 s(R) 与 t(R) 也是自反的。 2. 若R是对称的, 则 r(R) 与 t(R) 也是对称的。 3. 若R是传递的, 则 r(R) 是传递的。,定理4 设 RAA, 则 rs(R) = sr(R) rt(R) = tr(R) st(R) ts(R),4.5 等价关系与偏序关系,一、等价关系的定义与实例定义4.12 设R是非空集合A上二元关系, 若R是自反的、对称的和传递的, 则称R为A上的等价关系。设R是一个等价关系, 如果R, 称 a 等价于 b, 记作 ab。由于R是对称的, a等价b即b等价a, 反之亦然,

37、 a与b 彼此等价。,鉴于空集合上的二元关系是等价关系, 是一种平凡情形, 因此, 一般讨论非空集合上的等价关系。模m等价是Z或其子集上的等价关系, 并且是一类重要的等价关系。,例4.11 A=1, 2, , 8, P91 R = |x, yAxy(mod 3), 其中 xy(mod 3) 叫做 x 与 y 模 3相等, 即 x 除以 3 的余数与 y 除以 3 的余数相等。关系图如下所示：,例4.11 A=1, 2, , 8, R = |x, yAxy(mod 3), 不难验证R 是 A上的等价关系。 (1) xA, 有xx(mod 3) R 是自反的 (2) x, yA, 若xy(mo

38、d 3), 则有yx(mod 3), R 是对称的 (3) x, y, zA, 若xy(mod 3), yz(mod 3), 则有xz(mod 3), R 是传递的,1. 等价类定义4.13 设R为非空集合A上的等价关系, 对 xA, 令 xR= y| yAxRy 则称 xR 为 x关于R的等价类, 简称 x的等价类, 简记为 x 。,二、等价类及其性质,例4.11 A=1, 2, , 8, R = |x, yAxy(mod 3), 前已验证 R 是A上的等价关系则 A上模3同余等价关系的等价类: 1 = 4 = 7 = 1, 4, 7 2 = 5 = 8 = 2, 5, 8 3 = 6

39、= 3, 6,定理4.5 设R是非空集合A上的等价关系, 则 xA, xR是A的非空子集。 x, yA, 若R, 则 x=y。 x, yA, 若R, 则 xy=。 x | xA =A 利用非空集合A及其上等价关系可以构造一个新集合商集。,2. 等价类的性质,1. 商集定义4.14 设R是非空集合A上的等价关系, 以R的所有等价类为元素的集合称为A关于R的商集, 记作 A/R , 即 A/R = xR| xA ,三、商集与集合的划分,该定义表明了, 与商集 A/R 有密切联系的概念是集合的划分。如：设 A=1, 2, , 8, 则 A上模3同余等价关系的商集: A/R =1, 4, 7, 2

40、, 5, 8, 3, 6 A上恒等关系、全域关系的商集为： A/IA =1, 2, 3, 4, 5, 6, 7, 8 A/EA =1, 2, 3, 4, 5, 6, 7, 8,2. 集合的划分定义4.15 设A为非空集合, 若存在一个A的子集族 ( P(A) 满足下面的条件： (1) (2) xy( x, y x y xy= ) (3) =A 则称是A的一个划分, 称中的元素为A的划分块。,例4.14 设 A=a, b, c, d, 给定1, 2, 3, 4, 5如下： (1) 1=a, b, c, d (2) 2= a, b, c, d (3) 3=a,b, c, a,d (4) 4=

41、, a,b, c,d (5) 5=a, b,c 问：哪些是集合A的划分？解：1和 2是集体A的划分, 其余都不是。为什么？,例4.15 设 A =1, 2, 3, 求A上所有的等价关系。解：如下图, 先做出A的所有划分。,这些划分与A上的等价关系之间的一一对应是: 1对应全域关系EA, 5对应恒等关系IA, 2, 3和4分别对应于等价关系R2, R3和R4, 其中: R2 = , U IA R3 = , U IA R4 = , U IA,3. 商集与划分的对应关系,商集A/R就是A的一个划分, 不同的商集对应不同的划分。任给集体A的一个划分, 如下定义A上的关系R： R=|x, yAx

42、与y在的同一划分块中则R为A上的等价关系, 且等价关系R所确定的商集就是。 A上的等价关系与A的划分是一一对应,等价关系与划分是两个不同的概念, 表示方法也不同：等价关系是序偶的集合, 划分是子集的集合给定划分 , 求对应等价关系的方法：设 =A1, A2, , Am是集合A的一个划分, 定义R为： R=|a, b Ai , i=1, 2, , m （即 R= A1A1A2A2AmAm）则R是A上的等价关系, 且 = A/R。,1. 偏序关系的定义与实例定义4.16 设R是非空集合A上的关系, 若R是自反的, 反对称和传递的, 则称R为A上的偏序关系, 记作。设是偏序关系,

43、, 则记作 x y, 读作“小于或等于”。注意：这里的“小于或等于”不是指数的大小, 而是在偏序关系中的顺序性。,四、偏序关系,例：集合A上的恒等关系IA是A上的偏序关系。实数集合上的小于或等于、正整数集上的整除关系、集合A的幂集P(A)上的包含关系是相应集合上的偏序关系。包含关系, A B(常记: AB)是指A包含于B; 整除关系, 3 6 (常记: 3|6) 是指3整除6 若 R是A上的偏序, 则 R-1也是A上偏序。若用表示 R, 则用表示 R-1, 即互为对偶。,定义4.17 一个集合A与A上的偏序关系R一起叫作偏序集, 记作。如: 整数集合Z和小于或等于关系构成偏序集, 集合A的幂集P(A)和包含关系构成偏序集。,2. 偏序集,定义4.18 设为偏序集, a, bA, 若a b 或 b a 成立, 则称 a与b 是可比的若a b (即 a b ab ), 且不存在 cA使得 acb, 则称 b 盖住 a 。定义可知, 在偏序集中, a, bA, 可能有

展开阅读全文