格与布尔代数课件.ppt

1、格与布尔代数 布尔代数是计算机逻辑设计的基础，它是由格引出的，布尔代数是计算机逻辑设计的基础，它是由格引出的，格又是从偏序集引出的。所以我们先格又是从偏序集引出的。所以我们先回顾回顾一下一下偏序集偏序集。是偏序集是偏序集:是是A上自反上自反,反对称和传递关系反对称和传递关系(偏序偏序).偏序集中的元素间的次序可以通过它的偏序集中的元素间的次序可以通过它的Hasse图反映出来图反映出来.例如例如A=1,2,3,6,12,24,36,是是A上上整除整除关系关系其其Hasse图如图所示，图如图所示，BA B1。12。24。36。1.B的极小元与极大元的极小元与极大元 y是是B的极小元的极小元yBx(

2、xBxy)y是是B的极大元的极大元yBx(xByx)例如例如2,3,6的极小元的极小元:2,3 极大元极大元:62.B的最小元与最大元的最小元与最大元 y是是B的最小元的最小元yBx(xByx)y是是B的最大元的最大元yBx(xBxy)2,3,6的最小元的最小元:无无 最大元最大元:6 B如果有最小元如果有最小元(最大元最大元),则是则是唯一唯一的。的。3.B的下界与上界的下界与上界 y是是B的下界的下界yAx(xByx)y是是B的上界的上界yAx(xBxy)2,3,6的下界的下界:1 上界上界:6,12,24,364.B的最大下界的最大下界(下确界下确界)与最小上界与最小上界(上确界上确界)

3、y是是B的最大下界的最大下界(下确界下确界)：B的所有下界的所有下界x,有有xy。y是是B的最小上界的最小上界(上确界上确界)：B的所有上界的所有上界x,有有yx。2,3,6下确界下确界:1 上确界上确界:6 (B若有下若有下(上上)确界确界,则则唯一唯一)2。12。24。36。1 格(Lattice)一一.基本概念基本概念1.格的定义格的定义 是偏序集，如果任何是偏序集，如果任何a,bA,使得使得a,b都有最大都有最大下界和最小上界，则称下界和最小上界，则称是是格格。右图三个偏序右图三个偏序集集,哪个是格？哪个是格？3。12。24。36。30。3。2。5。10。15。6。3。4。1。2。不是

4、格，不是格，因为因为24,36无最小上界。无最小上界。和和是格。再看下面三个偏序集，哪个是格？是格。再看下面三个偏序集，哪个是格？第一个与第三个第一个与第三个是同构的。因为是同构的。因为 d和和e无下界，也无无下界，也无最小上界；最小上界；b,c虽有下界，但无最大下界。虽有下界，但无最大下界。第二个图第二个图：2,3无最大下界，无最大下界，4,5无最小上界。无最小上界。这三个偏序集，都不是格，这三个偏序集，都不是格，2.平凡格平凡格：所有：所有全序全序都是格，称之为平凡格。都是格，称之为平凡格。因为全序中任何两个元素因为全序中任何两个元素x,y，要么要么xy,要么要么yx。如果如果xy，则则x

5、,y的最大下界为的最大下界为x，最小上界为最小上界为y。如果如果yx，则则x,y的最大下界为的最大下界为y，最小上界为最小上界为 x。即这即这x,y的最大下界为较小元素，最小上界为较大元素的最大下界为较小元素，最小上界为较大元素.4dab ce12 34 5 6dab c e3.由格诱导的代数系统由格诱导的代数系统设设是格是格,在在A上定义二元运算上定义二元运算和和为为:a,bAab=LUB a,b,a,b的最小上界的最小上界.Least Upper Boundab=GLB a,b,a,b的最大下界的最大下界.Greatest Lower Bound称称是由格是由格诱导的代数系统诱导的代数系统

6、.(-并并,-交交)例如右边的格中例如右边的格中ab=b ab=a bc=e5 e ab d cb a c fe gb a c fe g d a cb d4.子格子格：设：设是格是格,是由是由诱导的代数系统。诱导的代数系统。B是是A的非空子的非空子集，如果集，如果和和在在B上封闭，则称上封闭，则称是是的的子格子格。是是的的子格。而子格。而不是不是.因因bc=dB,(判定子格：看去掉的元素是否影响封闭判定子格：看去掉的元素是否影响封闭)二二.格的对偶原理格的对偶原理 设设是格，是格，的逆关系记作的逆关系记作，也是偏序关系。也是偏序关系。所以所以也是格，也是格，的的Hasse图是将图是将的的Has

