离散数学课件-第4章-7.ppt

1,离散数学Discrete Mathematics,汪荣贵 教授合肥工业大学软件学院专用课件2010.03,学习内容,4.1集合的基本知识4.2 序偶与笛卡尔积4.3 关系及其性质4.4 n元关系及其应用4.5 关系的闭包4.6 等价关系4.7 偏序,偏序,一、偏序 定义1：集合S上的关系R，如果它是自反的、反对称的 和传递的，就称为偏序 集合S与偏序R一起叫做偏序集，记作（S,R）. 例如数值的≤、≥关系和集合的都是偏序关系example 1】证明“大于或等于”关系（ ≥ ）是整数集合上的偏序 solution： 因为对所有整数a，有a ≥a， ≥是自反的 如果a ≥b且b ≥a，那么a=b，因此≥是反对称的 最后，因为a ≥b和b ≥c，所以≥是传递的从而≥是整数集合上的偏序且（Z, ≥ ）是偏序集example 2】整除关系“ | ”是正整数集合上的偏序，因为由前几节所述，它是自反的、反对称的和传递的我们看到（Z+, | ）是偏序集（Z+表示正整数集合）example 3】证明包含关系是集合S的幂集上的偏序。

Solution： 因为只要A是S的子集，就有A A, 是自反的 因为A B和B A推出A=B，因此它是反对称的 最后，因为A B和B C推出A  B, 是传递的因此，  是P(S)上的偏序，且（ P(S) ，  ）是偏序集在任意一个偏序集中记号a ≼ b表示(a，b)R.使用这个记号 是由于“小于或等于”关系是偏序关系的范例注意：符号 ≼ 表示任意偏序关系，并不仅仅是“小于或等于”关系 记号a

当集合中的每对元素都可比时，这个关系叫做全序定义3：如果(S, ≼ ) 是偏序集，且S的每对元素都是可比的，则S叫做全序集或线序集，且≼ 叫做全序或线序一个全序集也叫做链example 5】偏序集(Z, ≤)是全序集，因为只要a和b是整数，就有a ≤b或b ≤aexample 6】偏序集(Z+, | )不是全序集，因为它包含着不可比的元素，例如5和7.,定义4：对于偏序集(S, ≼ ) ，如果≼是全序，并且S的每 个非空子集都有一个最小元素，就称它为良序集For example， N是自然数集合，I是整数集合，≤是小于等于关系，就是良序集而不是良序集定理 所有良序集，一定是全序集Proof： 设为良序集,任取x, y ∈ A, 则{x, y} A, 它有最小元素该最小元素或是x,或是y 于是有x ≤ y或 y ≤ x，所以是全序集定理 有限的全序集，一定是良序集Proof： 设A={a1, a2, …，an}, 是全序集 假设它不是良序，必存在非空子集BA，B中无最小元素，因B是有限集，必存在x, y ∈ B,使得x与y之间不满足≤关系,与≤是全序矛盾。

∴是良序集example 7】正整数的有序对的集合Z+×Z+与≼构成良序集，对于(a1, a2)和(b1, b2),如果a1

二、字典顺序字典顺序是以字母表中的字母顺序为基础的这是从一个集合上的偏序构造一个集合上的串的序的特殊情况我们将说明这种构造在任一个偏序集上是怎么做的首先，我们将说明怎样在两个偏序集(A1, ≼1)和(A2, ≼2)的笛卡尔积上构造一个偏序在A1×A2上的字典顺序定义如下：如果第一个对的第一个元素（在A1中）小于第二个对的第一个元素，或者第一个元素相等，但是第一个对的第二个元素（在A2中）小于第二个对的第二个元素，那么第一个对小于第二个对换句话说，(a1, a2)小于(b1,b2),即(a1, a2) < (b1,b2)或者a1<1b1,或者a1=b1且a2<2b2. 把相等加到A1×A2上的序就得到偏序≼example 8】确定在偏序集（Z×Z，≼ ）中是否有(3, 5) < (4,8), (3,8)<(4,5) 和(4,9) <(4,11) ?这里的≼ 是从Z上通常的≤关系构造的字典顺序Solution： 因为3<4,故而(3, 5) < (4,8), 且(3,8)<(4,5) 因为(4,9)与(4,11) 的第一元素相同，但9<11,我们有(4,9) <(4,11) 。

