離散數(shù)學習題

1、第一篇 緒論內(nèi)容：（三句話）典型題例：1、離散數(shù)學是計算機科學所涉及的 和 的總稱。2、離散數(shù)學是數(shù)學中的一個分支，它以 作為其主要研究對象，非常重視 問題的研究。3、要解決一個問題，首先要證明此問題解的 ，還需要找出得到此問題的步驟來，而且其步驟必須是 ，有規(guī)則的，這就是所謂“能行性”問題的研究。第二篇 集合論內(nèi)容：典型題例：1、設集合，那么下列命題中正確的是 。A、 B、 C、 D、2、設A，B是集合，如果，則 。A、 B、 C、 D、3、設集合，那么下列命題中錯誤的是。A、 B、 C、 D、4、設集合，,則 。A、 B、 C、 D、5、設，那么集合A，B的對稱差A+B= 。A、 B、 C

2、、 D、6、集合，X上的一個劃分，那么所對應的等價關系R應有有 個序偶。A、8 B、9 C、10 D、137、設集合上的二元關系，則R不具有。A、傳遞性 B、自反性 C、對稱性 D、反對稱性8、設集合，X上的關系，則R具有 。A、自反性 B、非自反性 C、對稱性 D、傳遞性9、設集合，A上的二元關系，則關系。A、 B、 C、 D、10、設集合，和都是X上的二元關系，其中，則。A、 B、 C、 D、11、，那么可以定義 種不同的從A到B的映射。A、8 B、16 C、32 D、6412、設R是實數(shù)集，函數(shù)，則f是。A、單射 B、滿射 C、雙射 D、既不是單射，也不是滿射13、設R是實數(shù)集，映射，則

3、f是。A、單射 B、滿射 C、雙射 D、都不是14、設，集合的這種表示方法稱為；Y=xx是正偶數(shù)，集合的這種表示方法稱為。15、設全集 ，則：，A+B= 。16、A，B，C為 任意三集合，則 。17、 ， 。18、設，則 。19、設集合，R是A上的整除關系，則A的極大元是，極小元是。20、設集合，R是X上的整除關系，則X的極大元是，極小元是。21、對于一個關系R，它可能具有 、 、 、 、 等五種性質(zhì)。22、對于一個等價關系，則它對應的等價類為 。23、設集合，A上的等價關系，則它所對應的等價類為 。24、設集合，A上的一個劃分，那么所對應的等價關系R應有個序偶。25、凡與自然數(shù)集等勢的集合都

4、是可列集，那么整數(shù)集Z是 ，實數(shù)集R是 。26、一集合為無限集，則它必含有與其的真子集，在無限集中，最小的無限集是，其次是。27、集合A=a,b,c的冪集（A）上的“”關系是一個偏序關系，設B=a,b,b,c,b,c,，則B的極大元素為 ，極小元為 ，上確界為 ，下確界為 。28、設A，B為有限集，且，那么A與B間存在雙射，當且僅當 。29、設集合，則從A到B的所有映射有個，其中滿射有個。30、設集合，則從A到B的所有映射有個，其中雙射有個。31、證明題設A，B，C為任意集合，試證明：。32、簡答題 試解釋偏序關系和等價關系的概念，并給出一個集合上的關系，使它既是偏序關系又是等價關系。33、設

5、，并設是NN上的關系，其定義為：若ad=bc，則有（a,b）(c,d)，試證明：是一個等價關系。34、計算題1、 設集合，求：。2、 設集合，求：。3、 設集合，求：。4、設集合，A上二元關系，求（1）復合關系，（2）求R與的逆關系的關系矩陣。5、 集合，求，和。6、設集合，A的二元關系（1）畫出偏序集（A，R）的哈斯圖；（2）寫出A的最大元、最小元；（3）判定偏序集（A，R）是不是格？元素b的補元素是什么？7、設，S上的偏序關系R=(a,a), (b,a), (b,b),(c,a),(c,c),(d,a),(d,b),(d,c),(d,d),(e,a),(e,c),(e,e),(f,f)。

6、（1）試畫出偏序集（S，R）的哈斯圖； （2）寫出（S，R）的最大(小)元，極大（?。┰５谌?代數(shù)系統(tǒng)內(nèi)容：典型題例：1、下面的代數(shù)系統(tǒng)（G，*）中，不是群。A、G=Q，*是加法 B、G=Q，*是乘法C、，*是加法 D、，*是加法2、設G是含6個元素的循環(huán)群，a是生成元，則下列為G的子群的是。 A、 B、 C、 D、3、下面的代數(shù)系統(tǒng)（G，*）中，*是普通加法運算，則 不是群。A、G為有理數(shù)集合 B、G為整數(shù)集合C、G為實數(shù)集合 D、G為自然數(shù)集合4、設是環(huán)，是它的子代數(shù)，是的子環(huán)的充要條件是 。 A、 B、 C、 D、存在單位元5、下面的代數(shù)系統(tǒng)（G，*）中，不是群。A、G為n階方陣的集

