離散數(shù)學(xué)格與布爾代數(shù)

離散數(shù)學(xué)格與布爾代數(shù)第一頁，共八十七頁，2022年，8月28日2.B的最小元與最大元y是B的最小元y∈B∧x(x∈By≤x)y是B的最大元y∈B∧x(x∈Bx≤y){2,3,6}的最小元:無最大元:6B如果有最小元(最大元),則是唯一的。3.B的下界與上界y是B的下界y∈A∧x(x∈By≤x)y是B的上界y∈A∧x(x∈Bx≤y){2,3,6}的下界:1上界:6,12,24,364.B的最大下界(下確界)與最小上界(上確界)y是B的最大下界(下確界)：B的所有下界x,有x≤y。y是B的最小上界(上確界)：B的所有上界x,有y≤x。{2,3,6}下確界:1上確界:6(B若有下(上)確界，則唯一)６。１。３。12。２。24。36。第二頁，共八十七頁，2022年，8月28日7-1格

(Lattice)一.基本概念1.格的定義<A,≤>是偏序集，如果任何a,b∈A,使得{a,b}都有最大下界和最小上界，則稱<A,≤>是格。

右圖的三個(gè)偏序集，<A,≤>不是格，因?yàn)閧24,36}無最小上界。<B,≤><C,≤>是格。６。１。３。12。２。24。36。30。3。１。2。5。10。１5。6。<A,≤><B,≤>3。4。1。2。<C,≤>第三頁，共八十七頁，2022年，8月28日這三個(gè)偏序集，也都不是格，第一個(gè)與第三個(gè)是同構(gòu)的。因?yàn)閐和e無下界，也無最小上界；b,c雖有下界，但無最大下界。2,3無最大下界，4,5無最小上界。2.平凡格：所有全序都是格，稱之為平凡格。因?yàn)槿蛑腥魏蝺蓚€(gè)元素x,y，要么x≤y,要么y≤x。如果x≤y，則{x,y}的最大下界為x，最小上界為y。如果y≤x，則{x,y}的最大下界為y，最小上界為x。即這{x,y}的最大下界為較小元素，最小上界為較大元素.dabce123456dabce第四頁，共八十七頁，2022年，8月28日3.由格誘導(dǎo)的代數(shù)系統(tǒng)設(shè)<A,≤>是格,在A上定義二元運(yùn)算∨和∧為:a,b∈Aa∨b=LUB{a,b}{a,b}的最小上界.LeastUpperBounda∧b=GLB{a,b}{a,b}的最大下界.GreatestLowerBound稱<A,∨,∧>是由格<A,≤>誘導(dǎo)的代數(shù)系統(tǒng).(∨-并,∧-交)例如右邊的格中a∧b=ba∨b=ab∧c=e4.子格：設(shè)<A,≤>是格,<A,∨,∧>是由<A,≤>誘導(dǎo)的代數(shù)系統(tǒng)。B是A的非空子集，如果∧和∨在B上封閉，則稱<B,≤>是<A,≤>的子格。<C,≤>是<A,≤>的子格。而<B,≤>不是.b∧c=dB,(運(yùn)算規(guī)則要從格<A,≤>中找)

eabdcbacfe

gbacfe

gd<B,≤><A,≤>acbd<C,≤>第五頁，共八十七頁，2022年，8月28日二.格的對(duì)偶原理設(shè)<A,≤>是格，≤的逆關(guān)系記作≥，≥也是偏序關(guān)系。<A,≥>也是格，<A,≥>的Hasse圖是將<A,≤>的Hasse圖顛倒180o即可。

格的對(duì)偶原理：設(shè)P是對(duì)任何格都為真的命題，如果將P中的≤換成≥，∧換成∨，∨換成∧，就得到命題P’,稱P’為P的對(duì)偶命題，則P’對(duì)任何格也是為真的命題。例如：P:a∧b≤aP’:a∨b≥a{a,b}的最大下界≤a{a,b}的最小上界≥a第六頁，共八十七頁，2022年，8月28日三.格的性質(zhì)

<A,∨,∧>是由格<A,≤>誘導(dǎo)的代數(shù)系統(tǒng)。a,b,c,d∈A1.a≤a∨bb≤a∨ba∧b≤aa∧b≤b此性質(zhì)由運(yùn)算∨和∧的定義直接得證。

2.如果a≤b，c≤d，則a∨c≤b∨d，a∧c≤b∧d。證明：如果a≤b，又b≤b∨d，由傳遞性得a≤b∨d,

類似由c≤d，d≤b∨d，由傳遞性得c≤b∨d,這說明b∨d是{a,c}的一個(gè)上界，而a∨c是{a,c}的最小上界，所以a∨c≤b∨d。類似可證a∧c≤b∧d。推論：在一個(gè)格中，任意a,b,c∈A，如果b≤c，則a∨b≤a∨c，a∧b≤a∧c。此性質(zhì)稱為格的保序性。第七頁，共八十七頁，2022年，8月28日3.∨和∧都滿足交換律。即a∨b=b∨a，a∧b=b∧a此性質(zhì)由運(yùn)算∨和∧的定義直接得證。4.∨和∧都滿足冪等律。即a∨a=aa∧a=a證明：由性質(zhì)1,a≤a∨a

(再證a∨a≤a)又由≤自反有a≤a，這說明a是a的上界，而a∨a是a的最小上界，所以a∨a≤a。最后由≤反對(duì)稱得a∨a=a。

由對(duì)偶原理得a∧a=a第八頁，共八十七頁，2022年，8月28日5.∨和∧都滿足結(jié)合律。即(a∨b)∨c=a∨(b∨c)，(a∧b)∧c=a∧(b∧c)

證明：⑴先證明(a∨b)∨c≤a∨(b∨c)

因a≤a∨(b∨c)，b≤b∨c≤a∨(b∨c)所以a∨b≤a∨(b∨c)又c≤b∨c≤a∨(b∨c)于是有(a∨b)∨c≤a∨(b∨c)

⑵再證a∨(b∨c)≤(a∨b)∨c

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

再由b≤a∨b≤(a∨b)∨c，c≤(a∨b)∨c所以b∨c≤(a∨b)∨c于是有a∨(b∨c)≤(a∨b)∨c最后由≤反對(duì)稱得

