离散习题答案1-4

（2）{,}

（3）{,,,,} （4）{,,,,} （5）{,}

9. 设Rj表示Z上模j等价关系，Rk表示Z上模k等价关系, 证明：Z/Rk细分Z/Rj当且仅当k是j的整数倍。

证明：充分性：若k是j的整数倍，即?l?Z，使k=lj， Z/Rk={[a]Rk| a?Z}，Z/Rj={[a]Rj| a?Z }，[a]Rk={x| x?Z∧aRkx}，[a]Rj={x| x?Z∧aRjx}，显然对任意的x?[a]Rk，a?x(mod k)，即?m?Z，使得a?x=km= ljm= lmj，即x?[a]Rj，因此Z/Rk细分Z/Rj。 必要性：若Z/Rk细分Z/Rj，即[a]Rk?[a]Rj，显然?[a]Rk，因此?[a]Rj，所以k?0=1·k=c·j， c?Z，于是k是j的整数倍。

10. 证明：若关系R是对称的, 则Rk(k≥1, k?N)也是对称的。 证明：

设R是A上的二元关系，?x，y?A，若xRky成立，则由关系复合的定义，存在x0=x,x1,x2,…xk-1,xk=y，使得x0Rx1, x1Rx2,…, xk-1Rxk成立，由R是对称的,故xkRxk-1, xk-1Rxk-2, …, x2Rx1, x1Rx0成立,再由关系复合的定义，有xkRkx0成立，即yRkx，因而Rk(k≥1, k?N)是对称的。

11. 设集合A={a,b,c,d}上的关系R={,,,}，用矩阵运算求出R的自反、对称和传递闭包。 解：

?0?1MR???0??0?0?1??0??0?0?1??0??0

1000100001000100

100001000??1?00??，IA???01???0??0010010100?0??1??0?00100001?0?1??0??00100001011001010

0??0?10??，M?1??R?00???1??0011001010?0??。 1??1?0?0?? 1??0?010010000?1?? 0??0?101000010?0??, 0??0?0??1

?00??∨?1??0??0??00??0

?10??∨?1??0??0??0100001000??1

?10??=?0??0??1??00??0

?10??=?0??0??0??010000100所以r(R)={,,,,,,}

所以s(R)={,,,,}

MR2?0?1???0??00??1?00????1??0??0??0MR3?1?0???0??0?0?1???0??001001000?1?1???0??01000010011000?1??0??0?1?0??0??0?1100?0?1??0??0?0?1??0??010001000010001000??0?10????1??0??0??00??1?00????1??0??0??010000100010010001?0?? 0??0?0?1?? 0??0?MR4所以Mt(R)1?1?? 1??0?t(R)={ ,,,,,,,,}

12. 设R和S是A上的二元关系，且R?S，证明： （1）r(R) ?r(S) （2）s(R) ?s(S) （3）t(R) ?t(S) 证明：

（1）??r(R),由r(R)的定义有?R??IA, 若?R ,由R?S, ?r(S), 若?IA, 有?r(S),所以r(R)?r(S)。 （2）??s(R)，由s(R)的定义有?R??R?1, 若?R ,由R?S, ?s(S), 若? R?1, 有?R,因而?S,所以?S?1, 即?s(S)，所以s(R)?s(S)。

（3）?? t(R),由t(R)的定义有?Rk(k≥1, k?N)，即存在x0=x,x1,x2,…xk-1,xk=y，使得x0Rx1, x1Rx2,…, xk-1Rxk成立，由R?S,因而x0Sx1, x1Sx2,…, xk-1Sxk成立，所以?Sk(k≥1, k?N)，即? t(S),因而t(R) ?t(S)。 13. 设R和S是A上的二元关系，证明： （1）r(R∪S)= r(R)∪r(S) （2）s(R∪S)= s(R)∪s(S) （3）t(R)∪t(S)?t(R∪S) 证明：

（1）r(R∪S)= (R∪S)∪IA= (R∪IA)∪(S∪IA) = r(R)∪r(S)。

（2）s(R∪S)= (R∪S)∪(R∪S) ?1= (R∪S)∪(R?1∪S?1) = (R∪R?1)∪(S∪S?1) = s(R)∪s(S)。 （3）t(R)∪t(S) =

