第七章格和布爾代數(shù)精簡

格與布爾代數(shù)主講：魚亮西安電子科技大學(xué)多媒體研究所yuliang@西安電子科技大學(xué)多媒體研究所yuliang@12023/2/6第七章格與布爾代數(shù)7.1

格7.2

子格和格同態(tài)7.3

特殊的格7.4

布爾代數(shù)與布爾表達(dá)式西安電子科技大學(xué)多媒體研究所yuliang@22023/2/67.1格格的定義：設(shè)<L,≤>是一個偏序集，如果集合L中的任意兩個元素都有最小上界和最大下界，則稱<L,≤>為格。西安電子科技大學(xué)多媒體研究所yuliang@32023/2/67.1格【例題1】判斷下圖中所示各哈斯圖代表的偏序集合是否是格？為什么？abcdefabcdeabcdefabcdabcdabcdefghabcdeabcde西安電子科技大學(xué)多媒體研究所yuliang@42023/2/67.1格【例題2】設(shè)I+是正整數(shù)集合，定義I+上的二元關(guān)系“|”,任取a,b∈I+,a|b當(dāng)且僅當(dāng)a能整除b。證明:<I+,|>是一個格。證明：I+上的二元關(guān)系|是自反、反對稱和傳遞的，因此<I+,|>是一個偏序集合。任取a,b∈I+,

a與b在偏序集合<I+,|>中的最小上界是其最小公倍數(shù):lub{a,b}∈I+。任取a,b∈I+,a與b在偏序集合<I+,|>中的最大下界是其最大公約數(shù)：glb{a,b}∈I+。結(jié)論得證。西安電子科技大學(xué)多媒體研究所yuliang@52023/2/67.1格【例題3】設(shè)S是任意集合，ρ(S)是S的冪集，偏序集合<ρ(S),>是否是格？解答:任取A,B∈ρ(S),

A與B在偏序集合<ρ(S),>中的最小上界是A∪B∈ρ(S),A與B在偏序集合

<ρ(S),>中的最大下界是A∩B∈ρ(S)。西安電子科技大學(xué)多媒體研究所yuliang@62023/2/67.1格保交運(yùn)算

a∧b=glb{a,b},求a,b的最大下界保聯(lián)運(yùn)算

a∨b=lub{a,b},求a,b的最小上界『定理』(格的對偶定理)如果<L,≤>是一個格，則<L,≥>也是一個格。設(shè)P是一個命題，P的對偶命題P*是將關(guān)系符≤換成≥，將保交∧與保聯(lián)∨運(yùn)算符互換所得的命題。若P中對一切格都為真，則P*對一切格也都為真。西安電子科技大學(xué)多媒體研究所yuliang@72023/2/67.1格【例題】設(shè)<L,≤>是一個格,其哈斯圖如下圖所示，畫出<L,≥>的哈斯圖。解答：<L,≥>是<L,≤>的對偶格，因此其哈斯圖可由<L,≤>旋轉(zhuǎn)180°得到，如(b)圖所示。(a)(b)西安電子科技大學(xué)多媒體研究所yuliang@82023/2/67.1代數(shù)格代數(shù)格：設(shè)<L,≤>是一個格，a,b∈L。在L上可以定義兩個運(yùn)算*和：

a*b=glb{a,b}

也可寫成a∧b=glb{a,b}

ab=lub{a,b}

也可寫成a∨b=lub{a,b}

則稱<L,*,>(或<L,∧,∨>)為格<L,≤>所誘導(dǎo)的代數(shù)系統(tǒng)，簡稱代數(shù)格。西安電子科技大學(xué)多媒體研究所yuliang@92023/2/67.1代數(shù)格的性質(zhì)『定理1』在一個格<A,≤>中，對任意的a,b∈A,都有

a≤a∨b,b≤a∨b

a∧b≤a,a∧b≤b證明：因為a和b的并是a的一個上界，所以

a≤a∨b

同理b≤a∨b

由對偶原理即得a∧b≤a,a∧b≤b西安電子科技大學(xué)多媒體研究所yuliang@102023/2/67.1代數(shù)格的性質(zhì)『定理2』在一個格<A,≤>中，對于a,b,c,d∈A,如果a≤b

和c≤d

則a∨c≤b∨d

a∧c≤b∧d證明：因為b≤b∨d,d≤b∨d,由傳遞性可得a≤b∨d,c≤b∨d

