离散数学相容关系.pptVIP

3-11 相容关系 特殊的关系：等价关系?相容关系 定义3-11.1 给定集合A上的关系r, 若r是自反的, 对称的， 则称r是相容关系。 例如，设A是由下列英文单词组成的集合: A={cat, teacher, cold, desk, knife, by} 定义关系： 3-11 相容关系 3-11 相容关系 由于相容关系是自反和对称的，因此其关系矩阵的对角线元素都是1，且矩阵是对称的。为此可将矩阵用梯形表示。 3-11 相容关系 在相容关系的关系图上，每个结点处都有自回路且每两个相关给点间的弧线都是成对出现的。为了简化图形，我们今后画相容关系因，不画自回路，并用单线代替来回弧线 3-11 相容关系 3-11 相容关系 最大相容类： 3-11 相容关系 例题1 设给定相容关系图，写出最大相容类 3-11 相容关系 3-11 相容关系 3-11 相容关系 3-11 相容关系 3-11 相容关系 3-11 相容关系 3-11 相容关系：小结 3-11 相容关系：小结 3-12 序关系 在一个集合上，常常要考虑元素的次序关系，其中很重要的一类关系称作偏序关系 3-12 序关系 3-12 序关系 为了更清楚地描述偏序集合中元素间的层次关系，先介绍“盖住”的概念。 3-12 序关系 3-12 序关系 约定，若A的子集只有单个元素，则这个子集既是链又是反链 3-12 序关系 3-12 序关系 3-12 序关系 从哈斯图中可以看到偏序集A中各个元素处于不同层次的位置 下面讨论偏序集中具有一些特殊位置的元素：极大元、极小元 3-12 序关系 例题6 设A＝{2,3,5,7,14,15,21}，其偏序关系 R={2,14,3,15,3,21,5,15,7,14,7,21,2,2,3,3,5,5,7,7,14,14,15,15,21,21} 求B={2,7,3,21,14}的极大元与极小元。 3-12 序关系 3-12 序关系 3-12 序关系 3-12 序关系 3-12 序关系 3-12 序关系 3-12 序关系:小结 3-12 序关系:小结 3-12 序关系:小结 3-12 序关系:小结 例 偏序集A, ≤，其中A={a,b,c,d}，偏序关系≤={a,a,b,b,b,a,c,c,d,d,d,a,d,b,d,c} 画出A, ≤的哈斯图 设B={b,c}，求B的所有上界集合C和上确界，下界集合D和下确界。 解： (1) COV A={b,a,d,b,d,c} a b d c B没有上界。下界集合D={d}，下确界是d。 例 设偏序集合的哈斯图如图所示，求 极大元和极小元 最小元和最大元，如果有 如果存在，确定LUB{d,c},GLB{a,g} 找出满足条件e≤x的元素x h g f e c b a d 定义3-12.9 任一偏序集合，假如它的每一个非空子集存在最小元素，这种偏序集称为良序的。 例如，In={1,2,…,n}及N={1,2,3,…}，对于小于等于关系来说是良序集合，即In, ≤， In, ≤是良序集合。 定理3-12.2 每一个良序集合，一定是全序集合。 证明 设A, ≤为良序集合，则对任意两个元素x,y∈A可构成子集{x,y}，必存在最小元素，这个最小元素不是x就是y，因此一定有x≤y或y≤x。所以A, ≤为全序集。 定理3-12.3 每一个有限的全序集合，一定是良序集合。 证明 设A={a1,a2,…,an}，令A, ≤是全序集合，假定A, ≤不是良序集合，那么必定存在一个非空子集B?A，在B中不存在最小元素。由于B是一个有限集合，故一定可以找出两个元素x,y是无关的，由于A, ≤是全序集，x,y∈A，x,y必有关系，得出矛盾，故A, ≤必是良序集合。 注意 上述结论对于无限的全序集合不一定成立。 例如，大于零小于1的全部实数，按大小次序关系是一个全序集合，但不是良序集合，因为集合本身就不存在最小元素。 习题3-12 (7) (a) 哈斯图如下，因为3,2之间无偏序关系，所以它不是全序关系。又因为{2,3}不存在最小元，所以也不是良序关系。 3 1 4 2 *离散数学-lecture15 * 则r是相容关系 r={x,y|x,y∈A且x和y有相同的字母} 令x1=cat，x2=teacher， x3=cold， x4=desk， x5=knife， x6=by。 R的关系图及关系矩阵 最大相容类：对于前三个相容类，都能加进新的元素组成新的相容类，而后两个相容类，加入任一新元素，就不再组成相容类，称为最大相容类。 定义3-11.2 设r是集合A上的相容关系，若C?A，如果对于C中任意两个元素a1,a2有a1ra2，则称C是由相容关系r产生的相容类。 例如上例的相容关系