计算机离散数学试卷

计算机离散数学试卷一、选择题（每题1分，共10分）

1.下列哪个集合是有限集？

A.自然数集

B.整数集

C.有理数集

D.{1,2,3}

2.设A和B是集合，以下哪个式子是正确的？

A.A∪B=B∪A

B.A∩B=B∩A

C.A×B=B×A

D.A⊆B⇒B⊆A

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

A.p∨¬p

B.p∧¬p

C.p→p

D.¬p→p

4.设有命题p:今天下雨，q:我会去图书馆。命题“如果今天不下雨，那么我会去图书馆”可以表示为：

A.p→q

B.¬p→q

C.q→p

D.¬q→¬p

5.下列哪个是图G的Eulerian路的充分必要条件？

A.G是连通的

B.G是连通的且所有顶点的度数都是偶数

C.G是连通的且至少有两个顶点的度数是奇数

D.G是连通的且所有顶点的度数都是奇数

6.设有函数f:A→B，以下哪个是函数的必要条件？

A.f是单射

B.f是满射

C.f是双射

D.A和B的元素个数相同

7.下列哪个是偏序关系的性质？

A.传递性

B.对称性

C.反对称性

D.以上都是

8.设有命题公式p∧q→p，以下哪个是它的等价式？

A.p∨q

B.p∧q

C.¬p∨¬q

D.¬p∧¬q

9.下列哪个是组合数学中的基本原理？

A.加法原理

B.乘法原理

C.排列

D.以上都是

10.设有有向图D，以下哪个是D的强连通分量的定义？

A.D的最大连通子图

B.D的最大强连通子图

C.D的最小连通子图

D.D的最小强连通子图

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

1.下列哪些是集合论中的基本运算？

A.并集

B.交集

C.差集

D.补集

E.幂集

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

A.p∨¬p

B.p∧¬p

C.(p→q)→(q→p)

D.(p∧q)→p

E.¬(p∧¬p)

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

A.顶点

B.边

C.邻接矩阵

D.通路

E.网络流

4.下列哪些是组合数学中的计数方法？

A.排列

B.组合

C.二项式定理

D.递推关系

E.鸽巢原理

5.下列哪些是数理逻辑中的基本概念？

A.命题

B.谓词

C.量词

D.谓词逻辑公式

E.模型论

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

1.设集合A={1,2,3}，B={3,4,5}，则A∪B=________。

2.命题公式p∧q的否定是________。

3.一个有n个顶点的简单无向图中，最多有________条边。

4.在组合数学中，从n个不同元素中取出k个元素的组合数记作________，计算公式为________。

5.设集合A={a,b,c}，则A的所有子集个数是________。

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

1.设有命题公式A=(p→q)∧(¬q→¬p)。求命题公式A的主析取范式。

2.设集合A={1,2,3,4}，B={2,4,6,8}，C={3,4,5,6}。求(A∩B)∪C。

3.证明命题公式(p∧q)→p是重言式。

4.设有向图G如下，其中顶点集V={a,b,c,d}，边集E={(a,b),(b,c),(c,d),(d,a),(a,c)}。判断图G是否是强连通图，并说明理由。

5.计算从5个不同元素中取出3个元素的排列数P(5,3)。

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

一、选择题（每题1分，共10分）

1.D{1,2,3}是一个包含三个元素的有限集。A、B、C都是无限集。

2.A、B、CA∪B=B∪A是集合的并运算满足交换律。A∩B=B∩A是集合的交运算满足交换律。(A×B)一般不等于(B×A)因为元素的顺序和组合方式不同。A⊆B不一定意味着B⊆A，例如A={1,2}，B={2}，则A⊆B但B⊈A。

3.Ap∨¬p是一个永真式，因为它总是为真。当p为真时，¬p为假，p∨¬p为真；当p为假时，¬p为真，p∨¬p为真。

4.B“如果今天不下雨，那么我会去图书馆”是命题¬p→q的形式。原命题是“如果今天不下雨(¬p)，那么我会去图书馆(q)”。

5.B图G有Eulerian路的充分必要条件是G是连通的，并且G中恰好有两个顶点的度数是奇数。A是必要非充分条件。C和D描述的是Eulerian回路的条件。

6.B函数f:A→B是一个函数，如果对于A中的每一个元素，在B中都有唯一的元素与之对应。这是函数的基本定义。A单射、C双射、D都是更强的条件，不是所有函数都必须满足。

7.A、C偏序关系是指集合中的元素之间可以定义一种“小于等于”或“大于等于”的关系，它满足自反性、反对称性和传递性。对称性不是偏序关系的性质。

8.B¬p∨¬q是p∧q→p的等价式。根据蕴涵式的等价式，p→q≡¬p∨q。所以p∧q→p≡¬(p∧q)∨p≡(¬p∨¬q)∨p≡¬p∨p∨¬q≡T∨¬q≡T。但更标准的转换是p∧q→p≡¬(p∧q)∨p≡(¬p∨¬q)∨p≡¬p∨p∨¬q≡T∨¬q≡T。或者用分配律(¬p∨p)∧(¬q∨p)≡T∧(¬q∨p)≡¬q∨p。但最直接的等价形式是¬p∨¬q。

