離散數(shù)學(xué)1第14與代數(shù)

1、離 散 數(shù) 學(xué)電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院示 范 性 軟 件 學(xué) 院16 九月 20222022/9/16第15章 格與布爾代數(shù)集合的表示方法2子格與格同態(tài)3特殊格4偏序格與代數(shù)格1格的性質(zhì)2布爾代數(shù)52022/9/1615.1 本章學(xué)習(xí)要求重點(diǎn)掌握一般掌握了解11 格的定義及性質(zhì)2 子格與格同態(tài)3 特殊格4 布爾代數(shù)31 斯通定理2 布爾函數(shù) 21 格與布爾代數(shù)的證明2022/9/16偏序格 efabdcabcd(a)(b)比較右邊兩個(gè)哈斯圖的不同？2022/9/16定義15.2.1設(shè)是一個(gè)偏序集，如果對(duì)任意a, bL，a, b都有最大下界和最小上界存在，則稱是格，簡(jiǎn)稱L是格。若L為有限

2、集，則稱格為有限格。暫且把由偏序關(guān)系定義的格稱為偏序格2022/9/16保交與保聯(lián)在格中，任取a, bG，則a, b的最大下界和最小上界都是惟一存在的，且均屬于L。用a*b表示a, b的最大下界，稱為a與b的保交，用ab表示a, b的最小上界，稱為a與b的保聯(lián)，即a*b = GLBa, b，ab = LUBa, b也可用和、和、和分別表示保交和保聯(lián) 2022/9/16例15.2.1（1）考慮偏序集，其中Z+是正整數(shù)，D是一個(gè)整除關(guān)系，問(wèn)此偏序集是否是一個(gè)格？（2）設(shè)A是一個(gè)集合，P(A)是A的冪集，*是集合上的包含關(guān)系，問(wèn)此偏序集是否是一個(gè)格？（3）考慮偏序集，其中D是一個(gè)整除關(guān)系，Sn是n的

3、所有因子的集合，問(wèn)此偏序集是否是一個(gè)格？（4）所有的全序集都是格？分析 判斷一個(gè)偏序集是否是格，要對(duì)L的所有2元子集看它是否都有最大下界和最小上界2022/9/16例15.2.1（續(xù)）分析 判斷一個(gè)偏序集是否是格，要對(duì)L的所有2元子集看它是否都有最大下界和最小上界解 （1）對(duì)a, bZ，有a*b = GLBa, b = GCDa, bZGCD表示a, b的最大公因子。ab = LUBa, b = LCMa, bZLCM表示a, b的最小公倍數(shù)。所以，是一個(gè)格。2022/9/16例15.2.1 解（續(xù)）（2）對(duì)S1，S2P(S)，有S1*S2 = GLBS1, S2 = S1S2P(S)S1S2

4、 = LUBS1, S2 = S1S2P(S)所以，是一個(gè)格。（3）由(1)可知：一定是一個(gè)格。舉例如下： 當(dāng)n = 6和n = 24時(shí)，有和是格。此時(shí)S6 = 1, 2, 3, 6，S24 = 1, 2, 3, 4, 6, 8, 12, 24，2022/9/16例15.2.1 解（續(xù)） 對(duì)a, bS6(或S24)，有a*b = GLBa, b= GCDa, bS6(或S24)ab = LUBa, b = LCMa, bS6(或S24)對(duì)應(yīng)的Hasse圖如圖 (a)和圖 (b)所示。61232412123684(a)(b)2022/9/16例15.2.1 解（續(xù)）（4）因?yàn)樵谌蚣校瑢?duì)任意a

5、, bL，都有a b或b a成立。若a b成立，則a, b有最大下界為a，最小上界為b；若b a成立，則a, b有最大下界為b，最小上界為a；故是一個(gè)格。2022/9/16例15.2.2判斷哈斯圖如下圖所示的幾個(gè)偏序集是否是格。(a)abcdefg(a)(b)abcde(c)abcdea(e)bcdea(d)bcdeba(f)cefd2022/9/16例15.2.2（續(xù)）a(g)bdfhceghadbcf(h)ge(i)abcdeffb(j)baceca(k)bdea(l)bcde2022/9/16例15.2.2（續(xù)）分析 圖 (h)中2元素子集g, h不存在最小上界，圖 (i)中2元素子集e