這就表明b∨d是a和c的一個上界，而a∨c

是a和c的最小上界，所以，必有西安電子科技大學(xué)多媒體研究所yuliang@112023/2/67.1代數(shù)格的性質(zhì)

a∨c≤b∨d

類似地可以證明a∧c≤b∧d西安電子科技大學(xué)多媒體研究所yuliang@122023/2/67.1代數(shù)格的基本性質(zhì)由格誘導(dǎo)的代數(shù)系統(tǒng)滿足以下性質(zhì)：(1)自反性a≤a(2)反對稱性(a≤b)且

(b≤a)a=b(3)傳遞性(a≤b)且

(b≤c)a≤c(4)a∧b≤a,a∧b≤b

a≤a∨b,b≤a∨b(5)(c≤a)

且(c≤b)c≤(a∧b),

(b≤c)且(a≤c)

c≥(a∨b)(6)交換律a∧b=b∧a

a∨b=b∨a西安電子科技大學(xué)多媒體研究所yuliang@132023/2/67.1代數(shù)格的基本性質(zhì)(7)結(jié)合律(a∧b)∧c=a∧(b∧c),

(a∨b)∨c=a∨(b∨c)(8)等冪律a∧a=a,

a∨a=a

(9)吸收律a∧(a∨b)=a,a∨(a∧b)=a(10)a≤ba∧b=aa∨b=b(11)a≤b

且d≤c

a∧d≤b∧c

a≤b

且d≤c

a∨d≤b∨c西安電子科技大學(xué)多媒體研究所yuliang@142023/2/67.1代數(shù)格的基本性質(zhì)(12)保序性b≤ca∧b≤a∧c,

b≤ca∨b≤a∨c(13)分配不等式a∨(b∧c)≤(a∨b)∧(a∨c)a∧(b∨c)≥(a∧b)∨(a∧c)

(14)模不等式a≤ca∨(b∧c)≤(a∨b)∧c證明：(7)由定理1可知

b≤b∨c≤a∨(b∨c)

和a≤a∨(b∨c)

西安電子科技大學(xué)多媒體研究所yuliang@152023/2/67.1代數(shù)格的基本性質(zhì)由定理2可知

a∨b≤a∨(b∨c)

又因c≤b∨c≤a∨(b∨c)

說明a∨(b∨c)

是a∨b和c的上界,而(a∨b)∨c是a∨b和c的最小上界，因此

(a∨b)∨c≤a∨(b∨c)類似得可以證明

a∨(b∨c)≤(a∨b)∨c因此a∨(b∨c)=(a∨b)∨c

由對偶原理可得a∧(b∧c)=(a∧b)∧c

西安電子科技大學(xué)多媒體研究所yuliang@162023/2/67.1代數(shù)格的基本性質(zhì)(8)由定理1可知a≤a∨a由自反性可知a≤a由此可得a∨a≤a因此a∨a=a利用對偶原理可得a∧a=a(9)根據(jù)定理1可得a≤a∨(a∧b)因為a≤a,a∧b≤a

因此a∨(a∧b)≤a所以a∨(a∧b)=a利用對偶原理，即得a∧(a∨b)=a西安電子科技大學(xué)多媒體研究所yuliang@172023/2/67.1代數(shù)格的基本性質(zhì)(10)首先證明a≤ba∧b=a因為a≤b和a≤a,就有a≤a∧b,但由定理1可知a∧b≤a,由反對稱性，得a∧b=a。這就證明了a≤ba∧b=a。反之，假定a∧b=a，則a=a∧b≤b,這就證明了a∧b=aa≤b因此a≤ba∧b=a用同樣得方法可以a≤ba∨b=b西安電子科技大學(xué)多媒體研究所yuliang@182023/2/67.1代數(shù)格的基本性質(zhì)最后證明a∧b=aa∨b=b根據(jù)定理1可知a∨b≥b,而a∧b≤b,因為a∧b=a,故a≤b,而b≤b,因此a∨b≤b,這樣就得到了a∨b=b，即a∧b=aa∨b=b。反之，假定a∨b=b,由定理1可知a∧b≤a,因為a∨b=b，故b=a∨b≥a,而a≥a,因此a∧b≥a,這樣就得到了a∧b=a,即a∨b=ba∧b=a

