第6章格與布爾代數(shù)

格論是近代數(shù)學(xué)的一個(gè)重要分支，由它所引出的布爾代數(shù)在計(jì)算機(jī)科學(xué)中有很多直接應(yīng)用。第六章格與布爾代數(shù)

格的概念分配格有補(bǔ)格布爾代數(shù)布爾表達(dá)式1、回憶偏序集〈A，≤〉，≤偏序關(guān)系：滿(mǎn)足自反性，反對(duì)稱(chēng)性，傳遞性。有限集合上的偏序集可用哈斯圖來(lái)表示：6-1格的概念

Hasse圖為:

{a,b}最小上界是c,無(wú)最大下界

{e,f}最大下界是d,無(wú)最小上界

因而任兩元素未必有最小上界，最大下界。而我們要介紹的格是一種特殊的偏序集——任兩元素均有最小上界和最大下界6-1格的概念

例1：〈I+,|〉a|b：a整除b——偏序關(guān)系。a,b最小上界：a,b的最小公倍數(shù)LCMa,b最大下界：a,b的最大公約數(shù)GCD∴〈I+,|〉是格例2：S——集合〈P(s),〉——偏序集。A,B∈P(s)

A，B最小上界：AB

A，B最大下界：AB∴這一偏序集是格2、格

〈A，≤〉是偏序集，若對(duì)a,b∈A，a,b有最大下界和最小上界，則稱(chēng)〈A，≤〉為格。一般可用Hasse圖表示格。6-1格的概念

例：用圖形判斷含1—5個(gè)元素的格：1—3個(gè)元素Hasse圖情況唯一6-1格的概念

3、格〈A，≤〉誘導(dǎo)的代數(shù)系統(tǒng)：在A上定義兩個(gè)運(yùn)算∧和∨：

a,b∈A，a∧b：a和b的最大下界

∧：交運(yùn)算

a∨b：a和b的最小上界

∨：并運(yùn)算則〈A，∨，∧〉稱(chēng)為由格〈A，≤〉誘導(dǎo)的代數(shù)系統(tǒng)例：A={1，2，3，6}?！碅，|〉→〈A，∨，∧〉∧也易求得∴〈A，∨，∧〉是格〈A，|〉誘導(dǎo)的代數(shù)系統(tǒng)6-1格的概念

4、格的對(duì)偶原理：

〈A，≤〉≤有逆關(guān)系≤c：≥；而〈A，≥〉也是一偏序關(guān)系

〈A，≤〉與〈A，≥〉是互為對(duì)偶的

〈A，≤〉是格，則〈A，≥〉也是格

a∨b=a∧cb哈斯圖互為顛倒有對(duì)偶原理：若P是〈A，≤〉格中真命題，若將P中≤換成≥，∨換成∧，∧換成∨，則得到另一命題P′，P′是P的對(duì)偶命題，且P′也是真命題所以，在證明格有關(guān)的命題時(shí)，證明一個(gè)，則另一個(gè)對(duì)偶式也成立。6-1格的概念

(3)傳遞性

a≤b，b≤c

a≤c；a≥b,b≥ca≥c(4)a≤a∨b；a∧b≤a；b≤a∨b；a∧b≤b(5)a≤c,b≤ca∨b≤c；

a≥c,b≥c

a∧b≥c(6)a≤b,c≤da∨c≤b∨d(a∧c≤b∧d)；

a≥b,c≥da∧c≥b∧d(a∨c≥b∨d)(7)保序性

b≤ca∨b≤a∨c,a∧b≤a∧c(8)交換性

a∨b=b∨a;a∧b=b∧a;5、格的基本性質(zhì)：設(shè)〈A，≤〉是格。

(1)自反性

a≤a|對(duì)偶a≥a(2)反對(duì)稱(chēng)性

a≤b,b≤aa=b.|對(duì)偶a≥b,b≥aa=b6-1格的概念

