《离散数学》期末复习题答案 - 53551553740738151 联系客服

发布时间 : 星期五 文章《离散数学》期末复习题答案 - 53551553740738151更新完毕开始阅读ff6b9ed84b7302768e9951e79b89680202d86b20

《离散数学》期末复习题参考答案

一、填空题(每空1分,共20分)

1、集合A上的偏序关系的三个性质是自反性、反对称性和传递性。 2、一个集合的幂集是指该集合所有子集的集合。

3、集合A={b,c},B={a,b,c,d,e},则A?B={a,b,c,d,e}。 4、集合A={1,2,3,4},B={1,3,5,7,9},则A?B={1,3}。 5、若A是2元集合, 则 2A 有 4 个元素。

6、集合 A={1,2,3},A上的二元运算定义为:a* b = a和b两者的最大值,则2*3= 3 。 7、设A={a, b,c,d}, 则∣A∣= 4 。

8、对实数的普通加法和乘法, 0 是加法的幂等元, 1 是乘法的幂等元。 9、设a,b,c是阿贝尔群的元素,则-(a+b+c)=(-a)+( -b)+( -c)。

10、一个图的哈密尔顿路是一条通过图中所有结点一次且恰好一次的路。

11、不能再分解的命题称为原子命题,至少包含一个联结词的命题称为复合命题。 12、命题是能够表达判断(分辩其真假)的陈述语句。

13、如果p表示王强是一名大学生,则┐p表示王强不是一名大学生。 14、与一个个体相关联的谓词叫做一元谓词。 15、量词分两种:全称量词和存在量词。

16、设A、B为集合,如果集合A的元素都是集合B的元素,则称A是B的子集。 17、集合上的三种特殊元是单位元、零元及可逆元。

18、设A={a, b},则 ρ(A) 的四个元素分别是:空集,{a},{b},{a, b}。 19、代数系统是指由集合及其上的一元或二元运算符组成的系统。

20、设是代数系统,其中是*1,*2二元运算符,如果*1,*2都满足交换律、结合律,并且*1和*2满足吸收律,则称是格。

21、集合A={a,b,c,d},B={b },则A \\ B={ a, c,d }。 22、设A={1, 2}, 则∣A∣= 2 。

23、在有向图中,结点v的出度deg+(v)表示以v为起点的边的条数,入度deg-(v)表示以v为终点的边的条数。

24、一个图的欧拉回路定义为一条通过图中所有边一次且恰好一次的回路。 25、不含回路的连通图是树。

26、不与任何结点相邻接的结点称为孤立结点。

27、推理理论中的四个推理规则是全称指定规则 (US规则)、全称推广规则 (UG规则)、存在指定规则 (ES规则) 、存在推广规则 (EG规则)。

二、判断题(每题2分,共20分)

1、空集是唯一的。√

2、对任意的集合A,A包含A。√

3、恒等关系不是对称的,也不是反对称的。× 4、集合{1,2,3,3}和{1,2,2,3}是同一集合。√

5、图G中,与顶点v关联的边数称为点v的度数,记作deg(v)。√ 6、在实数集上,普通加法和普通乘法不是可结合运算。×

7、对于任何一命题公式,都存在与其等价的析取范式和合取范式。√

8、设(A,*)是代数系统,a∈A,如果a*a=a,则称a为(A,*)的等幂元。√ 9、设f:A→B, g:B→C。若f,g都是双射,则gf不是双射。× 10、无向图的邻接矩阵是对称阵。√

11、一个集合不可以是另一个集合的元素。×

12、映射也可以称为函数,是一种特殊的二元关系。√ 13、群中每个元素的逆元都不是惟一的。× 14、<{0,1,2,3,4},MAX,MIN>是格。√ 15、树一定是连通图。√ 16、单位元不是可逆的。×

17、一个命题可赋予一个值,称为真值√。

18、复合命题是由连结词、标点符号和原子命题复合构成的命题。√ 19、任何两个重言式的合取或析取不是一个重言式。×

20、设f:A→B, g:B→C。若f,g都是满射,则g?f不是满射。× 21、集合{1,2,3,3}和{1,2,3}是同一集合。√ 22、零元是不可逆的√。

23、一般的,把与n个个体相关联的谓词叫做一元谓词×。 24、“我正在说谎。”不是命题。√

25、用A表示“是个大学生”,c表示“张三”,则A(c):张三是个大学生。√ 26、设F={<3,3>,<6,2>},则 F-1 ={<6,3>,<2,6>}。× 27、欧拉图是有欧拉回路的图。√

28、设f:A→B, g:B→C。若f,g都是单射,则g?f也是单射。√

三、计算题(每题10分,共40分)

1、设A={c,d}, B={0,1,2},则A×B={,,,,,},B×A= {<0,c>,<0,d>,<1,c>,<1,d>,<2,c>,<2,d>}。

