毕业论文中期报告-暑期活动

离散数学习题解答
习题五（第五章 格与布尔代数）
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
c) 〈L，≼〉不是格。因为L中存在着两个元素没有上确界。
106

倒例如：46=LUB{4，6}不存在。
8
10
4
6
9
5 2 3 7
1

2．设A，B是两个集合，f是从A到B 的映射。证明：〈S，⊆〉是〈2
B
，⊆〉的子格。其中
S={y|y=f (x)，x∈2
A
}
[证] 对于任何B
1
∈S，存在着A
1
∈2
A
，使B
1
=f（A
1
），由于f(A< br>1
)={y|y∈B∧(x)(x∈A
1
∧f (x)=y)}
⊆B 所以B
1
∈2
B
，故此S⊆2
B
；又B
0
=f (A)∈S (因为A∈2
A
)，所以S非空；
对于任何B
1
，B
2
∈S，存在着A
1
，A
2
∈2
A
，使得B
1
=f (A
1
)，B
2
=f (A
2
)，从而
L∪B{B
1
，B
2
}=B1
∪B
2
=f (A
1
)f (A
2
)
=f (A
1
∪A
2
) （习题三的8的1））
由于A
1∪A
2
⊆A，即A
1
∪A
2
∈2
A
， 因此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< br>2
=f
-1
(B
2
)={x|x∈A∧f (x)∈B
2
}，
则A
1
，A
2
∈2
A
，且显然B
1
=f (A
1
)，B
2
=f (A
2
)，于是
GLB{B
1
，B
2
}=B1
∩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
)
这说明 GLB{B
1
，B
2
}=B
1
∩B
2
=f (A
1
)∩f (A
2
)=f (A
1
∩A
2)于是从A
1
∩A
2
∈2
A
可知f (A
1< br>∩A
2
)∈
S，即下确界GLB{B
1
，B
2
}存在。
因此，〈S，⊆〉是〈2
B
，⊆〉的子格。
3．设〈L，≼〉是格，任取a，b∈L且a≼b。证明〈B，≼〉是格。其中
107

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，故有z
1
=xy为下确界∈L
存 在。我们只需证明z
1
，z
2
∈B即可，证明方法有二，方法一为：
由于
a≼x，所以ax=x，于是
z
1
=xy
=(ax) y （利用ax=x）
=a (xy) （由运算结合律）
因此a≼z
1
；另一方面，由y≼b可知yb=b，由x≼b可知xb=b，于是
z
1
b=(xy) b
=x(yb) （由运算结合律）
=xb （利用yb=b）
=b （利用xb=b）
因此 z
1
≼b，即 a≼z
1
≼b 所以z
1
∈B
由于a≼x及a≼y，所以a*x=a，a*y=a，因而
a*z
2
=a* (x*y)
=(a*x) *y （由*运算结合律）
=a*y （利用a*x=a）
=a （利用a*y=a）
因而a≼z
2
；又由于y≼b，所以y*b=y 于是
z
2
=x*y
=x* (y*b)
=(x*y) *b （利用*运算结合律）
=z
2
*b
从而z
2
≼b，即a≼z
2
≼b 所以z
2
∈B
因此〈B，≼〉是格（是格〈L，≼〉的子格）。
方法二：根据上、下确界性质，由a≼x，a≼y，可得a≼x*y，（见附页数）

4．设〈L，≼，*，〉是格。a，b∈L，证明：（附页）
a≼x≼y，即a≼z
2
，a≼
又由x≼b，y≼b，可得xy≼b， x*y≼y≼b，即z
1
≼b，z
2
≼b
108

所以a≼z
1
≼b，a≼z
2
≼b，故此z
1
， z
2
∈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)
同理可得
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)
109

≼[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
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)
110

根据对偶原理，就还有
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) （交换律）
充分性，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) （交换，分配律）
111

=(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；
故此格为有界格。
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结点后所形成的子 格与分配格〈S
24
，I，GCD，LCM，1，24〉同构，因此若
此格不是分配格 ，则必有子格
112
a
b
c
d
e
f
g
h
i

h * (fg)=h*b=h
(h*f)  (h*g)=ii=I
24
a
1
12
6
3
1

〈S
24
，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）
=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) （吸收律）
b
1

