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

格和布爾代數(shù)精簡2023/4/111第1頁，共69頁，2023年，2月20日，星期五第七章格與布爾代數(shù)7.1

格7.2

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

特殊的格7.4

布爾代數(shù)與布爾表達(dá)式2023/4/112第2頁，共69頁，2023年，2月20日，星期五7.1格格的定義：設(shè)<L,≤>是一個偏序集，如果集合L中的任意兩個元素都有最小上界和最大下界，則稱<L,≤>為格。2023/4/113第3頁，共69頁，2023年，2月20日，星期五7.1格【例題1】判斷下圖中所示各哈斯圖代表的偏序集合是否是格？為什么？abcdefabcdeabcdefabcdabcdabcdefghabcdeabcde2023/4/114第4頁，共69頁，2023年，2月20日，星期五7.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é)論得證。2023/4/115第5頁，共69頁，2023年，2月20日，星期五7.1格【例題3】設(shè)S是任意集合，ρ(S)是S的冪集，偏序集合<ρ(S),>是否是格？解答:任取A,B∈ρ(S),

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

<ρ(S),>中的最大下界是A∩B∈ρ(S)。2023/4/116第6頁，共69頁，2023年，2月20日，星期五7.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*對一切格也都為真。2023/4/117第7頁，共69頁，2023年，2月20日，星期五7.1格【例題】設(shè)<L,≤>是一個格,其哈斯圖如下圖所示，畫出<L,≥>的哈斯圖。解答：<L,≥>是<L,≤>的對偶格，因此其哈斯圖可由<L,≤>旋轉(zhuǎn)180°得到，如(b)圖所示。(a)(b)2023/4/118第8頁，共69頁，2023年，2月20日，星期五7.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ù)格。2023/4/119第9頁，共69頁，2023年，2月20日，星期五7.1代數(shù)格的性質(zhì)『定理1』在一個格<A,≤>中，對任意的a,b∈A,都有

a≤a∨b,b≤a∨b

a∧b≤a,a∧b≤b證明：因?yàn)閍和b的并是a的一個上界，所以

a≤a∨b

同理b≤a∨b

由對偶原理即得a∧b≤a,a∧b≤b2023/4/1110第10頁，共69頁，2023年，2月20日，星期五7.1代數(shù)格的性質(zhì)『定理2』在一個格<A,≤>中，對于a,b,c,d∈A,如果a≤b

和c≤d

則a∨c≤b∨d

a∧c≤b∧d證明：因?yàn)閎≤b∨d,d≤b∨d,由傳遞性可得a≤b∨d,c≤b∨d

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

是a和c的最小上界，所以，必有2023/4/1111第11頁，共69頁，2023年，2月20日，星期五7.1代數(shù)格的性質(zhì)

a∨c≤b∨d

類似地可以證明a∧c≤b∧d2023/4/1112第12頁，共69頁，2023年，2月20日，星期五7.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∨a2023/4/1113第13頁，共69頁，2023年，2月20日，星期五7.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∨c2023/4/1114第14頁，共69頁，2023年，2月20日，星期五7.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)

2023/4/1115第15頁，共69頁，2023年，2月20日，星期五7.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

2023/4/1116第16頁，共69頁，2023年，2月20日，星期五7.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)因?yàn)閍≤a,a∧b≤a

因此a∨(a∧b)≤a所以a∨(a∧b)=a利用對偶原理，即得a∧(a∨b)=a2023/4/1117第17頁，共69頁，2023年，2月20日，星期五7.1代數(shù)格的基本性質(zhì)(10)首先證明a≤ba∧b=a因?yàn)閍≤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=b2023/4/1118第18頁，共69頁，2023年，2月20日，星期五7.1代數(shù)格的基本性質(zhì)最后證明a∧b=aa∨b=b根據(jù)定理1可知a∨b≥b,而a∧b≤b,因?yàn)閍∧b=a,故a≤b,而b≤b,因此a∨b≤b,這樣就得到了a∨b=b，即a∧b=aa∨b=b。反之，假定a∨b=b,由定理1可知a∧b≤a,因?yàn)閍∨b=b，故b=a∨b≥a,而a≥a,因此a∧b≥a,這樣就得到了a∧b=a,即a∨b=ba∧b=a

