贵州大学离散数学试卷

贵州大学离散数学试卷一、选择题（每题1分，共10分）

1.下列哪个命题在逻辑上为真？

A.如果今天下雨，那么地面是湿的。

B.今天下雨且地面是干的。

C.如果今天不下雨，那么地面是干的。

D.今天不下雨且地面是湿的。

2.设集合A={1,2,3}，B={2,3,4}，则A∪B等于？

A.{1,2,3}

B.{2,3,4}

C.{1,2,3,4}

D.{1,4}

3.下列哪个是命题？

A.今天天气真好！

B.请你安静一点。

C.x+y=5。

D.这朵花很漂亮。

4.设命题p为“今天下雨”，q为“我带伞”，则“如果今天不下雨，那么我没有带伞”的符号表达式为？

A.¬p→¬q

B.p→q

C.¬q→¬p

D.q→p

5.下列哪个是图论中的基本概念？

A.群

B.环

C.序列

D.基数

6.设有向图G包含n个顶点，m条边，则G的邻接矩阵是一个？

A.n×n的矩阵

B.m×m的矩阵

C.n×m的矩阵

D.m×n的矩阵

7.下列哪个是树？

A.有环的图

B.没有环的连通图

C.有向图

D.无向图

8.设集合A有n个元素，则A的幂集有多少个元素？

A.n

B.2n

C.n!

D.2^n

9.下列哪个是等价关系？

A.大于关系

B.小于关系

C.相等关系

D.整除关系

10.设函数f:A→B，其中A和B都是有限集合，|A|=m，|B|=n，则f有多少个不同的同态？

A.m

B.n

C.m*n

D.m^n

二、多项选择题（每题4分，共20分）

1.下列哪些是命题逻辑的公理？

A.交换律

B.结合律

C.双重否定律

D.排中律

2.设集合A={a,b,c}，B={1,2}，下列哪些是A到B的函数？

A.f(a)=1,f(b)=1,f(c)=2

B.f(a)=2,f(b)=1,f(c)=1

C.f(a)=1,f(b)=2,f(c)=1

D.f(a)=2,f(b)=2,f(c)=2

3.下列哪些是图论中的基本概念？

A.路径

B.顶点

C.环

D.矩阵

4.设有向图G包含n个顶点，m条边，则G的邻接矩阵有什么性质？

A.对角线元素都为0

B.矩阵是方阵

C.矩阵是对称的

D.矩阵是可逆的

5.下列哪些是树？

A.有环的无向图

B.没有环的连通无向图

C.有向树

D.满足任何两个顶点之间都有唯一路径的无向图

三、填空题（每题4分，共20分）

1.若命题p为“今天是星期一”，q为“我上课”，则命题“如果今天不是星期一，那么我不上课”的符号表达式为：¬p→¬q。

2.设集合A={1,2,3}，B={a,b}，则从A到B的所有不同函数的个数为：2^3=8。

3.在图论中，一个无向图如果没有任何环，且任意两个顶点之间都存在路径，则称该图为：树。

4.设有向图G包含n个顶点，若G是强连通的，则对于任意的顶点u和v（u≠v），在G中存在从u到v的路径和从v到u的路径。

5.在集合论中，一个集合的所有子集的集合称为该集合的：幂集。

四、计算题（每题10分，共50分）

1.已知命题公式(p∧¬q)∨(¬p∧q)，请判断该命题公式是否为重言式，并给出证明。

2.设集合A={1,2,3}，B={a,b}，构造从A到B的所有不同函数，并说明共有多少个这样的函数。

3.给定一个无向图G，其顶点集V={v1,v2,v3,v4}，边集E={(v1,v2),(v2,v3),(v3,v4),(v4,v1)}。请画出该图，并判断它是否为树，说明理由。

4.设有向图G的邻接矩阵为：

```

0100

0010

0001

1000

```

请判断该图是否为强连通图，并说明理由。

5.设集合A={1,2,3,4}，B={a,b,c}。请构造一个从A到B的满射，并说明该满射的定义域和陪集的集合。

本专业课理论基础试卷答案及知识点总结如下

一、选择题答案及解析

