第七章格与布尔代数.docx

第七章格与布尔代数.docx

《第七章格与布尔代数.docx》由会员分享，可在线阅读，更多相关《第七章格与布尔代数.docx（18页珍藏版）》请在冰点文库上搜索。

第七章格与布尔代数

第七章格与布尔代数

1.说明什么叫格？

2.给定偏序集、、如下图所示，其中哪些不是格？

为什么？

3下面图哪些是格？

对于不是格的，要说明原因。

4.填空：

是平凡格，当且仅当（）.

5.证明全序都是格。

6.填空：

设是格,是由格诱导的代数系统。

其中∨与∧是在A上定义二元运算。

:

a,b∈A则

a∨b表示（）。

a∧b表示（）。

7.说明什么叫子格？

8.给定偏序集、、如下图所示，其中哪些不是格的子格？

为什么？

9.设是一个格,任取a,b∈A,a

B={x|x∈A且a≤x≤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}

令≤是上述集合上的整除关系。

1.请分别画出各个偏序集的哈斯图（i=1,2,3,4,5）

2.用“√”表示“是”，用“×”表示“否”填下表。

分配格

有补格

布尔格

注意：

如果1题不答而只填此表、或者全都画√、或者全都画×，则都不给分。

22.设是分配格,a,b∈A,且a

其中B={x|x∈A且a≤x≤b}。

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）三个格是布尔格吗？

如果是，请指出各个格的原子。

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.判断下面命题的真值，并说明原因。

是有限布尔格，仅当它的元素个数为2n。

（n是正整数）

35.设是布尔代数，*是A上的二元运算，定义如下：

a*b=

b其中a,bA

1．化简表达式

2．是否为半群？

为什么？

36.设是布尔代数，x,y∈S,证明:

x≤y当且仅当

37.举例说明并非有补格都是分配格。

并非分配格都是有补格。

（画出图说明即可）

38.给定布尔代数<{0,1},∨,∧,―>中的布尔表达式E（x,y,z）如下，请用最简单的方法对它化简。

（提示：

考虑析取范式与合取范式的关系）

39.给定布尔代数<{0,1},∨,∧,―>中的布尔表达式E（x,y,z）如下，请用最简单的方法对它化简。

（提示：

考虑析取范式与合取范式的关系）

40.给定布尔代数<{0,1},∨,∧,¯>上的一个布尔表达式如下：

分别写出它的析取范式与合取范式。

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钟。

任何一个具有四个元素的格必同构于下面两种格形式之一：

它们的哈斯图如下：

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∧b

a∧b≤a∧a∧b≠a,于是有a∧b

必要性：

已知a∧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.答案：

有两个。

图形如下：

18.答案：

2∧（3∨5）=2∧30=2（2∧3）∨（2∧5）=1∨1=12∧（3∨5）（2∧3）∨（2∧5）

19.答案：

c∧（b∨d）=c∧a=c（c∧b）∨（c∧d）=e∨d=dc∧（b∨d）（c∧b）∨（c∧d）

20.答案：

（a）和（b）是分配格。

（c）不是分配格。

因为（c）图等价于下面图（d），而其中结点bfged构成的子格就是与五元素非分配格（e）同构的子格。

所以它不是分配格。

21.答案：

1．各个偏序集的哈斯图如下：

（i=1,2,3,4,5）

2．

分配格

√

√

×

√

×

有补格

×

√

√

×

√

布尔格

×

√

×

×

×

22.答案：

证明:

先证f是从A到B的映射:

任取x∈A,由f的定义得f（x）=（x∨a）∧b）显然（x∨a）∧b≤b，而（x∨a）∧b=（x∧b）∨（a∧b）=（x∧b）∨a（因a

即a≤f（x）≤b∴f（x）∈B，∴domf=A.又由于∨和∧的定义知（x∧b）∨a是唯一的。

即f（x）是唯一的.所以f是从A到B的映射。

再证f满足同态等式:

任取x1,x2∈A,

f（x1∧x2）=（（x1∧x2）∨a）∧b=（（x1∨a）∧（x2∨a））∧b

