离散数学第五章格与布尔代数(2)

1、1西安交通大学西安交通大学电子与信息工程学院电子与信息工程学院计算机软件所计算机软件所刘国荣刘国荣2离散数学 第五章第五章 格与布尔代数格与布尔代数 1.格格 2.布尔代数布尔代数 3离散数学 2.布尔代数布尔代数 布尔代数的定义布尔代数的定义 布尔代数的性质布尔代数的性质 布尔代数中的宏运算布尔代数中的宏运算 有限有限布尔代数的原子表示布尔代数的原子表示 布尔函数与布尔表达式布尔函数与布尔表达式 布尔环与布尔代数布尔环与布尔代数4离散数学 2. 布尔代数布尔代数定义定义1.布尔代数(Boolean algebra) 有补的分配格(B, , , , , 0, 1) 称为布尔代数。注：布尔代数(

2、B, , , , , 0, 1)简记为B； 若0=1，则B称为退化的布尔代数。以后，我们不讨论此种情况，因此，今后，我们假定总有|B|2； 例例1.集合代数(2X, , , , , X ) 是布尔代数 已知集合代数(2X, , , , , X ) 是有补的分配格(本章1例10和例20)，因此是布尔代数。注：当X=a时， 2X=, X ，集合代数的一个特例是5离散数学(, X , , , , , X ) ，其运算表如下：它当然也是一个布尔代数。例例2.开关代数开关代数 (switching algebra) (S, , , , 0, 1) 是布尔代数这里：S=0,1，00, 01, 11,其运算

3、表如下：表1 A A X X AB ABAB X XX XXX X X6离散数学通过变元代换，显见表2与表1是完全相同的。即，令 h:S 2X , h (0)= , h (1)= X (这里：X=a) 则易证h是一个双射的同态函数。因此开关代数(S, , , , 0, 1)与集合代数(2X, , , , , X ) 是同构的(这里X=a)，所以开关代数(S, , , , 0, 1)是一个布尔代数。 x yx yx y00 0 001 0 110 0 111 1 1 x 0 1 1 0表2x xx7离散数学例例3.命题代数( , , , , , F, T) 是布尔代数 这里： =F,T，F F,

4、 F T, T T,其运算表如下：通过变元代换，显见表3与表1是完全相同的。即，令 h: 2X , h (F)= , h (T)= X(这里 X=a) PQPQ P QFF F FFT FTTF FTTT TT P P F T T F表38离散数学则易证h是一个双射的同态函数。因此，命题代数( , , , , , F, T)与集合代数(2X, , , , , X ) 是同构的(这里X=a) ，所以命题代数( , , , , , F, T)是一个布尔代数。 注：利用 ，在命题逻辑中可定义逻辑推论(蕴涵)关系( )。即 (或 ) v(v) (v) 有限布尔代数有限布尔代数：对于布尔代数(B, ,

5、, , , 0, 1)，若nN，使|B|=n ，则称其为有限布尔代数；集合代数(, X , , , , , X )、开关代数(S, , , , 0, 1) 、命题代数( , , , , , F, T)都是有限布尔代数；例例4.n元集合代数(2X, , , , , X ) 是有限布尔代数 这里：X=a1, a2, an,因此， |X|=n， |2X|=2n 。9离散数学 显然，有限集合代数是有限布尔代数。 n元集合代数是有限集合代数，因此是有限布尔代数。 例例5.n元(维)开关代数(Sn, , , , 0, 1)是有限布尔代数这里：Sn=(x1, x2, , xn)：xiS(1i n)= Sn

6、(其中S=0,1)， 0 = (0,0, ,0)，1 = (1,1, ,1)，并且x,ySn ，x = (x1, x2, , xn) ， y = (y1, y2, , yn) x yi(1i n)(xi yi) x y = (x1 y1, x2 y2, , xn yn) x y = (x1 y1, x2 y2, , xn yn) = ( , , , )即n元开关代数的序关系、运算、最小元和最大元的定义都归结为一元开关代数(S, , , , 0, 1) 。x1x2xnx10离散数学现在我们来证：(Sn, , , , 0, 1) (2X, , , , , X ) 这里：X=a1, a2, , an

7、，即n元开关代数与n元集合代数是同构的。从而由n元集合代数是有限布尔代数(例4)，可知n元开关代数(Sn, , , , , 0, 1)也是有限布尔代数。令：h: Sn 2X , xSn ，x = (x1, x2, , xn) ，h(x)=A2X (或AX )这里：A=ai：ai X xi =1(1i n)因此 aih(x) aiA xi =1 (1i n) 。 下面我们证明h是一同构函数： 为此，我们总设 x, ySn ， h(x)=A， h(y)=B明显地 x = (x1, x2, , xn) ， y = (y1, y2, , yn) 11离散数学 显然有h (0)= , h (1)= X

