离散数学第六章第三节

1、1第6-3讲 布尔代数1. 布尔代数2.原子3.Stone表示定理4. 课堂练习5. 第6-3讲 作业21、布尔代数(1)定理1 若a,b是布尔代数中任意两个元素，则 (a)=a； (ab)=ab； (ab)=ab定义1 布尔格诱导的代数系统叫布尔代数。证： (1)按定义，按定义，a a与与a a互补，所以互补，所以a a的补元是的补元是a a，即，即 (a(a) )=a=a。(2)可直接验证可直接验证a ab b的补元是的补元是(a(ab b):): (ab)(ab)=(aba)(abb) (分配律) =(1b)(a1)=11=1 (ab)(ab)=(aab)(bab) =(0b)(a0)=

2、00=0(3)可仿照(2)证31、布尔代数(2)定义3 具有有限个元素的布尔代数叫有限布尔代数。定义2 设和是两个布尔代数，如果存在双射f:AB，对任意a,bA,有 f(ab)=f(a)f(b) f(ab)=f(a)f(b) f(a)=f(a)则称和 同构。关于有限布尔代数有如下重要结论：v 对任一正整数n，必存在含有2n个元素的布尔代数。v 任一有限布尔代数的元素的个数必为2n，n为正整数。v 元素个数相同的布尔代数都是同构的。42、原子 (1)定义4 设格具有全下界0，如果元素a(0) A A盖住0，则称a是原子。例如，右图所示格中，例如，右图所示格中，元素元素d,ed,e是原子。是原子。

3、 显然，显然，如果如果a,ba,b皆为原子，皆为原子，a a b b，则，则a a b=0b=0。 为了证明上述关于有限布尔代数的结论，先引入原子为了证明上述关于有限布尔代数的结论，先引入原子的概念。的概念。52、原子 (2)定理2 设有限格具有全下界0，若b0，则至少存在一个原子a，使得ab。 证：如果如果b b本身为原子本身为原子，因，因b b b b，命题得证。，命题得证。如果如果b b不是原子不是原子，按盖住的定义，必存在，按盖住的定义，必存在b b1 1 A A，使，使00b b1 1bb，若若b b1 1为原子，命题得证。否则，必存在为原子，命题得证。否则，必存在b b1 1 A

4、A，使，使 0 0 b b2 2 b b1 1 bb，因为因为A A是有限集合，经过上述有限的步骤之后，必可找到是有限集合，经过上述有限的步骤之后，必可找到一个原子一个原子b bi i，使使 0 0 b bi i .b b2 2 b b1 1 bb证毕。证毕。63、Stone表示定理 (1)引理1 在布尔格中， b bc c=0=0当且仅当当且仅当b b c。证：如果如果bc=0，则 (bc)c=0c=c (1)另一方面，另一方面， (bc)c=(b bc)(cc)=(b bc)1 =b bc (2)由由(1)(1)、(2)(2)式得式得 bc=c再根据格的性质再根据格的性质8 8可知可知 b

5、 b c。 反之，如果反之，如果b b c，则则bc c cc（格的保序性格的保序性），即即bc 0 0，因，因0 0是全下界，要上式成立，只能是是全下界，要上式成立，只能是bc=0=0。73、Stone表示定理 (2)引理2 设是有限布尔代数，若bA，且b0，又设a1,a2,ak是A中满足aj b(j=1,2,k)的所有原子，则b=a1a2 ak，并且这种表示是唯一的。证：令令c=a1a2 ak 因因aj b（0 j k），所以所以c c b b。 下面证明下面证明b b c c。根据引理。根据引理1 1，只须证，只须证b bc=0。用反证法，用反证法，假设假设b bc0，根据定理根据定理2

6、 2，存在原子，存在原子a a，使，使a a b bc。 根据格的性质根据格的性质8 8， b bc b b， b bc c。 再由传递性得：再由传递性得： a a b b， a a c c。 因因a a是原子，且是原子，且a a b b，所以，所以 a aa1,a2,ak，故故a a c c。 由由a a c c和和a a c c可得可得a a c cc，从而a a 0 0，与，与a a是原子矛盾。是原子矛盾。 最后由最后由c c b b和和b b c c得得: b=c=: b=c=a1a2 ak。83、Stone表示定理 (3)引理2 设是有限布尔代数，若bA且b0，又设a1,a2,ak是

