河海大学离散数学试卷

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

1.下列哪个命题公式是永真的？

A.(P→Q)∧(Q→P)

B.(P∧Q)→P

C.P→(Q→P)

D.(P∨Q)→(P∧Q)

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

A.A×B

B.A∪B

C.A∩B

D.A-B

3.下列哪个是命题逻辑的一个有效公式？

A.(P∧Q)→P

B.P∧(Q→P)

C.(P→Q)∧(Q→P)

D.(P∨Q)→(P∧Q)

4.在图论中，一个无向图G的补图记作：

A.G'

B.G⁻¹

C.G∨

D.G∧

5.下列哪个是等价式？

A.P→Q↔Q→P

B.P→Q↔¬P∨Q

C.P∧Q↔Q∧P

D.P∨Q↔¬P∧¬Q

6.在集合论中，集合A的幂集记作：

A.P(A)

B.A^P

C.A×A

D.A∪A

7.下列哪个是图论中的一个基本概念？

A.环

B.端点

C.对角线

D.虚边

8.在命题逻辑中，下列哪个是重言式？

A.P∧¬P

B.P∨¬P

C.(P∧Q)→P

D.(P→Q)→P

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

A.A+B

B.A∪B

C.A∩B

D.A×B

10.在图论中，一个有向图G的逆图记作：

A.G'

B.G⁻¹

C.G∨

D.G∧

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

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

A.与（∧）

B.或（∨）

C.非（¬）

D.蕴含（→）

E.等价（↔）

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

A.并集（∪）

B.交集（∩）

C.差集（-）

D.幂集（P(A)）

E.补集（'）

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

A.顶点（Vertex）

B.边（Edge）

C.邻接（Adjacency）

D.环（Loop）

E.多重边（MultipleEdge）

4.下列哪些是等价式？

A.P∧Q↔Q∧P

B.P∨Q↔Q∨P

C.(P∧Q)∧R↔P∧(Q∧R)

D.(P∨Q)∨R↔P∨(Q∨R)

E.P∧(Q∨R)↔(P∧Q)∨(P∧R)

5.在命题逻辑中，下列哪些是重言式？

A.P∨¬P

B.(P∧Q)→P

C.(P→Q)→(Q→P)

D.(P→Q)↔(¬P∨Q)

E.(P∧¬P)→Q

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

1.在命题逻辑中，联结词“非”的符号表示是______。

2.集合A包含元素1,2,3，集合B包含元素2,3,4，则A与B的并集是______。

3.在图论中，一个有n个顶点的无向完全图有______条边。

4.命题公式(P→Q)∧(Q→P)是______。

5.集合A的幂集是指集合A的所有______的集合。

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

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

2.写出命题公式(P∧¬Q)→(R∨¬P)的真值表。

3.给定一个图G，顶点集V={v1,v2,v3,v4}，边集E={(v1,v2),(v2,v3),(v3,v4),(v4,v1),(v1,v3)}。求图G的度数序列。

4.证明命题公式(P→Q)↔(¬Q→¬P)是重言式。

5.设集合A={a,b,c}，求集合A的所有非空子集。

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

一、选择题答案

1.B

2.B

3.A

4.A

5.C

6.A

7.B

8.B

9.C

10.B

二、多项选择题答案

1.A,B,C,D,E

2.A,B,C,D,E

3.A,B,C,D,E

4.A,B,C,D,E

5.A,B,D,E

三、填空题答案

1.¬

2.{1,2,3,4}

3.n(n-1)/2

4.等价式

5.子集

四、计算题答案

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

2.真值表如下：

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

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

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

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

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

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

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

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

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

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

3.度数序列为3,3,3,3。

4.证明：

(P→Q)↔(¬Q→¬P)

(¬P∨Q)↔(¬¬Q∨¬P)

(¬P∨Q)↔(Q∨¬P)

根据对偶律，(P→Q)与(¬Q→¬P)是等价的。

5.集合A的所有非空子集为：{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}。

知识点总结

离散数学是一门研究离散量结构的数学学科，主要包含逻辑、集合论、图论、组合数学等部分。本试卷涵盖了这些部分的基础知识，通过不同题型考察学生对这些知识点的理解和应用能力。

一、选择题考察的知识点

1.命题逻辑的基本联结词和公式

2.集合论的基本运算

3.图论的基本概念

4.等价式和重言式的判断

二、多项选择题考察的知识点

1.命题逻辑的基本联结词

2.集合论的基本运算

3.图论的基本概念

4.等价式和重言式的判断

5.集合的幂集和子集

三、填空题考察的知识点

1.命题逻辑的基本联结词

2.集合论的基本运算

3.图论的基本概念

4.等价式和重言式的判断

5.集合的幂集和子集

四、计算题考察的知识点

1.集合论的基本运算

2.命题逻辑的真值表

3.图论的基本概念

4.等价式的证明

5.集合的子集

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

一、选择题

1.命题逻辑的基本联结词和公式

示例：命题公式(P→Q)∧(Q→P)是等价式，表示P与Q等价。

2.集合论的基本运算

示例：集合A={1,2,3}，集合B={2,3,4}，则A与B的并集是{1,2,3,4}。

3.图论的基本概念

示例：一个有n个顶点的无向完全图有n(n-1)/2条边。

4.等价式和重言式的判断

示例：命题公式P∨¬P是重言式，因为无论P的真值如何，P∨¬P总是为真。

二、多项选择题

1.命题逻辑的基本联结词

示例：命题逻辑中的基本联结词有与（∧），或（∨），非（¬），蕴含（→），等价（↔）。

2.集合论的基本运算

示例：集合论中的基本运算有并集（∪），交集（∩），差集（-），幂集（P(A)），补集（'）。

3.图论的基本概念

示例：图论中的基本概念有顶点（Vertex），边（Edge），邻接（Adjacency），环（Loop），多重边（MultipleEdge）。

4.等价式和重言式的判断

示例：命题公式(P∧Q)↔(Q∧P)是等价式，表示P与Q的顺序可以交换。

5.集合的幂集和子集

示例：集合A={a,b}的幂集是{{},{a},{b},{a,b}}，所有非空子集是{{a},{b},{a,b}}。

三、填空题

1.命题逻辑的基本联结词

示例：联结词“非”的符号表示是¬。

2.集合论的基本运算

示例：集合A={1,2,3}，集合B={2,3,4}，则A与B的并集是{1,2,3,4}。

3.图论的基本概念

示例：一个有n个顶点的无向完全图有n(n-1)/2条边。

4.等价式和重言式的判断

示例：命题公式(P∧¬Q)→(R∨¬P)是等价式。

5.集合的幂集和子集

示例：集合A={a,b,c}的所有非空子集是{{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}。

四、计算题

1.集合论的基本运算

示例：集合A={1,2,3}，集合B={2,3,4}，集合C={2,4,6}，求(A∪B)∩C={2,3,4}∩{2,4,6}={2,4}。

2.命题逻辑的真值表

示例：命题公式(P∧¬Q)→(R∨¬P)的真值表如上所示。

3.图论的基本概念

示例：给定一个图G，顶点集V={v1,v2