8、；(1)先证h是双射函数 h是单射函数 h(x)= h(y) A=B aiA aiB (1i n) xi =1 yi =1 (1i n) xi = yi (1i n) x= y ； h是满射函数 A2X (即AX )，我们构造 x = (x1, x2, , xn)Sn ，使得12离散数学 即 xi =1 aiA (1i n) 因此aih(x) (1i n) xi =1 (1i n) aiA (1i n)所以 h(x) = A ；(2)次证h满足同态公式h(x y)= h(x) h(y) 因为aih(x y) (1i n) xi yi =1 (1i n) xi =1 yi =1 (1i n) a

9、iA aiB (1i n)1 (01niAaAaxiii 时当时当13离散数学 aiA B (1i n) aih(x) h(y) (1i n)所以 h(x y)= h(x) h(y) ； h(x y)= h(x) h(y)仿可证； h( )=h(x) 因此aih( ) (1i n) =1 (1i n) xi = 0 (1i n) aiA (1i n) aiA (1i n) aih(x) (1i n)所以 h( ) =h(x) ；xxixx14离散数学(3)最后证h满足保序性即x y h(x) h(y)因为 aih(x) (1i n) aiA (1i n) xi =1 (1i n) yi =1

10、(1i n) (x yi(1i n)(xi yi) aiB (1i n) aih(y) (1i n)所以 h(x) h(y) ；例例6. n元命题代数(n, , , , , F, T) 是有限布尔代数 这里：n=(P1, P2, , Pn)：Pi (1i n)= n 15离散数学(其中 =F,T)， F = (F,F, ,F)，T = (T,T, ,T)，并且P,Qn ，P = (P1, P2, , Pn) ，Q = (Q1, Q2, , Qn) P Q i(1i n)(Pi Qi) P Q = (P1 Q1, P2 Q2, , Pn Qn) P Q = (P1 Q1, P2 Q2, , Pn

11、 Qn) P = (P1 , P2 , , Pn)即n元命题代数的序关系、运算、最小元和最大元的定义都归结为一元命题代数( , , , , , F, T) 。仿例5我们易证： (n, , , , , F, T) (2X, , , , , X ) 这里：X=a1, a2, , an，即n元命题代数与n元集合代数是同构的。从而由n元集合代数是有限布尔代数(例4)，可知n元命题代数(n, , , , , F, T)也是有限布尔代数。16离散数学定理定理1.(反身律)设( B , , , , , 0,1 )是布尔代数。则xB ，(x)=x。证. xB ，x x = 0 = (x) x (互补律)x x

12、 = 1 = (x) x (互补律) x = (x) (根据上节定理10：分配格有消去律) (x)=x (等号的对称性) 定理定理2.(消去律之二)设( B , , , , , 0,1 )是布尔代数。则x , y , zB ，x y = x zx y = x z 。zy 17离散数学证. x, y, zB ， y = 0 y (因 0 y) =(x x) y (互补律) =(x y) (x y) (分配律) =(x z) (x z) (条件x y =x z和x y =x z) =(x x) z (分配律) = 0 z (互补律) = z (因 0 z )所以，消去率之二在布尔代数中成立。定理定

13、理3.(消去律之三)设( B , , , , , 0,1 )是布尔代数。则x , y , zB ，x y = x zx y = x z 。zy 18离散数学证. 仿定理2可证。对偶原理对偶原理(duality principle): 设(B , , , , , 0 , 1) 是布尔代数， 是 的逆关系。则 (1)在布尔代数(B , , , , , 0 , 1)中实行：将 换成 ；将 换成 ；将 换成 ； 将 0 换成 1 ；将 1 换成 0 ； 得到的(B, , , , , 1 , 0)仍是一布尔代数； (2)若T是原布尔代数中某个已经证明的定理，那么在定理T的条件和结论中实行：将 换成 ；将

14、 换成 ；将 换成 ；将 0 换成 1 ；将 1 换成 0 ；由此所得到的新的定理T在原布尔代数中仍然成立。19离散数学证.布尔代数中的对偶原理实质上来源于两个二元运算 和 所具有的结合律、交换律、幂等律、吸收律、分配律的对称性，半序关系 和其逆关系 的对称性；最小元0和最大元1的对称性；以及任何元素x与其补元x的对称性。注：布尔代数(B, , , , ,1 , 0)称为原布尔代数 (B , , , , , 0 , 1)的对偶布尔代数。实际上，它们互为对偶；定理T称为原定理T的对偶定理。实际上，它们互为对偶；定理定理4.(de Morgan律)设(B , , , , , 0 , 1)是布尔代数

15、。则x , y , zB ， (1) (x y) = x y ； (2) (x y) = x y 。20离散数学证.根据对偶原理的(2) ，只须证(1) 即可： x , y , zB ，由于 (x y) (x y) = (x y ) x) (x y ) y) (分配律) = (x x) y) (x ( y y) (结合律、交换律) =(0 y) (x 0)(互补律) = 0 0 (因 0 x及0 y) = 0 (因自反性 0 0 ) 及 (x y) (x y) = (x (x y) ( y (x y) (分配律) = (x x) y) (x (y y) (结合律、交换律) = (1 y) (x

16、 1) (互补律) = 1 1 (因 x 1及y 1) = 1 (因自反性 1 1 )21离散数学所以，(x y) = x y。定理定理5.设(B , , , , , 0 , 1)是布尔代数。则x , yB ，以下四条等价 (1) x y ( x y = x x y = y (1定理4 ) ) ； (2) y x ( x y = y x y = x (1定理4 ) ) ； (3) x y = 0 ； (4) x y = 1 。证.采用环形证法。即(1)(2)(3)(4)(1) (1)(2)： x y = (x y) (de Morgan律) = y (因 (1) x y) y x (1定理4

17、) 22离散数学 (2)(3)： x y = x (x y) (因 (2) y x ) = (x x) y (结合律) = 0 y (互补律) = 0 (因 0 y ) (3)(4)： x y= (x y) 0 (因 0 x y )= (x y) (x y) (因(3) x y = 0 )= (x y) x)(x y) y) (分配律)= (x x) y) (x (y y) (结合律、交换律)23离散数学= (1 y) (x 1) (互补律)= 1 1 (因 x 1及y 1)= 1 (因自反性 1 1 ) (4)(1)： x y = (x y) 0 (因 0 x y )= (x y) (x x

18、) (互补律) = x (y x) (分配律) = x (x y) (交换律) = x 1 (因(4) x y = 1 ) = x (因 x 1 ) x y (1定理4 ) 证明完毕。24离散数学定义定义2.宏运算(macro operation) 在布尔代数(B, , , , , 0, 1)中可定义如下的宏运算： x , yB (1) xy= x y ；(差运算) (2) x+y= (xy ) (yx )= (x y ) (y x ) ；(对称差)(3) xy= (x y ) (y x ) ； (对称积)注：这些宏运算与第一章集合代数中的宏运算是对应的概念；因而也有如下有关宏运算的定理。定理

19、定理6.设(B , , , , , 0 , 1)是布尔代数。则x , y , zB 25离散数学 (1) x= 1x ； (2) x y x y = 0 ； (3) x y = (xy ) y ； (4) y x (xy ) y = x ； (5) xy = x x y = 0 ； (6) (xy ) z = (x z )(y z ) 。证.只证(1) ,(3) ,(5) (1) x= 1 x (因 x 1及定理5(1) ) = 1x (3) x y = (x y) 1 (因 x y 1及定理5(1) = (x y) (y y ) (互补律) = (x y) (y y) (交换律)26离散数学

20、 =(x y ) y (分配律) =(xy ) y (5) xy = x x y = x x y (定理5(1) ) x (y ) = 0 (定理5(3) ) x y = 0 (反身律)定理定理7.设(B , , , , , 0 , 1)是布尔代数。则x , y , zB (1) x+ y = y + x ； (2) x = y x+ y = 0 ；27离散数学 (3) x+ y = (x y) (x y ) = (x y) (x y) ； (4) x y = (x + y) (x y) ； (5) (x+ y )+ z = x + (y + z) 。证.只证(2) ,(4) (2) x =

21、y (x y)(y x) (自反性及反对称性) (x y = 0) (y x = 0) (定理5(3) )x+ y = (x y ) (y x ) = 0 0 = 0 (因自反性 0 0及定理5(1)(4) x y = (x y) 1 (因 x y 1 及定理5(1)= (x y) (x y) (x y) (互补律) 28离散数学= (x y) (x y) (x y) (x y) (分配律)=(x y)(x y) (x y) (因 x y x y 及定理5(1) = (x + y) (x y) (由本定理(3) 定理定理8.设(B , , , , , 0 , 1)是布尔代数。则x , y ,

22、zB (1) x y = y x ； (2) x y = x y ； (3) x y = (x + y) ； (4) x x = 1 ； (5) x y = x + y = x + y ； (6) x y = x y = x + y ； (7) (x y) z= x (y z) ；29离散数学 (8) x 1 = x + 0 = x ； (9) x 0 = x + 1 = x ； (10)x = y x y = 1 。证.只证(3) ,(6) ,(9) (3) x y = (x y ) (y x ) = (x y ) (y x ) (de Morgan律及反身律等)=(x + y)(6) x

23、y = x (y ) (由本定理(2)= x y (反身律)=(x+ y) (由本定理(3)30离散数学= (x y ) (y (x)= (x y ) (y x) (反身律)= (x y) (x y ) (交换律)= (x y ) (x y) (de Morgan律及反身律)= (x y) (x y ) (交换律)= x + y (定理7(3) )(9) x 0=x 1 (1= 0 )= x + 1 (由本定理(6)=(x1) (1x )= (x 1) x (定理6(1)= (x 0) x (1= 0 )31离散数学= 0 x (因 0 x 及定理5(1) = x (因 0 x 及定理5(1)

24、 有限集合代数是有限布尔代数(例4)；有限布尔代数是否是有限集合代数呢？下面的斯笃(stone)定理回答了这个问题，答案是肯定的；这就为我们利用熟悉、简单的有限集合代数来研究、简化有限布尔代数奠定了理论基础。定义定义3.原子(atom) 设(B, , , , , 0, 1)是布尔代数。 a是B 的一个原子 aBa 0 (xB)(a x =0 a x = a) aBa 0 (xB)(x0 a x =0 a x) 。 32离散数学注：令 S=a：aB a是原子称S为B的原子集；定义中a 0 说明原子a不能是最小元；定义中后一等价式说明：任一非零元(x0)，要么与原子不可比较(a x =0 )，要么

25、比原子大(a x)。例例7. a0a6a2a7a4a5a3a1图3图图a0a1a2a3a0a133离散数学 在图1中，a0是最小元， a1是原子， a1是最大元 ； 在图2中，a0是最小元， a2 , a3是原子， a1是最大元 ； 在图3中，a0是最小元， a2 , a3 , a4是原子， a1是最大元； 定理定理9.设(B, , , , , 0, 1)是布尔代数，并且aB 。 a是B 的一个原子 a是0的一个直接后继；即a是B 的一个原子 0 a a 0 (xB)(0 x x a x=0 x=a) 。证.先证)： 已知a 0 (原子的定义) ； 显然0 a (0是B的最小元及aB) ； (

26、xB)(0 x x a x=0 x=a) 34离散数学 对于任何元素xB ， 0 x x a a x = x (本节定理5(1)及x a) x=0 x=a (a是原子，故 a x =0 a x = a) 由可知， a是0的直接后继； 次证)： 已知aB ； 已知a 0 (a是0的直接后继) ； (xB)(a x =0 a x = a) (采用二分法) ； 对于任何元素xB ，分情况论证如下：(甲)x与a可比较： ()x=0 ，则有a x = 0 (本节定理5(1)及 0 a) 35离散数学 ()x0 (a)x a 0 x x a (0是B的最小元及x0 ) x=a (a是0的直接后继) a x

27、 = a (幂等律) (b)a x，则有a x =a (本节定理5(1)(乙)x与a不可比较： 我们可设a x = t ，于是 a x = t t a (因 t是a和x 的下界， 或因a t= a (a x ) =a (吸收律) 及本节定理5(1) ) 0 t t a (0是B的最小元) 36离散数学 t= 0 t=a (a是0的直接后继) a x = 0 a x = a于是，总有 a x = 0 a x = a ；综上所证，a是B 的原子。注：此定理具体到集合代数，原子就是那些单元素集合。因为单元素集合在包含关系下是空集(最小元)的直接后继。即， 对于一般集合代数，有原子集S=a:aX； 对

28、于n元集合代数，这里X=a1, a2, an，有原子集 S= a1, a2, , an 。定理定理10.设(B, , , , , 0, 1)是布尔代数，并且a,b 都是B的原子。则 (1) a b 0 a=b ；37离散数学 (2)a b a b = 0 。证. (2)是(1)的逆否；于是只证(1) a b 0 a b =a a b = b (a是原子 b 是原子) a=b注：此定理说明两个原子，要么是同一个，要么相互不可比较。形象的，拿图论的语言来说，就是代表两个原子的结点，要么是同一个结点，要么分处在从0结点到1结点的两条不同的路上。定理定理11.设(B, , , , , 0, 1)是有限

29、布尔代数，|B|=n ， S是B的原子集。则 (xB)(x 0 (aS)(a x) 38离散数学即，对任何B的非零元素x ，都存在着B的某一原子a ，使得 a x 。证. 若x已是原子，则由x x ( 的自反性)，记a为x，就有a x ，定理得证； 若x不是原子，则必有x1 0 ，x1 x，使0 x1 x1 x(否则， x是0的直接后继，因而由本节定理9， x是原子，与已设x不是原子矛盾)； 若x1是原子，则由x1 x，记a为x1 ，就有a x ，定理得证；若x1不是原子，则必有x2 0 ，x2 x1 ，使0 x2 x2 x1(否则， x1是0的直接后继，因而由本节定理9， x1是原子，与已设

30、x1不是原子矛盾)； 若x2是原子，则由x2 x1 ，记a为x2 ，从a x1 x1 x ( 的传递性) ，就有a x，定理得证；若x2不是原子，则必有x3 0 ，x3 x2 ，使0 x3 39离散数学 x3 x2(否则， x2是0的直接后继，因而由本节定理9， x2是原子，与已设x2不是原子矛盾)；重复以上过程。从B的有限性可知，一定存在某个xk (kn) ， xk是原子，使得0 xk xk xk-1 ，从而有 0 xk xk-1 x3 x2 x1 x 根据 的传递性可知 xk x，记a为xk ，于是a是原子,并且 a x，定理得证。注：此定理说明在任一非零元素x的下方，一定有原子a存在；或

31、者形象的，拿图论的语言来说，就是在结点x所处的从0结点到1结点的某条路上， 在0结点上方，x结点下方，一定有原子结点a存在。定理定理12.(可表示性定理) 设(B, , , , , 0, 1)是有限布尔代数。 40离散数学 对任何元素xB，x 0 ，我们令 S(x)=a：aS a x则一定有(元素x的原子表示式)。证. 首先，我们令 ，则一方面，显然有 y x(因为对每个原子aS(x)，都有a x，根据上确界的最小性，就有 x ) ； 另一方面， 必有x y；为证x y ，根据定理5，我们只须证x y = 0即可。(采用反证法) 否则，x y0,那么，根据定理11，一定有原子aS存在，使得0

32、a x y。但是 x y x ， x y y，从而由 的传递性有a x，这说明aS(x)，从而a y(因y是S(x)中诸原子的上确界)；同时由 的传递性，axxSa)(ayxSa)(ayxSa)(41离散数学 又有a y；故此a y y= 0(下确界的最大性及互补律)，但0 a，于是由 的反对称性有a= 0。这就与a是原子(a 0)矛盾；综合这两方面，再次由 的反对称性可得 x=y 。注：此定理说明B的任一非零元素x，都可由在它下面的(即小于它的)全部原子来表示。定理定理13.设(B, , , , , 0, 1)是有限布尔代数。设b,a1, a2, , anS都是原子。我们令，那么 b x b

33、a1, a2, , an。证. 采用反证法。否则，ba1, a2, , an，故i(1i n)，bai 。由于b, ai 都是原子，故根据定理10(2)可得i(1i n)， b ai = 0。于是我们有iniax142离散数学 (条件：b x) (分配律) (b ai = 0 (i(1i n)这与已知b是原子(b 0)矛盾。定理定理14.(原子表示式的唯一性定理) 设(B, , , , , 0, 1)是有限布尔代数。则 B中任何非零元素x的原子表示式是唯一的。即00)()(111niiniiniababxbb43离散数学 对任何元素xB，x 0 ，那么 这里：S1 , S2 S证. 先证：S1

34、 S2 aS, aS1 a x ( ) aS2 (定理13及)所以S1 S2 ；次证：S2 S1 bS, bS2 b x ( ) bS1 (定理13及)所以S2 S1 ； 综合 ，我们有 S1= S2。)(2121xSSSbxaxSbSaaxSa1bxSb2axSa1bxSb244离散数学注：定理12及14说明B的任一非零元素x，都可由在它下面的(即小于它的)全部原子来表示。而所有的原子都小于最大元1 ，故最大元1可由全部原子唯一的表示为： 另外，最小元0也可形式的表示为：。定理定理15.(斯笃(stone)定理) 设(B, , , , , 0, 1)是一有限布尔代数，S是B的所有原子的集合。

35、则 有限布尔代数(B, , , , , 0, 1)与有限集合代数(2S, , , , , X )同构。证. (1)首先构造自然映射：h:B 2S 使得xB，x 0 ，h(x)=S(x)=a：aS a x 2S h(0)= 2S aSa1a0a45离散数学 h是函数(后者唯一)：x , yB， x = y aS, a x a y( 的传递性，定理13) a；aS a x= a：aS a y S(x)=S(y) h(x)=h(y) ； (2)h是双射函数： h是满射：A2S(即AS) ，令，则 h(x) = S(x) =a：aS a x = A (定理13) ； axAa46离散数学 h是单射：x

36、 , yB， h(x)=h(y) S(x)=S(y) (定理12) ( S(x)=S(y) ) (定理12) ； (3)h满足同态公式：x , yB，x , y 0 ， h(x y) = h(x) h(y) h(x y) = S(x y) yaaxySaxSa)()(47离散数学 = a：aSa x y = a：aS(a xa y) (见注：由a是原子易证：a x y a xa y) = a：(aSaS)(a xa y) (的幂等律) = a：(aSa x)(aSa y) (的结合律、交换律) = a：(aSa x)a：(aSa y) = S(x) S(y) = h(x) h(y)当x , y

37、至少有一为 0 时，易直接验证如上的同态公式也成立； h(x y)= h(x) h(y) 48离散数学 h(x y) = S(x y) = a：aSa x y = a：aS(a xa y) (见注：由a是原子易证：a x y a x a y) = a：(aSa x)(aSa y)(对的分配律) = a：(aSa x)a：(aSa y) = S(x) S(y) = h(x) h(y)当x , y至少有一为 0 时，易直接验证如上的同态公式也成立； 49离散数学 h(x)= h(x) = S(x) = a：aSa x = a：aS(a x) (见注：由a是原子易证：a x(a x) =S a：aS

38、a x = = 当x为 0 或1时，易直接验证如上的同态公式也成立；)(xS)(xh)(xh50离散数学 (4)h具有保序性： x , yB，x , y 0 ， x y h(x)h(y) x y a：aSa xa：aSa y (因x y (aS, a x a y)( 的传递性) S(x)S(y) h(x)h(y) (5)h具有齐性：显然 h(0)= h(1)=S最后，由同构函数的定义可知h是从(B, , , , , 0, 1) 到(2S, , , , , X )的同构函数，因而有限布尔代数(B, , , , , 0, 1)与有限集合代数(2S, , , , , X )同构。证明完毕。51离散数

39、学注：定理15证明(3)： a x y a xa y； 先证)：(采用反证法)否则，(a xa y)，于是则有(a xa y) (a x)(a y) (de Morgan律) a x=0a y =0 (因a是原子) a (x y) =(a x) y (结合律) = 0 y (因a x=0) = 0 (因0 a) (a x y) (因a是原子) 而这与必要性条件a x y矛盾； 次证)： a xa y (说明a是一下界) a x y (下确界的最大性) ；52离散数学 定理15证明(3) ： a x y a xa y ； 先证)：(采用反证法)否则，(a xa y)，于是则有(a xa y) (

40、a x)(a y) (de Morgan律) a x=0a y =0 (因a是原子) a (x y) =(a x) (a y) (分配律) = 0 0 (因a x=0和 a y =0 ) = 0 (幂等律) (a x y) (因a是原子) 而这与必要性条件a x y矛盾； 次证)： a xa y (a x x y )(a y y x y ) (上确界是上界) a x ya x y ( 的传递性) a x y (的幂等律) ；53离散数学 定理15证明(3) ： a x(a x) ； a x a x= a (x) (反身律) =0 (定理5(3)及 a x) (a x) (因a是原子) 。注：由

41、Stone 定理知每一个布尔代数都和某一个集合代数同构。前面还证明了开关代数和集合代数同构，命题代数和集合代数同构。因此研究集合代数也就是在研究布尔代数、开关代数、命题代数，它们的地位都是平等的。在以后的研究中，哪个方便就用哪个。 由于在有限集合代数中，母集是2X ，因此集合代数中母集的势为 |2X| =2|X| ，即其元素的个数是2的若干次幂。由Stone 定理可知任何一个布尔代数中母集的势也是的若干次幂，并且母集具有相同势的布尔代数是同构的，都同构于母集为2S的集合代数，其中S是布尔代数的原子集合。这样对于布尔代数的结构就了解得比较透彻了。54离散数学定义定义4.布尔函数(Boolean

42、function) 设(B, , , , , 0, 1)是布尔代数。 (1) B中的每个元素aB，特别是0和1称为布尔常量布尔常量； (2)在B中取值的变量称为布尔变量布尔变量； (3)以布尔变量为自变量且在B中取值的函数称为B上的布尔函数布尔函数；更进一步地， n元函数 f :BnB 称为n元元布尔函数布尔函数。例例8.设(B, , , , , 0, 1)是如图4所示的布尔代数。这里 B=0,a,b, 1,则 f(x1, x2, x3)=a (b x1 x2) x3是B上的三元布尔函数。 a1b0图55离散数学注：这个布尔代数的验证是容易的，因为它与有两个元素的集合上的集合代数同构。注：我们

43、知道在实数中取值的变量为实变量，以实变量为自变量的函数为实函数；在复数中取值的变量为复变量，以复变量为自变量的函数为复变函数；同理在B中取值的变量为布尔变量，以布尔变量为自变量的函数为布尔函数。 每个布尔函数可以由布尔表达式来表示。为此我们先给出布尔表达式的定义。定义定义5.布尔表达式(Boolean expression) 设(B, , , , , 0, 1)是布尔代数。 (1)布尔常量是布尔表达式； (2)布尔变量是布尔表达式； (3)如果E是布尔表达式，则E是布尔表达式；56离散数学 (4)如果E1 , E2是布尔表达式，则E1 E2 , E1 E2都是布尔表达式； 只有有限次使用(1)

44、,(2),(3),(4)所得到的有限符号串才是布尔表达式布尔表达式。注：当B是有限的情况，布尔函数也可用表的形式给出。例例9. 设布尔代数是(0,1, , , , 0, 1)(参见例2，开关代数)。 f 是从B2到B的布尔函数， f 定义如右表1：则f可用布尔表达式表示为f(x1, x2)=x1 x2。 x1x2 f(x1, x2) 00 0 01 0 10 0 11 1表157离散数学定义定义6.布尔小项(Boolean minteam) 设x1, x2,xn是n个布尔变量，称布尔表达式是布尔小项布尔小项，其中：是xi或是xi (1i n)。注： n个布尔变量的布尔小项只有2n个，因为每个变

45、量xi (1i n)都有取补与不取补两种选择。定义定义7.布尔析取范式(BDNF) (Boolean disjunctive normal form) 若n元布尔函数f具有形式，其中： Xi (1i 2n)都是布尔小项，ai B(1i 2n) ，则称f为布尔析取范式布尔析取范式。nxxxX21ix)()()(222211nnXaXaXa58离散数学注： n个布尔变量的布尔析取范式只有 个，因为每个常量ai (1i 2n)都有|B|种选择。定理定理16.(布尔析取范式存在定理) 每一个n元布尔函数f都可表示成布尔析取范式。证.(1)表示式 设n元布尔函数f可表示成布尔析取范式，即 f(x1, x

46、2, xn)=为此，我们只需求出2n个布尔小项的2n个系数ai (1i 2n)即可。 令 Pi=(pi1, pi2, pin)是与布尔小项相对应的布尔向量(1i 2n) ,这里：n2B)()()(222211nnXaXaXa)(njxxxxpjjjjij101当当nixxxX2159离散数学 于是，显然有布尔小项Xk在布尔向量Pi 处的布尔值：从而 f(Pi)=f(pi1, pi2, , pin) =(a1X1(Pi) (aiXi(Pi) (anX1(Pi) =(a10) (ai1) (an0) =0 ai 0 =ai 因此，我们得到 2n个布尔小项的2n个系数： ai = f(Pi) (1i

47、 2n) 。 (2)可表示性 任何一个n元布尔函数f都可表示成一布尔析取范式。这点可由如下给出的算法来保证。ikikPXnjpxikijj当当011)()(60离散数学 将将n元布尔函数化成布尔析取范式的算法元布尔函数化成布尔析取范式的算法：No1.补运算深入：运用de Morgan律将 运算移到各常量和各变量的右肩膀上去；No2.调整与 ：运用(第一)分配律，构成积之和；No3.消除多余：运用互补律(xx=0)及零壹律(E0=E)以消除和的多余零元；运用幂等律以消除积的多余变量，和的多余积式；No4.补齐变量：运用零壹律(E0=E)及互补律(xx=0)，将积式所缺之变量补齐，使其成为布尔小项

48、；No5.编码：对每个布尔小项用二进制进行编码，然后转换成对应的十进制编码(从0到2n-1，而非从1到2n)。例例10.在布尔代数(B, , , , , 0,1)(这里B=0,a,b,1参见61离散数学例8图4)中求三元布尔函数 f(x1, x2, x3)=(b x z (b y z) (xz)的布尔析取范式(BDNF)。解解.方法一：使用转换算法 No1.补运算深入：f(x1, x2, x3)=(bxz(b y z) (xz)No2.调整与 ：f(x1, x2, x3)=(bbxz)(bxyz)(bxzz)(xz)No3.消除多余：f(x1, x2, x3)=(bxyz)(xz)No4.补齐

49、变量：f(x1, x2, x3)=(bxyz)(xyz)(xyz)62离散数学 =(axyz)(xyz)(xyz)(因b=a及交换律)No5.编码：于是所求之布尔析取范式为：f(x1, x2, x3)=(am2)m5m7 ； 方法二：使用布尔向量(从0到7，而非从1到8)a0= f(P0) f(0, 0, 0) =(b 0 0 (b 0 0) (00)布尔小项 二进制码 十进制码 xyz 2 xyz 5 xyz 763离散数学 = (bb)=1=0a1= f(P1) f(0, 0, 1) =(b 0 1 (b 0 1) (01) =(11)= (10)=1=0a2= f(P2) f(0, 1,

50、 0) =(b 0 0 (b1 0) (00) =(b1)= (b0)=b=aa3= f(P3) f(0, 1, 1) =(b 0 1 (b1 1) (01) =(11)= (10)=1=0a4= f(P4) f(1, 0, 0) =(b 1 0 (b0 0) (10) =(1b)= (1a)=1=064离散数学a5= f(P5) f(1, 0, 1) =(b 1 1 (b0 1) (11) =(11)1 = (10)1 =11 =01 = 1 a6= f(P6) f(1, 1, 0) =(b 1 0 (b1 0) (10) =(11) = (10)= 1=0a7= f(P7) f(1, 1,

51、 1) =(b 1 1 (b1 1) (11) =(11)1 = (10)1 =11 =01 = 1 所以 f(x1, x2, x3)=(b x z (b y z) (xz) =(a2xyz)(a5 xyz)(a7 xyz) =(axyz)(1 xyz)(1 xyz)65离散数学 =(axyz)(xyz)(xyz) =(am2)m5m7注： n个布尔变量的布尔函数只有 个，因为n个布尔变量的布尔析取范式只有 个； 特别的，布尔代数(0,1, , , , 0, 1)(参见例2，开关代数)上的n个布尔变量的布尔函数只有 个。 定理16的证明不但给出了求布尔函数的布尔析取范式的算法，而且直接给出了布

52、尔函数的布尔析取范式中布尔小项的系数表达式： ai = f(Pi) (1i 2n) 这在理论上具有重要的意义； 定理16的证明中给出的求布尔函数的布尔析取范式的算法，比直接用布尔向量Pi求布尔析取范式中布尔小项的系数 ai = f(Pi) (1i 2n) 的方法，在一般情况 下，显然要简单的多；故一般我们多用算法，而不甚用求系数方法。n2Bn2Bn2266离散数学定义定义8.布尔大项(Boolean maxteam) 设x1, x2,xn是n个布尔变量，称布尔表达式是布尔大项布尔大项，其中：是xi或是xi (1i n)。注：n个布尔变量的布尔大项只有2n个，因为每个变量xi (1i n)都有取

53、补与不取补两种选择。定义定义9. (BCNF) (Boolean conjunctive normal form) 若n元布尔函数f具有形式其中： Xi (1i 2n)都是布尔大项，bi B(1i 2n) ，则称f为布尔合取范式布尔合取范式。nxxxY21ix)()()(222211nnYbYbYb67离散数学注： n个布尔变量的布尔合取范式只有 个，因为每个常量ai (1i 2n)都有|B|种选择。定理定理17. (布尔合取范式存在定理) 每一个元布尔函数都可表示成布尔合取范式。证. 仿定理16可证 。 这里n元布尔函数f的布尔合取范式为 f(x1, x2, xn)=其中：2n个布尔大项的2

54、n个系数 bi = f(Qi) (1i 2n)。这里Qi=(qi1, qi2, qin)是与布尔大项相对应的布尔向量(1i 2n) ,这里：n2B)()()(222211nnYbYbYbnixxxY21)(njxxxxqjjjjij110当当68离散数学 现在我们已学习了两种不同性质的代数系统：环与布尔代数。它们都含有两个二元运算，那么这两种代数系统间是否能建立起某种联系呢？下面我们就解决这个问题。定义定义10.布尔环(Boolean ring)乘法具有幂等律的环称为布尔环。即，设(R,)是环。若aR，a a=a，则称(R,)是布尔环。例例11.X的子集环(2X,)是布尔环已知(2X,)是环(

55、第四章5例4)；交运算满足幂等律。即 A2X ，A A=A；因此，由布尔环的定义10可知(2X,)是布尔环。69离散数学定理定理18. 布尔环是交换环。证. (1)aR , aaaa =(aa)(aa)(aa)(aa) (的幂等律) =(aa)(aa) (对的分配律) =aa (的幂等律) aa=0 (消去律) (2)a,bR , a(ab)(ba)b =(aa)(ab)(ba)(bb) (的幂等律) =(ab)(ab) (对的分配律) =ab (的幂等律) (ab)(ba)=0 (消去律) 70离散数学 (3)a,bR , ab=(ab)0 (0是的幺元) =(ab)(ab)(ba) (已证

56、(ab)(ba)=0) =(ab)(ab)(ba) (的结合律) =0(ba) (已证 aR , aa=0) = ba (0是的幺元) 由交换律的定义知运算满足交换律。 故布尔环是交换环。下面我们在布尔代数和布尔环之间建立一种相对应的关系。定理定理19. 设(B, , , , 0, 1)是布尔代数。在B上定义两个二元运算如下：+,:BBB a,bB ,a+b=(ab)(ba) 71离散数学 a b=ab则(B,+, )是含幺布尔环。证. (一)先证(B,+)是交换群：(1)封闭性：由,和 的封闭性可知运算具有；(2)结合律：由和的结合律、交换律、分配律以及 和, 之间的De Morgan 律可

57、得运算满足；(3)有幺元(零元)：关于运算的幺元是最小元0；(4)有逆元(负元) ：aR ,a关于运算的逆元是a；(5)交换律：由和的交换律可知运算满足； 由交换群的定义知是(B,+)交换群。 (二)再证(B, )是交换含幺半群：(1)封闭性：由的封闭性知运算封闭；(2)结合律：由的结合律知运算满足结合律；72离散数学(3)交换律：由的交换律运算满足交换律；(4)有逆元：关于运算的幺元是最大元1；由交换含幺半群的定义知(B, )是交换含幺半群。 (三)下证运算对运算满足分配律： a,b,cB , a (b+c) =a (bc)(cb) =(a bc)(a cb) (对的分配律) =(a bc)

58、(a b c) (的交换律) (a b)+ (a c) =(a b)(a c)(a c)(a b) =(ab (ac)(ac(ab) =(ab (a c)(ac(a b) (de Morgan律) 73离散数学 =(abc)(acb) (对的分配律、互补律) =(abc)(abc) (的交换律) 故 a (b+c)=(a b)+ (a c) ； 由运算的交换律知另一分配等式也成立；即运算对运算满足分配律。 由环的定义可知(B,+, )是含幺环。 又 aB ,a a= aa=a (的幂等律)故由布尔环的定义知(B,+, )是含幺布尔环。例例12. 集合代数(2X, , , , , , X ) 是

59、布尔代数(例1)； 由此布尔代数可定义两个运算 和 如下： A,B2X ，AB=(AB) (BA) (参见第一章2定义4的注 ) A B=A B 74离散数学 由此产生的含幺布尔环是X的子集环(2X,) ，其关于运算的幺元是X (参见例11) 。定理定理20.设(B,+, )是含幺布尔环。在B上定义两个二元运算及一个一元运算如下： , :BBB ， :BB a,bB ,a b=ab ab=a+b - ab aB ,a=1-a于是有a,bB , a b ab=aab=b (定理5) 则(B, , , , 0, 1)是布尔代数，其中0是关于运算的幺元(零元)，1是关于运算的幺元。证. (一)先证(

60、B, , , )是格 (1) 运算具有封闭性，满足结合律、交换律、幂等律75离散数学由于运算是由运算直接定义的，故运算的封闭性、结合律、交换律、幂等律，可直接由运算所具有的封闭性，所满足的结合律、交换律、幂等律而得到； (2)运算具有封闭性，满足结合律、交换律、幂等律封闭性：由和+ 的封闭性可知运算具有封闭性；结合律：a,b,cB , (ab)c(a+b-ab)+c-(a+b-ab)c a+b+c(ab+ab+ab)+abc (对+,-的分配律， +的结合律、交换律) a(bc)a+(b+c-bc)-a(b+c-bc) a+b+c(ab+ab+ab)+abc (对+,-的分配律， +的结合律、