离散数学练习题含复习资料

1、易自考1 / 702324# 离散数学试题第7页共4页离散数学试题第一部分选择题、单项选择题1 .下列是两个命题变元 p, q的小项是（ C ）A.pApAqB.pVqC.pAqD.pVpV q2 .令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（D ）A . p一n qB . p Vq qC. p A q3.下列语句中是命题的只有(A. 1+1=10C. sinx+siny<04.下列等值式不正确的是(A. n ( x)A ( x) n AB. ( x)(B-A(x) B-( C.(x)(A(x) A B(x)( x)A(x) A(D. pAq qA )B.

2、 x+y=10D. x mod 3=2C )x)A(x)x)B(x)D. ( x)( y)(A(x) -B(y)( x)A(x) 一( y)B(y)5.谓词公式(x)P(x,y) A ( x)(Q(x,z) 一( x)( y)R(x,y,z)中量词 x 的辖域是( C )A . ( x)Q(x,z)f( 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= <a,b>,<b,a>,<c,d>,<d,c>

3、 U Ia,则对应于 R 的 A 的划 分是( D )A.a,b,c,dB.a,b,c,dC .a,b,c,dD.a,b,c,d7 .设A=? , B=P(P(A),以下正确的式子是( A )A.?,? C BB.?,? C BC. ?,? e Bd. ?,? e b8 .设X, Y, Z是集合，一是集合相对补运算，下列等式不正确的是( A )A . (X- Y)- Z=X- (Y A Z)B. (X- Y)- Z=(X - Z)- YC. (X- Y)- Z=(X - Z)- (Y- Z)D. (X- Y)- Z=X- (Y U Z)9.在自然数集 N上，下列定义的运算中不可结合的只有( D

4、 )A . a*b=min(a,b)B. a*b=a+bC. a*b=GCD(a,b)(a,b 的最大公约数)D. a*b=a(mod b)10 .设R和S是集合A上的关系，RAS必为反对称关系的是(A ) A.当R是偏序关系，S是等价关系；B.当R和S都是自反关系； C.当R和S都是等彳关系；D.当R和S都是传递关系11 .设R是A上的二元关系，且R R R,可以肯定R应是(D ) A.对称关系；B.全序关系；C.自反关系；D.传递关系第二部分非选择题二、填空题1 .设论域是a,b,c,则(x)S(x)等价于命题公式S(a)A S(b)A S(c) ; ( x )S(x)等价于命题公式 S(

5、a)VS(b) VS(c) 。2 .设R为A上的关系，则R的自反闭包r(R尸 RU 1A，对称闭包s(R尸 RU R_3 .某集合A上的二元关系 R具有对称性，反对称性，自反性和传递性，此关系R是_Ia其关系矩阵是只有主对角线上元素为 1。三、计算题1. (4分)如果论域是集合a,b,c,试消去给定公式中的量词：(y)( x)(x y 0)。解：By)奴-By) (a+y=O) A A )=(a=Q) A Ma=Q)A即。)V (a+tFOl A (b十X0)A 化+FO)(P Q) ( Q P)V C(a+c=O) A (b+(F=O) A (c+g=O)2 .用等值演算求下面公式的主析取范

6、式。(-1f)一(-» gVp)一(pMq) V L gVp)=5 p 八-q) V-1 g Vp=q Vp= (-,7A(pV-,jj)V(pA(gV-i(/)二(pAr g) V(r p A-1 g) V (pAg) V(p A-1 9)=(-> pA-> q) V(p Af g) V (p Ag)3 .用等值演算法求公式(P Q) (P%勺主合取范式。解；1 (pfq)T>gf-! q)二K tn pVq)"pVn q)<二Xp八qH*' (q pV-i q)V=X3八 1 q)f h pVn q)A<Cn pVn q)-i G)

7、"Xi (pAi q) V tn pVn q)A tn (i pVn q) V (pAn q)<=X I p V q) M (n pV i q) 3 A (Cp A q) V (pAn q)<=Xi pV (qVi q) A (pAq) V (pAn q)<=?TA(pAq)V(pA-i q)<=XpAq) V (pA-i q)apNqVi q)<=>pAt<=>pV (qAn q)<±Xp/q) A q)4 . (6分)在偏序集<Z,W>中，其中Z=1,2,3,4,6,8,12,14 , W是Z中的整除关系

8、，求集合D=2,3,4,6的极大元，极小元，最大元,最小元，最小上界和最大下界。触：哈斯图如下：需合口二眨,64,仃的械大元为电5极小元入3i最大元K存在，费小无不存在，谖小上界1E和最大下界1.5 .设集合 A=1,2,3,4,5,A 上的划分为 =1,2,3,4,5,试求：1）写出划分诱导的等价关系R;2）写出关系矩阵M R ；3）画出关系图。1我的关系矩阵为Mk=101 1 0 Oi110 0110 00 0 11R的关系图如下=6 .设人=2, b, c, d , R是 A 上的二元关系，且 R= <a, b>, <b, a>, <b, c>, &l

9、t;c, d>, 求 r(R)、s(R)和 t(R)。解 r(R) = RU I a= < a, b>, <b, a>, <b, c>, <c, d>, <a, a>, <b, b>, <c, c>, <d, d>-1s( R) = RU R =<a, b>, <b, a>, <b, c>, <c, d>, <c, b>, <d, c>R2=<a,a>,<a,c>,<b,b>,<b

10、,d>R3=<a,b>,<a,d>,<b,a>,<b,c>R4=<a,a>,<a,c>,<b,b>,<b,d> = R2<a, a>, <a, c>, <b, b>, <b, d>, <a,t(R) =Ri =<a, b>, <b, a>, <b, c>, <c, d>,i 1d>四、证明题1 .设R和S是.兀关系，证明11(R S) 1 R 1(h j)左(AU5) "0(3

11、) jS)«(/,>)是无或者。eS0(3)白尸或者(“ eS'1 浓/冷晨Qus”)所以(kus)t=/tI 驴2 .设 A=a,b,c,R=(a,a),(a,b),(b,c), 验证 rs(R尸sr(R)。,3,&) *3*c) (£5) (口*(口*(C.±) ir(R)K (d，n), Q 4), S,c),(6小)Me) )=3*G *S*c)* (eM)，Qb).Q"»223 .设R是A上的二元关系，试证： R是传递的当且仅当 R R,其中R表示R?R。(6分Xi)祝R传递1 vG4)en1，m1A使(t)Xt

12、ay)£ft (因为 R： 心田:R传递，凡,力Er二H工匚RG分)设R七典若由Er则(3)6片.R'qR一二 GCGr 即 R 传建4 .证明下列结论：(1) P Q R P Q R(2) (AB) (A C), (B C),D A解：(1) 1 PA QP附加前提2PT, 1, 123PV QT, 2, I14PV CH RP5RT, 3, 4,6PA CH RCP)1DP假设前提2DV AP3AT, 1, 2,3I(A-B)A(AC)Af BT,4,T,3,5,Af CT,4,T,3,7,BA CT,6,10(BA Q115.已知R和S是非空集合(BA C) AA上的等

13、价关系,(BA C)试证：1)T , 9, 10,合取式，矛盾Rn S是A上的等价关系；2)对 aC A,a Rns=a rA a s。解：xCA,因为R和S是自反关系,所以 <x,x> £ R、<x,x> £ S,因而 <x,x>e Rn s,故Rn s是自反的。x、y e A,若 <x,y> RA S,贝U <x,y><y,x> C R、<y,x> C S,因而 <y,x> C RC S,£ R、<x,y> £ S,因为 故Rn s是对称的。R

14、和S是对称关系,所以因x、V、z A,若 <x,y> RA S 且<丫2> £ RC S,则 <x,y> £<y,z> £ S,因为R和S是传递的，所以因<x,z> £ R、<x,z> £ S,R、<x,y> C S 且 <y,z> £ R、因而 <x,z> e Rn s,故 Rn s是传递的。总之Rn s是等价关系。2)因为 xC a ras<x,a> RA S<x,a> C RA <x,a> CS x a rA x C a s x a rA a s所以a Rns=a rA a s。五、