下图明显地显示了Z+×Z+ 中比(3,4)小的有序对的集合可以在n个偏序集(A1, ≼1 ), (A2, ≼2 ), …, (An, ≼n ) 的笛卡尔积上定义字典顺序 如下定义A1×A2×…×An上的偏序 ≼ ：如果a10 是的a1=b1,…,ai=bi,且ai+1

换句话说，为确定两个不同串的序，较长的串被切到较短的串的长度t，即t=min(m,n) 然后使用St上的字典顺序比较每个船的前t为组成的t元组，如果对应于第一个串的t元组小于第二个串的t元组，或者这两个t元组相等，但是第二个串更长，那么第一个串小于第二个串example 10】 考虑小写英语字母串构成的集合使用在字母表中的字母序，可以构成在串的集合上的字典顺序 如果两个串第一次出现不同字母时，第一个串的字母先于第二个字母，或者如果第一个串和第二个串在所有的位都相同，但是第二个串有更多的字母，那么，第一个串小于第二个串这种排序和字典使用的排序相同例如 discreet < discrete因为这两个串在第7位首次出现字母，并且 e< t. discreet < discreetness因为这两个串前8个字母相同，但是第二个串更长此外 discrete < discretion,在有穷偏序集的有向图中有许多可以不必显示出来，因为他们是必须存在的 例如，考虑在集合{1，2，3，4}上的偏序{(a, b)| a ≤b}的有向图，参见图a因为这个关系是偏序，它是自反的并且有向图在所有的顶点都有环，因此，我们不必显示这些环，因为它们是必须出现的。

在图b中没有显示这些环由于一个偏序是传递的，我们不必显示那些由于传递性而必须出现的边例如，在图c中没有显示边(1,3),(1,4)和(2,4)，因为它们是必须出现的如果假设所有的边的方向是向上的，我们不必显示边的方向；图c没有显示方向三、哈塞图（ Hasse 图）,我们可以使用下面的过程表示一个有穷集上的偏序 从这个关系的有向图开始： (1)自反性：每个顶点都有自回路，省去 (2)反对称性：两个顶点间只可能有一个箭头从左→ 右，或从下→上的方向从小到大安置顶点，可省略箭头 (3)传递性：由于有(a,b)，(b,c)∈R 则(a,c) ∈R故只画(a,b)，(b,c)对应的边,省略边(a,c)完成以上步骤就得到一个包含着足够表示偏序信息的图，这个图叫作哈塞图,哈塞图（ Hasse 图）定义：设≼是Ａ上的一个偏序关系，如果a ≼ b ，则将ａ画在 ｂ下面，且不ｃ，使a≼c，c ≼ b，则ａ，ｂ间用直线连 接并符合简化的关系图的绘制，称这样得到关系图为 哈塞图（Hasse图）29,2017/5/28,【example 11】画出表示{1，2，3，4，6，8，12}上的偏序{(a,b)|a 整除b}的哈塞图。

Solution： 由这个偏序的有向图开始，如下图a所示移走所有的环，如下图b所示，然后删去所有由传递性导出的边这些边是(1,4),(1,6),(1,8),(1,12),(2,8),(3,12).排列所有的边使得方向向上，并且删除所有的箭头得到哈塞图结果如图c所示example 12】画出幂集P(S)上的偏序{(A, B) | A  B}的哈塞 图，其中S={a, b, c}.Solution : 关于这个偏序的哈塞图是由相关的有向图得到的，先删除所有的环和所有的由传递性产生的边，即(Φ, {a, b}), (Φ, {a, c}), (Φ, {b, c}), (Φ, {a, b, c}), ({ a }, {a, b, c}), ({ b} ,{a, b, c})和({c}, {a, b, c}). 最后，使所有的边方向向上并删除箭头得到哈塞图如下所示example】： Ａ＝｛１，２，３，４，５，６，７，８，９｝ Ｂ＝｛ａ，ｂ，ｃ｝ Ｒ1＝｛（ａ，ｂ）｜ ａ≤ｂ，ａ，ｂ∈Ａ｝ Ｒ2＝｛（ａ，ｂ）｜ ａ|ｂ，ａ，ｂ∈Ａ｝ Ｒ3＝｛(s1,s2)｜s1s2，s1，s2∈p(B)｝求R1, R2, R3 所表示关系的哈塞图。