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

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上的相容关系。 易知，等价关系是一种特殊的相容关系，即具有传递的相 容关系。 在人际关系中朋友关系是相容关系，但它不是等价关系， 因为它满足自反性、对称性、但它不满足可传递性。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 设A={boy, root, cat, beer, and},R是A上的二元关系， 其定义为：当两个单词至少有一个字母相同时， 则认为是相关的。 显然R是自反的，对称的，所以R是A上的相容关系。 但它不是等价关系，因为它不是可传递的。 如(boy, root) ∈R,(root, cat) ∈R,而(boy, cat) ? R 。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 定义： 设R是 A上的相容关系，B是A的子集， 而且在B中任意两个元素都是相关的，则称B为 由相容关系R产生的相容类。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 例如设A={134，345，275，347，348，129}， R是A上的二元关系，其定义为：a,b∈A; 且a 和b至少有一个数码相同，则（a,b）∈R. 显然R是相容关系。A的子集：{134，347，348}， {275，345}，{134，129}等都是相容类。 对于前两个相容类，都能添加新的元素组成新的相容类。 如在相容类{134，347，348}中添加新的元素345，可组成新的相 容类：{134，347，348，345}；在相容类{275，345}中添加新的 元素347，可组成新的相容类：{275，345，347}。 而对于第三个相容类：{134，129}，添加任意一个新元素就 不再组成相容类，称这样的相容类为最大相容类。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 对于最大相容类还可以这样认定：R是 A上的相容关系， B是相容类，在差集A—B中没有元素能和B中所有元素 都是相关的，则称B为最大相容类。 利用相容关系的图形表示可以很方便地确定相容类和最 大相容类。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. * * Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Pro