7、se图颠倒图颠倒180即可。即可。格的对偶原理格的对偶原理：设：设P是对任何格都为真的命题，如果将是对任何格都为真的命题，如果将P中的中的换成换成，换成换成，换成换成，就得到命题，就得到命题P,称称P为为P的对偶命题，则的对偶命题，则P对任何格也是为真的命题。对任何格也是为真的命题。例如：例如：P:aba P:aba a,b的最大下界的最大下界a a,b的最小上界的最小上界a三三.格的性质格的性质 是由格是由格诱导的代数系统。诱导的代数系统。a,b,c,dA1.aab bab aba abb 此性质由运算此性质由运算和和的定义直接得证。的定义直接得证。62.如果如果ab，cd，则则 acbd，

8、acbd。证明证明：如果：如果ab，又又bbd,由传递性得由传递性得abd,类似由类似由cd，dbd，由传递性得由传递性得cbd,这说明这说明bd是是a,c的上界，而的上界，而ac是是a,c的最小上界，的最小上界，所以所以acbd。类似可证类似可证 acbd。推论推论：在一个格中，任何：在一个格中，任何 a,b,cA，如果，如果bc，则，则 abac，abac。此性质称为此性质称为格的保序性格的保序性。3.和和都满足都满足交换律交换律。即。即 ab=ba，ab=ba。此性质由运算此性质由运算和和的定义直接得证。的定义直接得证。74.和和都满足都满足幂等律幂等律。即。即 aa=a aa=a 证明

9、证明：由性质：由性质1 得得 aaa (再证再证aaa)由由自反得自反得aa,这说明这说明a是是a的上界，而的上界，而aa是是a的的最小上界，所以最小上界，所以 aa a。最后由最后由反对称得反对称得 aa=a。由对偶原理得由对偶原理得 aa=a 5.和和都满足都满足结合律结合律。即。即 (ab)c=a(bc)，(ab)c=a(bc)。证明证明：先证明先证明(ab)c a(bc)a a(bc)bbc a(bc)(ab)a(bc)cbc a(bc)(ab)c a(bc)同理可证同理可证 a(bc)(ab)c 最后由反对称得最后由反对称得(ab)c=a(bc)类似可证类似可证 (ab)c=a(bc

10、)。86.和和都满足都满足吸收律吸收律。即。即 a(ab)=a，a(ab)=a。证明证明：显然有显然有 aa(ab).再证再证 a(ab)a a a ab a a(ab)a最后由最后由反对称得反对称得 a(ab)=a，类似可证类似可证 a(ab)=a。7.是代数系统，如果是代数系统，如果和和是是满足吸收律满足吸收律的二的二元运算，则元运算，则和和必满足幂等律必满足幂等律。证明证明：任取：任取a,bA 和和是满足吸收律。是满足吸收律。有有 a(ab)=a-a(ab)=a-。由于上式中的由于上式中的b是任意的，可以令是任意的，可以令b=ab 并代入并代入式得式得 a(a(ab)=a 由式得由式得

11、aa=a 同理可证同理可证aa=a98.和和不不满足满足分配律分配律。但有分配。但有分配不等式不等式：a(bc)(ab)(ac)，(ab)(ac)a(bc)。我们我们先看先看右图的右图的例子例子：10 c ab e d d(be)=dc=d (db)(de)=ae=e de 即即 d(be)(db)(de)证明证明：aab aac a(ab)(ac)bcb ab bcc ac bc(ab)(ac)于是有于是有 a(bc)(ab)(ac)类似可证类似可证(ab)(ac)a(bc)。*9.ab ab=b ab=a证明证明：教材教材 P239 已证已证 ab ab=a 这里从略。这里从略。下面证明下

12、面证明 ab ab=b 先证先证ab ab=b 设设 ab，又，又bb ab b 又又 bab 由由反对称得反对称得 ab=b 再证再证 ab=b ab 已知已知 ab=b a ab ab。最后最后得得 ab ab=b 这是个很重要的定理，在以后用到此结论这是个很重要的定理，在以后用到此结论证明证明ab。11四.格的同态与同构1.定义定义：设：设 和和是两个格，由它们诱导是两个格，由它们诱导的代数系统分别是的代数系统分别是和和，如果存，如果存在映射在映射f:A1A2 使得对任何使得对任何a,bA1,f(a1b)=f(a)2f(b)f(a1b)=f(a)2f(b)则称则称f是是到到 的的同态映射

13、同态映射。也称也称是是 的的同态像同态像。如果如果 f 是双射的，就称是双射的，就称f是是到到，的格的格同构同构，也称格，也称格 和和同构同构。12例如例如,A=1,2,3,6,是是A上整除关系。上整除关系。,E=a,b它们诱导的代数系统分别是它们诱导的代数系统分别是和和。其中其中和和分别是求两个数的最小公倍数和最大公约数分别是求两个数的最小公倍数和最大公约数.13 ba a,b 1 32 6f6 3 2 1 aba,bA P(E)f(23)=f(6)=a,b f(2)f(3)=ab=a,b f(23)=f(1)=f(2)f(3)=ab=f(26)=f(6)=a,b f(2)f(6)=aa,b

14、=a,b f(26)=f(2)=a f(2)f(6)=aa,b=a可见它们同构。可见它们同构。格同构格同构，它们的，它们的图的形状一定相同图的形状一定相同。2.格同态的保序性格同态的保序性定理定理：设：设f是格是格 到到 的的同态同态映射，映射，则则对任对任何何a,bA1,如果如果a1b,则则 f(a)2f(b).证明证明：令令和和 是格是格 和和 诱导的代数系统，任取诱导的代数系统，任取a,bA1,设设a1b,则则 a1b=a f(a1b)=f(a)而而f(a1b)=f(a)2f(b)，所以，所以 f(a)2f(b)=f(a)，所以所以 f(a)2f(b).3.格同构的保序性格同构的保序性定

15、理定理：设：设双射双射f是格是格 到到 的的同构同构映射，映射，当且仅当当且仅当 对任何对任何a,bA1,若若 a1b f(a)2f(b).证明证明：令令和和 是格是格 和和 诱导的代数系统，诱导的代数系统，141).充分性充分性：已知，任取：已知，任取a,bA1,若若a1b f(a)2f(b).(应证出应证出 f(a1b)=f(a)2f(b)f(a1b)=f(a)2f(b)a)先先证证 f(a1b)=f(a)2f(b)令令a1b=c c1a,c1b,由已知得由已知得 f(c)2f(a)和和f(c)2f(b).所以所以 f(c)2f(a)2f(b)-再证再证 f(a)2f(b)2 f(c)：由