(9)結(jié)合性：a∨(b∨c）=(a∨b)∨c;a∧(b∧c)=(a∧b)∧c(10)等冪性：a∨a=a;a∧a=a(11)吸收性：a∨(a∧b)=a;a∧(a∨b)=a(12)分配不等式：a∨(b∧c)≤(a∨b)∧(a∨c)(a∧b)∨(a∧c)≤a∧(b∨c)(13)a≤ba∧b=a；a≤ba∨b=b(14)模不等式：a≤ca∨(b∧c)≤(a∨b)∧c6-1格的概念

6-1格的概念

證：只證（6）（11）其他書(shū)上有

(6)b≤b∨da≤b

a≤b∨d

∴a∨c≤b∨d.d≤b∨dc≤d

c≤b∨d

另一類(lèi)似可證(11)要證a≤a∨(a∧b)

a∨(a∧b)≤a

第一式顯然成立

a≤a

a∧b≤a∴a∨(a∧b)≤a∴a=a∨(a∧b)6、格的等價(jià)原理：格〈A，≤〉(1)引理6-1.1：〈A，∨，∧〉代數(shù)系統(tǒng)，若∨,∧滿(mǎn)足吸收性，則∨,∧滿(mǎn)足冪等性證：a,b∈A.a∨(a∧b)=aa∧(a∨b)=a.b用a∨b代替(∵兩式中b是相互獨(dú)立的)∴a∨(a∧(a∨b))=a即a∨a=a.(2)格的等價(jià)定理：〈A，∨，∧〉代數(shù)系統(tǒng)，∨.∧滿(mǎn)足交換性，結(jié)合性，吸收性，則A上存在偏序關(guān)系≤，使〈A，≤〉是一個(gè)格從格可引出代數(shù)系統(tǒng)〈A，∨，∧〉；而從滿(mǎn)足三個(gè)條件的〈A，∨，∧〉也可導(dǎo)出格〈A，≤〉證明見(jiàn)書(shū)：（格中⑻⑼⑾三個(gè)性質(zhì)很重要，決定了格）6-1格的概念

6-1格的概念

證：定義一個(gè)≤，a,bA,a≤ba∧b=a.可證≤是一偏序關(guān)系。1）自反性a∧a=a,a≤a(吸收性導(dǎo)出冪等性)。

2）反對(duì)稱(chēng)性a≤b,b≤aa∧b=a,b∧a=b.

交換性a∧b=a=b∧a=b∧a=ba＝b3)傳遞性a≤b,b≤c∴a∧b=a,b∧c=b,∴a∧c=(a∧b)∧c=a∧(b∧c)=a∧b=a∴a≤c.故≤是一偏序關(guān)系。

6-1格的概念

4）下面證明a∧b就是a,b的最大下界，即要證明 a∧b≤a,a∧b≤b且最大(a∧b)∧a=a∧(b∧a)=a∧(a∧b)=(a∧a)∧b=a∧b(a∧b)∧b=a∧(b∧b)=a∧b∴a∧b≤a,a∧b≤b即a∧b是a和b的下界。

設(shè)c是a∧b的任一下界，即c≤a,c≤b則c∧a=c,c∧b=cc∧(a∧b)=(c∧a)∧b=c∧b=c∴c≤a∧b故a∧b是a和b的最大下界6-1格的概念

若a∧b=a則a∨b=(a∧b)∨b=b反之，若a∨b=b則a∧b=a∧(a∨b)=a ∴a∧b=aa∨b=b故A上偏序關(guān)系a≤ba∧b=aa∨b=b可類(lèi)似證明得a∨b是a,b的最小上界。因此?A,≤?是一個(gè)格5）下面證明a∧b=aa∨b=b7、子格：由格?A,≤?誘導(dǎo)的代數(shù)系統(tǒng)為?A,∨,∧?。設(shè)BA,且B，如果A中的這兩個(gè)運(yùn)算∧和∨關(guān)于B是封閉的（B中任兩元在A中的最小上界和最大下界也在B中），則稱(chēng)?B,≤?是?A,≤?的子格例：?I+，｜?格→?I+

