6离散数学(2)-2复习题

一、填空题

1．集合X={a，b，c，d}上二元关系R={，，，，，}，则R的自反闭包r(R)= _ ，对称闭包s(R)= _。

2．已知G=<{l，-1，i，-i}，·>(其中i=1，是数的乘法)是群，则-l的阶是_ _；i的阶是_ _。

3．设是群，则满足结合律和_ _；若｜S｜>l，S中不可能 有_ _ 。

4．写出如右有向图的一条初级回路：__ _，其长度是_ _。

5．设X，U，V，Y都是实数集，f1：X→U，且fl(x)→ex； f2：U→V，且f2(u)＝u (1+u)；f3：V→Y，且f3(v)=cosv。那么f3f2f1的定义域是_ _，而复合函数(f3f2f1)(x)= _ _。

6．对代数系统，其中*是S上的二元运算，若a，b∈S，且对任意的x∈S，都有a*x=x*a=x，b*x=x*b=b，则称a为运算“*”的_ _，称b为运算“*”的_ _。

7．一个_ _且_ _的无向图称为树。

8．设R为非空集合A上的二元关系，如果R具有自反性、_ _、_ _则称R为A上的一个偏序关系。

9．设x＝{1，3，5，9，15，45}，R是x上的整除关系，则R是x上的偏序，其最大元是_ _，极小元是_ _。 答案： 一、填空题

1．集合X={a，b，c，d}上二元关系R={，，，，

，}，则R的自反闭包r(R)= _RUIA_，对称闭包s(R)= _RU{，，，，，} _。

2．已知G=<{l，-1，i，-i}，·>(其中i=1，是数的乘法)是群，则-l的阶是_2_；i的阶是_4_。

3．设是群，则满足结合律和_消去律_；若｜S｜>l，S中不可能 有_零元_。

4．写出如右有向图的一条初级回路：__v2v3v2_，其长度是_2_。

5．设X，U，V，Y都是实数集，f1：X→U，且fl(x)→ex； f2：U→V，且f2(u)＝u (1+u)；f3：V→Y，且f3(v)=cosv。那么f3f2f1的定义域是_X_，而复合函数(f3f2f1)(x)= _ cosv（ex（1 + ex））_。

6．对代数系统，其中*是S上的二元运算，若a，b∈S，且对任意的x∈S，都有a*x=x*a=x，b*x=x*b=b，则称a为运算“*”的_幺元_，称b为运算“*”的_零元_。

7．一个_连通_且_无回路_的无向图称为树。

8．设R为非空集合A上的二元关系，如果R具有自反性、_反对称性_、_传递性_则称R为A上的一个偏序关系。

9．设x＝{1，3，5，9，15，45}，R是x上的整除关系，则R是x上的偏序，其最大元是_45_，极小元是_1_。

二、计算

1．设X={{{1，2}，{1}}，{1，0}}，求

X，X。

2．所有一元一次方程的解组成的集合。

3．在直角坐标系中，单位圆内的点集（包括单位圆周）。

4．在极坐标系中，单位圆外的点集（不包括单位圆周）。

5．设A={0,1}，B={1,2}，确定如下集合： a)、AB b)、A{1}B

6．设X={{{1，2}，{1}}，{1，0}}，求X，X。

7．设X={{{1，2}，{1}}，{1，0}}，求

8．根据有向图的邻接矩阵，写出该有向图的关系R，并求出关系R的自反闭包和对称闭包。1 10邻接矩阵：001

010

9．若集合A={a，{b，c}}的幂集为P(A)，集合B={ O / ，{ O / }}的幂集为P(B)， 求P(A)∩P(B)。

10．有6个村庄Vi，i=l，2，…，6欲修建道路使村村可通。现已有修建方案如下带权无向图所示，其中边表示道路，边上的数字表示修建该道路所需费用，问应选择修建哪些道路可使得任二个村庄之间是可通的且总的修建费用最低?要求写出求解过程，画出符合要求的最低费用的道路网络图并计算其费用。

11、已知集合A和B且|A|=n，|B|=m，求A到B的二元关系数是多少？A到B的函数数是多少？

12、75个儿童到公园游乐场，他们在那里可以骑旋转木马，坐滑行铁道，乘宇宙飞船，已知其中20人这三种东西都乘过，其中55人至少乘坐过其中的两种。若每样乘坐一次的费用是0.5元，公园游乐场总共收入70元，求有多少儿童没有乘坐过其中任何一种。

X，X。

13、已知A={1,2,3,4,5}和R={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>}，求r(R)、s(R)和t(R)。

14、已知：D=，V={1,2,3,4,5}，E={<1,2>,<1,4>,<2,3>,<3,4>,<3,5>,<5,1>}，求D的邻接距阵A和可达距阵P

15、求叶的权分别为2、4、6、8、10、12、14的最优二叉树及其权。（15分） 答案： 二、计算