16、于由于f(a),f(b)A2,又又2的封闭性得的封闭性得 f(a)2f(b)A2,又由又由f:A1A2是满射，必有是满射，必有dA1,使得使得 f(d)=f(a)2f(b)所以所以 f(d)2f(a),f(d)2f(b).由已知条件得：由已知条件得：d1a,d1b d1a1b=c,d1c,于是得于是得 f(d)2f(c),即即f(a)2f(b)2 f(c)-由由得得 f(c)=f(a)2f(b)即即 f(a1b)=f(a)2f(b)。b)类似可证类似可证 f(a1b)=f(a)2f(b)所以所以 f是它们的同构映射是它们的同构映射.152).必要性必要性：已知：已知 f是格是格 到到 的的同构

17、同构映射，映射，（证出：任取（证出：任取a,bA1,若若a1b f(a)2f(b)）a)先证先证 a1b f(a)2f(b)任取任取a,bA1,设设a1b，由格同态保序性得，由格同态保序性得 f(a)2 f(b)b)再证再证f(a)2f(b)a1b 设设 f(a)2f(b)，f(a)=f(a)2f(b)=f(a1b)f 是入射，是入射，a=a1b 所以所以 a1b 由由a),b)最后得最后得 a1b f(a)2f(b)。定理证毕。定理证毕。由格的同构得如下结论：由格的同构得如下结论：具有具有一、二、三个元素一、二、三个元素的格分别同构于含有一、二、的格分别同构于含有一、二、三个元素的三个元素的

18、链链。16 a a b a b c 具有具有四个元素四个元素的格分别同构于下面两种格形式之一的格分别同构于下面两种格形式之一：17 d a b c d a b c e c d d a b c e a b c e a b d a e b c d d a b c e 具有具有五个元素五个元素的格分别同构于下面五种格形式之一：的格分别同构于下面五种格形式之一：作业作业 P242(1)(2)(4)(7)2 几个特殊格一一.分配格分配格 前面我们介绍一般的格，前面我们介绍一般的格，和和只满足分配不等式。只满足分配不等式。a(bc)(ab)(ac)，(ab)(ac)a(bc)。下面介绍的是满足分配律的格下

19、面介绍的是满足分配律的格-分配格。分配格。1.定义定义：是由格是由格诱导的代数系统。如果诱导的代数系统。如果对对a,b,cA，有，有 a(bc)=(ab)(ac)，a(bc)=(ab)(ac)则称则称是分配格。是分配格。例例 是分配格。是分配格。182.二个重要的五元素非分配格二个重要的五元素非分配格：2(35)=230=2(23)(25)=11=1 c(bd)=ca=c(cb)(cd)=ed=d可见它们都不是分配格。可见它们都不是分配格。3.分配格的判定分配格的判定：见书：见书 P245 一个格是分配格的一个格是分配格的充分且必要条件充分且必要条件是在该格中没有任是在该格中没有任何子格与上述

