離散數(shù)學(xué)課件第十三章格與布爾代數(shù)

第13章格與布爾代數(shù)第13章格與布爾代數(shù)本章內(nèi)容13.1 格的定義與性質(zhì)13.2 子格與格同態(tài)13.3 分配格與有補格13.4 布爾代數(shù)

本章總結(jié)

作業(yè)本章內(nèi)容13.1 格的定義與性質(zhì)13.1格的定義與性質(zhì)定義13.1設(shè)<S,≤>是偏序集，如果x,y∈S，{x,y}都有最小上界和最大下界，則稱S關(guān)于偏序≤作成一個格(lattice)。說明：由于最小上界和最大下界的唯一性，可以把求{x,y}的最小上界和最大下界看成x與y的二元運算∨和∧。

x∨y：表示x與y的最小上界

x∧y：表示x和y的最大下界。

本章出現(xiàn)的∨和∧符號只代表格中的運算，而不再有其它的含義。13.1格的定義與性質(zhì)定義13.1設(shè)<S,≤>是偏序格的實例例13.1設(shè)n是正整數(shù)，Sn是n的正因子的集合。D為整除關(guān)系，則偏序集<Sn,D>構(gòu)成格。x,y∈Sn， x∨y是lcm(x,y)，即x與y的最小公倍數(shù)。 x∧y是gcd(x,y)，即x與y的最大公約數(shù)。 下圖給出了格<S8,D>，<S6,D>和<S30,D>。格的實例例13.1設(shè)n是正整數(shù)，Sn是n的正因子的集合。D例13.2例13.2判斷下列偏序集是否構(gòu)成格,并說明理由。 (1)<P(B),>，其中P(B)是集合B的冪集。 (2)<Z,≤>，其中Z是整數(shù)集,≤為小于或等于關(guān)系。 (3)偏序集的哈斯圖分別在下圖給出。例13.2例13.2判斷下列偏序集是否構(gòu)成格,并說明理由。例13.2解答(1)是格。 x,y∈P(B)，x∨y就是x∪y，x∧y就是x∩y。 由于∪和∩運算在P(B)上是封閉的，所以x∪y，x∩y∈P(B)。 稱<P(B),>,為B的冪集格。(2)是格。 x,y∈Z,x∨y＝max(x,y)，x∧y＝min(x,y)，它們都是整數(shù)。(3)都不是格。 (a)中的{a,b}沒有最大下界。 (b)中的{b,d}有兩個上界c和e,但沒有最小上界。 (c)中的{b,c}有三個上界d,e,f,但沒有最小上界。 (d)中的{a,g}沒有最大下界。例13.2解答(1)是格。例13.3例13.3設(shè)G是群，L(G)是G的所有子群的集合。即 L(G)＝{H|H≤G} 對任意的H1,H2∈L(G)，H1∩H2也是G的子群，而<H1∪H2>是由H1∪H2生成的子群（即包含著H1∪H2的最小的子群）。 在L(G)上定義包含關(guān)系，則L(G)關(guān)于包含關(guān)系構(gòu)成一個格，稱為G的子群格。 易見在L(G)中，H1∧H2就是H1∩H2，H1∨H2就是<H1∪H2>。例13.3例13.3設(shè)G是群，L(G)是G的所有子群的集合對偶原理定義13.2設(shè)f是含有格中元素以及符號＝、≤、≥、∨和∧的命題。令f*是將f中的≤替換成≥，≥替換成≤，∨替換成∧，∧替換成∨所得到的命題。稱f*為f的對偶命題。例如 在格中令f是(a∨b)∧c≤c，則f*是(a∧b)∨c≥c。格的對偶原理設(shè)f是含有格中元素以及符號＝、≤、≥、∨和∧的命題。若f對一切格為真，則f的對偶命題f*也對一切格為真。例如

對一切格L都有 a,b∈L，a∧b≤a (因為a和b的交是a的一個下界) 那么對一切格L都有 a,b∈L，a∨b≥a說明 許多格的性質(zhì)都是互為對偶命題的。 有了格的對偶原理，在證明格的性質(zhì)時，

只須證明其中的一個命題即可。對偶原理定義13.2設(shè)f是含有格中元素以及符號＝、≤、≥、格的運算性質(zhì)定理13.1設(shè)<L,≤>是格，則運算∨和∧適合交換律、結(jié)合律、冪等律和吸收律，即 (1)交換律a,b∈L有 a∨b＝b∨a a∧b＝b∧a (2)結(jié)合律a,b,c∈L有 (a∨b)∨c＝a∨(b∨c) (a∧b)∧c＝a∧(b∧c) (3)冪等律a∈L有 a∨a＝a a∧a＝a (4)吸收律a,b∈L有 a∨(a∧b)＝a a∧(a∨b)＝a格的運算性質(zhì)定理13.1設(shè)<L,≤>是格，則運算∨和∧適合定理13.1(1)a∨b和b∨a分別是{a,b}和{b,a}的最小上界。 由于{a,b}＝{b,a}，所以a∨b＝b∨a。 由對偶原理，a∧b＝b∧a得證。(2)由最小上界的定義有 (a∨b)∨c≥a∨b≥a (13.1) (a∨b)∨c≥a∨b≥b (13.2) (a∨b)∨c≥c (13.3) 由式13.2和13.3有 (a∨b)∨c≥b∨c (13.4) 再由式13.1和13.4有 (a∨b)∨c≥a∨(b∨c) 同理可證 (a∨b)∨c≤a∨(b∨c) 根據(jù)偏序關(guān)系的反對稱性有 (a∨b)∨c＝a∨(b∨c) 由對偶原理，(a∧b)∧c＝a∧(b∧c)得證。定理13.1(1)a∨b和b∨a分別是{a,b}和{b,a}定理13.1(3)顯然a≤a∨a, 又由a≤a可得 a∨a≤a。 根據(jù)反對稱性有 a∨a＝a， 由對偶原理，a∧a＝a得證。(4)顯然 a∨(a∧b)≥a (13.5) 又由a≤a，a∧b≤a可得 a∨(a∧b)≤a (13.6) 由式13.5和13.6可得

a∨(a∧b)＝a， 根據(jù)對偶原理，a∧(a∨b)＝a得證。定理13.1(3)顯然a≤a∨a,定理13.2定理13.2設(shè)<S,*,>是具有兩個二元運算的代數(shù)系統(tǒng)，若對于*和運算適合交換律、結(jié)合律、吸收律，則可以適當(dāng)定義S中的偏序≤，使得<S,≤>構(gòu)成一個格，且a,b∈S有a∧b＝a*b，a∨b＝ab。思路

