《离散数学》题库答案 集合论与二元关系

一、选择或填空

1. 设A={a, {a}}，下列命题错误的是（ ）。

（1） {a} P(A) （2） {a} P(A) （3） {{a}} P(A) （4） {{a}} P(A) 答：（2）

2. 在0（ ）Ф之间写上正确的符号。 （1）= （2） （3） （4） 答：（4）

3. 若集合S的基数|S|=5，则S的幂集的基数|P(S)|=（ ）。 答：32

4. 设P={x：(x+1)2 4且x R}，Q={x：5 x2+16且x R}，则下列命题哪个正确（ ）？

（1）Q P （2）Q P （3）P Q （4）P=Q 答：（3）

5. 下列各集合中，哪几个分别相等？（ ） （1）A1={a, b} （2）A2={b, a} （3）A3={a, b, a} （4）A4={a, b, c} （5）A5={x：(x-a)(x-b)(x-c)=0} （6）A6={x：x2-(a+b)x+ab=0}

答： A1=A2=A3=A6，A4=A5

6. 若A-B=Ф，则下列哪个结论不可能正确？（ ） （1）A=Ф （2）B=Ф （3）A B （4）B A 答：（4）

7. 判断下列命题哪个为真?（ ）

（1）空集只是非空集合的子集 （2）空集是任何集合的真子集 （3）A-B=B-A A=B （4）若A的一个元素属于B，则A=B 答：（3）

8. 判断下列命题哪几个为正确？（ ）

（1）{Ф}∈{Ф, {{Ф}}} （2）{Ф} {Ф, {{Ф}}} （3）Ф∈{{Ф}} （4）Ф {Ф} （5）{a, b}∈{a, b, {a}, {b}} 答：（2）（4）

9. 判断下列命题哪几个正确？（ ） （1）所有空集都不相等 （2）{Ф} Ф （3）若A为非空集，则A A成立。 答：（2）

10. 设A∩答：=（等于）

11. 判断下列命题哪几个正确？（ ）

（1）若A∪B＝A∪C，则B＝C （2）{a, b}={b, a}

，A ∩B=A ∩C，则B（ ）C。

（3）P(A∩B) P(A)∩P(B) （P(S)表示S的幂集） （4）若A为非空集，则A A∪A成立 答：（2）

12. Ａ，Ｂ，Ｃ是三个集合，则下列哪几个推理正确？（ ） （1）A B，B C A C （2）A B，B C A∈B （3）A∈B，B∈C A∈C 答：（1）

13. 设A={1, 2, 3,4, 5, 6}，B={1, 2, 3}，从A到B的关系R={(x, y)：x=y2}，求（1） R （2） R-1 。

答：（1）R={<1, 1>, <4, 2>} （2） R-1={<1, 1>, <2, 4>}。

14. 举出集合A上的既是等价关系又是偏序关系的一个例子。（ ） 答：A上的恒等关系

15. 集合A上的等价关系的三个性质是什么？（ ） 答：自反性、对称性和传递性

16. 集合A上的偏序关系的三个性质是什么？（ ） 答：自反性、反对称性和传递性

17. 设S={1, 2, 3, 4}，A上的关系Ｒ={<1, 2>，<2, 1>，<2, 3>，<3, 4>}。求（1） R R （2） R-1 。

答：R R ={<1, 1>，<1, 3>，<2, 2>，<2, 4>}

R-1 ={<2, 1>，<1, 2>，<3, 2>，<4, 3>}。

18. 设A=｛1，2，3，4，5，6｝，R是A上的整除关系，求R={（ ）}。 答：R={<1, 1>, <2, 2>, <3, 3>, <4, 4>, <5, 5>, <6, 6>, <1, 2>, <1, 3>, <1, 4>, <1, 5>, <1, 6>, <2, 4>, <2, 6>, <3, 6>}。

