离散习题答案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不是入射。

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4