(1)證明在S中*和運算都適合冪等律。 (2)在S上定義二元關(guān)系R，并證明R為偏序關(guān)系。 (3)證明<S,≤>構(gòu)成格。說明 通過規(guī)定運算及其基本性質(zhì)可以給出格的定義。定理13.2定理13.2設(shè)<S,*,>是具有兩個二元運算定理13.2a∈S，由吸收律得(1)證明在S中*和運算都適合冪等律。a*a＝a*(a(a*a))＝a同理有aa＝a。(2)在S上定義二元關(guān)系R，a,b∈S有<a,b>∈Rab＝b下面證明R在S上的偏序。根據(jù)冪等律，a∈S都有aa＝a，即<a,a>∈R，所以R在S上是自反的。a,b∈S有aRb且bRaab＝b且ba＝aa＝ba＝ab＝b(由于ab=ba)所以R在S上是反對稱的。定理13.2a∈S，由吸收律得(1)證明在S中*和運算都定理13.2a,b,c∈S有 aRb且bRc ab＝b且bc＝c ac＝a(bc) ac＝(ab)c ac＝bc＝c aRc 這就證明了R在S上是傳遞的。 綜上所述，R為S上的偏序。 以下把R記作≤。定理13.2a,b,c∈S有定理13.2(3)證明<S，≤>構(gòu)成格。即證明a∨b＝ab，a∧b＝a*b。a,b∈S有a(ab)＝(aa)b＝abb(ab)＝a(bb)＝ab根據(jù)≤的定義有a≤ab和b≤ab，所以ab是{a,b}的上界。假設(shè)c為{a,b}的上界，則有ac＝c和bc＝c，從而有(ab)c＝a(bc)＝ac＝c這就證明了ab≤c，所以ab是{a,b}的最小上界，即a∨b＝ab為證a*b是{a,b}的最大下界，先證首先由ab＝b可知a*b＝a*(ab)＝a反之由a*b＝a可知ab＝(a*b)b＝b(b*a)＝b再由式(13.7)和≤的定義有a≤ba*b＝a，依照前邊的證明,類似地可證a*b是{a,b}的最大下界，即a∧b＝a*b。ab＝ba*b＝a (13.7)定理13.2(3)證明<S，≤>構(gòu)成格。即證明a∨b＝a格的等價定義根據(jù)定理13.2，可以給出格的另一個等價定義。定義13.3設(shè)<S,*,>是代數(shù)系統(tǒng)，*和是二元運算，如果*和滿足交換律，結(jié)合律和吸收律，則<S,*,>構(gòu)成一個格(lattice)。說明 格中的冪等律可以由吸收律推出。 以后我們不再區(qū)別是偏序集定義的格，

還是代數(shù)系統(tǒng)定義的格，而統(tǒng)稱為格L。格的等價定義根據(jù)定理13.2，可以給出格的另一個等價定義。格的性質(zhì)定理13.3

設(shè)L是格，則a,b∈L有 a≤ba∧b＝aa∨b＝b證明

先證a≤ba∧b＝a 由a≤a和a≤b可知，a是{a,b}的下界， 故a≤a∧b。顯然又有a∧b≤a。 由反對稱性得a∧b＝a。

再證a∧b＝aa∨b＝b。 根據(jù)吸收律有b＝b∨(b∧a) 由a∧b＝a得b＝b∨a,即a∨b＝b。

最后證a∨b＝ba≤b。 由a≤a∨b得a≤a∨b＝b。格的性質(zhì)定理13.3設(shè)L是格，則a,b∈L有格的性質(zhì)定理11.4設(shè)L是格，a,b,c,d∈L，若a≤b且c≤d，則 a∧c≤b∧d， a∨c≤b∨d證明 a∧c≤a≤b a∧c≤c≤d 因此，a∧c≤b∧d。 同理可證a∨c≤b∨d。格的性質(zhì)定理11.4設(shè)L是格，a,b,c,d∈L，若a≤例13.4

例13.4設(shè)L是格，證明a,b,c∈L有 a∨(b∧c)≤(a∨b)∧(a∨c)證明 由a≤a，b∧c≤b得 a∨(b∧c)≤a∨b 由a≤a，b∧c≤c得 a∨(b∧c)≤a∨c 從而得到a∨(b∧c)≤(a∨b)∧(a∨c)說明 在格中分配不等式成立。 一般說來，格中的∨和∧運算并不是滿足分配律的。例13.4

例13.4設(shè)L是格，證明a,b,c∈L有本節(jié)小結(jié)偏序集構(gòu)成格的條件：任意二元子集都有最大下界和最小上界。

格的實例：正整數(shù)的因子格，冪集格，子群格。格的性質(zhì)：對偶原理，格中算律（交換、結(jié)合、冪等、吸收），保序性，分配不等式。

格作為代數(shù)系統(tǒng)的定義。格的證明方法本節(jié)小結(jié)偏序集構(gòu)成格的條件：任意二元子集都有最大下界和最小上13.2子格與格同態(tài)定義13.4設(shè)<L,∧,∨>是格，S是L的非空子集，若S關(guān)于L中的運算∧和∨仍構(gòu)成格，則稱S是L的子格。例13.5設(shè)格L如右圖所示。令S1＝{a,e,f,g}S2＝{a,b,e,g}則S1不是L的子格，S2是L的子格。因為對于e和f,有e∧f＝c，但cS1。13.2子格與格同態(tài)定義13.4設(shè)<L,∧,∨>是格，S格同態(tài)定義13.5設(shè)L1和L2是格，:L1→L2，若a,b∈L1有 (a∧b)＝(a)∧(b),

(a∨b)＝(a)∨f(b) 成立，則稱為格L1到L2的同態(tài)映射，簡稱格同態(tài)。例13.6(1)設(shè)L1＝{2n|n∈Z+}，L2＝{2n+1|n∈N} 則L1和L2關(guān)于通常數(shù)的小于或等于關(guān)系構(gòu)成格。 令:L1→L2，(x)＝x-1 不難驗證是L1到L2的同態(tài)映射，因為對任意的x,y∈L1有(x∨y)＝(max(x,y))＝max(x,y)-1(x)∨(y)＝(x-1)∨(y-1)＝max(x-1,y-1)＝max(x,y)-1(x∧y)＝(min(x,y))＝min(x,y)-1(x)∧(y)＝(x-1)∧(y-1)＝min(x-1,y-1)＝min(x,y)-1即(x∧y)＝(x)∧(y),

(x∨y)＝(x)∨(y)格同態(tài)定義13.5設(shè)L1和L2是格，:L1→L2，若例13.6(2)如圖中的格L1，L2和L3，若定義1:L1→L21(a)＝1(b)＝1(c)＝a1，1(d)＝d12:L1→L3

2(a)＝a2，2(b)＝b2,2(c)＝c2，2(d)＝d2則1和2都不是格同態(tài)，因為 1(b∨c)＝1(d)＝d1 1(b)∨1(c)＝a1∨a1＝a1 2(b∨c)＝2(d)＝d2 2(b)∨2(c)＝b2∨c2＝c2從而

1(b∨c)≠1(b)∨1(c) 2(b∨c)≠2(b)∨2(c)例13.6(2)如圖中的格L1，L2和L3，若定義1:L1格同態(tài)的性質(zhì)定理13.5設(shè)是格L1到L2的映射， (1)若是格同態(tài)映射，則是保序映射，即x,y∈L1，有 x≤y

(x)≤(y) (2)若是雙射，則是格同構(gòu)映射當(dāng)且僅當(dāng)x,y∈L1，有 x≤y

(x)≤(y)證明(1)任取x,y∈L1，x≤y， 由格的性質(zhì)知x∨y＝y(tǒng)。 又由于是格同態(tài)映射，必有

(y)＝(x∨y)＝(x)∨(y) 從而得到(x)≤(y)。格同態(tài)的性質(zhì)定理13.5設(shè)是格L1到L2的映射，定理13.5(2)的證明充分性。(2)若是雙射，則是格同構(gòu)映射當(dāng)且僅當(dāng)x,y∈L1，有 x≤y(x)≤(y)只須證明是L1到L2的同態(tài)映射即可。任取x,y∈L1，令x∨y＝z，由x≤z和y≤z知(x)≤(z)，(y)≤(z)從而有(x)∨(y)≤(z)＝(x∨y)另一方面，由(x)∨(y)∈L2和的滿射性可知，必存在u∈L1使得 (u)＝(x)∨(y)因此有 (x)≤(u)，(y)≤(u)。由已知條件可得x≤u，y≤u。從而推出x∨y≤u。再次使用已知條件得

(x∨y)≤(u)＝(x)∨(y)。綜合上述有 (x∨y)＝(x)∨(y)。同理可證 (x∧y)＝(x)∧(y)。定理13.5(2)的證明充分性。(2)若是雙射，則是格同定理13.5(2)的證明必要性。由(1)的結(jié)論必有 x≤y(x)≤(y)反之，若(x)≤(y)，由于是同構(gòu)映射，則

