考研离散数学试卷_第1页
考研离散数学试卷_第2页
考研离散数学试卷_第3页
考研离散数学试卷_第4页
考研离散数学试卷_第5页
已阅读5页,还剩5页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

考研离散数学试卷一、选择题(每题1分,共10分)

1.下列哪个集合是有限集?

A.自然数集

B.整数集

C.有理数集

D.{1,2,3,...,100}

2.下列哪个命题是永真式?

A.p∨¬p

B.p∧¬p

C.p→¬p

D.¬(p∧q)→¬p

3.设A={1,2,3},B={2,3,4},则A∩B等于?

A.{1,2}

B.{3,4}

C.{2,3}

D.{1,4}

4.下列哪个是有效的推理形式?

A.(p→q)∧q→p

B.(p→q)∧¬q→¬p

C.(p∧q)→p

D.p→(q→p)

5.设f:A→B是一个函数,A={1,2,3},B={a,b,c},则下列哪个是可能的函数?

A.f={(1,a),(2,b),(3,c)}

B.f={(1,a),(2,a),(3,b)}

C.f={(1,b),(2,c),(3,a)}

D.f={(1,c),(2,a),(3,b)}

6.下列哪个是图G的Eulerian回路?

A.G中所有顶点的度数都是偶数,且G连通

B.G中所有顶点的度数都是奇数,且G连通

C.G中存在一条经过所有边的路径,且起点和终点相同

D.G中存在一条经过所有顶点的路径,且每条边恰好经过一次

7.下列哪个是偏序集?

A.(N,≤)

B.(Z,<)

C.(Q,≥)

D.(R,≠)

8.下列哪个是可判定问题?

A.判断一个图是否是连通的

B.判断一个图是否是Eulerian图

C.判断一个图是否是Hamiltonian图

D.判断一个命题公式是否是永真式

9.下列哪个是可计算问题?

A.判断一个数是否是素数

B.判断一个数是否是偶数

C.判断一个数是否是合数

D.判断一个数是否是黄金分割数

10.下列哪个是图G的着色问题?

A.用k种颜色给图G的顶点着色,使得相邻顶点颜色不同

B.用k种颜色给图G的边着色,使得相邻边颜色不同

C.用k种颜色给图G的顶点着色,使得所有顶点颜色相同

D.用k种颜色给图G的边着色,使得所有边颜色相同

二、多项选择题(每题4分,共20分)

1.下列哪些是命题逻辑的永真式?

A.p∨¬p

B.(p∧q)→p

C.(p→q)→(¬q→¬p)

D.p∧(q∧r)↔(p∧q)∧r

2.设A={1,2,3},B={2,3,4},C={3,4,5},则下列哪些集合运算结果是有限集?

A.A∪B

B.A∩C

C.B∩C

D.A×B

3.下列哪些是有效的推理形式?

A.(p∧q)→p

B.(p→q)∧p→q

C.(p→q)∧(q→r)→(p→r)

D.p→(q→p)

4.设f:A→B是一个函数,A={1,2,3},B={a,b,c},则下列哪些是可能的函数?

A.f={(1,a),(2,b),(3,c)}

B.f={(1,a),(2,a),(3,b)}

C.f={(1,b),(2,c),(3,a)}

D.f={(1,c),(2,a),(3,b),(2,c)}

5.下列哪些是图G的Eulerian路径?

A.G中所有顶点的度数都是偶数,且G连通

B.G中恰好有两个顶点的度数是奇数,且G连通

C.G中存在一条经过所有边的路径,且起点和终点不同

D.G中存在一条经过所有顶点的路径,且每条边恰好经过一次

三、填空题(每题4分,共20分)

1.若命题p为“今天下雨”,q为“我出门不带伞”,则命题“如果今天下雨,那么我出门不带伞”的逻辑表达式为______。

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

3.在命题逻辑中,永真式的定义是______。

4.设f:A→B是一个函数,A={1,2},B={a,b},则函数f的所有可能个数为______。

5.一个图G是Eulerian图的充分必要条件是______。

四、计算题(每题10分,共50分)

1.对于命题公式p∧(q∨¬r)→(¬p∨r),请写出其真值表,并判断该公式是否为永真式。

2.设集合A={1,2,3},B={2,3,4},C={3,4,5}。计算A×(B∩C)和(A×B)∩(A×C)的结果。

3.给定函数f:Z→Z,定义为f(x)=x+1。请判断该函数是否为单射、满射、双射,并说明理由。

4.考虑图G,其顶点集V={v1,v2,v3,v4},边集E={(v1,v2),(v1,v3),(v2,v4),(v3,v4)}。请计算该图的度数列,并判断该图是否为连通图。

5.对于偏序集(S,≤),其中S={a,b,c,d},偏序关系≤如下所示:

a≤a

a≤b

a≤c

b≤b

b≤c

c≤c

d≤d

请画出该偏序集的Hasse图,并找出其所有极大元和极小元。

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

一、选择题答案

1.D

2.A

3.C

4.C

5.A

6.A

7.A

8.D

9.A

10.A

二、多项选择题答案

1.A,B,C,D

2.A,B,C,D

3.A,B,C

4.A,B,C

5.B,C

三、填空题答案

1.p→q

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

3.对于任意输入的真值组合,该命题公式都为真

4.4

5.图G中所有顶点的度数都是偶数,且G连通

四、计算题答案

1.真值表:

|p|q|r|¬r|q∨¬r|p∧(q∨¬r)|¬p|¬p∨r|(p∧(q∨¬r))→(¬p∨r)|

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

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

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

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

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

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

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

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

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

该公式为永真式。

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

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

3.f(x)=x+1是单射,因为对于任意x1,x2∈Z,若f(x1)=f(x2),则x1+1=x2+1,即x1=x2。

f(x)=x+1不是满射,因为不存在x∈Z使得f(x)=0,即0∉Im(f)。

f(x)=x+1不是双射,因为它不是满射。

4.度数列:deg(v1)=2,deg(v2)=2,deg(v3)=2,deg(v4)=1。

该图不是连通图,因为顶点v4与其他顶点不相连。

5.Hasse图:

```

b

/\

ac

/

d

```

极大元:{b,c}

极小元:{d}

知识点分类和总结

1.命题逻辑

-命题:能够判断真假的陈述句。

-逻辑连接词:¬(非),∧(与),∨(或),→(蕴涵),↔(双蕴涵)。

-永真式:对于任意真值赋值,命题公式都为真的表达式。

-推理形式:从前提推导出结论的合法形式。

2.集合论

-集合:一组确定的、互不相同的对象的全体。

-集合运算:并集(∪),交集(∩),差集(-),笛卡尔积(×)。

-子集:A⊆B表示集合A中的每个元素都是集合B中的元素。

3.函数

-函数:一个集合到另一个集合的映射。

-单射:对于任意x1,x2∈A,若f(x1)=f(x2),则x1=x2。

-满射:对于任意y∈B,都存在x∈A使得f(x)=y。

-双射:既是单射又是满射的函数。

4.图论

-图:由顶点集合和边集合组成的结构。

-度数:与顶点相连的边的数量。

-Eulerian图:所有顶点的度数都是偶数,且图连通。

-连通图:任意两个顶点之间都存在路径的图。

5.偏序集

-偏序关系:满足自反性、反对称性和传递性的关系。

-Hasse图:偏序集的图形表示,忽略传递闭包中的边。

-极大元:没有其他元素严格大于它的元素。

-极小元:没有其他元素严格小于它的元素。

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

1.选择题

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

-示例:判断一个命题公式是否

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论