《离散数学》题库及答案 下载本文

的子群的充分必要条件是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