(x∨y)＝(x)∨(y)＝(y)又由于是雙射，必有x∨y＝y(tǒng)。從而證明了x≤y。(2)若是雙射，則是格同構(gòu)映射當(dāng)且僅當(dāng)x,y∈L1，有 x≤y(x)≤(y)定理13.5(2)的證明必要性。由(1)的結(jié)論必有(2)若例13.7例13.7設(shè)L1＝<S12,D>,L2＝<S12,≤>是格，其中S12是12的所有正因子構(gòu)成的集合，D為整除關(guān)系，≤為通常數(shù)的小于或等于關(guān)系。令

:S12→S12，(x)＝x 則是雙射，但不是格L1到L2的同構(gòu)映射。 因為(2)≤(3)，但2不整除3。 根據(jù)定理13.5可知，不是同構(gòu)映射。例13.7例13.7設(shè)L1＝<S12,D>,L2＝<S1格的直積類似于半群,群和環(huán),也可以定義格的直積。定義13.6設(shè)L1和L2是格，定義L1×L2上的運算∩,∪： 即<a1,b1>,<a2,b2>∈L1×L2有 <a1,b1>∩<a2,b2>＝<a1∧a2,b1∧b2> <a1,b1>∪<a2,b2>＝<a1∨a2,b1∨b2> 稱<L1×L2,∩,∪>為格L1和L2的直積。 可以證明<L1×L2,∩,∪>仍是格。格的直積類似于半群,群和環(huán),也可以定義格的直積。格的直積<a1,b1>，<a2,b2>，<a3,b3>∈L1×L2，有交換律<a1,b1>∩<a2,b2>＝<a1∧a2,b1∧b2>＝<a2∧a1,b2∧b1>＝<a2,b2>∩<a1,b1>結(jié)合律(<a1,b1>∩<a2,b2>)∩<a3,b3>＝<a1∧a2,b1∧b2>∩<a3,b3>＝<(a1∧a2)∧a3,(b1∧b2)∧b3>＝<a1∧a2∧a3,b1∧b2∧b3>同樣

<a1,b1>∩(<a2,b2>∩<a3,b3>)＝<a1∧a2∧a3,b1∧b2∧b3>同理可證∪運算也滿足交換律和結(jié)合律。格的直積<a1,b1>，<a2,b2>，<a3,b3>∈L格的直積吸收律 <a1,b1>∩(<a1,b1>∪<a2,b2>) ＝<a1,b1>∩<a1∨a2,b1∨b2> ＝<a1∧(a1∨a2),b1∧(b1∨b2)> ＝<a1,b1>同理有

