1 离散数学习题解答 习题五(第五章 格与布尔代数) 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 中任两个元素都有上、下确界。 b) 〈L,≼ 〉不是格。因为L 中存在着两个元素没有上确界。 例如:812=LUB{8,12}不存在。 12 6 3 1 2 4 8 6 3 1 2 4 12 10 2 c) 〈L,≼ 〉不是格。因为L 中存在着两个元素没有上确界。 倒例如:46=LUB{4,6} 不存在。 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),所以 8 4 2 6 97 3 1 5 10 3 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...