8
b
2
4
2
a
5
b
5

a
2
a
3
a
4
b
3
b
4
113

=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
因此， 对于任何元素a≼L，都有a=0=1（因为0≼a≼1），从而|L|=1，这与已知|L，|≥2
矛 盾。
13．设〈L，≼〉是全序集，|L|≥3。证明：〈L，≼〉是格，但不是有补格。
[证] 由于〈L，≼〉是全序集，那么L中任意两个元素都可比较，于是L中任意两个元素都有上< br>确界和下确界，因此〈L，≼〉是格。
下面我们来证〈L，≼〉不是有补格，用反证法： 否则〈L，≼〉是有补格，则对任何a∈L，都存在着一个元素b∈L，使ab=1及a*b=0。由于〈L，≼〉是全序集，所以任二元素可比较，从而
114

①若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′非空；对于任何a
1
，a
2
∈ L′，我们来证a
1
*a
2
，
a
1
a
2
∈L′
为证a
1
*a
2
∈L′，只需找出a
1< br>*a
2
的补元即可。由于a
1
，a
2
∈L′，故此存 在着b
1
，b
2
∈L，
使a
1
*b
1=0，a
1
b
1
=1以及a
2
*b
2
=0，a
2
b
2
=1，于是构造出a
1
*a
2
补元为b
1
b
2
∈L。这是因为
(a
1
*a
2
) * (b
1
b
2
)=((a
1
*a
2
) * b
1
) ((a
1
*a
2
) * b
2
) （分配律）
=((a
1
*b
1
) *a
2
) (a
1
*(a
2
* b
2
) （交换律）
=(0*a
2
) (a
1
*0)（由 a
1
*b
1
=0，a
2
b
2
=0）
=00 （由0—1律）
=0
(a
1
*a
2
)  (b
1
b
2
)=(a
1
 (b
1
 b
2
)) * (a
2
 (b
1
 b
2
))（分配律）
=((a
1
b
2
) b
2
) * ((a
2
b
2
) b
1
)（交换律，结合律）
=(1b
2
)* (1b
1
)（由a
1
b
1
=1及a
2
b
2
=1）
=1*1（由0—1律）
=1
为证a
1
a
2
∈L′只需找出a
1
a< br>2
的补元即可。由于a
1
，a
2
的补元是b
1
，b
2
，故构造出a
1
a
2
的补元为b
1*b
2
∈L。这是因为
(a
1
a
2
) * (b
1
*b
2
)=(a
1
* (b
1
* b
2
)) (a
2
* (b
1
* b
2
))（分配律）
=((a
1
*b
2
) *b
2
)  ((a
2
*b
2
) *b
1
)（交换律，结合律）
=(0*b
2
)  (0*b1
)（由a
1
*b
1
=0及a
2
*b
2
=0）
=00（由0—1律）
=0
(a
1
a
2
)  (b
1
*b
2
)=((a
1
a
2
) b
1
) * ((a
1
a
2
) b
2
)（分配律）
= ((a
1
b
1
) a
2
) * (a
1
 (a
2
b
2
))（交换律，结合律）
=(1a
2
) * (a
1
1)（由a
1
b
1
=1及a
2
b
2
=1）
=1*1 （由0—1律）
=1
115

15．求〈S
12
，1〉的所有子格，其中，S
12
是12的所有因子的集合1
是S
12上的整除关系。
[解] 一个结点：{1}，{2}，{3}，{4}，{6}，{12}
二个结点：{1，2}，{1，3}，{1，4}，{1，6}，
4
{1，12}
{2，4}，{2，6}，{2，12}
2
{3，6}，{3，12}
{4，12}
{6，12}
三个结点：{1，2，4}，{1，2，6}，{1，2，12}〈S
12
，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}
六个结点：S
12
={1，2，3，4，6，12}
都是〈S
12
，1〉的子格。
16．证明：一个格〈L，≼〉分配格的充分必要条件是
a
，b，c∈L，有
(ab) *c≼a (b*c)
[证] 必要性
对任何a，b，c∈L
(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)（交换律）
116
12
6
3
1