。因此得到a∧b=aa∨b=b西安電子科技大學(xué)多媒體研究所yuliang@192023/2/67.1代數(shù)格的基本性質(zhì)(13)由定理1可知a≤a∨b和a≤a∨c,由定理2可知

a≤(a∨b)∧(a∨c)(1)另外由于b∧c≤b≤a∨b,b∧c≤c≤a∨c,故b∧c≤(a∨b)∧(a∨c)(2)

因此由(1)、(2)可得：a∨(b∧c)≤(a∨b)∧(a∨c)

利用對偶原理，即得

a∧(b∨c)≥(a∧b)∨(a∧c)

西安電子科技大學(xué)多媒體研究所yuliang@202023/2/67.1代數(shù)格的基本性質(zhì)(14)由性質(zhì)(10)有a≤c(a∨c)=c

再由性質(zhì)(13)有a∨(b∧c)≤(a∨b)∧(a∨c)

用c替代上式中的(a∨c)，即得

a∨(b∧c)≤(a∨b)∧c所以a≤ca∨(b∧c)≤(a∨b)∧c另外，若a∨(b∧c)≤(a∨b)∧c,則明顯地有

a≤a∨(b∧c)≤(a∨b)∧c≤c所以a∨(b∧c)≤(a∨b)∧ca≤c

因此a≤ca∨(b∧c)≤(a∨b)∧c西安電子科技大學(xué)多媒體研究所yuliang@212023/2/67.1格『定理』設(shè)<A,∧,∨>是一個代數(shù)系統(tǒng)，其中運(yùn)算∧和∨都滿足吸收律，則運(yùn)算∧和∨都滿足等冪律。證明：由于∧和∨都滿足吸收律，則任取a,b∈A,有a∧(a∨b)=a(1)

a∨(a∧b)=a(2)將(1)式中的b用(a∧b)替換得

a∧(a∨(a∧b))=a∧a=a

西安電子科技大學(xué)多媒體研究所yuliang@222023/2/67.1格將(2)式中的b用(a∨b)替換得到

a∨(a∧(a∨b))=a∨a=a

故∧和∨都滿足等冪律。西安電子科技大學(xué)多媒體研究所yuliang@232023/2/67.1格『定理』設(shè)<A,∧,∨>是一個代數(shù)系統(tǒng)，其中∧和∨都是二元運(yùn)算且滿足交換律、結(jié)合律、吸收律，則A上存在偏序關(guān)系≤，使得<A,≤>是一個格。證明：在A上定義二元關(guān)系≤為：任取a,b∈A,a≤b

當(dāng)且僅當(dāng)a∧b=a。(i)證明≤是一個偏序關(guān)系。西安電子科技大學(xué)多媒體研究所yuliang@242023/2/67.1格任取a,b∈A,a∧a=a,根據(jù)≤的定義可知a≤a,因此a是自反的。設(shè)a≤b,b≤a,則a∧b=a=b,因此≤是反對稱的。設(shè)a≤b,b≤c,則有

a∧b=a

和b∧c=ba∧c=(a∧b)∧c=a∧(b∧c)=a∧b=a則有a≤c。因此≤是傳遞的。因此可知<A,

≤>是一個偏序集合。

西安電子科技大學(xué)多媒體研究所yuliang@252023/2/67.1格(ii)證明任取a,b∈A,a和b存在最小上界和最大下界。因為(a∧b)∧a=a∧b∧a=a∧b(a∧b)∧b=a∧b∧b=a∧b因此a∧b≤a,a∧b≤ba∧b是a和b的下界。西安電子科技大學(xué)多媒體研究所yuliang@262023/2/67.1格設(shè)c是a和b的任意下界，即有c≤a且c≤b,則有

c∧a=c且c∧b=c而c∧(a∧b)=(c∧a)∧b=c∧b=c所以有c≤a∧b。由此可知，a∧b是a和b的最大下界。同理可證，a∨b是a和b的最小上界。由(i)、(ii)可知，<A,

≤>是一個格。西安電子科技大學(xué)多媒體研究所yuliang@272023/2/67.2子格子格：設(shè)<L,≤>是一個格，<L,∧,∨>是由<L,≤>所誘導(dǎo)的代數(shù)系統(tǒng)。SL且S≠,

如果L中的兩個運(yùn)算∧和∨在S上是封閉的，則稱<S,≤>是<L,≤>的子格。

格<L,≤

