离散数学等价关系与偏序关系(课堂PPT)

[3]=[6]={3,6}
5
集合与图论
等价类的性质
定理1 设R是非空集合X上的等价关系, 则 (1) xX, [x]≠ 。
(2) x, yX, 如果(x, y)R, 则 [x]=[y]。
(3) x, yX, 如果(x, y)R, 则 [x]∩[y]=。
(4)
，即所有等价类的并集就是X。
6
集合与图论
集合与图论
等价关系的运算
R的等价闭包(R的自反对称传递闭包)，记为e(R), e(R)是X上包含R的那些等价关系的交集。
定理4 设R为X上的一个二元关系，则 e(R)=(R∪R-1)*。
定理5 设R,S是X上的等价关系，则RS是等价关 系的充要条件是RS=SR。
推论 设R,S是X上的等价关系，则RS是等价关 系的充要条件是RSSR。
定理1 设R是X上的一个等价关系，则R的所有等 价类的集合是X的一个划分。
定理2 设是集合X的一个划分，令 R ={(x,y) | x,yX∧x与y在的同一划分块中}
则R是X上的一个等价关系，并且就是R的等价类之集。
注： 由定理1、2可得：X上的等价关系与X的划分 是一一对应的，并且互相确定。
9
集合与图论
2
集合与图论
等价关系实例
例2：考虑整数集Z上的模n同余关系。
是等价关系。
例3：实数集上的“>”、“<”、“≧”、“≦”是 不是R上的等价关系？
实数集上的“>”、“<”、“≧”、“≦”都不 是R上的等价关系。
例4：设f:XY，Ker(f)={(x,y)x,yX，且f(x)=f(y)}。 Ker(f)是X上的等价关系。
A关于恒等关系和全域关系的商集为： A/IA = { {1},{2}, … ,{8}} A/EA = { {1, 2, … ,8} }
11
集合与图论
实例
例8：给出A＝{1,2,3}上所有的等价关系。 求解思路：先做出A的所有划分, 然后根据划分写出 对应的等价关系。
12
集合与图论
实例
A上的等价关系与划分之间的对应：
x的等价类常记为[x]，即[x]={yyX且xRy}。
例5：设 A={1, 2, …, 8}, 如下定义 A上的关系R： R={(x,y)| x,yA∧x≡y (mod 3)}
A={ 1, 2, … , 8 }上模 3 等价关系的等价类：
[1]=[4]=[7]={1,4,7}
[2]=[5]=[8]={2,5,8}
4对应于全域关系EA； 5对应于恒等关系IA； 1, 2和 3分别对应于等价关系 R1, R2和R3，其中 R1={(2,3),(3,2)}∪IA R2={(1,3),(3,1)}∪IA R3={(1,2),(2,1)}∪IA
问题：设集合X为有限集，|X|=n，则X上有多少个 等价关系？
13
1={{a, b, c},{d}}， 2={{a, b},{c},{d}} 3={{a},{a, b, c, d}}， 4={{a, b},{c}} 5={,{a, b},{c, d}}， 6={{a,{a}},{b, c, d}}
1和 2是A的划分，其他都不是A的划分。
8
集合与图论 等价关系与集合的划分
3
集合与图论
等价关系的关系图
例5：设 A={1, 2, …, 8}, 如下定义 A上的关系R： R={(x,y)| x,yA∧x≡y (mod 3)}
R 的关系图如下：
4
集合与图论
等价类的定义
定义2 设R是X上的一个等价关系，xX，X的 子集Ex={yyX且xRy}称为x关于R的等价类，或简 记为x的等价类。
14
集合与图论
2 偏序关系
定义1 集合X上的二元关系R称为偏序关系，如 果R同时满足以下三个性质：
1. R是自反的； 2. R是反对称的；
3. R是传递的。
当抽象地讨论X上的偏序关系时，常用符号“” 表示偏序关系。如果xy，则读作“x小于或等于y”。
约定xy且xy时，就记为x<y。
如果存在x,yX使得xy与yx中有一个成立，则称x 与y可比较;
集wk.baidu.com与图论 第9节 等价关系与偏序关系
主要内容：
• 等价关系 • 偏序关系
1
集合与图论
1 等价关系
定义1 集合X上的二元关系R称为等价关系，如果R 同时具有以下三个性质：
1. R是自反的，即xX，xRx;
2. R是对称的，即如果xRy，则yRx;
3. R是传递的，即如果xRy，yRz，则xRz。
例1：集合X上的恒等关系是不是X上的等价关系？ 是X上的等价关系。
若x≥y且xy，则简记为x>y。
S的子集间的包含关系是2S上的偏序关系， (2S,)是一个偏序集。
在这个偏序集中，存在着不可比较元素。 例如：S={a,b,c}，则{a}与{b,c}不可比较。
16
集合与图论
实例
例2：自然数集合N上的整除关系“”是不是偏序关系? 自然数集合N上的整除关系“”是偏序关系。 (N,)是一个偏序集。
设≤是X上的偏序关系，则≤的逆≤-1也是X上的偏 序关系，以后用“≥”表示≤的逆关系，并读成“大 于或等于”。
商集
等价关系R确定的划分是R的所有等价类之集 {[x]xX}
定义4 设R是X上的等价关系，由R所确定的X的 划分也就是R的所有等价类之集称为X对R的商集， 并记X/R。
即：X/R={[x] xX，[x]是x的等价类}。
10
集合与图论
实例
例7：令A={1, 2, …, 8}。
A关于模 3 等价关系R 的商集为： A/R = { {1, 4,7}, {2, 5, 8}, {3, 6} }
在偏序关系中，并不是X中所有元素都可比较; 如果x,yX，xy并且yx，则称x与y不可比较。15
集合与图论
偏序集
定义2 设是X上的一个偏序关系，则称二元 组(X,)为偏序集。
一个集合上可能存在多个偏序集。 例如实数集上存在(R,)和(R,≥)两个偏序集。
例1：设S是一个集合，S的子集间的包含关系是不 是偏序关系？
集合的划分
定义3 设X为非空集合，X的若干个子集形成的集 族称为X的一个划分，如果具有性质：
(1) ；
(2) x,y，若xy，则x∩y=;
(3)
。
称 中的元素为X的划分块。
如果是X的一个划分，则当=k时， 被称为X的 一个k-划分。
7
集合与图论
实例
例6：设A＝{a, b, c, d}, 给定 1, 2, 3, 4, 5, 6