离散数学期末考试题及答案.docxVIP

离散数学期末考试题及答案

一、选择题（每题3分，共30分）

1.下列语句中，是命题的是（）

A.请把门关上B.$x+56$C.地球外的星球上也有人D.明天去旅游吗

2.设$P$：天下雨，$Q$：我骑车上班。则命题“除非天下雨，否则我骑车上班”可符号化为（）

A.$P\toQ$B.$Q\toP$C.$\negP\toQ$D.$\negQ\toP$

3.公式$\forallx(P(x)\toQ(x))$中，$\forallx$的辖域是（）

A.$P(x)$B.$Q(x)$C.$P(x)\toQ(x)$D.以上都不对

4.设集合$A=\{1,2,3\}$，$B=\{2,3,4\}$，则$A\capB$等于（）

A.$\{1,2,3,4\}$B.$\{2,3\}$C.$\{1\}$D.$\{4\}$

5.设$R$是集合$A$上的等价关系，$a\inA$，则$[a]_R$表示（）

A.元素$a$的等价类B.集合$A$C.集合$A$中与$a$不相等的元素D.以上都不对

6.设函数$f:A\toB$，$g:B\toC$，若$g\circf$是满射，则（）

A.$f$是满射B.$g$是满射C.$f$是单射D.$g$是单射

7.设图$G=(V,E)$，其中$V=\{v_1,v_2,v_3,v_4\}$，$E=\{(v_1,v_2),(v_2,v_3),(v_3,v_4),(v_4,v_1)\}$，则$G$是（）

A.无向图B.有向图C.树D.多重图

8.一个连通无向图$G$有10个顶点，12条边，则$G$的面数为（）

A.2B.3C.4D.5

9.设代数系统$(G,)$是群，$a,b\inG$，则$(ab)^{-1}$等于（）

A.$a^{-1}b^{-1}$B.$b^{-1}a^{-1}$C.$ab$D.$ba$

10.设$L$是一个格，$a,b\inL$，若$a\leqb$，则$a\veeb$等于（）

A.$a$B.$b$C.$a\wedgeb$D.以上都不对

二、填空题（每题3分，共15分）

1.命题公式$(P\wedgeQ)\vee(\negP\wedge\negQ)$的对偶式是______。

2.设集合$A=\{1,2,3\}$，则$A$的幂集$P(A)$的元素个数为______。

3.设$R$是集合$A=\{1,2,3\}$上的关系$R=\{(1,2),(2,3),(3,1)\}$，则$R$的传递闭包$t(R)$中元素个数为______。

4.设图$G$有$n$个顶点，$m$条边，且$G$是连通的，则$G$的生成树有______条边。

5.设$(G,)$是一个群，$|G|=6$，则$G$中元素的阶可能为______。

三、判断题（每题2分，共10分）

1.命题公式$\neg(P\toQ)$与$P\wedge\negQ$是等价的。（）

2.空集是任何集合的真子集。（）

3.若关系$R$是对称的，则$R$的逆关系$R^{-1}$也是对称的。（）

4.一个图是欧拉图当且仅当它是连通的且每个顶点的度数都是偶数。（）

5.设$(L,\vee,\wedge)$是一个格，若对于任意$a,b,c\inL$，都有$a\vee(b\wedgec)=(a\veeb)\wedge(a\veec)$，则称$L$是分配格。（）

四、解答题（每题10分，共30分）

1.求命题公式$(P\toQ)\wedge(Q\toR)$的主析取范式和主合取范式。

2.设集合$A=\{1,2,3,4\}$，$R$是$A$上的关系$R=\{(x,y)|x+y$是偶数，$x,y\inA\}$。

写出$R$的关系矩阵$M_R$。

判断$R$是否为等价关系，若是，求出所有等价类。

3.已知一个图$G$的邻接矩阵为

\[

A