第七章 格和布尔代数精简

1、格与布尔代数主讲：鱼亮主讲：鱼亮西安电子科技大学多媒体研究所西安电子科技大学多媒体研究所西安电子科技大学多媒体研究所 12022-7-3第七章第七章 格与布尔代数格与布尔代数7.1 格格 7.2 子格和格同态子格和格同态7.3 特殊的格特殊的格7.4 布尔代数布尔代数与布尔表达式与布尔表达式西安电子科技大学多媒体研究所 22022-7-37.17.1格格u格的定义：格的定义：设设是一个偏序集，如果集是一个偏序集，如果集合合L中的任意两个元素都有最小上界和最大中的任意两个元素都有最小上界和最大下界，则称下界，则称为格。为格。西安电子科技大学多媒体研究所 32022-7-37.17.1格格u【例题

2、例题1】判断下图中所示各哈斯图代表的判断下图中所示各哈斯图代表的偏序集合是否是格？为什么？偏序集合是否是格？为什么？abcdefabcdeabcdefabcdabcdabcdefghabcdeabcde西安电子科技大学多媒体研究所 42022-7-37.17.1格格u【例题例题2】设设I+是正整数集合，定义是正整数集合，定义I+上的上的二元关系二元关系“|”,任取任取a,bI+,a|b当且仅当当且仅当a能能整除整除b。证明。证明:是一个格。是一个格。证明：证明：I+上的二元关系上的二元关系|是自反、反对称和传递的，是自反、反对称和传递的，因此因此是一个偏序集合。是一个偏序集合。任取任取a, b

3、I+, a与与b在偏序集合在偏序集合中的最小上界中的最小上界是其最小公倍数是其最小公倍数:luba,bI+。任取任取a,bI+, a与与b在偏序集合在偏序集合中的最大下界中的最大下界是其最大公约数：是其最大公约数：glba,bI+。结论得证。结论得证。西安电子科技大学多媒体研究所 52022-7-37.17.1格格u【例题例题3】设设S是任意集合，是任意集合，(S)是是S的幂集，的幂集，偏序集合偏序集合是否是格？是否是格？解答解答:任取任取A,B(S), A与与B在偏序集合在偏序集合中的最小上界是中的最小上界是AB (S), A与与B在偏序集合在偏序集合 中的最大下界是中的最大下界是AB (S

4、)。西安电子科技大学多媒体研究所 62022-7-37.17.1格格u保交运算保交运算 ab = glba, b,求求a,b的最大下界的最大下界u保联运算保联运算 ab = luba, b,求求a,b的最小上界的最小上界u定理定理(格的对偶定理格的对偶定理)如果如果是一个是一个格，则格，则也是一个格。设也是一个格。设P是一个命题，是一个命题，P的对偶命题的对偶命题P*是将关系符是将关系符换成换成，将保交，将保交与保联与保联运算符互换所得的命题。若运算符互换所得的命题。若P中中对一切格都为真，则对一切格都为真，则P*对一切格也都为真。对一切格也都为真。西安电子科技大学多媒体研究所 72022-7

5、-37.17.1格格u【例题例题】设设是一个格是一个格,其哈斯图如下其哈斯图如下图所示，画出图所示，画出的哈斯图。的哈斯图。 解答：解答：是是的对偶格，因此其哈的对偶格，因此其哈斯图可由斯图可由旋转旋转180得到，如得到，如(b)图所图所示。示。(a)(b)西安电子科技大学多媒体研究所 82022-7-37.17.1代数格代数格u代数格：代数格：设设是一个格，是一个格，a,bL。在。在L上可以定义两个运算上可以定义两个运算*和和 ： a*b = glba,b 也可写成也可写成 ab = glba,b a b = luba,b 也可写成也可写成 ab = luba,b 则称则称(或或)为格为格所

6、所诱导的代数系统，简称代数格。诱导的代数系统，简称代数格。西安电子科技大学多媒体研究所 92022-7-37.17.1代数格的性质代数格的性质u定理定理1在一个格在一个格中，对任意的中，对任意的a,bA,都有都有 aab, bab aba, abb证明：因为证明：因为a和和b的并是的并是a的一个上界，所以的一个上界，所以 aab 同理同理 bab 由对偶原理即得由对偶原理即得 aba, abb西安电子科技大学多媒体研究所 102022-7-37.17.1代数格的性质代数格的性质u定理定理2在一个格在一个格中，对于中，对于a,b,c,dA,如果如果 ab 和和 cd 则则 ac bd ac bd

