离散数学：7 格与布尔代数(简化版)

1、第七章 格与布尔代数集合代数：(S),)对A,B,C(S)，运算，满足：等幂律 AA = A， AA = A，交换律 AB = BA， AB = BA，结合律 A(BC)=(AB)C， A(BC)=(AB)C，分配律 A(BC)=(AB)(AC)， A(BC)=(AB)(AC)，吸收律 A(AB)=A， A(AB)=A若引进余集的概念，有De Morgan定律:命题代数（S，）对A,B,CS，运算，满足：等幂律 AA = A， AA = A， ，交换律 AB = BA，AB = BA 结合律 A（BC）=（AB）C， A（BC） = （AB）C 分配律 A(BC)=(AB)(AC)， A（BC

2、） = （AB） （AC） 吸收律 A(AB)=A，A（AB）=A， 若引进否定的概念，有De Morgan定律:(AB )= AB, (AB )= AB, 7.2 格 的 定 义 偏序（半序）格(定义A )给出一个偏序集（L,），如果对于任意a,bL，L的子集a, b在L中都有一个最大下界(记为infa, b)和一个最小上界（记为supa, b），则称（L，）为一个格。 半序格的例例. S是任意一个集合，(S)是S的幂集合， 则，部分序集(S)，)是一个格。因为对A, B(S)，supA, B=AB(S), infA,B=AB(S)例.设I+是所有正整数集合，D是I+中的“整除关系”，对任意

3、a，bI+，aDb当且仅当a整除b，于是，（I+，D）是一个格。supa,b=a，b的最小公倍I+，infa,b= a，b的最高公因I+ 。 半序格的例例. 设n是一个正整数，Sn是n的所有正因数的集合，于是，（Sn，D）是格。因为supa,b=a，b的最小公倍 Sn，infa,b= a，b的最高公因 Sn。例. 设S是所有的命题集合，定义“ ” 如下：A B 当且仅当 B蕴涵A。则（S，）是一个格。因为supA，B=ABS， infA，B=ABS。 半序子格定义A 设（L，）是格，S L，如果（S，）是格，则称（S，）是格（L，）的子格。 例.（S6，D）是（S24，D）的子格。 代数格定义

4、B 设L是一个集合，是L上两个二元代数运算，如果这两种运算对于L中元素满足： （1）交换律：ab=ba，ab=ba。 （2）结合律：a（bc）=（ab）c， a（bc）=（ab）c。 （3）吸收律：a（ab）=a， a （ab）=a。则称此代数系统（L，）为一个格。 note:设(L, , )是格，则(L, )和(L, )均为交换半群。定义B中由， 满足吸收律可推出它们一定满足等幂律。证明：任取L中元素a，由，满足吸收律知，a(aa)=a， a (aa)=a。故aa=a(a(aa)， aa=a(a(a a)。又由，满足吸收律知，上面两式的等式右端都等于a。因此， aa = a， a a = a

5、。即， 定义B中的，运算亦满足等幂律。代数格的例例. 设S是一个集合,(S)是S的幂集合，于是，(S),)是一个代数格。而(S)，)是半序格。易见对A,B(S)， A B AB = A AB = B。例. 设I+是所有正整数集合, 两个正整数的最高公因, 最小公倍是I+上两个代数运算，于是, (I+, ,)是一个代数格。而（I+,D）是半序格, D是整除关系。易见，对任意a，bI+, a D b ab = a ab = b。例. 设n是一个正整数,Sn是n的所有正因数的集合,两个正整数的最高公因,最小公倍是Sn上两个代数运算,于是,(Sn,)是一个代数格。 代数格与半序格的等价性定理7.2.1

6、 定义A所定义的格和定义B所定义的格是等价的，亦即，一个半序格必是一个代数格；反之亦然。证明：i）若(L,)是一个半序格,则对a,bL，记infa,b为ab； supa, b为ab。由于对任意a，b，其infa, b，supa, b是唯一的，所以，如上定义的，是集合L上的两种二元代数运算。 不难证明：对于,满足交换律、结合律、吸收律。则根据定义B，(L,)是一个代数格。 只证明吸收律中的一条： a（ab）=a其它算律的证明作为课后练习。因为a(ab)是a与(ab)的最大下界，所以a(ab)a另一方面，由于aa，aab，所以，a是a与ab的下界，故aa(ab)所以，a=a(ab)。证明证明ii）

