南华大学的离散数学试卷

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

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

A.非

B.且

C.或

D.等价

2.在谓词逻辑中，下列哪个符号表示“所有”？

A.∀

B.∃

C.→

D.↔

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

4.下列哪个不是图的基本概念？

A.顶点

B.边

C.权重

D.环

5.在树中，下列哪个定义是正确的？

A.至少有一个根的连通无向图

B.没有环的连通无向图

C.至少有一个根的无向图

D.没有环的无向图

6.下列哪个不是图遍历算法？

A.深度优先搜索

B.广度优先搜索

C.Dijkstra算法

D.Floyd算法

7.在集合论中，下列哪个符号表示“属于”？

A.∈

B.⊆

C.⊂

D.⊃

8.下列哪个不是关系的基本性质？

A.自反性

B.对称性

C.传递性

D.可逆性

9.在组合数学中，下列哪个符号表示排列？

A.P(n,k)

B.C(n,k)

C.Σ

D.∏

10.下列哪个不是数理逻辑的基本推理规则？

A.拒绝式

B.合取引入

C.附加式

D.拉格朗日规则

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

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

A.非

B.且

C.或

D.等价

E.如果

2.在谓词逻辑中，下列哪些符号表示量词？

A.∀

B.∃

C.→

D.↔

E.∧

3.设集合A={1,2,3}，B={2,3,4}，C={3,4,5}，则下列哪些是A∩B∩C的子集？

A.{1}

B.{2}

C.{3}

D.{4}

E.{5}

4.下列哪些是图的基本概念？

A.顶点

B.边

C.权重

D.环

E.路

5.在树中，下列哪些定义是正确的？

A.至少有一个根的连通无向图

B.没有环的连通无向图

C.至少有一个根的无向图

D.没有环的无向图

E.每对顶点之间都有唯一的路径

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

1.在命题逻辑中，用字母p表示命题“今天是星期一”，则命题“今天不是星期一”可以表示为________。

2.在谓词逻辑中，谓词P(x)表示“x是偶数”，则表达式∀x(P(x)→Q(x))表示________。

3.设集合A={a,b,c}，B={b,c,d}，则集合A与B的笛卡尔积A×B等于________。

4.在图G中，若顶点u和顶点v之间存在一条边，则称顶点u和顶点v是________。

5.设T是一个树，且T有n个顶点，则T有________条边。

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

1.给定命题公式P:"他去看电影"，Q:"他下雨"，用自然语言写出下列命题公式所表示的句子，并判断其真假：(P→Q)↔(¬Q→¬P)

2.设集合A={1,2,3}，B={x|x∈N且1≤x≤4}，C={x|x∈Z且-2≤x≤2}。求(A∩B)×C。

3.画出下列命题逻辑公式的真值表，并判断该公式是否为重言式：(P↔Q)→(P↔¬Q)

4.设无向图G的顶点集V={v1,v2,v3,v4,v5}，边集E={e1,e2,e3,e4,e5,e6}，其中e1=(v1,v2),e2=(v1,v3),e3=(v2,v4),e4=(v3,v4),e5=(v4,v5),e6=(v2,v5)。求图G的度数序列，并判断图G是否是连通图。

5.设集合A={1,2,3,4,5}，B={a,b,c}。计算从集合A到集合B的所有的函数个数，并给出其中一个双射函数的例子。

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

一、选择题答案

1.D

2.A

3.C

4.C

5.B

6.C

7.A

8.D

9.A

10.D

解题过程：

1.命题逻辑的基本联结词包括非、且、或、等价，故D不是基本联结词。

2.∀表示“所有”，∃表示“存在”，→表示“蕴涵”，↔表示“等价”，∧表示“合取”，故A表示“所有”。

3.A∪B包含A和B中的所有元素，即{1,2,3,4}。

4.图的基本概念包括顶点、边、环、路等，权重不是基本概念。

5.树是至少有一个根的连通无向图，且没有环，故B正确。

6.图遍历算法包括深度优先搜索和广度优先搜索，Dijkstra算法和Floyd算法是求最短路径的算法。

7.∈表示“属于”，⊆表示“包含于”，⊂表示“真包含于”，⊃表示“包含于”，故A表示“属于”。

8.关系的基本性质包括自反性、对称性、传递性，可逆性不是基本性质。

9.P(n,k)表示从n个元素中取出k个元素的排列数，C(n,k)表示组合数，Σ表示求和，∏表示求积，故A表示排列。

10.数理逻辑的基本推理规则包括合取引入、附加式、拒绝式等，拉格朗日规则不是基本推理规则。

二、多项选择题答案

1.A,B,C,D

2.A,B

3.A,C

4.A,B,D,E

5.A,B,D

解题过程：

1.命题逻辑的基本联结词包括非、且、或、等价，故全选。

2.∀表示“所有”，∃表示“存在”，故A和B表示量词。

3.A∩B∩C包含A、B、C中的公共元素，即{3}，其子集为{3}和空集{}，故A和C。

4.图的基本概念包括顶点、边、环、路，故全选。

5.树是至少有一个根的连通无向图，且没有环，故A、B、D。

三、填空题答案

1.¬P

2.对于所有的x，如果x是偶数，那么Q(x)成立

3.{(a,b),(a,c),(a,d),(b,b),(b,c),(b,d),(c,b),(c,c),(c,d)}

4.邻接

5.n-1

解题过程：

1.¬P表示命题P的否定，即“今天不是星期一”。

2.∀x(P(x)→Q(x))表示对于所有的x，如果P(x)成立，那么Q(x)也成立。

3.A×B包含A中每个元素与B中每个元素的有序对，即{(a,b),(a,c),(a,d),(b,b),(b,c),(b,d),(c,b),(c,c),(c,d)}。

4.若顶点u和顶点v之间存在一条边，则称顶点u和顶点v是邻接的。

5.树有n个顶点，则必有n-1条边。

四、计算题答案

1.命题公式表示的句子为：“如果他去看电影，那么他下雨”与“如果他不下雨，那么他不看电影”是等价的。该公式为重言式，因为其真值表在所有情况下都为真。

2.(A∩B)×C={(1,1),(1,0),(1,-1),(2,1),(2,0),(2,-1),(3,1),(3,0),(3,-1)}。

3.真值表如下：

PQP↔Q¬Q→¬P(P↔Q)→(P↔¬Q)

TTTTT

TFFTT

FTFTT

FFTTT

该公式为重言式。

4.度数序列为3,3,2,3,2。图G是连通图。

5.从集合A到集合B的所有的函数个数为3^5=243个。一个双射函数的例子为f={1→a,2→b,3→c,4→a,5→b}。

知识点总结：

1.命题逻辑：基本联结词、量词、命题公式、真值表、推理规则。

2.集合论：集合的基本运算（并、交、差、补）、笛卡尔积、子集。

3.图论：基本概念（顶点、边、环、路）、度数序列、连通图、遍历算法。

4.组合数学：排列、组合、求和、求积。

5.数理逻辑：基本推理规则、重言式。

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

1.选择题：考察学生对基本概念和定理的掌握程度，如命题逻辑的基本联结词、集合论的基本运算、图论的基本概念等。

2.多项选