習題61. 設a=，b=a×a。確定下述集合是否為a到b的全函式或部分函式。
(1) .
(2) .
(3) .
解：（1）、全函式
（2）、不符合單值
（3）、全函式
要點： 根據全函式定義，x中每個元素x都在y中有唯一元素y與之對應。
2. 判別以下關係中那些是全函式。
(1) 。
(2) 。
(3) 且s1s2=}。
(4) .
(5) .
解： (1)
不是函式，n1=0時無定義，且(3,4),(3,5)在其中。
(2)部分函式，n1=0時無定義
(3) 且 s1 s2= }
不是函式，因為(,) ,(,)均在其中。
(4)不是函式，因為(3, 3) ,(3, 6), (3, 9)均在其中。
(5)全函式3. 在§3.1中已經定義了集合的特徵函式。請利用集合a和b的特徵函式a（x）和b（x）表示出ab，ab，a-b，以及ab對應的特徵函式。
解：（略）
4. 試確定在含n個元素的集合上可以定義多少個二元關係，其中有多少個是全函式。
解: 可以定義nn個二元關係，n！個全函式
5. 設，證明：。
證明：bf(a)-f(c)bf(a) bf(c)
x)[xa xc f(x)=b]
x)[xa-c f(x)=b]
bf(a-c)
所以f(a)-f(c)f(a-c)
7. 設f：xy，a和b是x的子集。
證明，證明：（1）y∈f(a∪b)
(x)[x∈(a∪b)∧f(x)=y]
(x)[x∈a ∧ f(x)=y]∪(x)[x∈∪b ∧ f(x)=y]
y∈f(a)∪y∈f(b)
∴f(a∪b)=f(a)∪f(b)
（2）y∈f(a∩b)
(x)[x∈(a∩b)∧f(x)=y]
(x)[x∈a∧f(x)=y]∩(x)[x∈b∧f(x)=y]
y∈f(a)∩y∈f(b)
∴f(a∩b)f(a)∩f(b)
8. 確定下例對映是否單射、滿射或雙射：
（1） f1:nr,f1(n)= n.
（2） f2:nn,f2(n)為不超過n的素數數目。
（3） f3:nnn,f3(n,n)=(n+1).
（4） f4:rr,f4(x)=x2+2x-15.
（5） f5:zz,f5(x)=1+2x3.
（6） a是集合，f6:2a2a2a2a,f6(x,y)=(xy,xy).
（7） f7:rrr,f7(x,y)=x+y. f8:rrr,f8(x,y)=xy.
解： (1)單射
(2)滿射，非單。如f(5)=f(6)=3
(3)非單,非滿。f(0,1)=f(1,0)=1,且f(x,y)=0無解。
(4)非單,非滿。
(5)單,非滿。如： 1+2x3=5無解。
(6)非單: (, ) = ( , )
非滿: (x y,x y)=(, )無解。
(7) f7: 非單,滿，如： f(1,3)=f(2,2)
f8: 非單,滿，如： f(1,3)=f(3,1)
9. 設x是有限集合，f：xx。證明：
(1)如果f是單射時，f必是雙射。
(2)如果f是滿射時，f必是雙射。
證明： (1).當f是單射時，根據單射定義，對所有任意t,s∈x,當t≠s時f(t)≠f(s),則f(x)中的元素個數與x中的元素個數相同；
又∵f:x→x，所以，f(x)是乙個滿射
∴f必是雙射。
(2)當f是滿射時，根據滿射定義及f的定義，對所有y∈x，都存在x∈x，使f(x)=y，再根據函式的單值性，對所有t,s∈x,當t≠s時，f(t)≠f(s)。
∴f必是雙射。
10. 設f是有限集x上的乙個函式，滿足xx，f2（x）=x。證明：f是雙射。
證明：設x,y是有限集x上的2個元素，如果f(x)=f(y),則x= f2(x)= f2(y)= y ，說明是單射，由上題結果知f是雙射。
11.設f:ab，g：b2a，滿足bb，g（b）=.證明：當f為滿射時g為單射。問g為單射時，f是否必是滿射？
證：1）對任意b1、b2∈b，且b1≠b2。
∵f(x)是滿射
∴。12. 設a和b都是有限集合，試確定a到b有多少個單射？多少個滿射？多少個雙射？
解：設a、b中元素個數分別為：m、n,則單射個數為：n(n-1)(n-2)…(n-m)
滿射個數為：nm,雙射個數為：n!或m!
13.設有函式f，g，h：rr，這裡f(x)=2x，g(x)=x2+x-1，h(x)=x-2。寫出fg，gfh，hhg。
解：fg=f(g(x)) =2x2+2x-2
gfh= (g(f(h(x))) = 4(x-2)2+2(x-2)-1
hhg= (h(h(g(x))) = x2+x-5
14. 設f，g，h都是集合a上的函式。如果f=g，是否必有hf=hg或fh=gh？
解：（1）∵f=g，則對於所有xa，都有f(x)=g(x),
所以，對於所有的xa，h(f(x))=h(g(x)),f(h(x))=g(h(x))即h。f=h。g
（2）∵h。f=h。g則，h(f(x))=h(g(x)),
當對於a中任意兩個不同的元素x,y都有h(x)≠h(y)時，f=g；
當a中存在兩個不同的元素x,y有h(x)=h(y)，即對於同乙個元素z,當f(z)=x ,g(z)=y，則有h(f(z))=h(g(z))，而此種情況下f≠g
綜上，當h。f=h。g時，f不一定等於g
15. 設f，g是實數集r上的函式，其中f(x)=x2+2，g(x)=2x-1。確定fg和gf是否滿射、單射或雙射？
解：f。g=(2x-1)2 +2,函式圖形為以x=1/2為對稱軸的乙個拋物線，由題，f,g都是實數上的函式，則f。g不是單射，不是滿射，也不是雙射；
g。f=2(x2+2)-1=2x2+3,函式圖形為以y座標為對稱軸的拋物線，f(x)=f(-x)，所以，g。f不是單射，不是滿射，也不是雙射。
16. 設f和g都是函式。證明：
(1) 當gf為單射時，f必為單射；
(2) 當gf為滿射時，g必為滿射；
(3) 當gf為雙射時，g為滿射，f為單射。
證明：設 f: a→b, g: b→c。
（1）（反證法）設f不是單射，存在x1≠x2∈a,且f(x1)=f(x2)，
即：gf(x1)= g(f(x1))= g(f(x2))= gf(x2),與gf為單射矛盾。因此，f必為單射。
（2）對於任意z∈c，由於gf為滿射，那麼存在x∈a使得gf(x)=z，因此存在y=f(x)∈b,使得z=g(y)，因此g是滿射。
（3）由（1）、（2）可得證。
17. 設a=。
（1）找出乙個a上的非單位置換的置換，計算=2， 2=3，以及-1。
（2）若a上置換滿足=（1），稱為冪么置換，求出a上的全部冪么置換。
解：(提示，按照定義求解即可)
（1）任定義為：(2,1,3,4)
（2）（略）
18. 計算有限集合x可以定義出多少個函式f，使得f=f-1。
解：（略）
19.證明下列集合a和b等勢。
1) a=(0,1),b=(-2,2).
2) a=(-,+),b=(0,+).
3) a=(0,1),b=(，).
4) a=n, b= .
證明：（思路：想辦法構造乙個雙射函式即可）
（1）f(x)=2tan()
(2）（略）
(3)f(x)=
(4)(略)
20.設a～b，c～d。證明：ac～bd。
證明：（略）
21.證明：非空有限集a與可數集b的笛卡爾積ab也是可數集。
證明：非空有限集a與可數集b的笛卡爾積a×b也是可數集。
證明：設a=
令bi = (i≤n),則
a×b因為b為可數集，所以bi為可數集。a×b為有限個可數集的並集。下面用歸納法證明有限個(m個)可數集的並集為可數集。
設cm=
當m=2時，
構造雙射f:n→c1∪c2,
n 1 2 3 4 5 6 … n-1 n …
f(n) c11 c21 c12 c22 c13 c23 … c1(n/2) c2(n/2) …
所以2個可數集的並集為可數集。
假設m=k-1(k≥3)時結論成立，即k-1個可數集的並集為可數集，記為d。
則m=k時，可以構造類似的雙射g:n→d∪ck,所以為可數集。因而有限個可數集的並集為可數集。所以a×b是可數集。
補充：1. 設和是兩個有限集合，它們的元數都是，則是單射的充分必要條件是為滿射
證必要性，當是單射時，的元數是，而的元數也是，故，因此是滿射。
充分性，若為滿射時，有，則的元數為，的元數也是，個原象對應個象，即不同元素對應不同的象，因此是到的單射。
2．設為實數集，試證明和都是滿射，而不是單射。
證對於任意，可以使成立的有無數對，且，也就是說值域中每個元素都有無數原象在中，所以是滿射，而不是單射。
離散數學補充習題
一 填空題 每空1分，本大題共15分 1 設，請在下列每對集合中填入適當的符號 122 設，n為自然數集，若，則是 射的，若，則是射的。3 設圖g v e 中有7個結點，各結點的次數分別為2，4，4，6，5，5，2，則g中有條邊，根據 4 兩個重言式的析取是 乙個重言式和乙個矛盾式的合取是 5 設個...
學習離散數學總結
學習離散數學的心得體會 姓名 學號 1 班級 計算機 離散數學，對絕大多數學生來說應該都會是一門十分困難的課程，當然也包括我在內。通過這一學期的學習，我對這門課程有一些初步的了解，現在的心情和當初也很不相同。在還沒有接觸的時候，看見課本就想退縮，心想 這是什麼課程啊，這叫數學嗎，這些符號都是之前沒有...
離散數學心得體會 離散數學學習心得
離散數學心得體會 離散數學，對絕大多數學生來說是一門十分困難的課程，當然也包括我在內，而當初選這門課是想挑戰一下自己。通過這一學期的學習，我對這門課程有一些初步的了解，現在的心情和當初也很不相同。在還沒有接觸的時候，看見課本就想退縮，心想 這是什麼課程啊，這叫數學嗎，這些符號都是之前沒有見過的呢！但...