《aolm-离散数学》PPT课件.ppt

一种重要的关系序关系。 全序关系 偏序关系 序关系: 良序关系 拟序关系，,4.5 偏序关系,定义4.26 设 R 是给定集合 X 上的一个二元关系，若它满足自反性，反对称性和传递性，则称 R 是 X 上的偏序关系。偏序关系一般用符号 “” 表示。序偶 X, 称为偏序集（或半序集）。 (有的资料把反对称性也作为拟序关系定义的一个条件。定理表明，这是不必要的。) 对偏序集 X, 来说，若 x,yX 且 xy，就说 “y 在 x 的后面”（或 “x 小于或等于 y” ）。,定理4.14 设 R 是集合 X 上的一个二元关系，若 R 是一个偏序关系，则其逆关系 R1 也是一个偏序关系。 证明：因为 R 是一个偏序关系， 则它具有自反性，反对称性和传递性， 容易证明 R1 也具有自反性，反对称性和传递性。 故 R1 也是一个偏序关系。 若 R 用 表示，则 R1 用 表示，这意味着若 X,是偏序集，则 X, 也是一个偏序集，称 X, 为 X, 的对偶，显然 X, 也是 X, 的对偶。,【例4.24】集合 A 的幂集 (A) 上的 “” 关系是自反的、非对称的、传递的。所以它是一个偏序。 【例4.25】整数集合上的 “整除” 关系也是偏序关系。 在偏序集中，任何两个元素 x 和 y 并非都有 xy 或 yx。若任何两个元素 x 和 y 要么有 xy 要么有 yx，则称 x 和 y 是可比的，否则是不可比的。,定义4.27 在偏序集 X,中，如果 x,yX，xy, 但 xy，并且没有其他元素 zX 且满足 xz, zy，那么称元素 y 盖住元素 x。记 COVX x,y | x, yX，y 盖住 x 【例4.26】集合 X 2, 3, 6, 8 上的整除关系 R 2,2, 3,3, 6,6, 8,8, 2,6, 2,8, 3,6 ， 显然，该关系是偏序。根据定义4.28我们很容易求出 COVX 2,6, 2,8, 3,6 。,对于偏序集 X,，它的盖住关系是唯一的，所以可 以利用盖住的性质画出偏序集合图（又称“哈斯图”），其作图 规则为： (1) 用小圆圈代表元素； (2) 若 xy 且 xy，则将代表 y 的小圆圈画在代表 x 的小圆圈之上； (3) 若 x,yCOVX，则在 x 与 y 之间用直线连接。 【例4.27】例 4.26 的偏序 R 的哈斯图为如下图所示。,定义4.28 设 X, 是偏序集，若对于任意的 x, yX 都有 xy 或 yx，则称 是 X 上的全序关系，也可称为 “简单序” 或 “线性序”。X,称为全序集或链。 【例4.28】实数集合上的 “小于或等于” 关系就是一个全序关系，R, 是一个全序集。 定义4.29 设 R 是集合 X 上的一个二元关系，若 R 是反自反的和传递的，则称 R 是集合 X 上的拟序关系，或简称拟序，并记作，序偶 X, 称为拟序集。 【例4.29】实数集合上的 “小于” 关系是拟序关系。,【例4.30】令实数集 X 上的关系是通常的“大于或等于”关系。 设 PXX 且 P 上的全序关系 S 定义为： 对于任二序偶 x1,y1, x2,y2P， x1,y1Sx2,y2 (x1x2)(x1x2)(y1y2) 若 x1,y1 x2,y2， 则必有x2,y2Sx1,y1， 使得 S 是 P 上的全序集。这种关系叫词典编序。 下面是 P 中具有 S 关系的一些序偶的例子： 2,2S2,1，3,1S1,5 2,2S2,2，3,2S1,1,现在来推广这个概念，设 R 是集合 X 上的全序关系，且令 P XX2Xn (n1, 2, 3, ) 可假定 n 为某个固定值，长度为 p 的串可看成 p 元组。令 1, 2, , p与1, 2, , q 是 P 中任意两个元素且 pq。现在，如下列条件中的任 一个成立： （1）1, 2, , p1, 2, , q； （2）11 而在 X 中有1R1； （3）ii，i1, 2, , k (kp) 且 k1k1 而在 X 中k1Rk1，则 1, 2, , pS1, 2, , q。 如这些条件中没有任何一个被满足，则 1, 2, , pS1, 2, , q。,作为一般的词典编序的特殊情形，考虑英文字母表 Xa, b, c, , y, z。 令 R 是 X 上的一个全序关系，其中 abyz， 且 PX1X2X3，于是 P 是由 X 中三个或少于三个字母的 “词” 所组成。令 S 表示上面所描述的 P 上的词典编序，则有： me S met （条件）； bet S met （条件）； beg S bet （条件）； get S go （依最后规则，此时若比较 go 与 get， 则 3 个条件均不满足）。 在英文词典中，词出现的顺序是词典编序的一个熟悉例 子，习惯上常用例如 “按词典编序小于或等于” 或 “按词典编序 大于” 等名称来代替使用 S 表示词典顺序。,定义4.30 设 X,是偏序集，若 X 的子集 P 中任何两个元素之间都是不可比的，则称 P 是一条反链。 定理4.15 设X,是偏序集，若 X 中最长链的长度是 n，那么 P 中的元素能划分成 n 条不相交的反链。 证明：对链的长度用数学归纳法 归纳基础：对 n1，P 中任何两个元素都没有关 系，显然，P 是一条反链。 归纳步骤：设最长链的长度为 n1 时定理成立。 设 P 的最长链长度为 n，P 中每一条长度为 n 的链中，必有一个最小元素，P 中所有长度为 n 的链的最小元素，构成一个集合，记为 M。,显然 M 是一条非空的反链。考虑集合 PM，可知 PM,是偏序集。 因为 PM 中不存在长度为 n 的链，故它的最长链长度最多为 n1。 但是，若 PM 中的最大链长度小于 n1，那么，M 中必有两个或两个以上元素在同一条链上，这是不可能的。 因此，按归纳假设，PM 可以分成 n1 条互不相交的反链。 由于 M 是一条反链，故 P 可分成 n 条互不相交的反链。,定义4.31 设X,是偏序集，若存在这样的元素xX，使得对于任意的 yX 都有 xy，则称 x 为集合 X 上关系 的最小元。若存在这样的元素 xX，使得对于任意的 yX 都有 yx，则称 x 为集合 X 上关系 的最大元。若 X 中没有 yX 使得 yx 且 yx，则称 x 为集合 X 上关系 的极小元，若 X 中没有 yX 使得 yx 且 yx，则称 x 为集合 X 上关系 的极大元。,【例4.31】设集合 A 的幂集上的包含关系，试对 (1) Aa (2) Aa, b (3) Aa, b, c 分别画出偏序集 (A), ) 的哈斯图及其最小元、最 大元、极小元和极大元。 解：它们的哈斯图分别对应于图(a)、(b)、(c)。,b,a, b,a,c,a,a,b,a, b,b,c,a, c,a, b,c,(1) 最小元、极小元都为，最大元、极大元都为a； (2) 最小元、极小元都为，最大元、极大元都为a, b； (3) 最小元、极小元都为，最大元、极大元都为a, b, c。,定义4.32 设 X, 是偏序集，又设 AX。对于元素xX，若对所有的 aA 都有 ax，则称 x 是 A 的上界。同样，对于元素 xX，若对所有的 aA 都有 xa，则称 x 是 A 的下界。 定义4.33 设 X, 是偏序集，又设 AX。若元素 xX 是 X 的上界且对于 A 的任一个上界 y 都有 xy，则称元素 x 是集合 A 的最小上界或上确界，通常记为 sup(A)；同样，若元素 xX 是 X 的下界且对于A的任一个下界 y 都有 yx，则称元素 x 是集合 A 的最大下界或下确界，通常记为 inf(A)。,对于一个偏序集 X,，知道它的对偶 X, 也是一个偏序集。在 X 中关于偏序 的最小元是在 X 中关于偏序 的最大元；反之亦真。同样，极大元和极小元、上确界和下确界也被交换。 定义4.34 设 X, 是偏序集，若 X 的任一个非空子集都有最小元，则称 X, 是良序集， 是良序关系。,定理4.16 每一个有限全序集，一定是良序集。 证明：设 Xx1, x2, , xn，令 X, 是全序集， 若假设 X, 不是良序集合， 那么必存在 X 的一个非空子集 A 且在其中不存在最 小元素，由于 A 是一个有限集合， 故一定可以找出两个元素 x 和 y 是不可比的， 由于 X, 是全序集且 x,yX，所以 x 与 y 必有关系， 这与根据假设所得出的结论相矛盾， 故 X, 必定是良序集合。,定理4.17 每一个良序集，一定是全序集。 证明：设 X, 是良序集。对于任意的 x,yX， 则 x,y X， 故 x,y 必有最小元， 故必有 xy 或 yx 成立。 X 的任意两个元素均可比较， 故 X, 是全序集。,定理4.18 设 X, 是偏序集，当且仅当其满足： (1) 是 X 上的全序； (2) X 的每个非空子集都有最小元。 那么，X, 是良序集。 证明：设 X, 是良序集，对于任意的 x,yX，x,y都有最小元。 若 minx,yx，则 xy；若 minx,yy，则 yx； 所以 是 X 上的全序关