离散数学习题解答(第五章)格与布尔代数

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 中存在着两个元素没有上确界。 例如：812=LUB{8，12}不存在。 12 6 3 1 2 4 8 6 3 1 2 4 12 10 2 c) 〈L，≼ 〉不是格。因为L 中存在着两个元素没有上确界。 倒例如：46=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...