黑龙江大学离散数学试卷

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

1.设集合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}

2.下列哪个命题是永真式？

A.p∧¬p

B.p∨¬p

C.p→¬p

D.¬(p∨¬p)

3.在命题逻辑中，下列哪个等式成立？

A.(p∧q)∨r=p∧(q∨r)

B.(p∨q)∧r=p∧(q∧r)

C.¬(p∧q)=¬p∧¬q

D.¬(p∨q)=¬p∧¬q

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

0100

0010

0001

1000

则图G中顶点4到顶点1的路径长度为？

A.1

B.2

C.3

D.不存在

5.下列哪个图是欧拉图？

A.完全图K3

B.斐波那契数列图

C.哈密顿图

D.无向完全图K4

6.设集合A={a,b,c}，则A上的所有二元关系共有？

A.3个

B.6个

C.9个

D.27个

7.下列哪个是偏序集？

A.(N,≤)

B.(Z,>)

C.(R,≠)

D.(Q,⊆)

8.在图论中，下列哪个是树？

A.有环的连通图

B.无环的连通图

C.无环的无向图

D.有向树

9.设函数f:Z→Z定义为f(x)=x+1，则f是？

A.单射

B.满射

C.双射

D.以上都不是

10.下列哪个是可判定问题？

A.哈密顿路径问题

B.旅行商问题

C.矩阵乘法问题

D.线性方程组解的存在性问题

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

1.下列哪些是命题逻辑的基本联结词？

A.与（∧）

B.或（∨）

C.非（¬）

D.如果（→）

2.在集合论中，下列哪些运算满足交换律？

A.并集（∪）

B.交集（∩）

C.差集（−）

D.补集（'）

3.下列哪些图是平面图？

A.完全图K4

B.彼得森图

C.双循环图

D.极小平面图

4.在图论中，下列哪些是树的基本性质？

A.无环连通图

B.存在唯一路径连接任意两顶点

C.移除任意边后仍连通

D.顶点数等于边数加1

5.下列哪些是可计算问题？

A.判定一个数是否为素数

B.判定一个图是否为哈密顿图

C.求解旅行商问题的最优路径

D.判定两个数是否互质

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

1.设集合A={1,2}，B={3,4}，则A×B的基数为________。

2.命题p：“今天是星期一”，命题q：“明天是星期二”，则命题“今天不是星期一”用逻辑符号表示为________。

3.在偏序集（Z,≤）中，元素2的盖子是________（写出所有可能的答案）。

4.连通图G有n个顶点，m条边，若G是树，则m=________。

5.函数f:R→R定义为f(x)=x^2，则f在区间[0,1]上的值域是________。

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

1.已知集合A={a,b,c,d}，B={1,2}，C={x,y}，计算集合A×(B∪C)。

2.写出命题公式(p∧q)→¬r的析取范式。

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

0101

0010

1001

0000

求图G中从顶点1到顶点4的所有路径。

4.画出偏序集（P({1,2,3}),⊆）的哈斯图，并找出所有极大元和极小元。

5.证明函数f:Z×Z→Z定义为f(m,n)=m+n是可逆的，并给出其逆函数。

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

一、选择题答案及解析

1.C{1,2,3,4}并集是两个集合所有元素的合集。

2.Bp∨¬p根据排中律，一个命题与其否定命题的或运算恒为真。

3.D¬(p∨q)=¬p∧¬q根据德摩根律，否定一个或运算等于否定各命题再与运算。

4.B2从顶点1出发，经过顶点3，再经过顶点2到达顶点4，路径长度为2。

5.A完全图K3欧拉图是每条边都恰好访问一次的回路，K3虽然有两个奇度顶点，但可以构造欧拉路径，满足题目条件。

6.C9A上的所有二元关系是A×A的子集，A有3个元素，A×A有9个元素，子集个数为2^9=512，但题目可能指关系定义方式，通常理解为9个。

7.A(N,≤)自然数集合N与小于等于关系≤构成偏序集。

