2.6半序[偏序]关系.pptVIP

;定义1 设R为非空集合A上的关系。如果R是自反的、反对称的和传递的，则称 R 为 A上的半序(偏序)关系，记为 ? 。 对一个偏序关系 ? ，如果x, y? ? ，则记为 x ? y。 注： 1. 集合A上的恒等关系IA是A上的偏序关系，但空关系和全 域关系EA 一般不是A上的偏序关系。 2. 实数域上的小于等于关系（大于等于关系），自然数域上 的整除关系，集合的包含关系等都是偏序关系。;注：在具有偏序关系的集合A中任二元素 x 和 y 之间必有下列四 种情形之一： x ? y ，y ? x ，x=y ，x 与 y 不可比。 例 设A={1, 2, 3} ? 是A上的整除关系，则：1 ? 2, 1 ? 3, 1＝1, 2＝2, 3＝3， 2 和 3 不可比； (2) ? 是 A 上的大于等于关系，则: 2 ? 1, 3 ? 1, 3 ? 2, 1＝1, 2＝2，3＝3。;定义3 设R为非空集合A上的偏序关系，如果?x, y?A, x 与 y 都是可比的, 则称R为A上的全序关系。 例如 大于等于关系（小于等于关系）是全序集，但整除关系一般不是全序集。 定义4 带有某种指定的偏序关系 ? 的集合A称为偏序集，记为A, ? . 例如 整数集Z和数的小于等于关系≤构成偏序集 Z, ? ; 集合A的幂集P(A)和集合的包含关系? 构成偏序集P(A), ?. 定义5 设 A, ? 为偏序集，?x, y ? A, 如果 x ? y且不存在 z ?A, 使得x ? z ? y, 则称 y 覆盖 x。 例如 A={1, 2, 4, 6}上的整除关系，有2覆盖1，4和6都覆盖2，但4不覆盖1,6不覆盖4。;;;定义6 设A, ? 为偏序集， B ?A. 存在y?B, 使得 (1)??? ?x(x?B→y?x) 成立，则称 y 是B的最小元； (2)??? ?x(x?B→x?y) 成立，则称 y 是B的最大元； (3)??? ?x(x?B∧x?y→x=y) 成立，则称 y 是B的极小元； (4)??? ?x(x?B∧y?x→x=y)成立，则称 y 是B的极大元； 注： 极大 (极小) 元未必是最大 (最小) 元。极大 (极小) 元未必与B中任 何元素都可比； (2) 对有限集B，极大 (极小)元一定存在，但最大(最小)元不一定存在; (3) 最大 (最小) 元如果存在，必定是唯一的; 而极大 (极小) 元一般不唯一。但如果B中只有一个极大 (极小) 元, 则它一定是B的最大 (最小) 元。;解：??大元：a, f, h; 极小元: a,b,c,g; 无最大元和最小元。;定义7 设A, ? 为偏序集，B?A. ;例 考虑下图中的偏序集.令B = { b, c, d }, 试讨论B的上(下)界，最大下界，最小上界等。 ; ; ;