，∨，∧?a∨b=LCM(a,b)a∧b=GCD(a,b)又∵兩個(gè)偶數(shù)的GCD，LCM均是偶數(shù)。∴E+正偶數(shù)全體，∨、∧封閉，?E+

，｜?是?I+

，｜?的子格。注意：

?A，≤?格，BA,B,?B,≤?未必是格，且若即使是格，也未必是子格。6-1格的概念

例：S={a,b,c,d,e,f,g,h}

?S,≤

?是格

S3={a,b,c,d,e,g,h}

?S3,≤

?也是格，但不是?S,≤

?的子格∵b∧d=fS3.在S3中b∧d=h6-1格的概念

8、格同態(tài)和格同構(gòu)：

設(shè)?A1,≤1?和?A2,≤2?都是格，它們誘導(dǎo)的代數(shù)系統(tǒng)分別是：?A1,∨1,∧1?和?A2,∨2,∧2?。若存在映射f:A1→A2使得對(duì)a,bA1,有f(a∨1b)=f(a)∨2f(b),f(a∧1b)=f(a)∧2f(b)則稱(chēng)f是從?A1,∨1,∧1?到?A2,∨2,∧2?的格同態(tài)，稱(chēng)?f(A1),≤2?為格?A1,≤1?的格同態(tài)象。若f是雙射，則稱(chēng)f是從?A1,∨1,∧1?到?A2,∨1,∧1?的格同構(gòu)，稱(chēng)?A1,≤1?和?A2,≤2?格同構(gòu)的。6-1格的概念

例：A1={1,2,3,6},?A1,｜?格，?A1,∨1,∧1?；

A2=P(s),S={a,b},?A2,

?格，?A2,∨2,∧2

?

雙射f:A1→A2為：

f(1)=，f(2)={a}，f(3)=，f(6)={a,b}易得f(a∨1b)=f(a)∨2f(b)；

f(a∧1b)=f(a)∧2f(b)∴?A1,｜?與?A2,?同構(gòu)兩個(gè)格同構(gòu)時(shí)，其哈斯圖是相同的，僅是標(biāo)記不同。6-1格的概念

9、同態(tài)的性質(zhì)：（1）保序性：設(shè)f是格?A1,≤1?到?A2,≤2?的格同態(tài)，則對(duì)x,yA1，若x≤1y,則必有f(x)≤2f(y)格同態(tài)必保序，但反之未必，保序的映射未必同態(tài)。（2）雙向保序性：設(shè)?A1,≤1?和?A2,≤2?是格，f是A1到A2的雙射，則f是?A1,≤1?到?A2,≤2?的格同構(gòu)對(duì)a,bA1,a≤1b當(dāng)且僅當(dāng)f(a)≤2f(b)6-1格的概念

證：∵x≤1y，∴x∧1y=x（格性質(zhì)）f(x∧1y)=f(x),∴f(x)∧2f(y)=f(x)f(x)≤2f(y)6-1格的概念

證

f:?A1,≤1?→?A2,≤2?的格同構(gòu)由定理知a,bA,a≤1bf(a)≤2f(b)反之設(shè)f(a)≤2f(b)∴f(a)∧2f(b)=f(a)=f(a∧1b)f是雙射，∴a∧1b=a,故a≤1b已知a,bA,a≤1bf(a)≤2f(b)要證格同構(gòu)保運(yùn)算設(shè)a∧1b=c.要證f(a∧1b)=f(a)∧2f(b)f(a∨1b)=f(a)∨2f(b)c≤1a,c≤1b∴f(c)≤2f(a)f(c)≤2f(b)f(a∧1b)=f(c)f(c)≤2f(a)∧2f(b)6-1格的概念

