離散數(shù)學(xué)-第6章格與布爾代數(shù)課件

代數(shù)系統(tǒng)

第六章 格和布爾代數(shù) §1格的概念 §2分配格 §3有補(bǔ)格

1代數(shù)系統(tǒng) 第六章 格和布爾代數(shù)1§6-1格的概念偏序集<A,?>{a,b}最小上界最大下界{e,f}最大下界最小上界注意：今后把{a，b}的最小上界（最大下界）稱為元素a，b的最小上界（最大下界）。{a,b}最小上界c最大下界無{e,f}最大下界d最小上界無2§6-1格的概念偏序集<A,?>{a,b}最小上§6-1格的概念共同的特性：在這些偏序集中，任何兩個(gè)元素都有最小上界和最大下界。3§6-1格的概念共同的特性：在這些偏序集中，任何兩個(gè)元素一、格定義1設(shè)<A,?>是一個(gè)偏序集，如果A中任意兩個(gè)元素都有最小上界和最大下界，則稱<A,?>為格。復(fù)習(xí)§6-1格的概念4一、格復(fù)習(xí)§6-1格的概念4§6-1格的概念5§6-1格的概念5§6-1格的概念6§6-1格的概念6§6-1格的概念7§6-1格的概念7§6-1格的概念例：<I+，|>：a|b當(dāng)且僅當(dāng)a整除b<

(S)，>任意兩元素a,b的最小上界：最小公倍數(shù)最大下界：最大公約數(shù)任意兩元素S1,S2的最小上界：S1∪S2最大下界：S1∩S2稱為正整數(shù)格8§6-1格的概念例：<I+，|>：a|b當(dāng)且僅§6-1格的概念例：給定S={a，b}，

(S)={

,{a},,{a,b}}，那么，格<

(S)，

>如圖所示。{a,b}{a}