(a∨b)∨c=a∨(b∨c)類似可證(a∧b)∧c=a∧(b∧c)。第九頁，共八十七頁，2022年，8月28日6.∨和∧都滿足吸收律。即a∨(a∧b)=a，a∧(a∨b)=a。證明：⑴顯然有a≤a∨(a∧b)⑵再證a∨(a∧b)≤a因a≤a，a∧b≤a所以a∨(a∧b)≤a最后由≤反對(duì)稱得a∨(a∧b)=a，類似可證a∧(a∨b)=a。第十頁，共八十七頁，2022年，8月28日7.∨和∧不滿足分配律。但有分配不等式：

a∨(b∧c)≤(a∨b)∧(a∨c)，(a∧b)∨(a∧c)≤a∧(b∨c)。我們先看右圖的例子：d∨(b∧e)=d∨c=d(d∨b)∧(d∨e)=a∧e=e而d≤e即d∨(b∧e)≤(d∨b)∧(d∨e)證明：⑴因a≤a∨b，a≤a∨c所以a≤(a∨b)∧(a∨c)

又因b∧c≤b≤a∨b，b∧c≤c≤a∨c所以b∧c≤(a∨b)∧(a∨c)

于是有a∨(b∧c)≤(a∨b)∧(a∨c)。由對(duì)偶原理得a∧(b∨c)≥(a∧b)∨(a∧c)。即(a∧b)∨(a∧c)≤a∧(b∨c)。cabed第十一頁，共八十七頁，2022年，8月28日8.a≤ba∨b=ba∧b=a證明：⑴先證明a≤ba∧b=a

先證a≤ba∧b=a由a≤b，又a≤a所以a≤a∧b又由a∧b的定義有a∧b≤a由反對(duì)稱得a∧b=a

再證a∧b=a

a≤b由a∧b=a則a=a∧b≤b。

綜上得a≤ba∨b=b⑵下面證明a≤ba∨b=b

先證a≤ba∨b=b由a≤b，又b≤b所以a∨b≤b又因?yàn)閎≤a∨b由反對(duì)稱得a∨b=b

再證a∨b=b

a≤b由a∨b=b因a≤a∨b所以a≤b。

綜上得a≤ba∨b=b第十二頁，共八十七頁，2022年，8月28日引理：<A,∨,∧>是代數(shù)系統(tǒng)，如果∨和∧是滿足吸收律的二元運(yùn)算，則∨和∧必滿足冪等律。證明：任取a,b∈A因?yàn)椤藕汀臐M足吸收律。于是有a∨(a∧b)=a------⑴a∧(a∨b)=a-------⑵。由于上式中的b是任意的，可以令b=a∨b并代入⑴式得a∨(a∧(a∨b))=a由⑵式得a∨a=a同理可證a∧a=a第十三頁，共八十七頁，2022年，8月28日定理：設(shè)<A,∨,∧>是代數(shù)系統(tǒng)，如果∨和∧是滿足交換律，結(jié)合律，和吸收律的二元運(yùn)算，則A上存在偏序關(guān)系?

，使<A,?>是一個(gè)格，并且該格所誘導(dǎo)的代數(shù)系統(tǒng)恰好是<A,∨,∧>。（由代數(shù)系統(tǒng)得到格）證明：設(shè)在A上定義二元關(guān)系?為：對(duì)任意a,b∈A,a?b當(dāng)且僅當(dāng)a∧b=a（1）先證二元關(guān)系?是一個(gè)偏序關(guān)系（2）再證a∧b是{a,b}的下確界（3）然后證a∨b是{a,b}的上確界見書上238頁第十四頁，共八十七頁，2022年，8月28日四.格的同態(tài)與同構(gòu)1.定義：設(shè)<A1,≤1>和<A2,≤2>是兩個(gè)格，由它們誘導(dǎo)的代數(shù)系統(tǒng)分別是<A1,∨1,∧1>和<A2,∨2,∧2>，如果存在映射f:A1A2

，使得對(duì)任何a,b∈A1，有

f(a∨1b)=f(a)∨2f(b)f(a∧1b)=f(a)∧2f(b)則稱f是<A1,∨1,∧1>到<A2,∨2,∧2>的同態(tài)映射。也稱<f(A1),≤2>是<A1,≤1>的同態(tài)像。如果f是雙射的，就稱f是<A1,∨1,∧1>到<A2,∨2,∧2>，的格同構(gòu)，也稱格<A1,≤1>和<A2,≤2>同構(gòu)。第十五頁，共八十七頁，2022年，8月28日例：<A,≤>，A={1,2,3,6},≤是A上整除關(guān)系。<P(E),>，E={a,b}它們誘導(dǎo)的代數(shù)系統(tǒng)分別是<A,∨,∧>和<P(E),∪,∩>其中∨和∧分別是求兩個(gè)數(shù)的最小公倍數(shù)和最大公約數(shù).f(2∨3)=f(6)={a,b}f(2)∪f(3)={a}∪={a,b}f(2∧3)=f(1)=Φf(2)∩f(3)={a}∩=Φf(2∨6)=f(6)={a,b}f(2)∪f(6)={a}∪{a,b}={a,b}f(2∧6)=f(2)={a}f(2)∪f(6)={a}∪{a,b}={a}……可見它們同構(gòu)。格同構(gòu)，它們的哈斯圖的形狀一定相同。Φ{a}

{a,b}1

32

6f6321{a}{a,b}ΦA(chǔ)P(E)第十六頁，共八十七頁，2022年，8月28日具有1、2、3個(gè)元素的格分別同構(gòu)于含有一、二、三個(gè)元素的鏈。具有4個(gè)元素的格分別同構(gòu)于下面兩種格形式之一：具有5個(gè)素的格分別同構(gòu)于下面五種格形式之一：edabcda

bccdda

bcea

bcea

bdaeb

cddabceaababc第十七頁，共八十七頁，2022年，8月28日2.格同態(tài)的保序性定理：設(shè)f是格<A1,≤1>到<A2,≤2>的同態(tài)映射，則對(duì)任何a,b∈A1，如果a≤1b，則f(a)≤2f(b)。證明：令<A1,∨1,∧1>和<A2,∨2,∧2>是格<A1,≤1>和<A2,≤2>誘導(dǎo)的代數(shù)系統(tǒng)，任取a,b∈A1，設(shè)a≤1b，則a∧1b=af(a∧1b)=f(a)即f(a)∧2f(b)=f(a)而f(a)∧2f(b)≤2f(b)所以f(a)≤2f(b).3.格同構(gòu)的保序性定理：設(shè)兩個(gè)格為<A1,≤1>和<A2,≤2>，f是A1到A2的雙射，則f是<A1,≤1>到<A2,≤2>的格同構(gòu)，當(dāng)且僅當(dāng)對(duì)任意a,b∈A1，a≤1bf(a)≤2f(b)證明：令<A1,∨1,∧1>和<A2,∨2,∧2>是格<A1,≤1>和<A2,≤2>誘導(dǎo)的代數(shù)系統(tǒng)，第十八頁，共八十七頁，2022年，8月28日1)必要性：已知f是格<A1,≤1>到<A2,≤2>的同構(gòu)映射，（往證：任取a,b∈A1,a≤1bf(a)≤2f(b)）a)先證a≤1bf(a)≤2f(b)

