离散数学 格与布尔代数.ppt

《离散数学 格与布尔代数.ppt》由会员分享，可在线阅读，更多相关《离散数学 格与布尔代数.ppt（84页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、离散数学 格与布尔代数现在学习的是第1页，共84页2.B的最小元与最大元的最小元与最大元 y是是B的最小元的最小元y B x(x Byx)y是是B的最大元的最大元y B x(x Bxy)2,3,6的最小元的最小元:无无 最大元最大元:6B如果有最小元如果有最小元(最大元最大元),则是则是唯一唯一的。的。3.B的下界与上界的下界与上界y是是B的下界的下界y A x(x Byx)y是是B的上界的上界y A x(x Bxy)2,3,6的下界的下界:1 上界上界:6,12,24,364.B的最大下界的最大下界(下确界下确界)与最小上界与最小上界(上确界上确界)y是是B的最大下界的最大下界(下确界下确界

2、)：B的所有下界的所有下界x,有有xy。y是是B的最小上界的最小上界(上确界上确界)：B的所有上界的所有上界x,有有yx。2,3,6下确界下确界:1 上确界上确界:6 (B若有下若有下(上上)确界，则确界，则唯一唯一)。12。24。36。现在学习的是第2页，共84页7-1 格(Lattice)一一.基本概念基本概念1.格的定义格的定义 是偏序集，如果任何是偏序集，如果任何a,b A,使得使得a,b都有最大都有最大下界和最小上界，则称下界和最小上界，则称是格。是格。右图的三个偏右图的三个偏序集，序集，不是格，不是格，因为因为24,36无无最小上界。最小上界。是格。是格。12。24。36。30。3

3、。2。5。10。5。6。3。4。1。2。现在学习的是第3页，共84页这三个偏序集，也都不是格，第一个与第三个是同构的。这三个偏序集，也都不是格，第一个与第三个是同构的。因为因为 d和和e无下界，也无最小上界；无下界，也无最小上界；b,c虽有下界，但无虽有下界，但无最大下界。最大下界。2,3无最大下界，无最大下界，4,5无最小上界。无最小上界。2.平凡格平凡格：所有全序都是格，称之为平凡格。：所有全序都是格，称之为平凡格。因为全序中任何两个元素因为全序中任何两个元素x,y，要么要么xy,要么要么yx。如果如果xy，则则x,y的最大下界为的最大下界为x，最小上界为最小上界为y。如果如果yx，则则x

4、,y的最大下界为的最大下界为y，最小上界为最小上界为 x。即这即这x,y的最大下界为较小元素，最小上界为较大元素的最大下界为较小元素，最小上界为较大元素.dab ce12 34 5 6dab c e现在学习的是第4页，共84页3.由格诱导的代数系统由格诱导的代数系统设设是格是格,在在A上定义二元运算上定义二元运算和和为为:a,b A a b=LUB a,b a,b的最小上界的最小上界.Least Upper Bound a b=GLB a,b a,b的最大下界的最大下界.Greatest Lower Bound称称是由格是由格诱导的代数系统诱导的代数系统.(-并并,-交交)例如右边的格中例如右

5、边的格中a b=b a b=a b c=e4.子格子格：设：设是格是格,是是由由诱导的代数系统。诱导的代数系统。B是是A的的非空子集，如果非空子集，如果和和在在B上封闭，则上封闭，则称称是是的子格。的子格。是是的子格。的子格。而而不是不是.b c=d B,(运算规则要从格运算规则要从格中找中找)e ab d cb a c fe gb a c fe g d a cb d现在学习的是第5页，共84页二二.格的对偶原理格的对偶原理 设设是格，是格，的逆关系记作的逆关系记作，也是偏序关系。也是偏序关系。也是格，也是格，的的Hasse图是将图是将的的Hasse图图颠倒颠倒180即可。即可。格的对偶原理格

6、的对偶原理：设：设P是对任何格都为真的命题，如果将是对任何格都为真的命题，如果将P中的中的换成换成，换成换成，换成换成，就得到命题，就得到命题P,称称P为为P的对偶命题，则的对偶命题，则P对任何格也是为真的命题。对任何格也是为真的命题。例如：例如：P:a ba P:a ba a,b的最大下界的最大下界a a,b的最小上界的最小上界a现在学习的是第6页，共84页三三.格的性质格的性质 是由格是由格诱导的代数系统。诱导的代数系统。a,b,c,d A1.aa b ba b a ba a bb 此性质由运算此性质由运算和和的定义直接得证。的定义直接得证。2.如果如果ab，cd，则则 a cb d，a

