华侨大学离散数学试卷

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

1.下列哪个命题公式是重言式？

A.(p∧q)→p

B.p∧(q→p)

C.(p∨q)→(p∧q)

D.p→(p∨q)

2.在集合论中，集合A的幂集P(A)的基数是多少，如果A有n个元素？

A.n

B.2^n

C.n^2

D.n!

3.下列哪个图是欧拉图？

A.完全图K_3

B.星型图（一个中心顶点连接多个叶子顶点）

C.斜线图（一个顶点连接自身）

D.二分图

4.在命题逻辑中，下列哪个联结词是可交换的？

A.→（蕴涵）

B.↔（双条件）

C.∧（合取）

D.¬（非）

5.下列哪个是正确的全称量词公式？

A.∀x∃yP(x,y)

B.∃x∀yP(x,y)

C.∀x∀yP(x,y)

D.∀y∃xP(x,y)

6.在图论中，一个连通无向图的最小生成树有多少条边？

A.n

B.n-1

C.n+1

D.2n

7.下列哪个是正确的谓词逻辑公式？

A.∀xP(x)∧∃yQ(y)

B.∃xP(x)∨∀yQ(y)

C.∀x(P(x)→Q(x))

D.∃x(P(x)∧Q(x))

8.在组合数学中，8个元素的全排列有多少种？

A.8!

B.2^8

C.8^2

D.16!

9.下列哪个是正确的偏序关系？

A.<（小于）

B.≥（大于等于）

C.≠（不等于）

D.=（等于）

10.在布尔代数中，下列哪个是正确的分配律？

A.a∧(b∨c)=(a∧b)∨(a∧c)

B.a∨(b∧c)=(a∨b)∧(a∨c)

C.a∧(b∧c)=(a∧b)∧(a∧c)

D.a∨(b∨c)=(a∨b)∨(a∨c)

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

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

A.∧（合取）

B.∨（析取）

C.→（蕴涵）

D.↔（双条件）

E.∀（全称量词）

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

A.并集（∪）

B.交集（∩）

C.差集（-）

D.补集（'）

E.幂集（P(A)）

3.在图论中，下列哪些是图的基本概念？

A.顶点（Vertex）

B.边（Edge）

C.邻接矩阵

D.通路

E.顶点度数

4.在谓词逻辑中，下列哪些是正确的量词？

A.∀（全称量词）

B.∃（存在量词）

C.→（蕴涵）

D.∧（合取）

E.≠（不等于）

5.在组合数学中，下列哪些是组合计数的基本原理？

A.加法原理

B.乘法原理

C.排列

D.组合

E.鸽巢原理

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

1.谓词逻辑中的量词“∀x”表示_________________________。

2.在图论中，一个无向图中所有顶点的度数之和等于边数的_________________________倍。

3.集合A={1,2,3}的幂集P(A)的基数为_________________________。

4.命题逻辑中的重言式是指在任何解释下都为_________________________的命题公式。

5.组合数学中的排列是指从n个不同元素中取出k个元素的_________________________的全体。

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

1.设命题公式P为(p→q)∧(¬q→¬p)，求P的真值表。

2.给定集合A={1,2,3}，B={2,3,4}，C={3,4,5}，计算(A∪B)∩C的元素。

3.设有向图G的邻接矩阵为：

```

0101

0010

1001

0100

```

求图G中顶点1到顶点4的所有可能通路（至少包含2个边）。

4.写出谓词逻辑公式∀x∃y(P(x,y)→Q(y))的否定形式。

5.从5个男生和4个女生中选出3个男生和2个女生组成一个委员会，问有多少种不同的选法？

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

一、选择题答案及解析

1.A

解析：A.(p∧q)→p是重言式，因为当p为真时，p∧q为真，则蕴涵式为真；当p为假时，p∧q为假，根据蕴涵式的定义，假命题蕴涵任何命题也为真。

2.B

解析：集合A的幂集P(A)包含A的所有子集，基数为2^n，因为每个元素都有被包含或不被包含两种可能，n个元素就有2^n种组合。

3.B

解析：B.星型图是欧拉图，因为它存在一条经过所有边的简单回路。A.完全图K_3不是欧拉图，因为没有奇数度顶点。C.斜线图有一个自环，不是欧拉图。D.二分图不一定是欧拉图，取决于度数分布。

