离散数学习题集(十五套)

一、 填空 20% (每空 2分)

1、 设 f,g是自然数集N上的函数?x?N,f(x)?x?1,g(x)?2x,

则f?g(x)? 。

2、 设A={a,b,c},A上二元关系R={< a, a > , < a, b >,< a, c >, < c, c>} ,

则s(R)= 。

},则用列举3、 A={1,2,3,4,5,6},A上二元关系T?{?x,y?|x?y是素数法

T= ; T的关系图为

; T具有 性质。 4、 集

A?{{?,2},{2}}的幂集

2A= 。

5、 P,Q真值为0 ;R,S真值为1。则wff(P?(R?S))?((P?Q)?(R?S))的

真值为 。 6、 wff?((P?Q)?R)?R的

为 。

7、 设 P(x):x是素数, E(x):x 是偶数,O(x):x是奇数 N (x,y):x可以整数y。

则谓词wff?x(P(x)??y(O(y)?N(y,x)))的自然语言是

。 8、 谓词wff?x?y(?z(P(x,z)?P(y,z))??uQ(x,y,u))的前束范式为

二、 选择 20% (每小题 2分)

1、 下述命题公式中,是重言式的为( )。

A、(p?q)?(p?q); B、(p?q)?((p?q))?(q?p)); C、?(p?q)?q; D、(p??p)?q。 2、 wff?(p?q)?r的主析取范式中含极小项的个数为( )。

A 、2; B、 3; C、5; D、0; E、 8 。 3、 给定推理

①?x(F(x)?G(x)) ②F(y)?G(y) ③?xF(x) ④F(y) ⑤G(y) ⑥?xG(x)

P US① P ES③ T②④I UG⑤

??x(F(x)?G(x))??xG(x)

推理过程中错在( )。

A、①->②; B、②->③; C、③->④; D、④->⑤; E、⑤->⑥

4、 设S1={1,2,?,8,9},S2={2,4,6,8},S3={1,3,5,7,9},S4={3,4,5},

S5={3,5},在条件X?S1且X?S3下X与( )集合相等。 A、 X=S2或S5 ; B、X=S4或S5;

C、X=S1,S2或S4; D、X与S1,?,S5中任何集合都不等。 5、 设

R

S

P

上的关系,P

是所有人的集合,

R?{?x,y?|x,y?P?x是y的父亲},S?{?x,y?|x,y?P?x是y的母亲}则S?1?R表示关系 ( )。

}; A、{?x,y?|x,y?P?x是y的丈夫}; B、{?x,y?|x,y?P?x是y的孙子或孙女}。 C、 ?; D、{?x,y?|x,y?P?x是y的祖父或祖母6、 下面函数( )是单射而非满射。

A、f:R?R,B、f:Z?R,C、f:R?Z,D、f:R?R,?f(x)??x2?2x?1;

f(x)?lnx;

f(x)?[x],[x]表示不大于x的最大整数;

f(x)?2x?1。

其中R为实数集,Z为整数集,R+,Z+分别表示正实数与正整数集。 7、 设S={1,2,3},R为S上的关系,其关系图为

则R具有( )的性质。

A、 自反、对称、传递; B、什么性质也没有;

C、反自反、反对称、传递; D、自反、对称、反对称、传递。 8、 设S?{?,{1},{1,2}},则有( )?S。

A、{{1,2}} ;B、{1,2 } ; C、{1} ; D、{2} 。 9、 设A={1 ,2 ,3 },则A上有( )个二元关系。

A、2 ; B、3 ; C、2; D、2。 10、全体小项合取式为( )。

A、可满足式; B、矛盾式; C、永真式; D、A,B,C 都有可能。

3

2

2332三、 用CP规则证明 16% (每小题 8分)

1、A?B?C?D,D?E?F?A?F

2、?x(P(x)?Q(x))??xP(x)??xQ(x)

四、(14%)

集合X={<1,2>, <3,4>, <5,6>,? },R={<,>|x1+y2 = x2+y1} 。 1、 证明R是X上的等价关系。 (10分) 2、 求出X关于R的商集。(4分)

五、(10%)

设集合A={ a ,b , c , d }上关系R={< a, b > , < b , a > , < b , c > , < c , d >} 要求 1、写出R的关系矩阵和关系图。(4分) 2、用矩阵运算求出R的传递闭包。(6分)

六、(20%)

1、(10分)设f和g是函数,证明f?g也是函数。 2、(10分)设函数g:S?T入射函数。 答案:

五、 填空 20%(每空2分)

1、2(x+1);2、{?a ,a?,?a ,b?,?a ,c?,?c ,c?,?b ,a?,?c ,a?};3、

f:T?S,证明 f:T?S有一左逆函数当且仅当f是

{?2,1?,?3,1?,?5,1?,?4,2?,?6,2?,?6,3??;

4、

反对称性、反自反性;4、{?,{{?,2}},{{2}},{{?,2},{2}}};5、1;

6、(P??Q?R)?(?P?Q?R)?(P?Q?R);7、任意x,如果x是素数则存在一个y,y是奇数且y整除x ;8、?x?y?z?u(?P(x,z)??P(y,z)?Q(x,y,u))。

六、 选择 20%(每小题 2分) 题目 答案

七、 证明 16%(每小题8分) 1、 ①A ②A?B

③A?B?C?D ④C?D ⑤D ⑥D?E ⑦D?E?F ⑧F ⑨A?F 2、

P(附加前提) T①I P T②③I T④I T⑤I P T⑥⑦I CP

1 C 2 C 3 C 4 C 5 A 6 B 7 D 8 A 9 D 10 C ??xP(x)??xQ(x)??(?x)P(x)??xQ(x)本题可证?x(P(x)?Q(x))??(?xP(x)??xQ(x)

① ?(?xP(x)) ②?x(?P(x)) ③?P(a)

④?x(P(x)?Q(x)) ⑤P(a)?Q(a) ⑥Q(a) ⑦?xQ(x)

P(附加前提) T①E ES② P US④ T③⑤I EG⑥

联系客服:779662525#qq.com(#替换为@)