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

1、1代数系统代数系统第六章第六章 格和布尔代数格和布尔代数 1格的概念格的概念 2分配格分配格 3有补格有补格26-1 格的概念格的概念偏序集偏序集a,b 最小上界最小上界 最大下界最大下界 e,f 最大下界最大下界 最小上界最小上界 注意：注意：今后把今后把a，b的最小上界（最大下界）称的最小上界（最大下界）称为元素为元素a，b的最小上界（最大下界）。的最小上界（最大下界）。a,b 最小上界最小上界 c 最大下界最大下界 无无e,f 最大下界最大下界 d 最小上界最小上界 无无36-1 格的概念格的概念共同的特性：在这些偏序集中，任何两个元素都共同的特性：在这些偏序集中，任何两个元素都有有最小

2、上界最小上界和和最大下界最大下界。4一、格一、格定义定义1 设设是一个偏序集，如果是一个偏序集，如果A中中任意任意两个元素都有最小上界和最大下界两个元素都有最小上界和最大下界，则称，则称为格为格。复习6-1 格的概念格的概念56-1 格的概念格的概念66-1 格的概念格的概念76-1 格的概念格的概念86-1 格的概念格的概念 例：例：a|b当且仅当当且仅当a整除整除b 任意两元素任意两元素a,b的最小上界：最小公倍数的最小上界：最小公倍数 最大下界：最大公约数最大下界：最大公约数任意两元素任意两元素S1,S2的最小上界：的最小上界：S1S2 最大下界：最大下界：S1 S2称为正整数格称为正整

3、数格96-1 格的概念格的概念例：例：给定给定S=a，b，(S)=,a,b,a,b，那么，格那么，格如图所示。如图所示。a,bba 106-1 格的概念格的概念定义定义2 设设是一个格，如果在是一个格，如果在A上定义两个二上定义两个二元运算元运算和和，使得对于，使得对于 a,b A，ab等于等于a和和b的最小上界的最小上界(LUB)，ab等于等于a和和b的最大下界的最大下界(GLB)，则称则称为由格为由格所诱导的代数系统。所诱导的代数系统。二元运算二元运算和和分别称为分别称为并运算并运算和和交运算交运算。复习116-1 格的概念格的概念例：例：1.2.3.：最小公倍数（：最小公倍数（lcm）：

4、最大公约数（：最大公约数（gcd）：集合的并：集合的并 ：集合的交：集合的交，A:1,2,3,4,5 ab=max(a,b)ab=min(a,b)126-1 格的概念格的概念 4.设设n I+，In=x|x I+，(x|n),为格，为格，当当n=20时，时，I20=1,2,4,5,10,20，如图：如图：20104251 xy=lcm(x,y),xy=gcd(x,y)则则是由格是由格所诱导的代数系统所诱导的代数系统136-1 格的概念格的概念二、子格二、子格定义定义3 设设是一个格，由格是一个格，由格所诱导所诱导的代数系统为的代数系统为，设，设B A且且B，如果如果A中的这两个运算中的这两个运