任取a,b∈A1,設(shè)a≤1b

，由格同態(tài)保序性得f(a)≤2f(b)

b)再證f(a)≤2f(b)a≤1b設(shè)f(a)≤2f(b)，于是有f(a)=f(a)∧2f(b)=f(a∧1b)因f是雙射，所以a=a∧1b所以a≤1b最后得a≤1bf(a)≤2f(b)

。第十九頁，共八十七頁，2022年，8月28日2)充分性：已知，對(duì)任意a,b∈A1,a≤1bf(a)≤2f(b)(往證f(a∧1b)=f(a)∧2f(b)f(a∨1b)=f(a)∨2f(b))a)證f(a∧1b)=f(a)∧2f(b)

令a∧1b=c所以c≤1ac≤1b，由已知得f(c)≤2f(a)和f(c)≤2f(b)，所以f(c)≤2f(a)∧2f(b)-------⑴

再證f(a)∧2f(b)≤2f(c)：由于f(a),f(b)∈A2,又∧2封閉，得f(a)∧2f(b)∈A2,又由f:A1A2是雙射，必有d∈A1,使得f(a)∧2f(b)=f(d)所以f(d)≤2f(a)，f(d)≤2f(b)由已知得：d≤1a，d≤1b，于是d≤1a∧1b=c，即d≤1c，于是f(d)≤2f(c)即f(a)∧2f(b)≤2f(c)

-----⑵由⑴⑵得f(a)∧2f(b)=f(c)

，即f(a∧1b)=f(a)∧2f(b)

。b)類似可證f(a∨1b)=f(a)∨2f(b)，所以f是它們的同構(gòu)映射。第二十頁，共八十七頁，2022年，8月28日7-2幾個(gè)特殊格一.分配格

前面我們介紹一般的格，∧和∨只滿足分配不等式。a∨(b∧c)≤(a∨b)∧(a∨c)，(a∧b)∨(a∧c)≤a∧(b∨c)。下面介紹的是滿足分配律的格----分配格。1.定義：<A,∨,∧>是由格<A,≤>誘導(dǎo)的代數(shù)系統(tǒng)。如果對(duì)a,b,c∈A，有a∨(b∧c)=(a∨b)∧(a∨c)，a∧(b∨c)=(a∧b)∨(a∧c)則稱<A,≤>是分配格。例：<P(E),>所誘導(dǎo)的代數(shù)系統(tǒng)為<P(E),∪,∩>所以<P(E),>是分配格。第二十一頁，共八十七頁，2022年，8月28日2.二個(gè)重要的五元素非分配格：

2∧(3∨5)=2∧30=2(2∧3)∨(2∧5)=1∨1=1c∧(b∨d)=c∧a=c(c∧b)∨(c∧d)=e∨d=d可見它們都不是分配格。3.分配格的判定：

一個(gè)格是分配格的充分且必要條件是在該格中沒有任何子格與上述兩個(gè)五元素非分配格之一同構(gòu)。用此方法可以判定下面兩個(gè)格不是分配格：3130

25dea

bc416

352fga

dc

e

b第二十二頁，共八十七頁，2022年，8月28日4.分配格的性質(zhì)1.

在一個(gè)格中，如果∧對(duì)∨可分配，則∨對(duì)∧也可分配。反之亦然。證明：設(shè)<A,∨,∧>是由格<A,≤>誘導(dǎo)的代數(shù)系統(tǒng)，且∧對(duì)∨可分配。則任取a,b,c∈A，(a∨b)∧(a∨c)=((a∨b)∧a)∨((a∨b)∧c)分配=a∨((a∨b)∧c)=a∨((a∧c)∨(b∧c))吸收、分配=(a∨(a∧c))∨(b∧c)結(jié)合=a∨(b∧c)

即∨對(duì)∧也可分配

同理可證:如果∨對(duì)∧可分配，則∧對(duì)∨也可分配.2.所有鏈均為分配格。證明：顯然任何鏈都不會(huì)含有與那兩個(gè)五元素非分配格之一同構(gòu)的子格，所以鏈必是分配格。第二十三頁，共八十七頁，2022年，8月28日3.設(shè)<A,≤>是分配格，對(duì)任何a,b,c∈A，如果有a∧b=a∧c及a∨b=a∨c則必有b=c。證明：任取a,b,c∈A,設(shè)有a∧b=a∧c及a∨b=a∨cb=b∨(a∧b)(吸收律)=b∨(a∧c)(代換)=(b∨a)∧(b∨c)(分配)=(a∨b)∧(b∨c)(交換)=(a∨c)∧(b∨c)(代換)=(a∧b)∨c(分配)

=(a∧c)∨c(代換)=c(吸收律)第二十四頁，共八十七頁，2022年，8月28日二.有界格1.格的全上界與全下界1).全上界:設(shè)<A,≤>是格，如果存在元素a∈A對(duì)任何x∈A,x≤a，則稱a是格的全上界，記作1。(即是A的最大元)定理7-2.4一個(gè)格如果有全上界，則是唯一的。(我們已證明過，最大元如果有，則是唯一的)2).全下界:設(shè)<A,≤>是格，如果存在元素a∈A對(duì)任何x∈A,a≤x,則稱a是格的全下界,記作0。(即是A的最小元)定理7-2.5一個(gè)格如果有全下界，則是唯一的。從格的圖形看：全上界1，就是圖的最上邊元素(只一個(gè))，全下界0，就是圖的最下邊元素(只一個(gè))。b01

ac1c0第二十五頁，共八十七頁，2022年，8月28日2.有界格定義：如果一個(gè)格存在全上界1與全下界0，則稱此格為有界格。設(shè)<A,≤>是有界格，則對(duì)任何a∈A,有因?yàn)閍≤1,所以a∧1=aa∨1=10≤a所以a∧0=0a∨0=a是否所有格都是有界格？所有有限個(gè)元素的格都是有界格，而無限個(gè)元素的格可能是無界格。例如<I,≤>就既無全上界也無全下界。

