江汉大学离散数学试卷

江汉大学离散数学试卷一、选择题（每题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+3=5

C.请开门。

D.x+y=7

3.在命题逻辑中，命题p和命题q的合取（与）表示为？

A.p∨q

B.p→q

C.p∧q

D.p⊕q

4.下列哪个是永真式？

A.p∨¬p

B.p∧¬p

C.p→p

D.p⊕p

5.在谓词逻辑中，∀x(P(x))表示？

A.对所有x，P(x)成立

B.存在x，P(x)成立

C.P(x)不成立

D.对所有x，P(x)不成立

6.下列哪个是谓词逻辑中的量词？

A.∃

B.∀

C.→

D.∧

7.在图论中，一个图G=(V,E)中，顶点V的度数是指？

A.顶点的数量

B.边的数量

C.与该顶点相连的边的数量

D.图的总边数

8.下列哪个不是图的性质？

A.无向图

B.有向图

C.网络图

D.拓扑图

9.在树论中，一个树的度是指？

A.树的顶点数量

B.树的边数量

C.树的最大度数

D.树的层次数量

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.树中有n个顶点，则有n-1条边

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.在图论中，一个无向图G=(V,E)中，如果对于任意两个顶点u和v，都存在一条从u到v的路径，则称该图是________。

4.在树论中，一个树的度是指该树中顶点的最大度数，度数为0的顶点称为________。

5.在谓词逻辑中，∀x(P(x))∧∃y(Q(y))的表达式表示________。

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

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

2.写出命题公式(p∧q)→¬r的否定形式。

3.给定图G如下，其中顶点集V={a,b,c,d,e}，边集E={ab,ac,be,bd,ce}，求每个顶点的度数，并判断该图是否是连通图。

4.给定一棵树，其中顶点集V={1,2,3,4,5,6,7}，边集E={12,13,24,25,26,34,37}，求该树的高度和每个顶点的父节点。

5.给定谓词逻辑公式∀x∃y(P(x,y))，解释该公式的含义，并给出一个具体的例子来说明该公式为真。

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

一、选择题答案及解析

1.A

解析：集合的并集是包含两个集合中所有元素的集合，即{1,2,3,4,5}。

2.D

解析：命题是能够判断真假的陈述句，而x+y=7是一个含有变量的表达式，无法判断真假。

3.C

解析：命题逻辑中的合取（与）用∧表示，p∧q表示p和q同时为真。

4.A

解析：永真式是在任何赋值下都为真的命题公式，p∨¬p是矛盾律的体现，总是为真。

5.A

解析：∀x(P(x))表示对于所有x，命题P(x)都成立。

6.AB

解析：谓词逻辑中的量词有全称量词∀和存在量词∃。

7.C

解析：顶点的度数是指与该顶点相连的边的数量。

8.C

解析：网络图通常指带有权重的图，不是图的基本性质。

9.C

解析：树的度是指树中顶点的最大度数。

10.C

解析：有向图是图的一种类型，不是树的结构。

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

1.ABCDE

解析：集合论中的基本运算包括并集、交集、补集、差集和对称差集。

2.ABCDE

解析：逻辑联结词包括与、或、非、蕴含和等价。

3.ABCDE

解析：图论中的基本概念包括顶点、边、邻接矩阵、路径和连通性。

4.ABCDE

解析：树的性质包括没有环、连通、n个顶点n-1条边、唯一根节点和层次结构。

5.AB

解析：谓词逻辑中的量词有全称量词和存在量词。

三、填空题答案及解析

1.{3,4}

解析：集合的交集是两个集合中共同拥有的元素。

2.今天是星期一且明天是星期二

解析：合取用“且”表示，p∧q表示p和q同时为真。

3.连通图

解析：如果对于任意两个顶点都存在一条路径，则该图是连通的。

4.叶子节点

解析：度数为0的顶点称为叶子节点。

5.对所有x，P(x)成立并且存在一个y，Q(y)成立

解析：∀x(P(x))表示对所有x，P(x)成立；∃y(Q(y))表示存在一个y，Q(y)成立。

四、计算题答案及解析

1.{3,4,5,6,7,8}

解析：(A∩B)∪C即{3,4}∪{5,6,7,8}，合并后为{3,4,5,6,7,8}。

2.¬(p∧q)∨r

解析：根据命题逻辑的德摩根律，命题公式的否定形式为¬(p∧q)∨r。

3.度数：a-2,b-3,c-2,d-2,e-2；连通图

解析：计算每个顶点的度数，ab,ac,be,bd,ce分别连接了顶点a,b,c,d,e，度数分别为2,3,2,2,2。由于所有顶点都通过边相连，因此是连通图。

4.高度：3；父节点：1-无，2-1，3-1，4-1，5-2，6-2，7-3

解析：树的高度是树中最高顶点的层次数，该树的高度为3。父节点是指连接到子节点的顶点，1是根节点没有父节点，2,3,4连接到1，5,6连接到2，7连接到3。

5.对所有x，存在一个y，使得P(x,y)成立；例如，P(x,y)表示x是y的老师，则公式表示对所有学生x，都存在一个老师y。

解析：∀x∃y(P(x,y))表示对于所有x，存在一个y，使得P(x,y)成立。例如，P(x,y)可以表示x是y的老师，则公式表示对于所有学生x，都存在一个老师y。

知识点分类和总结

集合论：集合的基本运算（并集、交集、补集、差集、对称差集），集合的性质（幂集、子集、真子集）。

命题逻辑：命题、逻辑联结词（与、或、非、蕴含、等价）、量词（全称量词、存在量词）、命题公式及其推理规则。

图论：图的基本概念（顶点、边、邻接矩阵、路径、连通性），图的基本性质（无向图、有向图、网络图），树的基本概念（根节点、叶子节点、父节点、子节点、树的高度、树的性质）。

谓词逻辑：谓词、量词、谓词逻辑公式及其解释。

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

选择题：考察学生对集合论、命题逻辑、图论、树论和谓词逻辑的基本概念和性质的理解，通过选择题的形式考察学生的记忆和