20、两个五元素非分配格之一同构。何子格与上述两个五元素非分配格之一同构。用此方法可以判定下面两个格不是分配格：用此方法可以判定下面两个格不是分配格：19 3 1 30 2 5 d e a b c 4 1 6 3 5 2 f g a d c e b4.分配格的性质分配格的性质1).定理定理 2.1.在格中，如果在格中，如果对对可分配，则可分配，则对对也也可分配。反之亦然。可分配。反之亦然。证明证明：设设是由格是由格诱导的代数系统。且诱导的代数系统。且对对可分配。任取可分配。任取a,b,cA，a(bc)=(ab)(ac)而而(ab)(ac)=(ab)a)(ab)c)(分配分配)=a(ab)c)=a(a

21、c)(bc)(吸收、分配吸收、分配)=(a(ac)(bc)(结合结合)=a(bc)(吸收吸收)同理可证同理可证:如果如果对对可分配，则可分配，则对对也可分配也可分配.2).定理定理 2.2.所有链均为分配格。所有链均为分配格。证明证明：显然任何链都不会含有与五元素非分配格之一同：显然任何链都不会含有与五元素非分配格之一同构的子格，所以链必是分配格。构的子格，所以链必是分配格。203).定理定理 2.3.设设是分配格，对任何是分配格，对任何a,b,cA,如果如果有有 ab=ac 及及 ab=ac 则必有则必有 b=c.证明证明：任取：任取a,b,cA,设有设有 ab=ac 及及 ab=ac b=

22、b(ab)(吸收律吸收律)=b(ac)(代换代换)=(ba)(bc)(分配分配)=(ab)(bc)(交换交换)=(ac)(bc)(代换代换)=(ab)c (分配分配)=(ac)c (代换代换)=c (吸收律吸收律)21二.有界格1.格的全上界与全下界格的全上界与全下界1).全上界全上界:设设是格，如果存在元素是格，如果存在元素aA对任何对任何xA,xa,则称则称 a是格的全上界是格的全上界,记作记作1。(即是即是A的最大元的最大元)定理定理 2.4 一个格如果有全上界，则是唯一的。一个格如果有全上界，则是唯一的。(我们已证明过，如果有最大元，则是唯一的我们已证明过，如果有最大元，则是唯一的)2

23、).全下界全下界:设设是格，如果存在元素是格，如果存在元素aA对任何对任何xA,ax,则称则称 a是格的全下界是格的全下界,记作记作0。(即是即是A的最小元的最小元)定理定理 2.5 一个格如果有全下界，则是唯一的。一个格如果有全下界，则是唯一的。从格的图形看从格的图形看：全上界：全上界1，就是图的最上边元素，就是图的最上边元素(只一个只一个).全下界全下界0，就是图的最下边元素，就是图的最下边元素(只一个只一个)。22 b 0 1 a c 1 c 02.有界格定义有界格定义：如果一个格存在：如果一个格存在全上界全上界1与全下界与全下界0，则，则称此格为有界格。称此格为有界格。设设是是有界有界

24、格，则对任何格，则对任何aA,有有 因为因为a1,a1=a a1=1 0a a0=0 a0=a由此看出：对于由此看出：对于 来说来说 1是么元，是么元，0是零元。是零元。对于对于 来说来说 0是么元，是么元，1是零元。是零元。思考题思考题：是否所有格都是是否所有格都是有界格？有界格？所有有限个元素的格都是有界格。所有有限个元素的格都是有界格。而无限个元素的格可能是无界格。而无限个元素的格可能是无界格。例如例如就是既无全上界也无全下界。就是既无全上界也无全下界。23三.有补格回顾回顾：集合的补集，：集合的补集，若若 AB=E AB=则则 A=B，B=A 如如E=a,b E=E a=b,b=a1.

25、元素的补元元素的补元：设设是个有界格，是个有界格，aA,如果存在如果存在 bA,使得使得 ab=1 ab=0 则称则称a与与b互为补元。互为补元。例例：右边的格中：右边的格中 a的补元：的补元：c,e b的补元：的补元：无无 c的补元：的补元：a,d d的补元：的补元：c e的补元：的补元：a 0 的补元：的补元：1 1的补元：的补元：024 a,b a b e 0 1 b c d a2.有补格的定义有补格的定义：一个有界格中，如果每个元素都有补元，则称之为有一个有界格中，如果每个元素都有补元，则称之为有补格。补格。下述有界格中，哪些是有补格？下述有界格中，哪些是有补格？25 a,b a b

