離散數(shù)學(xué)復(fù)習(xí)思考題-2022年整理

優(yōu)質(zhì)資料word版本——下載后可編輯優(yōu)質(zhì)資料word版本——下載后可編輯16/16優(yōu)質(zhì)資料word版本——下載后可編輯《離散數(shù)學(xué)》復(fù)習(xí)思考題一、選擇題對(duì)于公式，下列說(shuō)法正確的是（）。y是自由出現(xiàn)的；B．x是約束出現(xiàn)的；C．的轄域是；D．的轄域是．A設(shè)，下列正確的是（）。A．；B．；C．；D．．D設(shè)A-B=，則有（）。A．B=；B．B≠；C．AB；D．AB．C設(shè)N是自然數(shù)集合，函數(shù)是（）。滿射，不是單射；B．單射，不是滿射；C．雙射；D．非單射非滿射．B設(shè)R為實(shí)數(shù)集，函數(shù)f：R→R，f(x)=，則f是（）。A．滿射函數(shù)；B．單射函數(shù)；C．雙射函數(shù)；D．非單射非滿射．B設(shè)Z是整數(shù)集合，N是自然數(shù)集合，則函數(shù)是（）。滿射，不是單射；B．單射，不是滿射；C．雙射；D．非單射非滿射．A設(shè)函數(shù)f：N→N（N為自然數(shù)集），f(n)=n+1，下面四個(gè)命題為真的是（）。A.f是滿射

；

B.

f是單射；

C.f是雙射的

；

