《离散数学第2章 关系》由会员分享，可在线阅读，更多相关《离散数学第2章 关系（84页珍藏版）》请在金锄头文库上搜索。
1、1,世间万物都存在着联系. 利用集合刻划这种联系的数学模型 关系. “关系” 的相关内容对今后学习数据结构、数据库等许多课程都是很重要的.,1,Chapter 2 关系,2,例 学生 A = 张三, 李四, 王五; 课程 B = 英语, 数学实验, 离散数学, 数据结构, 汇编语言; 成绩 C = 优, 良, 合格, 不合格.,2,2.1 关系的概念,2.1.1 n 元关系的定义,选课 (A与B之间的关系): R = (张三, 离散数学), (张三, 数据结构), (张三, 英语), (李四, 数据结构), (王五, 数学实验), (王五, 汇编语言).,课程得分 (A, B与C之间的关系):
2、,R = (张三, 离散数学, 优), (张三, 数据结构, 良), (张三, 英语, 优), (李四, 数据结构, 优), (王五, 数学实验, 合格), (王五, 汇编语言, 良).,3,定义 特别地, 若 , 则称 R 为 A 上的n元关系. n = 2: 2元关系. 例 设 A = 0, 1, 2, 3, 4, A上的关系R = (x, y)|x = y+1 或 y = x/2, 试用列举法求出R. 解 R = (1, 0), (2, 1), (3, 2), (4, 3) (0, 0), (2, 1), (4, 2),3,4,2元关系: 两个集合A和B(可以相同)间的关系 A到B的关系
3、: A到A, 即A上的关系: A到B的空关系 AB与全关系AB AB. 例 A = a, b, B = 1, 2, 3, Theorem |A| = m, |B| = n, 则A到B的关系有2mn个. 提示 |A B| = mn. 若|A| = m, 则A上的关系有2m2个.,4,2.1.2 二元关系,?,?,5,关系符号: 设R AB, 若(x, y) R, 则称元素x与y有关系R, 可记为xRy: 例 实数集合R上的大于“”关系: 例 整数集合Z上的模k同余关系k: 定义：A上的恒等关系: 例 若A = a, b, c, 则IA = (a, a), (b, b), (c, c).,k |
4、(x - y) x 除以k的余数 = y 除以k的余数.,6,定义域: 设R AB, dom R = x | x A, 存在 y B, 使得(x, y) R 即R中所有有序对中第一位置元素组成的集合, 它显然是A的子集. 例 R = (1, 1), (1, 3), (2, 2), (2, 4), (3,1), (3, 3), (4, 2), (4, 4) dom R = 1, 2, 3, 4. 值域: 设R AB, ran R = y | y B, 存在 x A, 使得(x, y) R 即R中所有有序对中第二位置元素组成的集合, 它是B的子集. 在上例中, ran R = 1, 2, 3, 4
5、.,6,2.1.3 关系的定义域与值域,7,1、关系图 情形1 R是 A 到 B (包括A上)的关系 例 A = a, b, c, d, B = 1, 2, 3, R = (a, 2), (a, 3), (c, 2), (d, 2).,7,2.1.4 关系的表示,(除集合表示外),8,情形2 R是 A 上的关系 例 A = a, b, c, d, R = (a, b), (a, c), (c, a), (d, c), (d, d).,8,9,2、关系矩阵 例 A = a, b, c, d, B = 1, 2, 3, R = (a, 2), (a, 3), (c, 2), (d, 2).,9,1
6、0,例 A = a, b, c, B = 1, 2, 3, f: A B, f(a) = 2, f(b) = 3, f(c) = 3. 备注 一般来说, A到B的关系不是A到B的函数.,2.1.5 函数的关系(集合)定义,11,函数: A 到 B 有关系 f, 并满足以下条件, (1) dom f = A; (2) 例 判断自然数集合N上的下列关系能否构成函数. f = (x, y) | x, y N, x + y 5 f = (x, y) | x, y N, y 为小于等于x的素数个数 作业 习题 2.1 P44: 2. 13(4). 15.,11,不能,能,12,集合运算:,12,2.2
7、关系的运算 2.2.1 关系的集合运算,13,逆关系: 例 A = a, b, c, d, B = 1, 2, 3, R = (a, 3), (c, 2), (a, 2), (b, 2). 逆关系的关系图与关系矩阵: 逆运算的性质: Theorem (对合律),13,2.2.2 关系的逆运算,14,Theorem (逆运算与关系的集合运算并, 交, 补的关系) (1) (2) (3) Proof (2) (4) (5),14,15,1、关系 R 与关系 S 的复合 RS 例,15,2.2.3 关系的复合运算,16,借助于关系图理解复合运算:,16,17,例,A=1, 2, 3, 4,R1=(2
8、,4), (3,3),(4,2),(4,4), R2=( 2,1), (3,2), (4,3),R1 R2 = (2,3), (3,2),(4,1),(4,3),R2 R1 = (3,4),(4,3),18,借助于关系矩阵进行复合运算:,0，1之间的逻辑加 , 逻辑乘,19,设 A=aij为m p布尔矩阵，B=bij为p n布尔矩阵,A和B的逻辑乘运算为m n布尔矩阵C = cij 定义如下,矩阵的逻辑乘运算,20,矩阵的逻辑乘运算,2 3,3 2,2 2,1,0,1,1,R1=(1,b), (2,b),(2,c), R2=( a,1), (a,2), (b,1),(c,1),(c,2),R1
9、 R2 = (1,1), (2,1),(2,2),A=1, 2,B=a,b,c,21,备注 关系的复合运算不满足交换律,即一般来说 R S S R, 但关系的复合运算满足结合律: Theorem (1) (复合运算对并运算可分配) (2) 备注 一般来说,21,22,Theorem (复合运算与逆运算之间的关系) Proof 备注 本性质与矩阵的有关运算性质类似(注意顺序),22,23,2、关系 R 的方幂运算 Rn 备注 若R A B, 一般来说, R R 没有意义. 方幂运算的性质,23,24,例,A = a,b,c ,R = (a,b),(b,c),(c,a), T= (a,b),(b,
10、c),(c,c),解 R2 = (a,c),(b,a),(c,b),R3 = (a,a),(b,b),(c,c),R4 = R,试求R,T的各次幂。,R5 = R2,Rn = Rres3(n),T2 = (a,c),(b,c),(c,c),T3 = (a,c),(b,c),(c,c)= T2,T4 = T3 T =T2 T= T3 =T2,Tn = T2,(n2),=R0,25,定理： 设|A| n，R为A上关系，则存在整数k, l , 0kl2n2 ,使Rk = Rl 。,证：,|A| n，,故A上共有2n2个不同关系，,而R0 , R1, , R2n2均为A上的关系，共有2n21个，,由鸽
11、笼原理,它们至少有两个相同。,P62,26,2.2.4 关系的其他运算 在具体应用中, 如在数据库理论中, 还会涉及到关系的其他运算, 如关系的连接运算、关系的投影运算、关系的限制运算、关系的除运算等. 关系的3种闭包运算 r(R), s(R), t(R).,26,27,关系的限制运算 作业 习题 2.2 P51 ：3, 8.,27,A = a, b, c, d, e, f ,R = (a, a), (a, c), (b, c), (a, e), (b, e), (c, e) ,例,取 B = a, b, c ,R 在 B上的限制为,(a, a), (a, c), (b, c) .,28,定义
12、：设R A A, 若对于任意 x A, 均有(x, x) R, 则称 R 是 A 上的自反关系, 或称 R 是自反的, 或称 R 具有自反性. 例 A = a, b, c, d, R = (a, a), (a, b), (b, b), (c, c), (c, a), (d, d)是否自反? 例 Z 上的整除关系 | 是自反的; P(X) 上的包含关系 是自反的;,28,2.3 关系的性质,2.3.1 自反性,29,Theorem R 自反 IA R. 备注 空集上的关系只有空关系一个, 该空关系是空集上的自反关系. 问题 如何根据 R 的关系矩阵及关系图去判断 R 是否自反?,29,30,定义
13、: 设 R A A, 若对于任意 x A, 均有 (x, x) R, 则称 R 是 A 上的反自反关系, 或称 R 是反自反的, 或称 R 具有反自反性. 例 A = a, b, c, d, R = (b, a), (a, b), (b, c), (c, d), (c, a) 是否反自反? 例 Z 上的整除关系 | 不是反自反的; P(X) 上的包含关系 不是反自反的;,30,2.3.2 反自反性,31,Theorem R 反自反 IA R = . 备注 空关系 是空集 上的反自反关系. 问题 如何根据 R 的关系矩阵及关系图去判断 R 是否反自反?,31,32,解：,判断下列1,2,3,4上
14、的关系的自反性和反自反性?,R1 = (1,1),(1,2),(2,1),(2,2),(3,4),(4,1),(4,4) R2 = (1,1),(1,2),(2,1) R3 = (1,1),(1,2),(1,4),(2,1),(2,2),(3,3),(4,1),(4,4) R4 = (2,1),(3,1),(3,2), (4,1),(4,2),(4,3) R5 = (1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,3), (3,4),(4,4) R6 = (3,4),自反性：,反自反性：,R3,R5,R4,R6,33,R1 = (a, b) | a b R2 = (a, b) | a b R3 = (a, b) | a = b or a = -b R4 = (a, b) | a = b R5 = (a, b) | a = b + 1 R6 = (a, b) | a + b 3,R1,R3,R4,R2,R5, a = b ,判断下列整数集上的关系的自反性和反自反性?,解：,自反性：,反自反性：,34,A 上的自反关系与反自反关系的区别与联系: 一、R 既自反又反自反? 二、R 自反但不是反自反? 三、R 不是自反的但是反自反? 四、R 既不是自反的又不是反自反?,34,空集
