第1學(xué)期《離散數(shù)學(xué)》試卷A得分閱卷人（試卷共6頁(yè)，答題時(shí)間120分鐘）題號(hào)一二三四總分統(tǒng)分人復(fù)核人得分得分閱卷人一、選擇題（每小題2分，共20分。請(qǐng)將答案1、從集合分類(lèi)的角度看，命題公式可分為A.1、從集合分類(lèi)的角度看，命題公式可分為A.永真式、矛盾式題號(hào)12345678910答案()B.永真式、可滿足式、矛盾式C.可滿足式、矛盾式C.可滿足式、矛盾式D.永真式、可滿足式2、設(shè)B不含有x,x（A（x）B）等值于A.xA(x)BB.x(A(x)B)A.xA(x)BB.x(A(x)B)C.xA(x)BC.xA(x)BD.x(A(x)B)3、設(shè)S,T,M是集合，下列結(jié)論正確的是（A.如果A.如果SUT=SUM,則T=M.如果S-T=①，貝US=TC.SSS.STS(~T)C.SSS.STS(~T)4、設(shè)R是集合A上的偏序關(guān)系，則4、設(shè)R是集合A上的偏序關(guān)系，則R不一定是（A.自反的B.對(duì)稱(chēng)的C.反對(duì)稱(chēng)的D.傳遞5設(shè)R為實(shí)數(shù)集，定義R上4個(gè)二元運(yùn)算，不滿足結(jié)合律的是fi(x,y)=x+yf2(x,y)=x-yf3(x,y尸xyf4(x,y)=max{x,y}6、設(shè)＜工5設(shè)R為實(shí)數(shù)集，定義R上4個(gè)二元運(yùn)算，不滿足結(jié)合律的是fi(x,y)=x+yf2(x,y)=x-yf3(x,y尸xyf4(x,y)=max{x,y}6、設(shè)＜工,＞是一個(gè)格，則它不滿足（A.交換律B.結(jié)合律C.吸收律D.消去律7、設(shè)A={1,2},則群P(A),的單位元和零元是（A.與AB.C.{1}與D.{1}8、下列編碼是前綴碼的是).A.{1,11,101}B.{1,001,0011}C.{1,01,001,000}D.{0,00,000}9、下圖中既是歐拉圖又是哈密頓圖的是（A.K9K10A.K9K10C.K2,3K3,310、下圖所示的二叉樹(shù)中序遍歷的結(jié)果是B.edcba.badce得分閱卷人A.abcde二、填空題（每題3B.edcba.badce得分閱卷人A.abcde二、填空題（每題3分，共24分）1、含3個(gè)命題變項(xiàng)的命題公式的主合取范式為 MoM3M4M6M7,則它的主析取范式為。（表示成mm的形勢(shì)）2、〈Z4,〉模4加群，則3是 階元，33=—,3的逆元是

3、設(shè)3、設(shè)V=<Z,+>,其中“+”是普通加法xZ,令1（x）=x, 2（x）=-x,3（x）=x+5,4(x)=2x,其中有 上自同構(gòu).123456 4、設(shè) 是集合A={1,2,3,4,5,6}上的一個(gè)置換，則231546把它表示成不相交的輪換的積是。4、已知n階無(wú)向簡(jiǎn)單圖G有m條邊，則G的補(bǔ)圖有條邊。5、一個(gè)有向圖是強(qiáng)連通的充分必要條件是7、已知n階無(wú)向圖G中有m條邊，各頂點(diǎn)的度數(shù)均為3。又已知2n-3=m,貝Um= .8、在下圖中從A點(diǎn)開(kāi)始，用普里姆算法構(gòu)造最小生成樹(shù)，加入生成樹(shù)的第三條邊是( )。計(jì)算題(每題9分，共計(jì)算題(每題9分，共36分)1、已知命題公式(pq)(qp),(1)構(gòu)造真值表。(2)求主析取范式(要求通過(guò)等值演算推出)。2、R1={<1,2>,<1,3>,<2,3>},R 2={<2,2>,<2,3>,<3,4>},求：(1)RiR2 (2)R1 (3)求R2R13、設(shè)<A,R>為一個(gè)偏序集，其中，A={1,2,3,4,6,9,12,24},R是A上的整除關(guān)系。(1)畫(huà)R出的哈斯圖;

(2)求A的極大元和極小元；(3)求B={4,6}的上確界和下確界。4、畫(huà)一棵帶權(quán)為1,1,1,3,3,5,8的最優(yōu)二叉樹(shù)T,并計(jì)算它的權(quán)W(T)得分閱卷人得分閱卷人四、證明題(共20分)1、(7分)前提：p(qs),q,pr結(jié)論：rs2、(7分)A={(0,0),(0,1),(1,0),(1,3),(2,2),(2,3),(3,1)},R={<(a,b),(c,d)>|(a,b),(c,d) A且a+b=c+d}.(1)證明：R是A上的等價(jià)關(guān)系.(2)給出R確定的對(duì)A的劃分(分類(lèi)).3、(6分)設(shè)G,是群，S{x|xG且對(duì)于yG,xyyx},證明S是G的子群.《離散數(shù)學(xué)》試卷A

參考答案、選擇題(每小題2分，共20分。請(qǐng)將答案填在下面的表格內(nèi))得分閱卷人得分閱卷人二、填空題(每題3分，共24分)題號(hào)12345678910答案cadbbdbcaa1、m〔m2m53、2 4 、（123）（45）。4n（n」）n 5、存在經(jīng)過(guò)每個(gè)頂點(diǎn)的回路27、 9 . 8 、d,c或c,d三、計(jì)算題（每題9分，共36分）1、（1）構(gòu)造真值表（4分）p,q(pq)(qp)(pq)(qp)0001101100101111,1111⑵主析取范式(5分)：(pq)(qp)(pq)(qp)(pq)(qp)(pq)(qp)(pq)(pq)(pq)mom2m3 (0,2,3)2、(每小題3分)⑴RiR2={<1,2>,<1,3>} (2)Ri1={<2,1>,<3,1>,<3,2>}(1)求R2R1={<1,2>,<1,3>,<1,4>,<2,4>}3、(每小題3分)(4分)24（3分）A的極大元9,24;極小元1;（2分）B={4,6}的上確界12下確界24、畫(huà)圖（7分）W（T）=55（2分）四、證明題（共20分）1、（7分）證明：附加前提證明法..1分①r②pr③p ①② 3分④p(qs)③④..5分③④⑦s ⑤⑥ 7分2、證明： (1)(5分)(a,b)R(a,b)自反性成立自反性。對(duì)于 (a,b)R(a,b)自反性成立對(duì)稱(chēng)性。對(duì)于 (a,b),(c,d)A,如果(a,b)R(c,d),abcdcdab所以(c,d)R(a,b)對(duì)稱(chēng)性成立傳遞性。(a,b),(c,d),(x,y)A,如果(a,b)R(c,d), (c,d)R(x,y),abcd,cdxy,所以abxy,從而(a,b)R(x,y)傳遞性成立(2)A/R={{(0,0)},{(0,1),(1,0)},{(1,3),(2,2),(3,1)},{(2,3)}}(2分)3、證明：(每步各2分)S不空：G,是群，設(shè)e是G,的單位元，那么yG,都有eyye,eS,所以S不空。x1,x2S,那么對(duì)于 yG, 都有x1y