第二十六頁，共八十七頁，2022年，8月28日三.有補(bǔ)格回顧：集合的補(bǔ)集，若A∪B=EA∩B=Φ則~A=B，~B=A如E={a,b}~E=Φ~Φ=E~{a}=,~={a}1.元素的補(bǔ)元：

設(shè)<A,≤>是個(gè)有界格，a∈A,如果存在b∈A，使得a∨b=1且a∧b=0，則稱a與b互為補(bǔ)元。例：右邊的格中a的補(bǔ)元：c,eb的補(bǔ)元：無c的補(bǔ)元：a,dd的補(bǔ)元：ce的補(bǔ)元：a0的補(bǔ)元：11的補(bǔ)元：0Φ{a,b}

{a}e01

bc

d

a第二十七頁，共八十七頁，2022年，8月28日2.有補(bǔ)格的定義：

一個(gè)有界格中，如果每個(gè)元素都有補(bǔ)元，則稱之為有補(bǔ)格。上述有界格中，哪些是有補(bǔ)格？上述有補(bǔ)格中，有些元素的補(bǔ)元不唯一，如(2)中的b，那么什么樣的有補(bǔ)格元素的補(bǔ)元唯一呢？有界分配格。請(qǐng)看下面定理：Φ{a,b}

{a}b01

ace01

bc

d

a1c0(1)(2)(3)(4)第二十八頁，共八十七頁，2022年，8月28日定理7－2.6在有界分配格中，如果元素有補(bǔ)元，則補(bǔ)元是唯一的。證明：設(shè)<A,≤>是有界分配格，任取a∈A，假設(shè)a有兩個(gè)補(bǔ)元b和c，則a∧b=0a∨b=1a∧c=0a∨c=1于是有a∧b=a∧c及a∨b=a∨c由分配格的性質(zhì)3得b=c，所以a的補(bǔ)元是唯一的。四.布爾格

如果一個(gè)格既是分配格又是有補(bǔ)格，則稱之為布爾格。布爾格中每個(gè)元素都有唯一補(bǔ)元，元素a的補(bǔ)元記作。顯然<P(E),>是布爾格。下面介紹由布爾格誘導(dǎo)的代數(shù)系統(tǒng)－－布爾代數(shù)。第二十九頁，共八十七頁，2022年，8月28日7－3布爾代數(shù)

BooleanAlgebra一.定義

由布爾格<B,≤>誘導(dǎo)的代數(shù)系統(tǒng)<B,∨,∧,ˉ>稱之為布爾代數(shù)。其中ˉ是取補(bǔ)元運(yùn)算。如果A是有限集合，則稱它是有限布爾代數(shù)。例如：令B＝{F,T}，∧表示合取，∨表示析取，表示否定，<B,∨,∧,>

就是個(gè)由右面格所誘導(dǎo)的布爾代數(shù)。

E={a,b},<P(E),∪,∩,~>也是個(gè)由右面格所誘導(dǎo)的布爾代數(shù)。TFΦ{a,b}

{a}第三十頁，共八十七頁，2022年，8月28日二.布爾代數(shù)的性質(zhì)設(shè)<B,∨,∧,ˉ>布爾代數(shù),任意x,y,z∈B,有⑴交換律x∨y=y∨xx∧y=y∧x⑵結(jié)合律x∨(y∨z)=(x∨y)∨zx∧(y∧z)=(x∧y)∧z

⑶冪等律x∨x=xx∧x=x

⑷吸收律x∨(x∧y)=xx∨(x∧y)=x⑸分配律x∨(y∧z)=(x∨y)∧(x∨z)

x∧(y∨z)=(x∧y)∨(x∧z)⑹同一律x∨0=xx∧1=x

⑺零律x∨1=1x∧0=0

⑻互補(bǔ)律x∨=1x∧=0

⑼對(duì)合律⑽底－摩根定律第三十一頁，共八十七頁，2022年，8月28日上述性質(zhì)都可以由格，分配格，有界格，布爾格得到。下面只證明底－摩根定律。所以。類似可證另一個(gè)。第三十二頁，共八十七頁，2022年，8月28日三.布爾代數(shù)的同構(gòu)1.定義：令<B1,∨1,∧1,ˉ>和<B2,∨2,∧2,~>是兩個(gè)布爾代數(shù)，如果存在映射f:B1B2，對(duì)任何a,b∈B1，有f(a∨1b)=f(a)∨2f(b)f(a∧1b)=f(a)∧2f(b)f()=則稱f是<A1,∨1,∧1>到<A2,∨2,∧2>的同態(tài)映射。

與格同構(gòu)比較，多了一個(gè)關(guān)于補(bǔ)運(yùn)算的同構(gòu)關(guān)系等式。為了引出有限布爾代數(shù)的stone的定理，下面介紹原子的概念。~f(a)第三十三頁，共八十七頁，2022年，8月28日2.原子

定義1:設(shè)設(shè)<B,∨,∧,ˉ>布爾代數(shù),元素a∈B,a≠0,對(duì)任何元素x∈B,有x∧a=a,或x∧a=0,則稱a是原子。

定義2:<A,≤>是布爾格,在<A,≤>的哈斯圖中稱蓋住全下界0的元素為原子。例如：1。e。0。d。f。b。c。a。0。1。01a

b第三十四頁，共八十七頁，2022年，8月28日下面先介紹原子的判定定理7-3.1設(shè)<B,∨,∧,ˉ>是布爾代數(shù)，a∈B,且a≠0,則a是原子的充分且必要條件是對(duì)任何y∈B，如果y≤a,則y=0或y=a。證明:必要性.設(shè)a是原子,且對(duì)任何y∈B，有y≤a(往證y=0或y=a),

由原子定義得y∧a=a,或y∧a=0,而由y≤a得y∧a=y,所以有y=0或y=a.充分性.已知對(duì)任何y∈B，如果y≤a,則y=0或y=a。(往證a是原子,即證出對(duì)任何x∈B有x∧a=a,或x∧a=0),

任取x∈B,令y=x∧a,因x∧a≤a,所以y≤a,由已知條件得y=0或y=a,所以有x∧a=a,或x∧a=0,所以a是原子.第三十五頁，共八十七頁，2022年，8月28日定理7-3.2設(shè)a,b是布爾代數(shù)<B,∨,∧,ˉ>中的原子，如果a≠b,則a∧b=0,(如果a∧b≠0,則a=b)即不同兩個(gè)原子的下確界為0證明:設(shè)a和b是B中原子,(由原子定義得:對(duì)任何x∈B有x∧a=a,或x∧a=0,)

