離散數(shù)學(xué)試卷及答案二

1、一、單項選擇題（本大題共15小題，每小題1分，共15分）在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內(nèi)。錯選、多選或未選均無分。1下列是兩個命題變元p，q的小項是（ ）AppqBpqCpqDppq2令p：今天下雪了，q：路滑，則命題“雖然今天下雪了，但是路不滑”可符號化為（ ）ApqBpqCpqDpq3下列語句中是命題的只有（ ）A1+1=10Bx+y=10Csinx+siny<0Dx mod 3=24下列等值式不正確的是（ ）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(

2、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的轄域是（ ）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è)R為實數(shù)集，函數(shù)f：RR，f(x)=2x，則f是（ ）A滿射函數(shù)B入射函數(shù)C雙射函數(shù)D非入射非滿射7設(shè)A=a,b,c,d，A上的等價關(guān)系R=<a,b>,<b,a>,<c,d>,<d,c>IA，則對應(yīng)于R的A的劃分是（ ）Aa,b,c,dBa,b,c,dCa,b,c,dD

3、a,b,c,d8設(shè)A=Ø，B=P(P(A)，以下正確的式子是（ ）AØ,ØBBØ,ØBCØ,ØBDØ,ØB9設(shè)X，Y，Z是集合，一是集合相對補(bǔ)運算，下列等式不正確的是（ ）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)10設(shè)*是集合A上的二元運算，稱Z是A上關(guān)于運算*的零元，若（ ）A有x*Z=Z*x=ZBZA，且有x*Z=Z*x=ZCZA，且有x*Z=Z*x=xDZA，且有x*Z=Z*x=Z11在自然數(shù)集N上，下列定義

4、的運算中不可結(jié)合的只有（ ）Aa*b=min(a,b)Ba*b=a+bCa*b=GCD(a,b)(a,b的最大公約數(shù))Da*b=a(mod b)12設(shè)R為實數(shù)集，R+=x|xRx>0，*是數(shù)的乘法運算，<R+，*>是一個群，則下列集合關(guān)于數(shù)的乘法運算構(gòu)成該群的子群的是（ ）AR+中的有理數(shù)BR+中的無理數(shù)CR+中的自然數(shù)D1，2，313設(shè)<A,*,>是環(huán)，則下列正確的是（ ）A<A,>是交換群B<A,*>是加法群C對*是可分配的D*對是可分配的14下列各圖不是歐拉圖的是（ ）15設(shè)G是連通平面圖，G中有6個頂點8條邊，則G的面的數(shù)目是（ ）

5、A2個面B3個面C4個面D5個面第二部分 非選擇題（共85分）二、填空題（本大題共10小題，每空1分，共20分）請在每小題的空格中填上正確答案。錯填、不填均無分。16一公式為 之充分必要條件是其析取范式之每一析取項中均必同時包含一命題變元及其否定；一公式為 之充分必要條件是其合取范式之每一合取項中均必同時包含一命題變元及其否定。17前束范式具有形式(Q1V1)(Q2V2)(QnVn)A，其中Qi(1in)為 ，A為 的謂詞公式。18設(shè)論域是a,b,c，則(x)S(x)等價于命題公式 ；()S(x)等價于命題公式 。19設(shè)R為A上的關(guān)系，則R的自反閉包r(R)= ，對稱閉包s(R)= 。20某集

6、合A上的二元關(guān)系R具有對稱性，反對稱性，自反性和傳遞性，此關(guān)系R是 ，其關(guān)系矩陣是 。21設(shè)<S,>是一個偏序集，如果S中的任意兩個元素都有 和 ，則稱S關(guān)于構(gòu)成一個格。22設(shè)Z是整數(shù)集，在Z上定義二元運算*為a*b=a+b+a·b，其中+和·是數(shù)的加法和乘法，則代數(shù)系統(tǒng)<Z,*>的幺元是 ，零元是 。23如下平面圖有2個面R1和R2，其中deg(R1)= ，deg(R2)= 。24無向圖G具有一條歐拉回路，當(dāng)且僅當(dāng)G是 ，并且所有結(jié)點的度數(shù)都是 。25在下圖中，結(jié)點v2的度數(shù)是 ，結(jié)點v5的度數(shù)是 。三、計算題（本大題共6小題，第2627小題每小題

7、4分，第28、30小題每小題5分，第29、31小題每小題6分，共30分）26（4分）求出從A=1,2到B=x,y的所有函數(shù)，并指出哪些是雙射函數(shù)，哪些是滿射函數(shù)。27（4分）如果論域是集合a,b,c，試消去給定公式中的量詞：。28（5分）設(shè)A=a,b,c ，P（A）是A的冪集，是集合對稱差運算。已知<P(A),>是群。在群<P(A),>中，找出其幺元。找出任一元素的逆元。求元素x使?jié)M足ax=b。29（6分）用等值演算法求公式(pq)(pq)的主合取范式30（5分）畫出5個具有5個結(jié)點5條邊的非同構(gòu)的無向連通簡單圖。31（6分）在偏序集<Z,>中，其中Z=1,2,3,4,6,8,12,14，是Z中的整除關(guān)系，求集合D=2,3,4,6的極大元，極小元，最大元，最小元，最小上界和最大下界。四、證明題（本大題共3小題，第3233小題每小題6分，第34小題8分，共20分）32（6分）用等值演算法證明(qs)r)(s(pr)(s(pq)r33（6分）設(shè)n階無向樹G=<V，E>中有m條邊，證明m=n-1。34（8分）設(shè)P=Ø,1,1,2,1,2,3，是集合P上的包含關(guān)系。（1）證明：