发布时间 : 星期三 文章离散数学习题解答(第五章)格与布尔代数更新完毕开始阅读
[证] 我们已证过〈N，GCD，LCM，〉是分配格，故此为证〈B，GCD，LCM〉
是分配格，只需证〈B，GCD，LCM〉是〈N，GCD，LCM，〉的子格即可。 易于验证，对于任何a，b∈B，恒有GCD{a，b}，LCM{a，b}∈B故此两个运算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}。 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，′〉也不是布尔代数。
2 1 8 4 24 12 6 3 因为虽然〈L2，GCD，LCM，′〉是分配格（〈N，1，GCD，LCM，〉的子格），但不是有补格，元素2，4，6，12没有补元。所以也不是布尔代数。 20．设〈B，*，?，′〉是布尔代数。证明下列布尔恒等式。 a) a? (a′*b)=a?b
b) a* (a′?b)=a*b
c) (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 （0—1律）
b) a (a′?b)=(a*a′) ? (a*b)（分配律）
=1? (a*b) （由a*a′=0） = a*b （0—1律）
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，从而由保序性，得到
13
b*c≤(a?b) * (a′?c)
又由b*c≤b?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 （1—1律） =a′* b* c
14
只需证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)
15
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上定义二元运算○
*b=(a*b′)(a′*b) ?a，b∈B，a○
证明：〈B，?〉是交换群 [证] ①封闭性
*b=(a*b)?(a*)∈对于任何a，b∈B，由于*，?，′运算的封闭性，可知a○*运算具有封闭性。 B，因此○
②结合律
对于任何a，b，c∈B， *b)○*c (a○
*b)*c′)?((a○*b)′*c) ((a○
=(((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) （分配律，互补律，0—1律）
=(a*b′*c′)?(a′*b*c′)?(a*b*c) ? (a′*b′*c)
16