第一篇：離散數(shù)學(xué)考試大綱

武漢理工大學(xué)2011年博士入學(xué)考試《離散數(shù)學(xué)》考試大綱

一、考試要求共濟(jì)

要求考生系統(tǒng)地掌握離散數(shù)學(xué)的基本概念、基本定理和方法，具有較強(qiáng)的邏輯思維和抽象思維能力，能夠靈活運(yùn)用所學(xué)的內(nèi)容和方法解決實(shí)際問(wèn)題。考

二、考試內(nèi)容濟(jì)

1、數(shù)理邏輯濟(jì)

1)命題和聯(lián)結(jié)詞，謂詞與量詞，合適公式，賦值，解釋與指派，范式共

2)命題形式化，等價(jià)式與對(duì)偶式，蘊(yùn)含式，推理與證明

3)證明方法3

4)數(shù)學(xué)歸納法

2、集合論院

1)集合代數(shù)，笛卡爾乘積，關(guān)系與函數(shù)，關(guān)系的性質(zhì)與運(yùn)算

2)等價(jià)關(guān)系，劃分共濟(jì)

3)偏序關(guān)系與偏序集，格輔導(dǎo)

3、計(jì)數(shù)336260 37

1)排列與組合，容斥原理，鴿巢原理共

2)離散概率正門

3)函數(shù)的增長(zhǎng)與遞推關(guān)系院

4、圖論 共濟(jì)網(wǎng)

1)歐拉圖與哈密頓圖，平面圖與對(duì)偶圖，二部圖與匹配，圖的著色021-

2)樹，樹的遍歷，最小生成樹正門

3)最短路經(jīng)，最大流量

5、形式語(yǔ)言與自動(dòng)機(jī) 院

1)語(yǔ)言與文法，正則表達(dá)式與正則集

2)有限狀態(tài)自動(dòng)機(jī)，自動(dòng)機(jī)與正則語(yǔ)言

6、代數(shù)系統(tǒng)

1)二元運(yùn)算，群與半群，積群與商群，同態(tài)與同構(gòu)

2)群與編碼

3)格與布爾代數(shù)，環(huán)與域

三、試卷結(jié)構(gòu)

1、考試時(shí)間為3小時(shí)，滿分100分。

2、題目類型：計(jì)算題、簡(jiǎn)答題和證明題。

參考書

1．離散數(shù)學(xué)，胡新啟，武漢大學(xué)出版社，2007年。

2．離散數(shù)學(xué)，尹寶林、何自強(qiáng)、許光漢、檀鳳琴等，高等教育出版社，1998年。

3．離散數(shù)學(xué)及其應(yīng)用，Kenneth H.Rosen，機(jī)械工業(yè)出版社，2002年。

第二篇：離散數(shù)學(xué)考試范圍

第一部分 簡(jiǎn)單命題符號(hào)化，求主析取范式，判斷公式類型（重言式，矛盾式，可滿足式）量詞消去規(guī)則。命題邏輯推理規(guī)則

帶全稱量詞和存在量詞的命題邏輯推理的構(gòu)造和證明 第二部分

集合基本運(yùn)算，文氏圖 有序?qū)Φ幕局R(shí)，笛卡兒積，特征函數(shù)

函數(shù)的性質(zhì)（單射，滿射，雙射）

集合的基本概念（交集，并集，冪集，定義域，值域）

給出關(guān)系圖，畫出r(R)，s(R)，t(R)等價(jià)關(guān)系及等價(jià)劃分 集合相等證明

從A到B的函數(shù)的性質(zhì)

關(guān)系的性質(zhì)（自反，對(duì)稱，傳遞）偏序關(guān)系和哈斯圖

A卷

1、選擇10題（2*10=20分）

2、填空8題（1*15=15分）

3、綜合題（6題，39分）（1）前束范式

（2）偏序關(guān)系和哈斯圖（3）文氏圖（4）關(guān)系的閉包

（5）用真值表判斷公式的成真賦值（6）量詞消去

