淮阴工学院离散数学试卷

淮阴工学院离散数学试卷一、选择题（每题1分，共10分）

1.在集合论中，集合A包含元素1,2,3，集合B包含元素2,3,4，则集合A与集合B的交集是？

A.{1,2,3,4}

B.{2,3}

C.{1}

D.∅

2.下列哪个不是命题？

A.今天天气很好。

B.2+2=4

C.请开门。

D.他很高。

3.在逻辑运算中，命题p为“今天下雨”，命题q为“我出门不带伞”，则“今天不下雨或者我出门不带伞”的逻辑表达式是？

A.p∧q

B.p∨q

C.¬p∧¬q

D.¬p∨¬q

4.设有一个有向图G，其中有n个顶点和m条边，则G的邻接矩阵是一个？

A.n×n的矩阵

B.m×m的矩阵

C.n×m的矩阵

D.m×n的矩阵

5.在图论中，一个无向图G被称为树，如果它满足？

A.没有环且任意两个顶点之间有唯一的一条路径

B.至少有一个环

C.没有环但可能存在多个路径

D.至少有一个环且任意两个顶点之间有唯一的一条路径

6.在组合数学中，从n个不同元素中取出k个元素的组合数记作C(n,k)，则C(n,k)等于？

A.n!

B.k!

C.(n-k)!

D.n!/(k!×(n-k)!)

7.在数理逻辑中，谓词逻辑比命题逻辑？

A.更复杂，能表达更丰富的命题

B.更简单，只能表达简单的命题

C.没有区别

D.只能表达特定的命题

8.在算法分析中，一个算法的时间复杂度是O(n^2)，当n增加一倍时，算法的执行时间大约增加？

A.一倍

B.两倍

C.四倍

D.八倍

9.在集合论中，集合A有m个元素，集合B有n个元素，则集合A和集合B的笛卡尔积的元素个数是？

A.m

B.n

C.m+n

D.m×n

10.在图论中，一个图G被称为连通图，如果？

A.图中任意两个顶点之间都有边相连

B.图中至少有两个顶点之间没有边相连

C.图中存在至少一个环

D.图中不存在环

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

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

A.今天天气很好。

B.2+2=5

C.请开门。

D.他很高。

E.x+y=z

2.在集合论中，集合A包含元素1,2,3，集合B包含元素2,3,4，则下列哪些是正确的集合运算结果？

A.A∪B={1,2,3,4}

B.A∩B={2,3}

C.A-B={1}

D.B-A={4}

E.A×B={(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,2),(3,3),(3,4)}

3.在图论中，下列哪些是图的性质？

A.图是有向图

B.图是无向图

C.图中有环

D.图中没有环

E.图是连通图

4.在组合数学中，下列哪些是正确的组合公式？

A.C(n,k)=C(n,n-k)

B.C(n,0)=1

C.C(n,1)=n

D.C(n,k)=n/k

E.C(n,k)=n!/(k!×(n-k)!)

5.在数理逻辑中，下列哪些是谓词逻辑的组成部分？

A.量词

B.命题变量

C.逻辑连接词

D.谓词

E.常量

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

1.在集合论中，集合A包含元素1,2,3，集合B包含元素2,3,4，则集合A和集合B的并集是________。

2.在逻辑运算中，命题p为“今天下雨”，命题q为“我出门不带伞”，则“今天下雨且我出门不带伞”的逻辑表达式是________。

3.在图论中，一个有向图G包含n个顶点和m条边，则G的邻接矩阵是一个________矩阵。

4.在组合数学中，从n个不同元素中取出k个元素的排列数记作P(n,k)，则P(n,k)等于________。

5.在数理逻辑中，谓词逻辑通过引入________来量化命题，从而表达更丰富的语义。

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

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

2.写出命题公式(p∧¬q)∨(r→p)的真值表。

3.给定一个有向图G，其邻接矩阵为：

