离散数学第五章答案
【篇一：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中任两个元素都有上、下确界。
6
3
1
b) 〈l，?〉不是格。因为l中存在着两个元素没有上确界。
例如：8?12=lub{8，12}不存在。
12 6
3 1
c) 〈l，?〉不是格。因为l中存在着两个元素没有上确界。
倒例如：4?6=lub{4，6}不存在。
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，?〉是格。其中
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
所以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) 方法一，根据上、下确界的性质
