广西大学离散数学试卷

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

1.下列哪个命题在数理逻辑中是永真的？

A.P∨¬P

B.P∧¬P

C.P→P

D.P↔¬P

2.在集合论中，集合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,4,5}

3.下列哪个是正确的命题公式？

A.(P∧Q)→P

B.(P→Q)∧(Q→P)

C.(P∨Q)↔(¬P∧¬Q)

D.(P∧¬P)∨Q

4.在图论中，一个无向图中每个顶点的度数之和等于？

A.图的边数

B.2倍图的边数

C.图的顶点数

D.2倍图的顶点数

5.下列哪个是正确的等价式？

A.P↔(Q→P)

B.(P∧Q)↔(Q∧P)

C.(P∨Q)↔(¬P∧¬Q)

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

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

A.P∨¬P

B.P∧¬P

C.(P∧Q)→P

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

7.在集合论中，集合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,4,5}

8.在图论中，一个有向图中所有顶点的入度之和等于？

A.图的边数

B.2倍图的边数

C.图的顶点数

D.2倍图的顶点数

9.下列哪个是正确的蕴涵式？

A.P→(Q→P)

B.(P→Q)→(Q→P)

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

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

10.在命题逻辑中，下列哪个是矛盾式？

A.P∨¬P

B.P∧¬P

C.(P∧Q)→P

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

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

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

A.非

B.合取

C.析取

D.蕴含

E.等价

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

A.并集

B.交集

C.差集

D.补集

E.幂集运算

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

A.顶点

B.边

C.度数

D.路径

E.函数

4.下列哪些是命题逻辑中的重言式？

A.P∨¬P

B.P∧¬P

C.(P∧Q)→P

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

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

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

A.幂集合

B.并集

C.交集

D.差集

E.补集

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

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

2.集合A={1,2,3}与集合B={3,4,5}的差集A-B=______。

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

4.命题公式(P→Q)↔(¬Q→¬P)的逻辑等价式是______。

5.集合A={1,2,3}的幂集P(A)中的元素个数是______。

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

1.对于命题公式P→(Q∧¬R)，请写出它的真值表。

2.设集合A={x|x∈N,1≤x≤5},B={x|x∈N,3≤x≤7},请计算A∩B和A∪B。

3.给定图G=<V,E>，其中V={a,b,c,d}，E={(a,b),(a,c),(b,d),(c,d)}，请计算每个顶点的度数，并判断该图是否是连通图。

4.对于命题公式(P↔Q)→(R→P)，请证明它是重言式。

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

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

一、选择题答案

1.A

2.A

3.A

4.B

5.B

6.A

7.B

8.A

9.A

10.B

二、多项选择题答案

1.A,B,C,D,E

2.A,B,C,D

3.A,B,C,D

4.A,C,D

5.A,B,C,D,E

三、填空题答案

1.¬(P∧Q)

2.{1,2}

3.n(n-1)/2

4.P↔Q

5.8

四、计算题答案及解题过程

1.真值表：

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

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

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

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

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

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

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

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

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

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

2.计算：

A∩B={x|x∈N,1≤x≤5}∩{x|x∈N,3≤x≤7}={3,4,5}

A∪B={x|x∈N,1≤x≤5}∪{x|x∈N,3≤x≤7}={1,2,3,4,5}

3.计算顶点度数：

度(a)=2,度(b)=2,度(c)=2,度(d)=2

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

4.证明重言式：

(P↔Q)→(R→P)等价于¬(P↔Q)∨(¬R∨P)

等价于¬((P→Q)∧(Q→P))∨¬R∨P

等价于¬((¬P∨Q)∧(¬Q∨P))∨¬R∨P

等价于¬(¬P∨Q)∨¬(¬Q∨P)∨¬R∨P

等价于(P∧¬Q)∨(Q∧¬P)∨¬R∨P

等价于(P∧¬Q∨¬R∨P)∨(Q∧¬P∨¬R∨P)

等价于P∨(¬Q∨¬R)∨(Q∧¬P∨¬R∨P)

等价于P∨¬Q∨¬R∨Q∧¬P∨¬R∨P

等价于T（因为P∨¬P=T，¬Q∨Q=T）

所以(P↔Q)→(R→P)是重言式。

5.计算：

A×B={(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,2),(3,3),(3,4)}

B×C={(2,3),(2,4),(2,5),(3,3),(3,4),(3,5),(4,3),(4,4),(4,5)}

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

知识点分类和总结

集合论：

-集合的基本运算：并集、交集、差集、补集

-集合的性质：幂集、交换律、结合律、分配律

-集合的表示：列举法、描述法

命题逻辑：

-基本联结词：非、合取、析取、蕴含、等价

-命题公式：真值表、重言式、矛盾式、等价式

-蕴含式：逻辑推理、推理规则

图论：

-图的基本概念：顶点、边、度数、路径

-图的性质：连通图、完全图

-图的表示：集合表示、矩阵表示

计算题考察学生的知识点详解及示例

1.真值表：通过列出所有可能的真值组合，验证命题公式的真假情况。

示例：P→(Q∧¬R)的真值表，需要考虑P、Q、R的所有八种组合。

2.集合运算：计算集合的并集、交集、差集等，需要掌握集合的基本运算规则。

示例：A∩B和A∪B的计算，需要找出两个集合的共同元素和所有元素。

3.图的度数和连通性：计算每个顶点的度数，判断图是否连通，需要理解图的基本概念和性质。

示例：度(a)=2