26、b 0 1 a c e 0 1 b c d a 1 c 0(1)(2)(3)(4)上述有补格中，有些元素的补元不唯一，如上述有补格中，有些元素的补元不唯一，如(2)中的中的b,那么什么样的有补格元素的补元唯一呢？那么什么样的有补格元素的补元唯一呢？就是就是有界分配格有界分配格.请看下面定理：请看下面定理：定理定理 2.6 在有界分配格中，如果元素有补元，则补元在有界分配格中，如果元素有补元，则补元是唯一的。是唯一的。证明证明：设：设是是有界分配格，任取有界分配格，任取aA,假设假设a有两个有两个补元补元b和和c，则则 ab=0 ab=1 ac=0 ac=1于是有，于是有，ab=ac ab=ac

27、由分配格的定理由分配格的定理 2.3得得 b=c a的的补元是唯一的。补元是唯一的。四四.布尔格布尔格 如果一个格既是分配格又是有补格，则称之为如果一个格既是分配格又是有补格，则称之为布尔格布尔格。26a布尔格中每个元素都有唯一补元布尔格中每个元素都有唯一补元，元素，元素a的补元记作的补元记作 。显然显然是布尔格。是布尔格。下面介绍由布尔格诱导的代数系统布尔代数。下面介绍由布尔格诱导的代数系统布尔代数。作业作业 P248 (2)(5)P252(1)(3)(6)3 布尔代数 Boolean Algebra一一.定义定义 由由布尔格布尔格诱导的代数系统诱导的代数系统称之称之 为布尔代数。其中为布尔