>載體L的一個子集S如果對原保交和保聯(lián)運(yùn)算都封閉，稱<S,≤>是<L,≤>的子格。子格是子代數(shù)的概念在格上的擴(kuò)展。西安電子科技大學(xué)多媒體研究所yuliang@282023/2/67.2子格【例題】圖(a)、(b)中所示的格<S’,≤>分別是格<S,≤>的子格嗎？(a)abdcedeab<S,≤><S’,≤>(b)一個格中的部分元素在原偏序關(guān)系上構(gòu)成一個格，不能說明它就是原格的子格。主要看該子集上的任意兩個元素在原運(yùn)算保交和保聯(lián)下的結(jié)果是否也在該子集中。<S,≤>abecdffacd<S’,≤>e西安電子科技大學(xué)多媒體研究所yuliang@292023/2/67.2格同態(tài)格同態(tài)：設(shè)<L1,≤>和<L2,≤>是兩個格，由它們所分別誘導(dǎo)的代數(shù)系統(tǒng)為<L1,∧,∨>和<L2,∧’,∨’>,其中∧和∧’是保交運(yùn)算,∨和∨’是保聯(lián)運(yùn)算。如果存在一個從L1到L2的映射f,使得任取a,b∈L1滿足

f(a∧b)=f(a)∧’f(b)f(a∨b)=f(a)∨’f(b)則稱f為從<L1,≤>到<L2,≤>的格同態(tài)，稱<f(L1),≤>為<L1,≤>的同態(tài)象。西安電子科技大學(xué)多媒體研究所yuliang@302023/2/67.2格同態(tài)【例題】設(shè)集合A={a,b,c},<A,≤>是一個格，其哈斯圖如圖(a)所示。集合B=(A),<B,>也是一個格，其哈斯圖如圖(b)所示。函數(shù)f:A→B,其中f(x)={y|y≤x}。證明:f是從<A,≤>到<B,>的格同態(tài)。(a)(b)abc{c}西安電子科技大學(xué)多媒體研究所yuliang@312023/2/67.2格同態(tài)證明：<A,≤>是一個格，設(shè)其誘導(dǎo)的代數(shù)格為<A,∧,∨>，任取a,b∈A,因為<A,≤>是一個鏈，所以a∧b=min{a,b}a∨b=max{a,b}<B,>誘導(dǎo)的代數(shù)格為<B,∩,∪>。(i)A中元素在函數(shù)f下的象分別為

f(a)={a},f(b)={a,b},f(c)={a,b,c}故f是從A到B的單射函數(shù)。西安電子科技大學(xué)多媒體研究所yuliang@322023/2/67.2格同態(tài)(ii)f(x1∧x2)=f(min{x1,x2})={y|y≤min{x1,x2}}={y|y≤x1}∩{y|y≤x2}=f(x1)∩f(x2)

f(x1∨x2)=f(max{x1,x2})={y|y≤max{x1,x2}}={y|y≤x1}∪{y|y≤x2}=f(x1)∪f(x2)故f是從<A,≤>到<B,>的格同態(tài)。西安電子科技大學(xué)多媒體研究所yuliang@332023/2/67.2格同態(tài)性質(zhì)『定理』(格同態(tài)的保序性)設(shè)f是從格

<L1,≤>到格<L2,≤’>的格同態(tài)，則對任意x,y∈L1,如果x≤y,必有f(x)≤’f(y)。

證明：因為x≤y，所以有x∧y=x,又

f(x∧y)=f(x)∧’f(y)=f(x)

故f(x)≤’f(y)。西安電子科技大學(xué)多媒體研究所yuliang@342023/2/67.2格同構(gòu)格同構(gòu)：設(shè)f是從格<L1,≤>到格<L2,≤’>的格同態(tài)，若f是雙射函數(shù)，則稱f為從

<L1,≤>到<L2,≤’>的格同構(gòu)。具有一,二,三個元素的格,分別是一、二,三個元素的鏈,四個和五個元素對應(yīng)表中同構(gòu)格之一，如下表所示：西安電子科技大學(xué)多媒體研究所yuliang@352023/2/6哈斯圖1個元素的格2個元素的格3個元素的格4個元素的互不同構(gòu)的格5個元素的互不同構(gòu)的格西安電子科技大學(xué)多媒體研究所yuliang@362023/2/67.3特殊的格：分配格分配格：設(shè)<L,∧,∨>是由格<L,≤>所誘導(dǎo)的代數(shù)系統(tǒng)，如果對任意的a,b,c∈L,滿足：

