第4讲 关系的概念与运算 重点内容: 1.关系的定义. 2.关系的运算,特别是关系的复合运算.

Chapter 2 关系 世间万物都存在着联系.借助于集合可以给出刻划这种联系的数学模型 — 关系(Relation). 在信息科学中,数据与数据之间总存在一定的关系,关系这些内容对今后学习数据结构以及数据库等很多课程都是很重要的. 我们不以个别特殊关系为研究对象,而是关注关系的一般特性.

2.1 关系的概念 1. n元关系的定义 日常生活中存在各种各样的关系, 数学中也学习过很多关系. 引例(P33) A = {张三, 李四, 王五}; B = {英语, 数学实验, 离散数学, 数据结构, 汇编语言}; C = {优, 良, 合格, 不合格}.

A与B之间的关系: R = {(张三, 离散数学), (张三, 数据结构), (张三, 英语), (李四, 数据结构), (王五, 数学实验), (王五, 汇编语言)}. A, B与C之间的关系: R' = {(张三, 离散数学, 优), (张三, 数据结构, 良), (张三, 英语, 优), (李四, 数据结构, 优), (王五, 数学实验, 合格), (王五, 汇编语言, 良)}.

Def 2-1 结合引例? 特别地, 若 , 则称R为A上的n元关系. n = 2: 2元关系. 下面主要讨论2元关系, 可类似推广到n(n > 2)元关系.

2. 2元关系 两个集合A和B(可以相同)间的关系称为2元关系: A到B的关系: A到A, 即A上的关系: 例2-1(P34) A = {a, b}, B = {1, 2, 3},

A到B的空关系与全关系AB. 集合A, B可以无限, 可以有限. Theorem 若|A| = m, |B| = n, 则A到B的关系有2mn. Hint |A  B| = mn. 显然, 若|A| = m, 则A上的关系有2mm.

关系符号 任意集合符号可以作为关系符号；其次, 对于常见的很有用的关系可以给出一个固定的特殊符号. 设R  AB, 若(x, y)  R, 则称元素x与y有关系R, 可记为xRy: 例如, 实数集合R上的大于”>”关系: 例2-3(P35) 整数集Z上的模k同余关系k: 3|(x - y)  x除以3的余数 = y除以3的余数(P12).

A上的恒等关系: 例如, 若A = {a, b, c}, 则IA = {(a, a), (b, b), (c, c)}. 通常一个集合到一个集合的关系非常多,但在一个实际问题中,需要找到一个与问题有关的有助于问题解决的关系,这就要求我们要逐渐学会自己定义关系. 几个例子(PP35-36): 理解[例2-5]?

Remark 由后面函数的关系定义知, dom R和ran R与函数的定义域与值域一致. 3. 关系的定义域与值域 设R  AB, dom R = {x|xA, 存在yB, 使得(x, y)  R}, 即R中所有有序对中第一位置元素组成的集合, 它显然是A的子集. 例2-10 R = {(1, 1), (1, 3), (2, 2), (2, 4), (3,1), (3, 3), (4, 2), (4, 4)}, 则dom R = {1, 2, 3, 4}. 设R  AB, ran R = {y|yB, 存在xA, 使得(x, y)  R}, 即R中所有有序对中第二位置元素组成的集合, 它是B的子集. 在上例中, ran R = {1, 2, 3, 4}. Remark 由后面函数的关系定义知, dom R和ran R与函数的定义域与值域一致.

4. 关系的表示 除关系的集合表示外, 还可以有下列两种表示方法. (1)关系图 情形1 R是A到B(包括A上)的关系 A = {a, b, c, d}, B = {1, 2, 3}, R = {(a, 2), (a, 3), (c, 2), (d, 2)}.

情形2 R是A上的关系 A = {a, b, c, d}, R = {(a, b), (a, c), (c, a), (d, c), (d, d)}. (2)关系矩阵

例2-13(P37) A = {a, b, c, d}, B = {1, 2, 3}, R = {(a, 2), (a, 3), (c, 2), (d, 2)}.

5. 函数的关系(集合)定义 函数是如何转换成关系? 例如, A = {a, b, c}, B = {1, 2, 3}, f: A  B, f(a) = 2, f(b) = 3, f(c) = 3. Remark 一般来说, A到B的关系不是A到B的函数.

A到B的关系f 满足什么条件成为A到B的函数? (1)dom f = A; (2) (Why?) 例2-16(P38): 可按以前的理解讨论.

2.2 关系的运算 讨论关系的运算是为了从已知的关系得出新的关系. 1.关系的集合运算 Remark 例2-17(P40)

2. 关系的逆运算 为何考虑关系的逆运算? 若x是y的老师,则y是x的学生, … 例 A = {a, b, c, d}, B = {1, 2, 3}, R = {(a, 3), (c, 2), (a, 2), (b, 2)}. 逆运算的性质: Theorem(对合律)

Theorem 2-3(逆运算与关系的集合运算并, 交, 补的关系) (1) (2) (3) Proof (2)

3. 关系的复合运算 (1)关系R与关系S的复合R◦S 为何考虑关系的复合运算? 若x是y的母亲, y是z的妻子, 则x是z的岳母, … 例2-19

借助于关系图理解复合运算: 可以利用关系矩阵计算关系的复合.

Remark 关系的复合运算不满足交换律,即一般来说R ◦ S  S ◦ R, 但关系的复合运算满足结合律: Theorem 正因为这样, R ◦ S ◦ T 可以不加括号. Theorem 2-5(P44) (1)(复合运算对并运算可分配) (2) Remark 一般来说

下述定理给出复合运算与逆运算之间的关系. Theorem 2-6(P44) Proof 本性质与矩阵的有关运算性质类似, 请注意顺序.

(2)关系R的方幂运算Rn 若R  A  B, 一般来说, R ◦ R 没有意义. 方幂运算的性质(P44) 例 2-23(P45).

(3)函数f与函数g的复合f◦g 设f: A  B, g: B  C, 按以前的记号,函数f与函数g的复合记为f◦g: 若f (x) = y且g(y) = z, 则(f◦g)(x) = g(f(x)) = z. 由于f  A  B, g  B  C, 关系f与关系g的复合记为f◦g: 若(x, y)  f且(y, z)  g, 则(x, z)  f◦g. 所以,函数f与函数g的复合f◦g与将其看作关系时关系f与关系g的复合是完全一致的(与大多数教材不同! 考虑到运算都是从左到右进行.).

4. 关系的其他运算 在具体应用中, 如在数据库理论中, 还会涉及到关系的其他运算, 如关系的连接运算、关系的投影运算、关系的限制运算、关系的除运算等, 由于篇幅限制和侧重点不同, 再此不作讨论. 但为了后面讨论子格的方便, 用较小的篇幅介绍关系限定运算中的一种特殊情况: 关系在一个子集上的限定. Def 2-8(P45)

有时侯, 例2-24(P45) 关系的3种闭包运算r(R), s(R), t(R). Remark C语言中的关系符号=, >, >=, <, <=, !=, 其构成的关系表达式(将关系符号看作了运算符号)有一个逻辑值.