7、cb d。证明证明：如果：如果ab，又又bb d，由传递性得由传递性得 ab d,类似由类似由cd，db d，由传递性得由传递性得 cb d,这说明这说明b d是是 a,c 的的一个一个上界，上界，而而a c是是 a,c 的最小上界，所的最小上界，所以以 a cb d。类似可证类似可证 a cb d。推论推论：在一个格中，任在一个格中，任意意 a,b,c A，如果，如果bc，则，则 a ba c，a ba c。此性质称为此性质称为格的保序性格的保序性。现在学习的是第7页，共84页3.和和都满足交换律。都满足交换律。即即 a b=b a，a b=b a 此性质由运算此性质由运算和和的定义直接得证

8、。的定义直接得证。4.和和都满足幂等律。都满足幂等律。即即 a a=a a a=a 证明证明：由性质：由性质1,aa a (再证再证a aa)又由又由自反有自反有aa，这说明这说明a是是a的上界，的上界，而而a a是是a的最小的最小上界上界，所以所以 a a a。最后由最后由反对称得反对称得 a a=a。由对偶原理得由对偶原理得 a a=a现在学习的是第8页，共84页5.和和都满足结合律。即都满足结合律。即 (a b)c=a(b c)，(a b)c=a(b c)证明证明：先证明先证明(a b)c a(b c)因因 a a(b c)，bb c a(b c)所以所以 a ba(b c)又又 cb

9、c a(b c)于是有于是有(a b)c a(b c)再再证证 a(b c)(a b)c 因因aa b(a b)c；再由再由ba b(a b)c，c(a b)c 所以所以 b c(a b)c于是有于是有 a(b c)(a b)c最后由最后由反对称得反对称得(a b)c=a(b c)类似可证类似可证 (a b)c=a(b c)。现在学习的是第9页，共84页6.和和都满足都满足吸收律吸收律。即。即 a(a b)=a，a(a b)=a。证明证明：显然有显然有 aa(a b)再证再证 a(a b)a 因因 a a ，a b a 所以所以 a(a b)a最后由最后由反对称得反对称得 a(a b)=a，类

10、似可证类似可证 a(a b)=a。现在学习的是第10页，共84页7.和和不不满足满足分配律分配律。但有分配。但有分配不等式不等式：a(b c)(a b)(a c)，(a b)(a c)a(b c)。我们我们先看先看右图的右图的例子例子：d(b e)=d c=d (d b)(d e)=a e=e 而而 de 即即 d(b e)(d b)(d e)证明证明：因因 aa b，aa c 所以所以 a(a b)(a c)又因又因 b cb a b，b cc a c 所以所以 b c(a b)(a c)于是有于是有 a(b c)(a b)(a c)。由对偶原理得由对偶原理得 a(b c)(a b)(a c

11、)。即即 (a b)(a c)a(b c)。c ab e d现在学习的是第11页，共84页8.ab a b=b a b=a证明证明：先先证明证明ab a b=a 先证先证ab a b=a 由由 ab，又，又aa 所以所以aa b 又由又由a b的定义有的定义有a ba 由反对由反对称得称得 a b=a 再证再证 a b=a ab 由由 a b=a 则则 a=a b b。综上综上得得 ab a b=b 下面证明下面证明ab a b=b 先证先证ab a b=b 由由 ab，又，又bb 所以所以 a b b 又因为又因为 ba b 由反对称得由反对称得 a b=b 再证再证 a b=b ab 由由