7、证明：因为证明：因为 bbd, dbd,由传递性可得由传递性可得 a b d, c b d 这就表明这就表明bd是是a和和c的一个上界，而的一个上界，而ac 是是a和和c的最小上界，所以，必有的最小上界，所以，必有西安电子科技大学多媒体研究所 112022-7-37.17.1代数格的性质代数格的性质 ac bd 类似地可以证明类似地可以证明 ac bd西安电子科技大学多媒体研究所 122022-7-37.17.1代数格的基本性质代数格的基本性质u由格诱导的代数系统满足以下性质：由格诱导的代数系统满足以下性质：(1)自反性自反性 a a(2)反对称性反对称性 (a b) 且且 (b a) a =

8、 b(3)传递性传递性 (a b) 且且 (b c) a c(4) aba, abb aab, bab(5) (ca) 且且(cb) c(ab), (bc)且且(ac) c (ab)(6)交换律交换律 ab=ba ab= ba西安电子科技大学多媒体研究所 132022-7-37.17.1代数格的基本性质代数格的基本性质(7)结合律结合律 (ab)c=a(bc), (ab)c=a(b c)(8)等幂律等幂律 aa=a, a a=a (9)吸收律吸收律 a(ab)= a, a(ab)=a(10) ab ab=a a b=b(11) ab 且且d c ad bc ab 且且d c a d bc西安电

9、子科技大学多媒体研究所 142022-7-37.17.1代数格的基本性质代数格的基本性质(12)保序性保序性 bc abac, bc a bac(13)分配不等式分配不等式 a (bc) (ab)(ac) a(bc) (ab)(ac) (14)模不等式模不等式 a c a(bc)(ab)c证明：证明：(7) 由定理由定理1可知可知 bbca(bc) 和和 aa(bc) 西安电子科技大学多媒体研究所 152022-7-37.17.1代数格的基本性质代数格的基本性质由定理由定理2可知可知 ab a(bc) 又因又因cbc a(bc) 说明说明a(bc) 是是ab 和和c的上界的上界,而而(ab)c

10、是是 ab 和和c的最小上界，因此的最小上界，因此 (ab)c a(bc) 类似得可以证明类似得可以证明 a(bc) (ab)c 因此因此 a(bc) = (ab)c 由对偶原理可得由对偶原理可得 a(bc) = (ab)c 西安电子科技大学多媒体研究所 162022-7-37.17.1代数格的基本性质代数格的基本性质(8)由定理由定理1可知可知 aaa由自反性可知由自反性可知 a a由此可得由此可得 aa a因此因此 aa = a利用对偶原理可得利用对偶原理可得 aa = a(9)根据定理根据定理1可得可得 aa(ab)因为因为 a a, ab a 因此因此 a(ab ) a所以所以 a(a

11、b ) = a利用对偶原理，即得利用对偶原理，即得 a(ab) = a西安电子科技大学多媒体研究所 172022-7-37.17.1代数格的基本性质代数格的基本性质(10)首先证明首先证明ab ab=a因为因为ab和和aa,就有就有aab,但由定理但由定理1可知可知ab a,由反对称性，得由反对称性，得ab=a。这就证明了。这就证明了ab ab=a。反之，假定反之，假定ab=a，则，则a= abb,这就证明了这就证明了 ab=a ab因此因此ab ab=a用同样得方法可以用同样得方法可以ab ab=b西安电子科技大学多媒体研究所 182022-7-37.17.1代数格的基本性质代数格的基本性质

12、最后证明最后证明ab=a ab=b根据定理根据定理1可知可知abb,而而abb,因为因为ab=a,故故a b,而而bb,因此因此 abb,这样就得到了这样就得到了ab=b，即，即ab=a ab=b。反之，假定反之，假定ab=b, 由定理由定理1可知可知aba, 因为因为ab=b，故，故b=aba,而而aa,因此因此aba,这样就这样就得到了得到了ab=a,即即ab=b ab=a 。 因此得到因此得到ab=a ab=b西安电子科技大学多媒体研究所 192022-7-37.17.1代数格的基本性质代数格的基本性质(13)由定理由定理1可知可知 aab和和aac,由定理由定理2可知可知 a (ab)

