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