6、, f不存在最小上界，圖 (j)中2元素子集e, f不存在最小上界，圖 (k)中2元素子集a, b不存在最大下界，圖 (l)中2元素子集d, e不存在最大下界，因此它們都不是格。解 圖 (a)至(g)中的偏序集都是格，圖 (h)至(l)中的偏序集都不是格。2022/9/16定義15.2.2 設(shè)是具有兩個(gè)二元運(yùn)算的代數(shù)系統(tǒng)，如果運(yùn)算和滿足交換律、結(jié)合律和吸收律，則稱為格。 把由代數(shù)系統(tǒng)定義的格稱為代數(shù)格。2022/9/16例15.2.3 設(shè)A是一個(gè)集合，P(A)是A的冪集，和分別是集合的交和并運(yùn)算，試證明代數(shù)系統(tǒng)是一個(gè)格。證明 由集合的運(yùn)算性質(zhì)知，交和并運(yùn)算都滿足交換律、結(jié)合律和吸收律，因此由定

7、義15.2.2知，是一個(gè)格。2022/9/16定理15.2.1偏序格與代數(shù)格是等價(jià)的。證明 先證偏序格是代數(shù)格。設(shè)是一個(gè)格，*和分別是L上的保交和保聯(lián)。對(duì)任意a, bL，由最小上界和最大下界的惟一性知，a*b = b*a，ab = ba即*和都滿足交換律。2022/9/16定理15.2.1 證明（續(xù)）對(duì)任意a, b, cL，因?yàn)?a*b)*c a*b b，(a*b)*c c，所以(a*b)*c b*c又因?yàn)?a*b)*c a*b a，于是有(a*b)*c a*(b*c)同樣有，a*(b*c) (a*b)*c。故(a*b)*c = a*(b*c)即*滿足結(jié)合律。同理可證，滿足結(jié)合律。2022/9

