第七章 格与布尔代数1. 说明什么叫格？2. 给定偏序集<A,≤>、<B,≤>、<C,≤>如下图所示，其中哪些不是格？为什么？3下面图哪些是格？对于不是格的，要说明原因。
4. 填空： <A,≤>是平凡格，当且仅当 ( ).5.证明全序都是格。
6. 填空： 设<A, ≤>是格, <A,∨,∧>是由格<A,≤>诱导的代数系统。
其中∨与∧是在A 上定义二元运算。
: a,b ∈A 则 a ∨b 表示（ ）。
q(a)(b)(c)(d)３２5156<A,≤> <C,≤><B,≤>41 23a ∧b 表示（ ）。
7. 说明什么叫子格？8. 给定偏序集<A,≤>、<B,≤>、<C,≤>如下图所示，其中哪些不是格<A,≤>的子格？ 为什么？9.设<A, ≤>是一个格,任取a,b ∈A,a<b (即a ≤b ∧a ≠b) ,构造集合： B={x| x ∈A 且a ≤x ≤b}, 证明<B, ≤>也是格.10.具有一、二、三个元素的格各有几种不同构形式？请分别请画出它们的哈斯图。
11.具有四个元素的格有几种不同构形式？请分别请画出它们的哈斯图。
12具有五个元素的格有几种不同构形式？请分别请画出它们的哈斯图。
13. 证明格中下面式子成立： (a ∧b)∨(c ∧d)≤(a ∨c)∧(b ∨d)aac<B,≤> <A,≤>a<C,≤>14. 请说出什么叫分配格？15. 指出判定一个格是分配格的充分且必要条件是在该格中没有任何子格与两个五元素非分配格之一同构。
请画出这两个五元素非分配格。
16. 下面具有五个元素的格中，哪些是分配格？17.具有五个元素的格中，有几个不是分配格？请画出这些非分配格的图。
18. 验证下面格不是分配格。
19. 验证下面格不是分配格。
a b c de20.下面图中哪个是分配格？对不是分配格的，说明原因。
21. 给定集合如下：A 1={1,2,4,8,16} A 2={1,2,3,5,6,10,15,30}A 3={1,2,3,5,30} A 4={1,2,3,5,10,15,30} A 5={1,2,3,4,9,36}令≤是上述集合上的整除关系。
1. 请分别画出各个偏序集<A i ,≤>的哈斯图（i=1,2,3,4,5）22. 设<A,≤>是分配格,a,b ∈A, 且a<b, 证明 f(x)=(x ∨a)∧b 是一个从A 到B 的同态映射。
其中 B={x|x ∈A 且a ≤x ≤b}。
(a)34(b)b(c)dac23 给出有界格如图(1)所示。
问 a) 哪些元素有补元? b) 该格是分配格吗? c) 该格是有补格吗?24. 证明具有两个或更多个元素的格中 不存在以自身为补元的元素。
25. 在有界分配格中,证明具有补元的那些元素组成一个子格。
26. 设<A,≤>是有界格, 对于任何x,y ∈A, 证明 a). x ∨y=0 , 则 x=y=0 b). x ∧y=1, 则 x=y=127. 填空1．<A,≤>是布尔格，当且仅当它是 ( ) 格。
28. 下面(a),(b),(c)三个格是布尔格吗？如果是，请指出各个格的原子。
cbdgedaf(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.判断下面命题的真值，并说明原因。
d fc1b(a)(b)<A,≤>是有限布尔格，仅当它的元素个数为2n 。
(n 是正整数)35.设<A,∨,∧, ->是布尔代数，* 是A 上的二元运算，定义如下： a *b=a ∨b 其中a,b ∈A1．化简表达式 a b a a b a *****)(())(( 2．<A,*>是否为半群？为什么？36. 设<S,∨,∧,¯>是布尔代数，x,y ∈S, 证明:x ≤y 当且仅当 x y ≤37. 举例说明并非有补格都是分配格。
并非分配格都是有补格。
（画出图说明即可）38. 给定布尔代数<{0,1},∨,∧,―>中的布尔表达式E(x,y,z)如下，请用最简单的方法对它化简。
(提示：考虑析取范式与合取范式的关系))()()()()()(),,(z y x z y x z y x z y x z y x z y x z y x E ∧∧∨∧∧∨∧∧∨∧∧∨∧∧∨∧∧=39.给定布尔代数<{0,1},∨,∧,―>中的布尔表达式E(x,y,z)如下，请用最简单的方法对它化简。
(提示：考虑析取范式与合取范式的关系))()()()()()(),,(z y x z y x z y x z y x z y x z y x z y x E ∧∧∨∧∧∨∧∧∨∧∧∨∧∧∨∧∧=40.给定布尔代数<{0,1},∨,∧, ¯ >上的一个布尔表达式如下：)()()(),,(323221321x x x x x x x x x E ∧∨∧∨∧=分别写出它的析取范式与合取范式。
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 ∧b<b 和a ∧b<a,当且仅当 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 ∧b<b a ∧b ≤a ∧ a ∧b ≠a,于是有 a ∧b<a必要性：已知a ∧b<b 和a ∧b<a, 假设a 与b 是可比较的，则要么a ≤b,要么b ≤a. 于是要么a ∧b=a 要么a ∧b=b. 这与a ∧b<b 和a ∧b<a 矛盾。
所以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.答案：有两个。
图形如下：dacdab18.答案：2∧(3∨5)=2∧30=2 (2∧3)∨(2∧5)=1∨1=1 2∧(3∨5)≠ (2∧3)∨(2∧5) 19.答案：c ∧(b ∨d)=c ∧a=c (c ∧b)∨(c ∧d)=e ∨d=d c ∧(b ∨d) ≠(c ∧b)∨(c ∧d) 20.答案：(a)和(b)是分配格。
(c)不是分配格。
因为(c)图等价于下面图(d)，而其中结点bfged 构成的子格就是与五元素非分配格(e)同构的子格。