-
有序集
鎖定
設R是集合A上的二元關係,如果R是自反、反對稱、傳遞的,那麼稱R為A上的序關係,如果集合A上有序關係R,則稱A為有序集,用序偶表示。設為有序集,B是A的子集,則有如下相關定義:B的最小元、最大元、極大元、極小元、上界、下界、上確界、下確界及A的鏈、反鏈。對於有序集上各定義也有相關的定理,如若b為B的最大(最小)元,則b為B的極大(極小)元等等。
- 中文名
- 有序集
- 外文名
- ordered set
- 定 義
- 集合A上有序關係R,則A為有序集
- 序關係
- 滿足自反、反對稱、傳遞
- 類 別
- 科技
- 應用學科
- 離散數學
有序集預備知識
有序集序關係的定義
設R是集合A上的二元關係。如果R是自反、反對稱、傳遞的,那麼稱R為A上的序關係(ordered relation)。如果集合A上有序關係R,則稱A為有序集(ordered set),用序偶表示。
[1]
有序集序關係的關係圖
可對序關係的關係圖進行簡化,操作如下:
(1)由於序關係是自反的,各結點處均有環,約定全部省去;
(2)由於序關係是反對稱且傳遞的,關係圖任何兩個不同結點之間不可能有相互反方向的邊或通路,因此可約定邊的向上方向為箭頭方向,即若a≤b,則將結點a畫在結點b之下,省略全部箭頭;
有序集有序集的相關定義
設R是集合A上的二元關係。如果R是A上的序關係,則稱A為有序集(ordered set),用序偶表示。
[1]
有序集是在其元素之間定義了一個序的集合,例如,一切實數構成的集合、一切整數構成的集合,一切自然數構成的集合等關於通常的大小關係是有序集。
[2]
還可表述為,有序集是由一個集合和這個集合中的一種序關係所組成的偶。
[3]
設為有序集,B
A,則有如下相關定義:
有序集B的最小元、最大元
(1)如果b∈B,且對每一個x∈B,b≤x,則稱b為B的最小元。
有序集B的極小元、極大元
(1)如果b∈B,並且沒有x∈B,x≠b,使得x≤b,則稱b為B的極小元。
有序集B的上界、下界
(1)如果a∈A,且對每一個x∈B,x≤a,則稱a為B的上界。
有序集B的上確界、下確界
(1)如果a是B的所有上界集合的最小元,則稱a為B的最小上界或上確界。
有序集A上的鏈、反鏈
(1)如果B中的任何兩個元素都是可以比較的,則稱B為A上的鏈;
(2)如果B中的任何兩個不同元素都是不可比較的,則稱B為A上的反鏈。
有序集相似的有序集
有序集相關定理
有序集最元與極元
設為有序集,B
A
(1)若b為B的最大(最小)元,則b為B的極大(極小)元;
(2)若B有最大(最小)元,則B的最大(最小)元唯一;
有序集最元與確界
設為有序集,B
A
(1)若b為B的最大(最小)元,則b必為B的上(下)確界;
(2)若b為B的上(下)界,且b∈B,則b必為B的最大(最小)元;
有序集鏈與反鏈
(1)設為一個有限的有序集,且A中最長的鏈的長度為n,那麼A有一劃分,使劃分有n個單元,且每一單元為反鏈。
有序集光纖通道中的有序集
有序集結構
有序集分類
(1)幀定界符:用來標識數據幀的幀頭和幀尾,例如K28.5 D21.5 D22.2 D22.2有序集可用來標識幀頭,稱之為Start-of-Frame(SOF);K28.5 D21.4 D21.6 D21.6有序集可用來標識幀尾,稱之為End-of-Frame(EOF)。光纖通道定義了11種類型的SOF有序集和8種類型的EOF有序集。
(2)原語信號:用來表示傳輸過程中的動作或事件。主要的原語信號有IDLE原語信號和R_RDY原語信號。IDLE表示為K28.5 D21.4 D21.5 D21.5,用於在沒有數據發送期間保持鏈路的激活。R_RDY表示為K28.5 D21.4 D10.2 D10.2,用於表示準備在鏈路層傳送幀。