12、 a b=b 因因 a a b 所以所以 ab。综上综上得得 ab a b=b 现在学习的是第12页，共84页引理：是代数系统，如果是代数系统，如果和和是是满足吸收律满足吸收律的二元运算，则的二元运算，则和和必满足幂等律必满足幂等律。证明证明：任取：任取a,b A 因为因为 和和满足吸收律。满足吸收律。于是有于是有 a(a b)=a-a(a b)=a-。由于上式中的由于上式中的b是任意的，可以令是任意的，可以令b=a b 并代入并代入式得式得 a(a(a b)=a 由由式得式得 a a=a同理可证同理可证a a=a现在学习的是第13页，共84页定理：定理：设设是代数系统，如果是代数系统，如果和

13、和是是满足交换律，满足交换律，结合律，和吸收律结合律，和吸收律的二元运算，的二元运算，则则A上存在偏序关系上存在偏序关系 ，使使是一个格，并且该格所诱导的代数系统恰好是是一个格，并且该格所诱导的代数系统恰好是。（由代数系统得到格）（由代数系统得到格）证明：设在证明：设在A上定义二元关系上定义二元关系 为：为：对任意对任意a,b A,a b 当且仅当当且仅当 a b=a（1）先证二元关系）先证二元关系 是一个偏序关系是一个偏序关系（2 2）再证再证a b 是是 a,b 的下确界的下确界（3）然后证）然后证a b是是 a,b 的上确界的上确界见书上见书上238页页现在学习的是第14页，共84页四.

14、格的同态与同构1.定义定义：设：设 和和是两个格，由它们诱导是两个格，由它们诱导的代数系统分别是的代数系统分别是和和，如果存，如果存在映射在映射 f:A1A2 ，使得对任何使得对任何a,b A1，有，有 f(a 1b)=f(a)2f(b)f(a 1b)=f(a)2f(b)则称则称f是是到到 的同态映射。的同态映射。也称也称是是 的同态像。的同态像。如果如果 f 是双射的，就称是双射的，就称f是是到到，的格同构，的格同构，也称格也称格 和和同构。同构。现在学习的是第15页，共84页例：例：，A=1,2,3,6,是是A上整除关系。上整除关系。，E=a,b它们诱导的代数系统分别是它们诱导的代数系统分

15、别是和和其中其中和和分别分别是求两个数的最小公倍数和最大公约数是求两个数的最小公倍数和最大公约数.f(2 3)=f(6)=a,b f(2)f(3)=a b=a,b f(2 3)=f(1)=f(2)f(3)=ab=f(2 6)=f(6)=a,b f(2)f(6)=a a,b=a,b f(2 6)=f(2)=a f(2)f(6)=a a,b=a 可见它们同构。可见它们同构。格同构，它们的哈斯图的形状一定相同。格同构，它们的哈斯图的形状一定相同。ba a,b 1 32 6f6 3 2 1 aba,bA P(E)现在学习的是第16页，共84页 具有具有1、2、3个元素的格分别同构于含有一、二、三个元素

16、的格分别同构于含有一、二、三 个元素个元素的链。的链。具有具有4个元素的格分别同构于下面两种格形式之一：个元素的格分别同构于下面两种格形式之一：具有具有5个素的格分别同构于下面五种格形式之一：个素的格分别同构于下面五种格形式之一：e d a b c d a b c c d d a b c e a b c e a b d a e b c d d a b c e a a b a b c现在学习的是第17页，共84页2.格同态的保序性格同态的保序性定理：设定理：设f是格是格 到到 的的同态同态映射，则对任映射，则对任何何a,b A1，如果如果a1b，则，则 f(a)2f(b)。证明：证明：令令和和

17、是格是格 和和 诱导的代数系统，任取诱导的代数系统，任取a,b A1，设设a1b，则则 a 1b=a f(a 1b)=f(a)即即 f(a)2f(b)=f(a)而而 f(a)2f(b)2f(b)所以所以 f(a)2f(b).3.格同构的保序性格同构的保序性定理：设两个定理：设两个格格为为和和，f是是A1到到A2的双射，的双射，则则f是是 到到的格同构，当且仅当的格同构，当且仅当 对任意对任意a,b A1，a1b f(a)2f(b)证明证明：令令和和 是格是格 和和 诱导的代数系统，诱导的代数系统，现在学习的是第18页，共84页1)必要性必要性：已知：已知 f是格是格 到到 的的同构同构映射，映

