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

1、離散數(shù)學(xué)復(fù)習(xí)題離散數(shù)學(xué)復(fù)習(xí)題一、填空1、命題中的否定聯(lián)接詞；析取聯(lián)接詞；蘊(yùn)含聯(lián)接詞。2、一個(gè)命題公式，若在所有賦值下取值為真，則稱此公式為永真式；若……假，則……..為永假式；若至少存在一組賦值，其命題為真，則…….為可滿足式。3、有限布爾代數(shù)只能有個(gè)元素。2n4、R是定義在集合上的二元關(guān)系，若R滿足自反性、對(duì)稱性、傳遞性，則稱R是A上的等價(jià)關(guān)系。5、全序集（A，）必是偏序集，且是鏈。≤6、n階m條邊無向圖G是樹，當(dāng)且僅當(dāng)G是連通點(diǎn)，且

2、m=n1。7、若有向樹G中，有一個(gè)頂點(diǎn)的入度為0，其余點(diǎn)的入度均1，則稱G為根樹。8、有序?qū)哂幸韵滦再|(zhì)（1）當(dāng)x不等于y時(shí)，≠（2）=的充要條件是x=u且y=r。9、關(guān)系的性質(zhì)五自反、反自反、對(duì)稱、反對(duì)稱、傳遞。10、圖中頂點(diǎn)作為邊的端點(diǎn)的條數(shù)稱為此頂點(diǎn)的度數(shù)。11、設(shè)X是格，并對(duì)交運(yùn)算時(shí)可分配的，則格中的并運(yùn)算對(duì)交運(yùn)算是可分配的且格中的交運(yùn)算對(duì)并運(yùn)算是可分配的。12、有向圖按連通圖分為三類強(qiáng)連通圖、單向連通圖、弱連通圖。13、T為一

3、顆根樹，若T的每個(gè)分支點(diǎn)的兒子數(shù)都為r，則稱T為r元正則樹。14、設(shè)A、B是集合，求A與B之間關(guān)系（屬于、不屬于、包含…）如果A=1，B=112，則A不屬于B、A不包含B15、若R是定義在集合A上的一個(gè)二元關(guān)系，若R滿足自反性、反對(duì)稱性、可傳遞性則稱R是偏序關(guān)系。16、設(shè)集合A=1234，A上二元關(guān)系R=，則逆序關(guān)系=R?1。17、在有補(bǔ)分配格中，每個(gè)元素（的補(bǔ)元）都是唯一的。18、在無向圖中，度數(shù)為奇數(shù)的頂點(diǎn)個(gè)數(shù)必為偶數(shù)。19、若圖中

4、通路P中所有邊互不相同，則稱P為簡(jiǎn)單通路，若通路中所有頂點(diǎn)互不相同，則稱P為基本通路。二、簡(jiǎn)述題8、集合A=1236812，求A上的整除關(guān)系R并畫出Hasse圖9、寫出的前綴式和后綴式（（a4b）c（7bd））（c8a）10、求群的自同態(tài)（N6?6）五、證明題1、證明是循環(huán)群（N13?0，?13）2、證明不存在含有奇數(shù)個(gè)面且每個(gè)面上有奇數(shù)個(gè)棱的多面體3、設(shè)是代數(shù)系統(tǒng)，R是上的同余關(guān)系，是其商代數(shù)，（A?）（A?）(AR?)設(shè)f是A到AR

5、的函數(shù)，對(duì)于A中任意元素a，都有f（a）=|a|R證明：f是到的同態(tài)映射（A?）(AR?)4、設(shè)T是完全k元樹，若分枝點(diǎn)為i，樹葉數(shù)為t，證明：i=(t?1)(k?1)5、證明偶數(shù)階群必有二階子群，且必有奇數(shù)個(gè)二階子群6、R是集合A上的等價(jià)關(guān)系，證明：對(duì)任意x，y屬于A（1）若，則xRy|x|R=|y|R（2）若，則(xy)?R|x|R∩|x|R=?7、證明下列說法是等價(jià)的（1）（2）（3）（4）A≤BA?B=?A∩B=AA∪B=B8、