9§6-1格的概念例：給定S={a，b}，(S)={§6-1格的概念定義2設(shè)<A,?>是一個(gè)格，如果在A上定義兩個(gè)二元運(yùn)算∨和∧，使得對(duì)于a,bA，a∨b等于a和b的最小上界(LUB)，a∧b等于a和b的最大下界(GLB)，則稱<A,∨,∧>為由格<A,?>所誘導(dǎo)的代數(shù)系統(tǒng)。二元運(yùn)算∨和∧分別稱為并運(yùn)算和交運(yùn)算。復(fù)習(xí)10§6-1格的概念定義2設(shè)<A,?>是一個(gè)格，如果在A§6-1格的概念例：1.<I+，|>2.<

(S)，>

3.<A，≤>

<I+，∨，∧>∨：最小公倍數(shù)（lcm）∧：最大公約數(shù)（gcd）<

(S)，∨，∧>∨：集合的并∪∧：集合的交∩<A，∨，∧>，A:{1,2,3,4,5}

a∨b=max(a,b)a∧b=min(a,b)11§6-1格的概念例：1.<I+，|><§6-1格的概念

4.設(shè)nI+，In={x|xI+，(x|n)},<In,|>為格，當(dāng)n=20時(shí)，I20={1,2,4,5,10,20}，<I20,|>如圖：20104251x∨y=lcm(x,y),x∧y=gcd(x,y)則<In，∨，∧>是由格<In,|>所誘導(dǎo)的代數(shù)系統(tǒng)12§6-1格的概念

4.設(shè)nI+，In={x|§6-1格的概念二、子格定義3設(shè)<A,?>是一個(gè)格，由格<A,?>所誘導(dǎo)的代數(shù)系統(tǒng)為<A,∨,∧>，設(shè)BA且B≠

，如果A中的這兩個(gè)運(yùn)算∨和∧關(guān)于B是封閉的，則稱<B,?>是<A,?>的子格。注意：與子群概念的異同復(fù)習(xí)13§6-1格的概念二、子格復(fù)習(xí)13{a}{c}{b,c}{a,c}{a,b}{a,b,c}φ{(diào)b}<S1,

><S2,

><S3,

>

§6-1格的概念{a}{c}

{b,c}{a,c}{a,b}{a,b,c}φ{(diào)b}{a}{c}{b,c}{a,c}{a,b}{a,b,c}φ{(diào)b}例：A={a,b,c},<

(A),

>

(A)={

,{a},,{c},{a,b},{b,c},{c,a},{a,b,c}}S1={{a,b,c},{a,b},{b,c},}S2={{a,c},{a},{c},

}S3={{

,{a},{c},{a,b},{b,c},{c,a},{a,b,c}}是格，并且是<

(A),

>的子格是格，但不是<

(A),

>的子格因?yàn)閧a,b}∧{b,c}=S314{a}{c}{b,c}{a,c}{a,b}φ{(diào)b}<§6-1格的概念注意：對(duì)于格<A,?>，設(shè)B是A的非空子集，盡管<B,?>必定是一個(gè)偏序集，然而<B,?>不一定是格，即使<B,?>是格，也不一定是<A,?>的子格。15§6-1格的概念注意：對(duì)于格<A,?>，設(shè)B是A的非空格的主要性質(zhì)格的對(duì)偶原理:設(shè)<A,?>是格，“?”的逆關(guān)系“?R”與A組成的偏序集<A,?R>也是格。兩者互為對(duì)偶。前者的GLB(最大下界），LUB（最小上界）恰好是后者的LUB，GLB。如有關(guān)于<A,?>的有效命題P， (1)將“?”換成“≥”， (2)“”換成“”， (3)“”換成“”，便能得到<A,≥>的有效命題P’。反之亦然?！?-1格的概念16格的主要性質(zhì)§6-1格的概念16§6-1格的概念定理1

在一個(gè)格<A,?>中，對(duì)于任意的a,b

A，都有a?a∨b，b?a∨ba∧b?a，a∧b?b證明：因?yàn)閍∨b是a的一個(gè)上界所以a?a∨b同理b?a∨b由對(duì)偶原理得a∧b?a，a∧b?b復(fù)習(xí)17§6-1格的概念定理1在一個(gè)格<A,?>中，對(duì)于任意的§6-1格的概念定理2

在一個(gè)格<A,?>中，對(duì)于

a,b,c,d

A，如果有a?b，c?d，則：

a∨c?b∨da∧c?b∧d證明：因?yàn)閍∧c?aa∧c?c而a?b，c?d所以a∧c?ba∧c?d所以a∧c?b∧d復(fù)習(xí)18§6-1格的概念定理2在一個(gè)格<A,?>中，對(duì)于§6-1格的概念推論：(格的保序性）在一個(gè)格<A,?>中，對(duì)于a,b,c

A，如果有b?c，則

a∨b?a∨ca∧b?a∧c證明：因?yàn)閍?a，b?c依據(jù)定理2可得。復(fù)習(xí)19§6-1格的概念推論：(格的保序性）在一個(gè)格<A,?>定理3設(shè)<A,?>是一個(gè)格，由格<A,?>所誘導(dǎo)的代數(shù)系統(tǒng)為<A,∨,∧>，則對(duì)于

a,b,c,d

A，有：（１）交換律a∨b=b∨aa∧b=b∧a（２）結(jié)合律（a∨b）∨c=a∨（b∨c）（a∧b）∧c=a∧（b∧c）（３）冪等律a∨a=aa∧a=a（４）吸收律a∨（a∧b）=aa∧（a∨b）=a復(fù)習(xí)§6-1格的概念20定理3設(shè)<A,?>是一個(gè)格，由格<A,?>所誘導(dǎo)的代§6-1格的概念結(jié)合律（a∨b）∨c=a∨（b∨c）

證明：∵由定理1知b?b∨c?a∨(b∨c)

a?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∨b）∨c=a∨（b∨c）21§6-1格的概念結(jié)合律（a∨b）∨c=a∨（b∨c）§6-1格的概念冪等律a∨a=aa∧a=a證明：∵a?a∨a由自反性可知a?a∴a∨a?a（a∨a是最小上界）∴a∨a=a由對(duì)偶原理：a∧a=a22§6-1格的概念冪等律a∨a=aa∧a=a§6-1格的概念吸收律a∨（a∧b）=a,a∧（a∨b）=a證明：∵由定理1知a?a∨（a∧b）又∵a?a，a∧b?a∴a∨（a∧b）?a∴a∨（a∧b）=a

23§6-1格的概念吸收律a∨（a∧b）=a,a∧§6-1格的概念例：設(shè)<N,≤>是一個(gè)偏序集，N是自然數(shù)集，≤是“小于等于”關(guān)系，定義a∨b=max{a,b}（取大運(yùn)算）a∧b=min{a,b}（取小運(yùn)算）則<N,≤>是一個(gè)格。由此格誘導(dǎo)的代數(shù)系統(tǒng)為<N,∨,∧>。

則該代數(shù)系統(tǒng)的兩個(gè)運(yùn)算滿足交換律結(jié)合律等冪律吸收律24§6-1格的概念例：設(shè)<N,≤>是一個(gè)偏序集，N是自然數(shù)§6-1格的概念1.交換性：任意兩個(gè)數(shù)a和b的最大值（最小值）與b和a的最大值（最小值）是相等的。2.結(jié)合性：max(max(a,b),c)=max(a,max(b,c))都是三個(gè)數(shù)a,b,c中的最大值，所以∨是可結(jié)合的，min(min(a,b),c)=min(a,min(b,c))，說明∧是可結(jié)合的。3.冪等性：max(a,a)=min(a,a)=a4.吸收性：max(a,min(a,b))=amin(a,max(a,b))=a25§6-1格的概念1.交換性：任意兩個(gè)數(shù)a和b的最大值（§6-1格的概念引理：設(shè)<A,∨,∧>是一個(gè)代數(shù)系統(tǒng)，其中∨,∧都是二元運(yùn)算且滿足吸收性，則∨和∧都滿足冪等性。即要證，已知對(duì)于

a,b

A有a∨(a∧b)=a和a∧(a∨b)=a則:a∨a=aa∧a=a復(fù)習(xí)證明:∵a∨（a∧b）=a（吸收律）用（a∨b）代替b，得：a∨（a∧（a∨b））=a又∵a∧（a∨b）=a∴a∨a=a26§6-1格的概念引理：設(shè)<A,∨,∧>是一個(gè)代數(shù)系統(tǒng)，其§6-1格的概念定理4

設(shè)<A,∨,∧>是一個(gè)代數(shù)系統(tǒng)，其中∨,∧都是二元運(yùn)算且滿足交換性，結(jié)合性和吸收性，則A上存在偏序關(guān)系?，使<A,?>是一個(gè)格。復(fù)習(xí)證明思路：分四部分內(nèi)容來證明：(1)定義二元關(guān)系?：a?

b當(dāng)且僅當(dāng)(a∧b)=a(2)證明是偏序關(guān)系（證自反、反對(duì)稱和傳遞）；(3)證明a∧b是a和b的最大下界（下確界）；(4)根據(jù)∨、∧滿足交換律和吸收律，證明a∨b是a和b的最小上界（上確界）。27§6-1格的概念定理4設(shè)<A,∨,∧>是一個(gè)代數(shù)系統(tǒng)，首先證明?是偏序關(guān)系（1）∵∧滿足吸收律∴∧滿足冪等性(根據(jù)引理)即a∧a=a∴a?a

自反性（2）設(shè)a?b，則a∧b=a再設(shè)b?a，則b∧a=b∵∧滿足交換律∴a=b反對(duì)稱性

（3）設(shè)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)系證明:在A上定義二元關(guān)系?為：對(duì)于

