南京體育學(xué)院《離散數(shù)學(xué)》2021-2022學(xué)年期末試卷

1南京體育學(xué)院期末考試試題2021-2022學(xué)年第一學(xué)期《離散數(shù)學(xué)》（請(qǐng)考生在答題卡作答）一、單項(xiàng)選擇題(本大題共15小題．每小題1分．共15分)B．PV]QD．PA1Q2．下列命題公式為重言式的是()A.→(PAQB．P→(PAQ)D．(PVQ)Q3．下列4個(gè)推理定律中，不正確的是()4．謂詞公式中量詞的轄域是()B．P{X)C．(P(XV3YR())D．P(X),Q(X)5．設(shè)個(gè)體域A={a，b}，公式vxp(x)/]xs(x)在A中消去量詞后應(yīng)為(A．P(X}AS(XB．P(a)AP(b)A(S(a)VS(b)C．P(a)AS(bD．P(a)AP(b)AS(a)VS(b)6．下列選項(xiàng)中錯(cuò)誤的是()G{}{})2A．{{a}{bc}wmf5fd0}B．{{a,b}{c}{d{{a},{cd}D．{{a,b}，{cd}}8．設(shè)R為實(shí)數(shù)集，函數(shù)，則f是()A．滿射函數(shù)B．入射函數(shù)C．雙射函數(shù)D．非入射非滿射9．設(shè)R為實(shí)數(shù)集，R*={xlxRAX>0}，*是數(shù)的乘法運(yùn)算，是一個(gè)群，則下列集合關(guān)于數(shù)的乘法運(yùn)算構(gòu)成該群的子群的是()C．{R*中的自然數(shù)}D．{1,2,3}10．下列運(yùn)算中關(guān)于整數(shù)集不能構(gòu)成半群的是()A．a(chǎn)b=max{a,bB．a(chǎn)eb=bC．a(chǎn)b=2abD．a(chǎn)=la-b11．設(shè)z是整數(shù)集，+，別是普通加法和乘法，則(z，+，)是()B．整環(huán)和域D．含零因子環(huán)12．設(shè)A=fa，b，C)，R是A上的二元關(guān)系那A．反自反的B．反對(duì)稱的C．可傳遞的D．不可傳遞的13．設(shè)D=<V，E>為有向圖，V={a，b，c，d，e，f}，E={<a，b>，<A．強(qiáng)連通圖B．單向連通圖C．弱連通圖3D．不連通圖14．在有n個(gè)結(jié)點(diǎn)的連通圖中，其邊數(shù)A．最多有n—l條B．至少有n—l條C．最多有n條D．至少有n條15．連通圖G是一棵樹，當(dāng)且僅當(dāng)G中A．有些邊不是割邊B．每條邊都是割邊C．無(wú)割邊集D．每條邊都不是割邊二、填空題(本大題共l0小題，每小題2分，共20分)17．公式中的自由變?cè)獮椋s束變?cè)獮椤?9.當(dāng)f：x喻Y是函數(shù)時(shí)，f有逆函數(shù)，且f-1of=.20．設(shè)A={a，b，c}，R是A上的二元關(guān)系，且給定R={<a，b>．<b，C>，<C，a>}的自反閉包r(R)=，對(duì)稱閉包r(R)=。21．設(shè)Q為有理數(shù)集，笛卡爾集是s上的二元運(yùn)算22．設(shè)*是集合S上的二元運(yùn)算，若運(yùn)算*滿足且存在，則稱<S，*>為獨(dú)異點(diǎn)。23．令A(yù)={a，b，c}，<A，*>是循環(huán)群，a是單位元，則b2=，c的階是24．如下無(wú)向圖剖點(diǎn)是，割邊是。25．無(wú)向圖G具有生成樹．當(dāng)且僅當(dāng)。C的所有生成樹中的生成樹稱為最小生成樹。三、計(jì)算題(本大題共5小題，第26、27小題各5分．第28、29小題各6分．第30小題8分．共30分)26．集合A={a，b．C，d，e)上的二元關(guān)系R為4(1)寫出R的關(guān)系矩陣；(2)判斷R是不是偏序關(guān)系，為什么？27．利用真值表判斷公式是否為重言式。28.求公式（x）(F(x)A(y)G(x,y,z))(z)H(x,y,z)的前束范式。29．求下列公式的主析取范式和主合取范式：30．設(shè)A為54的因子構(gòu)成的集合，RGAXA,vx,yeA,XRyex整除y。畫出偏序集<A，R>的哈斯圖。并求A中的最大元，最小元，極大元，極小元。四、證明題（本大題共3小題。第3l、32小題各6分。第33小題8分。共20分)31．設(shè)R是A上的一個(gè)自反關(guān)系，證明：R是一個(gè)等價(jià)關(guān)系，當(dāng)且僅當(dāng)若<a，b>∈R，<a，c>R，則<b，C>R?！彩且粋€(gè)群。33．設(shè)圖G是具有6個(gè)結(jié)點(diǎn)，12條邊的無(wú)向簡(jiǎn)單圖，證明圖G是漢密爾頓圖。五、應(yīng)用題(本大題共2小題，第34小題8分，第35小題7分，共15分)34．構(gòu)造下面推理的證明。如果今天是星期六，我們就要到頤和園或圓明園去玩。如果頤和園游人太多，我們就不去頤和園玩。今天是星期六，頤