离散数学古天龙-1-4章答案

P20

1.用枚举法写出下列集合。 2大于5小于13的所有偶数。 ○A={6,8,10,12} 520的所有因数 ○

A={1,2,4,5,10,20} 6小于20的6的正倍数 ○

A={6,12,18}

2.用描述法写出下列集合 3能被5整除的整数集合 ○A{5x|x是整数}

4平面直角坐标系中单位圆内的点集 ○

A{|x2+y2≤1} 4.求下列集合的基数 1 9 ○3 1 ○7 3 ○8 2 ○10 1 ○

6.求下列集合的幂集 6{1，{2}} ○

解：{空集，{1}，{{2}}，{1，{2}}} 7 解：{空集，{空集}，{a}，{空集，a}} ○

9 解：{空集，{{1，2}}，{{2}}，{{1，2}，{2}}} ○

15.设全集U={1，2，3,4,5}，集合A={1，4}，B={1，2，5}， C={2，4}，确定下列集合。 2 {1，3,5} ○

3 {1，4,} ○

8 {5} ○

9 {空集，{1}，{2}，{4}，{1，4}，{2，4}} ○

18.对任意集合A，B和C，证明下列各式 2（A-(BUC)）=((A-B)-C) ○

证：（A-(BUC)）=A∩~(BUC)=A∩(~B∩~C) ((A-B)-C)=(A∩~B)∩~C=A∩~B∩~C 所以 （A-(BUC)）=((A-B)-C)

