第七章格与布尔代数..doc

第七章 格与布尔代数 1. 说明什么叫格？ 2. 给定偏序集A,≤、B,≤、C,≤如下图所示，其中哪些不是格？为什么？ 3下面图哪些是格？对于不是格的，要说明原因。 4. 填空： A,≤是平凡格，当且仅当 ( ). 5.证明全序都是格。 6. 填空： 设A, ≤是格, A,∨,∧是由格A,≤诱导的代数系统。其中∨与∧是在A上定义二元运算。:a,b∈A则 a∨b表示（ ）。 a∧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) 14. 请说出什么叫分配格？ 15. 指出判定一个格是分配格的充分且必要条件是在该格中没有任何子格与两个五元素非分配格之一同构。请画出这两个五元素非分配格。 16. 下面具有五个元素的格中，哪些是分配格？ 17.具有五个元素的格中，有几个不是分配格？请画出这些非分配格的图。 18. 验证下面格不是分配格。 19. 验证下面格不是分配格。 20.下面图中哪个是分配格？对不是分配格的，说明原因。 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} 令≤是上述集合上的整除关系。 请分别画出各个偏序集Ai,≤的哈斯图（i=1,2,3,4,5） 用“√”表示“是”，用“×”表示“否”填下表。 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}。 23 给出有界格如图(1)所示。问 a) 哪些元素有补元? b) 该格是分配格吗? c) 该格是有补格吗? 24. 证明具有两个或更多个元素的格中 不存在以自身为补元的元素。 25. 在有界分配格中,证明具有补元的那些元素组成一个子格。 26. 设A,≤是有界格, 对于任何x,y∈A, 证明 a). x∨y=0 , 则 x=y=0 b). x∧y=1, 则 x=y=1 27. 填空 1．A,≤是布尔格，当且仅当它是 ( ) 格。 28. 下面(a),(b),(c)三个格是布尔格吗？如果是，请指出各个格的原子。 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.判断下面命题的真值，并说明原因。 A,≤是有限布尔格，仅当它的元素个数为2n。(n是正整数) 35.设A,ú,ù, -是布尔代数，* 是A上的二元运算，定义如下： a*b=úb 其中a,b?A 1．化简表达式 2．A,*是否为半群？为什么？ 36. 设S,∨,∧,ˉ是布尔代数，x,y∈S, 证明: x≤y 当且仅当 37. 举例说明并非有补格都是分配格。并非分配格都是有补格。（画出图说明即可） 38. 给定布尔代数{0,1},∨,∧,―中的布尔表达式E(x,y,z)如下，请用最简单的方法对它化简。(提示：考虑析取范式与合取