| 离散数学第二章关系 | 您所在的位置：网站首页 › 全域关系定义 › 离散数学第二章关系 |
|
关系笛卡尔积与关系关系笛卡尔积与关系笛卡尔积 序偶 由两个具有给定次序的个体 a，b 组成的序列，称为序偶或有序对，记作(a，b)，其中 a，b 常称为该序偶的第 1 个和第 2 个分量或坐标．设(a，b)和(c，d)是两个序偶，若 a = c 且 b = d，则称这两个序偶 相等，并记作(a，b) = (c，d)．序偶的概念可以推广到有序 n 元组 , 即有序n元组 . 笛卡尔积 定义 设 A，B 为任意集合，称集合 {(a，b) | a ∈ A，b ∈ B} 为 A 与 B 的笛卡尔积，记作 A × B．设 A1，A2，…，An 为任意集合，称集合 {(a1，a2，…，an) | ai ∈ Ai，i = 1，2，…，n} 为 A1，A2，…，An 的 n 阶笛卡尔积，记作 A1 × A2 × … × An． 性质 （1）不满足交换律，即 A × B ≠ B × A（A ≠ B 且 A、B 都不是空集）．（2）不满足结合律，即(A × B) × C ≠ A × (B × C)（A、B、C 都不是空集）．（3）A × B = 空集 当且仅当 A = 空集 或者 B = 空集 ．（4）A × B ⊆ C × D 当且仅当 A ⊆ C 且 B ⊆ D（A、B、C、D 都不是空集） ．（5）A × B = C × D 当且仅当 A = C 且 B = D（A、B、C、D 都不是空集） ．（6）若 C ≠ 空集 ，则 A ⊆ B 当且仅当 A × C ⊆ B × C 当且仅当 C × A ⊆ C × B． 与笛卡尔积有关的一些恒等式 设 A，B，C 是任意集合，则有 （1）A × (B ∪ C) = (A × B) ∪ (A × C)． （2）(B ∪ C) × A = (B × A) ∪ (C × A)． （3）A × (B ∩ C) = (A × B) ∩ (A × C)． （4）(B ∩ C) × A = (B × A) ∩ (C × A)．（5）A × (B – C) = (A × B) – (A × C)．（6）(B – C) × A = (B × A) – (C × A)． 笛卡尔积的基数 当 A，B 均是有限集时，A × B 必为有限集，且#(A × B) = #A × #B． 关系的基本概念设 A，B 为任意集合，集合 A × B 的任意一个子集称为一个由 A 到B 的二元关系．特别当 A = B 时称为 A 上的二元关系．两个集合的二元关系可以推广到 n 个集合的 n 元关系．、 设 R 是由集合 A 到 B 的关系，若(a，b) ∈ R，则称 a 与 b 有关系 R，又记作 a R b a 与 b 没有关系 R，不能说明 a 与 b 就没有关系，可能还有其它关系 .数学上抽象定义的关系，有的在直观上已无法再用自然语言来描述了 对任意的集合 A 与 B 称空集为空关系；称 A × B 为由 A 到B 的全关系或普遍关系；称 A × A 为 A 上的全关系或普遍关系；称集合{(a，a) | a ∈ A}为 A 上的恒等关系，记为 IA． 设 R 是由集合 A 到 B 的一个关系， （1）R 中所有序偶的第一个分量构成的集合称为 R 的定义域，记作 domR（2）R 中所有序偶的第二个分量构成的集合称为 R 的值域，记作 ranR关系的表示方法集合表示法 矩阵表示法 关系矩阵是一个 0-1 矩阵，称为布尔矩阵． 关系图表示法 关系图由结点和边组成： （1）用小圆圈代表元素，在图中称为结点．（2）用从结点 a 指向结点 b 的有向单边表示序偶(a，b)；用绕结点 a 且指向 自身的带箭头的小圆圈表示序偶(a，a)，其中方向任意．（自环）如果 A = B，则只需画出 A 中的所有元素即可关系的运算关系的并、交、差、补运算关系的逆运算定义：设 A，B 是两个集合，R 是由 A 到 B 的关系，则由 B 到 A 的关系 {(b，a) | (a，b) ∈ R} 称为关系 R 的逆关系 ，记为 R–1．这种由关系 R 得到逆关系 R–1 的运算称为关系的逆运算． 性质 （1）(R1 ∪ R2)–1 = (R1)–1 ∪ (R2)–1． （2）(R1 ∩ R2)–1 = (R1)–1 ∩ (R2)–1．（3）(R1 – R2)–1 = (R1)–1 – (R2)–1． （4）((R1)‘)–1 = ((R1)–1)’．（5）((R1)–1)–1 = R1． （6）若 R1 ⊆ R2，则(R1)–1 ⊆ (R2)–1． （7）若 R1 = R2，则(R1)–1 = (R2)–1．关系的复合运算 定义 设 A，B，C 是三个集合，R1 是由 A 到 B 的关系，R2 是由 B 到 C的关系，则 R1 和 R2 的复合关系，记为 R1 ◦ R2，是一个由 A 到 C 的关系，且 R1 ◦ R2 = {(a，c) | a ∈ A，c ∈ C，且存在 b ∈ B，使得 a R1 b，b R2 c}，这种由关系 R1 和 R2 求复合关系 R1 ◦ R2 的运算称为关系的复合运算． 如果 R1 的值域和 R2 的定义域的交集为空，复合关系 R1 ◦ R2 是空关系．R1 ◦ 空集 = 空集 ◦ R2 = 空集 性质 设 R 是由集合 A 到 B 的关系，则 IA ◦ R = R ◦ IB = R． 设 R1，R2 是集合 A 上的任意关系，则(R1 ◦ R2)–1 = (R2)–1 ◦ (R1)–1． 设 R1，R2，…，Rn 是集合 A 上的关系，则 (R1 ◦ R2 ◦ … ◦ Rn)–1 = (Rn)–1 ◦ … ◦ (R2)–1 ◦ (R1)–1，n 为正整数． 设 R 是集合 A 上的关系，则(Rn)–1 = (R–1)n，n 为正整数． 设 R1 是由集合 A 到 B 的关系，R2 是由集合 B 到 C 的关系，R3 是由集合 C 到 D 的关系，则有(R1 ◦ R2) ◦ R3 = R1 ◦ (R2 ◦ R3)． 设 R 是集合 A 上的二元关系，则 R 的 n 次幂定义如下： R0 = IA；Rn+1 = Rn ◦ R（n ∈ N） Rm ◦ Rn = Rm+n． (Rm)n = Rmn． 设 R1 是由集合 A 到 B 的关系，R2 和 R3 都是由集合 B 到 C 的关系，R4 是由集合 C 到 D 的关系，则 （1）R1 ◦ (R2 ∪ R3) = (R1 ◦ R2) ∪ (R1 ◦ R3)． （2）(R2 ∪ R3) ◦ R4 = (R2 ◦ R4) ∪ (R3 ◦ R4)． （3）R1 ◦ (R2 ∩ R3) ⊆ (R1 ◦ R2) ∩ (R1 ◦ R3)． （4）(R2 ∩ R3) ◦ R4 ⊆ (R2 ◦ R4) ∩ (R3 ◦ R4)． 求复合关系的方法 定义 关系矩阵的运算 布尔加法：关系矩阵的布尔加法的运算法则与一般矩阵的加法是相同的，只是其中数的加法运算为布尔加．布尔乘法：关系矩阵的布尔乘法的运算法则与一般矩阵的乘法是相同的，只是其中数的的加法运算和乘法运算改为布尔加和布尔乘． 复合关系的关系矩阵 设 A = {a1，a2，…，al}，B = {b1，b2，…，bm}，C = {c1，c2，…，cn}均是有限集，R1 是一由 A 到 B 的关系，R2是一由 B 到 C 的关系，它们的关系矩阵分别为 1和 2，则复合关系 R1 ◦ R2 的关系矩阵 1∘ 2 = 1 ∘ 2． 可以推广至n个关系矩阵 关系图 关系的性质关系性质的定义 设 R 是集合 A 上的关系 （1）若对于所有的 x ∈ A，均有 x R x，则称 R 在 A 上是自反的．否则 R 是非自反的． 若对于所有的 x ∈ A，均有 x R‘ x，则称 R 在 A 上是反自反的． （2）对于所有的 x，y ∈ A，若每当有 x R y 就必有 y R x，则称 R 在 A 上是对称的．否则 R 是非对称的． 对于所有的 x，y ∈ A，若每当有 x R y 和 y R x 就必有 x = y，则称 R 在 A 上是反对称的． （3）对于所有的 x，y，z ∈ A，若每当有 x R y 和 y R z 就必有 x R z，则称 R在 A 上是可传递的．否则 R 是不可传递的． 注意 定义中使用了条件语句，当条件不满足时该语句按为真处理．集合 A 上的恒等关系是自反关系，但自反关系却不一定是恒等关系（如 R2）．反自反关系是非自反关系的一个特例．不是自反的关系不一定就是反自反的关系，不是反自反的关系也不一定就是自反的关系．若 R 是集合 A 上的反对称关系，则由定义知，在 R 中， (a，b)与(b， a)至多有一个出现，其中 a ≠ b．不是对称的关系不一定就是反对称关系，不是反对称的关系也不一定就是对称关系．集合 A 上的恒等关系是可传递关系． 关系性质的判别 集合运算的方法 （1）R 在 A 上自反当且仅当 IA ⊆ R． （2）R 在 A 上反自反当且仅当 R ∩ IA = 空集 ． （3）R 在 A 上对称当且仅当 R = R–1．（4）R 在 A 上反对称当且仅当 R ∩ R–1 ⊆ IA． （5）R 在 A 上可传递当且仅当 R ◦ R ⊆ R． 关系矩阵的方法 （1）若 R 是自反的，则关系矩阵的主对角线上的所有元素均为 1．（2）若 R 是反自反的，则关系矩阵的主对角线上所有元素均为 0．（3）若 R 是对称的，则关系矩阵为对称矩阵．（4）若 R 是反对称的，则在关系矩阵中，关于主对角线对称的元素不同时 为 1，即 i ≠ j 时，rij 与 rji这两个数中至多一个是 1，但允许两个均为 0． （5）若 R 是可传递的，M 为 R 的关系矩阵，则在 M^2 中 1 所在的位置，M 中相应的位置上都是 1 ． 关系图的方法 （1）若 R 是自反的，则关系图中每一结点均有自环．（2）若 R 是反自反的，则关系图中每一结点均无自环．（3）若 R 是对称的，则在关系图中，若两结点之间存在有边，则必存在两条方向相反的边．（4）若 R 是反对称的，则在关系图中，任意两个不同的结点间至多有一条边．（5）若 R 是可传递的，则在关系图中，若每当有边由 ai指向 ak，且又有边由 ak指向 aj，则必有一条边由 ai指向 aj．关系的闭包定义对集合 A 上给定的关系 R 和一种性质 P，包含 R 且满足性质 P的最小关系称为 R 对于 P 的闭包，记作 P(R)．构造闭包的运算称为闭包运算． 设 R 是集合 A 上的关系，则 A 上的关系 （1）r(R) = R ∪ IA为 R 的自反闭包． （2）s(R) = R ∪ R–1 为 R 的对称闭包． （3） ( ) = R ∪ R^2 ... 为 R 的传递闭包． 设 A 为非空有限集合，#A = n，R 是集合 A 上的关系，则存在正 整数 k n，使得 t(R) = R ∪ R^2 ... R^k性质 设 R 是非空集合 A 上的关系，则 （1）R 是自反的当且仅当 r(R) = R．（2）R 是对称的当且仅当 s(R) = R．（3）R 是可传递的当且仅当 t(R) = R． 设 R1 和 R2是非空集合 A 上的关系，且 R1 ⊆ R2，则 （1）r(R1) ⊆ r(R2)（2）s(R1) ⊆ s(R2)（3）t(R1) ⊆ t(R2)． 设 R1 和 R2是非空集合 A 上的关系，则 （1）r(R1 ∪ R2) = r(R1) ∪ r(R2)．（2）s(R1 ∪ R2) = s(R1) ∪ s(R2)．（3）t(R1 ∪ R2) ⊇ t(R1) ∪ t(R2)． 设 R 是非空集合 A 上的关系 （1）若 R 是自反的，则 r(R)，s(R)和 t(R)是自反的．（2）若 R 是对称的，则 r(R)，s(R)和 t(R)是对称的．（3）若 R 是可传递的，则 r(R)和 t(R)是可传递的． 设 R 是非空集合 A 上的关系，则 （1）rs(R) = sr(R)．（2）rt(R) = tr(R)． （3）st(R) ⊆ ts(R)． 关系闭包的求法 利用关系矩阵求关系闭包 利用关系图求关系闭包 （1）考察 G 的每个结点：如果没有自环就加上一个自环．最终得到的是 Gr． （2）考察 G 的每一条边：如果有一条由 ai指向 aj的单向边，i ≠ j，则在 G中添加一条由 aj指向 ai的反方向边．最终得到 Gs．（3）考察 G 的每个结点 ai：找出从 ai 出发的所有 2 步、3 步、…、n 步长的路径（n = #A），设这些路径的所有终点为 1， 2，⋯， ．如果没有从 ai到 （l = 1，2，…，k）的边，就加上这条边．当检查完所有的结点后就得到图 Gt． 利用 Warshall 算法求关系的传递闭包 设 n 个元素的有限集合上关系 R 的关系矩阵为 M，用 A[i，j]表示矩阵 A 的（i，j）项元素． 步骤 （1）置新矩阵 A = M． （2）j = 1． （3）对所有的 i，如果 A[i，j] = 1，则对 k = 1，2，…，n，作布尔加 A[i，k] = A[i，k] 布尔加 A[j，k]，即将第 j 行加到第 i 行上去． （4）j 加 1． （5）如果 j ≤ n，则转到步骤（3），否则停止． 等价关系基本概念集合 A 上的关系 R，如果它是自反的、对称的、可传递的，则称R 是 A 上的等价关系．设 R 是集合 A 上的等价关系，若 a R b 成立，则称 a 等价于 b ． a 与 b 是等价的（在 R 下），记作 a ~ b． 设 R 是集合 A 上的等价关系，a ∈ A，则 A 中等价于元素 a 的所有元素组成的集合称为 a 生成的等价类，记为[a]R，即 [a]R = {b | b ∈ A 且 a R b}，a 称为[a]R的代表元或生成元．性质（1）对任意的 a ∈ A，[a]R ≠ 空集．（2）对任意的 a，b ∈ A，若 a R b，则[a]R = [b]R． （3）对任意的 a，b ∈ A，若 a R ‘ b，则[a]R ∩ [b]R = 空集 ． 等价关系与分划设 R 是集合 A 上的一个等价关系，则集合 A 中所有元素产生的 等价类的集合{[a]R | a ∈ A}是 A 的一个分划． 由等价关系 R 的等价类所形成的 A 的分划（唯一的）称为 A 上由 R 导出的等价分划 .对任意的集合 A，恒等关系 IA导出的等价关系是 A 的“最细”的分划，普遍关系 UA导出的等价关系是 A 的“最粗”的分划，合称 A 的平凡分划． 商集 设 R 为非空集合 A 上的等价关系，以 R 的所有等价类作为元素 的集合称为 A 关于 R 的商集，记做 A/R .A/R 的基数（A 在 R 下的不同等价类的个数）称为 R 的秩设 R1，R2是非空集合 A 上的等价关系，则 R1 = R2 的充分必要条件是 A/R1 = A/R2． {A1，A2，…，AR}是集合 A 的一个分划，则存在 A 上的一 个等价关系 R，使得其是 A 上由 R 导出的等价分划． 其他性质设 R1，R2 是非空集合 A 上的等价关系，则 R1 ∩ R2 也是集合 A 上的等价关系． 设 R 是非空集合 A 上的等价关系，则对任意的正整数 n 有 （1）Rn = R． （2）(R–1)n = R． 相容关系基本概念定义：集合 A 上的关系 R，如果它是自反的、对称的，则称 R 是 A 上的相容关系． 最大相容类 设 R 是有限集 A 上的相容关系，C ⊆ A，C ≠ 空集，如果 （1）对任意a，b ∈ C，均有 a R b（称 C 为相容关系 R 的一个相容类）（2）不存在任何相容类 D，使 C ⊂ D则称 C 是相容关系 R 的最大相容类，记为 CR． 如果 CR 是最大相容类 （1）它是 A 的一个非空子集； （2）对任意的 x ∈ CR，x 必与 CR中的所有元素有相容关系；（3）在 A – CR 中没有元素与 CR 中所有元素有相容关系． 最大相容类的关系简图求法 不画自环，用单线（无向）替代来回线，并称其为相容关系的关系简图．在相容关系的关系简图中，定义每个结点都与其他结点有边相连接的多边形为完全多边形．关系简图中每一最大完全多边形的结点集合就是一个最大相容类．孤立结点以及不是完全多边形的边的两个结点的连线也是最大相容类 .相容关系与覆盖设 R 是有限集合 A 上的一个相容关系，#A = n，则对任意的 a ∈ A，必存在一个最大相容类 C，使得 a ∈ C． 设 R 是有限集合 A 上的一个相容关系，则 R 的所有最大相容类的集合是 A 的一个覆盖 . 若 H = {A1，A2，…，Am}是集合 A 的覆盖，且 H 中任意元素不是其它元素的子集，则称 H 是 A 的一个完全覆盖。集合 A 上相容关系 R 的最大相容类所构成的 A 的覆盖为 A 的完全覆盖，记作 CR(A)． 设 S = {A1，A2，…，Am}是 A 的一个覆盖，根据 S 定义的关系 R = (A1 × A1) ∪ (A2 × A2) ∪ … ∪ (Am × Am) 是 A 上的相容关系． 对于集合，给定一个相容关系必可对应一个覆盖，给定一个覆盖也可确定一个相容关系，但二者之间不存在一对一的关系．即任一覆盖可以确定一个对应于此覆盖的相容关系，但可以不同的覆盖构造相同的相容关系．偏序关系基本概念集合 A 上的关系 R，如果它是自反的、反对称的、可传递的，则称 R 是 A 上的偏序关系，简称偏序．集合 A 与 A 上的偏序关系 R 一起构成的有序对称为偏序集或偏序结构，记为．偏序关系的关系矩阵是主对角线上的元素全为 1 的矩阵，且当 i ≠ j时，rijrji = 0．次序图（1）去掉所有结点的自环． （2）用无向单边表示两元素之间有关系，若 a ≼ b，则结点 a 位于结点 b 的下方（一律由下向上，下小上大，因而不应出现水平画置的边）．（3）删去传递性的第三边． 偏序集的特殊元素 设为偏序集，B 为 A 的非空子集，b ∈ B， （1）如果 B 中没有任何元素 x 满足 x ≠ b 及 b ≼ x，则称 b 为 B 的极大元．（2）如果 B 中没有任何元素 x 满足 x ≠ b 及 x ≼ b，则称 b 为 B 的极小元．（3）如果对任意的 x ∈ B 都有 x ≼ b，则称 b 为 B 的最大元． （4）如果对任意的 x ∈ B 都有 b ≼ x，则称 b 为 B 的最小元． 注意 B 的极大元，极小元，最大元，最小元如果存在，一定在 B 中． 极大元与最大元，极小元与最小元是不一样的． b 是 B 的极大元当且仅当 B 中没有比 b 大的元素． b 是 B 的最大元当且仅当 B 中所有其他元素都比 b 小． 设为偏序集，B 为 A 的非空子集， （1）若 b 为 B 的最大元（最小元），则 b 为 B 的极大元（极小元）．（2）若 b 为 B 的最大元（最小元），则 B 的最大元（最小元）唯一．（3）若 B 为有限集，则 B 的极大元、极小元恒存在． 设为偏序集，B 为 A 的非空子集， （1）如果 a ∈ A 且对任意的 x ∈ B 都有 x ≼ a，则称 a 为 B 的上界．（2）如果 a ∈ A 且对任意的 x ∈ B 都有 a ≼ x，则称 a 为 B 的下界．（3）如果 a 是 B 的所有上界集合的最小元，则称 a 为 B 的最小上界或上确界．（4）如果 a 是 B 的所有下界集合的最大元，则称 a 为 B 的最大下界或下确界．上、下界未必存在，存在时未必唯一．即使在有上界、下界时，最小上界和最大下界也未必存在． 注意 偏序集的有限子集一定存在极大元和极小元，不一定存在最大元和最小元．极大元和极小元可能存在多个，而最大元和最小元若存在必定是唯一 的．最大元一定是极大元，最小元一定是极小元，反之不一定． 孤立元素本身既是极大元，也是极小元． 最大元一定是最小上界，最小元一定是最大下界，反之不一定． 全序和良序设≼是集合 A 上的一个偏序关系，a，b ∈ A，若有 a ≼ b 或 b ≼a，则称元素 a 和 b 是可比的或可排序的，否则是不可比的或不可排序的．若对任意的 a，b ∈ A，a 与 b 都是可比的，则称≼为 A 上的一个全序． 设≼是集合 A 上的一个偏序，若对于 A 的每一个非空子集 S 都有最小元，则称它为 A 上的一个良序．一个偏序若是良序，则一定是全序． 有限集上的全序一定是良序． XMind - Trial Version 笛卡尔积 序偶 由两个具有给定次序的个体 a，b 组成的序列，称为序偶或有序对，记作(a，b)，其中 a，b 常称为该序偶的第 1 个和第 2 个分量或坐标．设(a，b)和(c，d)是两个序偶，若 a = c 且 b = d，则称这两个序偶 相等，并记作(a，b) = (c，d)．序偶的概念可以推广到有序 n 元组 , 即有序n元组 . 笛卡尔积 定义 设 A，B 为任意集合，称集合 {(a，b) | a ∈ A，b ∈ B} 为 A 与 B 的笛卡尔积，记作 A × B．设 A1，A2，…，An 为任意集合，称集合 {(a1，a2，…，an) | ai ∈ Ai，i = 1，2，…，n} 为 A1，A2，…，An 的 n 阶笛卡尔积，记作 A1 × A2 × … × An． 性质 （1）不满足交换律，即 A × B ≠ B × A（A ≠ B 且 A、B 都不是空集）．（2）不满足结合律，即(A × B) × C ≠ A × (B × C)（A、B、C 都不是空集）．（3）A × B = 空集 当且仅当 A = 空集 或者 B = 空集 ．（4）A × B ⊆ C × D 当且仅当 A ⊆ C 且 B ⊆ D（A、B、C、D 都不是空集） ．（5）A × B = C × D 当且仅当 A = C 且 B = D（A、B、C、D 都不是空集） ．（6）若 C ≠ 空集 ，则 A ⊆ B 当且仅当 A × C ⊆ B × C 当且仅当 C × A ⊆ C × B． 与笛卡尔积有关的一些恒等式 设 A，B，C 是任意集合，则有 （1）A × (B ∪ C) = (A × B) ∪ (A × C)． （2）(B ∪ C) × A = (B × A) ∪ (C × A)． （3）A × (B ∩ C) = (A × B) ∩ (A × C)． （4）(B ∩ C) × A = (B × A) ∩ (C × A)．（5）A × (B – C) = (A × B) – (A × C)．（6）(B – C) × A = (B × A) – (C × A)． 笛卡尔积的基数 当 A，B 均是有限集时，A × B 必为有限集，且#(A × B) = #A × #B． 关系的基本概念设 A，B 为任意集合，集合 A × B 的任意一个子集称为一个由 A 到B 的二元关系．特别当 A = B 时称为 A 上的二元关系．两个集合的二元关系可以推广到 n 个集合的 n 元关系．、 设 R 是由集合 A 到 B 的关系，若(a，b) ∈ R，则称 a 与 b 有关系 R，又记作 a R b a 与 b 没有关系 R，不能说明 a 与 b 就没有关系，可能还有其它关系 .数学上抽象定义的关系，有的在直观上已无法再用自然语言来描述了 对任意的集合 A 与 B 称空集为空关系；称 A × B 为由 A 到B 的全关系或普遍关系；称 A × A 为 A 上的全关系或普遍关系；称集合{(a，a) | a ∈ A}为 A 上的恒等关系，记为 IA． 设 R 是由集合 A 到 B 的一个关系， （1）R 中所有序偶的第一个分量构成的集合称为 R 的定义域，记作 domR（2）R 中所有序偶的第二个分量构成的集合称为 R 的值域，记作 ranR关系的表示方法集合表示法 矩阵表示法 关系矩阵是一个 0-1 矩阵，称为布尔矩阵． 关系图表示法 关系图由结点和边组成： （1）用小圆圈代表元素，在图中称为结点．（2）用从结点 a 指向结点 b 的有向单边表示序偶(a，b)；用绕结点 a 且指向 自身的带箭头的小圆圈表示序偶(a，a)，其中方向任意．（自环）如果 A = B，则只需画出 A 中的所有元素即可关系的运算关系的并、交、差、补运算关系的逆运算定义：设 A，B 是两个集合，R 是由 A 到 B 的关系，则由 B 到 A 的关系 {(b，a) | (a，b) ∈ R} 称为关系 R 的逆关系 ，记为 R–1．这种由关系 R 得到逆关系 R–1 的运算称为关系的逆运算． 性质 （1）(R1 ∪ R2)–1 = (R1)–1 ∪ (R2)–1． （2）(R1 ∩ R2)–1 = (R1)–1 ∩ (R2)–1．（3）(R1 – R2)–1 = (R1)–1 – (R2)–1． （4）((R1)‘)–1 = ((R1)–1)’．（5）((R1)–1)–1 = R1． （6）若 R1 ⊆ R2，则(R1)–1 ⊆ (R2)–1． （7）若 R1 = R2，则(R1)–1 = (R2)–1．关系的复合运算 定义 设 A，B，C 是三个集合，R1 是由 A 到 B 的关系，R2 是由 B 到 C的关系，则 R1 和 R2 的复合关系，记为 R1 ◦ R2，是一个由 A 到 C 的关系，且 R1 ◦ R2 = {(a，c) | a ∈ A，c ∈ C，且存在 b ∈ B，使得 a R1 b，b R2 c}，这种由关系 R1 和 R2 求复合关系 R1 ◦ R2 的运算称为关系的复合运算． 如果 R1 的值域和 R2 的定义域的交集为空，复合关系 R1 ◦ R2 是空关系．R1 ◦ 空集 = 空集 ◦ R2 = 空集 性质 设 R 是由集合 A 到 B 的关系，则 IA ◦ R = R ◦ IB = R． 设 R1，R2 是集合 A 上的任意关系，则(R1 ◦ R2)–1 = (R2)–1 ◦ (R1)–1． 设 R1，R2，…，Rn 是集合 A 上的关系，则 (R1 ◦ R2 ◦ … ◦ Rn)–1 = (Rn)–1 ◦ … ◦ (R2)–1 ◦ (R1)–1，n 为正整数． 设 R 是集合 A 上的关系，则(Rn)–1 = (R–1)n，n 为正整数． 设 R1 是由集合 A 到 B 的关系，R2 是由集合 B 到 C 的关系，R3 是由集合 C 到 D 的关系，则有(R1 ◦ R2) ◦ R3 = R1 ◦ (R2 ◦ R3)． 设 R 是集合 A 上的二元关系，则 R 的 n 次幂定义如下： R0 = IA；Rn+1 = Rn ◦ R（n ∈ N） Rm ◦ Rn = Rm+n． (Rm)n = Rmn． 设 R1 是由集合 A 到 B 的关系，R2 和 R3 都是由集合 B 到 C 的关系，R4 是由集合 C 到 D 的关系，则 （1）R1 ◦ (R2 ∪ R3) = (R1 ◦ R2) ∪ (R1 ◦ R3)． （2）(R2 ∪ R3) ◦ R4 = (R2 ◦ R4) ∪ (R3 ◦ R4)． （3）R1 ◦ (R2 ∩ R3) ⊆ (R1 ◦ R2) ∩ (R1 ◦ R3)． （4）(R2 ∩ R3) ◦ R4 ⊆ (R2 ◦ R4) ∩ (R3 ◦ R4)． 求复合关系的方法 定义 关系矩阵的运算 布尔加法：关系矩阵的布尔加法的运算法则与一般矩阵的加法是相同的，只是其中数的加法运算为布尔加．布尔乘法：关系矩阵的布尔乘法的运算法则与一般矩阵的乘法是相同的，只是其中数的的加法运算和乘法运算改为布尔加和布尔乘． 复合关系的关系矩阵 设 A = {a1，a2，…，al}，B = {b1，b2，…，bm}，C = {c1，c2，…，cn}均是有限集，R1 是一由 A 到 B 的关系，R2是一由 B 到 C 的关系，它们的关系矩阵分别为 1和 2，则复合关系 R1 ◦ R2 的关系矩阵 1∘ 2 = 1 ∘ 2． 可以推广至n个关系矩阵 关系图 关系的性质关系性质的定义 设 R 是集合 A 上的关系 （1）若对于所有的 x ∈ A，均有 x R x，则称 R 在 A 上是自反的．否则 R 是非自反的． 若对于所有的 x ∈ A，均有 x R‘ x，则称 R 在 A 上是反自反的． （2）对于所有的 x，y ∈ A，若每当有 x R y 就必有 y R x，则称 R 在 A 上是对称的．否则 R 是非对称的． 对于所有的 x，y ∈ A，若每当有 x R y 和 y R x 就必有 x = y，则称 R 在 A 上是反对称的． （3）对于所有的 x，y，z ∈ A，若每当有 x R y 和 y R z 就必有 x R z，则称 R在 A 上是可传递的．否则 R 是不可传递的． 注意 定义中使用了条件语句，当条件不满足时该语句按为真处理．集合 A 上的恒等关系是自反关系，但自反关系却不一定是恒等关系（如 R2）．反自反关系是非自反关系的一个特例．不是自反的关系不一定就是反自反的关系，不是反自反的关系也不一定就是自反的关系．若 R 是集合 A 上的反对称关系，则由定义知，在 R 中， (a，b)与(b， a)至多有一个出现，其中 a ≠ b．不是对称的关系不一定就是反对称关系，不是反对称的关系也不一定就是对称关系．集合 A 上的恒等关系是可传递关系． 关系性质的判别 集合运算的方法 （1）R 在 A 上自反当且仅当 IA ⊆ R． （2）R 在 A 上反自反当且仅当 R ∩ IA = 空集 ． （3）R 在 A 上对称当且仅当 R = R–1．（4）R 在 A 上反对称当且仅当 R ∩ R–1 ⊆ IA． （5）R 在 A 上可传递当且仅当 R ◦ R ⊆ R． 关系矩阵的方法 （1）若 R 是自反的，则关系矩阵的主对角线上的所有元素均为 1．（2）若 R 是反自反的，则关系矩阵的主对角线上所有元素均为 0．（3）若 R 是对称的，则关系矩阵为对称矩阵．（4）若 R 是反对称的，则在关系矩阵中，关于主对角线对称的元素不同时 为 1，即 i ≠ j 时，rij 与 rji这两个数中至多一个是 1，但允许两个均为 0． （5）若 R 是可传递的，M 为 R 的关系矩阵，则在 M^2 中 1 所在的位置，M 中相应的位置上都是 1 ． 关系图的方法 （1）若 R 是自反的，则关系图中每一结点均有自环．（2）若 R 是反自反的，则关系图中每一结点均无自环．（3）若 R 是对称的，则在关系图中，若两结点之间存在有边，则必存在两条方向相反的边．（4）若 R 是反对称的，则在关系图中，任意两个不同的结点间至多有一条边．（5）若 R 是可传递的，则在关系图中，若每当有边由 ai指向 ak，且又有边由 ak指向 aj，则必有一条边由 ai指向 aj．关系的闭包定义对集合 A 上给定的关系 R 和一种性质 P，包含 R 且满足性质 P的最小关系称为 R 对于 P 的闭包，记作 P(R)．构造闭包的运算称为闭包运算． 设 R 是集合 A 上的关系，则 A 上的关系 （1）r(R) = R ∪ IA为 R 的自反闭包． （2）s(R) = R ∪ R–1 为 R 的对称闭包． （3） ( ) = R ∪ R^2 ... 为 R 的传递闭包． 设 A 为非空有限集合，#A = n，R 是集合 A 上的关系，则存在正 整数 k n，使得 t(R) = R ∪ R^2 ... R^k性质 设 R 是非空集合 A 上的关系，则 （1）R 是自反的当且仅当 r(R) = R．（2）R 是对称的当且仅当 s(R) = R．（3）R 是可传递的当且仅当 t(R) = R． 设 R1 和 R2是非空集合 A 上的关系，且 R1 ⊆ R2，则 （1）r(R1) ⊆ r(R2)（2）s(R1) ⊆ s(R2)（3）t(R1) ⊆ t(R2)． 设 R1 和 R2是非空集合 A 上的关系，则 （1）r(R1 ∪ R2) = r(R1) ∪ r(R2)．（2）s(R1 ∪ R2) = s(R1) ∪ s(R2)．（3）t(R1 ∪ R2) ⊇ t(R1) ∪ t(R2)． 设 R 是非空集合 A 上的关系 （1）若 R 是自反的，则 r(R)，s(R)和 t(R)是自反的．（2）若 R 是对称的，则 r(R)，s(R)和 t(R)是对称的．（3）若 R 是可传递的，则 r(R)和 t(R)是可传递的． 设 R 是非空集合 A 上的关系，则 （1）rs(R) = sr(R)．（2）rt(R) = tr(R)． （3）st(R) ⊆ ts(R)． 关系闭包的求法 利用关系矩阵求关系闭包 利用关系图求关系闭包 （1）考察 G 的每个结点：如果没有自环就加上一个自环．最终得到的是 Gr． （2）考察 G 的每一条边：如果有一条由 ai指向 aj的单向边，i ≠ j，则在 G中添加一条由 aj指向 ai的反方向边．最终得到 Gs．（3）考察 G 的每个结点 ai：找出从 ai 出发的所有 2 步、3 步、…、n 步长的路径（n = #A），设这些路径的所有终点为 1， 2，⋯， ．如果没有从 ai到 （l = 1，2，…，k）的边，就加上这条边．当检查完所有的结点后就得到图 Gt． 利用 Warshall 算法求关系的传递闭包 设 n 个元素的有限集合上关系 R 的关系矩阵为 M，用 A[i，j]表示矩阵 A 的（i，j）项元素． 步骤 （1）置新矩阵 A = M． （2）j = 1． （3）对所有的 i，如果 A[i，j] = 1，则对 k = 1，2，…，n，作布尔加 A[i，k] = A[i，k] 布尔加 A[j，k]，即将第 j 行加到第 i 行上去． （4）j 加 1． （5）如果 j ≤ n，则转到步骤（3），否则停止． 等价关系基本概念集合 A 上的关系 R，如果它是自反的、对称的、可传递的，则称R 是 A 上的等价关系．设 R 是集合 A 上的等价关系，若 a R b 成立，则称 a 等价于 b ． a 与 b 是等价的（在 R 下），记作 a ~ b． 设 R 是集合 A 上的等价关系，a ∈ A，则 A 中等价于元素 a 的所有元素组成的集合称为 a 生成的等价类，记为[a]R，即 [a]R = {b | b ∈ A 且 a R b}，a 称为[a]R的代表元或生成元．性质（1）对任意的 a ∈ A，[a]R ≠ 空集．（2）对任意的 a，b ∈ A，若 a R b，则[a]R = [b]R． （3）对任意的 a，b ∈ A，若 a R ‘ b，则[a]R ∩ [b]R = 空集 ． 等价关系与分划设 R 是集合 A 上的一个等价关系，则集合 A 中所有元素产生的 等价类的集合{[a]R | a ∈ A}是 A 的一个分划． 由等价关系 R 的等价类所形成的 A 的分划（唯一的）称为 A 上由 R 导出的等价分划 .对任意的集合 A，恒等关系 IA导出的等价关系是 A 的“最细”的分划，普遍关系 UA导出的等价关系是 A 的“最粗”的分划，合称 A 的平凡分划． 商集 设 R 为非空集合 A 上的等价关系，以 R 的所有等价类作为元素 的集合称为 A 关于 R 的商集，记做 A/R .A/R 的基数（A 在 R 下的不同等价类的个数）称为 R 的秩设 R1，R2是非空集合 A 上的等价关系，则 R1 = R2 的充分必要条件是 A/R1 = A/R2． {A1，A2，…，AR}是集合 A 的一个分划，则存在 A 上的一 个等价关系 R，使得其是 A 上由 R 导出的等价分划． 其他性质设 R1，R2 是非空集合 A 上的等价关系，则 R1 ∩ R2 也是集合 A 上的等价关系． 设 R 是非空集合 A 上的等价关系，则对任意的正整数 n 有 （1）Rn = R． （2）(R–1)n = R． 相容关系基本概念定义：集合 A 上的关系 R，如果它是自反的、对称的，则称 R 是 A 上的相容关系． 最大相容类 设 R 是有限集 A 上的相容关系，C ⊆ A，C ≠ 空集，如果 （1）对任意a，b ∈ C，均有 a R b（称 C 为相容关系 R 的一个相容类）（2）不存在任何相容类 D，使 C ⊂ D则称 C 是相容关系 R 的最大相容类，记为 CR． 如果 CR 是最大相容类 （1）它是 A 的一个非空子集； （2）对任意的 x ∈ CR，x 必与 CR中的所有元素有相容关系；（3）在 A – CR 中没有元素与 CR 中所有元素有相容关系． 最大相容类的关系简图求法 不画自环，用单线（无向）替代来回线，并称其为相容关系的关系简图．在相容关系的关系简图中，定义每个结点都与其他结点有边相连接的多边形为完全多边形．关系简图中每一最大完全多边形的结点集合就是一个最大相容类．孤立结点以及不是完全多边形的边的两个结点的连线也是最大相容类 .相容关系与覆盖设 R 是有限集合 A 上的一个相容关系，#A = n，则对任意的 a ∈ A，必存在一个最大相容类 C，使得 a ∈ C． 设 R 是有限集合 A 上的一个相容关系，则 R 的所有最大相容类的集合是 A 的一个覆盖 . 若 H = {A1，A2，…，Am}是集合 A 的覆盖，且 H 中任意元素不是其它元素的子集，则称 H 是 A 的一个完全覆盖。集合 A 上相容关系 R 的最大相容类所构成的 A 的覆盖为 A 的完全覆盖，记作 CR(A)． 设 S = {A1，A2，…，Am}是 A 的一个覆盖，根据 S 定义的关系 R = (A1 × A1) ∪ (A2 × A2) ∪ … ∪ (Am × Am) 是 A 上的相容关系． 对于集合，给定一个相容关系必可对应一个覆盖，给定一个覆盖也可确定一个相容关系，但二者之间不存在一对一的关系．即任一覆盖可以确定一个对应于此覆盖的相容关系，但可以不同的覆盖构造相同的相容关系．偏序关系基本概念集合 A 上的关系 R，如果它是自反的、反对称的、可传递的，则称 R 是 A 上的偏序关系，简称偏序．集合 A 与 A 上的偏序关系 R 一起构成的有序对称为偏序集或偏序结构，记为．偏序关系的关系矩阵是主对角线上的元素全为 1 的矩阵，且当 i ≠ j时，rijrji = 0．次序图（1）去掉所有结点的自环． （2）用无向单边表示两元素之间有关系，若 a ≼ b，则结点 a 位于结点 b 的下方（一律由下向上，下小上大，因而不应出现水平画置的边）．（3）删去传递性的第三边． 偏序集的特殊元素设为偏序集，B 为 A 的非空子集，b ∈ B， 注意 B 的极大元，极小元，最大元，最小元如果存在，一定在 B 中． 极大元与最大元，极小元与最小元是不一样的． b 是 B 的极大元当且仅当 B 中没有比 b 大的元素． b 是 B 的最大元当且仅当 B 中所有其他元素都比 b 小． （1）如果 B 中没有任何元素 x 满足 x ≠ b 及 b ≼ x，则称 b 为 B 的极大元．（2）如果 B 中没有任何元素 x 满足 x ≠ b 及 x ≼ b，则称 b 为 B 的极小元．（3）如果对任意的 x ∈ B 都有 x ≼ b，则称 b 为 B 的最大元． （4）如果对任意的 x ∈ B 都有 b ≼ x，则称 b 为 B 的最小元． 设为偏序集，B 为 A 的非空子集， （1）若 b 为 B 的最大元（最小元），则 b 为 B 的极大元（极小元）．（2）若 b 为 B 的最大元（最小元），则 B 的最大元（最小元）唯一．（3）若 B 为有限集，则 B 的极大元、极小元恒存在． 设为偏序集，B 为 A 的非空子集， （1）如果 a ∈ A 且对任意的 x ∈ B 都有 x ≼ a，则称 a 为 B 的上界．（2）如果 a ∈ A 且对任意的 x ∈ B 都有 a ≼ x，则称 a 为 B 的下界．（3）如果 a 是 B 的所有上界集合的最小元，则称 a 为 B 的最小上界或上确界．（4）如果 a 是 B 的所有下界集合的最大元，则称 a 为 B 的最大下界或下确界．上、下界未必存在，存在时未必唯一．即使在有上界、下界时，最小上界和最大下界也未必存在． 注意 偏序集的有限子集一定存在极大元和极小元，不一定存在最大元和最小元．极大元和极小元可能存在多个，而最大元和最小元若存在必定是唯一 的．最大元一定是极大元，最小元一定是极小元，反之不一定． 孤立元素本身既是极大元，也是极小元． 最大元一定是最小上界，最小元一定是最大下界，反之不一定． 全序和良序设≼是集合 A 上的一个偏序关系，a，b ∈ A，若有 a ≼ b 或 b ≼a，则称元素 a 和 b 是可比的或可排序的，否则是不可比的或不可排序的．若对任意的 a，b ∈ A，a 与 b 都是可比的，则称≼为 A 上的一个全序． 设≼是集合 A 上的一个偏序，若对于 A 的每一个非空子集 S 都有最小元，则称它为 A 上的一个良序．一个偏序若是良序，则一定是全序． 有限集上的全序一定是良序． |
| CopyRight 2018-2019 实验室设备网 版权所有 |