9学习指导与习题解答-8.doc

第八章 格与布尔代数8.1 基本要求1. 掌握半序格、半序子格、代数格、代数子格的定义，了解半序格和代数格的定义是等价的。2. 掌握互相对偶的两个关系、互相对偶的两个格的定义，了解二者关系。掌握格中表达式、对偶格中的对偶表达式、本格中的对偶表达式的定义，掌握并会应用对偶原理1及对偶原理2。3. 了解格的其它性质，如格的保序性、分配不等式、模不等式等。4. 掌握并会应用格同态映射、格的自同态映射、格同构映射的定义。了解格的同态映射一定是保序映射，同构映射的逆映射也是同构映射等结论。5. 掌握有界格、有余格、分配格以及模格的定义以及相关的结论。了解一个格为模格的充要条件。6. 掌握布尔代数的定义及其16个性质，掌握并会应用Huntington公理来判定一代数系统是否为布尔代数。了解电路代数、集合代数、命题代数、开关代数。掌握并会应用布尔代数的子集是其子代数的充要条件。7. 掌握可唯一表示布尔代数中元素的基底的定义及其性质。掌握极小元的定义及其性质。掌握布尔代数的生成、极小项、多项式、多项范式、布尔代数中一组元素互相独立等概念，了解布尔代数中元素与多项范式的关系和极小项、基底、极小元间的关系。8. 掌握布尔代数中同态、同构的概念及其相应结论。了解如果两个有限布尔代数的维数相同，则这两个代数同构；任意n维布尔代数（B，+，0，1）与开关代数（Bn，+，0n，1n）同构；Stone定理。9. 掌握电路函数、布氏式的概念，了解任意一个电路函数，都可表为一个布氏式。掌握最简多项式、极简多项式的概念。掌握两种得到组成极简多项式的极简项的方法：Quine方法、Karnaugh图法，会应用这两种方法求极简项，对布尔代数进行化简。10. 了解格与布尔代数在计算机科学中的应用。8.2 主要解题方法8.2.1 应用格的性质 这部分习题要求读者熟记格及特殊的格的性质，并能灵活应用。例8.2.1 请判断下面关于格的命题的真假性 设（L，）是格，则（L，）和（L，）均为交换半群。 设（L，）是格，a，bL，那么，ab=a和ab=b至少有一个成立。 设（L，）是格，aL，若a有余元素，那么该余元素是唯一的。 设N为正整数集合，| 为其上的整除关系，则（N，|）为有余分配格。解： 该命题为真命题。因为若（L，）是格，则和均满足交换律、结合律和运算的封闭性，所以（L，）和（L，）均为交换半群。 该命题为假命题。设L=，x,y,x，y，则（L，）是一个格，若令a=x，b=y，则ab=a和ab=b两者均不成立。 该命题为假命题。因为一个元素可能有两个以上的余元素。 该命题为假命题。因为根据有余格的定义，有余格一定是有界格，而（N，|）显然不存在上界，因而不可能是有余分配格。例8.2.2 证明：若一个有界格（L，0，1）含有不只一个元素，则该有界格中任何一个元素的余元素必不是它自身。证明：我们已经知道在有界格中0，1互为余元素。若存在x0，x1，但x以自身为余元素，则有xx=0， xx=1，而又由于xx=x， xx=x，所以，x=0，x=1，即0=1。由题设有界格（L，0，1）含有不止一个元素知，0=1显然是矛盾的。因此，若一个有界格含有不只一个元素，则任何一个元素的余元素必不是它自身。例8.2.3 证明：若一个有限的全序格含有不只两个元素，则这个格必定不是有余格。证明：因为全序关系是特殊的部分序关系，所以可以定义全序关系的格，设为（L，0，1），相应的全序关系为。在全序格中任取非0、1的元素x。由于x0=0，但x0=x1，x1=1，但x1=x0，所以0和1均不是x的余元素。对任意非0、非1的元素y，由全序格中任意两个元素可比较大小知，或者有xy，或者有yx，不妨设前者成立，则xy=x0，因此，x无余元素。即，若一个有限的全序格含有不只两个元素，则其中非0、非1元均无余元素，故不是有余格。例8.2.4 设（L，0，1）是有界格，相应的部分序关系是，证明：对于a，bL，（1）若ab=0，则a=b=0，（2）若ab=1，则a=b=1。证明：（1）因为aab，由题设ab=0，所以a0。另一方面，因0是L上的最小元，有0a。由的反对称性知，a=0。同理可证b=0。（2）因为aba, 由题设ab=1，所以1a。另一方面，因1是L上的最大元，有a1。由的反对称性知，a=1。同理可证b=1。也可用对偶原理证。8.2.2 子格的判断 判断一个格中的一个子集是其格的办法是根据格的定义来进行判断，即证明该子集中任意两个元素构成的集合的最小上界和最大下界都在该子集中，即运算封闭。 例8.2.5 设（L，0，1）是有界分配格，证明：L中拥有余元素的的各元素构成一个代数子格。证明：设L中拥有余元素的的各元素构成的集合为L，对于任意的a，bL，它们的余元素分别记为a和b。首先考察ab，因为(ab)(ab)=(aba)(abb)=00=0(ab)(ab)=(aab)(bab)=11=1所以ab有余元素ab，abL。同理，ab有余元素ab，所以，abL。因此，L对运算，封闭，故L是L的代数子格。例8.2.6 设（L，+）是格，L是L的非空子集，如果： 对于任意的a，bL，有a+bL; 对任意的aL和任意xL，若xa，则xL。那么称L是格L的理想。试证明：格L的理想是一个子格。证明：根据（1），有L对运算+是封闭的。因为（L，+）是一个格，L是L的子集，所以对任意的a，bL，有aba，再根据（2），得abL。因此L对运算亦封闭。故格L的理想是一个子格。例8.2.7 设f是格（L，+）到格（S，）的同态映射，试证明（L，+）的同态象是（S，）的子格。证明：（L，+）的同态象是f(L)=f(x)|xL。任取s1，s2f(L)，则有l1，l2L，满足f(l1)=s1，f(l2)=s2。由f是格（L，+）到格（S，）的同态映射，知：s1s2 = f(l1)f(l2) = f(l1l2)，s1s2 = f(l1)f(l2) = f(l1+l2)。由（L，+）是格知，l1l2L，l1+l2L，因此，f(l1l2)f(L)，f(l1+l2)f(L)，即，s1s2f(L)，s1s2f(L)，故，f(L)对运算和封闭。（L，+）的同态象是（S，）的子格。8.2.3 格的同态判断一映射为格的同态映射，需注意验证加同态与乘同态两条。要记住格的同态映射一定是保序映射，但保序映射未必是同态映射。例8.2.8 设（L，+）是一分配格，aL，设f(x)=x+a，xL，g(x)=xa，xL，证明：f和g都是（L，+）到自身的格同态映射。证明：对任意的x，yL，有：f(x)+f(y)=(x+a)+(y+a) = (x+y)+a =f(x+y) f(x)f(y)= (x+a)(y+a) =(xy)+a L是分配格 = f(xy)。因此，f是（L，+）到自身的格同态映射。同理可证，g是（L，+）到自身的格同态映射。例8.2.9 设f是格（L，1）到格（S，2）的满同态映射。证明：若（L，1）是有界格，则（S，2）也是有界格。证明：因（L，1）是有界格，设最大元为1，最小元为0。令f(1)=1,f(0)=0，则1，0S。因f是满设，故对任意的xS，都有xL，使得f(x)=x。又因为f是同态映射，因此亦是保序映射，故由01x11，有f(0)2f(x)2f(1)，即02x21，这就是说1和0分别是（S，2）的最大元和最小元。因此，（S，2）是有界格。例8.2.10 设（L，+）是一个分配格，相应的部分序关系为，a，bL。设R=x|xL，abxa，S=y|yL，bya+b，令f(x)=x+b，xR，g(y)=ya，yS。试证明：f和g是R与S之间一对互逆的格同构映射。证明：（1）首先证明f是R到S的映射，g是S到R的映射。任取xR，由R的定义知，abxa。因此，（ab）+bx+ba+b，而（ab）+b=b，f(x)=x+b，故bf(x)a+b，由S的定义知，f(x)S。所以，f是R到S的映射。任取yS，由S的定义知，bya+b。因此，abaya(a+b)，而a(a+b)=a，g(y)=ya=ay，由交换律。故abg(y)a，由R的定义知，g(y)S。所以，g是S到R的映射。(2)往证f和g都是1-1映射而且互为逆映射。任取xR，有 g(f(x)=(x+b)a 由f,g定义 =(xa)+(ba) 由L是分配格 =x+(ba) 由xa =x+(ab) 由交换律 =x 由abx任取yS，有 f(g(y)=(ya)+b 由f,g定义 =(y+b)(a+b) 由L是分配格 =y(a+b) 由by =y 由ya+b因此，f和g都是1-1映射而且互为逆映射。（3）往证f是R到S的格同态映射，g是S到R的格同态映射。显然，（R，+）和（S，+）均是格。任取x,yR，有f(x)+f(y)=(x+b)+(y+b) =(x+y)+b =f(x+y),f(x)f(y)= (x+b)(y+b) = (xy)+b =f(xy)，所以，f是R到S的格同态映射。任取x,yS，有g(x)+g(y)=(xa)+(ya) =(x+y)a =g(x+y),g(x)g(y)= (xa)(ya) = (xy)a =g(xy)，所以，g是S到R的格同态映射。综上，f和g是R与S之间一对互逆的格同构映射。下面是一道综合题，考察读者对第一章介绍的等价类、第六章介绍的二元代数运算的概念及本章中的代数格、格同构映射等概念的理解。注意证明一个映射是格同构映射，它必须是1-1映射而且是格同态映射。例8.2.11 设f是（L，1，1）到（S，2，2）的格同态映射。考虑商集L/f=a|aL，其中a=x|xL且f(x)=f(a)。在L/f上规定运算和如下：对任意的a，bL/f，定义ab=a1b，ab=a1b。证明：（1）和是L/f上的二元代数运算。（2）（L/f，）是一个代数格。（3）令g：af(a)，aL/f，则g是L/f到f(L)的格同构映射。证明：（1）任取x，yL，规定xyf(x)=f(y)。显然，是L上的等价关系，其等价类集合就是L/f。由和的定义，运算封闭性显然。对任意的a1，a2，b1，b2L，若a1=a2，b1=b2，往证a1b1= a2b2。由a1=a2，b1=b2，知f(a1)=f(a2)，f(b1)=f(b2)。又因f是同态映射，所以f(a11b1)=f(a1)2f(b1)=f(a2)2f(b2)=f(a21b2)。因此， a11b1=a21b2。再由的定义ab=a1b，得a1b1= a2b2。同理可证a1b1=a2b2。这说明运算和与等价类的代表选取无关，它们确实是L/f上的二元代数运算。（2）根据1，1具有交换律、结合律、吸收律，不难验证和也具有这些性质。从而，（L/f，）是一个代数格。例如，任取a，bL，则ab=a1b=b1a=ba，ab=a1b=b1a=ba。故，满足交换律。（3）首先证明（f(L)，2，2）是（S，2，2）的子格。任取a,bf(L)，存在a，bL，使得a=f(a),b=f(b)。于是，由f是同态映射，得a2b=f(a)2f(b)= f(a1b)f(L)，a2b=f(a)2f(b)= f(a1b)f(L)，因此，（f(L)，2，2）是（S，2，2）的子格。再证明g是L/f到f(L)的1-1映射。任取a，bL/f，有a=bf(a)=f(b)，故g是L/f到f(L)的映射且是单射，又，显然g是L/f到f(L)的满射，因而为1-1映射。最后证明g是L/f到f(L)的同态映射。任取a，bL/f，有g(ab)=g(a1b)=f(a1b)=f(a)2f(b)= g(a)2g(b)，g(ab)=g(a1b)=f(a1b)=f(a)2f(b)= g(a)2g(b)。综上，g是L/f到f(L)的格同构映射。8.2.4 布尔代数布尔代数是特殊的格-有余分配格，故格、分配格、有余格所具有的性质，它都有，要熟记其性质并灵活应用。正是由于其特殊性，布尔代数间同态映射的要求更严格了。还要注意到布尔代数的子代数一定含有原布尔代数的最大、最小元，并且应该保持原来的运算，一个元素若在子代数中，它的余元素也一定在该子代数中。布尔代数的化简问题教材中讲得比较详细，在此不再赘述。例8.2.12 设f是布尔代数（B，+，0，1）到布尔代数（S，）的同态映射，令L=f-1()=x|xB，f(x)=，试证明：（1）0L。（2）若bL，则对任意的xB，只要xb，就有xL。（3）对于任意的x,yL，有x+yL。证明：（1）因为f(0)=f(0)= f(0) f() 由f是同态映射= f(0) （f(0)） 由f是同态映射=，所以，由L的定义知，0L。（2）因为bL，所以，f(b)= 。对任意的xB，若xb，则x+b=b，于是，f(x+b)=f(b) = 。另一方面，由f是同态映射知，f(x+b)=f(x)f(b) =f(x)。因此，有f(x)=，故f(x)=，即xL。（3）任取x,yL，有f(x)=，f(y)=。于是，f(x+y)=f(x)f(y)= =，故x+yL。例8.2.13 给出含有8个元素的布尔代数的全体子代数。解：由教材中定理8.5.8（Stone定理）知，若取A=a,b,c，则8个元素的布尔代数必同构于（A）,）。故，只需给出（A）,）的全部子代数。（A）=，a,b,c,a,b,a,c,b,c,a,b,c。注意到它的子代数必然含有最小元，和最大元a,b,c。a和b,c互为余元素，b和a,c互为余元素，c和a,b互为余元素。故全部子代数为：，a,b,c，a，b,c，a,b,c，b，a,c，a,b,c，c，a,b，a,b,c，a,b,c,a,b,a,c,b,c,a,b,c。例8.2.14 设（L，0，1）是一个布尔代数，如果在L上定义二元运算+如下：a+b=(a(b)(a)b)证明：（L,+）是一个交换群。证明：由于，这三个运算在L上都是封闭的，所以，+在L上也是封闭的。（1）往证运算+满足结合律。任取a,b,cL，有（a+b）+c=(a(b)(a)b)+c =(a(b)(a)b)(c)(a(b)(a)b)c) =(a(b)(c)(a)b(c)(a)b)(a(b)c) =(a(b)(c)(a)b(c)(abc)(a)(b)c)，同理可证a+（b+c）=(a(b)(c)(a)b(c)(abc)(a)(b)c)，所以，（a+b）+c= a+（b+c），即运算满足结合律。故（L,+）是半群。（2）往证运算+满足交换律。由，运算满足交换律，得a+b=(a(b)(a)b) =（b(a)）（(b)a） = b+a,故运算+是可交换的。（3）往证（L,+）有壹（单位元）。任取aL，有a+0=0+a=（0(a)）（(0)a）=0(1a)=0a=a，故，0是（L,+）的单位元。（4）往证L中任意元素有逆。任取aL，有a+a=（a(a)）（(a)a）=00=0，故L中每个元素都以自身为逆元素。综上，（L,+）一个交换群。例8.2.15 设（L，0，1）是一个布尔代数，相应的部分序关系为“”。若a,b1,b2,br是极小元素，试证明：ab1b2br 当且仅当 存在i，1ir，a=bi。证明：（必要性）用反证法。假设对任意的i，都有abi。由ab1b2br 有 a=a(b1b2br ) =(ab1)(ab2)(abr) =000 =0，而a为极小元素，由极小元素的定义知，a0，这就产生了矛盾。因此，一定存在i，1ir，a=bi。（充分性）若存在i，1ir，a=bi，则由于bib1b2br ，故ab1b2br。说明：此例的必要性部分使用了关于极小元素的一个结论（教材中结论8.5.3），即，若（L，0，1）是一个布尔代数，a，b为该布尔代数中的两个不同的极小元素，则必有：ab=0。例8.2.16 设（L，0，1）是一个有限布尔代数，相应的部分序关系为“”, aL，且a0。试证明：必存在极小元素b，使得ba。证明：若a是L的极小元素，则取b=a即可。否则，必存在b1L，使得0b1a（注：用b1a表示b1a，但b1a），若b1为极小元素，则得证，否则，必存在b2L，使得0b2b1a，若b2为极小元素，则得证，否则，继续这一过程。由于（L，0，1）是一个有限布尔代数，经过有限步后必找到br ，使得0brb2b1a，且br 是极小元素。于是，取b=br ,则b是极小元素，且ba。例8.2.17 设（L，0，1）是一个有限布尔代数，相应的部分序关系为“”, b1,b2,br是该布尔代数的所有极小元素。对于任意的aL，证明：a=0当且仅当对于每个i（i=1,2,r），都有abi=0。证明：（必要性）显然成立。（充分性）已知对于每个i（i=1,2,r），都有abi=0，使用反证法，假设a0，由例8.2.15的结论知，必存在极小元素bj，使得bja。于是，bjabj，而abj=0，故bj=0，这与极小元素bj0矛盾。因此，a=0。下面我们用布尔代数的定义来验证一个代数系统是布尔代数。例8.2.18 设f是布尔代数（L，1，1，0，1）到（S，2，2，）的同态映射。考虑商集L/f=a|aL，其中a=x|xL且f(x)=f(a)。在L/f上规定运算，和如下：对任意的a，bL/f，定义ab=a1b，ab=a1b，a=a。证明：（L/f，0，1）是一个布尔代数，并且L/f同构于f(L)。证明：（1）往证（L/f，）是一个代数格。f是布尔代数（L，1，1，0，1）到（S，2，2，）的同态映射，当然也是（L，1，1）到（S，2，2）的同态映射，由例8.2.11知，L/f是一个等价类集合，和是L/f上的二元代数运算，且（L/f，）是一个代数格。（2）往证（L/f，）是一个分配格。任取a，b，cL/f，有a(bc)=a1(b1c)=(a1b)1(a1c) =(ab)(ac)。类似可证，a(bc)= (ab)(ac)。所以，（L/f，）是一个分配格。（3）往证（L/f，0，1）是一个有余格。因为，对任意的aL/f，有a0=a10=a，a1=a11= a，所以，0和1分别是L/f的最小元和最大元。又，对任意的a，bL/f，若a=b，则f(a)=f(b)。于是， f(a)=f(b)，故有a=b，即a=b。这说明运算与等价类a的代表a的选取无关，从而确定是L/f上的一元运算。对于任意的aL/f，有a(a)=aa=a1a=1，a(a)=aa=a1a=0，故，a是a的余元素，是L/f上的余运算。综上，（L/f，0，1）是一个布尔代数。（4）往证（f(L)，2，2，）是（S，2，2，）的子代数。任取aL，因为f是同态映射，必有f(1)=f(a1a)=f(a)2f(a)=，f(0)=f(a1a)=f(a)2f(a)=，因此，f(L)。又任取x,yf(L)，则存在a,bL，使得x=f(a),y=f(b)。于是x2y= f(a)2f(b)=f(a1b)f(L)，x2y= f(a)2f(b)=f(a1b)f(L)，=f(a)f(L)，因此，f(L)关于运算2，2和都是封闭的。故（f(L)，2，2，）是（S，2，2，）的子代数。（5）定义g：af(a)，aL/f，则由例8.2.11知，g是L/f到f(L)的1-1映射，且对任意的a，bL/f，有g(ab)=g(a)2g(b)，g(ab)=g(a)2g(b)，又，g(a)=g(a)=f(a)= =，故，g是布尔代数（L/f，0，1）到（f(L)，2，2，）的同构映射，从而，L/f同构于f(L)。例8.2.19 设f是布尔代数（L，1，1，0，1）到（S，2，2，）的同态映射。L/f及L/f上的运算，和如例8.2.18，令g：aa，aL，证明：g是布尔代数L到L/f的满同态映射，这个g称为L到L/f的自然同态。证明：例8.2.18已经证明（L/f，0，1）是一个布尔代数。由g定义，显然g是L到L/f的满射。任取a，bL，有 g(a1b)=a1b=ab=g(a)g(b)，g(a1b)=a1b=ab=g(a)g(b)，g(a)=a=a=g(a)。因此，g是布尔代数L到L/f的满同态映射。例8.2.20 设f是布尔代数（L，1，1，0，1）到（S，2，2，）的满同态映射。L/f及L/f上的运算，和如例8.2.18，g为L到L/f的自然同态(见例8.2.19)。证明：存在唯一的L/f到S的同构映射h，使得f=hg。证明：往证存在性。令h：af(a)，aL/f，则由例8.2.18，知，h是布尔代数（L/f，0，1）到（f(L)，2，2，）的同构映射，又由f是布尔代数（L，1，1，0，1）到（S，2，2，）的满同态映射，知，f(L)=S。因此，h是布尔代数（L/f，0，1）到（S，2，2，）的同构映射。对于任意aL，有（hg）（a）=h(g(a)=h(a)=f(a)，因此，f=hg。往证唯一性。假设h也是L/f到S的同构映射，且使得f=hg。那么，对于任意的aL/f，有h(a)=h(g(a)=(hg)(a)=f(a)=h(a)，可见，h=h。因此，使得f=hg的L/f到S的同构映射h是唯一的。 此例中还用到了映射乘积的概念。8.3 第八章习题解答8.3.1 习题8.2解答1. 设S是所有命题做成的集合，说明S在什么运算下做成代数格？在什么部分序下做成半序格。解：S在合取运算()和析取运算()下做成代数格。不难验证这两种运算有交换律、结合律、吸收律。S在蕴涵()这个部分序下做成半序格。ABAB=A且AB=B.2. 设(L，*，)是一个格，a,bL。令S=x|(xL)(axb)其中是与(L,*, )等价的半序格中的部分序。证明：(S, *，)是L的子格。设c，dS,则c,dL，且ac,db所以 ac*d 而显然有c*dbcdb acd故S对*，运算封闭即(S，*，)是L的子格。3. 设D是集合S上的整除关系。以下部分序集是否为格：(1) S = 1，2，3，4，6，12(2) S = 1，2，3，4，6，8，10，12(3) S = 1，2，3，4，5，6，7，8，9，10(4) S = 2，3，6，12，24，36 解：（1）和（4）是格。8.3.2 习题8.3解答1. 设(L，)是格，若a,b,cL,abc，则ab=b*c(a*b)(b*c)=(ab)*(ac)证明：因abc故ab=b=b*c a*b=a,b*c=b,ab=b,ac=c故(a*b)(b*c)=(ab)=b (ab)*(ac)=b*c=b即(a*b)(b*c)=(ab)*(ac).2. 设(L,)是格，若a b,cd,a,b,c,dL,则a*cb*d acbd证明：(a*c)*(b*d)=a*c*b*d=(a*b)*(c*d)=(a*c)故a*cb*d,(ac)(bd)=acbd=(ab)(cd)=bd,故acbd.3. 设(L，)是一个格。证明：(a*b) (c*d)(ac)*(bd);(a*b) (b+c)(c*a)(ab)*(bc)*(ca)证明：(a*b) (c*d)(a*b) (c)*(a*b) d(ac)*(bc) (ad)*(bd)(ac)*(ad)*(bd)*(bc)(ac)*(bd)(a*b) (b*c)(c*a)(a*b) (a*b)c)(c*a)=b*(a*b) c)(c*a)(b*(a*b) c)c*(b*(a*b)c)a(bc)*(a*b)c)c)*(ba)*(a*b)c)a=(bc)*(a(a*bc)*(ab)*(a*b)c(bc)*(ab)*(ac)*(bc)=(ab)*(bc)*(ca)4. 若(L，)是有限格，则L中必有最大最小元素。证明：L有限，可设L=a1,a2,an与其等价的代数格记为(L，*，),则a=a1*a2*anL b=a1a2anL不难看出，对任aiL，有aaib，即L中最大最小元素分别为a,b。5. 举例说明，对于两个格L和S，g是L到S的保序映射，但g不是同态映射。解：设S=a,b,c,d,e，其半序如图8.3.1所示，易见S是格，令S=P(S)，,则S也是格，令g:xg(x)=y|yS,yx,g(a)=S,g(b)=b,e,g(c)=c,e,g(d)=d,e,g(e)=e.当xy时，显然有g(x)g(y),即g是格S到S的保序映射。但在S中，bc=a,而g(b)g(c)=b,c,e g(bc)=g(a)=S.可见g(bc)g(b)g(c)，即g不是同态映射。ceabd 图8.3.16. 令S=所有正偶数集合。证明：(I+，D)与(S，D)同构。 证明：对任意nI+，规定I+到S的映射：g:n2n显然此映射是一对一的。与这两个格等价的代数格的*，运算都是求最大公因和最小公倍。对任n1,n2I+,n1*n2为其最大公因，记为d.而2n1,2n2S,2n1*2n2为2n1和2n2的最大公因。为2d 。故g(n1*n2)=g(d)=2d=2n1*2n2=g(n1)*g(n2).同理可证g(n1n2)=g(n1)g(n2)即g是同态映射，故(I+，D)和(S，D)同构。7. 证明：4个元素的格(L，*，)必同构于格(I4，)或者格(S6，D)。证明：设4个元素的格L=a1,a2,a3,a4，L有限，故必有最大，最小元素，不妨设为a4,a1,则a1a2,a3a4。其中，a2,a3有两种可能：(1)a2a3(a2,a3有关系，不妨设为如此)则成为链，因此与(I4，)同构。(2)a2,a3没有关系，则此格与(S6，D)同构.8. 证明：格(E，)和格(O，)同枸。其中，E是正偶数集。O是正奇数集。是数的小于等于关系，给出的同构映射是否格(E，D)和格(O，D)之间的同构映射？其中D是整除关系。证明：规定(E，)到(O，)上的映射g:mm-1，mE。这显然是一对一的。与这两格等价的代数格的*，运算即求两个数中最大，最小者的运算。对任m1,m2E，不妨设m1m2有 g(m1*m2)=g(m1)m1-1=g(m1-1)*(m2-1)=g(m1)*g(m2)g(m1m2)=g(m2)=m2-1=(m1-1) (m2-1)=g(m1) g(m2)因此格(E，)和格(O，)同构。此映射不是关于(E，D)和(O，D)的同构映射。例：在该映射中65，34，而与(E，D)和(O，D)等价的代数格中的乘加运算分别是求最大公因和最小公倍的运算。若记两格中的乘运算分别为*1和*2。则有g(6*13)=g(3)=2，而g(6)*2g(3)=5*22=1，因此，g不是关于(E，D)和(O，D)的同构映射。9. 设(L，*，)，(S，)是两个格，证明：若g是L到S上的一一映射，则g是同构映射的充要条件是g与g-1是保序映射。证明：)若g是L到S上的同构映射，则显然g-1存在并且是S到L上的同构映射，而同构映射当然是同态故保序。)设a,bL,a,bS且有g(a)=a，g(b)=b,a*b=c,ab=c，则ca,cb。由g是保序的，所以g(c )a,g( c)b，因此g(c)(ab)，即g(c)c。由ab=c，我们又得到ca cb。由g-1是保序的，得g-1( c)a,g-1(c)b。于是gg-1( c)g(c)，所以c=g (c)，即cg (c)。所以c=g(c)，即g(a*b)=g(c)=c=ab=g(a) g(b)。同理可得，g(ab)=g(a)g(b).故g是同构映射。10. 设(L，*，)是有限格，g是L到L的映射。如果对a,bL，有g(a*b)=g(a)*g(b)，则必有eL,使得g(e)=e。证明： 由g(a*b)=g(a)*g(b)，不难推得对任m有g(a1*a2*am)=g(a1)*g(a2)*g(am)。取L中任一元，记为a1,g(a1)=a2,若a2=a1,则取e=a1，得证.否则,令a3=g(a2)，如此下去，必有两种可能:()对某个j出现g(aj)=aj(1jn),则e=a，j得证。()g(aj)=ai其中1ij.因此,令e=ai*ai+1*ajg(e)=g(ai*ai+1*aj)=g(ai)*g(ai+1)*g(aj)=ai+1*ai+2*aj*ai=e原命题成立。11. 证明：8.3中定理8.3.7的推论。证明：由定理8.3.7，g-1是S到L上的同构映射当然也是同态映射。因此g和g-1都是保序的。8.3.3 习题8.4解答1证明：在有余分配格（L，）中，对任意a，bL，有abab= 0baab= 1abba 证明：abab=0)ab， ab=a，ab=(ab)b=a(bb)=a0=a)ab=(ab)0=(ab)(ab)=a(b+b)=a1=a故ab)ba， ba=a，ab=(ba)b=a(bb)=a1=1)ab=(ab)1=(ab)(ab)=a(bb)=a0=aba。abbaabab=aab=aba2. 证明：在格(L，)中，若第一分配律成立，不用对偶原理可推出第二分配律，反之亦然。证明：由第一分配律证第二分配律。亦即已知a(bc)=(ab)(ac)成立，往证a(bc)=(ab)(ac)。(ab)(ac)=(ab)a)(ab)c)=a(ac)(bc)=(a(ac) (bc)=a(bc)同理可由第二分配律证第一分配律。3. 证明： 8.4中的引理1，引理2引理1 设(L，)是一个格，若S是L的任意一个有限非空子集，则S有一个最大下界和一个最小上界。证明：设S=S1，S2，Sn令m=S1S2Sn，M=S1S2Sn。其中，是与格(L，)中“”关系等价的最大下界和最小上界运算。由，的封闭性，显然m,ML.任取SkS,则Skm=SkS1SkSn=S1Sn=mmSkm是S的一个下界。取m为S的任意下界，mS1,mS2,mSnmS1S2Sn=mm=S1S2Sn是S的最大下界。同理SkM=SkS1SkSn=S1Sn=M，SkM，M是S的一个上界。任取S的上界M，S1M,S2M,SnMM=S1S2SnMM是S的最小上界。引理2 若(L，0，1)是有界格。对任意aL，则恒有a0=a,a1=aa1=1,a0=0证明：对任aL,a1 a1=a,a1=10a a0=0,a0=a。4设（L，）为模格，试证明若有（ab） c = bc则有 （cb）a = ba。证明：一方面，由cbb知，(cb)aba。另一方面,(cb)a(cb)(ab) 由（L，）为模格，且bab，知(ab)(bc) = b(ab)c)而(ab)(bc)= (cb)(ab)，且由已知，（ab）c = bc，得：(cb)a(cb)(ab)=(ab)(bc) = b(ab)c) = b(bc)=b，因此,(cb)ab，又显然，(cb)aa，因此，(cb)aba。综上(cb)a=ba.8.3.4 习题8.5解答1. 设(B，+，-，0，1)是布尔代数，定义B上两种代数运算如下：ab=abab=ab于是，称代数(B，, )为布尔环。证明：在布尔环中，有如下性质：aa=0aa=a+a=0+0=0a0=aa0=a+0=a1+0=a+0=aa1=a1=a+1=a0+1=0+=a(bc)=(ab) (ac)a(bc)=a(b+c)=ab+ac)(ab) (ac)=(ab) (ac)=(ab)()a=bab=0 ab=aa=0 ab=0 a+b=0 a=a1+0=a(b+)+a+b=ab+a+b=(ab+b)+a=(a+)b+a=b+a故a(ab)=a(a+b)=a+0=a又a(ab)=a0=0ab=b=a=0+故若ab=0,则ab=a+bab=若ac=b，则a=b由有：(ac)(bc)=0即acbc=(ab)(cc)=abc=ab=0再由因ab=0, a=b.2. 证明：8.5中引理2，3，4。引理2 设f是布尔代数(B，+，-，0，1)到布尔代数(S，a，b)的一个映射，如果对任意a,bB,都有：f(ab)=f(a) f(b)f(a)=f(a)则f是B到S的同态映射。证明：f(a+b)=f(0)=f(1)=引理3 设f是布尔代数(B，+，-，0，1)到布尔代数(S，a，b)的一个映射，如果对任意a,bB,都有：f(ab)=f(a) f(b)f(a+b)= f(a) f(b)则(f(B), ，,f(0),f(1)是一个布尔代数，且f是B到f(B)的同态映射。其中是关于f(0),f(1)的余运算。证明：要验证f(B)仍是布尔代数，利用逆象。设a，b，gf(B)，则必有a,b,cB，使f(a)=a,f(b)=b,f(c)=g。因B中有交换律、结合律、吸收律和分配律利用逆象容易验证f(B)中也有上述四条规律。又0a=a 1a=a，f(0)f(a)=f(0a)=f(0)，故f(0)f(a)=a。f(1)f(a)=f(1a)=f(a)，故f(a)f(1)，即af(1)。由a的任意性知，f(0),f(1)分别为f(B)中的最小、最大元素。f(a) f()=f(a+)=f(1)f(a) f()=f(a)=f(0)根据余元素的定义。任意f(a)= af(B)有余元素。f(B)是有余分配格即是布尔代数由布尔代余元素的唯一性知对f(1)和f(0)有故f是B到f(B)的同态映射。引理4 设(B，+，-，0，1)和(S，a，b)是两个布尔代数，