基于偏序關系確定特殊元素的標記方法

李曉陽

（太原理工大學軟件學院，山西晉中 030600）

0.引言

依據偏序關系畫哈斯圖并求解特殊元素是離散數學課程考試中經常出現的一類問題，但是由于教材中的定義簡潔凝練，相似度高，同學們很容易混淆[1]。本文在不偏離教材定義的基礎上采用可視化的方法求解偏序關系中八大特殊元素。

1.相關概念

定義：設R 為非空集合A 上的關系。如果R 是自反的、反對稱的和傳遞的，則稱R 為A 上的偏序關系，記作≤。設≤為偏序關系，如果∈≤，則記作x≤y,讀作x“小于或等于”y。

定義：設為偏序集，B ?A，y∈A。

（1）若?x(x∈B →x≤y)成立，則稱y為B 的上界。

（2）若?x(x∈B →y≤x)成立，則稱y為B 的下界。

（3）令C={y|y為B 的上界}，則稱C 的最小元為B的最小上界或上確界。

（4）令D={y|y為B 的下界}，則稱D 的最大元為B的最小上界或上確界。

定義：設為偏序集，B ?A，y∈B。

（1）若?x(x∈B →x≤y)成立，則稱y為B 的最大元。

（2）若?x(x∈B →y≤x)成立，則稱y為B 的最小元。

（3）若?x(x∈B ∧y≤x→x=y)成立，則稱y為B的極大元。

（4）若?x(x∈B ∧x≤y→x=y)成立，則稱y為B的極小元[2]。

2.基于偏序關系確定特殊元素的標記方法

2.1 確定哈斯圖的標記方法

步驟一：在偏序關系二元表中標記相應的偏序關系。

步驟二：在偏序關系二元表中找行組中具有唯一標記的元素，該元素即為同一層元素。

步驟三：刪除上一步驟中元素的列，在剩余元素中的行組找唯一標記的元素，該元素即為下一層元素。依據兩層元素之間的偏序關系連線。

步驟四：重復步驟三。

2.2 確定八大特殊元的標記方法

子集B 上界確定方法：在集合B 中所有元素用不同的標志標記，每種標志逆流而上，并做出相同標志的標記，最終被集合B 中所有標志標記的元素即為上界。

子集B 下界確定方法：在集合B 中所有元素用不同的標志標記，每種標志順流而下，并做出相同標志的標記，最終被集合B 中所有標志標記的元素即為下界。

子集B 上確界（最小上界）確定方法：先由標記法確定子集B 上界，若位于最下層的上界元素存在且僅存在唯一一個，則該元素即為上確界。

子集B 下確界（最大下界）確定方法：先由標記法確定子集B 下界，若位于最上層的下界元素存在且僅存在唯一一個，則該元素即為下確界。

子集B 極大元確定方法：在集合B 中所有元素用不同的標志標記，然后每種標志在集合B 中逆流而上，并做出相同標志的標記，最終流到盡頭的元素即為極大元。

子集B2 最大元確定方法：若極大元被集合B 中所有標志標記，則該元素為最大元。

子集B 極小元確定方法：在集合B 中所有元素用不同的標志標記，然后每種標志在集合B 中順流而下，并做出相同標志的標記，最終流到盡頭的元素即為極小元。

子集B 最小元確定方法：若極小元被集合B 中所有標志標記，則該元素為最小元。

3.證明基于偏序關系確定特殊元素的標記方法

3.1 證明確定哈斯圖的標記方法

哈斯圖的標記方法采用遞歸的形式，先找出最上層元素，之后每找出一層的元素就與上一層元素之間依據偏序關系連線。

因為偏序關系具有自反性，在偏序關系二元表中每行至少有一個元素被標記（若被標記的元素唯一，即為自身元素），每行唯一被標記的元素說明該元素不與其他元素存在覆蓋關系，則該元素在最上層。

根據遞歸方法，每次找出的元素均不與剩下的元素之間存在覆蓋關系，則每次找出的元素唯一哈斯圖的同一層，每兩層元素之間依據偏序關系連線，最終哈斯圖迎刃而解。

3.2 證明確定八大特殊元的標記方法

由標記范圍確定原始定義中的y∈A 或y∈B。當y∈A 時，標記沿著整個哈斯圖進行；當y∈B 時，標記范圍僅限于子集中。

標記的方向確定原始定義中的x≤y或y≤x。當x≤y時，x對y有偏序關系，由覆蓋關系確定標記方向為順流而下；當y≤x時，y對x有偏序關系，由覆蓋關系確定標記方向為逆流而上。

最小元是子集中的最小元素，它與子集中的其他元素都可比。最大元是子集中的最大元素，它與子集中的其他元素都可比。“都可比”使用被子集中所有元素的標志標記來表示。

