Induction and recursion
Copyright © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of McGraw-Hill Education.
大数据科学系/大连东软信息学院
Copyright By PowCoder代写 加微信 powcoder
Section 5.1
定义: 一个从集合 A 到集合 B 的二元关系R 是A×B的子集， R ⊆ A × B。
令 A = {0,1,2} ， B = {a,b}
{(0, a), (0, b), (1,a) , (2, b)} 是从A 到 B的关系。
使用集合、图或矩阵表示从A 到集合 B 的关系:
关系是函数的一般表示。一个函数是一个关系，只要对A中的每个元素指定B中唯一的一个元素与之对应。
定义: 集合 A 上的一个二元关系R 是 A × A 的子集或者叫从A 到 A的关系。
令 A = {a,b,c}。 那么 R = {(a,a),(a,b), (a,c)} 是 A 上的一个关系。
令 A = {1, 2, 3, 4}。
关系 R = {(a,b) | a 整除 b} 的有序对有 (1,1), (1, 2), (1,3), (1, 4), (2, 2), (2, 4), (3, 3), 和 (4, 4)。
集合上的二元关系(续)
问题: 在集合 A上有多少个不同的关系?
解: 集合A 上的关系是 A ⨉ A的子集, A × A子集的个数有多少？
因为如果A 有 n 个元素，那么A × A 有 n2 个元素, 并且n 个元素的集合有2n 个子集（幂集的基）, 所以 A × A的子集有个。
于是n 个元素的集合有个关系。
集合上的二元关系(续)
例: 考虑整数集合上的关系:
R1 = {(a,b) | a ≤ b}, R4 = {(a,b) | a = b},
R2 = {(a,b) | a > b}, R5 = {(a,b) | a = b + 1},
R3 = {(a,b) | a = b 或者 a = −b}, R6 = {(a,b) | a + b ≤ 3}.
上述哪些关系包含了如下有序对？
(1,1), (1, 2), (2, 1), (1, −1), 和 (2, 2)?
解:检查每个关系定义的条件, 我们发现(1,1) 在R1, R3, R4 , 和 R6中, (1,2) 在R1 和 R6中， (2,1) 在 R2, R5, 和 R6中， (1, −1) 在R2, R3, 和 R6 中， (2,2) 在R1, R3, 和 R4中。
请注意，这些关系是在一个无限集上，每一个关系是一个无限集。
定义: R 是自反的，iff 对每个元素x ∊ A有(x, x) ∊ R。
∀x[x ∊A ⟶ (x, x) ∊ R]
例: 下面定义在整数上的关系是哪些是自反的:
R1 = {(a,b) | a ≤ b}, R4 = {(a,b) | a = b},
R2 = {(a,b) | a > b}, R5 = {(a,b) | a = b + 1},
R3 = {(a,b) | a = b 或者 a = −b}, R6 = {(a,b) | a + b ≤ 3}.
如果A = ∅ 那么显然空关系是自反的。空集合上的空关系是自反的!
定义: R 是反自反的，iff 对每个元素x ∊ A有(x, x) ∊ R。
∀x[x ∊A ⟶ (x, x) R]
例: 下面定义在整数上的关系是哪些是反自反的:
R1 = {(a,b) | a ≤ b}, R4 = {(a,b) | a = b},
R2 = {(a,b) | a > b}, R5 = {(a,b) | a = b + 1},
R3 = {(a,b) | a = b 或者 a = −b}, R6 = {(a,b) | a + b ≤ 3}.
定义: R 是对称的，对于任意的x,y ∊ A，若(x,y) ∊ R 就有(y,x) ∊ R。 ∀x∀y [(x,y) ∊R ⟶ (y,x) ∊ R]
例: 下面在整数集合上的关系哪些是对称的:
R1 = {(a,b) | a ≤ b}, R4 = {(a,b) | a = b},
R2 = {(a,b) | a > b}, R5 = {(a,b) | a = b + 1},
R3 = {(a,b) | a = b 或者 a = −b}, R6 = {(a,b) | a + b ≤ 3}.
定义: 关系R是反对称的。对于任意的x,y ∊ A ，若(x,y) ∊ R 且(y,x) ∊ R ，那么x = y 。 ∀x∀y [(x,y) ∊R ∧ (y,x) ∊ R ⟶ x = y]
例:下面在整数集合上的关系哪些是反对称的:
R1 = {(a,b) | a ≤ b}, R4 = {(a,b) | a = b},
R2 = {(a,b) | a > b}, R5 = {(a,b) | a = b + 1},
R3 = {(a,b) | a = b 或者 a = −b}, R6 = {(a,b) | a + b ≤ 3}.
定义: 集合A 上的关系R是传递的，如果对于任意的x,y,z ∊ A，(x,y) ∊ R 且 (y,z) ∊ R, 那么 (x,z) ∊ R。
∀x∀y ∀z[(x,y) ∊R ∧ (y,z) ∊ R ⟶ (x,z) ∊ R ]
例: 下面整数集合上的关系是传递的:
R1 = {(a,b) | a ≤ b}, R4 = {(a,b) | a = b},
R2 = {(a,b) | a > b}, R5 = {(a,b) | a = b + 1},
R3 = {(a,b) | a = b 或者 a = −b}, R6 = {(a,b) | a + b ≤ 3}.
(a) {(2,2), (2,3), (2,4), (3,2), (3,3), (3,4)}
(b) {(1,1), (1,2), (2,1), (2,2), (3,3), (4,4)}
(c) {(2,4), (4,2)}
(d) {(1,2), (2,3), (3,4)}
(e) {(1,1), (2,2), (3,3), (4,4)}
(f) {(1,3), (1,4), (2,3), (2,4), (3,1), (3,4)}
给定两个关系R1 和 R2, 我们可以按照两个集合组合的任何方式来组合生成新的关系 R1 ∪ R2, R1 ∩ R2, R1 − R2, 以及 R2 − R1。
例: 令 A = {1,2,3} ，B = {1,2,3,4}。 关系 R1 = {(1,1),(2,2),(3,3)} ， R2 = {(1,1),(1,2),(1,3),(1,4)} 可以得到:
R1 ∪ R2 ={(1,1),(1,2),(1,3),(1,4),(2,2),(3,3)}
R1 ∩ R2 ={(1,1)}
R1 − R2 ={(2,2),(3,3)}
R2 − R1 ={(1,2),(1,3),(1,4)}
R1 是从集合A 到集合 B的关系。
R2 是从集合B 到集合 C 的关系。
关系R1与R2 的合成, 是从A 到 C 的关系，其中
如果 (x,y) 属于R1 且 (y,z) 属于R2, 那么 (x,z) 属于 R2∘ R1
R2 ∘ R1= {(b,x),(b,z)}
R={(1,1),(1,4),(2,3),(3,1),(3,4)}
S={(1,0),(2,0), (3,1),(3,2),(4,1)}
设A={a, b, c, d}，R1和R2是A上的关系，
其中R1={(a,a), (a,b), (b,d)},
R2={(a,d), (b,c), (b,d), (c,d)}，
求R1oR2，R2oR1
定义: 令 R 是A上的关系。那么关系 R 的幂Rn 能递归的定义为:
初始: R1 = R
递归: Rn+1 = Rn ∘ R
传递关系的幂是该关系的子集。由以下定理建立的:
定理 1: 集合A上的关系R 是传递的，当且仅当 Rn ⊆ R ， n = 1,2,3 ….
（1）假设(a,b) ∊Rn+1 ，因为 Rn+1 = Rn ∘ R，所以存在元素x ∊A使得(a,x) ∊R且(x,b) ∊Rn ，由归纳假设可知， Rn ⊆ R，所以(x,b) ∊ R。
（2）又因为R是传递的， (a,x) ∊R且(x,b) ∊R，所以(a,b) ∊R。
R={(a,b),(b,c),(c,d),(d,b)}
Section 5.3
可以用0-1矩阵表示有限集之间的关系。
假设 R 是从A = {a1, a2, …, am} 到 B = {b1, b2, …, bn}的关系。
关系 R 可以用矩阵MR = [mij]表示，其中
当 ai 和 bj 有关系时表示R的0-1矩阵的(i, j)项是1，没有关系时，该项是 0 。
例 1: 假定 A = {1,2,3} ， B = {1,2}。令 R 是从 A 到 B 关系，如果 a ∈ A, b ∈ B, 且 a > b，则R包含(a, b) 。 表示R 的矩阵是什么?
解: 因为 R = {(2,1), (3,1),(3,2)}, 矩阵是
(假设元素的顺序与数值递增的顺序相同)
用矩阵表示关系(cont.)
例 2: 令 A = {a1,a2, a3} ，B = {b1,b2, b3,b4, b5}。哪些有序对在下面矩阵所表示的关系R中？
解: 因为 R 包含有序对 (ai, bj) 满足 mij = 1, 所以:
R = {(a1, b2), (a2, b1),(a2, b3), (a2, b4),(a3, b1), {(a3, b3), (a3, b5)}.
表示集合上关系的矩阵
如果集合上关系 R 是自反的, 矩阵MR 的所有主对角线上的元素都等于1。
R 是对称的, 当且仅当只要mij = 1 就有 mji = 1。
R 是反对称的, 当且仅当如果mij = 1 且 i≠ j ，则mji = 0 。
表示集合上关系的矩阵
例 3: 假定集合上的关系 R 用下面矩阵表示：
R 是自反的, 对称的, 和反对称的吗?
解: 因为所有的对角元素都等于1, R 是自反的。 因为 MR 是对称阵, R 是对称的，不是反对称的。
定义: 一个有向图由顶点集合 V 和边集 E 组成，其中边集是V 中元素的有序对的集合。顶点a 叫作边 (a,b)的始点，顶点 b 叫作这条边的终点。
形如 (a,a) 的边叫作环。
例 7: 具有顶点a, b, c和d,
边(a, b), (a, d), (b, b), (b, d), (c, a), (c, b)
和(d, b) 的有向图。
例 8:这个有向图表示的关系中的有序对是什么?
解: 这个关系中的有序对为
(1, 3), (1, 4), (2, 1), (2, 2), (2, 3), (3, 1), (3, 3), (4, 1)和(4, 3)
从有向图确定关系的性质
自反的: 有向图的每个顶点都有环。
反自反：有向图的每个顶点都没有环。
对称的: 如果有边(x,y), 就有边(y,x)。
反对称的: 如果有边(x,y) 满足 x ≠ y, 就没有边 (y,x) 。
传递的: 如果有边 (x,y) 和 (y,z), 那么也有边(x,z)。
自反的? 不是， 不是每个顶点都有环
对称的? 是 (平凡的)，从任意一个顶点到其它顶点没有边
反对称的? 是 (Triviality)，从任意一个顶点到其它顶点没有边
传递的? 是, (Triviality)，从任意一个顶点到其它顶点没有边
从有向图确定关系的性质– 例 1
在很多数学的定义中，遇到“平凡”一词，英文为Triviality(琐碎的，没用的)。翻译成“平凡”反而让没接触过的读者很难以理解。其实就是特别简单的，特别显而易见的，用屁股想都知道的一个问题的解。而常常在一个相对复杂的问题中，这类解是可以被人忽略的，但是对于问题的完整性，又不得不提，所以只能加上限制条件–非平凡解。
自反的? 不是， 没有环
对称的？不是，从a 到b有边, 但从b 到 a没有边
反对称的? 不是， 有边从d到b 且从 b到 d
传递的?不是， 有从 a 到 b且从 b 到 d, 但没有边从a 到 d
从有向图确定关系的性质– 例 2
自反的? 不是， 没有环
对称的？不是，没有边从c 到 a
反对称的？是, 有边从一个顶点到其它顶点，但不存在反向
传递的? 是， 有边从 a 到 b
从有向图确定关系的性质– 例 3
自反的? 不是， 没有环
对称的？不是，没有边从d 到 a
反对称的？是, 有边从一个顶点到其它顶点，但不存在反向
传递的 ? 是 (trivially), 没有这样的两条边，以第一条边的终点作为第二条边的始点。
从有向图确定关系的性质– 例 4
设A={1,2,3}，对每种关系写出关系矩阵，并说明它所具有的性质。
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com