离散数学试题及答案

离散数学试题及答案

一、单选题（每题2分，共20分）

1.下列哪个不是命题？（）A.今天天气很好B.2+3=5C.请开门D.地球是圆的【答案】C【解析】命题是可以判断真假的陈述句，请开门是祈使句，不是命题

2.设A={1,2,3}，B={2,3,4}，则A∩B等于（）A.{1,2}B.{3,4}C.{2,3}D.{1,4}【答案】C【解析】A和B的交集是它们共有的元素，即{2,3}

3.下列哪个是可判定问题？（）A.停机问题B.图论中的Hamilton回路问题C.素数判定问题D.旅行商问题【答案】C【解析】素数判定问题是可判定的，而停机问题、Hamilton回路问题和旅行商问题是不可判定的

4.设A={x|x∈N且x5}，则A的幂集PA的元素个数是（）A.4B.8C.16D.32【答案】C【解析】A={1,2,3,4}，其幂集的元素个数为2^4=

165.下列哪个不是图G的顶点u和顶点v之间的边e的表示方式？（）A.u,vB.u,vC.u→vD.u—v【答案】C【解析】顶点间边的表示方式通常用u,v、u,v或u—v表示，u→v一般表示有向边

6.一个有向图D是强连通的，当且仅当（）A.D中任意两个顶点间都有边B.D中任意两个顶点间都有有向边C.D中存在一条从每个顶点到其他所有顶点的路径D.D中存在一条从每个顶点到其他所有顶点的有向路径【答案】D【解析】强连通是指图中任意两个顶点间都有有向路径

7.设f:ℕ→ℕ为fx=x+1，则f是（）A.单射B.满射C.双射D.非单射非满射【答案】A【解析】fx=x+1是单射，因为不同的x映射到不同的y

8.在命题逻辑中，p→q∧q→r等价于（）A.p→rB.r→pC.p∨rD.r∨p【答案】A【解析】根据逻辑蕴涵的性质，p→q∧q→r等价于p→r

9.设A={1,2,3}，B={1,2,3,4}，则A到B的函数f的数量是（）A.4B.9C.16D.24【答案】D【解析】A到B的函数数量为|B|^|A|=4^3=

6410.下列哪个不是等价关系？（）A.数轴上的点与其实数的对应关系B.集合的包含关系C.整数的模n等价关系D.字符串的字典序关系【答案】B【解析】集合的包含关系不是等价关系，因为它不满足对称性和传递性

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

1.以下哪些是图论中的基本概念？（）A.顶点B.边C.路径D.环E.函数【答案】A、B、C、D【解析】顶点、边、路径和环都是图论的基本概念，函数不是

2.以下哪些是可计算问题？（）A.阶乘计算B.素数判定C.图的着色问题D.排序问题E.停机问题【答案】A、B、C、D【解析】阶乘计算、素数判定、图的着色问题和排序问题都是可计算的，停机问题不可计算

3.以下哪些是命题逻辑中的基本联结词？（）A.非B.且C.或D.如果...那么...E.当且仅当【答案】A、B、C、D、E【解析】非、且、或、如果...那么...和当且仅当都是命题逻辑中的基本联结词

4.以下哪些是偏序关系的性质？（）A.自反性B.对称性C.传递性D.反自反性E.反对称性【答案】A、C、E【解析】偏序关系具有自反性、传递性和反对称性

5.以下哪些是图G的连通性质？（）A.强连通B.单连通C.弱连通D.连通E.部分连通【答案】A、C、D【解析】强连通、弱连通和连通是图G的连通性质

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

1.设A={1,2,3}，B={2,3,4}，则A×B=________【答案】{1,2,1,3,1,4,2,2,2,3,2,4,3,2,3,3,3,4}

2.一个有n个顶点的无向完全图有________条边【答案】nn-1/

23.命题p:今天下雨，q:我带伞，则¬p∧q的意思是________【答案】今天不下雨且我带伞

4.设f:ℕ→ℕ为fx=2x，则f是________【答案】单射

5.集合A={1,2,3}的所有子集共有________个【答案】

86.在图论中，一个有n个顶点和m条边的无向图称为________图【答案】n,m

7.设R是集合A上的等价关系，则A关于R的商集A/R等于________【答案】A的等价类集合

8.在命题逻辑中，p∨q∧r等价于________【答案】p∨q∧p∨r

四、判断题（每题2分，共20分）

1.一个函数可以不是单射（）【答案】（√）【解析】函数可以不是单射，例如fx=x^

22.一个图如果是连通的，那么它一定是强连通的（）【答案】（×）【解析】连通不一定是强连通，例如一个无向图

3.一个命题公式如果是重言式，那么它的对偶式也是重言式（）【答案】（√）【解析】重言式的对偶式也是重言式

4.一个集合的幂集是其所有子集的集合（）【答案】（√）【解析】幂集就是集合的所有子集的集合

5.一个偏序关系一定是等价关系（）【答案】（×）【解析】偏序关系不一定是等价关系，因为它不满足对称性

