离散数学等价关系与偏序关系.pptVIP

4.5 等价关系与偏序关系 等价关系的定义 等价类及其性质 商集与集合的划分 等价关系与划分的一一对应 相容关系 偏序关系 偏序集与哈斯图 偏序集中的特定元素 “商”和除法有关，比如把一块蛋糕平均分成四份，从 两种不同的角度看这件事： 从算术角度看：1用4除,每份1/4,这就是“商”,于是: 1=1/4+1/4+1/4+1/4 从集合角度看： 集合A用模3同余关系R划分，得到三个等价类，所以 A {{1,4,7},{2,5,８},{3,6}}={[1]R,[2]R,[3]R}----商集 思考： 设A＝{a, b, c, d}, 给定π1,π2,π3,π4,π5,π6如下：  π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} } 问哪些是A的划分, 哪些不是 A 的划分？ 四、 相容关系 定义： 设R是 A上的二元关系，如果满足： （1）R是自反的； （2） R是对称的。 则称R是A上的相容关系。 易知，等价关系是一种特殊的相容关系，即具有传递的相 容关系。 在人际关系中朋友关系是相容关系，但它不是等价关系， 因为它满足自反性、对称性、但它不满足可传递性。 设A={boy, root, cat, beer, and},R是A上的二元关系， 其定义为：当两个单词至少有一个字母相同时， 则认为是相关的。 显然R是自反的，对称的，所以R是A上的相容关系。 但它不是等价关系，因为它不是可传递的。 如(boy, root) ∈R,(root, cat) ∈R,而(boy, cat) ? R 。 定义： 设R是 A上的相容关系，B是A的子集， 而且在B中任意两个元素都是相关的，则称B为 由相容关系R产生的相容类。 * * 4.5 等价关系和划分 定义 设R是 A上的二元关系，如果 （1） R是自反的； （2） R是对称的； （3） R是可传递的。 则称R是A上的等价关系。若x,y∈R, 称 x 等价于y, 记做 x～y .? 等价关系是经常使用的重要的二元关系。 1、等价关系的定义 一、等价关系 例如，我们用a ,b,c,d,e,f 分别表示6位大学生，其中a ,b,c都姓 张，d,e,f都姓李。 若令集合A={a ,b ,c , d ,e , f } 张 李 R是A上的同姓氏关系（同姓的大学生认为是相关的） 容易验证同姓氏关系R是A上的等价关系。 （1）因为每一个大学生都和自已是同姓的，所以满足自反性； （2）当(a,b) ∈R时有(b,a) ∈R，所以满足对称性； （3）当(a,b) ∈R和(b,c) ∈R时有(a,c) ∈R，所以R是可传递的。 由此可得同姓氏关系 R是等价关系。 又如设集合A的情况同上所述 若令集合A={a ,b ,c , d ,e , f } 20 22 其中a ,b,c,d都是20岁，e,f都是22岁。 如果年龄相同的大学生认为是相关的，那么 “同年龄”关系R是 等价关系。 （1）因为每一个大学生都和自已是同年龄的，所以满足自反性； （2）当(a,b) ∈R时有(b,a) ∈R，所以满足对称性； （3）当(a,b) ∈R和(b,c) ∈R时有(a,c) ∈R，所以R是可传递的。 由此可得同年龄关系 R是等价关系。 再如设集合A的情况同上所述 若令集合A={a , b , d , c , e , f } 同房间 同房间 其中a ,b, d同住一个房间，c, e ,f同住另一个房间。 如果同住一个房间的大学生认为是相关的，那么 “同房间”关系 R也是等价关系。 （1）因为每一个大学生都和自已是同房间的，所以满足自反性； （2）当(a,b) ∈R时有(b,a) ∈R，所以满足对称性； （3）当(a,b) ∈R和(b,c) ∈R时有(a,c) ∈R，所以R是可传递的。 由此可得同房间关系 R是等价关系。 由上述3个例子可知那种同姓氏、同房间、同年龄的关系都是 等价关系。 如果抽象地讨论，对集合A中的元素按照某种特性分成几个组， 每个元素只属于一个组（如按年龄分组，即同年龄人在同一组 内；或按姓氏分组，即同姓人在同一组内），并且定义在同一 组