等价关系与偏序关系1.ppt

1等价关系定义4.19 设R为非空集合上的关系. 如果R是自反 的、对称的和传递的, 则称R为A上的等价关系. 设 R 是一个等价关系, 若∈R, 称 x等价于y, 记做 x～y. 由定义知： （1）关系R是等价关系当且仅当R同时具备自反性、对 称性和传递性； （2）关系R不是等价关系当且仅当R不具备自反性或对 称性或传递性2实例设 A={1, 2, …, 8}, R={ | x,y∈A∧x≡y (mod 3)} R 的关系图如：例1 设 A={1, 2, …, 8}, 如下定义 A上的关系R： ￿￿￿￿ R={| x,y∈A∧x≡y (mod 3)} 其中 x≡y (mod 3) 叫做 x与y 模3相等, 即 x 除以3的余数与 y 除以3的余数相等. 不难验证R为A上的等价关系, 因为x∈A, 有x≡x(mod 3) ￿￿ x,y∈A, 若x≡y(mod 3), 则有y≡x(mod 3) ￿￿ x,y,z∈A, 若x≡y(mod 3), y≡z(mod 3), 则有x≡z(mod 3)3定理4.8 设R是非空集合A上的等价关系，则有下面的结论成立 ： 1)对xA，[x]R≠Φ； 2)对x,y∈A，如果y∈[x]R，则有[x]R=[y]R3)对x,y∈A，如果y  [x]R，则有[x]R∩[y]R＝Φ4) ＝A；定义4.20 设R是非空集合A上的等价关系，对任意 x∈A，称集合 [x]R＝{y|y∈A∧∈R}(也即A中 与x等价的全体元素构成的子集)为x关于R的等价类.等价类4集合的划分定义4.21 设A为非空集合, 若A的子集族 ( P(A)) 满足下面条件：(1)  (2) xy (x,y∈∧x≠y→x∩y=)(3) ∪ =A 则称是A的一个划分, 称 中的元素为A的划分块.5商集定义4.22 设R 为非空集合A 上的等价关系, 以R 的 所有等价类作为元素的集合称为A关于R 的商集, 记做 A/R, ￿￿￿￿ A/R = { [x]R | x∈A }6等价关系与划分的一一对应(1) 商集 A/R 就是A 的一个划分 ,不同的商集对应于不同的划分 (2) 任给A 的一个划分 , 如下定义A 上的关系 R： ￿￿ R ={ | x,y∈A∧x 与 y 在的同一划分块中 } 则R 为A上的等价关系, 且该等价关系确定的商集就 是. 7总结1、熟记等价关系的定义； 2、利用等价关系的定义证明一个关系是等价关 系； 3、给定A上的等价关系R，会求所有的等价类和 商集A/R；并求出对应的集合的划分； 4、给定集合A上的划分，会求对应的等价类。

8判定下列关系具有哪些性质1、对任何非空集合A，A上的恒等关系； 2、多边形的“相似关系”、“全等关系”； 3、集合A的幂集P(A)上定义的“包含关系”； 4、集合A的幂集P(A)上定义的“真包含关系”解：1，2都具有自反性，对称性自反性，对称性和和传递性传递性，是等价，是等价关系；关系；3 具有自反性自反性，，反对称性和传递性；4 具有反自反性，反自反性，反对称性，传递性偏序关 系拟序关 系94.7 偏序关系定义4.22 非空集合A上的自反、反对称和传递的关 系，称为A上的偏序关系，记作≼. 设≼为偏序关系, 如果∈≼, 则记作 x≼y, 读作 x“小于或等于”y. 并将集合A与偏序关系R一起叫做偏序集， 用序偶 或者表示不指数的大小， 而指在偏序关 系中的顺序性【实例】试判断下列关系是否为偏序关系：（1）集合A的幂集P(A)上的包含关系“”（2）实数集合R上的小于等于关系“≤” （3）自然数集合N上的模m同余关系； （4）自然数集合N上的整除关系“|”；根据偏序关系的定义知(1)，(2)，(4)，所对应的 关系同时具有自反性，反对称性和传递性，所以都 是偏序集 ；(3)所对应的关系不具有反对称性， 所以不是偏序集 。