設(shè)f(a)∧2f(b)=f(d)f滿(mǎn)射，則f(c)≤2f(d)而f(d)≤2f(a),f(d)≤2f(b)由條件d≤1a,d≤1b∴d≤1a∧1b=c從而f(d)≤2f(c)故f(d)=f(c)即f(a)∧2f(b)=f(a∧1b)同理可得f(a∨1b)=f(a)∨2f(b)∴f是格同構(gòu)。格性質(zhì)中第12條有對(duì)任意格具有分配不等式：a∨(b∧c)≤(a∨b)∧(a∨c),(a∧b)∨(a∧c)≤a∧(b∨c)若上述兩式變?yōu)榈仁剑礉M(mǎn)足分配律，則此格稱(chēng)為分配格1、分配格定義：設(shè)?A,∨,∧?是由格A誘導(dǎo)的代數(shù)系統(tǒng)，若對(duì)a,b,cA有a∨(b∧c)=(a∨b)∧(a∨c)和a∧(b∨c)=(a∧b)∨(a∧c)則稱(chēng)?A,≤?是分配格6-2分配格

例：S={a,b,c},?P(s),?格，?P(S),∪，∩?對(duì)P，Q，RP(S),P∪(Q∩R)=（P∪Q）∩(P∪R)

P∩(Q∪R)=（P∩Q）∪(P∩R)所以?P(S),?是分配格格未必一定是分配格！6-2分配格

例：(a)中：b∨(c∧d)=b∨e=b；

(b∨c)∧(b∨d)=a∧a=a(b)中：c∧(b∨d)=c∧a=c；

(c∧b)∨(c∧d)=e∨d=d6-2分配格

2、分配格相關(guān)定理：①在一個(gè)格中，若交運(yùn)算對(duì)于并運(yùn)算可分配，則并運(yùn)算對(duì)交運(yùn)算也一定可分配，反之也成立（在分配格中定義中兩個(gè)等式只要有一個(gè)成立即可將一個(gè)格判定為分配格）6-2分配格

證：對(duì)a,b,c若a∧(b∨c)=(a∧b)∨(a∧c)則(a∨b)∧(a∨c)=((a∨b)∧a)∨((a∨b)∧c)=a∨((a∨b)∧c)=a∨((a∧c)∨(b∧c))=(a∨(a∧c))∨(b∧c)=a∨(b∧c)反之易得證2、分配格相關(guān)定理：②每個(gè)鏈?zhǔn)欠峙涓?-2分配格

證：?A,≤?偏序集a,bA,有a≤b或b≤a，則?A,≤?是鏈。它的哈斯圖排成直線(xiàn)。顯然?A,≤?是格。只要證a,b,cA有a∧(b∨c)=(a∧b)∨(a∧c)即可。2、分配格相關(guān)定理：②每個(gè)鏈?zhǔn)欠峙涓?-2分配格

分兩種情況：（1）a≤b或a≤c(a不是最大元（三者中）)（2）b≤a且c≤a（三者中a最大）

①無(wú)論b≤c或c≤b,a∧(b∨c)=a.(a∧b)∨(a∧c)=a∴a∧(b∨c)=(a∧b)∨(a∧c)②b∨c≤a,a∧(b∨c)=b∨c,(a∧b)∨(a∧c)=b∨c∴a∧(b∨c)=(a∧b)∨(a∧c)2、分配格相關(guān)定理：6-2分配格

定理：一個(gè)格是分配格（元素≥5）的充要條件是該格中沒(méi)有任何一個(gè)子格與書(shū)P244中圖6-2.2（a）或（b）中的任一個(gè)同構(gòu)。6-2分配格

n=1,2,3,4時(shí)情形易證aced

f子格bbdecf與其同構(gòu)，所以不是分配格6-2分配格

定理：分配格是模格。6-2分配格

3、模格定義：abcde不是模格，也不是分配格∵d＜c,但c∧(d∨b)=c∧a=cd∨(c∧b)=d∨e=dabecd是模格，不是分配格6-2分配格