因?yàn)閍是原子,而b∈B,所以b∧a=a∧b=a,或b∧a=a∧b=0,于是:如果a∧b≠0,必有a∧b=a.類似地,b是原子,而a∈B,所以a∧b=b,或a∧b=0,

于是:如果a∧b≠0,必有a∧b=b,最后得a=b.所以得出,如果a∧b≠0,則a=b.等價(jià)的如果a≠b,則a∧b=0.第三十六頁，共八十七頁，2022年，8月28日定理7-3.3設(shè)a,b1,b2…bn是布爾代數(shù)<B,∨,∧,ˉ>中的原子，則a≤b1∨b2∨…∨bn的充分且必要條件為對(duì)于某個(gè)i(1≤i≤n),有a=bi.證明:充分性顯然成立,因?yàn)閷?duì)于某個(gè)i(1≤i≤n),有a=bi.必有a≤b1∨b2∨…∨bn必要性,已知a≤b1∨b2∨…∨bn,則a∧(b1∨b2∨…∨bn)=a(a∧b1)∨(a∧b2)∨…∨(a∧bn)=a如果每個(gè)(a∧bi)=0(1≤i≤n)則(a∧b1)∨(a∧b2)∨…∨(a∧bn)=0這與a是原子矛盾.所以至少有某個(gè)i(1≤i≤n),使得(a∧bi)≠0因?yàn)閍和bi都是原子,由定理7-3.2得a=bi.第三十七頁，共八十七頁，2022年，8月28日定理7-3.4設(shè)b是有限布爾代數(shù)<B,∨,∧,ˉ>中的非0元素，則必存在原子a，使得a≤b.證明:1).如果b是原子,則令b=a,則a≤b.2).如果b不是原子,則必存在b1∈B使得0<b1<b,如果b1不是原子,則必存在b2∈B使得0<b2<b1<b,如此下去,由于B是有限集合,上述過程經(jīng)過有限步后而最終結(jié)束,最后得到原子bk,使得0<bk<…b2<b1<b令bk=a,于是a≤b.1。e。0。d。f。b。c。a。第三十八頁，共八十七頁，2022年，8月28日定理7-3.5有限布爾代數(shù)中，b∧=0，當(dāng)且僅當(dāng)b≤c。例如右圖中,2∧=02≤6證明:充分性.已知b≤c又于是因?yàn)?是全下界,所以b∧=0必要性.已知b∧=0(往證b≤c,即b∨c=c)b∨c=(b∨c)∧1=(b∨c)∧(c∨)=(b∧)∨c=0∨c=c所以b∨c=c,即b≤c30。3。1。2。5。10。15。6。第三十九頁，共八十七頁，2022年，8月28日定理7-3.6設(shè)<B,∨,∧,ˉ>是有限布爾代數(shù)，b非0元素，a1,a2…ak是B中滿足aj≤b的所有原子(j=1,2,…k),則

b＝a1∨a2∨…∨ak且除原子次序不同外，上述表達(dá)式是唯一的。證明:(1)令a1∨a2∨…∨ak＝c(往證b=c即證b≤c且c≤b)

a).證c≤b顯然成立,因?yàn)槊總€(gè)ai≤b,(j=1,2,…k)所以a1∨a2∨…∨ak≤b即c≤b.

b).證b≤c.(由定理7-3.5可知,只要證出b∧=0即可)假設(shè)b∧≠0,由定理7-3.4得,必存在原子a,使得a≤b∧,而b∧≤bb∧≤由≤的傳遞性得a≤b,a≤.因?yàn)閍是原子,且a≤b,b≠0,由題意a必是a1,a2,…,ak中之一,于是a≤a1∨a2∨…∨ak即a≤c,又a≤,得a≤c∧所以a≤0，這與a是原子矛盾.所以只有b∧=0

，

所以b≤c。綜上b=ca1a2bak...0第四十頁，共八十七頁，2022年，8月28日即得b＝a1∨a2∨…∨ak…….①(2)證明上式是唯一的.假設(shè)還有原子b1,b2,…,bm∈B,使得b＝b1∨b2∨…∨bm…….②

(下面證{b1,b2,…,bm}={a1,a2,...,ak})a).任取bi∈{b1,b2,…,bm},由②式得{b1,b2,…,bm}中每個(gè)bj≤b(1≤j≤m),又b＝a1∨a2∨…∨ak所以bi≤b即bi≤a1∨a2∨…∨ak,由于bi及每個(gè)aj(1≤j≤k)都是原子,由定理7-3.3得,{a1,a2,...,ak}中必存在一個(gè)aj,使得bi=aj

于是bi∈{a1,a2,…,ak}所以{b1,b2,…,bm}{a1,a2,...,ak}類似可以證明{a1,a2,...,ak}{b1,b2,…,bm}最后得

{b1,b2,…,bm}={a1,a2,...,ak}所以上述表達(dá)式在不考慮原子次序時(shí),形式是唯一的.第四十一頁，共八十七頁，2022年，8月28日定理7-3.7在布爾代數(shù)<B,∨,∧,ˉ>中，對(duì)B中任何原子a和任何非0元素b,a≤b和a≤兩式中有且僅有一個(gè)成立。證明:假設(shè)上述兩個(gè)式子都成立,即a≤b和a≤,則有a≤b∧=0,這與a是原子矛盾.下面證明兩個(gè)式中必有一個(gè)成立.因?yàn)閍∧b≤a,而a是原子,所以只能有a∧b=a或a∧b=0如果a∧b=0,即,由定理7-3.5得,a≤,如果a∧b=a,則a≤b.于是這兩個(gè)式中必有一個(gè)成立.

第四十二頁，共八十七頁，2022年，8月28日定理7-3.8(Stone定理)設(shè)<B,∨,∧,ˉ>是有限布爾代數(shù)，M是B中所有原子構(gòu)成的集合，則<B,∨,∧,ˉ>與<P(M),∪,∩,~>同構(gòu)。證明:構(gòu)造映射f:BP(M)對(duì)于x∈B先通過下邊例子了解映射f的形式:

f(x)={Φx=0{a|a∈M,a≤x}x≠030。3。1。2。5。10。15。6。12356101530Φ{2}{3}{5}{2,3}{2,5}{3,5}{2,3,5}BP(M)f第四十三頁，共八十七頁，2022年，8月28日1).先證明f是雙射.