D.f非單射非滿射．B謂詞公式x(P(x)∨yR(y))→Q(x)中的變?cè)獂是（）。A．自由出現(xiàn)的； B．約束出現(xiàn)的；C．既不是自由出現(xiàn)也不是約束出現(xiàn)； D．既是自由出現(xiàn)也是約束出現(xiàn)．D下列不是謂詞公式的是（）。A．x∧y∨P（x，y）；B．x(P(x)→x(Q(x)∧A(x，y)))； C．xP（x）→R（y）；D．xP（x）∧Q（y，z）．A下列句子為命題的是（）。A．全體起立!B．x=0；C．你會(huì)抽煙嗎？ D．張三生于1886年的春天．D下列命題正確的是（）。A．{}=；B．{}=；C．{a}{a，b，c}；D．{a，b，c}．A下列命題正確的是（）。A．{l，2}{{1，2}，{l，2，3}，1}； B．{1，2}{1，{l，2}，{l，2，3}，2}；C．{1，2}{{1}，{2}，{1，2}}； D．{1，2}∈{1，2，{2}，{l，2，3}}．B下列圖形是（）。A．完全圖；B．哈密頓圖；C．歐拉圖；D．平面圖．B下列圖中不是平面圖的為（）。A.．B．C．D．C下列為公式的是（）。A．；B．；C．；D．．C下列語(yǔ)句中，（）是命題。A．下午有會(huì)嗎？B．這朵花多好看呀！C．2是偶數(shù)；D．請(qǐng)把門關(guān)上!C下列語(yǔ)句中是假命題的是（）。A．5是素?cái)?shù)；B．太陽(yáng)從東方升起；C．；D．正在下雨呢！C下列語(yǔ)句中是命題的是（）。A．天氣真暖和呀！B．請(qǐng)別激動(dòng)！C．還記得我嗎？D．地球是運(yùn)動(dòng)的．D下面既是哈密頓圖又是歐拉圖的是（）。B一個(gè)連通圖G具有以下何種條件時(shí)，能一筆畫出：即從某結(jié)點(diǎn)出發(fā)，經(jīng)過(guò)圖中每邊僅一次回到該結(jié)點(diǎn)（）。A．G沒(méi)有奇數(shù)度的結(jié)點(diǎn)； B．G有1個(gè)奇數(shù)度的結(jié)點(diǎn)；C．G有2個(gè)奇數(shù)度的結(jié)點(diǎn)；D．G沒(méi)有或有2個(gè)奇數(shù)度的結(jié)點(diǎn)．A在自然數(shù)集合上，下列運(yùn)算滿足結(jié)合律的是（）。A．B．C．D．B二、填空題令p：今天下雪了，q：路滑，則命題“雖然今天下雪了，但是路不滑”可符號(hào)化為_______。p∧┐q設(shè)：明天上午8點(diǎn)下雨，：明天上午8點(diǎn)下雪，：我去學(xué)校，則命題“如果明天上午8點(diǎn)不下雨并且也不下雪，我就去學(xué)?！笨煞?hào)化為。設(shè)：是偶數(shù)，：是素?cái)?shù)，則命題“存在著偶素?cái)?shù)”可符號(hào)化為_______。n個(gè)頂點(diǎn)的無(wú)向完全圖記為，當(dāng)n滿足條件__________時(shí),不是平面圖。設(shè)：我們勤奮，：我們好學(xué)，：我們?nèi)〉煤贸煽?jī)，則命題“我們只要勤奮好學(xué)，就能取得好成績(jī)”符號(hào)化為。設(shè)A（x）：x是人，B（x）：x犯錯(cuò)誤，命題“沒(méi)有不犯錯(cuò)誤的人”符號(hào)化為_______。或設(shè)G是連通的平面圖，已知G中有6個(gè)頂點(diǎn)，8條邊，則G有_______個(gè)面。4設(shè)P：他聰明，Q：他用功，則命題“他雖聰明,但不用功”可符號(hào)化為_______。P∧Q設(shè)集合，，則。設(shè)集合，，則。設(shè)集合，則A的冪集。設(shè)集合，則A的冪集。答案：設(shè)是人，要吃飯，則命題“人都是要吃飯的”可符號(hào)化為_______。答案：設(shè)是跳高運(yùn)動(dòng)員，a：小張，則命題“小張不是跳高運(yùn)動(dòng)員”可符號(hào)化為_______。無(wú)向圖G=<V,E>如右所示，則圖G的最大度數(shù)Δ(G)=_______。4無(wú)向圖G中有16條邊，且每個(gè)結(jié)點(diǎn)的度數(shù)都是2，則G的結(jié)點(diǎn)數(shù)是_______個(gè)。16無(wú)向完全圖中有________條邊。10已知關(guān)系,,則=_______。答案：已知關(guān)系,則=。已知關(guān)系，，則=。答案：已知關(guān)系,則=。答案：三、計(jì)算題構(gòu)造命題公式（PQ）Q的真值表，并判斷其類型。解：真值表PQPQ（PQ）（PQ）Q00100011001001011100因此公式（PQ）Q為矛盾式．對(duì)某單位的100名員工進(jìn)行調(diào)查，結(jié)果發(fā)現(xiàn)他們喜歡看球賽、電影和戲?。渲?8人喜歡看球賽，52人喜歡看電影，38人喜歡看戲劇，既喜歡看球賽又喜歡看戲劇的有18人，既喜歡看電影又喜歡看戲劇的有16人，三種都喜歡看的有12人，求只喜歡看電影的有多少人。解：設(shè)喜歡看球賽、電影和戲劇的人的集合分別為A,B,C，那么=58，=52，=38，=18，=16,=12，ABC261422612416只喜歡看電影的有22人．構(gòu)造命題公式（PQ）∧R的真值表，并判斷其類型。解：真值表為：PQRPQR（PQ）∧R000001010011100101110111111100111010101010100010公式（PQ）∧R為可滿足式．構(gòu)造命題公式的真值表，并判斷其類型。解：真值表為0000010100111001011101110000001110101011公式為可滿足式．集合上的關(guān)系，試寫出關(guān)系矩陣M，并討論R的性質(zhì)。解：關(guān)系矩陣，R是自反的和傳遞的．集合上的關(guān)系，試寫出關(guān)系矩陣M，并討論R的性質(zhì)。解：關(guān)系矩陣，R具有反對(duì)稱性和傳遞性．集合上的關(guān)系，試寫出關(guān)系矩陣M，并討論R的性質(zhì)。解：關(guān)系矩陣，R是自反的，反對(duì)稱的和傳遞的．集合上的關(guān)系，試寫出關(guān)系矩陣M，并討論R的性質(zhì)。解：關(guān)系矩陣，R具有自反性和對(duì)稱性．今有工人甲、乙、丙去完成三項(xiàng)任務(wù)a、b、c．已知甲能勝任a、b、c三項(xiàng)任務(wù)；乙能勝任a、b二項(xiàng)任務(wù)；丙能勝任b、c二項(xiàng)任務(wù)．試給出一種方案，使每個(gè)工人各去完成一項(xiàng)他們能勝任的任務(wù)。解：工人與任務(wù)的勝任關(guān)系的二部圖為：甲乙丙abc一種方案是：甲完成a，乙完成b，丙完成c．（注：本題答案不唯一，還可以給出其它的方案．）某班有學(xué)生50人，有26人在第一次考試中得優(yōu)，有21人在第二次考試中得優(yōu)，有17人兩次考試都沒(méi)有得優(yōu)，試求兩次考試都得優(yōu)的學(xué)生人數(shù)。解：設(shè)兩次考試都得優(yōu)的學(xué)生人數(shù)為x人，由下列文氏圖可知171726-xx21-x17+(26-x)+x+(21-x)=50，解得：x=14，兩次考試都得優(yōu)的學(xué)生人數(shù)為14人．某大學(xué)計(jì)算機(jī)專業(yè)的80名學(xué)生在期末考試中，Pascal語(yǔ)言課有58人達(dá)到優(yōu)秀，數(shù)據(jù)結(jié)構(gòu)課有30人達(dá)到優(yōu)秀，離散數(shù)學(xué)課有25人達(dá)到優(yōu)秀．并且，Pascal語(yǔ)言和數(shù)據(jù)結(jié)構(gòu)兩門課都達(dá)到優(yōu)秀的有20人，Pascal語(yǔ)言和離散數(shù)學(xué)兩門課都達(dá)到優(yōu)秀的有19人，數(shù)據(jù)結(jié)構(gòu)和離散數(shù)學(xué)兩門課都達(dá)到優(yōu)秀的有17人，還有10人一門優(yōu)秀都沒(méi)得到．求三門課都達(dá)到優(yōu)秀的人數(shù)。解：設(shè)期末考試中Pascal語(yǔ)言課、數(shù)據(jù)結(jié)構(gòu)課、離散數(shù)學(xué)課達(dá)到優(yōu)秀的學(xué)生集合分別為A,B,C，那么=58，=30，=25，=20，=19，=17由題意，至少有一門課達(dá)到優(yōu)秀的學(xué)生人數(shù)為=80-=70．于是，三門課都達(dá)到優(yōu)秀的學(xué)生數(shù)為：=-(++)=70-58-30-25+20+19+17=13．求圖中A到其余各頂點(diǎn)的最短路徑的權(quán)（要求列表）。B5D12A433F35C1E解：用用標(biāo)號(hào)法解題過(guò)程如下BCDEF01311*36423*64364*946*858*13648求圖中A點(diǎn)到其余各頂點(diǎn)的最短路徑的權(quán)（要求列表）。B7C12A253D6E1F解：用用標(biāo)號(hào)法解題過(guò)程如下：BCDEF01411*836283*437104*47*959*17934求下面所示帶權(quán)圖中頂點(diǎn)A到其余各頂點(diǎn)的最短路徑的權(quán)（要求列表）。解：用用標(biāo)號(hào)法解題過(guò)程如下：BCDEF0812131*7223732*33*73453*55*3153214258142589263ABCDEF解：用用標(biāo)號(hào)法解題過(guò)程如下BCDEF042132*101123*81138*1014410*13513*3281013設(shè)，定義A上的二元運(yùn)算*如下：對(duì)，（表示xy除以5的余數(shù)），試求*的運(yùn)算表。解：運(yùn)算表如下：設(shè)，定義A上的二元運(yùn)算*如下：對(duì)，的最大公約數(shù)，試給出*的運(yùn)算表。解：運(yùn)算表如下：設(shè)，定義A上的二元運(yùn)算*如下：對(duì)，的最小公倍數(shù)，試給出*的運(yùn)算表。解：運(yùn)算表如下：設(shè)，試給出A上運(yùn)算的運(yùn)算表。解：運(yùn)算表如下設(shè)個(gè)體域?yàn)閧1，2}，，，，求公式的真值。解：．設(shè)個(gè)體域?yàn)閧1，2}，，，，求公式的真值．解：．設(shè)無(wú)向圖G有4個(gè)頂點(diǎn)，度數(shù)分別為1，2，2，3，問(wèn)G中有幾條邊？依據(jù)是什么？并畫出一個(gè)符合上述條件的圖。解：圖G有4條邊，依據(jù)是握手定理：1+2+2+3=2m，m=4．下面的圖就符合上述條件：設(shè)無(wú)向圖G有5個(gè)頂點(diǎn)，度數(shù)分別為1，1，2，2，4，問(wèn)G中有幾條邊？依據(jù)是什么？并畫出一個(gè)符合上述條件的圖。解：圖G有5條邊，依據(jù)是握手定理：1+1+2+2+4=2m，m=5.下面的圖就符合上述條件：題公式（PP）Q的真值表，并判斷其類型。解：真值表為：PQPPP（PP）Q00101011001000111000因此公式（PP）Q為可滿足式．現(xiàn)有三個(gè)課外小組：物理組、化學(xué)組、生物組，今有張、王、李、趙、陳5名同學(xué)，已知張、王為物理組成員，張、李、趙為化學(xué)組成員，李、陳為生物組成員，問(wèn)在這種情況下能否選出3名不兼職的組長(zhǎng)？若能選出，試給出一種方案。解：可以選出3名不兼職的組長(zhǎng)．物理組化學(xué)組生物組張王李趙陳一種方案是：張任物理組的組長(zhǎng)，李任化學(xué)組的組長(zhǎng)，陳任生物組的組長(zhǎng)．（注：本題答案不唯一，還可以給出其它的方案．）一棵無(wú)向樹有1個(gè)2度的頂點(diǎn)，3個(gè)3度的頂點(diǎn)，其余點(diǎn)都是樹葉，求該樹的葉子數(shù)．并畫出一棵符合上述條件的樹。解：設(shè)該樹的葉子數(shù)為x個(gè)，則2+9+x=2（4+x-1）解得x=5，即有5個(gè)樹葉子．下面的這棵樹就符合上述條件：一棵無(wú)向樹有4個(gè)樹葉，1個(gè)2度的頂點(diǎn)，其余的點(diǎn)度數(shù)都為3，該樹共有幾個(gè)點(diǎn)？畫出一棵符合上述條件的樹。解：設(shè)該樹中3度的點(diǎn)有x個(gè)，則4+2+3x=2（4+1+x-1）解得x=2，從而該樹共有7個(gè)點(diǎn)．下面的這棵樹就符合上述條件：已知公式，其中，，且個(gè)體域?yàn)閧1，2}，求該式的真值。解：．已知公式，其中，，且個(gè)體域?yàn)閧3，4}，求該式的真值。解：．有150人至少喜歡游泳或跑步中的一種．若85人喜歡游泳，60人同時(shí)喜歡游泳和跑步，問(wèn)有多少人喜歡跑步？解：由下列文氏圖可知25256065喜歡跑步而不喜歡游泳的人數(shù)為：150-85=65因此喜歡跑步的人數(shù)為：65＋60=125有四個(gè)信息c，ac，bd，abd，現(xiàn)想分別用組成每個(gè)信息的字母中的一個(gè)來(lái)表示該信息，這是否可能？如果可能，應(yīng)如何表示？解：可以做到：cacbdabddcbadcba一種方案是：c表示c，a表示ac，b表示bd，d表示abd．有張、王、李、趙四位教師，要分配他們教數(shù)學(xué)、物理、化學(xué)、英語(yǔ)等四門課程．張熟悉物理和英語(yǔ)，王熟悉數(shù)學(xué)和化學(xué)，李熟悉數(shù)學(xué)、物理和英語(yǔ)，趙只熟悉英語(yǔ)。（1）畫出關(guān)于教師熟悉課程的二部圖；（2）如何分配，才能使每位教師都教一門自己熟悉的課程？解：（1）畫出二部圖張王李趙數(shù)學(xué)物理化學(xué)英語(yǔ)（2）張：物理；王：化學(xué)；李：數(shù)學(xué)；趙：英語(yǔ)．四、證明構(gòu)造下列推理的證明．前提：，結(jié)論：。證明：（1）前提引入（2）前提引入（3）（1），（2）析取三段論（4）前提引入（5）（3），（4）拒取式（6）（5）置換（7）前提引入（8）（6），（7）析取三段論設(shè)Z表示整數(shù)集,在Z上定義二元運(yùn)算:，證明:Z關(guān)于運(yùn)算構(gòu)成群。證：根據(jù)群的定義，需證明運(yùn)算滿足結(jié)合律、有么元和每個(gè)元素都有逆元.對(duì),有(a*b)*c=(a*b)+c+3=(a+b+3)+c+3=a+b+c+6，而a*(b*c)=a+(b*c)+3=a+(b+c+3)+3=a+b+c+6，故(a*b)*c=a*(b*c),結(jié)合律成立.-3是么元,事實(shí)上：,a*(-3)=a+(-3)+3=a,(-3)*a=(-3)+a+3=a,對(duì)，a*(-6-a)=a+(-6-a)+3=-3,(-6-a)*a=(-6-a)+a+3=-3,可知-6-a是a的逆元.因此，Z關(guān)于運(yùn)算構(gòu)成群.構(gòu)造下列推理的證明：前提：P（QR），SP，Q，S結(jié)論：R證明：（1）SP前提引入（2）S前提引入（3）P（1），（2）析取三段論（4）P（QR）前提引入（5）QR（3），（4）假言推理（6）Q前提引入（7）R（5），（6）假言推理在整數(shù)集Z上定義:a*b=a+b-9,,證明:<Z,*>是一個(gè)群。證顯然*是二元運(yùn)算,根據(jù)群的定義，需證明運(yùn)算滿足結(jié)合律、有幺元和每個(gè)元素都有逆元。對(duì),有(a*b)*c=(a*b)+c-9=(a+b-5)+c-9=a+b+c-18而a*(b*c)=a+(b*c)-9=a+