18、射，（往证：任取（往证：任取a,b A1,a1b f(a)2f(b)）a)先证先证 a1b f(a)2f(b)任取任取a,b A1,设设a1b，由格同态保序性得，由格同态保序性得 f(a)2 f(b)b)再证再证f(a)2f(b)a1b 设设 f(a)2f(b)，于是有于是有 f(a)=f(a)2f(b)=f(a 1b)因因f 是双射，所以是双射，所以 a=a 1b 所以所以 a1b 最后得最后得 a1b f(a)2f(b)。现在学习的是第19页，共84页2)充分性充分性：已知，对任意：已知，对任意a,b A1,a1b f(a)2f(b)(往证往证 f(a 1b)=f(a)2f(b)f(a 1

19、b)=f(a)2f(b)a)证证 f(a 1b)=f(a)2f(b)令令a 1b=c 所以所以 c1a c1b，由已知得由已知得 f(c)2f(a)和和f(c)2f(b)，所以所以 f(c)2f(a)2f(b)-再证再证 f(a)2f(b)2 f(c)：由于由于f(a),f(b)A2,又又2封闭封闭，得得 f(a)2f(b)A2,又由又由f:A1A2是双射，必有是双射，必有d A1,使得使得 f(a)2f(b)=f(d)所以所以 f(d)2f(a)，f(d)2f(b)由已知得：由已知得：d1a，d1b，于是，于是 d1a 1b=c，即即 d1c，于是，于是 f(d)2f(c)即即f(a)2f(

20、b)2 f(c)-由由得得 f(a)2f(b)=f(c)，即即 f(a 1b)=f(a)2f(b)。b)类似可证类似可证 f(a 1b)=f(a)2f(b)，所以，所以 f是它们的同构映射是它们的同构映射。现在学习的是第20页，共84页7-2 几个特殊格一一.分配格分配格 前面我们介绍一般的格，前面我们介绍一般的格，和和只满足分配不等式。只满足分配不等式。a(b c)(a b)(a c)，(a b)(a c)a(b c)。下面介绍的是满足分配律的格下面介绍的是满足分配律的格-分配格。分配格。1.定义定义：是由格是由格诱导的代数系统。如果诱导的代数系统。如果对对 a,b,c A，有，有 a(b

21、c)=(a b)(a c)，a(b c)=(a b)(a c)则称则称是是分配格。分配格。例：例：所诱导的代数系统为所诱导的代数系统为 所以所以是是分配格。分配格。现在学习的是第21页，共84页2.二个重要的五元素非分配格二个重要的五元素非分配格：2(3 5)=2 30=2(2 3)(2 5)=1 1=1 c(b d)=c a=c(c b)(c d)=e d=d可见它们都不是分配格。可见它们都不是分配格。3.分配格的判定分配格的判定：一个格是分配格的一个格是分配格的充分且必要条件充分且必要条件是在该格中没有任何是在该格中没有任何子格与上述两个五元素非分配格之一同构。子格与上述两个五元素非分配格

22、之一同构。用此方法可以判定下面两个格不是分配格：用此方法可以判定下面两个格不是分配格：3 1 30 2 5 d e a b c 4 1 6 3 5 2 f g a d c e b现在学习的是第22页，共84页4.分配格的性质分配格的性质1.在一个格中，如果在一个格中，如果对对可分配，则可分配，则对对也可也可分配。反之亦然。分配。反之亦然。证明证明：设设是由格是由格诱导的代数系统诱导的代数系统，且且对对可分配。则任取可分配。则任取 a,b,c A，(a b)(a c)=(a b)a)(a b)c)分配分配=a(a b)c)=a(a c)(b c)吸收、分配吸收、分配 =(a(a c)(b c)结

23、合结合=a(b c)即即对对也可分配也可分配 同理可证同理可证:如果如果对对可分配，则可分配，则对对也可分配也可分配.2.所有链均为所有链均为分配格。分配格。证明证明：显然任何链：显然任何链都不会含有都不会含有与与那两个五元素非分配格那两个五元素非分配格之一同构之一同构的子格，所以链必是分配格。的子格，所以链必是分配格。现在学习的是第23页，共84页3.设设是分配格，对任何是分配格，对任何a,b,c A，如果，如果有有 a b=a c 及及 a b=a c 则必有则必有 b=c。证明证明：任取：任取a,b,c A,设有设有 a b=a c 及及 a b=a c b=b(a b)(吸收律吸收律)

24、=b(a c)(代换代换)=(b a)(b c)(分配分配)=(a b)(b c)(交换交换)=(a c)(b c)(代换代换)=(a b)c (分配分配)=(a c)c (代换代换)=c (吸收律吸收律)现在学习的是第24页，共84页二.有界格1.格的全上界与全下界格的全上界与全下界1).全上界全上界:设设是格，如果存在元素是格，如果存在元素a A对任何对任何x A,xa，则称，则称 a是是格的全上界格的全上界，记作记作1。(即是即是A的最大元的最大元)定理定理7-2.4 一个格如果有全上界，则是唯一的。一个格如果有全上界，则是唯一的。(我们已证明过，最大元如果有，则是唯一的我们已证明过，最

25、大元如果有，则是唯一的)2).全下界全下界:设设是格，如果存在元素是格，如果存在元素a A对任何对任何x A,ax,则称则称 a是是格的全下界格的全下界,记作记作0。(即是即是A的最小元的最小元)定理定理7-2.5 一个格如果有全下界，则是唯一的。一个格如果有全下界，则是唯一的。从格的图形看：全上界从格的图形看：全上界1，就是图的最上边元素，就是图的最上边元素(只一个只一个)，全下界全下界0，就是图的最下边元素，就是图的最下边元素(只一个只一个)。b 0 1 a c 1 c 0现在学习的是第25页，共84页2.有界格定义有界格定义：如果一个格存在：如果一个格存在全上界全上界1与全下界与全下界0