五、简答题（每题5分，共20分）

1.简述什么是命题逻辑【答案】命题逻辑是研究命题及其联结词的推理规则的数学分支命题是能够判断真假的陈述句，联结词包括非、且、或、如果...那么...和当且仅当

2.简述什么是图【答案】图是由顶点和边组成的数学结构，用于表示对象之间的关系顶点表示对象，边表示对象之间的联系

3.简述什么是等价关系【答案】等价关系是集合上的一种二元关系，具有自反性、对称性和传递性等价关系将集合分成若干个等价类，同一等价类内的元素视为等价

4.简述什么是函数【答案】函数是一种特殊的映射，将一个集合（定义域）中的每个元素映射到另一个集合（值域）中的唯一元素函数具有单射、满射和双射等性质

六、分析题（每题10分，共20分）

1.分析命题公式p∧q∨r和p∧q∨p∧r之间的逻辑关系【答案】p∧q∨r和p∧q∨p∧r是逻辑等价的根据分配律，p∧q∨r可以展开为p∧q∨p∧r这是因为p∧q∨r表示p为真且q为真或r为真，而p∧q∨p∧r也表示p为真且q为真或r为真

2.分析图论中连通性和强连通性的区别【答案】连通性和强连通性都是图论中的连通性质，但它们有所不同连通性是指图中任意两个顶点之间存在路径，而强连通性是指图中任意两个顶点之间存在有向路径简单来说，连通性是无向图的概念，而强连通性是有向图的概念一个强连通的图一定是连通的，但一个连通的图不一定是强连通的

七、综合应用题（每题25分，共50分）

1.设A={1,2,3}，B={a,b,c}，构造一个A到B的双射函数f，并证明其双射性【答案】构造一个双射函数f:A→B为f1=a，f2=b，f3=c证明其双射性首先证明单射性，即不同的x映射到不同的y假设fx1=fx2，则a=b，因为f1=a，f2=b，所以x1=1，x2=2同理，fx1=fx2只能有x1=x2，所以f是单射的其次证明满射性，即B中的每个元素都是A中某个元素的像a是f1的像，b是f2的像，c是f3的像，所以f是满射的因此，f是双射的

2.设有一个无向图G，顶点集V={v1,v2,v3,v4,v5}，边集E={v1,v2,v1,v3,v2,v3,v3,v4,v4,v5}画出该图，并判断其是否连通如果是连通的，找出其所有连通分量【答案】画出图G v1—v2，v1—v3，v2—v3，v3—v4，v4—v5图G是连通的，因为它存在从每个顶点到其他所有顶点的路径其所有连通分量只有一个，即整个图G完整标准答案

一、单选题

1.C

2.C

3.C

4.C

5.C

6.D

7.A

8.A

9.D

10.B

二、多选题

1.A、B、C、D

2.A、B、C、D

3.A、B、C、D、E

4.A、C、E

5.A、C、D

三、填空题

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

2.nn-1/

23.今天不下雨且我带伞

4.单射

5.

86.n,m

7.A的等价类集合

8.p∨q∧p∨r

四、判断题

1.√

2.×

3.√

4.√

5.×

五、简答题

1.命题逻辑是研究命题及其联结词的推理规则的数学分支命题是能够判断真假的陈述句，联结词包括非、且、或、如果...那么...和当且仅当

2.图是由顶点和边组成的数学结构，用于表示对象之间的关系顶点表示对象，边表示对象之间的联系

3.等价关系是集合上的一种二元关系，具有自反性、对称性和传递性等价关系将集合分成若干个等价类，同一等价类内的元素视为等价

4.函数是一种特殊的映射，将一个集合（定义域）中的每个元素映射到另一个集合（值域）中的唯一元素函数具有单射、满射和双射等性质

六、分析题

1.p∧q∨r和p∧q∨p∨r是逻辑等价的根据分配律，p∧q∨r可以展开为p∧q∨p∧r这是因为p∧q∨r表示p为真且q为真或r为真，而p∧q∨p∧r也表示p为真且q为真或r为真

2.连通性是指图中任意两个顶点之间存在路径，而强连通性是指图中任意两个顶点之间存在有向路径简单来说，连通性是无向图的概念，而强连通性是有向图的概念一个强连通的图一定是连通的，但一个连通的图不一定是强连通的

七、综合应用题

1.构造一个双射函数f:A→B为f1=a，f2=b，f3=c证明其双射性首先证明单射性，即不同的x映射到不同的y假设fx1=fx2，则a=b，因为f1=a，f2=b，所以x1=1，x2=2同理，fx1=fx2只能有x1=x2，所以f是单射的其次证明满射性，即B中的每个元素都是A中某个元素的像a是f1的像，b是f2的像，c是f3的像，所以f是满射的因此，f是双射的

2.画出图G v1—v2，v1—v3，v2—v3，v3—v4，v4—v5图G是连通的，因为它存在从每个顶点到其他所有顶点的路径其所有连通分量只有一个，即整个图G。