贵阳学院离散数学试卷

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

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

A.A=B

B.A≠B

C.A⊂B

D.B⊂A

2.下列哪个是命题？

A.今天天气很好。

B.2+3=5

C.请开门

D.这朵花很漂亮

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

A.p或q

B.p且q

C.非p

D.非q

4.在命题逻辑中，¬(p∧q)等价于？

A.p∧¬q

B.¬p∨¬q

C.p∨¬q

D.¬p∧¬q

5.设有集合A={1,2,3}，B={2,3,4}，则A∩B等于？

A.{1,2}

B.{3,4}

C.{1,3}

D.{2,3}

6.在图论中，一个图G由什么组成？

A.顶点和边

B.顶点和权重

C.边和权重

D.顶点和颜色

7.无向图中，如果顶点u和顶点v之间有一条边，则称u和v是？

A.邻接的

B.连通的

C.独立的

D.重叠的

8.在树中，一个顶点的度数是指？

A.该顶点的子树数量

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

C.该顶点的父节点数量

D.该顶点的叶子节点数量

9.在集合论中，A×B表示？

A.A和B的并集

B.A和B的交集

C.A和B的笛卡尔积

D.A和B的补集

10.在命题逻辑中，(p→q)∧(q→p)等价于？

A.p↔q

B.¬p∨q

C.p∧¬q

D.¬p∧¬q

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

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

A.合取（∧）

B.析取（∨）

C.非（¬）

D.蕴含（→）

E.等价（↔）

2.在集合论中，下列哪些是正确的集合运算？

A.并集（U）

B.交集（∩）

C.补集（'）

D.差集（-）

E.笛卡尔积（×）

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

A.顶点数

B.边数

C.连通性

D.度数序列

E.颜色数

4.在树中，下列哪些是正确的性质？

A.树中没有环

B.树中至少有一个根节点

C.树中任意两个顶点之间有唯一路径

D.树可以是空的

E.树中每个顶点的度数相同

5.在命题逻辑中，下列哪些是正确的等价式？

A.¬(p∧q)↔¬p∨¬q

B.¬(p∨q)↔¬p∧¬q

C.(p→q)↔¬p∨q

D.(p↔q)↔(p→q)∧(q→p)

E.(p↔q)↔¬p↔¬q

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

1.在集合论中，集合A包含元素1,2,3，集合B包含元素3,4，则A∪B=______。

2.在命题逻辑中，命题p表示“今天是星期一”，命题q表示“今天是星期二”，则p∧q表示______。

3.在图论中，一个无向图G包含n个顶点和m条边，则G的度数之和等于______。

4.在树中，一个根节点可以有______个子节点。

5.在命题逻辑中，命题p表示“天空是蓝色的”，命题q表示“太阳是亮的”，则p→q表示______。

四、计算题（每题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→p)的析取范式。

3.给定一个无向图G，顶点集V={v1,v2,v3,v4}，边集E={e1,e2,e3,e4,e5}，其中e1=(v1,v2)，e2=(v1,v3)，e3=(v2,v4)，e4=(v3,v4)，e5=(v2,v3)。画出该图，并判断该图是否连通。

4.给定一棵树，其顶点集V={v1,v2,v3,v4,v5,v6}，边集E={e1,e2,e3,e4,e5}，其中e1=(v1,v2)，e2=(v1,v3)，e3=(v2,v4)，e4=(v2,v5)，e5=(v3,v6)。求树的高度和每个顶点的度数。

5.写出命题公式¬(p↔q)↔(p∧¬q)↔(¬p∧q)的等价式。

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

一、选择题答案

1.A

2.B

3.B

4.B

5.D

6.A

7.A

8.B

9.C

10.A

二、多项选择题答案

1.A,B,C,D,E

2.A,B,C,D,E

3.A,B,C,D,E

4.A,B,C,D

5.A,B,C,D,E

三、填空题答案

1.{1,2,3,4}

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

3.2m

4.n-1

5.如果天空是蓝色的，那么太阳是亮的

四、计算题答案

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

2.(p∧¬q)∨(r→p)=(p∧¬q)∨(¬r∨p)=p∧¬q∨¬r∨p=p∨(¬q∨¬r)

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

4.树的高度为3。顶点度数：v1=2,v2=3,v3=2,v4=1,v5=1,v6=1。

5.¬(p↔q)↔(p∧¬q)↔(¬p∧q)

知识点总结及题型解析

集合论

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

-集合的性质：幂集、子集、真子集、空集。

-集合的应用：集合关系、集合映射。

命题逻辑

-命题的基本联结词：合取（∧）、析取（∨）、非（¬）、蕴含（→）、等价（↔）。

-命题公式：析取范式、合取范式、等价式。

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

图论

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

-图的性质：度数序列、欧拉图、哈密顿图。

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

树

-树的基本概念：根节点、子节点、父节点、叶子节点、路径、高度。

-树的性质：二叉树、满二叉树、完全二叉树。

-树的应用：文件系统、数据库索引。

解题过程详解

一、选择题解析

1.A:集合A和集合B的元素完全相同，只是顺序不同，因此A=B。

2.B:命题是能够判断真假的陈述句，"2+3=5"是一个命题，因为其真值为假。

3.B:合取（∧）表示逻辑与，p∧q表示p和q同时为真。

4.B:根据德摩根定律，¬(p∧q)等价于¬p∨¬q。

5.D:A∩B表示A和B的交集，即两个集合的共同元素，{2,3}。

6.A:图G由顶点和边组成，是图论的基本要素。

7.A:在无向图中，如果顶点u和顶点v之间有一条边，则称u和v是邻接的。

8.B:顶点的度数是指与该顶点相连的边数量。

9.C:A×B表示A和B的笛卡尔积，即所有可能的有序对。

10.A:(p→q)∧(q→p)是双条件，等价于p↔q。

二、多项选择题解析

1.A,B,C,D,E:命题逻辑中的基本联结词包括合取、析取、非、蕴含、等价。

2.A,B,C,D,E:集合论中的基本集合运算包括并集、交集、补集、差集、笛卡尔积。

3.A,B,C,D,E:图的性质包括顶点数、边数、连通性、度数序列、颜色数。

4.A,B,C,D:树的性质包括没有环、有根节点、唯一路径、可以为空。

5.A,B,C,D,E:命题逻辑中的等价式包括德摩根定律、蕴含的等价式、双条件的等价式。

三、填空题解析

1.{1,2,3,4}:A∪B表示A和B的并集，包含所有属于A或B的元素。

2.今天是星期一且今天是星期二:p∧q表示p和q同时为真。

3.2m:在无向图中，度数之和等于边数的两倍，因为每条边贡献两个度数。

4.n-1:在树中，根节点的子节点数量等于顶点数减去1。

5.如果天空是蓝色的，那么太阳是亮的:p→q表示如果p为真，则q也为真。

四、计算题解析

1.(A∪B)∩C={3,4}:先求A∪B={1,2,3,4}，再求与C的交集。

2.(p∧¬q)∨(r→p)=p∨(¬q∨¬r):化简命题公式。

3.图略。该图是连通的，因为任意两个顶点之间都有路径相连：画出图并判断连通性。

4.树的高度为3。顶点度数：v1=2,v2=3,v3=2,v4=1,v5=1,v6=1：计算树的高度和每个顶点的度数。

5.¬(p↔q)↔(p∧¬q)↔(¬p∧q):写出命题公式的等价式。

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

-