離散數(shù)學(xué)2017秋綜合練習(xí)題

1、精選優(yōu)質(zhì)文檔-傾情為你奉上離散數(shù)學(xué)綜合練習(xí)題 一、判斷下列命題是否正確如果正確，在題后括號(hào)內(nèi)填“/”；否則，填“” （1）空集是任何集合的真子集 （ ）（2）是空集 （ ）（3） （ ） （4）如果，則或 （ ） （5）設(shè)集合，則 （ ） （6）設(shè)集合，則 是到的關(guān)系 （ ）（7）關(guān)系的復(fù)合運(yùn)算滿足交換律 （ ）（8）設(shè)為集合 上的等價(jià)關(guān)系, 則也是集合 上的等價(jià)關(guān)系 ( ) （9）設(shè)是集合上的等價(jià)關(guān)系, 則當(dāng)時(shí)， ( ) （10）設(shè)為集合 上的等價(jià)關(guān)系, 則 ( )（11）集合A上的任一運(yùn)算對(duì)A是封閉的 （ ） （12）設(shè)A是集合，則是可結(jié)合的 （ ） （13）設(shè)是群如果對(duì)于任意，有 則是阿

2、貝爾群 （ ） （14）設(shè)a是群的元素，記 則是的子群 （ ） （15）是格 （ ） （16）設(shè)a，b是格的任意兩個(gè)元素，則 （ ） （17）設(shè)是布爾代數(shù)，則是格 （ ） （18）設(shè)集合，則是格 （ ）（19）設(shè)是布爾代數(shù)，則對(duì)任意，有 （ ） （20）設(shè)是布爾代數(shù)，則對(duì)任意，都有，使得 （ ）（21）n階完全圖的任意兩個(gè)不同結(jié)點(diǎn)的距離都為1. （ ）（22）在有向圖中，結(jié)點(diǎn)到結(jié)點(diǎn)的有向短程即為到的有向短程 （ ） （23）強(qiáng)連通有向圖一定是單向連通的 （ ） （24）不論無向圖或有向圖，初級(jí)回路一定是簡單回路 （ ） （25）設(shè)圖G是連通的，則任意指定G的各邊方向后所得的有向圖是弱連通的 （

3、 ） （26）設(shè)A是某個(gè)無向圖的鄰接矩陣，則(是的轉(zhuǎn)置矩陣) （ ）（27）設(shè)有向圖D的可達(dá)矩陣為 則是單向連通的 （ ） （28）有生成樹的無向圖是連通的 （ ） （29）由r棵樹組成的森林的結(jié)點(diǎn)數(shù)n與邊數(shù)m有下列關(guān)系：m=n-r. （ ）（30）如果有向圖D僅有一個(gè)結(jié)點(diǎn)的入度為0，其余結(jié)點(diǎn)的入度都為1，則D是有向樹 （ ）（31）“如果872，則三角形有四條邊”是命題 （ ） （32）設(shè)都是命題公式，則也是命題公式 （ ） （33）命題公式的真值分別為0，1，則的真值為0（以上是在對(duì)所包含的命題變元的某個(gè)賦值下） （ ）（34）邏輯結(jié)論是正確結(jié)論 （ ）（35）設(shè)都是謂詞公式，則也是謂詞公

4、式 （ ）（36）設(shè)都是謂詞公式，則是永真式 （ ） （37）設(shè)都是命題公式，則 也是命題公式 （ ） （38）命題公式的真值分別為0，1，則的真值為0（以上是在對(duì)所包含的命題變元的某個(gè)賦值下） （ ） （39）設(shè)是個(gè)體域中某個(gè)元素，則 其中都是謂詞 （ ） （40） （ ）二、填空題（1）設(shè)有個(gè)元素，則集合的冪集中有 個(gè)元素。（2）設(shè)，則= .（3）設(shè)集合中元素的個(gè)數(shù)分別為，且，則集合中元素的個(gè)數(shù) . （4）設(shè)集合，則中元素的個(gè)數(shù)為 .(5)設(shè)為集合 上的二元關(guān)系, 則 . (6)集合上的二元關(guān)系為傳遞的充分必要條件是 (7)設(shè)：稱為母親，：稱為父親，則： , (8)設(shè)為自然數(shù)的集合，“”為

