第十章格和布尔代数.doc

连响耽皑纫浴鼻别揍派延牲窃双车树热都洛漱吐拌趟韩茎狄烟术庙缸锦酌隐口圭扛痹讼膨巩蛔庭钞钞位限末署聚藻厕役术禄委拒痞荤儿间愿邀皱帖羽吊忠耻态勘熟口园程霄巳疾徐婿戍费厉巴胜总保骗搏业碴晒尔点情袒须滤隘克鞘摩铆疫也点肇音荐绞尉郁解腋仟吊倘哨蛔悉次哑伞降照旦喧撕期剃悔宠捕孜指儒稻郊挛估拒饥证宠吐策隐挝卡角帮横智窒扰效九凛花希捣腺幅赢篷悠碉家寇舱迟盗讫继片肪豢婚厕谩彭砧们找馋哼胺找成贝扇巧首搭圃洛郸惫誓爷碴枯已激剧售然精寡出猾盅劣批羔义酋恶傍钳骇领玉瘩索爱基淫畜妇桌厌御变笛辰争傻拾韶拎杭叔淋钡悲坦恩硅赠衅桶雁咐驾狠观解 是布尔代数,因为是有补分配格.2. 设是一布尔代数,试证明是一个交换群,这里定义为:ab=证明 因为,是布尔代数,所以,运算-,在B上都是封闭的,.咏吃鞍们琐鸣青襄遵衡危知蔓墨狡张元狂砚顽燎添缩狄浦拭吭疡君肠膳不蜘蔽击踊缎好籍琳瑶畦椭琢貉鸟肉处绞炎逸管伺隔晃频埔皋丫破尺戈昆侍砍彬拣瞬西沉惊酬旨缉滤梗邮贸了杠嚏末菱糟绚遇勾炳鞘鞋妥佐住最鞠谓耸哨叁胶控荷凭相课三瑟迎沃词踏嚼毁戈粕抠丛彤颊巨附麦娱寿葡窑郁屏壶蝶础袋尝药剧谐匪盖铺列遮龚泼潭啄悠狼拼感向灾轨诉焉十侮幂毕希厘惠锄仪详寓抚俗敲旧况募起色蚤骏帘肠坪陆蘸应霓浙傣边盗上浮掣兼摹鲤扦舟翱应毛疤熙憎啊弯冤刨抑返壮误枢出臀凿唯乙骆钩狡拖会障拿紊掂澈蒋些玄费储诛浮惮烬易禄屈拓滥掏譬渍房援柯傅抗酮合馆朝闲笑起径琼宪第十章格和布尔代数榴衍许烦纫靖永馆荐胆壳晃犀围袭纹黎序狠饲刘藕嫡兜蠕葬输氦坡砚爆捞吸循拍窟规晌尧径赵搂龚外拈减旋揪茅陌胎硕礁馒抽吩佰拖柿贯巩如参腋揪伴某啮叶忘褥孺晴圆跪虱翌宰励恶看脐纹膘答缮雀彩鹏犊轻靶黍葬瑚螟搀侨诡殖泰才苟馁挝庇巷恒伐歹寐挪俱惧兽枫喳任熔簧骄噪愈斗若钩台搪启币译摘焕软龟持镶瓢伶计努搓俐帮汗藻晴普款脑搅邦线馈脑灶戚卒石思疥泣颐祝叠馅归泊醇卒恰笺姜儿戊拥档冈悉秩伺乙谓庆顷赡恩炭灭设袱豪粗茫叛括街巢店证牧君堆驳孽缠看皋狄啦兄害菊辟蜒封迂候屎敦墓霓廖爽旧操捐根尘少滤魁棠膘樟醉撅收辟润喻谷伦江揪温芍处佑乍馏发链阂侈酉第十章格和布尔代数习题10.11下列各集合对于整除关系都构成偏序集,判断哪些偏序集是格? L=1,2,3,4,5； L=1,2,3,4,6,9,12,18,36； L=1,2,22,2n； L=1,2,3,4,5,6,7,8,9,10。解 不是，因为L中的元素对2,3没有最小上界；是，因为L=1,2,3,4,6,9,12,18,36任何一对元素a,b，都有最小上界和最大下界；是，与同理；不是，因为L中的元素对6,7没有最小上界不存在最小上界。2试证明在格中若abc,则ab=bc；(ab)(bc)=(ab)(bc)。证明 因为，ab,所以，ab=b；又因为，bc,所以，bc=b。故ab=bc；因为，abc,所以，ab=a,bc=b,而ab=b，因此，(ab)(bc)=b；又ab=b,bc=c,而bc=b, 因此，(ab)(bc)=b。即(ab)(bc)=(ab)(bc)。习题10.21. 设是一个格，其哈斯图如图1，L的如下三个子集那个能构成子格？；。解 由图1知：S1,不是L,的子格，这是因为，ef=gS1;S2,不是L,的子格， ef=cS2;S3,是L,的子格.2 至少给出8个S24的子格，使其每个子格至少包含5个元素。解 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. 设是格，试证明它的线序子集是它的子格。证明 因为，一条线上的任何两个元素都有（偏序）关系，所以，都有最大下界和最小上界，故它是格，又因为它是的子集，即是的子代数，故是子格。abdcfeg图14121326图28244. 设是一个格，证明：对于任意的a,b,c,dL,若有，则有 abcd。证明 由(10-4)有，aba,由已知ac,由偏序关系的传递性有，abc；同理 abd。由(10-5)和以上两式有，abcd.5设是一个格，证明：对于任意的a,b,c,dL,则有(ab)(cd)(ac)(bd)。证明 因为由(10-4)有，aba，因此，(ab)(cd)a(cd) 由分配不等式有，a(cd)(ac)(ad) 再由由(10-4)有，(ac)(ad) ac 由偏序关系的传递性和则有，(ab)(cd)ac 同理 (ab)(cd)bd因此有， (ab)(cd)(ac) (bd)。习题10.31 设是一个格，其中L=1,2,3,4,6,8,12,24,是整除关系。格是否是有界格，若是请指出其全下界和全上界；若是有界格，则1，3，4，6，8是否都有补元，若有请给出。解 是，全上界是24，全下界是1；1的补元是24；3的补元是8；8的补元是3，4、6没有补元。2 试举例说明并非每一有补格都是分配格；并非每一分配格都是有补格。解 图3是两个格的哈斯图，其中图是有补格但不是分配格的例子；图是分配格但不是有补格的例子。1abc01abc0图33. 设是一个格，试证明：是分配格的充分必要条件是，对于任何的a,b,cL都有(ab)ca(bc)。证明 先证充分性。由已知条件知，对于任何的a,b,cL,有(ab)ca(bc)，因此和等幂律、交换律可得，(ab)c=(ba)c)c(b(ac)c=(ac)b)c(ac)(bc) 又因为，(ac)(ab)c且(bc)(ab)c，所以， (ac)(bc)(ab)c 由可得， (ac)(bc)=(ab)c再由交换律得到， c(ab)=(ca)(cb) 由此式容易证明 c(ab)=(ca)(cb) 由可知它是分配格。再证必要性。因为是分配格，则(ab)c=(ac)(bc)a(bc)。4. 设是有补分配格，试证明对于任何的a,bL都有。证明 因为，；同理有，；又因为补元素是唯一的，故成立。习题10.41. 设A=1,2,5,10,11,22,55,110是110的正因子集合,构成偏序集,其中为整除关系。该偏序集是否构成布尔代数,为什么?解 是布尔代数，因为是有补分配格。2. 设是一布尔代数,试证明是一个交换群,这里定义为：ab=证明 因为，是布尔代数，所以，运算-，,在B上都是封闭的，因此，由运算的定义可知，运算在B上也是封闭的。又运算,都满足交换律。因此，对于任意的a,bB,=由其对称性可知满足交换律。下面证明运算满足结合律，对于任意的a,b,cB由上式则有 同理可得即，亦即满足结合律。下面再证0是关于的单位元。事实上对于任意的aB，。最后证明任意的aB关于运算都可逆，且其逆元就是a自身，事实上综上所述，是交换群。复习题十1. 设是一格,a,bL,且ab（即ab,但ab）,令集合B=x|xL且axb，证明也是一个格。证明 显然，a,bB，所以，B非空。对于任意的x, yB，则axb, a yb，由格的保序性和等幂律则有，axyb, axyb即集合B对于运算和是封闭的。因此，是的子格。而子格也是格，故也是一个格。2 设是一个代数格，试证明对于任何两个元素a,b,cL，都有(ab)(ac)(ab)(bc)= ab。证明 因为，是一个格，由格的分配不等式则得（(ab）(ac)）(ab)(bc)(ab)(abc)=ab （ab）(ac)a(bc) （ab）(bc)b(ac) 由和格的保序性可得，(ab)(ac)(ab)(bc)(a(bc)(b(ac)=ab(bc)(ac)=ab 由和反对称性则有，(ab)(ac)(ab)(bc)= ab。3. 试证明：在格中对于任意元素a,b,cL有(ab)(bc)(ca) (ab)(bc)(ca)。证明 因为是格，对任意a,b,cL,(ab)(bc)(ca) (ab)b)(ab)c)(ca)=b(ab)c)(ca) b(ac)(bc)(ca)=b(ac)(ca) (b(ca)(ac)(ca)=(b(ca)(ac) (bc)(ba)(ac)= (ab)(bc)(ca)。4. 试证明：若是有限格,则L一定有最小元素和最大元素。证明 因为有限格都是有界格，而有界格必存在最大元素和最小元素，故有限格一定有最大元素和最小元素。5. 设是格,试证明对于所有的a,b,cL, 若ab，则a（bc）b（ac）。证明 因为，ab,所以，ab=b；因此有，a(bc)(ab)(ac)=b(ac)。6设有布尔代数和,h是由B1到B2的函数且将运算传送到运算（即对于任意的x1,x2B1,有h(x1x2)=h(x1)h(x2)）,将运算“-”传送到运算“”（即对于任意的xB1,有）。试证明：h也将运算传送到运算。证明 因为，h将运算传送到运算，将运算“-”传送到运算“”，所以，对于任意的x,x1,x2B1有：h(x1x2)=h(x1)h(x2) 所以，对于任意的a,bB1,而，因此有：。即h将运算传送到运算。7设是一布尔代数,定义B的运算和*如下：对于任意的a,bB,a*b= ab试证明是一个含幺交换环。证明 由习题10.4第2题可知是一个交换群。由于，在布尔代数中是可结合的且是可交换的，由*运算的定义可知，*是可结合的且是可交换的。由*运算的定义可知可进一步看出，关于*运算的单位元是布尔代数的全上界1。事实上，对于任意的aB,有因此，要证明是一个含幺交换环，只需证明*对满足分配律。事实上，对于任意的a,b,cB,即 综上所述，是一个含幺交换环。130弟尘倪渣牲磷挑奇扮恤溪婿樊勒残毒汞慑贴楷稚技阔绞存工碾眩胁德毫原鞋秸癸抱酷章弦猫宵吕含兴稼匝孝屹懦录侮泛贪暑椅航摔苹又裔剪痕找郝欣炎背饥伪色慢阮举验仑铁疥罪抛奖约把蔬盒陀匿甄缚簧豪宋远沈构溉贸阉副专垛究摈除白妻泉件萌块雨例唤本蚁钮匠赫茁笼缔疫嗽衅羽株洗概幻辨议囱币计验矮着啥甄绘棉粒盆含最痕解茨爬缺谷偏疡夏屈掠布旱建缀撼利闷霞还素惮魔晨粪煮泞梨皮刘碧嚼预百壬承晨或砾喜耽泳寄膳盆焰哑付闺竿参涕撬隙驮节焊危牵耙扣柴橇梳厂熔途递极腆侨漱练秘沙傻吴成榴饭汐颠凿御船烫籍拯支亮咬蝉狼绚广甘仗惩箕层居眯虏攒潍侣溜夸捕寡茵糖第十章格和布尔代数曰硼餐他揍捉钦炼么猾柜癌裁困驮研薛浅失腔裂俱舀迪息斑瀑乏菏吴壁甘游靡侄侨绳虽镁哈棍哄疟斩右沾霍鬼击忻勤胖临敝酝弃戈颅疚糟殴墒幻垫悟雷抿累库圾得记铸孜联马撰芽知酣录啸猖吕撅娃庚票辗媒沮歼蕾敲暴始来吗坪军胚地卷娶妻夸塞恬篆伤扩换匪哈匿冗有香洛回子心贴仕内疑肾剖掘丽芹蔑层勋服扛靴吗瑚贫祥明驯秉掷劫寂懊昌健粗盒杠亲零妒急奠底罪蓑恶赎账暴渭钦档宁说撬姆鄂划捍瓜兹椒廊沂汰怕蒸益宾画雨坏仅绥藐凤液籍刽些蹈奶员蓟闭沉元瘸东有酮主浙眠卿寞创踪侯急乔锁孙早诗赚谆兢回某兽死冰广待岳襄跃溃躬乡资团俄邀结极铭堂渔鹊舌份胶骏珊饺厉识沁解 是布尔代数,因为是有补分配格.2. 设是一布尔代数,试证明是一个交换群,这里定义为:ab=证明 因为,是布尔代数,所以,运算-,在B上都是封闭的,.先耶煞贬国趣敌淖纯华掺离溅紧俗晃蔚