江南大学离散数学试卷

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

1.在集合论中，集合A包含元素1,2,3，集合B包含元素2,3,4，则集合A与集合B的交集是？

A.{1,2,3,4}

B.{2,3}

C.{1}

D.∅

2.下列哪个不是命题？

A.今天天气很好。

B.2+2=5。

C.请开门。

D.这个数是偶数。

3.命题公式(p→q)↔(¬p∨q)的等价形式是？

A.p↔q

B.p→q

C.¬p↔¬q

D.p∨¬q

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

A.p∧¬p

B.p∨¬p

C.p→¬p

D.¬p→p

5.在谓词逻辑中，∀x(P(x)→Q(x))的否定是？

A.∀x(P(x)∧¬Q(x))

B.∃x(P(x)∧¬Q(x))

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

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

6.设有一个有向图G，其顶点集V={v1,v2,v3,v4}，边集E={(v1,v2),(v2,v3),(v3,v4),(v4,v1)}，则图G的邻接矩阵是？

A.

0100

0010

0001

1000

B.

1001

0100

0010

0001

C.

0100

0010

0001

1000

D.

1001

0100

0010

0001

7.在图论中，一棵树的边数与其顶点数的关系是？

A.边数=顶点数

B.边数=顶点数-1

C.边数=顶点数+1

D.边数=2×顶点数

8.在组合数学中，从n个不同元素中取出k个元素的组合数记作C(n,k)，其计算公式是？

A.C(n,k)=n!/(k!×(n-k)!)

B.C(n,k)=k!/(n!×(n-k)!)

C.C(n,k)=n!/k!

D.C(n,k)=k!/n!

9.在数理逻辑中，下列哪个是正确的推理规则？

A.拒绝前件

B.合取引入

C.选择引入

D.演绎推理

10.在布尔代数中，下列哪个是正确的等式？

A.a+a=0

B.a×a=0

C.a+0=a

D.a×1=0

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

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

A.与

B.或

C.非

D.如果

E.当且仅当

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

A.并集

B.交集

C.差集

D.补集

E.笛卡尔积

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

A.无环

B.连通

C.顶点数等于边数加1

D.可以有多个根

E.每对顶点之间有唯一路径

4.在组合数学中，下列哪些是排列的计算公式？

A.P(n,k)=n!/(n-k)!

B.P(n,k)=n×(n-1)×...×(n-k+1)

C.P(n,k)=k!/(n-k)!

D.P(n,k)=n!/k!

E.P(n,k)=n×k

5.在数理逻辑中，下列哪些是正确的推理规则？

A.假言推理

B.拒绝后件

C.合取消除

D.析取引入

E.演绎推理

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

1.在命题逻辑中，公式(p∧q)→r的对偶式是________。

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

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

4.在组合数学中，从n个不同元素中取出k个元素的组合数记作________，其计算公式是________。

5.在谓词逻辑中，∀x(P(x)→Q(x))的否定是________。

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

1.对于命题公式(p→q)↔(¬p∨q)，写出它的真值表，并判断它是否是重言式。

2.设集合A={x|x是小于10的正偶数}，B={x|x是小于10的正奇数}，C={1,3,5,7}。求(A∪B)×C。

3.给定有向图G的邻接矩阵如下：

```

0101

0010

0001

0000

```

求图G的度数序列，并判断图G是否是强连通的。

4.计算C(10,3)和P(10,3)，并解释它们的区别。

5.对于谓词逻辑公式∀x∃y(P(x,y)∧Q(y))，假设解释域为自然数集合N，P(x,y)表示"x小于y"，Q(y)表示"y是偶数"。在该解释下，判断该公式是否为真。

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

一、选择题答案

1.B

2.D

3.B

4.B

5.A

6.A

7.B

8.A

9.B

10.C

二、多项选择题答案

1.A,B,C

2.A,B,D,E

3.A,B,C,E

4.A,B

5.A,C,E

三、填空题答案

1.(p∨q)→r

2.{1,2,3,4},{2,3}

3.n(n-1)/2

4.C(n,k),n!/(k!×(n-k)!)

5.∃x(P(x)∧¬Q(x))

四、计算题答案

1.真值表：

|p|q|p→q|¬p∨q|(p→q)↔(¬p∨q)|

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

|T|T|T|T|T|

|T|F|F|F|T|

|F|T|T|T|T|

|F|F|T|T|T|

该公式是重言式。

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

3.度数序列：3,2,2,0。图G不是强连通的，因为存在顶点无法通过有向边到达所有其他顶点。

4.C(10,3)=10!/(3!×(10-3)!)=120，P(10,3)=10!/(10-3)!=720。组合数表示从10个元素中取3个不考虑顺序，排列数表示考虑顺序。

5.假设解释域为自然数集合N，P(x,y)表示"x小于y"，Q(y)表示"y是偶数"。对于任意自然数x，存在一个自然数y（例如y=x+1）使得P(x,y)为真（因为x<x+1）。同时，如果y是偶数，则Q(y)为真。因此，对于任意自然数x，总能找到一个自然数y（当y为偶数时）使得P(x,y)∧Q(y)为真。所以该公式为真。

知识点分类和总结

离散数学的理论基础部分主要包括以下知识点：

1.集合论：集合的运算（并集、交集、差集、补集）、集合的性质、笛卡尔积等。

2.命题逻辑：命题、联结词、真值表、推理规则、对偶式等。

3.谓词逻辑：谓词、量词、解释域、公式等。

4.图论：图的表示（邻接矩阵）、图的性质（无环、连通、度数序列）、图的类型（完全图、强连通图）等。

5.组合数学：排列、组合、组合数计算公式等。

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

一、选择题

-考察学生对命题逻辑、集合论、图论、组合数学等基本概念的掌握程度。

-示例：选择题第1题考察集合的交集运算，第6题考察图的邻接矩阵表示。

二、多项选择题

-考察学生对多个相关概念的理解和区分能力。

-示例：多项选择题第1题考察命题逻辑