2、A = {a,b,c},B = {1,2},A×B = {a,b,c} ×{1,2} = {,,,,,}。 3、A = {a,b,c},A×A = {a,b,c} ×{a,b,c} =

{,,,,,,,,}。 4、符号化命题“如果2大于3,则2大于4。”。

设 L(x,y):x大于y, a:2, b:3, c:4,则命题符号化为L(a,b)→L(a,c)。 5、符号化命题“并不是所有的兔子都比所有的乌龟跑得快”。

设F(x):x是兔子。G(x):x是乌龟。H(x,y):x比y跑得快。该命题符号化为:??x?y(F(x)∧G(y)→H(x,y))。

6、符号化命题“2是素数且是偶数”。

设 F(x):x是素数。 G(x):x是偶数。 a: 2,则命题符号化为F(a)∧G(a)。 7、设A={a,b,c,d},R是A的二元关系,定义为:R={,,,, ,,, },写出A上二元关系R的关系矩阵。 解:R的关系矩阵为:

?1?1?1?1?101100010?0?0?0??

8、设A={1,2,3,4},R是A的二元关系,定义为:R={<1,1>,<1,2>,<2,1>,<3,2>, <3,1>,<4,3>,<4,2>,

<4,1>},写出A上二元关系R的关系矩阵。 解:R的关系矩阵为:

?1?1?1?1?101100010?0?0?0??

9、设有向图G如下所示,求各个结点的出度、入度和度数。

deg(v1)=3,deg+(v1)=1,deg-(v1)=2; deg(v2)=deg+(v4)=deg-(v2)=0;

deg(v3)=3,deg+(v3)=2,deg-(v3)=1; deg(v4)=2,deg+(v4)=1,deg-(v4)=1;

10、设有向图G如下所示,求各个结点的出度、入度和度数。

答:

deg(v1)=3,deg+(v1)=2,deg-(v1)=1; deg(v2)=3,deg+(v2)=2,deg-(v2)=1; deg(v3)=5,deg+(v3)=2,deg-(v3)=3; deg(v4)=deg+(v4)=deg-(v4)=0;

deg(v5)=1,deg+(v5)=0,deg-(v5)=1;

11、设无向图G如下所示,求它的邻接矩阵。

?0?1A(G)???0??1101??010? ?101?010?

12、求命题公式┐(p∧┐q)的真值表。 p q ┐q p∧┐q ┐ (p∧┐q) 0 0 1 1 0 1 0 1 1 0 1 0 0 0 1 0 1 1 0 1 13、设<2x+y, 5>=<10, x-3y>,求x,y。 解:由定理列出如下方程组:

?2x?y?10 ??x?3y?5求解得x=5,y=0。 14、R1、R2是从{1, 2, 3, 4, 5}到{2, 4, 6}的关系,若R1={<1, 2>, <3, 4>, <5, 6>},R2={<1, 4>, <2, 6>},计算domR1,ranR1,fldR1,domR2,ranR2,fldR2。

解:domR1={1, 3, 5},ranR1={2, 4, 6},fldR1=dom R1∪ran R1={1, 2, 3, 4, 5, 6}; domR2={1, 2},ranR2={4, 6},fldR2=dom R2∪ran R2={1, 2, 4, 6}。

15、设A={1, 2, 3, 4, 5},B={3, 4, 5}, C={1, 2, 3},A到B的关系R={|x+y=6},B到C的关系S={|y-z=2},求R?S。

解:R={<1, 5>, <2, 4>, <3, 3>}, S={<3, 1>, <4, 2>, <5, 3>},从而R?S={<1, 3>, <2, 2>, <3, 1>} 或者因<1, 5>∈R,<5, 3>∈S,所以<1, 3>∈ R?S;因<2, 4>∈R,<4, 2>∈S,所以<2, 2> ∈R?S;因<3, 3>∈R,<3, 1>∈S,所以<3, 1> ∈R?S;从而R?S={<1, 3>, <2, 2>, <3, 1>} 16、集合A={a, b, c},B={1, 2, 3, 4, 5},R是A上的关系,S是A到B的关系。R={, , , , },S={, , , , },求R?S,S–1?R–1 R?S={, , , , , , } (R?S)-1={<1, a>, <4, a>, <5, a>, <2, b>, <2, c>, <4, c>, <5, c>} –

R1={, , , , }, S–1={<1, a>, <4, a>, <2, b>, <4, c>, <5, c>}

S–1?R–1={<1, a>, <2, b>, <2, c>, <4, a>, <4, c>, <5, a>, <5, c>}。

17、A={1, 2, 3, 4, 5, 6},D是整除关系,画出哈斯图并求出最小元、最大元、极小元和极大元。 解:

4 6 2 5 1 3 1是A的最小元,没有最大元,1是极小元,4、5、6都是A的极大元。

18、设集合A={a,b,c},A上的关系R={, , },求R的自反、对称、传递闭包。 r(R)={,,,,} s(R)={,,,,} t(R)={,,,}

19、求下图中顶点v0与v5之间的最短路径。