吉财离散数学试卷

吉财离散数学试卷一、选择题（每题1分，共10分）

1.在集合论中，集合A={1,2,3}与集合B={3,4,5}的并集是？

A.{1,2,3,4,5}

B.{1,2,3}

C.{3,4,5}

D.{1,2,4,5}

2.下列哪个不是命题？

A.今天天气很好。

B.2+2=4

C.请开门。

D.火星上有生命。

3.在命题逻辑中，命题p和命题q的真值表，p为真，q为假时，p∧q的真值是？

A.真

B.假

C.无法确定

D.以上都不对

4.下列哪个是谓词逻辑的合法公式？

A.∀x∃y(x+y=0)

B.∃x∀y(x+y=0)

C.∀x(x+1=x)

D.∃y(y+1=0)

5.在图论中，一个图G=(V,E)中，V表示？

A.边

B.顶点

C.邻接矩阵

D.权重

6.下列哪个是欧拉图？

A.一个有奇数个顶点的连通图

B.一个所有顶点度数都是偶数的连通图

C.一个有奇数条边的连通图

D.一个无向图

7.在树论中，一个树的顶点数是n，则该树的边数是？

A.n-1

B.n

C.2n

D.n^2

8.下列哪个不是图论中的常用算法？

A.深度优先搜索

B.广度优先搜索

C.最小生成树算法

D.快速排序

9.在组合数学中，从n个不同元素中取出k个元素的组合数记作？

A.P(n,k)

B.C(n,k)

C.A(n,k)

D.G(n,k)

10.在数理逻辑中，下列哪个是正确的推理规则？

A.拒绝前件

B.合取引入

C.附加

D.拒绝后件

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

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

A.与

B.或

C.非

D.等价

E.蕴含

2.在谓词逻辑中，下列哪些是量词？

A.∀

B.∃

C.→

D.∧

E.¬

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}的交集是________。

2.在命题逻辑中，命题p为真，命题q为假时，p∨q的真值是________。

3.谓词逻辑中的全称量词∀表示________。

4.在图论中，一个有n个顶点的无向完全图有________条边。

5.组合数学中，从n个不同元素中取出k个元素的排列数记作________。

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

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

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

3.在谓词逻辑中，写出命题“所有的人都是聪明的”的谓词逻辑表达式，其中个体域为所有人，x表示人，P(x)表示x是聪明的。

4.设有一个无向图G，顶点集V={v1,v2,v3,v4,v5}，边集E={v1v2,v1v3,v2v4,v3v4,v4v5}。画出该图，并判断它是否是连通图。

5.计算从6个不同的元素中取出3个元素的排列数和组合数。

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

一、选择题答案

1.A

2.C

3.B

4.A

5.B

6.B

7.A

8.D

9.B

10.B

二、多项选择题答案

1.A,B,C,D,E

2.A,B

3.A,B,C,D,E

4.A,B,C,D

5.A,B,C,D,E

三、填空题答案

1.{3}

2.真

3.对于所有x，P(x)都为真

4.n(n-1)/2

5.P(n,k)或A(n,k)

四、计算题答案及解题过程

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

2.解：真值表如下：

pqrp∧q¬r(p∧q)→¬r

---------------

TTTTFF

TTFTTT

TFTFFT

TFFFTT

FTTFFT

FTFFTT

FFTFFT

FFFFTT

3.解：∀x(P(x))

4.解：图如下：

v1---v2

||

||v4---v5

v3---v4

该图是连通图，因为任意两个顶点之间都有路径相连。

5.解：排列数P(6,3)=6!/(6-3)!=6!/3!=(6×5×4×3×2×1)/(3×2×1)=6×5×4=120

组合数C(6,3)=6!/(3!×(6-3)!)=6!/(3!×3!)=(6×5×4×3×2×1)/((3×2×1)×(3×2×1))=20

解题过程详解：

1.首先求A和B的交集，A∩B={1,2,3}∩{3,4,5}={3}，然后再求交集与C的并集，得到最终结果。

2.根据命题逻辑的联结词定义，先计算p∧q和¬r的真值，然后根据蕴含的定义计算(p∧q)→¬r的真值。

3.在谓词逻辑中，全称量词∀表示“所有”，命题“所有的人都是聪明的”可以表示为对于所有的人x，x是聪明的，即∀x(P(x))。

4.根据顶点集和边集，画出无向图，然后判断任意两个顶点之间是否有路径相连，如果是，则是连通图。

5.排列数是从n个不同元素中取出k个元素的排列数，计算公式为P(n,k)=n!/(n-k)!；组合数是从n个不同元素中取出k个元素的组合数，计算公式为C(n,k)=n!/(k!×(n-k)!)。

知识点分类和总结：

集合论：集合的运算（并集、交集、差集、补集），集合的性质（幂集、子集、交集运算的性质），集合的应用。

命题逻辑：命题的定义，联结词（与、或、非、蕴含、等价），命题公式，真值表，推理规则。

谓词逻辑：谓词的定义，量词（全称量词、存在量词），谓词逻辑公式，谓词逻辑的应用。

图论：图的基本概念（顶点、边、无向图、有向图），图的性质（连通性、度数、回路、树），图的算法（深度优先搜索、广度优先搜索、最小生成树）。

组合数学：排列、组合、二项式系数、鸽巢原理、组合计数问题。

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

选择题：考察学生对集合论、命题逻辑、谓词逻辑、图论、组合数学等基本概念的掌握程度，以及运用这些概念解决简单问题的能力。例如，选择题第1题考察了集合的交集运算，学生需要掌握交集的定义和运算方法。

多项选择题：考察学生对多个相关概念的理解和区分能力，以及综合运用这些概念解决复杂问题的能力。例如，多项选择题第1题考察了命题逻辑的基本联结词，学生需要掌握每个联结词的定义和真值表。

填空题：考察学生对基本概念和公式的记忆和应用能力，以及简洁表达数学关系的能力。例如，