5、自然數(shù)的小于等于關(guān)系，的子集，則的下確界為 ，下確界為 , (9)設(shè)10人集合趙茵，錢小濱，孫麗春，趙萍，錢浩，李靖華，李秀娟，錢鈺，李惠芝，李莉上的同姓關(guān)系為，則等價(jià)類趙= ，錢= ， (10)設(shè) , 是 上的包含于關(guān)系，,則有= . (11)設(shè)為非空有限集，代數(shù)系統(tǒng)中，對(duì)運(yùn)算的單位元為 ，零元為 . (12)循環(huán)群的生成元為 . (13)循環(huán)群的所有子群為 . (14)代數(shù)系統(tǒng)中（其中為整數(shù)集合，+為普通加法），對(duì)任意的，其 . (15)在整數(shù)集合上定義運(yùn)算為，則的單位元為 . (16)設(shè),在代數(shù)系統(tǒng)中，的單位元為 ，可逆元為 . (17)設(shè)是群，則對(duì)于任意的，方程 和 有唯一解。 (18

6、)設(shè)是群，對(duì)任意，如果，則 . (19)設(shè)是群，為單位元，若元素滿足，則 . (20)在整數(shù)集合上定義運(yùn)算為，則的單位元為 . (21)設(shè)為樹，中有4度，3度，2度分支點(diǎn)各1個(gè)，問中有 片樹葉。 (22)為了從（n，m）連通無向圖得到一棵生成樹，必須刪除G的 條邊 (23)設(shè)樹T中有7片樹葉，3個(gè)3度結(jié)點(diǎn)，其余都是4度結(jié)點(diǎn)，問T中有 個(gè)4度結(jié)點(diǎn)。 (24)無環(huán)有向圖的關(guān)聯(lián)矩陣的所有元素之和為 (25)n階完全圖的任意兩個(gè)不同結(jié)點(diǎn)的距離都為 (26)圖為階無向完全圖，則共有 條邊。 (27)設(shè)為圖，則圖中結(jié)點(diǎn)度數(shù)的總和為 。 (28)設(shè)圖有6結(jié)點(diǎn)，若各結(jié)點(diǎn)的度數(shù)分別為：1，4，4，3，5，5，則

7、共有 條邊。 (29)無向圖是由棵樹組成的森林，至少要添加 條邊才能使成為一棵樹。 (30)在任何圖中，奇數(shù)結(jié)點(diǎn)必為 個(gè)。 (31)設(shè) 天氣很冷，老王還是來了，則命題“雖然天氣很冷, 但老王還是來了”符號(hào)化為 . (32)設(shè)天下雨， 我騎自行車上班，則命題“如果天不下雨, 我就騎自行車上班”符號(hào)化為 . (33)設(shè)經(jīng)一事, 長一智，則命題“不經(jīng)一事, 不長一智”符號(hào)化為 . (34)設(shè)的真值為0，的真值為1，則命題公式的真值為 . (35)設(shè)的真值為0，的真值為1，則命題公式的真值為 . (36)由個(gè)命題變項(xiàng)可以組成 個(gè)不等值的命題公式。 (37)設(shè)個(gè)體域，公式在上消去量詞后應(yīng)為 . (38)

8、設(shè)是自然數(shù)，是奇數(shù)，是偶數(shù)，則命題“任何自然數(shù)不是奇數(shù)就是偶數(shù)” 符號(hào)化為 . (39)設(shè)是素?cái)?shù)，是偶數(shù)，則命題“2既是偶數(shù)又是素?cái)?shù)”符號(hào)化為 . (40)設(shè)是金子，是發(fā)光的，則命題“金子是發(fā)光的, 但發(fā)光的不一定是金子”符號(hào)化為 .三、選擇題（每題后面有四個(gè)選項(xiàng)，四個(gè)選項(xiàng)中只有一個(gè)是正確的，請(qǐng)將正確的所對(duì)應(yīng)的字母填在括號(hào)內(nèi)）（1）設(shè)為實(shí)數(shù)集合，下列集合中哪一個(gè)不是空集 （ ）A. B C. D. （2）設(shè)為集合，若，則一定有 （ ）A. B C. D. （3）下列各式中不正確的是 （ ）A. B C. D. （4）設(shè)，則下列各式中錯(cuò)誤的是 （ ）A. B C. D. （5）設(shè)，則為 （ ）A