a).證明f是入射:只有x=0時(shí),才有f(x)=Φ.

任取x1,x2∈B,x1≠0

x1≠0且x1≠x2,由定理3-7.6得,x1,x2可以寫成如下形式:x1=a1∨a2∨…∨ak其中ai≤x1(1≤i≤k)x2=b1∨b2∨…∨bm其中bj≤x2(1≤j≤m)因?yàn)槊總€(gè)非0元素寫成上述表達(dá)式的形式是唯一的,又因?yàn)閤1≠x2,所以{a1,a2,...,ak}≠{b1,b2,…,bm}.由f定義得f(x1)={a1,a2,...,ak}f(x2)={b1,b2,…,bm}故f(x1)≠f(x2)f入射.

b).證明f滿射:任取M1∈P(M)如果M1為Φ,則f(0)=M1

,如果M1≠Φ,令M1={a1,a2,...,ak},由∨的封閉性得,必存在x∈B,使得a1∨a2∨…∨ak=x,顯然每個(gè)ai≤x(1≤i≤k),故f(x)=M1,所以f是滿射的.最后由a)b)得f是雙射的.第四十四頁，共八十七頁，2022年，8月28日2).證明f滿足三個(gè)同構(gòu)關(guān)系式.任取x1,x2∈B,因?yàn)閒是雙射,必有M1,M2∈P(M),使得

f(x1)=M1,f(x2)=M2,a).證明f(x1∧x2)=f(x1)∩f(x2)=M1∩M2,令f(x1∧x2)=M3,即證明M3=M1∩M2

先證M3M1∩M2

如果M3=Φ顯然有M3M1∩M2如果M3≠Φ,任取a∈M3,由f定義得a≤x1∧x2,又因?yàn)閤1∧x2≤x1,

x1∧x2≤x2,所以a≤x1a≤x2由f定義得a∈f(x1)a∈f(x2)即a∈M1a∈M2,故a∈M1∩M2,所以M3M1∩M2第四十五頁，共八十七頁，2022年，8月28日再證M1∩M2M3

如果M1∩M2=Φ顯然有M1∩M2M3如果M1∩M2≠Φ,任取a∈M1∩M2a∈M1a∈M2所以a是滿足a≤x1與a≤x2的原子,a≤x1∧x2由f定義得,a∈f(x1∧x2),即a∈M3所以M1∩M2M3

所以M3=M1∩M2

即f(x1∧

x2)=f(x1)∩f(x2)

第四十六頁，共八十七頁，2022年，8月28日b).證明f(x1∨

x2)=f(x1)∪f(x2)=M1∪M2,

令f(x1∨x2)=M4,即證明M4=M1∪M2先證M4M1∪M2

如果M4=Φ顯然有M4M1∪M2如果M4≠Φ,任取a∈M4,由f定義得a≤x1∨x2,則必有a≤x1,或者a≤x2,

(因?yàn)槿绻鸻≤x1與a≤x2都不成立,由定理7-3.7得必有

與a是原子矛盾,所以a≤x1或a≤x2)由f定義得a∈f(x1)即a∈M1或a∈f(x2)即a∈M2所以a∈M1∪

M2,所以M4M1∪M2第四十七頁，共八十七頁，2022年，8月28日再證M1∪M2

M4

如果M1∪M2

=Φ顯然有M1∪M2

M4如果M1∪M2≠Φ,任取a∈M1∪M2a∈M1或者a∈M2如果a∈M1則a≤x1a≤x1≤x1∨x2∴a∈f(x1∨x2),a∈M4如果a∈M2則a≤x2a≤x2≤x1∨x2∴a∈f(x1∨x2),a∈M4所以M1∪M2

M4

M4=M1∪M2與a≤x2的原子,由f定義得,即所以M1∩M2M4

所以M4=M1∩M2

即f(x1∨

x2)=f(x1)∪f(x2)第四十八頁，共八十七頁，2022年，8月28日3).證明于是有x1∨x2=1x1∧x2=0f(x1∨x2)=Mf(x1∧x2)=Φf(x1∨x2)=f(x1)∪f(x2)=M1∪M2=Mf(x1∧x2)=f(x1)∩f(x2)=M1∩M2=Φ所以M2=~M1即由1).2).3)得

f(x1∧x2)=f(x1)∩f(x2)f(x1∨x2)=f(x1)∪f(x2)所以<B,∨,∧,ˉ>與<P(M),∪,∩,~>同構(gòu)。第四十九頁，共八十七頁，2022年，8月28日推論1.任何有限布爾代數(shù)的元素個(gè)數(shù)為2n(n=1,2,3,…)因?yàn)閨P(M)|=2n推論2.兩個(gè)有限布爾代數(shù)同構(gòu)的充分且必要條件是其元素個(gè)數(shù)相同。1。e。0。d。f。b。c。a。0。1。01a

b第五十頁，共八十七頁，2022年，8月28日本節(jié)重點(diǎn)掌握布爾代數(shù)的性質(zhì)，同構(gòu)概念，Stone定理及其推論。作業(yè)P260（2）

Φ{c}4eqpx7k{a}{a,c,d}{a,b,d}{b,c,d}{a,b,c}{b,c}{a,d}{b,d}{a,c}{a,b,c,d}{c,d}{a,b}第五十一頁，共八十七頁，2022年，8月28日7-4.布爾表達(dá)式

一.布爾表達(dá)式概念1.定義：設(shè)<B,∨,∧,ˉ>是布爾代數(shù)，其上的布爾表達(dá)式遞歸定義如下：1)B中任何元素是個(gè)布爾表達(dá)式。2)任何變?cè)獂是個(gè)布爾表達(dá)式。3)如果E1,E2是個(gè)布爾表達(dá)式,則,(E1∧E2),(E1∨E2)也是布爾表達(dá)式。4)有限次地應(yīng)用規(guī)則1)2)3)得到的符號(hào)串都是布爾表達(dá)式。例如令B={0,1,a,b}(a∨),((x∧y)∨),*表達(dá)式的最外層括號(hào)可以省略.E1ˉbˉ