4、證明題（3題，共26分）自然推理系統(tǒng)證明（第三章）集合相等證明

命題邏輯推理證明（第五章）B卷

1、填空10題（2*10=20分）

2、選擇10題（1*10=10分）

3、綜合題（6題，44分）（1）主析取范式判斷公式類型（2）量詞消去，求公式真值（3）集合計(jì)算（4）量詞消去（5）前束范式

（6）偏序關(guān)系和哈斯圖

4、推理填空題（8分）

5、證明題（18分）集合相等證明 命題邏輯推理證明

第三篇：上海海事大學(xué)離散數(shù)學(xué)考試提綱

復(fù)習(xí)提綱：

一、判斷哪些是命題

*命題的表示（聯(lián)結(jié)詞），符號(hào)化命題(樣題2)*真值表（用來(lái)證明）

*等價(jià)式的證明（用已知的等價(jià)式推導(dǎo)）(樣題3)蘊(yùn)涵的證明(樣題4)對(duì)偶式（化對(duì)偶式）

*寫出主析（合）取范式（真值表，公式推導(dǎo)）(樣題5)*命題的推理（真值表，直接，間接）(樣體6)

二、*謂詞公式的翻譯（存在，全稱）(p60習(xí)題2,批p61例題,批p62習(xí)題1)約束變?cè)捌鋼Q名(p63例題1)等價(jià)式和蘊(yùn)涵式（轉(zhuǎn)換，擴(kuò)展和收縮，分配，多量詞）(p66-p70)前束范式(p73例題)*推理 p76-p77

三、*集合的表示

*集合的運(yùn)算（。。冪集）*包含排斥

序偶（同集合）

關(guān)系（定義域，值域，特殊的關(guān)系，*關(guān)系的表示,特別是矩陣）*關(guān)系的性質(zhì)（5大性質(zhì)，）

復(fù)合關(guān)系和逆關(guān)系 p114例題1,p115例題5,p118例題4 關(guān)系的閉包運(yùn)算（三個(gè)）p121例題1,p124例題4 集合的劃分和覆蓋（能判斷哪些是劃分和覆蓋）

*等價(jià)關(guān)系（判定，要會(huì)用等價(jià)關(guān)系對(duì)集合劃分即寫出等價(jià)類）p131,132例題, *序關(guān)系（判定，哈斯圖，鏈反鏈）p140,141例題, *求極大（小），最大（小），上（下）界，上（下）確界 p146習(xí)題6

四、*判定是否函數(shù)，滿，入，雙

*逆函數(shù)、復(fù)合函數(shù)（判定原函數(shù)是滿，入，雙復(fù)合后是否滿，入，雙）判定二個(gè)集合是否等勢(shì)（構(gòu)造雙射函數(shù)）有限集，無(wú)限集（可數(shù)，不可數(shù)）

自然數(shù) 實(shí)數(shù)集

可列

五、*代數(shù)運(yùn)算的表示（包括運(yùn)算表）p189例題

*判斷代數(shù)系統(tǒng)的運(yùn)算性質(zhì)：封閉，可交換，可結(jié)合，可分配，吸收率，等冪性 *代數(shù)系統(tǒng)的幺元和零元（唯一性證明），逆元 p184 半群的判斷，獨(dú)異點(diǎn)的判斷

*群與子群的判斷，群的性質(zhì)證明 交換群的性質(zhì)，循環(huán)群的性質(zhì) *定理5-7.1,意義，性質(zhì)

任何一個(gè)群不是4階循環(huán)群就是Klein群

*同構(gòu)同態(tài)的判斷（滿，單一，）p214例題，同余 環(huán)，域判斷，同態(tài)象

六、*格、子格的定義

*并，交運(yùn)算的定義及其性質(zhì) p233例題 p241例題 p242習(xí)題 格的同態(tài)與同構(gòu)

*分配格的性質(zhì)，p244例2,3 ,有補(bǔ)格的性質(zhì)，補(bǔ)元素 p252習(xí)題1 布爾代數(shù)，布爾表達(dá)式及其范式