abecd是模格，不是分配格6-2分配格

用定義證明任意x≤y,x∨(y∧z)=(x∨z)∧y.∵若x=y時(shí)此時(shí)顯然成立（吸收性）討論x≤y,x≠y的情形只有取x=e或y=a時(shí)才可能有x<y.

（1）x=e時(shí)y=b,c,d類(lèi)似（對(duì)稱(chēng)）6-2分配格

不妨取x=e,y=b.則e∨(b∧z)=b∧z(e∨z)∧b=z∧b∵e最小∴等式成立。（2）y=a,x=b時(shí)

b∨(a∧z)=b∨z,(b∨z)∧a=b∨z(∵a最大)∴等式成立因而，模格未必是分配格1、有界格：

?A,≤?是格，若a∈A時(shí)，x∈A,都有a≤x,則稱(chēng)a為格?A,≤?的全下界，記為0定理：一個(gè)格?A,≤?若有全下界，則是唯一的（即A的最小元）?A,≤?是格，若b∈A,

x∈A,都有x≤b,則稱(chēng)b為格?A,≤?的全上界，記為1定理：一個(gè)格?A,≤?若有全上界，則是唯一的（即A的最大元）6-3有補(bǔ)格

反證法：假設(shè)有兩個(gè)全下界a,b∈A,ab因?yàn)閍是全下界，b∈A,所以a≤b又b是全下界，a∈A,所以b≤a,從而a=b矛盾，所以a唯一。例：<(S),>,S有限集，全下界為，全上界為S，則為有界格定理：?A,≤?是有界格，則對(duì)a∈A,必有

a∨0=a,a∧1=a a∧0=0,a∨1=1即0，1分別是∨，∧的幺元，又分別是∧，∨的零元若一個(gè)格存在全上界和全下界，則稱(chēng)該格為有界格6-3有補(bǔ)格

6-3有補(bǔ)格

證明：

因?yàn)閍≤a,0是全下界，所以

0≤a,所以

a∨0≤a

又a∨0≧a故a∨0=a.

因?yàn)?是全下界

a∧0∈A,所以

0≤a∧0

而a∧0≤0所以a∧0=0,其他兩個(gè)同理類(lèi)似可證

2、有補(bǔ)格：（1）補(bǔ)元定義：?A,≤?是有界格，對(duì)于a∈A,若存在b∈A，使得a∨b=1,和a∧b=0，則稱(chēng)b是a的補(bǔ)元。b是a的補(bǔ)元，則稱(chēng)a也是b的補(bǔ)元（互為補(bǔ)元）

在有界格中，一個(gè)元素，可以沒(méi)有補(bǔ)元，也可以有多個(gè)補(bǔ)元b沒(méi)有補(bǔ)元

0-1互為補(bǔ)元a,d是e的補(bǔ)元

a:補(bǔ)元ec,e是d的

補(bǔ)元

b無(wú)補(bǔ)元c:補(bǔ)元為d6-3有補(bǔ)格

（2）有補(bǔ)格定義：在一個(gè)有界格中，每個(gè)元素都至少有一個(gè)補(bǔ)元，則稱(chēng)此格為有補(bǔ)格例：

下圖中都是有補(bǔ)格111000ababcdabcd16-3有補(bǔ)格

（3）定理：在有界分配格中，若元素a有補(bǔ)元素，則必是唯一的

證明：設(shè)a有兩個(gè)補(bǔ)元b,c，則

a∨b=1=a∨ca∧b=0=a∧c

有分配格性質(zhì)可得：b=c（4）布爾格：一個(gè)格若既是有補(bǔ)格，又是分配格，則稱(chēng)為有補(bǔ)分配格，也稱(chēng)布爾格。其中的任一元素a的唯一補(bǔ)元用來(lái)記，即是a的補(bǔ)元。

6-3有補(bǔ)格