<a1,b1>∪(<a1,b1>∩<a2,b2>)＝<a1,b1>這就證明了∩和∪運算滿足吸收律。從而證明L1×L2仍是格格的直積吸收律 <a1,b1>∩(<a1,b1>∪<a2格的直積舉例格L＝<{0,1},≤>，≤為通常的小于或等于關(guān)系。則 L×L＝{<0,0>，<0,1>，<1,0>，<1,1>}，其中<0,0>是最小元，<1,1>是最大元，且 <0,0>≤<0,1>≤<1,1>， <0,0>≤<1,0>≤<1,1>，而<0,1>與<1,0>是不可比的。易見L×L與圖13.4的L1同構(gòu)。格的直積舉例格L＝<{0,1},≤>，≤為通常的小于或等于關(guān)本節(jié)小結(jié)格L的非空子集S構(gòu)成L的子格的條件： S對L的兩個運算封閉。

函數(shù)構(gòu)成格同態(tài)的條件：

(a∧b)＝(a)∧(b)

(a∨b)＝(a)∨(b)格同態(tài)的保序性。本節(jié)小結(jié)格L的非空子集S構(gòu)成L的子格的條件：13.3分配格與有補格一般說來，格中運算∨對∧滿足分配不等式， 即a,b,c∈L，有 a∨(b∧c)≤(a∨b)∧(a∨c) 但是不一定滿足分配律。滿足分配律的格稱為分配格。定義13.7設(shè)<L,∧,∨>是格，若a,b,c∈L，有 a∧(b∨c)＝(a∧b)∨(a∧c) a∨(b∧c)＝(a∨b)∧(a∨c) 則稱L為分配格。說明 上面兩個等式互為對偶式。 在證明L為分配格時，只須證明其中的一個等式即可。13.3分配格與有補格一般說來，格中運算∨對∧滿足分配不等例13.8L1和L2是分配格，L3和L4不是分配格。在L3中， b∧(c∨d)＝b∧e＝b(b∧c)∨(b∧d)＝a∨a＝a在L4中, c∨(b∧d)＝c∨a＝c(c∨b)∧(c∨d)＝e∧d＝d鉆石格五角格例13.8L1和L2是分配格，L3和L4不是分配格。在L3中分配格的判別定理13.6設(shè)L是格，則L是分配格當(dāng)且僅當(dāng)L中不含有與鉆石格或五角格同構(gòu)的子格。證明 略。推論 (1)小于五元的格都是分配格。 (2)任何一條鏈都是分配格。分配格的判別定理13.6設(shè)L是格，則L是分配格當(dāng)且僅當(dāng)L中例13.9說明下圖中的格是否為分配格，為什么？L1,L2和L3都不是分配格。{a,b,c,d,e}是L1的子格，并且同構(gòu)于鉆石格。{a,b,c,e,f}是L2的子格，并且同構(gòu)于五角格。{a,c,b,e,f}是L3的子格，也同構(gòu)于鉆石格。

例13.9說明下圖中的格是否為分配格，為什么？L1,L2和定理13.7定理13.7格L是分配格當(dāng)且僅當(dāng) a,b,c∈L，a∧b＝a∧c且a∨b＝a∨cb＝c。證明

必要性。a,b,c∈L，有 b＝b∨(a∧b) (吸收律,交換律) ＝b∨(a∧c) (已知條件代入) ＝(b∨a)∧(b∨c) (分配律) ＝(a∨c)∧(b∨c) (已知條件代入,交換律) ＝(a∧b)∨c (分配律) ＝(a∧c)∨c (已知條件代入) ＝c (交換律,吸收律)定理13.7定理13.7格L是分配格當(dāng)且僅當(dāng)定理13.7充分性。假若a,b,c∈L，有 a∧b＝a∧c且a∨b＝a∨cb＝c 成立，而L不是分配格。 根據(jù)定理13.6，L中必含有與鉆石格或五角格同構(gòu)的子格。 假設(shè)L中含有與鉆石格同構(gòu)的子格，且該子格為{u,v,x,y,z}，其中u為它的最小元，v為它的最大元。從而推出 x∧y＝x∧z＝u，x∨y＝x∨z＝v但y≠z，與已知矛盾。對五角格的情況同理可證。vuxzy定理13.7充分性。假若a,b,c∈L，有從而推出vuxz定理13.7的應(yīng)用使用定理13.7也可以判別一個格是否為分配格。例如下圖中的三個格都不是分配格。在L1中有b∨c＝b∨d，b∧c＝b∧d，但c≠d。在L2中有b∧c＝b∧e，b∨c＝b∨e，但c≠e。在L3中有c∧b＝c∧d，c∨b＝c∨d，但b≠d。定理13.7的應(yīng)用使用定理13.7也可以判別一個格是否為分配格的全下界和全上界定義13.8設(shè)L是格， 若存在a∈L使得x∈L有a≤x，則稱a為L的全下界； 若存在b∈L使得x∈L有x≤b，則稱b為L的全上界。命題 格L若存在全下界或全上界，一定是唯一的。證明 以全下界為例，假若a1和a2都是格L的全下界, 則有a1≤a2和a2≤a1。 根據(jù)偏序關(guān)系的反對稱性必有a1＝a2。記法 將格L的全下界記為0，全上界記為1。格的全下界和全上界定義13.8設(shè)L是格，有界格定義13.9設(shè)L是格，若L存在全下界和全上界，則稱L為有界格，并將L記為<L,∧,∨,0,1>。說明 有限格L一定是有界格。舉例設(shè)L是n元格，且L＝{a1,a2,…,an}，那么a1∧a2∧…∧an是L的全下界，而a1∨a2∨…∨an是L的全上界。因此L是有界格。對于無限格L來說，有的是有界格，有的不是有界格。如集合B的冪集格<P(B),∩,∪>，不管B是有窮集還是無窮集，它都是有界格。它的全下界是空集，全上界是B。整數(shù)集Z關(guān)于通常數(shù)的小于或等于關(guān)系構(gòu)成的格不是有界格，因為不存在最小和最大的整數(shù)。有界格定義13.9設(shè)L是格，若L存在全下界和全上界，則稱L有界格的性質(zhì)定理13.8設(shè)<L,∧,∨,0,1>是有界格，則a∈L有 a∧0＝0 a∨0＝a a∧1＝a a∨1＝1證明 由a∧0≤0和0≤a∧0可知a∧0＝0。說明 在有界格中， 全下界0是關(guān)于∧運算的零元，∨運算的單位元。 全上界1是關(guān)于∨運算的零元，∧運算的單位元。對偶原理對于涉及到有界格的命題，如果其中含有全下界0或全上界1，在求該命題的對偶命題時，必須將0替換成1，而將1替換成0。例如 a∧0＝0和a∨1＝1互為對偶命題， a∨0＝a和a∧1＝a互為對偶命題。有界格的性質(zhì)定理13.8設(shè)<L,∧,∨,0,1>是有界格，有界格中的補元定義13.10設(shè)<L,∧,∨,0,1>是有界格，a∈L， 若存在b∈L使得

a∧b＝0和a∨b＝1 成立，則稱b是a的補元。說明 若b是a的補元，那么a也是b的補元。 換句話說，a和b互為補元。有界格中的補元定義13.10設(shè)<L,∧,∨,0,1>是有界例13.10考慮下圖中的四個格。L1中的a與c互為補元，其中a為全下界，c為全上界，b沒有補元。L2中的a與d互為補元，其中a為全下界，d為全上界，b與c也互為補元。L3中的a與e互為補元，其中a為全下界，e為全上界，b的補元是c和d，c的補元是b和d，d的補元是b和c。b,c,d每個元素都有兩個補元。L4中的a與e互為補元。其中a為全下界。e為全上界。b的補元是c和d，c的補元是b，d的補元是b。例13.10考慮下圖中的四個格。L1中的a與c互為補元，其中有界格中補元的說明在任何有界格中，全下界0與全上界1互補。對于其他元素，可能存在補元，也可能不存在補元。如果存在，可能是唯一的，也可能是多個補元。對于有界分配格，如果它的元素存在補元，一定是唯一的。有界格中補元的說明在任何有界格中，有界分配格中補元的唯一性定理13.9設(shè)<L,∧,∨,0,1>是有界分配格。 若a∈L，且對于a存在補元b，則b是a的唯一補元。證明 假設(shè)c∈L也是a的補元，則有 a∨c＝1，a∧c＝0 又知b是a的補元，故 a∨b＝1，a∧b＝0 從而得到 a∨c＝a∨b，a∧c＝a∧b 由于L是分配格，根據(jù)定理13.7，b＝c。有界分配格中補元的唯一性定理13.9設(shè)<L,∧,∨,0,有補格的定義定義13.11設(shè)<L,∧,∨,0,1>是有界格，若L中所有元素都有補元存在，則稱L為有補格。L2,L3和L4是有補格，L1不是有補格。L2和L3是有補格，L1不是有補格。有補格的定義定義13.11設(shè)<L,∧,∨,0,1>是有界格本節(jié)小結(jié)如果格中一個運算對另一個運算是可分配的，稱這個格是分配格。

分配格的兩種判別法： 不存在與鉆石格或五角格同構(gòu)的子格； 對于任意元素a,b,c,有a∧b＝a∧c且a∨b＝a∨cb＝c。

有界格的定義及其實例。

格中元素的補元及其性質(zhì)（分配格中補元的唯一性）。

有補格的定義。本節(jié)小結(jié)如果格中一個運算對另一個運算是可分配的，稱這個格是分13.4布爾代數(shù)定義13.12如果一個格是有補分配格，則稱它為布爾格或布爾代數(shù)。說明 在布爾代數(shù)中，每個元素都存在著唯一的補元。 可以把求補元的運算看作是布爾代數(shù)中的一元運算。 可以把一個布爾代數(shù)標(biāo)記為<B,∧,∨,＇,0,1>，

＇為求補運算,a∈B，a＇是a的補元。13.4布爾代數(shù)定義13.12如果一個格是有補分配格，則例13.11例13.11

設(shè)S110＝{1,2,5,10,11,22,55,110}是110的正因子集合。令gcd,lcm分別表示求最大公約數(shù)和最小公倍數(shù)的運算。問<S110,gcd,lcm>是否構(gòu)成布爾代數(shù)？為什么？解答

證明<S110,gcd,lcm>構(gòu)成格。容易驗證x,y,z∈S110，有g(shù)cd(x,y)∈S110 lcm(x,y)∈S110gcd(x,y)＝gcd(y,x)lcm(x,y)＝lcm(y,x)gcd(gcd(x,y),z)＝gcd(x,gcd(y,z))lcm(lcm(x,y),z)＝lcm(x,lcm(y,z))gcd(x,lcm(x,y))＝xlcm(x,gcd(x,y))＝x二元運算交換律結(jié)合律吸收律例13.11例13.11

設(shè)S110＝{1,2,5,10,例13.11證明<S110,gcd,lcm>是分配格。 易驗證x,y,z∈S110有 gcd(x,lcm(y,z))＝lcm(gcd(x,y),gcd(x,z))證明<S110,gcd,lcm>是有補格。 1為S110中的全下界 110為S110中的全上界 1和110互為補元，2和55互為補元， 5和22互為補元，10和11互為補元。綜上所述，<S110,gcd,lcm>為布爾代數(shù)。例13.11證明<S110,gcd,lcm>是分配格。例13.12例13.12設(shè)B為任意集合,證明B的冪集格<P(B),∩,∪,～,,B>構(gòu)成布爾代數(shù)，稱為集合代數(shù)。證明 P(B)關(guān)于∩和∪構(gòu)成格，因為 ∩和∪運算滿足交換律、結(jié)合律和吸收律。 由于∩和∪互相可分配，因此P(B)是分配格， 且全下界是空集,全上界是B。 根據(jù)絕對補的定義，取全集為B， x∈P(B)，～x是x的補元。 從而證明P(B)是有補分配格，即布爾代數(shù)。例13.12例13.12設(shè)B為任意集合,證明B的冪集格<P布爾代數(shù)的性質(zhì)定理13.10設(shè)<B,∧,∨,′,0,1>是布爾代數(shù)，則(1)a∈B，(a＇)＇＝a(2)a,b∈B，(a∧b)＇＝a＇∨b＇,(a∨b)＇＝a＇∧b＇說明 (1)稱為雙重否定律。 (2)稱為德摩根律。 命題代數(shù)與集合代數(shù)的雙重否定律與德摩根律實際上

是這個定理的特例。 可以證明德摩根律對有限個元素也是正確的。證明 (1)(a′)′是a′的補元，a也是a′的補元。 由補元的唯一性得(a′)′＝a。布爾代數(shù)的性質(zhì)定理13.10設(shè)<B,∧,∨,′,0,1>是定理13.10(2)的證明(2)a,b∈B，(a∧b)＇＝a＇∨b＇,(a∨b)＇＝a＇∧b＇ (a∧b)∨(a＇∨b＇) ＝(a∨a＇∨b＇)∧(b∨a＇∨b＇) ＝(1∨b＇)∧(a＇∨1) ＝1∧1 ＝1

(a∧b)∧(a＇∨b＇) ＝(a∧b∧a＇)∨(a∧b∧b＇) ＝(0∧b)∨(a∧0) ＝0∨0＝0 所以a＇∨b＇是a∧b的補元，根據(jù)補元的唯一性有 (a∧b)＇＝a＇∨b＇ 同理可證(a∨b)＇=a＇∧b＇。定理13.10(2)的證明(2)a,b∈B，(a∧b)＇布爾代數(shù)作為代數(shù)系統(tǒng)的定義定義13.13設(shè)<B,*,>是代數(shù)系統(tǒng)，*和是二元運算。 若*和°運算滿足： (1) 交換律，即a,b∈B有 a*b＝b*a， ab＝ba (2) 分配律，即a,b,c∈B有 a*(bc)＝(a*b)(a*c) a(b*c)＝(ab)*(ac)

(3) 同一律，即存在0,1∈B，使得a∈B有 a*1＝a， a0＝a (4) 補元律，即a∈B,存在a′∈B，使得 a*a′＝0， aa′＝1則稱<B,*,>是一個布爾代數(shù)。

布爾代數(shù)作為代數(shù)系統(tǒng)的定義定義13.13設(shè)<B,*,>是關(guān)于布爾代數(shù)定義的說明所謂同一律就是指運算含有單位元的性質(zhì)，這里的1是*運算的單位元，0是運算的單位元?？梢宰C明1和0分別也是和*運算的零元。a∈B有 a1 ＝(a1)*1 （同一律） ＝1*(a1) （交換律） ＝(aa′)*(a1) （補元律） ＝a(a′*1) （分配律） ＝aa′ （同一律） ＝1（補元律）同理可證a*0＝0。關(guān)于布爾代數(shù)定義的說明所謂同一律就是指運算含有單位元的性質(zhì)，關(guān)于布爾代數(shù)定義的說明為證明以上定義的<B,*,°>是布爾代數(shù)，只需證明它是一個格，即證明*和°運算滿足結(jié)合律和吸收律。證明吸收律，a,b∈B有

a(a*b) ＝(a*1)(a*b) （同一律） ＝a*(1b) （分配律） ＝a*1 （1是運算的零元) ＝a （同一律）同理有a*(ab)＝a。關(guān)于布爾代數(shù)定義的說明為證明以上定義的<B,*,°>是布爾代關(guān)于布爾代數(shù)定義的說明為證結(jié)合律，先證以下命題：

a,b,c∈B，ab＝ac且ab＝acb＝c由ab＝ac且ab＝ac可得 (ab)*(ab)＝(ac)*(ac)由分配律和交換律得 (a*a)b＝(a*a)c由補元律得 0b＝0c由同一律和交換律得 b＝c關(guān)于布爾代數(shù)定義的說明為證結(jié)合律，先證以下命題：關(guān)于布爾代數(shù)定義的說明使用這個命題，為證明(a*b)*c＝a*(b*c)，只需證明以下兩個等式：(1)a((a*b)*c)＝a(a*(b*c))(2)a((a*b)*c)＝a(a*(b*c))先證明第一個等式，由吸收律有 a(a*(b*c))＝a a((a*b)*c) ＝(a(a*b))*(ac) (分配律) ＝a*(ac) (吸收律) ＝a所以(1)式成立。關(guān)于布爾代數(shù)定義的說明使用這個命題，為證明(a*b)*c＝關(guān)于布爾代數(shù)定義的說明下面證明(2)式：a((a*b)*c)＝a(a*(b*c))

a(a*(b*c)) ＝(aa)*(a(b*c)) (分配律) ＝1*(a(b*c)) (交換律,補元律) ＝a(b*c) (交換律,同一律)

a((a*b)*c) ＝(a(a*b))*(ac)(分配律) ＝((aa)*(ab))*(ac) (分配律) ＝(1*(ab))*(ac) (交換律,補元律) ＝(ab)*(ac)(交換律,同一律) ＝a(b*c) (分配律)所以（2）式成立。關(guān)于布爾代數(shù)定義的說明下面證明(2)式：a((a*b)布爾代數(shù)的子代數(shù)定義13.14設(shè)<B,∧,∨,,0,1>是布爾代數(shù)，S是B的非空子集，若0,1∈S，且S對∧,∨和運算都是封閉的，則稱S是B的子布爾代數(shù)。

布爾代數(shù)的子代數(shù)定義13.14設(shè)<B,∧,∨,,0,1>例13.13例13.13設(shè)<B,∧,∨,,0,1>是布爾代數(shù)，a,b∈B，且a＜b。令 S＝{x|x∈B，且a≤x≤b} 稱S為B中的區(qū)間，可簡記為[a,b]。 可以證明[a,b]是一個布爾代數(shù)。 顯然S是B的非空子集，且a和b分別為S的全下界和全上界。 對任意的x,y∈S都有 a≤x≤b， a≤y≤b 從而有 a≤x∧y≤b,a≤x∨y≤b S關(guān)于∧和∨運算是封閉的。 易見∧和∨運算在S上適合交換律和分配律。例13.13例13.13設(shè)<B,∧,∨,,0,1>是布爾例13.13對任意的x∈S，令y＝(a∨x)∧b(下面證明y為x得補元。)由于a≤a∨x，a≤b，故a≤(a∨x)∧b。同時(a∨x)∧b≤b，因此y∈S。又x∨y ＝x∨((a∨x)∧b) ＝x∨((a∧b)∨(x∧b)) (分配律) ＝x∨a∨(x∧b) (a＜b) ＝x∨(x∧b) (a≤x) ＝(x∨x)∧(x∨b) (分配律) ＝1∧(x∨b) (補元律) ＝x∨b (交換律，同一律) ＝b (x≤b)例13.13對任意的x∈S，令y＝(a∨x)∧b(例13.13 x∧y ＝x∧((a∨x)∧b) ＝x∧(a∨x) (x≤b,交換律) ＝(x∧a)∨(x∧x) (分配律) ＝(x∧a)∨0 (補元律) ＝x∧a (同一律) ＝a (a≤x)根據(jù)定義13.13，<S,∧,∨>構(gòu)成布爾代數(shù)。其全上界是a，全下界是b。x∈[a,b]，x關(guān)于這個全上界和全下界的補元是(a∨x)∧b。當(dāng)a＝0且b＝1時，[a,b]是B的子布爾代數(shù)。但當(dāng)a≠0或b≠1時，[a,b]不是B的子布爾代數(shù)。例13.13 x∧y ＝x∧((a∨x)∧b)例13.14考慮110的正因子集合S110關(guān)于gcd,lcm運算構(gòu)成的布爾代數(shù)。它有以下的子布爾代數(shù)： {1,110} {1,2,55,110} {1,5,22,110} {1,10,11,110} {1,2,5,10,11,22,55,110}例13.14考慮110的正因子集合S110關(guān)于gcd,lcm布爾代數(shù)的同態(tài)映射定義13.15設(shè)<B1,∧,∨,,0,1>和<B2,∩,∪,-,θ,E>是兩個布爾代數(shù)。這里的∩,∪,-泛指布爾代數(shù)B2中的求最大下界、最小上界和補元的運算。θ和E分別是B2的全下界和全上界。

:B1→B2。如果對于任意的a,b∈B1有

(a∨b)＝(a)∪(b)

(a∧b)＝(a)∩(b)

(a)＝-(a) 則稱是布爾代數(shù)B1到B2的同態(tài)映射，簡稱布爾代數(shù)的同態(tài)。說明

類似于其它代數(shù)系統(tǒng)，也可以定義布爾代數(shù)的單同態(tài)、

滿同態(tài)和同構(gòu)。布爾代數(shù)的同態(tài)映射定義13.15設(shè)<B1,∧,∨,,0,例13.15例13.15設(shè)<B1,∧,∨,,0,1>和<B2,∩,∪,-,θ,E>是布爾代數(shù)。:B1→B2。若a,b∈B1有

(a∧b)＝(a)∩(b) (a)＝-(a) 證明是B1到B2的同態(tài)。證明 只須證明a,b∈B1有(a∨b)＝(a)∪(b)成立即可。

(a∨b) ＝(((a∨b))) (雙重否定律) ＝-((a∨b)) (已知) ＝-(a∧b) (德摩根律) ＝-((a)∩(b)) (已知) ＝-(-(a)∩-(b)) (已知) ＝-(-(a))∪-(-(b)) (德摩根律) ＝(a)∪(b) (雙重否定律)例13.15例13.15設(shè)<B1,∧,∨,,0,1>和<有限布爾代數(shù)的結(jié)構(gòu)定義13.16設(shè)L是格，0∈L，a∈L，若b∈L有 0＜b≤ab＝a 則稱a是L中的原子?？紤]右圖中的幾個格。L1的原子是a。L2的原子是a,b,c。L3的原子是a和b。若L是正整數(shù)n的全體正因子關(guān)于整除關(guān)系構(gòu)成的格，則L的原子恰為n的全體質(zhì)因子。若L是集合B的冪集合，則L的原子就是由B中元素構(gòu)成的單元集。有限布爾代數(shù)的結(jié)構(gòu)定義13.16設(shè)L是格，0∈L，a∈L，引理１引理1 設(shè)Ｌ是格，a,b是Ｌ中的原子，若a≠b，則a∧b＝0。證明 假設(shè)a∧b≠0，則有 0＜a∧b≤a和0＜a∧b≤b 由于a,b是原子，則有a∧b＝a和a∧b＝b， 從而有a＝b，與已知矛盾。引理１引理1 設(shè)Ｌ是格，a,b是Ｌ中的原子，若a≠b，則a∧引理２引理２設(shè)B是有限的布爾代數(shù)，x∈B，x≠0，令 T(x)＝{a1,a2,…,an} 是B中所有小于或等于x的原子構(gòu)成的集合，則 x＝a1∨a2∨…∨an 稱這個表示式為x的原子表示，且是唯一的表示。 這里的唯一性是指：若 x＝a1∨a2∨…∨an，x＝b1∨b2∨…∨bn 都是x的原子表示，則有 {a1,a2,…an}＝{b1,b2,…bn}引理２引理２設(shè)B是有限的布爾代數(shù)，x∈B，x≠0，令引理2的證明令y＝a1∨a2∨…∨an。由于ai≤x，i＝1,2,…n，所以必有y≤x。由此可知t1是原子，且t1≤x和t1≤y。假如x∧y≠0，則存在B中元素t1,t2,…,ts，現(xiàn)證明x∧y＝0。使得t1覆蓋0，t2覆蓋t1，…，ts覆蓋ts-1，且ts＝x∧y。由t1≤x可知t1∈T(x)。即存在ai∈T(x)，使得t1＝ai。又由t1≤y可知t1∧y＝t1，從而有t1＝t1∧y＝ai∧y＝ai∧(a1∨a2∨…∨an)＝ai∧(a1∧a2∧…∧ai∧…∧an)＝(ai∧ai)∧(a1∧…∧ai-1∧ai+1∧…∧an)＝0∧a1∧…∧ai-1∧ai+1∧…∧an＝0這與t1覆蓋0矛盾。從而證明了x∧y＝0。引理2的證明令y＝a1∨a2∨…∨an。由于ai≤x，i＝1引理２由 y＝y(tǒng)∨0＝(y∨x)∧(y∨y)＝y(tǒng)∨(x∧y)＝(y∨x)∧1＝y(tǒng)∨x可知x≤y。綜合上述得x＝y(tǒng)，即x＝a1∨a2∨…∨an。設(shè)x＝b1∨b2∨…∨bm是x的另一個原子表示，任取ai∈{a1,a2,…,an}，假若ai{b1,b2,…,bm}。由引理1必有ai∧bj＝0，j＝1,2,…m。又由于ai≤x，于是ai＝ai∧x＝ai∧(b1∨b2∨…∨bn)＝(ai∧b1)∨(ai∧b2)∨…∨(ai∧bm)＝0∨0∨…∨0＝0這與ai是原子矛盾。從而證明了ai∈{b1,b2,…,bm}。同理可證，bj∈{b1,b2,…,bm}，必有bj∈{a1,a2,…,an}，于是{a1,a2,…,an}＝{b1,b2,…,bm}。引理２由 y＝y(tǒng)∨0＝(y∨x)∧(y∨y)＝y(tǒng)∨(x∧有限布爾代數(shù)的表示定理定理13.11(有限布爾代數(shù)的表示定理)設(shè)B是有限布爾代數(shù)，A是B的全體原子構(gòu)成的集合，則B同構(gòu)于A的冪集代數(shù)P(A)。證明 任取x∈B，令T(x)＝{a|a∈B,a是原子且a≤x} 則T(x)A，定義函數(shù) ：B→P(A)，(x)＝T(x)，x∈B 下面證明是B到P(A)的同構(gòu)映射。 任取x,y∈B，b有 b∈T(x∧y)b∈A且b≤x∧y (b∈A且b≤x)且(b∈A且b≤y) b∈T(x)且b∈T(y) b∈T(x)∩T(y) 從而有T(x∧y)＝T(x)∩T(y)， 即x,yB有(x∧y)＝(x)∩(y)。有限布爾代數(shù)的表示定理定理13.11(有限布爾代數(shù)的表示定定理13.11證明任取x,y∈B，設(shè) x＝a1∨a2∨…∨an， y＝b1∨b2∨…∨bm是x,y的原子表示，則 x∨y＝a1∨a2∨…∨an∨b1∨b2∨…∨bm由引理2可知 T(x∨y)＝{a1,a2,…,an,b1,b2,…,bm}又由于 T(x)＝{a1,a2,…,an}， T(y)＝{b1,b2,…,bm}所以 T(x∨y)＝T(x)∪T(y)即 (x∨y)＝(x)∪(y)定理13.11證明任取x,y∈B，設(shè)定理13.11證明任取x∈B，存在x∈B使得 x∨x＝1，x∧x＝0因此有 (x)∪(x)＝(x∨x)＝(1)＝A (x)∩(x)＝(x∧x)＝(0)＝而和A分別為P(A)的全下界和全上界，因此(x)是(x)在P(A)中的補元，即 (x)＝?(x)綜上所述，是B到P(A)的同態(tài)映射。定理13.11證明任取x∈B，存在x∈B使得定理13.11證明下面證明為雙射。假設(shè)(x)＝(y)，則有 T(x)＝T(y)＝{a1,a2,…,an}由引理2可知x＝a1∨a2∨…∨an＝y(tǒng)于是為單射。任取{b1,b2,…,bm}∈P(A)，令x＝b1∨b2∨…∨bm，則 (x)＝T(x)＝{b1,b2,…,bm}于是為滿射。定理得證。定理13.11證明下面證明為雙射。例子考慮110的正因子的集合S110關(guān)于gcd,lcm運算構(gòu)成的布爾代數(shù)。它的原子是2、5和11，因此原子的集合A＝{2,5,11}。冪集P(A)＝{,{2},{5},{11},{2,5},{2,11},{5,11},{2,5,11}}。冪集代數(shù)是<P(A),∩,∪,∽,,A>。只要令

:S110→P(A)，

(1)＝， (2)＝{2}， (5)＝{5}，

(11)＝{11}， (10)＝{2,5}， (22)＝{2,11}，

(55)＝{5,11},

(110)＝A，那么f就是定理13.11中從S110到冪集P(A)的同構(gòu)映射。例子考慮110的正因子的集合S110關(guān)于gcd,lcm運算推論1推論1 任何有限布爾代數(shù)的基數(shù)為2n，n∈N。證明 設(shè)B是有限布爾代數(shù)，A是B的所有原子構(gòu)成的集合， 且|A|＝n，n∈N。 由定理13.11得 B≌P(A)，而|P(A)|＝2n，所以|B|＝2n。推論1推論1 任何有限布爾代數(shù)的基數(shù)為2n，n∈N。推論2推論2

任何等勢的有限布爾代數(shù)都是同構(gòu)的。證明設(shè)B1和B2是有限布爾代數(shù)，且|B1|=|B2|。 則B1≌P(A1)，B2≌P(A2)，其中A1和A2分別為B1和B2的原子集合。 易見|A1|＝|A2|，存在雙射f：A1→A2。令

：P(A1)→P(A2)，(x)＝f(x)，xA1 下面證明是P(A1)到P(A2)的同構(gòu)映射。 任取x,y∈P(A1)，由定理7.5有 f(x∪y)＝f(x)∪f(y) f(x∩y)f(x)∩f(y) 又由于f的單射性，必有f(x∩y)＝f(x)∩f(y)

由于 f(x)∩f(～x)＝f(x∩～x)＝f()＝ f(x)∪f(～x)＝f(x∪～x)＝f(A1)＝A2 得f(～x)＝～f(x)，這就證明了是P(A1)到P(A2)的同態(tài)映射。 綜上所述,有P(A1)≌P(A2),根據(jù)習(xí)題十三章第19題，B1≌B2得證。推論2推論2任何等勢的有限布爾代數(shù)都是同構(gòu)的。有限布爾代數(shù)的說明有限布爾代數(shù)的基數(shù)都是2的冪。在同構(gòu)意義上，對于任何2n，n為自然數(shù)，僅存在一個2n元的布爾代數(shù)。下圖給出了1元,2元,4元和8元的布爾代數(shù)。有限布爾代數(shù)的說明有限布爾代數(shù)的基數(shù)都是2的冪。主要內(nèi)容布爾代數(shù)的兩個等價定義：有補分配格；有兩個二元運算并滿足交換律、分配律、同一律和補元律的代數(shù)系統(tǒng)。

布爾代數(shù)的特殊性質(zhì)：雙重否定律和德摩根律。子布爾代數(shù)的定義及其判別。

布爾代數(shù)同態(tài)的判定：f(a∧b)＝f(a)∩f(b)(或f(a∨b)＝f(a)∪f(b)),f(a)＝-f(a)

對于任意自然數(shù)n，只有一個2n元的有限布爾代數(shù)，就是冪集代數(shù)。

主要內(nèi)容布爾代數(shù)的兩個等價定義：學(xué)習(xí)要求能夠判斷給定偏序集或者代數(shù)系統(tǒng)是否構(gòu)成格。

能夠確定一個命題的對偶命題。

能夠證明格中的等式和不等式。

能夠判別格L的子集S是否構(gòu)成格。了解格的同態(tài)及其性質(zhì)。能夠判別給定的格是否為分配格。能夠判別布爾代數(shù)并證明布爾代數(shù)的等式。學(xué)習(xí)要求能夠判斷給定偏序集或者代數(shù)系統(tǒng)是否構(gòu)成格。

作業(yè)習(xí)題十三1，2，3，6，8，12，16，17，19作業(yè)習(xí)題十三格的證明方法格中等式的證明方法 證明等式的左邊“小于等于”右邊，右邊“小于等于”左邊。 根據(jù)偏序關(guān)系的反對稱性，得到需要的等式。格中不等式的證明方法 a≤a (偏序關(guān)系的自反性) a≤b且b≤ca≤c (偏序關(guān)系的傳遞性) a∧b≤a，a∧b≤b，a≤a∨b，a≤a∨b (下界定義與上界的定義) a≤b且a≤ca≤b∧c，b≤a且c≤ab∨c≤a (最大下界定義與最小上界的定義) a≤b且c≤da∧c≤b∧d，a∨c≤b∨d (保序性)格的證明方法格中等式的證明方法第13章格與布爾代數(shù)第13章格與布爾代數(shù)本章內(nèi)容13.1 格的定義與性質(zhì)13.2 子格與格同態(tài)13.3 分配格與有補格13.4 布爾代數(shù)

本章總結(jié)

作業(yè)本章內(nèi)容13.1 格的定義與性質(zhì)13.1格的定義與性質(zhì)定義13.1設(shè)<S,≤>是偏序集，如果x,y∈S，{x,y}都有最小上界和最大下界，則稱S關(guān)于偏序≤作成一個格(lattice)。說明：由于最小上界和最大下界的唯一性，可以把求{x,y}的最小上界和最大下界看成x與y的二元運算∨和∧。

x∨y：表示x與y的最小上界

x∧y：表示x和y的最大下界。

本章出現(xiàn)的∨和∧符號只代表格中的運算，而不再有其它的含義。13.1格的定義與性質(zhì)定義13.1設(shè)<S,≤>是偏序格的實例例13.1設(shè)n是正整數(shù)，Sn是n的正因子的集合。D為整除關(guān)系，則偏序集<Sn,D>構(gòu)成格。x,y∈Sn， x∨y是lcm(x,y)，即x與y的最小公倍數(shù)。 x∧y是gcd(x,y)，即x與y的最大公約數(shù)。 下圖給出了格<S8,D>，<S6,D>和<S30,D>。格的實例例13.1設(shè)n是正整數(shù)，Sn是n的正因子的集合。D例13.2例13.2判斷下列偏序集是否構(gòu)成格,并說明理由。 (1)<P(B),>，其中P(B)是集合B的冪集。 (2)<Z,≤>，其中Z是整數(shù)集,≤為小于或等于關(guān)系。 (3)偏序集的哈斯圖分別在下圖給出。例13.2例13.2判斷下列偏序集是否構(gòu)成格,并說明理由。例13.2解答(1)是格。 x,y∈P(B)，x∨y就是x∪y，x∧y就是x∩y。 由于∪和∩運算在P(B)上是封閉的，所以x∪y，x∩y∈P(B)。 稱<P(B),>,為B的冪集格。(2)是格。 x,y∈Z,x∨y＝max(x,y)，x∧y＝min(x,y)，它們都是整數(shù)。(3)都不是格。 (a)中的{a,b}沒有最大下界。 (b)中的{b,d}有兩個上界c和e,但沒有最小上界。 (c)中的{b,c}有三個上界d,e,f,但沒有最小上界。 (d)中的{a,g}沒有最大下界。例13.2解答(1)是格。例13.3例13.3設(shè)G是群，L(G)是G的所有子群的集合。即 L(G)＝{H|H≤G} 對任意的H1,H2∈L(G)，H1∩H2也是G的子群，而<H1∪H2>是由H1∪H2生成的子群（即包含著H1∪H2的最小的子群）。 在L(G)上定義包含關(guān)系，則L(G)關(guān)于包含關(guān)系構(gòu)成一個格，稱為G的子群格。 易見在L(G)中，H1∧H2就是H1∩H2，H1∨H2就是<H1∪H2>。例13.3例13.3設(shè)G是群，L(G)是G的所有子群的集合對偶原理定義13.2設(shè)f是含有格中元素以及符號＝、≤、≥、∨和∧的命題。令f*是將f中的≤替換成≥，≥替換成≤，∨替換成∧，∧替換成∨所得到的命題。稱f*為f的對偶命題。例如 在格中令f是(a∨b)∧c≤c，則f*是(a∧b)∨c≥c。格的對偶原理設(shè)f是含有格中元素以及符號＝、≤、≥、∨和∧的命題。若f對一切格為真，則f的對偶命題f*也對一切格為真。例如

對一切格L都有 a,b∈L，a∧b≤a (因為a和b的交是a的一個下界) 那么對一切格L都有 a,b∈L，a∨b≥a說明 許多格的性質(zhì)都是互為對偶命題的。 有了格的對偶原理，在證明格的性質(zhì)時，

只須證明其中的一個命題即可。對偶原理定義13.2設(shè)f是含有格中元素以及符號＝、≤、≥、格的運算性質(zhì)定理13.1設(shè)<L,≤>是格，則運算∨和∧適合交換律、結(jié)合律、冪等律和吸收律，即 (1)交換律a,b∈L有 a∨b＝b∨a a∧b＝b∧a (2)結(jié)合律a,b,c∈L有 (a∨b)∨c＝a∨(b∨c) (a∧b)∧c＝a∧(b∧c) (3)冪等律a∈L有 a∨a＝a a∧a＝a (4)吸收律a,b∈L有 a∨(a∧b)＝a a∧(a∨b)＝a格的運算性質(zhì)定理13.1設(shè)<L,≤>是格，則運算∨和∧適合定理13.1(1)a∨b和b∨a分別是{a,b}和{b,a}的最小上界。 由于{a,b}＝{b,a}，所以a∨b＝b∨a。 由對偶原理，a∧b＝b∧a得證。(2)由最小上界的定義有 (a∨b)∨c≥a∨b≥a (13.1) (a∨b)∨c≥a∨b≥b (13.2) (a∨b)∨c≥c (13.3) 由式13.2和13.3有 (a∨b)∨c≥b∨c (13.4) 再由式13.1和13.4有 (a∨b)∨c≥a∨(b∨c) 同理可證 (a∨b)∨c≤a∨(b∨c) 根據(jù)偏序關(guān)系的反對稱性有 (a∨b)∨c＝a∨(b∨c) 由對偶原理，(a∧b)∧c＝a∧(b∧c)得證。定理13.1(1)a∨b和b∨a分別是{a,b}和{b,a}定理13.1(3)顯然a≤a∨a, 又由a≤a可得 a∨a≤a。 根據(jù)反對稱性有 a∨a＝a， 由對偶原理，a∧a＝a得證。(4)顯然 a∨(a∧b)≥a (13.5) 又由a≤a，a∧b≤a可得 a∨(a∧b)≤a (13.6) 由式13.5和13.6可得

a∨(a∧b)＝a， 根據(jù)對偶原理，a∧(a∨b)＝a得證。定理13.1(3)顯然a≤a∨a,定理13.2定理13.2設(shè)<S,*,>是具有兩個二元運算的代數(shù)系統(tǒng)，若對于*和運算適合交換律、結(jié)合律、吸收律，則可以適當(dāng)定義S中的偏序≤，使得<S,≤>構(gòu)成一個格，且a,b∈S有a∧b＝a*b，a∨b＝ab。思路

(1)證明在S中*和運算都適合冪等律。 (2)在S上定義二元關(guān)系R，并證明R為偏序關(guān)系。 (3)證明<S,≤>構(gòu)成格。說明 通過規(guī)定運算及其基本性質(zhì)可以給出格的定義。定理13.2定理13.2設(shè)<S,*,>是具有兩個二元運算定理13.2a∈S，由吸收律得(1)證明在S中*和運算都適合冪等律。a*a＝a*(a(a*a))＝a同理有aa＝a。(2)在S上定義二元關(guān)系R，a,b∈S有<a,b>∈Rab＝b下面證明R在S上的偏序。根據(jù)冪等律，a∈S都有aa＝a，即<a,a>∈R，所以R在S上是自反的。a,b∈S有aRb且bRaab＝b且ba＝aa＝ba＝ab＝b(由于ab=ba)所以R在S上是反對稱的。定理13.2a∈S，由吸收律得(1)證明在S中*和運算都定理13.2a,b,c∈S有 aRb且bRc ab＝b且bc＝c ac＝a(bc) ac＝(ab)c ac＝bc＝c aRc 這就證明了R在S上是傳遞的。 綜上所述，R為S上的偏序。 以下把R記作≤。定理13.2a,b,c∈S有定理13.2(3)證明<S，≤>構(gòu)成格。即證明a∨b＝ab，a∧b＝a*b。a,b∈S有a(ab)＝(aa)b＝abb(ab)＝a(bb)＝ab根據(jù)≤的定義有a≤ab和b≤ab，所以ab是{a,b}的上界。假設(shè)c為{a,b}的上界，則有ac＝c和bc＝c，從而有(ab)c＝a(bc)＝ac＝c這就證明了ab≤c，所以ab是{a,b}的最小上界，即a∨b＝ab為證a*b是{a,b}的最大下界，先證首先由ab＝b可知a*b＝a*(ab)＝a反之由a*b＝a可知ab＝(a*b)b＝b(b*a)＝b再由式(13.7)和≤的定義有a≤ba*b＝a，依照前邊的證明,類似地可證a*b是{a,b}的最大下界，即a∧b＝a*b。ab＝ba*b＝a (13.7)定理13.2(3)證明<S，≤>構(gòu)成格。即證明a∨b＝a格的等價定義根據(jù)定理13.2，可以給出格的另一個等價定義。定義13.3設(shè)<S,*,>是代數(shù)系統(tǒng)，*和是二元運算，如果*和滿足交換律，結(jié)合律和吸收律，則<S,*,>構(gòu)成一個格(lattice)。說明 格中的冪等律可以由吸收律推出。 以后我們不再區(qū)別是偏序集定義的格，

還是代數(shù)系統(tǒng)定義的格，而統(tǒng)稱為格L。格的等價定義根據(jù)定理13.2，可以給出格的另一個等價定義。格的性質(zhì)定理13.3

設(shè)L是格，則a,b∈L有 a≤ba∧b＝aa∨b＝b證明

先證a≤ba∧b＝a 由a≤a和a≤b可知，a是{a,b}的下界， 故a≤a∧b。顯然又有a∧b≤a。 由反對稱性得a∧b＝a。

再證a∧b＝aa∨b＝b。 根據(jù)吸收律有b＝b∨(b∧a) 由a∧b＝a得b＝b∨a,即a∨b＝b。

最后證a∨b＝ba≤b。 由a≤a∨b得a≤a∨b＝b。格的性質(zhì)定理13.3設(shè)L是格，則a,b∈L有格的性質(zhì)定理11.4設(shè)L是格，a,b,c,d∈L，若a≤b且c≤d，則 a∧c≤b∧d， a∨c≤b∨d證明 a∧c≤a≤b a∧c≤c≤d 因此，a∧c≤b∧d。 同理可證a∨c≤b∨d。格的性質(zhì)定理11.4設(shè)L是格，a,b,c,d∈L，若a≤例13.4

例13.4設(shè)L是格，證明a,b,c∈L有 a∨(b∧c)≤(a∨b)∧(a∨c)證明 由a≤a，b∧c≤b得 a∨(b∧c)≤a∨b 由a≤a，b∧c≤c得 a∨(b∧c)≤a∨c 從而得到a∨(b∧c)≤(a∨b)∧(a∨c)說明 在格中分配不等式成立。 一般說來，格中的∨和∧運算并不是滿足分配律的。例13.4

例13.4設(shè)L是格，證明a,b,c∈L有本節(jié)小結(jié)偏序集構(gòu)成格的條件：任意二元子集都有最大下界和最小上界。

格的實例：正整數(shù)的因子格，冪集格，子群格。格的性質(zhì)：對偶原理，格中算律（交換、結(jié)合、冪等、吸收），保序性，分配不等式。

格作為代數(shù)系統(tǒng)的定義。格的證明方法本節(jié)小結(jié)偏序集構(gòu)成格的條件：任意二元子集都有最大下界和最小上13.2子格與格同態(tài)定義13.4設(shè)<L,∧,∨>是格，S是L的非空子集，若S關(guān)于L中的運算∧和∨仍構(gòu)成格，則稱S是L的子格。例13.5設(shè)格L如右圖所示。令S1＝{a,e,f,g}S2＝{a,b,e,g}則S1不是L的子格，S2是L的子格。因為對于e和f,有e∧f＝c，但cS1。13.2子格與格同態(tài)定義13.4設(shè)<L,∧,∨>是格，S格同態(tài)定義13.5設(shè)L1和L2是格，:L1→L2，若