《离散数学》题库及答案

的子群的充分必要条件是HK=KH。 证明：

?HK是G的子群。?c?HK，则c?HK，故存在a?H,b?K ,使得c

-1

-1

=a·b。因为c=（a·b）=b·a。

-1-1-1

因为H和K都是G 的子群，所以a

-1

-1

-1

?H,b?K ，即c?KH。从而HK?KH。 ?c?KH，则存在a?H,b?K ,

-1

-1

使得c=b·a。因为c=（a·b）。因为H和K都是G 的子群，所以aHK是G的子群，所以c=（a·b）故HK=KH。

-1

-1

-1

-1

?H,b?K ，即a

-1

-1

·b

-1

?HK。因为

?HK。从而KH?HK。

HK，有a1,a2

?HK=KH。对

?c，d

??H,b1,b2

?K ,使得c=a1·b1 ,d=a2·b2。则

c·d=( a1·b1)·(a2·b2)=(( a1·b1)·a2)·b2=( a1·(b1·a2))·b2。因为b1·a2?KH=KH，所以存在a3?H,b3?K ,使得b1·a2 =a3·b3。从而c·d=( a1·（b1·a2）·b2=(a1·（a3·b3）)·b2=(a1·a3)·(b3·b2)。因为H和K都是G的子群，故a1·a3?H, b3·b2?K。从而c·d?HK。

又c=(a1·b1)=b1·a1。因为H和K都是G的子群，故a以c

-1

-1

-1

-1

-1

-11

?H, b?K。从而c?KH。因为HK=KH，所

-1

-1

1

?HK。

综上所述，HK是G的子群。

65、设H和K都 是G的不变子群。证明：HK也是G 的不变子群。 证明：

先证HK是G 的子群。 对?a?HK，有hh·k·h

-1

?H，k?K，使得a=h·k。因为a=h·k=(h·k·h)·h，且K是G 的不变子群，所以

-1

?K。故a?KH。从而HK?KH。

同理可证，KH?HK。

故HK=KH。从而HK是G的子群。 下证HK是G的不变子群。

?HK，有h?H，k?K，使得b=h·k。故a·b·a=a·(h·k)·a=(a·h·a)·(a·k·a)。因为H和K都是G的不变子群，所以a·h·a?H且a·k·a?K。从而a·b·a?HK。故HK是G 的不变

对?a?G，b

-1

-1

-1

-1

-1

-1

-1

子群。

66、设为群，a,b,c?G。若a*b=c*b*a,a*c=c*a,b*c=c*b，且a,b的阶分别为m,n，则c的阶整除m与n的最大公因子(m,n)。 证明：

设c的阶为k。在a*b=c*b*a两边同时右乘b

a*b=(c*b*a)*b=(c*b)*a*b=(c*b)*a*b

32n?2n?3nn?1n?1，再由a*b=c*b*a得

n?2=(c*b)*(a*b)*b

2n?3n?2=(c*b)*(c*b*a)*b

2

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

n=(c*b)*(c*b*a)*b

n?3

再由b*c=c*b及b 的阶为n得

a=a*b= (c*b)*a=(c*b)*a=c*a, 所以c=e。故由元素阶的定义有k|n。

由a*b=c*b*a,a*c=c*a,b*c=c*b得a*b=b*a*c，两边同时左乘aa

mm?1nnnnnn，再由a*b=b*a*c得

*b=a

m?1*(b*a*c)= a

m?2* (a*b)*(a*c)= a

33

m?2*(b*a*c)*(a*c)

= a= a

m?2m?3*b*(a*c)= a

32m?3*(a*b)*(a*c)= a

m2m?3*(b*a*c)*(a*c)

2*b*(a*c)=?=b*(a*c),

再由a*c=c*a及a 的阶为m得 b= a*b= b*(a*c)

mmm=b* a * c=b*c,

mmm 所以c=e。故由元素阶的定义有k|m。

由此可见，k是m和n的公因子，从而能整除m和n的最大公因子(m,n)。

（格与布尔代数）

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?证明：

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

?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，a?a???a?a，a?a?a???a。

1

2

n

k

k

1

2

n

因为a1?a2???an= a1?a2???an，且?是L上的偏序关系，故ak=a1?a2???an。从而a1=a2=?=an。

72、在布尔代数中，证明恒等式(ac)?(a?证明：

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

??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)。

((ac)?(a?

34

73、在布尔代数中，证明恒等式(ab)?(a?证明：

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

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

(ab)?(a?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时，画出的哈斯图。 解：

?? 5 ?2 5? 3? 1? ? 1

15 9

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

(a?证明：

(a? 10

??? 45

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

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

????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)。

=(abc)?(ab

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] 关于

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

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

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

35

的，则它就是的子格。

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

<{?,{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既不可能相等，也不可能是b和c。不妨记a=b≤a,b≤b,c≤c,d≤d,a≤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'，则a= a81、格

?c

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

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

?a'=0。若a'?a，则a= a?a'=1。无论如何，这与a?0,a?1矛盾。 ?(a?c))=(a?b)?(a?c)

?,?>是模格??a,b,c?L，有

a?(b

证明：

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

a?(b

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

?

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

(a?b)

82、设

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

36