1．设X={{{1，2}，{1}}，{1，0}}，求答案：

2．所有一元一次方程的解组成的集合。 答案：S

3．在直角坐标系中，单位圆内的点集（包括单位圆周）。 答案：S

4．在极坐标系中，单位圆外的点集（不包括单位圆周）。 答案：S

5．设A={0,1}，B={1,2}，确定如下集合： a)、AB b)、A{1}B 答案： a)、AB

6．设X={{{1，2}，{1}}，{1，0}}，求X，X。 答案：X={{1，2}，{1}，{1，0}}

7．设X={{{1，2}，{1}}，{1，0}}，求答案：

{0,1,1,1,0,2,1,2} {,|2X，X。

X==0 X={1}

{x|axb0,a0}。

{x,y|x2y21}。

1}。

b)、A{1}B{0,1,1,1,1,1,0,1,2,1,1,2}

X

X，X。

X={0，1，2}=3 X无定义。

8．根据有向图的邻接矩阵，写出该有向图的关系R，并求出关系R的自反闭包和对称闭包。1 邻接矩阵：00答案：关系R

9．若集合A={a，{b，c}}的幂集为P(A)，集合B={ O / ，{ O / }}的幂集为P(B)， 求P(A)∩P(B)。 答案：

10．有6个村庄Vi，i=l，2，…，6欲修建道路使村村可通。现已有修建方案如下带权无向图所示，其中边表示道路，边上的数字表示修建该道路所需费用，问应选择修建哪些道路可使得任二个村庄之间是可通的且总的修建费用最低?要求写出求解过程，画出符合要求的最低费用的道路网络图并计算其费用。 答案：

11、解：因为|P(A×B)|=2|A×B|=2|A||B|=2mn，所以A到B的二元关系有2mn个。因为|BA|=|B||A|=mn，所以A到B的函数mn个。

r(R) s(R)RR1001 1a0,a,{IxRca,b,b,c,c,b}

c,c,a,b,b,c,c,b}

c,b}

a,b,b,a,b,c,{a,a,b,b,{a,a,

12 解 设A、B、C分别表示骑旋转木马、坐滑行铁道、乘宇宙飞船的儿童组成的集合，|A∩B∩C|＝20，|A∩B|＋|A∩C|＋|B∩C|－2|A∩B∩C|＝55，|A|＋|B|＋|C|＝70/0.5＝140。

由容斥原理，得

|A∪B∪C|＝|A|＋|B|＋|C|―|A∩B|―|A∩C|―|B∩C|＋|A∩B∩C| 所以

|A∩B∩C|＝75－|A∪B∪C|＝75－(|A|＋|B|＋|C|)＋(|A∩B|＋|A∩

C|＋|B∩C|－2|A∩B∩C|)＋|A∩B∩C|＝75－140＋55＋20＝10 没有乘坐过其中任何一种的儿童共10人。

13 解：r(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<1,1>,<2,2>,<3,3>,<4,4>,<5,5>}

s(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<3,2>,<4,3>,<4,5>}

t(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<1,1>,<1,3>,<2,2>,<2,4>,<1,4>}

14 解：D的邻接距阵A和可达距阵P如下：

15 解：最优二叉树为

权＝148

0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0

1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1

A= 0 0 0 1 1 P= 1 1 1 1 1

三、证明

1．简单图的最大度小于结点数。

2．证明下面关于集合A和B的命题是相互等价的。 (a) AB (b) A∪B＝B (c) A∩B＝A

3、已知A、B、C是三个集合，证明(A∪B)－C＝(A－C)∪(B－C) 答案： 三、证明

1．简单图的最大度小于结点数。 答案：

证明：设简单图G有n个结点。对于任一结点u，由于G没有环和平行边，u至多与其余n-1个结点中的每一个有一条边相连接，即deg(u)(G)maxdeg(u)n1。

n-1，因此，

2．证明下面关于集合A和B的命题是相互等价的。 (a) AB (b) A∪B＝B (c) A∩B＝A 答案： 证明：通过证明（1）首先证明 已知

来说明它们是等价的。

，A的每个元素都是B中的元素，从集合运算的定义知

A∪B＝{x|x∈A或x∈B}＝{x|x∈B}＝B （2）再证明A∩B

＝A∩（A∪B）

＝（A∪Φ）∩（A∪B） ＝A∪（Φ∩B） ＝A∪Φ ＝A

（3）最后证明已知

。

已知A∪B＝B，等式两边同时与A求交仍然相等。

3、已知A、B、C是三个集合，证明(A∪B)－C＝(A－C)∪(B－C) 答案： 证明：因为

x∈(A∪B)－Cx∈(A∪B)－C

x∈(A∪B)∧xC (x∈A∨x∈B)∧xC (x∈A∧xC)∨(x∈B∧xC) x∈(A－C)∨x∈(B－C) x∈(A－C)∪(B－C)

所以，(A∪B)－C＝(A－C)∪(B－C)。