离散数学答案 第十章 格和布尔代数
第十章
格和布尔代数
习题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．证明 因为，一条线上的任何两个元素都有（偏序）关系，所以，都有最大下界和最小上界，故它是格，又因为它是
4．证明 由(10-4)有，a ∧b ≤a ,由已知a ≤c ,由偏序关系的传递性有，a ∧b ≤c ；
同理 a ∧b ≤d 。
由(10-5)和以上两式有，a ∧b ≤c ∧d .
5．证明 因为由(10-4)有，a ∧b ≤a ，因此，
(a ∧b )∨(c ∧d )≤a ∨(c ∧d ) ①
由分配不等式有，
a ∨(c ∧d )≤(a ∨c )∧(a ∨d ) ②
再由由(10-4)有，
(a ∨c )∧(a ∨d ) ≤a ∨c ③
由偏序关系的传递性和①②③则有，
(a ∧b )∨(c ∧d )≤a ∨c
同理 (a ∧b )∨(c ∧d )≤b ∨d
因此有， (a ∧b )∨(c ∧d )≤(a ∨c ) ∧(b ∨d )。
习题10.3
1．解 ⑴ 是，全上界是24，全下界是1；
⑵1的补元是24；3的补元是8；8的补元是3，4、6没有补元。
图1
图2
2．解 图3是两个格的哈斯图，其中图⑴是有补格但不是分配格的例子；图⑵是分配格但不是有补格的例子。
3．证明 先证充分性。由已知条件知，对于任何的a ,b ,c ∈L ,有(a ∨b )∧c ≤a ∨(b ∧c )，
因此和等幂律、交换律可得，
(a ∨b )∧c=((b ∨a )∧c)∧c≤(b ∨(a ∧c))∧c
=((a ∧c)∨b)∧c≤(a ∧c)∨(b ∧c) ①
又因为，(a ∧c)≤(a ∨b)∧c 且(b ∧c)≤(a ∨b)∧c ，
所以， (a ∧c)∨(b ∧c)≤(a ∨b)∧c ②
由①②可得， (a ∧c)∨(b ∧c)=(a ∨b)∧c
再由交换律得到， c ∧(a ∨b)=(c ∧a)∨(c ∧b) ③
由此式容易证明
c ∨(a ∧b)=(c ∨a)∧(c ∨b) ④
由③④可知它是分配格。
再证必要性。因为
(a ∨b )∧c =(a ∧c )∨(b ∧c )≤a ∨(b ∧c )。
4．证明 因为，∧∧=∨∧∧b a b a b a ()()(000)()=∨=∧∧∨b b a a ；
同理有，)()()(b a a b a b a ∨∨=∨∨∧111)(=∨=∨∧∧b a b ；
又因为补元素是唯一的，故b a b a ∨=∧)(成立。
习题10.4
1．解 是布尔代数，因为是有补分配格。
2．证明 因为，是布尔代数，所以，运算-，∨,∧在B 上都是封闭的，因此，由运算 的定义可知，运算 在B 上也是封闭的。
又运算∨,∧都满足交换律。因此，对于任意的a,b B,
)()(b a b a b a ∧∨∧=⊕=))(())((b b a a b a ∨∧∧∨∧
=)()()()(b a b a b a a b ∨∧∨=∨∧∨
由其对称性可知 满足交换律。下面证明运算 满足结合律，对于任意的a,b,c B 由上式则有
c b a b a c b a ⊕∨∧∨=⊕⊕)]()[()(
))()(())]()([(c b a b a c b a b a ∨∨∧∨∧∨∨∧∨=
])()[()()(c b a b a c b a c b a ∨∧∨∧∧∨∨∧∨∨=
)()()()(c b a c b a c b a c b a ∨∨∧∨∨∧∨∨∧∨∨=
同理可得
)(c b a ⊕⊕)()()()(c b a c b a c b a c b a ∨∨∧∨∨∧∨∨∧∨∨=
即，=⊕⊕c b a )()(c b a ⊕⊕，亦即 满足结合律。
下面再证0是关于 的单位元。事实上对于任意的a B ，
a a a a a =∨∧=∧∨∧=⊕0)1()0()0(0。
最后证明任意的a B 关于运算 都可逆，且其逆元就是a 自身，事实上
000)()(=∨=∧∨∧=⊕a a a a a a
综上所述，>⊕<,B 是交换群。
复习题十
1．证明 显然，a ,b ∈B ，所以，B 非空。
对于任意的x , y ∈B ，则a ≤x ≤b , a ≤ y ≤b ，由格的保序性和等幂律则有，
a ≤x ∨y ≤
b , a ≤x ∧y ≤b
即集合B 对于运算∨和∧是封闭的。
因此，是
2．证明 因为，
（(a ∧b ）∨(a ∧c)）∧((a ∧b)∨(b ∧c))≥(a ∧b)∨(a ∧b ∧c)=a ∧b ①
（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 ∧(b ∨c)∧(a ∨c)=a ∧b ④
由①④和反对称性则有，((a ∧b )∨(a ∧c ))∧((a ∧b )∨(b ∧c ))= a ∧b 。
3．证明 因为
(a ∧b )∨(b ∧c )∨(c ∧a ) ≤ [((a ∧b )∨b )∧((a ∧b )∨c )]∨(c ∧a )
=[b ∧((a ∧b )∨c )]∨(c ∧a ) ≤[b ∧(a ∨c )∧(b ∨c )]∨(c ∧a )
=[b ∧(a ∨c )]∨(c ∧a ) ≤(b ∨(c ∧a ))∧((a ∨c )∨(c ∧a ))
=(b ∨(c ∧a ))∧(a ∨c ) ≤ (b ∨c )∧(b ∨a )∧(a ∨c )
= (a ∨b )∧(b ∨c )∧(c ∨a )。
4．证明 因为有限格都是有界格，而有界格必存在最大元素和最小元素，故有限格一定有最大元素和最小元素。
5．证明 因为，a ≤b,所以，a ∨b=b ；因此有，a ∨(b ∧c)≤(a ∨b)∧(a ∨c)=b ∧(a ∨c)。
6．证明 因为，h 将运算∨传送到运算∪，将运算“-”传送到运算“＇”，所以，对于任意的x ,x 1,x 2∈B 1有：
h (x 1∨x 2)=h (x 1)∪h (x 2) ①
))(()('=x h x h ②
所以，对于任意的a ,b ∈B 1,而)(b b a ∨=∧，因此有：
))()(())(())(()('?='∨=∨=∧b h a h b a h b a h b a h
)()()))(())(((b h a h b h a h ?=''?'=。
即h 将运算∧传送到运算∩。
7．证明 由习题10.4第2题可知是一个交换群。由于，在布尔代数中∧是可结合的且是可交换的，由*运算的定义可知，*是可结合的且是可交换的。由*运算的定义可知可进一步看出，关于*运算的单位元是布尔代数的全上界1。事实上，对于任意的a B,有
a a a =∧=*11
因此，要证明是一个含幺交换环，只需证明*对⊕满足分配律。事实上，
对于任意的a,b,c B,
)()()]()[()(c b a c b a c b c b a c b a ∧∧∨∧∧=∧∨∧∧=⊕*
)()()()(c a b a c a b a ∧⊕∧=*⊕*
))()(())()((c a b a c a b a ∧∧∧∨∧∧∧=
))()(())()((c a b a c a b a ∧∧∨∨∨∧∧=
)()()()(c b a c a a c b a a b a ∧∧∨∧∧∨∧∧∨∧∧=
)()(c b a c b a ∧∧∨∧∧=
即 =⊕*)(c b a )()(c a b a *⊕*
综上所述，是一个含幺交换环。
第七章格与布尔代数
第七章 格与布尔代数 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,×）是可结合的。（也可以说因为矩阵乘法是可结合的。）
离散数学12格和布尔代数
第十二章 格和布尔代数 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 ∨∧∨∧∨=∧∨∧∨∧
格与布尔代数
一、格的引入 在上一章中讨论过偏序集与偏序关系时,已经把格定义为一种特殊的偏序集。下面, 先 回顾一下几个有关概念。 设
格与布尔代数试题
、选择题(每小题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,
离散数学代数系统部分练习题参考答案2018春
《离散数学》代数结构部分练习题参考答案 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 上的下列二元运算是否满足结合律与交换律？
离散数学答案 第十章 格和布尔代数
第十章 格和布尔代数 习题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．证明 因为，一条线上的任何两个元素都有（偏序）关系，所以，都有最大下界和最小上界，故它是格，又因为它是
格与布尔代数格与布尔代数万字
第5章：格与布尔代数 格与布尔代数是代数系统中的又一类重要代数系统。这两个代数系统与第4章讨论的代数系统之间存在着一个重要的区别：在格与布尔代数中，偏序关系具有重要的意义。为了强调偏序关系的作用，我们将分别从偏序关系和代数系统两个方面引入格的概念。 给格附加一定的限制后，格就转化为布尔代数，即布尔代数是一种特殊的格。 布尔代数最初是作为对逻辑思维法则的研究而出现的，创立者是英国哲学家和数学家布尔（G .Boole ）。自布尔之后，许多数学家对布尔代数的一般化作了许多努力，特别是斯通（M.H.Stone ），他的工作可以说是对现代布尔代数的发展开创了一个新阶段。 1938年，香农（C.E.Shannon ）发表了《继电器和开关电路的符号分析》一文，为布尔代数在工艺技术中的应用开创了道路，从而出现了开关代数。为了给开关代数奠定基础，于是自然形成了二值布尔代数，即逻辑代数。自香农之后，人们应用布尔代数对电路作了大量研究，并形成了网络理论。 格与布尔代数不仅是代数学的一个分支，而且在近代解析几何、半序空间等方面也都有重要的作用，同时，格与布尔代数在计算机科学中也有十分重要的作用，可直接用于开关理论和逻辑设计、密码学、计算机理论科学等。 §5.1 偏序关系与偏序集 1. 基本概念 我们常用关系对集合的某些元素或全体元素进行排序。例如，使用包含着字对>
离散数学-第三部分代数结构练习题答案(课件模板)
《离散数学》第三部分----代数结构 一、选择或填空 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
7格与布尔代数
布尔代数是计算机逻辑设计的基础，它是由格引出的，格又是从偏序集引出的。所以我们先回顾一下偏序集。
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.
第九章格与布尔代数
第九章 格与布尔代数 习题提示 9.1 下面整数集合对于整除关系都构成偏序集，判断哪些偏序集是格。 （1）L={1,2,3,4,5} （2）L={1,2,3,6,12} （3）L={1,2,3,4,6,9,12,18,38} （4）L={} 2 3 1,2,2,2,,2n 解：（1）不是格。（2）是格。（3）不是格。（4）是格。 9.2．试问下面哈斯图所示的偏序集是否是格？ 图9.2 解：（1）是格。（2）不是格。（3）不是格。（4）是格。（5）是格。（6）是格。 9.4 设G 是群，L (G )表示G 的所有子群组成的集合，L (G)的偏序关系定义为：对于任意 ，G 当且仅当，证明12,()G G L G ∈12G ≤21G G ?((),)L G ≤是格。 提示：直接验证。 9.5 设S 是非空集合，T S 是S 的非空子集，证明?()(),P T ?是()() ,P S ?的子格。
提示：关键要证格()() ,P T ?中运算与()() ,P S ?子格()P T 的运算也一致。 9.7 在格(,)+ ?Z 中（其中是正整数集合，偏序“+ Z ?”定义为：a b a b ??） ，下面的集合是否是它的子格。 （1）S={1,2,3,9,12,72} （2）S={1,2,3,12,18} （3）S={} 2 3 1,2,2,2,,2n 解：（1）和（2）都不是子格。（3）是子格。 9.10 证明如果L 是有界格，并且2L ≥，则0I ≠。 证明：如果0I =， 因为对任意L 中元x ，0x I ??，所以x I ?，I x ?。从而I x =。于2L ≥矛盾。 9.12 判断下面图所示的格是否是分配格，是否是补格。 图 9.4 解：（1）不是分配格，也不是补格。 （2）不是分配格，也不是补格。 （3）不是分配格，是补格。 9.16 在同构的意义下确定所有4个元素的格，并证明它们都是分配格。 解：（1）， 其中不可比较。（2）{0,,,}S b c =I I ,b c {0,,,}S b c =， 其中b c ?。 9.17 找出所有不同构的5元格。 解：不同构的5元格共有五个，它们的哈斯图如下：
离散数学复习提纲(代数系统)
离散数学复习提纲（代数系统） 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．设