《离散数学》练习题和参考答案

（格与布尔代数）

67、当n分别是24，36，110时，是布尔代数吗？若是，则求出其原子集。 解：

因为|S24|=8，|S36|=9，|S110|=8，故不是布尔代数。在中12没有补元，故它也不是布尔代数。是布尔代数，其原子集为{2,5,11}。 68、设L是有界格，且|L|>1。证明：0?1。 证明： 用反证法证明。

设0=1。则任取a?L，则由于L是有界格，故a?1且0?a。即0?a?1。因为0=1且?是L上的偏序关系，所以a=0。这与已知|L|>1矛盾。

69、设(L,≤)是格，若a,b,c?L，a≤b≤c，则 a?b=b⊙c , (a⊙b)?(b⊙c)=(a?b)⊙(a?c) 证明：

因为a?b?c，所以a?b=a，a?b=b=b，且b=b?c，以c=b?c。从而a?b=b?c。 (a?b)?(b?c)=a?(b?c)=a?(a?b)=(a?a) ?b=a?b=b， (a?b)?(a?c)=(b?c)?(a?c)=b?(c?(a?c))=b?c=b。 70、在布尔代数中，证明恒等式a?(a??b)=a?b 证明：

a?(a??b)=(a?a?)?(a?b)=1?(a?b)=a?b

71、设是格，a1,a2,…,an?L。试证：a1?a2?…?an= a1?a2?…?an当且仅当a1=a2=…=an。 证明：

? 显然是成立的。

? 对任一k=1,2,..,n，a1?a2?…?an?ak，ak?a1?a2?…?an。

因为a1?a2?…?an= a1?a2?…?an，且?是L上的偏序关系，故ak=a1?a2?…?an。从而a1=a2=…=an。 72、在布尔代数中，证明恒等式(a?c)?(a??b)?(b?c)=(a?c)?(a??b) 证明：

((a?c)?(a??b))?(b?c)=((a?c)?(b?c))?((a??b)?(b?c)) =(a?b?c)?(a??b?c)=(a?a?)?b?c=1?b?c=b?c, 故 b?c?(a?c)?(a??b)，从而

(a?c)?(a??b)?(b?c)=(a?c)?(a??b)。 73、在布尔代数中，证明恒等式(a?b)?(a??c)?(b?证明：

(a?b)?(a??c)?(b?

?c)=(a?b)?c

?c)=(a?b)?((a??b?)?c)

37

=(a?b)?((a?b)??c)=(a?b)?c。

74、设是格，a,b,c,d?L。试证：若a?b且c?d，则 a?c?b?d 证明：

因为a?b，c?d，所以a=a?b,c=c?d。从而

(a?c)?(b?d)=((a?c)?b)?d=(b?(a?c))?d=((b?a)?c)?d =a?(c?d)=a?c， 所以a?c?b?d。

75、当n分别是10,45时，画出的哈斯图。 解：

10 ? ? 45 15? 9? ? 5 ?2 5? 3? 1? ? 1

76、在布尔代数中，证明恒等式

(a?b?)?(b?c?)?(c?a?)=(a??b)?(b??c)?(c??a) 证明：

(a?b?)?(b?c?)?(c?a?)

=(a?b?c)?(a?b?a?)?(a?c??a?)?(a?c??c)?(b??b?c)

?(b??c??c)?(b??c??a?)?(b??b?a?)=(a?b?c)?(b??c??a?)，

(a??b)?(b??c)?(c??a) =(a??b??c?)?(a??b??a)?(a??c?c?)?(a??c?a)?(b?b??c?)

?(b?b??a)?(b?c?c?)?(b?c?a)=(a?b?c)?(a??b??c?)，

故(a?b?)?(b?c?)?(c?a?)=(a??b)?(b??c)?(c??a)。 77、设是格，a,b?L，且a≤b，记 I[a,b]={x?L|a≤x≤b}

则是的子格。 证明：

?x,y?I[a,b],a≤x≤b且a≤y≤b。由定理6.1.1有a≤x?y≤b且a≤x?y≤b。从而x?y?I[a,b]且x?y?I[a,b]。

