发布时间 : 星期日 文章3~离散数学习题解答（第五章）格与布尔代数5更新完毕开始阅读
离散数学习题解答
习题五（第五章 格与布尔代数）
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 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)，所以
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，?〉是格。其中
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，故有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，?〉的子格）。
方法二：根据上、下确界性质，由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
108
所以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) 同理可得
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