13、 (ac) (1)另外由于另外由于 bcbab, bcc ac, 故故 b c (a b) (a c) (2) 因此由因此由(1)、(2)可得：可得：a(bc)(ab) (ac) 利用对偶原理，即得利用对偶原理，即得 a (b c) (a b)(a c) 西安电子科技大学多媒体研究所 202022-7-37.17.1代数格的基本性质代数格的基本性质(14)由性质由性质(10)有有 ac (ac) = c 再由性质再由性质(13)有有 a(bc) (ab) (ac) 用用c替代上式中的替代上式中的(ac)，即得，即得 a(bc) (ab) c所以所以 ac a(bc) (ab) c另外，若另外，

14、若a(bc) (ab) c,则明显地有则明显地有 a a(bc) (ab) c c所以所以a(bc) (ab) c ac 因此因此ac a(bc) (ab) c西安电子科技大学多媒体研究所 212022-7-37.17.1格格u定理定理设设是一个代数系统，其是一个代数系统，其中运算中运算和和都满足吸收律，则运算都满足吸收律，则运算和和 都满足等幂律。都满足等幂律。证明：由于证明：由于和和都满足吸收律，则任取都满足吸收律，则任取a,bA,有有 a (a b) = a (1) a (a b) = a (2)将将(1)式中的式中的b用用(ab)替换得替换得 a (a (ab) = a a=a 西安电

15、子科技大学多媒体研究所 222022-7-37.17.1格格将将(2)式中的式中的b用用(ab)替换得到替换得到 a (a (ab) = aa = a 故故 和和都满足等幂律。都满足等幂律。西安电子科技大学多媒体研究所 232022-7-37.17.1格格u定理定理设设是一个代数系统，其是一个代数系统，其中中和和都是二元运算且满足交换律、结合都是二元运算且满足交换律、结合律、吸收律，则律、吸收律，则A上存在偏序关系上存在偏序关系，使得，使得是一个格。是一个格。证明：在证明：在A上定义二元关系上定义二元关系为：任取为：任取a,bA,a b 当且仅当当且仅当 a b = a。(i)证明证明是一个偏

16、序关系是一个偏序关系。西安电子科技大学多媒体研究所 242022-7-37.17.1格格任取任取a,bA, aa = a,根据根据的定义可知的定义可知 aa,因此因此a是是自反自反的。的。设设ab, ba,则则a b = a = b,因此因此是是反对称反对称的。的。设设ab, bc,则有则有 a b = a 和和 bc = bac = ( a b) c = a ( b c ) =a b = a则有则有 a c。因此。因此是是传递传递的。的。因此可知因此可知是一个偏序集合。是一个偏序集合。 西安电子科技大学多媒体研究所 252022-7-37.17.1格格(ii)证明任取证明任取a,bA, a和

17、和b存在存在最小上界最小上界和和最大下界最大下界。因为因为(ab)a = aba = ab (ab)b = abb = ab因此因此ab a , abbab是是a和和b的下界。的下界。西安电子科技大学多媒体研究所 262022-7-37.17.1格格设设c是是a和和b的任意下界，即有的任意下界，即有ca且且cb,则有则有 ca = c且且cb = c而而 c(ab) = (ca) b = cb = c所以有所以有c ab。由此可知，。由此可知， ab是是a和和b的最大下的最大下界。界。同理可证，同理可证， ab是是a和和b的最小上界。的最小上界。由由(i)、(ii)可知，可知，是一个格。是一个

18、格。西安电子科技大学多媒体研究所 272022-7-37.27.2子格子格u子格：子格：设设是一个格，是一个格，是由是由所诱导的代数系统。所诱导的代数系统。S L且且S , 如果如果L中的两个运算中的两个运算和和在在S上是封闭的，上是封闭的，则称则称是是的子格。的子格。 格载体L的一个子集S如果对原对原保交和保联运算都封闭保交和保联运算都封闭，称是的子格。子格是子代数的概念在格上的扩展。西安电子科技大学多媒体研究所 282022-7-37.27.2子格子格u【例题例题】图图(a)、(b)中所示的格中所示的格分别分别是格是格的子格吗？的子格吗？(a)abdcedeab(b)一个格中的部分元素在原

19、偏序关系上构成一个格，不能说明它就是原格的子格。主要看该子集上的任意两个元素在原运主要看该子集上的任意两个元素在原运算保交和保联下的结果是否也在该子集算保交和保联下的结果是否也在该子集中。中。abecdffacde西安电子科技大学多媒体研究所 292022-7-37.27.2格同态格同态u格同态：格同态：设设和和是两个格，由它们所是两个格，由它们所分别诱导的代数系统为分别诱导的代数系统为和和,其其中中和和是保交运算是保交运算, 和和是保联运算。如是保联运算。如果存在一个从果存在一个从L1到到L2的映射的映射f,使得任取使得任取a,bL1满足满足 f(ab)=f(a) f(b) f(ab)=f(

20、a) f(b)则称则称f为从为从到到的格同态，称的格同态，称为为的同态象。的同态象。西安电子科技大学多媒体研究所 302022-7-37.27.2格同态格同态u【例题例题】设集合设集合A=a,b,c,是一个格，其哈是一个格，其哈斯图如图斯图如图(a)所示。集合所示。集合B= (A),也是一个格，也是一个格，其哈斯图如图其哈斯图如图(b)所示。函数所示。函数f:AB,其中其中f(x)=y| yx。证明。证明:f是从是从到到的格同态。的格同态。(a)(b)abccb西安电子科技大学多媒体研究所 312022-7-37.27.2格同态格同态证明：证明：是一个格，设其诱导的代数格为是一个格，设其诱导的

21、代数格为，任取，任取a,bA,因为因为是一个链，是一个链，所以所以 a b=mina,b ab=maxa,b诱导的代数格为诱导的代数格为。(i)A中元素在函数中元素在函数f下的象分别为下的象分别为 f(a)=a, f(b)=a,b, f(c)=a,b,c故故f是从是从A到到B的单射函数。的单射函数。西安电子科技大学多媒体研究所 322022-7-37.27.2格同态格同态(ii)f(x1 x2)=f(minx1,x2)=y| yminx1,x2 =y| y x1 y| y x2 =f(x1) f(x2) f(x1 x2)=f(maxx1,x2)=y| ymaxx1,x2 =y| y x1 y|

22、 y x2 =f(x1) f(x2)故故f是从是从到到的格同态的格同态。西安电子科技大学多媒体研究所 332022-7-37.27.2格同态性质格同态性质u定理定理(格同态的保序性格同态的保序性) 设设f是从格是从格 到格到格的格同态，则对任意的格同态，则对任意x,yL1,如果如果xy,必有必有f(x) f(y)。 证明：因为证明：因为xy，所以有，所以有xy=x,又又 f(xy)=f(x) f(y) = f(x) 故故f(x) f(y)。西安电子科技大学多媒体研究所 342022-7-37.27.2格同构格同构u格同构：格同构：设设f是从格是从格到格到格的格的格同态，若同态，若f是双射函数，

23、则称是双射函数，则称f为从为从 到到的格同构。的格同构。u具有一具有一,二二,三个元素的格三个元素的格,分别是一、二分别是一、二,三三个元素的链个元素的链,四个和五个元素对应表中同构四个和五个元素对应表中同构格之一，如下表所示：格之一，如下表所示：西安电子科技大学多媒体研究所 352022-7-3哈斯图哈斯图1个元素的格个元素的格2个元素的格个元素的格3个元素的格个元素的格4个元素的互个元素的互不同构的格不同构的格5个元素的互个元素的互不同构的格不同构的格西安电子科技大学多媒体研究所 362022-7-37.37.3特殊的格：分配格特殊的格：分配格u分配格：分配格：设设是由格是由格所诱导所诱导

24、的代数系统，如果对任意的的代数系统，如果对任意的a,b,cL,满足：满足： a(bc) = (ab)(ac) 保交对保联可分配保交对保联可分配 a(bc) = (ab)(ac) 保联对保交可分配保联对保交可分配 则称则称是分配格。是分配格。 西安电子科技大学多媒体研究所 372022-7-37.37.3分配格分配格u【例题例题】图图(a)、(b)所示的格是分配格吗？所示的格是分配格吗？为什么？为什么？分析：均不是分配格。考虑分析：均不是分配格。考虑b(cd)与与(b c)(b d)；考虑；考虑c (bd)与与(cb)(cd)cabde(a)钻石格abcde(b)五角格西安电子科技大学多媒体研究

25、所 382022-7-37.37.3分配格分配格u定理定理设设是一个格，若是一个格，若运算对运算对运算可分配，则运算可分配，则对对也可分配，反之亦也可分配，反之亦然。然。证明：设证明：设运算对运算对运算可分配，即任取运算可分配，即任取a,b,cL,满足满足 a(bc) = (ab)(ac)现要证现要证 a(bc) = (ab)(ac)(ab)(ac) = (ab) a) (ab) c) = a (ab) c) 西安电子科技大学多媒体研究所 392022-7-37.37.3分配格分配格 = a(ac)(bc) = a(ac)(bc) = a(bc)由此可知，由此可知，运算对运算对运算也可分配。运

