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

離散數(shù)學(xué)習(xí)題整合離散數(shù)學(xué)習(xí)題整合離散數(shù)學(xué)習(xí)題整合資料僅供參考文件編號(hào)：2022年4月離散數(shù)學(xué)習(xí)題整合版本號(hào)：A修改號(hào)：1頁(yè)次：1.0審核：批準(zhǔn):發(fā)布日期：CH01復(fù)習(xí)題§1.命題判斷（每空1分，共4分）~P32-A小李和小王是同班同學(xué)B小豬不是鮮花C3-2n<0D若2+2=4，則太陽(yáng)從西方升起。上述語(yǔ)句中，是簡(jiǎn)單命題，不是命題，是符合命題且真值為假，是符合命題且真值為真。（參考答案：ACDB）2.命題符號(hào)化（每空2分，共4分）習(xí)題(7)(3)P32- p：天下大雨，q：他乘公共汽車(chē)去上班，命題“除非天下大雨，否則他不乘公共汽車(chē)去上班”可符號(hào)化為。（參考答案：q→p必要條件為后件） r：天很冷，s：老李來(lái)了，命題“雖然天很冷，老李還是來(lái)了”可符號(hào)化為。（參考答案r∧s）3.五個(gè)真值表（每空2分，共4分）習(xí)題(2)(4)P32- 設(shè)p的真值為0，r的真值為1，q、s都是命題，則命題公式（的真值為，命題公式的真值為。（參考答案：0,1）4.用符號(hào)p、q填空。（每空1分，共4分）基本概念設(shè)p：x>0（其中x是整數(shù)），q：太陽(yáng)從西方升起，則是命題，是命題變項(xiàng)，是命題常項(xiàng)，不是命題。（參考答案：q，p，q，p）5.命題符號(hào)化，相容或與排斥或設(shè)r：現(xiàn)在小李在圖書(shū)館，s：現(xiàn)在小李在學(xué)生宿舍，則“現(xiàn)在小李在圖書(shū)館或?qū)W生宿舍”可符號(hào)化為。（參考答案：B）Ar∨sB(r∧?s)∨(?r∧s)Cr∧sD(r∧?s)或(?r∧s)§命題公式及分類(lèi)已知：A是含三個(gè)命題變項(xiàng)的命題公式，且A(001)=0，A(100)=1，則A是。（D）A矛盾是B可滿足式C重言式D非重言式的可滿足式§等值演算用等值演算法證明等值式：(p∧q)→rp→(q→r).(演算的每一步都要寫(xiě)依據(jù))§范式6.（每項(xiàng)1分，共4分）已知命題公式A(p,q)的真值表PqA(p,q)000011100111求A的永主析取范式、主合取范式、成真賦值和成假賦值。（參考答案：m1∨m3，M0∧M2，01、11，00、10）7.（2分）命題公式B(p,q,r)=(?p∧r∧?q)的主析取范式是。（參考答案：C）Am2BM6Cm1DM5E命題公式B(p,q,r)=(?p∨?q∨r)的主析取范式是。（參考答案：A）Am0∨m1∨m2∨m3∨m4∨m5∨m7BM6Cm1DM1§全功能集（2分）不是聯(lián)結(jié)詞全功能集。（參考答案：D）A{↑}B{?,→}C{?,∨}D{∧,∨}是聯(lián)結(jié)詞全功能集。（參考答案：A）A{↓,}B{∨,∧}C{∨}D{∧}§組合電路（習(xí)題）有一盞燈由三個(gè)開(kāi)關(guān)控制，要求按任何一個(gè)開(kāi)關(guān)都能使燈由黒變亮或由亮變黑，試設(shè)計(jì)這樣的一個(gè)電路。（解題基本步驟：狀態(tài)設(shè)置、設(shè)計(jì)真值表、寫(xiě)主析取范式、化簡(jiǎn)、繪制電路.答案不唯一）§推理理論(習(xí)題(1))用直接證明法或歸謬法證明下面的推理.前提：?(p∧?q)，?q∨r，?r.結(jié)論：?p.證明：…(習(xí)題(3))用直附加前提法證明下面的推理.前提：P→q.結(jié)論：P→(p∧q).證明：…（例題）公安人員審查一件盜竊案，已知事實(shí)如下：李或王盜竊了錄音機(jī)；若李盜竊了錄音機(jī)，則作案時(shí)間不能發(fā)生在午夜前；若王的證詞正確，則午夜時(shí)屋里燈光未滅；若王的證詞不正確，則作案時(shí)間發(fā)生在午夜前；午夜時(shí)屋里燈光滅了.試問(wèn)盜竊錄音機(jī)的是李還是王，并證明你的結(jié)論。參考答案：王盜竊了錄音機(jī).設(shè)p：李盜竊了錄音機(jī)；q：王盜竊了錄音機(jī)；r：作案時(shí)間發(fā)生在午夜前；s：王的證詞正確；t：午夜時(shí)屋里燈光滅了.前提：p∨q，p→?r，s→t，?s→r，?t.結(jié)論：q.證明：…CH02復(fù)習(xí)題§例（3）1將命題“若李一的成績(jī)比王二高，王二的成績(jī)比吳三高，那么李一的成績(jī)比吳三高”用0元謂詞符號(hào)化。解：設(shè)H(x,y)：x的成績(jī)比y高，a：李一，b：王二，c:吳三則命題可符號(hào)化為H(a,b)∧H(b,c)H(a,c)§例（4）2在一階邏輯中將命題“素?cái)?shù)不全是奇數(shù)”符號(hào)化。解：設(shè)F(x)：x是素?cái)?shù)，G(x)：x是奇數(shù)則命題可符號(hào)化為x(F(x)∧G(x)) 或x(F(x)G(x))§3（每空1分，共4分）給定解釋I，對(duì)一階邏輯合式公式中每個(gè)出現(xiàn)的指定中的一個(gè)元素，稱(chēng)作在下的賦值。（自由個(gè)體變項(xiàng)個(gè)體域解釋I）§4下面的一階邏輯合式公式不是閉式。(D有自由出現(xiàn))Ax(F(x)G(X))By(F(x,y)G(x))CxF(x)yG(y)DxF(x,y)yG(y)§5下面各種敘述，不正確。(C例（5）)也可改造成正誤判斷題A在給定的解釋和賦值下，任何一階邏輯合式公式都是命題√P45-B閉公式的真值與賦值無(wú)關(guān)，只需要給定解釋C非閉式的公式的真值只與賦值有關(guān)D可滿足式可能是邏輯有效式§6在四個(gè)合式公式xy(F(x)(G(y)H(x,y)))、x(F(x)y(G(y)H(x,y)))、x(F(x)G(x))、x(F(x)G(x))中共有個(gè)是前束范式。（參考答案：A）A2B3C1D0（*參考答案：B）7已知F(x)=x(M(x)F(x))，G1(x)=x(M(x)F(x))，G2(x)=x(M(x)F(x))，G3(x)=x(M(x)F(x))，則在G1(x)、G2(x)和G3(x)中，有個(gè)是F(x)的前束范式。A0B3C2D1例（3）8求公式xF(x)G(x)的前束范式。解：xF(x)G(x)xF(x)xG(x)(蘊(yùn)涵等值式)xF(x)xG(x)(量詞否定等值式)xF(x)G(x))(量詞分配等值式)解法2：xF(x)G(x)xF(x)yG(y)(換名規(guī)則)x(F(x)yG(y))(量詞擴(kuò)(2)=3\*GB3③)xyF(x)G(y))(量詞擴(kuò)(2)=4\*GB3④)解法3：xF(x,)G(x)F(y)G(x))§例設(shè)個(gè)體域D={a,b}，消去公式x(F(x)∧yG(y))中的量詞。離散CH03復(fù)習(xí)題判斷（1分/每小題）若集合A={1，{1,2}，3}，則2A（×）若集合B={2，{a，b}}，則{a，b}B（×）單選（2分/每小題）下面的集合算式不正確。（∵A=∴C）AA-(B∪C)=A-B)∪(A-C)BA-B=A∩～BCA=ADABA-B=已知B={{a，b}，c}，則|P(A)|=.（∵P(A)={，{c}，{{a，b}}，B}，∴A）A|{，{c}，{{a，b}}，B}|B2C3D8填空（2分/每小題）若|P(A)|=128，則|A|=.(∵|P(A)|=27,∴7)設(shè)A={1,3,3}，則|A|=.(∵A={1,3}，∴2)計(jì)算（8分/每小題）某班有48個(gè)學(xué)生，第一次作業(yè)優(yōu)秀7人，第二次作業(yè)優(yōu)秀6人，兩次作業(yè)都沒(méi)得優(yōu)秀的41人，求兩次作業(yè)都得優(yōu)秀的人數(shù)。（求解過(guò)程參見(jiàn)[例]，參考答案：6）解：用A、B分別表示第一次和第二次作業(yè)優(yōu)秀的人數(shù)集合，E為某班全體學(xué)生的集合則：|E|=48，|A|=7，|B|=6，|～A∩～B|=41 |～A∩～B|=|E|-(|A|+|B|)+|A∩B| |A∩B|=41-48+(7+6) =6已知A={{a，b}，c，d}，B={c，d}，計(jì)算A∩B、A∪B、A-B、AB。（(1)）畫(huà)圖畫(huà)（A∩～B）∪（C-B）的文氏圖。（（3））AABC證明：（A∩～B）∪（C-B）=（A∪C）-B證：左式=（A∩～B）∪（C∩～B）（/差交運(yùn)算轉(zhuǎn)換）=(A∪C)∩～B（分配律）=(A∪C)-B（/差交運(yùn)算轉(zhuǎn)換）離散CH04復(fù)習(xí)題判斷（1分/每小題）§1.A是任意集合，則A×A的任何子集稱(chēng)作A上的二元關(guān)系。（√）2.若集合B={2，{a，b}}，則{a，b}B（×）單選（2分/每小題）§3.A是任意集合，{<x，x>|xA}稱(chēng)作關(guān)系。（∵恒等關(guān)系蘊(yùn)含其是A上的∴B）A空B恒等C全域DA上的4.設(shè)A={a，b，c}，R={<a，a>，<a，b>，<b，b>，<b，c>，<c，a>，<c，b>}，則是R的關(guān)系矩陣。（參見(jiàn)P80-，參考答案：（A）ABCD設(shè)S={1,2,3,4}，R是S上的關(guān)系，其關(guān)系矩陣是，R的關(guān)系圖中有個(gè)環(huán)。AA1B3C6D7填空（2分/每小題）§6.A、B是任意兩個(gè)集合，若|A|=m，|B|=n，則|P(A×B)|=。（）7.設(shè)A是任意集合，|A|=n，則A上有個(gè)不同的二元關(guān)系。(,|A×A|=n2)§8.R是集合A上的等價(jià)關(guān)系，如果有序?qū)?lt;a,b>R，則記作。（a～b）9.若R是集合A上的偏序關(guān)系，則可將此偏序關(guān)系簡(jiǎn)記作；有序?qū)?lt;x,y>，可記作。（ab）計(jì)算（8分/每小題）§10.已知關(guān)系R={<2,{2}>，<{2},{2,{2}}>}，求RR、R{2}、R[{2}].(同例理解定義解：RR={<2，{2,{2}}>} R{2}={<2,{2}>}限制 R[{2}]=ran（R{2}）=ran{<2,{2}>}={{2}}像集11.已知A={a，b，c，d}，R1和R2是A上的關(guān)系，且R1={<a，a>，<a，b>，<b，d>}，R2={<a，d>，<b，c>，<b，d>，<c，b>}。求R2R1。解：∵<a，a>R1<a，d>R2，∴<a，d>R2R1 <a，b>R1<b，c>R2，∴<a，c>R2R1 <a，b>R1<b，d>R2，∴<a，d>R2R1故R2R1={<a，d>，<a，c>}證明題綜合：§1等值公式和等值運(yùn)算+§3集合運(yùn)算+§4關(guān)系性質(zhì)的定義12.設(shè)集合A上的兩個(gè)關(guān)系R1和R2都是對(duì)稱(chēng)的，證明R1∩R2仍是對(duì)稱(chēng)的。證明：參見(jiàn)主教材P87-13.試證任何集合A的冪集P(A)上的包含關(guān)系R是偏序關(guān)系證明：xP(A)，都有xx，，<x，x>R∴R是自反的<x,y>R∧x≠yxy∧x≠yxy（集合包含關(guān)系的定義）yx<y,x>R(包含關(guān)系的定義)∴R是反對(duì)稱(chēng)的x、t、yP(A),若<x,t>R∧<t,y>R則xt∧ty(關(guān)系R的定義)xy（集合運(yùn)算律）<x,y>R（關(guān)系R的定義）∴R是傳遞的14.已知R的關(guān)系圖如下圖所示，畫(huà)R的自反閉包r（R）、對(duì)稱(chēng)閉包s（R）、傳遞閉包t(R).11235415.畫(huà)<{1,2,3,4,5,6,7,8}，R整除>的哈斯圖。16.判斷函數(shù)f：N→N，是否是滿射、單射、雙射，為什么?

01012...0123..1無(wú)原像，故f非滿射，也非雙射。但f是單射。離散CH05選擇一個(gè)最合適的答案

e0e1e2v3v4v5v6

e0e1e2v3v4v5v6e3v0v1v2e4e5e6A簡(jiǎn)單通路B初級(jí)通路C通路D復(fù)雜通路v0v1v2v3v4v5v62.下面有向圖中的頂點(diǎn)序列Γ：V0V1Vv0v1v2v3v4v5v6A路徑B初級(jí)通路C簡(jiǎn)單通路D復(fù)雜通路3.能構(gòu)成圖的度數(shù)序列。（C）A（3，3，2，1）B（2，3，2）C（1）D（3，3，3）填空：4.設(shè)G（V,E）是n階有向簡(jiǎn)單圖，若u，v∈V，都有，則稱(chēng)G是n階有向完全圖。（<u，v>∈E∧<v，u>∈E）5.G（V,E）是n階有向完全圖，通常記為。(Kn）v1v2v3e4v1v2v3e4e1e2e3v2e4v1e1v2v0v1v3v2e0e1e3v0v1v3v2e0e1e3e28.設(shè)G是有向圖或無(wú)向圖，稱(chēng)p（G）是圖G的。（連通分支個(gè)數(shù)）簡(jiǎn)答（6分/每小題）§9.下面三個(gè)無(wú)向圖，它們之間哪些同構(gòu)，哪些不同構(gòu)。若不同構(gòu)，為什么？若同構(gòu)，請(qǐng)建立頂點(diǎn)之間的雙射。圖G1圖G2圖G3答：圖G1與圖G2不同構(gòu)，因?yàn)閳DG1與G2存在度不相同的頂點(diǎn)?！?分同理G2G3.…2分G1G3.…2分因?yàn)?cb143da建立頂點(diǎn)之間的如下對(duì)應(yīng)關(guān)系f：1→a，2→b，3→c，4→d，f是雙射，并且兩圖的邊也一一對(duì)應(yīng)。10.無(wú)向圖的（點(diǎn)）著色：P132-例11.圖強(qiáng)連通，圖單向連通，圖弱連通，圖非連通。D2D2D3D4D1參考答案：D2、D3、D4、D1）12.應(yīng)用題P133-[例]離散CH06選擇一個(gè)最合適的答案1.下面三種說(shuō)法，其中不正確的有個(gè)。(C還有必要條件)=1\*GB3①Hall定理是二部圖G(V1,V2,E)存在完備匹配的充要條件=2\*GB3②無(wú)論是有向圖還是無(wú)向圖，都有判斷其是否存在歐拉通路和歐拉回路的充要條件=3\*GB3③目前只有判斷哈密頓圖的充分條件A0B3C1D22.下面四種說(shuō)法，其中正確的有個(gè)。（A）=1\*GB3①存在既是歐拉圖又是哈密頓圖的無(wú)向圖=2\*GB3②存在是歐拉圖不是哈密頓圖的無(wú)向圖=3\*GB3③存在不是歐拉圖卻是哈密頓圖的無(wú)向圖=4\*GB3④存在既不是歐拉圖又不是哈密頓圖的無(wú)向圖A4B3C2D1填空§3.用G(V1,V2,E)表示二部圖G，|V1|=n，|V2|=m，記號(hào)表示圖G為。（完全二部圖）§4.若圖G畫(huà)在平面上使得除頂點(diǎn)處外沒(méi)有出現(xiàn)，則稱(chēng)G為平面圖。（邊交叉）5.下面的平面圖共有個(gè)面，其中無(wú)限面R0的次數(shù)deg（R0）=。（3，8）平面圖6-16.非連通的平面圖6-2的外部面是R0，deg（R0）=。（9）RR1R0R2非連通平面圖6-2應(yīng)用題：7.P151-習(xí)題（二部圖的應(yīng)用）8.P151-習(xí)題（哈密頓圖的應(yīng)用）9.P152-習(xí)題（歐拉通路或歐拉回路的應(yīng)用）10.*P152-習(xí)題（平面圖在作色中的應(yīng)用）離散CH07復(fù)習(xí)題§1.P165-↓12設(shè)n階連通無(wú)向圖G(V,E)有m條邊，G的生成樹(shù)有條邊，余樹(shù)有條邊。（n-1，m-n+1）2.P167-例（2）畫(huà)出4個(gè)頂點(diǎn)非同構(gòu)無(wú)向樹(shù)。（2種）3.P173-習(xí)題（3）畫(huà)出4個(gè)頂點(diǎn)非同構(gòu)的根樹(shù)（4種）4.下面三條敘述中有條正確。（B）①一階零圖是一棵樹(shù)②只有一片樹(shù)葉的樹(shù)在同構(gòu)意義下只