故I[a,b] 关于

?和?是封闭的，从而是的子格。

38

78、设A＝{a,b,c}，求的子格（P(A)表示A的幂集）。 解：

P(A)={?,{a},{b},{c},{a,b},{a,c},{b,c},A}。在P(A)的所有非空子集中，只要它关于?和?是封闭的，则它就是的子格。

显然和<{?},?>是的子格。

<{?,{a}},?>、<{?,{b}},?>、<{?,{c}},?>、<{?,{a,b}},?>、<{?,{a,c}},?>、<{?,{b,c}},?>、<{?,A},?>、<{?,{c},{a,c},{b,c},A }，?>等都是的子格。 79、证明：在同构意义下，4阶格只有2个。 证明：

若≤是L上的全序关系，则它一定是良序关系(因为任一有限的全序集一定是良序集)。若设L={a,b,c,d}，则L的四个元素满足：a≤b≤c≤d。

若≤不是L上的全序关系，则L中一定存在两个元素（不妨设为b,c），b≤c和c≤b都不成立。因此b不可能相等，也不可能是b和c。不妨记a=b≤b,a≤c,a≤d,b≤d,c≤d。

d? ?d

c? b? ?c

b? a ?

a?

80、设是有界格，?是A上的全序关系。若|A|＞2，则?a?A-{0,1}，a无补元。 证明：

用反证法证明。

若? a?A-{0,1}，a有补元a'。即a?a'=1，a则a= a

?c和b?c既

?c,d=b?c。故的四个元素a,b,c,d满足a≤a,b≤b,c≤c,d≤d,a

?a'=0。因为?是A上的全序关系，所以a?a'或a'?a。若a?a'，

?a'=0。若a'?a，则a= a?a'=1。无论如何，这与a?0,a?1矛盾。 ?,?>是模格??a,b,c?L，有

81、格

?(a?c))=(a?b)?(a?c)

证明：

? ?a,b,c?L，记d= a?c。所以a?d,从而

39

a?(b

?(a?c))= a?(b?d)= (a?b)?d=(a?b)?(a?c)。 ?c= (a?b)?（a?c）= a?(b?(a?c))= a?(b?c)。

?,?>是分配格， a,b,c?L。若(a?b)＝(a?c)且(a?b)＝(a?c)，则b＝c。

? ?a,b,c?L，若a?c，则c= a?c。所以

(a?b)

82、设

由吸收律、分配律和交换律有 b=b?(a

?b)＝b?(a?c)=（b?a）?（b?c） ?(b?c)=c?(a?b)= c?(a?c)＝c。

=(a?c)

83、证明：在有补分配格中，每个元素的补元一定惟一。 证明：

设是一个有补分配格。?a?L,设b和c都是a 的补元，即 a?b=1,a?c=1,a

?b=0,a?c=0。

由吸收律、分配律和交换律有 b= b?0＝b?(ac= c?0=c?(a

?c)=(b?a)?(b?c)=1?(b?c)=b?c,

?b)＝(c?a)?(c?b)=1?(c?b)=c?b。

故b=c。从而每个元素的补元是惟一的。

84、设是格，则L是分配格当且仅当?a,b,c?L，有 (a?b)?c?a?(b?c) 证明：

?设L是分配格。对?a,b,c?L，有

(a?b)?c=(a?c)?(b?c)

因为a?c?a，故(a?c)?(b?c) ?a?(b?c)。从而 (a?b)?c?a?(b?c)

?对?a,b,c?L，因为a?c?a,a?c? c,a? a?b,b?c? c,b?c? b,b? a?b,所以a?c? a?b，a?c? c，b?c?

c,b?c? a?b，

从而(a?c)?(b?c)?(a?b)?c。 又由已知有

(a?b)?c=((b?a)?c)?c?(b?(a?c))?c=((a?c)?b)?c?(a?c)?(b?c)。 故(a?b)?c=((a?c)?b)?c?(a?c)?(b?c)。

40