第七章格与布尔代数

1、第七章格与布尔代数1. 说明什么叫格?2.给定偏序集A, 、B, 、C, W 如下图所示，其中哪些不是格?为什么?1553*3下面图哪些是格？对于不是格的,要说明原因。bcq(C)(d)4.填空：A, 是平凡格,当且仅当().5. 证明全序都是格。其中V与人6. 填空：设A, 是格,A,V,人 是由格A, 诱导的代数系统。是在A上定义二元运算。Va,b A则aV b表示（）。14.请说出什么叫分配格?7. 说明什么叫子格?8. 给定偏序集A, w 、B, w 、C, w 如下图所示，其中哪些不是格A, w 的子格？为什么？ccfc9.设 A,B=x| x证明也是格.是一个格，任取a,b A,a

2、b (即a b Ab),构造集合: A 且 a xw b,10.具有一、二、三个元素的格各有几种不同构形式？请分别请画出它们的哈斯图。11.具有四个元素的格有几种不同构形式？请分别请画出它们的哈斯图。12具有五个元素的格有几种不同构形式？请分别请画出它们的哈斯图。15.指出判定一个格是分配格的充分且必要条件是在该格中没有任何子格与两个 五元素非分配格之一同构。请画出这两个五元素非分配格。16. 下面具有五个元素的格中，哪些是分配格?41bc17. 具有五个元素的格中，有几个不是分配格？请画出这些非分配格的图。18. 验证下面格不是分配格。19. 验证下面格不是分配格。cd20. 下面图中哪个是

3、分配格？对不是分配格的，说明原因。c4(C)21. 给定集合如下：Ai=1,2,4,8,16 A 2=1,2,3,5,6,1O,15,3O A3=1,2,3,5,3O a 4=1,2,3,5,1O,15,3O A5=1,2,3,4,9,36令w是上述集合上的整除关系。1. 请分别画出各个偏序集的哈斯图(i=1,2,3,4,5 )2. 用“2”表示“是”，用“X”表示“否”填下表。分配格有补格布尔格注意：如果1题不答而只填此表、或者全都画/或者全都画X,则都不给分。22.设A, 是分配格，a,b A,且ab,证明f(x)=(x V a) A b是一个从 A到B的 同态映射。其中B=x|x A且a

4、w xw b。a)b)c)bdgdf24.证明具有两个或更多个元素的格中不存在以自身为补元的元素。25.在有界分配格中，证明具有补元的那些元素组成一个子格。设A, 是有界格,对于任何x,y A,证明26.a) . x V y=0 ,则 x=y=Ob) . x A y=1,贝U x=y=127.填空1. A, w 是布尔格，当且仅当它是 ()格。28. 下面(a),(b),(c)三个格是布尔格吗？如果是，请指出各个格的原子。23给出有界格如图(1)所示。问 哪些元素有补元？ 该格是分配格吗？ 该格是有补格吗？bcf29. 下面的说法是否正确？为什么？1 .不是所有格都是有界格。2 少于五个元素的

5、格，都是分配格。30.设A, V , A 是由格A, w 诱导的代数系统，求证如果A对V可分配，则V对 A也可分配。31.设A, w 是布尔格，求证，对于任何a,b,c A，如果有aA b=a A c 禾R aV b=aV c 成立，则 b=c 。32. 判断下面命题的真值，并说明原因。所有链都不是有补格。33. 判断下面命题的真值，并说明原因。A, 是格，如果|A|=3，则它不是有补格；如果|A|5，则它必是分配格。34. 判断下面命题的真值，并说明原因。A, w 是有限布尔格，仅当它的元素个数为2n。（n是正整数）35. 设A,羽八，-是布尔代数，*是A上的二兀运算，定义如下: a*b=a