9、. B C. D. （6）設(shè)，則的恒等關(guān)系為 （ ）A. B C. D. （7）集合上的二元關(guān)系，則的性質(zhì)為 （ ）A. 自反的； B對(duì)稱的； C. 反對(duì)稱的； D. 反自反的.（8）設(shè)上的二元關(guān)系如下，則具有傳遞性的為 （ ）A. B C. D. （9）設(shè)為集合上的等價(jià)關(guān)系，對(duì)任意，其等價(jià)類為 （ ）A. 空集； B非空集； C. 是否為空集不能確定； D. .（10）映射的復(fù)合運(yùn)算滿足 （ ）A. 交換律 B結(jié)合律 C. 冪等律 D. 分配律（11）在整數(shù)集上，下列哪種運(yùn)算是可結(jié)合的 （ ）A. B C. D. （12）設(shè)集合，下面定義的哪種運(yùn)算關(guān)于集合不是封閉的 （ ）A. B C. ，

10、即的最大公約數(shù)D. ，即的最小公倍數(shù)（13）下列哪個(gè)集關(guān)于減法運(yùn)算是封閉的 （ ）A. （自然數(shù)集）； B；C. ； D. .（14）設(shè)是有理數(shù)集，在定義運(yùn)算為，則的單位元為 （ ）A. ； B； C. 1； D. 0（15）下列代數(shù)系統(tǒng)中，哪一個(gè)不構(gòu)成群 （ ）A. 是模11乘法；B. 是模3加法；C. 普通加法；D. 普通乘法.（16）循環(huán)群 的生成元為1和2，它們的周期為 （ ）A. 5 B6 C. 3 D. 9（17）循環(huán)群 的所有子群為 （ ）A. B C. 和 D. （18）循環(huán)群的所有生成元為 （ ）A. 1，0 B-1，2 C. 1，2 D. 1，-1（19）有限布爾代數(shù)的元素

11、個(gè)數(shù)必定等于 （ ）A. ； B； C. ； D. .（20）在下面偏序集的哈斯圖中，哪一個(gè)是格 （ ） A B C D（21）僅由孤立點(diǎn)組成的圖稱為 （ ）A. 零圖； B平凡圖； C. 完全圖； D. 多重圖.（22）僅由一個(gè)孤立點(diǎn)組成的圖稱為 （ ）A. 零圖； B平凡圖； C.多重圖； D. 子圖.（23）在任何圖中必有偶數(shù)個(gè) （ ）A. 度數(shù)為偶數(shù)的結(jié)點(diǎn)； B度數(shù)為奇數(shù)的結(jié)點(diǎn)； C. 入度為奇數(shù)的結(jié)點(diǎn)； D. 出度為奇數(shù)的結(jié)點(diǎn).（24）設(shè)為有個(gè)結(jié)點(diǎn)的無向完全圖，則的邊數(shù)為 （ ）A. B C. D. （25）圖和的結(jié)點(diǎn)和邊分別存在一一對(duì)應(yīng)關(guān)系是（同構(gòu)）的 （ ）A. 充分條件； B必

12、要條件；C. 充分必要條件； D. 既不充分也不必要條件.（26）給定下列序列，哪一個(gè)可構(gòu)成無向簡單圖的結(jié)點(diǎn)度數(shù)序列 （ ）A. BC. D. （27）在有個(gè)結(jié)點(diǎn)的連通圖中，其邊數(shù) （ ）A. 最多條； B至少條；C. 最多條； D. 至少條.（28）是無向圖的關(guān)聯(lián)矩陣，是中的孤立點(diǎn)，則（ ）A. 對(duì)應(yīng)的一行元素全為0； B對(duì)應(yīng)的一行元素全為1；C. 對(duì)應(yīng)的一列元素全為0； D. 對(duì)應(yīng)的一列元素全為1.（29）任何無向圖中結(jié)點(diǎn)間的連通關(guān)系是 （ ）A. 偏序關(guān)系； B等價(jià)關(guān)系；C. 既是偏序關(guān)系又是等價(jià)關(guān)系； D. 既不是偏序關(guān)系也不是等價(jià)關(guān)系.（30）有向圖，其中，則有向圖是 （ ）A. 強(qiáng)

13、連通圖； B單向連通圖；C. 弱連通圖； D. 不連通圖.（31）下面哪個(gè)聯(lián)結(jié)詞不可交換 （ ）A. ； B； C.； D. .（32）命題公式是 （ ）A. 矛盾式； B非永真式的可滿足式；C. 重言式； D. 等價(jià)式.（33）下列哪一組命題公式是等值的 （ ）A. ，； B，；C. ，； D. ，（34）下面哪一個(gè)命題是假命題 （ ）A. 如果2是偶數(shù)，那么一個(gè)公式的析取范式唯一；B如果2是偶數(shù)，那么一個(gè)公式的析取范式不唯一；C. 如果2是奇數(shù)，那么一個(gè)公式的析取范式唯一；D. 如果2是奇數(shù)，那么一個(gè)公式的析取范式不唯一.（35）設(shè)論域?yàn)檎麛?shù)集，下列公式中哪個(gè)值為真 （ ）A. ； B.

