《格和布尔代数》doc版.doc

螀羄蒆蚆袂腿莂螆羅羂芈螅蚄膈膄螄螆羁薂螃罿芆蒈螂肁聿莄螁螁芄芀螀袃肇蕿螀羅芃蒅衿肈肅莁袈螇芁芇蒄袀肄芃蒄肂荿薂蒃螂膂蒈蒂袄莇莃蒁羆膀艿蒀聿羃薈蕿螈腿蒄薈袀羁莀薈羃膇莆薇螂羀节薆袅芅薁薅羇肈蒇薄聿芃莃薃蝿肆艿蚂袁节膅蚂羄肅蒃蚁蚃芀葿蚀袆膃莅虿羈莈芁蚈肀膁薀蚇螀羄蒆蚆袂腿莂螆羅羂芈螅蚄膈膄螄螆羁薂螃罿芆蒈螂肁聿莄螁螁芄芀螀袃肇蕿螀羅芃蒅衿肈肅莁袈螇芁芇蒄袀肄芃蒄肂荿薂蒃螂膂蒈蒂袄莇莃蒁羆膀艿蒀聿羃薈蕿螈腿蒄薈袀羁莀薈羃膇莆薇螂羀节薆袅芅薁薅羇肈蒇薄聿芃莃薃蝿肆艿蚂袁节膅蚂羄肅蒃蚁蚃芀葿蚀袆膃莅虿羈莈芁蚈肀膁薀蚇螀羄蒆蚆袂腿莂螆羅羂芈螅蚄膈膄螄螆羁薂螃罿芆蒈螂肁聿莄螁螁芄芀螀袃肇蕿螀羅芃蒅衿肈肅莁袈螇芁芇蒄袀肄芃蒄肂荿薂蒃螂膂蒈蒂袄莇莃蒁羆膀艿蒀聿羃薈蕿螈腿蒄薈袀羁莀薈羃膇莆薇螂羀节薆袅芅薁薅羇肈蒇薄聿芃莃薃蝿肆艿蚂袁节膅蚂羄肅蒃蚁蚃芀葿蚀袆膃莅虿羈莈芁蚈肀膁薀蚇螀羄蒆蚆袂腿莂螆羅羂芈螅蚄膈膄螄螆羁薂螃罿芆蒈螂肁聿莄螁螁芄芀螀袃肇蕿 第十章格和布尔代数这一章研究特殊的代数系统格,它的结构以偏序关系为基础。在格的基础上增加一些条件后,格就变成布尔代数。格的概念在有限自动机的研究方面是重要的,布尔代数可直接用于开关理论和逻辑设计。为此我们先复习一下偏序集的有关概念。 10.1 偏 序 集与格10.1.1 偏序集的性质在第四章我们将集合L上具有自反性、反对称性、传递性的关系称为集合L上的偏序关系,并用记号“”来表示,还将集合L和L上的偏序关系一起称为一个偏序集（Partially Ordered Set）,用来表示，并讨论了L的子集上的最大下界、最小上界、最大元、最小元等概念.我们先复习偏序集的这些概念和性质，并由此引出格的定义。由于和它的逆都是L上的偏序关系,因此,对于偏序集中所有的元素a, b ,c。 a a （L-1）若a b，ba，则有a =b （L-2）若a b，bc，则有a c （L-3） a a （L-1）若a b，bc，则有a c (L-2）若a b，bc，则有a c ( L-3）定义10.1-1 设是偏序集,对于a, bL,如果存在元素xL，满足xa ，xb,则称x为a和b的下界。如果存在元素yL，满足ay，by，则称y为a和b的上界。如果元素x是a和b的下界，且对于a和b的任何下界，都有，则称x是a和b的最大下界(下确界)(Greatest lower bound)。如果元素y是a和b的上界，且对于a和b的任何上界yL, 都有yy,则称y是a和b的最小上界(上确界)(Least upper bound)。定理10.1-1 设是一偏序集，a,bL,则若a和b有最大下界，则最大下界是唯一的，并记作glb(a,b)；若 a和b有最小上界，则最小上界是唯一的, 并记作lub(a,b)。证明 设a和b有最大下界x1和x2。因为，最大下界是下界，所以 x1是a和b的下界，而x2是a和b的最大下界，因此x1 x2；同理可证x2x1。故有x1= x2。同理可证。10.1.2 格的定义对任意一个偏序集来说,其中的每一对元素不一定都有最大下界或最小上界,我们讨论其中每一对元素都有最大下界和最小上界的偏序集,并将这种偏序集称作是“格”。定义10.1-2 设是一个偏序集,如果对于每一对元素a,bL构成的子集a,b均存在最大下界和最小上界，则称偏序集为格(Lattice)。由格的定义和定理10.1.1，格中任何一对元素a和b都有唯一的最大下界glb(a,b)，和唯一的最小上界lub(a,b)与其对应。也就是定义了两个LLL的函数，亦即定义了两个L上的二元运算，这两个二元运算分别用ab和ab来表示，即ab= glb(a,b)，ab=lub(a,b)和分别称为交(Meet)和并(Join)。例10.1-1 集合S的幂集和定义在其上的包含关系构成偏序集.对于任意子集A,BS，因为AAB,BAB，而且若AC,BC,则ABC。因此， A,B的最小上界AB=AB。同理A,B的最大下界AB=AB。于是，是格。由集合S=a,b,c得到的格的Hass图，如图10.1-1所示。a,b,ca,bb,cca,cab图10.1-1图10.1-23126(a)(b)1254102030611551023(c)例10.1-2 设I+为正整数集合，对于a,b I+，关系“”定义为：ab当且仅当a整除b。则偏序集构成格，其中ab是a,b的最大公因数（记作GCD），ab是a,b的最小公倍数(记作LCM)，即ab=GCD(a,b)， ab= LCM(a,b)例10.1-3 设n为正整数，Sn为n的正因数的集合，为例10.1-2中的整除关系，则是格。S6=1,2,3,6, S20=1,2,4,5,10,20,S30=1,2,3,5,6,10,15,30，图10.1-2中的图(a)、(b)、(c)分别给出了格和，的哈斯图。例10.1-4 判断图10.1-3中的哈斯图表示的偏序集是否构成格,说明为什么。(b)(c)(d)(e)aaaabbbbccccddddeeeef图10.1-3(a)abcd由格的定义，要考察一个偏序集是不是格，只要考察它的任何两个元素构成的子集a,b是否都有最大下界和最小上界。我们知道，有偏序关系的两个元素a,b构成的子集a,b都有最大下界和最小上界，而在一条线上的两个元素都有偏序关系。因此，要考察一个偏序集是不是格，我们只需考察不在一条线上的两个元素a,b构成的子集a,b是否都有最大下界和最小上界即可。(a)的元素都在一条线上，所以它是一个格。(b)b,c的最大下界和最小上界分别是a,e；a和e也分别是d,c最大下界和最小上界，所以(b)是格。(c) 因为，b,c没有最小上界，d,e没有最大下界，所以它不是格。(d) 因为，a,b没有最大下界, d,e没有最小上界，所以它不是格。(e) 因为，a,b没有最大下界也没有最小上界，所以它不是格。由于最大下界也是下界，同理最小上界也是上界。由下界和上界的定义，则对于任何的a,bL都有 ab a，ab b （L-4） aba，abb （L-4）由最大下界和最小上界的定义,在格中,对于所有的元素a,b ,xL,有若xa， xb，则x ab （L-5）若 xa， x b，则xab (L-5)注意（L-4），（L-4），（L-5），(L-5)是格的重要性质，在此后的学习中，常用这四个关系式来证明各种等式和不等式。10.1.3 格的对偶原理和性质观察前面这些格的公式或性质，我们发现它们都是有规律地成对出现。这就是我们要介绍的对偶原理。设f是一个含有格中的元素和符号=, , , , 的命题，而f*是将f中的, , 和分别用, ,和代替后得到的命题，则称f*是f的对偶命题。例如（ab）（ac）a（bc）与（ab）（ac）a（bc）互为对偶命题。容易看出,前面列出的有关格的10个基本关系式中,（L-1）, （L-2）, （L-3）, （L-4）, （L-5）,分别是（L-1）,（L-2）,（L-3）,（L-4）,（L-5）的对偶命题。由此可见,在格的任一由这些基本关系式所导出的关系式中,同时交换和以及和所得到的关系式也可以从这些基本关系式的对偶命题导出。于是,对于格中的每一条定理都存在着一条与其对偶的定理。格的对偶原理：设f一个含有格的元素和符号 =，的任一真命题，其对偶命题f*亦为真。由格的对偶原理,每一条关于格的定理，都有一对互相对偶的命题。因此，在证明格的性质时,我们只须证明一对互相对偶命题中一个就可以了。定理10.1-2 设是格, 则格的交和并运算满足交换律, 对于任意的a,bL有 ab= ba ，ab= ba结合律,对于任意的a,b,cL有a(bc)=(ab)c，a(bc)=(ab)c等幂律,对于任意的aL有aa = a，aa = a吸收律,对于任意的a,bL,有a(ab)=a，a(ab)=a证明 我们先证ab= ba。由（L-4）有abb,aba,则由（L-5）有abba,同理可得ba ab ,于是由反对称性,得ab=ba。再证ab=ba。由（L-4）有abb, aba,则由（L-5）有abba,同理可得baab ,于是由反对称性,得ba=ab。我们只证a(bc)=(ab)c。设x = a(bc), x=(ab)c。由（L-4）有xa, xbc,再由（L-4）和传递性,有xb, xc。由xa, xb,和（L-5）有xab,又xc,所以由（L-5）有x(ab)c,即xx。同理可证xx。故由反对称性,得x=x。即a(bc)=(ab)c。我们只证aa=a。由（L-4）有aaa，而由自反性（L-1）有aa ，又由（L-5）有aaa ，故由反对称性（L-2）有aa=a。我们只证a(ab)=a。由（L-4）有aa(ab)；再由自反性有aa,又由(L-4)得aba,故由（L-5）有a(ab）a。最后由反对称性可得a(ab)=a。习题10.110.1-1下列各集合对于整除关系都构成偏序集,判断哪些偏序集是格? L=1,2,3,4,5； L=1,2,3,4,6,9,12,18,36； L=1,2,22,2n； L=1,2,3,4,5,6,7,8,9,10。10.1-2试证明在格中若abc,则ab=bc；（ab）（bc）=（ab）（bc）。 10.2 格的代数定义如果是一个格,则“”和“”可看作是集合L上的两个二元运算,它们满足交换律、结合律、等幂律和吸收律。结论的逆也成立，即若在集合L上定义两个二元运算，且这两个二元运算满足以上四条定律，则L上必存在一个偏序关系，使得成为一个格。我们可以给出格作为特殊代数系统的另一种定义。定义10.2-1 设是一个代数系统,和是L上的两个二元运算,如果这两个运算满足交换律、结合律、等幂律和吸收律,则称是一个格(Lattice)。注意 定义中的等幂律可以省略，因为等幂律可以由吸收律推出。例10.2-1 例10.1-1中的格又可表示为。为了要证明定义10.1-2定义的格（称为偏序格(Partially ordered lattice)）与定义10.2-1格（称为代数格(Algebraic lattice)）是等价的，我们先证明如下的重要性质。定理10.2-1 设是格，对于a,bL,则ab=ba bab=a (L-6)证明 设ab=b,由（L-4）有aab，即 ab。因此，再由自反性 aa,于是由（L-5）可得aab；而由(L-4)有aba。因此,由反对称性,得ab=a。设ab=a,则由（L-4）,有a=abb。由自反性 bb,因而由（L-5）,有abb,又由（L-4）,有bab，于是有ab=b。 综合上述可得 ab=b abab=a。由偏序格和代数格的定义及定理10.1-2可知，偏序格及由在L上定义的两个运算ab= glb(a,b)，ab=lub(a,b)，则偏序格一定是代数格。反之，由在代数格上定义的偏序关系：ab当且仅当 ab=b，及定理10.2-1，容易证明代数格一定是偏序格。即有如下的定理。定理10.2-2 偏序格和代数格是等价的。注意 既然偏序格和代数格是等价的，以后就不加区别；格可以看作是一个代数，则可用代数的方法来研究格，即可以研究格的子格及格的同态和同构等格的代数性质以及格的积代数。定义10.2-2 设是一个格,如果是的子代数,则称是的子格(Sublattice)。子格也是一个格,因为当运算和限制在A上时,交换律、结合律和吸收律也是成立的。例10.2-2 设是一个格,其中，如图10.2-1。令,则和是的一个子格, 但不是的子格，这是因为。格除具有交换律、结合律、等幂律和吸收律等主要性质外,格中的元素还有如下一些关系。定理10.2-3 在格中,对于任意的a,b,c,dL,若ac, bd,则abcd，abcd （L-7） 证明 由（L-4）cdc,而ca,所以cda；同理，由cdd,而db,所以cdb,于是由（L-5）有cdab，abcd。ab cd的证明留给读者。推论(格的保序性) 格中,对于任意的a, b,cL,若bc ，则abac，ab ac （L-8）定理10.2-4 在格中,对于任意的a, b,cL，有下列分配不等式成立： a（bc）（ab）（ac） （L-9） a（bc）（ab）（ac） （L-9）证明 由（L-4）bcb,bcc,于是由定理10.2-3的推论有a(bc)ab ,a(bc)ac，再由（L-5）有a(bc)(ab)(ac)。根据对偶原理, 亦成立。习题10.2abdcfeg图10.2-110.2-1 设是一个格，其哈斯图如图10.2-1，L的如下三个子集那个能构成子格？；。10.2-2 至少给出8个S24的子格，使其每个子格至少包含5个元素。10.2-3 设是格，试证明它的线序子集是它的子格。10.2-4. 设是一个格，证明：对于任意的a,b,c,dL,若有，则有 abcd。10.2-5设是一个格，证明：对于任意的a,b,c,dL,则有(ab) (cd)(ac)(bd)。10.3 特殊的格10.3.1 分配格根据定理 10.2-4,我们知道格满足分配不等式,但任意一个格其运算与不一定能满足分配律。定义10.3-1 设是一个格,若对于任意的a, b, cL,有a(bc)=(ab)(ac)，a(bc)=(ab)(ac)则称为分配格(Distributive lattice)。例10.3-1 集合的幂集与其上所定义的并和交运算所组成的格 是一个分配格。例10.3-2 图10.3-1中的(a) ，(b)两个格都不是分配格，这是因为，图10.3-1(a)(c)aabbccddeef(b)abcde在图(a)中 而。在图(b)中 。但 (c)是分配格，为什么？注意 在分配格的定义中有些条件是多余的。定理10.3-1 设在格中,如果交运算对并运算是可分配的,则并运算对交运算也是可分配的；如果并运算对交运算是可分配的,则交运算对交运算也是可分配的。证明 设在格中,对任意的a,b,cL,有a(bc)=(ab)(ac)则 (ab )(ac)）= (ab)a (ab)c=a(ab )c= a (ac )( bc )= a(ac )( bc )= a( bc )由对偶原理,如果并算对交运算是可分配的,则交运算对并运算也是可分配的。定理10.3-2 设是分配格，对于任意的a,b,cL都有ba= ca, ba= ca当且仅当b= c。证明 从右到左的推断是显然的.从左到右的推断，利用交换律，吸收律和分配律,则有b= b(ba)= b(ca)=(bc)(ba)=( cb)(ca)= c(ba)= c(ca)= c 。 10.3.2 有界格和有补格在4.8节中我们给出过偏序集的最大元和最小元的概念，并证明了他们的唯一性。定义10.3-2 设是格，如果L中存在有最小元素和最大元素,分别用0和1来表示,则称格为有界格(Bounded lattice)，并称0、1为格的全下界和全上界。例如图10.3-1中的三个格都是有界格。定理10.3-3 有限格都是有界格。如果一个格有全下界0和全上界1,则对于任意的aL,都有0a1 (L-10)因此，由(L-6)可得，对于任意的aL,都有a1= a (L-11)a0= a (L-11)a0=0 (L-12) a1=1 (L-12)由(L-11)和(L-12)可知，有界格的全下界0是关于并运算的单位元，又是关于交运算的零元；全上界1是关于交运算的单位元，又是关于并运算的零元。设是一个含有元素1和0的格,对于aL,若有元素bL,使得ab=1, ab =0则称元素b是a的补元(Complement of an element)。注意 a和b是互补的。特别地,0和1互补。定义10.3-3 设是有界格,如果L中每一个元素都有补元,则称为有补格(Complemented lattice)。例如,格是一个有补格,其中集合A是全上界,空集F是全下界, A的每一子集Si的补元素是，即Si的补集。例10.3-3图10.3-2中格都是有界格，但都不是有补格。例10.3-4 图10.3-1中格 (a)是有补格，这里的全下界、全上界分别是a、e。显然a、e互为补元，因为bc=a，bc=e，所以b的补元是c，同理因为dc=a,dc=e, 所以d的补元也是c，因此b、d都是c补元。图10.3-1中格 (b)也是有补格，全下界、全上界分别是a、e，a、e互为补元，b的补元是c、d，c的补元是b、d，d的补元是c、b。图10.3-2b(a)0cb1a(c)acd1b0(b)0ac1由此可知有补格中的每个元素都有补元，但补元并不都是唯一的。那么自然会要问：什么格中每一个元素既有补元，且补元又是唯一的呢？10.3.3 有补分配格定义10.3-4 如果一个格既是有补格又是分配格,则称它为有补分配格或称其为布尔代数(Boolean Algbra)。例如,格就是一个有补分配格.而图10.3-1中的三个格都不是有补分配格。有补分配格有一些特殊性质.定理10.3-4 在有补分配格中,任一元素aL的补元素是唯一的。这时将a的补元记作。证明 假设元素a有两个元素b、b1，由补元的定义有ab=1, ab=0；ab1=1, ab1=0则有 ab=ab1, ab=ab1由定理10.3-2 有b= b1.则a的补元唯一.因此，对于任一元素aL有这二式称为互补律。定理10.3-5 (对合律) 在有补分配格中,对于任一元素aL,有。证明 因为,由交换律有.所以a是的补.又由定理10.3-4, 的补是唯一的,故得。定理10.3-6（德摩根定律） 在有补分配格中,对于任意的a,bL,有，。证明 由分配律可知：由补元的唯一性有 。可由对偶原理推出。习题10.310.3-1 设是一个格，其中L=1,2,3,4,6,8,12,24,是整除关系。格是否是有界格，若是请指出其全下界和全上界；若是有界格，则1，3，4，6，8是否都有补元，若有请给出。10.3-2 试举例说明并非每一有补格都是分配格；并非每一分配格都是有补格。10.3-3 设是一个格，试证明：是分配格的充分必要条件是，对于任何的a,b,cL都有(ab)ca(bc)。10.3- 4 设是有补分配格，试证明对于任何的a,bL都有。10.4 布尔代数有补分配格又称为一个布尔代数(Boolean Algbra).而在有补分配格中,每一元素的补元都是唯一的,因此求补运算能够作为这种格（布尔代数）的域上的一元运算,于是,具有域B的布尔代数可表示（这里和是原有的并与交运算,是求补运算）。一个布尔代数具有下列的基本性质：对于B中的任意元素x, y ,z,有：交换律 xy=yx (B-1 xy= yx (B-1) 结合律 x( yz)=(xy)z (B-2)x( yz)=(xy)z (B-2)等幂律 xx=x (B-3)xx=x (B-3)吸收律 x( xy)= x (B-4)x(xy)= x (B-4)分配律 x( yz)=( xy)(xz) (B-5)x( yz)=(xy)(xz) (B-5)同一律 x0= x (B-6)x1= x (B-6)零一律 x1=1 (B-7)x0=0 (B-7)互补律 (B-8) (B-8)对合律 (B-9,9)德摩根定律 (B-10) (B-10)以上这10条性质都可由其中的交换律、分配律、同一律和互补律推导出来。也就是说,若代数系统中的运算满足交换律、分配律、同一律和互补律,则它必定也满足结合律、等幂律等其它6条集合定律。注意 交换律、分配律、同一律和互补律这四条基本定律,每一条都包含了对偶的两个关系式。由交换律和同一律可知,0是运算的单位元,1是运算的单位元,根据例4.8-6,中满足同一律的元素0和元素1是唯一的。在代数系统中交换律、结合律和吸收律成立,因此是一个格,由于分配律成立,可知是一个分配格,又由于同一律和互补律成立,因此是一有补分配格。将布尔代数看作满足一些运算律的一个代数系统,得到其第二定义。定义10.4-1 设是一个代数系统,若该代数系统满足交换律、分配律、同一律和互补律，则称是一个布尔代数(Boolean Algbra)。例10.4-1 设B=0,1,运算,分别用表10.4-1定义：图10.4-1100101010100110011(c)表10.4-1(a)010101111(b)则是一个布尔代数，称为开关代数(Switching Algebra)。如图10.4-1。例10.4-2 设A是一个集合,则是一个布尔代数,称为集合代数(Algebra of Sets)。证明 因为运算,满足交换律,分配律和吸收律,所以是格;又因为运算和互相满足分配律,所以格是分配格,且的全上界是A,全下界是;设全集是A,对于任意的，则A-S是S的补元;所以是一个有补分配格,即布尔代数。A=a,b和 A=a,b,c时的集合代数如图10.4-2(a)和(b)。定义10.4-2 设是布尔代数, SB是B的非空子集,若S0,1并且S对,和运算封闭,则称是的子布尔代数。例如 S=B和S=0,1都是布尔代数的子布尔代数。ba(a)a,ba,b,ca,bb,cca,cab图10.4-2(b)定理10.4-1 布尔代数的每一子布尔代数仍是布尔代数。证明 设是布尔代数的子布尔代数.由子布尔代数的定义可知, 0,1S；由于对, 和封闭，所以，若，则；于是同一律和互补律成立。而交换律、分配律是继承的。由定义10.4-1, 是布尔代数。定理10.4-2 一个布尔代数的满同态像是布尔代数.证明 设是布尔代数在满同态h下的同态像.由同态保持运算性质知:交换律和分配律在中仍然成立.由布尔代数满足同一律，知h(1)和h(0)分别是的全上界元素和全下界元素。即满足同一律,又因为h是从B到B0的满射,因此，对于任一元素x0B0，都存在xB使得h(x)= x0.因此对于任一x0B0，有即是一个布尔代数。例10.4-3 设U=u1, u2, u3.布尔代数有子布尔代数：，它们都是布尔代数有子代数。可以看，以上三例给出的布尔代数都含有2n个元素，事实上这是布尔代数的一般规律，即有：若是有限布尔代数,则存在nN使得。而且我们可以进一步得到如下的定理。定理10.4-3 设是一有限布尔代数,则存在含有n个元素的集合S,使得与同构。习题10.410.4-1 设A=1,2,5,10,11,22,55,110是110的正因子集合,构成偏序集,其中为整除关系。说明该偏序集是否构成布尔代数,为什么?10.4-2 设是一布尔代数,试证明是一个交换群,这里定义为： ab=。10.5 习题解析例10.5-1 设I+ 是正整数集合，是普通的小于等于关系, 试证明是格，并且格中的并运算是max，交运算是min。试证明是分配格。证明 我们知道普通的小于等于关系是偏序关系。又因为，是普通的小于等于关系，所以，对于任意的a,bI+ ，都有ab或ba。若ab，则a,b的最小上界是b，最大下界是a；若ba，则a,b的最小上界是a，最大下界是b。因此，是格。由以上的证明过程可以看出，在格中,a,b的最大下界，最小上界分别是ab= LUB(a,b)=maxa,b, ab= GLB(a,b)=mina,b 对于任意的a,b,cI+，都有如下的6种情况之一：abc； acb； bac； bca； cab； cba。现在对情况证明：a(bc )=( ab)( ac )和a(bc )=( ab)( ac )，事实上a(bc )= maxa, min b, c = maxa, b= b,( ab)( ac )= minmaxa, b, maxa, c= minb, c= b即有a(bc )=( ab)( ac )。由对偶原理有：a(bc )=( ab)( ac )。其它5种情况可类似证明。故格是分配格。例10.5-2 设是格，对于任意的a,b,c,dL,证明：( ab)(cd) (ac)(b d)证明 对于任意的a,b,c,dL,由(L-4)有aba， abb，cdc，cdd， 所以由格的保序性有 ( ab)(cd) ac，( ab)(cd) bd进而有 ( ab)(cd) (ac)(b d)例10.5-3设是格，对于任意的a,b,cL, ab,证明：(a(bc