離散數(shù)學練習題(含答案).doc

易自考離散數(shù)學試題第一部分 選擇題 一、單項選擇題1下列是兩個命題變元p，q的小項是（ 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,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設A=a,b,c,d，A上的等價關(guān)系R=,IA，則對應于R的A的劃分是（ D ）Aa,b,c,dBa,b,c,dCa,b,c,dDa,b,c,d7設A=，B=P(P(A)，以下正確的式子是（ A ）A,BB,BC,BD,B8設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.設R和S是集合A上的關(guān)系,RS必為反對稱關(guān)系的是( A )A當R是偏序關(guān)系,S是等價關(guān)系; B當R和S都是自反關(guān)系;C當R和S都是等價關(guān)系; D當R和S都是傳遞關(guān)系11.設R是A上的二元關(guān)系,且RRR,可以肯定R應是( D )A對稱關(guān)系; B全序關(guān)系; C自反關(guān)系; D傳遞關(guān)系第二部分 非選擇題二、填空題1設論域是a,b,c，則(x)S(x)等價于命題公式 S(a)S(b)S(c) ；()S(x)等價于命題公式 S(a)S(b) S(c) 。2設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用等值演算法求公式的主合取范式。4（6分）在偏序集中，其中Z=1,2,3,4,6,8,12,14，是Z中的整除關(guān)系，求集合D=2,3,4,6的極大元，極小元，最大元，最小元，最小上界和最大下界。5設集合A=1,2,3,4,5,A上的劃分為1,2,3,4,5,試求：1) 寫出劃分誘導的等價關(guān)系R；2) 寫出關(guān)系矩陣；3) 畫出關(guān)系圖。6. 設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設R和S是二元關(guān)系，證明2設A=a,b,c,R=(a,a),(a,b),(b,c),驗證rs(R)=sr(R)。3設R是A上的二元關(guān)系，試證：R是傳遞的當且僅當，其中表示。4證明下列結(jié)論：（1） （2）解：（1）1PQP附加前提2PT，1，I23PQT，2，I14PQRP5RT，3，4，I36PQRCP（2）1DP假設前提2DAP3AT，1，2，I54(AB)(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上的等價關(guān)系，試證：1）RS是A上的等價關(guān)系；2）對aA，aRS=aRaS。解：xA，因為R和S是自反關(guān)系，所以R、S，因而RS，故RS是自反的。x、yA，若RS，則R、S，因為R和S是對稱關(guān)系，所以因R、S，因而RS，故RS是對稱的。x、y、zA，若RS且RS，則R、S且R、S，因為R和S是傳遞的，所以因R、S，因而RS，故RS是傳遞的。總之RS是等價關(guān)系。2）因為xaRSRSRS xaRxaS xaRaS所以aRS=aRaS。五、應