计算机学院离散数学试卷

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

1.下列哪个不是命题逻辑的有效推理规则？

A.假言推理

B.合取引入

C.选择引入

D.拒绝引入

2.在集合论中，集合A和集合B的并集记作？

A.A×B

B.A∪B

C.A∩B

D.A-B

3.下列哪个是图论中的欧拉回路？

A.经过每条边恰好一次的回路

B.经过每个顶点恰好一次的通路

C.经过每条边至少一次的通路

D.经过每个顶点至少一次的回路

4.在命题逻辑中，符号“∀”表示？

A.合取

B.析取

C.蕴含

D.全称量词

5.下列哪个不是谓词逻辑的量词？

A.∃

B.∀

C.→

D.∧

6.在集合论中，集合A的补集记作？

A.A'

B.A^C

C.AC

D.A∁

7.在图论中，无向图中的一条边连接两个顶点u和v，记作？

A.(u,v)

B.{u,v}

C.u-v

D.u+v

8.在命题逻辑中，符号“∧”表示？

A.合取

B.析取

C.蕴含

D.否定

9.在集合论中，集合A和集合B的交集记作？

A.A×B

B.A∪B

C.A∩B

D.A-B

10.在图论中，一个图G的顶点数记作？

A.|E|

B.|V|

C.|G|

D.|A|

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

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

A.合取（∧）

B.析取（∨）

C.蕴含（→）

D.否定（¬）

E.全称量词（∀）

2.在集合论中，下列哪些运算满足交换律？

A.并集（∪）

B.交集（∩）

C.补集（'）

D.差集（-）

E.幂集（P）

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

A.无向图

B.有向图

C.树

D.简单图

E.二分图

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

A.全称量词（∀）

B.存在量词（∃）

C.选择引入

D.拒绝引入

E.合取引入

5.在集合论中，下列哪些是集合的性质？

A.互异性

B.无序性

C.确定性

D.包含性

E.空集

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

1.在命题逻辑中，符号“¬(P∧Q)”等价于“P______Q”。

2.在集合论中，集合A包含n个元素，其所有子集的个数记作______。

3.在图论中，一个有n个顶点的无向连通图至少有______条边。

4.在谓词逻辑中，符号“(∀x)(P(x)→Q(x))”表示“对于所有的x，如果P(x)成立，则Q(x)______”。

5.在集合论中，集合A和集合B的差集记作“A______B”，表示属于A但不属于B的元素组成的集合。

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

1.对于命题公式(P→Q)∧(Q→R)，写出它的真值表，并判断该公式是否为重言式。

2.设集合A={1,2,3},B={2,3,4},C={3,4,5}。计算A∪(B∩C)和(A∩B)∪C。

3.给定图G=(V,E)，其中V={a,b,c,d},E={(a,b),(b,c),(c,d),(d,a),(a,c)}。判断图G是否是欧拉图？如果是，找出一条欧拉回路。

4.在谓词逻辑中，解释命题“∀x∃y(P(x,y))”的含义，并给出一个满足该命题的谓词P(x,y)的例子。

5.对于集合A={1,2,3,4,5}，计算其所有非空子集的个数，并列出其中所有包含元素1的子集。

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

一、选择题答案

1.C

2.B

3.A

4.D

5.C

6.A

7.B

8.A

9.C

10.B

二、多项选择题答案

1.A,B,C,D

2.A,B,C,D

3.A,B,C,D,E

4.A,B

5.A,B,C

三、填空题答案

1.或

2.2^n

3.n-1

4.成立

5.-(减去)

四、计算题答案

1.真值表：

|P|Q|R|P→Q|Q→R|(P→Q)∧(Q→R)|

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

|T|T|T|T|T|T|

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

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

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

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

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

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

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

该公式不是重言式。

解题过程：

-列出所有可能的P,Q,R的真值组合。

-计算P→Q和Q→R。

-计算(P→Q)∧(Q→R)。

-观察最后一列，发现存在F，因此不是重言式。

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

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

解题过程：

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

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

3.图G不是欧拉图。

解题过程：

-欧拉图的条件是所有顶点的度数均为偶数。

-计算各顶点的度数：deg(a)=3,deg(b)=2,deg(c)=3,deg(d)=3

-由于存在奇数度顶点，图G不是欧拉图。

4.∀x∃y(P(x,y))的含义是：对于所有的x，存在一个y，使得P(x,y)成立。

例子：P(x,y)表示“x是y的朋友”，则∀x∃y(P(x,y))表示“每个人都有朋友”。

5.集合A的所有非空子集的个数是31。

包含元素1的子集有：{1},{1,2},{1,3},{1,4},{1,5},{1,2,3},{1,2,4},{1,2,5},{1,3,4},{1,3,5},{1,4,5},{1,2,3,4},{1,2,3,5},{1,2,4,5},{1,3,4,5},{1,2,3,4,5}。

解题过程：

-集合A有5个元素，其所有子集的个数为2^5=32。

-非空子集的个数为32-1=31。

-包含元素1的子集可以通过从{2,3,4,5}的子集推导得到。

知识点总结

1.命题逻辑：基本连接词（合取、析取、蕴含、否定）、量词（全称量词、存在量词）、推理规则。

2.集合论：集合的基本运算（并集、交集、补集、差集）、集合的性质（互异性、无序性、确定性）、幂集。

3.图论：无向图、有向图、树、简单图、二分图、欧拉图、图的性质。

4.谓词逻辑：量词的应用、谓词的定义。

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

1.选择题：考察学生对基本概念和定理的理解，如命题逻辑的基本连接词、集合论的基本运算、图论的基本性质等。

示例：选择题第1题考察命题逻辑的基本连接词，学生需要知道合取、析取、蕴含、否定等连接词的含义。

2.多项选择题：考察学生对多个知识点综合应用的能力，如集合论和图论的综合应用。

示例：多项选择题第2题考察集合论的基本运算是否满足交换律，学生需要知道并集、交集、补集、差集是否满足交换律。