。因此得到a∧b=aa∨b=b2023/4/1119第19頁，共69頁，2023年，2月20日，星期五7.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)

2023/4/1120第20頁，共69頁，2023年，2月20日，星期五7.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)∧c2023/4/1121第21頁，共69頁，2023年，2月20日，星期五7.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

2023/4/1122第22頁，共69頁，2023年，2月20日，星期五7.1格將(2)式中的b用(a∨b)替換得到

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

故∧和∨都滿足等冪律。2023/4/1123第23頁，共69頁，2023年，2月20日，星期五7.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)系。2023/4/1124第24頁，共69頁，2023年，2月20日，星期五7.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,

≤>是一個偏序集合。

2023/4/1125第25頁，共69頁，2023年，2月20日，星期五7.1格(ii)證明任取a,b∈A,a和b存在最小上界和最大下界。因?yàn)?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的下界。2023/4/1126第26頁，共69頁，2023年，2月20日，星期五7.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,

≤>是一個格。2023/4/1127第27頁，共69頁，2023年，2月20日，星期五7.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ò)展。2023/4/1128第28頁，共69頁，2023年，2月20日，星期五7.2子格【例題】圖(a)、(b)中所示的格<S’,≤>分別是格<S,≤>的子格嗎？(a)abdcedeab<S,≤><S’,≤>(b)一個格中的部分元素在原偏序關(guān)系上構(gòu)成一個格，不能說明它就是原格的子格。主要看該子集上的任意兩個元素在原運(yùn)算保交和保聯(lián)下的結(jié)果是否也在該子集中。<S,≤>abecdffacd<S’,≤>e2023/4/1129第29頁，共69頁，2023年，2月20日，星期五7.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)象。2023/4/1130第30頁，共69頁，2023年，2月20日，星期五7.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}2023/4/1131第31頁，共69頁，2023年，2月20日，星期五7.2格同態(tài)證明：<A,≤>是一個格，設(shè)其誘導(dǎo)的代數(shù)格為<A,∧,∨>，任取a,b∈A,因?yàn)?lt;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ù)。2023/4/1132第32頁，共69頁，2023年，2月20日，星期五7.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)。2023/4/1133第33頁，共69頁，2023年，2月20日，星期五7.2格同態(tài)性質(zhì)『定理』(格同態(tài)的保序性)設(shè)f是從格

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

證明：因?yàn)閤≤y，所以有x∧y=x,又

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

故f(x)≤’f(y)。2023/4/1134第34頁，共69頁，2023年，2月20日，星期五7.2格同構(gòu)格同構(gòu)：設(shè)f是從格<L1,≤>到格<L2,≤’>的格同態(tài)，若f是雙射函數(shù)，則稱f為從

<L1,≤>到<L2,≤’>的格同構(gòu)。具有一,二,三個元素的格,分別是一、二,三個元素的鏈,四個和五個元素對應(yīng)表中同構(gòu)格之一，如下表所示：2023/4/1135第35頁，共69頁，2023年，2月20日，星期五哈斯圖1個元素的格2個元素的格3個元素的格4個元素的互不同構(gòu)的格5個元素的互不同構(gòu)的格2023/4/1136第36頁，共69頁，2023年，2月20日，星期五7.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,≤>是分配格。2023/4/1137第37頁，共69頁，2023年，2月20日，星期五7.3分配格【例題】圖(a)、(b)所示的格是分配格嗎？為什么？分析：均不是分配格?？紤]b∧(c∨d)與(b∧c)∨(b∧d)；考慮c∧(b∨d)與(c∧b)∨(c∧d)cabde(a)鉆石格abcde(b)五角格2023/4/1138第38頁，共69頁，2023年，2月20日，星期五7.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)

2023/4/1139第39頁，共69頁，2023年，2月20日，星期五7.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)算也可分配。2023/4/1140第40頁，共69頁，2023年，2月20日，星期五7.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)

2023/4/1141第41頁，共69頁，2023年，2月20日，星期五7.3分配格(ii)b≤a且c≤a:由b≤a,c≤a知b∨c≤a，可得

a∧(b∨c)=b∨c

又因?yàn)?a∧b)∨(a∧c)=b∨c,所以有

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