26、算也可分配。同理可证，若同理可证，若运算对运算对运算可分配，则运算可分配，则 运算运算对对运算也可分配。运算也可分配。西安电子科技大学多媒体研究所 402022-7-37.37.3分配格分配格u定理定理每个链都是分配格。每个链都是分配格。证明：设证明：设是一个链，则是一个链，则必是一个格。必是一个格。任取任取a,b,cL,讨论以下两种情况：讨论以下两种情况：(i)ab或或ac无论是无论是ab或或ac都有都有 a(bc)=a (ab)(ac) = a 即即 a(bc)= (ab)(ac) 西安电子科技大学多媒体研究所 412022-7-37.37.3分配格分配格(ii)ba且且ca:由由ba,

27、ca知知 bc a，可得，可得 a(bc )= bc 又因为又因为(ab) (ac) = bc ,所以有所以有 a(bc )= (ab) (ac) 由由(i)、(ii)可知可知运算对运算对运算可分配，于是运算可分配，于是运运算对算对运算也可分配。运算也可分配。故每个链都是分配格。故每个链都是分配格。西安电子科技大学多媒体研究所 422022-7-37.37.3分配格分配格u定理定理设设是一个分配格，那么对于是一个分配格，那么对于任意任意a,b,cL,如果有如果有ab=ac和和ab=ac成立，则必有成立，则必有b=c。证明：证明：b=b(ab)=b(ac) = (ba)(bc) =(ac) (b

28、c)=(ab)c = (ac) c = c西安电子科技大学多媒体研究所 432022-7-37.37.3分配格分配格u定理定理一个格是分配格，当且仅当它不一个格是分配格，当且仅当它不存在与钻石格和五角格同构的子格。存在与钻石格和五角格同构的子格。u定理定理分配格的子格是分配格。分配格的子格是分配格。西安电子科技大学多媒体研究所 442022-7-37.37.3有界格有界格u全上界全上界(全下界全下界)：如果格如果格中存在一个中存在一个元素元素a,对于任何元素对于任何元素bL,均有均有b a(a b),则则称称a为格为格的全上界的全上界(全下界全下界)。通常将。通常将全上界记为全上界记为“1”，

