文档库

最新最全的文档下载
当前位置:文档库 > 离散习题(附答案) (5)

离散习题(附答案) (5)

习题 5.1

1.设A=?a,b,c?,B=?1,2,3?,试说明下列A到B二元关系,哪些能构成A到B的函数?

⑴f1=?,,,?

⑵f2=?,,?

⑶f3=?,?

⑷f4=?,,,?

⑸f5=?,,?

解:⑴不能构成函数。因为∈f1且∈f1

⑵能构成函数

⑶不能构成函数。因为dom f3≠A

⑷不能构成函数。因为∈f4且∈f4

⑸能构成函数。

2.试说明下列A上的二元关系,哪些能构成A到A的函数?

⑴A=N(N为自然数集合),f1=?| a∈A∧b∈A∧a+b<10?

⑵A=R(R为实数集合),f2=?| a∈A∧b∈A∧b=a2?

⑶A=R(R为实数集合),f3=?| a∈A∧b∈A∧b2=a?

⑷A=N(N为自然数集合),f4=?| a∈A∧b∈A∧b为小于a的素数的个数?

⑸A=Z(Z为整数集合),f5=?| a∈A∧b∈A∧b=|2a|+1?

解:⑴不能构成函数。由于1+1<10且1+2<10,所以<1,1>∈f1且<1,2>∈f1。

⑵能构成函数。

⑶不能构成函数。由于12=1且(-1)2=1,所以<1,1>∈f3且<1,-1>∈f3。

⑷能构成函数。

⑸能构成函数。

3. 回答下列问题。

⑴设A=?a,b?,B=?1,2,3?。求B A,验证|B A|= |B||A|。

⑵设A=?a,b?,B=?1,2?。求B A×A,验证|B A×A|=|B||A|×|A|。

解:⑴f0=?,?

f1=?,?

f2=?,?

f3=?,?

f4=?,?

f5=?,?

f6=?,?

f7=?,?

f8=?,?

B A=?f0,f1,f2,f3,f4,f5,f6,f7,f8?

|B A|=9=32= |B||A|

⑵ A ×A =?,,,?

f 0=?<,1>,<,1>,<,1>,<,1>?

f 1=?<,1>,<,1>,<,1>,<,2>?

f 2=?<,1>,<,1>,<,2>,<,1>?

f 3=?<,1>,<,1>,<,2>,<,2>?

f 4=?<,1>,<,2>,<,1>,<,1>?

f 5=?<,1>,<,2>,<,1>,<,2>?

f 6=?<,1>,<,2>,<,2>,<,1>?

f 7=?<,1>,<,2>,<,2>,<,2>?

f 8=?<,2>,<,1>,<,1>,<,1>?

f 9=?<,2>,<,1>,<,1>,<,2>?

f 10=?<,2>,<,1>,<,2>,<,1>?

f 11=?<,2>,<,1>,<,2>,<,2>?

f 12=?<,2>,<,2>,<,1>,<,1>?

f 13=?<,2>,<,2>,<,1>,<,2>?

f 14=?<,2>,<,2>,<,2>,<,1>?

f 15=?<,2>,<,2>,<,2>,<,2>?

B A ×A =?f 0, f 1, f 2, f 3, f 4, f 5, f 6, f 7,f 8,f 9 f 10, f 11, f 12, f 13, f 14, f 15?

|B A ×A |=16=24=|B ||A |×|A |

4.下列函数中,哪些是单射?哪些是满射?哪些是双射?为什么?

⑴ f :N →N ,f (x )= x 2+1

⑵ f :Z →Z , f (x )=(x mod 3)(函数值为x 除以3的余数)

⑶ f :N →N , 为偶数若为奇数若x x x f ???=0