6、 JD 其中 a,bA1. 化简表达式（a*b）M a）*（a*b）* a2. A,*是否为半群？为什么？36. 设S, V , A , 是布尔代数，X,y S,证明: X w y当且仅当y兰x37. 举例说明并非有补格都是分配格。并非分配格都是有补格。（画出图说明即可）38. 给定布尔代数0,1, V , A， 中的布尔表达式 E（X,y,z）如下，请用最简单的方 法对它化简。（提示：考虑析取范式与合取范式的关系）yAZ)E（x,y,z） = （XAyAZ）v（X/yAZ）v（xA y/z）v（XA yA Z）v（x八V（X A y A Z）39. 给定布尔代数0,1, V ,A， 中的布尔

7、表达式 E（x,y,z）如下，请用最简单的方法 对它化简。（提示：考虑析取范式与合取范式的关系）E（X, y, Z）=（X 八 y 八 Z）V （X 八 y 八 Z）V（X A y A z） V（X 八 y A Z）V（X 八V（X八y八z）40.给定布尔代数0,1, V ,A ,上的一个布尔表达式如下:E(X1, X2, X3)=(X1 八 X2)V(X2 八 X3)V (X2A X3)91. 答案：A, 是偏序集，如果任何 a,b A,使得a,b都有最大下界和最小上界， 则称A, W 是格。2. 答案：A, 不是格。因为24,36无上界，所以无上确界。所以不是格。3. （a）不是格，因为d

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

9、如果A和V在 B上封闭，则称B, w 是A, w 的子格。8. 答案：B, w 不是格A, w 的子格。因为在A, w 中，bA c=d,而d誌B,，所以B, w 不是格A, w 的子格。9. 答案：证明：显然B是A的非空子集，個为aw aw b,aw bw b,所以a,b B）。 只要证明A和V在 B上封闭即可。任取x,y B,由B的构成得aw xw b,aw yw b,于是由格的性质得,aw x V y w b ,aw x A y w b,于是有 x V y B ,x A y B ,说明V和A在 B上圭寸闭。 所以B, w 也是格。10. 答案：含有一、二、三个元素的格都是链。都各有一种不

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

11、b, aA b a, 如果aA b=b,则有b a,如果aA b=a,则有a b,都与a与b是不可比较的矛 盾.所以有：aA b bA aA b* b,于是有 aA bbaA b aA aA b* a,于是有 aA ba必要性：已知 aA bb和aA ba,假设a与b是可比较的，则要么 a b,要么b w a.于是要么aA b=a要么aA b=b.这与aA bb和aA ba矛盾。所以 a与b是 不可比较的。13. 答案：证明：/ (aA b)w aw (aV c) / (aA b)w (aV c)/ (cA d) w cw (a V c) / (cA d) w (a V c) (a A b)

12、V (cA d) w (a V c)同理(aA b)w (bV d) (cA d)w (b V d) (aA b) V (cA d)w (b V d)(aA b) V (cA d) w (aV c) A (b V d)丁a,b,c A，有14. 答案：是由格诱导的代数系统。如果对aV (b A c) =(a V b) A (aV c),aA (b V c)= (a A b) V (aA c)则称是分配格。cda,d,e是分配格。有两个。图形如下:15. 答案：16. 答案:17. 答案:cd18. 答案:19. 答案:20. 答案:2 A (3 V 5)=2 A 30=2 (2 A 3) V

13、(2 A 5)=1 V 1=1 2A (3 V 5)H (2 A 3) V (2 A 5) cA (b V d)=c A a=c (cA b) V (cA d)=e V d=d cA (b V d)工(cA b) V (cA d) 和(b)是分配格。(c)不是分配格。bfged构成的子格就是与五元素非分c(d)配格(e)同构的子格。所以它不是分配格。2321.答案：1.各个偏序集(i=1,2,3,4,5)16“的哈斯图如下:102314215因为(c)图等价于下面图(d),而其中结点2.分配格VVXVX有补格XVVXV布尔格X 11 VXXX(X22. 答案：证明：先证f是从A到B的映射：任取

14、X A,由f的定义得f(x)=(x V a) A b)显然V a)A bw b,而(x V a)A b=(x A b) V (aA b)=(x A b) V a (因 ab aA b=a) / aw (x V a) A b w b即 aw f(x) w b f(x) B ,. dom f=A.又由于 V和 A 的定义知(x A b) V a 是唯一的。即f(x)是唯一的.所以f是从A到B的映射。再证f满足同态等式：任取Xi,x2 A,f(x i a X2)=(x i a X2)V a) A b=(x i V a) A(X2 V a) A b=(x i V a)A b) A (x?V a)A b

