華南理工《離散數(shù)學(xué)》模擬題及答案

1、1.A.1+101=110C.全體起立！B中國(guó)人民是偉大的。D計(jì)算機(jī)機(jī)房有空位嗎?在上面句子中，是命題的是（2.設(shè)Q（X）：x是有理數(shù),謂詞邏輯中的符號(hào)化公式是（5）R（x）：x是實(shí)數(shù)。命題“某些實(shí)數(shù)是有理數(shù)”在B）A.(Vx)(Q(x)tR(x)丿6Vx9(Q(x)aR(x)C.Ox)(Q(x)tR(x)D(3x)fQ(x)aR(x)對(duì)于集合1,2,3,下列關(guān)系中不等價(jià)的是(B)AR=,B.R=,C.R=v1,1,v3,3,v3,2,DR=,V3,1”V3,3,V2,3,設(shè)A=1,2,3,4,5,B=a,b,c,d,e,以下哪個(gè)函數(shù)是從A到B的雙射函數(shù)(B)AF=,E.F=1,O,C-F=,

2、DF=,下列判斷不正確的是(D)jtiV2|nN)關(guān)于普通加法構(gòu)成群iV2|nGN關(guān)于普通乘法構(gòu)成獨(dú)異點(diǎn)所有實(shí)數(shù)對(duì)。vc,d=va+c,b+d構(gòu)成群D實(shí)數(shù)集R關(guān)于。運(yùn)算構(gòu)成半群，其中aob=2（a+b）二、判斷題（本大題20分，每小題4分）1、命題公式p-（p/q）是重言式。()2、(Vx)A(x)tB)O(3x)(A(x)tE)。(_V)3、設(shè)A=a,b,c,RgAxAR=,則R是傳遞的。4、n階無(wú)向完全圖K“的每個(gè)頂點(diǎn)的度都是n。5、根樹中除一個(gè)結(jié)點(diǎn)外，其余結(jié)點(diǎn)的入度為1。（X）三、解答題（計(jì)算或者證明題：本大題50分，每小題10分）設(shè)命題公式為iQ/（PtQ）t-P。高級(jí)語(yǔ)言程序設(shè)計(jì)I試