19. 设A={1, 2, 3, 4, 5, 6}，B={1, 2, 3}，从A到B的关系R={<x, y>：x=2y}，求（1） R； （2） R-1 。

答：（1）R={<1, 1>, <4, 2>, <6, 3>}； （2）R 1={<1, 1>, <2, 4>, <3, 6>}。

20. 设A={1, 2, 3, 4, 5, 6}，B={1, 2, 3}，从A到B的关系R={<x, y>：x=y2}，求R和R-1的关系矩阵。

1

0 0

答：R的关系矩阵=

0 0 0

00

00

100000

00 000100 。 1

； R的关系矩阵= 10

000000

00 00

21. 集合A={1, 2, …, 10}上的关系R={<x, y>：x+y=10, x, y A}，则R 的性质为（ ）。

（1）自反的 （2）对称的 （3）传递的，对称的 （4）传递的 答：（2）

22. 设 A {x|(x N)且(x 5)},B {x|x E 且x 7}，则 A B （ ）。 答：{0, 1, 2, 3, 4, 6}

23. A，B，C表示三个集合，文图中阴影部分的集合表达式为 （ ）。

答：(B C) A

24. 设A={1, 2, 3, 4}，A上关系图为 则 R2 =（ ）。

答：{<1, 1>, <1, 3>, <2, 2>, <2, 4> }

25. 设A={a, b, c, d}，其上偏序关系R的哈斯图为

则 R=（ ）。

答：{<a, b>, <a, c>, <a, d>, <b, d>, <c, d>}∪IA

26. 下列集合中相等的有（ ）。 （1）{4, 3}∪Ф （2）{Ф, 3, 4} （3）{4, Ф, 3, 3} （4）{3, 4} 答：（2）（3）

27. 设A={1, 2, 3}，则A上的二元关系有（ ）个。 （1）23 （2）32 （3）2 （4）3

3 3

2 2

答：（3）

28. 设A={1, 2, 3, 4}，P(A)（A的幂集）上规定二关元系如下