```

0100

0010

0001

1000

```

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

4.计算组合数C(10,3)和排列数P(10,3)。

5.用谓词逻辑表示以下句子：所有的人都会读书。

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

一、选择题答案

1.B

2.A

3.B

4.A

5.A

6.D

7.A

8.C

9.D

10.A

二、多项选择题答案

1.A,B,D

2.A,B,C,D,E

3.B,D,E

4.A,B,C,E

5.A,B,C,D,E

三、填空题答案

1.{1,2,3,4}

2.p∧q

3.n×n

4.n!/(n-k)!

5.量词

四、计算题答案

1.(A∪B)∩C={3,5}

2.真值表如下：

|p|q|r|¬q|p∧¬q|r→p|(p∧¬q)∨(r→p)|

|---|---|---|----|--------|--------|---------------------|

|T|T|T|F|F|T|T|

|T|T|F|F|F|T|T|

|T|F|T|T|T|T|T|

|T|F|F|T|T|T|T|

|F|T|T|F|F|T|T|

|F|T|F|F|F|T|T|

|F|F|T|T|F|T|T|

|F|F|F|T|F|T|T|

3.顶点1到顶点4的所有可能路径为：1-2-3-4和1-4。

4.C(10,3)=10!/(3!×(10-3)!)=120,P(10,3)=10!/(10-3)!=720

5.∀x(人(x)→读书(x))

知识点总结

集合论部分：

-集合的基本运算：并集、交集、差集、笛卡尔积。

-集合的性质：幂集、子集、补集。

-集合的应用：描述集合论在逻辑和图论中的应用。

命题逻辑部分：

-命题的基本概念：命题变量、逻辑连接词、真值表。

-命题公式：合取、析取、非、蕴涵、等价。

-命题逻辑的应用：逻辑推理和证明。

谓词逻辑部分：

-谓词的基本概念：量词、谓词变量、个体变量。

-谓词公式：谓词、量词的应用。

-谓词逻辑的应用：表达复杂的逻辑关系和语义。

图论部分：

-图的基本概念：有向图、无向图、顶点、边、环、路径。

-图的性质：连通图、树、邻接矩阵。

-图论的应用：网络分析、算法设计。

组合数学部分：

-组合公式：组合数、排列数、二项式定理。

-组合应用：计数问题、概率论。

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

选择题：

-集合论：考察集合的基本运算和性质。

示例：集合A和B的并集是哪些元素的集合。

-命题逻辑：考察命题的基本概念和逻辑运算。

示例：命题p和q的逻辑表达式是什么。

-谓词逻辑：考察谓词的基本概念和量词的应用。

示例：用谓词逻辑表示一个句子。

-图论：考察图的基本概念和性质。

示例：一个图被称为连通图的条件是什么。

-组合数学：考察组合公式和计数问题。

示例：计算组合数C(n,k)和排列数P(n,k)。

多项选择题：

-集合论：考察集合的多个运算和性质。

示例：集合A和B的并集、交集、差集等。

-命题逻辑：考察命题的多个逻辑运算和真值表。

示例：命题p、q、r的逻辑表达式和真值表。

-谓词逻辑：考察谓词的多个量词和谓词公式。

示例：用谓词逻辑表示多个句子。

-图论：考察图的多个性质和应用。

示例：图的连通性、树的结构等。

-组合数学：考察组合公式和排列组合问题。

示例：计算多个组合数和排列数。

填空题：

-集合论：考察集合的基本运算和性质。

示例：集合A和B的并集是什么。

-命题逻辑：考察命题的基本概念和逻辑运算。

示例：命题p和q的逻辑表达式是什么。

-谓词逻辑：考察谓词的基本概念和量词的应用。

示例：用谓词逻辑表示一个句子。

-图论：考察图的基本概念和性质。

示例：图的邻接矩阵是什么。

-组合数学：考察组合公式和计数问题。

示例：计算组合数C(n,