離散數(shù)學2023秋綜合練習題

離散數(shù)學綜合練習題一、判斷下列命題是否正確．如果正確，在題后括號內(nèi)填“\/”；否則，填“”（1）空集是任何集合的真子集．（）（2）是空集．（）（3）（）（4）如果，則或．（）（5）設(shè)集合，，則（）（6）設(shè)集合，則是到的關(guān)系．（）（7）關(guān)系的復合運算滿足交換律．（）（8）設(shè)為集合上的等價關(guān)系,則也是集合上的等價關(guān)系()（9）設(shè)是集合上的等價關(guān)系,則當時，()（10）設(shè)為集合上的等價關(guān)系,則()（11）集合A上的任一運算對A是封閉的．（）（12）設(shè)A是集合，，，則是可結(jié)合的．（）（13）設(shè)是群．如果對于任意，有則是阿貝爾群．（）（14）設(shè)a是群的元素，記則是的子群．（）（15）<{0，1，2，3，4}，max，min>是格．（）（16）設(shè)a，b是格的任意兩個元素，則．（）（17）設(shè)是布爾代數(shù)，則是格．（）（18）設(shè)集合，則是格．（）（19）設(shè)是布爾代數(shù)，則對任意，有．（）（20）設(shè)是布爾代數(shù)，則對任意，都有，使得．（）（21）n階完全圖的任意兩個不同結(jié)點的距離都為1.（）（22）在有向圖中，結(jié)點到結(jié)點的有向短程即為到的有向短程．（）（23）強連通有向圖一定是單向連通的．（）（24）不論無向圖或有向圖，初級回路一定是簡單回路．（）（25）設(shè)圖G是連通的，則任意指定G的各邊方向后所得的有向圖是弱連通的．（）（26）設(shè)A是某個無向圖的鄰接矩陣，則(是的轉(zhuǎn)置矩陣)．（）（27）設(shè)有向圖D的可達矩陣為則是單向連通的．（）（28）有生成樹的無向圖是連通的．（）（29）由r棵樹組成的森林的結(jié)點數(shù)n與邊數(shù)m有下列關(guān)系：m=n-r.（）（30）如果有向圖D僅有一個結(jié)點的入度為0，其余結(jié)點的入度都為1，則D是有向樹．（）（31）“如果8＋7＞2，則三角形有四條邊”是命題．（）（32）設(shè)都是命題公式，則也是命題公式．（）（33）命題公式的真值分別為0，1，則的真值為0（以上是在對所包含的命題變元的某個賦值下）．（）（34）邏輯結(jié)論是正確結(jié)論．（）（35）設(shè)都是謂詞公式，則也是謂詞公式．（）（36）設(shè)都是謂詞公式，，則是永真式．（）（37）設(shè)都是命題公式，則也是命題公式．（）（38）命題公式的真值分別為0，1，則的真值為0（以上是在對所包含的命題變元的某個賦值下）．（）（39）設(shè)是個體域中某個元素，則其中都是謂詞．（）（40）（）二、填空題（1）設(shè)有個元素，則集合的冪集中有個元素。（2）設(shè)，則=.（3）設(shè)集合中元素的個數(shù)分別為，，且，則集合中元素的個數(shù).（4）設(shè)集合，，則中元素的個數(shù)為.(5)設(shè)為集合上的二元關(guān)系,則.(6)集合上的二元關(guān)系為傳遞的充分必要條件是．(7)設(shè)：稱為母親，：稱為父親，則：,(8)設(shè)為自然數(shù)的集合，“”為自然數(shù)的小于等于關(guān)系，的子集，則的下確界為，下確界為,(9)設(shè)10人集合{趙茵，錢小濱，孫麗春，趙萍，錢浩，李靖華，李秀娟，錢鈺，李惠芝，李莉}上的同姓關(guān)系為，則等價類[趙]=，[錢]=，(10)設(shè),是上的包含于關(guān)系，,則有=.(11)設(shè)為非空有限集，代數(shù)系統(tǒng)中，對運算的單位元為，零元為.(12)循環(huán)群的生成元為.(13)循環(huán)群的所有子群為.(14)代數(shù)系統(tǒng)中（其中為整數(shù)集合，+為普通加法），對任意的，其.(15)在整數(shù)集合上定義運算為，則的單位元為.(16)設(shè),在代數(shù)系統(tǒng)中，的單位元為，可逆元為.(17)設(shè)是群，則對于任意的，方程和有唯一解。(18)設(shè)是群，對任意，如果，則.(19)設(shè)是群，為單位元，若元素滿足，則.(20)在整數(shù)集合上定義運算為，則的單位元為.(21)設(shè)為樹，中有4度，3度，2度分支點各1個，問中有片樹葉。(22)為了從（n，m）連通無向圖得到一棵生成樹，必須刪除G的條邊．(23)設(shè)樹T中有7片樹葉，3個3度結(jié)點，其余都是4度結(jié)點，問T中有個4度結(jié)點。(24)無環(huán)有向圖的關(guān)聯(lián)矩陣的所有元素之和為．(25)n階完全圖的任意兩個不同結(jié)點的距離都為．(26)圖為階無向完全圖，則共有條邊。(27)設(shè)為圖，則圖中結(jié)點度數(shù)的總和為。(28)設(shè)圖有6結(jié)點，若各結(jié)點的度數(shù)分別為：1，4，4，3，5，5，則共有條邊。(29)無向圖是由棵樹組成的森林，至少要添加條邊才能使成為一棵樹。(30)在任何圖中，奇數(shù)結(jié)點必為個。(31)設(shè)天氣很冷，老王還是來了，則命題“雖然天氣很冷,但老王還是來了”符號化為.(32)設(shè)天下雨，我騎自行車上班，則命題“如果天不下雨,我就騎自行車上班”符號化為.(33)設(shè)經(jīng)一事,長一智，則命題“不經(jīng)一事,不長一智”符號化為.(34)設(shè)的真值為0，的真值為1，則命題公式的真值為.(35)設(shè)的真值為0，的真值為1，則命題公式的真值為.(36)由個命題變項可以組成個不等值的命題公式。(37)設(shè)個體域，公式在上消去量詞后應為.(38)設(shè)是自然數(shù)，是奇數(shù)，是偶數(shù)，則命題“任何自然數(shù)不是奇數(shù)就是偶數(shù)”符號化為.(39)設(shè)是素數(shù)，是偶數(shù)，，則命題“2既是偶數(shù)又是素數(shù)”符號化為.(40)設(shè)是金子，是發(fā)光的，則命題“金子是發(fā)光的,但發(fā)光的不一定是金子”符號化為.三、選擇題（每題后面有四個選項，四個選項中只有一個是正確的，請將正確的所對應的字母填在括號內(nèi)）（1）設(shè)為實數(shù)集合，下列集合中哪一個不是空集（）A.B．C.D.（2）設(shè)為集合，若，則一定有（）A.B．C.D.（3）下列各式中不正確的是（）A.B．C.D.（4）設(shè)，則下列各式中錯誤的是（）A.B．C.D.（5）設(shè)，，，則為（）A.B．C.D.（6）設(shè)，，則的恒等關(guān)系為（）A.B．C.D.（7）集合上的二元關(guān)系，則的性質(zhì)為（）A.自反的；B．對稱的；C.反對稱的；D.反自反的.（8）設(shè)上的二元關(guān)系如下，則具有傳遞性的為（）A.B．C.D.（9）設(shè)為集合上的等價關(guān)系，對任意，其等價類為（）A.空集；B．非空集；C.是否為空集不能確定；D..（10）映射的復合運算滿足（）A.交換律B．結(jié)合律C.冪等律D.分配律（11）在整數(shù)集上，下列哪種運算是可結(jié)合的（）A.B．C.D.（12）設(shè)集合，下面定義的哪種運算關(guān)于集合不是封閉的（）A.B．C.，即的最大公約數(shù)D.，即的最小公倍數(shù)（13）下列哪個集關(guān)于減法運算是封閉的（）A.（自然數(shù)集）；B．；C.；D..（14）設(shè)是有理數(shù)集，在定義運算為，則的單位元為（）A.；B．；C.1；D.0（15）下列代數(shù)系統(tǒng)中，哪一個不構(gòu)成群（）A.是模11乘法；B.是模3加法；C.普通加法；D.普通乘法.（16）循環(huán)群的生成元為1和2，它們的周期為（）A.5B．6C.3D.9（17）循環(huán)群的所有子群為（）A.B．C.和D.（18）循環(huán)群的所有生成元為（）A.1，0B．-1，2C.1，2D.1，-1（19）有限布爾代數(shù)的元素個數(shù)必定等于（）A.；B．；C.；D..（20）在下面偏序集的哈斯圖中，哪一個是格（）ABCD（21）僅由孤立點組成的圖稱為（）A.零圖；B．平凡圖；C.完全圖；D.多重圖.（22）僅由一個孤立點組成的圖稱為（）A.零圖；B．平凡圖；C.多重圖；D.子圖.（23）在任何圖中必有偶數(shù)個（）A.度數(shù)為偶數(shù)的結(jié)點；B．度數(shù)為奇數(shù)的結(jié)點；C.入度為奇數(shù)的結(jié)點；D.出度為奇數(shù)的結(jié)點.（24）設(shè)為有個結(jié)點的無向完全圖，則的邊數(shù)為（）A.B．C.D.（25）圖和的結(jié)點和邊分別存在一一對應關(guān)系是（同構(gòu)）的（）A.充分條件；B．必要條件；C.充分必要條件；D.既不充分也不必要條件.（26）給定下列序列，哪一個可構(gòu)成無向簡單圖的結(jié)點度數(shù)序列（）A.B．C.D.（27）在有個結(jié)點的連通圖中，其邊數(shù)（）A.最多條；B．至少條；C.最多條；D.至少條.（28）是無向圖的關(guān)聯(lián)矩陣，是中的孤立點，則（）A.對應的一行元素全為0；B．對應的一行元素全為1；C.對應的一列元素全為0；D.對應的一列元素全為1.（29）任何無向圖中結(jié)點間的連通關(guān)系是（）A.偏序關(guān)系；B．等價關(guān)系；C.既是偏序關(guān)系又是等價關(guān)系；D.既不是偏序關(guān)系也不是等價關(guān)系.（30）有向圖，其中，，則有向圖是（）A.強連通圖；B．單向連通圖；C.弱連通圖；D.不連通圖.（31）下面哪個聯(lián)結(jié)詞不可交換（）A.；B．；C.；D..（32）命題公式是（）A.矛盾式；B．非永真式的可滿足式；C.重言式；D.等價式.（33）下列哪一組命題公式是等值的（）A.，；B．，；C.，；D.，（34）下面哪一個命題是假命題（）A.如果2是偶數(shù)，那么一個公式的析取范式唯一；B．如果2是偶數(shù)，那么一個公式的析取范式不唯一；C.如果2是奇數(shù)，那么一個公式的析取范式唯一；D.如果2是奇數(shù)，那么一個公式的析取范式不唯一.（35）設(shè)論域為整數(shù)集，下列公式中哪個值為真（）A.；B.；C.；D..（36）設(shè)謂詞是奇數(shù)，是偶數(shù)，謂詞公式在哪個論域中是可滿足的（）A.自然數(shù)；B．整數(shù)；C.實數(shù)；D.以上均不成立.（37）命題“沒有不犯錯誤的人”符號化為(設(shè)是人,犯錯誤)（）A.；B.；C.；D..（38）設(shè)個體域，公式在上消去量詞后應為（）A.；B.；C.；D..（39）在謂詞演算中，下列各式中，哪一個是正確的（）A.；B.；C.；D..（40）“學習有如逆水行舟，不進則退”。設(shè)學習如逆水行舟，學習進步，學習退步。則命題符號化為（）A.；B．；C.；D..四、解答題1.設(shè)上的關(guān)系試（1）寫出的關(guān)系矩陣；（2）驗證是上的等價關(guān)系；（3）求出的各元素的等價類。2.設(shè)，上的整除關(guān)系，畫出的哈斯圖。3.設(shè)集合,是上的整除關(guān)系,畫出的哈斯圖；4.設(shè)集合,是上的整除關(guān)系，試求：集合的最大元，最小元子集和的上界、下界、上確界和下確界。5.在下面的無向圖中，回答下列問題（1）寫出之間的所有初級通路；（2）寫出之間的所有短程，并求；（3）判斷無向圖是否為歐拉圖并說明理由。6.下列各圖是否為歐拉圖，是否為哈密爾頓圖？為什么？(1)(2)7.下列圖形中最少需添加幾條邊才能成為歐拉圖．a(chǎn)abebdcdc（1）（2）8.有向圖如下圖所示(1)求的鄰接矩陣；(2)求中長度為4的通路數(shù)和回路數(shù)，并找出中從到長度為4的所有通路。(3)是哪類連通圖？9.設(shè)有向圖，，其鄰接矩陣為畫出有向圖；中長度為4的通路有多少條？其中有多少條為回路？是那類連通圖？10.設(shè)連通圖如下圖所示，求它的一棵生成樹．a(chǎn)bcef答案不唯一。五、構(gòu)造下列推理的證明1.證明2.證明3.證明4.證明5.構(gòu)造下列推理的證明：每個學術(shù)委員會的成員都是專家并且是大學生，有些成員是青年人，所以有些成員是青年專家。6.“有些病人相信所有的醫(yī)生，病人都不相信騙子，所以醫(yī)生都不是騙子?！痹谝浑A邏輯中證明以上推理是正確的。六、證明題1.設(shè)為集合上的等價關(guān)系,試證也是集合上的等價關(guān)系。2.設(shè)為無向連通圖中任意兩個頂點，證明：若，則存在頂點，使得3.證明下面四個矩陣關(guān)于矩陣乘法運算構(gòu)成群。，，，4.設(shè)是一個群，試證是交換群當且僅當對任意的,有.5.設(shè)是群的元素，記，證明是的子群．6.設(shè)是一個群，取定，定義，證明是一個群。離散數(shù)學綜合練習題答案判斷下列命題是否正確（1）錯誤；（2）錯誤；（3）正確；（4）錯誤；（5）錯誤；（6）正確；（7）錯誤；（8）正確；（9）正確；（10）錯誤；（11）正確；（12）正確；（13）正確；（14）正確；（15）正確；（16）正確；（17）正確；（18）正確；（19）正確；（20）正確；（21）正確；（22）錯誤；（23）正確；（24）正確；（25）正確；（26）正確；（27）正確；（28）正確；（29）正確；（30）錯誤；（31）正確；（32）錯誤；（33）錯誤；（34）錯誤；（35）錯誤；（36）正確；（37）正確；（38）正確；（39）錯誤；（40）錯誤.填空題（1）；（2）；（3）3；（4）40；(5)(6)；(7)稱為外祖父；(8)5，9；(9)[趙]={趙茵，趙萍}，[錢]={錢小濱，錢浩，錢鈺}，[孫]={孫麗春}，[李]={李靖華，李秀娟，李惠芝，李莉}.(10)(11)；(12)1和2；(13)，，，；(14)；(15)–2；(16)1，1；(17)，；(18)；(19)；(20)0；(21)5；(22)m-n＋1；(23)1；(24)0；(25)1；(26)；(27)；(28)11；(29)；(30)偶數(shù)；(31)；(32)；(33)；(34)0；(35)0；(36)；(37)；(38)；(39)；(40).選擇題（1）A；（2）C；（3）C；（4）B；（5）B；（6）A；（7）B；（8）D；（9）B；（10）B；（11）B；（12）D；（13）B；（14）D；（15）D；（16）C；（17）C；（18）D；（19）C；（20）A；（21）A；（22）B；（23）B；（24）C；（25）B；（26）B；（27）B；（28）A；（29）B；（30）C；（31）B；（32）C；（33）B；（34）A；（35）A；（36）D；（37）D；（38）B；（39）B；（40）B.解答題1.解（1）的關(guān)系矩陣為（2）從的關(guān)系矩陣可知：是自反的和對稱的。又由于所以是傳遞的。因為是自反的、對稱的和傳遞的，所以是上的等價關(guān)系。（3），2.解：2481246233.解：3224161286234.解：由于是上的整除關(guān)系，所以是上的偏序關(guān)系，的哈斯圖為462351（1）集合的最大元：無，最小元：1（2）子集上界下界上確界下確界無1無161615.解：（1）之間的所有初級通路共有7條，分別為，，，，，，（2）之間的長度最短的通路只有1條，即，因而它是之間唯一的短程，（3）由于無向圖中有兩個奇度頂點，所以無向圖沒有歐拉圖回路，因而不是歐拉圖。6.解：圖（1）中各頂點的度數(shù)為，，，，，，，，由于圖（1）中各頂點的度數(shù)均為偶數(shù)，所以圖（1）為歐拉圖。回路為經(jīng)過圖（1）中每個結(jié)點一次且僅一次的回路，所以回路為哈密爾頓回路，因此圖（1）是哈密爾頓圖。圖（2）中各頂點的度數(shù)為，，，，，，，，由于圖（2）中有兩個奇度頂點，所以圖（2）存在歐拉圖通路，但是沒有歐拉圖回路，因此圖（2）不是歐拉圖?；芈窞榻?jīng)過圖（2）中每個結(jié)點一次且僅一次的回路，所以回路為哈密爾頓回路，因此圖（2）是哈密爾頓圖。7.解由于(1)只有兩個奇度結(jié)點，b,e.因此，要由(1)得到一個歐拉圖，必須使它們的度數(shù)都為偶數(shù)。最少需添加一條邊才能使(1)為歐拉圖。由于(2)有4個奇度結(jié)點，因此，要由(2)得到一個歐拉圖，必須使它們的度數(shù)都為偶數(shù)。最少需添加兩條邊才能使(2)為歐拉圖。例如，可在(1)中添加邊(b,e),在(2)中添加邊(a,b),(c,d)aabebdcdc（1）（2）8.解：(1)求的鄰接矩陣；(2),,中長度為4的通路數(shù)為，其中對角元素之和為3，中長度為4的回路有3條。由于中，所以中到長度為4的通路有4條。即，，，，其中為簡單通路。(3)由于由可知道是單向連通圖。9.解：(1)有向圖為(2)由于中長度為4的通路數(shù)為32。因?qū)窃刂蜑?，故中無長度為4的回路。(4)從圖可得的可達矩陣為從可知是強連通的。10.解：abcef構(gòu)造下列推理的證明1.證明：①前提引入；②前提引入；③①②析取三段論；④前提引入；⑤