(x1∨)———第五十二頁，共八十七頁，2022年，8月28日2.對(duì)布爾表達(dá)式賦值：設(shè)<B,∨,∧,ˉ>是布爾代數(shù)，含有變?cè)獂1,x2…xn的布爾表達(dá)式記作E(x1,x2,…xn),對(duì)變?cè)獂1,x2,…,xn分別用B中元素代替的過程，稱之為對(duì)布爾表達(dá)式賦值。例如B={0,1,a,b}E(x1,x2)=E(a,b)====b一個(gè)的布爾表達(dá)式E(x1,x2,…xn),經(jīng)過賦值以后，就得到一個(gè)值(即是B中一個(gè)元素)。3.兩個(gè)布爾表達(dá)式相等:設(shè)<B,∨,∧,ˉ>是布爾代數(shù)，含有變?cè)獂1,x2,…xn的兩個(gè)布爾表達(dá)式E1(x1,x2,…xn)和E2(x1,x2,…xn),如果不論對(duì)變?cè)獂1,x2…xn分別用B中任何元素賦值,都使得E1和E2的值相同,則稱這兩個(gè)表達(dá)式相等,記作E1(x1,x2,…,xn)=E2(x1,x2,…,xn)01a

b(x1∨)———(a∨)———a∨a____aˉ第五十三頁，共八十七頁，2022年，8月28日我們可以通過布爾代數(shù)的性質(zhì)(10個(gè))得到很多等式.如,E1(x,y)=x∨(y∧)E2(x,y)=x∨yE1(x,y)=x∨(y∧)=(x∨y)∧(x∨)=(x∨y)∧1=x∨y=E2(x,y)二.布爾函數(shù)設(shè)<B,∨,∧,ˉ>是一個(gè)布爾代數(shù)，一個(gè)從BnB的函數(shù)被稱為n元布爾函數(shù)。含有變?cè)獂1,x2,…,xn的布爾表達(dá)式E(x1,x2,…xn),可以看成是一個(gè)BnB的布爾函數(shù).布爾函數(shù)有兩種表示方法:1.表達(dá)式方法:例如B={0,1}<B,∨,∧,ˉ>是布爾代數(shù)，即是表達(dá)式表示法.2.函數(shù)表法:見下面:第五十四頁，共八十七頁，2022年，8月28日例：B={0,1,2,3}，<B,∨,∧,ˉ>是布爾代數(shù)在其上定義的一個(gè)布爾函數(shù)f(x,y)的函數(shù)表如右圖所示:<x,y>f(x,y)<x,y>f(x,y)<0,0>

1<2,0>

2<0,1>

0<2,1>

0<0,2>

0<2,2>

1<0,3>

3<2,3>

1<1,0>

1<3,0>

3<1,1>

1<3,1>

0<1,2>

0<3,2>

2<1,3>

3<3,3>

3第五十五頁，共八十七頁，2022年，8月28日三.布爾表達(dá)式的范式

1.兩元素布爾代數(shù)的布爾表達(dá)式的范式:<{0,1},∨,∧,ˉ>是兩個(gè)元素的布爾代數(shù)

1).析取范式

(1).小項(xiàng):含有n個(gè)變?cè)男№?xiàng)形式為:其中例如都是小項(xiàng).

(2).布爾表達(dá)式的析取范式:含有變?cè)獂1,x2,…,xn的布爾表達(dá)式E(x1,x2,…xn),如果寫成如下形式:A1∨A2∨...∨Am(m≥1)其中每個(gè)Ai(1≤i≤m)都是有n個(gè)變?cè)男№?xiàng).則稱此式是E(x1,x2,…xn)的析取范式.例如:第五十六頁，共八十七頁，2022年，8月28日

2).合取范式

(1).大項(xiàng):含有n個(gè)變?cè)拇箜?xiàng)形式為:其中例如都是大項(xiàng).(2).布爾表達(dá)式的合取范式:含有變?cè)獂1,x2,…,xn的布爾表達(dá)式E(x1,x2,…xn),如果寫成如下形式:A1∧A2∧...∧Am(m≥1)其中每個(gè)Ai(1≤i≤m)都是有n個(gè)變?cè)拇箜?xiàng).則稱此式是E(x1,x2,…xn)的合取范式.例如:3).析取范式與合取范式的寫法:

方法1:列真值表

方法2:表達(dá)式的等價(jià)變換.第五十七頁，共八十七頁，2022年，8月28日方法1.用真值表求析取范式:先介紹小項(xiàng)的性質(zhì),以兩個(gè)變?cè)獂1,x2為例每一組賦值,有且僅有一個(gè)小項(xiàng)為1.根據(jù)一組賦值,求值為1的小項(xiàng):如果變?cè)獂,被賦值為0,則在此小項(xiàng)中,x以形式出現(xiàn);如果變?cè)獂,被賦值為1,則在此小項(xiàng)中,x以原形x形式出現(xiàn).求E(x1,x2,…xn)的析取范式:先列出它的真值表,找出表中每個(gè)1對(duì)應(yīng)的小項(xiàng),然后用∨連接上述小項(xiàng).

001000

010100

100010

110001第五十八頁，共八十七頁，2022年，8月28日例如,求布爾代數(shù)<{0,1},∨,∧,ˉ>上的布爾表達(dá)式E(x1,x2,x3)=x1∧(x2∨)的析取范式.E(x1,x2,x3)=(x1∧∧)∨(x1∧x2∧)∨(x1∧x2∧x3)x3ˉ

x1x2x3E(x1,

x2,

x3)

0010

0100

0110

1001

1010

1101

0000

1111x3ˉx3ˉx2ˉ第五十九頁，共八十七頁，2022年，8月28日方法1.用真值表求合取范式:先介紹大項(xiàng)的性質(zhì),以兩個(gè)變?cè)獂1,x2為例每一組賦值,有且僅有一個(gè)大項(xiàng)為0.根據(jù)一組賦值,求值為0的大項(xiàng):如果變?cè)獂,被賦值為1,則在此小項(xiàng)中,x以形式出現(xiàn);如果變?cè)獂,被賦值為0,則在此小項(xiàng)中,x以原形x形式出現(xiàn).求E(x1,x2,…xn)的合取范式:先列出它的真值表,找出表中每個(gè)0對(duì)應(yīng)的大項(xiàng),然后用∧連接上述大項(xiàng).

000111

011011

101101

111110第六十頁，共八十七頁，2022年，8月28日例如,求布爾代數(shù)<{0,1},∨,∧,ˉ>上的布爾表達(dá)式E(x1,x2,x3)=x1∧(x2∨)的合取范式.E(x1,x2,x3)=(x1∨x2∨x3)∧(x1∨x2∨)∧(x1∨∨x3)∧(x1∨∨)∧(∨x2∨)x3ˉ

x1x2x3E(x1,

x2,

x3)

0010

0100

0110

1001