首先，格是由偏序集?A,≤?引出的

若其中每任兩元有最小上界，最大下界，則為格

若格滿(mǎn)足分配等式，誘導(dǎo)運(yùn)算∨，∧可分配，則為分配格若格有0，1，則為有界格若有界格中任一元有補(bǔ)元，則為有補(bǔ)格分配格+有補(bǔ)格=>布爾格小結(jié)模格未必是分配格，分配格必是模格a,b∈A,<A,≤>是格

1.aba>b（∵a，b可以無(wú)關(guān)系

）

2.有界格未必是有限格，而有限格必是有界格偏序集?A,≤?格分配格有界格有補(bǔ)格布爾格偏序集格分配格有界格有補(bǔ)格布爾格小結(jié)1、布爾代數(shù)：由布爾格<A,≤>誘導(dǎo)的代數(shù)系統(tǒng)<A,∨,∧,ˉ>稱(chēng)為布爾代數(shù)6-4布爾代數(shù)6-4布爾代數(shù)

{a,b,c}{b,c}{a,c}{c}{a}{a,b}若：S={a,b,c}6-4布爾代數(shù)

2、性質(zhì)：6-4布爾代數(shù)

3、布爾代數(shù)的同構(gòu)2）著重研究有限布爾代數(shù)之間的同構(gòu)6-4布爾代數(shù)

4、有限布爾代數(shù)：

<A，∨，∧，ˉ>是布爾代數(shù)，若A是有限集，則稱(chēng)<A，∨，∧，ˉ>為有限布爾代數(shù)對(duì)于有限布爾代數(shù)，<A，∨，∧，ˉ>、<B，∨，∧，ˉ>若|A|=|B|，則A≌B，而且對(duì)任一有限布爾代數(shù)系統(tǒng)，元素個(gè)數(shù)必有2n

（1）原子：<A,≤>是格，且存在全下界0，若a∈A，a蓋住0，則稱(chēng)a為原子（第一個(gè)比0大的元素）6-4布爾代數(shù)

d,e是原子d≠e，d∧e=0一般來(lái)說(shuō)，任兩個(gè)原子交必為0aced01b定理：〈A，≤〉是有下界0的有限格，則對(duì)于b≠0，b∈A，都存在原子a∈A,使得a≤b。（即一定有某條路徑，往下走經(jīng)過(guò)原子到達(dá)0）6-4布爾代數(shù)

定理：〈A，≤〉是有下界0的有限格，則對(duì)于b≠0，b∈A，都存在原子a∈A,使得a≤b。（即一定有某條路徑，往下走經(jīng)過(guò)原子到達(dá)0）6-4布爾代數(shù)

證：（1）若b是原子，則b≤b成立。（2）若b不是原子，一定存在b1,使得0<b1<b若b1是原子，則成立。若b1不是原子，存在b2∈A,使得0<b2<b1<b∵〈A，≤〉是有限格∴經(jīng)過(guò)有限步，找到0<bi<……<b2<b1<b,

而bi是原子∴bi<b（2）Stone表示定理：引理1：布爾格中，b∧=0

b≤c(或∨c=1(對(duì)偶))

6-4布爾代數(shù)

證：要證b≤c,只須證b∨c=cb∧=0,∴（b∧）∨c=0∨c=c

而左邊=(b∨c)∧（∨c）=（b∨c）∧1=b∨c∴b∨c=c

從而b≤c

若b≤c則b∧≤c∧=0

而0是全下界

，0≤b∧

∴b∧=0

（2）Stone表示定理：引理2：〈A，∨，∧，‐>有限布爾代數(shù)中，0≠b∈A，a1,a2……ak是所有滿(mǎn)足ai≤b的原子，則

b=a1∨a2∨……∨ak并且這種表示是唯一的（也就是說(shuō)，任一非零元，我們可用原子來(lái)唯一表示它。）6-4布爾代數(shù)

分兩部分證明：