28、代数。其中 是是“取补元取补元”运算。运算。如果如果B是有限集合，则称它是有限布尔代数。是有限集合，则称它是有限布尔代数。例如例如：令：令BF,T，表示合取，表示合取，表示析取，表示析取，表示否定表示否定,就是个布尔代数。就是个布尔代数。如上图所示。如上图所示。27 T F a,b a b 也是个布尔代数。也是个布尔代数。如右图所示。如右图所示。二二.布尔代数的性质布尔代数的性质设设布尔代数布尔代数,任意任意x,y,zB,有有交换律交换律 xy=yx xy=yx结合律结合律 x(yz)=(xy)z x(yz)=(xy)z 幂等律幂等律 xx=x xx=x 吸收律吸收律 x(xy)=x x(xy

29、)=x分配律分配律 x(yz)=(xy)(xz)x(yz)=(xy)(xz)同一律同一律 x0=x x1=x 零律零律 x1=1 x0=0 28xx互补律互补律 x =1 x =0 xx 对合律对合律yxyxyxyx底摩根定律底摩根定律上述性质都可以由格，分配格上述性质都可以由格，分配格,有界格，布尔格得到。下有界格，布尔格得到。下面只证明面只证明底摩根定律。底摩根定律。29yxyxyxyx的补元是yxyx所以所以，类似可证另一个。，类似可证另一个。分配)()()()(yyxxyxyxyx交换、结合)()(yyxxxy结合、互补)1()(xxxy1111)1(y分配)()()()(yxyyxx

30、yxyx)()(xyyyxx)()0(xyyy)0(0 x000三三.布尔代数的同构布尔代数的同构1.定义定义：令：令和和 是两个布尔是两个布尔代数，如果存在双射代数，如果存在双射f:B1B2,对任何对任何a,bB1,有有 f(a1b)=f(a)2f(b)f(a1b)=f(a)2f(b)30af(a)f()=则称则称f是是到到 的同构映射。的同构映射。与格同构比较，多了一个关于补运算的同构关系等式。与格同构比较，多了一个关于补运算的同构关系等式。为了引出有限布尔代数的元素个数的定理，下面介绍为了引出有限布尔代数的元素个数的定理，下面介绍原子原子的概念。的概念。2.原子原子 定义定义1:设设是布

31、尔代数是布尔代数,元素元素aB,a0,对对任何元素任何元素xB,有有xa=a,或或 xa=0,则称则称a是原子。是原子。定义定义2:是布尔格是布尔格,在在的的哈斯图中称盖住全哈斯图中称盖住全下界下界0的元素为原子。的元素为原子。例如例如：311。e。0。d。f。b。c。a。0。1。01a b原子的判定：原子的判定：定理定理 3.1设设是布尔代数，是布尔代数，aB,且且a0,则则a是原子的充分且必要条件是是原子的充分且必要条件是 对任何对任何yB，如果，如果ya,则则y=0或或y=a。证明证明:必要性必要性.设设a 是原子是原子,且对任何且对任何yB，有，有ya(证出证出y=0或或y=a),由原

32、子定义得由原子定义得 ya=a,或或 ya=0,而由而由ya 得得 ya=y,所以有所以有y=0或或y=a.充分性充分性.已知已知对任何对任何yB，如果，如果ya,则则y=0或或y=a。(证出证出a是原子是原子,即证出对任何即证出对任何xB 有有xa=a,或或 xa=0,),任取任取xB,令令y=xa,因因xaa,所以所以ya,由已知条由已知条件得件得 y=0 或或 y=a,即有即有 xa=a,或或 xa=0,所以所以a是原子是原子.32定理定理 3.2 设设a,b是布尔代数是布尔代数中的原子中的原子，如果，如果ab,则则ab=0,(如果如果ab0,则则 a=b)证明证明:设设a和和b是是B中

33、原子中原子,(由原子定义得由原子定义得:对任何对任何xB 有有xa=a,或或 xa=0,)因为因为a是原子，而是原子，而bB，所以，所以 ba=ab=a，或者或者 ba=ab=0,于是于是:如果如果ab0，必有，必有 ab=a 。类似地，类似地，b是原子是原子,而而aB,所以所以ab=b,或或 ab=0,此结论等价于此结论等价于:如果如果ab0,必有必有 ab=b,最后得最后得 a=b.所以得出所以得出,如果如果ab0,则则 a=b.或者得出，或者得出，如果如果 ab,则则ab=0.33定理定理 3.3 设设a,b1,b2 bn是是 布尔代数布尔代数中的原中的原子子，则，则ab1b2bn的充分

34、且必要条件为的充分且必要条件为 对于某个对于某个i(1in),有有a=bi.证明证明:充分性充分性显然成立显然成立,因为因为对于某个对于某个i(1in)，有有a=bi,必有必有 ab1b2bn必要性必要性,已知已知 ab1b2bn,则则 a(b1b2bn)=a (a b1)(a b2)(a bn)=a 如果每个如果每个(a bi)=0 (1in)则则 (a b1)(a b2)(a bn)=0 于是得于是得a=0,这与这与a是原子矛盾。所以至少有某个是原子矛盾。所以至少有某个i (1in),使得使得(a bi)0，因为因为a和和 bi都是原子都是原子,由定理由定理 7.2 得得 a=bi.34定

35、理定理 3.4 设设b是有限布尔代数是有限布尔代数中的中的 非非0元素元素,则必存在原子则必存在原子a，使得使得ab.证明证明:1).如果如果b是原子是原子,则则 令令b=a,则则 ab.2).如果如果b不是原子不是原子,则必存在则必存在 b1B 使得使得0 b1b,如果如果b1不是原子不是原子,则必存在则必存在 b2B 使得使得 0b2 b1b,如此下去如此下去,由于由于B是有限集合是有限集合,上述过程经过有限步后而上述过程经过有限步后而最终结束最终结束,最后得到原子最后得到原子bk,使得使得 0bk b2 b1b 令令 bk=a,于是于是ab.例如例如，右图中每个，右图中每个非非0元素元素

36、x，都存在原子都存在原子a，使得使得ax.351。e。0。d。f。b。c。a。3630。3。1。2。5。10。15。6。cccb0cbc定理定理 3.5 有限布尔代数中，有限布尔代数中，b =0，当且仅当当且仅当 bc。56 例如例如 右图中右图中,62 =1(全下界全下界0)26cc 又又 于是于是c因为因为0是全下界是全下界,所以所以 b =0c必要性必要性.已知已知 b =0 (证出证出bc,即即bc=c)ccbc=(bc)1=(bc)(c )=(b )c证明证明:充分性充分性.已知已知 bc=0c=c所以所以bc=c,即即bc定理定理 3.6 设设是有限布尔代数，是有限布尔代数，b非非

37、0元素，元素，a1,a2 ak是是B中满足中满足ajb的所有原子的所有原子(j=1,2,k),则则 ba1a2 ak且除原子次序不同外，且除原子次序不同外，上述表达式是唯一的。上述表达式是唯一的。37a1a2b ak.0cb).证证bc.(由定理由定理 4.5可知可知,只要证出只要证出 b =0 即可即可)c假设假设b 0,由定理由定理 3.4得得,必存在原子必存在原子a,使得使得cccca b ,而而b b b 由由的传递性得的传递性得cab,a .因为因为a是原子是原子,且且ab,b0,由题意得由题意得a必是必是a1,a2,ak中之一中之一,由定理由定理 3.3得得aa1a2ak 即即cc

38、ac；又又a ,得得 ac 所以所以a0 与与a是原子矛盾是原子矛盾.c所以必有所以必有b =0 所以所以 bc。最后得最后得 b=c证明证明:(1)令令a1a2ak c(证出证出b=c 即证即证 bc且且cb)a).证证cb 显然成立显然成立,因为每个因为每个aib,(j=1,2,k)所以所以 a1a2akb 即即 cb.即得即得 ba1a2 ak .(2)证明上式是唯一的证明上式是唯一的.假设还有原子假设还有原子b1,b2,bmB,使得使得 bb1b2 bm .(下面证下面证b1,b2,bm=a1,a2,.,ak)a).任取任取bib1,b2,bm,由由式得式得b1,b2,bm中每个中每个

39、bj有有bjb(1jm),所以所以bib，又又 ba1a2 ak所以所以 bi a1a2 ak ,由于由于bi及每个及每个aj(1jk)都是原子都是原子,由定理由定理 3.3得得,a1,a2,.,ak 中必存在一个中必存在一个aj,使得使得bi=aj 于是于是bia1,a2,ak 所以所以b1,b2,bm a1,a2,.,akb).类似可以证明类似可以证明 a1,a2,.,ak b1,b2,bm最后得最后得 b1,b2,bm=a1,a2,.,ak所以上述表达式在不考虑原子次序时所以上述表达式在不考虑原子次序时,形式是唯一的形式是唯一的.38定理定理 3.7 在布尔代数在布尔代数中中，对，对B中

40、任何原子中任何原子a 39b和任何非和任何非0元素元素b,ab和和a 两式中有且仅有一个成立。两式中有且仅有一个成立。b证明证明:假设上述两个式子都成立假设上述两个式子都成立,即即ab和和a ,则有则有bab =0,这与这与 a是原子矛盾是原子矛盾.下面证明两个式中必有一个成立下面证明两个式中必有一个成立.因为因为aba,而而a是原子是原子,所以只能有所以只能有ab=a 或或 ab=0b0ba如果如果ab=0,即即 ,由定理由定理 3.5得得,a ,如果如果ab=a,则则 ab.于是这于是这两个式中必有一个成立两个式中必有一个成立.定理定理 3.8(Stone钻石钻石定理定理)设设是有限布尔代

41、数是有限布尔代数,M是是B中所有原子构成的集合，则中所有原子构成的集合，则与与同构。同构。证明证明:构造映射构造映射 f:BP(M)对于对于xB 40f(x)=x=0 a|aM,ax x030。3。1。2。5。10。15。6。123561015302352,32,53,52,3,5B P(M)f先通过下边先通过下边例子例子了解映射了解映射 f的形式的形式:1).先证明先证明f是双射是双射.a).证明证明f是入射是入射:只有只有x=0时时,才有才有 f(0)=.任取任取x1,x2B,x10 x20且且x1x2,由定理由定理3-7.6得得,x1,x2可以写成如下形式可以写成如下形式:x1=a1a2

42、ak 其中原子其中原子ai x1 (1 i k)x2=b1b2bm 其中原子其中原子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).证明证明f 满射满射:任取任取M1P(M)如果如果M1为为,则则f(0)=M1,如果如果M1,令令M1=a1,a2,.,ak,由由的封闭性得的封闭性得,必存在必存在xB,使得使得a1a2ak=x,显然每个显然

43、每个aix (1ik),故故f(x)=M1,所以所以f 是满射的是满射的.最后由最后由a)b)得得 f是双射的是双射的.412).证明证明f满足三个同构关系式满足三个同构关系式.任取任取x1,x2B,因为因为f是双射是双射,必有必有M1,M2P(M),使得使得 f(x1)=M1,f(x2)=M2,a).证明证明f(x1x2)=f(x1)f(x2)=M1M2,令令f(x1x2)=M3,即证明即证明 M3=M1M2 先证先证 M3 M1M2 如果如果 M3=显然有显然有 M3 M1M2 如果如果M3,任取任取aM3,即即 af(x1x2)由由f 定义得定义得ax1x2,又因为又因为x1x2x1,x

44、1x2x2,所以所以 ax1 ax2 由由f 定义得定义得af(x1)af(x2)即即 aM1 aM2,故故 aM1M2,所以所以 M3 M1M242再证再证 M1M2 M3 如果如果 M1M2=显然有显然有 M1M2 M3 如果如果 M1M2,任取任取aM1M2 aM1 aM2即即 af(x1),af(x2)，于是，于是 a是满足是满足ax1与与ax2的原子的原子,所以所以 ax1x2，由由f 定义得定义得,af(x1x2),即即 aM3 故故 M1M2 M3。所以所以 M3=M1M2 即即 f(x1 x2)=f(x1)f(x2)43b).证明证明 f(x1 x2)=f(x1)f(x2)=M