a,b

A，a?b當(dāng)且僅當(dāng)(a∧b)=a28首先證明?是偏序關(guān)系（2）設(shè)a?b，則a∧b=a（3）設(shè)其次證明a∧b是a和b的最大下界a?b當(dāng)且僅當(dāng)a∧b=a

由于（a∧b）∧a=a∧b（a∧b）∧b=a∧b所以a∧b?a,a∧b?b

即a∧b是a和b的下界設(shè)c

A，是a和b的任一下界，即：c?a，c?bc∧a=cc∧b=c∵c∧(a∧b)=(c∧a)∧b=c∧b=c∴c?a∧b∴

a∧b是a和b的最大下界§6-1格的概念29其次證明a∧b是a和b的最大下界a?b當(dāng)且僅當(dāng)a∧b=a∴?即為：對(duì)于

a,b

A，a?b當(dāng)且僅當(dāng)a∨b=b最后，根據(jù)交換性和吸收性，由a∧b=a得

（a∧b）∨b=a∨b即b=a∨b反之由a∨b=b得a∧（a∨b）=a∧ba=a∧b∴a=a∧b

b=a∨b在A上定義二元關(guān)系?為：對(duì)于

a,b

A，a?b當(dāng)且僅當(dāng)a∧b=a類似的可證明a∨b是a和b的最小上界因此，<A,?>是一個(gè)格§6-1格的概念30∴?即為：對(duì)于a,bA，a?b當(dāng)且僅當(dāng)a∨b=b最§6-1格的概念定理5設(shè)<A,?>是一個(gè)格，則對(duì)于