15、) =f(x i) a f(X2) f(xi V X2)=(xiV X2)V a) a b=(x i V a)V g a) A b=(x i V a)A b) V (X2V a)A b) =f(x i) V f(X2)f是同态映射。23. 答案：解0和1互为补元。:a) a、c、d、f、g 无补元 ； b和e互为补元；b)不是分配格，因为它含有如图所示的子格。c) 它不是有补格，因为很多元素无补元。24. 答案：证明：设A, w 是格，且|A| 2,假设有a A,使得a = a / a 0,1,但是有1=a V a =a V a=a 0=aA a =aA a=a产生矛盾.所以不存在以自身为补元

16、的元素.25. 证明：设A, w 是有界分配格，令B=x| x A任取 a,b B,aAbA, avb 亡 A,下面证明V和A在 B上圭寸闭，即aV b和aA b都有补元：(a vb) v(a /b) =(avbva)A(avbvb) =1a1 =1 (a vb) A(a Ab) = (aAa/b)v(b八aAb) =0v0=0所以a vb 有补元a Ab _所以avb已B(aAb)v(avb) =(avavb)八(bvavb) =1a1=1(aAb)A(avb) = (a AbAa) v(aAb/b) = OvO =0 所以aAb有补元avb 所以aab亡B所以B, 是A, 的子格。26.

17、答案：证明：a) x=x A(X V y)=x A 0=0 y=y A (y V x)=y A 0=0b) x=x V(X A y)=x V 1=1 y=y V (y A x)=y V 1=127. 答案：1. (有补分配)。2. (x/a=a) (x/a=O)。28. 答案：都是是布尔格。(a)： 1是原子。(b): a,b是原子。(c)： d,e,f是原子。29. 答案：1.是正确的。兰是小于或等于关系。因为有的格就不是有界格。例如1,兰,其中I是整数集合，所以都是分配格。 且A对V可分配。对于I就没有全上界，也没有全下界。所以它不是有界格。 2 .是正确的。因为少于五个元素的格，它们不可

18、能与五元素的非分配格同构。30. 答案：证明：设A,V ,A 是由格A, w 诱导的代数系统。任取 a,b,c A, aA (b V c)= (a A b) V (a A c) 而(aV b) A (a V c) = (a V b) A a) V (a V b) A c)(分配)=a V (a V b) A c)=a V (a A c) V (b A c)(吸收、分配)=(a V (a A c) V (b A c)(结合)=a V (bA c)(吸收)所以V对A也可分配。31. 答案：证明：任取 a,b,c A,设有aA b=aA c及a V b=aV c16?b=b V (a A b)(吸收

19、律) =b V (aA c)(代换) =(b V a) A (b V c)(分配) =(a V b) A (b V c)(交换) =(a V c)A (b V c)(代换) =(a A b) V c (分配) =(a A c) V c (代换) =c (吸收律)32.答案：真值为真。因为任何链都不会含有与五元素非分配格之一同构的子格,所以链必是分配格。33.答案：真值为真。因为如果|A|=3，则它的哈斯图是链。中间元素没有补员。所以它不是有补格;如果|A|5，则它都不会含有与五元素非分配格之一同构的子格，所以它们必是分配格。34.答案：真值为真。因为根据stone(钻石)定理的推论1可得：有限布尔格，它的元素个数为2n。(n 是正整数)35.答案1 .化简表达式:(a * b) * a) * (a* b) * a = (a vb) va)* (a vb) V a) = (a A b) V a) * (a A b)v a) = a*a =ava = a2. 不是半群。因为a) 证明*满足封闭性：这显然成立。因为任何a,b A，在布尔代数中并和补运算封闭，所以a*b=a s己a , a*A。b) 证明*满足结合性：任取 a,b,c A,(