≼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．设〈L
1
，R
1
〉和〈L
2
，R
2
〉是两个格，f：L
1
→
L
2
是从〈L
1
，R
1
〉到〈L
2
，R
2
〉的同态函数。证
明：f的同态象是〈L
2
，R
2
〉的子格。
[证] f的同态象f (L
1
) = {y : y∈L
2
∧(x∈L
1
) (f(x)=y)}
我们来证〈f (L
1
)，R
2
〉是〈L
2
，R
2
〉的子 格：
显然f (L
1
)⊆L
2
；若L
1
非空，则 有a∈L
1
，从而有b=f (a)∈f (L
1
)故f (L
1
)非空。
对于任何b
1
，b
2
∈f (L
1
)，存在着a
1
，a
2
∈L
1
，使b< br>1
=f (a
1
)，b
2
=f (a
2
)，从而
b
1

2
b
2
=f (a
1
) 
2
f (a
2
)
=f (a
1

1
a
2
)（同态公式）
∈f (L1
)（因〈L
1
，R
1
〉是格，故
1
运算封
闭，从而a
1

1
a
2
∈L
1
）
因此〈f（L
1
），R
1
〉是〈L
2
，R
2
〉子格。
18．设B={1，2，5，10，11，22，55，110}。证明：〈B，
GCD，LCM〉是布尔代数。其中，GCD是求最大公约
数，LCM是求最小公倍数，x′= 110x。
[证] 我们已证过〈N，GCD，LCM，〉是分配格，故此
为证〈B ，GCD，LCM〉是分配格，只需证〈B，
GCD，LCM〉是〈N，GCD，LCM，〉的子格即可 。
易于验证，对于任何a，b∈B，恒有GCD{a，b}，LCM{a，b}∈B故此两个运算GC D，
LCM关于B封闭。因而〈B，GCD，LCM〉是分配格。
又由于1和110互为补元 ；2和55互为补元；5和22互为补元；10和11互为补元，所
以〈B，GCD，LCM，′〉是有 补的分配格，故此〈B，GCD，LCM，′〉是布尔代数。
19．设L
1
={1， 2，3，4，6，12}，L
2
={1，2，3，4，6，8，16，24}。
a) 〈L
1
，GCD，LCM，′〉是布尔代数吗？为什么？
b) 〈L
2
，GCD，LCM，′〉是布尔代数吗？为什么？
110
10
55
2
5
1
22
24
8
4
2
12
6
3
1
117

[解] a) 〈L
1
，GCD，LCM，′〉不是布尔代数。 因为〈L
1
，GCD，LCM，′〉虽是分配格（〈N，1，GCD，LCM，〉的子格） 但不是有补格，
元素2，6没有补元。所以不是布尔代数。
b) 〈L
2
，GCD，LCM，′〉也不是布尔代数。
因为虽然〈L
2
，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，从而由保序性，得到
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
118

从而由消去律，有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
只需证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））
119

=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，*，，，′〉是布尔代数。在B上定义二元运算○
*
b=(a*b′)(a′*b) a，b∈B，a○
证明：〈B，〉是交换群
[证] ①封闭性
*
b=(a*b)(a*)∈B，因此○
*
运对于任何a，b∈ B，由于*，，′运算的封闭性，可知a○
算具有封闭性。
②结合律
对于任何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律）
120

=(a*b′*c′)(a′*b*c′)(a*b*c)  (a′*b′*c)
=(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，○
*
，′〉是一个交换群。 22．设〈B，*，○
如下
121

a，b∈B，a+b=(a*b′)(a′b)
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)
122

（分配律，结合律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) 的证明，分配律已成立。
23．设〈A，∧，∨∩∪－〉和〈B，∩，∪，－〉是两个布尔代数，f是 从〈A，∧，∨∩∪－〉
到〈B，∩，∪，－〉的满同态函数。证明：
f(O
A
)=O
B
f(1
A
)=1
B
其中，O
A
和O
B
分 别是A，B中的最小元，1
A
和1
B
分别是A，B中的最大元。
[证] 对于任何a∈A，由于A是布尔代数，所以存在着补元
a
∈A使得
O
A
=a∧
a
及1
A
=a∨
a
（互补律）
又由于B是布尔代数，f是从A到B的同态函数，从而有
f(
a
)=(f(a))′ （同态公式）
于是
f(O
A
)=f(a∧
a
)
=f(a)∩f(
a
) （同态公式）
=f(a)∩(f(a))′
=O
B
（互补律）
f(1
A
)=f(a∨
a
)
=f(a)∪f(
a
) （同态公式）
=f(a)∪(f(a))′
=1
B

