东北师范大学《离散数学》课件-第六讲.pdfVIP

离散数学 第六讲 偏序集 Partially Ordered Sets 偏序集 • 例如： –集合之间的包含关系 –实数间的小于等于关系 –实数间的大于等于关系 –整数间的整除关系 2 偏序集 • 假设R 是集合A 上的关系，如果R是自反 的、反对称的和传递的，则称R 是A 上的 一个偏序（partial order）或半序（semi order）关系，一般简记作“”或“”。 • 集合A 和偏序关系R 构成的有序二元组 (A , R)称作偏序集（partially ordered set ， 简记为poset）或半序集（semi ordered set）。 3 偏序集 • 例 1 –A = {1, 2, 3, 4, 5, 6} –D A A 6 1 –aDb 当且仅当a|b 5 2 4 3 4 偏序集 • 例2 – P ({a, b})上的 {a,b} 集合包含关系 {a} {b}  5 偏序集 • 假设(A , R) 为偏序集，a, b A ， 如果有ab 或ba 成立，则称 a, b 是可比的（comparable）， 否则称a, b 是不可比的 （incomparable）。 6 偏序集 • 例3 4 –A = { 1, 2, 3, 4 } –R = { (1, 1), (1, 2), 3 (1, 3), (1, 4), (2,2 ), (2, 3), (2, 4), (3, 3), 2 (3, 4), (4, 4) } 1 7 偏序集 • 假设(A , R) 为偏序集，如果对于任 意a, b A ，a, b 都是可比的，则 –称R 为线序（linear order）或全序 （total order）， –(A , R) 称作线序集（linearly ordered set）或全序集（totally ordered set）， 也称为链（chain）。 8 偏序集 • 设R 是集合A 上的偏序，并且 R1 是R 的逆关系。 9 偏序集 如果R 和S 那么 具有性质： R R-1 R ∩S R ∪S S ◦R 自反性 非自反性 √ √ √ √