29、而将全下界记为，而将全下界记为“0”。u定理定理一个格一个格若有全上界若有全上界(全下界全下界)，则是唯一的。则是唯一的。西安电子科技大学多媒体研究所 452022-7-37.37.3有界格有界格u有界格：有界格：如果一个格既有全上界又有全下如果一个格既有全上界又有全下界，则称该格为有界格。界，则称该格为有界格。u定理定理设设是一个有界格，则对任意是一个有界格，则对任意aA,必有必有 a1 = 1, a1 = a a0 = a, a0 = 0u定理定理每个有限格都是有界格。每个有限格都是有界格。西安电子科技大学多媒体研究所 462022-7-37.37.3有补格有补格u补元：补元：设设是一个有

30、界格，对于是一个有界格，对于L中一中一个元素个元素a,如果存在元素如果存在元素bL,使得使得ab=0, ab=1,则称元素则称元素b是是a的补元，记为的补元，记为a=b。同时，同时，a也是也是b的补元，即的补元，即b=a。西安电子科技大学多媒体研究所 472022-7-37.37.3有补格有补格u【例题例题】写出下图所示的各有界格中所有写出下图所示的各有界格中所有元素的补元。元素的补元。1abc0c1bd0(b)(c)(d)(a)1a 010abc西安电子科技大学多媒体研究所 482022-7-37.37.3有补格有补格u有补格：有补格：在一个有界格中，若每个元素至在一个有界格中，若每个元素至

