《离散数学》(上)试卷

（时间120分钟）

一、选择题（每小题2分，共20分）

01．谓词公式xyP(x,y)的否定式是：（ ）

02．使得命题公式(PQ)(QP)为真的指派的个数为：（ ） A．1 B．2 C．3 D．4

得分 A、xyP(x,y) B、xyP(x,y) C、xyP(x,y) D、xyP(x,y)

03．设A,B是集合，(A),(B)为其幂集，若AB，则(A)(B)（ ） A． B．{} C．{{}} D．{,{}} 04．对任意集合A,B,C，下列命题为真的是（ ）

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。 05.A{a,b,c}上的关系R{a,a,a,b,a,c}，则R具有（ ） A、传递性与反对称性； B、传递性与对称性； C、自反性与反对称性； D、反自反性与对称性。 06．设R是集合A上的自反关系，则（ ）

I D．RRI A．RRR B．RRR C．RRAA07．设集合A上有n个元素，则A上的既对称又反对称的二元关系共有（ ） A．0个 B．2n个 C．n个 D．2个 08．函数f:XY可逆的充要条件是：（ ） A．AB B．|A||B| C．f为双射 D．f为满射 09．下述哪一个关系不是等价关系（ ）

A、空集合上的二元关系； B、恒等关系； C、非空集合上的空关系； D、全域关系。 10．下列无限集合中，不可数的集合是：（ ）

2n1,2,...,n}) D、(N) A、({1,2,...,n}) B、NN C、N({

《离散学术》试卷 共3页第1页

二、填空题（每空2分，共30分）

得分

01．A{,{a},{b},{a,b}}上的包含关系为，则子集C{{a},{b}}的极大元为

＿＿＿＿＿＿，极小元为＿＿＿＿＿＿，上界为＿＿＿＿＿＿，下界为＿＿＿＿＿＿， 最大元为＿＿＿＿＿，最小元为＿＿＿＿＿（若没有填无）。

02．设集合A，B中分别有m,n(mn0)个元素，则A上有______个不同的二元关系，有______个不同

的函数，有______个不同的双射函数；从A到B有______个不同的二元关系，有______个不同的函数。

03．集合A{a,b}上有______个偏序关系，集合B{1,2,3}上有______个等价关系。

{a,}的}幂集为____________________________________________________，集合04．集合{,a,{{}}的幂集为_____________________________________________________

三、综合题（每小题分见下所列，共50分）

1．用等值演算法求命题公式((PQ)R)(QP)的主析取范式和主合取范式。（16分）

2．用推理规则证明：P(QR)，SP，Q永真蕴含SR。（10分）

3．设R是集合A上的关系，令S{a,bcA,使a,cR且c,bR}，证明：如果R是等价关系，则S也是等价关系。（12分）

224．已知f:NNN，f(x,y)xy。请问：（12分）

①f是单射吗？ ②f是满射吗？ ③计算f({0})。 ④计算f({0,0,1,2})1《离散数学》试卷 共3页第2页

《离散数学》(上)考试试卷答案

（时间120分钟）

一、单项选择（每小题2分，总210=20分）

01.A; 02.D; 03.B; 04.B; 05.A; 06.B; 07.D; 08.C; 09.C; 10.D.

二、填空题（每空2分，总215=30分）

01.{a}和{b}，{a}和{b}，{a,b}，，无，无； 02.2m2mmn，m，m!，2，n; 03.3，5;

m04.{,{},{a},{{,a}},{,a},{,{,a}},{a,{,a}},{,a,{,a}}}，

{,{},{{}},{,{}}}

三、综合题（每小题分具体见下所列，总50分） 1、解：

((PQ)R)(PQ)((PQ)R)(PQ)

((PQ)R)(PQ)(PQ)(PQ)R 4分 (P(QQ))RPR 7分

10分 (PQR)(PQR)（主合取范式）(0，2)(1,3,4,5,6,7)

(PQR)(PQR)(PQR)

(PQR)(PQR)(PQR)（主析取范式） 16分

2、证明：

(1) SP P 1分 (2) S P（附加前提） 3分 (3) P T (1),(2) I 4分 (4) P(QR) P 5分 (5) QR T (3),(4) I 6分 (6) Q P 7分 (7) R T (5),(6) I 8分 (8) SR CP (2),(7) 10分

3、证明：已知R是等价关系，对S是等价关系的证明分3步： （1）自反性（4分） R是自反的，

对aA，有a,aR， 根据S的定义，有a,aS，

S是自反的；

（2）对称性（8分）

如果a,bS，则cA，使a,cR且c,bR，

R是对称的，

b,cR且c,aR，

《离散数学》试卷答案 共2页第1页

再根据S的定义有b,aS， S是对称的；

（3）传递性（12分）

如果a,bS，b,cS，

则dA使a,dR，且d,bR。R是传递的，a,bR。 则eA使b,eR，且e,cR。R是传递的，b,cR。

根据S的定义有a,cS。S是传递的。

由（1），（2），（3）得S是等价关系。

4、解答：

①1,2,2,1NN，f(1,2)f(2,1)12225，但1,22,1，所以f不是单射（3分）。 ②3N，但找不出这样的x,yNN，使得f(x,y)x2y23。所以f不是满射（6分）。 ③f1({0}){x,yx2y20}，解之，得xy0，所以f1({0}){0,0}（9分）。

④f({0,0,1,2}){0,5}（12分）。

《离散数学》试卷答案 共2页第1页