3（A-(BUC)）=((A-C)-B ○

证：（A-(BUC)）=A∩~(BUC)=A∩~B∩~C

((A-C)-B)=(A∩~C)∩~B

所以 （A-(BUC)）=((A-C)-B

5P(A)UP(B)≤P(AUB) 原题有错 （注这里○5○6中的“≤”代表包含于符号） ○

证：任取C∈P（A）UP(B)由定义 C∈P（A）或C∈P（B）

若C∈P（A），则C≤A,则C≤AUB 若C∈P(B)，则C≤B,则C≤AUB 故C≤AUB，即C∈P(AUB) 证毕

6P(A)∩P(B)=P(A∩B) ○

证：先证P(A)∩P(B)≤P(A∩B)

任取 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) 再证P(A∩B)≤P(A)∩P(B) 任取C∈P(A∩B),即C=A∩B

C≤A,且C≤B,C∈P(A)且C∈P(B) 所以C∈P(A)∩P(B) 得证

21.用集合表示图1.7中各阴影部分。 a. (B∩C)-(A∩B∩C) ; b. b.(A∩B) -(A∩B∩C) ; c. U-(AUBUC) ; d .B-((A∩B)U(B∩C)); e .A∩B∩C

27.某班有25个学生，其中14人会打篮球，12 人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。已知6个会打网球的人都会打篮球或排球，求该班同学中不会打球的人数。

解：设 A={x|x会打篮球}，B={x|x会打排球}，C={x|x会打网球} 由题意知 |A|=14 ,|B|=12，|C|=6 ,|A∩B|=6，|A∩C|=5， |A∩B∩C|=2，|C∩(AUB)|=6，

|C∩(AUB)|=|(C∩A)U(C∩B)|=|C∩A|+|C∩B|-|C∩(AUB)|=6, |B∩C|=6+|A∩B∩C|-|A∩C|=3,

所以 |AUBUC|=|A|+|B+|C|-|A∩B|-|B∩C|-(|B∩C|+|A∩B∩C| =14+12+6-6-3-5+2=20

所以 该班同学中不会打球的人有25-20+5人。

30.假设在“离散数学”课程的第一次考试中14个学生得优，第二次考试中18个学生得优。如果22个学生在第一次或第二次考试得优，问有多少学生两次考试都得优。 解：设 A={x|x第一次得优的同学}，B={x|x第二次得优的同学}

由已知：|A|=14，|B|=18,|AUB|=22， 由 |AUB|=|A|+|B|-|A∩B|=22 所以 |A∩B|=32-22=10

两次考试都得优的有10人。

3.设集合A={1,23，}，B={1,3,5}和C={a,b}。求如下笛儿卡积。 ②、（A×C）∩（B×C）

（A×C）∩(B×C)＝{<1,a>，<3,a>,<1,b>,<3,b>}

③、(A∪B)×C＝{<1,a>,<1,b>,<2,a>,<2,b>,<3,a>,<3,b>,<5,a>,<5,b>}

4.对于集合A和B,证明。

①（A∩B）×C＝(A×C)∩(B×C) 证：

对任意∈(A∩B)×C,由笛儿卡积定义，

有x∈(A∩B),y∈C.那么x∈A且x∈B，由笛儿卡积定义， 故 ∈A×C (x,y)∈B×C ∴ ∈(A×C)∩(B×C)

故 （A∩B）×C ?(A×C)∩(B×C)

对任意∈(A×C)∩(B×C)

由交集知，∈A×C,且∈B×C，由笛儿卡积定义， x∈A,y∈C,且x∈B,y∈C

∴x∈A∩B,y∈C. 由笛儿卡积定义知，∈(A∩B) 故 （A×C∩(B×C) ?(A∩B)×C, 证毕

②(A∪B)×C＝(A×C)∪(B×C)

证： 任取 ∈(A∪B)×C,由笛儿卡积定义知， x∈A∪B, y∈C, 故∈A×C或∈B×C

∴∈(A×C∪(B×C),

∴(A∪B)×C?(A×C)∪(B×C)

任取∈(A×C)∪(B×C),由笛儿卡积定义知， ∈A×C或∈B×C,由笛儿卡积定义知， x∈A或x∈B, y∈C,

∴x∈A∪B,y∈C,由笛儿卡积定义知， ∈(A∪B)×C

∴(A×C)∪(B×C)?(A∪B)×C 证毕

5.对于集合A={1,2,3}和B={2,3,4,6}，求 ③从A到B的整除关系

R={<1,2>,<1,3>,<1,4>,<1,6>,<2,2>,<2,4>,<2,6>,<3,3>,<3,6>} R={|x∈A, y∈B, x能整除y} ⑥从B到A的整除关系 R={<2,2>,<3,3>}

R={|x∈B, y∈A, x能整除y }

6.对于集合A={1,2,3,4,6,8,12}， 求 ①A上的小于等于关系

R={<1,1>,<1,2>,<1,3>,<1,4>,<1,6>,<1,8>,<1,12>, <2,2>,<2,3>,<2,4>,<2,6>,<2,8>,<2,12>, <3,3>,<3,4>,<3,6>,<3,8>,<3,12>, <4,4>,<4,6>,<4,8>,<4,12>, <6,6>,<6,8>,<6,12>, <8,8>,<8,12>, <12,12>}

⑤A上的不等于关系

R={|x∈A, y∈A , x≠y}

R={<1,2>,<1,3>,<1,4>,<1,6>,<1,8>,<1,12>, <2,1>,<2,3>,<2,4>,<2,6>,<2,8>,<2,12>, <3,1>,<3,2>,<3,4>,<3,6>,<3,8>,<3,12>, <4,1>,<4,2>,<4,3>,<4,6>,<4,8>,<4,12>, <6,1>,<6,2>,<6,3>,<6,4>,<6,8>,<6,12>, <8,1>,<8,2>,<8,3>,<8,4>,<8,6>,<8,12>,

<12,1>,<12,2>,<12,3>,<12,4>,<12,6>,<12,8>}

7.对于集合A={a,b,c}和B={{a},{a,b},{a,c},{b,c}}, 求 ①从P(A)到B的包含关系

R＝{|x∈P(A) x∈B, x≤y }

P(A)＝{,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}

R={<,{a}>,<,{a,b}>,<,{a,c}>,<,{b,c}><{a},{a}>,<{a},{a,b}>,

<{a},{a,c}>,<{b},{a,b}>,<{b},{b,c}>,<{c},{a,c}>,<{c},{b,c}>,<{a,b},{a,b}>,<{a,c},{a,c}>,<{b,c},{b,c}>}

8.对于集合A={3,5,7,9}和B={2,3,4,6,8,10}，求关系矩阵 ③、从A到B的整除关系 ┏ 0 1 0 1 0 0 ┓ ┃ 0 0 0 0 0 1 ┃ MR＝ ┃ 0 0 0 0 0 0 ┃ ┗ 0 0 0 0 0 0 ┛

9.对于集合A={2,3,4,6,7,8,10}，求如下关系的关系矩阵 ②A上的大于关系

┏ 0 0 0 0 0 0 0 ┓ ┃ 1 0 0 0 0 0 0 ┃ ┃ 1 1 0 0 0 0 0 ┃ MR＝┃ 1 1 1 0 0 0 0 ┃

┃ 1 1 1 1 0 0 0 ┃ ┃ 1 1 1 1 1 0 0 ┃ ┗ 1 1 1 1 1 1 0 ┛

14.设A={a,b,c,d,e,f,g},其中a,b,c,d,e,f和g分别表示7人，且a,b和c都是18岁，

d和e都是21岁，f,和g都是23岁，试给出A上的同龄关系，并用关系矩阵和关系图表示 解：

R＝{,,,,,,

,,,,,, ,,,} ┏ 1 1 1 0 0 0 0 ┓

┃ 1 1 1 0 0 0 0 ┃ c ┃ 1 1 1 0 0 0 0 ┃ MR＝┃ 0 0 0 1 1 0 0 ┃

┃ 0 0 0 1 1 0 0 ┃ a b ┃ 0 0 0 0 0 1 1 ┃ ┗ 0 0 0 0 0 1 1 ┛

g

g P69

15.判断集合A={a,b,c}上的如下关系所具有的性质。 ① R1={,,,,,} 自反性、反对称性、传递性

④ R4={,,,,} 自反性、对称性、传递性

⑤ R5=A×A

对称性、自反性、传递性

⑥ R6=

自反性、对称性、传递性

16.判断集合A={3,5,6，7,10,12}上的如下关系所具有的性质。 ① A上的小于等于关系

自反性、反对称性、传递性

② A上的恒等关系

自反性、对称性、反对称性、传递性

e f

19.对于图2.16中给出的集合A={1，2,3}上的关系，写出相应的关系表达式和关系矩阵，并分析他们各自具有的性质。

R2={<1,1>,<3,3>,<1,2>,<2,1>,<2,3>,<3,2>,<1,3>,<3,1>} ┏ 1 1 1 ┓ 1 MR2= ┃ 1 0 1 ┃ ┗ 1 1 1 ┛ 2 （对称性） 3 R2

R11={<1,1>,<2,2>,<3,3>,<1,2>,<2,1>,<2,3>,<3,2>}

1 ┏ 1 1 0 ┓ MR11= ┃ 1 1 1 ┃ ┗ 0 1 1 ┛ 2 3 （自反性、对称性 ） 25.对于集合A={a,b,c}到集合B={1,2}的关系； R={,,}和S={,,} 求R∪S,R∩S,R﹣S,S﹣R,~R和~S。 解：

R∪S={,,,,}; R∩S={,}; R﹣S={}; S﹣R={};

~R=A×B－R={,,}; ~S=A×B－S={,,}.

27.对于集合A={1,2,3,4,5,6}上的关系R={|(x-y)2∈A}，S={|y是x的倍数}和 T={|x整除y，y是素数}，试写出各关系中的元素，各关系的关系矩阵和关系图， 并计算下列各式。 解：

R={<1,3>,<2,1>,<1,2>,<2,3>,<2,4>,<3,1>,<3,2>, <3,4>,<3,5>,<4,2>,<4,3>,<4,5>,<4,6>, <5,3>,<5,4>,<5,6>,<6,4>,<6,5>}; S={<1,1>,<1,2>,<1,3>,<1,4>,<1,5>,<1,6> ,<2,2>,<2,4>,<2,6> ,<3,3>,<3,6>

,<4,4>,<5,5>,<6,6>};

T={<1,1>,<1,2>,<1,3>,<1,5> ,<2,2>,<3,3>,<5,5>}

┏ 0 1 1 0 0 0 ┓ R的关系图： ┃ 1 0 1 1 0 0 ┃ 1 2 MR=┃ 1 1 0 1 1 0 ┃ ┃ 0 1 1 0 1 1 ┃

┃ 0 0 1 1 0 1 ┃ 6 ┗ 0 0 0 1 1 0 ┛

4 3 5

其余略；

① R·S={<1,2>,<1,4>,<1,6>,<1,3>,

<2,1>,<2,2>,<2,3>,<2,4>,<2,5>,<2,6>, <3,1>,<3,2>,<3,3>,<3,4>,<3,5>,<3,6>, <4,2>,<4,4>,<4,3>,<4,5>,<4,6>, <5,3>,<5,6>,<5,4>, <6,4>,<6,5>} ④ (R∩T)·S

R∩T={<1,2>,<1,3>}

(R∩T)·S={<1,2>,<1,4>,<1,6>,<1,3>}

32.对于集合A={a,b,c}上的如下关系，求各个关系的各次幂。 ① R1={,,}

R1o={,,} ┏ 1 0 0 ┓ MR1o=┃ 0 1 0 ┃ ┗ 0 0 1 ┛

┏ 1 0 0 ┓ ┏ 1 0 0 ┓ ┏ 1 0 0 ┓

MR1= ┃ 1 0 0 ┃ MR12=MR1·MR1=┃ 1 0 0 ┃=┃ 1 0 0 ┃=MR1 ┗ 0 0 0 ┛ ┗ 0 0 0 ┛ ┗ 0 0 0 ┛ ┏ 1 0 0 ┓

┃ 0 1 0 ┃ （n=0） ┗ 0 0 1 ┛ MR1的n次方=┏ 1 0 0 ┓

┃ 1 0 0 ┃ (n≥1) ┗ 0 0 0 ┛

③ R3={,,};

┏ 1 0 0 ┓ ┏ 0 1 1 ┓ MR3o=┃ 0 1 0 ┃ MR3=┃ 0 0 1 ┃ ┗ 0 0 1 ┛ ┗ 0 0 0 ┛

┏ 0 1 1 ┓ ┏ 0 1 1 ┓ ┏ 0 0 1 ┓ MR32=MR3·MR3=┃ 0 0 1 ┃ ·┃ 0 0 1 ┃ =┃ 0 0 0 ┃ ┗ 0 0 0 ┛ ┗ 0 0 0 ┛ ┗ 0 0 0 ┛ ┏ 0 0 1 ┓ ┏ 0 1 1 ┓ ┏ 0 0 0 ┓ MR33=MR32·MR3=┃ 0 0 0 ┃·┃ 0 0 1 ┃= ┃ 0 0 0 ┃ ┗ 0 0 0 ┛ ┗ 0 0 0 ┛ ┗ 0 0 0 ┛

┏ 0 0 0 ┓ ┏ 0 1 1 ┓ ┏ 0 0 0 ┓ MR3的4次方=MR33·MR3=┃ 0 0 0 ┃·┃ 0 0 1 ┃=┃ 0 0 0 ┃ ┗ 0 0 0 ┛ ┗ 0 0 0 ┛ ┗ 0 0 0 ┛

33.对于题29中的关系R和S，求下列各式，并给出所得关系的关系矩阵和关系图。 解： 题29中的关系R和S如下：

R={<1,2>,<2,1>,<2,3>,<3,4>,<4,2>}; S={<3,1>,<4,2>};

IA={<1,1>,<2,2>,<3,3>,<4,4>};

①r(R)=R∪IA={<1,1>,<2,2>,<3,3>,<4,4>,

<1,2>,<2,1>,<2,3>,<3,4>,<4,2>};

②S(R)=R∪R的负一次方={<1,2>,<2,1>,<2,3>,<3,2>, <3,4>,<4,3>,<4,2>,<2,4>};

③t(R)=R∪R2∪R3∪(R的4次方）

┏ 0 1 0 0 ┓ ┏ 0 1 0 0 ┓ ┏ 0 1 0 0 ┓ ┏ 1 0 1 0 ┓ MR=┃ 1 0 1 0 ┃ MR2=MR·MR=┃ 1 0 1 0 ┃·┃ 1 0 1 0 ┃=┃ 0 1 0 1 ┃

┃ 0 0 0 1 ┃ ┃ 0 0 0 1 ┃ ┃ 0 0 0 1 ┃ ┃ 0 1 0 0 ┃ ┗ 0 1 0 0 ┛ ┗ 0 1 0 0 ┛ ┗ 0 1 0 0 ┛ ┗ 1 0 1 0 ┛ ┏ 1 0 1 0 ┓ ┏ 0 1 0 0 ┓ ┏ 0 1 0 1 ┓ MR3=MR2·MR=┃ 0 1 0 1 ┃·┃ 1 0 1 0 ┃ =┃ 1 1 1 0 ┃ ┃ 0 1 0 0 ┃ ┃ 0 0 0 1 ┃ ┃ 1 0 1 0 ┃ ┗ 1 0 1 0 ┛ ┗ 0 1 0 0 ┛ ┗ 0 0 0 1 ┛

┏ 0 1 0 1 ┓ ┏ 0 1 0 0 ┓ ┏ 1 1 1 0 ┓ ┃ 1 1 1 0 ┃ ┃ 1 0 1 0 ┃ ┃ 1 1 1 1 ┃ (MR的4次方）=MR3·MR=┃ 1 0 1 0 ┃·┃ 0 0 0 1 ┃=┃ 0 1 0 1 ┃ ┗ 0 0 0 1 ┛ ┗ 0 1 0 0 ┛ ┗ 0 1 0 0 ┛ ┏ 1 1 1 1 ┓ ┃ 1 1 1 1 ┃

Mt(R)=┃ 1 1 1 1 ┃=A×A. ┗ 1 1 1 1 ┛

37.对于集合{0,1,2,3}上的如下关系，判定哪些关系式等价关系。 ① {<0,0>,<1,1>,<2,2>,<3,3>}; 是等价关系。

④ {<0,0>,<1,1>,<1,3>,<2,2>,<2,3>,<3,1>,<3,2>,<3,3>}; 自反性、对称性成立；

传递性不成立，因为<1,3>∈R,<3,2>∈R,但<1,2>?R.

38.对于人类集合上的如下关系，判定哪些是等价关系。 ①{|x与y有相同的父母}； 是等价关系。

∵∈R,满足自反性；

对称性：若∈R，则∈R,对称性成立。

传递性：若∈R∈R，则∈R,传递性成立。 ②{|x与y有相同的年龄} 是等价关系。

39.设R和S是集合A上的等价关系，判定下列各式中哪些是等价关系。 ① R∪S 解：

R∪S仍具有自反性和对称性，但不一定具备传递性，故不是等价关系。 ∵任意x∈A,有∈R,∈S,∴∈R∪S. 自反性成立。

对任意∈R∪S,则∈R或∈S.

由于R·S是等价关系，∴∈R或∈S,则∈R 对称性成立。

传递性不成立，反例：A{1,2,3}

R={<1,1>,<2,2>,<3,3>,<1,2>,<2,1>},S={<1,1>,<2,2>,<3,3>,<3,2>,<2,3>} ② R∩S

自反性：因为任意x∈A,有∈R,且∈S, 所以∈R∩S,自反性成立。

对称性：任取∈R∩S,故∈R,且∈S,由于R和S是等价关系， 故∈R且∈S,所以∈R∩S。

传递性：任取∈R∩S，∈R∩S，即∈R且∈S，∈R且∈S， 由于R和S是等价关系，所以∈R,且∈S, 所以∈R∩S,传递性成立。 ∴综上所述，R∩S是等价关系。

41.对于正整数集合上的关系R={<,>|a·b=c·d}，试证明R是等价关系。 自反性：任取a∈Z﹢,b∈Z+，∵ a·b=a·b， ∴<,>∈R，自反性成立。

对称性：任取<,>∈R，即a·b=c·d，c·d=a·b，故<,>∈R， 对称性成立。

传递性：任取<,>∈R，<,>∈R， ∴a·b=c·d，c·d=e·f，∴a·b=e·f， ∴<,>∈R,传递性成立。

45.对于题

37中的等价关系R，求集合A中各元素的等价类和

A的商集

解：

①[0]R=｛0｝ [1]R=｛1｝ [2]R=｛2｝ [3]R=｛3｝ A/R=｛｛0｝｛1｝｛2｝｛3｝｝

④不是等价关系

47.对于集合A=｛a,b,c,d,e,f,g｝的划分S=｛｛a,c,e｝｛b,d,｝｛f,g｝｝求划分S所对应的等价关系

解：

R=｛a,c,e｝×｛a,c,e｝U｛b,d｝×｛b,d｝U｛f,g｝×｛f,g｝

=

｛,,,,,,,,,,,,,,,,｝

52.画出如下集合A上整除关系的哈斯图

解：

①A=｛1,2,3,4,5,6,7,8｝

R=｛| x,y∈A,且x能被y整除｝

8

4

2 1

②A={1,2,3,5,7,11,13}

6

5 7

3 2 3 5 7 11 13

1

53.对于题52中关系①和②，求子集{1,2,3,5}和子集{2,3,7}的上

界，下界，上确界和下确界

解：

① 集合 {1,2,3,5} {2,3,7} ②

上界 无 无 下界 1 无 上确界 无 无 下确界 1 无 集合

上界 无 无 下界 1 无 上确界 无 无 下确界 1 无 {1,2,3,5} {2,3,7} 56.对于如图所示的集合A上的偏序关系所对应的哈斯图，求集合A的极大值，极小值，最大值和最小值

解：

h e

g f c b

极大值 a 极小值 最大值 最小值 b

a b a

⑦

极大值 g

b f

e d

b

c

a k

极小值 最大值 最小值 h

a,k h 无 P86

1.对于集合A={x,y,z}和B={1,2,3},判断下列A到B的关系哪些构成函数

①{,,,} 解：不是函数

②{,,} 解：是函数

③{,,} 解：是函数 ④{,} 解：不是函数

⑤{,,} 解：是函数

⑥{,,,,,} 解：不是函数

2.判断下列哪些是函数

①{|x∈R} 是函数

⑤{|x∈Z,y∈Z,x=y+1} 是函数

3.对于集合A={a,b,c},A到A可以定义多少个不同的函数

33=27

4.对于集合A={x,y,z},A×A到A可以定义多少个不同的函数

|A×A|=3×3

所以39

5.对于集合A={1,2,3}，A到A×A可以定义多少个不同的函数

|A×A|=9

所以93

8.下列哪些是单射函数，满射函数或双射函数

①f:Zf?Zf(Zf是正整数集合)，f(x)=3x; 所以是单射函数，不是满射，不是双射 ②f:Z?Z,f(x)=|x|;

所以不是单射函数，不是满射，不是双射 ③集合A={0,1,2,3}到B={0,1,2,3,4}的函数f, f(x)=x2;所以不是函数；

④f:R?R,f(x)=x+1

所以是单射函数，是满射，是双射 ⑤f:N?N?N,f(x)=

所以是单射函数，不是满射，不是双射 ⑥f:Z?N,f(x)=|2x|+1

所以不是单射函数，不是满射，不是双射

9.对于集合A和B，且|A|=m，|B|=n,问

①A到B可以定义多少个不同的函数？

nm

②A到B可以定义多少个不同的单射函数

mmCnAm（m≤n）

③A到B可以定义多少个不同的满射函数 ④A到B可以定义多少个不同的双射函数

m（m=n） Am14.对于集合A={a,b,c,d},B={1,2,3}和C={a,b,c}

计算如下函数f：A?B和g：B?C的复合函数f?g ①f={,,,},g={<1,a>,<2,b>,<3,d>}

f?g={,,,}

②f={,,,},g={<1,a>,<2,a>,<3,a>}

f?g={,,,}

③f={,,,},g={<1,b>,<2,b>,<3,b>}

f?g={,,,}

④f={,,,},g={<1,d>,<2,b>,<3,a>}

f?g={,,,}

16.对于集合A={a,b,c,d}和B={1,2,3,4},判断如下函数f:A?B的逆关系是否为函数

①f={,,,}

逆关系是函数

②f={,,,} 逆关系不是函数

③f={,,,} 逆关系是函数

④f={,,,} 逆关系是函数

18.对于函数f:Z?Z?Z?Z,f()=,证f是单射函数，满射函数

证明：

单射性，任取∈Z?Z ∈Z?Z

若≠，则有x1≠x2或y1≠y2

又f()= f()=

若f()= f()，即=

本文来源：https://www.bwwdw.com/article/4hmp.html