a∧(b∨c)=(a∧b)∨(a∧c)

保交對保聯(lián)可分配

a∨(b∧c)=(a∨b)∧(a∨c)

保聯(lián)對保交可分配

則稱<L,≤>是分配格。西安電子科技大學(xué)多媒體研究所yuliang@372023/2/67.3分配格【例題】圖(a)、(b)所示的格是分配格嗎？為什么？分析：均不是分配格。考慮b∧(c∨d)與(b∧c)∨(b∧d)；考慮c∧(b∨d)與(c∧b)∨(c∧d)cabde(a)鉆石格abcde(b)五角格西安電子科技大學(xué)多媒體研究所yuliang@382023/2/67.3分配格『定理』設(shè)<L,≤>是一個格，若∧運(yùn)算對∨運(yùn)算可分配，則∨對∧也可分配，反之亦然。證明：設(shè)∧運(yùn)算對∨運(yùn)算可分配，即任取a,b,c∈L,滿足a∧(b∨c)=(a∧b)∨(a∧c)現(xiàn)要證a∨(b∧c)=(a∨b)∧(a∨c)(a∨b)∧(a∨c)=((a∨b)∧a)∨((a∨b)∧c)=a∨((a∨b)∧c)

西安電子科技大學(xué)多媒體研究所yuliang@392023/2/67.3分配格

=a∨((a∧c)∨(b∧c))=a∨(a∧c)∨(b∧c)=a∨(b∧c)由此可知，∨運(yùn)算對∧運(yùn)算也可分配。同理可證，若∨運(yùn)算對∧運(yùn)算可分配，則∧運(yùn)算對∨運(yùn)算也可分配。西安電子科技大學(xué)多媒體研究所yuliang@402023/2/67.3分配格『定理』每個鏈都是分配格。證明：設(shè)<L,≤>是一個鏈，則<L,≤>必是一個格。任取a,b,c∈L,討論以下兩種情況：(i)a≤b或a≤c無論是a≤b或a≤c都有

a∧(b∨c)=a(a∧b)∨(a∧c)=a

即a∧(b∨c)=(a∧b)∨(a∧c)

西安電子科技大學(xué)多媒體研究所yuliang@412023/2/67.3分配格(ii)b≤a且c≤a:由b≤a,c≤a知b∨c≤a，可得

a∧(b∨c)=b∨c

又因為(a∧b)∨(a∧c)=b∨c,所以有

a∧(b∨c)=(a∧b)∨(a∧c)

由(i)、(ii)可知∧運(yùn)算對∨運(yùn)算可分配，于是∨運(yùn)算對∧運(yùn)算也可分配。故每個鏈都是分配格。西安電子科技大學(xué)多媒體研究所yuliang@422023/2/67.3分配格『定理』設(shè)<L,≤>是一個分配格，那么對于任意a,b,c∈L,如果有a∧b=a∧c和a∨b=a∨c成立，則必有b=c。證明：b=b∨(a∧b)=b∨(a∧c)=(b∨a)∧(b∨c)=(a∨c)∧(b∨c)=(a∧b)∨c=(a∧c)∨c=c西安電子科技大學(xué)多媒體研究所yuliang@432023/2/67.3分配格『定理』一個格是分配格，當(dāng)且僅當(dāng)它不存在與鉆石格和五角格同構(gòu)的子格?！憾ɡ怼环峙涓竦淖痈袷欠峙涓瘛Ｎ靼搽娮涌萍即髮W(xué)多媒體研究所yuliang@442023/2/67.3有界格全上界(全下界)：如果格<L,≤>中存在一個元素a,對于任何元素b∈L,均有b≤a(a≤b),則稱a為格<L,≤>的全上界(全下界)。通常將全上界記為“1”，而將全下界記為“0”。『定理』一個格<L,≤>若有全上界(全下界)，則是唯一的。西安電子科技大學(xué)多媒體研究所yuliang@452023/2/67.3有界格有界格：如果一個格既有全上界又有全下界，則稱該格為有界格。『定理』設(shè)<A,≤>是一個有界格，則對任意a∈A,必有