31、少有一个补元，则称此格为有补格。少有一个补元，则称此格为有补格。u【例题例题】下图中各哈斯图所表示的格是否下图中各哈斯图所表示的格是否是有补格？为什么？是有补格？为什么？01abcde10abcd10abcd01abcdef(a)(b)(c)(d)西安电子科技大学多媒体研究所 492022-7-37.37.3布尔格布尔格u布尔格：布尔格：若一个格既是有补格又是分配格，若一个格既是有补格又是分配格，则称此格为布尔格。则称此格为布尔格。u定理定理布尔格布尔格中，每一个元素都有中，每一个元素都有唯一的补元。唯一的补元。证明：证明： 是布尔格，因此是布尔格，因此L中的每一个元素都中的每一个元素都有补元

32、。设有补元。设aL, a有两个补元有两个补元b, cL,根据补元根据补元的定义有：的定义有：ab=0, ac=0 ab=1, ac=1根据分配格的性质可知：根据分配格的性质可知：b=c。西安电子科技大学多媒体研究所 502022-7-37.37.3布尔格布尔格u【例题例题】设设S是非空有限集合是非空有限集合,证明证明 是一个布尔格。是一个布尔格。证明：证明：是一个格，它诱导的代数格为是一个格，它诱导的代数格为。因为。因为,有全上界有全上界S和全和全下届下届 ，因此它是有界格。，因此它是有界格。任取任取T(S), =S T是是T的补元，因此它是有补格。的补元，因此它是有补格。和和是相互可分配的，

33、因此它是分配格。是相互可分配的，因此它是分配格。综上所述，综上所述，是一个布尔格。是一个布尔格。T西安电子科技大学多媒体研究所 512022-7-37.47.4布尔代数与布尔表达式布尔代数与布尔表达式u布尔代数：布尔代数：由布尔格由布尔格可以诱导出一个可以诱导出一个代数系统代数系统，该代数系统称为布，该代数系统称为布尔代数。尔代数。布尔格上的每个元素都有且仅有一个补元，因此布尔格诱导的代数系统有三个运算：保交、保联和补运算，其中求补运算是一元运算。西安电子科技大学多媒体研究所 522022-7-37.47.4布尔代数布尔代数u【例题例题】求由布尔格求由布尔格所诱导的布所诱导的布尔代数系统。尔代

34、数系统。解答：解答：是由布尔格是由布尔格所所诱导的一个布尔代数，其中诱导的一个布尔代数，其中、和和 分别是集分别是集合的交、并和补运算。合的交、并和补运算。西安电子科技大学多媒体研究所 532022-7-37.47.4布尔代数布尔代数u有限布尔代数：有限布尔代数：载体含有有限个元素的布载体含有有限个元素的布尔代数称为有限布尔代数。尔代数称为有限布尔代数。u布尔代数的性质：设布尔代数的性质：设是一个布是一个布尔代数，任取尔代数，任取a,b,cB都有性质成立：都有性质成立：(1)交换律交换律 ab = ba, ab = b a(2)结合律结合律 a(bc) = (ab)c, a (b c) = (

35、a b) c西安电子科技大学多媒体研究所 542022-7-37.47.4布尔代数的性质布尔代数的性质(3)等幂律等幂律 aa = a, aa = a(4)吸收律吸收律 a(ab) = a, a(ab) = a(5)分配律分配律 a(bc) = (ab)(ac) a(bc) = (ab)(ac)(6)同一律同一律 a0 = a, a 1 = a(7)零一律零一律 a0 = 0, a1 = 1(8)互补律互补律 aa = 1, a a = 0(9)对合律对合律 (a) = a(10)德德.摩根律摩根律 (ab)= ab, (ab)=ab西安电子科技大学多媒体研究所 552022-7-37.47.

36、4布尔代数的性质布尔代数的性质证明证明:(10)(ab)(ab)=(aba) (abb) = (b(aa) (a(bb) = (b1)(a1) = 1 1 = 1 (ab) (ab)=(aab)(bab) = (aa)b) (bb )a) =(0 b) (0 a) = 00 = 0所以有所以有(ab)= ab。同理可证。同理可证(ab)=ab。西安电子科技大学多媒体研究所 562022-7-37.47.4布尔代数布尔代数u定理定理设设是一个代数系统，是一个代数系统， 和和是是B上的二元运算，如果对任意上的二元运算，如果对任意a,b,cB 均满足以下四条性质，则称均满足以下四条性质，则称 是一个