1）引理：〈A，∨，∧，ˉ〉有限布爾代數(shù)，0≠b∈A，

a1,a2……,ak是所有滿(mǎn)足ai≤b的原子，則b=a1∨a2∨……∨ak（2）Stone表示定理：6-4布爾代數(shù)

證：記a1∨a2∨……∨ak=c,要證b=c∵ai≤b∴b是a1,a2,……ak的上界而c是a1,a2,……ak的最小上界∴c≤b下證b≤c用上述引理只要證b∧=0反證：設(shè)b∧≠0，則存在原子a，使得0<a≤b∧而b∧≤b∴a≤b,a≤而a1,a2,……ak是ai≤b的所有原子∴a∈∴a≤c而a≤故a≤∧c=0∴a=0與a是原子矛盾故b∧=0b≤c從而b=c（2）Stone表示定理：6-4布爾代數(shù)

2)表示法是唯一的

b=a1∨a2∨……∨ak，假設(shè)b=b1∨b2∨……∨bt，

bi（i=1……t）是原子∵bi≤b∴bi∈t≤k要證t=k反證法假設(shè)t<k至少存在aiai∧=ai∧分配展開(kāi)(ai∧b1)∨（ai∧b2）∨……∨（ai∧bt）=（ai∧a1）∨（ai∧a2）∨……∨（ai∧ai）∨……∨（ai∧ak）∵a,b是原子，a≠b時(shí)，a∧b=0?！嘧筮?0，右邊=ai，ai=0矛盾，∴t=k（2）Stone表示定理：引理3：布爾格<A,≤>中，對(duì)于任意原子a∈A，另一個(gè)元素b≠0，b∈A，則a≤b,和a≤

中有且僅有一個(gè)成立。

6-4布爾代數(shù)

證：（1）假設(shè)a≤b，a≤

，則a≤b∧=0，∴a=0與a

是原子矛盾∴兩式不可能同時(shí)成立。

（2）至少有一個(gè)成立。∵a∧b≤a，a是原子。

∴a∧b=0或a∧b=a。

若a∧b=0，則a∧（）=0，∴a≤.若a∧b=a，則a≤b.（2）Stone表示定理：Stone表示定理：<A,∨,∧,―>有限布爾代數(shù)，S是<A,≤>中所有原子的集合，則<A,∨,∧,―>≌<P(S),∪,∩,~>6-4布爾代數(shù)

（3）Stone表示定理的推論：①有限布爾格元素個(gè)數(shù)必定等于2n

，n是原子個(gè)數(shù)，即|A|=2n=|P(s)|②任何兩個(gè)具有相同元素個(gè)數(shù)的有限次布爾代數(shù)是同構(gòu)的|P(S)|=|P(Q)||S|=|Q|6-4布爾代數(shù)

1、布爾表達(dá)式：（1）布爾變?cè)喝≈禐锳中元素的變?cè)?lt;A,∨,∧,ˉ>布爾代數(shù))（2）布爾常元：A中元素（3）布爾表達(dá)式按下列規(guī)則定義：

①

單個(gè)布爾常元是布爾表達(dá)式③如果e1,e2是布爾表達(dá)式，則,(e1∨e2)，（e1∧e2）是布爾表達(dá)式②

單個(gè)布爾變?cè)遣紶柋磉_(dá)式④只有有限次使用（1）～（3）后得到的符號(hào)串是布爾表達(dá)式6-5布爾表達(dá)式

布爾表達(dá)式的定義類(lèi)似于以前所介紹的命題邏輯中的命題公式，謂詞邏輯中的謂詞公式。它們之間有一定的聯(lián)系，以后我們就可以看出，命題邏輯是一種特殊的布爾代數(shù)（取值T或F）。因而研究布爾代數(shù)很有意義。例：<{1,a,b,0}，∨，∧，ˉ>布爾代數(shù)

a∨x1 ——一元布爾表達(dá)式