=（（x1∨a）∧b）∧（（x2∨a）∧b）=f（x1）∧f（x2）

f（x1∨x2）=（（x1∨x2）∨a）∧b=（（x1∨a）∨（x2∨a））∧b

=（（x1∨a）∧b）∨（（x2∨a）∧b）=f（x1）∨f（x2）

∴f是同态映射。

23.答案：

解

:

a）a、c、d、f、g无补元；b和e互为补元；0和1互为补元。

b）不是分配格,因为它含有如图

（2）所示的子格。

c）它不是有补格,因为很多元素无补元。

24.答案：

证明：

设是格,且|A|≥2,假设有a∈A,使得

∴a≠0,a≠1,但是有

1=a∨

=a∨a=a0=a∧

=a∧a=a

产生矛盾.所以不存在以自身为补元的元素.

25.证明:

设是有界分配格,令B={x|

∈A}

任取a,b∈B,

下面证明∨和∧在B上封闭,即a∨b和a∧b都有补元：

所以是的子格。

26.答案：

证明:

a）x=x∧（x∨y）=x∧0=0y=y∧（y∨x）=y∧0=0

b）x=x∨（x∧y）=x∨1=1y=y∨（y∧x）=y∨1=1

27.答案：

1．（有补分配）。

2．（xa=a）（xa=0）。

28.答案：

都是是布尔格。

（a）：

1是原子。

（b）：

a,b是原子。

（c）：

d,e,f是原子。

29.答案：

1．是正确的。

因为有的格就不是有界格。

例如,其中I是整数集合，是小于或等于关系。

对于I就没有全上界，也没有全下界。

所以它不是有界格。

2．是正确的。

因为少于五个元素的格，它们不可能与五元素的非分配格同构。

所以都是分配格。

30.答案：

证明：

设是由格诱导的代数系统。

且∧对∨可分配。

任取a,b,c∈A，a∧（b∨c）=（a∧b）∨（a∧c）

而（a∨b）∧（a∨c）=（（a∨b）∧a）∨（（a∨b）∧c）（分配）

=a∨（（a∨b）∧c）=a∨（（a∧c）∨（b∧c））（吸收、分配）

=（a∨（a∧c））∨（b∧c）（结合）

=a∨（b∧c）（吸收）

所以∨对∧也可分配。

31.答案：

证明：

任取a,b,c∈A,设有a∧b=a∧c及a∨b=a∨c

b=b∨（a∧b）（吸收律）

=b∨（a∧c）（代换）

=（b∨a）∧（b∨c）（分配）

=（a∨b）∧（b∨c）（交换）

=（a∨c）∧（b∨c）（代换）

=（a∧b）∨c（分配）

=（a∧c）∨c（代换）

=c（吸收律）

32.答案：

真值为真。

因为任何链都不会含有与五元素非分配格之一同构的子格，所以链必是分配格。

33.答案：

真值为真。

因为

如果|A|=3，则它的哈斯图是链。

中间元素没有补员。

所以它不是有补格；

如果|A|<5，则它都不会含有与五元素非分配格之一同构的子格，所以它们必是分配格。

34.答案：

真值为真。

因为

根据stone（钻石）定理的推论1可得：

有限布尔格，它的元素个数为2n。

（n是正整数）

35.答案

1．化简表达式：

．

2．不是半群。

因为

a）证明*满足封闭性：

这显然成立。

因为

任何a,b∈A，在布尔代数中并和补运算封闭，所以a*b=

bA，a*bA。

b）证明*满足结合性：

任取a,b,c∈A，

（a*b）*ca*（b*c）,可见*不满足可结合性。

所以不是半群。

36.答案：

证明

充分性：

已知

。

必要性：

已知x≤y

37.答案：

38.答案：

=m7∨m3∨m5∨m2∨m4∨m0

=M1∧M6

=

39.答案：

=m7∨m3∨m6∨m5∨m4∨m2

=M0∧M1

=

=

=x∨y

40.答案:

先列出真值表如下：

E（x1,x2,x3）=