離散數學練習題

1、 離散數學題之相禮和創(chuàng)作第一部分 選擇題一、單項擇題1列是兩個命題變元 ，q 的小項是（ C ）Appq CpqBpDppq2令 p：天下雪了， q：路滑，則命題“雖今天下雪 了，但是路不滑”可號化為（ D ）ApqCpq3列語句中是命題的只要（ A ） ABq DpqBC D mod 4列等值式不正確的是（ C ）A( x)A ( x)AB( x)(BA(x) B( x)A(x)C( B(x) ( x)A(x)( x)B(x)D( x)( B(y) ( x)A(x)( y)B(y)5謂詞式 ( ( x)(Q(x,z) ( x)( 中量 A 詞 x 的域是（ ）A( x)Q(x,z) x)(

2、B( y)R(x,y,z)C( x)( y)R(x,y,z) D6 設A=a,b,c,d ， A上 的 等 價 關 系 I ，則對應于 R 的 A 劃 分是（ D ）Aa,b,c,dCa,b,c,dDa,b,c,dB a,b,c,d7 A=，B=P(P(A)，下正確的式子是（ A ）A,BB ,C,B , 8設 X，Y Z 是集合，一是集合絕對補算，下列等式 不正確的是（ A ）A Y)- Z=X- (YB(X- Y)- Z=(X- Z)- YC(X- Y)- Z)- (Y- Z)D(X- Y)- (Y9在自數集 ，下列定義的運算中不結合的只要 （ D ）Aa*b=min(a,b)BCa*b=

3、GCD(a,b)(a,b 最大公約數D b) R 和 是集合 A 上的關系R 必為反對稱關系的是 ( A )A當 R 是偏序關系, 等價關系 B當 都自反 關;C當 都是價關系; D當 R 都是傳遞關系 11.設 A 上的二元關系 且 RR 可以一定 R 應是( D ) A對稱關; B 全關系; 自反關系 D 傳遞關第二部分 非選擇題二、填空1設論域 ，則( 等價于命題式 S(a) S(b) ；( 價于命公式 S(a)S(b) 2 A 上的關系，則 R 自反閉 I ，對A稱閉包 s(R)=_R R .3集合 A 上的二元關系 R 具有對性，反對稱性，自反 性和傳遞性，此關系 R 是 I ，其關

4、系矩陣是只要對A角線上元素為 .三、計算1 分假如論域是集合 a,b,c ，試消往給定公式中的量詞：( y .2等值演算求上面公式的主析取范 ( Q ) ( )3等值演算法求公式 Q ) ( P )的主合取范式 .4 （ 6分 ） 在 偏 序 集 Z, 中 其 中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,寫出劃 誘導的等價關系 R；寫出關系矩陣MR；畫出關系圖 設 b c 是 上的二元系，且 R ，b，c，求 r)

5、、s)和 t(R).解 r R IA ， b ， c ， ，d，s) b d ， ，d，c2，a，b，d3，a，d，4，a，b，dR2t( R i ， b ， c ， d ， a i 1a，a，c，bb， a，d四、證明1 R 和 S 是二元關系，證明 )R 2 A=a,b,c,R=(a,a),(a,b),(b,c), 證 rs(R)=sr(R).3設 R 是 A 上的二元關系，試： R 是傳遞的當且僅當R R ，其中 R 2 暗示 .4明下列結論：（1）（2）P R R( B C ), B ), D D解：（1）1 附前提2 P T ， 1 ，I3 PQ T，2，I45QR P R ， 3

6、，4，I6（2）1QR CP D 假 設前提23DAA ， 1 ，2，I45(A(A AB ， 4 ，I6B ， 3 ，5，I7A ， 4 ，IR R 8 C ， ，7，I9 B ， ，8 合取式10（C）11（ B C ） （ B C ）T，910，合取式，矛盾已知 R 和 S 黑空集合 A 上的等價系，試證 1）S是 A 的價關系； ）對 aA，R=a a 解：xA，由于 R 和 是自反關系，以是x,x、，因 x,xR故 S 是自反的.x 、 A， 、 ， 由于 R 和 S 是對稱關系，以是 y,x、，此 RS， RS 是對稱的.x y 、 z ，若 R 且 S ， 、 且 、 S由于 R 和 S 是傳遞的，以是因 因此 R ，故 RS 是遞的 .總之 是等價關系.R R R R