26、，则，则称此格为有界格。称此格为有界格。设设是是有界有界格，则对任何格，则对任何a A,有有 因为因为a1,所以所以 a 1=a a 1=1 0a 所以所以 a 0=0 a 0=a 是否所有格都是是否所有格都是有界格？有界格？所有有限个元素的格都是有界格，所有有限个元素的格都是有界格，而无限个元素的格可能是无界格。例如而无限个元素的格可能是无界格。例如就既无全上界就既无全上界也无也无全全下界。下界。现在学习的是第26页，共84页三.有补格 回顾：集合的补集，回顾：集合的补集，若若 A B=E AB=则则 A=B，B=A如如E=a,b E=E a=b,b=a1.元素的补元元素的补元：设设是个有界

27、格，是个有界格，a A,如果存在如果存在 b A，使得使得 a b=1 且且 a b=0，则称则称a与与b互为补元。互为补元。例：右边的格中例：右边的格中 a的补元：的补元：c,e b的补元：的补元：无无 c的补元：的补元：a,d d的补元：的补元：c e的补元：的补元：a 0 的补元：的补元：1 1的补元：的补元：0 a,b a b e 0 1 b c d a现在学习的是第27页，共84页2.有补格的定义有补格的定义：一个有界格中，如果每个元素都有补元，则称之为有一个有界格中，如果每个元素都有补元，则称之为有补格。补格。上述有界格中，哪些是有补格？上述有界格中，哪些是有补格？上述有补格中，有

28、些元素的补元不唯一，如上述有补格中，有些元素的补元不唯一，如(2)中的中的b，那，那么什么样的有补格元素的补元唯一呢？么什么样的有补格元素的补元唯一呢？有界分配格有界分配格。请看下面定理：请看下面定理：a,b a b b 0 1 a c e 0 1 b c d a 1 c 0(1)(2)(3)(4)现在学习的是第28页，共84页定理定理72.6 在有界分配格中，如果元素有补元，则补元在有界分配格中，如果元素有补元，则补元是唯一的。是唯一的。证明：设证明：设是是有界分配格，任取有界分配格，任取a A，假设假设a有两个有两个补元补元b和和c，则则 a b=0 a b=1 a c=0 a c=1于是

29、有于是有 a b=a c 及及 a b=a c由分配格的性质由分配格的性质3得得 b=c ，所以，所以a的的补元是唯一的。补元是唯一的。四四.布尔格布尔格 如果一个格既是分配格又是有补格，则称之为布尔格。如果一个格既是分配格又是有补格，则称之为布尔格。布尔格中每个元素都有唯一补元，元素布尔格中每个元素都有唯一补元，元素 a 的补元记作的补元记作 。显然显然是布尔格。是布尔格。下面介绍由布尔格诱导的代数系统布尔代数。下面介绍由布尔格诱导的代数系统布尔代数。现在学习的是第29页，共84页73 布尔代数布尔代数 Boolean Algebra一一.定义定义 由布尔格由布尔格诱导的代数系统诱导的代数系

30、统称之为布尔代数。其称之为布尔代数。其中中 是取补元运算。是取补元运算。如果如果A是有限集合，则称它是有限布尔代数。是有限集合，则称它是有限布尔代数。例如例如：令：令BF,T，表示合取，表示合取，表示析取，表示析取，表示表示否定，否定，就是个就是个由右面格所诱导的由右面格所诱导的布尔代数。布尔代数。E=a,b,也是个也是个由右面格所诱导的由右面格所诱导的布尔代数。布尔代数。T F a,b a b现在学习的是第30页，共84页二二.布尔代数的性质布尔代数的性质设设布尔代数布尔代数,任意任意x,y,z B,有有交换律交换律 x y=y x x y=y x结合律结合律 x(y z)=(x y)z x

31、(y z)=(x y)z 幂等律幂等律 x x=x x x=x 吸收律吸收律 x(x y)=x x(x y)=x分配律分配律 x(y z)=(x y)(x z)x(y z)=(x y)(x z)同一律同一律 x 0=x x 1=x 零律零律 x 1=1 x 0=0 互补律互补律 x =1 x =0 对合律对合律底摩根定律底摩根定律现在学习的是第31页，共84页上述性质都可以由格，分配上述性质都可以由格，分配格，有界格，布尔格得到。下面只格，有界格，布尔格得到。下面只证明证明底摩根定律。底摩根定律。所以所以 。类似可证另一个。类似可证另一个。现在学习的是第32页，共84页三三.布尔代数的同构布尔