1

)( ⑷ f :N →?0,1?,为偶数若为奇数若x x x f ??

?=01

)( ⑸ f :Z +→R ,f (x )=3x

⑹ f :R →R ,f (x )=x 3

解:⑴是单射,不是满射,不是双射。

当x ,y ∈A ,x ≠y ,x 2≠y 2,x 2+1≠y 2+1,f (x )≠f (y )。所以f :N →N 是单射。

因为?x ∈N ,f (x )≠0∈N 。所以f :N →N 不是满射。

因为不是满射,所以不是双射。

⑵不是单射,不是满射,不是双射。

因为6≠9,而f (6)=(6 mod 3)=0=(9 mod 3)=f (9)。所以f :Z →Z 不是单射。

因为?x ∈Z ,f (x )≠3∈Z 。所以f :Z →Z 不是满射。

因为不是单射且不是满射,所以不是双射。

⑶不是单射,不是满射,不是双射。

因为1≠3,而f (1)=f (3)。所以f :N →N 不是单射。

因为?x∈Z,f(x)≠2∈N。所以f:N→N不是满射。

因为不是单射和不是满射,所以不是双射。

⑷不是单射,是满射,不是双射。

因为1≠3,而f(1)=1=f(3)。所以f:N→?0,1?不是单射。

显然,f:N→?0,1?是满射。

因为不是满射,所以不是双射。

⑸是单射,不是满射,不是双射。

f:Z+→R,f(x)=3x是单调递增函数,所以是单射。

因为?x∈Z+,f(x)≠0∈R。所以f:Z+→R不是满射。

因为不是满射,所以不是双射。

⑹是单射,是满射,是双射。

f:R→R,f(x)=x3是单调递增函数,所以是单射。

因为?y∈R,有x=3y∈R,使f(x)= f(3y)=(3y)3=y。所以f:R→R,f(x)=x3是满射。

因为是单射和满射,所以是双射。

5.设A=?1,2,3,4?,A上的等价关系R为:

R=?<1,4>,<4,1>,<2,3>,<3,2>?∪I A

求自然映射f:A→A/R

解:A/R=??1,4?,?2,3??

f=?<1,?1,4?>,<2,?2,3?>,<3,?2,3?>,<4,?1,4?>?

6.设f: Z×Z→Z(Z为整数集合),f(x,y)= x+y;g: Z×Z→Z,g(x,y)= x×y。试证明f和g是满射函数,但不是单射函数。

证明:?x∈Z,<0,x>∈Z×Z,f (0,x)= 0+x=x,所以f: Z×Z→Z,f(x,y)=x+y是满射。

<1,x>∈Z×Z,f (1,x)= 1×x=x,所以g: Z×Z→Z,g(x,y)=x×y是满射。

对于<1,2>∈Z×Z,<2,1>∈Z×Z,f(1,2)=3=f(2,1),但<1,2>≠<2,1>,所以f: Z×Z→Z,f(x,y)= x +y不是单射函数。

对于<3,2>∈Z×Z,<2,3>∈Z×Z,g(3,2)=6= g(2,3),但<3,2>≠<2,3>,所以g: Z×Z→Z,g(x,y)= x×y不是单射函数。

7.设A和B是有限集合,|A|=n,|B|=m。

⑴有多少个不同的单射函数f:A→B。

解:要使f:A→B是单射函数,必须n≤m,因此,当n>m时,无A到B的单射函数。当n≤m时,共有n m P=n(n-1)…(n-m+1)

⑵有多少个不同的双射函数f:A→B。

解:要使f:A→B是双射函数,必须n=m,此时共有m!个双射函数。请参看习题5.2的第6题。

8.设f:A→B,C?A,证明f(A)-f(C)?f(A-C)

证明:f(x)∈f(A)-f(C)?f(x)∈f(A)∧f(x)?f(C)?x∈A∧x?C?x∈A-C? f(A-C)

所以, f(A)-f(C)?f(A-C)

9.设A=?a1,a2,…,a n?,试证明任何从A到A的函数,如果它是单射,则它必是满射。反之亦真。

证明:设f:A→A是单射,下证f是满射。

反证法,设f不是满射,至少有一个元素不是f的像,设这个元素为a j,则ran f?A-?a j?,所以ran f?A,从而有|ran f|<|A|,与f是单射矛盾。

设f:A→A是满射,下证f是单射。

反证法,设f不是单射,?a i∈A,a j∈A,使f(a i)=f(a j),而a i≠a j,构造函数

f1:A-?a i?→A,f1(x)=f(x)

因为f:A→A是满射,所以f1:A-?a i?→A也是满射。故有|A-?a i?|≥|A|。又因为a i∈A,A-?a i??A,|A-?a i?|<|A|,所以,|A|≤|A-?a i?|<|A|,即|A|<|A|,矛盾。

10.设f:A→B,C?A,D?A,试证明:

⑴f(C∪D)= f(C)∪f(D)

⑵f(C∩D)?f(C)∩f(D)

证明:⑴f(x)∈f(C∪D)?x∈C∪D?x∈C∨x∈D?f(x)∈f(C)∨f(x)∈f(D)

?f(x)∈f(C)∪f(D)

即f(C∪D)= f(C)∪f(D)

⑵f(x)∈f(C∩D)?x∈C∩D?x∈C∧x∈D?f(x)∈f(C)∧f(x)∈f(D)?f(x)∈f(C)∩f(D)

即f(C∩D)?f(C)∩f(D)

11.设f:A→B。

g:B→P(A),定义为:对于b∈B,g(b)= ?x|x∈A∧f(x)=b?。

证明:如果f是A到B的满射,则g是B到P(A)的单射。

证明:以下证明g:B→P(A)的单射。g(b)=?x|x∈A∧f(x)=b?。

设x1∈B,x2∈B且x1≠x2,因为f是A到B的满射,?y1∈A,使f(y1)=x1,?y2∈A,使f(y2)=x2。因为x1≠x2,所以f(y1)≠f(y2),又因为f是函数,故有y1≠y2。由g的定义有,y1∈g(x1),y2∈g(x2)。

因为f(y2)=x2≠x1,所以y2?g(x1),故有g(x2)?g(x1),即g(x1)≠g(x2)。

这就证明了g是B到P(A)的单射。

12.设是偏序集,?x∈A,令f(a)= ?x|x∈A∧x?a?,证明:

⑴f:A→P(A) 是单射。

⑵若a?b时,必有f(a)?f(b)

证明:⑴?a∈A,?b∈A且a≠b

当a?b时,因为a≠b,则无b?a,b?f(a)。又由偏序关系的自反性知b?b,从而b∈f(b)。f(a)

≠f(b)

当b?a时,类似的可以证明f(a)≠f(b)

⑵设a?b,x∈f(a)?x∈A∧x?a,由a?b和偏序关系的传递性?x∈A∧x?b?x∈f(b)。即

f(a)?f(b)。

习题 5.2

1.设X=?x1,x2, x3, x4?,Y=?y1,y2, y3, y4, y5?,Z=?z1,z2, z3?

f:X→Y,定义为f=?,,,?

g:Y→Z,定义为g=?,,,,?

试求函数g在函数f左边的复合关系g f,验证复合关系g f是X到Z的函数。

解:g f=?,,,?

mod g f=?x1,x2,x3,x4?=X。当x1= x2时,f(x1)=f(x2)

g f:X→Z

2.设f,g,h∈R R,且f(x) =x2-2,g(x) =x+4,h(x) =x3-1

⑴试求g f和f g

⑵g f和f g是单射?满射?双射?

⑶f,g,h中哪些有反函数?若有,求出反函数。

解:⑴g f(x)= x2+2

f g(x)=x2+8x+14

⑵g f不是单射,不是满射,不是双射。

f g不是单射,不是满射,不是双射。

⑶f不是单射,不是满射,不是双射。无反函数。

g是单射,是满射,是双射。有反函数。g-1(x)= x-4

h是单射,是满射,是双射。有反函数。h-1(x)=31+

x

3.设f:A→B,g:B→C,g和f的复合函数g f:A→C,试证明:

⑴如果g f是单射,那么f是单射。

⑵如果g f是满射,那么g是满射。

⑶如果g f是双射,那么f是单射,g是满射。

证明:⑴?x1∈B,?x2∈B且f(x1)=f(x2),因为g是函数,g(f(x1))=g(f(x2))?g f(x1)=g f(x2),由于g f是单射,所以x1=x2,f是单射。

⑵?c∈C,因为g f是满射,存在a∈A,使g f(a)=c,又因为f:A→B是函数,令b=f(a),g(b)=g(f(a ))=g f(a)=c,g是满射。

⑶设g f是双射,由⑴知f是单射,由⑵知g是满射。

4.设f:A→B,f是双射,A′?A,B′?B,试证明

⑴f (f -1(B′))?B′

⑵利用f是满射,证明f (f -1(B′))=B′

⑶A′?f -1(f (A′))

⑷利用f是单射,证明A′=f -1(f (A′))

证明:⑴设f(x)∈f (f -1(B′))?x∈f -1(B′)??y∈B′使x=f -1(y)∈f -1(B′)? f(x)=y∈B′

所以,f (f -1(B′))?B′

⑵ ?y ∈B ′,因为f :A →B 是满射,?x ∈A 使f (x )=y ? x =f -1(y )?x ∈f -1(B ′)

?y =f (x )∈f (f -1(B ′))?B ′? f (f -1(B ′))

由⑴有 f (f -1(B ′))?B ′

所以,f (f -1(B ′))=B ′

⑶ ?x ∈A ′,因为f :A →B ,所以?y ∈B 使f (x )=y ,而y =f (x )∈f (A ′)

?x =f -1(y )∈f -1(f (A ′)),即x ∈f -1(f (A ′))?A ′?f -1(f (A ′))

⑷ ?x ∈f -1(f (A ′)),?y ∈f (A ′)使x =f -1(y ),从而y =f (x );再由?y ∈f (A ′),?x ′∈A ′,使y =f (x ′)。因为f :A →B 是单射,所以,x =x ′∈A ′,故有f -1(f (A ′))?A ′

又由⑶有A ′?f -1(f (A ′))

这就证明了A ′=f -1(f (A ′))

5.设f :A →B ,g :B →A ,证明:

g f =I A 且f g =I B 当且仅当g =f --1且f =g -1

证明:?设g =f --1且f =g -1,下证g f =I A 且f g =I B

因为g :B →A ,f --1:B →A ,g =f --1,所以?y ∈B ,g (y )=f -1(y )。令g (y )=f -1(y )=x ,则g (y )=x ,y =f (x )。 又由f =g -1? f :A →B ,g -1:A →B ,且?x ∈A ,f (x )=g -1(x )。由此y =f (x )=g -1(x )?g (y )=x

所以,g f (x )=g (f (x ))=g (y )=x =I A (x ),f g (y )=f (g (y ))=f (x )=y =I B (x )

显然,g f :A →A ,I A :A →A ;f g :B →B ,I B :B →B

这就证明了g f =I A 且f g =I B

?设g f =I A 且f g =I B ,下证g =f --1且f =g -1

因为恒等函数I A 是双射,所以g f :A →A 是双射,由习题5.2的第3题⑶,f 是单射,g 是满射。

同样,恒等函数I B 是双射,所以f g :B →B 是双射,由习题5.2的第3题⑶,g 是单射,f 是满射。

所以,f 和g 都是双射函数,他们的反函数都存在。

g :B →A ,f --1:B →A

?y ∈B ,由f --1:B →A ,令f --1(y )=x ∈A ?f (x )=y

g (y )=g (f (x ))=g f (x )=I A (x )=x = f --1(y ),显然,g :B →A ,f --1:B →A

所以,g =f -1

类似的可以证明,f =g -1

6.设A =?a 1,a 2, …, a n ?,函数f :A →A 是双射。称双射f 为集合A 上的置换,n 称为置换阶,常记为:

???

? ??=)()()(2121n n a f a f a f a a a f 由于f 是双射,f (a 1),f (a 2),…,f (a n )都是A 的元素且互不相同。因此f (a 1),f (a 2),…,f (a n )必为a 1,a 2, …, a n 的一个排列。而a 1,a 2, …, a n 的排列总数是n !个,因此集合A 上的n 阶置换的数目是n !个。即A 到A 是双射函数有n !个。

设A =?1,2,3?,集合A 上应有3!=6个3阶置换。写出集合A 上的所有3阶置换。

解:????

??321321 ???? ??231321 ???? ??312321 ???? ??132321 ???? ??213321 ???? ??123321

7.如果某人营造了n 个鸽舍,养了多于n 只鸽子,则必有一个鸽舍住有2只或2只以上的鸽子。这就是鸽舍原理。

用数学语言将这个原理抽象为:设A ,B 是有限集合,f 是A 到B 的函数,如果|A |>|B |,则A 中至少有两个元素,其函数值相等。

更一般的情况是:当鸽舍为n 个,鸽子数大于n ×m 只时,必有一个鸽舍住有m 十1个或多于m +1个鸽子。

用数学语言抽象为:设A ,B 是有限集合,f 是A 到B 的函数,如果|A |>n ×m ,|B |=n ,则在A 中至少有m +1个元素,其函数值相等。

例如,有3个鸽舍,13只鸽子。A 是鸽子构成的集合,|A |=13>3×4。B 是鸽舍构成的集合,|B |=3。则必有一个鸽舍,住有4+1=5个或5个以上鸽子。

利用鸽舍原理解下列各题:

⑴任意n +1个正整数,其中必有两个数之差能被n 整除。

⑵在边长为1的正三角形内,任取7个点,证明其中必有3个点联成的小三角形的面积不超过12

3。 解:⑴由于任意正整数被n 除后,其余数只能是0,1,…,n -1共n 种,所以在n +1个正整数中,必有两个数被n 除后余数相同,这两个数之差必能被n 整除。

⑵ 如图5.6所示,△ABC 是边长为1的正三角形,点O 是△ABC 的重心,连接OA 、OB ,

OC ,则将△ABC 分为面积相等的3个小三角形,每个小三角形的面积都为:31×21×23=12

3。

离散习题(附答案) (5)

把小三角形作为“鸽舍”,点作为“鸽子”,则有7只鸽子,3个鸽舍。而INT(7/3)=2,由鸽舍原理,7个点中至少有3个点在同一个小三角形中,由这3个点联成的三角形的面积必小于小三角形的面积12

3。 习题 5.3

1.证明区间(0,1)和区间[0,1]等势。

证明:设f :(0,1)→[0,1],f (x )=x 是单射函数。|(0,1)|≤|[0,1]|。

又设g :[0,1]→(0,1),g (x )=4

12 x 是单射函数。|[0,1]|≤|(0,1)|。故|(0,1)|=| [0,1]|。 2.设A ,B ,C ,D 是任意集合,A ~B ,C ~D ,证明A ×C ~ B ×D

证明:因为A ~B ,所以,存在f :A →B 是双射函数。

因为C ~D ,所以,存在g :C →D 是双射函数。

令h :A ×C →B ×D ,定义为:h ()=

以下证明h 是单射函数:设,则有下列3种情况:

⑴a 1≠a 2且c 1=c 2

因为,f :A →B 是单射函数,所以,f (a 1)≠f (a 2),故< f (a 1), g (c 1)>≠,即h 是单射函数。

⑵a 1=a 2且c 1≠c 2

类似⑴可以证明h 是单射函数。

⑶a 1≠a 2,且c 1≠c 2,

类似⑴和⑵可以证明h 是单射函数。

综上所述,h 是单射函数。

以下证明h 是满射函数:?∈B ×D ,则b ∈B ,d ∈D

因为,f :A →B 是满射函数,所以,?a ∈A 是f (a )=b 。

因为,g :C →D 是满射函数,所以,?c ∈C 是g (c )=d 。

∈A ×C 使h ()==∈B ×D 。

h 是满射函数。

故h :A ×C →B ×D 是双射函数。A ×C ~ B ×D

3.设N 是自然数集合,A =?x |x =n 5∧n ∈N ?,证明A 是可数集。

证明:令a i =i 5,则集合A 可用列举法表示为:

A =?05,15,25,35,… ?=? a 0,a 1,… ?

A 是能用自然数编号的无限集,根据定理5.3.5,A 是可数集。

4.设Q 是有理数集合,证明叉乘积Q ×Q 是可数集。

证明:由例5.13知Q 是可数集,Q 的元素能用自然数编号。设Q=? a 0,a 1,a 2,…?

Q ×Q=? ,,,,…?∪

? ,,,,…?∪

? ,,,,…?∪

? ,,,,…?∪

即Q ×Q 可以表示为可数个可数集的并集。由定理5.3.8知,Q ×Q 是可数集。

5.设N 是自然数集合,证明|P (N )|=?。

证明:

⑴作函数h :P (N )→[0,1],h 如下定义:?S ∈P (N )

h (S )=0.x 0x 1x 2x 3…(2进制小数),其中

S

i S i x i ?∈???=01

例如,h (?)=0, h (N )=0.1111…,h (?1,4,5?)=0.010011。

显然,h 是单射函数。|P (N )|≤|[0,1]|

⑵作函数k :[0,1]→P (N ),k 如下定义:?x =0.x 0x 1x 2x 3…∈[0,1] (x 是2进制小数,如果x 没有唯一表示,可任意选择其中之一)

k (x )= ?i |x i =1?

例如,k (0)=?, k (1)= k (0.1111…)=N ,h (0.010011)= ?1,4,5?。

显然,k 是单射函数。|[0,1]|≤|P (N )|

由⑴和⑵得|P (N )|=|[0,1]|

6.如果A 是不可数无限集,B 是A 的可数子集,证明(A -B ) ~ A 。

证明:显然A -B 是无限集,B 是可数集。因为B 是A 的子集,所以,A =(A -B )∪B ,从而,|A |=|(A -B )∪B |,由习题5.3的第7题的结论得,|A |=|(A -B )∪B |=|A -B |,即(A -B ) ~ A 。

7.如果A 是任意无限集,M 是一个可数集,证明 (A ∪M ) ~ A

证明:如果A 是任意可数无限集,由定理5.3.8知,可数集的并集是可数集。A ∪M 是可数集。得|A ∪M | =|A |,即(A ∪M ) ~ A

如果A 是任意不可数无限集,由本习题第8题⑴和定义知:

|A ∪M | =|A |+|M | =?+?0=?=|A |,即(A ∪M ) ~ A

8.设A ,B ,D 是任意集合,A ∩B =?,A ∩D =B ∩D =?,|A |=a ,|B |=b ,|D |=d 。定义

a +

b =|A ∪B |,a ×b =|A ×B |

证明

⑴ ?+?0=?。

⑵ 如果a ≤b ,则a +d ≤b +d 。

⑶ 如果a ≤b ,则a ×d ≤b ×d 。

证明:⑴令A =?x | x ∈R ∧x ≥1 ?,B =?2

1+n | n ∈N ?,显然,|A |=?,|B |=?0,A ∩B =?,A ∪B ? R 。作函数f :A ∪B →R ,?x ∈A ∪B ,f (x )=x 。显然,f 是A ∪B 到R 的单射函数。所以|A ∪B |≤|R |=?。即|A ∪B |≤?。

又因为A ?A ∪B ,所以|A |≤|A ∪B |,即?≤|A ∪B |。

所以,|A ∪B |=?。再由本题的定义有?+?0=|A |+|B |=|A ∪B |=?。

⑵ 因为a ≤b ,即|A |≤|B |,有一单射函数f :A →B ;设g :D →D ,g (x )=x ,显然,g 是D 到D 的单射函数。定义h :A ∪D →B ∪D 为:

h (x )=时

当时当D x A x x g x f ∈∈???)()

( ?y ∈B ∪D ,因为B ∩D =?,则y ∈B 且y ?D 或y ∈D 且y ?B 。

当y ∈B 时,y ?D ,由于f :A →B 是单射函数和A ∩D =?,所以A 中必有唯一的x 使h (x )=f (x )=y 。 当y ∈D 时,y ?B ,由于g :D →D ,g (x )=x ,是单射函数和A ∩D =?,所以D 中必有唯一的y 使h (y )= g (y )=y 。

所以,h :A ∪D →B ∪D 是单射函数。故|A ∪D |≤|B ∪D |,即a +d ≤b +d

⑶ 因为a ≤b ,即|A |≤|B |,有一单射函数f :A →B ;设g :D →D ,g (x )=x ,显然,g 是D 到D 的单射函数。定义h :A ×D →B ×D 为:h ()=

?∈A ×D 且?∈A ×D ,,从而

①x≠a,y=b,由于f:A→B是单射函数,所以f(x)≠f(a),h()== h(),所以h:A×D→B×D是单射函数。

②x=a,y≠b,由于g是D到D的单射函数,所以g(y)≠g(b),h()== h(),所以h:A×D→B×D是单射函数。

③x≠a,y≠b,可类似⑴和⑵证明。