7、合，*為矩陣乘法 B、G為有理數(shù)集合，*為加法C、G為整數(shù)集，*為加法 D、G為偶數(shù)集，*為加法6、一個群，而H是G的子集，那么是的子群的充要條件是。 A、 則 B、 則 C、則 D、存在單位元，存在逆元7、在群中，其單位元為 ，2的逆元素為 ，而2的周期為 。8、在群中，其單位元為 ，所有可能的子群為 。9、設集合上的兩個變換與分別為：，則= 。10、集合上的兩個變換與分別為，則= 。11、在群中，其單位元為，2的逆元素為，而2的周期為。12、集合上的兩個變換與分別為，則=。13、設，二元運算*定義為a*b=min(a,b),那么在（A，*）中，單位元是，零元是。14、在群中，其單位元為，所

8、有可能的子群為。15、分析題 1、設在有理數(shù)集Q上的有運算定義為：。 （1）是代數(shù)系統(tǒng)嗎： （2）是半群嗎？是可換半群嗎？ （3）有單位元嗎？單位元是什么？ （4）中每個元素有逆元素嗎？任一元素的逆元素是什么？2、設Q為有理數(shù)集，在Q上定義集合，運算*是普通乘法。 （1）是代數(shù)系統(tǒng)嗎? （2）是半群嗎？是可換半群嗎？ （3）有單位元嗎？單位元是什么？ （4）中每個元素有逆元素嗎？任一元素的逆元素是什么？3、設是正整數(shù)集，（即a,b的最小公倍數(shù)），試問：（1）是半群嗎？（2）有單位元嗎？單位元是什么？（3）是否每個元素都有逆元素？16、計算題：1、 求中子群H=0，3，6，9的左、右陪集，并問左

9、、右陪集是否相等？。2、 找出的所有子群。14、試證若群（G，*）的每個元素的逆元素都是它自己，則該群必是可換群。第四篇 圖論內(nèi)容：典型題例：1、設G是由5個頂點組成的完全圖，則從G中刪去 條邊可以得到樹。A、10 B、5 C、4 D、 62、一有向圖G=，其對應的鄰接矩陣為，則對于，它的引入次數(shù)為 。A、 B、 C、 D、 3、設連通圖G=，其中，則要刪去G中 條邊，才能確定G的一棵生成樹。A、n-m-1 B、n-m+1 C、m-n+1 D、m-n-14、無向連通圖G中結點間存在歐拉通路的充要條件是G中的次數(shù)均為 ，而其他結點的次數(shù)為 。5、一個有向（n, m）圖中任何基本通路長度均小于或等

10、于 ，而任何基本回路長度均小于或等于 。6、在圖G=V，E中，結點次數(shù)與邊數(shù)的關系是 。7、在有向圖的鄰接矩陣中，第i行元素之和為 ，而中的任一個元素代表的含義為 。8、D是具有結點的有向圖，它的鄰接矩陣表示如下： （1）D是單向連通的，還是強連通的？ （2）求從到，長度為3的通路數(shù)。9、設有向圖D=V，E，其中V=a1,a2,a3,a4,a5，E=(a1,a2),(a2,a4),(a3,a1),(a4,a5),(a5,a2)，（1） 求D的鄰接矩陣。（2）利用可達性矩陣判斷其連通性。10、D是具有結點的有向圖，它的鄰接矩陣表示如下： （1）利用可達性矩陣的特性，判斷D的連通性； （2）求從到

11、，到，到長度是3的通路數(shù)。11、設，畫出無向圖G=，其中：，再求每個結點的次數(shù)。12、設，畫出無向圖G=，其中：，再求每個結點的次數(shù)。第五篇 數(shù)理邏輯內(nèi)容：典型題例：1、設命題公式，則G是 。A、恒真的 B、恒假的 C、可滿足的 D、合取范式2、設命題公式G=，則使G為真的解釋是 。A、（F，F(xiàn)，F(xiàn)） B、（F，F(xiàn)，T） C、（F，T，F(xiàn)） D、（T，F(xiàn)，F(xiàn)）3、n個命題變元可以組成也只能組成 個不等的公式。A、 B、 C、 D、4、命題公式是。A、矛盾式 B、蘊含式 C、重言式 D、等價式5、下列命題中， 是重言式。A、 B、 C、 D、 6、設L(X)：x是演員，J(x)：x是教師，A（x,y）x佩服y，命題“所有演員都佩服某些教師”可符號化為。A、 B、C、 D、7、設A(X)：x是人，B(x)：x犯錯誤，命題“沒有不犯錯誤的人”可符號化為。A、 B、C、 D、8、設命題公式，則使G為真的解釋是 。9、謂詞演算的公理系統(tǒng)中，全稱規(guī)則為： ；存在規(guī)則為 。10、語句“對所有x”稱為全稱量詞，記作，語句“存在某些x”稱為存在量詞，記作。11、若命題變元P，