32、代数的同构1.定义定义：令：令和和 是两个布尔是两个布尔代数，如果存在映射代数，如果存在映射 f:B1B2，对任何对任何a,b B1，有有 f(a 1b)=f(a)2f(b)f(a 1b)=f(a)2f(b)f()=则称则称f是是到到 的同态映射。的同态映射。与格同构比较，多了一个关于补运算的同构关系等与格同构比较，多了一个关于补运算的同构关系等式。式。为了引出有限布尔代数的为了引出有限布尔代数的stone 的定理，下面介绍原子的定理，下面介绍原子的概念。的概念。f(a)现在学习的是第33页，共84页2.原子原子 定义定义1:设设设设布尔代数布尔代数,元素元素a B,a0,对任对任何元素何元素

33、x B,有有x a=a,或或 x a=0,则称则称a是原子。是原子。定义定义2:是布尔格是布尔格,在在的的哈斯图中称盖住全哈斯图中称盖住全下界下界0的元素为原子。的元素为原子。例如：例如：1。e。0。d。f。b。c。a。0。1。01a b现在学习的是第34页，共84页 下面先介绍原子的判定下面先介绍原子的判定定理定理7-3.1设设是布尔代数，是布尔代数，a B,且且a0,则则a是原子的充分且必要条件是是原子的充分且必要条件是 对任何对任何y B，如果，如果ya,则则y=0或或y=a。证明证明:必要性必要性.设设a 是原子是原子,且对任何且对任何y B，有，有ya(往证往证y=0或或y=a),由

34、原子定义得由原子定义得 y a=a,或或 y a=0,而由而由ya 得得 y a=y,所以有所以有y=0或或y=a.充分性充分性.已知已知对任何对任何y B，如果，如果ya,则则y=0或或y=a。(往证往证a是原子是原子,即证出对任何即证出对任何x B 有有x a=a,或或 x a=0),任取任取x B,令令y=x a,因因x aa,所以所以ya,由已知条由已知条件得件得 y=0 或或 y=a,所以有所以有 x a=a,或或 x a=0,所以所以a是原是原子子.现在学习的是第35页，共84页定理定理7-3.2 设设a,b是布尔代数是布尔代数中的原子中的原子，如果，如果ab,则则a b=0,(如

35、果如果a b0,则则 a=b)即即 不同两个原子的下确界为不同两个原子的下确界为0证明证明:设设a和和b是是B中原子中原子,(由原子定义得由原子定义得:对任何对任何x B 有有x a=a,或或 x a=0,)因为因为a是原子是原子,而而b B,所以所以b a=a b=a,或或b a=a b=0,于是于是:如果如果a b0,必有必有 a b=a .类似地类似地,b是原子是原子,而而a B,所以所以a b=b,或或 a b=0,于是于是:如果如果a b0,必有必有 a b=b,最后得最后得 a=b.所以得出所以得出,如果如果a b0,则则 a=b.等价的等价的 如果如果 ab,则则a b=0.现在

36、学习的是第36页，共84页定理定理7-3.3 设设a,b1,b2 bn是是 布尔代数布尔代数中的原中的原子子，则，则ab1 b2 bn的的充分且必要条件为充分且必要条件为 对于某个对于某个i(1in),有有a=bi.证明证明:充分性充分性显然成立显然成立,因为因为对于某个对于某个i(1in),有有a=bi.必有必有 ab1 b2 bn必要性必要性,已知已知 ab1 b2 bn,则则 a(b1 b2 bn)=a (a b1)(a b2)(a bn)=a如果每个如果每个(a bi)=0 (1in)则则(a b1)(a b2)(a bn)=0 这与这与a是原子矛盾是原子矛盾.所以至少有所以至少有某个

37、某个i (1in),使得使得(a bi)0 因为因为a和和 bi都是原子都是原子,由定理由定理7-3.2 得得 a=bi.现在学习的是第37页，共84页定理定理7-3.4 设设b是有限布尔代数是有限布尔代数中的中的 非非0元素，元素，则必存在原子则必存在原子a，使得使得ab.证明证明:1).如果如果b是原子是原子,则则 令令b=a,则则 ab.2).如果如果b不是原子不是原子,则必存在则必存在 b1 B 使得使得0 b1b,如果如果b1不是原子不是原子,则必存在则必存在 b2 B 使得使得 0b2 b1b,如此下去如此下去,由于由于B是有限集合是有限集合,上述过程经过有限步后而上述过程经过有限

38、步后而最终结束最终结束,最后得到原子最后得到原子bk,使得使得 0bk b2 b1b 令令 bk=a,于是于是ab.1。e。0。d。f。b。c。a。现在学习的是第38页，共84页定理定理7-3.5 有限布尔代数中，有限布尔代数中，b =0，当且仅当当且仅当 bc。例如右图中例如右图中,2 =0 26证明证明:充分性充分性.已知已知 bc又又 于是于是因为因为0是全下界是全下界,所以所以 b =0必要性必要性.已知已知b =0 (往证往证 bc,即即b c=c)b c=(b c)1=(b c)(c )=(b )c=0 c=c所以所以b c=c,即即bc30。3。1。2。5。10。15。6。现在学