a∨1=1,a∧1=aa∨0=a,a∧0=0『定理』每個有限格都是有界格。西安電子科技大學(xué)多媒體研究所yuliang@462023/2/67.3有補(bǔ)格補(bǔ)元：設(shè)<L,≤>是一個有界格，對于L中一個元素a,如果存在元素b∈L,使得a∧b=0,a∨b=1,則稱元素b是a的補(bǔ)元，記為a’=b。同時，a也是b的補(bǔ)元，即b’=a。西安電子科技大學(xué)多媒體研究所yuliang@472023/2/67.3有補(bǔ)格【例題】寫出下圖所示的各有界格中所有元素的補(bǔ)元。1abc0c1bd0(b)(c)(d)(a)1a010abc西安電子科技大學(xué)多媒體研究所yuliang@482023/2/67.3有補(bǔ)格有補(bǔ)格：在一個有界格中，若每個元素至少有一個補(bǔ)元，則稱此格為有補(bǔ)格?！纠}】下圖中各哈斯圖所表示的格是否是有補(bǔ)格？為什么？01abcde10abcd10abcd01abcdef(a)(b)(c)(d)西安電子科技大學(xué)多媒體研究所yuliang@492023/2/67.3布爾格布爾格：若一個格既是有補(bǔ)格又是分配格，則稱此格為布爾格?！憾ɡ怼徊紶柛?lt;L,≤>中，每一個元素都有唯一的補(bǔ)元。證明：<L,≤>是布爾格，因此L中的每一個元素都有補(bǔ)元。設(shè)a∈L,a有兩個補(bǔ)元b,c∈L,根據(jù)補(bǔ)元的定義有：a∧b=0,a∧c=0a∨b=1,a∨c=1根據(jù)分配格的性質(zhì)可知：b=c。西安電子科技大學(xué)多媒體研究所yuliang@502023/2/67.3布爾格【例題】設(shè)S是非空有限集合,證明

<ρ(S),>是一個布爾格。證明：<ρ(S),>是一個格，它誘導(dǎo)的代數(shù)格為<ρ(S),∩,∪>。因為<ρ(S),∩,∪>,有全上界S和全下屆，因此它是有界格。任取T∈ρ(S),=S–T是T的補(bǔ)元，因此它是有補(bǔ)格?！珊汀仁窍嗷タ煞峙涞模虼怂欠峙涓?。綜上所述，<ρ(S),>是一個布爾格。西安電子科技大學(xué)多媒體研究所yuliang@512023/2/67.4布爾代數(shù)與布爾表達(dá)式布爾代數(shù)：由布爾格<B,≤>可以誘導(dǎo)出一個代數(shù)系統(tǒng)<B,∧,∨,’>，該代數(shù)系統(tǒng)稱為布爾代數(shù)。布爾格上的每個元素都有且僅有一個補(bǔ)元，因此布爾格誘導(dǎo)的代數(shù)系統(tǒng)有三個運(yùn)算：保交、保聯(lián)和補(bǔ)運(yùn)算，其中求補(bǔ)運(yùn)算是一元運(yùn)算。西安電子科技大學(xué)多媒體研究所yuliang@522023/2/67.4布爾代數(shù)【例題】求由布爾格<ρ(S),>所誘導(dǎo)的布爾代數(shù)系統(tǒng)。解答：<ρ(S),∩,∪,>是由布爾格<ρ(S),>所誘導(dǎo)的一個布爾代數(shù)，其中∩、∪和分別是集合的交、并和補(bǔ)運(yùn)算。西安電子科技大學(xué)多媒體研究所yuliang@532023/2/67.4布爾代數(shù)有限布爾代數(shù)：載體含有有限個元素的布爾代數(shù)稱為有限布爾代數(shù)。布爾代數(shù)的性質(zhì)：設(shè)<B,∧,∨,’>是一個布爾代數(shù)，任取a,b,c∈B都有性質(zhì)成立：(1)交換律a∨b=b∨a,a∧b=b∧a(2)結(jié)合律a∨(b∨c)=(a∨b)∨c,a∧(b∧c)=(a∧b)∧c西安電子科技大學(xué)多媒體研究所yuliang@542023/2/67.4布爾代數(shù)的性質(zhì)(3)等冪律a∨a=a,a∧a=a(4)吸收律a∨(a∧b)=a,a∧(a∨b)=a(5)分配律a∧(b∨c)=(a∧b)∨(a∧c)a∨(b∧c)=(a∨b)∧(a∨c)(6)同一律a∨0=a,a∧1=a(7)零一律a∧0=0,a∨1=1(8)互補(bǔ)律a∨a’=1,a∧a’=0(9)對合律(a’)’=a(10)德.摩根律(a∨b)’=a’∧b’,(a∧b)’=a’∨b’西安電子科技大學(xué)多媒體研究所yuliang@552023/2/67.4布爾代數(shù)的性質(zhì)證明:(10)(a∨b)∨(a’∧b’)=(a∨b∨a’)∧(a∨b∨b’)=(b∨(a∨a’))∧(a∨(b∨b’))=(b∨1)∧(a∨1)=1∧1=1

