离散数学及其应用-第2版 第3-5章部分习题解答

第3章部分习题解答1.列出下列集合的元素.{x|x是小于5的非负整数}{x|x是大于0的偶数}{x|（x是整数）（2x10）}(4){x|xN˄t(t{2,3}˄x=2t)}(5){x|xR˄x2-1=0˄x>3}解：（1）{0,1,2,3,4}（2）{2,4,6，…，}（3）{3,4,5,6,7,8,9}（4）{4,6}（5）2.判断下列集合是否相等。{1,2,1,3,1,2},{2,3,1}{{1}},{1,{1}}

,{}解：（1）相等（2）不相等（3）不相等3.假定A,B,和C是集合，若AB且BC.

证明AC.证明：对任意xA，因为AB，有xB，又因为BC，有xC，所有AC.4.判定下列各题的正确与错误：（1）a{{a}}；（2）{a}{a，b，c}；（3）{}；（4）{a，b，c}；(5)；（6）；（7）{{a}，1，3，4}{{a}，3，4，1}；（8）{a，b}{a，b，c，{a，b}}；（9）{a，b}{a，b，{a，b}}；（10）{a，b}{a，b，{{a，b}}}。解：正确：2、3、4、6、8、9错误：1、5、7、105.设E={a,b,c,d,e},A={a,d},B={a,b,e}和C={b,d}.试求出下列的集合：(1)(2)(3)(4)（AC)B(5)ABC解：（1）{d}（2）{a,e}(3){b,c,d,e}(4){b}(5){e}6.给定自然数集合N的下列子集：A={1,2,7,8}B={i|ii<50}C={i|i可被3整除且0i30}D={i|i=2k,kI,0<k<6}试求出下列集合：(1)A(B(CD))(2)A(B(CD))(3)B-(AC)(4)(~AB)D（5）AB解：(1){0,1,2,3,4,5,6,7,8,9,10,12,15,18,,,30}(2){(3){4,5}(4){0,2,3,4,5,6,8,10}(5){0,3,4,5,6,8}7.给定正整数集合的下列子集：A={n|n<12}B={n|n8}C={n|n=2k,k}D={n|n=3k,k}F={n|n=2k-1,k}试用集合A,B,C,D和F表达下列集合：(1){2,4,6,8}(2){3,6,9}(3){10}(4){n|n是偶数，n>10}(5){n|n是正偶数且n10，或n是正奇数且n>=9}解：（1）BÇC(2)AD(3)(A-B)C(4)C-A（5）（CA）（F-B）8.设A,B和C是全集E的子集，下列关系是否成立？(AB)~(BC)A~B解：成立(AB)~(BC)A~B9.设A,B是全集E的子集，证明下列恒等式：(1)(AB)(A~B)=A(2)B~((~AB)A)=E（3）（A~B）（~AB）=（AB）（~A~B）。证明：（1）(AB)(A~B)=A（B~B）=AE=A(2)B~((~AB)A))=B(~(~AB)~A)=B((A~B)~A)=B((A~A)（~B~A）)=B（~B~A）=E（3）证明：左式=A∪∼B∩∼A=A∩∼A=[F（AB）][（~A~B）]=右式10.求下列集合的幂集:(1){a,b,c}(2){1,{2,3}}(3){{1,{2,3}}}(4){,{}}(5){{1,2},{2,1,1},{2,1,1,2}}解答：P({a,b,c})={，{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}P({1,{2,3}})={，{1},{{2,3}},{1,{2,3}}}P({{1,{2,3}}})={，{{1,{2,3}}}}P({,{}})={，{},{{}},{,{}}}P({{1,2},{2,1,1},{2,1,1,2}})=P({{1,2}})={，{{1,2}}}11.分别用空集构成集合A和B，使得AB和AB。解：（答案不唯一）A={},B={，{}}12.设A，B是两个集合，A={1，2，3}，B={1，2}，请计算P（A）–P（B）。解：P(A)-P(B)={{1,3},{1,2,3},{2,3},{3}}13.化简下列集合表达式：(清华98,99)（1）（（AB）B）-(AB)（2）（AB）(A-B)（3）（（ABC）-(BC)）A（4)(ABC)(~ABC)(AB~C)解答：(2)（AB）(A-B)=（AB）(A~B)=A（4）(ABC)(~ABC)(AB~C)=((A~A)(BC))((AB)(C~C))=(BC)(AB)=B(CA)14.设A,B,C,D是任意集合，判断下面的命题的真假，如果为真，给出证明；如果为假，请举出一个反例。（1）AB˄BCAC（清华P10030）（2）A≠B˄B≠CA≠C（清华P10030）（3）AB˄CDACBD（清华P10043）（4）AB˄CDACBD（清华P10043）（5）AB˄BCAC（清华P10030）解：（1）真（2）假如：A={1,2}B={1,2，3}C={1,2}（3）真（4）假如：A={1,2}B={1,2，3}C={3,4}D={2,3,4}（5）假A={1}B={{1},1}，C={{1},1,2}15.设A,B是任意集合，证明：（1）（A-B）（B-A）=（AB）-（AB）（2）A（B~A）=BA证明：（1）左边=AA∩∼BA∪B∩（2）左边=A∩B∪∼A=16.设A,B,C是任意集合，证明：CA˄CBCAB（清华10037）证:CA˄CBx((x∈Cx∈A)˄(x∈Cx∈B))x(((x∈C)x∈A)˄(((x∈C)x∈B))x(((x∈C)((x∈A)˄x∈B))x((x∈C)x∈A˄B)CAB17.设A，B是任意集合，证明：（清华1004445）（1）ABP(A)P(B)(2)P(A)P(B)=P(AB)(3)P(A)P(B)P(AB)解：(1)设对任意X，XP(A)，则XA，又AB，有XB，则XP(B)，所以P(A)P(B)。(2)设对任意X，X(P(A)P(B))X(P(A))(X(P(B)(XA)(XB)X(AB)XP(AB)所以P(A)P(B)=P(AB)(3)设对任意X，X(P(A)P(B))X(P(A))(X(P(B)(XA)(XB)X(AB)XP(AB)所以P(A)P(B)P(AB)第4章部分习题解答设集合A={0,1}和B={a,b}，试给出下列集合：(1)AB(2)A{2}B(3)BA解：(1)AB={(0,a),(1,a),(0,b),(1,b)}(2)A{2}B={(0,2,a),(0,2,b),(1,2,a),(1,2,b)}(3)BA={(a,0),(a,1),(b,0),(b,1)}设A={1，2}，试给出下列集合AP(A)。解：AP(A)={(1,),(1,{1}),(1,{2}),(1,{1,2}),(2,),(2,{1}),(2,{2}),(2,{1,2})}设A、B、C和D是四个任意的集合，下列各式哪些成立，哪些不成立，为什么？请举例说明。(1)(AB)(CD)=(AC)(BD)(2)(AB)(CD)=(AC)(BD)(3)(A−B)(C−D)=(AC)−(BD)(4)(AB)(CD)=(AC)(BD)(5)(AB)C=(AC)(BC)解：成立不成立A={1,2}B={2,3}C={1,2}D={2,3}，(AB)(CD)(AC)(BD)不成立A={1,2}B={2,3}C={1,2}D={2,3}，(A−B)(C−D)(AC)−(BD)不成立A={1}B={2}C={1}D={2}，(AB)(CD)={(1,1),(1,2),(2,1),(2,2)}(AC)(BD)={(1,1),(2,2)}故不成立（5）成立设A,B,是任意的集合，证明：若AB=BA，则A=B证明：设任意xA,yB,（x,y）AB,则xAyB。若AB=BA，则有（x,y）BA,则xByA。所以A=B对于下列各种情况，试求出从集合A到B的关系S的各元素：(1)A={0,1,2}，B={0,2,4}，S={<x,y>|x,yAB}(2)A={1,2,3,4,5}，B={1,2,3}，S={<x,y>|xy}解答：（1）S={（0,0），（2,2），（0,2），（2,0）}（2）S={（2,1），（3,1），（3,2），（4,1），（4,2），（4,3），（5,1），（5,2）.（5,3）}从m元集合到n元集合有多少个不同的二元关系。解答：2mn给定集合A={0,1,2,3}，并且有A上的关系R={<0,1>,<1,0>,<1,2>,<1,3>,<2,1>,<2,2>,<2,3>,<3,1>,<3,2>}画出R的关系图写出R的关系矩阵。设集合A={1，2，3，4，5}，试求A上的模2同余关系R的关系矩阵和关系图。解：关系矩阵：关系图：已知A={1，2，3，4，5}，B={1，2，3}，R是A到B的二元关系，并且R={(x，y)|xA且yB且2x+y4}，画出R的关系图，并写出关系矩阵。用L表示“小于或等于”关系；用D表示“整除”关系；xDy意味着“x整除y”。L和D都定义于集合S={1,2,3,6}。试把关系L和D表示成序偶集合，并且求出LD，LD，LD，LD。解：L={(1,1),(1,2),(1,3),(1,6),(2,2),(2,3),(2,6),(3,3),(3,6),(6,6)}D={(1,1),(1,2),(1,3),(1,6),(2,2),(3,3),(6,6),(2,6),(3,6)}LD={(1,1),(2,2),(1,2),(1,3),(1,6),(3,3),(6,6),(2,6),(3,6)}，LD={(1,1),(1,2),(1,3),(1,6),(2,2),(2,3),(2,6),(3,3),(3,6),(6,6)}，LD={(2,3)}，LD={(2,3)}给定集合X={a,b,c,d}，且X中有二元关系：R={<a,a>,<a,b>,<b,d>}S={<a,b>,<b,c>,<b,d>,<c,d>}(1)求出复合关系RoS。表示关系R，S和RoS的关系矩阵MR，MS，MRoS。解答：（1）RoS={<a,d>} (2)对以下整数集上的关系R和S，确定RoS。(1)R={<x,y>|y=x+1}，S={<x,y>|y=3x-2}(2)R={<x,y>|y=x2}，S={<x,y>|x=y2}(3)R={<x,y>|y=2x}，S={<x,y>|y=log2x}设R1，R2和R3是集合X中的二元关系。证明如果有R1R2，那么：(1)R1oR3R2oR3(2)R3oR1R3oR2证明：(1)∵R1R2，则对任意<x,y>,<x,y>R1，则<x,y>R2对任意y,z,<z,y>R1oR3x(<z,x>R3<x,y>R1)x(<z,x>R3<x,y>R2)<z,y>R2oR3∴R1oR3R2oR3（2）∵R1R2，则对任意<x,y>,<x,y>R1，则<x,y>R2对任意x,z,<x,z>R3oR1y(<x,y>R1<y,z>R3)y(<x,y>R2<y,z>R3)<z,y>R3oR2∴R3oR1R3oR2给定关系R={<i,j>|(i,jI)(j-i=1)}。分别写出关系R和Rn的关系矩阵。设R是A上的关系,证明RoIA=R=IAoR。整数集上的关系R={<x,y>|xy}和S={<x,y>|x整除y}，求R-1，S-1。解答：R-1={<x,y>|x>y},S-1={<x,y>|y整除x}给定集合S={1,2,...10}和S中的关系R={<x,y>|(x,yS)(xy2)}试问关系R具有哪几种性质？解答：反自反，反对称，传递是否存在既是对称的又是反对称的关系？若存在请举出一例。解答：A={1,2}，A上的关系R={（1,1），（2,2）}19.是否存在既不是对称的又不是反对称的关系？若存在请举出一例。解答：A={1,2}，A上的关系R={（1,2）}20.如果关系R和S都是自反的，试证明或反驳下面的论断。关系RS是自反的。关系RS是自反的。关系RS是反自反的。关系RS是自反的。解答：1），2）3）是，4）不是（1）是。证：对任意x∈A,因为（2）是。证：对任意x∈A,因为x,x(3)是。证：对任意x∈A,因为（4）不是。证：假设A={1,2,3}R={(1,1),(2,2),(3,3),(2,3)}S={(1,1),(2,2),(3,3)}R,S均是A上的自反关系，但R–S={(2,3)},显然不是集合A上的自反关系。21下列关系是否是可传递的？试给出证明。(1)R1={<1,1>}(2)R2={<1,2>,<2,2>}(3)R3={<1,2>,<2,3>,<1,3>,<2,1>}(4)R4={<1,2>,<3,4>}解答：（1）（2）（4）是，（3）不是22给定集合X，且R是X上的二元关系。证明RoRR，当且仅当关系R是可传递的。证明：证明充分性。对任意的x,z∈R∘R,根据关系复合运算的定义，则存在y∈X,使得(x,y∈R并且再证明必要性：对任意x,y,z∈A，若x,y∈R并且y,z∈R,则x,z∈R∘R.因为综上所述，RoRR，当且仅当关系R是可传递的。23设R1和R2是集合X上的任意二元关系。证明或反驳下列命题：(1)如果R1和R2是自反的，则R1oR2也是自反的。(2)如果R1和R2是反自反的，则R1oR2也是反自反的。(3)如果R1和R2是对称的，则R1oR2也是对称的。(4)如果R1和R2是反对称的，则R1oR2也是反对称的。(5)如果R1和R2是可传递的，则R1oR2也是可传递的。解答：真命题假命题，R1={<2,1>}，R2={<1,2>}，R1oR2={<1,1>}不是反自反假命题，R1={<2,1>，<1,2>}，R2={<3,2>，<,2,3>}，R1oR2={<3,1>}不是对称的假命题，R1={<2,1>，<1,3>}，R2={<3,2>，<1,1>}，R1oR2={<3,1>,<1,3>}不是反对称的假命题，R1={<2,3>，<4,4}，R2={<1,2>，<3,4>}，R1oR2={<1,3>,<3,4>}不是传递的24证明：(1)如果关系R是自反的，则R的逆关系也是自反的。(2)如果关系R是反自反的，则R的逆关系也是反自反的。(3)如果关系R是对称的，则R的逆关系也是对称的。(4)如果关系R是反对称的，则R的逆关系也是反对称的。(5)如果关系R是可传递的，则R的逆关系也是可传递的。证明：（3）设（x,y）R-1,则（y,x）R，由于关系R是对称的，则（x，y）R，因而（y，x）R-1,所以R的逆关系也是对称的。（5）设（x,y）R-1,（y,z）R-1,则（y,x）R，（z，y）R，由于关系R是可传递的，则（z，x）R，因而（x，z）R-1,所以R的逆关系也是可传递的。25设集合A={a，b，c，d}，R1，R2都是A上的二元关系，R1={(a，b)，(b，c)，(c，a)}，R2=，试求R1和R2的自反闭包，对称闭包和传递闭包。解答：R1自反闭包：{(a,a),(a,b),(b,b),(b,c),(c,c),(c,a),(d,d)}R1对称闭包：{(a,b),(b,a),(b,c),(c,b)(c,a),(a,c)}R1传递闭包：{(a,b),(b,c),(a,c),(b,a),(c,b),(c,a),(a,a),(b,b),(c,c)}R2自反闭包：{(a,a),(b,b),(c,c),(d,d)}R2对称闭包：R2传递闭包：26求正整数集合上的关系R={(a，b)|ab}自反闭包和对称闭包。解答：关系R={(a，b)|ab}自反闭包为r(R)={(a，b)|ab}对称闭包s(R)={(a，b)|ab}27求包含关系{(1，2)，(1，4)，(3，3)，(4，1)}的最小关系R，使得：R具有自反性和传递性；R具有对称性和传递性；R具有自反性、对称性和传递性。解答：(1){(1,1),(1,2),(2,2),(1,4),(3,3),(4,1),(4,4)}(2){(1,2),(1,4),(3,3),(4,1),(2,1),(1,1),(4,2),(4,4),(2,2),(2,4)}(3){(1,2),(1,4),(3,3),(4,1),(2,1),(2,2),(1,1),(4,4),(2,4),(4,2)}28证明：R是集合A上的二元关系，则R是反自反的当且仅当RIA=。证明：先证明充分性：因为R∩IA=ϕ,再证明必要性：因为R是反自反的，随意对任意的x有：x∈A→x,x∉R,又IA29设R是集合A上的一个具有自反和传递性质的关系，T是A上的关系，使得(a，b)T(a，b)R且(b，a)R，证明T是一个等价关系。证明：1）对任意aA,由于R是集合A上的自反关系，则有(a，a)R，(a，a)R且(a，a)R(a，a)T,因而T是自反的。2）设任意(a，b)T,由(a，b)T(a，b)R且(b，a)R，则有(b，a)R且(a，b)R(b，a)T,因而T是对称的。3）设任意(a，b)T,(b，c)T,由(a，b)T(a，b)R且(b，a)R，(b，c)T(b，c)R且(c，b)R，由于R是传递的，由(a，b)R和(b，c)R，则(a，c)R，由(b，a)R和(c，b)R，则(c，a)R，则有(a，c)R且(c，a)R(a，c)T,因而T是传递的。综上所述，T是一个等价关系。30设R是集合A上的一个自反的关系，证明R是一个等价关系，当且仅当若(a，b)R，(a，c)R则(b，c)R。31设R1和R2都是集合X上的等价关系。证明R1R2也是集合X中的一种等价关系。再证明，R1R2不一定是集合X中的一种等价关系。证明：由题意得，R1，R2是自反，对称和传递的。对任意xÎX，(x,x)ÎR1，(x,x)ÎR2，则(x,x)ÎR1R2，R1R2是自反的。对任意(x,y)ÎR1R2，则(x,y)ÎR1，(x,y)ÎR2，由于R1，R2是对称的，有(y,x)ÎR1，(y,x)ÎR2，因而有(y,x)ÎR1R2，R1R2是对称的。对任意(x,y)ÎR1R2，(y,z)ÎR1R2，则(x,y)ÎR1，(x,y)ÎR2，(y,z)ÎR1，(y,z)ÎR2，由于R1，R2是传递的，有(x,z)ÎR1，(x,z)ÎR2，因而有(x,z)ÎR1R2，R1R2是传递的。综上，R1R2是集合X中的一种等价关系。R1R2不一定为X上等价关系。例如：R1={(1,1),(2,2),(1,2),(2,1),(3,3)} R2={(1,1),(2,2),(3,3),(2,3),(3,2)}R1R2并不传递。因为有元素(1,2),(2,3)属于R1R2，但元素(1,3)不属于R1R232给定一个集合X，并且R是X中的一种关系。对于所有的xi、xj、xkX来说，如果xiRxj和xjRxk蕴含xkRxi,则称R是个循环关系。证明：R是一种等价关系，当且仅当关系R是自反的和循环的。证明：（必要性）若R是一种等价关系，则R是自反的，对称的和传递的。如果xiRxj和xjRxk，由于R是传递的，有xiRxk，又由于R是对称的，有xkRxi,则称R是循环的。（充分性）假设xiRxj，若R是自反的，则有xjRxj，由于R是循环关系，xiRxj和xjRxj蕴含xjRxi,所以R是对称的。假设xiRxj和xjRxk，由于R是循环关系，有xkRxi,又由于R是对称的，因而有xiRxk,所以R是传递的。R是自反、对称和传递的，所以R是等价关系。33设A={a，b，c，d}，R1，R2是A上的关系，其中R1={(a，a)，(a，b)，(b，a)，(b，b)，(c，c)，(c，d)，(d，c)，(d，d)}，R2={(a，b)，(b，a)，(a，c)，(c，a)，(b，c)，(c，b)，(a，a)，(b，b)，(c，c)}。画出R1和R2的关系图判断它们是否为等价关系，是等价关系的求A中各元素的等价类34设R1和R2都是集合X上的等价关系。证明：划分C1中的每一个等价类都包含于划分C2的某一个等价类之中，当且仅当有R1R2。证明：证明必要性设R1，R2造成的划分为：C1={c11,c12对任意的c1i∈C1i=1,2…n,在C2中都存在某一个c2j(j=1,2,…,m)并且c1i⊆c2j。对于任意的x,y∈c1i再证充分性：设R1⊆R2，于是对于任意的x,y∈c1i∈C1i=1,2…n,有<x,y>∈R1则<35设集合A={A1,A2,...,An}是集合S的划分，并且B是一个任意集合且AiB。试证明集合{A1B,A2B,...AnB}是集合SB的划分。证明：(1)由题设，Ai∩B≠ϕ(2)因为Ai为S的一个划分块，所以Ai∩Aj(3)对于任意的x,x∈B∩S,则xB且xS。因为A1∪A2∪…∪An=S,所以必存在i,使得xAi，因而对于任意的x,x∈i=1n(Ai∩B),存在i,使得x∈(Ai∩B)，因而xB且xAi，因为A1∪A所以i=1综上，由划分的定义，原命题成立。36把n个元素的集合划分成两个类，共有多少种不同的方法？解：2n-1-137.A={1，2，3}{1，2，3，4}，A中关系R定义为：(x，y)R(u，v)，当且仅当|x-y|=|u-v|，证明R是等价关系，并确定由R对集合A的划分。证明：1）设(x,y)A，则|x-y|=|x-y|(x-y)R(x-y)，R是自反的2）设(x,y)R(u,v)，则|x-y|=|x-y|，因而|u-v|=|x-y|，(u,v)R(x，y),R是对称的3）设(x,y)、(u,v)、(t,w)，若(x,y)R(u,v),(u,v)R(t,w)，则|x-y|=|u-v|，|u-v|=|t-w|，因而|x-y|=|t-w|，R是传递的因此，R是等价的关系。由R对集合A的划分（A）={{（1,1），（2,2），（3,3）}，{（1,2），（2,1），（2,3），（3,2），（3,4）}，{（1，3），（3,1），（2,4）}，{（1,4）}}38已知集合A1={1，2，3}，A2={4，5}，A3={6}是集合S={1，2，3，4，5，6}的一个划分，求由该划分产生的等价关系R。解答：R=A1A1A2A2A3A3={(1,1),(2,2),(3,3),(1,2),(2,1),(2,3),(3,2),(1,3),(3,1),(4,4),(4,5),(5,4),(5,5),(6,6)}39设集合A={1,2,3}。求出A中这样的等价关系R1和R2，使得复合关系R1oR2也是个等价关系。解答：R1={(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)}R2={(1,1),(2,2),(2,3),(3,2),(3,3)}复合关系R1oR2={(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)}（注：此题答案不唯一）40试给出一种关系，它既是集合中的偏序关系，又是等价关系。解答：集合A={1,2,3}，A上的关系R={（1,1），（2,2），（3,3）}41Z是整数集，下面哪些是偏序集？1)(Z，=)2)(Z，)3)(Z，)4)(Z，|)解答：1)是(相等关系既是对称也是反对称)、2)否、3)是、4)否（因为整数集中整除关系不是自反的，0不能整除0）42确定由下面的0-1矩阵表示的关系是否为偏序？解答：1）不是2）是3）不是43画出集合A={3，5，9，15，24，45}的整除关系的哈斯图，回答下列问题。求出A的极大元素和极小元素。A中存在最大元素和最小元素吗？找出{3，5}的所有上界和最小上界。找出{15，45}的所有下界和最大下界。解答：(1)极大元：45,24，极小元：3,5(2)不存在(3)上界：45和15最小上界：15(4)下界：3,5,15最大下界：1544设集合A={a，b，c，d，e}，A上的二元关系R为R={(a，b)，(a，c)，(a，d)，(a，e)，(b，e)，(c，e)，(d，e)}ÈIA写出R的关系矩阵，画出R的关系图；证明R是A上的偏序关系，画出其哈斯图；指出A的最大元，最小元，极大元，极小元，最小上界和最大下界。acbed解：R={(a，b)，(a，c)，(a，d)，(a，e)，(b，e)，(c，e)，(d，e)acbed证明：因为IA⊆R,所以R是自反的。R-1={(b，a)，(c，a)，(d，a)，(e，a)，(e，b)，(e，c)，(e，d),(a,a),(b,b),(c,c),(d,d),(e,e)}RÇR-1ÍIA,所以R是反对称的RoR=R,即RoRÍR,所以R是传递的。综上，R为A上的偏序关系。bbacde哈斯图：最小元、极小元、最大下界：a最大元、极大元、最小下界：e 45下列关系中哪一些能够构成函数?(1)R1={<x,y>|(x,yN)(x+y<10)}(2)R2={<x,y>|(x,yR)(y=x2)}(3)R3={<x,y>|(x,yR)(y2=x2)}解答：（1）（3）不是，（2）是46设Z是整数集合，Z+是正整数集合，函数f:ZZ+为f(x)=|2x|+1。试求出函数f的值域。解答：正奇数集合47下列映射中哪些是满射，哪些是单射，哪些是双射？(1)(2)(3)(4)(5)(6)解答：(1)（3）（5）映射，不是单射，不是满射（2）满射（4）双射（6）单射48设|A|=n,|Y|=m，从A到B有多少个不同的函数？当m和n满足什么条件时，存在单射函数？有多少不同的单射函数?当m和n满足什么条件时，存在满射函数？有多少不同的满射函数?当m和n满足什么条件时，存在双射函数？有多少不同的双射函数?解答：mnnm时存在单射函数，有个不同的单射函数。nm时存在满射函数，有个不同的满射函数。n=m时存在双射函数，有n!个不同的双射函数。49设f：AB，g：BC，是函数，证明：如果gof是满射且g是单射，则f是满射。如果gof是单射且f是满射，则g是单射。证明：(1)若f：AB，g：BC，对任意bB，因为g是函数，所以存在cC，使得g(b)=c，由于gof是满射函数，则对c，必存在aA，使得gof(a)=c，所以gof(a)=g(f(a))=c.因而有g(f(a))=g(b)=c，由