上確界與下確界中的“最大”與“最小”通過元素的上下層的關系來體現。

4.方法示例

例如，畫出偏序集的哈斯圖，找出A 的子集B 的極大元、極小元、最大元、最小元、上界、下界、上確界和下確界[3]。

A=P({a,b,c}),≤={|x∈P(A)∧y ∈P(A)∧x?y},B={?,{a},{b},{a,c}}

解法：集合A={?,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}。

R={,,,,,,,,,,,,,,,,,,,,<{a,b},{a,b}>,<{a,b},{a,b,c}>,<{b,c},{b,c}>,<{b,c},{a,b,c}>,<{a,c},{a,c}>,<{a,c},{a,b,c}>,<{a,b,c},{a,b,c}>}

步驟一：在偏序關系二元表中標記相應的偏序關系。偏序關系二元表執行步驟一如表1 所示。

步驟二：在偏序關系二元表中找行組中具有唯一標記的元素，集合{a,b,c}即為最上層元素。執行步驟二中確定元素結果如表2 所示，所畫哈斯圖（部分）如圖1 所示。圖1 確定哈斯圖的標記方法步驟二執行結果。

圖1 確定哈斯圖的標記方法步驟二執行結果

表2 偏序關系二元表執行步驟二結果

步驟三：刪除上一步驟中元素的列，在剩余元素中的行組找唯一標記的元素，該元素即為下一層元素。依據兩層元素之間的偏序關系連線。執行步驟三中確定元素結果如表3 所示，所畫哈斯圖（部分）如圖2 所示。

圖2 確定哈斯圖的標記方法步驟三執行結果

表3 偏序關系二元表執行步驟三結果

步驟四：刪除上一步驟中元素的列，在剩余元素中的行組找唯一標記的元素，該元素即為下一層元素。依據兩層元素之間的偏序關系連線。執行步驟四中確定元素結果如表4 所示，所畫哈斯圖（部分）如圖3 所示。

圖3 確定哈斯圖的標記方法步驟四執行結果

表4 偏序關系二元表執行步驟四結果

步驟五：刪除上一步驟中元素的列，在剩余元素中的行組找唯一標記的元素，該元素即為下一層元素。依據兩層元素之間的偏序關系連線。執行步驟五中確定元素結果如表5 所示，所畫哈斯圖（部分）如圖4 所示。

圖4 確定哈斯圖的標記方法步驟五執行結果

表5 偏序關系二元表執行步驟五結果

為使確定偏序關系八大特殊元的標記方法更清晰地表現，確定子集B 的標記方法分別如圖5 ～圖8 所示。

圖5 確定子集B上界和上確界的標記方法

圖6 確定子集B下界和下確界的標記方法

圖7 確定子集B極大元、最大元的標記方法

圖8 確定子集B極小元、最小元的標記方法

子集B 上界確定方法: 在集合B 中分別將元素{?}、{a}、{b}、{a,c}標記為●、▲、◆、★。然后每種標志沿哈斯圖逆流而上，并做出相同標志的標記，最終被集合B中所有標志標記的元素{a,b,c}即為上界。

子集B 上確界（最小上界）確定方法：位于最下層的上界元素存在且僅存在唯一一個，則{a,b,c}為上確界。

子集B 下界確定方法: 在集合B 中分別將元素{?}、{a}、{b}、{a,c}標記為●、▲、◆、★。然后每種標志沿哈斯圖順流而下，并做出相同標志的標記，最終被集合B中所有標志標記的元素{?}即為下界。

子集B 下確界（最大上界）確定方法：位于最上層的下界元素存在且僅存在唯一一個，則{?}為下確界。

子集B 極大元確定方法：在集合B 中分別將元素{?}、{a}、{b}、{a,c}標記為●、▲、◆、★。然后每種標志在集合B 中逆流而上，并做出相同標志的標記，最終流到盡頭的元素{a,c}和{b}即為極大元。

子集B 最大元確定方法：若極大元被集合B 中所有標志標記，則該元素為最大元。子集B 無最大元。

子集B 極小元確定方法: 在集合B 中分別將元素{?}、{a}、{b}、{a,c}標記為●、▲、◆、★。然后每種標志在集合B 中順流而下，并做出相同標志的標記，最終流到盡頭的元素{?}即為極小元。

子集B 最小元確定方法：若極小元被集合B 中所有標志標記，則該元素為最小元。子集B 最小元為{?}。

方法示例結果集如表6 所示。

表6 方法示例結果集

5.研究意義

基于哈斯圖確定偏序關系八大特殊元的標記方法可以將原依據定義的確定方法簡便化，在拓展到更大的集合與子集中更具有優勢。此外，在同學們學習《離散數學》課程中通過標記方法更能將定義可視化，有助于抽象化的理解。