华东理工离散数学试卷

华东理工离散数学试卷一、选择题（每题1分，共10分）

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

A.非

B.且

C.或

D.等价

2.在命题逻辑中，命题公式(P→Q)↔(¬P∨Q)的逻辑关系是？

A.等价

B.矛盾

C.含取

D.不可判定

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

A.∨

B.∧

C.∀

D.→

4.在谓词逻辑中，表达式∀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)的必要条件

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

A.群

B.环

C.域

D.连通性

6.在图论中，一个图G的补图是指？

A.G的所有边

B.G的所有顶点

C.G的所有顶点和边

D.G的所有顶点但不包括G的所有边

7.在图论中，树是一种特殊的图，下列哪个不是树的性质？

A.没有环

B.连通

C.有n个顶点，n-1条边

D.有多个根

8.在组合数学中，排列是指？

A.集合中元素的有序选择

B.集合中元素的无序选择

C.集合中元素的重复选择

D.集合中元素的不重复选择

9.在组合数学中，组合是指？

A.集合中元素的有序选择

B.集合中元素的无序选择

C.集合中元素的重复选择

D.集合中元素的不重复选择

10.在数理逻辑中，公理系统是指？

A.一组公理和推理规则

B.一组定理和推理规则

C.一组公式和推理规则

D.一组命题和推理规则

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

1.下列哪些是命题逻辑的基本公式？

A.P∧Q

B.¬P

C.(P∨Q)→R

D.P↔Q

2.在谓词逻辑中，下列哪些是量词的用法？

A.∀x(P(x)→Q(x))

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

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

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

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

A.顶点

B.边

C.环

D.连通性

4.在组合数学中，下列哪些是排列和组合的应用？

A.排列数公式P(n,k)=n!/(n-k)!

B.组合数公式C(n,k)=n!/(k!(n-k)!)

C.排列和组合的递推关系

D.排列和组合的生成函数

5.在数理逻辑中，下列哪些是公理系统的组成部分？

A.公理

B.推理规则

C.定理

D.证明

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

1.在命题逻辑中，表达式(P∧Q)∨¬R的对偶式是_______。

2.谓词逻辑中的量词∀和∃分别表示_______和_______。

3.在图论中，一个有n个顶点的无向图，其补图中的边数是_______。

4.组合数学中的排列数公式P(n,k)表示从n个不同元素中取出k个元素的_______数。

5.数理逻辑中的命题公式(P→Q)↔(¬P∨Q)是_______式。

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

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

2.对于谓词逻辑公式∀x∃y(P(x,y)∧Q(y,z))，解释其含义，并说明其真值依赖于哪些变量。

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

4.计算组合数C(10,3)和排列数P(10,3)，并解释它们在实际问题中的区别。

5.对于数列{an}，其递推关系为a1=1，an=an-1+2n(n≥2)。求通项公式an，并用数学归纳法证明其正确性。

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

一、选择题答案

1.D

2.A

3.C

4.A

5.D

6.D

7.D

8.A

9.B

10.A

二、多项选择题答案

1.A,B,C,D

2.A,B,C,D

3.A,B,D

4.A,B,C,D

5.A,B

三、填空题答案

1.(¬P∨¬Q)∧R

2.全称量词，存在量词

3.n(n-1)/2

4.有序

5.等价

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

1.真值表：

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

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

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

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

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

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

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

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

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

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

该公式不是重言式，因为在第一行中(P∧Q)→¬R为假。

2.∀x∃y(P(x,y)∧Q(y,z))的含义是：对于所有的x，存在一个y，使得P(x,y)和Q(y,z)同时为真。其真值依赖于变量x,y,z以及谓词P和Q的定义。

3.度数序列：d(v1)=2,d(v2)=2,d(v3)=2,d(v4)=2。该图不是树，因为树需要满足每个顶点度数为1或2，且图是连通的。此图中每个顶点的度数为2，不符合树的定义。

4.C(10,3)=10!/(3!*(10-3)!)=120，P(10,3)=10!/(10-3)!=720。排列数C(n,k)表示从n个不同元素中取出k个元素的有序组合，而组合数P(n,k)表示从n个不同元素中取出k个元素的无序组合。

5.通项公式an=2n^2-n+1。

证明：

基础情况：n=1时，a1=1，符合公式。

归纳假设：假设对于某个k≥1，ak=2k^2-k+1成立。

归纳步骤：证明ak+1=2(k+1)^2-(k+1)+1。

ak+1=ak+2(k+1)=(2k^2-k+1)+2k+2=2k^2+4k+3=2(k+1)^2-(k+1)+1。

因此，通项公式成立。

知识点分类和总结

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

1.命题逻辑：包括命题、联结词、公式的真值表、等价式、蕴含式等。

2.谓词逻辑：包括谓词、量词、公式的含义、真值等。

3.图论：包括图的基本概念、性质、树、图的遍历等。

4.组合数学：包括排列、组合、递推关系、生成函数等。

5.数理逻辑：包括公理系统、推理规则、证明方法等。

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

一、选择题：考察学生对基本概念和定义的理解，例如命题逻辑的基本联结词、谓词逻辑的量词、图论的基本概念、组合数学的排列和组合、数理逻辑的公理系统等。

二、多项选择题：考察学生对多个相关概念的综合理解和应用，例如命题逻辑和谓词逻辑的公式、图论的基本概念和性质、组合数学的应用、数理逻辑的公理系统等。

三、填空题：考察学生对基本概念的准确记忆和表达，例如命题逻辑的对偶式、谓词逻辑的量词、图论中的度数序列、组合数学中的排列和组合、数理逻辑的等价式等。

四、计算题：考察学生对基本概念和方法的综合应用能力，例如命题逻辑的真值表、谓词逻辑的公式含义、图论中的度数序列和树的性质、组合数学的排列和组合计算、数理逻辑的递推关系和证明等。

示例：

1.命题逻辑：P