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

《离散数学习题解答(第五章)格与布尔代数.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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}1263124[解]a)〈L，≼〉是格，因为L中任两个元素都有上、下确界。b)〈L，≼〉不是格。因为L中存在着两个元素没有上确界。例如：8Å12=LUB{8，12}不存在。8631241210c)〈L，≼〉不是格。因为L中存在着两个元素没有上确界

2、。842698731510倒例如：4Å6=LUB{4，6}不存在。2．设A，B是两个集合，f是从A到B的映射。证明：〈S，⊆〉是〈2B，⊆〉的子格。其中S={y

3、y=f(x)，x∈2A}[证]对于任何B1∈S，存在着A1∈2A，使B1=f（A1），由于f(A1)={y

4、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{B

5、1，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

6、x∈A∧f(x)∈B1}，A2=f-1(B2)={x

7、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，则

8、y∈B，且y∈B2。由于y∈B1=f(A1)={y

9、y∈B∧($x)(x∈A1∧f(x)=y)}，于是存在着x∈A1，使f(x)=y，但是f(x)=y∈B2。故此x∈A2=f-1(B2)={x

10、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{B

11、1，B2}存在。因此，〈S，⊆〉是〈2B，⊆〉的子格。3．设〈L，≼〉是格，任取a，b∈L且a≼b。证明〈B，≼〉是格。其中B={x

12、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

13、；另一方面，由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

14、，即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∈Ba*b≺a且a*b≺bÛa与b是不可比较的。[证]先证Þ用反证法，假设a与b是可比较的，于是有a≼b或者b≼a。当a≼b时，a*b=a与a*b≺

15、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)[证]