離散數(shù)學習題集(十五套).doc

離散數(shù)學試題與答案試卷一一、填空 20% （每小題2分）1設 （N：自然數(shù)集，E+ 正偶數(shù)） 則 。2A，B，C表示三個集合，文圖中陰影部分的集合表達式為 A B C 。3設P，Q 的真值為0，R，S的真值為1，則的真值= 。4公式的主合取范式為 。5若解釋I的論域D僅包含一個元素，則 在I下真值為 。6設A=1，2，3，4，A上關(guān)系圖為則 R2 = 。7設A=a，b，c，d，其上偏序關(guān)系R的哈斯圖為則 R= 。8圖的補圖為 。9設A=a，b，c，d ，A上二元運算如下：*a b c dabcda b c db c d ac d a bd a b c那么代數(shù)系統(tǒng)的幺元是 ，有逆元的元素為 ，它們的逆元分別為 。10下圖所示的偏序集中，是格的為 。 二、選擇 20% （每小題 2分）1、下列是真命題的有（）A ； B；C ； D 。2、下列集合中相等的有（ ） A4，3；B，3，4；C4，3，3；D 3，4。3、設A=1，2，3，則A上的二元關(guān)系有（ ）個。 A 23 ； B 32 ； C ； D 。4、設R，S是集合A上的關(guān)系，則下列說法正確的是（ ） A若R，S 是自反的， 則是自反的； B若R，S 是反自反的， 則是反自反的； C若R，S 是對稱的， 則是對稱的； D若R，S 是傳遞的， 則是傳遞的。5、設A=1，2，3，4，P（A）（A的冪集）上規(guī)定二元系如下則P（A）/ R=（ ）AA ；BP(A) ；C1，1，2，1，2，3，1，2，3，4；D，2，2，3，2，3，4，A6、設A=，1，1，3，1，2，3則A上包含關(guān)系“”的哈斯圖為（ ）7、下列函數(shù)是雙射的為（ ）Af : IE , f (x) = 2x ； Bf : NNN, f (n) = ；Cf : RI , f (x) = x ； Df :IN, f (x) = | x | 。（注：I整數(shù)集，E偶數(shù)集， N自然數(shù)集，R實數(shù)集）8、圖 中 從v1到v3長度為3 的通路有（ ）條。A 0；B 1；C 2；D 3。9、下圖中既不是Eular圖，也不是Hamilton圖的圖是（ ）10、在一棵樹中有7片樹葉，3個3度結(jié)點，其余都是4度結(jié)點則該樹有（ ）個4度結(jié)點。A1；B2；C3；D4 。三、證明 26%、 R是集合X上的一個自反關(guān)系，求證：R是對稱和傳遞的，當且僅當 和在R中有在R中。（8分）、 f和g都是群到的同態(tài)映射，證明是的一個子群。其中C= (8分)、 G= (|V| = v，|E|=e ) 是每一個面至少由k（k3）條邊圍成的連通平面圖，則， 由此證明彼得森圖（Peterson）圖是非平面圖。（11分）四、邏輯推演 16%用CP規(guī)則證明下題（每小題 8分）1、2、五、計算 18%1、設集合A=a，b，c，d上的關(guān)系R= , , , 用矩陣運算求出R的傳遞閉包t (R)。 （9分）2、如下圖所示的賦權(quán)圖表示某七個城市及預先算出它們之間的一些直接通信線路造價，試給出一個設計方案，使得各城市之間能夠通信而且總造價最小。（分）試卷二試題與答案一、填空 20% （每小題2分）1、 P：你努力，Q：你失敗?！俺悄闩?，否則你將失敗”的翻譯為 ；“雖然你努力了，但還是失敗了”的翻譯為 。2、論域D=1，2，指定謂詞PP (1,1)P (1,2)P (2,1)P (2,2)TTFF則公式真值為 。2、 設S=a1 ，a2 ，a8，Bi是S的子集，則由B31所表達的子集是 。3、 設A=2，3，4，5，6上的二元關(guān)系，則R= （列舉法）。R的關(guān)系矩陣MR= 。5、設A=1，2，3，則A上既不是對稱的又不是反對稱的關(guān)系R= ；A上既是對稱的又是反對稱的關(guān)系R= 。*a b cabca b cb b cc c b6、設代數(shù)系統(tǒng)，其中A=a，b，c,則幺元是 ；是否有冪等 性 ；是否有對稱性 。7、4階群必是 群或 群。8、下面偏序格是分配格的是 。9、n個結(jié)點的無向完全圖Kn的邊數(shù)為 ，歐拉圖的充要條件是 。10、公式的根樹表示為 。二、選擇 20% （每小題2分）1、在下述公式中是重言式為（ ）A；B；C； D。2、命題公式 中極小項的個數(shù)為（ ），成真賦值的個數(shù)為（ ）。A0； B1； C2； D3 。3、設，則 有（ ）個元素。A3； B6； C7； D8 。4、 設，定義上的等價關(guān)系則由 R產(chǎn) 生的上一個劃分共有（ ）個分塊。A4； B5； C6； D9 。5、設，S上關(guān)系R的關(guān)系圖為則R具有（ ）性質(zhì)。A自反性、對稱性、傳遞性； B反自反性、反對稱性；C反自反性、反對稱性、傳遞性； D自反性 。6、設 為普通加法和乘法，則（ ）是域。A BC D= N 。7、下面偏序集（ ）能構(gòu)成格。8、在如下的有向圖中，從V1到V4長度為3 的道路有（ ）條。A1； B2； C3； D4 。9、在如下各圖中（ ）歐拉圖。10、設R是實數(shù)集合，“”為普通乘法，則代數(shù)系統(tǒng) 是（ ）。A群； B獨異點； C半群 。三、證明 46%1、 設R是A上一個二元關(guān)系，試證明若R是A上一個等價關(guān)系，則S也是A上的一個等價關(guān)系。（9分）2、 用邏輯推理證明：所有的舞蹈者都很有風度，王華是個學生且是個舞蹈者。因此有些學生很有風度。（11分）3、 若是從A到B的函數(shù)，定義一個函數(shù)對任意有，證明：若f是A到B的滿射，則g是從B到 的單射。（10分）4、 若無向圖G中只有兩個奇數(shù)度結(jié)點，則這兩個結(jié)點一定連通。（8分）5、 設G是具有n個結(jié)點的無向簡單圖，其邊數(shù)，則G是Hamilton圖（8分）四、計算 14%1、 設是一個群，這里+6是模6加法，Z6=0 ，1，2，3，4，5，試求出的所有子群及其相應左陪集。（7分）2、 權(quán)數(shù)1，4，9，16，25，36，49，64，81，100構(gòu)造一棵最優(yōu)二叉樹。（7分）試卷三試題與答案一、 填空 20% （每空 2分）1、 設 f，g是自然數(shù)集N上的函數(shù)，則 。2、 設A=a，b，c，A上二元關(guān)系R= , , , 則s（R）= 。3、 A=1，2，3，4，5，6，A上二元關(guān)系，則用列舉法 T= ；T的關(guān)系圖為 ；T具有 性質(zhì)。4、 集合的冪集= 。5、 P，Q真值為0 ；R，S真值為1。則的真值為 。6、 的主合取范式為 。7、 設 P（x）：x是素數(shù)， E(x)：x 是偶數(shù)，O(x)：x是奇數(shù) N (x,y)：x可以整數(shù)y。則謂詞的自然語言是 。8、 謂詞的前束范式為 。二、 選擇 20% （每小題 2分）1、 下述命題公式中，是重言式的為（ ）。A、； B、；C、； D、。2、 的主析取范式中含極小項的個數(shù)為（ ）。A 、2； B、 3； C、5； D、0； E、 8 。3、 給定推理PUSPESTIUG推理過程中錯在（ ）。A、-; B、-; C、-; D、-; E、-4、 設S1=1，2，8，9，S2=2，4，6，8，S3=1，3，5，7，9，S4=3，4，5，S5=3，5，在條件下X與（ ）集合相等。A、 X=S2或S5 ； B、X=S4或S5；C、X=S1，S2或S4； D、X與S1，S5中任何集合都不等。5、 設R和S是P上的關(guān)系，P是所有人的集合，則表示關(guān)系 （ ）。A、；B、；C、 ； D、。6、 下面函數(shù)（ ）是單射而非滿射。A、；B、；C、；D、。其中R為實數(shù)集，Z為整數(shù)集，R+，Z+分別表示正實數(shù)與正整數(shù)集。7、 設S=1，2，3，R為S上的關(guān)系，其關(guān)系圖為 則R具有（ ）的性質(zhì)。A、 自反、對稱、傳遞； B、什么性質(zhì)也沒有；C、反自反、反對稱、傳遞； D、自反、對稱、反對稱、傳遞。8、 設，則有（ ）。A、1,2 ；B、1,2 ； C、1 ； D、2 。9、 設A=1 ,2 ,3 ，則A上有（ ）個二元關(guān)系。A、23 ； B、32 ； C、； D、。10、全體小項合取式為（ ）。A、可滿足式； B、矛盾式； C、永真式； D、A，B，C 都有可能。三、 用CP規(guī)則證明 16% （每小題 8分）1、2、四、（14%） 集合X=, , , ，R=,|x1+y2 = x2+y1 。1、 證明R是X上的等價關(guān)系。 （10分）2、 求出X關(guān)于R的商集。（4分）五、（10%）設集合A= a ,b , c , d 上關(guān)系R= , , , 要求 1、寫出R的關(guān)系矩陣和關(guān)系圖。（4分） 2、用矩陣運算求出R的傳遞閉包。（6分）六、（20%）1、（10分）設f和g是函數(shù)，證明也是函數(shù)。2、（10分）設函數(shù)，證明 有一左逆函數(shù)當且僅當f是入射函數(shù)。試卷四試題與答案一、 填空 10% （每小題 2分）1、 若P，Q，為二命題，真值為0 當且僅當 。2、 命題“對于任意給定的正實數(shù)，都存在比它大的實數(shù)”令F(x)：x為實數(shù)，則命題的邏輯謂詞公式為 。3、 謂詞合式公式的前束范式為 。4、 將量詞轄域中出現(xiàn)的 和指導變元交換為另一變元符號，公式其余的部分不變，這種方法稱為換名規(guī)則。5、 設x是謂詞合式公式A的一個客體變元，A的論域為D，A(x)關(guān)于y是自由的，則 被稱為存在量詞消去規(guī)則，記為ES。二、 選擇 25% （每小題 2.5分）1、 下列語句是命題的有（ ）。A、 明年中秋節(jié)的晚上是晴天； B、；C、當且僅當x和y都大于0； D、我正在說謊。2、 下列各命題中真值為真的命題有（ ）。A、 2+2=4當且僅當3是奇數(shù)；B、2+2=4當且僅當3不是奇數(shù)；C、2+24當且僅當3是奇數(shù)； D、2+24當且僅當3不是奇數(shù)；3、 下列符號串是合式公式的有（ ）A、；B、；C、；D、。4、 下列等價式成立的有（ ）。A、；B、；C、 ； D、。5、 若和B為wff，且則（ ）。A、稱為B的前件； B、稱B為的有效結(jié)論C、當且僅當；D、當且僅當。6、 A，B為二合式公式，且，則（ ）。A、為重言式； B、；C、； D、； E、為重言式。7、 “人總是要死的”謂詞公式表示為（ ）。（論域為全總個體域）M(x)：x是人；Mortal(x)：x是要死的。A、； B、C、；D、8、 公式的解釋I為：個體域D=2，P(x)：x3, Q(x)：x=4則A的真值為（ ）。A、1； B、0； C、可滿足式； D、無法判定。9、 下列等價關(guān)系正確的是（ ）。A、；B、；C、；D、。10、 下列推理步驟錯在（ ）。PUSPESTIEGA、；B、；C、；D、三、 邏輯判斷30% 1、 用等值演算法和真值表法判斷公式的類型。（10分）2、 下列問題，若成立請證明，若不成立請舉出反例：（10分）（1） 已知，問成立嗎？（2） 已知，問成立嗎？3、 如果廠方拒絕增加工資，那么罷工就不會停止，除非罷工超過一年并且工廠撤換了廠長。問：若廠方拒絕增加工資，面罷工剛開始，罷工是否能夠停止。（10分）四、計算10%1、 設命題A1，A2的真值為1，A3，A4真值為0，求命題的真值。（5分）2、 利用主析取范式，求公式的類型。（5分）五、謂詞邏輯推理 15%符號化語句：“有些人喜歡所有的花，但是人們不喜歡雜草，那么花不是雜草”。并推證其結(jié)論。六、證明：（10%）設論域D=a , b , c，求證：。試卷五試題與答案一、填空15%（每空3分）1、設G為9階無向圖，每個結(jié)點度數(shù)不是5就是6，則G中至少有 個5度結(jié)點。2、n階完全圖，Kn的點數(shù)X (Kn) = 。3、有向圖 中從v1到v2長度為2的通路有 條。4、設R，+，是代數(shù)系統(tǒng)，如果R，+是交換群 R，是半群 則稱R，+，為環(huán)。5、設是代數(shù)系統(tǒng)，則滿足冪等律，即對有 。二、選擇15%（每小題3分）1、 下面四組數(shù)能構(gòu)成無向簡單圖的度數(shù)列的有（ ）。A、（2，2，2，2，2）； B、（1，1，2，2，3）；C、（1，1，2，2，2）； D、（0，1，3，3，3）。2、 下圖中是哈密頓圖的為（ ）。3、 如果一個有向圖D是強連通圖，則D是歐拉圖，這個命題的真值為（ ）A、真； B、假。4、 下列偏序集（ ）能構(gòu)成格。5、 設，*為普通乘法，則S，*是（）。A、代數(shù)系統(tǒng)； B、半群； C、群； D、都不是。三、證明 48%1、（10%）在至少有2個人的人群中，至少有2 個人，他們有相同的朋友數(shù)。2、（8%）若圖G中恰有兩個奇數(shù)度頂點，則這兩個頂點是連通的。3、（8%）證明在6個結(jié)點12條邊的連通平面簡單圖中， 每個面的面數(shù)都是3。4、（10%）證明循環(huán)群的同態(tài)像必是循環(huán)群。5、（12%）設是布爾代數(shù)，定義運算*為，求證B，*是阿貝爾群。四、計算22%1、在二叉樹中1） 求帶權(quán)為2，3，5，7，8的最優(yōu)二叉樹T。（5分）2） 求T對應的二元前綴碼。（5分）2、 下圖所示帶權(quán)圖中最優(yōu)投遞路線并求出投遞路線長度（郵局在D點）。試卷六試題與答案一、 填空 15% （每小題 3分）1、 n階完全圖結(jié)點v的度數(shù)d(v) = 。2、 設n階圖G中有m條邊，每個結(jié)點的度數(shù)不是k的是k+1，若G中有Nk個k度頂點，Nk+1個k+1度頂點，則N k = 。3、 算式 的二叉樹表示為 。4、 如圖給出格L，則e的補元是 。5、 一組學生，用二二扳腕子比賽法來測定臂力的大小，則幺元是 。二、選擇 15% （每小題 3分）1、設S=0,1,2,3,為小于等于關(guān)系，則S，是（ ）。A、群；B、環(huán)；C、域；D、格。2、設a , b , c，*為代數(shù)系統(tǒng)，*運算如下：*abcaabcbbaccccc則零元為（ ）。A、a； B、b； C、c； D、沒有。3、如右圖 相對于完全圖K5的補圖為（ ）。4、一棵無向樹T有7片樹葉，3個3度頂點，其余頂點均為4度。則T有（ ）4度結(jié)點。A、1； B、2； C、3； D、4。5、設A，+，是代數(shù)系統(tǒng)，其中+，為普通加法和乘法，則A=（ ）時，A，+，是整環(huán)。A、； B、；C、； D、。三、證明 50%1、設G是（n,m）簡單二部圖，則。（10分）2、設G為具有n個結(jié)點的簡單圖，且，則G是連通圖。（10分）3、記“開”為1，“關(guān)”為0，反映電路規(guī)律的代數(shù)系統(tǒng)0，1，+，的加法運算和乘法運算。如下：+0101001000110101證明它是一個環(huán)，并且是一個域。（14分）4、 是一代數(shù)格，“”為自然偏序，則L，是偏序格。（16分）四、10%設是布爾代數(shù)上的一個布爾表達式，試寫出的析取范式和合取范式（10分）五、10%如下圖所示的賦權(quán)圖表示某七個城市及預先算出它們之間的一些直接通信成路造價（單位：萬元），試給出一個設計方案，使得各城市之間既能夠通信又使總造價最小。答案：試卷七試題與答案一、 填空 15% （每小題 3分）1. 任何(n,m) 圖G = (V,E) , 邊與頂點數(shù)的關(guān)系是 。2. 當n為 時,非平凡無向完全圖Kn是歐拉圖。3. 已知一棵無向樹T有三個3頂點,一個2度頂點,其余的都是1度頂點,則T中有 個1度頂點。4. n階完全圖Kn的點色數(shù)X(KN)= 。5. 一組學生,用兩兩扳腕子比賽來測定臂力大小,則幺元是 。二、