由(i)、(ii)可知∧運(yùn)算對∨運(yùn)算可分配，于是∨運(yùn)算對∧運(yùn)算也可分配。故每個鏈都是分配格。2023/4/1142第42頁，共69頁，2023年，2月20日，星期五7.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=c2023/4/1143第43頁，共69頁，2023年，2月20日，星期五7.3分配格『定理』一個格是分配格，當(dāng)且僅當(dāng)它不存在與鉆石格和五角格同構(gòu)的子格?！憾ɡ怼环峙涓竦淖痈袷欠峙涓瘛?023/4/1144第44頁，共69頁，2023年，2月20日，星期五7.3有界格全上界(全下界)：如果格<L,≤>中存在一個元素a,對于任何元素b∈L,均有b≤a(a≤b),則稱a為格<L,≤>的全上界(全下界)。通常將全上界記為“1”，而將全下界記為“0”?！憾ɡ怼灰粋€格<L,≤>若有全上界(全下界)，則是唯一的。2023/4/1145第45頁，共69頁，2023年，2月20日，星期五7.3有界格有界格：如果一個格既有全上界又有全下界，則稱該格為有界格。『定理』設(shè)<A,≤>是一個有界格，則對任意a∈A,必有

a∨1=1,a∧1=aa∨0=a,a∧0=0『定理』每個有限格都是有界格。2023/4/1146第46頁，共69頁，2023年，2月20日，星期五7.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。2023/4/1147第47頁，共69頁，2023年，2月20日，星期五7.3有補(bǔ)格【例題】寫出下圖所示的各有界格中所有元素的補(bǔ)元。1abc0c1bd0(b)(c)(d)(a)1a010abc2023/4/1148第48頁，共69頁，2023年，2月20日，星期五7.3有補(bǔ)格有補(bǔ)格：在一個有界格中，若每個元素至少有一個補(bǔ)元，則稱此格為有補(bǔ)格?！纠}】下圖中各哈斯圖所表示的格是否是有補(bǔ)格？為什么？01abcde10abcd10abcd01abcdef(a)(b)(c)(d)2023/4/1149第49頁，共69頁，2023年，2月20日，星期五7.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。2023/4/1150第50頁，共69頁，2023年，2月20日，星期五7.3布爾格【例題】設(shè)S是非空有限集合,證明

<ρ(S),>是一個布爾格。證明：<ρ(S),>是一個格，它誘導(dǎo)的代數(shù)格為<ρ(S),∩,∪>。因?yàn)?lt;ρ(S),∩,∪>,有全上界S和全下屆，因此它是有界格。任取T∈ρ(S),=S–T是T的補(bǔ)元，因此它是有補(bǔ)格?！珊汀仁窍嗷タ煞峙涞模虼怂欠峙涓?。綜上所述，<ρ(S),>是一個布爾格。2023/4/1151第51頁，共69頁，2023年，2月20日，星期五7.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)算。2023/4/1152第52頁，共69頁，2023年，2月20日，星期五7.4布爾代數(shù)【例題】求由布爾格<ρ(S),>所誘導(dǎo)的布爾代數(shù)系統(tǒng)。解答：<ρ(S),∩,∪,>是由布爾格<ρ(S),>所誘導(dǎo)的一個布爾代數(shù)，其中∩、∪和分別是集合的交、并和補(bǔ)運(yùn)算。2023/4/1153第53頁，共69頁，2023年，2月20日，星期五7.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)∧c2023/4/1154第54頁，共69頁，2023年，2月20日，星期五7.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’2023/4/1155第55頁，共69頁，2023年，2月20日，星期五7.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’。2023/4/1156第56頁，共69頁，2023年，2月20日，星期五7.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)2023/4/1157第57頁，共69頁，2023年，2月20日，星期五7.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

2023/4/1158第58頁，共69頁，2023年，2月20日，星期五7.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)的。2023/4/1159第59頁，共69頁，2023年，2月20日，星期五7.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為原子。2023/4/1160第60頁，共69頁，2023年，2月20日，星期五7.4有限布爾代數(shù)的原子表示『定理』設(shè)<B,∧,∨,’>是一個布爾代數(shù)，a和b是該布爾代數(shù)的兩個原子，且有a≠b,則a∧b=0。證明：(