時間：2022-12-22 16:30:01 | 來源：信息時代
時間：2022-12-22 16:30:01 來源：信息時代
格 : 既是一種特殊的偏序集(見二元關(guān)系),又可以等價地轉(zhuǎn)換成一種有兩個二元運算的代數(shù)系統(tǒng)。
(1)偏序格: 任何兩個元素都有最小上界和最大下界的偏序集。例如,〈P(A),〉是格,其中P(A)是集合A的冪集; 〈Sn,|〉是格,其中n為正整數(shù),Sn為n的正因子集合,|是整除關(guān)系。
設(shè)〈L, ≼〉為格, 在L中引入兩個二元運算:∀a, b∈L, a與b的最小上界記為a∨b, 最大下界記為a∧b。這樣得到有兩個二元運算的代數(shù)系統(tǒng)〈L, ∧, ∨〉, 它具有性質(zhì): ①冪等律: ∀a∈L,a∨a=a, a∧a=a; ②交換律: ∀a, b∈L, a∨b=b∨a, a∧b=b∧a; ③結(jié)合律: ∀a, b, c∈L, a∨(b∨c)=(a∨b)∨c,a∧(b∧)c=(a∧b)∧c;④吸收律:∀a,b∈L,a∧(a∨b)=a,a∨(a∧b)=a。
(2)代數(shù)格: 二元運算∨與∧滿足交換律,結(jié)合律和吸收律的代數(shù)系統(tǒng)〈L,∨,∧〉。給定偏序格〈L, ≼〉, 則可得到一個代數(shù)格〈L, ∨, ∧〉。反之,給定代數(shù)格〈L, ∨, ∧〉, 在L上定義偏序關(guān)系≼如下: ∀a,b∈L, a≼b當(dāng)且僅當(dāng)a∧b=a(或a∨b=b)。那么,∀a, b∈L, a∨b和a∧b分別為a與b關(guān)于≼的最小上界和最大下界,從而〈L, ≼〉構(gòu)成一個偏序格。于是,每個偏序格能誘導(dǎo)出一個代數(shù)格; 反之,每個代數(shù)格有一個偏序格與之對應(yīng)。也就是說,這兩種格是等價的,把它們統(tǒng)稱為格。
例如,偏序格〈Sn,|〉對應(yīng)的代數(shù)格為〈Sn,1cm,gcd〉,其中1cm(x,y)和gcd(x,y)分別是x和y的最小公倍數(shù)和最大公約數(shù)。圖1給出偏序格〈S24,|〉的哈斯圖。 偏序格〈P(A), 〉稱作冪集格, 對應(yīng)的代數(shù)格為〈P(A)),∪,∩〉。
圖1 偏序格〈S24,|〉
圖2 一個有補格
微信公眾號
版權(quán)所有? 億企邦 1997-2022 保留一切法律許可權(quán)利。
在線咨詢