b∧——二元布爾表達(dá)式

6-5布爾表達(dá)式

2、

n元布爾表達(dá)式：

含有n個(gè)不同的布爾變?cè)谋磉_(dá)式，記為E(x1，……，xn)。布爾表達(dá)式的值：將A中的元素代入表達(dá)式中變?cè)?所得到的值，也稱(chēng)對(duì)表達(dá)式賦值.例： <{1,a,b,0}，∨，∧，ˉ>布爾代數(shù)含四個(gè)元素的布爾格一定是此形狀：0是全下界，1是全上界；而a、b必?zé)o關(guān)系，否則a無(wú)補(bǔ)元，不是布爾格ab01E(x1,x2)=(1∧x1)∨x2——二元布爾表達(dá)式取x1=a,x2=b,E(a,b)=(1∧a)∨b=a∨b=16-5布爾表達(dá)式

3、n元布爾表達(dá)式的等價(jià)（相等）：E1(x1,x2,……,xn)和E2(x1,x2,……,xn)，若對(duì)任意的<x1,x2,…xn>∈An，兩布爾表達(dá)式的值相等，則稱(chēng)E1和E2等價(jià)，記E1(x1,x2,……,xn)=E2(x1,x2,……,xn)

（即任意賦值相等則等價(jià)）例：<{0，1}，∨，∧，ˉ>布爾代數(shù)

E1(x1,x2,x3)=(x1∧x2)∨

E2(x1,x2,x3)=由<A,≤>布爾格，可直接利用其性質(zhì)化簡(jiǎn)得E1=E2（分配性）6-5布爾表達(dá)式

列出所有可能的值：x1x2x3E1(x1,x2,x3) E2(x1,x2,x3)000 0 0001 0 0010 0 0011 0 0100 1 1101 0 0110 1 1111 1 1∴E1=E26-5布爾表達(dá)式

4、布爾函數(shù)在<A，∨，∧，ˉ>布爾代數(shù)中，a,b∈A，E(x1,x2,……xn)∵a∨b∈A；a∧b∈A；∈A∴E<x1,x2,…xn>∈A∴n元布爾表達(dá)式是An→A的函數(shù)若函數(shù)An

→A是n元布爾表達(dá)式則為布爾函數(shù).

對(duì)<A，∨，∧，ˉ>，是否任一An→A的函數(shù)都是布爾表達(dá)式？不一定！6-5布爾表達(dá)式

5、布爾表達(dá)式的析取，合取范式： 在命題邏輯中，我們討論了任一命題公式的主析取，主合取范式。主析取范式是小項(xiàng)的并，主合取范式是大項(xiàng)的交，即將命題公式規(guī)范化；類(lèi)似地，我們引進(jìn)布爾小項(xiàng)，布爾大項(xiàng)。（1）布爾小項(xiàng)：其中是xi或

（2）布爾大項(xiàng)：其中是xi或大項(xiàng)，小項(xiàng)各有2n個(gè)，用m0，m1，……

表示小項(xiàng)

用M0，M1，……

表示大項(xiàng)6-5布爾表達(dá)式

（3）析取范式：是形如下列的布爾表達(dá)式

m0= m1=

… =其中（i=0,1,……,）∈A，mi為布爾小項(xiàng)（類(lèi)似于命題邏輯中的主析取范式）6-5布爾表達(dá)式

（4）合取范式：是形如下列的布爾表達(dá)式，其中Mi為布爾大項(xiàng)∵∈A∴有|A|種取法因而共有個(gè)不同的析取范式和合取范式而f：A→B有 個(gè)不同函數(shù)∴f：→A有個(gè)不同函數(shù)6-5布爾表達(dá)式

定理：布爾代數(shù)<A，∨，∧，ˉ>上的任一布爾表達(dá)式E(x1,x2,……xn)都唯一地等價(jià)于某個(gè)析取范式，或者唯一地等價(jià)于某個(gè)合