7、若代数系统（L, , ）是一个代数格，在集合L上定义一个关系如下：对任意a，bL， ab ab=a往证：是一个半序关系。反身性:因为aa=a(a(aa)= a, 所以aa。反对称性:若有ab,ba,则应有ab=a，ba=b，而ab = ba，所以a=b。传递性:若ab，bc，则有ab=a，bc=b，故ac=(ab)c=a(bc)=ab=a，亦即，ac。往证：ab = a a b = b。若ab = a，则 ab = （ab） b = b。若ab = b，则 ab=a（ab）=a。往证:对任意a, bL, a,b在L中必有infa, b, supa, b，且就是ab和ab.由吸收律知 a（ab）

8、= a， b（ab）= b，故有a（ab），b（ab）。亦即，ab是a，b的上界。证明若cL，且c是a，b的上界，亦即有ac，bc，则应有 ac=c，bc=c，于是，（ab）c =a（ bc） =ac =c故有（ab）c。因此，（ab）是a，b的最小上界，即supa，b=（ab）。同理可证，infa，b=（ab）。综上，（L，）为半序格。 代数子格定义B 设(L,)是一个代数格，S L，(S,)称为(L,)的一个代数子格，当且仅当在运算,下，S是封闭的。结论：(S,)是格(L,)的子格的充要条件是：SL 且（S,）是一个格。 例.(Sn, ,)是(I+,)的代数子格，其中,分别是最高公因和最小

9、公倍运算。代数子格与半序子格的关系设(L，)是一个半序格，与其等价的代数格为(L,)，S L。若(S,)是(L, , )的代数子格，则（S，）是（L，）的半序子格；若（S，）是（L，）的半序子格，则(S,)不一定是(L, , )的代数子格。 a3a5a1a2a4a6a7a8设L=a1,a2,a3,a4,a5,a6,a7,a8,（L,）是格。(1)取S1=a1,a2,a3,a4,则（S1，）是（L，）的半序子格，也是（L,）的代数子格。(2)取S2=a1,a2,a4,a7,则(S2 ，)是(L，)的半序子格,但(S2,)不是(L,)的代数子格。因为:a2a4=a3，而a3S2， 即，S2在下不封

10、闭。7.3 格的性质7.3.1 格 的 性 质 7.3.2 格的同态与同构7.3.1 格 的 性 质定理7.3.1 设（L，）是一个格，a，b是L中任意元素，于是 ab ab = a a b = b定理7.3.2 设（L，）是一个格，a，b，c是L中任意元素，如果bc，则有 abac, abac定理7.3.3 设（L，）是一个格，a，b，c是L中任意元素。于是有 a（bc） （ab）（ac） a（bc）（ab）（ac）Note:在一般格中，分配律不是总成立的，但上述分配不等式总是成立的。因为a2（a1a3）= a2 （a2a1）（a2a3）=a3只有对特殊的格（分配格、模格）分配律才成立 a2

11、a301a17.3.1 格 的 性 质定理7.3.4 设（L，）是一个格，a，b，c是L中任意元素，于是， ab a（bc）b（ac）7.3.1 格 的 性 质 7.3.2 格的同态与同构定义. 设(L,)和(S,)是两个格，L到S内的映射g称为(L,)到(S,)的格同态映射，如果对任意a，bL，都有 g（ab）= g（a）g（b） g（ab）= g（a）g（b）.定义. 格L到L内的同态映射称为格的自同态映射。定义. 若g是L到S上的同态映射，且是一对一的，则称g是格同构映射，并称格L与格S是同构的。此时，对任意xL，任意yS ，有 g-1(g(x)=x，g(g-1(y)=y。 同态映射例例

12、. 设S=a, b,(S)=, a, b, a,b，则(S), , )是一个格。设L=0，1，规定01，分别是集合L中两个元素在下的最大下界，最小上界运算，则（L,）是一个格。规定映射g为：g(a) = 1， g(a, b) = 1， g(b) = 0， g() = 0。则显然g是(S)到L上的同态映射.格的同态映射一定是保序映射定理7.3.5 设(L,)和(S,)是两个格。集合L上对应于运算，的部分序为L，集合S上对应于运算，的部分序为s。如果g是L到S内的同态映射，则g是保序映射，亦即，对任意a，bL，若aLb，则g（a）sg（b）。例子同态具有保序性，但其逆不一定成立，保序映射不一定是同

13、态的。下面给出3个格L1, L2, L3。定义映射1, 2和3：1：L1L2, 1(a)= 1(b)= 1(c)=a1, 1(d)=d1.2：L1L2, 2(b)= 2(c)= 2(d)=d1, 2(a)=a1.3：L1L3, 3(a)=a2, 3(b)=b2, 3(c)=c2, 3(d)=d2.c2b2a2d2L3d1a1L2cabdL1例子可以看出这3个映射都是保序的，但都不是同态的。因为1(bc)= 1(d)=d1, 1(b) 1(c)= a1 a1=a1,2(bc)= 2(a)=a1, 2(b) 2(c)= d1 d1=d1,3(bc)= 3(d)=d2, 3(b) 3(c)=b2 c

14、2=c2, 定理7.3.6 设(L,)是一个格，g是此格的自同态映射，于是g(L)是(L, , )的代数子格。证明： 任取a,bg(L),则必有a,bL, 使 a= g（a）， b= g（b）因为g是格（L，）的自同态映射，所以 ab=g(a)g(b)= g(ab)g(L)， ab= g(a)g(b)=g(ab)g(L)。即在运算，下，g（L）是封闭的。故（g（L）， ，）是（L，）的代数子格。 定理7.3.7 设(L,), (S,)是两个格，若g是L到S上的同构映射，则g的逆映射g-1是S到L上的同构映射。证明： 显然g-1是S到L上的一对一映射。下面证明g-1是S到L上的同态映射。任取a,

15、bS,令g-1(a)=a,g-1(b)=b。于是g（a）= a， g（b）= b。g-1(ab)=g-1(g(a)g(b)=g-1(g(ab) = ab =g-1(a)g-1(b)。g-1(ab)= g-1(g(a)g(b)=g-1(g(ab) = ab= g-1（a）g-1（b）。故g-1是S到L上的同构映射。 推论 若格(L,)和格(S, ,)同构，g是其同构映射，则对L中任意两个元素a，b，有aLb g（a）sg（b）其中L，S分别是集合L，S上对应于运算，的部分序关系。 a,b,ca,ba,cb,cab维格 设L=0, 1，规定01。于是，(L, )是格。令(

16、L, ,)是与之等价的代数格。令 Ln=(a1，an)aiL，i=1，n规定：(a1,an )n ( b1,bn ) aibi (i=1,n)不难证明：(Ln，n)是一个格，通常称为n维格。令与(Ln，n)等价的代数格为(Ln,)，对Ln中任意两个元素(a1,an)，(b1,bn)，显然有(a1,an)(b1,bn)=(a1b1,anbn)(a1,an)(b1,bn)=(a1b1,anbn)。 7.4.1 有 界 格 7.4.2 有 余 格 7.4.3 分 配 格 7.4.4 模 格7.4 几种特殊的格7.4.1 有 界 格 引理1 设(L，)是一个格。若S是L的任意一个有限非空子集，则S有一

17、个最大下界和一个最小上界。记集合S的最大下界为inf S； 集合S的最小上界为sup S。 Note: 对于格的一个无穷子集，引理1的结论不成立。 例.在格（I+，）中，所有正偶数组成的集合记为E+，显然，E+ I+，但E+没有最小上界。定义. 格（L，）称为有界格，如果它有一个最大元素（记为1）和一个最小元素（记为0），亦即，对任意aL，都有 0a1 0，1称为格（L，）的界。 结论：有限格必是有界格 令L=a1，an , 0 = a1a2an, 1 = a1a2an 引理2. 若（L, 0, 1）是有界格，则对任意aL，恒有 a 0 = a， a1 = a， a 1 = 1， a0 = 0

18、。 7.4.1 有 界 格 定义. 在有界格（L，0，1）中，一个元素bL，称为元素aL的余元素，如果 ab = 0， ab = 1。ab10ab10ac10ba,b均无余a有唯一余bc有两个余a,b在有界格（L, 0, 1)中，1是0的唯一一个余元素，反之亦然。7.4.2 有 余 格 定义. 称有界格（L，0，1）是一个有余格，如果对L中每一个元素，都至少有一个余元素。例. 设S是有n个元素的集合，(S)是S的幂集合，于是，（S），）是有余格。其中， 和S是此格的界.对（S）中任意元素A，（S）中的元素S-A是其余元素。a,b,ca,ba,cb,cabc7.4.3 分 配 格 定义7.4.4

19、 格（L,）称为分配格，如果对任意a，b，cL，恒有a(bc)=(ab)(ac)a(bc)=(ab)(ac)Note: (1)分配格定义中的两个等式是等价的(ab)(ac)(aa)(ac)(ba)(bc)a(ac)(ab)(bc)a(a(cb) )(bc)a(bc)7.4.3 分 配 格 Note: (2) n维格(Ln, n)，格(S), )，(I+, D)，(Sn, D)都是分配格。 但不是所有的格都是分配格 (3)分配格的任意子格仍是分配格。 证明：设格（L，）是一个链，任取a, b, c L, 1）若ab且ac，于是abc，故 a(bc)= bc而ab = b，ac = c，所以 (a

20、b)(ac)= bc故a(bc)=(ab)(ac)。2）若ab或者ac，于是a(bc)，故a(b c)= a。而 (ab)(ac)= a所以a(bc)=(ab)(ac)。 引理4 任意一个链都是一个分配格De Morgan定律定理7.4.1 设（L,）是一个分配格，对任意a,bL，若a，b有余元素a,b，则 (ab)= ab (ab)= ab证明： (ab)(ab)=(aba)(abb) =(1b)(a1)= 11 = 1而(ab)(ab)=(aab)(bab) =(0b)(0a)= 00 = 0故由余元素定义知， (ab)= ab同理可证另一等式。例子图中L1和L2是分配格，但L3, L4不

21、是。因为在L3中 b(cd)=b e=b和(b c) (b d)=a a=a；在L4中d(bc)=d e=d和(d b) (d c)=a c=c。L3称为钻石格， L4称为五角格。cbadL1cbadcbadcbadeeL3L2L4定理7.4.2 设格（L,）是分配格，对任意a,b,cL，如果 ac = bc， ac = bc，则a = b。证明：若（L,）是分配格，且ac=bc，ac=bc，则a = a(ac)= a(bc) =(ab)(ac) =(ab)(bc)= b(ac) = b(bc)= b 定理7.4.2 设格（L,）是一个有余分配格，则对任意aL，a的余元素a是唯一的。证明： 因

22、（L,）是有余格，设a和a都是a的余元素，即 aa= 0， aa= 1 aa= 0， aa= 1故aa= aa，aa= aa。由定理8.4.2知，a= a。 推论 7.4.4 模 格 定义7.4.5 设(L,)是一个格，对任意a, b, cL，如果ab，都有a(bc)= b(ac)则称（L，）为模格。例子与结论格L1、L2和L3都是模格，但L4不是。因为c d, 但c (bd)=c,(cb) d=d 一个格L是模格当且仅当L不含与五角格同构的子格。一个模格是分配格当且仅当L不含与钻石格同构的子格cbadL1cbadcbadcbadeeL3L2L4Note:(1)任意一个分配格都是模格， 由ab

23、， ab=b, 故 a(bc)=(ab)(ac) = b(ac)(2)模格不一定是分配格。如图所示L=0, 1, a, b, c。则格(L,)是模格，但不是分配格，因为 a(bc)= a(ab)(ac)= 0。 ba0c1cb0d1不是模格也不是分配格是模格不是分配格定理7.4.3定理7.4.3 格(L，)是模格的充要条件是：对任意a，b，cL，如果ab，ac=bc，ac=bc则必有a=b。证明：必要性。若格（L，）是模格，则对任意a，b，cL，如果ab，ac=bc，a c=b c，则a = a （ac）= a （bc） = b（ac）= b（bc）= b充分性。任取a，b，cL，且ab。因为

24、(a(bc) c = a (bc)c)=ac 又因为ab，所以ab(ac)，故a c(b(ac)c (a c) c = ac所以，(b(a c) c = a c。因此(a(bc)c =(b(ac)c (1)亦即，在格（L，）中，若ab，则有（1）式。 定理7.4.37.5 布 尔 代 数7.5.1 布尔代数的定义及其性质 7.5.2 有限布尔代数的表示理论7.5.3 布尔代数的同态与同构7.5.1 布尔代数的定义及其性质定义. 一个有余分配格是一个布尔代数。记为（B，+，0，1）。a，b，c是集合B中任意元素，有如下性质:（一）因为（B，+）是一个格，有1）aa= a， 1）a+a = a。2

25、）ab=ba， 2）a+b = b+a。3）(ab)c=a(bc)， 3）(a+b)+c=a+(b+c)。4）a（a+b）= a, 4）a+（ab）= a。 （二） 因为（B，+）是分配格，所以有5)a(b+c)=(ab)+(ac)， 5)a+(bc)=(a+b)(a+c)。6）(ab)+(ac)+(bc)=(a+b)(a+c)(b+c)。7）若ab = ac，a+b = a+c，则b=c。 （三）因为（B，+，0，1）是有界格，所以 有 8）0a1。 9） a0 = 0， 9）a+1 = 1。 10）a1 = a， 10）a+0 = a。布尔代数的性质（四） 因为（B，+，0，1）是有余分配

26、格，所以有11） 11）12） 12）13） 13） （五） 因为（B，）是半序格，所以有14）ab = infa，b 14）a+b = supa，b。15）ab a+b = b ab = a。16）布尔代数的性质Huntington公理 定理7.5.1 设B是一个至少含有两个不同元素的集合，+是定义在B上的两种代数运算，如果对任意a，b，cB，满足下面公理：H1：ab = ba，a+b = b+a.H2：a(b+c)=(ab)+(ac), a+(bc)=(a+b)(a+c)。H3：B中有元素0和元素1,使得对任意aB,有 a1 = a, a+0 = a。 H4： 对任意aB，有 B，使得 则

27、（B，+，0，1）是一个布尔代数。 布尔代数的例电路代数 （B，+，0，1） 其中B=0，1, B上的运算+，如下表定义：集合代数 （S），S） 其中S是一个非空集合。01000101+01001111x0110 命题代数（S，F，T）其中S是命题公式的集合。 开关代数 （Bn，+，0n，1n）其中Bn是由0，1做分量的所有n元向量集合。对任意a,bBn,令a=(a1，an)，b=(b1，bn)，定义Bn上的运算如下：ab=（a1b1，a2b2，anbn）a+b =（a1+b1，a2+b2，an+bn）0n表示n个0做成的n元向量(0，0)，1n表示n个1做成的n元向量(1，1) 。 子代数定

28、义 任给一个布尔代数 (B, , +, , 0, 1)。若B的一个子集S包含0和1, 且(S，+，0，1)仍是一个布尔代数,则称S为B的子代数。例. 设S = a，b，c，则(S), , S)是一个布尔代数。(1)设S1=,a,b,c,a,b,c，则(S1, , S)是(S), , S)的子代数。定理7.5.2 设（B，+，0，1）是布尔代数。于是，B的子集S是B的子代数的充要条件是S在运算 ，+，下是封闭的。7.5.2有限布尔代数的表示理论 基 底设（B，+，0，1）是布尔代数，e1，en是B中有如下性质的一组元素, 对任意aB，都可唯一地表示为 a =1e1+2e2+nen其中i或为0，或

29、为1，（i = 1，n）。则称e1，en为布尔代数B的一组基底，并称此布尔代数为n维的。 结论1 设e1，en为布尔代数B的一组基底，则对于 i1,n, ei0。证明： 用反证法。若有ei = 0，则一方面，ei = 0e1 + 0e2 + +0ei + + 0en，另一方面，ei = 0e1 + 0e2 + +1ei + + 0en，而eiB，且表示方法不唯一。这与定义中任意aB,都可唯一地表示为1e1+2e2+ +nen矛盾。因此，ei0，i=1，n。 结论2. 设e1，en为布尔代数B的一组基底，则对于，如果ij，那么eiej。证明： 用反证法。若存在ij，而ei=ej，不妨设ij，则有

30、 ei = 0e1 + 0e2 + +1ei + 0ej + + 0en， ei = ej= 0e1 + 0e2 + +0ei + 1ej + + 0en， 显然与ei表示方法唯一矛盾。 例. 设S30是30的所有正因数做成的集合。对任意a，bS30，规定运算a + b 为a、b的最小公倍数，ab 为a、b的最大公约数。则（S30，+，1，30）是布尔代数，1是其最小元素，30是其最大元素。该布尔代数的基底为2，3，5：1=(12)+(13)+(15)， 2=(302)+(13)+(15)，3=(12)+(303)+(15)，5=(12)+(13)+(305)，6=(302)+(303)+(15), 10=(302)+(13)+(305)，15=(12)+(303)+(305)， 30=(302)+(303)+(305)。 极小元定义. 设（B，+，0，1）是布尔代数。若B中非零元素a有性质：对任意B，a或者为0，或者为a，则称a为布尔代数的极小元素。结论3 若a，b为布尔代数中的两个不同的极小元素，必有ab=0。证明：用反证法。若a，b为布尔代数中的两个不同的极小元素，而ab0，则一方面由a为极小元素知，ab = a； 另一方面， 由b为极小元素知，ab = b。于是，a=b，与ab矛盾。 引理1 设B是布尔代数，a是B中任一非零元素。若a不是