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.5
定义 1: 定义在集合 A 上的关系叫作等价关系，如果它是自反的、对称的和传递的。
定义 2: 如果两个元素a 和 b 由于等价关系而相关联，则称它们是等价的，记作 a ∼ b。
下面定义在{0,1,2,3}上的关系哪些是等价的？
下图所示的关系是否是等价关系？
例: 令 m 是一整数，满足m > 1。证明以下关系是定义在整数集上的等价关系。
R = {(a,b) | a ≡ b (mod m)}
解: a ≡ b (mod m) 当且仅当 m 整除 a − b
自反的: a ≡ a (mod m) ，注意 a − a = 0 能被 m 整除，因为 0 = 0 ∙ m
对称的: 假设 a ≡ b (mod m)。 a − b能被 m整除, 即 a − b = km, 其中 k 是整数。从而 b − a = (− k) m， 所以 b ≡ a (mod m)
传递的: 假设 a ≡ b (mod m) ， b ≡ c (mod m)。那么 m 整除 a − b 和 b − c。因此, 存在整数k 和 l 满足 a − b = km 以及 b − c = lm。把两个等式加起来可得:
a − c = (a − b) + (b − c) = km + lm = (k + l) m.
所以, a ≡ c (mod m)
例: 设 R 是定义在英文字母组成的字符串的集合上的关系，满足 aRb 当且仅当 l(a) = l(b), 其中 l(x) 字符串x 的长度。 R是等价关系吗?
解：考察等价关系的所有性质
自反的: 因为 l(a) = l(a)，对于所有的字符串 a 满足 aRa。
对称的: 假设 aRb，l(a) = l(b), l(b) = l(a) 那么有bRa。
传递的: 假设有 aRb 且 bRc。 因为 l(a) = l(b), l(b) = l(c), 故 l(a) = l(c) 即 aRc。
例: 定义在正整数集合上的“整除”关系不是等价关系。
解: 整除关系是自反和传递的，但不是对称的。因此整除关系不是等价关系。
自反的: a ∣ a ，对于所有a
非对称的: 例如, 2 ∣ 4, 但 4 ∤ 2
传递的: 假设 a 整除 b 且 b 整除 c。那么存在正整数 k 和 l 满足 b = ak 和 c = bl。因此, c = a(kl), 于是 a 整除 c。
定义 3: 设 R 是定义在集合 A 上的等价关系。
A 中的一个元素a 有关系的所有元素的集合叫作a 的等价类，记作 [a]R。
当只考虑一个关系时，我们可以省去下标R 并把这个等价类写作[a]。
注意 [a]R = {x |(a, x) ∈ R }。
例：设 A={1,2,…,8}
R={
解：R={(1,4),(4,1),(1,7),(7,1),(4,7),(7,4),(2,5),(5,2),(2,8), (8,2),(5,8),(8,5),(3,6),(6,3)}∪∆
A的等价类为[1]={1,4,7} , [2]={2,5,8}, [3]={3,6}
如果 b ∈ [a]R, 那么 b 也可叫作这个等价类的代表元。一个等价类中的任何元素都可以作为这个等价类的代表元。
模m 同余的等价类叫作模 m 同余类。整数a模 m 同余类记作[a]m , 满足 [a]m = {…, a−2m, a−m, a+2m, a+2m, … }。例如:
[0]4 = {…, −8, −4 , 0, 4 , 8 , …} [1]4 = {…, −7, −3 , 1, 5 , 9 , …}
[2]4 = {…, −6, −2 , 2, 6 , 10 , …} [3]4 = {…, −5, −1 , 3, 7 , 11 , …}
当n为下列各数时，同余类[n]5是什么？
定理 1: 设 R 是定义在集合 A 上的等价关系。下面关于集合A中的 a 和 b 两个元素的命题是等价的：
(ii) [a] = [b]
(iii) [a] ∩ [b] ≠
例：设 A={1,2,…,8}, R={
定义: 集合 S 的划分是 S 的不相交的非空子集构成的集合，且它们的并集就是 S 。
换句话说, 一族子集 Ai, i ∈ I (其中 I 是下标的集合), 构成 S 的划分，当且仅当
Ai ≠ ∅ ， i ∈ I,
Ai ∩ Aj=∅ ， i ≠ j
例：设 A={1,2,…,8}, R={
[1]=[4]=[7]={1,4,7} [2]=[5]=[8]={2,5,8} [3]=[6]={3,6}
以上3 类两两不交， {1,4,7}{2,5,8}{3,6} = {1,2, … ,8}
设 R 是定义在集合 A 上的等价关系。
R 的所有等价类的并集就是集合 A, 因为 A 的每个元素a都在它自己的等价类中，即[a]R。 换句话说,
从定理 1, 这些等价类或者相等或者不相交, 因此当 [a]R ≠ [b]R 时，[a]R ∩[b]R=∅.
等价类构成A的划分，因为它们将A划分成不相交的子集。
下列是集合{1,2,3,4,5,6}的划分的是：
(a) {1}, {2,3,4}, {5,6}
(b) {1,2},{2,3,4},{4,5,6}
(c) , {1}, {2,3,4}, {5,6}
(d) {1}, {2,4}, {5,6}
等价类与划分(continued)
定理 2: 设 R 是定义在集合S上的等价关系，那么R 的等价类构成S的划分。反过来，给定集合S的划分{Ai | i ∈ I}, 则存在一个等价关系R ，它以集合Ai, i ∈ I, 作为它的等价类。
证明: 第一部分已经在前面进行了证明。
第二部分的证明，只需证明R具有如下性质：
自反的: 对每个 a ∈ S, (a,a) ∈ R。
对称的: 如果 (a,b) ∈ R, 那么 b 和 a 属于划分的同一子集,所以 (b,a) ∈ R。
传递的: 如果 (a,b) ∈ R 且 (b,c) ∈ R, 那么 a 和 b 是属于划分的同一子集, 对于b 和 c也是如此。又因为划分的各子集之间是不相交的，那么 b 属于两个子集, 这两个子集必是同一个。因此 (a,c) ∈ R ，那么 a 和 c属于同一个子集。
列出由{0，1，2，3，4，5}的划分产生的等价关系中的有序对。
{0}，{1,2}，{3,4,5}
{0,1}，{2,3}，{4,5}
Section 5.6
定义 1: 定义在集合S 上的关系R ，如果它是自反的、反对称的和传递的，就成为偏序（partial ordering）。
集合S与定义在其上的偏序 R 一起成为偏序集，
记作(S, R)。 集合 S 中的成员称为偏序集的元素。
下面定义在{0,1,2,3}上的关系哪些是偏序的？
偏序(continued)
例 1: 证明“大于等于” 关系 (≥) 是整数集合上的偏序。
自反的: 对所有整数a， a ≥ a。
反对称的: 如果 a ≥ b 且 b ≥ a , 那么 a = b。
传递的: 如果 a ≥ b 且 b ≥ c , 那么 a ≥ c。
偏序(continued)
例 2: 整除关系(∣) 是整数集合上的偏序。
自反的: 对所有的整数a ,a ∣ a 。
反对称的: 如果 a 和 b 正整数，且满足 a | b 和 b | a, 那么 a = b。
传递的: 假设 a 整除 b ， b整除c，那么存在一个正整数 k 和 l 以至于b = ak ， c = bl。 因此, c = a(kl), 所以 a 整除 c。故, 整除关系是传递的。
(Z+, ∣) 是偏序集。
偏序(continued)
例3: 证明包含关系(⊆) 是定义在集合 S 的幂集上的偏序。
自反的: A ⊆ A ，只要 A ⊆ S。
反对称的: 如果 A ⊆ B 和 B ⊆ A, 那么 A = B。
传递的: 如果 A ⊆ B ， B ⊆ C, 那么 A ⊆ C。
下面哪些集合是偏序集？
确定以下0-1矩阵表示的关系是否为偏序。
确定有向图所表示的关系是否为偏序。
可比性 Comparability
定义 2: 偏序集(S,≼ )中的元素a 和 b 称为可比的，如果 a ≼ b 或 b ≼ a。
当 a 和 b 是S 中的元素并且既没有a ≼ b 也没有 b ≼ a，那么称 a 和b 是不可比的。
例：在偏序集(Z+, ∣)中，3和9是可比的，5和7是不可比的。
符号≼用来表示任意偏序集中的关系
在下面的偏序集中找出两个不可比的元素。
(P ({0,1,2}), )
({1,2,4,6,8}, |)
定义 3: 如果 (S，≼ ) 是偏序集，且S 中的每对元素都是可比的，则S 称为全序集或线序集，且≼ 称为全序或线序。一个全序集也称为链。
定义 4: 对于偏序集(S,≼ ) ，如果 ≼ 是全序，并且 S 的每个非空子集都有一个最小元素，就称它为良序集。
定义: 给定两个偏序集(A1,≼1) 和 (A2,≼2), 则其笛卡儿积A1 ⨉ A2 上的字典顺序定义为 (a1, a2) 小于(b1,b2), 即,
(a1, a2) ≺ (b1,b2),
或者a1 ≺1 b1 ，或者如果a1 = b1 且 a2 ≺2 b2。
例: 考虑英文小写字母构成的字符串。字典顺序可以用字母在字母表中定义的顺序。
discreet ≺ discrete,因为这些字符串在第七个位置不同且e ≺ t。
discreet ≺ discreetness,因为前八个字母一致，但第二个字符串较长。
定义: Hasse图是直观地表示偏序，有一些边不必显示出来，因为它们是必须存在的（自反性和传递性）。
图(a)表示偏序关系，因为自反性，图中所有顶点都有环，可以不画，因为是必须存在的，得到图 (b)。由于偏序是传递的，所以表示传递的边也可以不画，得到图 (c)。
使用哈塞图表示有穷偏序集(S, ≼ ), 从偏序关系的有向图开始:
移走所有的环(a, a) 。
移走所有这样的边(x, y) ，存在z ∈ S 满足x ≺ z 且 z ≺ y。
最后，排列每条边使得它的起点在终点下面。移走有向边上所有的箭头，所有的边“向上”指向它们的终点。
用平面上的点代表集合中的元素，当b盖住a时，代表b的点应画在代表a的点的上方，并用直线段连接．否则不画线。
例：A = {1，2，3，4，5，6，8，10，12，16，24}，R是A上的整除关系，Ｒ的哈塞图如下：
例：画出幂集P(S)上的偏序{(A,B)|A ⊆ B}的哈塞图，其中S={a,b,c}。
已知偏序集（A, R）的哈塞图如图所示, 试求出集合A和关系R的表达式。
A={a, b, c, d, e, f, g, h}
R={(b,d),(b,e),(b,f),(c,d),
(c,e),(c,f),(d,f),(e,f),(g,h)}∪IA
定义: 设(S， ≼)是偏序集，如果S中存在元素a，使得S中没有其他元素b，满足a b，则称a为S中的极大元。
定义: 设(S，≼)是偏序集，如果S中存在元素a，使得S中没有其他元素b，满足b a，则称a为S中的极小元。
例:A = {2，3，4，6，8，12，16,24}， ≼是A上的整除关系。其哈塞图见图。
(A， ≼)的极小元为2和3，极大元为16和24。
定义：设(S， ≼)是偏序集，如果S中存在元素a，使得对于S中任何元素b，都有b ≼ a，则称a为S中的最大元。
定义：设(S ， ≼)是偏序集，如果S中存在元素a，使得对于S中任何元素b，都有a ≼ b，则称a为S中的最小元。
注意:最大(小)元与极大(小)元的区别
例2:A = {1，2，3，4，6，12}， ≼是整除关系，其哈塞图见下图。
1是最小元，12是最大元。
偏序集中特殊元素的性质
对于有穷集，极小元和极大元必存在，可能存在多个。
最小元和最大元不一定存在，如果存在一定唯一。
最小元一定是极小元；最大元一定是极大元。
孤立结点既是极小元，也是极大元。
A = {1，2，3，4，5，6，10，12}， ≼是A上的整除关系。其哈塞图见右。
子集{1，2，3，6}中，1是极小元也是最小元；6是极大元也是最大元。
子集{2，3，4，12}中，2和3是极小元；但没有最小元；12是极大元也是最大元。
子集{2，5，6}中，2和5是极小元，而5还是极大元，6也是极大元，但此子集中没有最小元也没有最大元。
定义：设(A， ≼)是偏序集，B为A的子集，如果在A中存在元素a，使得对于子集B中任何元素b，都有b ≼ a，则称a为子集B的上界；
同样，如果在A中存在元素a，使得对于子集B中任何元素b，都有a ≼ b，则称a为子集B的下界。
注意：上界(下界)与最大(小)元和极大（小）元的区别
设A = {1，2，3，4，5，6，10，12 }， ≼为整除关系。
在子集{2，3，6}中，上界为6和12，下界为1。
在子集{2，3，6，12}中，
在子集{2，5，6}中，
在子集{2，4}中，
上界为12，下界为1。
没有上界，下界为1。
上界为4和12，下界为1和2。
定义:设(S， ≼)是偏序集，A是S的子集，a是子集A的上界，如果对于A中的任何上界x，都有a ≼ x，则称a为子集A的最小上界（或称上确界），记作lub(A) = a；
同样，b是子集A的下界，如果对于A的任何下界y，都有y ≼b，则称b为子集A的最大下界（或称下确界），记作glb(A) = b。
例：最小上届、最大下界
设A = {1，2，3，4，5，6，10，12 }， ≼为整除关系。
在子集{2，3，6}中，最小上界为6，最大下界为1。
在子集{2，3，6，12}中，
在子集{2，5，6}中，
在子集{2，4}中，
最小上界为12，最大下界为1。
没有最小上界，最大下界为1。
最小上界为4，最大下界为2。
偏序集中特殊元素的性质
下界、上界、最大下界、最小上界不一定存在。
下界、上界存在不一定唯一。
最大下界、最小上界如果存在，则唯一。
集合的最小元就是它的最大下界，最大元就是它的最小上界；反之不对。
设偏序集(A, ≼)如下图所示，求 A 的极小元、最小元、极大元、最大元。 设 B＝{b,c,d }, 求 B 的下界、上界、最大下界、最小上界。
极小元：a, b, c, g；
极大元：a, f, h；
没有最小元与最大元。
B的下界和最大下界都不存在, 上界有d 和 f,
练习：确定下列哈塞图的最大，最小元
1）最小元a,无最大元
2）无最小元,无最大元
3）无最小元,最大元d
4）最小元a,最大元d
找出图所示哈斯图的子集{a,b,c}、{j,h}和{a,c,d,f}的上界和下界
{a,b,c}上界：e,f,j,h
{j,h} 上界：无
下界：a,b,c,d,e,f
{a,c,d,f}上界：f,j,h
例：如果一个偏序集的每对元素都有最小上界和最大下界，就称这个偏序集为格。
幂集上的偏序{(A,B)|A ⊆ B}是否是格？
课后题 25、27、33、35、43
1.设A={a,b,c},试给出A上的一个二元关系R，使其同时不满足自反，反自反，对称，反对称和传递性。
2.下面的图具备什么性质？
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com