14、；C. ； D. .（36）設(shè)謂詞是奇數(shù)，是偶數(shù)，謂詞公式在哪個(gè)論域中是可滿足的 （ ）A. 自然數(shù)； B整數(shù)； C. 實(shí)數(shù)； D. 以上均不成立.（37）命題“沒有不犯錯(cuò)誤的人”符號(hào)化為(設(shè)是人,犯錯(cuò)誤) （ ）A. ； B.；C. ； D.（38）設(shè)個(gè)體域，公式在上消去量詞后應(yīng)為 （ ）A. ； B. ；C. ； D. .（39）在謂詞演算中，下列各式中，哪一個(gè)是正確的 （ ）A.； B.；C.； D.（40）“學(xué)習(xí)有如逆水行舟，不進(jìn)則退”。設(shè)學(xué)習(xí)如逆水行舟，學(xué)習(xí)進(jìn)步，學(xué)習(xí)退步。則命題符號(hào)化為 （ ）A. ； B； C. ； D. .四、解答題1. 設(shè) 上的關(guān)系試 （1）寫出的關(guān)系矩陣；

15、（2）驗(yàn)證是上的等價(jià)關(guān)系； （3）求出的各元素的等價(jià)類。2. 設(shè)，上的整除關(guān)系，畫出的哈斯圖。3. 設(shè)集合 , 是上的整除關(guān)系,畫出的哈斯圖；4. 設(shè)集合, 是上的整除關(guān)系，試求：（1） 集合的最大元，最小元（2） 子集和的上界、下界、上確界和下確界。5. 在下面的無向圖中，回答下列問題 （1）寫出之間的所有初級(jí)通路； （2）寫出之間的所有短程，并求； （3）判斷無向圖是否為歐拉圖并說明理由。6. 下列各圖是否為歐拉圖，是否為哈密爾頓圖？為什么？ (1) (2)7. 下列圖形中最少需添加幾條邊才能成為歐拉圖 a a b e b d c d c （1） （2）8. 有向圖如下圖所示(1) 求的鄰

16、接矩陣；(2) 求中長度為4的通路數(shù)和回路數(shù)，并找出中從到長度為4的所有通路。(3) 是哪類連通圖？9. 設(shè)有向圖，其鄰接矩陣為(1) 畫出有向圖；(2) 中長度為4的通路有多少條？其中有多少條為回路？(3) 是那類連通圖？ 10. 設(shè)連通圖如下圖所示，求它的一棵生成樹a b c e f答案不唯一。五、構(gòu)造下列推理的證明 1. 證明 2. 證明 3. 證明 4. 證明 5. 構(gòu)造下列推理的證明：每個(gè)學(xué)術(shù)委員會(huì)的成員都是專家并且是大學(xué)生，有些成員是青年人，所以有些成員是青年專家。6.“有些病人相信所有的醫(yī)生，病人都不相信騙子，所以醫(yī)生都不是騙子?！痹谝浑A邏輯中證明以上推理是正確的。六、證明題1.

17、 設(shè)為集合上的等價(jià)關(guān)系, 試證也是集合上的等價(jià)關(guān)系。2. 設(shè)為無向連通圖中任意兩個(gè)頂點(diǎn)，證明：若，則存在頂點(diǎn)，使得3. 證明下面四個(gè)矩陣關(guān)于矩陣乘法運(yùn)算構(gòu)成群。， ， ， 4. 設(shè) 是一個(gè)群，試證 是交換群 當(dāng)且僅當(dāng)對(duì)任意的 ,有 . 5. 設(shè)是群的元素，記，證明是的子群6. 設(shè)是一個(gè)群，取定，定義 ， 證明是一個(gè)群。離散數(shù)學(xué)綜合練習(xí)題答案一、 判斷下列命題是否正確（1）錯(cuò)誤； （2）錯(cuò)誤； （3）正確； （4）錯(cuò)誤； （5）錯(cuò)誤；（6）正確； （7）錯(cuò)誤； （8）正確； （9）正確； （10）錯(cuò)誤；（11）正確；（12）正確；（13）正確；（14）正確；（15）正確；（16）正確；（17）正