?R∪?S，t(R∪S) =?(R?S)=?R∪?S∪?iiiiii?1i?1i?1i?1i?1?????Ri?Sj显，

1?i,j??然t(R)∪t(S)?t(R∪S)。14. 求集合{a，b，c，d }的所有划分和等价关系。

解：集合{a，b，c，d}中共有4个元素，可作如下划分：

1) 4＝1＋1＋1＋1型划分，只有一个，即{ {a}，{b}，{c}，{d}}，对应的等价关系为：{

a>，，，}。 2) 4＝2＋1＋1型划分，有C4＝6个，即{ {a，b}，{c}，{d}}，{ {a，c}，{b}，{d}}，{ {a，

2d}，{b}，{c}}，{ {b，c}，{a}，{d}}，{ {b，d}，{a}，{c}}，{ {c，d}，{a}，{b}}，对应的等价关系为：{ ，，，，，}，{ ，，，，，}，{ ，，，，，}，{ ，，，，，}，{ ，，，，，}，{ ，，，，，}。

13) 4＝3＋1型划分，有C4＝4个，即{ {a，b，c}，{d}}，{ {a，b，d}，{c}}，{ {a，c，d}，

{b}}，{ {b，c，d}，{a}}，对应的等价关系为：{ ，，，，

，，，，，}，{ ，，，，，，，，，}，{ ，，，，，，，，，}，{ ，，，，，，，，，}。

24) 4＝2＋2型划分，有C4/2＝3个，即{ {a，b}，{c，d}}，{ {a，c}，{ b，d}}，{ {a，

d}，{b，c}}，对应的等价关系为：{ ，，，，，

d>，，}，{ ，，，，，，，}，{ ，，，，，，，}。

5) 4＝4＋0型划分，有1个，即{ {a，b，c，d}}，对应的等价关系为：{ ，，

，，，，，，，，，，，，， }。

综上，集合{a，b，c，d}的划分和等价关系共有15个。

15. 设R是非空集合A上的二元关系。如果对?a,b,c∈A满足aRb且bRc?cRa，则称R为A上循环关系。证明：R是自反和循环的关系当且仅当R是等价关系。 证明：

必要性：若R是自反和循环的，对?a,b,c∈A，aRa成立，若aRc成立，由R是循环的，有cRa，因此R是对称的，再若aRb且bRc，由R是循环的，有cRa，再由R是对称的，有aRc，因此R是传递的，因而R是等价关系。

充分性：若R是等价关系，则显然R是自反的，只需证R是循环的。对?a,b,c∈A，若 aRb且bRc，由R的传递性，有aRc，再由R的对称性，有cRa，因此R是循环的。 16. 设A, B是非空集合，f是从A到B的映射。定义A上二元关系R为：

x，y∈A, xRy当且仅当f(x)=f(y)

证明：R是A上等价关系，并描述由R生成的A的划分。 证明：

显然f(x)=f(x)，因此xRx当，即R是自反的。

若xRy，有f(x)=f(y)，因此f(y)=f(x)，所以yRx，即R是对称的。

若xRy，yRz，有f(x)=f(y)，f(y)=f(z)，因此f(x)=f(z)，所以xRz，即R是传递的。 因此R是A上等价关系。

由R生成的A的划分中凡是对应的值相同的自变量属于同一分块。 17. 给出一个既是等价关系又是偏序关系的二元关系。 解： A＝{a,b,c}上的R={,,}。

18. 设A1、A2和A3是全集U的子集，则形如?Ai?(Ai?为Ai或~Ai)的集合称为由A1、A2和A3

i?13产生的小项。试证由A1、A2和A3所产生的所有非空小项的集合构成全集U的一个划分。 证明： （1）?Ai???

i?13（2）?Ai?∩?Aj?=?

i?1i?133（3）(A1∩A2∩A3)∪(A1∩A2∩~A3)∪(A1∩~A2∩A3)∪(A1∩~A2∩~A3)∪(~A1∩A2∩A3)∪(~A1∩A2∩~A3)∪(~A1∩~A2∩A3)∪(~A1∩~A2∩~A3)=(A1∩A2)∪(A1∩~A2)∪(~A1∩A2)∪(~A1∩~A2) = A1∪~A1=U