11相关概念定义4.24 x与y可比 设R为非空集合A上的偏序关系, ￿￿ x, yA, x与y 可比  x≼y ∨ y≼x. x,y∈A, 如果x≺y且不存在zA使得 x≺z≺y, 则称 y覆盖 x.结论：x, yA，下述几种情况发生其一且仅发生其 一：x≺y, y≺x, x＝y, x与y不是可比的定义4.25 R为非空集合A上的偏序, x, yA, x与y 都可比， 则称R为全序. 实例：数集上的小于或等于关系是全序关系整除关系不是正整数集合上的全序关系{1, 2, 4, 6}集合上的整除关系, 2覆盖1, 4 和 6 覆盖2. 但4不覆盖1.12偏序集与哈斯图定义： 集合A和A上的偏序关系≼一起叫做偏序集, 记作.实例：整数集和数的小于等于关系构成偏序集幂集P(A)和包含关系构成偏序集 . 利用偏序自反、反对称、传递性简化的关系图 ： （1）由偏序关系是自反的，故关系图上每个节 点都有环，用小圆圈或点表示A中的元素，省 掉关系图中的所有的环； （因自反性) （2）对任意x,y∈A，若x＜y，则将x画在y的下 方，可省掉关系图中所有边的箭头；（因反对称性 ） （3）具有覆盖关系的两个结点之间连边.即对 任意x,y∈A(x≠y)，若x ＜ y，且x与y之间不 存在z∈A，使得x ＜ z ＜ y，则x与y之间用一 条线相连，否则无线相连。

（因传递性 ）哈斯图 ：14哈斯图实例例 例 练习115设A={2,3,6,12,24,36}，“≤”是A上的整除关系R，画出 其一般的关系图和哈斯图 解 由题意可得 R={,,,,,,,,,,,,,,,,,,}，从而得出该偏序集 的一般关系图和哈斯图如下：哈斯图236123624关系图23612362416练习2 已知偏序集 的哈斯图如右图所示, 试求出集合A和关系 R的表达式. 解：A={a, b, c, d, e, f, g, h} R={,,,,,,,, }∪IA 174.7.2 极值与最值定义4.26 设为偏序集, BA, y∈B.(1) 若x(x∈B→y≼x)成立, 则称 y 为 B 的最小元.(2) 若x(x∈B→x≼y)成立, 则称 y 为 B 的最大元. (3) 若x(x∈B∧x≼y→x=y)成立, 则称 y 为B的极小元. (4) 若x(x∈B∧y≼x→x=y)成立, 则称 y 为B的极大元. 【性质】￿￿对于有穷集，极小元和极大元必存在，可能存 在多个. 最小元和最大元不一定存在，如果存在一 定惟一.最小元一定是极小元；最大元一定是极大 元. 【特定元素与哈斯图】如果图中有孤立结点，那么这个结点既是极小 元，也是极大元，并且图中既无最小元，也无最大 元(除了图中只有唯一孤立结点的特殊情况)。

除了孤立结点以外，其他的极小元是图中所有 向下通路的终点，其他的极大元是图中所有向上通 路的终点图中唯一的极小元是最小元，唯一的极大元是 最大元；否则最小元和最大元不存在19定义4.27 设为偏序集, BA, yA.（1） 若x (x∈B→x≼y) 成立, 则称 y 为B 的上界. （2） 若x (x∈B→y≼x) 成立, 则称 y 为B 的下界. （3） 令C＝{y | y为B的上界}, 则称C的最小元为B 的最小 上界 或上确界. （4） 令D＝{y | y为B的下界}, 则称D的最大元为B 的最大 下界 或下确界. 由定义4.27可知以下性质： 1. 下界、上界、下确界、上确界不一定存在于集合B中 2. 下界、上界存在不一定惟一 3. 下确界、上确界如果存在，则惟一 4. 子集B的最小元就是它的下确界，最大元就是它的上确 界；反之不对. 偏序集的特定元素20实例练3 设偏序集如下图所示，求A 的极小元、最小元、 极大元、最大元. 设B＝{ b, c, d }, 求B 的下界、上界、下 确界、上确界. 解： A的极小元：a, b, c, g； 极大元：a, f, h； 没有最小元与最大元. B的下界不存在,上界有d 和 f 下确界不存在, 上确界为 d. 实例21练4 A={x1,x2,x3,x4}，A上定义偏序集的哈斯 图如图所示。

求B={x1,x2}和C={x3,x4}上界、下界、 上确界和下确界 【解】 B、C的各种特殊元见下表集合集合上界上界下界下界上确界上确界下确界下确界B无x3,x4无无 Cx1,x2无无无x1x3x2x4实例22练5 设集合A={a,b,c,d,e,f,g,h}，对应的哈斯图 见下图令B1={a,b}，B2={c,d,e}求出B1， B2的最大元、最小元、极大元、极小元、上界、下界、上确界、下确界 【解】B1和B2的各种特殊元素见下表 eabcdfgh集合最大元 最小元 极大元 极小元上界下 界上确 界下确界B1B2无cd,echc,a, bhc无无a,ba,bc,d,e,f, g,h无c无。