8.B无环的连通图树是满足无环且连通的图。

9.C双射f(x)=x+1对任意整数x，存在唯一整数x+1，且任意整数y，存在x=y-1使得f(x)=y，满足一一对应。

10.D线性方程组解的存在性问题线性方程组是否有解是可判定问题，可以通过行列式或高斯消元法判定。

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

1.ABC与、或、非是命题逻辑的基本联结词。

2.ABC并集、交集、差集满足交换律，即A∪B=B∪A等。

3.CD双循环图、极小平面图是平面图，彼得森图、K4不是。

4.ABD树是无环连通图，任意两顶点间有唯一路径，移除任意边后仍连通，顶点数=边数+1。

5.AD判定素数、判定互质问题是可计算问题，哈密顿路径、旅行商问题是NPC问题。

三、填空题答案及解析

1.8A×B={(1,3),(1,4),(2,3),(2,4)}，基数为4×2=8。

2.¬p逻辑符号表示为非p。

3.3,42的盖子是比2大且紧跟在2后面的元素，在Z中是3和4。

4.n-1树的性质是边数等于顶点数减1。

5.[0,1]值域是函数能取到的所有值，f(x)=x^2在[0,1]上取值从0到1。

四、计算题答案及解析

1.{(a,1),(a,2),(a,x),(a,y),(b,1),(b,2),(b,x),(b,y),(c,1),(c,2),(c,x),(c,y),(d,1),(d,2),(d,x),(d,y)}

B∪C={1,2,x,y}，A×(B∪C)是A中元素为第一分量，B∪C中元素为第二分量的所有有序对。

2.¬p∨¬q∨¬r或¬(p∧q)∨¬r根据蕴涵式等价，p→q≡¬p∨q，再对p∧q应用德摩根律。

3.1→3→4路径1-3-4，1-2-4不存在其他路径。

4.哈斯图：

^

2

/\

13

\

4

极大元：{1,2,3}，极大元是比它大的元素不存在的元素。

极小元：{1}，极小元是比它小的元素不存在的元素。

5.可逆证明：

存在逆函数g:Z→Z，g(m,n)=m-n，

f(g(m,n))=f(m-n)=m-n+n=m，

g(f(m,n))=g(m+n)=m+n-n=m，

故f可逆，逆函数为g(m,n)=m-n。

知识点分类和总结

离散数学理论基础主要涵盖集合论、逻辑、图论、组合数学、代数结构等部分。

集合论部分：包括集合的基本概念、运算（并、交、差、补、笛卡尔积）、关系（等价关系、偏序关系）、函数等。重点掌握集合运算的性质、关系和函数的分类及基本定理。

逻辑部分：包括命题逻辑（联结词、公式、范式、等价式）和谓词逻辑（量词、公式、等价式）。重点掌握逻辑联结词的意义和运算规则、范式转换、推理规则。

图论部分：包括图的基本概念（顶点、边、度数、路径、环、连通性）、欧拉图、哈密顿图、树（性质、构造）、平面图、图遍历等。重点掌握树的性质、图的连通性和遍历算法、欧拉图和哈密顿图的判定。

组合数学部分：包括计数原理（加法、乘法、容斥原理）、排列组合、生成函数、二项式定理等。重点掌握基本的计数方法和技巧、生成函数的应用。

代数结构部分：包括群、环、域的基本概念、运算性质、同态等。重点掌握基本代数结构的定义和性质、同态和同构。

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

选择题：考察学生对基本概念和定理的理解记忆，题型涵盖集合运算、逻辑联结词、图的基本性质、函数性质、可计算性问题等。示例：判断一个图是否是欧拉图，考察对欧拉图定义的理解。

多项选择题：考察学生对多个知识点或一个知识点不同方面的综合理解，题型涵盖逻辑运算性质、平面图判定、树的性质、可计算性问题分类等。示例：判断哪些运算满足交换律，考察对集合运算