因此，由A1、A2和A3所产生的所有非空小项的集合构成全集U的一个划分。 19. 设R和S是A上的相容关系，问：

（1）复合关系RS是A上的相容关系吗？ （2）R∩S是A上的相容关系吗？ （3）R∪S是A上的相容关系吗？ 解： （1）设A={1,2,3}，R={<1,1>,<2,2>,<3,3>,<1,2>,<2,1>}，S={<1,1>,<2,2>,<3,3>,<2,3>,<3,2>}，RS={<1,1>,<2,2>,<3,3>,<1,2>,<2,1>,<2,3>,<3,2>,<1,3>}，不是相容关系。 （2）R∩S显然是自反的，∈R∩S，则∈R且∈S，因而∈R且∈S，即∈R∩S，因此R∩S是A上的相容关系。 （3）R∪S显然是自反的，∈R∪S，则∈R或∈S，因而∈R或∈S，即∈R∪S，因此R∪S是A上的相容关系。 是A上的相容关系。

20. 画出集合S={1,2,3,4,5,6}在偏序关系“整除”下的哈斯图， （1）写出{1,2,3,4,5,6}的最大(小)元和极大(小)元；

（2）分别写出{2,3,6}和{2,3,5}的上(下)界、上(下)确界。 解：哈斯图如下：

{1,2,3,4,5,6}的最大元：无。{1,2,3,4,5,6}的最小元：1。 {1,2,3,4,5,6}的极大元：4、5、6。{1,2,3,4,5,6}的极小元：1 546{2,3,6}的上界：6。{2,3,6}的下界：1。

{2,3,6}的上确界：6。{2,3,6}的下确界：1。

23{2,3,5}的上界：无。{2,3,5}的下界：1。 {2,3,5}的上确界：无。{2,3,5}的下确界：1。

1

习题四

1. 分析下列各个函数，指出其性质（入射、满射或双射）

（1）f: Z→Z, f(j)=j mod 3 （2）f: N→N，f(j)??10j是偶数

j是奇数（3）f: N→{0,1}，f(j)??10j是偶数

j是奇数（4）f: Z→N，f(i)=|2i|+1 （5）f: R→R，f(r)=2r –15 解：

（1）、（2）、（4）既不是入射，也不是满射。 （3）是满射。 （5）是双射。

2. 假设f和g是函数，求证f∩g也是函数。 证明： f∩g={|x?dom f∧x?dom g∧y=f(x)∧y=g(x)}={|x?dom f∩dom g∧y=f(x)=g(x)} 令h = f∩g，则

dom h ={x|x?dom f∩dom g∧f(x) =g(x)}

若y1? y2，因为f是函数，故必有y1=f(x1)，y2=f(x2)，且x1?x2，所以h = f∩g是一个函数。因为dom h存在且y1? y2时x1?x2，即 h ={|x?dom h，y=h(x) =f(x) =g(x)}

3. 设A={1，2，?，n}，证明从A到A的任意单射函数必是满射函数，其逆亦真。 证明：设f是从A到A的单射函数，则|A|=| f(A)|，因为f是A到A的函数，所以 f(A) ? A，又因为|A|=| f(A)|，且|A|是有限的，因此必有f(A) = A，即f是满射函数。

反之，若f是从A到A的满射函数，根据满射定义有，f(A) = A，于是|A|=| f(A)|，又由|A|是有限的，故f是从A到A的单射函数。

4. 证明从N×N到N的函数f(x，y)=x+y和g(x，y)=x?y是满射，但不是单射。 证明：对任意z?N，显然存在0，1，z?N，使得0+z=z，1?z=z，因而f(x，y)=x+y和g(x，y)=x?y是满射。由于3+2=4+1=5，因而f(x，y)=x+y不是单射，由于3?2=6?1=6，因而g(x，y)=x?y不是单射。

5. 试给出满足下列条件的函数例子。 （1）是单射而不是满射。 （2）是满射而不是单射。 （3）不是单射也不是满射。 （4）既是单射又是满射。 解：

