离散数学(第5章)陈瑜.ppt

计算机科学与工程学院 陈瑜 Email：chenyu.inbox@ * 等价类 例5.4 例5.4 例5.4 例5.4 例5.4 等价类的性质 等价类的性质 等价类的性质 等价类的性质 等价类的性质 集合的划分 证明：（定理5.2） 证明：（定理5.2） 证明：（定理5.2） 证明：（定理5.2） 证明：（定理5.2） 证明：（定理5.2） §5.2 次(偏)序关系 §5.2 次(偏)序关系 §5.2 次(偏)序关系 例5.5 例5.5 例5.5 偏序集的哈斯图 偏序集的哈斯图 偏序集的哈斯图 偏序集的哈斯图 偏序集的哈斯图 例5.6 ★ 例5.7★ 例5.28 例5.28 例5.28 例5.28 例5.29： 字典次序（自学） 例5.29： 字典次序 ②.若存在最大的k且k≤min(n,m)，使xi＝yi(i＝1,2,3,…,k)，而xk+1≠yk+1，若xk+1≤yk+1，则xLy；若yk+1≤xk+1，则yLx； ③.若存在最大的k且k＝min(n,m)，使xi＝yi(i＝1,2,3,...,k),此时,若n≤m,则xLy；若m≤n,则yLx 显然，L是一个偏序关系，且也是一个全序关系。 2) 如英语词典和汉语词典都是按字典次序排列的。 ②.若存在最大的k且k≤min(n,m)，使xi＝yi(i＝1,2,3,…,k)，而xk+1≠yk+1，若xk+1≤yk+1，则xLy；若yk+1≤xk+1，则yLx； ③.若存在最大的k且k＝min(n,m)，使xi＝yi(i＝1,2,3,...,k),此时,若n≤m,则xLy；若m≤n,则yLx 显然，L是一个偏序关系，且也是一个全序关系。 2) 如英语词典和汉语词典都是按字典次序排列的。 ②.若存在最大的k且k≤min(n,m)，使xi＝yi(i＝1,2,3,…,k)，而xk+1≠yk+1，若xk+1≤yk+1，则xLy；若yk+1≤xk+1，则yLx； ③.若存在最大的k且k＝min(n,m)，使xi＝yi(i＝1,2,3,...,k),此时,若n≤m,则xLy；若m≤n,则yLx 显然，L是一个偏序关系，且也是一个全序关系。 2) 如英语词典和汉语词典都是按字典次序排列的。 ②.若存在最大的k且k≤min(n,m)，使xi＝yi(i＝1,2,3,…,k)，而xk+1≠yk+1，若xk+1≤yk+1，则xLy；若yk+1≤xk+1，则yLx； ③.若存在最大的k且k＝min(n,m)，使xi＝yi(i＝1,2,3,...,k),此时,若n≤m,则xLy；若m≤n,则yLx 显然，L是一个偏序关系，且也是一个全序关系。 2) 如英语词典和汉语词典都是按字典次序排列的。 良序关系 良序关系 良序关系 在例5.28中，（1）中的?是良序关系，（2）中的?不是良序。 (如（-∞，0）?R ，但没有最小元) 一般地，任何有限的全序集的每一个非空的子集一定有最小元，所以，有限全序集一定是良序集。对于无穷的全序集，则并非如此。如全序集N, ?是良序集，但全序集Z, ?和(0,1), ?都不是良序集，其中(0,1)为0到1的开区间。 在例5.28中，（1）中的?是良序关系，（2）中的?不是良序。 (如（-∞，0）?R ，但没有最小元) 一般地，任何有限的全序集的每一个非空的子集一定有最小元，所以，有限全序集一定是良序集。对于无穷的全序集，则并非如此。如全序集N, ?是良序集，但全序集Z, ?和(0,1), ?都不是良序集，其中(0,1)为0到1的开区间。 有限偏序集到全(良)序集的转化 在实际问题中,如程序控制流,数据分析流中,有时需要把一个不是全序集的有限偏序集合转化全序集,或良序集,这就涉及到由一种偏序关系转变成另一种偏序关系的问题。 定义5.11 设 ? 、?′是集合A上的两个偏序关系。如果对?a,b ? A,当a?b时必导致a?′b,则称关系?, ?′是可比较的 。 有限偏序集到全(良)序集的转化 在实际问题中,如程序控制流,数据分析流中,有时需要把一个不是全序集的有限偏序集合转化全序集,或良序集,这就涉及到由一种偏序关系转变成另一种偏序关系的问题。 定义5.11 设 ? 、?′是集合A上的两个偏序关系。如果对?a,b ? A,当a?b时必导致a?′b,则称关系?, ?′是可比较的 。 例：‘整除’和‘小于等于’是自然数集上的两个偏序关系,而且‘︱’和‘≤’是可比较的, ∵对任何a,b ?N,a︱b时也有a≤b。 注意:例中的‘︱’是偏序而非全序,‘≤’却是一个全序。现在问: 对于任何一个有限偏序集A, ? ,能否在A上定义一个全序?