七、圖簡(jiǎn)單性質(zhì)（點(diǎn)邊數(shù)目關(guān)系），圖的同構(gòu)判斷，生成子圖，補(bǔ)圖 路，回路，通路，連通，點(diǎn)割集（割點(diǎn)），邊割集（割邊）及其性質(zhì)

有向圖的單側(cè)連通（分圖），強(qiáng)連通（分圖），弱連通（分圖）p287習(xí)題8 *圖的矩陣（鄰接，可達(dá)性，完全關(guān)聯(lián)）p290例題1, *歐拉圖的判定，H圖的判定,p306,p310,樣體21平面圖的判定（K3,3 K5）p317習(xí)題5 對(duì)偶圖和著色 p318,p319 p321習(xí)題 *樹的等價(jià)定義和證明

*最小生成樹 p327習(xí)題6 *根樹p327習(xí)題2，叉樹，m叉數(shù)轉(zhuǎn)換成二叉樹

第四篇：離散數(shù)學(xué)考試題型之定理應(yīng)用題

下面我們就列出常用的幾種應(yīng)用：

證明等價(jià)關(guān)系：即要證明關(guān)系有自反、對(duì)稱、傳遞的性質(zhì)。

證明偏序關(guān)系：即要證明關(guān)系有自反、反對(duì)、傳遞的性質(zhì)（特殊關(guān)系的證明就列出來(lái)兩種，要證明剩下的幾種只需要結(jié)合定義來(lái)進(jìn)行）。

證明滿射：函數(shù)f：X?Y，即要證明對(duì)于任意的y?Y，都有x?X，使得f(x)=y。

證明入射：函數(shù)f：X?Y，即要證明對(duì)于任意的x1，x2?X，且x1≠x2，則f(x1)≠f(x2)；或者對(duì)于任意的f(x1)=f(x2)，則有x1=x2。

證證明集合等勢(shì)：即明兩個(gè)集合中存在雙射。有三種情況：第一，證明兩個(gè)具體的集合等勢(shì)，用構(gòu)造法，或者直接構(gòu)造一個(gè)雙射，或者構(gòu)造兩個(gè)集合相互間的入射。

第二，已知某個(gè)集合的基數(shù)，如果為?，就設(shè)它和R之間存在雙射f，然后通過(guò)f的性質(zhì)推出另外的雙射，因此等勢(shì)；如果為?0，則設(shè)和N之間存在雙射。第三，已知兩個(gè)集合等勢(shì)，然后再證明另外的兩個(gè)集合等勢(shì)，這時(shí)，先設(shè)已知的兩個(gè)集合存在雙射，然后根據(jù)剩下題設(shè)條件證明要證的兩個(gè)集合存在雙射。

證明群：即要證明代數(shù)系統(tǒng)封閉、可結(jié)合、有幺元和逆元（同樣，這一部分可以作為證明題的概念更多，要結(jié)合定義把它們?nèi)坷斫馔笍兀?/p>

證明子群：雖然子群的證明定理有兩個(gè)，但如果考證明子群的話，通常是考第二個(gè)定理，即設(shè)是群，S是G的非空子集，如果對(duì)于S中的任意元素a和b有a*b-1?S，則是的子群。對(duì)于有限子群的相關(guān)證明，則可以考慮第一個(gè)定理。

證明正規(guī)子群：若是一個(gè)子群，H是G的一個(gè)子集，即要證明對(duì)于任意的a?G，有aH=Ha，或者對(duì)于任意的h?H，有a-1 *h*a?H。這是最常見的題目中所使用的方法。

證明格和子格：子格沒有條件，因此和證明格一樣，證明集合中任意兩個(gè)元素的最大元和最小元都在集合中。

第五篇：離散數(shù)學(xué)考試試題(A卷及答案)

離散數(shù)學(xué)考試試題（A卷及答案）

