1、離散數學綜合練習題 一、判斷下列命題是否正確如果正確，在題后括號內填“/”；否則，填“” （1）空集是任何集合的真子集 （ ）（2）是空集 （ ）（3） （ ） （4）如果，則或 （ ） （5）設集合，則 （ ） （6）設集合，則是到的關系 （ ）（7）關系的復合運算滿足交換律 （ ）（8）設為集合 上的等價關系, 則也是集合 上的等價關系 ( ) （9）設是集合上的等價關系, 則當時， ( ) （10）設為集合 上的等價關系, 則 ( )（11）集合A上的任一運算對A是封閉的 （ ） （12）設A是集合，則是可結合的 （ ） （13）設是群如果對于任意，有則是阿貝爾群 （ ） （14）設a是

2、群的元素，記則是的子群 （ ） （15）<0，1，2，3，4，max，min>是格 （ ） （16）設a，b是格的任意兩個元素，則 （ ） （17）設是布爾代數，則是格 （ ） （18）設集合，則是格 （ ）（19）設是布爾代數，則對任意，有 （ ） （20）設是布爾代數，則對任意，都有，使得 （ ）（21）n階完全圖的任意兩個不同結點的距離都為1. （ ）（22）在有向圖中，結點到結點的有向短程即為到的有向短程 （ ） （23）強連通有向圖一定是單向連通的 （ ） （24）不論無向圖或有向圖，初級回路一定是簡單回路 （ ） （25）設圖G是連通的，則任意指定G的各邊方向后所得的有

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

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

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

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

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

8、. (38)設是自然數，是奇數，是偶數，則命題“任何自然數不是奇數就是偶數” 符號化為 . (39)設是素數，是偶數，則命題“2既是偶數又是素數”符號化為 . (40)設是金子，是發光的，則命題“金子是發光的, 但發光的不一定是金子”符號化為 .三、選擇題（每題后面有四個選項，四個選項中只有一個是正確的，請將正確的所對應的字母填在括號內）（1）設為實數集合，下列集合中哪一個不是空集 （ ）A. B C. D. （2）設為集合，若，則一定有 （ ）A. B C. D. （3）下列各式中不正確的是 （ ）A. B C. D. （4）設，則下列各式中錯誤的是 （ ）A. B C. D. （5）設，則

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

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

11、爾代數的元素個數必定等于 （ ）A. ； B； C. ； D. .（20）在下面偏序集的哈斯圖中，哪一個是格 （ ）A B C D（21）僅由孤立點組成的圖稱為 （ ）A. 零圖； B平凡圖； C. 完全圖； D. 多重圖.（22）僅由一個孤立點組成的圖稱為 （ ）A. 零圖； B平凡圖； C.多重圖； D. 子圖.（23）在任何圖中必有偶數個 （ ）A. 度數為偶數的結點； B度數為奇數的結點； C. 入度為奇數的結點； D. 出度為奇數的結點.（24）設為有個結點的無向完全圖，則的邊數為 （ ）A. B C. D. （25）圖和的結點和邊分別存在一一對應關系是（同構）的 （ ）A. 充分條

12、件； B必要條件；C. 充分必要條件； D. 既不充分也不必要條件.（26）給定下列序列，哪一個可構成無向簡單圖的結點度數序列 （ ）A. BC. D. （27）在有個結點的連通圖中，其邊數 （ ）A. 最多條； B至少條；C. 最多條； D. 至少條.（28）是無向圖的關聯矩陣，是中的孤立點，則（ ）A. 對應的一行元素全為0； B對應的一行元素全為1；C. 對應的一列元素全為0； D. 對應的一列元素全為1.（29）任何無向圖中結點間的連通關系是 （ ）A. 偏序關系； B等價關系；C. 既是偏序關系又是等價關系； D. 既不是偏序關系也不是等價關系.（30）有向圖，其中，則有向圖是 （

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

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

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

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

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

18、正確；（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)

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) 偶數；(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）的關系矩陣為（2）從的關系矩陣可知：是自反的和對稱的。又由于所以是傳遞的。 因為是自反的、對稱的和傳遞的，所以是上的等價關系。（3） ，2. 解： 248 12 4 62 33. 解： 32 24 16 12 8 6 2

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

22、兩個奇度頂點，所以圖（2）存在歐拉圖通路，但是沒有歐拉圖回路，因此圖（2）不是歐拉圖。 回路為經過圖（2）中每個結點一次且僅一次的回路，所以回路為哈密爾頓回路，因此圖（2）是哈密爾頓圖。7. 解 由于(1)只有兩個奇度結點，b,e. 因此，要由(1)得到一個歐拉圖，必須使它們的度數都為偶數。最少需添加一條邊才能使(1)為歐拉圖。由于(2)有 4個奇度結點，因此，要由(2)得到一個歐拉圖，必須使它們的度數都為偶數。最少需添加兩條邊才能使(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的通路數為，其中對角元素之和為3，中長度為4的回路有3條。由于中，所以中到長度為4的通路有4條。即，其中為簡單通路。(3) 由于由可知道是單向連通圖。9. 解：(1) 有向圖為(2) 由于中長度為4的通路數為32。因對角元素之和為0，故中無長度為4的回路。(4) 從圖可得的可達矩陣為從可知是強連通的。10. 解： a b c e f五、 構造下列推理的證明1. 證明： 前提引入； 前提引入； 析取三段論； 前提引入； 置換； 析取三段論。2. 證明 前提引入； 前提引入； 拒取式； 前提引入； 假言推理； 前提引入； 拒取式； 前提引入； 析取三段論。3. 證明 前提引入； 前提引入； 析取三段論； 前提引入； 假言推理； 前提引入； 假言推理。4. 證明： 前提引入； EI； 化簡； 前提引入； UI； 假言推理； 化簡； 化簡； 合取引入(10) EG 5.