8、/16定理15.2.1 證明（續(xù)）對(duì)任意a, bL，因?yàn)閍 a，a ab，所以a a*(ab)顯然a*(ab) a，故a*(ab) = a同理可證，a (a*b) = a。故*與滿足吸收律。綜上，是一個(gè)格。2022/9/16定理15.2.1證明（續(xù)）再證一個(gè)代數(shù)格是一個(gè)偏序格。設(shè)代數(shù)系統(tǒng)一個(gè)格，在L上定義一種關(guān)系“ ”如下： 對(duì)任意a, bL，有a b ab = a(1)分下面3步證明。（1）證明 是偏序關(guān)系。對(duì)任意aL，由吸收律有aa = a(a(aa) = a故a a，即關(guān)系 是自反的。 2022/9/16定理15.2.1證明（續(xù)）對(duì)任意a, bL，若a b，b a，有：ab = a，ab

9、 = b所以a = b，即關(guān)系 是反對(duì)稱的。對(duì)任意a, b, cL，若a b，b c，有ab = a, bc = b由結(jié)合律知ac = (ab)c = a(bc) = ab = a所以a c，即關(guān)系 是傳遞的。故 是偏序關(guān)系，即是偏序集。2022/9/16定理15.2.1 證明（續(xù)）（2）證明：對(duì)任意a, bL，有ab = a ab = b事實(shí)上，若有ab = a，則由吸收律ab = (ab)b = b反之，若ab = b，再由吸收律ab = a(ab) = a因此，a b ab = a ab = b。2022/9/16定理15.2.1證明（續(xù)）（3）證明：對(duì)任意a, bL，a, b存在最大下

10、界和最小上界。由吸收律a(ab) = a a abb(ab) = b b ab因此，ab是a, b的一個(gè)上界。設(shè)cL是a, b的任意一個(gè)上界，即a c，b c，于是有ac = c，bc = c2022/9/16定理15.2.1證明（續(xù)）由結(jié)合律知(ab)c = a(bc) = ac = c故有ab c，即ab是a, b的最小上界。同理，ab是a, b的最大下界。故是一個(gè)格。且有a*b = ab， ab = ab注意：偏序格與代數(shù)格等價(jià)，今后就不再區(qū)分偏序格與代數(shù)格了，而把它們統(tǒng)稱為格。2022/9/16自然運(yùn)算與自然偏序任何偏序格都存在兩個(gè)二元運(yùn)算保交(*)和保聯(lián)()，稱之為格的自然運(yùn)算；代數(shù)

11、格都可以得到一個(gè)偏序關(guān)系 ，稱之為格的自然偏序。2022/9/16對(duì)偶格對(duì)于集合L的任何偏序關(guān)系“ ”，其逆關(guān)系“”也是集合L上的偏序關(guān)系；對(duì)L的任意子集T，T在偏序集中的最大下界和最小上界分別是中的最小上界和最大下界。因此偏序集是格當(dāng)且僅當(dāng)是格，我們稱此兩個(gè)格為對(duì)偶格；格的保聯(lián)運(yùn)算與保交運(yùn)算分別是對(duì)偶格的保交運(yùn)算和保聯(lián)運(yùn)算。2022/9/16對(duì)偶原理 對(duì)于格的任何命題，將保聯(lián)運(yùn)算與保交運(yùn)算分別換成對(duì)偶格的保交運(yùn)算和保聯(lián)運(yùn)算，將命題中的“ ”換成對(duì)偶格中的“”，得到的一個(gè)關(guān)于對(duì)偶格中的命題，稱這個(gè)命題為對(duì)偶命題。 容易證明，關(guān)于格的任何真命題，其對(duì)應(yīng)的對(duì)偶命題在對(duì)偶格中也是真命題，把這個(gè)原理稱

12、為對(duì)偶原理。2022/9/16性質(zhì)15.2.1設(shè)是格，“ ”是“ ”的逆關(guān)系。則對(duì)任意a, b, c, dL，有（1）自反性：a a；aa（2）反對(duì)稱性：a b且b aa = b ab且ba a = b （3）傳遞性：a b且b c a c； ab且bcac（4）a*b a；ab a（5）c a且c b c a*b； ca且cbcab2022/9/16性質(zhì)15.2.1（續(xù)）（6）交換律：a*b = b*a；ab = ba。（7）結(jié)合律：(a*b)*c = a* (b*c)； (ab) c = a (bc) （8）吸收律：a* (ab) = a； a (a*b) = a（9）冪等律：a*a =

13、a；aa = a（10）a b a*b = a ab = b2022/9/16性質(zhì)15.2.1（續(xù)）（11）a b且c da*c b*d； a b且c dac bd（12）保序性：a b a*c b*c； a b ac bc（13）分配不等式： a (b*c) (ab) * (ac)； a* (bc)(a*b) (a*c) （14）模不等式： a c a (b*c) (ab) *c2022/9/16性質(zhì)15.2.1 證明性質(zhì)(1)、(2)、(3) (4)、(5)直接可得。性質(zhì)(6)、(7)、(8)由定理15.2.1的直接得到。性質(zhì)(9)由性質(zhì)(8)得到：a*a = a*(a(a*a) = a，

14、aa = a (a*(aa) = a。性質(zhì)(10)由最大下界和最小上界的定義直接得到。性質(zhì)(11)：因a*c a，a*c c，由假設(shè)a b，c d，利用傳遞性得a*c b，a*c d，由性質(zhì)(5)得a*c b*d；同理可證，ac bd。性質(zhì)(12)是性質(zhì)(11)中c = d的特殊情況。2022/9/16性質(zhì)15.2.1 證明（續(xù)）性質(zhì)(13)：因a*b a，ac a，所以(ab) (ac) a由于ab b，ac c，由性質(zhì)11得(ab) (ac) bc故(ab) (ac) a (bc)，即a(bc)(ab)(ac)2022/9/16性質(zhì)15.2.1 證明（續(xù)）性質(zhì)(14)：必要性：若a c，則

15、ac = c，由性質(zhì)13得a (bc) (ab)c充分性：若a (bc) (ab) c，因a a(bc)，(ab)c c由傳遞性得a c。2022/9/16定義15.2.3設(shè)代數(shù)系統(tǒng)是一個(gè)格，S L，若S滿足：（1）S；（2）運(yùn)算和對(duì)子集S都是封閉的；則稱是的子格，簡(jiǎn)稱S是L的子格。2022/9/16例15.2.4在正整數(shù)集合Z+中規(guī)定、為：對(duì)任意a, bP，ab = a, b，其中a, b表示a, b的最小公倍數(shù)ab = (a, b)，其中(a, b)表示a, b的最大公因數(shù)則, 是Z+上的二元運(yùn)算，且滿足交換律、結(jié)合律、吸收律和等冪律，于是是一個(gè)格。S = 3k | kZ+Z+，試證明是的

16、子格。2022/9/16例15.2.4 證明顯然S。因?yàn)閷?duì)任意3m, 3nS，都有3m3n = 3m, 3n = 3m, nS，3m3n = (3m, 3n) = 3(m, n)S所以，是的子格。2022/9/16子格定義15.2.4 設(shè)是一個(gè)格，S L，若S滿足：（1）S；（2）對(duì)任意a, bS， 的保交和保聯(lián)運(yùn)算都有ab = GLBa, bS，ab = LUBa, bS，則稱是的一個(gè)子格，簡(jiǎn)稱S是L的子格。2022/9/16例15.2.5在如下圖 (a)所示的偏序格中，考慮如下子集：B1 = a, b, g, h，B2 = a, b, c, d，B3 = a, b, d, h ，問(wèn)B1，B

17、2，B3中那些是的子格？habca(a)bdfhceg(b)2022/9/16例15.2.5（續(xù)）分析 顯然B1，B2，B3都是L的非空子集，B1是L的子格；B2的2元素子集b, c的最小上界e不在B2中，因此B2不是L的子格；B3的2元素子集b, c的最小上界e不在B3中，因此B3不是L的子格。注意，偏序集的哈斯圖如上圖 (b)所示，因此是格。即存在子集關(guān)于偏序能構(gòu)成格，但不是子格，主要原因是它們的保交或保聯(lián)運(yùn)算不一樣。解 B1是L的子格，B2, B3, B4都不是L的子格。2022/9/16例15.2.5設(shè)是一個(gè)格，aL，令S = x|xL, x a，則S是L的子格。證明 因?yàn)閍 a，所以

