第七章 格与布尔代数
- 格式：doc
- 大小：287.50 KB
- 文档页数：14
第七章 格与布尔代数 1. 说明什么叫格？ 2. 给定偏序集、、如下图所示，其中哪些不是格？为什么？
3下面图哪些是格？对于不是格的，要说明原因。 4. 填空： 是平凡格，当且仅当 ( ). 5.证明全序都是格。
6. 填空： 设是格, 是由格诱导的代数系统。其中∨与∧是在A上定义二元运算。:a,b∈A则 a∨b表示（ ）。
1 d a b c e f g h i j k 5 2 4 6 l
m n
o q r p 3 8 7
(a) (b) (c) (d)
６ １ ３ 12 ２ 24 36 30 3 １ 2 5 10 15 6 4
1
2
3 a∧b表示（ ）。 7. 说明什么叫子格？ 8. 给定偏序集、、如下图所示，其中哪些不是格的子格？ 为什么？
9.设是一个格,任取a,b∈A,aB={x| x∈A且a≤x≤b}, 证明也是格.
10.具有一、二、三个元素的格各有几种不同构形式？请分别请画出它们的哈斯图。 11.具有四个元素的格有几种不同构形式？请分别请画出它们的哈斯图。 12具有五个元素的格有几种不同构形式？请分别请画出它们的哈斯图。 13. 证明格中下面式子成立： (a∧b)∨(c∧d)≤(a∨c)∧(b∨d)
b a c f e g b a c f e
g
d
a c b d 14. 请说出什么叫分配格？ 15. 指出判定一个格是分配格的充分且必要条件是在该格中没有任何子格与两个五元素非分配格之一同构。请画出这两个五元素非分配格。
16. 下面具有五个元素的格中，哪些是分配格？
17.具有五个元素的格中，有几个不是分配格？请画出这些非分配格的图。 18. 验证下面格不是分配格。
19. 验证下面格不是分配格。 3 1
30 2 5
a b c d e 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} 令≤是上述集合上的整除关系。 1. 请分别画出各个偏序集的哈斯图（i=1,2,3,4,5） 2. 用“√”表示“是”，用“×”表示“否”填下表。
分配格 有补格 布尔格 注意：如果1题不答而只填此表、或者全都画√、或者全都画×，则都不给分。
22. 设是分配格,a,b∈A, 且a同态映射。其中 B={x|x∈A且a≤x≤b}。
(a) d c a b f e 1 2 3 4 5 (b) f g
a d c
e b
(c)
d e
a b c 23 给出有界格如图(1)所示。问 a) 哪些元素有补元? b) 该格是分配格吗? c) 该格是有补格吗?
24. 证明具有两个或更多个元素的格中 不存在以自身为补元的元素。 25. 在有界分配格中,证明具有补元的那些元素组成一个子格。 26. 设是有界格, 对于任何x,y∈A, 证明 a). x∨y=0 , 则 x=y=0 b). x∧y=1, 则 x=y=1
27. 填空 1．是布尔格，当且仅当它是 ( ) 格。
28. 下面(a),(b),(c)三个格是布尔格吗？如果是，请指出各个格的原子。
1 c a b d f g e 0 e d a 0 f
(1) (2) 29.下面的说法是否正确？为什么？ 1．不是所有格都是有界格。 2．少于五个元素的格，都是分配格。
30. 设是由格诱导的代数系统，求证如果∧对∨可分配，则∨对∧也可分配。
31. 设是布尔格，求证，对于任何a,b,c∈A，如果有 a∧b=a∧c 和 a∨b=a∨c 成立，则 b=c 。
32. 判断下面命题的真值，并说明原因。 所有链都不是有补格。
33.判断下面命题的真值，并说明原因。 是格，如果|A|=3，则它不是有补格；如果|A|<5，则它必是分配格。
34.判断下面命题的真值，并说明原因。
1 e 0 d f b c a 0
1
0 1
a b
(a) (b) (c) 是有限布尔格，仅当它的元素个数为2n。(n是正整数) 35.设是布尔代数，* 是A上的二元运算，定义如下： a*b=ab 其中a,bA 1．化简表达式 abaaba)(())(( 2．是否为半群？为什么？
36. 设是布尔代数，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,b∈A,使得{a,b}都有最大下界和最小上界，则称是格。 2.答案：不是格。因为{24,36}无上界，所以无上确界。所以不是格。 3.(a) 不是格，因为d和e没有下确界,也没有上确界. (d) 不是格，因为5和6没有下确界,7和8既没下确界,也没上确界. 4.答案：(是全序 ) 5.答案：设是全序。所以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.答案：设是格, 是由诱导的代数系统。B是A的非空子集，如果∧和∨在B上封闭，则称是的子格。 8.答案：不是格的子格。 因为在中，b∧c=d，而dB,，所以不是格的子格。 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上封闭 。 所以也是格。 10.答案：含有一、二、三个元素的格都是链。都各有一种不同构形式。 它们的哈斯图如下：
11.答案：具有四个元素的格不同构形式有2钟。 任何一个具有四个元素的格必同构于下面两种格形式之一： 它们的哈斯图如下：
a a b a b c 12.答案：具有五个元素的格有五种不同构的形式，其图形如下： 设a,b是格中的两个元素,证明: a). a∧b=b 当且仅当a∨b=a. b). 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∨b b) 充分性:已知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∧ba∧b≤a∧ a∧b≠a,于是有 a∧b必要性：已知a∧b≤a. 于是要么a∧b=a 要么a∧b=b. 这与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,b,c∈A，有 a∨(b∧c) =(a∨b)∧(a∨c) ， a∧(b∨c)= (a∧b)∨(a∧c) 则称是分配格。 15.答案：
16.答案：a,d,e是分配格。 17.答案：有两个。图形如下：
3 1 30 2 5 d e
a b c
d a b c d a b c
