半序偏序關(guān)系

1、第六節(jié) 半序（偏序）關(guān)系1定義1 設(shè)R為非空集合A上的關(guān)系。如果R是自反的、反對稱的和傳遞的，則稱 R 為 A上的半序(偏序)關(guān)系，記為 。 對一個偏序關(guān)系 ，如果 ，則記為 x y。注： 1. 集合A上的恒等關(guān)系IA是A上的偏序關(guān)系，但空關(guān)系和全 域關(guān)系EA 一般不是A上的偏序關(guān)系。 2. 實數(shù)域上的小于等于關(guān)系（大于等于關(guān)系），自然數(shù)域上 的整除關(guān)系，集合的包含關(guān)系等都是偏序關(guān)系。一.偏序關(guān)系與偏序集2注：在具有偏序關(guān)系的集合A中任二元素 x 和 y 之間必有下列四 種情形之一： x y ，y x ，x=y ，x 與 y 不可比。例 設(shè)A=1, 2, 3 是A上的整除關(guān)系，則：1 2, 1

2、 3, 11, 22, 33， 2 和 3 不可比；(2) 是 A 上的大于等于關(guān)系，則: 2 1, 3 1, 3 2, 11, 22，33。定義2 設(shè)R為非空集合A上的偏序關(guān)系，定義 (1) x, yA, x y當且僅當 x y且 xy (2) x, y A, x 與 y 可比當且僅當 x y 或 y x3定義3 設(shè)R為非空集合A上的偏序關(guān)系，如果x, yA, x 與 y 都是可比的, 則稱R為A上的全序關(guān)系。 例如 大于等于關(guān)系（小于等于關(guān)系）是全序集，但整除關(guān)系一般不是全序集。定義4 帶有某種指定的偏序關(guān)系 的集合A稱為偏序集，記為.例如 整數(shù)集Z和數(shù)的小于等于關(guān)系構(gòu)成偏序集 ; 集合A

3、的冪集P(A)和集合的包含關(guān)系 構(gòu)成偏序集.定義5 設(shè) 為偏序集，x, y A, 如果 x y且不存在 z A, 使得x z y, 則稱 y 覆蓋 x。 例如 A=1, 2, 4, 6上的整除關(guān)系，有2覆蓋1，4和6都覆蓋2，但4不覆蓋1,6不覆蓋4。4 利用偏序關(guān)系的自反性、反對稱性和傳遞性可簡化偏序關(guān)系的關(guān)系圖，得到偏序集的哈斯圖。 設(shè)有偏序集, 其哈斯圖的畫法如下：(1) 以 A 的元素作為頂點，適當排列各頂點的順序, 使得對 x, y A， 若x y, 則將 x 畫在 y 的下方。(2) 對A中兩個不同元素 x 和 y, 如果 y 覆蓋x, 則用一條線段連接 x 和 y.例 畫出偏序集

4、1, 2, 3, , 9, R整除 和 的哈斯圖. 二. 哈斯圖解：它們的哈斯圖分別為圖A、圖B表示如下： 847236951圖Aa,ba,b,cabb,cca,c圖B5例 已知偏序集的哈斯圖如下：求集合A和關(guān)系R的表達式。aedfhgbc解: A=a, b, c, d, e, f, g, h, R=, , , , , , , , IA.6定義6 設(shè) 為偏序集， B A. 存在yB, 使得(1) x(xByx) 成立，則稱 y 是B的最小元；(2) x(xBxy) 成立，則稱 y 是B的最大元；(3) x(xBxyx=y) 成立，則稱 y 是B的極小元；(4) x(xByxx=y)成立，則稱

5、y 是B的極大元；注：極大 (極小) 元未必是最大 (最小) 元。極大 (極小) 元未必與B中任 何元素都可比；(2) 對有限集B，極大 (極小)元一定存在，但最大(最小)元不一定存在;(3) 最大 (最小) 元如果存在，必定是唯一的; 而極大 (極小) 元一般不唯一。但如果B中只有一個極大 (極小) 元, 則它一定是B的最大 (最小) 元。三. 偏序集中的特殊元素7解：極大元：a, f, h; 極小元: a,b,c,g; 無最大元和最小元。例 求上例中A的極大元、極小元、最大元、最小元，8定義7 設(shè)為偏序集，BA. (1)若存在yA, 使得x(xBxy)成立, 則稱y為B的上界;(2)若存在

6、yA, 使得x(xByx)成立，則稱y為B的下界； (3) 令 Cy|y為B的上界，則稱C的最小元為B的最小上界或上確界；(4) 令 Dy|y為B的下界，則稱D的最大元為B的最大下界或下確界. 注：B的最大元(最小元)必定是B的上界(下界)，也是B的上確界(下確界)。2. B的上界和上確界都未必是B的最大元，因它們可能不在B中。同理，下界和下確也未必是B的最小元。3. B的上界、上確界、下界、下確界都可能不存在。但如果上確界(下確界)存在，則它是唯一的。9例 考慮下圖中的偏序集.令B = b, c, d , 試討論B的上(下)界，最大下界，最小上界等。解析：(1)則B的下界和最大下界 都不存在;(2)上界有d和f, 最小上界為d.10例 設(shè)A=2,3,4,6,7,8,12,36,60, 在半序集(A,|)上，半序關(guān)系|是整除關(guān)系。取 B1=7,8, B2=8,12, B3=2,3, B4=2,4,12，則Bi(i=1,2,3,4)集合上的上(下)界,上(下)確界，極大(下)元 ？作出哈斯圖 ！