9.A、B、C加法原理、乘法原理和排列都是组合数学中的基本原理和方法。组合数学研究计数、排列组合等问题。

10.B有向图D的强连通分量是指D的最大强连通子图。一个强连通子图是其中任意两个顶点之间都有双向的路径。最大强连通子图是指在该定义下包含最多顶点的子图。

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

1.A、B、C、D集合论中的基本运算包括并集、交集、差集和补集。E幂集是集合的子集构成的集合，也是一个重要概念，但不是基本运算。

2.A、D、Ep∨¬p是永真式（排中律）。¬(p∧¬p)是永真式（矛盾律）。(p∧q)→p是永真式（合取对蕴含式的分离规则）。B是永假式。C不是永真式，例如p=True,q=False时，(True→False)→(False→True)=(False→True)=True，但当p=False,q=True时，(False→True)→(True→False)=(True→False)=True，但当p=False,q=False时，(False→False)→(False→True)=(True→True)=True。这个选项需要更仔细的验证，或者可能题目有误。根据标准永真式定义，A、D、E是正确的。

3.A、B、C、D顶点、边、邻接矩阵和通路是图论中的基本概念。E网络流是图论的一个应用分支，虽然重要，但通常不被视为最基础的概念。

4.A、B、C、D、E排列、组合、二项式定理、递推关系和鸽巢原理都是组合数学中的重要计数方法和概念。

5.A、B、C、D、E命题、谓词、量词、谓词逻辑公式和模型论都是数理逻辑的基本组成部分和研究内容。

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

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

2.¬(p∧q)根据德摩根律，命题公式p∧q的否定是¬p∨¬q。

3.n(n-1)/2在简单无向图中，任意两个不同的顶点之间至多有一条边。对于n个顶点，第一个顶点可以与其他n-1个顶点连线，第二个顶点可以与剩下的n-2个顶点连线，依此类推。总边数为1+2+...+(n-1)=n(n-1)/2。

4.C(n,k)或∑_{i=0}^{k}(-1)^{i}C(n,i)组合数表示从n个不同元素中取出k个元素的组合方式的总数，记作C(n,k)或写作�binom{n}{k}。计算公式为C(n,k)=n!/(k!*(n-k)!).

5.2^3=8集合A有3个元素，其子集个数为2的3次方，即2^3=8个。这些子集包括空集、单元素子集、双元素子集和全集。

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

1.主析取范式为p∧¬q∧¬r∧s。分析略。

2.(A∩B)∪C={2,4}∪{3,4,5,6}={2,3,4,5,6}。

3.证明略。p∧q→p是重言式。

4.图G不是强连通图。因为顶点a不能通过有向边到达顶点c(没有a→c的边)，所以a和c不在同一个强连通分量中。存在至少两个顶点不在同一个强连通分量中，所以图不是强连通的。

5.P(5,3)=5!/(5-3)!=5!/2!=(5×4×3×2×1)/(2×1)=5×4×3=60。

知识点分类和总结：

本试卷主要涵盖离散数学的基础理论部分，包括集合论、命题逻辑、谓词逻辑、图论、组合数学和数理逻辑初步等知识点。

一、选择题知识点详解及示例：

集合论：理解集合的基本运算（并、交、差、补）、集合的性质（幂集、子集）、集合的计数（子集个数）。示例：计算{1,2}∪{2,3}={1,2,3}。

命题逻辑：掌握命题的概念、逻辑联结词（与、或、非、蕴含、等价）、命题公式及其真值表、永真式和永假式、等价式转换。示例：证明p∧(q∨r)≡(p∧q)∨(p∧r)。

谓词逻辑：理解谓词、量词（全称量词∀、存在量词∃）的概念和表示。示例：将“所有的人都是会死的”表示为∀x(Person(x)→Mortal(x))。

图论：掌握图的基本概念（顶点、边、有向图、无向图、带权图）、图的基本性质（连通性、路径、回路）、Eulerian路和回路的条件、图的表示方法（邻接矩阵）。示例：判断一个图是否有Eulerian回路。

组合数学：掌握基本的计数原理（加法原理、乘法原理）、排列（有序选取）、组合（无序选取）、二项式定理、递推关系、鸽巢原理。示例：计算从5人中选出3人组成一个委员会的选法数。

数理逻辑初步：了解逻辑推理的基本规则、模型论的基本概念。示例：使用逻辑推理证明一个命题公式是重言式。

二、多项选择题知识点详解及示例：

本题型考察学生对多个知识点的综合理解和应用能力，需要学生能够识别正确的选项，并排除错误选项。通常涉及的概念较多，需要扎实的基础知识。示例：选择所有属于图论基本概念的项目。

三、填空题知识点详解及示例：

本题型考察学生对基本概念、公式和定理的准确记忆和理解。要求学生能够准确填写答案，通常答案简洁明了。示例：填写集合A={1,2,3}和B={3,4,5}的并集。

四、计算题知识点详解及示例：

本题型考察学生运用所学理论知识解决具体问题的能力，需要学生能够进行逻辑推理、代数计算和证明。通常涉及具体的计算过程或证明步骤。示例：计算