R { s,t |s,t p(A) (|s| |t|}

则P(A)/ R=（ ）。 （1）A

（2）P(A)

（3）{{{1}}, {{1, 2}}, {{1, 2, 3}}, {{1, 2, 3, 4}}}

（4）{{Ф}, {{1}, {2}, {3}, {4}}, {{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}}, {{1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}}, {A}} 答：（4）

29. 设A={Ф, {1}, {1, 3}, {1, 2, 3}}，则A上包含关系“ ”的哈斯图为（ ）。

（1） （2） （3） （4） 答：（3）

30. 下列函数是双射的为（ ）。

（1）f : Z E , f (x) = 2x （2）f : N N N, f (n) =<n （3）f : R Z , f (x) = [x] （4）f : Z N, f (x) = | x |

（注：Z—整数集，E—偶数集， N—自然数集，R—实数集） 答：（1）

二、解答题或证明题： 1. A (B-C)＝(A B)-(A C)。 证明：

(A B)-(A C) = (A B) (A C) = (A B) (A C ) = (A B A ) (A B C ) = A B C = A B C = A (B-C)

2. (A-B) (A-C)=A-(B C)。 证明：

(A-B) (A-C) = (A B ) (A C ) = A (B C ) = A (B C) = A-(B C)

3. A B=A C，A B=A C，则C=B。 证明：

B = B (A A) = (B A ) (B A) = (C A ) (C A) = C (A A) = C。

4. A B=A (B-A)。 证明：

A (B-A) = A (B A ) = (A B) (A A )

= (A B) U = A B。

5. A=B A B=Ф。 证明：

设A=B，则A B=(A-B) (B-A)= Ф Ф=Ф。

则A B=(A-B) (B-A)= Ф。故A-B=Ф，B-A=Ф， 设A B=Ф，

从而A B，B A，故A=B。

6. A B=A C，A B=A C，则C=B。 证明：

B=B (A B)= B (A C)= (B A) (B C) = (A C) (B C)= C (A B) = C (A C) =C

7. A B=A C，A B=A C，则C=B。 证明：

B= B (A A ) = (B A) (B A ) = (C A) (C A ) = C (A A ) = C

8. A-(B C)＝(A-B)-C。 证明：

A-(B C) = A (B C) = A (B C ) = (A B ) C = (A-B) C = (A-B)-C

9. (A-B) (A-C)=A-(B C)。 证明：

(A-B) (A-C) = (A B ) (A C ) = (A A) (B C ) = A (B C) = A-(B C)

10. A-B=B，则A=B=Ф。 证明：

因为B=A-B，所以B B=(A-B) B=Ф。从而A=A-B=B=Ф。

11. A=(A-B) (A-C) A B C=Ф。 证明：

因为(A-B) (A-C) =(A B ) (A C ) =A (B C )

=A (B C) = A-(B C)，且A=(A-B) (A-C)，

所以A= A-(B C)，故A B C=Ф。

因为A B C=Ф，所以A-(B C)=A。而A-(B C)=

(A-B) (A-C)，

所以A=(A-B) (A-C)。

12. (A-B) (A-C)= Ф A B C。 证明：

因为(A-B) (A-C) =(A B ) (A C ) =A (B C )

=A (B C) = A-(B C)，且(A-B) (A-C)= Ф，

所以Ф= A-(B C)，故A B C。

所以A-(B C)=A。而A-(B C)= (A-B) (A-C)， 因为A B C， 所以A=(A-B) (A-C)。

13. (A-B) (B-A)=A B=Ф。 证明：

因为(A-B) (B-A)=A，所以B-A A。但(B-A) A=Ф，故

B-A=Ф。

即B A，从而B=Ф（否则A-B A，从而与(A-B) (B-A)=A矛盾）。

因为B=Ф，所以A-B=A且B-A=Ф。从而(A-B) (B-A)=A。

14. (A-B)-C A-(B-C)。

证明： x (A-B)-C，有x A-B且x C，即x A，x B且x C。

从而x A，x B-C，故x A-(B-C)。从而(A-B)-C A-(B-C)。

15. P(A) P(B) P(A B)（P(S)表示S的幂集）。 证明：

C P(A) p(B)，有

C P(A)或C P(B)，所以C A或C B。

从而C A B，故C P(A B)。即P(A) P(B) P(A B)。

16. P(A) P(B)=P(A B)（P(S)表示S的幂集）。 证明：

C P(A) P(B)，有C P(A)且

C P(B)，所以C A且C B。

从而C A B，故C P(A B)。即P(A) P(B) P(A B)。

C P(A B)，有

C A B，所以C A且C B。

从而C P(A)且C P(B)，故C P(A) P(B)。即P(A B) P(A) P(B)。

故P(A B)=P(A) P(B)。

17. (A-B) B=(A B)-B当且仅当B=Ф。 证明：

当

B=Ф时，因为（A-B） B=(A-Ф) Ф=A，

(A B)-B=(A Ф)-Ф=A，所以(A-B) B=(A B)-B。

假设B≠Ф，则存在b B。因为b B且b A B， 用反证法证明。

所以b (A-B) B。而显然b (A B)-B。故这与已知(A-B) B=(A B)-B矛盾。

18. 列出下列二元关系的所有元素：

（1）A={0, 1, 2}，B={0, 2, 4}，R={<x, y>: x, y A B};

（2）A={1, 2, 3, 4, 5}, B={1, 2}，R={<x, y>: 2 x+y 4且x A且y b}; （3）A={1, 2, 3}，B={-3, -2, -1, 0, 1}，R={<x, y>: |x|=|y|且x A且y b}; 解：

（1）R={<0, 0>, <0, 2>, <2, 0>, <2, 2>}； （2）R={<1, 1>, <1, 2>, <2, 1>, <2, 2>, <3, 1>}； （3）R={<1, 1>, <1, -1>, <2, -2>, <3, -3>}。

19. 对任意集合A, B，证明：若A A=B B，则A=B。 证明：

若B=Ф，则B B=Ф。从而A A =Ф。故A=Ф。从而B=A。 若B≠Ф，则B B≠Ф。从而A A≠Ф。

对 x B, <x, x> B B。因为A A=B B，则<x, x> A A。从而x A。故B A。

同理可证，A B。 故B=A。

20. 对任意集合A, B，证明：若A≠Ф，A B=A C，则B=C。 证明：

若B=Ф，则A B=Ф。从而A C = 。因为A≠Ф，所以C=Ф。即B=C。若B≠Ф，则A B≠Ф。从而A C≠Ф。

对 x B，因为A≠Ф，所以存在y A，使<y, x> A B。因为A B=A C，则<y, x> A C。从而x C。故B C。

同理可证，C B。 故B=C。

21. 设A={a, b}， B={c}。求下列集合： （1）A {0, 1} B； （2）B2 A； （3）(A B)2； （4）P(A) A。 解：

（1）A {0, 1} B={<a, 0, c>, <a, 1, c>, <b, 0, c>, <b, 1, c>}； （2）B2 A={<c, c, a>, <c, c, b>}；

（3）(A B)2={<a, c, a, c>, <a, c, b, c>, <b, c, a, c>, <b, c, b, c>}； （4）P(A) A={<Ф, a>, <Ф, b>, <{a}, a>, <{a}, b>, <{b}, a>, <{b}, b>, <a, a>, <a, b>}。

22. 设全集U={a, b, c, d, e}, A={a, d}, B={a, b, c}, C={b, d}。求下列各集合：

（1）A B C ； （2）(A B C) ； （3）(A B ) C； （4）P(A)-P(B)； （5）(A-B) (B-C)； （6）(A B) C。 解 ：

（1）A B C={a}； （2）(A B C) ={a, b, c, d, e}； （3）(A B ) C ={b, d}； （4）P(A)-P(B)={{d}, {a, d}}； （5）(A-B) (B-C)={d, c, a}； （6）(A B) C ={b, d}。

23. 设A, B, C是任意集合，证明或否定下列断言： （1）若A B，且B C，则A C； （2）若A B，且B C，则A C； （3）若A B，且B C，则A C； （4）若A B，且B C，则A C。 证明：

（1）成立。

对 x A，因为A B，所以x B。又因为B C，所以x C。即A C。

（2）不成立。反例如下：A={a}，B={a, b}，C={a, b, c}。虽然A B，且B C，但A C。

（3）不成立。反例如下：A={a}，B={{a}, b}，C={{{a}, b}, c}。虽然A B，且B C，但A C。

（4）成立。因为A B，且B C，所以A C。

24. A上的任一良序关系一定是A上的全序关系。 证明：

a，b∈A，则{a, b}是

A的一个非空子集。 ≤是A上的良序关系，

{a, b}有最小元。若最小元为a，则a≤b；否则b≤a。从而≤为A上的

的全序关系。

25. 若R和S都是非空集A上的等价关系，则R S是A上的等价关系。 证明：

a∈A，因为

R和S都是A上的等价关系，所以aRa且aSa。故

aR Sa。从而R S是自反的。

a, b∈A，aR Sb，即aRb

且aSb。因为R和S都是A上的等价

关系，所以bRa且bSa。故bR Sa。从而R S是对称的。

a, b, c∈A，aR Sb

且bR Sc，即aRb，aSb，bRc且bSc。因为

R和S都是A上的等价关系，所以aRc且aSc。故aR Sc。从而R S是传递的。

故R S是A上的等价关系。

26. 设R A×A，则R自反 IA R。

证明：

x A， R是自反的， xRx。即<x, x> R，故IA R。 x A， IA R， <x, x> R即xR，故R是自反的。

27. 设A是集合，R A×A，则R是对称的 R=R-1。 证明：

即<y, x> R，故<x, y> R 。 R是对称的， yRx。 <x, y> R ，从而R R-1。

反之 <y, x> R-1，即<x, y> R 。即<y, x> R， R是对称的， yRx。R-1 R。

故R=R-1。

x，y A，若<x, y> R ，即<y, x> R。 R=R， <y, x> R。

-1

-1

-1

即yRx，故R是对称的。

28. 设A, B, C和D均是集合，R A×B，S B×C，T C×D，则 （1）R (S T)=(R S) (R T)； （2）R (S T) (R S) (R T)。 证明：

（1） <x, z> R (S T)，则由合成关系的定义知 y B，使得<x, y> R且<y, z> S T。从而<x, y> R且<y, z> S或<x, y> R且<y, z> T，即<x, z> R S或<x, z> R T。故<x, z> (R S) (R T) 。从而R (S T) (R S) (R T)。

同理可证(R S) (R T) R (S T)。 故R (S T)=(R S) (R T)。

（2） <x, z> R (S T)，则由合成关系的定义知 y B，使得<x, y> R且<y, z> S T。从而<x, y> R且<y, z> S且<y, z> T，即<x,

z> R S且<x, z> R T。故<x, z> (R S) (R T)。从而R (S T) (R S) (R T)。

29. 设(A, ≤)为偏序集，Ф≠B A，若B有最大（小）元、上（下）确界，则它们是惟一的。 证明：

设a, b都是B的最大元，则由最大元的定义a b，b a。 是A上的偏序关系， a=b。即B如果有最大元则它是惟一的。

30. 设A={1, 2, 3}，写出下列图示关系的关系矩阵，并讨论它们的性质：

1

2 解：

000 101（1）R={(2, 1>, <3, 1>, <2, 3>}；Mr= ；它是反自反的、反 100

对称的、传递的；

（2）R={<1, 2>, <2, 1>, <1, 3>, <3, 1>, <2, 3>, <3, 2>}；

011

Mr= 101 ；它是反自反的、对称的；

110

011

（3）R={<1, 2>, <2, 1>, <1, 3>, <3, 3>}；Mr= 100 ；它既不是

001

自反的、反自反的，也不是对称的、反对称的、传递的。

31. 设A={1, 2, …, 10}。下列哪个是A的划分？若是划分，则它们诱导的等价关系是什么？

（1）B={{1, 3, 6}, {2, 8, 10}, {4, 5, 7}}； （2）C={{1, 5, 7}, {2, 4, 8, 9}, {3, 5, 6, 10}}； （3）D={{1, 2, 7}, {3, 5, 10}, {4, 6, 8}, {9}}。 解：

（1）和（2）都不是A的划分。 （3）是A的划分。其诱导的等价关系是

IA {<1, 2>, <2, 1>, <1, 7>, <7, 1>, <2, 7>, <7, 2>, <3, 5>, <5, 3>, <3, 10>, <10, 3>, <10, 5>, <5, 10>, <4, 6>, <6, 4>, <4, 8>, <8, 4>, <6, 8>, <8, 6>}。

32. R是A={1, 2, 3, 4, 5, 6}上的等价关系，

R=IA {<1, 5>, <5, 1>, <2, 4>, <4, 2>, <3, 6>, <6, 3>} 求R诱导的划分。 解：

R诱导的划分为{{1, 5}, {2, 4}, {3, 6}}。

33. A上的偏序关系 的Hasse图如下。

（1）下列哪些关系式成立：a b，b a，c e，e f，d f，c f； （2）分别求出下列集合关于 的极大（小）元、最大（小）元、上（下）界及上（下）确界（若存在的话）：

（a）A； （b）{b, d}； （c）{b, e}； （d）{b, d, e}。 e f

c