7、A中满足aj b(j=1,2,k)的所有原子， 则b=a1a2 ak，并且这种表示是唯一的。证(续)：下面证明表示的唯一性。下面证明表示的唯一性。设设b有另一表达式：有另一表达式：b=aj1aj2 ajt，其中其中ajr(0 r t)是是原子。于是有原子。于是有 ajr b b(0 r t) 因为已设因为已设a1,a2,ak是是A A中所有满足中所有满足ai b的不同原子，的不同原子，所以所以t t k k。问题转化为证明。问题转化为证明t t=k=k。 假设假设t tkk ，则至少存在一个则至少存在一个aj0a1,a2,ak，使得a aj0j0 a ajx jx (0 x t)。因因 a a

8、j0j0( (aj1aj2ajt)=a)=aj0j0( (a1a2a aj0j0ak) )即即 (a(aj0j0aj1) )(a(aj0j0aj2) ).( a aj0j0ajt) ) =(a =(aj0j0a1) )(a(aj0j0a2) ).(a aj0j0aj0j0) ).( a aj0j0ak) ) 亦即亦即 0 0 0 . 0 = 0 0 .a aj0 j0 0 .0那么得那么得a aj0j0=0=0，与，与a aj0 j0 是原子相矛盾，故必有是原子相矛盾，故必有t=kt=k。93、Stone表示定理 (4)引理3 设是布尔格，a为原子，b0，则a b和a b 二式有且仅有一个成立

9、。证：因因ab a，若若a a为原子为原子，b也是原子，则是原子，则ab=0。即即a(b)=0，根据引理根据引理1 1，a a b b。 如如b b不不是原子，则是原子，则ab=a，根据格的性质根据格的性质8 8，a a b b。 下面证明下面证明二式仅有一个成立二式仅有一个成立。 假设假设a a b b和和a a b同时同时成立，则成立，则a a b bb，即即a=0，与与a a是原是原子矛盾。子矛盾。 103、Stone表示定理 (5)定理3(Stone表示定理) 设是有限布尔格所诱导的有限布尔代数，S是中所有原子的集合，则和同构。证明线索： (1) (1) 作映射作映射f:Af:A(S)

10、(S)， 当当a=0a=0时，时，f(a)=f(a)= ； 当当a a 0 0时，时，f(a)=Sf(a)=Si i，S Si i表示所有满足表示所有满足x x a a的原子的原子x x的集合。的集合。然后证明然后证明f f是双射。是双射。 (2)(2)证明证明f f是同构映射：是同构映射： f(af(a b)=f(a)b)=f(a) f(b)f(b) f(a f(a b)=f(a)b)=f(a) f(b)f(b) f(a f(a)=f)=f(a)(a)113、Stone表示定理 (6)定理3的推论： 推论1 有限布尔格的元素的个数必等于2n，其中n是布尔格中所有原子的个数。（这是因为（这是因

11、为|A|=|A|=| (S)(S)|=2|=2|S|S|）推论2 元素的个数相同的有限布尔代数是同构的。（这是因为任何有限布尔代数都与它的原子集合构成的幂（这是因为任何有限布尔代数都与它的原子集合构成的幂集代数集代数 同构。同构。） 问题：问题：四个元素的链是布尔代数吗？四个元素的链是布尔代数吗？答：答：不是布尔代数。因为链的中间两个元素没有补元，链不是布尔代数。因为链的中间两个元素没有补元，链仅仅是分配格，不是有补格。仅仅是分配格，不是有补格。124、课堂练习练习1 设是布尔代数，x,yS。证明，xy当且仅当yx解:由由 引理引理1 1 ， y y x x当且仅当当且仅当y y (x(x) )=0,=0,即即y y x=0 x=0。 再由引理再由引理1 1， x x y y=0=0当且仅当当且仅当x x y y。 故在任何布尔代数中，故在任何布尔代数中， x x y y当且仅当当且仅当y y x x。提示：应用教材P255引理6-4.1进行证明13第6-3讲