4.C

解析：C.∧（合取）是可交换的，即p∧q与q∧p意义相同。其他联结词不满足交换律。

5.C

解析：C.∀x∀yP(x,y)表示对于所有x，所有y，P(x,y)都成立，这是正确的全称量词公式。其他选项中量词和谓词的顺序或搭配不当。

6.B

解析：一个连通无向图的最小生成树有n-1条边，其中n是顶点数。这是最小生成树的基本性质。

7.A

解析：A.∀xP(x)∧∃yQ(y)是正确的谓词逻辑公式，表示所有x满足P(x)，并且存在至少一个y满足Q(y)。其他选项中量词和谓词的顺序或逻辑联结词使用不当。

8.A

解析：8个元素的全排列有8!=40320种，即8个元素可以按不同顺序排列的总数。

9.B

解析：B.≥（大于等于）是偏序关系，满足自反性、反对称性和传递性。其他选项不满足偏序关系的定义。

10.A

解析：A.a∧(b∨c)=(a∧b)∨(a∧c)是布尔代数中的分配律。其他选项不是分配律。

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

1.A,B,C,D

解析：命题逻辑的联结词包括合取（∧）、析取（∨）、蕴涵（→）和双条件（↔）。E.∀是全称量词，不属于联结词。

2.A,B,C,D,E

解析：集合论中的集合运算包括并集（∪）、交集（∩）、差集（-）、补集（'）和幂集（P(A)）。

3.A,B,C,D,E

解析：图论的基本概念包括顶点（Vertex）、边（Edge）、邻接矩阵、通路和顶点度数。

4.A,B

解析：谓词逻辑中的量词包括全称量词（∀）和存在量词（∃）。C,D,E不是量词。

5.A,B,C,D,E

解析：组合计数的基本原理包括加法原理、乘法原理、排列、组合和鸽巢原理。

三、填空题答案及解析

1.对于所有x，P(x)都成立。

解析：谓词逻辑中的量词“∀x”表示对于所有x，后面的谓词P(x)都成立。

2.2

解析：根据握手定理，无向图中所有顶点的度数之和等于边数的2倍。

3.8

解析：集合A={1,2,3}有3个元素，其幂集P(A)的基数为2^3=8。

4.真

解析：命题逻辑中的重言式是指在任何解释下都为真的命题公式。

5.有序

解析：组合数学中的排列是指从n个不同元素中取出k个元素的有序的全体。

四、计算题答案及解析

1.真值表：

```

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

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

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

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

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

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

```

解析：通过计算真值表，可以看到命题公式P在不同情况下的真值。

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

解析：首先计算A和B的并集，然后与C取交集，得到最终结果。

3.顶点1到顶点4的通路有：

1-3-4,1-4-3,1-2-3-4,1-3-2-4

解析：通过遍历邻接矩阵，找出所有从顶点1到顶点4的通路，至少包含2条边。

4.否定形式：∃x∀y¬(P(x,y)→Q(y))≡∃x∀y(P(x,y)∧¬Q(y))

解析：根据谓词逻辑的否定规则，逐层否定量词和谓词，得到否定形式。

5.选法数为C(5,3)*C(4,2)=10*6=60

解析：先从5个男生中选出3个，再从4个女生中选出2个，根据乘法原理计算总数。

知识点分类和总结

谓词逻辑：量词（全称量词∀和存在量词∃）、命题逻辑联结词（合取∧、析取∨、蕴涵→、双条件↔）、命题公式及其真值表。

集合论：集合的基本运算（并集∪、交集∩、差集-、补集'）、幂集、基数、集合恒等式。

图论：无向图、有向图、欧拉图、最小生成树、邻接矩阵、通路、顶点度数、握手定理。

组合数学：基本原理（加法原理、乘法原理）、排列、组合、鸽巢原理。

布尔代数：基本运算（与∧、或∨、非¬）、分配律、德摩根律。

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

选择题：考察学生对基本概念和定义的理解，如联结词、量词、图的基本性质、集合运算等。示例：判断一个图是否为欧拉图，需要知道欧拉图的定义和性质。

多项选择题：考察学生对多个相关概念的理解和区分，如命题逻辑联结词、集合运算、图论基本概念、谓词逻辑量词等。示例：列