第七章格与布尔代数

第七章格与布尔代数1.说明什么叫格？2.给定偏序集A,≤、B,≤、C,≤如下图所示，其中哪些不是格？为什么？3下面图哪些是格？对于不是格的，要说明原因。4.填空：A,≤是平凡格，当且仅当().5.证明全序都是格。6.填空：设A,≤是格,A,∨,∧是由格A,≤诱导的代数系统。其中∨与∧是在A上定义二元运算。:a,b∈A则a∨b表示（）。1dabcefghijk5246lmnoqrp387(a)(b)(c)(d)６１３12２2436303１2510156A,≤C,≤B,≤4123a∧b表示（）。7.说明什么叫子格？8.给定偏序集A,≤、B,≤、C,≤如下图所示，其中哪些不是格A,≤的子格？为什么？9.设A,≤是一个格,任取a,b∈A,ab(即a≤b∧a≠b),构造集合：B={x|x∈A且a≤x≤b},证明B,≤也是格.10.具有一、二、三个元素的格各有几种不同构形式？请分别请画出它们的哈斯图。11.具有四个元素的格有几种不同构形式？请分别请画出它们的哈斯图。12具有五个元素的格有几种不同构形式？请分别请画出它们的哈斯图。13.证明格中下面式子成立：(a∧b)∨(c∧d)≤(a∨c)∧(b∨d)bacfegbacfegdB,≤A,≤acbdC,≤14.请说出什么叫分配格？15.指出判定一个格是分配格的充分且必要条件是在该格中没有任何子格与两个五元素非分配格之一同构。请画出这两个五元素非分配格。16.下面具有五个元素的格中，哪些是分配格？17.具有五个元素的格中，有几个不是分配格？请画出这些非分配格的图。18.验证下面格不是分配格。19.验证下面格不是分配格。313025abcde20.下面图中哪个是分配格？对不是分配格的，说明原因。21.给定集合如下：A1={1,2,4,8,16}A2={1,2,3,5,6,10,15,30}A3={1,2,3,5,30}A4={1,2,3,5,10,15,30}A5={1,2,3,4,9,36}令≤是上述集合上的整除关系。1.请分别画出各个偏序集Ai,≤的哈斯图（i=1,2,3,4,5）2.用“√”表示“是”，用“×”表示“否”填下表。A1,≤A2,≤A3,≤A4,≤A5,≤分配格有补格布尔格注意：如果1题不答而只填此表、或者全都画√、或者全都画×，则都不给分。22.设A,≤是分配格,a,b∈A,且ab,证明f(x)=(x∨a)∧b是一个从A到B的同态映射。其中B={x|x∈A且a≤x≤b}。(a)dcabfe12345(b)fgadceb(c)deabc23给出有界格如图(1)所示。问a)哪些元素有补元?b)该格是分配格吗?c)该格是有补格吗?24.证明具有两个或更多个元素的格中不存在以自身为补元的元素。25.在有界分配格中,证明具有补元的那些元素组成一个子格。26.设A,≤是有界格,对于任何x,y∈A,证明a).x∨y=0,则x=y=0b).x∧y=1,则x=y=127.填空1．A,≤是布尔格，当且仅当它是()格。28.下面(a),(b),(c)三个格是布尔格吗？如果是，请指出各个格的原子。1cabdfge0eda0f(1)(2)29.下面的说法是否正确？为什么？1．不是所有格都是有界格。2．少于五个元素的格，都是分配格。30.设A,∨,∧是由格A,≤诱导的代数系统，求证如果∧对∨可分配，则∨对∧也可分配。31.设A,≤是布尔格，求证，对于任何a,b,c∈A，如果有a∧b=a∧c和a∨b=a∨c成立，则b=c。32.判断下面命题的真值，并说明原因。所有链都不是有补格。33.判断下面命题的真值，并说明原因。A,≤是格，如果|A|=3，则它不是有补格；如果|A|5，则它必是分配格。34.判断下面命题的真值，并说明原因。1e0dfbca0101ab(a)(b)(c)A,≤是有限布尔格，仅当它的元素个数为2n。(n是正整数)35.设A,,,是布尔代数，*是A上的二元运算，定义如下：a*b=ab其中a,bA1．化简表达式abaaba)(())((2．A,*是否为半群？为什么？36.设S,∨,∧,¯是布尔代数，x,y∈S,证明:x≤y当且仅当xy37.举例说明并非有补格都是分配格。并非分配格都是有补格。（画出图说明即可）38.给定布尔代数{0,1},∨,∧,―中的布尔表达式E(x,y,z)如下，请用最简单的方法对它化简。(提示：考虑析取范式与合取范式的关系))()()()()()(),,(zyxzyxzyxzyxzyxzyxzyxE39.给定布尔代数{0,1},∨,∧,―中的布尔表达式E(x,y,z)如下，请用最简单的方法对它化简。(提示：考虑析取范式与合取范式的关系))()()()()()(),,(zyxzyxzyxzyxzyxzyxzyxE40.给定布尔代数{0,1},∨,∧,¯上的一个布尔表达式如下：)()()(),,(323221321xxxxxxxxxE分别写出它的析取范式与合取范式。1.答案：A,≤是偏序集，如果任何a,b∈A,使得{a,b}都有最大下界和最小上界，则称A,≤是格。2.答案：A,≤不是格。因为{24,36}无上界，所以无上确界。所以不是格。3.(a)不是格，因为d和e没有下确界,也没有上确界.(d)不是格，因为5和6没有下确界,7和8既没下确界,也没上确界.4.答案：(A,≤是全序)5.答案：设A,≤是全序。所以A中任何两个元素x,y，要么有x≤y,要么有y≤x。如果x≤y，则{x,y}的最大下界为x，最小上界为y。如果y≤x，则{x,y}的最大下界为y，最小上界为x。即{x,y}的最大下界为较小元素，最小上界为较大元素。所以全序都是格。6.答案：a∨b表示（LUB{a,b},或者{a,b}的最小上界）a∧b表示（GLB{a,b},或者{a,b}的最大下界）7.答案：设A,≤是格,A,∨,∧是由A,≤诱导的代数系统。B是A的非空子集，如果∧和∨在B上封闭，则称B,≤是A,≤的子格。8.答案：B,≤不是格A,≤的子格。因为在A,≤中，b∧c=d，而dB,，所以B,≤不是格A,≤的子格。9.答案：证明:显然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≤b，a≤x∧y≤b,于是有x∨y∈B,x∧y∈B,说明∨和∧在B上封闭。所以B,≤也是格。10.答案：含有一、二、三个元素的格都是链。都各有一种不同构形式。它们的哈斯图如下：11.答案：具有四个元素的格不同构形式有2钟。任何一个具有四个元素的格必同构于下面两种格形式之一：它们的哈斯图如下：aababc12.答案：具有五个元素的格有五种不同构的形式，其图形如下：设a,b是格A,≤中的两个元素,证明:a).a∧b=b当且仅当a∨b=a.b).a∧bb和a∧ba,当且仅当a与b是不可比较的.答案：证明:a)充分性：已知a∨b=a，b=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是不可比较的。13.答案：证明:∵(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)14.答案：A,∨,∧是由格A,≤诱导的代数系统。如果对a,b,c∈A，有a∨(b∧c)=(a∨b)∧(a∨c)，a∧(b∨c)=(a∧b)∨(a∧c)则称A,≤是分配格。15.答案：16.答案：a,d,e是分配格。17.答案：有两个。图形如下：313025deabcdabcdabc18.答案：2∧(3∨5)=2∧30=2(2∧3)∨(2∧5)=1∨1=12∧(3∨5)(2∧3)∨(2∧5)19.答案：c∧(b∨d)=c∧a=c(c∧b)∨(c∧d)=e∨d=dc∧(b∨d)(c∧b)∨(c∧d)20.答案：(a)和(b)是分配格。(c)不是分配格。因为(c)图等价于下面图(d)，而其中结点bfged构成的子格就是与五元素非分配格(e)同构的子格。所以它不是分配格。21.答案：1．各个偏序集Ai,≤的哈斯图如下：（i=1,2,3,4,5）2．A1,≤A2,≤A3,≤A4,≤A5,≤分配格√√×√×有补格×√√×√布尔格×√×××22.答案：证明:先证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的映射。1428166510151233013253015233010159423361fgadceb(d)14213(e)313025deabc再证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是同态映射。23.答案：解:a)a、c、d、f、g无补元；b和e互为补元；0和1互为补元。b)不是分配格,因为它含有如图(2)所示的子格。c)它不是有补格,因为很多元素无补元。24.答案：证明：设A,≤是格,且|A|≥2,假设有a∈A,使得aa∴a≠0,a≠1,但是有1=a∨a=a∨a=a0=a∧a=a∧a=a产生矛盾.所以不存在以自身为补元的元素.25.证明:设A,≤是有界分配格,令B={x|x∈A}任取a,b∈B,,,,,AbaAbaBba下面证明∨和∧在B上封闭,即a∨b和a∧b都有补元：所以B,≤是A,≤的子格。26.答案：证明: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=127.答案：1．（有补分配）。2．（xa=a）（xa=0）。28.答案：都是是布尔格。(a)：1是原子。(b)：a,b是原子。(c)：d,e,f是原子。29.答案：1．是正确的。因为有的格就不是有界格。例如I,,其中I是整数集合，是小于或等于关系。对于I就没有全上界，也没有全下界。所以它不是有界格。2．是正确的。因为少于五个元素的格，它们不可能与五元素的非分配格同构。所以都是分配格。30.答案：证明：设A,∨,∧是由格A,≤诱导的代数系统。且∧对∨可分配。任取a,b,c∈A，a∧(b∨c)=(a∧b)∨(a∧c)而(a∨b)∧(a∨c)=((a∨b)∧a)∨((a∨b)∧c)(分配)=a∨((a∨b)∧c)=a∨((a∧c)∨(b∧c))(吸收、分配)=(a