离散数学-格与布尔代数ppt课件.ppt

第七章 格与布尔代数 布尔代数是计算机逻辑设计的基础，它是由格引出的，布尔代数是计算机逻辑设计的基础，它是由格引出的，格又是从偏序集引出的。所以我们先格又是从偏序集引出的。所以我们先回顾回顾一下一下偏序集偏序集。是偏序集是偏序集:是是A上自反上自反,反对称和传递关系反对称和传递关系(偏序).偏序集中的元素间的次序可以通过它的偏序集中的元素间的次序可以通过它的Hasse图反映出来图反映出来. 例如例如A=1,2,3,6,12,24,36, 是是A上上的的整除整除关系关系其其Hasse图如图所示，图如图所示，B A B1.B的极小元与极大元的极小元与极大元 y是是B的极小元的极小元yBx(xBxy)y是是B的极大元的极大元yBx(xByx)例如例如2,3,6的极小元的极小元:2,3 极大元极大元:6。12。24。36。2.B的最小元与最大元的最小元与最大元 y是是B的最小元的最小元yB x(xByx) y是是B的最大元的最大元yB x(xBxy) 2,3,6的最小元的最小元:无无 最大元最大元: 6B如果有最小元如果有最小元(最大元最大元), 则是则是唯一唯一的。的。3.B的下界与上界的下界与上界y是是B的下界的下界yA x(xByx)y是是B的上界的上界yA x(xBxy) 2,3,6的下界的下界:1 上界上界: 6,12,24,364.B的最大下界的最大下界(下确界下确界)与最小上界与最小上界(上确界上确界)y是是B的最大下界的最大下界(下确界下确界)：B的所有下界的所有下界x,有有xy。y是是B的最小上界的最小上界(上确界上确界)：B的所有上界的所有上界x,有有yx。2,3,6下确界下确界:1 上确界上确界:6 (B若有下若有下(上上)确界，则确界，则唯一唯一)。12。24。36。7-1 格 (Lattice)一一 . . 基本概念基本概念1. 格的定义格的定义 是偏序集，如果任何是偏序集，如果任何a,bA,使得使得a,b都有最大都有最大下界和最小上界，则称下界和最小上界，则称是格。是格。 右图的三个偏右图的三个偏序集，序集，不是格，不是格，因为因为24,36无无最小上界。最小上界。是格。是格。12。24。36。30。3。2。5。10。5。6。3。4。1。2。这三个偏序集，也都不是格，第一个与第三个是同构的。这三个偏序集，也都不是格，第一个与第三个是同构的。因为因为 d和和e无下界，也无最小上界；无下界，也无最小上界；b,c虽有下界，但无虽有下界，但无最大下界。最大下界。 2,3无最大下界，无最大下界，4,5无最小上界。无最小上界。2. 平凡格平凡格：所有全序都是格，称之为平凡格。：所有全序都是格，称之为平凡格。 因为全序中任何两个元素因为全序中任何两个元素x,y，要么，要么xy, 要么要么yx。如果如果xy，则，则x,y的最大下界为的最大下界为x，最小上界为，最小上界为y。如果如果yx，则，则x,y的最大下界为的最大下界为y，最小上界为，最小上界为 x 。即这即这x,y的最大下界为较小元素，最小上界为较大元素的最大下界为较小元素，最小上界为较大元素. dab ce12 34 5 6dab c e3. 由格诱导的代数系统由格诱导的代数系统设设是格是格,在在A上定义二元运算上定义二元运算和和为为: a,bA ab=LUB a,b a,b的最小上界的最小上界.Least Upper Bound ab=GLB a,b a,b的最大下界的最大下界.Greatest Lower Bound称称是由格是由格诱导的代数系统诱导的代数系统. (-并并,-交交) 例如右边的格中例如右边的格中ab=b ab=a bc=e4. 子格子格：设：设是格是格, 是是由由诱导的代数系统。诱导的代数系统。B是是A的的非空子集，如果非空子集，如果和和在在B上封闭，则上封闭，则称称是是的子格。的子格。是是的子格。的子格。而而不是不是. bc=d B, (运算规则要从格运算规则要从格中找中找) e ab d cb a c fe gb a c fe g d a cb d二二. . 格的对偶原理格的对偶原理 设设是格，是格，的逆关系记作的逆关系记作，也是偏序关系。也是偏序关系。也是格，也是格，的的Hasse图是将图是将的的Hasse图图颠倒颠倒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 此性质由运算此性质由运算和和的定义直接得证。的定义直接得证。 2.如果如果ab，cd，则，则 acbd，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 此性质由运算此性质由运算和和的定义直接得证。的定义直接得证。4. 和和都满足幂等律。都满足幂等律。即即 aa=a aa=a 证明证明：由性质：由性质1, aaa (再证再证aaa) 又由又由自反有自反有aa，这说明这说明a是是a的上界，的上界，而而aa是是a的最小上界的最小上界，所以所以 aa a。 最后由最后由反对称得反对称得 aa=a 。 由对偶原理得由对偶原理得 aa=a5. 和和都满足结合律。即都满足结合律。即 (ab)c =a(bc)，(ab)c =a(bc) 证明证明：先证明先证明(ab)c a(bc) 因因 a a(bc) ， bbc a(bc) 所以所以 aba(bc) 又又 cbc a(bc) 于是有于是有 (ab)c a(bc) 再再证证 a(bc)(ab)c 因因aab (ab)c； 再由再由bab(ab)c， c (ab)c 所以所以 bc (ab)c于是有于是有 a(bc)(ab)c最后由最后由反对称得反对称得 (ab)c = a(bc) 类似可证类似可证 (ab)c =a(bc) 。6. 和和都满足都满足吸收律吸收律。即。即 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(bc) (ab)(ac) ， (ab)(ac) a(bc) 。我们我们先看先看右图的右图的例子例子： 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) 。由对偶原理得由对偶原理得 a(bc) (ab)(ac) 。 即即 (ab)(ac) a(bc) 。 c ab e d8. ab ab=b ab=a证明证明：先先证明证明ab ab=a 先证先证ab ab=a 由由 ab，又，又aa 所以所以aab 又由又由ab的定义有的定义有aba 由反对称得由反对称得 ab=a 再证再证 ab=a ab 由由 ab=a 则则 a=ab b。 综上综上得得 ab ab=b 下面证明下面证明ab ab=b 先证先证ab ab=b 由由 ab，又，又bb 所以所以 ab b 又因为又因为 bab 由反对称得由反对称得 ab=b 再证再证 ab=b ab 由由 ab=b 因因 a ab 所以所以 ab。 综上综上得得 ab ab=b 引理： 是代数系统，如果是代数系统，如果和和是是满足满足吸收律吸收律的二元运算，则的二元运算，则和和必满足幂等律必满足幂等律。证明证明：任取：任取a,bA 因为因为 和和满足吸收律。满足吸收律。于是有于是有 a( ab) =a - a(ab) =a -。由于上式中的由于上式中的b是任意的，可以令是任意的，可以令b=ab 并代入并代入式得式得 a(a(ab) =a 由由式得式得 aa=a同理可证同理可证aa=a定理：定理： 设设是代数系统，如果是代数系统，如果和和是是满足满足交换律，结合律，和吸收律交换律，结合律，和吸收律的二元运算，的二元运算，则则A上存在上存在偏序关系偏序关系 ，使，使是一个格，并且该格所诱导是一个格，并且该格所诱导的代数系统恰好是的代数系统恰好是。（由代数系统得到格）（由代数系统得到格）证明：设在证明：设在A上定义二元关系上定义二元关系 为：为：对任意对任意a,bA, a b 当且仅当当且仅当 ab=a（1）先证二元关系）先证二元关系 是一个偏序关系是一个偏序关系（2 2）再证再证ab 是是 a,b 的下确界的下确界（3）然后证）然后证a b是是 a,b 的上确界的上确界见书上见书上238页页四.格的同态与同构1.定义定义：设：设 和和是两个格，由它们诱导是两个格，由它们诱导的代数系统分别是的代数系统分别是和和 ，如果存，如果存在映射在映射 f:A1A2 ，使得对任何使得对任何a,bA1，有，有 f(a1b)=f(a)2f(b) f(a1b)=f(a)2f(b)则称则称f是是到到 的同态映射。的同态映射。也称也称是是 的同态像。的同态像。如果如果 f 是双射的，就称是双射的，就称f是是到到 ，的格同构，的格同构，也称格也称格 和和同构。同构。例：例：，A=1,2,3,6, 是是A上整除关系。上整除关系。 ，E=a,b它们诱导的代数系统分别是它们诱导的代数系统分别是和和其中其中和和分别分别是求两个数的最小公倍数和最大公约数是求两个数的最小公倍数和最大公约数. 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=a,b f(26)=f(2)=a f(2)f(6)=aa,b=a 可见它们同构。可见它们同构。格同构，它们的哈斯图的形状一定相同。格同构，它们的哈斯图的形状一定相同。 ba a,b 1 32 6f6 3 2 1 aba,bA P(E) 具有具有1、2、3个元素的格分别同构于含有一、二、三个元素的格分别同构于含有一、二、三 个个元素的链。元素的链。具有具有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 c2. 格同态的保序性格同态的保序性定理：设定理：设f是格是格 到到 的的同态同态映射，则对任映射，则对任何何a,bA1，如果如果a1b，则，则 f(a)2f(b)。证明：证明：令令和和 是格是格 和和 诱导的代数系统，任取诱导的代数系统，任取a,bA1，设设a1b， 则则 a1b=a f(a1b)=f(a) 即即 f(a)2f(b)=f(a) 而而 f(a)2f(b) 2f(b) 所以所以 f(a)2f(b).3. 格同构的保序性格同构的保序性定理：设两个定理：设两个格格为为和和 ，f是是A1到到A2的双射，的双射，则则f是是 到到的格同构，当且仅当的格同构，当且仅当 对任意对任意a,bA1，a1b f (a)2f(b)证明证明：令令和和 是格是格 和和 诱导的代数系统，诱导的代数系统，1) 必要性必要性：已知：已知 f是格是格 到到 的的同构同构映射，映射，（往证：任取（往证：任取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 最后得最后得 a1b f (a)2f(b) 。2) 充分性充分性：已知，对任意：已知，对任意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) ： 由于由于f(a),f(b)A2 , 又又2封闭封闭，得得 f(a)2f(b)A2 , 又由又由f:A1A2是双射，必有是双射，必有dA1, 使得使得 f(a)2f(b)=f(d)所以所以 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(a)2f(b)=f(c) ，即即 f(a1b)=f(a)2f(b) 。b)类似可证类似可证 f(a1b)=f(a)2f(b)，所以，所以 f是它们的同构映射是它们的同构映射。7-2 几个特殊格一一. . 分配格分配格 前面我们介绍一般的格，前面我们介绍一般的格，和和只满足分配不等式。只满足分配不等式。 a(bc) (ab)(ac) ， (ab)(ac) a(bc) 。下面介绍的是满足分配律的格下面介绍的是满足分配律的格-分配格。分配格。1. 定义定义： 是由格是由格诱导的代数系统。如果诱导的代数系统。如果对对 a,b,cA，有，有 a(bc) =(ab)(ac) ， a(bc)= (ab)(ac)则称则称是是分配格。分配格。例：例： 所诱导的代数系统为所诱导的代数系统为 所以所以是是分配格。分配格。2. 二个重要的五元素非分配格二个重要的五元素非分配格： 2(35)=230=2(23)(25)=11=1 c(bd)=ca=c(cb)(cd)=ed=d可见它们都不是分配格。可见它们都不是分配格。3.分配格的判定分配格的判定： 一个格是分配格的一个格是分配格的充分且必要条件充分且必要条件是在该格中没有任何是在该格中没有任何子格与上述两个五元素非分配格之一同构。子格与上述两个五元素非分配格之一同构。用此方法可以判定下面两个格不是分配格：用此方法可以判定下面两个格不是分配格： 3 1 30 2 5 d e a b c 4 1 6 3 5 2 f g a d c e b4. 分配格的性质分配格的性质1. 在一个格中，如果在一个格中，如果对对可分配，则可分配，则对对也可也可分配。反之亦然。分配。反之亦然。证明证明：设设是由格是由格诱导的代数系统诱导的代数系统，且且对对可分配。则任取可分配。则任取 a,b,cA， (ab)(ac) = (ab)a)(ab)c) 分配分配=a(ab)c)=a(ac)(bc) 吸收、分配吸收、分配 = (a(ac)(bc) 结合结合= a(bc) 即即对对也可分配也可分配 同理可证同理可证: 如果如果对对可分配，则可分配，则对对也可分配也可分配.2. 所有链均为所有链均为分配格。分配格。证明证明：显然任何链：显然任何链都不会含有都不会含有与与那两个五元素非分配格那两个五元素非分配格之之一同构的子格，所以链必是分配格。一同构的子格，所以链必是分配格。3. 设设是分配格，对任何是分配格，对任何a,b,cA，如果，如果有有 ab=ac 及及 ab=ac 则必有则必有 b=c 。证明证明：任取：任取a,b,cA, 设有设有 ab=ac 及及 ab=ac b=b(ab) (吸收律吸收律) =b(ac) (代换代换) =(ba)(bc) (分配分配) =(ab)(bc) (交换交换) =(ac)(bc) (代换代换) = (ab)c (分配分配) = (ac)c (代换代换) =c (吸收律吸收律)二. 有界格1. 格的全上界与全下界格的全上界与全下界1).全上界全上界:设设是格，如果存在元素是格，如果存在元素aA对任何对任何xA, xa，则称，则称 a是是格的全上界格的全上界，记作记作1。(即是即是A的最大元的最大元)定理定理7-2.4 一个格如果有全上界，则是唯一的。一个格如果有全上界，则是唯一的。 (我们已证明过，最大元如果有，则是唯一的我们已证明过，最大元如果有，则是唯一的)2).全下界全下界:设设是格，如果存在元素是格，如果存在元素aA对任何对任何xA, ax, 则称则称 a是是格的全下界格的全下界,记作记作0。(即是即是A的最小元的最小元)定理定理7-2.5 一个格如果有全下界，则是唯一的。一个格如果有全下界，则是唯一的。从格的图形看：全上界从格的图形看：全上界1，就是图的最上边元素，就是图的最上边元素(只一个只一个)，全下界全下界0，就是图的最下边元素，就是图的最下边元素(只一个只一个)。 b 0 1 a c 1 c 02. 有界格定义有界格定义：如果一个格存在：如果一个格存在全上界全上界1与全下界与全下界0，则，则称此格为有界格。称此格为有界格。设设是是有界有界格，则对任何格，则对任何aA, 有有 因为因为a1, 所以所以 a1=a a1=1 0a 所以所以 a0=0 a0=a 是否所有格都是是否所有格都是有界格？有界格？ 所有有限个元素的格都是有界格，所有有限个元素的格都是有界格， 而无限个元素的格可能是无界格。例如而无限个元素的格可能是无界格。例如就既无全上就既无全上界界也无也无全下界。全下界。 三. 有补格 回顾：集合的补集，回顾：集合的补集，若若 AB=E AB= 则则 A=B，B=A如如E=a,b E= =E a=b, b=a1. 元素的补元元素的补元： 设设是个有界格，是个有界格，aA, 如果存在如果存在 bA，使得使得 ab=1 且且 ab=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 a2. 有补格的定义有补格的定义： 一个有界格中，如果每个元素都有补元，则称之为有一个有界格中，如果每个元素都有补元，则称之为有补格。补格。上述有界格中，哪些是有补格？上述有界格中，哪些是有补格？上述有补格中，有些元素的补元不唯一，如上述有补格中，有些元素的补元不唯一，如(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) 定理定理72.6 在有界分配格中，如果元素有补元，则补元在有界分配格中，如果元素有补元，则补元是唯一的。是唯一的。证明：设证明：设是是有界分配格，任取有界分配格，任取aA，假设假设a有两个有两个补元补元b和和c，则，则 ab=0 ab=1 ac=0 ac=1于是有于是有 ab= ac 及及 ab=ac由分配格的性质由分配格的性质3得得 b=c ，所以，所以a的的补元是唯一的。补元是唯一的。四四. . 布尔格布尔格 如果一个格既是分配格又是有补格，则称之为布尔格。如果一个格既是分配格又是有补格，则称之为布尔格。布尔格中每个元素都有唯一补元，元素布尔格中每个元素都有唯一补元，元素 a 的补元记作的补元记作 。显然显然是布尔格。是布尔格。下面介绍由布尔格诱导的代数系统布尔代数。下面介绍由布尔格诱导的代数系统布尔代数。a73 布尔代数布尔代数 Boolean Algebra一一. 定义定义 由布尔格由布尔格诱导的代数系统诱导的代数系统称之为布尔称之为布尔代数。其中代数。其中 是取补元运算。是取补元运算。 如果如果A是有限集合，则称它是有限布尔代数。是有限集合，则称它是有限布尔代数。例如例如：令：令BF,T，表示合取，表示合取，表示析取，表示析取， 表示表示否定，否定， 就是个就是个由右面格所诱导的由右面格所诱导的布尔代数。布尔代数。 E=a,b, 也是个也是个由右面格所诱导的由右面格所诱导的布尔代数。布尔代数。 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)=x分配律分配律 x(yz)=(xy)(xz) x(yz)=(xy)(xz)同一律同一律 x0=x x1=x 零律零律 x1=1 x0=0 互补律互补律 x =1 x =0 对合律对合律底摩根定律底摩根定律xx xxyxyxyxyx上述性质都可以由格，分配上述性质都可以由格，分配格，有界格，布尔格得到。格，有界格，布尔格得到。下面只证明下面只证明底摩根定律。底摩根定律。所以所以 。类似可证另一个。类似可证另一个。yxyxyxyx000)0(0)()0()()()()()()(1111) 1() 1()()()()()()()(xxyyyxyyyxxyxyyxxyxyxyxxxyyyxxxyyyxxyxyxyx的补元是yxyx三三. 布尔代数的同构布尔代数的同构1. 定义定义：令：令和和 是两是两个布尔代数，如果存在映射个布尔代数，如果存在映射 f:B1B2，对任何对任何a,bB1 ，有有 f(a1b) = f(a)2f(b) f(a1b) = f(a)2f(b) f( ) =则称则称f是是到到 的同态映射。的同态映射。 与格同构比较，多了一个关于补运算的同构关系等与格同构比较，多了一个关于补运算的同构关系等式。式。 为了引出有限布尔代数的为了引出有限布尔代数的stone 的定理，下面介绍的定理，下面介绍原子的概念。原子的概念。af(a)2. 原子原子 定义定义1: 设设设设布尔代数布尔代数, 元素元素aB, a0, 对任何元素对任何元素xB, 有有xa=a, 或或 xa=0, 则则称称a是原子。是原子。 定义定义2:是布尔格是布尔格,在在的哈斯图中称盖的哈斯图中称盖住全下界住全下界0的元素为原子。的元素为原子。例如：例如：1。e。0。d。f。b。c。a。0。1。 01a b 下面先介绍原子的判定下面先介绍原子的判定定理定理7-3.1设设是布尔代数，是布尔代数，aB,且且a0,则则a是原子的充分且必要条件是是原子的充分且必要条件是 对任何对任何yB，如果，如果ya, 则则y=0或或y=a。证明证明:必要性必要性.设设a 是原子是原子, 且对任何且对任何yB，有，有ya (往证往证y=0或或y=a), 由原子定义得由原子定义得 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是原是原子子. 定理定理7-3.2 设设a,b是布尔代数是布尔代数中的原子中的原子，如果，如果ab, 则则ab=0, (如果如果ab0, 则则 a=b) 即即 不同两个原子的下确界为不同两个原子的下确界为0证明证明:设设a和和b是是B中原子中原子, (由原子定义得由原子定义得: 对任何对任何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 . 定理定理7-3.3 设设a,b1,b2 bn是是 布尔代数布尔代数中的原中的原子子，则，则ab1b2bn的的充分且必要条件为充分且必要条件为 对于某个对于某个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是原子矛盾是原子矛盾.所以至少有所以至少有某个某个i (1in), 使得使得(a bi)0 因为因为a和和 bi都是原子都是原子, 由定理由定理7-3.2 得得 a=bi.定理定理7-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.1。e。0。d。f。b。c。a。定理定理7-3.5 有限布尔代数中，有限布尔代数中，b =0，当且仅当，当且仅当 bc。例如右图中例如右图中, 2 =0 26证明证明: 充分性充分性.已知已知 bc又又 于是于是因为因为0是全下界是全下界, 所以所以 b =0必要性必要性. 已知已知b =0 (往证往证 bc, 即即bc=c)bc=(bc)1=(bc)( c )=(b )c =0c=c所以所以bc=c, 即即bcc30。3。1。2。5。10。15。6。56 6cc ccccb0cbccc定理定理7-3.6 设设是有限布尔代数，是有限布尔代数，b非非0元素，元素，a1,a2 ak是是B中满足中满足ajb的所有原子的所有原子(j=1,2,k), 则则 ba1a2 ak且除原子次序不同外，且除原子次序不同外，上述表达式是唯一的。上述表达式是唯一的。 证明证明:(1)令令a1a2ak c (往证往证b=c 即证即证 bc且且cb) a).证证cb 显然成立显然成立, 因为每个因为每个aib, (j=1,2,k) 所以所以 a1a2akb 即即 cb . b).证证bc.(由定理由定理7-3.5可知可知, 只要证出只要证出 b =0 即可即可)假设假设b 0 , 由定理由定理7-3.4得得, 必存在原子必存在原子a, 使得使得a b , 而而b b b 由由的传递性得的传递性得ab, a . 因为因为a是原子是原子, 且且ab, b0, 由题意由题意 a必是必是a1,a2 , ak中之一中之一, 于是于是 aa1a2ak 即即 ac, 又又a , 得得 ac 所以所以a0，这，这与与a是原子矛盾是原子矛盾.所以只有所以只有b =0 ， 所以所以bc 。 综上综上 b=cccccccca1 a2 b ak.0 ccc即得即得 ba1a2 ak .(2)证明上式是唯一的证明上式是唯一的.假设还有原子假设还有原子b1,b2 , bmB,使得使得 bb1b2 bm . (下面证下面证b1,b2,bm=a1,a2,.,ak)a). 任取任取bib1,b2,bm , 由由式得式得b1,b2,bm中每个中每个bjb (1jm) ,又又 ba1a2 ak 所以所以 bib 即即 bi a1a2 ak ,由于由于bi及每个及每个aj (1jk)都是原子都是原子, 由定理由定理7-3.3得得, a1,a2,.,ak 中必存在一个中必存在一个aj ,使得使得bi =aj 于是于是bia1,a2,ak 所以所以b1,b2,bm a1,a2,.,ak类似可以证明类似可以证明 a1,a2,.,ak b1,b2,bm最后得最后得 b1,b2,bm=a1,a2,.,ak所以上述表达式在不考虑原子次序时所以上述表达式在不考虑原子次序时, 形式是唯一的形式是唯一的.定理定理7-3.7 在布尔代数在布尔代数中，对中，对B中任何中任何原子原子a和任何非和任何非0元素元素b, ab和和a 两式中有且仅两式中有且仅有一个成立。有一个成立。证明证明:假设上述两个式子都成立假设上述两个式子都成立, 即即ab和和a , 则则有有ab =0 , 这与这与 a是原子矛盾是原子矛盾.下面证明两个式中必有一个成立下面证明两个式中必有一个成立. 因为因为aba , 而而a是原子是原子, 所以只能有所以只能有ab=a 或或 ab=0如果如果ab=0 , 即即 , 由定理由定理7-3.5得得, a ,如果如果ab=a , 则则 ab. 于是这于是这两个式中必有一个成立两个式中必有一个成立. bbbb0ba定理定理7-3.8 (Stone定理定理)设设是有限布尔代数，是有限布尔代数，M是是B中所有原子构成的集合，则中所有原子构成的集合，则与与同构。同构。证明证明:构造映射构造映射 f: BP(M) 对于对于xB 先通过下边例子了解映射先通过下边例子了解映射 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) f1).先证明先证明f是双射是双射. a).证明证明f是入射是入射: 只有只有x=0时时, 才有才有 f(x)=. 任取任取x1, x2B, x10 x10且且x1x2 , 由定理由定理3-7.6得得, x1, x2可以写成如下形式可以写成如下形式: x1= a1a2ak 其中其中 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, 显然每个显然每个aix (1ik) ,故故f(x)= M1, 所以所以f 是满射的是满射的. 最后由最后由a)b)得得 f是双射的是双射的.2).证明证明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, 由由f 定义得定义得ax1x2 ,又因为又因为x1x2x1, x1x2x2 , 所以所以 ax1 ax2 由由f 定义得定义得af(x1) af(x2) 即即 aM1 aM2 , 故故 aM1M2, 所以所以 M3 M1M2再证再证 M1M2 M3 如果如果 M1M2= 显然有显然有 M1M2 M3 如果如果 M1M2, 任取任取aM1M2 aM1 aM2所以所以 a是满足是满足ax1与与ax2的原子的原子, ax1x2 由由f 定义得定义得,af(x1x2), 即即 aM3 所以所以 M1M2 M3 所以所以 M3 = M1M2 即即 f(x1 x2 )=f(x1)f(x2) b).证明证明 f(x1 x2 )=f(x1)f(x2)=M1M2, 令令f(x1x2 )=M4 , 即证明即证明 M4 = M1M2先证先证 M4 M1M2 如果如果 M4 = 显然有显然有 M4 M1M2 如果如果M4, 任取任取aM4, 由由f 定义得定义得ax1x2 ,则必有则必有ax1, 或者或者 ax2 , (因为如果因为如果ax1与与ax2都不成立都不成立, 由定理由定理7-3.7得得 必有必有 与与a是原子矛盾是原子矛盾, 所以所以ax1 或或 a x2)由由f 定义得定义得 af(x1) 即即aM1 或或af(x2) 即即 aM2所以所以aM1 M2, 所以所以 M4 M1M20)()(2121212121xxxxaxxxxaxaxa所以及再证再证 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与与ax2的原子的原子, 由由f 定义得定义得,即即 所以所以 M1M2 M4 所以所以 M4 = M1M2 即即 f(x1 x2 )=f(x1)f(x2)3).证明证明于是有于是有 x1x2=1 x1x2=0 f(x1x2)=M f(x1x2)= f(x1x2)=f(x1)f(x2)= M1M2 =M f(x1x2)=f(x1)f(x2)= M1M2 =所以所以 M2 =M1 即即 由由1).2).3)得得 f(x1x2 )=f(x1)f(x2) f(x1x2)=f(x1)f(x2)所以所以 与与同构。同构。221112111)()()()(MxfMxfxxBxxfxf且令)()(11xfxf)()(11xfxf推论推论1. 任何有限布尔代数的元素个数为任何有限布尔代数的元素个数为2n (n=1,2,3,) 因为因为|P(M)|= 2n推论推论2. 两个有限布尔代数同构的充分且必要条件是两个有限布尔代数同构的充分且必要条件是其其元素个数相同。元素个数相同。1。e。0。d。f。b。c。a。0。1。 01a b本节重点掌握本节重点掌握布尔代数的性质，同构概念，布尔代数的性质，同构概念，Stone定理及定理及其推论。其推论。 作业作业 P260 （2） cbdaa,c,da,b,db,c,da,b,cb,ca,db,da,ca,b,c,dc,d a,b7-4.布尔表达式 一一. . 布尔表达式概念布尔表