離散模擬題(自己總結(jié)版)

一.單項選擇題1. 永真命題公式( ) 只存在主析取范式;只存在主合取范式;既存在主析取范式也存在主合取范式;都不對.2. 下列代數(shù)系統(tǒng)中消去侓不成立的是( ).群;含幺半群;整環(huán);分配格.3.在4個元素的集合上可定義的滿射有( )個 4;12; 16 244. 在整環(huán)和格的定義中對運算都要求滿足的性質(zhì)是( ) 及收律; 冪等律; 交換律; 分配律.5. 下面對于群、環(huán)、格中運算都要求的性質(zhì)是( ) 結(jié)合性; 交換性; 冪等性; 分配性6. 下面說法中正確的是( ) 半群都有冪等元;.剩余類環(huán)中沒有零因子;.整數(shù)加法群不是循環(huán)群;每個群都有正規(guī)子群.7.下面正確的說法是( ) 5點格都不是分配格;剩余類環(huán)中沒有零因子; 數(shù)加群不是循環(huán)群;群中一定有等冪元8.Z5為模5剩余類集,定義f: Z5Z5如下:f(x)=2x+1,則f0f( ).不是函數(shù);不是單射;是置換;不是滿射(0:1;1:3;2:0;3:2;4:4)9.下面關(guān)于集合基數(shù)正確的說法是( ) 沒有最大的基數(shù)集;.任何集合都存在與它等勢的真子集; 有最小的基數(shù);有理數(shù)集合與實數(shù)集合等勢10. 下面圖中,可以割邊的圖是( )K10,10; 歐拉圖;平面圖;哈密頓圖.11. 在4個元素的集合上可定義的等價關(guān)系有( )個 4;8;12 15.12.群沒有平凡子群,則G( ) 沒有平凡子群;是循環(huán)群;是置換群;不存在.13. 設(shè)R是A上的二元關(guān)系,且R0R=R,則( ) r（ R）=R;S( R )=R;t( R )=R;R=IA.14.謂詞合適公式同時又是命題合適公式時,公式中必?zé)o( ) 自由變量;約束變量;個體常量;函數(shù).15.設(shè)T是G的生成樹,則( )G的回路必含T的邊;G的回路必不含T的邊;G的割邊必含T的邊;G的割邊必不含T的邊.16. 設(shè)18階簡單連通平面圖G有35條邊,則最多能為它增加( )條邊使其仍能保持是簡單平面圖. 13;.18;.20;.25.(35+133*18-6=48)17.下式中( )是永真的.(PQ) (PQ)；(PQ)(PQ)；(PQ) (PQ)；(PQ)(PQ).18. 下面在集合論和邏輯學(xué)中正確的公式有( ) PPPP;2AU2B=2AUB;x(A(x) B(x) $xA(x)xB(x);AB=ACB=C;19. 下面可由拉格朗日定理推出的結(jié)論是( )每個群都有循環(huán)子群;素數(shù)階的群是循環(huán)群;群中方程有解;群的同態(tài)核是群的正規(guī)子群.20. 下面能夠符合既無割點也無割邊的圖類是( ).樹; 歐拉圖;哈密頓圖;二部圖.21. 設(shè)R是A上的二元關(guān)系,且R0R=R可以肯定R應(yīng)是( ) 自反關(guān)系;傳遞關(guān)系;反對稱關(guān)系;等價關(guān)系22.一個格中每個元都有補元,則該格必是( ) 有限格; 分配格; 有界格; 布爾格23.如果圖G存在完備匹配M,下面敘述正確的是( ) G中無割邊;G中無割點;不存在M非飽和點;存在M增廣道路24. 下面哪個是有限半群必然具備的? ( ) 有等冪元; 有零元; 有幺元; 方程有解25.循環(huán)群之間的滿同態(tài)映射( ) 是單射; 是雙射; 把生成元映成生成元; 把零元映成零元二.多項選擇題 1.下面各圖中必存在生成樹的有( )哈密頓圖;歐拉圖;平面圖;平面圖的對偶圖;K6,82. 下面可由拉格朗日定理推出的結(jié)論是( )每個群都有循環(huán)子群;素數(shù)階的群是循環(huán)群;群中消去律成立;元素的周期可整除群的階;子群的階是群的階的因子3.下面集合中基數(shù)為阿列夫零的有( )100的倍數(shù)集;區(qū)間（2，4）;素數(shù)集合;偶數(shù)集合的冪集合；分子為5的真分數(shù)所成之集4.下列代數(shù)系統(tǒng)中消去律成立的有( )2A，;2A，U;置換群Sn，0;環(huán);分配格5.下面含有生成元的群有( ) 整數(shù)加法群;非零實數(shù)乘群;置換群; 素數(shù)階群剩余類乘群6.如果一個格中消去律成立,那么這個格( )是有補格;是分配格;是有界格;滿足吸收律;滿足冪等律7.下面各圖中邊數(shù)必不小于結(jié)點數(shù)的圖有( )哈密頓圖;歐拉圖;平面圖;二部圖;樹三.計算題1.求剩余類環(huán)Z12, ,上方程2x2+3x-3=0的全部解。2.如果一個n階簡單平面圖又是自補圖時,求n的可能值。3.寫出(PR) (QR)的主析取范式。4.設(shè)A=a,b,c,d,e,求該集合元素a和b在同一個等價類中的等價關(guān)系數(shù)目。5.設(shè)G是n階3度正則平面圖,求要給它新加多少邊才可能使它成為自對偶圖。6.寫出置換群中關(guān)于置換子群的全部左陪集。7.決定冪集代數(shù)系統(tǒng)2A，中有無幺元、零元、冪等元，如果有，寫出它們。8.當(dāng)n階K度正則圖是平面圖時，求n和k滿足的關(guān)系式。9.寫出5個元素的集合上可以定義的含2個等價類的全部等價關(guān)系。10. 設(shè)T是一個n階的完全3叉樹，求最少要給它新加多少邊才能使它成為歐拉圖。11.畫出元素個數(shù)為6的全部有補格對應(yīng)的Hasse圖。12.設(shè)a和b是交換群中周期分別為4和6的兩個元素,求a*b的周期。13.求一個20階的、非連通的、簡單平面圖的最大邊數(shù)。14設(shè)A=a,b,c,計算A上可以定義多少個二元關(guān)系,等價關(guān)系和雙射。15. 設(shè)n階簡單連通圖G既是自補圖又是平面圖,求它的面數(shù)表達式。16求的全部生成元。四.證明題1.1設(shè)R是集A上的等價關(guān)系，證明：對任何正整數(shù)n,Rn也是等價關(guān)系。1.2設(shè)R是集A上一個自反二元關(guān)系，且（a，b）R（a，c）R（b，c）R。證明：R是等價關(guān)系。1.3設(shè)R是集A上一個自反、對稱二元關(guān)系，且RoR-1=IA，證明：R是等價關(guān)系。2.1證明：連通圖G其對偶圖是平面二部圖當(dāng)且僅當(dāng)G是平面歐拉圖。2.2證明：如果圖G中存在兩個不同的完備匹配,證明G中必有回路。3.1證明：Q(PR)，(RS)B,A (SB)QPA。3.2證明：x(P(x)(Q(x)R(x)，xQ(x)$y(R