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

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

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

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

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

5、，并設(shè)是NN上的關(guān)系，其定義為：若ad=bc，則有（a,b）(c,d)，試證明：是一個(gè)等價(jià)關(guān)系。34、計(jì)算題1、 設(shè)集合，求：。2、 設(shè)集合，求：。3、 設(shè)集合，求：。4、設(shè)集合，A上二元關(guān)系，求（1）復(fù)合關(guān)系，（2）求R與的逆關(guān)系的關(guān)系矩陣。5、 集合，求，和。6、設(shè)集合，A的二元關(guān)系（1）畫(huà)出偏序集（A，R）的哈斯圖；（2）寫(xiě)出A的最大元、最小元；（3）判定偏序集（A，R）是不是格？元素b的補(bǔ)元素是什么？7、設(shè)，S上的偏序關(guān)系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）試畫(huà)出偏序集（S，R）的哈斯圖； （2）寫(xiě)出（S，R）的最大(小)元，極大（?。┰?。第三篇 代數(shù)系統(tǒng)內(nèi)容：典型題例：1、下面的代數(shù)系統(tǒng)（G，*）中，不是群。A、G=Q，*是加法 B、G=Q，*是乘法C、，*是加法 D、，*是加法2、設(shè)G是含6個(gè)元素的循環(huán)群，a是生成元，則下列為G的子群的是。 A、 B、 C、 D、3、下面的代數(shù)系統(tǒng)（G，*）中，*是普通加法運(yùn)算，則 不是群。A、G為有理數(shù)集合 B、G為整數(shù)集合C、G為實(shí)數(shù)集合 D、G為自然數(shù)集合4、設(shè)是環(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、一個(gè)群，而H是G的子集，那么是的子群的充要條件是。 A、 則 B、 則 C、則 D、存在單位元，存在逆元7、在群中，其單位元為 ，2的逆元素為 ，而2的周期為 。8、在群中，其單位元為 ，所有可能的子群為 。9、設(shè)集合上的兩個(gè)變換與分別為：，則= 。10、集合上的兩個(gè)變換與分別為，則= 。11、在群中，其單位元為，2的逆元素為，而2的周期為。12、集合上的兩個(gè)變換與分別為，則=。13、設(shè)，二元運(yùn)算*定義為a*b=min(a,b),那么在（A，*）中，單位元是，零元是。14、在群中，其單位元為，所

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

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

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

11、，到，到長(zhǎng)度是3的通路數(shù)。11、設(shè)，畫(huà)出無(wú)向圖G=，其中：，再求每個(gè)結(jié)點(diǎn)的次數(shù)。12、設(shè)，畫(huà)出無(wú)向圖G=，其中：，再求每個(gè)結(jié)點(diǎn)的次數(shù)。第五篇 數(shù)理邏輯內(nèi)容：典型題例：1、設(shè)命題公式，則G是 。A、恒真的 B、恒假的 C、可滿(mǎn)足的 D、合取范式2、設(shè)命題公式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個(gè)命題變?cè)梢越M成也只能組成 個(gè)不等的公式。A、 B、 C、 D、4、命題公式是。A、矛盾式 B、蘊(yùn)含式 C、重言式 D、等價(jià)式5、下列命題中， 是重言式。A、 B、 C、 D、 6、設(shè)L(X)：x是演員，J(x)：x是教師，A（x,y）x佩服y，命題“所有演員都佩服某些教師”可符號(hào)化為。A、 B、C、 D、7、設(shè)A(X)：x是人，B(x)：x犯錯(cuò)誤，命題“沒(méi)有不犯錯(cuò)誤的人”可符號(hào)化為。A、 B、C、 D、8、設(shè)命題公式，則使G為真的解釋是 。9、謂詞演算的公理系統(tǒng)中，全稱(chēng)規(guī)則為： ；存在規(guī)則為 。10、語(yǔ)句“對(duì)所有x”稱(chēng)為全稱(chēng)量詞，記作，語(yǔ)句“存在某些x”稱(chēng)為存在量詞，記作。11、若命題變?cè)狿，