信安离散试卷2004A

中国地质大学离散数学

试卷类别

A√ B

使用班级

使用学期

任课教师

教研室主任 审核签字

中国地质大学（武汉）考试出题专用纸 教务处制

考试课程名称： 离 散 数 学 学时： 50

考试方式：开卷，闭卷√，笔试√，口试，其它 考试内容：

一、填空题（每空1分，共18分）

1．空集的幂集的基数是________。

2．某学校学生选课的情况如下：260名学生选法语，208人选德语，160人选俄语，76人选法语和德语，48人选法语和俄语，62人选德语和俄语，三门课都选的有30人，三门都没选的有150人，问：共有_______学生；有_______学生选法语和德语，而没选俄语；有_______学生选俄语，而没选德语或法语。3．设集合A含有n个元素，则在A上可定义______种不同的二元关系，______种不同的反自反关系。

4．设A和B都是有限集合，且|A|=3，|B|=4，则有_______个不同的从A到B的函数；有_______个不同的从A到B的满射；有_______个不同的从A到B的内射。

5．判断下列公式的类型：

(P≡R)∧((¬Q∧¬S)∨(Q∧S))是________式； (P∧Q)≡(P∨Q) 是________式； (P∧(P→Q))→Q 是________式。

6．设S是非空有限集，代数系统<P(S);∪,∩>中，P(S)对∪运算的单位元是_______，零元是_______，P(S)对∩运算的单位元是_______。

7．设G=(n,m)，且G中每个结点的度数不是k就是k+1，则G中度数为k的结点的个数是 。

8．K4中含3条边的不同构生成子图的个数是 。

9．设有56

二、解答题（共82分）

1．（10分）设N是自然数集合，定义N上的二元关系ρ：ρ={（x,y）|x∈N,y

∈N,x+y是偶数}，证明ρ是一个等价关系。 2．（5分）设有函数f,g,h：R→R，给定为f(x)=x+5，g(x)=x-3，h(x)=6x，求以

下复合函数fοg，gοf，hοg，hοh，fοgοh。 3．（6分）求命题公式¬((P→Q)∧(R→P))∨¬((R→¬Q)→¬P)的主析取范式

和主合取范式。

4．（6分）求谓词公式 xP(x)→(Q(y)→¬( yR(y)→ xS(x)))的前束合取范式。5．（10分）符号化下列命题并推论其结论：

任何人如果违反交通规则，就要被处罚；总有些人违反了交通规则。因

此有些人被处罚。（使用全总个体域） 6．（7分）设f是代数系统<A;ο>到<B;*>的同态，试证明<f(A);*>是<B;*>的子代

数系统。 7．（8分）设<G;*>是一个群，x∈G，在G中定义新的运算ο，使得对于任意的a,b

∈G，aοb=a*x*b，证明<G;ο>也是一个群。 8．（10分）设<G;*>是一个群，定义G的子集H为H={a|a*x=x*a，对于任意的x

∈G}，试问：H对于运算*能否构成<G;*>的正规子群？ 9．（10分）今要将6个人分成3组（每组2个人）去完成3项任务。已知每个人

至少与其余5个人中的3个人能互相合作。问：能否使得每组的2个人都能相互合作？请说明理由。 10．（10分）设G为连通的简单平面图，结点数为n，面数为f，证明：

（1）若n≥3，则f≤2n-4；

（2）若G中结点最小的度为4，则G中至少有6个结点的度小于等于5。