45、1M2,令令f(x1x2)=M4,即证明即证明 M4=M1M2先证先证 M4 M1M2 如果如果 M4=显然有显然有 M4 M1M2 如果如果M4,任取任取aM4,af(x1x2)由由f 定义得定义得ax1x2,则必有则必有 ax1,或者或者 ax2,(因为如果因为如果ax1与与ax2都不成立都不成立,由定理由定理 3.7得得 必有必有 440)()(2121212121xxxxaxxxxaxaxa所以及与与a是原子矛盾是原子矛盾,所以有所以有 ax1 或或 a x2)由由f 定义得定义得 af(x1)即即aM1 或或af(x2)即即 aM2于是有于是有 aM1 M2,所以所以 M4 M1M2

46、再证再证 M1M2 M4 如果如果 M1M2=显然有显然有 M1M2 M4 如果如果 M1M2,任取任取aM1M2 aM1 或者或者 aM2如果如果aM1 则则 ax1 ax1x1x2 af(x1x2),aM4 如果如果aM2 则则 ax2 ax2x1x2 af(x1x2),aM4所以所以M1M2 M4 最后得最后得 M4=M1M2即即 f(x1 x2)=f(x1)f(x2)4546221112111)()()()(MxfMxfxxBxxfxf且令)()(11xfxf3).证明证明于是有于是有 x1x2=1 x1x2=0 f(x1x2)=M f(x1x2)=f(x1x2)=f(x1)f(x2)

47、=M1M2=M f(x1x2)=f(x1)f(x2)=M1M2=)()(11xfxf所以所以 M2=M1 即即 综上所述综上所述 由由1).2).3)得得 f(x1x2)=f(x1)f(x2)f(x1x2)=f(x1)f(x2)所以所以 与与同构。同构。推论推论1.任何有限布尔代数的元素个数为任何有限布尔代数的元素个数为2n (n=1,2,3,)因为因为|P(M)|=2n 其中其中|M|=n推论推论2.两个有限布尔代数同构的充分且必要条件是元素两个有限布尔代数同构的充分且必要条件是元素个数相同。个数相同。471。e。0。d。f。b。c。a。0。1。01a b48cbdaa,c,da,b,db,

48、c,da,b,cb,ca,db,da,ca,b,c,dc,d a,b本节重点掌握本节重点掌握布尔代数的性质，同构概念，布尔代数的性质，同构概念，Stone定理及定理及其推论。其推论。作业作业 P260 （2）4.布尔表达式 此内容在开关理论，逻辑设计中有着广泛的应用。此内容在开关理论，逻辑设计中有着广泛的应用。一一.布尔表达式概念布尔表达式概念1.定义定义：设设是布尔代数，其上的布尔表达式是布尔代数，其上的布尔表达式递归定义如下：递归定义如下：1)B中任何元素是个布尔表达式。中任何元素是个布尔表达式。2)任何变元任何变元x是个布尔表达式是个布尔表达式.49E13)如果如果E1,E2是个布尔表达

49、式是个布尔表达式,则则 ,(E1E2),(E1E2)也也是布尔表达式。是布尔表达式。4)有限次地应用规则有限次地应用规则1)-3),得到的符号串都是布尔表达式得到的符号串都是布尔表达式.xb(x1 )2x例如令例如令B=0,1,a,b (a ),(xy),*表达式的最外层括号可以省略表达式的最外层括号可以省略.2.对布尔表达式赋值对布尔表达式赋值：设：设是布尔代数，含有是布尔代数，含有变元变元 x1,x2 xn 的布尔表达式记作的布尔表达式记作E(x1,x2,xn),对变元对变元 x1,x2,xn分别用分别用B中元素代替的过程，称之为对布尔表中元素代替的过程，称之为对布尔表达式赋值。达式赋值。

50、例如例如 B=0,1,a,b 50 01a b(a )baa_a E(a,b)=b 一个一个的布尔表达式的布尔表达式E(x1,x2,xn),经过赋值以后，就得到经过赋值以后，就得到一个值一个值(即是即是B中一个元素中一个元素)。3.两个布尔表达式相等两个布尔表达式相等:设设是布尔代数，含有是布尔代数，含有变元变元 x1,x2,xn 的两个布尔表达式的两个布尔表达式E1(x1,x2,xn)和和E2(x1,x2,xn),如果不论对变元如果不论对变元x1,x2 xn分别用分别用B中任何元素赋值中任何元素赋值,都使得都使得E1和和E2的值相同的值相同,则称这两个表达式相等则称这两个表达式相等,记作记作