a,b,c

A，有：

a∨（b∧c）?（a∨b）∧（a∨c）（a∧b）∨（a∧c）?a∧（b∨c）

（分配不等式）

復(fù)習(xí)31§6-1格的概念定理5設(shè)<A,?>是一個(gè)格，則對(duì)于a∨（b∧c）?（a∨b）∧（a∨c）證明：∵a?a∨ba?a∨c∴a=a∧a?（a∨b）∧（a∨c）（1）

又∵b∧c?b?a∨bb∧c?c?a∨c∴b∧c=(b∧c)∧(b∧c)?(a∨b)∧（a∨c）（2）∴a∨（b∧c）?（a∨b）∧（a∨c）利用對(duì)偶原理（a∧b）∨（a∧c）?a∧（b∨c）§6-1格的概念32a∨（b∧c）?（a∨b）∧（a∨c）又∵b§6-1格的概念定理6設(shè)<A,?>是一個(gè)格，則對(duì)于

a,b

A，有

a?b

a∧b=a

a∨b=b證明：先證a?b

a∧b=a（1）∵a?b，a?a，∴a?a∧b又∵a∧b?a，則a∧b=a（2）反之，假定a∧b=a則a=a∧b?b∴

a?b

∴

a?b

a∧b=a同理：

a?b

a∨b=b復(fù)習(xí)33§6-1格的概念定理6設(shè)<A,?>是一個(gè)格，則對(duì)于§6-1格的概念定理7設(shè)<A,?>是一個(gè)格，對(duì)于

a,b,c

A，有

a?c

a∨(b∧c)?(a∨b)∧c（模不等式）證明：由定理6a?c

a∨c=c由定理5a∨(b∧c)?(a∨b)∧(a∨c)

用c代替a∨ca∨(b∧c)?(a∨b)∧c∴a?c

a∨(b∧c)?(a∨b)∧c復(fù)習(xí)若a∨(b∧c)?(a∨b)∧c則a?a∨(b∧c)?(a∨b)∧c?c即a?c∴a∨(b∧c)?(a∨b)∧c

a?c∴a?c

a∨(b∧c)?(a∨b)∧c34§6-1格的概念定理7設(shè)<A,?>是一個(gè)格，對(duì)于a§6-1格的概念推論：在格<A,?>中，則對(duì)于

a,b,c

A，必有：（a∧b）∨（a∧c）?a∧（b∨（a∧c））a∨（b∧（a∨c））?（a∨b）∧（a∨c）

復(fù)習(xí)證明：∵(a∧b)∨(a∧c)?(a∨(a∧c))∧(b∨(a∧c))∴（a∧b）∨（a∧c）?a∧（b∨（a∧c））∵a∨(b∧(a∨c))?(a∨b)∧(a∨(a∨c))∴a∨(b∧(a∨c))?(a∨b)∧(a∨c)35§6-1格的概念推論：在格<A,?>中，則對(duì)于a,定義:設(shè)<A1,?1>和<A2,?2>是兩個(gè)格，由它們分別誘導(dǎo)的代數(shù)系統(tǒng)為<A1,∨1,∧1>和<A2,∨2,∧2>，若存在著一個(gè)從A1到A2的映射f，使得對(duì)于a,bA1，有f(a∨1b)=f(a)∨2

f(b)

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

