等价关系与偏序关系学习教案

1、会计学1等价关系等价关系(gun x)与偏序关系与偏序关系(gun x)第一页，共24页。2第1页/共24页第二页，共24页。3设设 A=1,2,8, R= | x,yAxy(mod 3) 第2页/共24页第三页，共24页。4定义定义 设设R为非空集合为非空集合A上的等价上的等价(dngji)关系关系, xA，令令xR = y | yAxRy 称称 xR 为为 x 关于关于R 的等价的等价(dngji)类类, 简称为简称为 x 的等价的等价(dngji)类类, 简简记为记为x. 实例实例 A= 1, 2, , 8 上模上模 3 等价等价(dngji)关系的等价关系的等价(dngji)类：类：

2、1=4=7=1,4,7 2=5=8=2,5,8 3=6=3,6第3页/共24页第四页，共24页。5 定理定理1 设设R是非空集合是非空集合A上的等价关系上的等价关系, 则则 (1) xA, x 是是A的非空子集的非空子集. (2) x, yA, 如果如果 x R y, 则则 x=y. (3) x, yA, 如果如果 x y, 则则 x与与y不交不交. (4) x | xA=A，即所有等价类的并集就即所有等价类的并集就是是A. 第4页/共24页第五页，共24页。6第5页/共24页第六页，共24页。7定义定义 设设R为非空集合为非空集合A上的等价关系上的等价关系, 以以R的所有的所有(suyu)等

