2016-1学期《离散数学》复习题

复习题

一、单选题（）：

1．下列命题公式为重言式的是（） A．p→ (p∨q) B．(p∨┐p)→q C．q∧┐q

D．p→┐q

3．设p：我很累，q：我去学习，命题：“除非我很累，否则我就去学习”的符号化正确的是 A．┐p∧q B．┐p→q C．┐p→┐q

D．p→┐q

5．在公式(?x)(?y)(P(x,y)?Q(z))?(?y)P(y,z)中变元y是（） A．自由变元B．约束变元

C．既是自由变元，又是约束变元D．既不是自由变元，又不是约束变元

7．设集合X为人的全体，在X上定义关系R、S为R={

b>|a，b∈X∧a是b的母亲}，那么关系{|a，b∈x∧ a是b的祖母}的表达式为（） A．R?S B．R-1?S C．S?R

D．R?S-1

9．下列式子不正确的是（）

A．(A-B)-C=(A-C)-B B．(A-B)-C=A-(B∪C) C．(A-B)-C=(A-C)-(B-C)

D．A-(B∪C)=(A-B)∪ C 11．在下列代数系统中，不是环的只有（）

A．，其中R为实数集，+为实数加法，a*b=a+2b。

D．，其中Mn(R)为实数集n×n阶矩阵结合，+，*是矩阵加法和乘法。 13．结点数为奇数且所有结点的度数也为奇数的连通图必定是（）

A．欧拉图 B．汉密尔顿图 C．非平面图

D．不存在的 15．平面图(如下)的三个面的次数分别是（ ）

A．11，3，4 B．11，3，5 C．12，3，6

D．10，4，3

二、填空题（）：

1．求一个公式的主析取或主合取范式的方法，有______________法和______________法。 3．设X，U，V，Y都是实数集，f1：X→U，且fl(x)→ex； f2：U→V，且f2(u)＝u (1+u)；f3：V→Y，

且f3(v)=cosv。那么f3?f2?f1的定义域是______________，而复合函数(f3?f2?f1)(x)= ______________。

5．已知G=<{l，-1，i，-i}，·>(其中i=?1，是数的乘法)是群，则-l的阶是______________；i的

阶是______________。

7．设是群，则满足结合律和______________；若｜S｜>l，S中不可能有______________。 9．一个______________且______________的无向图称为树。

三、名词解释()： 1、命题： 2、谓词： 3、代数系统： 4、图：

四、计算题（）：

1、求(P Q)∧Q 得主析取范式

2、E={a,b,c,d,e},X={a,b,c},Y={a,c,d}.求X∩Y、X∪Y、X-Y、Y-X、～X、～Y、和X 的幂集P(X) 解：

3、设S={1,2}，求P(S)上对称差运算?的运算表 答：

五、证明（）：

设集合A={a,b,c,d,e},R={﹤a,a﹥,﹤a,b﹥,﹤b,a﹥,﹤b,b﹥,﹤c,c﹥,﹤c,d﹥,

1/ 2

﹤c,e﹥,﹤d,c﹥,﹤d,d﹥,﹤d,e﹥,﹤e,c﹥﹤e,d﹥﹤e,e﹥ },验证R是A上的等价关系。

六、画图（）：

求下图的最小生成树

2/ 2