39、习的是第39页，共84页定理定理7-3.6 设设是有限布尔代数，是有限布尔代数，b非非0元素，元素，a1,a2 ak是是B中满足中满足ajb的所有原子的所有原子(j=1,2,k),则则 ba1 a2 ak且除原子次序不同外，且除原子次序不同外，上述表达式是唯一的。上述表达式是唯一的。证明证明:(1)令令a1 a2 ak c(往证往证b=c 即证即证 bc且且cb)a).证证cb 显然成立显然成立,因为每个因为每个aib,(j=1,2,k)所以所以 a1 a2 akb 即即 cb.b).证证bc.(由定理由定理7-3.5可知可知,只要证出只要证出 b =0 即可即可)假设假设b 0,由定理由定理

40、7-3.4得得,必存在原子必存在原子a,使得使得a b ,而而b b b 由由的传递性得的传递性得ab,a .因为因为a是原子是原子,且且ab,b0,由题意由题意 a必是必是a1,a2,ak中之一中之一,于是于是 aa1 a2 ak 即即 ac,又又a ,得得 ac 所以所以a0，这，这与与a是原子矛盾是原子矛盾.所以只有所以只有b =0，所以所以bc。综上综上 b=ca1 a2 b ak.0 现在学习的是第40页，共84页即得即得 ba1 a2 ak .(2)证明上式是唯一的证明上式是唯一的.假设还有原子假设还有原子b1,b2,bm B,使得使得 bb1 b2 bm .(下面证下面证b1,b

41、2,bm=a1,a2,.,ak)a).任取任取bi b1,b2,bm,由由式得式得b1,b2,bm中每个中每个bjb(1jm),又又 ba1 a2 ak 所以所以 bib 即即 bi a1 a2 ak ,由于由于bi及每个及每个aj(1jk)都是原子都是原子,由定理由定理7-3.3得得,a1,a2,.,ak 中必存在一个中必存在一个aj,使得使得bi=aj 于是于是bi a1,a2,ak 所以所以b1,b2,bm a1,a2,.,ak类似可以证明类似可以证明 a1,a2,.,ak b1,b2,bm最后得最后得 b1,b2,bm=a1,a2,.,ak所以上述表达式在不考虑原子次序时所以上述表达式

42、在不考虑原子次序时,形式是唯一的形式是唯一的.现在学习的是第41页，共84页定理定理7-3.7 在布尔代数在布尔代数中中，对，对B中任何原子中任何原子a和任何非和任何非0元素元素b,ab和和a 两式中有且仅有一个成两式中有且仅有一个成立。立。证明证明:假设上述两个式子都成立假设上述两个式子都成立,即即ab和和a ,则有则有ab =0,这与这与 a是原子矛盾是原子矛盾.下面证明两个式中必有一个成立下面证明两个式中必有一个成立.因为因为a ba,而而a是原子是原子,所以只能有所以只能有a b=a 或或 a b=0如果如果a b=0,即即 ,由定理由定理7-3.5得得,a ,如果如果a b=a,则则

43、 ab.于是这于是这两个式中必有一个成立两个式中必有一个成立.现在学习的是第42页，共84页定理定理7-3.8(Stone定理定理)设设是有限布尔代数，是有限布尔代数，M是是B中所有原子构成的集合，则中所有原子构成的集合，则与与同构。同构。证明证明:构造映射构造映射 f:BP(M)对于对于x B 先通过下边例子了解映射先通过下边例子了解映射 f的形式的形式:f(x)=x=0 a|aM,ax x030。3。1。2。5。10。15。6。1 2 3 5 6 10 15 30 2 3 5 2,3 2,5 3,5 2,3,5B P(M)f现在学习的是第43页，共84页1).先证明先证明f是双射是双射.a

44、).证明证明f是入射是入射:只有只有x=0时时,才有才有 f(x)=.任取任取x1,x2 B,x10 x10且且x1x2,由定理由定理3-7.6得得,x1,x2可以写成如下形式可以写成如下形式:x1=a1 a2 ak 其中其中 ai x1 (1 i k)x2=b1 b2 bm 其中其中 bj x2 (1j m)因为每个非因为每个非0元素写成上述表达式的形式是唯一的元素写成上述表达式的形式是唯一的,又因又因为为x1x2,所以所以 a1,a2,.,akb1,b2,bm.由由f 定义得定义得f(x1)=a1,a2,.,ak f(x2)=b1,b2,bm 故故f(x1)f(x2)f入射入射.b).证明

