离散数学第6章格与布尔代数课件

代数系统

第六章 格和布尔代数 §1格的概念 §2分配格 §3有补格

1代数系统 第六章 格和布尔代数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格的概念共同的特性：在这些偏序集中，任何两个元素都有最小上界和最大下界。3§6-1格的概念共同的特性：在这些偏序集中，任何两个元素一、格定义1设<A,≼>是一个偏序集，如果A中任意两个元素都有最小上界和最大下界，则称<A,≼>为格。复习§6-1格的概念4一、格复习§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当且仅当a整除b<(S)，>任意两元素a,b的最小上界：最小公倍数最大下界：最大公约数任意两元素S1,S2的最小上界：S1∪S2最大下界：S1∩S2称为正整数格8§6-1格的概念例：<I+，|>：a|b当且仅§6-1格的概念例：给定S={a，b}，(S)={,{a},{b},{a,b}}，那么，格<(S)，

>如图所示。{a,b}{b}{a}9§6-1格的概念例：给定S={a，b}，(S)={§6-1格的概念定义2设<A,≼>是一个格，如果在A上定义两个二元运算∨和∧，使得对于a,bA，a∨b等于a和b的最小上界(LUB)，a∧b等于a和b的最大下界(GLB)，则称<A,∨,∧>为由格<A,≼>所诱导的代数系统。二元运算∨和∧分别称为并运算和交运算。复习10§6-1格的概念定义2设<A,≼>是一个格，如果在A§6-1格的概念例：1.<I+，|>2.<(S)，>

3.<A，≤>

<I+，∨，∧>∨：最小公倍数（lcm）∧：最大公约数（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.设nI+，In={x|xI+，(x|n)},<In,|>为格，当n=20时，I20={1,2,4,5,10,20}，<I20,|>如图：20104251x∨y=lcm(x,y),x∧y=gcd(x,y)则<In，∨，∧>是由格<In,|>所诱导的代数系统12§6-1格的概念

4.设nI+，In={x|§6-1格的概念二、子格定义3设<A,≼>是一个格，由格<A,≼>所诱导的代数系统为<A,∨,∧>，设BA且B≠

，如果A中的这两个运算∨和∧关于B是封闭的，则称<B,≼>是<A,≼>的子格。注意：与子群概念的异同复习13§6-1格的概念二、子格复习13{a}{c}{b,c}{a,c}{a,b}{a,b,c}φ{b}<S1,><S2,><S3,>

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

{b,c}{a,c}{a,b}{a,b,c}φ{b}{a}{c}{b,c}{a,c}{a,b}{a,b,c}φ{b}例：A={a,b,c},<(A),>(A)={,{a},{b},{c},{a,b},{b,c},{c,a},{a,b,c}}S1={{a,b,c},{a,b},{b,c},{b}}S2={{a,c},{a},{c},}S3={{,{a},{c},{a,b},{b,c},{c,a},{a,b,c}}是格，并且是<(A),>的子格是格，但不是<(A),>的子格因为{a,b}∧{b,c}={b}S314{a}{c}{b,c}{a,c}{a,b}φ{b}<§6-1格的概念注意：对于格<A,≼>，设B是A的非空子集，尽管<B,≼>必定是一个偏序集，然而<B,≼>不一定是格，即使<B,≼>是格，也不一定是<A,≼>的子格。15§6-1格的概念注意：对于格<A,≼>，设B是A的非空格的主要性质格的对偶原理:设<A,≼>是格，“≼”的逆关系“≼R”与A组成的偏序集<A,≼R>也是格。两者互为对偶。前者的GLB(最大下界），LUB（最小上界）恰好是后者的LUB，GLB。如有关于<A,≼>的有效命题P， (1)将“≼”换成“≥”， (2)“”换成“”， (3)“”换成“”，便能得到<A,≥>的有效命题P’。反之亦然。§6-1格的概念16格的主要性质§6-1格的概念16§6-1格的概念定理1

在一个格<A,≼>中，对于任意的a,bA，都有a≼a∨b，b≼a∨ba∧b≼a，a∧b≼b证明：因为a∨b是a的一个上界所以a≼a∨b同理b≼a∨b由对偶原理得a∧b≼a，a∧b≼b复习17§6-1格的概念定理1在一个格<A,≼>中，对于任意的§6-1格的概念定理2

在一个格<A,≼>中，对于a,b,c,dA，如果有a≼b，c≼d，则：

a∨c≼b∨da∧c≼b∧d证明：因为a∧c≼aa∧c≼c而a≼b，c≼d所以a∧c≼ba∧c≼d所以a∧c≼b∧d复习18§6-1格的概念定理2在一个格<A,≼>中，对于§6-1格的概念推论：(格的保序性）在一个格<A,≼>中，对于a,b,cA，如果有b≼c，则

a∨b≼a∨ca∧b≼a∧c证明：因为a≼a，b≼c依据定理2可得。复习19§6-1格的概念推论：(格的保序性）在一个格<A,≼>定理3设<A,≼>是一个格，由格<A,≼>所诱导的代数系统为<A,∨,∧>，则对于a,b,c,dA，有：（１）交换律a∨b=b∨aa∧b=b∧a（２）结合律（a∨b）∨c=a∨（b∨c）（a∧b）∧c=a∧（b∧c）（３）幂等律a∨a=aa∧a=a（４）吸收律a∨（a∧b）=aa∧（a∨b）=a复习§6-1格的概念20定理3设<A,≼>是一个格，由格<A,≼>所诱导的代§6-1格的概念结合律（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格的概念结合律（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由对偶原理：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格的概念例：设<N,≤>是一个偏序集，N是自然数集，≤是“小于等于”关系，定义a∨b=max{a,b}（取大运算）a∧b=min{a,b}（取小运算）则<N,≤>是一个格。由此格诱导的代数系统为<N,∨,∧>。

则该代数系统的两个运算满足交换律结合律等幂律吸收律24§6-1格的概念例：设<N,≤>是一个偏序集，N是自然数§6-1格的概念1.交换性：任意两个数a和b的最大值（最小值）与b和a的最大值（最小值）是相等的。2.结合性：max(max(a,b),c)=max(a,max(b,c))都是三个数a,b,c中的最大值，所以∨是可结合的，min(min(a,b),c)=min(a,min(b,c))，说明∧是可结合的。3.幂等性：max(a,a)=min(a,a)=a4.吸收性：max(a,min(a,b))=amin(a,max(a,b))=a25§6-1格的概念1.交换性：任意两个数a和b的最大值（§6-1格的概念引理：设<A,∨,∧>是一个代数系统，其中∨,∧都是二元运算且满足吸收性，则∨和∧都满足幂等性。即要证，已知对于a,bA有a∨(a∧b)=a和a∧(a∨b)=a则:a∨a=aa∧a=a复习证明:∵a∨（a∧b）=a（吸收律）用（a∨b）代替b，得：a∨（a∧（a∨b））=a又∵a∧（a∨b）=a∴a∨a=a26§6-1格的概念引理：设<A,∨,∧>是一个代数系统，其§6-1格的概念定理4

设<A,∨,∧>是一个代数系统，其中∨,∧都是二元运算且满足交换性，结合性和吸收性，则A上存在偏序关系≼，使<A,≼>是一个格。复习证明思路：分四部分内容来证明：(1)定义二元关系≼：a≼

b当且仅当(a∧b)=a(2)证明是偏序关系（证自反、反对称和传递）；(3)证明a∧b是a和b的最大下界（下确界）；(4)根据∨、∧满足交换律和吸收律，证明a∨b是a和b的最小上界（上确界）。27§6-1格的概念定理4设<A,∨,∧>是一个代数系统，首先证明≼是偏序关系（1）∵∧满足吸收律∴∧满足幂等性(根据引理)即a∧a=a∴a≼a

自反性（2）设a≼b，则a∧b=a再设b≼a，则b∧a=b∵∧满足交换律∴a=b反对称性

（3）设a≼b，b≼c，则a∧b=a，b∧c=b∵a∧c=（a∧b）∧c=a∧（b∧c）=a∧b=a

∴

a≼c传递性即≼是偏序关系证明:在A上定义二元关系≼为：对于a,bA，a≼b当且仅当(a∧b)=a28首先证明≼是偏序关系（2）设a≼b，则a∧b=a（3）设其次证明a∧b是a和b的最大下界a≼b当且仅当a∧b=a

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

即a∧b是a和b的下界设cA，是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当且仅当a∧b=a∴≼即为：对于a,bA，a≼b当且仅当a∨b=b最后，根据交换性和吸收性，由a∧b=a得

（a∧b）∨b=a∨b即b=a∨b反之由a∨b=b得a∧（a∨b）=a∧ba=a∧b∴a=a∧bb=a∨b在A上定义二元关系≼为：对于a,bA，a≼b当且仅当a∧b=a类似的可证明a∨b是a和b的最小上界因此，<A,≼>是一个格§6-1格的概念30∴≼即为：对于a,bA，a≼b当且仅当a∨b=b最§6-1格的概念定理5设<A,≼>是一个格，则对于a,b,cA，有：

a∨（b∧c）≼（a∨b）∧（a∨c）（a∧b）∨（a∧c）≼a∧（b∨c）

（分配不等式）

复习31§6-1格的概念定理5设<A,≼>是一个格，则对于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）利用对偶原理（a∧b）∨（a∧c）≼a∧（b∨c）§6-1格的概念32a∨（b∧c）≼（a∨b）∧（a∨c）又∵b§6-1格的概念定理6设<A,≼>是一个格，则对于a,bA，有

a≼ba∧b=aa∨b=b证明：先证a≼ba∧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≼ba∧b=a同理：

a≼ba∨b=b复习33§6-1格的概念定理6设<A,≼>是一个格，则对于§6-1格的概念定理7设<A,≼>是一个格，对于a,b,cA，有

a≼ca∨(b∧c)≼(a∨b)∧c（模不等式）证明：由定理6a≼ca∨c=c由定理5a∨(b∧c)≼(a∨b)∧(a∨c)

用c代替a∨ca∨(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≼c∴a∨(b∧c)≼(a∨b)∧ca≼c∴a≼ca∨(b∧c)≼(a∨b)∧c34§6-1格的概念定理7设<A,≼>是一个格，对于a§6-1格的概念推论：在格<A,≼>中，则对于a,b,cA，必有：（a∧b）∨（a∧c）≼a∧（b∨（a∧c））a∨（b∧（a∨c））≼（a∨b）∧（a∨c）

复习证明：∵(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,≼>中，则对于a,定义:设<A1,≼1>和<A2,≼2>是两个格，由它们分别诱导的代数系统为<A1,∨1,∧1>和<A2,∨2,∧2>，若存在着一个从A1到A2的映射f，使得对于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>的格同态。称<f(A1)，≼2>是<A1，≼1>的格同态象。当f是双射时，称f为从<A1,∨1,∧1>到<A2,∨2,∧2>的格同构。复习§6-1格的概念36定义:设<A1,≼1>和<A2,≼2>是两个格，由它们§6-1格的概念定理8：(格同态的保序性）设f是<A1,≼1>和<A2,≼2>的格同态，则对x,yA1，如果x≼1y，必有f(x)≼2f(y)证明：∵x≼1y∴x∧1y=xf(x∧1y)=f(x)=f(x)∧2

f(y)（同态公式）∴f(x)≼2f(y)注意：定理8的逆命题是不一定成立的

格同态是保序的，但是保序的不一定是格同态复习37§6-1格的概念定理8：(格同态的保序性）证明：∵x但是，对于b,dS，有b∨d=a

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

f(b)∪f(d)例：设<S,≼>是一个格，其中S={a,b,c,d,e}，如图则<(S)，>也是一个格。作f：S→(S)，对xS，使得f(x)={y|yS，y≼x}有f(a)=S,f(b)={b,e},f(c)={c,e},

f{d}={d,e},f(e)={e}当x,yS且x≼y时，有f(x)f(y)∴f是保序的adbce§6-1格的概念38但是，对于b,dS，有b∨d=a例：设<S,≼>§6-1格的概念定理9：设两个格<A1，≼1>和<A2，≼2>，f是从A1到A2的双射，则f是<A1，≼1>到<A2，≼2>的格同构，当且仅当对a,bA1，a≼1bf(a)≼2

f(b)。复习证明：设f是<A1，≼1>到<A2，≼2>的格同构。由定理8知对a,bA1，若a≼1b，必有f(a)≼2f(b)反之，设f(a)≼2f(b)，则f(a)∧2f(b)=f(a∧1b)=f(a)∵f是双射∴a∧1b=a故a≼1b39§6-1格的概念定理9：设两个格<A1，≼1>和<A2，§6-1格的概念设对a,bA1，a≼1bf(a)≼2

f(b)设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)设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>的格同构40§6-1格的概念设对a,bA1，a≼1bf(代数系统

第六章 格和布尔代数 §1格的概念 §2分配格 §3有补格

41代数系统 第六章 格和布尔代数41§6-2分配格 定义1：设<A,∨,∧>是由格<A,≼>所诱导的代数系统。如果对于任意的a,b,cA，满足：

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

则称<A，≼>是分配格。复习42§6-2分配格 定义1：设<A,∨,∧>是由格<A,讨论定义：(1)定义中的两式互为对偶式。(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},{b},{c},{a,b},{b,c},{c,a},{a,b,c}}<(S),∪,∩>{a}{c}{b,c}{a,c}{a,b}{a,b,c}φ{b}对于P,Q,R(S),有P∩(Q∪R)=(P∩Q)∪(P∩R)P∪(Q∩R)=(P∪Q)∩(P∪R)则<(S),>是一个分配格§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注意：一个格是分配格的充要条件是该格中没有任何子格与这两个五元素格中的任一个同构。复习§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：如果格中交对并是分配的，那么并对交也是分配的，反之亦然。证明：已知a(bc)=(ab)(ac)

(ab)(ac)=((ab)a)((ab)c) =a((ab)c) =a((ac)(bc)) =(a(ac))(bc) =a(bc)即：并对交也是分配的。复习§6-2分配格 47定理1：如果格中交对并是分配的，那么并对交也证明：已知a§6-2分配格 定理2：每个链均是分配格。证明：设<A,≼>是链。则<A,≼>一定是格对

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)。复习48§6-2分配格 定理2：每个链均是分配格。证明：设<A,定理3设<A,≼>是一个分配格，对于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复习§6-2分配格 49定理3设<A,≼>是一个分配格，对于a,b,c定义2设<A,∨,∧>是由格<A,≼>所诱导的代数系统。如果对于a,b,cA，当b≼a时，有

a(bc)=b(ac)则称<A,≼>为模格。也称戴德金格。定理6-1.7：设<A，≼>是一个格，则对于a,b,cA，有a≼ca∨（b∧c）≼（a∨b）∧c（模不等式）(bc)a=b(ca)模律（模等式）复习§6-2分配格 50定义2设<A,∨,∧>是由格<A,≼>所诱导的代数系定理4：格<A,≼>是模格，当且仅当A中不含有适合下述条件的元素u，v，w

v﹤u且u∨w＝v∨w,u∧w=v∧w证明：(反证法)(1)存在这样三个元素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,≼>是模格，当且仅当A中不含有适合下述条件（2）若<A，≼>不是模格，则存在a,b,c，当b≼a时，有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对于模格，若有三个元素a,b,c，使得上面三个式子的任何一个式子中把“≼”换成“=”成立，则另外两个式子中把“≼”换成“=”也必成立。一般的格中，下式成立：（1）a(bc)≼(ab)(ac)（2）(ab)(ac)≼a(bc)（3）(ab)(bc)(ca)≼(ab)(bc)(ca)§6-2分配格 54定理5对于模格，若有三个元素a,b,c，使得上面三证明：若（1）中=成立，则由对偶性（2）的=也成立(ab)(bc)(ca)=((ac)b)(ca)=((ca)b)(ac)=(ab)(bc)

(ca)若（3）中=成立，则有a(bc)=a(ab)(ca)(bc)=a((ab)(bc)(ca))=a((bc)(ab)(ca))=(abc)(ab)(ca)=(ab)(ac)（1）a（bc）=（ab）（ac）（2）（ab）（ac）=a（bc）§6-2分配格 55证明：若（1）中=成立，则由对偶性（2）的=也成立若定理6：分配格必定是模格。证明：设<A,≼>是一个分配格，对于a,b,cA

若b≼a，则ab=b a(bc)=(ab)(ac)=b(ac) ∴分配格是模格§6-2分配格 56定理6：分配格必定是模格。证明：设<A,≼>是一个分配格，注意：分配格一定是模格，但模格不一定是分配格。对于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)即该格是模格，但不是分配格。§6-2分配格 当b≼a时，有a(bc)=b(ac)57注意：分配格一定是模格，但模格不一定是分配格。对于x，y补充性质：（1）四个元素以下的格都是分配格。§6-2分配格 58补充性质：§6-2分配格 58（2）五个元素的格仅有两个格是非分配格。§6-2分配格 59（2）五个元素的格仅有两个格是非分配格。§6-2分配格 5代数系统

第六章 格和布尔代数 §1格的概念 §2分配格 §3有补格

60代数系统 第六章 格和布尔代数60§6-3有补格定义1

设<A,≼>是一个格，如果存在元素aA，对于xA，都有：a≼x，则称a为格<A,≼>的全下界，记格的全下界为0。定义2

设<A,≼>是一个格，如果存在元素bA，对于xA，都有：x≼b，则称b为格<A,≼>的全上界，记格的全上界为1。61§6-3有补格定义1设<A,≼>是一个格，如果存在元素§6-3有补格定理1、2如果格<A,≼>有全上界（全下界），那么它是唯一的。证明：（反证法）设有两个全上界a和b,a,bA且ab则由定义a≼b，且b≼a，由“≼”的反对称性，a=b。62§6-3有补格定理1、2证明：（反证法）62全下界：h全上界：a定义3如果一个格中存在全上界和全下界，则称该格为有界格。例1：<(S),>中,全下界：φ全上界：Sabcdefgh例2：§6-3有补格63全下界：h定义3如果一个格中存在全上界和全下界，则称该格定理3

如果<A,≼>是有界格，全上界和全下界分别是1和0，则对任意元素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有补格64定理3如果<A,≼>是有界格，全上界和全下界分别是1和定义4设<A,≼>是一个有界格，对于A中的一个元素a，如果存在bA，使得ab=1和ab=0，则称元素b是元素a的补元。讨论定义：（1）∵和是可交换的，∴补元是相互的。（2）在有界格中，1和0互为补元；（3）A中一个元素的补元不一定是唯一的；§6-3有补格65定义4设<A,≼>是一个有界格，对于A中的一个元素a，如1abcd0e∵dc=1dc=0∴d和c互补d的补元：c和ea的补元：eb的补元：无c的补元：de的补元：a和d§6-3有补格∵dc=1dc=0∴d和c互补d的补元：a的补元：b的补元：c的补元：e的补元：661abcd0e∵dc=1dc=0定义5在一个有界格中，如果每个元素都至少有一个补元素，则称此格为有补格。注意：（1）在有补格中，每一个元素一定存在补元（不一定只有一个补元）；（2）有补格一定是有界格，而有界格不一定是有补格。（3）有补格不一定是分配格，分配格不一定是有补格。§6-3有补格67定义5在一个有界格中，如果每个元素都至少有一个补元素，则1ab010abcd1abcd01abcd0(a)(b)(c)(d)下类有界格中哪个是有补格？§6-3有补格681ab010abcd1abcd01abcd0(a)(b)(c01abc0abc1（a）（b）(a)是分配格，不是有补格。(b)是有补格，不是分配格。§6-3有补格6901abc0abc1（a）（b）(a)是分配格，不是有补格。定理4在有界分配格中，若有一个元素有补元，则必是唯一的。证明：设a有两个补元素b和c且bc，即有

ab=1ab=0ac=1ac=0∴ab=acab=ac由定理6-2.3得b=c即a的补元是唯一的。§6-3有补格70定理4在有界分配格中，若有一个元素有补元，则必是唯一的。证定义6

一个格如果它既是有补格，又是分配格，则称它为有补分配格。我们把有补分配格中任意元素a的唯一补元记为a。定义:一个有补分配格称为布尔格。性质：有补分配格中，每个元素都存在唯一的补元。（定理4的推论）§6-3有补格71定义6一个格如果它既是有补格，又是分配格，则称它为有补分定义：由布尔格<A,≼>，可以诱导一个包括交，并和补运算的代数系统<A,,,->，称此代数系统为布尔代数。例：设S是一个非空有限集，<(S),>是一个格，且是一个布尔格。由<(S),>所诱导的代数系统为

<(S),

,,->是一个布尔代数。其中“,,-”分别是集合的交、并、补运算。若S有n个元素，该布尔代数的哈斯图为n为立方体图。§6-4布尔代数72定义：由布尔格<A,≼>，可以诱导一个包括交，并例：设S01abccab{a}{c}{b,c}{a,c}{a,b}{a,b,c}φ{b}§6-4布尔代数7301abccab{a}{c}{b,c}{a,c}{a定义：一个格<L,≤>如果它既是有补格，又是分配格，则它为有补分配格。我们把有补分配格中任一元素a的唯一补元记为a。讨论定义：(1)布尔格中，每个元素有唯一的补元。(2)我们可以定义L上的一个一元运算，称为补运算，记为“-”。-§6-4布尔代数74-§6-4布尔代数74§6-4布尔代数定义：由布尔格<L,≤>，可以诱导一个包括交，并和补运算的代数系统<L,,,->，称此代数系统为布尔代数。例：设S是一个非空有限集，<(S),>是一个格，且是一个布尔格。由<(S),>所诱导的代数系统为

<(S),

,,->是一个布尔代数。其中“,,-”分别是集合的交、并、补运算。75§6-4布尔代数定义：由布尔格<L,≤>，可以诱导一个包括§6-4布尔代数定理：对于布尔代数中任意两个元素a,b，必定有76§6-4布尔代数定理：对于布尔代数中任意两个元素a,b，必§6-4布尔代数定理：设<A,,,->是由有限布尔格<A,≤>所诱导的一个有限布尔代数，S是布尔格<A,≤>中的所有原子的集合，则<A,,,->和<(S),,,~>同构。讨论：(1)当布尔代数<A,,,->的载体A的基数|A|是有限数时,则称之为有限布尔代数。(2)设<A,,,->是一个布尔代数，a∈A,如果a盖住0，则称元素a是该布尔代数的一个原子。(3)A中除0外的每个元素，都可唯一地表示成原子的并。77§6-4布尔代数定理：设<A,,,->是由有限布尔格<§6-4布尔代数例：<(S),,,~,,S>，其中S={a,b,c}，在这个布尔代数中的元素分三种情况：（ⅰ）界：全上界S，全下界；（ⅱ）{a},{b},{c}单个元素集合的元素；（ⅲ）二，三个元素作为集合的元素，但它们均可用单个元素的集合的元素来表述：{a,b}={a}{b},{a,c}={a}{c},{b,c}={b}{c},{a,b,c}={a}{b}{c}。

{a,c}{a,b,c}{a,b}{b,c}{a}{c}{b}Ø78§6-4布尔代数例：<(S),,,~,,§6-4布尔代数该定理可得以下两个推论：a)<B,*,,’,0,1>与<p(S),∪,∩,~,Ø,S>同构，|p(S)|=2|s|所以，|B|=2|s|，故任一有限布尔代数载体的基数是2的幂。b)任一有限布尔代数和它的原子集合S构成的幂集集合代数<p(S),∪,∩,~,Ø,S>同构，但后者又与任一基数相同的幂集集合代数同构，故具有相同载体基数的有限布尔代数都同构。79§6-4布尔代数该定理可得以下两个推论：79§6-4布尔代数格有界格有补格布尔代数分配格结合律吸收律交换律幂等律同一律零一律互补律分配律德·摩根律双重否定律80§6-4布尔代数格有界格有补格布尔代数分配格结合律吸收律§6-4布尔代数例：设A是一非空集合，(A)是A的幂集，可以验证，<(A),∪,∩,~,,A>是个布尔代数,称此为集合代数，其中运算为∪,∩,~,最小元,最大元A。S是命题公式的全体，则<S,∨,∧,,0,1>是一个布尔代数，称之为命题代数。其中运算为∨,∧,，最小元是恒假公式0，最大元是恒真公式1。81§6-4布尔代数例：81§6-4布尔代数因此，从逻辑观点看，布尔代数是命题演算系统。从集合论观点看，布尔代数是集合代数。从抽象代数的观点看，布尔代数是一个代数系统。82§6-4布尔代数因此，82第三篇小结通过本篇的学习应该达到以下基本要求：(1)给定集合与运算的解析表达式，写出该运算的运算表。(2)给定集合和运算，判别该集合对运算是否封闭。(3)给定二元运算，说明运算是否满足交换律、结合律、幂等律、分配律和吸收律。(4)给定集合S上的二元运算，求出该运算的幺元、零元、幂等元和所有可逆元素的逆元。(5)给定集合S和二元运算

，能判定<S,>是否构成半群、独异点和群。83第三篇小结通过本篇的学习应该达到以下基本要求：83第三篇小结(6)给定半群S和子集B，判定B是否为S的子半群；给定独异点V和子集B，判定B是否为V的子独异点，给定群G和子集H，判定H是否为G的子群。(7)求循环群的所有生成元。(8)给定代数系统V1=<S1,º>，V2=<S2,>，其中“º”和“”为二元运算，判定：S1S2是否为V1到V2的同态映射。如果是，说明是否为单同态、满同态和同构，并求出同态象(V1)。(9)判别格、分配格、有界格、有补格和布尔格。求有界格的全上界、全下界和给定元素的补元。84第三篇小结(6)给定半群S和子集B，判定B是否为S的子半群；8585代数系统

第六章 格和布尔代数 §1格的概念 §2分配格 §3有补格

86代数系统 第六章 格和布尔代数1§6-1格的概念偏序集<A,≼>{a,b}最小上界最大下界{e,f}最大下界最小上界注意：今后把{a，b}的最小上界（最大下界）称为元素a，b的最小上界（最大下界）。{a,b}最小上界c最大下界无{e,f}最大下界d最小上界无87§6-1格的概念偏序集<A,≼>{a,b}最小上§6-1格的概念共同的特性：在这些偏序集中，任何两个元素都有最小上界和最大下界。88§6-1格的概念共同的特性：在这些偏序集中，任何两个元素一、格定义1设<A,≼>是一个偏序集，如果A中任意两个元素都有最小上界和最大下界，则称<A,≼>为格。复习§6-1格的概念89一、格复习§6-1格的概念4§6-1格的概念90§6-1格的概念5§6-1格的概念91§6-1格的概念6§6-1格的概念92§6-1格的概念7§6-1格的概念例：<I+，|>：a|b当且仅当a整除b<(S)，>任意两元素a,b的最小上界：最小公倍数最大下界：最大公约数任意两元素S1,S2的最小上界：S1∪S2最大下界：S1∩S2称为正整数格93§6-1格的概念例：<I+，|>：a|b当且仅§6-1格的概念例：给定S={a，b}，(S)={,{a},{b},{a,b}}，那么，格<(S)，

>如图所示。{a,b}{b}{a}94§6-1格的概念例：给定S={a，b}，(S)={§6-1格的概念定义2设<A,≼>是一个格，如果在A上定义两个二元运算∨和∧，使得对于a,bA，a∨b等于a和b的最小上界(LUB)，a∧b等于a和b的最大下界(GLB)，则称<A,∨,∧>为由格<A,≼>所诱导的代数系统。二元运算∨和∧分别称为并运算和交运算。复习95§6-1格的概念定义2设<A,≼>是一个格，如果在A§6-1格的概念例：1.<I+，|>2.<(S)，>

3.<A，≤>

<I+，∨，∧>∨：最小公倍数（lcm）∧：最大公约数（gcd）<(S)，∨，∧>∨：集合的并∪∧：集合的交∩<A，∨，∧>，A:{1,2,3,4,5}

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

4.设nI+，In={x|xI+，(x|n)},<In,|>为格，当n=20时，I20={1,2,4,5,10,20}，<I20,|>如图：20104251x∨y=lcm(x,y),x∧y=gcd(x,y)则<In，∨，∧>是由格<In,|>所诱导的代数系统97§6-1格的概念

4.设nI+，In={x|§6-1格的概念二、子格定义3设<A,≼>是一个格，由格<A,≼>所诱导的代数系统为<A,∨,∧>，设BA且B≠

，如果A中的这两个运算∨和∧关于B是封闭的，则称<B,≼>是<A,≼>的子格。注意：与子群概念的异同复习98§6-1格的概念二、子格复习13{a}{c}{b,c}{a,c}{a,b}{a,b,c}φ{b}<S1,><S2,><S3,>

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

{b,c}{a,c}{a,b}{a,b,c}φ{b}{a}{c}{b,c}{a,c}{a,b}{a,b,c}φ{b}例：A={a,b,c},<(A),>(A)={,{a},{b},{c},{a,b},{b,c},{c,a},{a,b,c}}S1={{a,b,c},{a,b},{b,c},{b}}S2={{a,c},{a},{c},}S3={{,{a},{c},{a,b},{b,c},{c,a},{a,b,c}}是格，并且是<(A),>的子格是格，但不是<(A),>的子格因为{a,b}∧{b,c}={b}S399{a}{c}{b,c}{a,c}{a,b}φ{b}<§6-1格的概念注意：对于格<A,≼>，设B是A的非空子集，尽管<B,≼>必定是一个偏序集，然而<B,≼>不一定是格，即使<B,≼>是格，也不一定是<A,≼>的子格。100§6-1格的概念注意：对于格<A,≼>，设B是A的非空格的主要性质格的对偶原理:设<A,≼>是格，“≼”的逆关系“≼R”与A组成的偏序集<A,≼R>也是格。两者互为对偶。前者的GLB(最大下界），LUB（最小上界）恰好是后者的LUB，GLB。如有关于<A,≼>的有效命题P， (1)将“≼”换成“≥”， (2)“”换成“”， (3)“”换成“”，便能得到<A,≥>的有效命题P’。反之亦然。§6-1格的概念101格的主要性质§6-1格的概念16§6-1格的概念定理1

在一个格<A,≼>中，对于任意的a,bA，都有a≼a∨b，b≼a∨ba∧b≼a，a∧b≼b证明：因为a∨b是a的一个上界所以a≼a∨b同理b≼a∨b由对偶原理得a∧b≼a，a∧b≼b复习102§6-1格的概念定理1在一个格<A,≼>中，对于任意的§6-1格的概念定理2

在一个格<A,≼>中，对于a,b,c,dA，如果有a≼b，c≼d，则：

a∨c≼b∨da∧c≼b∧d证明：因为a∧c≼aa∧c≼c而a≼b，c≼d所以a∧c≼ba∧c≼d所以a∧c≼b∧d复习103§6-1格的概念定理2在一个格<A,≼>中，对于§6-1格的概念推论：(格的保序性）在一个格<A,≼>中，对于a,b,cA，如果有b≼c，则

a∨b≼a∨ca∧b≼a∧c证明：因为a≼a，b≼c依据定理2可得。复习104§6-1格的概念推论：(格的保序性）在一个格<A,≼>定理3设<A,≼>是一个格，由格<A,≼>所诱导的代数系统为<A,∨,∧>，则对于a,b,c,dA，有：（１）交换律a∨b=b∨aa∧b=b∧a（２）结合律（a∨b）∨c=a∨（b∨c）（a∧b）∧c=a∧（b∧c）（３）幂等律a∨a=aa∧a=a（４）吸收律a∨（a∧b）=aa∧（a∨b）=a复习§6-1格的概念105定理3设<A,≼>是一个格，由格<A,≼>所诱导的代§6-1格的概念结合律（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）106§6-1格的概念结合律（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由对偶原理：a∧a=a107§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

108§6-1格的概念吸收律a∨（a∧b）=a,a∧§6-1格的概念例：设<N,≤>是一个偏序集，N是自然数集，≤是“小于等于”关系，定义a∨b=max{a,b}（取大运算）a∧b=min{a,b}（取小运算）则<N,≤>是一个格。由此格诱导的代数系统为<N,∨,∧>。

则该代数系统的两个运算满足交换律结合律等幂律吸收律109§6-1格的概念例：设<N,≤>是一个偏序集，N是自然数§6-1格的概念1.交换性：任意两个数a和b的最大值（最小值）与b和a的最大值（最小值）是相等的。2.结合性：max(max(a,b),c)=max(a,max(b,c))都是三个数a,b,c中的最大值，所以∨是可结合的，min(min(a,b),c)=min(a,min(b,c))，说明∧是可结合的。3.幂等性：max(a,a)=min(a,a)=a4.吸收性：max(a,min(a,b))=amin(a,max(a,b))=a110§6-1格的概念1.交换性：任意两个数a和b的最大值（§6-1格的概念引理：设<A,∨,∧>是一个代数系统，其中∨,∧都是二元运算且满足吸收性，则∨和∧都满足幂等性。即要证，已知对于a,bA有a∨(a∧b)=a和a∧(a∨b)=a则:a∨a=aa∧a=a复习证明:∵a∨（a∧b）=a（吸收律）用（a∨b）代替b，得：a∨（a∧（a∨b））=a又∵a∧（a∨b）=a∴a∨a=a111§6-1格的概念引理：设<A,∨,∧>是一个代数系统，其§6-1格的概念定理4

设<A,∨,∧>是一个代数系统，其中∨,∧都是二元运算且满足交换性，结合性和吸收性，则A上存在偏序关系≼，使<A,≼>是一个格。复习证明思路：分四部分内容来证明：(1)定义二元关系≼：a≼

b当且仅当(a∧b)=a(2)证明是偏序关系（证自反、反对称和传递）；(3)证明a∧b是a和b的最大下界（下确界）；(4)根据∨、∧满足交换律和吸收律，证明a∨b是a和b的最小上界（上确界）。112§6-1格的概念定理4设<A,∨,∧>是一个代数系统，首先证明≼是偏序关系（1）∵∧满足吸收律∴∧满足幂等性(根据引理)即a∧a=a∴a≼a

自反性（2）设a≼b，则a∧b=a再设b≼a，则b∧a=b∵∧满足交换律∴a=b反对称性

（3）设a≼b，b≼c，则a∧b=a，b∧c=b∵a∧c=（a∧b）∧c=a∧（b∧c）=a∧b=a

∴

a≼c传递性即≼是偏序关系证明:在A上定义二元关系≼为：对于a,bA，a≼b当且仅当(a∧b)=a113首先证明≼是偏序关系（2）设a≼b，则a∧b=a（3）设其次证明a∧b是a和b的最大下界a≼b当且仅当a∧b=a

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

即a∧b是a和b的下界设cA，是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格的概念114其次证明a∧b是a和b的最大下界a≼b当且仅当a∧b=a∴≼即为：对于a,bA，a≼b当且仅当a∨b=b最后，根据交换性和吸收性，由a∧b=a得

（a∧b）∨b=a∨b即b=a∨b反之由a∨b=b得a∧（a∨b）=a∧ba=a∧b∴a=a∧bb=a∨b在A上定义二元关系≼为：对于a,bA，a≼b当且仅当a∧b=a类似的可证明a∨b是a和b的最小上界因此，<A,≼>是一个格§6-1格的概念115∴≼即为：对于a,bA，a≼b当且仅当a∨b=b最§6-1格的概念定理5设<A,≼>是一个格，则对于a,b,cA，有：

a∨（b∧c）≼（a∨b）∧（a∨c）（a∧b）∨（a∧c）≼a∧（b∨c）

（分配不等式）

复习116§6-1格的概念定理5设<A,≼>是一个格，则对于a∨（b∧c）≼（a∨b）∧（a∨c）证明：∵a≼a∨ba