5、算和和关于关于B是封闭是封闭的的，则，则称称是是的的子格子格。注意：与子群概念的异同注意：与子群概念的异同复习14a c b,ca,ca,ba,b,cb 6-1 格的概念格的概念a c b,ca,ca,ba,b,cba c b,ca,ca,ba,b,cb例：例：A=a,b,c,(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,b b,c=b S3156-1 格的概念格的概念注意：注意：对于格

6、对于格，设，设B是是A的非空子集，尽的非空子集，尽管管必定是一个偏序集，然而必定是一个偏序集，然而不一定是格不一定是格，即使，即使是格，也不一定是格，也不一定是是的子格。的子格。16格的主要性质格的主要性质格的对偶原理格的对偶原理:设设是格，是格，“”的逆关系的逆关系“R”与与 A组成的偏序集组成的偏序集也是格。两者互为对偶。也是格。两者互为对偶。前者的前者的GLB(最大下界），最大下界），LUB（最小上界）恰好是（最小上界）恰好是后者的后者的LUB，GLB。如有关于如有关于的有效命题的有效命题P，(1)将将“”换成换成“”，(2)“”换成换成“”，(3)“”换成换成“”，便能得到便能得到的有

7、效命题的有效命题P。反之亦然。反之亦然。6-1 格的概念格的概念176-1 格的概念格的概念定理定理1 在一个在一个格格中，对于任意的中，对于任意的a,b A，都有都有 a ab ，b ab ab a ，ab b证明：因为证明：因为ab 是是a的一个上界的一个上界 所以所以 a ab 同理同理 b ab 由对偶原理得由对偶原理得 ab a ，ab b复习186-1 格的概念格的概念定理定理2 在一个格在一个格中，对于中，对于 a,b,c,d A，如果有如果有a b，c d，则：，则：ac bdac b d证明：因为证明：因为ac a ac c 而而a b，c d 所以所以 ac b ac d

8、所以所以 ac b d复习196-1 格的概念格的概念推论：推论：(格的保序性格的保序性）在一个格）在一个格中，中，对于对于a,b,c A，如果有如果有b c，则，则 ab acab ac证明：证明：因为因为a a，b c 依据定理依据定理2可得。可得。复习20定理定理3 设设是一个格，由格是一个格，由格所诱导的代数所诱导的代数系统为系统为，则对于，则对于 a,b,c,d A，有：，有：（）（）交换律交换律ab=baab=ba（）（）结合律结合律（ab）c=a（bc）（a b）c=a（bc）（）（）幂等律幂等律aa=aaa=a（）（）吸收律吸收律a（ab）=a a（ab）=a复习6-1 格的概

9、念格的概念216-1 格的概念格的概念结合律（结合律（ab）c=a（bc）证明：证明：由定理由定理1知知 b bc a(bc)a a(bc)ab a(bc)又又 c bc a(bc)（ab）c a（bc）类似地类似地 a（bc）（ab）c （ab）c=a（bc）226-1 格的概念格的概念幂等律幂等律aa=a aa=a 证明：证明：a aa 由自反性可知由自反性可知 a a aa a（aa是最小上界）是最小上界）aa=a 由对偶原理：由对偶原理：aa=a236-1 格的概念格的概念吸收律吸收律 a（ab）=a,a（ab）=a 证明：证明：由定理由定理1知知 a a（ab）又又 a a，ab a

10、 a（ab）a a（ab）=a 246-1 格的概念格的概念例：例：设设是一个偏序集，是一个偏序集，N是自然数集，是自然数集，是是“小小于等于于等于”关系，定义关系，定义 ab=maxa,b （取大运算）取大运算）ab=min a,b （取小运算）取小运算）则则是一个格。由此格诱导的代数系统为是一个格。由此格诱导的代数系统为。则该代数系统的两个运算满足则该代数系统的两个运算满足交换律交换律结合律结合律等幂律等幂律吸收律吸收律256-1 格的概念格的概念1.交换性：交换性：任意两个数任意两个数a和和b的最大值（最小值）与的最大值（最小值）与b和和a的最大值（最小值）是相等的。的最大值（最小值）是

11、相等的。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)=a min(a,max(a,b)=a 266-1 格的概念格的概念引理：引理：设设是一个代数系统，其中是一个代数系统，其中,都是二都是二元运算且元运算且满足吸收性满足吸收性，则则和和都满足幂等性。都满足幂等性。即要证，已知

12、对于即要证，已知对于 a,b A 有有a(ab)=a和和a(ab)=a则则:aa=a aa=a复习证明证明:a（ab）=a （吸收律）（吸收律）用（用（ab）代替）代替b，得：，得：a（a（ab）=a 又又 a（ab）=a aa=a276-1 格的概念格的概念定理定理4 设设是一个代数系统，其中是一个代数系统，其中,都是都是二二元运算元运算且满足且满足交换性，结合性和吸收性，交换性，结合性和吸收性，则则A上存上存在偏序关系在偏序关系 ，使使是一个格。是一个格。复习证明思路：证明思路：分四部分内容来证明：分四部分内容来证明：(1)定义二元关系定义二元关系 ：a b当且仅当当且仅当(ab)=a(2

13、)证明是偏序关系（证自反、反对称和传递）证明是偏序关系（证自反、反对称和传递）；(3)证明证明ab是是a和和b的最大下界（下确界）；的最大下界（下确界）；(4)根据根据、满足交换律和吸收律，证明满足交换律和吸收律，证明ab是是a和和b的最小上界（上确界）的最小上界（上确界）。首先证明首先证明 是偏序关系是偏序关系（1）满足吸收律满足吸收律 满足幂等性满足幂等性(根据引理根据引理)即即 a a=a a a 自反性自反性（2）设）设a b，则，则ab=a 再设再设b a，则，则ba=b 满足交换律满足交换律 a=b 反对称性反对称性 （3）设）设a b，b c，则，则ab=a，bc=b ac=（a

14、b）c =a（b c）=ab=a a c 传递性传递性 即即 是偏序关系是偏序关系证明证明:在在A上定义二元关系上定义二元关系 为：为：对于对于 a,b A，a b当且仅当当且仅当(ab)=a29其次证明其次证明ab是是a和和b的最大下界的最大下界 a b当且仅当当且仅当ab=a 由于由于（ab）a=ab （ab）b=ab 所以所以 ab a,ab b 即即 ab是是a和和b的的下界下界设设c A，是，是a和和b的任一下界，即：的任一下界，即：c a，c b ca=c cb=c c(ab)=(ca)b=cb=c c ab ab是是a和和b的的最大最大下界下界6-1 格的概念格的概念30 即为：

15、对于即为：对于 a,b A，a b当且仅当当且仅当 ab=b最后，最后，根据交换性和吸收性，由根据交换性和吸收性，由ab=a 得得 （ab）b=a b 即即 b=a b 反之由反之由 a b=b 得得 a（a b）=a b a=a b a=a b b=a b在在A上定义二元关系上定义二元关系 为：为：对于对于 a,b A，a b当且仅当当且仅当ab=a类似的可证明类似的可证明 ab是是 a和和 b的最小上界的最小上界 因此，因此，是一个格是一个格6-1 格的概念格的概念316-1 格的概念格的概念定理定理5 设设是一个格，则对于是一个格，则对于 a,b,c A，有：，有：a（bc）（ab）（a

16、c）（ab）（ac）a（bc）（分配不等式）（分配不等式）复习32 a（bc）（ab）（ac）证明：证明：a a b a ac a=aa （ab）（ac）（1）又又 bc b ab bc c ac bc=(bc)(bc)(ab)（ac）（）（2）a（bc）（ab）（ac）利用对偶原理（利用对偶原理（ab）（ac）a（bc）6-1 格的概念格的概念336-1 格的概念格的概念定理定理6 设设是一个格，则对于是一个格，则对于 a,b A，有，有 a b ab=a ab=b证明：证明：先证先证a b ab=a （1）a b，a a，a a b 又又 ab a，则，则 ab=a （2）反之，假定）反之

17、，假定 ab=a 则则 a=ab b a b a b ab=a同理：同理：a b ab=b复习346-1 格的概念格的概念定理定理7 设设是一个格，对于是一个格，对于 a,b,c A，有，有 a c a(bc)(ab)c（模不等（模不等式）式）证明：由证明：由定理定理6 a c ac=c 由由定理定理5 a(bc)(ab)(ac)用用c代替代替ac a(bc)(ab)c a c a(bc)(ab)c复习若若 a(bc)(ab)c则则 a a(bc)(ab)c c 即即 a c a(bc)(ab)c a c a c a(bc)(ab)c356-1 格的概念格的概念推论：推论：在格在格中，则对于中

18、，则对于 a,b,c A，必有：，必有：（ab）（ac）a（b（ac）a（b（ac）（ab）（ac）复习证明：证明：(ab)(ac)(a(ac)(b(ac)（ab）（ac）a（b（ac）a(b(ac)(ab)(a(ac)a(b(ac)(ab)(ac)36定义定义:设设和和是两个格，由它们分别诱是两个格，由它们分别诱导的代数系统导的代数系统为为和和，若存，若存在着一个从在着一个从A1到到A2的映射的映射f，使得对于使得对于 a,b A1，有有 f(a 1 b)=f(a)2 f(b)f(a 1 b)=f(a)2 f(b)则称则称f为从为从到到 的的格同态格同态。称称是是的的格同态象格同态象。当当f

19、是双射是双射时，称时，称f为从为从到到的的格同构格同构。复习6-1 格的概念格的概念376-1 格的概念格的概念定理定理8：(格同态的保序性）格同态的保序性）设设f是是和和的格同态，则的格同态，则对对 x,y A1，如果如果x 1y，必有，必有f(x)2 f(y)证明：证明：x 1 y x1y=x f(x1y)=f(x)=f(x)2 f(y)（同态公式）（同态公式）f(x)2 f(y)注意：注意：定理定理8的逆命题是不一定成立的的逆命题是不一定成立的 格同态是保序的，但是保序的不一定是格同态格同态是保序的，但是保序的不一定是格同态复习38但是，对于但是，对于b,d S，有，有bd=a f(bd

20、)=f(a)=S f(b)f(d)=b,d,e f(bd)f(b)f(d)例：设例：设是一个格，其中是一个格，其中S=a,b,c,d,e，如图，如图 则则也是一个格。也是一个格。作作f：S(S)，对，对 x S，使得使得 f(x)=y|y S，y x 有有f(a)=S,f(b)=b,e,f(c)=c,e,fd=d,e,f(e)=e 当当x,y S 且且 x y 时，有时，有f(x)f(y)f是保序的是保序的adbce6-1 格的概念格的概念396-1 格的概念格的概念定理定理9：设两个格设两个格和和，f是从是从A1到到A2的双射，则的双射，则f是是到到的格同构，的格同构，当且仅当当且仅当对对

21、a,b A1，a 1 b f(a)2 f(b)。复习证明：证明：设设f是是到到的格同构。的格同构。由由定理定理8知知对对 a,b A1，若若a 1b，必有，必有f(a)2f(b)反之，设反之，设f(a)2f(b)，则则f(a)2f(b)=f(a1b)=f(a)f是双射是双射 a1b=a 故故a 1 b 406-1 格的概念格的概念设对设对 a,b A1，a 1b f(a)2 f(b)设设a1b=c，则，则c 1a，c 1b，有，有 f(a1b)=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)2 f(d)，

22、f(d)2 f(a)，f(d)2 f(b)d 1 a，d 1 b d 1 a1 b 即即d 1 c，f(d)2 f(c)f(c)=f(d)即即f(a1b)=f(a)2f(b)类似地可证类似地可证 f(a1b)=f(a)2f(b)因此，因此，f是是到到的格同构的格同构41代数系统代数系统第六章第六章 格和布尔代数格和布尔代数 1 格的概念格的概念 2 分配格分配格 3 有补格有补格426-2 分配格分配格定义定义1：设设是由格是由格所诱导的代数系所诱导的代数系统。如果对于任意的统。如果对于任意的a,b,c A，满足：，满足：a（bc）=（ab）（ac）a（bc）=（ab）（ac）则则称称是是分配

23、格分配格。复习43讨论定义：讨论定义：(1)定义中的两式互为对偶式。定义中的两式互为对偶式。(2)如如为非分配格，则有下面的分配不等式：为非分配格，则有下面的分配不等式：a (b c)(a b)(a c)(a b)(a c)a (b c)(定理定理6-1.5)以及模不等式：以及模不等式：a ca (b c)(a b)c (定理定理6-1.7)6-2 分配格分配格44例：例：S=a,b,c (S)=,a,b,c,a,b,b,c,c,a,a,b,c a c b,ca,ca,ba,b,cb对于对于 P,Q,R(S),有有P(QR)=(PQ)(PR)P(QR)=(PQ)(PR)则则是一个分配格是一个分

24、配格6-2 分配格分配格45adbceabcde b（cd）=b a=b（bc）（bd）=ee=e c（bd）=ca=c（cb）（cd）=ed=d注意：注意：一个格是分配格的充要条件一个格是分配格的充要条件是该格中是该格中没有任何子格没有任何子格与这与这两个五两个五元素格元素格中的任一个中的任一个同构同构。复习6-2 分配格分配格46abcdfge 是格是格 的子格，的子格，但不是分配格但不是分配格6-2 分配格分配格47定理定理1：如果格中如果格中交对并交对并是分配的，那么是分配的，那么并对交并对交也也 是分配的，反之亦然。是分配的，反之亦然。证明：已知证明：已知 a (b c)=(a b)

25、(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)即：并对交也是分配的。即：并对交也是分配的。复习6-2 分配格分配格486-2 分配格分配格定理定理2：每个链均是分配格。每个链均是分配格。证明：设证明：设是链。则是链。则一定是格一定是格 对对 a，b，c A(1)若若a b 或或 a c，则，则 a (b c)=a (a b)(a c)=a 即：即：a (b c)=(a b)(a c)(2)若若 b a 且且 c a，则，则 a (b c)=b c，(a b)(a c)=b c 即：即：a (

26、b c)=(a b)(a c)。复习49定理定理3 设设是一个分配格，对于是一个分配格，对于 a,b,c A，如果，如果有有a b=a c 和和 a b=a c 成立，则必有成立，则必有b=c。证明：证明：（a b）c=（a c）c=c 而而 （a b）c=(a c)(b c)=(a b)(b c)=b （a c）=b （a b）=b 所以所以 b=c 复习6-2 分配格分配格50定义定义2 设设是由格是由格所诱导的代数系统。所诱导的代数系统。如果对于如果对于 a,b,c A，当当b a时时，有有 a (b c)=b (a c)则则称称为模格。也称戴德金格。为模格。也称戴德金格。定理定理6-1

27、.7：设设是一个格，则对于是一个格，则对于 a,b,c A，有，有 a c a（bc）（ab）c （模不等式模不等式）(b c)a=b (c a)模律（模等式）模律（模等式）复习6-2 分配格分配格51定理定理4：格格是模格，当且仅当是模格，当且仅当A中中不含有不含有适合下适合下述条件的元素述条件的元素u，v，w vu 且且 uwvw,uw=vw 证明：证明：(反证法反证法)(1)存在这样三个元素存在这样三个元素u,v,w满足上式满足上式 u（wv）=u（wu）=u （uw）v=（vw）v=v 又又 vu v（wu）（vw）u 模不等式模不等式 不是模格。不是模格。6-2 分配格分配格52 （

28、2）若）若不是模格，则存在不是模格，则存在 a,b,c，当当b a时，有时，有b（c a）（bc）a令令 v=b（c a），），u=（bc）a，w=c uw=（bc）a）c =a（bc）c）=ac =（ac）c 又又（ac）b（c a）（ac）c b（c a）c 即即 uw vw 6-2 分配格分配格53因此，若因此，若不是模格，就一定存在不是模格，就一定存在u，v，wA，使得使得vu 且且 uwvw,uw=vw。所以，定理成立。所以，定理成立。又又v u vw uw 故故 uw=vw 同理：同理：uwvw 6-2 分配格分配格54定理定理5 对于模格，若有三个元素对于模格，若有三个元素a,b

29、,c，使得上面三个，使得上面三个式子的任何式子的任何一个式子中把一个式子中把“”换成换成“=”成立成立，则则另外两个式子中把另外两个式子中把“”换成换成“=”也必成立也必成立。一般的格中，下式成立：一般的格中，下式成立：（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 分配格分配格55证明：若（证明：若（1）中）中=成立，则由对偶性（成立，则由对偶性（2）的）的=也成立也成立 (a b)(b c)(c a)=(a c)b)(c a)=(c a)b)(a c)=(a b)(b c)(c a)若

30、（若（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 分配格分配格56定理定理6：分配格必定是模格。分配格必定是模格。证明：设证明：设是一个分配格，对于是一个分配格，对于 a,b,c A 若若b a，则，则a b=b a (b c)=(a b)(a c)=b (a c)分配格是模格分配格是模格6-2 分配格分配格57注意：分配格一定是模格

31、，但模格不一定是分配格。注意：分配格一定是模格，但模格不一定是分配格。对于对于 x，y，z0，1，a，b，c 若有若有y x,则只有则只有y=0或或x=101abc若若y=0，则，则x (y z)=x z y (x z)=x z若若x=1，则，则x (y z)=y z y (x z)=y z所以，所以，x (y z)=y (x z)即该格是模格，但不是分配格。即该格是模格，但不是分配格。6-2 分配格分配格当当b a时，有时，有 a(b c)=b(a c)58补充性质：补充性质：（1）四个元素四个元素以下的格都是以下的格都是分配格分配格。6-2 分配格分配格59（2 2）五个元素的格仅有两个格

32、是非分配格。）五个元素的格仅有两个格是非分配格。6-2 分配格分配格60代数系统代数系统第六章第六章 格和布尔代数格和布尔代数 1 格的概念格的概念 2 分配格分配格 3 有补格有补格616-3 有补格有补格定义定义1 设设是一个格，如果存在元素是一个格，如果存在元素a A，对于，对于 x A，都有：，都有：a x，则称则称a为格为格的全下的全下界界，记格的全下界，记格的全下界为为0。定义定义2 设设是一个格，如果存在元素是一个格，如果存在元素b A，对于，对于 x A，都有：，都有：x b，则称则称b为格为格的全上的全上界界，记格的全上界，记格的全上界为为1。626-3 有补格有补格定理定理

33、1、2 如果格如果格有有全上界（全下界），全上界（全下界），那么它是那么它是唯一唯一的。的。证明：（反证法）证明：（反证法）设有两个全上界设有两个全上界a和和b,a,b A 且且 a b 则由定义则由定义a b，且，且b a，由由“”的反对称性，的反对称性，a=b。63全下界：全下界：h全上界：全上界：a定义定义3 如果如果一个格中存在一个格中存在全上界全上界和和全下界全下界，则称该格为，则称该格为有界格有界格。例例1：中中,全下界：全下界：全上界：全上界：Sabcdefgh例例2：6-3 有补格有补格64定理定理3 如果如果是有界格，全上界和全下界分别是是有界格，全上界和全下界分别是1和和0

34、，则对任意元素，则对任意元素a A，有：，有：a 1=1 a=1，a 1=1 a=a a 0=0 a=a，a 0=0 a=0证明证明:(1)(a 1)A且且1是全上界，是全上界，a 1 1 又又 1 a 1 a 1=1 由交换律：由交换律：1 aa 1=1 (2)a a，a 1，a a a 1，即，即 a a 1 又又 a 1 a a 1=a 由交换律：由交换律：a 1=1 a=a 的幺元：的幺元：0 的零元：的零元：1 的幺元：的幺元：1 的零元：的零元：06-3 有补格有补格65定义定义4 设设是一个有界格，对于是一个有界格，对于A中的一个元素中的一个元素a，如果存在如果存在b A，使得，

35、使得a b=1和和a b=0，则称元素，则称元素b是元素是元素a的补元的补元。讨论定义：讨论定义：（1）和和 是可交换的，是可交换的，补元是相互的补元是相互的。（2）在有界格中，）在有界格中，1和和0互为补元；互为补元；（3）A中一个元素的补元不一定是唯一的；中一个元素的补元不一定是唯一的；6-3 有补格有补格661abcd0e d c=1 d c=0 d和和c互补互补 d的补元：的补元：c和和ea的补元：的补元：e b的补元：无的补元：无 c的补元：的补元：de的补元：的补元：a和和d6-3 有补格有补格 d c=1 d c=0 d和和c互补互补 d的补元：的补元：a的补元：的补元：b的补元

36、：的补元：c的补元：的补元：e的补元：的补元：67定义定义5 在一个有界格中，如果每个元素都至少有一个在一个有界格中，如果每个元素都至少有一个补元素，则称此格为补元素，则称此格为有补格有补格。注意：注意：（1）在有补格中，每一个元素一定存在补元（不一定只）在有补格中，每一个元素一定存在补元（不一定只有一个补元）；有一个补元）；（2）有补格一定是有界格，而有界格不一定是有补格。有补格一定是有界格，而有界格不一定是有补格。（3）有补格不一定是分配格，分配格不一定是有补格。有补格不一定是分配格，分配格不一定是有补格。6-3 有补格有补格681ab010abcd1abcd01abcd0(a)(b)(c

37、)(d)下类有界格中哪个是有补格？下类有界格中哪个是有补格？6-3 有补格有补格6901abc0abc1（a）（b）(a)(a)是分配格，不是有补格。是分配格，不是有补格。(b)(b)是有补格，不是分配格。是有补格，不是分配格。6-3 有补格有补格70定理定理4 在在有界分配格有界分配格中，若有一个元素有中，若有一个元素有补元补元，则必，则必是是唯一的唯一的。证明：设证明：设a有两个补元素有两个补元素b和和c且且b c，即有，即有 a b=1 a b=0 a c=1 a c=0 a b=a c a b=a c 由由定理定理6-2.3得得 b=c 即即 a的补元是唯一的。的补元是唯一的。6-3

38、有补格有补格71定义定义6 一个格如果它既是有补格，又是分配格，则称一个格如果它既是有补格，又是分配格，则称它为它为有补分配格有补分配格。我们把有补分配格中任意元。我们把有补分配格中任意元素素a的唯一补元记为的唯一补元记为a。定义定义:一个有补分配格称为一个有补分配格称为布尔格布尔格。性质：性质：有补分配格中，每个元素都存在唯一的补元有补分配格中，每个元素都存在唯一的补元。（定理（定理4的推论）的推论）6-3 有补格有补格72定义：由布尔格定义：由布尔格，可以诱导一个包括交，并，可以诱导一个包括交，并 和补运算的代数系统和补运算的代数系统，称此代数，称此代数 系统为系统为布尔代数布尔代数。例：

39、设例：设S是一个非空有限集，是一个非空有限集，是一个格，且是一个格，且是一个布尔格。由是一个布尔格。由所诱导的代数系统为所诱导的代数系统为 是一个布尔代数。其中是一个布尔代数。其中“,-”分别分别是集合的交、并、补运算。是集合的交、并、补运算。若若S有有n个元素，该布尔代数的哈斯图为个元素，该布尔代数的哈斯图为n为立方体图。为立方体图。6-4 布尔代数布尔代数7301abccaba c b,ca,ca,ba,b,cb6-4 布尔代数布尔代数74定义：定义：一个格一个格如果它既是有补格，又是分配如果它既是有补格，又是分配格，则它为有补分配格。我们把有补分配格中格，则它为有补分配格。我们把有补分配

40、格中任一元素任一元素a的唯一补元记为的唯一补元记为a。讨论定义：讨论定义：(1)布尔格中，每个元素有唯一的补元。布尔格中，每个元素有唯一的补元。(2)我们可以定义我们可以定义L上的一个一元运算，称为补运算，上的一个一元运算，称为补运算，记为记为“-”。-6-4 布尔代数布尔代数756-4 布尔代数布尔代数定义：定义：由布尔格由布尔格，可以诱导一个包括交，并和，可以诱导一个包括交，并和补运算的代数系统补运算的代数系统，称此代数系统为，称此代数系统为布尔代数。布尔代数。例：设例：设S是一个非空有限集，是一个非空有限集，是一个格，且是一个格，且是一个布尔格。由是一个布尔格。由所诱导的代数系统为所诱导

41、的代数系统为 是一个布尔代数。其中是一个布尔代数。其中“,-”分别分别是集合的交、并、补运算。是集合的交、并、补运算。766-4 布尔代数布尔代数定理：定理：对于布尔代数中任意两个元素对于布尔代数中任意两个元素a,b，必定有，必定有aa)(babababa776-4 布尔代数布尔代数定理：定理：设设是由有限布尔格是由有限布尔格所诱导的一所诱导的一个有限布尔代数，个有限布尔代数，S是布尔格是布尔格中的所有原中的所有原子的集合，则子的集合，则和和同构。同构。讨论：讨论：(1)当当布尔代数布尔代数的载体的载体A的基数的基数|A|是有限数时是有限数时,则称之为有限布尔代数。则称之为有限布尔代数。(2)

42、设设是一个布尔代数，是一个布尔代数，aA,如果如果a盖住盖住0，则，则称元素称元素a是该布尔代数的一个原子。是该布尔代数的一个原子。(3)A中除中除0外的每个元素，都可唯一地表示成原子的并。外的每个元素，都可唯一地表示成原子的并。786-4 布尔代数布尔代数例：例：，其中，其中S=a,b,c，在这个布尔代数中的元素分三种情况：在这个布尔代数中的元素分三种情况：（）界：全上界）界：全上界S，全下界，全下界 ；（）a,b,c单个元素集合的元素；单个元素集合的元素；（）二，三个元素作为集合的元素，但它们均可用单）二，三个元素作为集合的元素，但它们均可用单个元素的集合的元素来表述：个元素的集合的元素来

43、表述：a,b=a b,a,c=a c,b,c=b c,a,b,c=a b c。a,ca,b,ca,bb,cacb796-4 布尔代数布尔代数该定理可得以下两个推论：该定理可得以下两个推论：a)与与同构，同构，|p(S)|=2|s|所以，所以，|B|=2|s|，故任一有限布尔代数载体，故任一有限布尔代数载体的基数是的基数是2的幂。的幂。b)任一有限布尔代数和它的原子集合任一有限布尔代数和它的原子集合S构成的幂集集构成的幂集集合代数合代数同构，但后者又与任同构，但后者又与任一基数相同的幂集集合代数同构，故具有相同载一基数相同的幂集集合代数同构，故具有相同载体基数的有限布尔代数都同构。体基数的有限布

44、尔代数都同构。806-4 布尔代数布尔代数格格有界格有界格有补格有补格布尔代数布尔代数分配格分配格结合律结合律 吸收律吸收律交换律交换律 幂等律幂等律同一律同一律零一律零一律互补律互补律分配律分配律德德摩根律摩根律双重否定律双重否定律816-4 布尔代数布尔代数例：例：设设A是一非空集合，是一非空集合，(A)是是A的幂集，可以验证，的幂集，可以验证，是个布尔代数是个布尔代数,称此为集合代数，称此为集合代数，其中运算为其中运算为,最小元最小元,最大元最大元A。S是命题公式的全体，则是命题公式的全体，则是一个是一个布尔代数，称之为命题代数。其中运算为布尔代数，称之为命题代数。其中运算为,，最，最小

45、元是恒假公式小元是恒假公式0，最大元是恒真公式，最大元是恒真公式1。826-4 布尔代数布尔代数因此，因此，从逻辑观点看，布尔代数是命题演算系统。从逻辑观点看，布尔代数是命题演算系统。从集合论观点看，布尔代数是集合代数。从集合论观点看，布尔代数是集合代数。从抽象代数的观点看，布尔代数是一个代数系统。从抽象代数的观点看，布尔代数是一个代数系统。83第三篇小结第三篇小结通过本篇的学习应该达到以下基本要求：通过本篇的学习应该达到以下基本要求：(1)给定集合与运算的解析表达式，写出该运算的运给定集合与运算的解析表达式，写出该运算的运算表。算表。(2)给定集合和运算，判别该集合对运算是否封闭。给定集合和

46、运算，判别该集合对运算是否封闭。(3)给定二元运算，说明运算是否满足交换律、结合给定二元运算，说明运算是否满足交换律、结合律、幂等律、分配律和吸收律。律、幂等律、分配律和吸收律。(4)给定集合给定集合S上的二元运算，求出该运算的幺元、零上的二元运算，求出该运算的幺元、零元、幂等元和所有可逆元素的逆元。元、幂等元和所有可逆元素的逆元。(5)给定集合给定集合S和二元运算和二元运算 ，能判定，能判定是否构成半是否构成半群、独异点和群。群、独异点和群。84第三篇小结第三篇小结(6)给定半群给定半群S和子集和子集B，判定，判定B是否为是否为S的子半群；给定的子半群；给定独异点独异点V和子集和子集B，判定

47、，判定B是否为是否为V的子独异点，给定的子独异点，给定群群G和子集和子集H，判定，判定H是否为是否为G的子群。的子群。(7)求循环群的所有生成元。求循环群的所有生成元。(8)给定代数系统给定代数系统V1=，V2=，其中，其中“”和和“”为二元运算，判定为二元运算，判定：S1 S2是否为是否为V1到到V2的同态映的同态映射。如果是，说明射。如果是，说明 是否为单同态、满同态和同构，是否为单同态、满同态和同构，并求出同态象并求出同态象(V1)。(9)判别格、分配格、有界格、有补格和布尔格。求有界判别格、分配格、有界格、有补格和布尔格。求有界格的全上界格的全上界、全下界和给定元素的补元。、全下界和给定元素的补元。85