離散數(shù)學(xué)練習(xí)題

1、精選優(yōu)質(zhì)文檔-傾情為你奉上離散數(shù)學(xué)試題第一部分 選擇題 一、單項選擇題1下列是兩個命題變元p，q的小項是（ C ）AppqBpqCpqDppq2令p：今天下雪了，q：路滑，則命題“雖然今天下雪了，但是路不滑”可符號化為（ D ）ApqBpqCpqDpq3下列語句中是命題的只有（ A ）A1+1=10Bx+y=10Csinx+siny<0Dx mod 3=24下列等值式不正確的是（ C ）A(x)A(x)AB(x)(BA(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)(

2、Q(x,z)(x)(y)R(x,y,z)中量詞x的轄域是（ C ）A(x)Q(x,z)(x)(y)R(x,y,z)BQ(x,z)(y)R(x,y,z)CQ(x,z)(x)(y)R(x,y,z)DQ(x,z)6設(shè)A=a,b,c,d，A上的等價關(guān)系R=<a,b>,<b,a>,<c,d>,<d,c>IA，則對應(yīng)于R的A的劃分是（ D ）Aa,b,c,dBa,b,c,dCa,b,c,dDa,b,c,d7設(shè)A=Ø，B=P(P(A)，以下正確的式子是（ A ）AØ,ØBBØ,ØBCØ,ØB

3、DØ,ØB8設(shè)X，Y，Z是集合，一是集合相對補運算，下列等式不正確的是（ A ）A(X-Y)-Z=X-(YZ)B(X-Y)-Z=(X-Z)-YC(X-Y)-Z=(X-Z)-(Y-Z)D(X-Y)-Z=X-(YZ)9在自然數(shù)集N上，下列定義的運算中不可結(jié)合的只有（ D ）Aa*b=min(a,b)Ba*b=a+bCa*b=GCD(a,b)(a,b的最大公約數(shù))Da*b=a(mod b)10.設(shè)R和S是集合A上的關(guān)系,RS必為反對稱關(guān)系的是( A )A當(dāng)R是偏序關(guān)系,S是等價關(guān)系; B當(dāng)R和S都是自反關(guān)系;C當(dāng)R和S都是等價關(guān)系; D當(dāng)R和S都是傳遞關(guān)系11.設(shè)R是A上的二元關(guān)

4、系,且R·RÍR,可以肯定R應(yīng)是( D )A對稱關(guān)系; B全序關(guān)系; C自反關(guān)系; D傳遞關(guān)系第二部分 非選擇題二、填空題1設(shè)論域是a,b,c，則(x)S(x)等價于命題公式 S(a)S(b)S(c) ；()S(x)等價于命題公式 S(a)S(b) S(c) 。2設(shè)R為A上的關(guān)系，則R的自反閉包r(R)= _R_ ，對稱閉包s(R)= _R 。3某集合A上的二元關(guān)系R具有對稱性，反對稱性，自反性和傳遞性，此關(guān)系R是 _ ，其關(guān)系矩陣是 只有主對角線上元素為1 。三、計算題1（4分）如果論域是集合a,b,c，試消去給定公式中的量詞：。2用等值演算求下面公式的主析取范式。3用等

5、值演算法求公式的主合取范式。4（6分）在偏序集<Z,>中，其中Z=1,2,3,4,6,8,12,14，是Z中的整除關(guān)系，求集合D=2,3,4,6的極大元，極小元，最大元，最小元，最小上界和最大下界。5設(shè)集合A=1,2,3,4,5,A上的劃分為1,2,3,4,5,試求：1) 寫出劃分誘導(dǎo)的等價關(guān)系R；2) 寫出關(guān)系矩陣；3) 畫出關(guān)系圖。6. 設(shè)Aa，b，c，d，R是A上的二元關(guān)系，且R<a，b>，<b，a>，<b，c>，<c，d>，求r(R)、s(R)和t(R)。解 r(R)RIA<a，b>，<b，a>，<

6、;b，c>，<c，d>，<a，a>，<b，b>，<c，c>，<d，d>s(R)RR-1<a，b>，<b，a>，<b，c>，<c，d>，<c，b>，<d，c>R2<a，a>，<a，c>，<b，b>，<b，d>R3<a，b>，<a，d>，<b，a>，<b，c>R4<a，a>，<a，c>，<b，b>，<b，d>R2t(R)

7、<a，b>，<b，a>，<b，c>，<c，d>，<a，a>，<a，c>，<b，b>，<b，d>，<a，d>四、證明題1設(shè)R和S是二元關(guān)系，證明2設(shè)A=a,b,c,R=(a,a),(a,b),(b,c),驗證rs(R)=sr(R)。3設(shè)R是A上的二元關(guān)系，試證：R是傳遞的當(dāng)且僅當(dāng)，其中表示。4證明下列結(jié)論：（1） （2）解：（1）1PQP附加前提2PT，1，I23PQT，2，I14PQRP5RT，3，4，I36PQRCP（2）1DP假設(shè)前提2DAP3AT，1，2，I54(AB)(AC)P5

8、ABT，4，I2 6 BT，3，5，I3 7 ACT，4，I2 8CT，3，7，I3 9BCT，6，8 ，合取式10（BC）P11（BC）（BC）T，9，10，合取式，矛盾5. 已知R和S是非空集合A上的等價關(guān)系，試證：1）RS是A上的等價關(guān)系；2）對aA，aRS=aRaS。解："xA，因為R和S是自反關(guān)系，所以<x,x>R、<x,x>S，因而<x,x>RS，故RS是自反的。"x、yA，若<x,y>RS，則<x,y>R、<x,y>S，因為R和S是對稱關(guān)系，所以因<y,x>R、<y,x>S，因而<y,x>RS，故RS是對稱的。"x、y、zA，若<x,y>RS且<y,z>RS，則<x,y>R、<x,y>S且<y,z>R、<y,z>S，因為R和S是傳遞的，所以因<x,z>R、<x,z>S，因而<x,z>RS，故RS是傳遞的?？傊甊S是等價關(guān)系。2）因為xaRSÛ<x,a>RSÛ<x,