45、证明f 满射满射:任取任取M1 P(M)如果如果M1为为,则则f(0)=M1,如果如果M1,令令M1=a1,a2,.,ak,由由的封闭性得的封闭性得,必存在必存在x B,使得使得a1 a2 ak=x,显然每个显然每个aix (1ik),故故f(x)=M1,所以所以f 是满射的是满射的.最后由最后由a)b)得得 f是双射的是双射的.现在学习的是第44页，共84页2).证明证明f满足三个同构关系式满足三个同构关系式.任取任取x1,x2 B,因为因为f是双射是双射,必有必有M1,M2 P(M),使得使得 f(x1)=M1,f(x2)=M2,a).证明证明f(x1 x2)=f(x1)f(x2)=M1M

46、2,令令f(x1 x2)=M3,即证明即证明 M3=M1M2 先证先证 M3 M1M2 如果如果 M3=显然有显然有 M3 M1M2 如果如果M3,任取任取a M3,由由f 定义得定义得ax1 x2,又因为又因为x1 x2x1,x1 x2x2,所以所以 ax1 ax2 由由f 定义得定义得a f(x1)a f(x2)即即 a M1 a M2,故故 a M1M2,所以所以 M3 M1M2现在学习的是第45页，共84页再证再证 M1M2 M3 如果如果 M1M2=显然有显然有 M1M2 M3 如果如果 M1M2,任取任取a M1M2 a M1 a M2所以所以 a是满足是满足ax1与与ax2的原子

47、的原子,ax1 x2 由由f 定义得定义得,a f(x1 x2),即即 a M3 所以所以 M1M2 M3 所以所以 M3=M1M2 即即 f(x1 x2)=f(x1)f(x2)现在学习的是第46页，共84页b).证明证明 f(x1 x2)=f(x1)f(x2)=M1 M2,令令f(x1 x2)=M4,即证明即证明 M4=M1 M2先证先证 M4 M1 M2 如果如果 M4=显然有显然有 M4 M1 M2 如果如果M4,任取任取a M4,由由f 定义得定义得ax1 x2,则必有则必有ax1,或者或者 ax2,(因为如果因为如果ax1与与ax2都不成立都不成立,由定理由定理7-3.7得得 必有必

48、有 与与a是原子矛盾是原子矛盾,所以所以ax1 或或 a x2)由由f 定义得定义得 a f(x1)即即a M1 或或a f(x2)即即 a M2所以所以a M1 M2,所以所以 M4 M1 M2现在学习的是第47页，共84页再证再证 M1 M2 M4 如果如果 M1 M2=显然有显然有 M1 M2 M4 如果如果 M1 M2,任取任取a M1 M2 a M1 或者或者 a M2如果如果a M1 则则 ax1 ax1x1 x2 a f(x1 x2),a M4 如果如果a M2 则则 ax2 ax2x1 x2 a f(x1 x2),a M4所以所以M1 M2 M4 M4=M1 M2与与ax2的原

49、子的原子,由由f 定义得定义得,即即 所以所以 M1M2 M4 所以所以 M4=M1M2 即即 f(x1 x2)=f(x1)f(x2)现在学习的是第48页，共84页3).证明证明于是有于是有 x1 x2=1 x1 x2=0 f(x1 x2)=M f(x1 x2)=f(x1 x2)=f(x1)f(x2)=M1 M2=M f(x1 x2)=f(x1)f(x2)=M1M2=所以所以 M2=M1 即即 由由1).2).3)得得 f(x1 x2)=f(x1)f(x2)f(x1 x2)=f(x1)f(x2)所以所以 与与同构。同构。现在学习的是第49页，共84页推论推论1.任何有限布尔代数的元素个数为任何

50、有限布尔代数的元素个数为2n (n=1,2,3,)因为因为|P(M)|=2n推论推论2.两个有限布尔代数同构的充分且必要条件是两个有限布尔代数同构的充分且必要条件是其其元素个数相同。元素个数相同。1。e。0。d。f。b。c。a。0。1。01a b现在学习的是第50页，共84页本节重点掌握本节重点掌握布尔代数的性质，同构概念，布尔代数的性质，同构概念，Stone定理及定理及其推论。其推论。作业作业 P260 （2）cbdaa,c,da,b,db,c,da,b,cb,ca,db,da,ca,b,c,dc,d a,b现在学习的是第51页，共84页7-4.布尔表达式 一一.布尔表达式概念布尔表达式概念