引言8.2格的定義(離散數(shù)學(xué))

《引言8.2格的定義(離散數(shù)學(xué))》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、第八章格與布爾代數(shù)§8.1引言集合代數(shù)：（ρ(S)，∪，∩）對(duì)?A,B,C∈ρ(S)，運(yùn)算∪，∩滿足：等冪律A∩A=A，A∪A=A，交換律A∩B=B∩A，A∪B=B∪A，結(jié)合律A∩（B∩C）=（A∩B）∩C，A∪（B∪C）=（A∪B）∪C，分配律A∩（B∪C）=（A∩B）∪（A∩C），A∪（B∩C）=（A∪B）∩（A∪C），吸收律A∩（A∪B）=A，A∪（A∩B）=A，若引進(jìn)余集ˉ的概念，有DeMorgan定律:命題代數(shù)（S，∧，∨）對(duì)?A,B,C∈S，運(yùn)算∧，∨滿足：等冪律A∧A=A，A∨A=A，，交換律A∧B=B∧A，A∨B=B∨A結(jié)合律A

2、∧（B∧C）=（A∧B）∧C，A∨（B∨C）=（A∨B）∨C分配律A∧(B∨C)=(A∧B)∨(A∧C)，A∨（B∧C）=（A∨B）∧（A∨C）吸收律A∧(A∨B)=A，A∨（A∧B）=A，若引進(jìn)否定?的概念，有DeMorgan定律:?(A∧B)=?A∨?B,?(A∨B)=?A∧?B,§8.2格的定義半序格定義A給出一個(gè)部分序集（L，≤）,如果對(duì)于任意a，b∈L，L的子集{a，b}在L中都有一個(gè)最大下界(記為inf{a，b})和一個(gè)最小上界（記為sup{a，b}），則稱（L，≤）為一個(gè)格。半序格的例例.S是任意一個(gè)集合，ρ(S)是S的冪集合，則

3、，部分序集(ρ(S)，?)是一個(gè)格。因?yàn)閷?duì)?A,B∈ρ(S)，sup{A,B}=A∪B∈ρ(S),inf{A,B}=A∩B∈ρ(S)例.設(shè)I+是所有正整數(shù)集合，D是I+中的“整除關(guān)系”，對(duì)任意a，b∈I+，aDb當(dāng)且僅當(dāng)a整除b，于是，（I+，D）是一個(gè)格。sup{a，b}=a，b的最小公倍∈I+，inf{a,b}=a，b的最高公因∈I+。半序格的例例.設(shè)n是一個(gè)正整數(shù)，Sn是n的所有正因數(shù)的集合，于是，（Sn，D）是格。因?yàn)閟up{a，b}=a，b的最小公倍∈Sn，inf{a,b}=a，b的最高公因∈Sn。例.設(shè)S是所有的命題集合，定義“”如

4、下：AB當(dāng)且僅當(dāng)B蘊(yùn)涵A。則（S，）是一個(gè)格。因?yàn)閟up{A，B}=A∧B∈S，inf{A，B}=A∨B∈S。半序子格定義A′設(shè)（L，≤）是格，S?L，如果（S，≤）是格，則稱（S，≤）是格（L，≤）的子格。例.（S6，D）是（S24，D）的子格。代數(shù)格定義B設(shè)L是一個(gè)集合，×，⊕是L上兩個(gè)二元代數(shù)運(yùn)算，如果這兩種運(yùn)算對(duì)于L中元素滿足：（1）交換律：a×b=b×a，a⊕b=b⊕a。（2）結(jié)合律：a×（b×c）=（a×b）×c，a⊕（b⊕c）=（a⊕b）⊕c。（3）吸收律：a×（a⊕b）=a，a⊕（a×b）=a。則稱此代數(shù)系統(tǒng)（L，×，）為一個(gè)格

5、。note:定義B中由×，⊕滿足吸收律可推出它們一定滿足等冪律。證明：任取L中元素a，由×，⊕滿足吸收律知，a×（a⊕a）=a，a⊕（a×a）=a。故a×a=a×（a⊕（a×a）），a⊕a=a⊕（a×（a⊕a））。又由×，⊕滿足吸收律知，上面兩式的等式右端都等于a。因此，a×a=a，a⊕a=a。即，定義B中的×，運(yùn)算亦滿足等冪律。代數(shù)格的例例.設(shè)S是一個(gè)集合,ρ(S)是S的冪集合，于是，(ρ(S),∩,∪)是一個(gè)代數(shù)格。而(ρ(S)，?)是半序格。易見(jiàn)對(duì)?A,B∈ρ(S)，A?BA∩B=AA∪B=B。例.設(shè)I+是所有正整數(shù)集合,兩個(gè)正整數(shù)的最高

6、公因×,最小公倍⊕是I+上兩個(gè)代數(shù)運(yùn)算，于是,(I+,×,⊕)是一個(gè)代數(shù)格。而（I+,D）是半序格,D是整除關(guān)系。易見(jiàn)，對(duì)任意a，b∈I+,aDba×b=aa⊕b=b。例.設(shè)n是一個(gè)正整數(shù),Sn是n的所有正因數(shù)的集合,兩個(gè)正整數(shù)的最高公因×,最小公倍⊕可是Sn上兩個(gè)代數(shù)運(yùn)算,于是,(Sn,×,⊕)是一個(gè)代數(shù)格。代數(shù)格與半序格的等價(jià)性定理8.2.1定義A所定義的格和定義B所定義的格是等價(jià)的，亦即，一個(gè)半序格必是一個(gè)代數(shù)格；反之亦然。證明：i）若(L,≤)是一個(gè)半序格,則對(duì)?a,b∈L，記inf{a，b}為a×b；sup{a，b}為a⊕b。由于對(duì)任

7、意a，b，其inf{a，b}，sup{a，b}是唯一的，所以，如上定義的×，⊕是集合L上的兩種二元代數(shù)運(yùn)算。不難證明,對(duì)于×,⊕滿足交換律,結(jié)合律,吸收律。則根據(jù)定義B,(L,×,⊕)是一個(gè)代數(shù)格。我們只證明吸收律：a×（a⊕b）=a為例，其它算律的證明留給讀者。因?yàn)閍×(a⊕b)是a與(a⊕b)的最大下界，所以a×(a⊕b)≤a另一方面，由于a≤a，a≤a⊕b，所以，a是a與a⊕b的下界，故a≤a×(a⊕b)所以，a=a×(a⊕b)。證明證明ii）若代數(shù)系統(tǒng)（L，×，⊕）是一個(gè)代數(shù)格，在集合L上定義一個(gè)關(guān)系≤如下：對(duì)任意a，b∈L，a≤ba×

8、b=a①往證：≤是一個(gè)半序關(guān)系。反身性:因?yàn)閍×a=a×(a⊕(a×a))=a,所以a≤a。反對(duì)稱性:若有a≤b,b≤a,則應(yīng)有a×b=a，b×a=b