離散數(shù)學(xué)練習(xí)題

TTAstandardizationoffice【TTA5AB-TTAK08-TTA2C】TTAstandardizationoffice【TTA5AB-TTAK08-TTA2C】離散數(shù)學(xué)練習(xí)題一、填空題（10分，每空1分，請(qǐng)將本題答案填在原題橫線上?。?、設(shè)集合X={0，1，2}，R是X上的二元關(guān)系，R={<0，0>，<0，2>，<1，2>，<2，0>，<2，1>}，則R的關(guān)系矩陣MR=。2、為模6整數(shù)加群，則由2生成的子群<2>=，右陪集<2>⊕65=。3、設(shè)A和B為有限集，|A|=m，|B|=n，則有個(gè)從A到B的關(guān)系，有個(gè)從A到B的函數(shù)。4、無(wú)向圖G如下圖所示，G的點(diǎn)連通度κ為，邊連通度λ為。5、在上面無(wú)向圖中，已給出了一棵生成樹T（粗邊所示），則樹枝d對(duì)應(yīng)的基本割集是，弦b對(duì)應(yīng)的基本回路是。6、令F(x)：x是整數(shù)，G(x)：x是奇數(shù)，則“不存在不是奇數(shù)的整數(shù)”符號(hào)化為。7、含有三個(gè)命題變項(xiàng)P，Q，R的命題公式PQ的主析取范式是（用mi形式表示最小項(xiàng)）。二、單選題（20分，每題1分，請(qǐng)將本題答案寫在下方表格中?。?2345678910111213141516171819201、下面給出的符號(hào)串集合中，（）不是前綴碼。A、B、C、D、2、下列()組賦值不是命題公式的成真賦值。A、010B、011C、110D、1013、設(shè)A={a，b，c，d}，A上的等價(jià)關(guān)系R={<a，b>，<b，d>，<d，a>}∪R-1∪IA，則對(duì)應(yīng)于R的A的劃分是（）。A、{{a，b}，{c，d}}B、{{a，b，d}，{c}}C、{{a}，，{c}，tjmqenr}D、{{a}，{b，c}，nxrkd59}4、二部圖是()。A、歐拉圖B、哈密頓圖C、非連通圖D、完全圖5、令p:我將去上網(wǎng)，q:我有時(shí)間，則“我將去上網(wǎng)，僅當(dāng)我有時(shí)間”可符號(hào)化為()。(A)(B)(C)(D)6、下面（）圖不一定是樹。A、每對(duì)結(jié)點(diǎn)間都有路的圖B、無(wú)回路的連通圖C、連通但刪去一條邊則不連通的圖D、有n個(gè)頂點(diǎn)n—1條邊的連通圖7、集合A={1,2,…,10}上的關(guān)系R={<x,y>|x+y=10,x,y∈A},則R的性質(zhì)是()。(A)自反的 (B)傳遞的、對(duì)稱的(C)對(duì)稱的 (D)反自反的、傳遞的8、設(shè)G如右圖，那么G不是()。 (A)哈密頓圖 (B)完全圖(C)歐拉圖 (D)樹9、設(shè)圖D的鄰接矩陣為，則D的頂點(diǎn)數(shù)與邊數(shù)分別為()。A、4，5B、5，16C、4，10D、5，810、下列式子中正確的是（）。A、＝1B、C、｛｝D、＝{}11、由2個(gè)命題變?cè)猵和q組成的不等值的命題公式的個(gè)數(shù)有()。(A)2(B)4(C)16(D)812、給定下列非負(fù)整數(shù)序列，可構(gòu)成簡(jiǎn)單無(wú)向圖的節(jié)點(diǎn)度數(shù)序列的為()。(A)(1，3，4，4，5)(B)(1，1，2，2，2)(C)(0，1，3，3，5)(D)(1，1，2，2，3)13、4階完全無(wú)向圖中含3條邊的不同構(gòu)的生成子圖有()。(A)5(B)4(C)3(D)214、任意12階群的子群的階一定不為()。(A)3(B)6(C)8(D)415、在公式F(x，y)→yG(x，y)中變?cè)獂是()。(A)既是自由變?cè)?，又是約束變?cè)?(B)既不是自由變?cè)?，又不是約束變?cè)?C)自由變?cè)?(D)約束變?cè)?6、設(shè)圖G=<V，E>為無(wú)向圖，|V|=5，|E|=20，則G一定是()。A、完全圖B、正則圖C、多重圖D、簡(jiǎn)單圖17、給定公式，當(dāng)D={a,b}時(shí)，解釋()使該公式真值為0。(a)=0、P(b)=0 (a)=0、P(b)=1 (a)=1、P(b)=118、設(shè)A={1,2,3}，則A上有（）個(gè)二元關(guān)系。A、23B、32C、D、19、設(shè)Z是整數(shù)集合，“+”是數(shù)的加法運(yùn)算，則<Z，+>的單位元是()A、1B、-1C、沒有單位元D、020、設(shè)R和S是集合A={1，2，3，4}上的二元關(guān)系，則S是R的（）閉包。R={1，1，1，2，2，2，2，3，4，4}S={1，1，1，2，2，2，2，3，3，3，4，4}A、對(duì)稱B、自反C、傳遞D、以上都不對(duì)三、求解題（40分，每題8分，請(qǐng)將本題答案寫在后面答題紙上?。?、在自然推理系統(tǒng)中構(gòu)造證明：已知張三或李四的彩票中獎(jiǎng)了。如果張三的彩票中獎(jiǎng)了，那么你會(huì)知道張三的彩票中獎(jiǎng)了。如果李四的彩票中獎(jiǎng)了，那么王五的彩票也中獎(jiǎng)了。你不知道張三的彩票中獎(jiǎng)了。所以，李四和王五的彩票都中獎(jiǎng)了。2、設(shè)A={a,b,c,d,e}，A上的偏序關(guān)系R＝{<c,a>，<c,b>，<d,a>，<d,b>，<e,a>，<e,b>，<e,c>，<e,d>}IA，求：(1)畫出偏序集<A，R>的哈斯圖；(2)求子集B={c,d,e}的極大元，極小元，最大元，最小元。3、求一階邏輯公式的前束范式：(xF(x,y)→yG(y))→xH(x,y,z)。4、設(shè)7個(gè)字母在通信中出現(xiàn)的頻率如下：a:35%，b:20%，c:15%，d:10%，e:10%，f:5%，g:5%，用Huffman算法求傳輸它們的最佳前綴碼。要求畫出最優(yōu)二叉樹，并指出傳輸100個(gè)按上述頻率出現(xiàn)的字母，需要多少個(gè)二進(jìn)制數(shù)字。5、四、證明題（30分，每題7、7、8、8分，請(qǐng)將本題答案寫在后面答題紙上?。?、例如，f和g都是群<G1，。>到群<G2，*>的同態(tài)映射，C={x|x∈G1∧f(x)=g(x)}。證明：<C，。>是<G1，。>的一個(gè)子群。2、要在七天安排七場(chǎng)考試，同一個(gè)老師監(jiān)的任何兩場(chǎng)考試不能安排在接連的兩天內(nèi)進(jìn)行。假如每個(gè)教師最多監(jiān)