离散数学(第14讲)(免费阅读).pptVIP

计算机学院 计算机科学与工程学院 冯伟森 Email：fws365@scu.edu.cn * * 计算机学院 * 主要内容 1、偏序关系 1）偏序集的哈斯图 2）偏序集中的特殊元素 2、全序集与良序集 1）全序关系 2）良序关系 * 计算机学院 * §5.2 偏序关系 偏序关系是集合上的自反的、可传递、反对称关系,它提供比较集合中元素的工具;也提供了事物之间的顺序关系。 定义5.4 设R是集合A上的自反的、反对称的、可传递的关系，则称R是A上的偏序关系(记为“ ”,读作“小于等于”)。序偶A，R称为偏序集。 容易证明：偏序 的逆关系 也是一个偏序，我们用“ ”表示，读作“大于等于”。 * 计算机学院 * 例5-2.1 集合A的幂集2A上定义的“?”是偏序关系。2A,?是偏序集。 实数集合R上定义的“≤”是偏序关系，R,≤是偏序集。 大于零的自然数集合N＋上定义的“整除”关系“|”也是一个偏序关系,N＋,|是偏序集。 ALGOL或PL/I等都是块结构语言，设： B＝{b1,b2,b3,…,bn} 是这种语言的一个程序中的块的集合。对所有i和j，定义关系“ ”如下： bi bj当且仅当bi被bj所包含。 则“ ”也是一个偏序关系,B, 是偏序集。 设A＝{2,3,6,12,24,36},“|”是A上的整除关系，画出其一般的关系图。 * 计算机学院 * 关系图 2 3 6 12 36 24 * 计算机学院 * 偏序集的哈斯图 用小圆圈或点表示A中的元素，省掉关系图中所有的环。 (因自反性) 对任意x,y∈A，若x y，则将x画在y的下方，可去掉关系图中所有边的箭头。 (因反对称性) 去掉有向边，即当（i，j）和（j，k）都是有向边时，去掉有向边（i，k）。 (因传递性) 按1),2),3)所作成的图称为哈斯图(Hasse图)。 * 计算机学院 * 例5-2.2 设A＝{2,3,6,12,24,36},“|”是A上的整除关系，画出其一般的关系图和哈斯图。 关系图 哈斯图 2 3 6 12 36 24 2 3 6 12 36 24 * 计算机学院 * 偏序关系R的Hasse图是由R的一个真子集cover(R)的关系图构成的。这个cover(R)又称为盖住关系，可以用符号表示为 Cover(R)={(x,y)∈R∣(?t∈A)[(t≠x∧t≠y) →((x,t)?R∧(t,y)?R)]} 求出了R的cover(R)，作Hasse图就容易了。 例5-2.4 * 计算机学院 * 作出下面偏序集对应的Hasse图：2{a,b,c} ,? 偏序关系对应的盖住关系是： Cover(?)={(?,{a}), (?,{b}),(?,{c}), ({a},{a,b}), ({a},{a,c}), ({b},{a,b}), ({b},{b,c}), ({c},{a,c}), ({c},{b,c}), ({a,b},{a,b,c}), ({a,c},{a,b,c}), ({b,c},{a,b,c})} * 计算机学院 * 画出相应的Hasse图 ? * 计算机学院 * 可比较的 定义5.5 设A, 是一个偏序集，对任意x,y?A，如果x y或y x，则称x与y是可比较的。否则，称x与y是不可比较的。 例5-2.3 1）集合A={a,b,c}，偏序集2A,?中，{a}与{a,b}是可比的，{a}与{b,c}不是可比的。 偏序集R,≤中，对任意x,y∈A，x与y都是可比的。 偏序集Z,≤中，对任意x,y∈A，x与y都是可比的。 偏序集N,|中，2与3不是可比的；2与6是可比的；2与8是可比的。 * 计算机学院 * 全序关系 定义5.6设A, 是一个偏序关系，若对任意x,y∈A， x与y都是可比的，则称关系“ ”为A上的全序关系。称A, 为全序集。 定义5.7设A, 是一个偏序集， 。如果B, 是一个全序子集，则称B为A中的一条链。链中元素数目减1称为该链的长度。 * 计算机学院 * 例5-3.1 集合A＝{a,b,c}上定义的关系 R＝{a,a,b,b,c,c,a,b,b,c,a,c} 是一个全序关系，A, 的哈斯图如右图。 实数集合R上定义的“≤”是全序关系，R,≤是全序集。 集合A＝{a}的幂集2A上定义的“?”是全序关系，2A,?是全序集。若|A|≥２，则2A,?不是全序集。 a b c * 计算机学院 * 偏序集中的特殊元素 定义5.8 设A, 是偏序集，a是A的一个元素。 若对任意b∈A,都有b a,则称a为A中的最大元 。 若对任意b∈