1.A.如果今天下雨，那么地面是湿的。这是一个正确的逻辑命题，因为下雨会导致地面湿。

2.C.{1,2,3,4}。集合A和集合B的并集包含两个集合中的所有元素，不重复。

3.C.x+y=5。这是一个命题，因为它是一个可以判断真假的数学等式。

4.A.¬p→¬q。根据逆否命题的等价性，原命题和逆否命题是等价的。

5.A.群。群是图论中的一个基本概念，但更准确地说是代数结构。这里可能是个错误选项，应该是图的基本概念，如路径、环等。

6.A.n×n的矩阵。邻接矩阵是表示图的结构的一种矩阵，其大小等于顶点的数量。

7.B.没有环的连通图。树是图论中的一个基本概念，定义为没有环的连通图。

8.D.2^n。一个集合的幂集是其所有子集的集合，包括空集和集合本身，所以其大小为2的集合元素个数次方。

9.C.相等关系。相等关系是自反的、对称的、传递的，因此是等价关系。

10.D.m^n。一个函数从集合A到集合B的映射方式总数是B的集合元素个数次方，因为每个A中的元素都有B中元素的选择余地。

二、多项选择题答案及解析

1.A.交换律，B.结合律，C.双重否定律，D.排中律。这些都是命题逻辑的公理。

2.A.f(a)=1,f(b)=1,f(c)=2，B.f(a)=2,f(b)=1,f(c)=1，C.f(a)=1,f(b)=2,f(c)=1。这些都是从A到B的函数，因为每个A中的元素都映射到了B中的唯一元素。

3.A.路径，B.顶点，C.环。这些都是图论中的基本概念。

4.A.对角线元素都为0，B.矩阵是方阵。邻接矩阵的对角线元素为0（因为自我环边不存在），且矩阵的大小等于顶点的数量，所以是方阵。

5.B.没有环的连通无向图，D.满足任何两个顶点之间都有唯一路径的无向图。这些都是树的定义。

三、填空题答案及解析

1.¬p→¬q。这是根据逆否命题的等价性得到的。

2.2^3=8。A中有3个元素，每个元素有B中2个元素的选择余地，所以总共有8个不同的函数。

3.树。无环且连通的无向图。

4.是。因为对于任意的顶点u和v，都存在从u到v的路径和从v到u的路径。

5.幂集。一个集合的所有子集的集合。

四、计算题答案及解析

1.不是重言式。可以通过真值表来验证，该命题公式在至少一种情况下为假。

2.共有8个不同的函数。因为A中有3个元素，B中有2个元素，所以每个A中的元素都有2种选择，总共有2^3=8个不同的函数。

3.图G是一个环，不是树。因为树没有环，而该图中有环(v1,v2,v3,v4,v1)。

4.不是强连通图。因为有顶点对（如v1和v4）之间不存在路径。

5.一个满射可以是f(1)=a,f(2)=b,f(3)=c,f(4)=c。定义域是A，陪集的集合是{a},{b},{c}。

知识点分类和总结

集合论：集合的基本概念（如并集、交集、补集、幂集），函数（如满射、单射、双射），关系（如等价关系）。

命题逻辑：命题的基本概念（如命题变元、联结词、真值表），逻辑公式（如重言式、矛盾式），逻辑等价。

图论：图的基本概念（如顶点、边、路径、环、连通图），树（如二叉树、满二叉树），图矩阵表示（如邻接矩阵、可达矩阵）。

各题型所考察学生的知识点详解及示例

选择题：考察学生对基本概念和定理的理解，如集合运算、命题逻辑公理、图论基本概念等。

多项选择题：考察学生综合运用知识的能力，需要学生从多个选项中选择所有正确的答案。

填空题：考察学生对基本概念的精确记忆和表达，需要学生用简短的文字或符号填写答案。

计算题：考察学生运用所学知识解决具体问题的能力，需要学生进行计算、推理和证明。

示例：

选择题示例：判断“若p为真，则q也为真”的逆命题是否为真。答案：真。因为逆命题是“若q为真，则p也为真”，这与原命题等价。

多项选择题示例：判断哪些是图论中的基本概念。答案：顶点、边、