基于偏序關(guān)系確定特殊元素的標(biāo)記方法

李曉陽

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

0.引言

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

1.相關(guān)概念

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

定義：設(shè)為偏序集，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的最小上界或上確界。

定義：設(shè)為偏序集，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.基于偏序關(guān)系確定特殊元素的標(biāo)記方法

2.1 確定哈斯圖的標(biāo)記方法

步驟一：在偏序關(guān)系二元表中標(biāo)記相應(yīng)的偏序關(guān)系。

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

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

步驟四：重復(fù)步驟三。

2.2 確定八大特殊元的標(biāo)記方法

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

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

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

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

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

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

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

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

3.證明基于偏序關(guān)系確定特殊元素的標(biāo)記方法

3.1 證明確定哈斯圖的標(biāo)記方法

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

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

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

3.2 證明確定八大特殊元的標(biāo)記方法

由標(biāo)記范圍確定原始定義中的y∈A 或y∈B。當(dāng)y∈A 時，標(biāo)記沿著整個哈斯圖進(jìn)行；當(dāng)y∈B 時，標(biāo)記范圍僅限于子集中。

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

最小元是子集中的最小元素，它與子集中的其他元素都可比。最大元是子集中的最大元素，它與子集中的其他元素都可比?！岸伎杀取笔褂帽蛔蛹兴性氐臉?biāo)志標(biāo)記來表示。

上確界與下確界中的“最大”與“最小”通過元素的上下層的關(guān)系來體現(xiàn)。

4.方法示例

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

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

解法：集合A={?,{a},,{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}>}

步驟一：在偏序關(guān)系二元表中標(biāo)記相應(yīng)的偏序關(guān)系。偏序關(guān)系二元表執(zhí)行步驟一如表1 所示。

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

圖1 確定哈斯圖的標(biāo)記方法步驟二執(zhí)行結(jié)果

表2 偏序關(guān)系二元表執(zhí)行步驟二結(jié)果

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

圖2 確定哈斯圖的標(biāo)記方法步驟三執(zhí)行結(jié)果

表3 偏序關(guān)系二元表執(zhí)行步驟三結(jié)果

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

圖3 確定哈斯圖的標(biāo)記方法步驟四執(zhí)行結(jié)果

表4 偏序關(guān)系二元表執(zhí)行步驟四結(jié)果

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

圖4 確定哈斯圖的標(biāo)記方法步驟五執(zhí)行結(jié)果

表5 偏序關(guān)系二元表執(zhí)行步驟五結(jié)果

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

圖5 確定子集B上界和上確界的標(biāo)記方法

圖6 確定子集B下界和下確界的標(biāo)記方法

圖7 確定子集B極大元、最大元的標(biāo)記方法

圖8 確定子集B極小元、最小元的標(biāo)記方法

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

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

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

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

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

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

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

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

方法示例結(jié)果集如表6 所示。

表6 方法示例結(jié)果集

5.研究意義

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