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

1、.離散數(shù)學(xué)試題第一部分 選擇題 一、單項(xiàng)選擇題1下列是兩個(gè)命題變元p，q的小項(xiàng)是（ C ）AppqBpqCpqDppq2令p：今天下雪了，q：路滑，則命題“雖然今天下雪了，但是路不滑”可符號化為（ D ）ApqBpqCpqDpq3下列語句中是命題的只有（ A ）A1+1=10Bx+y=10Csinx+siny0Dx 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)(Q(x,z)(x)(y)R(x,

2、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上的等價(jià)關(guān)系R=,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,BD,B8設(shè)X，Y，Z是集合，一是集合相對補(bǔ)運(yùn)算，下列等式不正確的是（ 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)

3、9在自然數(shù)集N上，下列定義的運(yù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是等價(jià)關(guān)系; B當(dāng)R和S都是自反關(guān)系;C當(dāng)R和S都是等價(jià)關(guān)系; D當(dāng)R和S都是傳遞關(guān)系11.設(shè)R是A上的二元關(guān)系,且RRR,可以肯定R應(yīng)是( D )A對稱關(guān)系; B全序關(guān)系; C自反關(guān)系; D傳遞關(guān)系第二部分 非選擇題二、填空題1設(shè)論域是a,b,c，則(x)S(x)等價(jià)于命題公式 S(a)S(b)S(c) ；()S(x)等價(jià)于命題公式 S(

4、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 。三、計(jì)算題1（4分）如果論域是集合a,b,c，試消去給定公式中的量詞：。2用等值演算求下面公式的主析取范式。3用等值演算法求公式的主合取范式。4（6分）在偏序集中，其中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,試

5、求：1) 寫出劃分誘導(dǎo)的等價(jià)關(guān)系R；2) 寫出關(guān)系矩陣；3) 畫出關(guān)系圖。6. 設(shè)Aa，b，c，d，R是A上的二元關(guān)系，且R，求r(R)、s(R)和t(R)。解 r(R)RIA，s(R)RR-1，R2，R3，R4，R2t(R)，四、證明題1設(shè)R和S是二元關(guān)系，證明2設(shè)A=a,b,c,R=(a,a),(a,b),(b,c),驗(yàn)證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

6、)(AC)P5ABT，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上的等價(jià)關(guān)系，試證：1）RS是A上的等價(jià)關(guān)系；2）對aA，aRS=aRaS。解：xA，因?yàn)镽和S是自反關(guān)系，所以R、S，因而RS，故RS是自反的。x、yA，若RS，則R、S，因?yàn)镽和S是對稱關(guān)系，所以因R、S，因而RS，故RS是對稱的。x、y、zA，若RS且RS，則R、S且R、S，因?yàn)镽和S是傳遞的，所以因R、S，因而RS，故RS是傳遞的。總之RS是等價(jià)關(guān)系。2）因?yàn)閤aRSRSRS xaRxa