Δ第十二章格与布尔代数
12.1 格
内容提要
格是一种特殊的有序集，因此我们先从有序集方面引入格的概念。
定义12.1称有序集
通常用a∨b表示{a，b}的上确界，用a∧b表示{a，b}的下确界，∨和∧分别称为保联（join）和保交（meet）运算。由于对任何a，b，a∨b及a∧b都是L中确定的成员，因此∨,∧均为L 上的运算．
现设≥表示序关系≤的逆关系，那么据逆关系的性质可知：
定理12.1当< L,≤>为格时，< L, ≥>亦为格,且它的保联、保交运算∨~,∧~对任意a,b∈L 满足
a∨~b = a∧b , a∧~b = a∨b
于是，我们有下列对偶原理。
定理12.2 A为格< L，≤>上的真表达式，当且仅当A*为< L，≥>上的真表达式，这里A*称为A的对偶式，即将A中符号∨，∧，≤分别改为∧，∨，≥后所得的公式，而 a≥b意即b≤a 。
定理12.3设< L,≤>为格，那么对L中任何元素a,b,c 有
（l）a≤a∨b， b≤a∨b
a∧b≤a， a∧b≤b
（2）若a≤b，a≤c，则a≤b∨c
若b≤a，c≤a，则b∧c≤a．
（3）若a≤b，c≤d，则a∨c≤b∨d，a∧c≤b∧d
（4）若a≤b，则a∨c≤b∨c，a∧c≤b∧c．
定理12.4设< L,≤>为格，那么对L中任意元素来a,b,c 有
（1）a∨a = a ，a∧a＝a (幂等律)
（2）a∨b = b∨a ，a∧b = b∧a （交换律）
（3）a∨（b∨c）=（a∨b）∨c
a∧（b∧c）=（a∧b）∧c (结合律)
（4）a∧ (a∨b) = a ，a∨ (a∧b) = a (吸收律)
格还有下列性质；
定理12.5 设< L,≤>为格。那么对L中任意元素a,b,c有
（1） a≤b当且仅当。a∧b = a当且仅当a∨b = b 。
（2） a∨（b∧c）≤（a∨b）∧（a∨c）。
（3） a≤c当且仅当 a∨ (b∧c)≤（a∨b）∧c。
定义12.2设L为一非空集合，∨,∧为L上的两个二元运算，称 < L，∨,∧>为格代数，或简单地称为格，如果< L，∨,∧>中运算∨,∧满足幂等律、交换律、结合律和吸收律（见定理12.4）。
定义12.3 格< L，∨,∧>称为完全格（complete lattice），如果L的所有非空子集都有上确界和下确界。
设S ?L ，那么S 的上确界记为S ∨或a S a ∈∨，S 的下确界记为S ∧或a S
a ∈∧。L 的上确界记为1，L 的下确界记为0 。
定理12.6设< L ，∨,∧>为完全格，那么0为∨运算么元、∧运算零元；l 为∧运算么元、∨运算零元．
定理12.7有序集< L ，≤>为完全格的充分必要条件是:存在L 的上确界1，并且L 的每一非空子集有下确界。
定理12.8设< L ，∨,∧>为格，a ∈L ，令
L a = {x | x ∈L 且x ≤a} , M a ={x | x ∈L 且a ≤x}
那么< L a ，∨,∧> ,
定理 12.9设< L ，∨,∧> , < L ’，∨’,∧’>为两个格，f 为L 到L ’的同态，那么对任意a,b ∈L ，a ≤b 蕴涵f(a) ≤’f(b) 。即同态是保序的。
注意，本定理的逆不成立。
但是，对于同构映射我们却有以下定理
定理12.10 设< S , ≤>,< S ’, ≤’>均为格，f 为S 到S ’的双射，那么 f 为 S 到 S ’的同构映射，当且仅当对任意a,b ∈ S ，
a ≤
b ? f （a ）≤’f （b ） （12－1）
定义12.4 称格< L ，∨,∧>为分配格（distributive lattice ）。如果它满足分配津，即对任意a,b,c ∈ L ，
a ∧（
b ∨
c ）=（a ∧b ）∨（a ∧c ） （12－2）
a ∨（
b ∧
c ）=（a ∨b ）∧（a ∨c ） （12－3） 定理12.11在格中式（12－2）等价于式（12－3）。
有的格虽不能满足分配律。但它们可以有条件地满足分配律，这就是模格.
定义12.5 称格< L ，∨,∧>为模格（moduler lattice ）。如果对任意元素a,b,c ∈ L ，它满足：
a ≤c 蕴涵a ∨（
b ∧
c ）＝（a ∨b ）∧（a ∨c ）
或
a ≤c 蕴涵a ∨（
b ∧
c ）=（a ∨b ）∧c
定理12.12 设< L ，∨,∧>为分配格，那么对L 中任意元素a ，b ，c ，有
a ∧
b = a ∧
c 并且a ∨b = a ∨c 当且仅当b = c
定理12.13 格< L ，∨,∧>为模格的充分必要条件是：对L 中任意元素a,b,c ，若b ≤c ， a ∨b ＝a ∨c ，a ∧b = a ∧c ，则b = c 。
习题解答
练习12.1
1．对格L 中任意元素a ，b ，c ，d ，证明：
（1）a ≤b,a ≤c 当且仅当 a ≤b ∧c 。
（2）a ≤c,b ≤c 当且仅当a ∨b ≤c 。
（3）若a ≤b ≤c ,d ∧c ＝a ，则d ∧b ＝a 。
（4）若a ≤b ≤c ,d ∨a ＝c ，则d ∨b ＝c 。
（5）（a ∧b ）∨（a ∧c ）≤ a ∧（b ∨c ）。
（6）（（a ∧b ）∨（a ∧c ））∧（（a ∧b ）∨（b ∧c ））= a ∧b 。
（7）（a ∧b ）∨（c ∧d ）≤（a ∨c ）∧（b ∨d ）。
（8）（a∧b）∨（b∧C）∨（c∧a）≤（a∨b）∧（b∨C）∧（c∨a）。
证（1）a≤b,a≤c 当且仅当 a≤b∧c 。
设a≤b,a≤c，那么a∧a≤b∧c ,即a≤b∧c。
另一方面，设a≤b∧c，由于b∧c≤b，b∧c≤c，故a≤b,a≤c。
（2）a≤c,b≤c 当且仅当a∨b≤c 。
设a≤b,b≤c，那么a∨b≤c∨c ,即a∨b≤c。
另一方面，设a∨b≤c，由于a≤a∨b，b≤a∨b，故a≤c,b≤c。
（3）若a≤b≤c ,d∧c＝a，则d∧b＝a 。
设a≤b≤c ,d∧c＝a，那么,d∧c∧b＝a∧b，从而d∧b＝a。
（4）若a≤b≤c ,d∨a＝c，则d∨b＝c 。
设a≤b≤c ,d∨a＝c，那么,d∨a∨b＝c∨b，从而d∨b＝c。
（5）（a∧b）∨（a∧c）≤ a∧（b∨c）。
因为b≤b∨c，c≤b∨c,因此a∧b≤a∧（b∨c），a∧c≤a∧（b∨c），故
（a∧b）∨（a∧c）≤ a∧（b∨c）。
（6）（（a∧b）∨（a∧c））∧（（a∧b）∨（b∧c））= a∧b。
首先a∧b≤（a∧b）∨（a∧c），a∧b≤（a∧b）∨（b∧c），因此a∧b≤（（a∧b）∨（a∧c））∧（（a∧b）∨（b∧c））。
另一方面，据（5）
（a∧b）∨（a∧c）≤a∧（b∨c）
（a∧b）∨（b∧c）≤b∧（a∨c）
（（a∧b）∨（a∧c））∧（（a∧b）∨（b∧c））≤a∧（b∨c）∧b∧（a∨c）
≤a∧b
因此（（a∧b）∨（a∧c））∧（（a∧b）∨（b∧c））= a∧b。
（7）（a∧b）∨（c∧d）≤（a∨c）∧（b∨d）。
因为a∧b≤a≤a∨c, a∧b≤b≤b∨d,c∧d≤c≤（a∨c），c∧d≤d≤（b∨d），因此（a∧b）≤（a∨c）∧（b∨d）
（c∧d）≤（a∨c）∧（b∨d）
故（a∧b）∨（c∧d）≤（a∨c）∧（b∨d）。
（8）（a∧b）∨（b∧C）∨（c∧a）≤（a∨b）∧（b∨C）∧（c∨a）。
因为a∧b≤a≤a∨b, a∧b≤b≤b∨C, a∧b≤a≤c∨a,
b∧C≤b≤a∨b, b∧C≤b≤b∨C, b∧C≤c≤c∨a,
c∧a≤a≤a∨b, c∧a≤c≤b∨C, c∧a≤c≤c∨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）
2. 令x 仅当a与b是不可比较的，即a≤b,b≤a 都不能成立。 证设a∧b < a 且a∧b < b。若a与b是可比较的，即a≤b或,b≤a，从而a∧b = a 且a∧b = b。与题设矛盾。 另一方面，设a与b是不可比较的。我们已知a∧b ≤ a 且a∧b ≤ b，若a∧b < a 不成立，或a∧b < b不成立，那么或a∧b =a 或a∧b = b，也就是说a,b是可比较的，又与题设矛盾。 3．求证：有序集< L，≤>为完全格的充分必要条件是：L有下确界0，且L的每一子集有上确界。 证必要性是显然的。 为证充分性，只要证L的任一非空子集都有下确界． 设 S?L ，S ≠?。考虑 S的下界集合B。由于0∈B是显然的，因此B ≠?。据题设，B 有上确界，记为b，现证b为S的下确界． b当然是S的下界，因为b∈B。另设a是S的任一下界，那么 a∈B，因而 a≤b。这就是说，b是S的下确界。 4．问开区间（0，1）中的有理数集合按有理数的大小排序是否构成完全格？闭区间［0，1］呢？ 解开区间（0，1）中的有理数集合按有理数的大小排序不构成完全格。闭区间［0，1］中的有理数集合按有理数的大小排序构成完全格 5．证明：定义12.2中L满足幂等律的要求是多余的,即由交换律、结合律和吸收律可导出它满足幂等律。 证由吸收律a∨（a∧a）=a ,于是 a∧（a∨（a∧a））=a∧a a∨（a∧a）=a∧a 据吸收律 a =a∧a 据吸收律 同理可证a =a∨a 。 6．设格L1与L2同态，求证；若L1有幺元（零元），那么L2也有么元（零元）。 证设h为格L1到L2的满同态，e是L1的关于∧运算的幺元，o是L1的关于∧运算的零元，可证h(e), h(o)是L1的关于∧运算的幺元和零元。 对任意元素b∈L2,有L1中元素a，使得h(a) = b,因此 h(e)∧b = h(e)∧h(a) = h(e∧a) = h(a) = b , b∧h(e) = h(a)∧h(e)= h(a∧e) = h(a) = b h(o)∧b = h(o)∧h(a) = h(o∧a) = h(o) , b∧h(o) = h(a)∧h(o)= h(a∧o) = h(o) 关于∨运算同理可证。 7．证明：格L的两个子格的交仍为L的子格。 证设格L的两个子格为L1与L2，它们的交为L1∩L2。L1∩L2?L是显然的。对任意a,b∈L1∩L2，那么a,b∈L1 且a,b∈L2。由于L1与L2是子格，因此，a∧b∈L1 且a∧b∈L2，a∨b∈L1 且a∨b∈L2。故a∧b∈L1∩L2，a∨b∈L1∩L2。L1∩L2为L的子格得证。 8．设a，b为格L中的两个元素,证明：S = {x |x∈L且a≤x≤b}可构成L的一个子格。 证设x,y为S = {x |x∈L且a≤x≤b}中的任意元素，考虑x∨y,x∧y。由于a≤x≤b， a ≤y ≤b,因此a ≤x ∨y ≤ b ，a ≤x ∧y ≤b ，故x ∨y,x ∧y ∈S ，S 为L 的子格得证。 9. 设f 为格L1到格L2的同态映射，证明f 的同态像是L2的子格。 证 设x ’,y ’为f(L1)中的任意元素，f(x)= x ’， f(y)= y ’。那么 x ’∧y ’= f(x)∧f(y)= f(x ∧y) ∈ f(L1) x ’∨y ’= f(x)∨f(y)= f(x ∨y) ∈ f(L1) 故f 的同态像f(L1)是L2的子格。 10．完成定理12.8中< M a ,∨,∧>为子格的证明。 证 已知< L ，∨,∧>为格，a ∈L ，M a ={x | x ∈L 且a ≤x}。 为证< M a ，∨,∧>为子格，只要证M a 对运算∨，∧封闭。设x ，y 为M a 中任意元素，那么，a ≤x ，a ≤y ，从而a ≤x ∨y ，a ≤x ∧y ，即x ∨y ∈M a ，x ∧y ∈M a 。 11．完成例12.6之(2)的证明。 证 设 x ∈（D1＋ D2）∩ D3,那麽 x = d1+d2 ,其中d1∈D1 ,d2∈D2 , d1+d2∈D3 。于是 由D1?D3, d1+d2+（-d1）∈D3 (D3为理想)，知d1∈D3，d2∈D3。 故 x= d1+d2∈ D1＋（D2 ∩ D3）。（D1＋D2）∩ D3? D1＋（D2 ∩ D3）得证。 12．设< L ，∨,∧>为分配格，a 为L 中一确定元素。定义函数 f:L →L ；g: L →L ，使得对任一x ∈L ， f(x) = x ∧a ，g(x) = x ∨a 求证，f ，g 都是 L 上的自同态，从而它们的像都是 L 的子格。 证 设x ，y 为L 中任意元素，那么， f(x ∧y )= x ∧y ∧a=(x ∧a)∧(y ∧a)=f(x)∧f(y ) f(x ∨y )=(x ∨y)∧a=(x ∧a)∨(y ∧a)=f(x)∨f(y ) 13．请作出三个哈斯图（与书中已给出的不同），使它们分别是分配格、非分配格的模格、非模格，并证明你所作的图合乎要求。 (a) (b) (c) （a ）显然是分配格。 在（b ）中， b ∧（ c ∨ d ）= b ∧a ＝ b （b ∧c ）∨（b ∧d ）＝e ∨e = e 但b ≠ f 。（b ）不是分配格，但它是模格。 在(c) 中， d ∨（c ∧b ）＝ d ∨f ＝ d （d ∨c ）∧b ＝ a ∧b ＝ b 但d ≠ b 。故(c)不是模格。 14．对分配格L 中任意元素 a, b ，c,证明： 若a ∧c ＝b ∧c ，a ∨c ＝b ∨c ，则a ＝b 证 设a ∧c ＝b ∧c ，a ∨c ＝b ∨c ，那么 a = a ∧(a ∨c) = a ∧( b ∨c) = (a ∧b)∨(a ∧c) = (a ∧b)∨(b ∧c) = b ∧(a ∨c) = b ∧(b ∨c)=b *15.证明:格< L ，∨,∧>为分配格,当且仅当对L 中任意元素a ，b ，c ，有 （a ∧b ）∨(b ∧c)∨(c ∧a)＝（a ∨b ）∧(b ∨c)∧(c ∨a) 提示:为证充分性,可令 a ＝（A ∨B ）∧（A ∨C ），b = B ∨C ，c = A ，从而对A,B,C 证明∨,∧能满足分配律。 证 设格< L ，∨,∧>为分配格,那么 （a ∧b ）∨(b ∧c)∨(c ∧a)＝（（a ∨b ）∧(a ∨c)∧b ∧(b ∨c)）∨(c ∧a) ＝（（a ∨b ）∧(a ∨c)∧b ）∨(c ∧a) ＝（(a ∨c)∧b ）∨(c ∧a) ＝(a ∨c)∧(b ∨(c ∧a)) ＝（a ∨b ）∧(b ∨c)∧(c ∨a) 另一方面，对L 中任意元素A ，B ，C ，令a ＝（A ∨B ）∧（A ∨C ），b = B ∨C ，c = A ，计算 （a ∧b ）∨(b ∧c)∨(c ∧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 ）∧（B ∨C ））∨A =（（A ∧B ）∨（A ∧C ）∨（B ∧C ））∨A = A ∨（B ∧C ） （a ∨b ）∧(b ∨c)∧(c ∨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 ∨B ）∧（A ∨C ）） =（(（A ∨B ）∧（A ∨C ）)∨（B ∨C ））∧（（A ∨B ）∧（A ∨C ）） =（A ∨B ）∧（A ∨C ） 由题设（a ∧b ）∨(b ∧c)∨(c ∧a)＝（a ∨b ）∧(b ∨c)∧(c ∨a)可得 A ∨（ B ∧ C ）=（A ∨B ）∧（A ∨C ） 格< L ，∨,∧>为分配格证毕。 16.证明:在分配格中有 （l ）)(11i m i i m i b a b a ∧∨=∨∧== 证 对m 归纳。M=1时，等式显然成立。设等式对m=k 时真，即)(11i k i i k i b a b a ∧∨=∨∧== 那么m=k+1时 )()()()()()(1111111111i k i k i k i k i k i k i k i i k i b a b a b a b a b a b b a b a ∧∨=∧∨∧∨=∧∨∨∧=∨∨∧=∨∧+=+=+=+=+= （2）)(11i m i i m i b a b a ∨∧=∧∨== 证 对m 归纳。M=1时，等式显然成立。设等式对m=k 时真，即)(11i m i i m i b a b a ∨∧=∧∨== 那么m=k+1时 )()()()()()(1111111111i k i k i k i k i k i k i k i i k i b a b a b a b a b a b b a b a ∨∧=∨∧∨∧=∨∧∧∨=∧∧∨=∧∨+=+=+=+=+= *17.求证：格< L,∨,∧>为模格的充分必要条件是，对L 中任意元素a ，b ，c,有 a ∧((a ∧b)∨c)＝（a ∧ b ）∨（a ∧ c ） 证 设格< L ，∨,∧>为模格。由于a ∧b ≤a ，因此 （a ∧b ）∨（a ∧c ）=（a ∧b ）∨（c ∧a ）=（（a ∧b ）∨c ）∧（（a ∧b ）∨a ） = a ∧（（a ∧b ）∨c ） 反之设对L 中任意元素a ，b ，c,有a ∧((a ∧b)∨c)＝（a ∧b ）∨（a ∧c ）。据对偶原理有 a ∨((a ∨b)∧c)＝（a ∨ b ）∧（a ∨ c ） 设a ≤b ，那么 a ∨( b ∧c)＝（a ∨b ）∧（a ∨ c ） 故格< L,∨,∧>为模格。 18.完成定理12.13的证明。 定理12.13 格< L ，∨,∧>为模格的充分必要条件是：对L 中任意元素a,b,c ，若b ≤c ， a ∨b ＝a ∨c ，a ∧b = a ∧c ，则b = c 。 证 先证必要性。 设< L ，∨,∧>为模格，且b ≤c ，a ∨b ＝a ∨c ，a ∧b = a ∧c ，那么， b ＝b ∨（a ∧b ） ＝b ∨（a ∧c ） =（b ∨a ）∧（b ∨c ） =（c ∨a ）∧（b ∨c ） ＝c ∨（a ∧b ） = c ∨（a ∧c ） = c 再证充分性。 为证< L ，∨,∧>为模格，设 b ≤c ，需证 c ∧（b ∨a ）＝ b ∨（c ∧a ）。 首先，据定理12.5之（3），由b ≤c 可知 b ∨（ c ∧a ）≤c ∧（b ∨a ） （12－4） 由此 c ∧a ＝（c ∧a ）∧a ≤（b ∨（c ∧a ））∧a ≤（c∧（b∨a））∧a （由式（12-4）） = c∧a 于是 （b∨（c∧a））∧a＝（c∧（b∨a）∧a = c∧a （12－5） 由 b∨a＝（b∨a）∨a ≥（c∧（b∨a））∨a ≥（b∨（c∧a））∨a （由式（12-4）） = b∨a 同样可以证得 （b∨（c∧a））∨a =（c∧（b∨a）∨a ＝b∨a （12－6） 因此,由题设及式（12－4）----（12－ 6）即得 c∧（b∨a）＝b∨（c∧a） < L，∨,∧>为模格得证。 12.2 布尔代数 内容提要 定义12.8 格< L，∨,∧>称为有界格（bounded lattice）,如果L中既有上确界1，又有下确界0。0，l称为L的界（bound）。 定义12.7 设< L，∨,∧>为有界格，a为L中一元素，称 b为 a的补元或补（complements），如果 a∨b = 1， a∧b = 0 定义12.8 有界格< L，∨,∧>称为有补格（complemented lettice），如果L中每个元素都有补元。 关于有补格有下列事实： 定理12.14 有补格< L,∨,∧>中元素0，1的补元是唯一的。 定理12.15有补分配格中每一元素的补元都是唯一的。因此, 有补分配格中一元素a 的补可用a’来表示。 定理12.16对有补分配格中每一元素a，有 （a’）’＝ a 定理12.17设< L，∨,∧>为有补分配格，那么对L中任意元素a，b，有 (1)（a∨b）’＝ a’∧b’ （2）（a∧b）’= a’∨ b’ 定义12.9 有补分配格称为布尔代数（Boolean algebra）。 其实我们也可以用少数的几个特征性来定义布尔代数． 定义12.10 代数系统< B，∨，∧>（∨，∧为B上二元运算）称为布尔代数，如果B满足下列条件： （l）运算∨，∧满足交换律。 （2）∨运算对∧运算满足分配律，∧运算对∨运算也满足分配律。 （3）B有∨运算么元和∧运算零元O，∧运算么元和∨运算零元1。 （4）对B中每一元素a，均存在元素a’，使 a∨a’＝ 1， a ∧a’= 0 布尔代数通常用序组< B，∨，∧，’，0，1>来表示。其中’为一元求补运算。这并不意味着布尔代数至少有两个不同元素，当B只有一个元素0时，可以认为< {0}，∨，∧，’，0>仍为布尔代数（它满足定义12.10），这时它被称为退化了的布尔代数。 定义12.11称< A，∨，∧，’，0，1> 为布尔代数< B，∨，∧，’，0，1>的子代数，如果A?B，且< A，∨，∧，’，0，1>为布尔代数。 定理12.19设< B，∨，∧，’，0，1>为布尔代数，A?B且A含有元素0，1，对运算∨，∧，’封闭，那么< A，∨，∧，’，0，1>为B的子代数。 定义12.2 设h：A→B为布尔代数< A，∨，∧，’，0，1>到布尔代数< B，∨，∧，’，0，1>的同态映射，即对任何元素a，b， h（a∨b）= h（a）∨h（b）（12-9） h（a∧b）＝h（a）∧h（b）（12-10） h（a’）= (h(a))’ （12-11） 那么称h为A到B的布尔同态。 定理12.20设h为布尔代数< A，∨，∧，’，0，1>到布尔代数< B，∨，∧，’，0，1>的布尔同态，那么 h（0）= 0， h（1）= 1 定理12.21设h为布尔代数< A，∨，∧，’，0，1>到格< B，∨，∧>的格同态（仅保∨，∧运算），那么当h为满射时< B，∨，∧>为一布尔代数。 为了介绍重要的布尔代数表示定理；先给出下列概念： 定义12.13 设< B，∨，∧，’，0，1>为布尔代数，≤为B作为格时的序关系，x a盖着b，当且仅当哈斯图中 a在b的上方，且a， b间有一边相关联。 定义12.14 布尔代数中盖着元素0的元素称为该布尔代数的原子（atoms）． 关于布尔代数的原子我们有以下定理． 定理 12.22 元素a是布尔代数< B，∨，∧，’，0，1>的原子，当且仅当a ≠0且对B 中任何元素x x∧a = a 或 x∧ a = 0 （12－ 12）定理12.23 设a是布尔代数< B，∨，∧，’，0，1>的原子，x为B中任一元素，那么a≤x或a≤x’，但不兼而有之。 本定理说明，布尔代数结构如下： （1）有一个处于最“低层”的子集----原子的集合． （2）依每个原子可以将布尔代数的非零元素分为两类，一类与该原子可比较，另一类与该原子不可较。 定理12.24 设< B，∨，∧，’，0，1>为一有限布尔代数，那么对于B中任一非零元素x，恒有一原子a∈B,使a≤x 。 定理12.25 设a1，a2为布尔代数< B，∨，∧，’，0，1>中任意两个不相同的原子，那麽a1∧a2 = 0． 本定理也可叙述为：若原子a1,a2满足a1∧a2 ≠ 0，那么a1 = a2 。 定理12.26 设< B，∨，∧，’，0，1>为有限布尔代数，x为B中任一非零元素，a1，a2，…, a k为满足a i≤x（i = 1,2,…,k）的所有原子，那么 x = a1∨a2∨…∨a k（x的原子表示） 定理12.27定理12.26中非零元素x的原子表示形式 x = a1∨a2∨…∨a k 是唯一的。 定理12.28 设< B ，∨，∧，’，0，1>为有限布尔代数，A( ? B)为B 中所有原子的集合，那么B 同构于布尔代数< ρ(A)，∪, ∩, ˉ, ? , A >。 本定理说明，有限布尔代数与集合代数同构，从而它总是恰含2n 个元素，其中n 正是它 的原子的数目． 这一定理对无限布尔代数不能成立． 定义12.15 设< B ，∨，∧，’，0，1>为布尔代数，如下递归地定义B 上布尔表达式（Boolean expressions ）： （1）布尔常元和布尔变元（取值于B 的常元和变元）是布尔表达式．布尔常元常用a,b ，c 等字母表示，布尔变元常用x ，y ，z 等字母表示． （2）如果e,e1,e2为布尔表达式，那么 (e ’),(e1∨e2),(e1∧e2)也是布尔表达式． （3）除有限次使用条款（l ），（2）生成的表达式是布尔表达式外，没有别的是布尔表达式． 为了省略括号，我们约定运算 ’的优先级高于运算∨，∧，并约定表达式最外层括号省略． 常用f(x 1,x 2,…,x n )，g(y 1,y 2,…,y m )等分别表示含有n 个变元x 1,x 2,…,x n 的n 元布尔表达式和含有m 个变元y 1,y 2,…,y m 的m 元布尔表达式． 定义12.16 布尔表达式f(x 1,x 2,…,x n )所定义的函数f:B →B 称为布尔函数（Booleanl functions ）． 定义12.17 布尔表达式 α1∧α2∧…∧αn 称为n 个变元的极小项，其中αi 为变元x i 或x i ’,而表达式 α1∨α2∨…∨αn 称为 n 个变元的极大项，其中 αi 为变元x i 或x i ’. 显然，n 个变元的极小项和极大项各有2n 个，我们分别用 m 0 ,m 1 ,…,m e(n) M 0 ,M 1 ,…,M e(n) （e(n)= 2n - 1） 来表示它们，它们满足下列性质： （1） m i ∧m j ＝0 ；M i ∨M j = 1 (i ≠ j) （2） 0,1)(0) (0==∧∨==i n e i i n e i M m 定义12.18 布尔表达式f(x 1 ,x 2 ,…,x n )的主析取范式和主合取范式分别指下列布尔表达式： (a 0∧m 0)∨(a 1∧m 1)∨…∨(a e(n)∧m e(n)) （12－13） (a 0∨M 0)∧(a 1∨M 1)∧…∧(a e(n)∨M e(n)) （12－14） 其中a i 为布尔常元，m i 与M i 分别是极小项与极大项，且两式对x 1 ,x 2 ,…,x n 一切的取值可能均与f(x 1 ,x 2 ,…,x n )等值． 习题解答 练习12.2 l. 图12.11中各哈斯图是否表示有补格？ （a）（b）（C）（d） 图12.11 解（a）（C）（d）不是有补格，（b）是有补格。 2．证明：在有界分配格中,拥有补元的所有元素可以构成一个子格。 证设有补元的所有元素组成集合S，只要证明S对∨，∧运算封闭。设a,b S,分别有补元a’,b’。考虑a∨b和a∧b，由于 （a∨b）∨（a’∧b’）= （a∨b∨a’）∧（a∨b∨b’）= 1 （a∨b）∧（a’∧b’）= （a∧b∧a’）∨（a∧b∧b’）= 0 故（a∨b）’=（a’∧b’） 同理可证（a∧b）’=（a’∨b’）。 因此，S对∨，∧运算封闭，可以构成一个子格。 3. 设< L，∨,∧>为有补分配格，a,b为L中任意元素，证明： b’≤ a’当且仅当a∧b’ = 0当且仅当a’∨b = 1 证设b’≤ a’，那么a∧b’ = a∧（a’∧b’）= （a∧a’）∧b’ = 0∧b’ = 0。 设a∧b’ = 0，那么（a∧b’）’ = 0’,即a’∨b = 1。 设a’∨b = 1，那么b’∧a’= 0∨(b’∧a’) = (b’∧b)∨(b’∧a’) = b’∧(b∨a’) = b’∧1= b’ 因此，b’≤a’。 4．化简下列布尔表达式: （1）（l∧a）∨（0∧a’） （2）（a∧b）∨（a’∧b∧c）∨（b∧c） （3）((a∧b’)∨c)∧（a∨b’）∧c （4）（a∧b）’∨（a∨b）’ 解（1）（l∧a）∨（0∧a’）= a （2）（a∧b）∨（a’∧b∧c）∨（b∧c）=（a∨c）∧b （3）((a∧b’)∨c)∧（a∨b’）∧c =((a∧b’)∨((a∨b’)∧c))∧c =((a∧b’)∧c)∨((a∨b’)∧c) =(a∨b’)∧c （4）（a∧b）’∨（a∨b）’=（a’∨b’）∨（a’∧b’） = a’∨b’ 5．证明下列布尔恒等式； （1）（a∧b）∨（a∧b’）∨（a’∧b）＝a∨b （2）（a∧c）∨（a’∧b）∨（b∧c）=（a∧c）∨（a’∧b） （3）（a∨b’）∧（b∨c’）∧（c∨a’）=（a’∨b）∧（b’∨c）∧（c’∨a） （4）（a∧b）∨（a’∧c）∨（b’∧c）=（a∧b）∨c （5）（a∨b∨d）∧（a’∨c∨e）＝((a∨b)∧(a’∨c))∨((a∨d)∧(a’∨e)) （6）（a∨b）∧（a’∨c）＝（a’∧b）∨（a∧c） 证（1）（a∧b）∨（a∧b’）∨（a’∧b）＝（a∧（b∨b’））∨（a’∧b） ＝（a∧1）∨（a’∧b） ＝a∨（a’∧b） ＝（a∨a’）∧（a∨b） ＝a∨b （2）（a∧c）∨（a’∧b）∨（b∧c）=（a∧c）∨（a’∧b）∨（（a∨a’）∧（b∧c）） =（a∧c）∨（a’∧b）∨（a∧b∧c）∨(a’∧b ∧c) =（a∧c）∨（a’∧b） （3）（a∨b’）∧（b∨c’）∧（c∨a’）=((a∧b)∨(a∧c’)∨(b’∧c’))∧（c∨a’） =(a∧b∧c)∨(b’∧c’∧a’) =(a∧b∧c)∨(b’∧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） 同理可证（a’∨b）∧（b’∨c）∧（c’∨a）≤（a∨b’）∧（b∨c’）∧（c∨a’） 因此（a∨b’）∧（b∨c’）∧（c∨a’）=（a’∨b）∧（b’∨c）∧（c’∨a） （4）（a∧b）∨（a’∧c）∨（b’∧c）=（a∧b）∨（（a’∨b’）∧c） =（（a∧b）∨（a’∨b’））∧（（a∧b）∨c） =（a∧b）∨c （5）（a∨b∨d）∧（a’∨c∨e）＝(a∧c)∨(a∧e)∨(b∧a’) ∨(b∧e)∨(b∧c)∨(d∧ a’)∨(d∧c)∨(d∧e) (根据（2）)) =(a∧c)∨(a∧e)∨(b∧a’)∨(b∧c)∨(d∧a’)∨(d∧c) ∨(d∧e) (根据（2）)) =(a∧c)∨(a∧e)∨(b∧a’)∨(b∧c)∨(d∧a’)∨(d∧e) ((a∨b)∧(a’∨c))∨((a∨d)∧(a’∨e))=(a∧c)∨(b∧a’)∨(b∧c)∨(a∧e)∨(d∧a’) ∨(d∧e) 故（a∨b∨d）∧（a’∨c∨e）＝((a∨b)∧(a’∨c))∨((a∨d)∧(a’∨e))。 （6）（a∨b）∧（a’∨c）＝（a’∧b）∨（a∧c）∨（b∧c） ＝（a’∧b）∨（a∧c）(根据（2）)) 6．设a，b为布尔代数B中任意元素，求证： a＝b当且仅当（a∧b’）∨（a’∧b）＝0 证必要性显然。 为证充分性，设（a∧b’）∨（a’∧b）＝0，那么 a∨(（a∧b’）∨（a’∧b）)＝a∨0 a∨（a’∧b）＝a a∨b＝a 故b≤a 。同理可证a≤b 。a＝b 得证。 7．设a, b，c，d为布尔代数B中任意元素，求证:当c∨a = b，c∧a = 0，d∨a＝b，d ∧a = 0时有b∧a = a，b∧c＝c，c = d 。 证 b∧a = (c∨a)∧a = a b∧c = (c∨a)∧c = c c = b∧c = (d∨a)∧c = d∧c ，故d≤c 。 另一方面，d∨a＝b，于是(d∨a)∧c＝b∧c＝c，即(d∧c)∨(c∧a)=c, d∧c=c, 故c≤d 。因此c = d 。 8．试证明:在布尔同态的定义（定义12.12）中,式（12－9）和式（12－10）两条件之一可省去。 证设 h(a∨b)= h(a)∨h(b）（12-9），那么 h(a∧b)=h((a’∨b’)’)=(h(a’)∨h(b’))’=((h(a))’∨(h(b))’)’=h(a)∧h(b) （12-10） 设h(a∧b)＝h(a)∧h(b)（12-10）,同理可证h(a∨b)= h(a)∨h(b)（12-9）。 （注意，以上证明需应用 h(a’)=(h(a))’（12-11）） 9．设 h是布尔代数B1和B2的格同态（即仅满足式(12－9)和式(12-10)），同时h(O)= 0，h(1)=1。证明h是B1,B2之间的布尔同态。 证h(a)∨h(a’)= h(a∨a’)=h(1)=1，同理h(a’)∨h(a)=1。 h(a)∧h(a’)= h(a∧a’)=h(0)=0，同理h(a’)∧h(a)=0。 故h(a’)=(h(a))’（12-11）。h是B1,B2之间的布尔同态。 10．设< B，∨，∧，’，0，1>为布尔代数，定义 B上环和运算⊕：对任意a，b ∈ B， a⊕b =（a∧b’）∨（a’∧b） （1）证明:< B，⊕>为一阿贝尔群。 （2）证明: 证（1）⊕运算满足交换律是显然的。且容易验证0是⊕运算的幺元： a⊕0 =（a∧0’）∨（a’∧0）= a∧1= a 0⊕a =（0∧a’）∨（0’∧a）= 1∧a= a 最后，可验证：任何元素x的逆元为x，因为 x⊕x =（x∧x’）∨（x’∧x）= 0∨0 =0 （2）已知< B，⊕>为一阿贝尔群。需证 事实上1是∧运算的幺元，∧运算满足结合律， 11．设< B，∨，∧，’，0，1>为布尔代数，a ∈ B 。称a是极小的，如果a ≠O且对 于任意x ∈ B，有 x≤a蕴涵x=a或x=0 证明:a是极小的当且仅当a是原子。 证若a是原子，0 设a是极小的，那么a ≠0。若a不是原子，那么有b , 0 12. 不利用布尔代数表示定理，证明没有恰含3个元素的布尔代数。 证设布尔代数B恰含3个元素：0，1，b 。那么b’= 0，1，b,都将引起矛盾，因此没有恰含3个元素的布尔代数。 13．设< B，∨，∧，’，0，1>为布尔代数, k∈B，h:B→B为如下定义的映射；对任何x∈ B， h(x) = x∨k （1）问h是否为一布尔同态，为什么？ （2）证明< h(B)，∨，∧，’，k，1>为一布尔代数。 解（1）h是格同态，不是一布尔同态，因为 h(x)∨h(y)= x∨k∨y∨k= x∨y∨k= h(x∨y) h(x)∧h(y)= (x∨k)∧(y∨k)= (x∧y)∨k=h(x∧y) 但 h(x’) = x’∨k ，(h(x))’=(x∨k)’= x’∧k’ h(x’)≠(h(x))’ 证（2）显然< h(B)，∨，∧，’，k，1>为分配格对运算∨，∧封闭，且k，1分别为下界和上界。由于 h(x)∨h(x’)= h(x∨x’)=h(1)= 1∨k=1 h(x)∧h(x’)= h(x∧x’)=h(0)= 0∨k=k 故(h(x))’= h(x’), 补运算’对h(B)封闭，且 k’=(h(0))’= h(0’)= h(1)=1 1’=(h(1))’= h(1’)= h(0)= k 因此< h(B)，∨，∧，’，k，1>为有补分配格，亦即一布尔代数。 14．已知<{0,a,b,1}，∨，∧，’，0，1>为布尔代数,其上有布尔函数: f(x1,x2,x3)=(a∧x1∧x2’)∨(x1∧(x3∨b)) （1）求 f(b，l，a)的值． （2）求f(x1,x2,x3)的主析取范式与主合取范式。 解（1）f(b，l，a)= (a∧b∧l’)∨(b∧(a∨b)) = 0∨(b∧(a∨b)) =b （2）f(x1,x2,x3)=(a∧x1∧x2’)∨(x1∧(x3∨b)) =(a∧x1∧x2’)∨(x1∧x3)∨(b∧x1) =(a∧x1∧x2’∧x3)∨(a∧x1∧x2’∧x3’)∨(x1∧x2∧x3)∨(x1∧x2’ ∧x3)∨(b∧x2∧x1)∨(b∧x1∧x2’) =(a∧x1∧x2’∧x3’)∨(x1∧x2∧x3)∨(x1∧x2’∧x3)∨(b∧x1∧x2∧ x3)∨(b ∧x1∧x2∧x3’)∨(b ∧x1∧x2’∧x3)∨(b ∧x1∧x2’∧x3’) =(x1∧x2’∧x3’)∨(x1∧x2∧x3)∨(x1∧x2’∧x3)∨(b ∧x1∧x2∧ x3’) f(x1,x2,x3)=(a ∧x1∧x2’)∨(x1∧(x3∨b)) =(a ∨x1)∧x1∧(x2’∨x1)∧((a ∧x1∧x2’)∨(x3∨b)) =(a ∨x1)∧(x2’∨x1)∧(a ∨x3∨b)∧(x1∨x3∨b)∧(x2’∨x3∨b) =(a ∨x1)∧(x2’∨x1)∧x3 =(a ∨x1∨x2)∧(a ∨x1∨x2’)∧(x1∨x2’∨x3)∧(x1∨x2’∨x3’)∧x3 =(a ∨x1∨x2∨x3’)∧(x1∨x2’∨x3’)∧(x1∨x3)∧(x1’∨x3) =(a ∨x1∨x2∨x3’)∧(x1∨x2’∨x3’)∧(x1∨x2∨x3)∧(x1∨x2’∨x3) ∧(x1’∨x2∨x3)∧(x1’∨x2’∨x3) *15. 设a,b 为布尔代数B 的两个常元，且a ∧b = a ，证明下列方程组： ???=∧=∨0 a x b a x 有惟一解x = a ’∧b 。 证 由 x ∨a = b 得a ’∧(x ∨a)= a ’∧b ，即a ’∧x = a ’∧b 。于是 (a ’∧x)∨(x ∧a) = (a ’∧b)∨0 x = a ’∧b 若x ≠a ’∧b ，那么(a ’∧x)∨(x ∧a)≠(a ’∧b)∨0，a ’∧(x ∨a)≠a ’∧b ，进而x ∨a ≠b 。 因此x = a ’∧b 是方程组的惟一解。 第七章 格与布尔代数 1. 说明什么叫格？ 2. 给定偏序集 a ∧ b 表示（ ）。 7. 说明什么叫子格？ 8. 给定偏序集 14. 请说出什么叫分配格？ 15. 指出判定一个格是分配格的充分且必要条件是在该格中没有任何子格与两个五元素非分配格之一同构。请画出这两个五元素非分配格。 16. 下面具有五个元素的格中，哪些是分配格？ 17.具有五个元素的格中，有几个不是分配格？请画出这些非分配格的图。 18. 验证下面格不是分配格。 19. 验证下面格不是分配格。 a b c d e 离散数学习题解答 习题五（第五章 格与布尔代数） 1．设〈L ，?〉是半序集，?是L 上的整除关系。问当L 取下列集合时，〈L ，?〉是否是格。 a) L={1，2，3，4，6，12} b) L={1，2，3，4，6，8，12} c) L={1，2，3，4，5，6，8，9，10} [解] a) 〈L ，?〉是格，因为L 中任两个元素都有上、下确界。 b) 〈L ，?〉不是格。因为L 中存在着两个元素没有上确界。 例如：8 12=LUB{8，12}不存在。 c) 〈L ，?〉不是格。因为L 中存在着两个元素没有上确界。 1 6 3 1 2 4 8 63 1 2 4 1 1 倒例如：46=LUB{4，6}不存在。 2．设A ，B 是两个集合，f 是从A 到B 的映射。证明：〈S ，?〉是〈2B ，?〉的子格。其中 S={y|y=f (x)，x ∈2A } [证] 对于任何B 1∈S ，存在着A 1∈2A ，使B 1=f （A 1），由于f(A 1)={y|y ∈B ∧(x)(x ∈A 1∧f (x)=y)}?B 所以B 1∈2B ，故此S ?2B ；又B 0=f (A)∈S (因为A ∈2A )，所以S 非空； 对于任何B 1，B 2∈S ，存在着A 1，A 2∈2A ，使得B 1=f (A 1)，B 2=f (A 2)，从而 L ∪B{B 1，B 2}=B 1∪B 2=f (A 1)f (A 2) =f (A 1∪A 2) （习题三的8的1）） 由于A 1∪A 2?A ，即A 1∪A 2∈2A ，因此f (A 1∪A 2)∈S ，即上确界L ∪B{B 1，B 2}存在。 对于任何B 1，B 2∈S ，定义A 1=f –1 (B 1)={x|x ∈A ∧f (x)∈B 1}，A 2=f -1 (B 2)={x|x ∈A ∧f (x)∈B 2}，则A 1，A 2∈2A ，且显然B 1=f (A 1)，B 2=f (A 2)，于是 GLB{B 1，B 2}=B 1∩B 2=f (A 1)∩f (A 2) ?f (A 1∩A 2) （习题三的8的2）） 又若y ∈B 1∩B 2，则y ∈B ，且y ∈B 2。由于y ∈B 1=f (A 1)={y|y ∈B ∧(x)(x ∈A 1∧f (x)=y)}，于是存在着x ∈A 1，使f (x)=y ，但是f (x)=y ∈B 2。故此x ∈A 2=f -1 (B 2)={x|x ∈A ∧f(x)∈B 2}，因此x ∈A 1∩A 2，从而y=f (x)∈f (A 1∩A 2)，所以 GLB{B 1，B 2}=B 1∩B 2=f (A 1)∩f (A 2) ?f (A 1∩A 2) 9 7 31 第四章代数结构（作业） 作业：P86：4、7、9 4、 （1）若a和b是整数，则a+b+ab也是整数，故a*b也是整数，所以运算*是封闭的。（2）任选整数集合中的三个元素x,y和z。则有： (x*y)*z = (x+y+xy)*z = (x+y+xy)+z+(x+y+xy)×z = x+y+z+xy+xz+yz+xyz x*(y*z) = x*(y+z+yz) = x+(y+z+yz)+x×(y+z+yz) = x+y+z+yz+xy+xz+xyz = (x*y)*z 因此，*运算满足结合律。 （3）假设e为（Z,*）的幺元，则有： 任选整数集中的一个元素x，都有 0*x = 0+x+0×x=x且 x*0 = x+0+x×0=x 故0是(Z,*)的幺元。 7、N+上的所有元素都是（N+ ,*）等幂元； （N+ ,*）无幺元； （N+ ,*）的零元为1。 9、（A,*）中的等幂元：a、b、c、d； （A,*）中的幺元：b； （A,*）中的零元：c； a-1 = d，b-1 = b，c-1 不存在，d-1 = a， 作业：P87：12、13、18 12、（A，*）到（N4,⊕4）的同构映射f为： f(a)=0, f(b)=1, f(c)=2, f(d)=3; 或者： f(a)=0, f(b)=3, f(c)=2, f(d)=1; 13、同构映射f为： f(0)=?, f(1)={a}, f(2)={b}, f(3)={a,b}; 或者： f(0)=?, f(1)={b}, f(2)={a}, f(3)={a,b}; 18、任选a ∈N +,b ∈N +, 只需证明f(a+b)=f(a)+f(b) 由f 的定义可知：f(a+b)=2a+2b=f(a)+f(b)，故f 是（N +,+）到(E +,+)的同态映射。 作业：P96：3，P97：7 3、(1)显然，*运算对Z 是封闭的。 (2) (a*b)*c = (3(a+b+2)+ab)*c = 3((3(a+b+2)+ab)+c+2)+(3(a+b+2)+ab)×c = 3(3a+3b+c+ab+8+ac+bc+2c)+abc = 3(3a+3b+3c+ab+ac+bc+8)+abc a*(b*c) = a*(3(b+c+2)+bc) = 3(a+(3(b+c+2)+bc)+2)+a(3(b+c+2)+bc) = 3(a+3b+3c+bc+8+ab+ac+2a)+abc = 3(3a+3b+3c+ab+ac+bc+8)+abc = (a*b)*c 故*运算满足结合律。 （3）任选a ∈Z ，(-2)*a=a 且a*(-2)=a ，所以-2是(Z,*)的幺元。 所以（Z,*）是独异点。 7、因为1为(A,*)运算的幺元，而且对任意A 的子集A ’,*在A ’上都是封闭和可结合的运算，因此，（A,*）的所有子独异点为(A ’,*)，其中A ’必须包含1。即：(A,*)的所有子独异点为： ({1},*),({1,2},*),({1,3},*),({1,4},*),({1,2,3},*),({1,2,4},*),({1,3,4},*),({1,2,3,4},*) P105：3、4、13 3、??????1100b a ×??????220 0b a ＝??? ?? ?212100b b a a ,a 1,a 2∈{1,-1}, 所以a 1×a 2∈{1,-1}，b 1×b 2∈{1,-1}。 故（G,×）是封闭的。 而 (??????1100b a ×??????2200b a )×??????3300b a =??????212 100b b a a ×????? ?3300b a =??????3213 2100b b b a a a ??????1100b a ×(????? ?22 00b a ×??????3300b a )=??????1100b a ×??????323 200b b a a =??????3213210 0b b b a a a 故（G,×）是可结合的。（也可以说因为矩阵乘法是可结合的。） 、选择题(每小题2分，共30分) 1、N 是自然数集， 是小于等于关系, 则 N, 是(C )。 (A)有界格 (B) 有补格 (C)分配格 (D) 2、在有界格中，若只有一个元素有补元, 有补分配格 则补元( C ) (A)必唯 (B) 不唯 (C)不一定唯 (D) 可能唯 3、 F 面是一些偏序集的哈斯图，判断哪一个为格( C ) d c e e e c D A C B D ) (A)分配格 (B)有补格 (C)布尔格 (D) 有界格 6设L,是一条链，其中L -3，贝U L, ( C ) (A)不是格 (B) 是有补格 5、只含有有限个元素的格称为有限格, 有限格必是( (C)是分配格 (D) 是布尔格 7、 设A 为一个集合， P(A), 为有补格，P(A)中每个元素的补元(A ) (A) 存在且唯一 (B) 不存在 (C)存在但不唯一 (D)可能存在 8、 设 代 是一个有界格，若它也是有补格，只要满足( B ) (A)每个元素都有一个补元 (B)每个元素都至少有一个补元 9、如下哈斯图(C )表示的关系构成有补格。 (C)每个元素都无补元 (D)每个元素都有多个补元 10、如图给出的哈斯图表示的格中( (A)a (C)e (D) f 11、设格 B, 2如图所示，它们的运算分别为 和，。令 f(a) X !, f(b) X 2, f (c) X 4, f (d) X 8，则 f ( B ) B )元素无补元。 d g c (A)是格同态映射 (B)不是格同态映射 系。贝U 30的补元为 (B) 30 (D) 70 f (a) 2 f(b)是格同构的( (B)充分条件 ,其中定义为：对于n 1 , n 2 L, n 1 n 2 当且仅当n 1是n 2的因子。问其中哪几个偏序集是格(说明理由)。(共6 分) a)、L {1,2,3,4,6,12} b)、L {1,2,3,4,6,8,12,14} C)、L {1,2,3,4,5,6,7,8,9,10,11,12} 、图中为格L 所对应的哈斯图。(共10分) (C) 是格同构映射 (D) 是自同态映射 (A) 2n (B) (C) 2n (D) 4n 13、在布尔格 A, 中有3个原子a 1,a 2,a 3则6 ( B ) (A) a 2 a 3 (B) a 2 a 3 (C) a 2 a 3 (D) a 2 a 3 14、在布尔格 代 中, A {X | X 是5的整数倍且是210的正因子} , |为整除关 (A)15 (C)35 15、设A, 1和 B, 2 是两个格, f 是A 到B 的双射，则对任意的a,b A ，有 (A)必要条件 (C)充要条件 (D)既不充分也不必要 、由下列集合L 构成的偏序集 L, 一、格的引入 在上一章中讨论过偏序集与偏序关系时,已经把格定义为一种特殊的偏序集。下面, 先 回顾一下几个有关概念。 设 第十二章 格和布尔代数 12.1 设c b a ,,是格),( A 中的元素，求证：如果b a ，则)()(c a b c b a ∨∧∧∨ 证明 因为b a ，且)(c a a ∨ ，所以)(c a b a ∨∧ 。 又因为b c b ∧，且c a c c b ∨∧ ，所以)(c a b c b ∨∧∧ 。 即)(c a b ∨∧是a 和c b ∧的上界，从而有： )()(c a b c b a ∨∧∧∨ 。 12.2 设c b a ,,是格),( A 中的元素，求证： （1）)()()(c a b a c b a ∨∧∨∧∨ （2）)( )()(c b a c a b a ∨∧∧∨∧ (1)证明 因为c a a b a a ∨∨ ,，所以)()(c a b a a ∨∧∨ 。 又因为b a b c b ∨∧ ，且c a c c b ∨∧ ，所以)()(c a b a c b ∨∧∨∧ 。 即)()(c a b a ∨∧∨是a 和c b ∧的上界。 所以，)()()(c a b a c b a ∨∧∨∧∨ 。 （2）证明 因为a b a ∧，a c a ∧，则有a c a b a )()(∧∨∧。 又因为b b a ∧，有c b b b a ∨∧ ，同理c b c a ∨∧ 。从而有c b c a b a ∨∧∨∧ )()(。 即)()(c a b a ∧∨∧是a 和c b ∨的下界。 因此，)( )()(c b a c a b a ∨∧∧∨∧ 。 10.3 设),,(∧∨A 是一个代数系统，其中∨和∧是满足吸收律的二元运算，证明：∨和∧也满足等幂律。 证明 因为∨和∧是满足吸收律，所以a b a a =∨∧)(，a b a a =∧∨)(。于是有： )((b a a a a a ∧∨∧=∧ )(c a a ∨∧= （其中b a c ∧=） a = 同理可证，a a a =∨。 故∨和∧也满足等幂律。 10.4 证明：一个格是可分配的，当且仅当对于这个格中的任意元素a ，b 和c ，有 )()(c b a c b a ∧∨∧∨ 证明 （1）必要性 因为a c a ∧和c b c b ∧∧ ，所以)()()(c b a c b c a ∧∨∧∨∧ 。 又因为格为分配格，所以)()()(c b c a c b a ∧∨∧=∧∨。 因此，)()(c b a c b a ∧∨∧∨ 。 （2）充分性 因为对于c b a ,,?，有)()(c b a c b a ∧∨∧∨ ，则 )()()(c c b a c b a ∧∧∨=∧∨ （等幂律） c c b a ∧∧∨=))(( （结合律） c c b a ∧∧∨))(( （假设） c a c b ∧∨∧=))(( （交换律） )()(c a c b ∧∨∧ （假设） 又因为b a a ∨ ，c c ，所以c b a c a ∧∨∧)( ；同理，c b a c b ∧∨∧)( 因此，c b a c b c a ∧∨∧∨∧)()()( 综上所述，)()()(c b c a c b a ∧∨∧=∧∨ 故该格是可分配的。 10.5 证明一个格),( A 是分配的，当且仅当对A 中的任意元素a ，b 和c ，有 )()()()()()(a c c b b a a c c b b a ∨∧∨∧∨=∧∨∧∨∧ 《离散数学》代数结构部分练习题参考答案 2018年6月 一、填空题 1.在代数系统（N ，+）中，其单位元是0，仅有单位元0有逆元. 2.设A 是非空集合，集合代数),),(( A P 中，)(A P 对运算 的单位元是?，零元是 A.)(A P 对运算 的单位元是A . 3.设Z 为整数集，若1,,-+=∈?b a b a Z b a ，则Z a ∈?，a 的逆元=-1a 2－a . 4.设}3,2,1,0{4=Z ，?为模4乘法，即4mod )(xy y x =?，4,Z y x ∈?.则4Z 上运算?的运算表为.（略） 二、选择题 1.设集合{}10,...,3,2,1=A ,在集合A 上定义运算,不是封闭的为(A ) (A){}b a lcm b a A b a ,,,=?∈?(最小公倍数)(B){}b a ged b a A b a ,,,=?∈?(最大公约数) (C){}b a b a A b a ,max ,,=?∈?(D){} b a b a A b a ,min ,,=?∈?2.在自然数集N 上定义的二元运算?,满足结合律的是 (C )(A)b a b a -=?(B)b a b a 2+=?(C){}b a b a ,max =?(D)b a b a -=?三、解答题 1.通常数的乘法运算是否可以看成是下列集合上的二元运算，说明理由. （1）{}2,1=A （2）{}是质数x x B =（3）{}是偶数x x C =（4）{}N n D n ∈=2解：（1）数的乘法运算不是集合A 上的二元运算.因为A ?=?422（2）数的乘法运算不是集合B 上的二元运算.因为质数与质数的乘积不是质数. （3）数的乘法运算是集合C 上的二元运算.因为偶数乘偶数是偶数. （4）数的乘法运算是集合D 上的二元运算.因为D n m m n ∈=?+222. 2.实数集R 上的下列二元运算是否满足结合律与交换律？ 第5章：格与布尔代数 格与布尔代数是代数系统中的又一类重要代数系统。这两个代数系统与第4章讨论的代数系统之间存在着一个重要的区别：在格与布尔代数中，偏序关系具有重要的意义。为了强调偏序关系的作用，我们将分别从偏序关系和代数系统两个方面引入格的概念。 给格附加一定的限制后，格就转化为布尔代数，即布尔代数是一种特殊的格。 布尔代数最初是作为对逻辑思维法则的研究而出现的，创立者是英国哲学家和数学家布尔（G .Boole ）。自布尔之后，许多数学家对布尔代数的一般化作了许多努力，特别是斯通（M.H.Stone ），他的工作可以说是对现代布尔代数的发展开创了一个新阶段。 1938年，香农（C.E.Shannon ）发表了《继电器和开关电路的符号分析》一文，为布尔代数在工艺技术中的应用开创了道路，从而出现了开关代数。为了给开关代数奠定基础，于是自然形成了二值布尔代数，即逻辑代数。自香农之后，人们应用布尔代数对电路作了大量研究，并形成了网络理论。 格与布尔代数不仅是代数学的一个分支，而且在近代解析几何、半序空间等方面也都有重要的作用，同时，格与布尔代数在计算机科学中也有十分重要的作用，可直接用于开关理论和逻辑设计、密码学、计算机理论科学等。 §5.1 偏序关系与偏序集 1. 基本概念 我们常用关系对集合的某些元素或全体元素进行排序。例如，使用包含着字对> 格与布尔代数试题1 一、选择题（每小题2分，共30分） 1、N 是自然数集，≤是小于等于关系，则≤><,N 是（C ）。 )(A 有界格 )(B 有补格 )(C 分配格 )(D 有补分配格 2、在有界格中，若只有一个元素有补元，则补元（C ）。 )(A 必唯一 )(B 不唯一 )(C 不一定唯一 )(D 可能唯一 3、下面是一些偏序集的哈斯图，判断哪一个为格（C ） f g c e a e c d f d e b c a e b A B C D 4、以下为4个格对应的哈斯图，（ D ）是分配格。 A B C D 5、只含有有限个元素的格称为有限格，有限格必是（ D ） )(A 分配格 )(B 有补格 )(C 布尔格 )(D 有界格 6、设≤><,L 是一条链，其中3≥L ，则≤><,L （ C ） )(A 不是格 )(B 是有补格 )(C 是分配格 )(D 是布尔格 7、设A 为一个集合，?><),(A P 为有补格，)(A P 中每个元素的补元（ A ） )(A 存在且唯一 )(B 不存在 )(C 存在但不唯一 )(D 可能存在 8、设≤><,A 是一个有界格，若它也是有补格，只要满足（ B ） )(A 每个元素都有一个补元 )(B 每个元素都至少有一个补元 )(C 每个元素都无补元 )(D 每个元素都有多个补元 9、如下哈斯图（ C ）表示的关系构成有补格。 A B C D 10、如图给出的哈斯图表示的格中（ B ）元素无补元。 a b d f g )(A a )(B c )(C e )(D f 11、设格>≤<>≤<21,,B A 和如图所示，它们的运算分别为?⊕∧∨，和,。令8421)(,)(,)(,)(x d f x c f x b f x a f ====，则f （ B ） )(A 是格同态映射 )(B 不是格同态映射 )(C 是格同构映射 )(D 是自同态映射 12、有限布尔代数的元素的个数必定等于（ C ） )(A n 2 )(B 2n )(C n 2 )(D n 4 13、在布尔格≤><,A 中有3个原子321,,a a a 则=1a （ B ） )(A 32a a ∧ )(B 32a a ∨ )(C 32a a ∧ )(D 32a a ∨ 14、在布尔格≤><,A 中，}2105|{的正因子的整数倍且是是X X A =，|为整除关系。则30的补元为（ C ） )(A 15 )(B 30 )(C 35 )(D 70 15、设>≤<>≤<21,,B A 和是两个格，的双射到是B A f ，则对任意的A b a ∈,，有)()(21b f a f b a ≤?≤是格同构的（ C ） )(A 必要条件 )(B 充分条件 )(C 充要条件 )(D 既不充分也不必要 二、由下列集合L 构成的偏序集≤><,L ，其中≤定义为：对于1n ， 2n ,L ∈1n ≤2n 当且仅当1n 是2n 的因子。问其中哪几个偏序集是格（说明理 由）。（共6分） 《离散数学》第三部分----代数结构 一、选择或填空 1、设A={2,4,6}，A上的二元运算*定义为：a*b=max{a,b}，则在独异点 答：单位元，1 8、素数阶群一定是( )群, 它的生成元是( )。 答：循环群，任一非单位元 9、设〈G,*〉是一个群，a,b,c∈G，则 (1) 若c*a=b，则c=( )；(2) 若c*a=b*a，则c=( )。 答：（1）b1- *a(2) b 10、 第七章 格与布尔代数 1. 说明什么叫格？ 2. 给定偏序集 a ∧ b 表示（ ）。 7. 说明什么叫子格？ 8. 给定偏序集 14. 请说出什么叫分配格？ 15. 指出判定一个格是分配格的充分且必要条件是在该格中没有任何子格与两个五元素非分配格之一同构。请画出这两个五元素非分配格。 16. 下面具有五个元素的格中，哪些是分配格？ 17.具有五个元素的格中，有几个不是分配格？请画出这些非分配格的图。 18. 验证下面格不是分配格。 19. 验证下面格不是分配格。 a b c d e 第十章 格和布尔代数 习题10.1 1．解 ⑴不是，因为L 中的元素对{2,3}没有最小上界； ⑵是，因为L=｛1,2,3,4,6,9,12,18,36｝任何一对元素a ,b ，都有最小上界和最大下界； ⑶是，与⑵同理； ⑷不是，因为L 中的元素对{6,7}没有最小上界不存在最小上界。 2．证明 ⑴因为，a ≤b,所以，a ∨b=b ；又因为，b ≤c,所以，b ∧c=b 。故a ∨b=b ∧c ； ⑵因为，a ≤b ≤c,所以，a ∧b=a,b ∧c=b,而a ∨b=b ，因此，(a ∧b )∨(b ∧c )=b ； 又a ∨b=b,b ∨c=c,而b ∧c=b, 因此，(a ∨b )∧(b ∨c )=b 。即 (a ∧b)∨(b ∧c)=(a ∨b)∧(b ∨c)。 习题10.2 1．解 由图1知：＜S 1,≤＞不是＜L,≤＞的子格，这是因为，e ∨f=g ?S 1; ＜S 2,≤＞不是＜L,≤＞的子格， ∵e ∧f=c ?S 2; ＜S 3,≤＞是＜L,≤＞的子格. 2．解 S 24的包含5个元素的子格有如下的8个： S 1={1,3,6,12,24}, S 2={1,2,6,12,24}, S 3={1,2,4,12,24}, S 4={1,2,4,8,24}, S 5={1,2,3,6,12}, S 6={1,2,4,6,12}, S 7={2,4,6,12,24}, S 7={2,4,8,12,24}. 3．证明 因为，一条线上的任何两个元素都有（偏序）关系，所以，都有最大下界和最小上界，故它是格，又因为它是 布尔代数是计算机逻辑设计的基础，它是由格引出的，格又是从偏序集引出的。所以我们先回顾一下偏序集。 2.B的最小元与最大元 y是B的最小元??y∈B∧?x(x∈B→y≤x) y是B的最大元??y∈B∧?x(x∈B→x≤y) {2,3,6}的最小元:无最大元: 6 B如果有最小元(最大元), 则是唯一的。3.B的下界与上界 y是B的下界??y∈A∧?x(x∈B→y≤x) y是B的上界??y∈A∧?x(x∈B→x≤y) {2,3,6}的下界:1 上界: 6,12,24,36 4.B的最大下界(下确界)与最小上界(上确界)24 。36 。12。 ６。２。３。 １。 y是B的最大下界(下确界)：B的所有下界x,有x≤y。 y是B的最小上界(上确界)：B的所有上界x,有y≤x。 {2,3,6}下确界:1 上确界:6 (B若有下(上)确界，则唯一) 2 一 . 基本概念 1.格的定义 一、选择题（每小题2分，共30分） 1、N 是自然数集，≤是小于等于关系，则≤><,N 是（C ）。 )(A 有界格 )(B 有补格 )(C 分配格 )(D 有补分配格 2、在有界格中，若只有一个元素有补元，则补元（C ）。 )(A 必唯一 )(B 不唯一 )(C 不一定唯一 )(D 可能唯一 3、下面是一些偏序集的哈斯图，判断哪一个为格（C ） f g c e a e c d f d e b c a e b A B C D 4、以下为4个格对应的哈斯图，（ D ）是分配格。 A B C D 5、只含有有限个元素的格称为有限格，有限格必是（ D ） )(A 分配格 )(B 有补格 )(C 布尔格 )(D 有界格 6、设≤><,L 是一条链，其中3≥L ，则≤><,L （ C ） )(A 不是格 )(B 是有补格 )(C 是分配格 )(D 是布尔格 7、设A 为一个集合，?><),(A P 为有补格，)(A P 中每个元素的补元（ A ） )(A 存在且唯一 )(B 不存在 )(C 存在但不唯一 )(D 可能存在 8、设≤><,A 是一个有界格，若它也是有补格，只要满足（ B ） )(A 每个元素都有一个补元 )(B 每个元素都至少有一个补元 )(C 每个元素都无补元 )(D 每个元素都有多个补元 9、如下哈斯图（ C ）表示的关系构成有补格。 A B C D 10、如图给出的哈斯图表示的格中（ B ）元素无补元。 a b d f g )(A a )(B c )(C e )(D f 11、设格>≤<>≤<21,,B A 和如图所示，它们的运算分别为?⊕∧∨， 和,。令8421)(,)(,)(,)(x d f x c f x b f x a f ====，则f （ B ） 授课时间第十三周第1/2 次课 注意：这里出现的∨和∧符号只代表格中的运算，而不再有其他的含义. 格的实例 例设n是正整数，Sn是n的正因子的集合. D为整除关系，则偏序集 例判断下列偏序集是否构成格，并说明理由. (1) 《离散数学》第4次作业 一、填空题 1. 设A = {1, 2, 3, {1, 2}, {3}}, B = {2, {2,3}, {1}} , 则A–B = { }, B–A = { }, A⊕B = { }. 2. 实数集合R关于加法运算“+”的单位元为( ), 关于乘法运算“?”的单位元为( ), 关于乘法运算“?”的零元为( ). 3. 令Z(x): x是整数，O(x): x是奇数，则“不是所有整数都是奇数”符号化为( ). 4. 有限域的元素个数为( ), 其中( )且( ). 5. 设G是(7, 15)简单平面图，则G一定( )连通图，其每个面恰由( )条边围成，G的面数为( ). 二、单选题 1. 函数的复合运算“ ”满足( ) (A)交换律. (B)结合律. (C)幂等律. (D)消去律. 2. 设集合A中有4个元素，则A上的等价关系共有( )个. (A)13 (B)14 (C)15 (D)16 3.下列代数结构(G, *)中，( )是群. (A)G = {0, 1, 3, 5}, “*”是模7加法. (B) G = Q, “*”是数的乘法. (C)G = Z, “*”是数的减法. (D) G = {1, 3, 4, 5, 9}, “*”是模11乘法. 4. 下列偏序集，( )是格. 5. 不同构的(5, 3)简单图有( )个. (A)4 (B)5 (C)3 (D)2 三、设C , :, 若g f 是满射，证明g是满射，并举例说明f不一定是满 →: B g B A f→ 射. 四、在整数集合Z 上定义关系R 如下：对于任意∈y x , Z ， y y x x R y x +=+?∈22),(. 判断R 是否具有自反性、反自反性、对称性、反对称性及传递性. 五、利用真值表求命题公式 )())(q p q p A ?→?→?= 的主析取范式和主合取范式. 六、将6阶完全无向图K 6的边随意地涂上红色或蓝色，证明：无论如何涂法，总存在红色的K 3或蓝色的K 3. 离散数学复习提纲（代数系统） 1．（1）相等关系显然是所有代数结构上的同余关系. 同余关系是相等关系的推广。 （2）同余关系也是模k相等关系（数论中也称模k同余关系）的推广。可证模k相等关系是如上定义的关于整数加、乘运算的同余关系。 设整数x,y,u,v满足x＝y（mod k）, u＝v（mod k）,那么x –y = nk,u –v = mk(n,m 为整数),于是 (x+u) – (y+v) = (n+m)k 故x+u = y+v（mod k）。 为证 xu＝yv（mod k），将 x = y+nk与u = v+mk两边分别相乘,于是有 xu – yv = ymk+vnk+nmk2 xu – yv = (ym+vn+nmk)k 由于ym+vn+nmk 为整数，xu＝yv（mod k）得证。 模k相等关系关于减运算和一元减运算（添负号运算）也是同余关系，请读者自行验证。2．设第七章格与布尔代数
离散数学习题解答(第五章)格与布尔代数
离散数学代数结构作业部分答案
格与布尔代数试题
格与布尔代数
离散数学12格和布尔代数
离散数学代数系统部分练习题参考答案2018春
格与布尔代数格与布尔代数万字
格与布尔代数试题1电子版本
离散数学-第三部分代数结构练习题答案(课件模板)
第七章 格与布尔代数
离散数学答案 第十章 格和布尔代数
7格与布尔代数
格与布尔代数试题
格与布尔代数
离散数学作业
离散数学复习提纲(代数系统)
相关主题
文本预览