2009-2010离散数学A卷

山东财政学院东方学院

2009—2010学年第一学期期末考试《离散数学》

试卷(A )

（考试时间为120分钟）

系部__________ 班级__________ 姓名__________ 学号__________ 题 号 得 分 阅卷人 一 二 三 四 五 总 分 合分人

一．填空题：（共5小题，每空2分，合计20分）

1. 量词否定等值式?x?A(x)? 。

2. 设F(x):x是人，G(x):x爱吃糖。在一阶逻辑中，命题“有人爱吃糖”的符号化形

式为 。

3. 设A?{{a,b},c}，B?{c,d}，则A?B? 。

?1

?1

4. 设S?{1,2,3,4}，R为S上的关系，其关系矩阵是：?

?0??1

00000000

1?0??，则（1）R的1??0?

关系表达式是 ，

ranR? ，(2) domR? ，（3）（4）R?R中有 个

有序对。

5. 设S?Q?Q，其中Q为有理数集合，定义S上的二元运算?，

??a,b?,?x,y??S，有?a,b???,xy??,a?xa，y??1）则b（

?3,4???1,2?? ，??1,3???5,2?? ，

（2）?S,??的幺元是 。 二．选择题：（共10小题，每小题2分，合计20分） 1. 使命题公式p→(p∧q)为假的赋值是 ( )。

A.10 B.01 C. 00 D.11

第 1 页 共 3 页

2．令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（ ）。

A. p∧┐q B．p∨┐q C.p∧q D．p→┐q

3．设B不含有x，下列一阶逻辑等值式不正确．．．

的是 ( )。 A.?x(A(x)?B)??xA(x)?B B.?x(A(x)?B)??xA(x)?B C. ?x(A(x)?B(x))??xA(x)??xB(x) D. ?x(A(x)?B(x))??xA(x)??xB(x) 4．设X，Y，Z是集合，下列结论不正确．．．

的是（ ）。 A．（X∪Y）∪Z=X∪(Y∪Z) B．X∩(Y∪Z)=(X∩Y)∪Z C．(X∩Y) ∩Z=X∩(Y∩Z) D．X∪(Y∩Z)=(X∪Y)∩(X∪Z)

5．设R是集合A上的二元关系，IA是上的恒等关系，IA?R下面四个命题为真的是 ( )A.R是自反的 B.R是传递的 C.R是对称的 D.R是反对称的 6．设函数f：N→N（N 为自然数集），f(n)=n+1，下面四个命题为真的是 ( )。 A. f是单射 B. f是满射 C. f是双射的 D.f非单射非满射 7．设B不含有x，?x(A(x)?B)等值于 ( )。

A.?xA(x)?B B.?x(A(x)?B) C.?xA(x)?B D.?x(A(x)?B)8．设R是集合A上的偏序关系，则R不一定是( )。

A.自反的 B. 对称的 C. 反对称的 D. 传递的 9． 设R为实数集，定义R上4个二元运算，不满足结合律的是（ ）。 A. f1(x,y)= x+y B. f2(x,y)=x-y C. f3(x,y)=xy D. f4(x,y)=max{x,y} 10. 在下图所示的哈斯图中的偏序集不是格的是（ ）。

第 2 页 共 3 页

。

三．判断题：（共10小题，每小题2分，合计20分） 1. “现在开会吗？”是命题。（ ） 2. “4是偶数且是奇数”不是命题。（ ） 3.

?x(A(x)?B(x))??xA(x)??xB(x) （ ）

4. 空集是唯一存在的。（ ） 5. 二元关系中的等价关系、偏序关系、函数关系，它们的共同特点是都具有自反性。 （ ） 6. 函数f:A?B，若ranf?B，则称f:A?B是满射的。（ ） 7. 群一定是独异点和半群。（ ） 8. 独异点是含幺元的半群。（ ） 9. 任何群G都有两个平凡子群。（ ） 10. 布尔代数既是分配格，也是有补格。（ ） 四．计算题：（共2小题，每小题10分，合计20分） 1. 已知命题公式(?p?q)?(?q?p)，

（1）构造真值表。 (2) 求主析取范式(要求通过等值演算推出)。

2. 设为一个偏序集，其中，A={1，2，3，4，6，9，12，24},R是A上的整除关系。 （1）画R出的哈斯图； （2）求A的极大元和极小元；

（3）求B={4,6}的最小上界和最大下界。

五．证明题：（共2小题，每小题10分，合计20分）

1. 前提：?x(P(x)?Q(x)) 结论：?xP(x)??xQ(x) 2. 设?G,??是群, S?{x|x?G且对于?y?G,x?y?y?x},

第 3 页 共 3 页