《離散數(shù)學(xué)》樣卷一、單選題（共20分）1．下列命題公式中，是重言式的是____________。A．?(?púq)ùqB.(p?q)?(?púq)C.p∧qD.p?q2．設(shè)A、B、C為任意集合，下面命題為真的____________。A．A－(B∪C)＝(A－B)∩(A－C)B.若AíB，則有~Aí~BC.~(A∪B)=~A∪~BD.~(A∩B)=~A∩~B3．2個頂點非同構(gòu)的無向樹有__________棵。A.1B.2C.3D.44．含有3個元素的集合共有____C______不同的劃分.A.3B.4C.5D.65．S是具有3個元素的集合，在S上可定義___________種不同的二元關(guān)系。A．512B.256C.128D.816．設(shè)A、B是集合，右圖的文氏圖的陰影部分的區(qū)域可用________表達式表示A.A∩BB.A∪BC.A-BD.(A∪B)-(A∩B)7．下面函數(shù)（）是單射而非滿射。A、；B、；C、；D、。其中R為實數(shù)集，Z為整數(shù)集，R+，Z+分別表示正實數(shù)與正整數(shù)集。8．用2面紅旗、3面黃旗依次懸掛在一根旗桿中，可以組成____________種不同的標志。A.10B.12C.120D.249．下列各數(shù)組中，不能構(gòu)成無向圖度數(shù)列的是__________。A．1，1，1，2，3；B.2,2,2,2,2C.3,3,3,3D.1，2，3，4，510．一棵無向樹T有7片樹葉，3個3度頂點，其余頂點均為4度。則T有______4度結(jié)點。A、1；B、2；C、3；D、4。二、填空題（共20分）1．設(shè)p、q的真值為0；r的真值為1，則命題公式：p∨(q∧r)的真值是______________。2．設(shè)解釋I為：個體域DI={2,3}，一元謂詞F(x):F(2)=0,F(3)=1；G(x,y):G(i,j)=1,(i,j=2,3)在解釋I下，公式："x(F(x)ùG(x,2))的真值為_________________。3．已知無向樹T中,有1個3度頂點,2個2度頂點,其余頂點全是樹葉.則它有_____片樹葉.4．若一個無向圖中共有12條邊，各頂點度數(shù)相同，則此圖有_______________個頂點。5.畫一個無向歐拉圖，它有偶數(shù)個頂點和偶數(shù)條邊。6．右圖的平面嵌入中，面次為____________，次數(shù)最高的面的次數(shù)為____________。7．在n元集A上定義的二元關(guān)系中有_________個自反關(guān)系。三．計算題（20分）1．求命題公式：(p??q)?r的主析取范式和成真賦值。2.設(shè)A={a,b,c,d,e}，R={<a,b>,<b,c>,<d,c>,<c,d>,<b,e>,<e,e>}，求R的自反閉包r(R)、對稱閉包s(R)和傳遞閉包t(R)。3.設(shè)f,g,h∈NN，且有求f°f,g°f,f°g,h°f,f°g°h。4.有向圖D如圖所示,求A,A2,A3,A4,求：D中長度為1,2,3,4的通路各有多少條？其中回路分別為多少條？四．證明題（共20分）1．用等值演算法證明等值式：?（A?B）?（A∨B）∧?（A∧B）2.證明：任何無向連通圖都有生成樹.3.證明：若R，S是對稱的，則R∪S也是對稱的。4.證明：設(shè)G為n階m條邊r個面的連通平面圖，則n-m+r=2.五．應(yīng)用題（共20分）1．符號化下面命題，并用謂詞邏輯構(gòu)造其推證結(jié)論的過程：每個大學(xué)生不是文科學(xué)生就是理工科學(xué)生，有的大學(xué)生是優(yōu)等生，小張不是理工科學(xué)生，但他是優(yōu)等生，因而如果小張是大學(xué)生，他就是文科學(xué)生。2．求1到1000之間（包含1和1000在內(nèi)）既不能被5和6整除，也不能被8整除的數(shù)有多少個？3.設(shè)A={1,2,3,4,5,6,7,8},A上的關(guān)系R如下定義：R={<x,y>|x,y∈A∧x≡y(mod3)}證明R為等價關(guān)系，并求A/R。4.已知如下圖所示項目網(wǎng)絡(luò)圖，求(1)關(guān)鍵路徑；(2)v0到v5的最短距離5.在通信中，設(shè)八進制數(shù)字出現(xiàn)的頻率如下：0：25%，1：20%，2：15%，3：10%，4：10%，5：