二元关系和函数讲解学习

《二元关系和函数讲解学习》由会员分享，可在线阅读，更多相关《二元关系和函数讲解学习（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 是它的第二元素。 例：平面直角坐标系中点的坐标,定义4.2 一个有序 n 元组(n3)是一个有序对

3、, 其中第一个元素是一个有序 n-1元组, 一个有序 n元组记作：, 即 , xn 例：空间直角坐标系中点的坐标 , 等, 都是有序3元组。 n 维空间中点的坐标或 n 维向量都是有序n元组。,二、笛卡尔积,定义4.3 设A, B为集合, 用A中元素为第一元素, B中元素为第二元素, 构成有序对, 所有这样的有序对组成的集合叫做A和B的笛卡儿积, 记作AB。符号化表示为 AB| xA y B 例：Aa, b, B0, 1, 2, 则 AB, , , , , BA, , , , , ,问：如果A中有m个元素, B中有n个元素, 则 AB 和 BA 中都有多少个元素? 答：mn 个 若AB, 则有

4、 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) xAyBC xA(yByC) (xAyB)(xAyC) ABAC (AB)(AC) A(BC) = (AB)(AC),例题,解： (1) 任取 AC xA yC xB yD BD,例： (1)

5、 证明 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) 证： 对于任意的, A(BC) xAyBC xA(yByC) (xAyB)(xAyC) ABAC (AB)(AC). A(BC)(AB)(AC)。,例4.1 设A=1, 2, 求: (A)A

6、 解：(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 yCD xAxB yCyD AC BD (AC)(BD) (2) 不成立。举一反例如下： 若AD, BC1 则有：(AB)(CD)BC, (AC)(BD)。 (3) 和 (4) 都不成立,

7、例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是集合(n2), 它们的n阶笛卡儿积, 记作A1A2An, 其中 AlA2An | x1Alx2A2xnAn 例: A=a, b, 则 A3=, , , , , , , ,三、二元关系的定义,所谓二元

8、关系就是在集合中两个元素之间的某种相关性。 例：甲、乙、丙三个人进行乒乓球比赛, 如果任何两个人之间都要赛一场, 那么共要赛三场。假设三场比赛的结果是乙胜甲、甲胜丙、乙胜丙, 这个结果可以记作 , , , 其中表示 x 胜 y 。它表示了集合甲, 乙, 丙中元素之间的一种胜负关系。,例：有A, B, C三个人和四项工作, , , , 已知A可以从事工作, , B可以从事工作, C可以从事工作, 。那么人和工作之间的对应关系可以记作 R, , , , 这是人的集合A, B, C 到 工作的集合, , , 之间的关系。,定义4.5 如果一个集合为空集或者它的元素都是有序对, 则称这个集合是一个二元

9、关系, 一般记作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)|=2n2 每一个子集代表一个A上的关系, 共 2n2个关系。,A上重要关系的特例,对于任何集合A, 空集是AA的子集, 叫做A上的空关系。 定义4.7 对任意集合A, 定义： EA=| x

10、AyA =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=, , , , , DA=, , , , ,例4.4 设Aa, b, R是P(A)上的包含关系, R|x, yP(A)xy 则有 P(A), a, b, A 。 R, , , , , , , , ,例：设A=1,

11、 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, x2, , xm, B=y1, y2, , yn, R是从A到B的关系, R的关系矩阵是布尔矩阵 MR = rij mn, 其中 rij = 1 R。,关系图：若A= x1, x2, , xm,

12、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 关系的运算,一、关系的基本运算 1、关系的定义域、值域和域 定义4.8 设 R XY, (1) R的定义域： dom R = x | y(R) X (2) R值域：ran R = y | x(R) Y (3) R的

13、域：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+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。 (

14、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, F-1| F (2) F与G的合成记作 FG, FG | z(GF) (3) F在A上的限制记作 FA, FA | FxA (4) A在F下的像记作FA, FAran (FA),例：设 R=, ,

15、, S=, , , , 求：R1 , RS, SR 解：R1 = , , , RS =, , , SR =, , ,利用图示方法求合成,S,R,RS,S,R,SR,例4.6 设F, G是N上的关系, 其定义为 F = | x, yNy = x2 G = | x, yNy = x + 1。 求：G1 、FG、GF、F1, 2、F1, 2 解：(1) G1 = | x, yNy = x -1 =, , , , , (2) FG = |z (GF) = | z (z = x +1 y = z2 ) = | x,yNy = (x +1)2,(3) GF = | z(FG) = | x,yN y = x

16、2 +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) 任取 , 由逆的定义有 (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