18、aS，即S是非空子集。對(duì)任意x, yS，由x a，y a，可知xy = GLBx, y a，即xy = GLBx, ySxy = LUBx, y a，即xy = LUBx, yS故S是L的子格。 2022/9/16定義15.2.5設(shè)和是兩個(gè)格，f是L到S的映射。如果對(duì)任意x, yL，都有f(xy) = f(x)* f(y)，f(xy) = f(x) f(y)則稱f為從格到格的格同態(tài)映射，簡(jiǎn)稱格同態(tài)。如果f是格同態(tài)，當(dāng)f分別是單射、滿射和雙射時(shí)，f分別稱為單一格同態(tài)、滿格同態(tài)和格同構(gòu)。2022/9/16定理15.2.3 (保序定理)設(shè)和是兩個(gè)格，對(duì)應(yīng)的偏序關(guān)系為 1、 2，則有：（1）如f：L1

19、L2是格同態(tài)，則對(duì)任意a, bL1，a 1 b f(a) 2 f(b)；（2）如f：L1L2是格同構(gòu)，則對(duì)任意a, bL1，a 1 b f(a) 2 f(b)。證明 （1）對(duì)任意a, bL1，若a 1b，則有a*1b = a，由同態(tài)式知：f(a)*2f(b) = f(a*1b) = f(a)所以f(a) 2f(b)。2022/9/16定理15.2.3（續(xù)）（2）“”：若f是格同構(gòu)，則f是格同態(tài)。由(1)知：對(duì)任意a, bL1，a 1b f(a) 2f(b)?！啊保簩?duì)任意a, bL1，有f(a) 2 f(b) f(a)*2f(b) = f(a)于是，由同態(tài)式知f(a*1b) = f(a)*2f(

20、b) = f(a)因f是單射，故有a*1b = a所以，a 1b。2022/9/16例15.2.6設(shè)是格，其中L = a, b, c, d, e，它的Hasse圖如右圖所示。也是一個(gè)格。作映射f：LP(L)，使得對(duì)任意xL，有f(x) = yyL，y x試證明：f是保序映射，但不是格同態(tài)。ebcda2022/9/16例15.2.6（續(xù)）分析 要證明f是保序映射，必須驗(yàn)證：對(duì)任意x, yL，xy f(x) f(y)。而證明f不是格同態(tài)，只需要找到一對(duì)x, yL，使得f(xy)f(x)f(y) 。證明 容易驗(yàn)證f是保序映射。對(duì)于b, dL，有bd = a，f(bd) = f(a) = L，而f(b

21、)f(d) = b, ed, e = b, d, e所以，f(bd)f(b)f(d)，即f不是格同態(tài)。2022/9/16定義15.2.6設(shè)是一個(gè)格，如果對(duì)任意a, b, cL，都有a (bc) = (ab) (ac) ， a (bc) = (ab) (ac)，即運(yùn)算滿足分配律，則稱是一個(gè)分配格。2022/9/16例15.2.7（1）設(shè)A為任意一個(gè)集合，格是否是分配格？（2）設(shè)P為命題公式集合，與分別是命題公式的合取與析取運(yùn)算，格是否是分配格？解 （1）因集合的交、并運(yùn)算滿足分配律，所以，格是一個(gè)分配格。（2）因命題公式的析取、合取運(yùn)算滿足分配律，所以，格是分配格。2022/9/16定理15.2

