离散数学答案第十章格和布尔代数

第十章格和布尔代数习题10.11．解⑴不是，因为L中的元素对{2,3}没有最小上界；⑵是，因为L=｛1,2,3,4,6,9,12,18,36｝任何一对元素a,b，都有最小上界和最大下界；⑶是，与⑵同理；⑷不是，因为L中的元素对{6,7}没有最小上界不存在最小上界。2．证明⑴因为，a≤b,所以，a∨b=b；又因为，b≤c,所以，b∧c=b。故a∨b=b∧c；⑵因为，a≤b≤c,所以，a∧b=a,b∧c=b,而a∨b=b，因此，(a∧b)∨(b∧c)=b；又a∨b=b,b∨c=c,而b∧c=b,因此，(a∨b)∧(b∨c)=b。即(a∧b)∨(b∧c)=(a∨b)∧(b∨c)。习题10.21．解由图1知：＜S1,≤＞不是＜L,≤＞的子格，这是因为，e∨f=gS1;＜S2,≤＞不是＜L,≤＞的子格，∵e∧f=cS2;＜S3,≤＞是＜L,≤＞的子格.2．解S24的包含5个元素的子格有如下的8个：S1={1,3,6,12,24},S2={1,2,6,12,24},S3={1,2,4,12,24},S4={1,2,4,8,24},S5={1,2,3,6,12},S6={1,2,4,6,12},S7={2,4,6,12,24},S7={2,4,8,12,24}.3．证明因为，一条线上的任何两个元素都有（偏序）关系，所以，都有最大下界和最小上界，故它是格，又因为它是L，∨,∧的子集，即是L，∨,∧的子代数，故是子格。4．证明由(10-4)有，a∧b≤a,由已知a≤c,由偏序关系的传递性有，a∧b≤c；同理a∧b≤d。由(10-5)和以上两式有，a∧b≤c∧d.5．证明因为由(10-4)有，a∧b≤a，因此，(a∧b)∨(c∧d)≤a∨(c∧d)①由分配不等式有，a∨(c∧d)≤(a∨c)∧(a∨d)②再由由(10-4)有，(a∨c)∧(a∨d)≤a∨c③由偏序关系的传递性和①②③则有，(a∧b)∨(c∧d)≤a∨c同理(a∧b)∨(c∧d)≤b∨d因此有，(a∧b)∨(c∧d)≤(a∨c)∧(b∨d)。习题10.31．解⑴是，全上界是24，全下界是1；⑵1的补元是24；3的补元是8；8的补元是3，4、6没有补元。abdcfeg图14121326图28242．解图3是两个格的哈斯图，其中图⑴是有补格但不是分配格的例子；图⑵是分配格但不是有补格的例子。3．证明先证充分性。由已知条件知，对于任何的a,b,c∈L,有(a∨b)∧c≤a∨(b∧c)，因此和等幂律、交换律可得，(a∨b)∧c=((b∨a)∧c)∧c≤(b∨(a∧c))∧c=((a∧c)∨b)∧c≤(a∧c)∨(b∧c)①又因为，(a∧c)≤(a∨b)∧c且(b∧c)≤(a∨b)∧c，所以，(a∧c)∨(b∧c)≤(a∨b)∧c②由①②可得，(a∧c)∨(b∧c)=(a∨b)∧c再由交换律得到，c∧(a∨b)=(c∧a)∨(c∧b)③由此式容易证明c∨(a∧b)=(c∨a)∧(c∨b)④由③④可知它是分配格。再证必要性。因为L,≤是分配格，则(a∨b)∧c=(a∧c)∨(b∧c)≤a∨(b∧c)。4．证明因为，bababa()()(000)()bbaa；同理有，)()()(baababa111)(bab；又因为补元素是唯一的，故baba)(成立。习题10.41．解是布尔代数，因为A，≤是有补分配格。2．证明因为，B，-,∨,∧是布尔代数，所以，运算-，∨,∧在B上都是封闭的，因此，由运算的定义可知，运算在B上也是封闭的。又运算∨,∧都满足交换律。因此，对于任意的a,bB,)()(bababa=))(())((bbaaba=)()()()(bababaab由其对称性可知满足交换律。下面证明运算满足结合律，对于任意的a,b,cB由上式则有cbabacba)]()[()(1abc⑴0⑵1abc0图3))()(())]()([(cbabacbaba])()[()()(cbabacbacba)()()()(cbacbacbacba同理可得)(cba)()()()(cbacbacbacba即，cba)()(cba，亦即满足结合律。下面再证0是关于的单位元。事实上对于任意的aB，aaaaa0)1()0()0(0。最后证明任意的aB关于运算都可逆，且其逆元就是a自身，事实上000)()(aaaaaa综上所述，,B是交换群。复习题十1．证明显然，a,b∈B，所以，B非空。对于任意的x,y∈B，则a≤x≤b,a≤y≤b，由格的保序性和等幂律则有，a≤xy≤b,a≤xy≤b即集合B对于运算和是封闭的。因此，B，≤是L,≤的子格。而子格也是格，故B，≤也是一个格。2．证明因为，L,∨,∧是一个格，由格的分配不等式则得（(a∧b）∨(a∧c)）∧((a∧b)∨(b∧c))≥(a∧b)∨(a∧b∧c)=a∧b①（a∧b）∨(a∧c)≤a∧(b∨c)②（a∧b）∨(b∧c)≤b∧(a∨c)③由②③和格的保序性可得，((a∧b)∨(a∧c))∧((a∧b)∨(b∧c))≤(a∧(b∨c))∧(b∧(a∨c)=a∧b∧(b∨c)∧(a∨c)=a∧b④由①④和反对称性则有，((a∧b)∨(a∧c))∧((a∧b)∨(b∧c))=a∧b。3．证明因为L,≤是格，对任意a,b,c∈L,(a∧b)∨(b∧c)∨(c∧a)≤[((a∧b)∨b)∧((a∧b)∨c)]∨(c∧a)=[b∧((a∧b)∨c)]∨(c∧a)≤[b∧(a∨c)∧(b∨c)]∨(c∧a)=[b∧(a∨c)]∨(c∧a)≤(b∨(c∧a))∧((a∨c)∨(c∧a))=(b∨(c∧a))∧(a∨c)≤(b∨c)∧(b∨a)∧(a∨c)=(a∨b)∧(b∨c)∧(c∨a)。4．证明因为有限格都是有界格，而有界格必存在最大元素和最小元素，故有限格一定有最大元素和最小元素。5．证明因为，a≤b,所以，a∨b=b；因此有，a∨(b∧c)≤(a∨b)∧(a∨c)=b∧(a∨c)。6．证明因为，h将运算∨传送到运算∪，将运算“-”传送到运算“＇”，所以，对于任意的x,x1,x2∈B1有：h(x1∨x2)=h(x1)∪h(x2)①))(()(xhxh②所以，对于任意的a,b∈B1,而)(baba，因此有：))()(())(())(()(bhahbahbahbah)()()))(())(((bhahbhah。即h将运算∧传送到运算∩。7．证明由习题10.4第2题可知B,⊕是一个交换群。由于，在布尔代数B，-,∨,∧中∧是可结合的且是可交换的，由运算的定义可知，是可结合的且是可交换的。由运算的定义可知可进一步看出，关于运算的单位元是布尔代数B，-,∨,∧的全上界1。事实上，对于任意的aB,有aaa11因此，要证明B,⊕,是一个含幺交换环，只需证明对⊕满足分配律。事实上，对于任意的a,b,cB,)()()]()[()(cbacbacbcbacba)()()()(cabacaba))()(())()((cabacaba))()(())()((cabacaba)()()()(cbacaacbaaba)()(cbacba即)(cba)()(caba综上所述，B,⊕,是一个含幺交换环。