当前位置：文档库 › 离散数学练习题含答案

离散数学练习题含答案

离散数学试题

第一部分选择题

一、单项选择题

1．下列是两个命题变元p，q的小项是（C ）

A．p∧┐p∧q B．┐p∨q

C．┐p∧q D．┐p∨p∨q

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

C．p∧q D．p∧┐q

3．下列语句中是命题的只有（ A ）

A．1+1=10 B．x+y=10

C．sinx+siny<0 D．x mod 3=2

4．下列等值式不正确的是（ D ）

A．┐(?x)A?(?x)┐A

B．(?x)(B→A(x))?B→(?x)A(x)

C．(?x)(A(x)∧B(x))?(?x)A(x)∧(?x)B(x)

D．(?x)(?y)(A(x)→B(y))?(?x)A(x)→(?y)B(y)

5．谓词公式(?x)P(x,y)∧(?x)(Q(x,z)→(?x)(?y)R(x,y,z)中量词?x的辖域是（C ）A．(?x)Q(x,z)→(?x)(?y)R(x,y,z))

B．Q(x,z)→(?y)R(x,y,z)

C．Q(x,z)→(?x)(?y)R(x,y,z)

D．Q(x,z)

6．设A={a,b,c,d}，A上的等价关系R={,,,}∪I A，则对应于R的A的划分是（ D ）

A．{{a},{b,c},{d}} B．{{a,b},{c},{d}}

C．{{a},{b},{c},{d}} D．{{a,b},{c,d}}

7．设A={?}，B=P(P(A))，以下正确的式子是（A ）

A．{?,{?}}∈B B．{{?,?}}∈B

C．{{?},{{?}}}∈B D．{?,{{?}}}∈B

8．设X，Y，Z是集合，一是集合相对补运算，下列等式不正确的是（A ）

A．(X-Y)-Z=X-(Y∩Z)

B．(X-Y)-Z=(X-Z)-Y

C．(X-Y)-Z=(X-Z)-(Y-Z)

D．(X-Y)-Z=X-(Y∪Z)

9．在自然数集N上，下列定义的运算中不可结合的只有（ D ）

A．a*b=min(a,b)

B．a*b=a+b

C．a*b=GCD(a,b)(a,b的最大公约数)

D．a*b=a(mod b)

1word版本可编辑.欢迎下载支持.

2word 版本可编辑.欢迎下载支持.

10.设R 和S 是集合A 上的关系,R ∩S 必为反对称关系的是( ) A ．当R 是偏序关系,S 是等价关系; B ．当R 和S 都是自反关系; C ．当R 和S 都是等价关系; D ．当R 和S 都是传递关系

11.设R 是A 上的二元关系,且R ·R ?R,可以肯定R 应是( D ) A ．对称关系; B ．全序关系; C ．自反关系; D ．传递关系 12．设R 为实数集，函数f ：R →R ，f(x)=2x ，则f 是（） A ．满射函数 B ．单射函数 C ．双射函数 D ．非单射非满射 CDACCDAADADB

第二部分非选择题

二、填空题

1．设论域是{a,b,c}，则(?x)S(x)等价于命题公式 S(a)∧S(b)∧S(c) ；(x ?)S(x)等价于

命题公式 S(a)∨S(b) ∨S(c) 。 2．设R 为A 上的关系，则R 的自反闭包r(R)= _R ∪A I _ ，对称闭包s(R)= _R ∪R ~

。 3．某集合A 上的二元关系R 具有对称性，反对称性，自反性和传递性，此关系R 是 A I _ ，其关系矩阵是只有主对角线上元素为1 。三、计算题 1．（4分）如果论域是集合{a,b,c}，试消去给定公式中的量词：)0y x )(x )(y (=+??。 2．用等值演算求下面公式的主析取范式。)()(P Q Q P ∨?→→? 3．用等值演算法求公式)()(Q P Q P ?→?→?的主合取范式。

4．（6分）在偏序集中，其中Z={1,2,3,4,6,8,12,14}，≤是Z 中的整除关系，求集合

D={2,3,4,6}的极大元，极小元，最大元，最小元，最小上界和最大下界。 5．设集合A={1,2,3,4,5},A 上的划分为π＝{{1,2,3},{4,5}},试求：

1) 写出划分π诱导的等价关系R ；

2) 写出关系矩阵R M ；

3) 画出关系图。

6. 设A ＝{a ，b ，c ，d }，R 是A 上的二元关系，且R ＝{，，，}，求r (R )、s (R )和t (R )。

解 r (R )＝R ∪I A ＝{，，，，，，，}

s (R )＝R ∪R -1

＝{，，，，，} R 2

＝{，，，}

3word 版本可编辑.欢迎下载支持.

R 3