3、价类作为元素的集合称为等价类作为元素的集合称为A关于关于R的商集的商集, 记做记做A/R, A/R = xR | xA 实例实例 A=1,2,8，A关于模关于模3等价关系等价关系R的商集为的商集为 A/R = 1,4,7, 2,5,8, 3,6 A关于恒等关系和全域关系的商集为：关于恒等关系和全域关系的商集为： A/IA = 1,2, ,8 A/EA = 1, 2, ,8 第6页/共24页第七页，共24页。8定义定义(dngy) 设设A为非空集合为非空集合, 若若A的子集族的子集族(P(A) 满足下面条件：满足下面条件： (1) (2) xy (x,yxyxy=) (3) =A 则称则称是是A

4、的一个划分的一个划分, 称称中的元素为中的元素为A的划分块的划分块.第7页/共24页第八页，共24页。9第8页/共24页第九页，共24页。10商集商集 A/R 就是就是 A 的一个划分的一个划分 不同的商集对应于不同的划分不同的商集对应于不同的划分 任给任给 A 的一个划分的一个划分, 如下如下(rxi)定义定义 A 上的关系上的关系 R： R = | x,yAx 与与 y 在在的同一划分块中的同一划分块中则则 R 为为 A上的等价关系上的等价关系, 且该等价关系确定的商集且该等价关系确定的商集就是就是. 例例2 给出给出A1,2,3上所有的等价关系上所有的等价关系求解思路：先做出求解思路：先

5、做出A的所有划分的所有划分(hu fn), 然后根然后根据划分据划分(hu fn)写写出对应的等价关系出对应的等价关系. 第9页/共24页第十页，共24页。111,2和和3分别分别(fnbi)对应等价关系对应等价关系 R1, R2 和和 R3. R1=,IA，R2=,IA R3=,IA4 对应对应(duyng)于全域关系于全域关系 EA，5 对应对应(duyng)于恒等关系于恒等关系 IA第10页/共24页第十一页，共24页。12例例3 设设 A=1, 2, 3, 4，在，在 AA上定义上定义(dngy)二元关二元关系系R： ,R x+y = u+v，求求 R 导出的划分导出的划分. 解解 A

6、 A=, , , , , , , , , , , , , 第11页/共24页第十二页，共24页。13第12页/共24页第十三页，共24页。14定义定义 非空集合非空集合(jh)A上的自反、反对称和传递的关系上的自反、反对称和传递的关系，称为，称为A上的偏序关系，记作上的偏序关系，记作 . 设设 为偏序关系为偏序关系, 如如果果 , 则记作则记作 x y, 读作读作 x“小于等于小于等于”y. 实例实例 集合集合(jh)A上的恒等关系上的恒等关系 IA 是是A上的偏序关系上的偏序关系. 小于等于关系小于等于关系, 整除关系和包含关系也是相应集合整除关系和包含关系也是相应集合(jh)上的偏序关系上

7、的偏序关系. 第13页/共24页第十四页，共24页。15x与与 y 可比：设可比：设R为非空集合为非空集合A上的偏序关系上的偏序关系(gun x), x,yA, x与与y可比可比 x y y x.结论：任取两个元素结论：任取两个元素x和和y, 可能有下述情况：可能有下述情况： x y (或或y x), xy, x与与y不是可比的不是可比的.全序关系全序关系(gun x)： R为非空集合为非空集合A上的偏序上的偏序, x,yA, x与与 y 都是可比的，则都是可比的，则称称 R 为全序关系为全序关系(gun x)实例：数集上的小于等于关系实例：数集上的小于等于关系(gun x)是全序关系是全序关

8、系(gun x) 整除关系整除关系(gun x)不是正整数集合上的全序关系不是正整数集合上的全序关系(gun x)第14页/共24页第十五页，共24页。16第15页/共24页第十六页，共24页。17定义定义 集合集合A和和A上的偏序关系上的偏序关系 一起叫做偏序集一起叫做偏序集, 记作记作 .实例：整数集和小于等于关系构成偏序集实例：整数集和小于等于关系构成偏序集，幂集，幂集P(A)和包含关系构成偏序集和包含关系构成偏序集. 哈斯图：利用偏序自反、反对称、传递性简化哈斯图：利用偏序自反、反对称、传递性简化(jinhu)的关的关系图系图特点：每个结点没有环，两个连通的结点之间的序关系通过特点：每

9、个结点没有环，两个连通的结点之间的序关系通过结点位置的高低表示，位置低的元素的顺序在前，具有盖住结点位置的高低表示，位置低的元素的顺序在前，具有盖住关系的两个结点之间连边关系的两个结点之间连边第16页/共24页第十七页，共24页。18例例4 第17页/共24页第十八页，共24页。19A=a, b, c, d, e, f, g, h R=,IA 例例5 已知偏序集已知偏序集的哈斯图如右图所示的哈斯图如右图所示, 试求出集合试求出集合(jh)A和关和关系系R的表达式的表达式. 第18页/共24页第十九页，共24页。20定义定义(dngy) 设设为偏序集为偏序集, BA, yB.(1) 若若x(xB

10、y x) 成立成立, 则称则称 y 为为 B 的最小元的最小元.(2) 若若x(xBx y) 成立成立, 则称则称 y 为为 B 的最大元的最大元. (3) 若若x (xBx y) 成立成立, 则称则称 y 为为B的极小元的极小元. (4) 若若x (xBy x) 成立成立, 则称则称 y 为为B的极大元的极大元. 第19页/共24页第二十页，共24页。21第20页/共24页第二十一页，共24页。22定义定义(dngy) 设设为偏序集为偏序集, BA, yA. (1) 若若x(xBx y) 成立成立, 则称则称 y 为为B的上界的上界. (2) 若若x(xBy x) 成立成立, 则称则称 y 为为B的下界的下界. (3) 令令Cy | y为为B的上界的上界, 则称则称C的最小元为的最小元为B的的最小上界最小上界 或或 上确界上确界. (4) 令令Dy | y为为B的下界的下界, 则称则称D的最大元为的最大元为B的的最大下界最大下界 或或 下确界下确界.第21页/共24页第二十二页，共24页。23第22页/共24页第二十三页，共24页。24例例6 设偏序集设偏序集如下图所示，求如下图所示，求 A 的极小的极小(j xio)元、元、最小元、极大元、最大元最小元、极大元、最大元. 设设 Bb,c,d, 求求