第七章-格与布尔代数--习题课

第七章习题课P242(1).(a)不是格因为d和e没有下确界,也没有上确界.(d)不是格5和6没有下确界,7和8既没下确界,也没上确界.进一步问,如果是格,哪些是分配格?哪些是有补格?(b)不是分配格,因去掉结点j后的子格如图所示但它是有补格.(c)不是分配格(去m,p),不是有补格.1dabcefghijk5246lmnoqrp387(a)(b)(c)(d)jkfgh(2).设≤是L上的整除关系,下面偏序集中,哪些是格?a)L={1,2,3,4,6,12},b).L={1,2,3,4,6,8,12,14}c)L={1,2,3,4,5,6,7,8,9,10,11,12}可见只有(a)是格.12462318412531678142111092124613(a)(b)(c)(4).设A,≤是一个格,任取a,b∈A,ab(即a≤b∧a≠b),构造集合:B={x|x∈A且a≤x≤b},则B,≤也是格.证明:显然B是A的非空子集(因为a≤a≤b,a≤b≤b,所以a,b∈B),只要证明∧和∨在B上封闭即可.任取x,y∈B,由B的构成得a≤x≤b,a≤y≤b,于是由格的性质得,a≤x∨y≤ba≤x∧y≤b,于是有x∨y∈Bx∧y∈B,说明∨和∧在B上封闭,所以B,≤也是格.(7).设a,b是格A,≤中的两个元素,证明:a).a∧b=b当且仅当a∨b=a.b).a∧bb和a∧ba,当且仅当a与b是不可比较的.证明:a)充分性:已知a∨b=ab=b∧(b∨a)=b∧(a∨b)=b∧a=a∧b必要性:已知a∧b=b,a=a∨(a∧b)=a∨bb)充分性:已知a与b是不可比较的.因a∧b≤b,a∧b≤a,如果a∧b=b,则有b≤a,如果a∧b=a,则有a≤b,都与a与b是不可比较的矛盾.所以有:a∧b≤b∧a∧b≠b,于是有a∧bba∧b≤a∧a∧b≠a,于是有a∧ba必要性:已知a∧bb和a∧ba,假设a与b是可比较的.则要么a≤b,要么b≤a.于是要么a∧b=a要么a∧b=b.这与a∧bb和a∧ba矛盾.所以a与b是不可比较的.(9).证明格中成立:a)(a∧b)∨(c∧d)≤(a∨c)∧(b∨d)b)(a∧b)∨(b∧c)∨(c∧a)≤(a∨b)∧(b∨c)∧(c∨a)证明:a)∵(a∧b)≤a≤(a∨c)∴(a∧b)≤(a∨c)∵(c∧d)≤c≤(a∨c)∴(c∧d)≤(a∨c)∴(a∧b)∨(c∧d)≤(a∨c)同理(a∧b)≤(b∨d)(c∧d)≤(b∨d)∴(a∧b)∨(c∧d)≤(b∨d)∴(a∧b)∨(c∧d)≤(a∨c)∧(b∨d)b)∵(a∧b)≤(a∨b),(a∧b)≤(b∨c),(a∧b)≤(c∨a)∴(a∧b)≤(a∨b)∧(b∨c)∧(c∨a)同理有(b∧c)≤(a∨b)∧(b∨c)∧(c∨a)(c∧a)≤(a∨b)∧(b∨c)∧(c∨a)最后得(a∧b)∨(b∧c)∨(c∧a)≤(a∨b)∧(b∨c)∧(c∨a).P248(2).下面哪个是分配格?解:判定一个格是否分配格,看它是否含有五元素的非分配格形式的子格.(a)图好像可以去掉b或c后得到如下图:但它们不是(a)的子格.因d∨e=bb∧c=eb,e不在子集里.∴(a)是分配格.(b)也是分配格.(c)不是分配格.(a)dcabfefgadceb12345(b)fgadceb(c)31245dcafebdcaf(c)*(5).设A,≤是分配格,a,b∈A,且ab,证明f(x)=(x∨a)∧b是一个从A到B的同态映射.其中B={x|x∈A且a≤x≤b}证明:先证f是从A到B的映射:任取x∈A,由f的定义得f(x)=(x∨a)∧b)显然(x∨a)∧b≤b而(x∨a)∧b=(x∧b)∨(a∧b)=(x∧b)∨a(因aba∧b=a)∴a≤(x∨a)∧b≤b即a≤f(x)≤b∴f(x)∈B∴domf=A.又由于∨和∧的定义知(x∧b)∨a是唯一的.即f(x)是唯一的.所以f是从A到B的映射.再证f满足同态等式:任取x1,x2∈A,f(x1∧x2)=((x1∧x2)∨a)∧b=((x1∨a)∧(x2∨a))∧b=((x1∨a)∧b)∧((x2∨a)∧b)=f(x1)∧f(x2)f(x1∨x2)=((x1∨x2)∨a)∧b=((x1∨a)∨(x2∨a))∧b=((x1∨a)∧b)∨((x2∨a)∧b)=f(x1)∨f(x2)∴f是同态映射.P252(1).给出有界格如图a)哪些元素有补元?b)该格是分配格吗?c)该格是有补格吗?解:a)a、c、d、f、g无补元;b和e互为补元;0和1互为补元.b)不是分配格,因为它含有子格如下图.c)它不是有补格,因为很多元素无补元.(3).证明具有两个或更多个元素的格中不存在以自身为补元的元素.证明:设A,≤是格,且|A|≥2,假设有a∈A,使得=a∴a≠0,a≠1,但是有1=a∨=a∨a=a0=a∧=a∧a=a产生矛盾.所以不存在以自身为补元的元素.a¯1cabdfge0eda0fa¯a¯(4).在有界分配格中,证明具有补元的那些元素组成一个子格.证明:设A,≤是有界分配格,令B={x|∈A}任取a,b∈B,,∈B,∨∈A,∧∈A下面证明∨和∧在B上封闭,即a∨b和a∧b都有补元:所以B,≤是A,≤的子格.x¯b¯a¯a¯a¯b¯b¯BbabababbaabababababbaababaBbababababbaabababbaabababa所以有补元所以所以有补元所以000)()()()(111)()()()(000)()()()(111)()()()((6).设A,≤是有界格,对于任何x,y∈A,证明a).x∨y=0,则x=y=0b).x∧y=1,则x=y=1证明:a)x=x∧(x∨y)=x∧0=0y=y∧(y∨x)=y∧0=0b)x=x∨(x∧y)=x∨1=1y=y∨(y∧x)=y∨1=1P260(2).设S,∨,∧,¯是布尔代数，x,y∈S,证明:x≤y当且仅当证明:充分性已知必要性:已知x≤yxyxyyxyxyyyxyyxy所以即xyxyxxyxxyx所以即P260(2)设B,∨,∧,¯是个布尔代数,x,y∈B,证明:x≤y当且仅当.解.必要性.已知x≤y,充分性:已知xyxyxyxxyxxyx,xyyxyyxyyxyyx即P269(1).设是{0,1},∨,∧,¯上的一个布尔表达式.分别写出它的析取范式与合取范式.方法1.用真值表)()()(),,(323221321xxxxxxxxxEx1x2x3E(x1,x2,x3)00110100011110001011110100001111)()()(),,(321321321321xxxxxxxxxxxxE)()()()()(),,(321321321321321321xxxxxxxxxxxxxxxxxxE方法2.用等价变换的方法.这是析取范式.求它的合取范式可能要麻烦一些.下面求合取范式:)()()()()()()()()()()())(())(())(()()()(),,(321321321321321321321321321321321321132113321323221321xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxE可见与用真值表求的结果相同.)()()()()()()())(())(()()()())(()()()()(),,(32132132132132132132132113221323132132221323221321xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxE