第七章格与布尔代数

1、第七章 格与布尔代数1. 说明什么叫格？2. 给定偏序集<A,>、<B,>、<C,>如下图所示，其中哪些不是格？为什么？1224363032510156<A,><C,><B,>41233下面图哪些是格？对于不是格的，要说明原因。1dabcefghijk5246lmnoqrp387(a)(b)(c)(d)4. 填空： <A,>是平凡格，当且仅当 ( ).5.证明全序都是格。6. 填空： 设<A, >是格, <A,>是由格<A,>诱导的代数系统。其中与是在A上定义二元运算。:&q

2、uot;a,bA则ab表示（ ）。ab表示（ ）。7. 说明什么叫子格？8. 给定偏序集<A,>、<B,>、<C,>如下图所示，其中哪些不是格<A,>的子格？为什么？b acfe gb acfe gd<B,><A,>acb d<C,>9.设<A, >是一个格,任取a,bA,a<b (即abab) ,构造集合：B=x| xA且axb,证明<B, >也是格.10.具有一、二、三个元素的格各有几种不同构形式？请分别请画出它们的哈斯图。11.具有四个元素的格有几种不同构形式？请分别请画出它

3、们的哈斯图。12具有五个元素的格有几种不同构形式？请分别请画出它们的哈斯图。13. 证明格中下面式子成立： (ab)(cd)(ac)(bd)14. 请说出什么叫分配格？ 15. 指出判定一个格是分配格的充分且必要条件是在该格中没有任何子格与两个五元素非分配格之一同构。请画出这两个五元素非分配格。16. 下面具有五个元素的格中，哪些是分配格？abcde17.具有五个元素的格中，有几个不是分配格？请画出这些非分配格的图。18. 验证下面格不是分配格。31302519. 验证下面格不是分配格。deabc20.下面图中哪个是分配格？对不是分配格的，说明原因。(a)dcab fe12345(b)fgad

4、ceb(c)21. 给定集合如下：A1=1,2,4,8,16 A2=1,2,3,5,6,10,15,30A3=1,2,3,5,30 A4=1,2,3,5,10,15,30A5=1,2,3,4,9,36 令是上述集合上的整除关系。1. 请分别画出各个偏序集<Ai,>的哈斯图（i=1,2,3,4,5）2. 用“”表示“是”，用“×”表示“否”填下表。<A1,><A2,><A3,><A4,><A5,>分配格有补格布尔格注意：如果1题不答而只填此表、或者全都画、或者全都画×，则都不给分。22. 设<A,&

5、gt;是分配格,a,bA, 且a<b, 证明 f(x)=(xa)b 是一个从A到B的同态映射。其中 B=x|xA且axb。23 给出有界格如图(1)所示。问a) 哪些元素有补元?b) 该格是分配格吗?c) 该格是有补格吗?1cabdfge 0eda0f(1)(2)24. 证明具有两个或更多个元素的格中 不存在以自身为补元的元素。25. 在有界分配格中,证明具有补元的那些元素组成一个子格。26. 设<A,>是有界格, 对于任何x,yA, 证明 a). xy=0 , 则 x=y=0 b). xy=1, 则 x=y=1 27. 填空1<A,>是布尔格，当且仅当它是 (

6、) 格。 28. 下面(a),(b),(c)三个格是布尔格吗？如果是，请指出各个格的原子。1e0dfbca0101ab(a)(b)(c)29.下面的说法是否正确？为什么？1不是所有格都是有界格。2少于五个元素的格，都是分配格。30. 设<A,>是由格<A,>诱导的代数系统，求证如果对可分配，则对也可分配。31. 设<A,>是布尔格，求证，对于任何a,b,cA，如果有ab=ac 和 ab=ac 成立，则 b=c 。32. 判断下面命题的真值，并说明原因。所有链都不是有补格。33.判断下面命题的真值，并说明原因。<A,>是格，如果|A|=3，则它不是

7、有补格；如果|A|<5，则它必是分配格。34.判断下面命题的真值，并说明原因。<A,>是有限布尔格，仅当它的元素个数为2n。(n是正整数) 35.设<A,Ú,Ù, ->是布尔代数，* 是A上的二元运算，定义如下：a*b=Úb 其中a,bÎA1化简表达式 2<A,*>是否为半群？为什么？36. 设<S,¯>是布尔代数，x,yS, 证明:xy 当且仅当 37. 举例说明并非有补格都是分配格。并非分配格都是有补格。（画出图说明即可）38. 给定布尔代数<0,1,>中的布尔表达式E(x,

8、y,z)如下，请用最简单的方法对它化简。(提示：考虑析取范式与合取范式的关系)39.给定布尔代数<0,1,>中的布尔表达式E(x,y,z)如下，请用最简单的方法对它化简。(提示：考虑析取范式与合取范式的关系)40.给定布尔代数<0,1, ¯ >上的一个布尔表达式如下：分别写出它的析取范式与合取范式。1.答案：<A,>是偏序集，如果任何a,bA,使得a,b都有最大下界和最小上界，则称<A,>是格。 2.答案：<A,>不是格。因为24,36无上界，所以无上确界。所以不是格。3.(a) 不是格，因为d和e没有下确界,也没有上确界.

9、(d) 不是格，因为5和6没有下确界,7和8既没下确界,也没上确界.4.答案：(<A,>是全序 ) 5.答案：设<A,>是全序。所以A中任何两个元素x,y，要么有xy, 要么有yx。如果xy，则x,y的最大下界为x，最小上界为y。如果yx，则x,y的最大下界为y，最小上界为 x 。即x,y的最大下界为较小元素，最小上界为较大元素。所以全序都是格。6.答案：ab表示（LUB a,b, 或者a,b的最小上界）ab表示（GLB a,b, 或者a,b的最大下界）7.答案：设<A,>是格, <A,>是由<A,>诱导的代数系统。B是A的非空子集，

