华工离散数学试卷

华工离散数学试卷一、选择题（每题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}

2.下列哪个不是命题？

A.今天天气很好

B.2+3=5

C.请开门

D.火星上有生命

3.在命题逻辑中，命题p为“今天是星期一”，命题q为“明天是星期二”，则“今天不是星期一”用逻辑符号表示为？

A.¬p

B.¬q

C.p∧q

D.p∨q

4.设集合A={a,b,c}，则A的所有真子集个数是？

A.4

B.5

C.6

D.7

5.在图论中，一个有n个顶点的无向图，其边数最多为？

A.n

B.n(n-1)/2

C.n(n+1)/2

D.2n

6.下列哪个是欧拉图？

A.一个有5个顶点、6条边的无向图

B.一个有4个顶点、4条边的无向图

C.一个有3个顶点、3条边的无向图

D.一个有2个顶点、3条边的无向图

7.在数理逻辑中，谓词p(x):“x是偶数”，则“存在一个偶数”用谓词逻辑表示为？

A.∀xp(x)

B.∃xp(x)

C.∀x¬p(x)

D.∃x¬p(x)

8.在集合论中，若A⊆B，B⊆C，则？

A.A⊆C

B.A⊇C

C.A=C

D.A与C无关系

9.在图论中，一个有n个顶点的连通无向图，其边数最少为？

A.1

B.n-1

C.n

D.2n

10.在命题逻辑中，命题p为“天在下雨”，命题q为“我会在家”，则“如果天不在下雨，那么我会在家”用逻辑符号表示为？

A.p→q

B.¬p→q

C.q→p

D.¬q→p

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

1.下列哪些是命题逻辑的定律？

A.交换律

B.结合律

C.分配律

D.吸收律

2.在集合论中，下列哪些表达式是正确的？

A.A∪(B∩C)=(A∪B)∩(A∪C)

B.A∩(B∪C)=(A∩B)∪(A∩C)

C.A∪A=A

D.A∩A=∅

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

A.图的顶点数和边数的关系

B.图的连通性

C.图的Coloring问题

D.图的Euler回路

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

A.∀（全称量词）

B.∃（存在量词）

C.¬（非）

D.→（蕴涵）

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

A.并集

B.交集

C.差集

D.补集

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

1.在命题逻辑中，表达式(p∧q)∨(¬p∧q)的等价式是________。

2.设集合A={1,2,3}，B={2,3,4}，则A∩B=________。

3.在图论中，一个有n个顶点和m条边的无向图，其顶点的度数之和为________。

4.在数理逻辑中，谓词公式∀x∃y(P(x,y))的否定是________。

5.在集合论中，若A⊆B，则A的补集A^与B的补集B^的关系是________。

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

1.已知命题公式p:"今天是星期一"，q:"天气很好"，用逻辑符号表示命题"如果今天是星期一，那么天气很好，并且如果天气很好，那么今天是星期一"。

2.设集合A={1,2,3,4}，B={3,4,5,6}，C={1,4,7,8}，求(A∪B)∩C以及A∩(B∪C)，并验证这两个结果是否相等。

3.画一个有5个顶点的无向图，使其是一个连通图但不是欧拉图，并说明理由。

4.写出谓词公式∀x∃y(P(x,y))的Skolem形式，其中P(x,y)表示"x是y的朋友"。

5.给定集合A={a,b,c}，列出A的所有子集，并从中选出所有真子集。

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

一、选择题答案及解析

1.A

解析：并集是两个集合中所有元素的集合，不重复。

2.C

解析：命题是能够判断真假的陈述句，“请开门”是祈使句，不是命题。

3.A

解析：¬p表示p的否定，即“今天不是星期一”。

4.C

解析：真子集是不包括集合本身的子集，A有2^3-1=7个子集，其中6个是真子集。

5.B

解析：无向图中边数最多是n(n-1)/2，其中n是顶点数。

6.B

解析：欧拉图是每条边都经过一次且仅一次的图，B满足条件。

7.B

解析：∃xp(x)表示存在一个x使得p(x)成立，即“存在一个偶数”。

8.A

解析：如果A⊆B，B⊆C，根据集合传递性，A⊆C。

9.B

解析：连通图至少需要n-1条边才能保证所有顶点连通。

10.B

解析：¬p→q表示如果p不成立，则q成立，即“如果天不在下雨，那么我会在家”。

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

1.A,B,C,D

解析：交换律、结合律、分配律和吸收律都是命题逻辑的定律。

2.A,B,C

解析：A∪(B∩C)=(A∪B)∩(A∪C)是分配律，A∩(B∪C)=(A∩B)∪(A∩C)是分配律，A∪A=A是幂等律，A∩A=∅是补律。

3.A,B,D

解析：图的性质包括顶点数和边数的关系、连通性和Euler回路。

4.A,B

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

5.A,B,C,D

解析：并集、交集、差集和补集都是集合的运算。

三、填空题答案及解析

1.q

解析：根据德摩根定律和分配律，(p∧q)∨(¬p∧q)=q。

2.{2,3}

解析：交集是两个集合中都有的元素。

3.2m

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

4.∃x∀y(¬P(x,y))

解析：否定谓词公式时，量词需要反转，谓词也需要取否定。

5.A^⊇B^

解析：如果A⊆B，则B的补集包含A的补集，即A^⊇B^。

四、计算题答案及解析

1.(p→q)∧(q→p)

解析：p→q表示“如果今天是星期一，那么天气很好”，q→p表示“如果天气很好，那么今天是星期一”，两者结合即为所求。

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

解析：(A∪B)∩C=({1,2,3,4}∪{3,4,5,6})∩{1,4,7,8}={1,4}，A∩(B∪C)={1,2,3,4}∩({3,4,5,6}∪{1,4,7,8})={1,4}，两者相等。

3.

解析：画一个有5个顶点的连通图，例如一个环状图，然后确保其中有一条边不满足Euler回路条件（例如去掉一条边）。

4.∀x∃y(P(y,x))

解析：Skolem形式需要将存在量词后的变量替换为常量或函数，这里将y替换为x的函数。

5.子集：{},{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}；真子集：{},{a},{b},{c},{a,b},{a,c},{b,c}

解析：子集是集合的所有可能组合，真子集是不包括原集合本身的子集。

知识点分类和总结

集合论：集合的运算（并集、交集、差集、补集）、子集、真子集、幂等律、分配律等。

命题逻辑：命题、逻辑运算（与、或、非）、量词、定律（交换律、结合律、分配律、吸收律）、等价式。

图论：无向图、连通图、欧拉图、握手定理、子图等。

谓词逻辑：量词（全称量词、存在量词）、谓词公式、Skolem形式等。

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

选择题：考察学生对基本概念和定律的理解，例如命题逻辑的定律、集合的运算、