离散数学习题解答
习题五（第五章 格与布尔代数）
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中任两个元素都有上、下确界。
12 4 6
2 3
1
b) 〈L，?〉不是格。因为L中存在着两个元素没有上确界。 例如：8?12=LUB{8，12}不存在。
8 10 4 12
6 3
2 1
1
c) 〈L，?〉不是格。因为L中存在着两个元素没有上确界。 倒例如：4?6=LUB{4，6}不存在。
8 10 4 6 95 2 3 7
1
2．设A，B是两个集合，f是从A到B的映射。证明：〈S，?〉是〈2B，?〉的子
格。其中
S={y|y=f (x)，x∈2A}
[证] 对于任何B1∈S，存在着A1∈2A，使B1=f（A1），由于f(A1)={y|y∈B∧(?x)(x∈
A1∧f (x)=y)}?B 所以B1∈2B，故此S?2B；又B0=f (A)∈S (因为A∈2A)，所以S非空；
对于任何B1，B2∈S，存在着A1，A2∈2A，使得B1=f (A1)，B2=f (A2)，从而
L∪B{B1，B2}=B1∪B2=f (A1)f (A2)
=f (A1∪A2) （习题三的8的1））
由于A1∪A2?A，即A1∪A2∈2A，因此f (A1∪A2)∈S，即上确界L∪B{B1，B2}存在。
对于任何B1，B2∈S，定义A1=f –1(B1)={x|x∈A∧f (x)∈B1}，A2=f-1(B2)={x|x∈A∧f (x)∈B2}，则A1，A2∈2A，且显然B1=f (A1)，B2=f (A2)，于是 GLB{B1，B2}=B1∩B2=f (A1)∩f (A2)
?f (A1∩A2) （习题三的8的2））
又若y∈B1∩B2，则y∈B，且y∈B2。由于y∈B1=f (A1)={y|y∈B∧(?x)(x∈A1∧f (x)=y)}，于是存在着x∈A1，使f (x)=y，但是f (x)=y∈B2。故此x∈A2=f-1(B2)={x|x∈A∧f(x)∈B2}，因此x∈A1∩A2，从而y=f (x)∈f (A1∩A2)，所以
2
GLB{B1，B2}=B1∩B2=f (A1)∩f (A2) ?f (A1∩A2)
这说明 GLB{B1，B2}=B1∩B2=f (A1)∩f (A2)=f (A1∩A2)于是从A1∩A2∈2A可知f (A1∩A2)∈S，即下确界GLB{B1，B2}存在。 因此，〈S，?〉是〈2B，?〉的子格。
3．设〈L，?〉是格，任取a，b∈L且a?b。证明〈B，?〉是格。其中
B={x|x∈L 且 a?x?b}
[证] 显然B?L；根据自反性及a?b?b
所以a，b∈B，故此B非空；
对于任何x，y∈B，则有a?x?b及a?y?b，由于x，y∈L，故有z1=x?y为下确界∈L存在。我们只需证明z1，z2∈B即可，证明方法有二，方法一为： 由于
a?x，所以a?x=x，于是 z1=x?y
=(a?x) ?y （利用a?x=x） =a? (x?y) （由?运算结合律）
因此a?z1；另一方面，由y?b可知y?b=b，由x?b可知x?b=b，于是
z1?b=(x?y) ?b
=x?(y?b) （由?运算结合律） =x?b （利用y?b=b） =b （利用x?b=b）
因此 z1?b，即 a?z1?b 所以z1∈B 由于a?x及a?y，所以a*x=a，a*y=a，因而
a*z2=a* (x*y)
=(a*x) *y （由*运算结合律） =a*y （利用a*x=a） =a （利用a*y=a）
因而a?z2；又由于y?b，所以y*b=y 于是
z2=x*y =x* (y*b)
=(x*y) *b （利用*运算结合律） =z2*b
从而z2?b，即a?z2?b 所以z2∈B
因此〈B，?〉是格（是格〈L，?〉的子格）。
3
方法二：根据上、下确界性质，由a?x，a?y，可得a?x*y，（见附页数）
4．设〈L，?，*，?〉是格。?a，b∈L，证明：（附页）
a?x??y，即a?z2，a?
又由x?b，y?b，可得x?y?b，x*y?y?b，即z1?b，z2?b 所以a?z1?b，a?z2?b，故此z1，z2∈B a*b?a且a*b?b?a与b是不可比较的。 [证] 先证?
用反证法，假设a与b是可比较的，于是有a?b或者b?a。 当a?b时，a*b=a与a*b?a（得a*b≠a）矛盾； 当b?a时，a*b=b与a*b?b（得a*b≠b）矛盾； 因此假设错误，a与b是不可比较的。 次证?
由于a*b?a，a*b?b。如果a*b?a，则a?b，与a和b不可比较的已知条件矛盾，所以a*b≠a，故此a*b?a；如果a*b=b，则b?a，也与a和b不可比较的已知条件矛盾，所以a*b≠b，故此可得a*b?b。 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*b?a?a?c及a*b?b?b?d 所以得到
a*b?(a?c) * (b?d)
又由 c*d?c?a?c及c*d?d?b?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*b?a?a?b，a*b?b?b?c，a*b?a?c?a可得 a*b?(a?b) * (b?c) * (c?a) 同理可得
4
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，c∈I 有 a* (b?c)=min{a，max{b，c}}
(a*b) ? (a*c)=min{min{a，b}，min{a，c}} （1）若b≤c时，当
（a） a≤b，则a≤c ，故此 min{a，max{b，c}}=min{a，c}=a
max{min{a，b}，min{a，c}}=max{a，a}=a （b）b≤a≤c ，则
min{a，max{b，c}}=min{a，c}=a
max{min{a，b}，min{a，c}}=max{b，a}=a （c）c≤a，则b≤a，因此
min{a，max{b，c}}=min{a，c}=c
max{min{a，b}，min{a，c}}=max{b，a}=c （2）若c≤b时，当
（a）a≤c，则a≤b，故此 min{a，max{b，c}}=min{a，b}
max{min{a，b}，min{a，c}}=min{a，a}=a
（b）c≤a≤b，则
min{a，max{b，c}}=min{a，b}=a
5
max{min{a，b}，min{a，c}}=max{a，c}=a
（c）b≤a，则c≤a，因此 min{a，max{b，c}}=min{a，b}=b
max{min{a，b}}，min{a，c}}=max{b，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，b∈A且a?b。证明： f (x)=(x?a) *b
是从A到B的同态函数。其它 B={x|x∈A且a?x?b}
[证] 由于a?x?a，及已知a?b，所以a?(x?a)*b；其次(x?a)*b?b，所以a?f (x) ?
b，因而f (x)是从A到B的函数。 对于任何x，y∈A， 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，c∈L，有(a*b) ? (b*c) ? (c*a)=(a?b)
* (b?c) * (c?a)
[证] 必要性。对于任何a，b，c∈L，
(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) （交换律）
6
充分性，f满足同态公式，因而f是从A到B的同态函数。 8．证明：一个格是分配格的充分必要条件是?a，b，c∈L，有
(a*b) ? (b*c) ? (c*a)=(a?b) * (b?c) * (c?a) [证] 必要性。对于任何a，b，c∈L，
(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，c∈L 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)) （吸收律，结合律） =(a? b)* (a?c) （吸收律）
根据对偶原理 还有a* (b?c)= (a?b) * (a?c) 所以格L是分配格。
9．设〈L，?〉是格。其Hasse图如右 a) 找出格中每个元素的补元；
b) 此格是有补格吗？ c) 此格是分配格吗？ [解] a)最小元0=i；最大元1=a；
故此格为有界格。
i
7
a
b
c d
e f
g h 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=h (h*f) ? (h*g)=i?i=I
24 a1
12 6 3
1
〈S24，I，GCD，LCM，1，24〉 两个不是分配格的特殊格
与两个不是分配格的特殊格同构，并且此子格必含有g点。而特殊不分配格之图或是含有五个结点的圈，或是有六个结点：gebdfi；gebdhi；gehdfi；或是有八个结：gecabdfi；gecabdhi；或是只有一个四结点的圈：gehi。因此此格绝不会有含g点的子格与两个不是分配格的特殊格同构。 10．设〈L，?，*，?〉是有界格。x，y∈L，证明： a) 若x?y=0，则x=0且y=0。
b) 若x*y=1，则x=1且y=1。 [证] a) 对任何x，y∈L，若x?y=0，则
x=x* (x?y) （吸收律） =x*0 （x?y=0） =0 （0—1律） y=y* (y?x) （吸收律） =y* (x?y) （交换律） =y*0 （x?y=0）
8
b2 4 2
a5
b5
a2
a3 a4
b3 b4 b1 8
=0 （0—1律） b) 对任何x，y∈L，若x*y=1，则 x=x? (x*y) （吸收律） =x?1 （x*y=1） =1 （0—1律） y=y? (y*x) （吸收律） =y? (x*y) （交换律） =y?1 （x*y=1） =1 （0—1律）
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中存在着以自己为补元的元素，不妨是b∈L，那么b?b=1，
b*b=0，于是由幂等律，可得 b=b*b=0，b?b=1， 从而有0=b=1，即0=1
9
因此，对于任何元素a?L，都有a=0=1（因为0?a?1），从而|L|=1，这与已知|L，|≥2矛盾。
13．设〈L，?〉是全序集，|L|≥3。证明：〈L，?〉是格，但不是有补格。 [证] 由于〈L，?〉是全序集，那么L中任意两个元素都可比较，于是L中任意两
个元素都有上确界和下确界，因此〈L，?〉是格。 下面我们来证〈L，?〉不是有补格，用反证法：
否则〈L，?〉是有补格，则对任何a∈L，都存在着一个元素b∈L，使a?b=1及a*b=0。由于〈L，?〉是全序集，所以任二元素可比较，从而
①若a?b，则a=a*b=0 ②若b?a，则a=a?b=1 因此|L|=2，与已知|L|≥3矛盾。
14．在有界的分配格中，证明：具有补元的那些元素组成一个子格。 [证] 设〈L，*，?，0，1〉是有界分配格，令 L′={x|x∈L∧(?y∈L)(x*y=0∧x?y=1)}
我们来证〈L′，*，?，0，1〉是〈L，*，?，0，1〉的子格：
显然L′?L；其次易证0，1∈L′，故此L′非空；对于任何a1，a2∈L′，
我们来证a1*a2，a1?a2∈L′
为证a1*a2∈L′，只需找出a1*a2的补元即可。由于a1，a2∈L′，故此存在着b1，b2∈L，使a1*b1=0，a1?b1=1以及a2*b2=0，a2?b2=1，于是构造出a1*a2补元为b1b2∈L。这是因为
(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 （由0—1律） =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（由0—1律） =1
为证a1?a2∈L′只需找出a1?a2的补元即可。由于a1，a2的补元是b1，b2，故构造出a1?a2的补元为b1*b2∈L。这是因为
(a1?a2) * (b1*b2)=(a1* (b1* b2)) ?(a2* (b1* b2))（分配律）
10
=((a1*b2) *b2) ? ((a2*b2) *b1)（交换律，结合律） =(0*b2) ? (0*b1)（由a1*b1=0及a2*b2=0） =0?0（由0—1律） =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 （由0—1律） =1
15．求〈S12，1〉的所有子格，其中，S12是12的所有因子
的集合1是S12上的整除关系。
[解] 一个结点：{1}，{2}，{3}，{4}，{6}，{12} 二个结点：{1，2}，{1，3}，{1，4}，{1，6}，
{1，12}
{2，4}，{2，6}，{2，12} {3，6}，{3，12} {4，12} {6，12}
三个结点：{1，2，4}，{1，2，6}，{1，2，12}〈S12，1〉的图
{1，3，6}，{1，3，12} {1，4，12} {1，6，12}
{2，4，12}，{2，6，12} {3，6，12}
四个结点：{1，2，4，12}，{1，2，6，12}，{1，3，6，12}
{1，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，c∈L，有
(a?b) *c?a? (b*c)
[证] 必要性
对任何a，b，c∈L
11
12 4 2 6 3 1
(a?b) *c=(a*c) ? (b*c) （分配律）
?a? (b*c) （由a*c?a，及保序性） 充分性
一方面，由a? (b*c)?a? b （根据b*c?b及保序性）
和a? (b*c)?a? c （根据b*c?c及保序性）
及上、下确界的性质可得
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)*b?a? (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：L1→L2是从〈L1，R1〉到〈L2，R2〉的
同态函数。证明：f的同态象是〈L2，R2〉的子格。 [证] f的同态象f (L1) = {y : y∈L2∧(?x∈L1) (f(x)=y)} 我们来证〈f (L1)，R2〉是〈L2，R2〉的子格：
显然f (L1)?L2；若L1非空，则有a∈L1，从而有b=f (a)∈f (L1)故f (L1)非空。 对于任何b1，b2∈f (L1)，存在着a1，a2∈L1，使b1=f (a1)，b2=f (a2)，从而 b1 ?2b2=f (a1) ?2f (a2)
=f (a1?1a2)（同态公式）
∈f (L1)（因〈L1，R1〉是格，故
?1运算封闭，从而a1?1a2∈L1）
因此〈f（L1），R1〉是〈L2，R2〉子格。 18．设B={1，2，5，10，11，22，55，110}。证
明：〈B，GCD，LCM〉是布尔代数。其中，GCD是求最大公约数，LCM是求最小公倍数，x′=110/x。
1
22 2 5
10 55
110
12
[证] 我们已证过〈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
=(a*b*c)?(a*b′*c′)?(a′*b*c′) ? (a′*b′*c)（交换律） *(b○*c) a○
*c)′)?(a′* (b○*c)) =(a* (b○
=(a*((b′?c) * (b?c′)))?(a′* b*c′) ?(a′* b′*c)) （de Morgam 律，反身律，分配律）
=(a* ((b*c)?(b′*c′)))?(a′*b*c′)?(a′*b′*c) （分配律） *b)○*c=a○*(b○*c) 所以 (a○
*运算具有结合律 所以○
③交换律
*b 对任何a，b∈B，a○
=(a*b′)?(a′*b)
=(a′*b)?(a*b′) （?运算交换律） =(b′*a)(b′*a) （*运算交换律） *a =b○
所以运算具有结合律
④有幺元0： 首先0∈B，其次
*0=(a*0′)?(a′*0) a○
=(a*1)(a′*0) （由0′=1） =a?0 （0—1律） =a （0—1律） *a=a 即 由运算交换律也有0○*a=a○*0=a 0○
*运算的幺元。 所以0是○
⑤于任何a∈B，其逆元是a自己，因为
*a=(a*a′)?(a′*a) a○
=0?0 （互补律） =0 （幂等律）
*〉是一个交换群。 因此，〈B，○*，′〉是一个交换群。 23．设〈B，*，○
如下
?a，b∈B，a+b=(a*b′)?(a′b)
17
a·b=a*b
a) 证明：〈B，+，·〉是环 b) 找出关于·的幺元；
c) 证明：?a∈B，a+a=0，a+0=a，a+1=a′； d) 证明：?a，b∈B，（a+b）+b=a；
e) 证明：?a，b，c∈B，a·（b+c）=(a·b)+（a·c）
*运算的定义相同，因此〈B，十〉是[证] a) 由于这里定义的十运算与22题的○
交换群。
其次·运算就是运算，故此具有封闭性及结合律，因此〈B，·〉是半群。 对任何a，b，c∈B，由于 a·(b+c)=a* ((b*c′)?(b′*c)) =(a*b*c)?(a*b*c) （分配律） (a·b)+(a·c)=((a*b) *(a*c)′)(a*b)′* (a*c) =((a*b) * (a?c))?((a?b) * (a*c)) （deMorgan律） =(a*b*c′)?(a*b′*c) （分配律，互补律，0—1律） 所以a·（b+c）=（a·b）+（a·c）
由于·和十运算都有交换律，故另一分配律不需证 所以〈B，+，·〉是环（实际上是含幺交换环） b) ·的幺元是1，因为 1·a=1*a=a=a*1=a·1
c) 对任何a∈B，a+a=0在22题的证明⑤已证； a+0=a在22题的证明中④已证；
a+1+=(a*1′)?(a′*1)
=(a*0)?(a′*1) （由1′=0） =0?a′（0—1律） =a′ （0—1律）
d) 对任何a，b∈B （a+b）+b
=((a+b) *b′)?((a+b)′*b)
=(((a*b′)? (a′*b)) *b′)?(((a*b′) * (a*b))′*b) =(a*b′*b′)?(a′*b*b′)?(((a′?b) * (a?b′)) *b)
18
（分配律，结合律de Morgan律，反身律） =(a*b′)?(((a*b)?(a′*b)) *b)
（幂等律，互补律0-1律，分配律，交换律）
=(a*b′)?(a*b*b)?(a′*b′*b)
（分配律）
=(a*b′)?(a*b)
（幂等，互补律，0-1律）
=a* (b?b) （分配律） =a （互补律，0-1律） e) 根据a) 的证明，分配律已成立。
24．设〈A，∧，∨∩∪－〉和〈B，∩，∪，－〉是两个布尔代数，f是从〈A，∧，
∨∩∪－〉到〈B，∩，∪，－〉的满同态函数。证明：
f(OA)=OB f(1A)=1B
其中，OA和OB分别是A，B中的最小元，1A和1B分别是A，B中的最大元。 [证] 对于任何a∈A，由于A是布尔代数，所以存在着补元a∈A使得
OA=a∧a 及1A=a∨a （互补律）
又由于B是布尔代数，f是从A到B的同态函数，从而有
f(a)=(f(a))′ （同态公式）
于是
f(OA)=f(a∧a)
=f(a)∩f(a) （同态公式） =f(a)∩(f(a))′ =OB （互补律） f(1A)=f(a∨a)
=f(a)∪f(a) （同态公式） =f(a)∪(f(a))′ =1B
25．设a，b，b2，…br是布尔代数〈B，?，*，?，′〉的原子。证明：ab1?b1?…
?br的充分必要条件是存在i（1≤i≤r），使a=bi。 [证] 必要性
用反证法。假设对每个i，1≤i≤r，都有a≠bi，那么由a，bi（1≤i≤r）都是原子，因此a*bi=0（否则有a=a*bi=bi，与假设a≠bi矛盾）。从而 a* (b1?b2?…?br)
19
=(a*b1)?(a*b2)?…?(a*br) （分配律） =0?0?…?0 =0 (0-1律)
但是由已知a?b1?b2? … ?br，从下确界的性质可知 a* (b1?b2?…br)=a
从而得到a=0，这与已知a是原子，a≠0矛盾， 充分性
若对某个i。1≤i0≤r，使a=bi0。则由上确界的性质可知 a?b1?b2?…? bi0-1?a? bi0+1?…?br =b1?b2?…?bi0-1? bi0+1…?br（因为a=bi0）
26．设b1，b2…，br是有限布尔代数〈B，*，?，′〉的所有原子。
证明：
y=0的充分必要条件?i（1≤i≤r），都有y*bi=0 [证] 必要性
对于任何bi（1≤i≤r） y*bi=0*bi=0总是成立，因为y=0 充分性
根据布尔代数的元素的原子表示定理，可知 y=?bi 这里S(y)={bi :1≤i≤r∧bi?y}
bi?S(y)因此，y=y*y （幂等律） =y?bi
bi?S(y) =?(y?bi) （分配律）
bi?S(y) =?0 （因为对任何i，1≤i≤r，都有y*bi=0）
bi?S(y) =0 （0-1律）
27．设〈{0，1}，*，?，′〉是布尔代数。写出下列布尔表达式的析取范式和合取
范式。
a) (x1*x2)?(x2*x3)?(x?2*x3)
??? b) (x1*x2*x?3)?(x1*x2*x4)?(x2*x3*x4)
3
[解] a) 令f(x1，x2，x3)=(x1*x2)?(x2*x3)?(x?3*x3)是{0，1}到{0，1}函数，则其
运算表为
20
x1 0 0 0 0 1 1 1 1
x2 0 0 1 1 0 0 1 1 x3 0 1 0 1 0 1 0 1 f (x1，x2，x3) 0 1 0 1 0 1 1 1 根据f (x1，x2，x3)=0的元组可构造出f的合取范式为
? (x1?x2?x3)* (x1? x?2?x3)(x2 ? x1?x3)=M3* M5* MT
根据 f (x1，x2，x3)=1的元组可构造出f的析取范式为
?? x?2?x3) ?(x1?? x2?x3)?=m1?m3?m5?m6?m7 (x1??b) 令g(x1，x2，x3，x4)=(x1* x2* x3)?( x1* x?2*x4)?(x2*x3*x4)
是{0，1}4到{0，1}的函数，于是 析取范式：
f (x1，x2，x3，x4)
??? =(x1* x2* x?3)?( x1* x2*x4) ?(x2*x3*x4)
?????? =( x1* x2* x?3( x4? x4))?( x1* x2* (x3? x3)*x4)?((x1? x1)x2*x3*x4) ????? =( x1* x2* x?3* x4)?(x1* x2*x3*x4)?( x1* x2*x3*x4)
=m4?m9?m11?m12?m13 合取范式：
(f (x1，x2，x3，x4))′（由去掉f中的那些小项后剩下的小项构成）
?? =(x1，x2，x3，x4)? (x1，x2，x3，x?4)?( x1* x2* x3*x4)
?*x2*x3*x4))? ?4)?(x1 ?( x1* x?2*x3*x?3
[解] a) 令f(x1，x2，x3)=(x1*x2)?(x2*x3)?(x?3*x3)是{0，1}到{0，1}函数，则其
运算表为
x1 0 0 0
x2 0 0 1 x3 0 1 0 21
f (x1，x2，x3) 0 1 0 0 1 1 1 1
1 0 0 1 1 1 0 1 0 1 1 0 1 1 1 根据f (x1，x2，x3)=0的元组可构造出f的合取范式为
? (x1?x2?x3)* (x1? x?2?x3)(x2 ? x1?x3)=M3* M5* MT
根据 f (x1，x2，x3)=1的元组可构造出f的析取范式为
?? x?2?x3) ?(x1?? x2?x3)?=m1?m3?m5?m6?m7 (x1??b) 令g(x1，x2，x3，x4)=(x1* x2* x3)?( x1* x?2*x4)?(x2*x3*x4)
是{0，1}4到{0，1}的函数，于是 析取范式：
f (x1，x2，x3，x4)
??? =(x1* x2* x?3)?( x1* x2*x4) ?(x2*x3*x4)
?????? =( x1* x2* x?3( x4? x4))?( x1* x2* (x3? x3)*x4)?((x1? x1)x2*x3*x4) ????? =( x1* x2* x?3* x4)?(x1* x2*x3*x4)?( x1* x2*x3*x4)
=m4?m9?m11?m12?m13 合取范式：
(f (x1，x2，x3，x4))′（由去掉f中的那些小项后剩下的小项构成）
?? =(x1，x2，x3，x4)? (x1，x2，x3，x?4)?( x1* x2* x3*x4) ????? ?( x1* x?2*x3*x4)?(x1*x2*x3*x4))? (x1*x2*x3*x4) ?*x2*x????? ?(x13*x4) ?(x1*x2*x3*x4) ?( x1* x2* x3*x4) ?*x?2*x????? ?(x13* x4) ?(x1*x2*x3*x4)
因此
f (x1，x2，x3，x4)
=(f (x1，x2，x3，x4))″ （反身律）
?? x?2?x??????? =(x13?x4)*(x1? x2?x3? x4) * (x1*x2*x3*x4) ??x2?x3?x4) * (x1? x?2?x???? * (x13?x4) * (x1? x2?x3? x4) ??x2?x3?x4) * (x1? x2? x??? * (x13? x4)( x1?x2? x3?x4)
* (x1? x2? ? x3? x?4)* (x1?x2?x3?x4)
=M0* M1* M5* M7* M8* M9* M10* M12* M13* M14* M15
22
28．设〈2X，∩，∪，′〉到〈B，∧，∨，—〉的满同态函数。
[证]（1）后者唯一
用反证法。对于任何x2X，若有y1，y2∈B，且y1y2使得g(x)=y1，且g(x)=y2，则由于
(x，y1)∈g∧(x，y2)∈g
?(x，0)∈g(x，1)∈g （由于y1≠y2，且y1，y2，且y1，y2∈B={0，1}） ?b∈x∧b?x
矛盾，故引假设y1≠y2错误，从而y1=y2，g是后者唯一的。 （2）?(g)=2X
（3）g是满射数，?(g)=B
由于B={0，1}，并且存在着x1={a，c}，和x2={a，b}使g(x1)=0，g(x2)=1，故?(g)=B。
（4）g满足同态公式，即g保持运算。 对于任何x∈2X，由于 g(x′)=1
?b∈x′ ?b?x ?g(x)=0
g(x)=1
所以g(x′)= g(x) 对于任何x1，x∈2X，由于
g(x1∩x2)=1 ?b∈x1∩x2 ?b∈x1∧b∈x2 ?g(x1)=1∧g(x2)=1 ?g(x1)∧g(x2)=1
所以 g(x1∩x2)=g(x1)∧g(x2) 由于 g(x1∪x2)=1
?b∈x1∪x2
23
?b∈x1∨b∈x2 ?g(x1)=1∨g(x2)=1 ?g(x1)∨g(x2)=1 所以 g(x1∪x2)= g(x1)∨g(x2)
综合以上四条，可知g是从〈2X，∩，∪，′〉到〈B，∧，∨，—〉到的满同态函数。
24