（1）设A={a,b,c}，B={1,2,3,4}，f={,,}。 （2）设A={a,b,c}，B={1,2}，f={,,}。 （3）设A={a,b,c}，B={1,2,3,4}，f={,,}。 （4）设A={a,b,c}，B={1,2,3}，f={,,}。 6. 有限集A和B，|A|=m，|B|=n，问： （1）A到B的不同的二元关系有多少？ （2）从A到B存在多少不同的函数？

（3）从A到B存在入射的条件是什么？有多少不同的入射？ （4）从A到B存在满射的条件是什么？有多少不同的满射？ （5）从A到B存在双射的条件是什么？有多少不同的双射？

解：（1）2 mn 。（2）n m。（3）m≤n，Cn?m!。 （4）n≤m，n!S(m，n)。(本题具有一定的难度，S(m，n)的意义请参见9.5节，本题即第9章44题。)（5）m=n，m！。 7. 证明：

（1）f(A∪B)= f(A)∪f(B) （2）f(A∩B)? f(A)∩f(B) （3）f(A)-f(B) ? f(A-B) 证明：

m（1）对任意的y?f(A∪B)有，

y?f(A∪B) ??x?A∪B∧f(x)= y??x?A∨?x?B∧f(x)= y ?(?x?A∧f(x)= y)∨(?x?B∧f(x)= y) ? y?f(A)∨y?f(B) ? y?f(A)∪f(B) （2）对任意的y?f(A∩B)有，

y?f(A∩B) ??x?A∩B∧f(x)= y??x?A∧?x?B∧f(x)= y ?(?x1?A∧f(x1)= y) ∧(?x2?B∧f(x2)= y) ? y?f(A)∧y?f(B) ? y?f(A)∩f(B)

（3）对任意的y? f(A)-f(B)有，y?f(A)∧y?f(B)。即对某个x1?A，y=f(x1)，但对任意x?B，y?f(x)。故对某个x1?A-B，y=f(x1)，即 y? f(A-B) 于是 f(A)-f(B) ? f(A-B)。

8. 设f: A→B是满射函数，且函数g: B→P(A)定义为: g(b)={x|x∈A∧f(x)=b}

证明：g是单射。其逆成立吗？若成立给出证明，否则给出例子予以说明。

证明：因为f是满射函数，则对任意b∈B，至少存在一个x∈A，使得f(x)=b，故g的定义域为B。对任意的b1，b2?B，且b1?b2， g(b1)={x|x∈A∧f(x)= b1} g(b2)={y|y∈A∧f(y)= b2}

因为b1?b2，f(x)?f(y)，而f是函数，故x?y，所以 g(b1)?g(b2) 故g是单射。 逆不成立。

例如：A={a,b,c}，B={x,y,z}，则 f: A→B，f(a)=x，f(b)=x，f(c)=y。

g: B→P(A)，g(x)={a,b}，g(y)={c}，g(z)= ?。 g是单射，但f不是满射。

9. 证明：若f: A→B，g: B→A，且gf =IA，f g =IB，则g=f-1，且f=g-1。

证明：因为gf =IA，所以gf (a1)= g(f (a1)) =a1，gf (a2)= g(f (a2)) =a2，若a1≠a2，g(f (a1))≠g(f (a2))，所以f (a1)≠f (a2)，即f:是入射。

又对任意的a?A有gf (a)= g(f (a)) =a，即存在f (a)=b?B，使得g(b) =a，因此g是满射。同理，若f g =IB，则g是入射且f是满射，故可知f和g都是双射函数。

设?f，因为?IA，而gf =IA，故必有某个c?B，使得?f且?g，由?f∧?f?b=c 因此?g。

反之，若?g，由?IB，故必有某个d?A，有?g∧?f，由?g∧?g?a=d 因此?f。

上述证明得到?f当且仅当?g，所以g=f-1且f=g-1。 10. 证明：若(gf)-1是一个函数，则f和g不一定是入射。

证明：设A={a,b,c}，B={1,2,3,4}，C={x,y,z}，f是A到B的函数，g是B到C的函数，

f={,,}，g={<1,x>,<2,x>,<3,y>,<4,z>},

则gf={,,}，(gf)-1={,,}是双射函数，但g不是入射。