3、卷（A）第1頁(yè)共11頁(yè)高級(jí)語(yǔ)言程序設(shè)計(jì)I試卷（A）第3頁(yè)共11頁(yè)高級(jí)語(yǔ)言程序設(shè)計(jì)I試卷（A）第3頁(yè)共11頁(yè)高級(jí)語(yǔ)言程序設(shè)計(jì)I試卷（A）第2頁(yè)共（1）求此命題公式的真值表；（2）求此命題公式的析取范式;（3）判斷該命題公式的類型。pQQPtQ-iQa(PtQ)P-Q/(PtQ)t-iP0011111010101110100011101001(2)QA(P-Q)T-iPO-1(-QA(-PvQ)v-iPO(Qv-n(iPvQ)ViPO-1(-iPvQ)v(Qv-nP)O1(析取范式)O(P/Q)v(P/Q)v(P/Q)v(PaQ)(主析取范式)(3)該公式為重言式用直接證法證明：前提：(0 x)(

4、C(x)tW(x)AR(x),(3x)(C(x)AQ(x)結(jié)論：Gx)(Q(x)AR(x)oc(ccwRQX17X17x)zX17lzx)zX172345678z(vz(vz(vz(z(vz(vz(X/(Q(wRaq(ctar(x)ar(x)ARpES(1)PUS(3)T(2)IT(4,5)IT(6)IT(2)IT(7,8)I(3x)(Q(x)AR(x)EG(9)設(shè)R是集合A=1,2,3,4,6,12上的整除關(guān)系。給出關(guān)系R;給出COVA畫出關(guān)系R的哈斯圖；給出關(guān)系R的極大、極小元、最大、最小元。3、解R=,UIaCOV缶V12,V2,4,V2,6,作哈斯圖如右：1叭極小元和最小元為1；4rX

5、極大元和最大元為12如圖所示帶權(quán)圖，用避圈法（Kniskal算法）求一棵最小生成樹并計(jì)算它的權(quán)值。高級(jí)語(yǔ)言程序設(shè)計(jì)I試卷（A）第3頁(yè)共11頁(yè)高級(jí)語(yǔ)言程序設(shè)計(jì)I試卷（A）第3頁(yè)共11頁(yè)高級(jí)語(yǔ)言程序設(shè)計(jì)I試卷（A）第2頁(yè)共C(T)=l+3+4+5+2=155、設(shè)字母a,b,c,d,e,f在通訊中出現(xiàn)的頻率為：a:30%b:25%c:20%,d:10%e:10%f:5%。試給出傳輸這6個(gè)字母的最佳前綴碼？問(wèn)傳輸1000個(gè)字符需要多少位二進(jìn)制位？解先求傳輸100個(gè)字符所需要的位數(shù)。a:30,b:25,c:20,d:10,e:10,f:5是依照出現(xiàn)頻率得出的個(gè)數(shù)。構(gòu)造最優(yōu)二義樹如下:5101020253

6、01510202530252025302545304555100需要二進(jìn)制位數(shù)為10W(T)=10 x4x(5+10)+3x10+2x(20+25+30)=2400高級(jí)語(yǔ)言程序設(shè)計(jì)I試卷(A)第 頁(yè)共11頁(yè)B設(shè)P,Q是命題公式，德摩根律為：-(P八Q)0(iPv-,Q)。令M(x)：x是大學(xué)生,P(y)：y是運(yùn)動(dòng)員，H(x,y)：x欽佩y。則命題“有些大學(xué)生不欽佩所有運(yùn)動(dòng)員?！笨煞?hào)化為(3x(M(X)AVy(P(y)-H(x,y)o設(shè)集合匪a,b,c,E的幕集P(E)=(a,b,c,a,b,a,c,b,c,a,b,c)。設(shè)R為定義在集合A上的一個(gè)關(guān)系，若R是(自反的，對(duì)稱的，傳遞的)，則R稱

7、為是集合A上的等價(jià)關(guān)系。設(shè)集合A上的關(guān)系R和S,R=,S=,則MS二(,)。個(gè)代數(shù)系統(tǒng)VS,*,其中S是非空集合。*是5上的一個(gè)二元運(yùn)算，如果(運(yùn)算*是封閉的),則稱代數(shù)系統(tǒng)VS,*為廣群。設(shè)圖G=，如果有圖G=VV,E，且(VrcVrEcE),則稱G，是G的子圖。一棵有n個(gè)頂點(diǎn)的樹含有(n-1)邊。P322如果二元運(yùn)算運(yùn)算*對(duì)集合A封閉，則意味著對(duì)任意的a,bwA有(a*bWA)o設(shè)非空集合A的幕集為pZ則在代數(shù)系統(tǒng)丹，QU中，對(duì)于U運(yùn)算的幺元是();設(shè)G是個(gè)具有5個(gè)結(jié)點(diǎn)的簡(jiǎn)單無(wú)向完全圖，則6有(5*(5-1)/2)條邊。設(shè)G是個(gè)無(wú)自環(huán)的無(wú)向圖，其中有2個(gè)結(jié)點(diǎn)的度數(shù)為4,其余結(jié)點(diǎn)的度為2,有

8、6條邊。則G中共有(2)個(gè)結(jié)點(diǎn)。因此，G是個(gè)(多重)圖。判斷下列命題的對(duì)錯(cuò)。正確的在括號(hào)內(nèi)填錯(cuò)誤的在括號(hào)內(nèi)填X。TOC o 1-5 h z“我們要努力學(xué)習(xí)”是命題。(x)命題“如果雪是黑的，那么太陽(yáng)從東方出”是假命題。(X)3(3x)(A(x)tB(x)O(Vx)A(x)(3x)B(x)。P70(V)命題公式(Q/(PtQ)TiP是重言式。P19,永真式(X)命題公式(P/Q)v(iRtT)是析取范式。P31析取范式定義(X)R(x)：“x是大學(xué)生?！笔敲}。(X)7設(shè)A,B是任意集合，則AGB=(A-B)U(B-A)P92(V)8集合A=12,3上的關(guān)系,是對(duì)稱的。(X)集合A的幕集Q(刃上

9、的包含關(guān)系是偏序關(guān)系。P140TOC o 1-5 h z每個(gè)元素都有逆元的半群是群。不一定有幺元(X)設(shè)X=1,2,3,Y=a,bo關(guān)系F=,是函數(shù)。(X)P14712ii階無(wú)向完全圖Kn的每個(gè)頂點(diǎn)的度都是ii。頂點(diǎn)數(shù)-1(X)設(shè)I是整數(shù)集，+是I上的普通加法，則代數(shù)系統(tǒng)是群。(V)經(jīng)過(guò)圖中每條邊一次且僅一次的回路稱為漢密爾頓回路。(X)根樹中除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)的入度都為1。(V)設(shè)A,B都是合式公式，則AaBt-JB也是合式公式。(J)PtQOiPvQo(V)對(duì)謂詞公式(Vx)(P(y)vQ(x,y)aR(x,y)中的自由變?cè)M(jìn)行代入后得到公式(Vx)(P(z)vQ(x,z)aR(x,y)

10、o(J)對(duì)任意集合A、B、C,有(A-B)-C=(A-C)-(B-C)oP95(V)20.三、在每小題的備選答案中只有一個(gè)正確答案，將正確答案序號(hào)填入下列敘述中的內(nèi)。1.(1)如果天氣好，那么我去散步。(3)x=3。在上面句子中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)可達(dá)或相互可達(dá)。P284(X)2.34.5.是命題。(2)天氣多好呀！(4)明天下午有會(huì)嗎?(1)設(shè)：P：王強(qiáng)身體很好；Q：王強(qiáng)成績(jī)很好。命題“王強(qiáng)身體很好，成績(jī)也很好。”在命題邏輯中可符號(hào)化為o(4)PvQ(2)PtQPa-,Q(4)PaQ設(shè)S(x)：x是學(xué)生，J(y)：y是教師，L(x,y)：x欽佩y。命題所有學(xué)生都?xì)J佩一些教師”的符號(hào)化公式是。

11、(3)(1)(2)(4)Vx(S(x)aVy(J(y)aL(x,y)Vx3y(S(x)t(J(y)tL(x,y)Vx(S(x)-3y(J(y)aL(x,y)3yVx(S(x)t(J(y)aL(x,y)_o(2)P9(2)-i(Pa(QvR)(4)/QT/RtPo(4)下列式子是合式公式的是(PVQAQ)(3)(P-iQ)下列式子中正確的是(1)(2)(Vx)P(x)O(3x)P(x)-i(Vx)P(x)：(Vx)-iP(x)-1(3x)P(x)U(3x)-nP(x)(4)-!(3x)P(x)U(Vx)-.P(x)設(shè)S=d,3,a,a,則S的幕集P(S)有個(gè)元素。P858(2)12(3)16(4

12、)32設(shè)R為定義在集合A上的一個(gè)關(guān)系，若R是,則R為等價(jià)關(guān)系。(2)(1)反自反的，對(duì)稱的和傳遞的(2)自反的，對(duì)稱的和傳遞的(3)自反的，反對(duì)稱的和傳遞的(4)對(duì)稱的，反對(duì)稱的和傳遞的設(shè)A=1,2,3,B=1,2,則下列命題不正確的是。(1)AAB=1,2(2)A-B=3P90(3)AB=2,3(4)BcA命題公式P蘊(yùn)涵Q是指。(3)(1)P與Q都是重言式(2)P/Q是重言式(3)PQ為重言式(4)QhR為重言式設(shè)A=1,2,3,4,5,B=6,7,8,9,10,以下哪個(gè)關(guān)系是從A到B的入(單)射函數(shù)。(2)對(duì)應(yīng)(1)F=,(2)F=,F=,(4)F=,笛.運(yùn)算“一”是整數(shù)集I上的普通減法，

13、則代數(shù)系統(tǒng)滿足下列性質(zhì)o(4)(1)結(jié)合律(2)交換律(3)有零元(4)封閉性高級(jí)語(yǔ)言程序設(shè)計(jì)I試卷(A)第 #頁(yè)共11頁(yè)高級(jí)語(yǔ)言程序設(shè)計(jì)I試卷(A)第 #頁(yè)共11頁(yè)高級(jí)語(yǔ)言程序設(shè)計(jì)I試卷（A）第2頁(yè)共高級(jí)語(yǔ)言程序設(shè)計(jì)I試卷(A)第 #頁(yè)共11頁(yè)高級(jí)語(yǔ)言程序設(shè)計(jì)I試卷(A)第 #頁(yè)共11頁(yè)高級(jí)語(yǔ)言程序設(shè)計(jì)I試卷（A）第2頁(yè)共13.設(shè)I是整數(shù)集，N是自然數(shù)集，P(S)是S的幕集，“X,+,C”是普通的乘法，加法和集合的交運(yùn)算。下面代數(shù)系統(tǒng)中是群。(1)(2)(3)(4)14.下列四個(gè)有6個(gè)結(jié)點(diǎn)的圖是連通圖。P281(3)高級(jí)語(yǔ)言程序設(shè)計(jì)I試卷(A)第 #頁(yè)共11頁(yè)高級(jí)語(yǔ)言程序設(shè)計(jì)I試卷(A)第

14、#頁(yè)共11頁(yè)高級(jí)語(yǔ)言程序設(shè)計(jì)I試卷（A）第2頁(yè)共高級(jí)語(yǔ)言程序設(shè)計(jì)I試卷(A)第 #頁(yè)共11頁(yè)高級(jí)語(yǔ)言程序設(shè)計(jì)I試卷(A)第 #頁(yè)共11頁(yè)高級(jí)語(yǔ)言程序設(shè)計(jì)I試卷（A）第2頁(yè)共P274(4)(1)(2)15有m條邊的圖的結(jié)點(diǎn)度數(shù)總和為(1)m(3)2(m-1)設(shè)：p：劉平聰明。q：劉平用功。在命題邏輯中，命題：“劉平不但聰明，而且用功”可符號(hào)化為：。(1)(1)PaQ(2)-.PVQ是重言式時(shí)，稱“A蘊(yùn)含B”，并(S)Pv-iQB0(2)高級(jí)語(yǔ)言程序設(shè)計(jì)I試卷（A）第 頁(yè)共11頁(yè)高級(jí)語(yǔ)言程序設(shè)計(jì)I試卷（A）第 #頁(yè)共11頁(yè)高級(jí)語(yǔ)言程序設(shè)計(jì)I試卷（A）第2頁(yè)共(1)(2)AtE(3)AiB(4)iA

15、BTOC o 1-5 h z設(shè)Q(x)：x是有理數(shù)，R(x)：x是實(shí)數(shù)。命題“每一個(gè)有理數(shù)是實(shí)數(shù)”在謂詞邏輯中的符號(hào)化公式是(1)(1)(Vx)(Q(x)-R(x)(2)(Vx)(Q(x)aR(x)(3)(3x)(Q(x)-R(x)(4)(3x)(Q(x)aR(x)19設(shè)a,b和(c,d)分別表示實(shí)數(shù)集上的閉區(qū)間和開區(qū)間，則(0,4n2,6)-(1,3)=(1)(1)3,4(2)(3,4)(3)3,4(4)0,1U3,620對(duì)于集合1,2,3,下列關(guān)系中不等價(jià)的是(2)R=,R=V1,1,V1,4R=,(4)R=vi,l,vi2,v2,l,vi,3,”,集合S的慕集P(S)關(guān)于集合的并運(yùn)算“U

16、”的零元為(2)(1)e(2)S(3)沒(méi)有(4)P(S)給定無(wú)孤立點(diǎn)無(wú)向圖G的邊集：(1,2),(1,3),(2,3),(2,4),(2,5),(3,4),(3,5),找出圖G的一棵生成樹為P324(1)(1)1(2)J:(1,2),(1,3),(:(1,2),(1,3),24),23),（3,5）（2,4）!(1,2),(1,3),：3,5),(4,5）(4)!(1,2),(3,4),Q）的真值表;（2）求命題公式（PA（Q-R）S的析取范式。真值表：PQQI001Q1iQa(PtQ)1-iPHQ/(PtQ)T-1P11010101110100011101001析取范式：P31(Pa(QtR

17、)tSO-i(Pa(-iQvR)vSO-iPv-i(-iQvR)vSOPv(Qa-iR)vS六、用推理規(guī)則證明P75六、用推理規(guī)則證明P75高級(jí)語(yǔ)言程序設(shè)計(jì)I試卷（A）第 #頁(yè)共11頁(yè)高級(jí)語(yǔ)言程序設(shè)計(jì)I試卷（A）第 頁(yè)共11頁(yè)高級(jí)語(yǔ)言程序設(shè)計(jì)I試卷（A）第2頁(yè)共Vx(P(x)-Q(x)證明：(Vx)P(x)P(u)(Vx)(P(x)-Q(x)P(u)tQ(u)Q(u)(Vx)Q(x)(Vk)P(x)-(Hx)Q(x)VxP（x）tVxQ（x）P（附加前提）US（全稱指定規(guī)則），PUS,T,，,5UG（全稱推廣規(guī)則），CP七、求下面公式的主析取范式與主合取范式，并寫出相應(yīng)的成真賦值(PtQ)/(

18、RtP)/(RtQ)tP)P34PQR-.(PtQ)/(RtP)v-i(Rt-!Q)t世)TTTFTTFTTFTTTFFTFTTFFTFTFFTFFFFF高級(jí)語(yǔ)言程序設(shè)計(jì)I試卷（A第10頁(yè)共11頁(yè)高級(jí)語(yǔ)言程序設(shè)計(jì)I試卷（A）第 #頁(yè)共11頁(yè)高級(jí)語(yǔ)言程序設(shè)計(jì)I試卷（A）第2頁(yè)共高級(jí)語(yǔ)言程序設(shè)計(jì)I試卷（A第10頁(yè)共11頁(yè)高級(jí)語(yǔ)言程序設(shè)計(jì)I試卷（A）第 頁(yè)共11頁(yè)高級(jí)語(yǔ)言程序設(shè)計(jì)I試卷（A）第2頁(yè)共主析取范式：iiiiiovinioivinioovmoio=(PAQA-iR)V(PA-iQAR)V(PAqQAqR)VhPAQAqR)主合取范式：mmAmonAmooiam00o=(PVQVR)A(-1PVQVR)AhPVqQVR