华师大软院离散数学试卷

华师大软院离散数学试卷一、选择题（每题1分，共10分）

1.设集合A={1,2,3}，B={2,3,4}，则集合A和B的并集是？

A.{1,2,3}

B.{2,3,4}

C.{1,2,3,4}

D.{1,4}

2.下列哪个不是命题？

A.今天天气很好

B.2+2=4

C.请开门

D.他很高

3.设命题p为“今天是星期一”，命题q为“今天是星期二”，则命题“今天不是星期一”可以表示为？

A.p∧q

B.p∨q

C.¬p

D.¬q

4.下列哪个是永真式？

A.p∧¬p

B.p∨¬p

C.p→p

D.p↔¬p

5.设集合A和B都是有限集合，|A|=m，|B|=n，则集合A和B的笛卡尔积的基数是？

A.m+n

B.mn

C.max(m,n)

D.min(m,n)

6.下列哪个不是图？

A.一个点集和一个边集的集合

B.一个点集和一个边集的函数

C.一个点集和一个边集的二元关系

D.一个点集和一个边集的线性关系

7.设有一个无向图G，其顶点数为n，边数为m，如果G是连通的，则m的最小值是？

A.n-1

B.n

C.n+1

D.2n

8.设有一个有向图G，其顶点数为n，边数为m，如果G是强连通的，则m的最小值是？

A.n-1

B.n

C.n+1

D.2n

9.下列哪个不是树的性质？

A.树中任意两个顶点之间都有且只有一条路径

B.树中至少有一个顶点的度数为0

C.树是连通的但不含环

D.树的顶点数和边数的关系为|E|=|V|-1

10.设有一个命题公式，其对应的命题树的高度为h，则该命题公式的长度至少为？

A.h

B.2h

C.h+1

D.2h+1

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

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.组合

C.二项式系数

D.递推关系

E.图的着色问题

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

1.设命题p为“今天下雨”，命题q为“我出门带伞”，如果“今天不下雨”则“我出门不带伞”用逻辑符号表示为_______。

2.集合A={1,2,3}，B={3,4,5}，则A和B的交集A∩B=_______。

3.一个有n个顶点的无向完全图，其边数m=_______。

4.设命题公式p→q和¬p为真，则命题q的值为_______。

5.在组合数学中，从n个不同元素中取出k个元素的排列数记作P(n,k)，其计算公式为_______。

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

1.已知命题公式A为(p∧q)→¬r，求命题公式A的成真赋值。

2.集合A={1,2,3}，B={2,3,4}，C={3,4,5}，计算(A∪B)∩C的所有元素。

3.一个有向图G包含4个顶点，边集E={<a,b>,<b,c>,<c,d>,<d,a>,<a,c>}，判断图G是否是强连通的，并说明理由。

4.从5个男生和4个女生中选出3人组成一个委员会，其中至少有一个女生，求不同的选法数目。

5.写出命题公式(p∨q)↔(¬p∧¬q)的真值表，并判断该命题公式是永真式、矛盾式还是可满足式。

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

一、选择题答案及解析

1.C{1,2,3,4}并集是两个集合中所有元素的集合，不重复。

2.D“他很高”不是命题，因为它没有明确的真值。

3.C¬p今天不是星期一，即命题p的否定。

4.Bp∨¬p根据排中律，p或非p必有一个为真。

5.Bmn笛卡尔积的基数是两个集合基数的乘积。

6.D一个点集和一个边集的线性关系线性关系不是图论中的基本概念。

7.An-1连通无向图的最小边数是顶点数减一，形成一棵树。

8.Bn强连通有向图的最小边数是顶点数，保证所有顶点间都有双向路径。

9.D树的顶点数和边数的关系为|E|=|V|-1这是森林的性质，树是特殊的森林。

10.B2h命题树的高度h表示公式的长度至少为2h，因为每个非叶节点最多有两个子节点。

二、多项选择题答案及解析

1.A,B,C,D假言推理、拒绝式推理、合取引入、析取三段论都是常见推理规则。

2.A,B,D并集、交集、补集运算满足交换律。

3.A,B,C,D顶点、边、路径、环是图论的基本概念。

4.A,B,C,D,E非、与、或、蕴含、等价都是常见的逻辑连接词。

5.A,B,C,D,E排列、组合、二项式系数、递推关系、图的着色问题都是组合数学中的常见问题。

三、填空题答案及解析

1.¬p↔¬q根据逆否律，今天不下雨等价于我出门不带伞。

2.{3}交集是两个集合中都有的元素。

3.n(n-1)/2无向完全图的每对顶点之间都有一条边，总边数为组合数C(n,2)。

4.真p→q为真且¬p为真，根据反证法，q必为真。

5.n!/(n-k)!从n个元素中取出k个元素的排列数公式。

四、计算题答案及解析

1.成真赋值为p=F,q=T,r=F。当p为假时，p∧q为假，¬r为真，命题公式为真。

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

3.不是强连通的。因为顶点a无法通过边直接到达顶点b。

4.34种。可以分为三类：1女2男，2女1男，3女。分别计算组合数相加。

5.真值表略。该命题公式是矛盾式，因为其真值表中所有赋值都为假。

知识点分类和总结

集合论：集合的基本运算（并、交、差、补）、集合的性质（交换律、结合律、分配律）、集合的基数、笛卡尔积。

命题逻辑：命题的定义、逻辑连接词（非、与、或、蕴含、等价）、命题公式、真值表、推理规则（假言推理、拒绝式推理等）、永真式、矛盾式、可满足式。

图论：图的定义（顶点、边）、无向图、有向图、路径、环、连通性（连通图、强连通图）、树、森林。

组合数学：排列、组合、二项式系数、递推关系、图的着色问题。

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

选择题：考察学生对基本概念的掌握程度，如集合运算、命题逻辑连接词、图论基本概念等。示例：判断一个命题是否为命题，考察学生对命题定义的理解。

多项选择题：考察学生对多个相关概念的理解和区分能力，如推理规则、集合运算性质等。示例：判断哪些运算满足交换律，考察学生对集合运算性质