一、（10分）判斷下列公式的類型（永真式、永假式、可滿足式）？ 1)((P?Q)∧Q)?((Q∨R)∧Q)2)?((Q?P)∨?P)∧(P∨R)3)((?P∨Q)?R)?((P∧Q)∨R)解：1)永真式；2）永假式；3)可滿足式。

二、（8分）個(gè)體域?yàn)閧1，2}，求?x?y（x+y=4）的真值。

解：?x?y（x+y=4）??x（（x+1=4）∨（x+2=4））

?（（1+1=4）∨（1+2=4））∧（（2+1=4）∨（2+1=4））?（0∨0）∧（0∨1）?1∧1?0

三、（8分）已知集合A和B且|A|=n，|B|=m，求A到B的二元關(guān)系數(shù)是多少？A到B的函數(shù)數(shù)是多少？

解：因?yàn)閨P(A×B)|=2|A×B|=2|A||B|=2mn，所以A到B的二元關(guān)系有2mn個(gè)。因?yàn)閨BA|=|B||A|=mn，所以A到B的函數(shù)mn個(gè)。

四、（10分）已知A={1,2,3,4,5}和R={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>}，求r(R)、s(R)和t(R)。

解：r(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<1,1>,<2,2>,<3,3>,<4,4>,<5,5>} s(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<3,2>,<4,3>,<4,5>} t(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<1,1>,<1,3>,<2,2>,<2,4>,<1,4>}

五、(10分)75個(gè)兒童到公園游樂(lè)場(chǎng)，他們?cè)谀抢锟梢则T旋轉(zhuǎn)木馬，坐滑行鐵道，乘宇宙飛船，已知其中20人這三種東西都乘過(guò)，其中55人至少乘坐過(guò)其中的兩種。若每樣乘坐一次的費(fèi)用是0.5元，公園游樂(lè)場(chǎng)總共收入70元，求有多少兒童沒有乘坐過(guò)其中任何一種。

解 設(shè)A、B、C分別表示騎旋轉(zhuǎn)木馬、坐滑行鐵道、乘宇宙飛船的兒童組成的集合，|A∩B∩C|＝20，|A∩B|＋|A∩C|＋|B∩C|－2|A∩B∩C|＝55，|A|＋|B|＋|C|＝70/0.5＝140。

由容斥原理，得

|A∪B∪C|＝|A|＋|B|＋|C|―|A∩B|―|A∩C|―|B∩C|＋|A∩B∩C| 所以

|A∩B∩C|＝75－|A∪B∪C|＝75－(|A|＋|B|＋|C|)＋(|A∩B|＋|A∩C|＋|B∩C|－2|A∩B∩C|)＋|A∩B∩C|＝75－140＋55＋20＝10 沒有乘坐過(guò)其中任何一種的兒童共10人。

六、（12分）已知R和S是非空集合A上的等價(jià)關(guān)系，試證：1）R∩S是A上的等價(jià)關(guān)系；2）對(duì)a∈A，[a]R∩S=[a]R∩[a]S。

解：?x∈A，因?yàn)镽和S是自反關(guān)系，所以∈R、∈S，因而∈R∩S，故R∩S是自反的。

?x、y∈A，若∈R∩S，則∈R、∈S，因?yàn)镽和S是對(duì)稱關(guān)系，所以因∈R、∈S，因而∈R∩S，故R∩S是對(duì)稱的。?x、y、z∈A，若∈R∩S且∈R∩S，則∈R、∈S且∈R、∈S，因?yàn)镽和S是傳遞的，所以因∈R、∈S，因而∈R∩S，故R∩S是傳遞的。

總之R∩S是等價(jià)關(guān)系。

2）因?yàn)閤∈[a]R∩S?∈R∩S?∈R∧∈S? x∈[a]R∧x∈[a]S? x∈[a]R∩[a]S 所以[a]R∩S=[a]R∩[a]S。

七（10分）設(shè)A、B、C、D是集合，f是A到B的雙射，g是C到D的雙射，令h：A×C?B×D且?∈A×C，h()＝。證明h是雙射。