22、.4所有鏈都是分配格。證明 設(shè)是鏈，因此是格，任取a, b, cL，只有以下兩種情況：（1）a是三者中最大的，即b a，c a；（2）a不是三者中最大的，即a b或a c。在情況(1)中，bc a，故a (bc) = bc。顯然，ab = b，ac = c。所以a (bc) = bc = (ab) (ac)。2022/9/16定理15.2.4（續(xù)）在情況(2)中，a bc，而ab = a或ac = a，從而(ab) (ac) = a，所以(ab) (ac) = a = a (bc) 所以是分配格。 2022/9/16例15.2.8右圖所示的兩個(gè)格都不是分配格。分析 由于鏈?zhǔn)欠峙涓?，因此在同一條

23、鏈上的元素都滿足分配等式，最有可能不滿足分配等式的元素不在同一條鏈上。選取b, c, d來(lái)驗(yàn)證即可。a(b)bcdea(a)bcde2022/9/16例15.2.8（續(xù)）解 取圖中b, c, d三個(gè)元素驗(yàn)證。在圖 (a)中，b (cd) = ba = b，而(bc) (bd) = ee = e。在圖 (b)中，b (cd) = ba = b，而(bc) (bd) = ed = d。因此，在圖 (a)和(b)中都有，b (cd)(bc) (bd)故它們都不是分配格。2022/9/16定理15.2.5一個(gè)格是分配格的充分必要條件是該格中沒(méi)有任何子格與圖15.2.7（例15.2.8）中的兩個(gè)五元素格