24．设a，b，b
2
，…b
r
是布尔代数〈B，≼，*，，′〉的原子。证明：ab
1
b
1
…b< br>r
的充分必要
条件是存在i（1≤i≤r），使a=b
i
。
[证] 必要性
用反证法。假设对每个i，1≤i≤r，都有a≠b
i，那么由a，b
i
（1≤i≤r）都是原子，因此
a*b
i
=0 （否则有a=a*b
i
=bi，与假设a≠bi矛盾）。从而
a* (b
1
b
2
…b
r
)
123

=(a*b
1
)(a*b
2
)…(a*b
r
) （分配律）
=00…0
=0 (0-1律)
但是由已知a≼b
1
b
2
 … b
r
，从下确界的性质可知
a* (b
1
b
2
…b
r
)=a
从而得到a=0，这与已知a是原子，a≠0矛盾，
充分性
若对某个i。1≤i
0
≤r，使a=b
i0
。则由上确界的性质可知
a≼b
1
b
2
…
b
i
0
-1
a
b
i
0
+1
…b
r

0
=b
1
b
2
…
b
i
-1

b
i
0
+1
…b
r
（因为a=
b
i
0
）
25．设b
1
，b
2
…，b
r
是 有限布尔代数〈B，*，，′〉的所有原子。
证明：
y=0的充分必要条件i（1≤i≤r），都有y*b
i
=0
[证] 必要性
对于任何b
i
（1≤i≤r） y*b
i
=0*b
i
=0总是成立，因为y=0
充分性
根据布尔代数的元素的原子表示定理，可知
y=
i
b
i
S(y)
b
这里S(y)={b
i
:1≤i≤r∧b
i
≼y}
因此，y=y*y （幂等律）
=y
b
i

b
i
S(y)
=
(yb
i
)
（分配律）
b
i
S(y)
=
b
i
S(y)

0 （因为对任何i，1≤i≤r，都有y*b
i
=0）
=0 （0-1律）
26．设〈2
X
，∩，∪，′〉到〈B，∧，∨，—〉的满同态函数。
[证]（1）后者唯一
用反证法。对于任何x2
X
，若有y
1
，y
2
∈B，且y
1
y
2
使得g(x)=y< br>1
，且g(x)=y
2
，则由于
(x，y
1
)∈g∧(x，y
2
)∈g
(x，0)∈g(x，1)∈g （由于y
1
≠y
2
，且y1
，y
2
，且y
1
，y
2
∈B={0，1}）
b∈x∧b∉x
124

矛盾，故引假设y
1
≠y
2
错误，从而y
1
=y
2
，g是后者唯一的。
（2）Ɗ(g)=2
X

（3）g是满射数，ℛ(g)=B
由于B ={0，1}，并且存在着x
1
={a，c}，和x
2
={a，b}使g(x
1
)=0，g(x
2
)=1，故ℛ(g)=B。
（4）g满足同态公式，即g保持运算。
对于任何x∈2
X
，由于
g(x′)=1
b∈x′
b∉x
g(x)=0
g(x)
=1
所以g(x′)=
g(x)

对于任何x
1
，x∈
2
X
，由于
g(x
1
∩x
2
)=1
b∈x
1
∩x
2

b∈x
1
∧b∈x
2

g(x
1
)=1∧g(x
2
)=1
g(x
1
)∧g(x
2
)=1
所以 g(x1
∩x
2
)=g(x
1
)∧g(x
2
)
由于 g(x
1
∪x
2
)=1
b∈x
1
∪x
2

b∈x
1
∨b∈x
2

g(x
1
)=1∨g(x
2
)=1
g(x
1
)∨g(x
2
)=1
所以 g(x
1
∪x
2
)= g(x
1
)∨g(x
2
)
综合以上四条，可知g是从〈2
X
，∩，∪，′〉到〈B，∧，∨，—〉到的满同态函数。

125