證明：1）先證h是滿射。

?∈B×D，則b∈B，d∈D，因?yàn)閒是A到B的雙射，g是C到D的雙射，所以存在a∈A，c∈C，使得f(a)=b，f(c)=d，亦即存在∈A×C，使得h()＝＝，所以h是滿射。

2）再證h是單射。

?、∈A×C，若h()＝h()，則＝，所以f(a1)＝f(a2)，g(c1)＝g(c2)，因?yàn)閒是A到B的雙射，g是C到D的雙射，所以a1＝a2，c1＝c2，所以＝，所以h是單射。綜合1）和2），h是雙射。

八、（12分）是個(gè)群，u∈G，定義G中的運(yùn)算“?”為a?b=a*u-1*b，對(duì)任意a,b∈G，求證：也是個(gè)群。

證明：1）?a,b∈G，a?b=a*u-1*b∈G，運(yùn)算是封閉的。

2）?a,b,c∈G，（a?b）?c=（a*u-1*b）*u-1*c=a*u-1*（b*u-1*c）=a?（b?c），運(yùn)算是可結(jié)合的。3）?a∈G，設(shè)E為?的單位元，則a?E=a*u-1*E=a，得E=u，存在單位元。

4）?a∈G，a?x=a*u-1*x=E，x=u*a-1*u，則x?a=u*a-1*u*u-1*a=u=E，每個(gè)元素都有逆元。所以也是個(gè)群。

九、（10分）已知：D=，V={1,2,3,4,5}，E={<1,2>,<1,4>,<2,3>,<3,4>,<3,5>,<5,1>}，求D的鄰接距陣A和可達(dá)距陣P。

解：D的鄰接距陣A和可達(dá)距陣P如下：

A= 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 1 0 0

0 0 1 0 0

P= 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1

十、（10分）求葉的權(quán)分別為2、4、6、8、10、12、14的最優(yōu)二叉樹及其權(quán)。

解：最優(yōu)二叉樹為

權(quán)＝148

離散數(shù)學(xué)考試試題（B卷及答案）

一、（10分）求命題公式?(P∧Q)??(?P?R)的主合取范式。

解：?(P∧Q)??(?P?R)?（?(P∧Q)??(?P?R)）∧（?(?P?R)??(P∧Q)）?（(P∧Q)∨(?P∧?R)）∧（(P∨R)∨(?P∨?Q)）?(P∧Q)∨(?P∧?R)?(P∨?R)∧（Q∨?P）∧（Q∨?R）

?(P∨Q∨?R)∧(P∨?Q∨?R)∧（?P∨Q∨R）∧（?P∨Q∨?R）?M1∧M3∧M4∧M5

二、（8分）敘述并證明蘇格拉底三段論

解：所有人都是要死的，蘇格拉底是人，所以蘇格拉底是要死的。符號(hào)化：F（x）：x是一個(gè)人。G（x）：x要死的。A：蘇格拉底。命題符號(hào)化為?x（F（x）?G（x）），F(xiàn)（a）?G（a）證明：

（1）?x(F(x)?G(x))P（2）F(a)?G(a)T(1),US（3）F(a)P（4）G(a)T(2)(3),I

三、（8分）已知A、B、C是三個(gè)集合，證明A∩(B∪C)=(A∩B)∪(A∩C)證明：∵x? A∩（B∪C）? x? A∧x?（B∪C）

? x? A∧（x?B∨x?C）

?（x? A∧x?B）∨（x? A∧x?C）? x?（A∩B）∨x? A∩C ? x?（A∩B）∪（A∩C）

∴A∩（B∪C）=（A∩B）∪（A∩C）

四、（10分）已知R和S是非空集合A上的等價(jià)關(guān)系，試證：1）R∩S是A上的等價(jià)關(guān)系；2）對(duì)a∈A，[a]R∩S=[a]R∩[a]S。

解：?x∈A，因?yàn)镽和S是自反關(guān)系，所以∈R、∈S，因而∈R∩S，故R∩S是自反的。