37、布尔代数。是一个布尔代数。(1)交换律交换律 ab = ba, ab = b a(2)分配律分配律 a(bc) = (ab)(ac) a(bc) = (ab)(ac)西安电子科技大学多媒体研究所 572022-7-37.47.4布尔代数布尔代数(3)同一律同一律 B中存在两个元素中存在两个元素1和和0，并且对，并且对B中任中任意元素意元素a,满足满足 a 1 = a, a 0 = a(4)互补律互补律 对对B中每个元素中每个元素a都存在唯一元素都存在唯一元素aB，满足，满足 a a = 0, a a = 1 西安电子科技大学多媒体研究所 582022-7-37.47.4有限布尔代数的原子表示有

38、限布尔代数的原子表示u本小节研究有限布尔代数的一个重要性质，本小节研究有限布尔代数的一个重要性质，就是任何有限布尔代数就是任何有限布尔代数都同构都同构于某有限集合于某有限集合S的幂代数的幂代数,这说这说明有限布尔代数有以下结构特征：明有限布尔代数有以下结构特征：(1)任何有限布尔代数，其载体元素个数是任何有限布尔代数，其载体元素个数是2的幂次。的幂次。(2)对每个正整数对每个正整数n,都存在具有都存在具有2n个元素的布尔格。个元素的布尔格。(3)对于元素个数相同的布尔代数都是同构的。对于元素个数相同的布尔代数都是同构的。西安电子科技大学多媒体研究所 592022-7-37.47.4有限布尔代数

39、的原子表示有限布尔代数的原子表示u覆盖：覆盖：设设a,b是一个格中的两个元素，如果是一个格中的两个元素，如果ba且且ba,即即ba,并且在此格中再没有别的并且在此格中再没有别的元素元素c,使得使得bc和和ca,则称元素则称元素a覆盖元素覆盖元素b。u原子：原子：设设是一个格，且具有全下界是一个格，且具有全下界0,如果有元素如果有元素aA, a盖住盖住0，则称元素，则称元素a为原为原子。子。西安电子科技大学多媒体研究所 602022-7-37.47.4有限布尔代数的原子表示有限布尔代数的原子表示u定理定理设设是一个布尔代数，是一个布尔代数，a和和b是该布尔代数的两个原子，且有是该布尔代数的两个原

40、子，且有ab,则则a b = 0。证明：证明：(反证法反证法)假设假设ab = c 0,因为因为ab,则有则有0 c a或或0 c b，这与，这与a和和b是原子相矛盾是原子相矛盾,故假设错误，有故假设错误，有ab = 0。西安电子科技大学多媒体研究所 612022-7-37.4Stone7.4Stone表示定理表示定理u定理定理(Stone表示定理表示定理)设设是是一个有限布尔格一个有限布尔格所诱导的一个有限布所诱导的一个有限布尔格代数，尔格代数，S是布尔格是布尔格的所有原子的的所有原子的集合集合,则则和和同构。同构。西安电子科技大学多媒体研究所 622022-7-37.4Stone7.4St

41、one表示定理的推论表示定理的推论u推论推论1有限布尔格的元素个数必定等于有限布尔格的元素个数必定等于2n,其中其中n是该布尔格中所有原子的个数。是该布尔格中所有原子的个数。u推论推论2任何一个具有任何一个具有2n个元素的有限布个元素的有限布尔代数都是同构的。尔代数都是同构的。西安电子科技大学多媒体研究所 632022-7-37.47.4布尔表达式布尔表达式u布尔常元：布尔常元：设设是一个布尔代数，是一个布尔代数，称称B中的元素为该布尔代数的布尔常元。中的元素为该布尔代数的布尔常元。u布尔变元：布尔变元：设设是一个布尔代数，是一个布尔代数，称取值于称取值于B中元素的变量为该布尔代数的布中元素的变量为该布尔代数的布尔变元。尔变元。西安电子科技大学多媒体研究所 642022-7-37.47.4布尔表达式布尔表达式u布尔表达式的归纳定义：布尔表达式的归纳定义：n单个布尔常元和单个布尔变元是布尔表达式。单个布尔常元和单