九、序关系.pptVIP

一、 偏序关系 例: 设集合A＝{a,b,c},A上的关系 (1)每个结点均有自回路,故R有自反性。 (2)每两点间最多有一条有向弧,故R有反对称性。 (3)任两点a，c，若有a到c的有向路径,则有a到c的有向弧，故R有传递性。 故R是偏序关系。 二、 元素y盖住元素x 三、 哈斯图（偏序集合图） 四、链、反链 定义 设A, ≤ 是一个偏序集合，在A的一个子集中，如果每两个元素都是有关系的，则称这个子集为链。在A的一个子集中，如果每两个不同的元素都是无关的，则称这个子集为反链。 五、 全序关系（线序关系） 六、极大元、极小元与最大元、最小元 定义1 设A，≤是一个偏序集合，且B是A的子集，对于b?B，如果B中没有任何元素x，满足b≠x且b≤x，则称b为B的极大元；同理，如果b?B，且B中不存在元素x，使b≠x且 x≤b，则称b为B的极小元。 定义2 设A，≤是一个偏序集合，且B是A的子集，则(a)若有某个元素b?B，对B中任何元素x，有x≤b，则称b为B,≤的最大元；(b)若有某个元素b?B，对B中任何元素x，有b≤x ，则称b为B,≤的最小元。 例： 考虑偏序集P({a,b})，?，其哈斯图如下： 例：考虑偏序集｛1，2，3，4，5，6｝,整除 ， 其哈斯图如下： (3)B={4} 最大元： 最小元： 定理1 令A，≤为偏序集，且B?A，若B有最大(最小)元，则必唯一。 证明：假设a和b两者都是B的最大元，则a≤b 和 b≤a，从“≤”的反对称性，得到a＝b。当a，b都是B的最小元时，证明类似。 定义2 设A, ≤ 为一偏序集，B是A的子集，则 (1)若a为B的任一上界且对B的任一上界y，均有a≤y，则称a为B的最小上界(上确界)； (2)若a为B的任一下界且对B的任一下界z，均有z≤a，则称a为B的最大下界(下确界) ； 八、良序 定义 任一偏序集合，假如它的每一个非空子集存在最小元素，则这种偏序集称为良序的。 九、元素比较表 * * 定义1 如果集合A上的关系R满足自反性、反对称性和传递性，则称R是A上的一个偏序关系。 此时：把关系R记作“≤”,序偶A,≤称为偏序集。如果a,b∈≤,则记作a≤b 。 注意：定义中的“≤”不是指普通的实数上的“小于等于”关系,而是偏序关系 。 3-12 序关系 例 证明实数集R上的小于等于“≤”关系是偏序关系。 证明见书P140 R＝{a,a,a,b,a,c,b,b,b,c,c,c}, 从关系图来验证R是偏序关系。 a b c 定义 在偏序集合A，≤中，如果 x,y ∈A，x ≤y，x≠y，且没有其它元素 z 满足x≤z ，z≤y，则称元素y盖住x，并且记：COV A ={ x,y | x,y ∈A， y盖住x } 例： 设A是正整数m=6的因子的集合，并设≤为整除关系，求：COV A 解：A={1, 2, 3, 6} ≤={ 1,1,1,2,1,3,1,6,2,2,2,6,3,3, 3,6,6,6} COV A = { 1,2 , 1,3 , 2,6 , 3,6} 用小圆圈代表元素； 如果x ≤y且x ≠ y，则将代表y的小圆圈画在代表x的小圆圈之上； 如果y盖住x ，则在x与y之间用直线连接。 1 3 2 6 画出上例中A={1,2,3,6}上“整除”关系的哈斯图： 练习：作集合A={2,3,6,8}上整除关系的哈斯图。 作图规则： 2 3 6 8 链： 反链： 约定：单个元素组成的子集，既是链也是反链。 {1,2,6}、{1,3,6}、{1,6}等 {2,3} 等 1 3 2 6 定义 在偏序集A, ≤ 中，如果A是一个链，则称A, ≤ 为全序集合或线序集合。 “≤”称为全序关系或线序关系。 例： 给定P ＝｛ ? , {a}，{a,b}，{a,b,c}｝上的包含关系，证明 P， ? 是个全序集合。 证明：∵ ? ? {a} ?{a,b} ?{a,b,c} ∴P中任意两个元素都有包含关系， ∴ P， ? 是个全序集合。 例：设A＝｛2,3,7,14,21｝，其偏序关系R为“整除”，求B＝｛2,7,14,21｝的极大元与极小元。 解：A，R的哈斯图为： 2 3 7 14 21 故B的极小元为：2，7 B的极大元为：14，21 极大(小)元不唯一 若B＝{{a}, ?} ? {a} {b} {a,b} 最大元： 最小元： {a} ? 若B＝{{a}, {b}} 最大元： 最小元： 无 无 1 2 3 4 5 6 (1)B={1,2,3,6} 最大元： 最小元： 6