?x、y∈A，若∈R∩S，則∈R、∈S，因?yàn)镽和S是對(duì)稱關(guān)系，所以因∈R、∈S，因而∈R∩S，故R∩S是對(duì)稱的。

?x、y、z∈A，若∈R∩S且∈R∩S，則∈R、∈S且∈R、∈S，因?yàn)镽和S是傳遞的，所以因∈R、∈S，因而∈R∩S，故R∩S是傳遞的。

總之R∩S是等價(jià)關(guān)系。

2）因?yàn)閤∈[a]R∩S?∈R∩S?

∈R∧∈S? x∈[a]R∧x∈[a]S? x∈[a]R∩[a]S 所以[a]R∩S=[a]R∩[a]S。

五、(10分)設(shè)A＝{a，b，c，d}，R是A上的二元關(guān)系，且R＝{，，，}，求r(R)、s(R)和t(R)。

解 r(R)＝R∪IA＝{，，，，，，，} s(R)＝R∪R＝{，，，，，} R＝{，，，} R＝{，，，} R＝{，，，}＝R

t(R)＝?R＝{，，，，，，，，} i?1?i

4232-

1六、(15分)設(shè)A、B、C、D是集合，f是A到B的雙射，g是C到D的雙射，令h：A×C?B×D且?∈A×C，h()＝。證明h是雙射。

證明：1）先證h是滿射。

?∈B×D，則b∈B，d∈D，因?yàn)閒是A到B的雙射，g是C到D的雙射，所以存在a∈A，c∈C，使得f(a)=b，f(c)=d，亦即存在∈A×C，使得h()＝＝，所以h是滿射。

2）再證h是單射。

?、∈A×C，若h()＝h()，則＝，所以f(a1)＝f(a2)，g(c1)＝g(c2)，因?yàn)閒是A到B的雙射，g是C到D的雙射，所以a1＝a2，c1＝c2，所以＝，所以h是單射。

綜合1）和2），h是雙射。

七、(12分)設(shè)是群，H是G的非空子集，證明是的子群的充要條件是若a，b?H，則有a*b?H。

證明：? ?a,b∈H有b∈H，所以a*b∈H。??a∈H，則e=a*a∈H-1-

1-1-1a=e*a∈H ∵a,b∈H及b∈H，∴a*b=a*（b）∈H ∵H?G且H≠?,∴*在H上滿足結(jié)合律 ∴是的子群。

八、（10分）設(shè)G=是簡(jiǎn)單的無(wú)向平面圖，證明G至少有一個(gè)結(jié)點(diǎn)的度數(shù)小于等于5。

解：設(shè)G的每個(gè)結(jié)點(diǎn)的度數(shù)都大于等于6，則2|E|=?d(v)≥6|V|，即|E|≥3|V|，與簡(jiǎn)單無(wú)向平面圖-

1-1

-1-1-1的|E|≤3|V|-6矛盾，所以G至少有一個(gè)結(jié)點(diǎn)的度數(shù)小于等于5。九.G=,A={a,b,c},*的運(yùn)算表為：(寫過(guò)程，7分)

（1）G是否為阿貝爾群？

（2）找出G的單位元；（3）找出G的冪等元（4）求b的逆元和c的逆元 解：（1）(a*c)*(a*c)=c*c=b=a*b=(a*a)*(c*c)(a*b)*(a*b)=b*b=c=a*c=(a*a)*(b*b)(b*c)*(b*c)=a*a=a=c*b=(b*b)*(c*c)所以G是阿貝爾群

（2）因?yàn)閍*a=a a*b=b*a=b a*c=c*a=c 所以G的單位元是a（3）因?yàn)閍*a=a 所以G的冪等元是a（4）因?yàn)閎*c=c*b=a，所以b的逆元是c且c的逆元是b

十、(10分)求葉的權(quán)分別為2、4、6、8、10、12、14的最優(yōu)二叉樹及其權(quán)。

解：最優(yōu)二叉樹為

權(quán)＝148 5