24、中的任何一個(gè)同構(gòu)。2022/9/16性質(zhì)15.2.2（1）四個(gè)元素以下的格都是分配格；（2）五個(gè)元素的格僅有兩個(gè)格是非分配格(圖15.2.7(a)和(b)，其余三個(gè)格(右圖 (a), (b)和(c)都是分配格。(a)(a)abcde(b)abcde(c)abcde2022/9/16定理15.2.6設(shè)是分配格，對(duì)于任何a, x, yL，如果ax = ay且ax = ay，則x = y。證明 x = x (ax)(吸收律)= x (ay)(已知ax = ay)= (xa) (xy)(分配律)= (ay) (xy)(已知ax = ay)= y (ax)(交換律，分配律)= y (ay)(已知ax =

25、 ay)= y(吸收律)2022/9/16定義15.2.7設(shè)是格，如果對(duì)任意a, b, cL，有a b a (bc) = b (ac) 或(模律) a b a (bc) = b (ac)則稱為模格，也稱為戴德金格 2022/9/16定理15.2.7分配格是模格。證明 設(shè)是分配格，對(duì)任意a, b, cL，如果a b，那么ab = b，由分配律得 a (bc) = (ab)(ac) = b(ac)故是模格。2022/9/16性質(zhì)13.2.3（1)每一個(gè)鏈格都是模格；（2）四個(gè)元素以下的格都是模格；（3）五個(gè)元素的格僅有一個(gè)格不是模格(圖15.2.7(b)，其余四個(gè)格(圖15.2.7(a), 圖15

26、.2.8(a), (b)和(c)都是模格。 2022/9/16定義15.2.8設(shè)是一個(gè)格，若存在元素aL，使得對(duì)任意xL，都有：a x(或x a)，則稱a為格的全下界(或全上界)，分別記為0(或1)，具有全上界和全下界的格稱為有界格。顯然，對(duì)任意xL，有1x = x1 = x，1x = x1 = 10 x = x0 = 0，0 x = x0 = x2022/9/16有限格與有界格若是有限格，設(shè)L = a1, a2, , an，由于運(yùn)算“”和“”滿足結(jié)合律，所以有(a1a2)an) = a1a2an(a1a2)an) = a1a2an此時(shí)， a1a2an和a1a2an分別是格L的全下界和全上界，

27、即有a1a2an = 0a1a2an = 1所以，有限格一定是有界格。2022/9/16定理15.2.8 在格中，全下界和全上界分別是集合L的最小元和最大元，由于最大元和最小元的惟一性，有下面的定理： 定理15.2.8 設(shè)是一個(gè)格，若格的全上界和全下界存在，則必惟一。2022/9/16定義15.2.9 設(shè)為有界格，1和0分別為它的全上界和全下界，aL。如果存在bL，使得ab = 0，ab = 1，則稱b為a的補(bǔ)元，記為a。 若有界格中的所有元素都存在補(bǔ)元，則稱為有補(bǔ)格。2022/9/16例15.2.9如下圖有界格，求其所有元素的補(bǔ)元(如果有的話)。a0(b)bd1c0(a)abd1ce2022

28、/9/16例15.2.9（續(xù)）解 對(duì)于圖a 0 = 1，1 = 0， a = e，c = e， c = d，e = a， d無(wú)補(bǔ)元。 對(duì)于圖b 0 = 1，1 = 0， a = d，a = c， b = d，b = c， c = a，c = b， d = a，d = b則圖a不是有補(bǔ)格，圖b是有補(bǔ)格。2022/9/16定理15.2.9 在有界分配格(既是有界格又是分配格，簡(jiǎn)稱為有界分配格)中，如元素aL有補(bǔ)元存在，則此元素的補(bǔ)元必惟一。證明 設(shè)a有兩個(gè)補(bǔ)元b和c，由補(bǔ)元的定義知ab = 0 = ac，ab = 1 = ac由定理15.2.6知，b = c。推論15.2.1 在有補(bǔ)分配格(既是有

29、補(bǔ)格又是分配格，簡(jiǎn)稱為有補(bǔ)分配格)中，每個(gè)元素都存在惟一的補(bǔ)元。2022/9/16定理15.2.10設(shè)是有補(bǔ)分配格，“ ”是該格的自然偏序，則對(duì)任意a, bL，都有（1）(a) = a；(對(duì)合律)（2）(ab ) = a b ， (ab) = ab； (De Morgan律)（3）a b b a；（4）a b ab = 0 ab = 1。2022/9/16定理15.2.10（續(xù)）證明 （1）因a是a的補(bǔ)元，反過(guò)來(lái)，a也是a的補(bǔ)元，由推論15.2.1得，(a) = a。（2）因?yàn)?ab) (ab)= (ab) a) (ab) b)(分配律)= (aa)b) (a (bb)(交換律，結(jié)合律)= (

30、0b) (a0)= 00 = 02022/9/16定理15.2.10（續(xù)）(ab) (ab)= (a (ab) * (b (ab)(分配律)= (aa) b) * (a (bb)(交換律，結(jié)合律)= (1b) (a1)= 11 = 1所以， ab是ab的補(bǔ)元，由補(bǔ)元的惟一性得，(ab) = ab。同理可證，(ab) = ab。2022/9/16定理15.2.10（續(xù)）（3）“”，由a b，可得ab = a，則有(ab) = a由De Morgan律(即(2)，有ab = a ，即是b a“”，上述過(guò)程可逆，故成立。 （4）“”由a b，根據(jù)(3)，有b a則ab aa = 0，即是2022/9

31、/16定理15.2.10（續(xù)）ab 0，又0是全下界，有0 ab則根據(jù)偏序關(guān)系“ ”的反對(duì)稱性，有ab = 0，對(duì)上式使用De Morgan律，自然有ab = 12022/9/16定理15.2.10（續(xù)）“”如果ab = 1，由De Morgan律，有ab = 0，則有a(ab) = a0 = a對(duì)上式的左邊使用分配律，可得a(ab) = (aa) (ab) = 1 (ab) = ab即是 ab = a，所以有 b a，由(3)可得a b。2022/9/16定義15.3.1稱有補(bǔ)分配格為布爾格。在有補(bǔ)分配格中每個(gè)元都有補(bǔ)元而且補(bǔ)元惟一，可以將求元素的補(bǔ)元作為一種一元運(yùn)算，則此布爾格可記為，此時(shí)

32、，稱為布爾代數(shù)。因此有：定義15.3.2 一個(gè)布爾格稱為布爾代數(shù)。若一個(gè)布爾代數(shù)的元素個(gè)數(shù)是有限的，則稱此布爾代數(shù)為有限布爾代數(shù)，否則稱為無(wú)限布爾代數(shù)。2022/9/16布爾代數(shù) 布爾代數(shù)是有補(bǔ)分配格，有補(bǔ)分配格必須滿足它是格、有全上界和全下界、分配律成立、每個(gè)元素都有補(bǔ)元存在。顯然，全上界1和全下界0可以用下面的同一律來(lái)描述：同一律：在L中存在兩個(gè)元素0和1，使得對(duì)任意aL，有a1 = a，a0 = a。2022/9/16布爾代數(shù)補(bǔ)元的存在可以用下面的互補(bǔ)律來(lái)描述?；パa(bǔ)律：對(duì)任意aL，存在aL，使得aa = 0，aa = 1。 格可以用交換律、結(jié)合律、吸收律來(lái)描述。因此，一個(gè)有補(bǔ)分配格就必須滿足交換律、結(jié)合律、吸收律、分配律、同一律、互補(bǔ)律。另外，可以證明，由交換律、分配律、同一律、互補(bǔ)律可以得到結(jié)合律、吸收律。所以布爾代數(shù)有下面的等價(jià)定義： 2022/9/16定義15.2.3設(shè)是代數(shù)系統(tǒng)，其中、是B中的二元運(yùn)算，如果對(duì)任意a, b, cB，滿足（1）交換律：ab = ba，ab = ba；