离散数学习题解答(第五章)格与布尔代数.doc

【精品文档】如有侵权，请联系网站删除，仅供学习与交流离散数学习题解答(第五章)格与布尔代数.精品文档.离散数学习题解答习题五（第五章 格与布尔代数）1设L，是半序集，是L上的整除关系。问当L取下列集合时，L，是否是格。 a) L=1，2，3，4，6，12b) L=1，2，3，4，6，8，12c) L=1，2，3，4，5，6，8，9，101263124解 a) L，是格，因为L中任两个元素都有上、下确界。b) L，不是格。因为L中存在着两个元素没有上确界。 例如：8Å12=LUB8，12不存在。8631241210c) L，不是格。因为L中存在着两个元素没有上确界。842698731510 倒例如：4Å6=LUB4，6不存在。2设A，B是两个集合，f是从A到B的映射。证明：S，是2B，的子格。其中S=y|y=f (x)，x2A证 对于任何B1S，存在着A12A，使B1=f（A1），由于f(A1)=y|yB($x)(xA1f (x)=y)B 所以B12B，故此S2B；又B0=f (A)S (因为A2A)，所以S非空；对于任何B1，B2S，存在着A1，A22A，使得B1=f (A1)，B2=f (A2)，从而LBB1，B2=B1B2=f (A1)f (A2) =f (A1A2) （习题三的8的1）由于A1A2A，即A1A22A，因此f (A1A2)S，即上确界LBB1，B2存在。对于任何B1，B2S，定义A1=f 1(B1)=x|xAf (x)B1，A2=f-1(B2)=x|xAf (x)B2，则A1，A22A，且显然B1=f (A1)，B2=f (A2)，于是GLBB1，B2=B1B2=f (A1)f (A2)f (A1A2) （习题三的8的2）又若yB1B2，则yB，且yB2。由于yB1=f (A1)=y|yB($x)(xA1f (x)=y)，于是存在着xA1，使f (x)=y，但是f (x)=yB2。故此xA2=f-1(B2)=x|xAf(x)B2，因此xA1A2，从而y=f (x)f (A1A2)，所以GLBB1，B2=B1B2=f (A1)f (A2) f (A1A2)这说明 GLBB1，B2=B1B2=f (A1)f (A2)=f (A1A2)于是从A1A22A可知f (A1A2)S，即下确界GLBB1，B2存在。因此，S，是2B，的子格。3设L，是格，任取a，bL且ab。证明B，是格。其中B=x|xL 且 axb证 显然BL；根据自反性及abb所以a，bB，故此B非空；对于任何x，yB，则有axb及ayb，由于x，yL，故有z1=xÅy为下确界L存在。我们只需证明z1，z2B即可，证明方法有二，方法一为：由于ax，所以aÅx=x，于是z1=xÅy =(aÅx) Åy （利用aÅx=x） =aÅ (xÅy) （由Å运算结合律） 因此az1；另一方面，由yb可知yÅb=b，由xb可知xÅb=b，于是z1Åb=(xÅy) Åb=xÅ(yÅb) （由Å运算结合律）=xÅb （利用yÅb=b）=b （利用xÅb=b）因此 z1b，即 az1b 所以z1B由于ax及ay，所以a*x=a，a*y=a，因而a*z2=a* (x*y)=(a*x) *y （由*运算结合律）=a*y （利用a*x=a）=a （利用a*y=a）因而az2；又由于yb，所以y*b=y 于是z2=x*y=x* (y*b)=(x*y) *b （利用*运算结合律）=z2*b从而z2b，即az2b 所以z2B 因此B，是格（是格L，的子格）。方法二：根据上、下确界性质，由ax，ay，可得ax*y，（见附页数）4设L，*，Å是格。"a，bL，证明：（附页）axÅy，即az2，a又由xb，yb，可得xÅyb，x*yyb，即z1b，z2b所以az1b，az2b，故此z1，z2Ba*ba且a*bbÛa与b是不可比较的。证 先证Þ用反证法，假设a与b是可比较的，于是有ab或者ba。当ab时，a*b=a与a*ba（得a*ba）矛盾；当ba时，a*b=b与a*bb（得a*bb）矛盾；因此假设错误，a与b是不可比较的。次证Ü由于a*ba，a*bb。如果a*ba，则ab，与a和b不可比较的已知条件矛盾，所以a*ba，故此a*ba；如果a*b=b，则ba，也与a和b不可比较的已知条件矛盾，所以a*bb，故此可得a*bb。5设L，*，Å是格。证明： a) (a*b) Å (c*d)(aÅ c) * (bÅ d)b) (a*b) Å (b*c)(c Å a)(aÅb) * (bÅc) * (cÅa)证 a) 方法一，根据上、下确界的性质，由a*baaÅc及a*bbbÅd 所以得到a*b(aÅc) * (bÅd)又由 c*dcaÅc及c*ddbÅd，所以得到c*d(aÅc) * (bÅd)因此(a*b) Å (c*d) (aÅc) * (bÅd)方法二 (a*b) Å (c*d) (aÅc) * (aÅd) * (aÅc) * (bÅd) （分配不等式，交换律，结合律，保序性） (aÅc) * (bÅd) （保序性） b) 方法一，根据上、下确界的性质由a*baaÅb，a*bbbÅc，a*bacÅa可得 a*b(aÅb) * (bÅc) * (cÅa)同理可得 b*c(aÅb) * (bÅc) * (cÅa)及 c*a(aÅb) * (bÅc) * (cÅa)所以 (aÅb) Å (bÅc) Å (cÅa)(aÅb) * (bÅc) * (cÅa) 方法二：(aÅb) Å (bÅc) Å (cÅa) b* (aÅc) Å (c*a) （交换律，结合律，分配不等式，保序性） bÅ (c*a) * (aÅc) Å (c*a)（分配不等式，交换律，） (aÅb) * (bÅc) * (aÅc)（分配不等式，结合律，交换律，吸收律，保序性） (aÅb) * (bÅc) * (cÅa) （结合律）6设I是整数集合。证明：I，min，max是分配格。证 由于整数集合I是全序集，所以任何两个整数的最小者和最大者是存在的，因此I，min，max是格是格是显然的。下面我们来证I，min，max满足分配律对于任何a，b，cI 有a* (bÅc)=mina，maxb，c(a*b) Å (a*c)=minmina，b，mina，c（1）若bc时，当 （a） ab，则ac ，故此 mina，maxb，c=mina，c=a maxmina，b，mina，c=maxa，a=a （b）bac ，则 mina，maxb，c=mina，c=a maxmina，b，mina，c=maxb，a=a （c）ca，则ba，因此 mina，maxb，c=mina，c=c maxmina，b，mina，c=maxb，a=c（2）若cb时，当 （a）ac，则ab，故此 mina，maxb，c=mina，b maxmina，b，mina，c=mina，a=a（b）cab，则 mina，maxb，c=mina，b=a maxmina，b，mina，c=maxa，c=a （c）ba，则ca，因此 mina，maxb，c=mina，b=b maxmina，b，mina，c=maxb，c=b综合（1）（2）总有 a* (bÅc)=(aÅb) * (aÅ c)根据对偶原理，就还有 aÅ (b*c)=(aÅb) * (aÅc)因此I，min，max是分配格。7设A，*，Å，max是分配格，a，bA且ab。证明： f (x)=(xÅa) *b是从A到B的同态函数。其它 B=x|xA且axb证 由于axÅa，及已知ab，所以a(xÅa)*b；其次(xÅa)*bb，所以af (x) b，因而f (x)是从A到B的函数。对于任何x，yA，f(xÅy)=(xÅy)Åa)*b =(xÅa) Å (yÅa) *b（幂等律，交换律，结合律） =(xÅ*a)b)(yÅa) *b)（分配律） =f (x) Åf (y)f (x*y) =(x*y) Åa) *b =(xÅa) * (yaÅ)*b （分配律） =(xÅa) *b)(yÅa) *b) （幂等律，交换律，结合律） =f (x) *f (y)所以，f满足同态公式，因而f 是从A到B的同态函数。8证明：一个格是分配格的充分必要条件是"a，b，cL，有(a*b) Å (b*c) Å (c*a)=(aÅb) * (bÅc) * (cÅa)证 必要性。对于任何a，b，cL，(a*b) Å (b*c) Å (c*a)=(b* (aÅc) Å (c*a) （交换律，分配律）=(bÅ (c*a) * (aÅc) Å (c*a) （分配律）=(bÅc) * (bÅa) * (aÅc) （分配律，吸收律）=(aÅb) * (bÅc) * (cÅa) （交换律）充分性，f满足同态公式，因而f是从A到B的同态函数。8证明：一个格是分配格的充分必要条件是"a，b，cL，有(a*b) Å (b*c) Å (c*a)=(aÅb) * (bÅc) * (cÅa)证 必要性。对于任何a，b，cL，(a*b) Å (b*c) Å (c*a)=(b* (aÅc) Å (c*a) （交换，分配律）=(bÅ (c*a)( aÅ c) Å (c*a) （分配律）=(bÅc) * (bÅa) * (aÅc) （分配律，吸收律）=(aÅb) * (bÅc) * (cÅa) （交换律）充分性，对于任何a，b，cL aÅ (b*c)=(aÅ (a*c) Å (b*c) （吸收律）=(aÅ (a*b) Å (a*c) Å (b*c) （吸收律）=(a*b) Å (b*c) Å (c*a) Å a （交换律，结合律）=(aÅb) * (bÅc) * (cÅa) Åa （已知条件）=(aÅb) * (aÅc) * (bÅc) Å (bÅc) *a) Å a （交换律，吸收律）=(aÅb) * (aÅc) * (bÅc) Å (bÅc) *a) Å (a* (aÅ b) * (aÅ c) （吸收律）=(aÅb) * (aÅc) Å (bÅc) * (bÅc) Åa) * (aÅ (aÅ b) * (aÅc) （已知条件）=(aÅb) * (aÅc) Å (bÅc) * (aÅbÅc) *(aÅ b)* (aÅc)（因为aÅ (aÅb) * (aÅc)= (aÅb) * (aÅc)=(aÅb) * (aÅc) Å(bÅc) * (aÅb)Åc) *(aÅ b)* (aÅc) （结合律）=(aÅb) * (aÅc) Å(bÅc) *(aÅ b)* (aÅc) （吸收律，结合律）cehabdfig=(aÅ b)* (aÅc) （吸收律）根据对偶原理 还有a* (bÅc)= (aÅb) * (aÅc)所以格L是分配格。9设L，是格。其Hasse图如右 a) 找出格中每个元素的补元；b) 此格是有补格吗？c) 此格是分配格吗？解 a)最小元0=i；最大元1=a；故此格为有界格。a和i互为补元；f和C互为补元；其余b，d，e，g，h等都没有补元。b) 根据a) 可知，此格不是有补格。c) 此格不是分配格，因为fÅ (g* h)=fÅ i=f (fÅg) * (fÅh)=b* d=d 因为去掉g结点后所形成的子格与分配格S24，I，GCD，LCM，1，24同构，因此若此格不是分配格，则必有子格h * (fÅg)=h*b=ha1a3a2a4a52484213612b1b4b5b3b2(h*f) Å (h*g)=iÅi=IS24，I，GCD，LCM，1，24 两个不是分配格的特殊格与两个不是分配格的特殊格同构，并且此子格必含有g点。而特殊不分配格之图或是含有五个结点的圈，或是有六个结点：gebdfi；gebdhi；gehdfi；或是有八个结：gecabdfi；gecabdhi；或是只有一个四结点的圈：gehi。因此此格绝不会有含g点的子格与两个不是分配格的特殊格同构。10设L，*，Å是有界格。x，yL，证明： a) 若xÅy=0，则x=0且y=0。b) 若x*y=1，则x=1且y=1。证 a) 对任何x，yL，若xÅy=0，则x=x* (xÅy) （吸收律） =x*0 （xÅy=0）=0 （01律）y=y* (yÅx) （吸收律） =y* (xÅy) （交换律） =y*0 （xÅy=0） =0 （01律）b) 对任何x，yL，若x*y=1，则 x=xÅ (x*y) （吸收律） =xÅ1 （x*y=1） =1 （01律）y=yÅ (y*x) （吸收律） =yÅ (x*y) （交换律） =yÅ1 （x*y=1） =1 （01律）11在有界格中，0是1的唯一补元，1是0的唯一补元。证 由于1Å0=1，1*0=0，所以0与1互为补元。下面我们先来证0是1的唯一补元：对于任何元素a属于有界格，若a是1的补元，则必有1Åa=1，及1*a=0，于是必有a=a* (aÅ1) （吸收律） =a* (1Åa) （交换律） =a*1 （由1Åa=1） =1*a （交换律） =0 （由1*a=0）从而0是1的唯一补元。次证1是0的唯一补元。对于任何元素a属于有界格，若a是0的补元，则必有0Åa=1，0*a=0。于是必有 a=a(a*0) （吸收律） =a(0Åa) （交换律） =aÅ0 （由0*a=0） =0Åa （交换律） =1 （由0Åa=1）12设L，是格，|L|2。证明：L中不存在以自己为补元的元素。证 用反证法，假设L中存在着以自己为补元的元素，不妨是bL，那么bÅb=1，b*b=0，于是由幂等律，可得b=b*b=0，bÅb=1，从而有0=b=1，即0=1因此，对于任何元素aL，都有a=0=1（因为0a1），从而|L|=1，这与已知|L，|2矛盾。13设L，是全序集，|L|3。证明：L，是格，但不是有补格。证 由于L，是全序集，那么L中任意两个元素都可比较，于是L中任意两个元素都有上确界和下确界，因此L，是格。下面我们来证L，不是有补格，用反证法：否则L，是有补格，则对任何aL，都存在着一个元素bL，使aÅb=1及a*b=0。由于L，是全序集，所以任二元素可比较，从而若ab，则a=a*b=0若ba，则a=aÅb=1因此|L|=2，与已知|L|3矛盾。14在有界的分配格中，证明：具有补元的那些元素组成一个子格。证 设L，*，Å，0，1是有界分配格，令 L=x|xL($yL)(x*y=0xÅy=1)我们来证L，*，Å，0，1是L，*，Å，0，1的子格： 显然LL；其次易证0，1L，故此L非空；对于任何a1，a2L，我们来证a1*a2，a1Åa2L为证a1*a2L，只需找出a1*a2的补元即可。由于a1，a2L，故此存在着b1，b2L，使a1*b1=0，a1Åb1=1以及a2*b2=0，a2Åb2=1，于是构造出a1*a2补元为b1b2L。这是因为(a1*a2) * (b1Åb2)=(a1*a2) * b1) Å(a1*a2) * b2) （分配律） =(a1*b1) *a2) Å(a1*(a2 * b2) （交换律） =(0*a2) Å(a1*0)（由a1*b1=0，a2b2=0） =0Å0 （由01律） =0(a1*a2) Å (b1Åb2)=(a1Å (b1Å b2) * (a2Å (b1Å b2)（分配律） =(a1Åb2) Åb2) * (a2Åb2) Åb1)（交换律，结合律） =(1Åb2)* (1Åb1)（由a1Åb1=1及a2Åb2=1） =1*1（由01律） =1为证a1Åa2L只需找出a1Åa2的补元即可。由于a1，a2的补元是b1，b2，故构造出a1Åa2的补元为b1*b2L。这是因为 (a1Åa2) * (b1*b2)=(a1* (b1* b2) Å(a2* (b1* b2)（分配律） =(a1*b2) *b2) Å (a2*b2) *b1)（交换律，结合律） =(0*b2) Å (0*b1)（由a1*b1=0及a2*b2=0） =0Å0（由01律） =0 (a1Åa2) Å (b1*b2)=(a1Åa2) Åb1) * (a1Åa2) Åb2)（分配律）= (a1Åb1) Åa2) * (a1Å (a2Åb2)（交换律，结合律）=(1Åa2) * (a1Å1)（由a1Åb1=1及a2Åb2=1）=1*1 （由01律）=1124213615求S12，1的所有子格，其中，S12是12的所有因子的集合1是S12上的整除关系。 解 一个结点：1，2，3，4，6，12 二个结点：1，2，1，3，1，4，1，6，1，122，4，2，6，2，123，6，3，124，126，12三个结点：1，2，4，1，2，6，1，2，12S12，1的图1，3，6，1，3，121，4，121，6，122，4，12，2，6，123，6，12四个结点：1，2，4，12，1，2，6，12，1，3，6，121，2，3，6，2，4，6，12，1，3，4，12五个结点：1，2，4，12，1，2，3，6，12六个结点：S12=1，2，3，4，6，12都是S12，1的子格。16证明：一个格L，分配格的充分必要条件是"a，b，cL，有(aÅb) *caÅ (b*c)证 必要性对任何a，b，cL (aÅb) *c=(a*c) Å (b*c) （分配律） aÅ (b*c) （由a*ca，及保序性）充分性一方面，由aÅ (b*c)aÅ b （根据b*cb及保序性）和aÅ (b*c)aÅ c （根据b*cc及保序性）及上、下确界的性质可得 aÅ (b*c)(aÅ b) * (aÅ c)另一方面(aÅ b) * (aÅ c) aÅ (b* (aÅ c)（已知条件）=aÅ (aÅ c) *b)（交换律）aÅ (aÅ (c*b)（已知条件(aÅc)*baÅ (c* b)及保序性）=(aÅa) Å (b*c)（结合律，交换律）=aÅ (b*c)（幂等律）所以，综合这两方面，得到分配律 aÅ (b*c)=(aÅ b) * (aÅ c)根据对偶原理，可得另一分配律 a* (bÅ c)=(a*b) Å (a*c)所以格L，是分配格。17设L1，R1和L2，R2是两个格，f：L1L2是从L1，R1到L2，R2的同态函数。证明：f的同态象是L2，R2的子格。证 f的同态象f (L1) = y : yL2($xL1) (f(x)=y)我们来证f (L1)，R2是L2，R2的子格：显然f (L1)L2；若L1非空，则有aL1，从而有b=f (a)f (L1)故f (L1)非空。对于任何b1，b2f (L1)，存在着a1，a2L1，使b1=f (a1)，b2=f (a2)，从而 b1 Å2b2=f (a1) Å2f (a2)110102221555=f (a1Å1a2)（同态公式）f (L1)（因L1，R1是格，故Å1运算封闭，从而a1Å1a2L1）因此f（L1），R1是L2，R2子格。18设B=1，2，5，10，11，22，55，110。证明：B，GCD，LCM是布尔代数。其中，GCD是求最大公约数，LCM是求最小公倍数，x=110/x。 证 我们已证过N，GCD，LCM，是分配格，故此为证B，GCD，LCM是分配格，只需证B，GCD，LCM是N，GCD，LCM，的子格即可。易于验证，对于任何a，bB，恒有GCDa，b，LCMa，bB故此两个运算GCD，LCM关于B封闭。因而B，GCD，LCM是分配格。又由于1和110互为补元；2和55互为补元；5和22互为补元；10和11互为补元，所以B，GCD，LCM，是有补的分配格，故此B，GCD，LCM，是布尔代数。19设L1=1，2，3，4，6，12，L2=1，2，3，4，6，8，16，24。2412631248 a) L1，GCD，LCM，是布尔代数吗？为什么？b) L2，GCD，LCM，是布尔代数吗？为什么？解 a) L1，GCD，LCM，不是布尔代数。因为L1，GCD，LCM，虽是分配格（N，1，GCD，LCM，的子格）但不是有补格，元素2，6没有补元。所以不是布尔代数。 b) L2，GCD，LCM，也不是布尔代数。因为虽然L2，GCD，LCM，是分配格（N，1，GCD，LCM，的子格），但不是有补格，元素2，4，6，12没有补元。所以也不是布尔代数。20设B，*，Å，是布尔代数。证明下列布尔恒等式。 a) aÅ (a*b)=aÅbb) a* (aÅb)=a*bc) (a*c) Å (a*b) Å (b*c)=(a*c) Å (a*b)d) (aÅ b) * (bÅ c) * (cÅ a)=(aÅ b) * (bÅ c) * (cÅ a)e) (aÅ b) * (bÅ c) * (cÅ a)=(a*b) Å (b*c) Å (c*a)证 a) aÅ (a*b)=(aÅa) * (aÅb)（分配律）=1* (aÅb) （由aÅa=1）=aÅb （01律） b) a (aÅb)=(a*a) Å (a*b)（分配律）=1Å (a*b) （由a*a=0）= a*b （01律） c)由于(a*c) Å (a*b) =(aÅa) * (aÅb)* (a*c) * (b*c)（分配律，结合律，交换律）= (aÅb)* (aÅc) * (bÅc) （由aÅa=1）并且因为b*aÅb，c*aÅc，从而由保序性，得到b*c(aÅb) * (aÅc)又由b*cbÅc及下确界的性质，得到b*c(aÅb) * (aÅc) * (bÅc)所以b*c(a*c) Å (a*b)所以(a*c) Å (a*b) Å (b*c)= (a*c) Å (a*b) d) 令B=(aÅb) * (bÅc) * (cÅa)，C=(aÅb) * (bÅc) * (cÅa) 于是为证B=C，根据布尔代数的性质：消去律。 = a*b*c （交换律）所以 a*B=a*c从而由消去律，有B=C 即 (aÅb) * (bÅc) * (cÅa)=(aÅb) * (bÅc) * (cÅa) e) 令B=(aÅb) * (bÅc) * (cÅa) C=(a* b)Å(b* c)Å(c* a) 由于a* B=a* (aÅb) * (bÅc) * (cÅa) =a* (bÅc) * (cÅa) （吸收律） =a* (aÅc) * (bÅc) （交换律） =a* (bÅc)（吸收律） a* C=a* (a* b)Å(b* c)Å(c* a) =(a* a* b)Å(a* b* c)Å(a* a* c) （分配律，交换律） =(a* b)Å(a* b* c)Å(a* c) （幂等律） =(a* b)Å(a* c) （分配律）所以 a* B=a* C又由于 a* B=a* (aÅb) * (bÅC) * (cÅa) = a* b* (bÅc) * (cÅa) （反身性，及本题b） = a* b*(cÅa) （吸收律） = a* b* c （交换律，反身律，本题b） a*C= a(a* b)Å(b* c)Å(c* a)=(a* a* b)Å(a* b* c)Å(a* a* c)（分配律，交换律）=(0* b)Å(a* b* c)Å(0* c) （由a* a=0）=0Å(a* b* c)Å0 （11律）=a* b* c只需证a* B=a* C和a* B=a* C 即可由于 a* B=a* (aÅb) * (bÅc) * (cÅa)= a* (bÅc) * (cÅa) （吸收律）= a*(aÅ c) * (bÅc) （交换律）=a* c* (cÅb) （本题b）及交换律）=a* c* b （本题b）=a* b* c （交换律）a* C=a* (aÅb) * (bÅC) * (cÅa)=a* b* (bÅC) * (cÅa) （本题b）=a* b* c* (cÅa) （本题b）=a* b* c* a （本题b）=a* a* b* c （交换律）=a* b* c （幂等律）所以 a* B=a* C又由于 a* B=a* (aÅb) * (bÅc) * (cÅa)=a* (a) Åb) * (bÅc) * (cÅa) （反身性）=a* b* (b)Åc) * (cÅa) （本题b）及反身性）=a* b* c* (c)Åa) （本题b）及反身性）=a* b* c* a （本题b）=a* a* b* c （交换律）=a* b* c （幂等性）a*C= a* (aÅb) * (bÅc) * (cÅa)= a* (bÅc) * (cÅa) （吸收律）= a* (a) Åc) * (bÅc) （交换律及反身性）= a* c* (c)Åb) （本题b）及反身性交换律）= a* c* b （本题b）所以 a* B=a* C故根据消去律得到B=C，即(aÅb) * (bÅC) * (cÅa)=(a* b)Å(b* c)Å(c* a)21设B，*，Å，是布尔代数，简化下列布尔表达式。 a) (a* b)Å(a* b* c)Å(b* c)b) (a* b)Å(a* b* c)Å(b* c) c) (a* b)Å(a* b* c)Å(b* c)d) (a* b)Åc) * (aÅb) * c解 a) (a* b)Å(a* b* c)Å(b* c)= (a* b)Å (b* c) （因为吸收律）=b* (aÅc) （分配律） b) (a* b)Å(a* b* c)Å(b* c)=(a* b)Å(a* b)Åb)* c （分配律）=(a* b)Å(a* b)* c) （20题a）=(a* b)Å(a* c) Å (b* c) （分配律）c) (a* b)Å(a* b* c)Å(b* c) =( b *( aÅ(a* c)Å(b* c) （分配律） =( b *( aÅa)* (aÅc)Å(b* c) （分配律） =(b* (aÅ c)Å(b* c) （互补aÅa=1） =b* (aÅcÅc) （分配律） =b （互补cÅc=1）d) (a* b)Åc) * (aÅb) * C =(a* b)Åc) * c* (aÅb) （交换律） =c* (aÅb) （吸收律）22设B，*，Å，是布尔代数。在B上定义二元运算如下"a，bB，ab=(a*b)(a*b)证明：B，Ä是交换群证 封闭性对于任何a，bB，由于*，Å，运算的封闭性，可知ab=(a*b)Å(a*)B，因此运算具有封闭性。结合律对于任何a，b，cB， (ab)c (ab)*c)Å(ab)*c) =(a*b)Å(a*b) *c)Å(a*b)Å(a*b)*c) =(a*b*c)Å(a*b*c)Å(aÅb) * (aÅb) *c) （分配律，deMorgan律，反身律） =(a*b*c)Å(a*b*c)Å(a*b) Å (aÅb) *c) （分配律，互补律，01律） =(a*b*c)Å(a*b*c)Å(a*b*c) Å (a*b*c) =(a