18、確；（18）正確；（19）正確；（20）正確；（21）正確；（22）錯(cuò)誤；（23）正確；（24）正確；（25）正確；（26）正確；（27）正確；（28）正確；（29）正確；（30）錯(cuò)誤；（31）正確；（32）錯(cuò)誤；（33）錯(cuò)誤；（34）錯(cuò)誤；（35）錯(cuò)誤；（36）正確；（37）正確；（38）正確；（39）錯(cuò)誤；（40）錯(cuò)誤.二、 填空題（1）； （2）； （3）3； （4）40； (5)(6) ； (7)稱為外祖父； (8)5，9； (9)趙= 趙茵，趙萍，錢= 錢小濱，錢浩，錢鈺，孫= 孫麗春，李= 李靖華，李秀娟，李惠芝，李莉.(10)(11) ； (12) 1和2；(13)，；(14)

19、； (15) 2； (16) 1，1； (17) ，； (18) ；(19) ； (20) 0； (21) 5； (22) m-n1； (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； （

20、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)系矩陣可知：是自反的和對(duì)稱的。又由于 所以是傳遞的。 因?yàn)槭亲苑吹?、?duì)稱的和傳遞的，所以是上的等價(jià)關(guān)系。（3） ，2. 解： 248 12 4 6 2 33. 解： 32 24 16 12 8 6

21、 2 34. 解：由于是上的整除關(guān)系，所以是上的偏序關(guān)系，的哈斯圖為 4 6 2 3 5 1（1）集合的最大元：無，最小元：1（2）子集上界下界上確界下確界無1無161615. 解：（1）之間的所有初級(jí)通路共有7條，分別為，（2）之間的長度最短的通路只有1條，即，因而它是之間唯一的短程，（3）由于無向圖中有兩個(gè)奇度頂點(diǎn)，所以無向圖沒有歐拉圖回路，因而不是歐拉圖。6. 解：圖（1）中各頂點(diǎn)的度數(shù)為 ，由于圖（1）中各頂點(diǎn)的度數(shù)均為偶數(shù)，所以圖（1）為歐拉圖。 回路為經(jīng)過圖（1）中每個(gè)結(jié)點(diǎn)一次且僅一次的回路，所以回路為哈密爾頓回路，因此圖（1）是哈密爾頓圖。圖（2）中各頂點(diǎn)的度數(shù)為 ，由于圖（2）

22、中有兩個(gè)奇度頂點(diǎn)，所以圖（2）存在歐拉圖通路，但是沒有歐拉圖回路，因此圖（2）不是歐拉圖。 回路為經(jīng)過圖（2）中每個(gè)結(jié)點(diǎn)一次且僅一次的回路，所以回路為哈密爾頓回路，因此圖（2）是哈密爾頓圖。7. 解 由于(1)只有兩個(gè)奇度結(jié)點(diǎn)，b,e. 因此，要由(1)得到一個(gè)歐拉圖，必須使它們的度數(shù)都為偶數(shù)。最少需添加一條邊才能使(1)為歐拉圖。由于(2)有 4個(gè)奇度結(jié)點(diǎn)，因此，要由(2)得到一個(gè)歐拉圖，必須使它們的度數(shù)都為偶數(shù)。最少需添加兩條邊才能使(2)為歐拉圖。例如，可在(1)中添加邊(b,e), 在(2)中添加邊(a,b),(c,d) a a b e b d c d c（1） （2）8. 解：(1)

23、 求的鄰接矩陣；(2) , , 中長度為4的通路數(shù)為，其中對(duì)角元素之和為3，中長度為4的回路有3條。由于中，所以中到長度為4的通路有4條。即，其中為簡單通路。(3) 由于 由可知道是單向連通圖。9. 解：(1) 有向圖為 (2) 由于 中長度為4的通路數(shù)為32。因?qū)窃刂蜑?，故中無長度為4的回路。(4) 從圖可得的可達(dá)矩陣為 從可知是強(qiáng)連通的。 10. 解： a b c e f五、 構(gòu)造下列推理的證明1. 證明： 前提引入； 前提引入； 析取三段論； 前提引入； 置換； 析取三段論。2. 證明 前提引入； 前提引入； 拒取式； 前提引入； 假言推理； 前提引入； 拒取式； 前提引入； 析取三段論。3. 證明 前提引入； 前提引入； 析取三段論； 前提引入； 假言推理； 前提引入； 假言推理。4. 證明： 前提引入； EI； 化簡； 前提引入； UI； 假言推理； 化簡； 化簡； 合取引入(10) EG 5. 解：設(shè)是學(xué)術(shù)委員