(a∨b)∧(a’∧b’)=(a∧a’∧b’)∨(b∧a’∧b’)=((a∧a’)∧b’)∨((b∧b’)∧a’)=(0∧b’)∨(0∧a’)=0∨0=0所以有(a∨b)’=a’∧b’。同理可證(a∧b)’=a’∨b’。西安電子科技大學(xué)多媒體研究所yuliang@562023/2/67.4布爾代數(shù)『定理』設(shè)<B,∧,∨>是一個代數(shù)系統(tǒng)，∧和∨是B上的二元運(yùn)算，如果對任意a,b,c∈B

均滿足以下四條性質(zhì)，則稱

<B,∧,∨>是一個布爾代數(shù)。(1)交換律a∨b=b∨a,a∧b=b∧a(2)分配律a∧(b∨c)=(a∧b)∨(a∧c)a∨(b∧c)=(a∨b)∧(a∨c)西安電子科技大學(xué)多媒體研究所yuliang@572023/2/67.4布爾代數(shù)(3)同一律B中存在兩個元素1和0，并且對B中任意元素a,滿足

a∧1=a,a∨0=a(4)互補(bǔ)律對B中每個元素a都存在唯一元素a’∈B，滿足

a∧a’=0,a∨a’=1

西安電子科技大學(xué)多媒體研究所yuliang@582023/2/67.4有限布爾代數(shù)的原子表示本小節(jié)研究有限布爾代數(shù)的一個重要性質(zhì)，就是任何有限布爾代數(shù)<B,∧,∨,’>都同構(gòu)于某有限集合S的冪代數(shù)<(S),∩,∪,>,這說明有限布爾代數(shù)有以下結(jié)構(gòu)特征：(1)任何有限布爾代數(shù)，其載體元素個數(shù)是2的冪次。(2)對每個正整數(shù)n,都存在具有2n個元素的布爾格。(3)對于元素個數(shù)相同的布爾代數(shù)都是同構(gòu)的。西安電子科技大學(xué)多媒體研究所yuliang@592023/2/67.4有限布爾代數(shù)的原子表示覆蓋：設(shè)a,b是一個格中的兩個元素，如果b≤a且b≠a,即b<a,并且在此格中再沒有別的元素c,使得b<c和c<a,則稱元素a覆蓋元素b。原子：設(shè)<A,≤>是一個格，且具有全下界0,如果有元素a∈A,a蓋住0，則稱元素a為原子。西安電子科技大學(xué)多媒體研究所yuliang@602023/2/67.4有限布爾代數(shù)的原子表示『定理』設(shè)<B,∧,∨,’>是一個布爾代數(shù)，a和b是該布爾代數(shù)的兩個原子，且有a≠b,則a∧b=0。證明：(反證法)假設(shè)a∧b=c≠0,因為a≠b,則有0<c<a或0<c<b，這與a和b是原子相矛盾,故假設(shè)錯誤，有a∧b=0。西安電子科技大學(xué)多媒體研究所yuliang@612023/2/67.4Stone表示定理『定理』(Stone表示定理)設(shè)<A,∧,∨,’>是一個有限布爾格<A,≤>所誘導(dǎo)的一個有限布爾格代數(shù)，S是布爾格<A,≤>的所有原子的集合,則<A,∧,∨,’>和<(S),∩,∪,ˉ>同構(gòu)。西安電子科技大學(xué)多媒體研究所yuliang@622023/2/67.4Stone表示定理的推論『推論1』有限布爾格的元素個數(shù)必定等于2n,其中n是該布爾格中所有原子的個數(shù)。『推論2』任何一個具有2n個元素的有限布爾代數(shù)都是同構(gòu)的。西安電子科技大學(xué)多媒體研究所yuliang@632023/2/67.4布爾表達(dá)式布爾常元：設(shè)<B,∧,∨,