f(b)則稱f為從<A1,∨1,∧1>到<A2,∨2,∧2>的格同態(tài)。稱<f(A1)，?2>是<A1，?1>的格同態(tài)象。當(dāng)f是雙射時(shí)，稱f為從<A1,∨1,∧1>到<A2,∨2,∧2>的格同構(gòu)。復(fù)習(xí)§6-1格的概念36定義:設(shè)<A1,?1>和<A2,?2>是兩個(gè)格，由它們§6-1格的概念定理8：(格同態(tài)的保序性）設(shè)f是<A1,?1>和<A2,?2>的格同態(tài)，則對(duì)x,yA1，如果x?1y，必有f(x)?2f(y)證明：∵x?1y∴x∧1y=xf(x∧1y)=f(x)=f(x)∧2

f(y)（同態(tài)公式）∴f(x)?2f(y)注意：定理8的逆命題是不一定成立的

格同態(tài)是保序的，但是保序的不一定是格同態(tài)復(fù)習(xí)37§6-1格的概念定理8：(格同態(tài)的保序性）證明：∵x但是，對(duì)于b,d

S，有b∨d=a

f(b∨d)=f(a)=Sf(b)∪f(d)={b,d,e}∴f(b∨d)

f(b)∪f(d)例：設(shè)<S,?>是一個(gè)格，其中S={a,b,c,d,e}，如圖則<

(S)，

>也是一個(gè)格。作f：S→

(S)，對(duì)x

S，使得f(x)={y|y

S，y?x}有f(a)=S,f(b)={b,e},f(c)={c,e},

feqogseu={d,e},f(e)={e}當(dāng)x,y

S且x?y時(shí)，有f(x)f(y)∴f是保序的adbce§6-1格的概念38但是，對(duì)于b,dS，有b∨d=a例：設(shè)<S,?>§6-1格的概念定理9：設(shè)兩個(gè)格<A1，?1>和<A2，?2>，f是從A1到A2的雙射，則f是<A1，?1>到<A2，?2>的格同構(gòu)，當(dāng)且僅當(dāng)對(duì)a,bA1，a?1b

f(a)?2

f(b)。復(fù)習(xí)證明：設(shè)f是<A1，?1>到<A2，?2>的格同構(gòu)。由定理8知對(duì)a,b

A1，若a?1b，必有f(a)?2f(b)反之，設(shè)f(a)?2f(b)，則f(a)∧2f(b)=f(a∧1b)=f(a)∵f是雙射∴a∧1b=a故a?1b39§6-1格的概念定理9：設(shè)兩個(gè)格<A1，?1>和<A2，§6-1格的概念設(shè)對(duì)a,bA1，a?1b

f(a)?2

f(b)設(shè)a∧1b=c，則c?1a，c?1b，有

f(a∧1b)=f(c)，f(c)?2

f(a)，f(c)?2

f(b)∴f(c)?2

f(a)∧2

f(b)設(shè)f(a)∧2

f(b)=f(d)，則

f(c)?2f(d)，f(d)?2

f(a)，f(d)?2

f(b)∴d?1a，d?1b∴d?1a∧1b即d?1c，f(d)?2

f(c)∴f(c)=f(d)即f(a∧1b)=f(a)∧2f(b)類似地可證f(a∨1b)=f(a)∨2f(b)因此，f是<A1，?1>到<A2，?2>的格同構(gòu)40§6-1格的概念設(shè)對(duì)a,bA1，a?1bf(代數(shù)系統(tǒng)

第六章 格和布爾代數(shù) §1格的概念 §2分配格 §3有補(bǔ)格

41代數(shù)系統(tǒng) 第六章 格和布爾代數(shù)41§6-2分配格 定義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）

則稱<A，?>是分配格。復(fù)習(xí)42§6-2分配格 定義1：設(shè)<A,∨,∧>是由格<A,討論定義：(1)定義中的兩式互為對(duì)偶式。(2)如<A,?>為非分配格，則有下面的分配不等式：a(bc)?(ab)(ac)(ab)(ac)?a(bc)(定理6-1.5)以及模不等式：a?ca(bc)?(ab)c(定理6-1.7)§6-2分配格 43討論定義：§6-2分配格 43例：S={a,b,c}

(S)={φ,{a},,{c},{a,b},{b,c},{c,a},{a,b,c}}<

(S),∪,∩>{a}{c}{b,c}{a,c}{a,b}{a,b,c}φ{(diào)b}對(duì)于

P,Q,R

(S),有P∩(Q∪R)=(P∩Q)∪(P∩R)P∪(Q∩R)=(P∪Q)∩(P∪R)則<

(S),

>是一個(gè)分配格§6-2分配格 44例：S={a,b,c}{a}{c}{b,c}{a,adbceabcde

b∧（c∨d）=b∧a=b（b∧c）∨（b∧d）=e∨e=e

c∧（b∨d）=c∧a=c（c∧b）∨（c∧d）=e∨d=d注意：一個(gè)格是分配格的充要條件是該格中沒有任何子格與這兩個(gè)五元素格中的任一個(gè)同構(gòu)。復(fù)習(xí)§6-2分配格 45adbceabcdeb∧（c∨d）=b∧a=babcdfge<{a,b,d,g,c},?>是格<{a,b,c,d,e,f,g},?>的子格，但不是分配格§6-2分配格 46abcdfge<{a,b,d,g,c},?>是定理1：如果格中交對(duì)并是分配的，那么并對(duì)交也是分配的，反之亦然。證明：已知a(bc)=(ab)(ac)

(ab)(ac)=((ab)a)((ab)c) =a((ab)c) =a((ac)(bc)) =(a(ac))(bc) =a(bc)即：并對(duì)交也是分配的。復(fù)習(xí)§6-2分配格 47定理1：如果格中交對(duì)并是分配的，那么并對(duì)交也證明：已知a§6-2分配格 定理2：每個(gè)鏈均是分配格。證明：設(shè)<A,?>是鏈。則<A,?>一定是格對(duì)

a，b，cA若a?b或a?c，則a(bc)=a(ab)(ac)=a即：a(bc)=(ab)(ac)(2)若b?a且c?a，則a(bc)=bc， (ab)(ac)=bc即：a(bc)=(ab)(ac)。復(fù)習(xí)48§6-2分配格 定理2：每個(gè)鏈均是分配格。證明：設(shè)<A,定理3設(shè)<A,?>是一個(gè)分配格，對(duì)于a,b,cA，如果有ab=ac和ab=ac成立，則必有b=c。證明：（ab）c=（ac）c=c而（ab）c=(ac)(bc)=(ab)(bc)=b（ac）=b（ab）=b所以b=c復(fù)習(xí)§6-2分配格 49定理3設(shè)<A,?>是一個(gè)分配格，對(duì)于a,b,c定義2設(shè)<A,∨,∧>是由格<A,?>所誘導(dǎo)的代數(shù)系統(tǒng)。如果對(duì)于a,b,cA，當(dāng)b?a時(shí)，有

a(bc)=b(ac)則稱<A,?>為模格。也稱戴德金格。定理6-1.7：設(shè)<A，?>是一個(gè)格，則對(duì)于

a,b,cA，有a?c

a∨（b∧c）?（a∨b）∧c（模不等式）(bc)a=b(ca)模律（模等式）復(fù)習(xí)§6-2分配格 50定義2設(shè)<A,∨,∧>是由格<A,?>所誘導(dǎo)的代數(shù)系定理4：格<A,?>是模格，當(dāng)且僅當(dāng)A中不含有適合下述條件的元素u，v，w

v﹤u且u∨w＝v∨w,u∧w=v∧w證明：(反證法)(1)存在這樣三個(gè)元素u,v,w滿足上式∵u∧（w∨v）=u∧（w∨u）=u（u∧w）∨v=（v∧w）∨v=v又∵v<u∴v∨（w∧u）<（v∨w）∧u模不等式∴<A,?>不是模格。§6-2分配格 51定理4：格<A,?>是模格，當(dāng)且僅當(dāng)A中不含有適合下述條件（2）若<A，?>不是模格，則存在a,b,c，當(dāng)b?a時(shí)，有b∨（c∧a）<（b∨c）∧a令v=b∨（c∧a），u=（b∨c）∧a，w=cu∧w=（（b∨c）∧a）∧c=a∧（（b∨c）∧c）=a∧c=（a∧c）∧c又∵（a∧c）?b∨（c∧a）∴（a∧c）∧c?b∨（c∧a）∧c即u∧w?v∧w§6-2分配格 52（2）若<A，?>不是模格，則存在a,b,因此，若<A，?>不是模格，就一定存在u，v，w∈A，使得v﹤u且u∨w＝v∨w,u∧w=v∧w。所以，定理成立。又∵v﹤u∴v∧w?u∧w故u∧w=v∧w同理：u∨w＝v∨w

§6-2分配格 53因此，若<A，?>不是模格，就一定存在u，v，w∈A，使定理5對(duì)于模格，若有三個(gè)元素a,b,c，使得上面三個(gè)式子的任何一個(gè)式子中把“?”換成“=”成立，則另外兩個(gè)式子中把“?”換成“=”也必成立。一般的格中，下式成立：（1）a

(b

c)?(a

b)

(a

c)（2）(a

b)

(a

c)?a

(b

c)（3）(a

b)(b

c)(c

a)?(a

b)(b

c)(c

a)§6-2分配格 54定理5對(duì)于模格，若有三個(gè)元素a,b,c，使得上面三證明：若（1）中=成立，則由對(duì)偶性（2）的=也成立(a

b)(b

c)(c

a)=((a

c)

b)(c

a)=((c

a)

b)

(a

c)=(ab)(bc)

(c

a)若（3）中=成立，則有a

(b

c)=a(a

b)(c

a)(b

c)=a

((a

b)

(b

c)

(c

a))=a

((b

c)(a

b)(c

a))=(a

b

c)

(a

b)

(c

a)=(a

b)(a

c)（1）a

（b

c）=（a

b）

（a

c）（2）（a

b）

（a

c）=a

（b

c）§6-2分配格 55證明：若（1）中=成立，則由對(duì)偶性（2）的=也成立若定理6：分配格必定是模格。證明：設(shè)<A,?>是一個(gè)分配格，對(duì)于a,b,cA

若b?a，則ab=b a(bc)=(ab)(ac)=b(ac) ∴分配格是模格§6-2分配格 56定理6：分配格必定是模格。證明：設(shè)<A,?>是一個(gè)分配格，注意：分配格一定是模格，但模格不一定是分配格。對(duì)于x，y，z∈{0，1，a，b，c}若有y?x,則只有y=0或x=101abc若y=0，則x(yz)=xzy(xz)=xz若x=1，則x(yz)=yzy(xz)=yz所以，x(yz)=y(xz)即該格是模格，但不是分配格?！?-2分配格 當(dāng)b?a時(shí)，有a(bc)=b(ac)57注意：分配格一定是模格，但模格不一定是分配格。對(duì)于x，y補(bǔ)充性質(zhì)：（1）四個(gè)元素以下的格都是分配格?！?-2分配格 58補(bǔ)充性質(zhì)：§6-2分配格 58（2）五個(gè)元素的格僅有兩個(gè)格是非分配格。§6-2分配格 59（2）五個(gè)元素的格僅有兩個(gè)格是非分配格。§6-2分配格 5代數(shù)系統(tǒng)

第六章 格和布爾代數(shù) §1格的概念 §2分配格 §3有補(bǔ)格

60代數(shù)系統(tǒng) 第六章 格和布爾代數(shù)60§6-3有補(bǔ)格定義1

設(shè)<A,?>是一個(gè)格，如果存在元素aA，對(duì)于xA，都有：a?x，則稱a為格<A,?>的全下界，記格的全下界為0。定義2

設(shè)<A,?>是一個(gè)格，如果存在元素bA，對(duì)于xA，都有：x?b，則稱b為格<A,?>的全上界，記格的全上界為1。61§6-3有補(bǔ)格定義1設(shè)<A,?>是一個(gè)格，如果存在元素§6-3有補(bǔ)格定理1、2如果格<A,?>有全上界（全下界），那么它是唯一的。證明：（反證法）設(shè)有兩個(gè)全上界a和b,a,bA且ab則由定義a?b，且b?a，由“?”的反對(duì)稱性，a=b。62§6-3有補(bǔ)格定理1、2證明：（反證法）62全下界：h全上界：a定義3如果一個(gè)格中存在全上界和全下界，則稱該格為有界格。例1：<

(S),

>中,全下界：φ全上界：Sabcdefgh例2：§6-3有補(bǔ)格63全下界：h定義3如果一個(gè)格中存在全上界和全下界，則稱該格定理3

如果<A,?>是有界格，全上界和全下界分別是1和0，則對(duì)任意元素aA，有：

a1=1a=1，a1=1a=a a0=0a=a，a0=0a=0證明:(1)∵(a1)A且1是全上界，∴a1?1又∵1?a1 ∴a1=1由交換律：1a＝a1=1(2)∵

a?a，a?1，∴aa?a1，即a?a1又∵a1?a∴a1=a由交換律：a1=1a=a

的幺元：0

的零元：1

的幺元：1

的零元：0§6-3有補(bǔ)格64定理3如果<A,?>是有界格，全上界和全下界分別是1和定義4設(shè)<A,?>是一個(gè)有界格，對(duì)于A中的一個(gè)元素a，如果存在bA，使得ab=1和ab=0，則稱元素b是元素a的補(bǔ)元。討論定義：（1）∵和是可交換的，∴補(bǔ)元是相互的。（2）在有界格中，1和0互為補(bǔ)元；（3）A中一個(gè)元素的補(bǔ)元不一定是唯一的；§6-3有補(bǔ)格65定義4設(shè)<A,?>是一個(gè)有界格，對(duì)于A中的一個(gè)元素a，如1abcd0e∵dc=1dc=0∴d和c互補(bǔ)d的補(bǔ)元：c和ea的補(bǔ)元：eb的補(bǔ)元：無c的補(bǔ)元：de的補(bǔ)元：a和d§6-3有補(bǔ)格∵dc=1dc=0∴d和c互補(bǔ)d的補(bǔ)元：a的補(bǔ)元：b的補(bǔ)元：c的補(bǔ)元：e的補(bǔ)元：661abcd0e∵dc=1dc=0定義5在一個(gè)有界格中，如果每個(gè)元素都至少有一個(gè)補(bǔ)元素，則稱此格為有補(bǔ)格。注意：（1）在有補(bǔ)格中，每一個(gè)元素一定存在補(bǔ)元（不一定只有一個(gè)補(bǔ)元）；（2）有補(bǔ)格一定是有界格，而有界格不一定是有補(bǔ)格。（3）有補(bǔ)格不一定是分配格，分配格不一定是有補(bǔ)格。§6-3有補(bǔ)格67定義5在一個(gè)有界格中，如果每個(gè)元素都至少有一個(gè)補(bǔ)元素，則1ab010abcd1abcd01abcd0(a)(b)(c)(d)下類有界格中哪個(gè)是有補(bǔ)格？§6-3有補(bǔ)格681ab010abcd1abcd01abcd0(a)(b)(c01abc0abc1（a）（b）(a)是分配格，不是有補(bǔ)格。(b)是有補(bǔ)格，不是分配格。§6-3有補(bǔ)格6901abc0abc1（a）（b）(a)是分配格，不是有補(bǔ)格。定理4在有界分配格中，若有一個(gè)元素有補(bǔ)元，則必是唯一的。證明：設(shè)a有兩個(gè)補(bǔ)元素b和c且b

c，即有

ab=1ab=0ac=1ac=0∴ab=acab=ac由定理6-2.3得b=c即a的補(bǔ)元是唯一的?！?-3有補(bǔ)格70定理4在有界分配格中，若有一個(gè)元素有補(bǔ)元，則必是唯一的。證定義6

一個(gè)格如果它既是有補(bǔ)格，又是分配格，則稱它為有補(bǔ)分配格。我們把有補(bǔ)分配格中任意元素a的唯一補(bǔ)元記為a。定義:一個(gè)有補(bǔ)分配格稱為布爾格。性質(zhì)：有補(bǔ)分配格中，每個(gè)元素都存在唯一的補(bǔ)元。（定理4的推論）§6-3有補(bǔ)格71定義6一個(gè)格如果它既是有補(bǔ)格，又是分配格，則稱它為有補(bǔ)分定義：由布爾格<A,?>，可以誘導(dǎo)一個(gè)包括交，并和補(bǔ)運(yùn)算的代數(shù)系統(tǒng)<A,,,->，稱此代數(shù)系統(tǒng)為布爾代數(shù)。例：設(shè)S是一個(gè)非空有限集，<(S),>是一個(gè)格，且是一個(gè)布爾格。由<(S),>所誘導(dǎo)的代數(shù)系統(tǒng)為

<(S),

,,->是一個(gè)布爾代數(shù)。其中“,,-”分別是集合的交、并、補(bǔ)運(yùn)算。若S有n個(gè)元素，該布爾代數(shù)的哈斯圖為n為立方體圖?！?-4布爾代數(shù)72定義：由布爾格<A,?>，可以誘導(dǎo)一個(gè)包括交，并例：設(shè)S01abccab{a}{c}{b,c}{a,c}{a,b}{a,b,c}φ{(diào)b}§6-4布爾代數(shù)7301abccab{a}{c}{b,c}{a,c}{a定義：一個(gè)格<L,≤>如果它既是有補(bǔ)格，又是分配格，則它為有補(bǔ)分配格。我們把有補(bǔ)分配格中任一元素a的唯一補(bǔ)元記為a。討論定義：(1)布爾格中，每個(gè)元素有唯一的補(bǔ)元。(2)我們可以定義L上的一個(gè)一元運(yùn)算，稱為補(bǔ)運(yùn)算，記為“-”。-§6-4布爾代數(shù)74-§6-4布爾代數(shù)74§6-4布爾代數(shù)定義：由布爾格<L,≤>，可以誘導(dǎo)一個(gè)包括交，并和補(bǔ)運(yùn)算的代數(shù)系統(tǒng)<L,,,->，稱此代數(shù)