第一篇：(11122)(離散數學)復習大綱(20120605)
《離散數學》復習大綱
《離散數學》復習大綱
考試時：允許帶計算器，不允許帶手機。
題型：單選題（10個*2分=20分），填空題（5個*3分=15分），大題（8個，每個分值不等，共計65分）
緒論
1、判斷一句話是否是命題（P2）
2、繪制真值表（P2,P3,P4,P5）
第1章：集合1.掌握以下概念：元素、集合、子集，元素與集合的關系（屬于或不屬于），集合之間的關系（包含于或不包含于）。
2.求冪集，計算冪集的基數。（P28—34，P28—35，P28—36，P28—37，P28—38）
3.利用文氏圖求集合的基數（P29—60，P28—48）
第2章：關系與函數
1.判斷某個映射是否是函數（P43），判斷某個函數是否有反函數（P52—33）
2.判斷某個關系是否具有自反性、對稱性、反對稱性、傳遞性（P50—13）
3.等價關系與劃分之間的轉換（P50—13）
第3章：布爾代數
1.求出某個布爾代數中某個定理的對偶定理（P74）
2.十進制、二進制、八進制之間的轉換（P78，P82—14，P82—15，P82—19）
3.根據電路圖，寫出布爾表達式，對布爾表達式進行化簡，畫出簡化之后的電路圖。（P84—53，P85—54）
第4章：自然數與歸納法：
1、使用數學歸納法進行等式、不等式、整除式的證明（P122—2，P122—3，P122—6，P122—8，P122—11，P124—39，P123—22，P124—40）
第5章：數論
1.使用歐幾里德算法進行反推（P152—例子）
2.求解模數方程（P166—9，P166—10）
3.位移加密、摩爾加密的加密解密過程（P167—26，P167—27，P167—28，P167—30）
4.5.6.7.利用快速求冪算法計算余數（P167—25）求解歐拉函數Φ函數（P166—16）利用歐拉函數Φ函數進行因式分解（P166—15）RSA加密的加密解密過程（P167—31，P167—32）
第6章：遞歸：
1、使用折半查找法在某個指定數組中查找某個元素時，得出查找成功或者不成功的結果時經歷的查找過程。（P207—例子）
第7章：遞歸式求解：
1、遞歸式求解（P234—5，P234—6，P234—11）
第8章：計數：
1、當從一幅標準撲克（52張）中選出一手牌（5張）時，計算出這手牌呈現某種特點（例如：一對、兩對、一滾、一連、一滾加一對、同花、順子、同花順等等）的概率。（該題可能需要使用計算器）（P252）
第9章：矩陣
1.矩陣加法（P276—方框）
2.矩陣乘法（P277—最后的例子）
3.給出與方程組對應的矩陣方程（P280—方框）
4.矩陣對應的行列式的值（P282—第一個矩陣，P282—方框）
5.利用克萊姆法則求解方程組（P283—例子，P283—方框）
6.利用矩陣加密解密，其中要用到高斯消去法（P287，P288，P289）
第10章：圖論
1.歐拉路徑和歐拉回路的判斷（P329—圖）
2.判斷圖形是否能“一筆畫出”（P329—圖）
3.利用Prim算法求出最小生成樹（P330—圖，P332—4，P332—13）
4.利用Kruskal算法求出最小生成樹（P330—圖，P332—4，P332—13）
2012-3-12唐斌
第二篇：離散數學復習重點
離散數學復習重點：
1、集合的運算以及運算律；
2、關系的三種表示方法，以及他們之間的轉化；
3、常見關系的定義；
4、哈斯圖的畫法，以及最大最小元、極大極小元、上下界，上下確界的求法；
5、單射、滿射以及雙射的證明（尤其是在代數系統中）；
6、代數系統的概念以及代數系統的常用性質，能夠證明具體的代數系統的運算律，找出單
位元，零元、以及逆元等；
7、環和格只要記住不同的環和格滿足的運算律就好；
8、各種圖和樹的概念及相關的結論，比如：歐拉圖的充要條件，哈密頓圖的充分條件、必
要條件、充要條件等；
9、圖的矩陣計算；
10、會畫一些簡單的樹；
11、五種聯結詞的真值表；
12、一些要求記住的命題公式；
13、命題公式的證明；
14、命題公式的析取范式，合取范式，主析取范式和主合取范式的求法。
題型：填空題、證明題和解答題。
友情提醒：
1、周三下午一點半到三點半在逸夫樓519答疑。
2、概念、定理和公式請務必記住，可能會出填空題；
3、考試內容不會超出我們的重點；
請大家好好復習，爭取一次性通過。
第三篇：《離散數學》期末復習
《離散數學》期末復習
內容：第一章~第七章 題型：
一、選擇題（20%，每題2分）二．填空題（20%，每題2分）
三、計算題（20%，每題5分）
四、證明題（20%，每題5分）
五、判斷題（20%，每題2分）
第1章 數學語言與證明方法
1.1 常用的數學符號
1.計算常用的數學符號式子 1.2 集合及其表示法
1.用列舉法和描述法表示集合
2.判斷元素與集合的關系(屬于和不屬于)3.判斷集合之間的包含與相等關系，空集(E)，全集(?)4.計算集合的冪集
5.求集合的運算：并、交、相對補、對稱差、絕對補
6.用文氏圖表示集合的運算 7.證明集合包含或相等
方法一： 根據定義, 通過邏輯等值演算證明
方法二： 利用已知集合等式或包含式, 通過集合演算證明
1.3 證明方法概述
1、用如下各式方法對命題進行證明。? 直接證明法：A?B為真
? 間接證明法：“A?B為真” ? “ ?B? ?A為真” ? 歸謬法(反證法)： A??B?0為真
? 窮舉法： A1?B, A2?B,…, Ak?B 均為真
? 構造證明法：在A為真的條件下, 構造出具有這種性質的客體B ? 空證明法：“A恒為假” ? “A?B為真” ?平凡證明法：“B恒為真” ? “A?B為真” ? 數學歸納法： 第2章 命題邏輯
2.1 命題邏輯基本概念
1、判斷句子是否為命題、將命題符號化、求命題的真值（0或1）。
命題的定義和聯結詞(?, ?, ?, ?, ?)
2、判斷命題公式的類型
賦值或解釋.成真賦值,成假賦值；重言式(永真式)、矛盾式(永假式)、可滿足式:。2.2 命題邏輯等值演算
1、用真值表判斷兩個命題公式是否等值
2、用等值演算證明兩個命題公式是否等值
3、證明聯結詞集合是否為聯結詞完備集 2.3 范式
1、求命題公式的析取范式與合取范式
2、求命題公式的主析取范式與主合取范式（兩種主范式的轉換）
3、應用主析取范式分析和解決實際問題 2.4 命題邏輯推理理論
1、用直接法、附加前提、歸謬法、歸結證明法等推理規則證明推理有效 第3章 一階邏輯
3.1 一階邏輯基本概念
1、用謂詞公式符號命題（正確使用量詞）
2、求謂詞公式的真值、判斷謂詞公式的類型 3.2 一階邏輯等值演算
1、證明謂詞公式的等值式
2、求謂詞公式的前束范式 第4章 關系
4.1 關系的定義及其表示
1、計算有序對、笛卡兒積
2、計算給定關系的集合
3、用關系圖和關系矩陣表示關系 4.2 關系的運算
1、計算關系的定義域、關系的值域
2、計算關系的逆關系、復合關系和冪關系
3、證明關系運算滿足的式子 4.3 關系的性質
1、判斷關系是否為自反、反自反、對稱、反對稱、傳遞的2、判斷關系運算與性質的關系
3、計算關系自反閉包、對稱閉包和傳遞閉包 4.4 等價關系與偏序關系
1、判斷關系是否為等價關系
2、計算等價關系的等價類和商集
3、計算集合的劃分
4、判斷關系是否為偏序關系
5、畫出偏序集的哈期圖
6、求偏序集的最大元、最小元、極小元、極大元、上界、下界、上確界、下確界
7、求偏序集的拓撲排序 第5章 函數
1.判斷關系是否為函數 2.求函數的像和完全原像
3.判斷函數是否為滿射、單射、雙射 4.構建集合之間的雙射函數 5.求復合函數
6.判斷函數的滿射、單射、雙射的性質與函數復合運算之間的關系 7.判斷函數的反函數是否存在，若存在求反函數 第6章 圖
1.指出無向圖的階數、邊數、各頂點的度數、最大度、最小度
2.指出有向圖的階數、邊數、各頂點的出度和入度、最大出度、最大入度、最小出度最小入出度
3.根據握手定理頂點數、邊數等
4.指出圖的平行邊、環、弧立點、懸掛頂點和懸掛邊 5.判斷給定的度數列能否構成無向圖
6.判斷圖是否為簡單圖、完全圖、正則圖、圈圖、輪圖、方體圖 7.求給定圖的補圖、生成子圖、導出子圖 8.判斷兩個圖是否同構 6.2 圖的連通性
1.求圖中給定頂點通路、回路的距離
2.計算無向圖的連通度、點割集、割點、邊割集、割邊 3.判斷有向圖的類型：強連通圖、單向連通圖、弱連通圖 6.3 圖的矩陣表示
1.計算無向圖的關聯矩陣 2.計算有向無環圖的關聯矩陣 3.計算有向圖的鄰接矩陣 4.計算有向圖的可達矩陣
5.計算圖的給定長度的通路數、回路數 6.4 幾種特殊的圖
1、判斷無向圖是否為二部圖、歐拉圖、哈密頓圖 第7章 樹及其應用 7.1 無向樹
1.判斷一個無向圖是否為樹
2.計算無向樹的樹葉、樹枝、頂點數、頂點度數之間的關系 3.給定無向樹的度數列，畫出非同構的無向樹 4.求生成樹對應的基本回路系統和基本割集系統 5.求最小生成樹 7.2 根樹及其應用
1.判斷一個有向圖是否為根樹
2.求根樹的樹根、樹葉、內點、樹高 3.求最優樹
4.判斷一個符號串集合是否為前綴碼 5.求最佳前綴碼
6.用三種方法遍歷根樹
第四篇：離散數學復習要點
離散數學復習要點
題型：選擇題、填空題、計算和證明題
(不用擔心，考題不難，都是平時上課講過的內容)
命題邏輯：
命題的判定和符號化（即命題的翻譯）.會畫命題公式的真值表.理解成真賦值，小項.含n個變元的不等價的命題公式有多少類.求公式的主合取范式和主析取范式.熟悉命題的等價公式(命題定律)和蘊涵公式(推理定律).謂詞邏輯:
命題的符號化，即帶量詞的謂詞公式的翻譯，包括一元謂詞和二元謂詞的翻譯.謂詞公式中量詞的作用域.會求謂詞公式的前束范式.謂詞邏輯中推理的證明(P,T規則 + EI,EG,UI,UG規則).集合與關系:
子集概念，會求冪集，會求冪集中元素個數.會求兩個集合的笛卡爾積.關系的性質：（反）自反性，（反）對稱性，傳遞性。弄清定義，會判斷。會求復合關系、逆關系.會求自反/對稱/傳遞閉包.會證明等價關系.等價關系與劃分的相互轉化.圖論：
基本概念: 簡單圖，多重圖，零圖，n階完全圖，結點的度.握手定理及推論:圖的度數之和=邊數的兩倍,邊數=圖的出度和=圖的入度和.無向圖的連通性.會判斷有向圖的強連通，單側連通，弱連通性.會求圖（包括零圖，完全圖等）的點連通度、邊連通度.由鄰接矩陣求結點的入度、出度，由鄰接矩陣的冪求結點間長度為k的路的數目.歐拉圖的判定.哈密頓圖的判定: 理解必要條件；會證明充分條件.好好復習!預祝成功!
第五篇：大學離散數學復習試題
離散數學練習題目
一、選擇題
1．設A={{1，2，3}，{4，5}，{6，7，8}}，下列各式中____D______是錯的。
A、??A； B、{6，7，8}?A； C、{{4，5}}?A； D、{1，2，3}?A。
2.已知集合A={a,b,c},B={b,c,e},則 A⊕B=___C___________ A.{a,b} B={c} C={a,e} D=φ
3.下列語句中，不是命題的是____A_________ A.我說的這句話是真話； B.理發師說“我說的這句話是真話”； C.如果明天下雨，我就不去旅游； D.有些煤是白的，所以這些煤不會燃燒；
4.下面___D______命題公式是重言式。
A.P?Q?R ； B.(P?R)?(P?Q)；C.(P?Q)?(Q?R)；
D、(P?(Q?R))?((P?Q)?(P?R))。
5.公式(p∧q)∨(p∧～q)的主析取范式是____B_______ A.m1∨m2 B.m2∨m3 C.m0∨m2 D.m1∨m3
6．設L(x)：x是演員，J(x)：x是老師，A(x , y)：x欽佩y，命題“所有演員都欽佩某些老師”符號化為___D______。
A、?x(L(x)?A(x,y))； B、?x(L(x)??y(J(y)?A(x,y)))； C、?x?y(L(x)?J(y)?A(x,y))； D、?x?y(L(x)?J(y)?A(x,y))。7.關于謂詞公式（x）(y)(P(x,y)∧Q(y,z))∧(x)p(x,y),下面的描述中錯誤的是__B_____ A．（x）的轄域是（y）（P（x,y）∧Q(y,z)）
B．z是該謂詞公式的約束變元
C．（x）的轄域是P（x,y）D．x是該謂詞公式的約束變元 8． 設S?A?B，下列各式中____B___________是正確的。
A、domS?B ； B、domS?A； C、ranS?A； D、domS ? ranS = S。9．設集合X??，則空關系?X不具備的性質是____A________。
A、自反性； B、反自反性； C、對稱性； D、傳遞性。
10.集合A，R是A上的關系，如果R是等價關系，則R必須滿足的條件是__D___ A.R是自反的、對稱的 B.R是反自反的、對稱的、傳遞的 C.R是自反的、對稱的、不傳遞的 D.R是自反的，對稱的、傳遞的 11.集合A={a,b,c,d},B={1,2,3},則下列關系中__ACD______是函數
A.R={(a,1),(b,2),(c,1),(d,2)} B.R={(a,1),(a,2),(c,1),(d,2)} C.R={(a,3),(b,2),(c,1)} D.R={(a,1),(b,1),(c,1),(d,1)} ????已知集合???????????? R?A,且R={(1,2),(1,2),(2,1),(2,2),(2,3),(2,4),(3,4),(4,1)},則頂點2的入度和出度分別是___D_______ A.2,3 B.2,4 C.3,3 D.3,4 13.設完全圖Kn有n個結點(n≥2)，m條邊，當下面條件__C____滿足時，Kn中存在歐拉回路．
A．m為奇數 B．n為偶數 C．n為奇數 D．m為偶數 14.下面敘述正確的是____B______ A.二部圖K3,3是歐拉圖 B.二部圖是平面圖
K3,3是哈密爾頓圖
C.二部圖 K3,32
D.二部圖K3,3是既不是歐拉圖也不哈密爾頓圖
15.已知某平面圖的頂點數是12，邊數是14，則該平面圖有__D___個面 A.3 B.2 C.5 D.4 16．設G是n個結點、m條邊和r個面的連通平面圖，則m等于___A____。
A、n+r-2 ； B、n-r+2 ； C、n-r-2 ； D、n+r+2。17.下面幾種代數結構中，不是群的是___D____ A.
二、問答題
1.在程序設計過程中，有如下形式的判斷語句： if(a>=0)if(b>1)if(c<0)cout< 請將這段程序化簡，并說明化簡的理由。解：簡化的程序： if(a>=0 && b>1 && c<0)cout< 設置命題變量： p: a>=0；q:b>1;r:c<0;s:cout< A=P→(q→(r→s))經過等值演算可得，A與下面的公式是等值的 P∧q∧r→s 2.集合A={ 1, 2, 3, 4, 5, 6, 7, 8, 9 }，R={(x,y)| x|y}, ①證明R是偏序關系。 ②寫出偏序集（A，R）的極小元、極大元；最小元、最大元 ③寫出A的子集B={1,2,3,6}的最小上界、最大下界 解：①根據整除性質可知，R滿足自反性，反對稱性，傳遞性。所以R是A上的偏序關系。 ②偏序集（A，R）的極小元：1，極大元：5, 6，7，8，9 最小元：1； 最大元：無 ③子集B={1,2,3,6}的最小上界：6 子集B={1,2,3,6}的最大下界：1 3.(1)m個男孩子，n個女孩排成一排，任何兩個女孩不相鄰，有多少種排法？ (n<=m)插空問題 (2)如果排成一個園環，又有多少種排法？ 解：(1)考慮5個男孩，5個女孩的情況 男孩的安排方法： _B_B_B_B_B_ 排列總數P(5,5)女孩的安排方法：6個位置安排5個女孩，排列中數 P(6,5)所以：總的排列方法數是 m!*p(m+1,n) (2)考慮男孩的圓排列情況，結果是(m-1)!*p(m,n) 4.某商家有三種品牌的足球，每種品牌的足球庫存數量不少于10只，如果我想買5只足球，有多少種買法？如果每種品牌的足球最少買一只，有多少種買法？ 解：①這是一個多重集的組合問題 類別數是k=3，選取的元素個數是 r=5 多重集組合數的計算公式是 N?所以：N=C(3+5-1,5)=c(7,5)=21 ②可自由選取的球只有2個 k=3,r=2 N=C(3+2-1,2)=C(4,2)=6 (r?k?1)!?C(k?r?1,r) r!(k?1)! 5．某軟件公司將職工分為三種崗位。該公司65人，有些職工（例如項目管理人員、設計人員）可能從事不止一個崗位的工作。每個職工至少被分在一個崗位?，F在軟件設計崗位（崗位A）（包括需求分析、概要設計和詳細設計等工作）的人數是15人，代碼編寫崗位（崗位B）的人數是32人，軟件測試崗位（崗位C）的人數是28人，同時參加崗位A和崗位B的有12人, 同時參加崗位B和崗位C的有8人, 同時參加崗位A和崗位C組的有3人，問，三個崗位參加的有多少人？ 解： 已知 |A|=15，|B|=32，|C|=28，|A∩B|=12，|B∩C|=8，|A∩C|=3 設S表示全班同學總人數，則 |S|=65 求：|A∩B∩C|=？ 根據容斥原理： |A∪B∪C|=|A|+|B|+|C|-|A∩B|-|B∩C|-|A∩C|+|A∩B∩C| 所以|A∩B∩C|=|A∪B∪C|-|A|-|B|-|C|+|A∩B|+|B∩C|+|A∩C| 因為每個同學至少參加一個小組，所以：|A∪B∪C|=|S| 因此：|A∩B∩C|=65-15-32-28+12+8+3=13 答：三個小組都參加的人數是13人 6.證明組合恒等式C(n,r)= C(n-1,r-1)+ C(n-1,r) 說明：也可以直接利用組合演算公式進行演算 7.求1228的個位數是多少? 解：1228的個位數就是1228 mod 10的余數1228mod10?(12mod10)28mod10?24*7mod10?(27mod10)4mod10?8mod10?64 8.已知圖G有10條邊, 4個3度頂點, 其余頂點的度數均小于2, 問G至少有多少個頂點? 解：由握手定理∑d(v)=2m=20，度數為3的頂點有3個占去12度，還有8度由其余頂點占有，而由題意，其余頂點的度數可為0，1，當均為1時所用頂點數最少，所以應有8個頂點占有此8度，即G中至少有8+4=12個頂點。 9刑偵人員審一件盜竊案時，已經掌握的線索如下：（1）甲或乙盜竊了電腦。 （2）若甲盜竊了電腦，則作案時間不能發生在午夜前。（3）若乙證詞正確，則在午夜時屋里燈光未滅。（4）若乙證詞不正確，則作案時間發生在午夜前。（5）午夜時屋里燈光滅了。 請通過命題邏輯推理，推論出誰是真正的盜竊犯？（寫出詳細的推理步驟）解 設p： 甲盜竊了電腦，q： 乙盜竊了電腦，r： 作案時間發生在午夜前，s： 乙證詞正確，t：午夜時屋里燈光滅了。 前提： p∨q，p→~r，s→~t，~s→r，t(7)非p。。 10.插入排序算法的時間T與數據規模n的遞推關系如下，求出T與n的顯示關系表達式 ?T(n)?T(n?1)?n?1 ??T(1)?0 解： ??T(n)?T(n?1)?n?1 ??T(n?2)?n?2?n?1???T(n?3)?n?3?n?2?n?1 ?????T(n?k)?n?k???n?2?n?1??T(n?k)?kn-(1?2??k)??k(k?1)??T(n?k)?kn?2?令n-k=1，那么 k=n-1，所以： n(n?1)n(n?1)n(n?1)? T(n)?T(1)??0???222?答：T與n的顯示關系是：T(n)? 11.解下列一階同余方程組 n(n?1)2x?1(mod 3)x?2(mod 4)x?3(mod 5)解：已知a1?1,a2?2,a3?3;m1?3,m2?4,m3?5 方程組的齊次通解是：x?k?Lcm(1,2,3)?6k 60k 根據中國剩余定理，特解是： x0?a1M1(M1mod m1)?a2M2(M2mod m2)?a3M3(M3mod m3)M1?m2m3?20,M2?m1m3?15,M3?m1m2?12 ?1?1?1M1mod m1是下列同余方程的解 3)，解得：x=2，即M1?2 M1x?1(mod m1)即20x?1(mod?1?1同理可解得：M2?3，M3?3 ?1?1 7 x0?a1M1(M1mod m1)?a2M2(M2mod m2)?a3M3(M3mod m3)mod m?（1?20?2?2?15?3?3?12?3）mod 60?1?1?1所以：?(40?90?108)mod 60?238mod 6058 同余方程組的解是 x?x?x0?6k?58 60k 12.假設需要加密的明文數據是a=8,選取兩個素數p=7,q=19,使用RSA算法： ① 計算出密鑰參數 ② 利用加密算法計算出密文c ③ 利用解密算法根據密文c反求出明文a 解：① 取 p=7,q=19;計算 n=p*q=7*19=133 計算φ(n)=(p-1)*(q-1)=(7-1)*(19-1)=108 選取較小的數w,使w與108互質, 5是最小的,于是w=5 計算d,使d*w≡1(mod φ(n)),即d*5 mod 108=1,取d=65，d*5除以108余數為1, 于是算出d=65 至此加密、解密參數計算完成： 公鑰w=5,n=133.私鑰d=65,n=133.② 加密 c?mwmodn?85mod133?((82mod133)*(83mod133))mod133 ?(64*113)mod133?50③ 解密 a?cdmodn?5065mod133 a?A0?A6 其中，A0?50, Ai?(Ai?1)2 根據上述遞推公式可以計算出：A1?502mod133?106,A2?1062mod133?64 A3?642mod133?106，??, A6?1062mod133?64 a?A0?A6?(50*64)mod133?8 解密后的明文與原來的明文是相等的，所以算法正確。 13.設A={1，2，3，4，6，9，12，24},R定義為R?{(a,b)|a?b(mod 3)}，（1）證明R是一個等價關系；（2）寫出A的商集； 14.基于字典序的組合生成算法 問題說明：假設我們需要從5個元素中選取3個的所有組合，已知組合個數為 C（５，３）＝１０，按字典序，其具體組合為： 123,124,125,134,135,145,234,235,245,345 所謂按字典序生成組合，就是已知當前的組合（例如135），求下一個組合（例如，145）。下面給出算法的函數頭： //數組s[]:函數運行前，保存當前的組合，函數結束后，是新生成的下一個組合 //n,r:表示從n個元素中選取r個元素的組合 void next_comb(int s[],int n,int r)解： void next_comb(into s[],int n,int r){ int j,m,max_val; max_val=n; m=r; while(s[m]==max_val) { m=m-1; max_val=max_val-1; } s[m]=s[m]+1; for(j=m+1;j s[j]=s[j-1]+1;} 15.某單位要從A,B,C三人選派若干人出國考察, 需滿足下述條件:(1)若A去, 則C必須去;(2)若B去, 則C不能去;(3)A和B必須去一人且只能去一人.問有幾種可能的選派方案? 9
點擊咨詢 