10、如果和在B上封闭，则称<B, >是<A, >的子格。8.答案：<B,>不是格<A,>的子格。因为在<A,>中，bc=d，而dÏB,，所以<B,>不是格<A,>的子格。9.答案：证明:显然B是A的非空子集, (因为aab,abb,所以a,bB)。只要证明和在B上封闭即可。任取x,yB, 由B的构成得axb,ayb, 于是由格的性质得,axyb ，axyb, 于是有 xyB ,xyB , 说明和在B上封闭 。所以<B, >也是格。10.答案：含有一、二、三个元素的格都是链。都各有一种不同构形式

11、。它们的哈斯图如下：· aababc11.答案：具有四个元素的格不同构形式有2钟。任何一个具有四个元素的格必同构于下面两种格形式之一：它们的哈斯图如下：dabcdabc12.答案：具有五个元素的格有五种不同构的形式，其图形如下：设a,b是格<A, >中的两个元素,证明:a). ab=b 当且仅当ab=a.b). ab<b和ab<a,当且仅当 a与b是不可比较的.答案：证明:a) 充分性：已知ab=a，b=b(ba)= b(ab) =ba=ab必要性：已知ab=b , a=a(ab)=abb) 充分性:已知a与b是不可比较的. 因abb, aba, 如果ab=b

12、, 则有ba, 如果ab=a, 则有ab,都与a与b是不可比较的矛盾. 所以有：abb abb,于是有 ab<baba aba,于是有 ab<a 必要性：已知ab<b和ab<a, 假设a与b是可比较的，则要么ab,要么ba. 于是要么ab=a 要么ab=b. 这与ab<b和ab<a矛盾。所以a与b是不可比较的。13. 答案：证明: (ab)a(ac) (ab)(ac) (cd)c(ac) (cd)(ac) (ab)(cd)(ac)同理 (ab)(bd) (cd)(bd) (ab)(cd)(bd)(ab)(cd)(ac)(bd)14.答案：<A,>

13、是由格<A,>诱导的代数系统。如果对"a,b,cA，有a(bc) =(ab)(ac) ， a(bc)= (ab)(ac)则称<A,>是分配格。15.答案：313025deabc16.答案：a,d,e是分配格。17.答案：有两个。图形如下：313025deabc18.答案：2(35)=230=2 (23)(25)=11=1 2(35)¹ (23)(25)19.答案：c(bd)=ca=c (cb)(cd)=ed=d c(bd) ¹(cb)(cd) 20.答案：(a)和(b)是分配格。 (c)不是分配格。因为(c)图等价于下面图(d)，而其中结点

14、bfged构成的子格就是与五元素非分配格(e)同构的子格。所以它不是分配格。fgadceb(d)1 4213(e)21.答案：1各个偏序集<Ai,>的哈斯图如下：（i=1,2,3,4,5）14281665101512330132530152330101594233612<A1,><A2,><A3,><A4,><A5,>分配格××有补格××布尔格××××22.答案：证明:先证 f 是从A到B的映射:任取xA, 由f的定义得f(x)=(xa)b)

15、显然 (xa)bb，而 (xa)b=(xb)(ab)=(xb)a (因a<b ab=a) a(xa)bb 即af(x)b f(x)B， dom f=A. 又由于和的定义知(xb)a是唯一的。即f(x)是唯一的. 所以f 是从A到B的映射。再证f 满足同态等式:任取x1,x2A,f(x1x2)=(x1x2)a)b=(x1a)(x2a)b=(x1a)b)(x2a)b) =f(x1)f(x2)f(x1x2)=(x1x2)a)b=(x1a)(x2a)b=(x1a)b)(x2a)b) =f(x1)f(x2) f 是同态映射。23.答案：解:a) a、c、d、f、g 无补元 ； b和e互为补元； 0

16、和1互为补元。b) 不是分配格, 因为它含有如图(2)所示的子格。c) 它不是有补格,因为很多元素无补元。24.答案：证明：设<A,>是格,且|A|2, 假设有aA,使得 a0, a1, 但是有1=a=aa=a 0=a=aa=a产生矛盾. 所以不存在以自身为补元的元素.25.证明: 设<A,>是有界分配格,令B=x| A任取a,bB, 下面证明和在B上封闭,即ab和ab都有补元：所以<B,>是<A,>的子格。26.答案：证明:a) x=x(xy)=x0=0 y=y(yx)=y0=0 b) x=x(xy)=x1=1 y=y(yx)=y1=127.答

17、案：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,cA， a(bc)= (ab)(ac)而 (ab)(ac)

18、= (ab)a)(ab)c) (分配)=a(ab)c)=a(ac)(bc) (吸收、分配) = (a(ac)(bc) (结合)= a(bc) (吸收) 所以对也可分配。31.答案：证明：任取a,b,cA, 设有 ab=ac 及 ab=ac b=b(ab) (吸收律)=b(ac) (代换)=(ba)(bc) (分配)=(ab)(bc) (交换)=(ac)(bc) (代换)= (ab)c (分配) = (ac)c (代换)=c (吸收律)32.答案：真值为真。因为任何链都不会含有与五元素非分配格之一同构的子格，所以链必是分配格。33.答案：真值为真。因为如果|A|=3，则它的哈斯图是链。中间元素没有补员。所以它不是有补格；如果|A|<5，则它都不会含有与五元素非分配格之一同构的子格，所以它们必是分配格。34.答案：真值为真。因为根据stone(钻石)定理的推论1可得：有限布尔格，它的元素个数为2n。(n是正整数) 35.答案1化简表达式：2<A,*>不是半群。因为a) 证明 * 满足