《离散数学试题1套》

《离散数学试题1套》

一、选择题（每题3分，共30分） 1. 下列语句中，( )是命题。 A. 请把门关上 B. 地球外的星球上也有人

C. x + 5 > 6 D. 下午有会吗？

2. 命题公式﹁B→﹁A等价于( )

A. ﹁A∨﹁B B. ﹁(A∨B) C. ﹁A∧﹁B D. A→B

P(a,a) P(a,b) P(b,a) P(b,b)3. 设I是如下一个解释：D＝{a,b}, 1 0 1 0，则在解释I下取真值为1的公式是( A. ?x?yP(x,y) B. ?x?yP(x,y) C. ?xP(x,x) D. ?x?yP(x,y)

4. 下列说法正确的是 ( ).

A．若A?B及B?C 则 A?C B．若A?B及B?C 则 A?C C．若A?B及B?C 则 A?C D．若A?B及B?C 则 A?C

5． 下列说法错误的是 ( ).

A．{?}??(?) B．???({?})

C．?(?)?{?}

D．?(?)??({?})

6．设A?{ ?， {1}， {1， 2} }，P(A)为A的幂集，则P(A)的元素个数为( ). A．3 B．6 C．7 D．8

7. 集合A的一个划分，确定A的元素间的关系为( ).

A．全序关系 B．等价关系 C．偏序关系 D．拟序关系

8. 下列函数中为双射的是( ).

A．f: I?I, f(j)?j (mod) 3 B．f:N?N, f(j)?1，j是奇数0，j是偶数

C．f:I?N, f(i)? |2i|?1 D．f:R?R, f(r)?2r?15

9. 设I为整数集，Q为有理数集，R为实数集；下列代数结构为群的是( ).

(1)?I， ?? (2)?I， ??

(3)?Q， ?? (4)?R， ??

A．无 B．(1)、(4) C．(1)、(3)、(4) D．全体都是

10. 设简单图G所有结点的度之和为12，则G一定有( ). A．3条边 B．4条边 C．5条边 D．6条边

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

1. 设S(x)∶x是大学生；K(x)∶x是运动员。则命题：“有些运动员不是大学生”的 符号化为 .

).

2. 已知命题公式G?(?P?Q)∧R，则G的主析取范式是 .

3. 将公式化为等价的前束范式: ?xF(x)∧??xG(x)? .

4. 设A?{ 1， 2， 3， 4 }，R?A?A，R?{?a,b?|a?b，a,b?R}， 则domR= ，ranR= .

5. 设A为非空集合，P(A)为A的幂集，则对于P(A)中的二元运算：? ，?，求运算? 的幺元 ，运算 ?的幺元 . 6.设P?{ ?1， 2?， ? 2， 4?， ? 3， 3? }Q?{ ?1， 3?， ? 2， 4?， ? 4， 2? }则

dom(P?Q)= ， ran(P?Q)= .

7. 设A?{ 1， 2， 3， 4， 5 }，R?A?A，R?{ ?1， 2?， ? 3， 4?， ? 2， 2? } 求r(R)= ，s(R)=

8. 设G是完全二叉树，G有15个点，其中8个叶点，则G的总度数为__________， 分枝点数为________________.

三、计算题（每题6分，共18分）

1. 设集合A?{a， b }，P(A)为A的幂集，求笛卡尔积?(A)?A.

2. 设A?{ 1， 2， 3， 4， 6， 8， 12， 24 }，R?{?x，y?|y/x?整数}，试求： (1) 作出〈A，R〉的哈斯图

(2) 求A的最大元、最小元、上界、下界

3. 已知群?Z6， ?6?其中Z6?{0， 1， 2， 3， 4， 5 }， ?6为模6加法； (1) 列出运算表；

(2) 求该群的所有子群

四、证明题（共28分）

1. (5分)在命题逻辑中构造下面推理的证明：

前提：p→┐q, ┐r∨q, r∧┐s 结论：┐p

2．(5分)证明：(?x)(H(x)→M(x))，(?x)H(x)?(?x)M(x)

2. (5分)设A={1，2，3，4}，关系R?(A?A)?(A?A)，

R?{??a,b?,?c,d??|a?d?b?c，a,b,c,d?A}，证明：R是等价关系

3. (5分)设Z是整数集合，在Z上定义二元运算如下：x * y = x + y – 2，

证明：〈Z，*〉是群。

4. (8分)设是一个环, 并且对于任何a∈A ，有a?a=a，证明

(1)对于任何a∈A，都有a+a=θ，其中θ是+的幺元；

(2)是一个交换环。