1010

1101

0000

1111x3ˉx2ˉx3ˉx1ˉx2ˉx3ˉ第六十一頁，共八十七頁，2022年，8月28日方法2.用表達(dá)式的等價(jià)變換求析取范式:E(x1,x2,x3)=x1∧(x2∨)=(x1∧x2)∨(x1∧)=(x1∧x2∧(x3∨))∨(x1∧(x2∨)∧)=(x1∧x2∧x3)∨(x1∧x2∧)∨(x1∧x2∧

)∨(x1∧∧)=(x1∧x2∧x3)∨(x1∧x2∧)∨(x1∧∧)結(jié)果與前相同.用表達(dá)式的等價(jià)變換求合取范式:E(x1,x2,x3)=x1∧(x2∨)=(x1∨(x2∧)∨(x3∧))∧((x1∧)∨x2∨)=(x1∨x2∨x3)∧(x1∨x2∨)∧(x1∨∨x3)∧(x1∨∨)∧(x1∨x2∨)∧(∨x2∨)=(x1∨x2∨

x3)∧(x1∨x2∨)∧(x1∨∨x3)∧(x1∨∨)∧(∨x2∨)x3ˉx3ˉx2ˉx2ˉx3ˉx3ˉx3ˉx3ˉx3ˉx3ˉx2ˉx3ˉx3ˉx3ˉx2ˉx1ˉx3ˉx3ˉx2ˉx1ˉx3ˉx3ˉx2ˉx3ˉx3ˉx2ˉx1ˉx3ˉx3ˉx2ˉ第六十二頁，共八十七頁，2022年，8月28日*2.一般布爾代數(shù)的布爾表達(dá)式的范式:<B,∨,∧,ˉ>是布爾代數(shù),含有變?cè)獂1,x2,…,xn的布爾表達(dá)式E(x1,x2,…xn),1).小項(xiàng):是由n個(gè)變?cè)虰中元素構(gòu)成的如下形式,，稱為小項(xiàng).其中Cδ1δ2...δn為B中元素,稱之為小項(xiàng)的系數(shù).例如B={0,1,a,b},下面就是E(x1,x2,x3)中的小項(xiàng):

第六十三頁，共八十七頁，2022年，8月28日2).布爾表達(dá)式E(x1,x2,...xn)的析取范式:E(x1,x2,…,xn)是含有變?cè)獂1,x2,…,xn的布爾表達(dá)式，如果等價(jià)的寫成如下形式:A1∨A2∨...∨Am(m≥1)其中每個(gè)Ai(1≤i≤m)都是有n個(gè)變?cè)男№?xiàng).則稱此式是E(x1,x2,…,xn)的析取范式.定理7-4.1.設(shè)<B,∨,∧,ˉ>是布爾代數(shù),含有變?cè)獂1,x2,…,xn的布爾表達(dá)式為E(x1,x2,…xn),則該布爾表達(dá)式可以寫成析取范式的形式.第六十四頁，共八十七頁，2022年，8月28日類似地,E(x1,x2,…xn)的合取范式為:E(x1,x2,…xn)=(x1∨x2∨...∨xn∨E(0,0,…,0))∧(x1∨x2∨...∨xn-1∨∨E(0,0,…0,1))∧...∧(∨∨...∨∨xn∨E(1,1,…,1,0))∧(∨∨...∨∨E(1,1,…,1))其中E(0,0…,0),E(0,0,…0,1),…,E(1,1,…1,0)和E(1,1,…,1)就是所謂的“系數(shù)”.實(shí)際上,求E(x1,x2,…xn)的析取或者合取范式時(shí),就是求這些“系數(shù)”.下面看一個(gè)例子.xnˉx1ˉx2ˉxnˉx1ˉx2ˉxn-1ˉ第六十五頁，共八十七頁，2022年，8月28日已知<B,∨,∧,ˉ>是布爾代數(shù),其中B={0,a,b,1}分別求出下面布爾表達(dá)式的析取范式和合取范式.解.先求四個(gè)系數(shù):析取范式為:第六十六頁，共八十七頁，2022年，8月28日合取范式為:一般的布爾函數(shù)不一定都能寫成布爾表達(dá)式的形式。例：設(shè)B={0,1,2,3},<B,∨,∧,ˉ>是布爾代數(shù)，在其上定義的一個(gè)布爾函數(shù)g(x,y)，其函數(shù)表如下圖所示:證明其不能用一個(gè)布爾表達(dá)式將其表示。第六十七頁，共八十七頁，2022年，8月28日例：B={0,1,2,3},<B,∨,∧,ˉ>是布爾代數(shù),

在其上定義的一個(gè)布爾函數(shù)g(x,y),其函數(shù)表如右圖所示:<x,y>g(x,y)<x,y>g(x,y)<0,0>

1<2,0>

2<0,1>

0<2,1>

0<0,2>

0<2,2>

1<0,3>

3<2,3>

1<1,0>

1<3,0>

3<1,1>

1<3,1>

0<1,2>

0<3,2>

2<1,3>

3<3,3>

3第六十八頁，共八十七頁，2022年，8月28日證明：用反證法。若g(x,y)能被布爾表達(dá)式表示，則其必可寫成析取范式的形式,設(shè)其為：而g(1,1)=1,g(1,0)=1,g(0,1)=0,g(0,0)=1所以對(duì)于布爾格<{0,1,2,3},?>，其哈斯圖為考查g(3,3)=(2∧2)∨(3∧2)∨(3∧3)=2∨0∨3=101

23第六十九頁，共八十七頁，2022年，8月28日而在表中g(shù)(3,3)=2，矛盾，所以該函數(shù)不能用布爾表達(dá)式表示。第七十頁，共八十七頁，2022年，8月28日本節(jié)重點(diǎn)掌握內(nèi)容：布爾表達(dá)式定義、析取范式和合取范式的寫法。本章內(nèi)容小結(jié)：1.格的概念、格的性質(zhì).格的同構(gòu).2.分配格的性質(zhì)、判斷.有界格有補(bǔ)格布爾格概念性質(zhì).3.布爾代數(shù)的性質(zhì),Stone定理的應(yīng)用.4.布爾表達(dá)式定義,范式的寫法.第七十一頁，共八十七頁，2022年，8月28日

習(xí)題課

———格與布爾代數(shù)第七十二頁，共八十七頁，2022年，8月28日P242(1).(a)不是格，因?yàn)閐和e沒有下確界,也沒有上確界.(d)不是格，5和6沒有下確界,7和