離散數(shù)學(xué)內(nèi)容總結(jié)第一篇數(shù)理邏輯第1章命題邏輯求命題公式的主析取范式及主合取范式例求的主析取范式及主合取范式。例求(P→Q)R的主析取范式及主合取范式。例求命題公式的主析取范式和主合取范式。例求公式A=(p??q)?r的主析取范式與主合取范式。例求的主析取范式。判斷公式類型例用等值演算法判斷公式qù?(p?q)的類型例判斷下列命題公式的類型（永真式、永假式、可滿足式）,方法不限。(1)(2)證明例證明:
例證明:
例推證:
Q∧(P→Q)

P例前提：
,結(jié)論：
。該結(jié)論是否有效？請(qǐng)說明原因。在命題邏輯中構(gòu)造下面推理的證明:例如果小張守第一壘并且小李向B隊(duì)投球,則A隊(duì)獲勝?；蛘逜隊(duì)未獲勝,或者A隊(duì)成為聯(lián)賽的第一名。小張守第一壘。A隊(duì)沒有成為聯(lián)賽的第一名。因此小李沒有向B隊(duì)投球。例一個(gè)公安人員審查一件盜竊案,已知下列事實(shí)：（1）甲或乙盜竊了錄像機(jī)；（2）若甲盜竊了錄像機(jī),則作案時(shí)間不能發(fā)生在午夜前；（3）若乙的證詞正確,則午夜時(shí)屋里燈光未滅；（4）若乙的證詞不正確,則作案時(shí)間發(fā)生在午夜前；（5）午夜時(shí)屋里燈光滅了。根據(jù)以上事實(shí),推斷誰是盜竊犯。（在命題邏輯中構(gòu)造推理證明。）例如果今天是周一,則要進(jìn)行離散數(shù)學(xué)或C語言程序設(shè)計(jì)兩門課中一門課的考試。如果C語言程序設(shè)計(jì)課的老師有會(huì),則不考C語言程序設(shè)計(jì)。今天是周一,C語言程序設(shè)計(jì)課的老師有會(huì),所以進(jìn)行離散數(shù)學(xué)課的考試。例若明天是星期一或星期三,我就有課。若有課,今天必須備課。我今天沒備課。所以,明天不是星期一和星期三。例若明天是周一或周二,小華就要考試。若要考試,今天必須復(fù)習(xí)。小華今天沒復(fù)習(xí)。所以,明天不是周一和周二。例如果A工作努力,B或C將生活愉快。如果B生活愉快,那么A將不努力工作。如果D愉快,則C將不愉快。所以,如果A工作努力,D將不愉快。第2章謂詞邏輯求謂詞公式的前束范式例求謂詞公式的前束范式例求公式?xF(x)∧?xG(x)的前束范式。證明例證明:﹁
x(A(x)∧B(x))

x(A(x)→﹁B(x))在一階邏輯中符號(hào)化下述命題,并推證之。例凡人必有一死,蘇格拉底是人,所以蘇格拉底會(huì)死的。凡人都會(huì)犯錯(cuò),小王是人,所以小王會(huì)犯錯(cuò)。所有三角形其內(nèi)角和為180度?！鰽BC是三角形。所以△ABC內(nèi)角和為180度。所有的有理數(shù)均可以表示成分?jǐn)?shù)。0.3是有理數(shù)。所以0.3可以表示成分?jǐn)?shù)。偶數(shù)都可以被2整除,6是偶數(shù)。所以6可以被2整除。哲學(xué)家都善于思考。柏拉圖是哲學(xué)家。所以,柏拉圖善于思考。例東北人都不怕冷,王國(guó)端怕冷。所以王國(guó)端不是東北人。非洲人都不怕熱,瑪麗怕熱。所以瑪麗不是非洲人。凡奇數(shù)均不能被2整除,8能被2整除。所以8不是奇數(shù)。凡奇數(shù)均不能被2整除,36能被2整除。所以36不是奇數(shù)。英語系學(xué)生都不學(xué)離散數(shù)學(xué),小劉學(xué)離散數(shù)學(xué)。因此,小劉不是英語系學(xué)生。海南人都不怕熱,小趙怕熱。所以小趙不是海南人。無理數(shù)都不能表示成分?jǐn)?shù),3.1415能表示成分?jǐn)?shù)。所以3.1415不是無理數(shù)。例鳥都會(huì)飛,麻雀是鳥,所以麻雀會(huì)飛。例烏鴉都不是白色的,北京鴨是白色的。因此,北京鴨不是烏鴉。第二篇集合論第3章集合計(jì)算例設(shè).例設(shè)A={{a,},c,{c},{a,b}},B={{a,b},},計(jì)算(1)A∩B,(2)A⊕B,(3)P(B)集合恒等式的證明例設(shè)A.B.C是三個(gè)集合,證明:A
B=A
(B-A)例設(shè)A.B.C是三個(gè)集合,證明:A－(B
C)＝(A－B)－C例設(shè)A.B.C是三個(gè)集合,證明:A
(B－C)＝(A
B)－(A
C)例設(shè)A、B、C是三個(gè)集合,證明:(A－B)
(A－C)=A－(B
C)例設(shè)A、B、C是任意三個(gè)集合,證明：((A(B－C))A)(B－(B－A))＝A。例設(shè)A.B.C是任意三個(gè)集合,證明:((A
(B－C))
A)
(B－(B－A))＝A例設(shè)A,B,C為集合,證明:A∩(B－C)=(A－C)∩(B－C)例已知A∩B=A∩C,且
∩B=
∩C,證明B=C。包含排斥原理（即容斥原理）的簡(jiǎn)單應(yīng)用例假設(shè)某班有20名學(xué)生,其中有10人英語成績(jī)?yōu)閮?yōu),有8人數(shù)學(xué)成績(jī)?yōu)閮?yōu),又知有6人英語和數(shù)學(xué)成績(jī)都為優(yōu)。問兩門課都不為優(yōu)的學(xué)生有幾名？例有100名程序員,其中47名熟悉C++語言,35名熟悉JAVA語言,23名熟悉這兩種語言。問有多少人對(duì)兩種語言都不熟悉？例在一個(gè)班級(jí)的50名學(xué)生中,有26人在第一次考試中得到A,21人在第二次考試中得到A,假如有17人兩次考試都沒得到A,問有多少學(xué)生兩次考試都得到A？第4章關(guān)系第5章函數(shù)例設(shè)集合A={1,2,3,4,5},A上的關(guān)系R和S為:R={<x,y>|x+y=5,x,y
A},S={<x,y>|x<y,x,y
A},求R
S。例設(shè)A={0,1,2,3},A上的兩個(gè)關(guān)系:R={(a,b)︱a=b+1或a=b/2},S={(a,b)︱b=a+2},求(1)R
S,(2)S
R。例設(shè)B={1,2,3,4},B上的關(guān)系R＝{〈1,2〉,〈2,1〉,〈2,3〉,〈3,4〉｝,求(1)RR(2)R-1例設(shè)A={a,b,c,d},A上的關(guān)系R＝{<a,b>,<b,a>,<b,c>,<c,d>｝,求(1)R
R(2)R-1例設(shè)集合A＝{2,4,6,8,10,12},B={2,4,6},從A到B的關(guān)系R＝{<x,y>|x=2y},求R和R-1例設(shè)集合A＝｛1,2,3,4,5,6｝,B={1,2,3},從A到B的關(guān)系R＝｛〈x,y〉|x=2y｝,求(1)R,(2)R-1例設(shè)R1={<1,2>,<2,2>,<2,3>,<3,3>},R2={<2,2>,<2,3>,<3,4>},求(1)R1-1,(2)R1
R2例R1={<1,2>,<1,3>,<2,3>,<3,3>},R2={<2,2>,<2,3>,<3,4>},(1)求R1-1(2)求R2
R1(3)R1是函數(shù)嗎？例設(shè)A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>},求r(R),s(R),t(R)。例已知A＝{
},在A上定義二元關(guān)系R：R={}（1）試畫出R的關(guān)系圖；（2）求R的自反閉包和對(duì)稱閉包。例R1={<1,2>,<1,3>,<2,3>,<3,3>},R2={<2,2>,<2,3>,<3,4>},(1)求R1-1(2)求R2
R1(3)R1是函數(shù)嗎？例設(shè)集合A={a,b,c,},B={b,c,d},C={d,e,f},R1={<1,2>,<2,2>,<2,3>,<3,3>},R2={<2,2>,<2,3>,<3,4>},求(1)
,(2)A⊕B,(3)R1-1,(4)R1
R2例設(shè)A={a,b,c},R是A冪集上的包含關(guān)系,說明R是偏序關(guān)系并畫出R的哈斯圖。例求集合A={1,2,3}的冪集,R是A冪集上的包含關(guān)系,說明R是偏序關(guān)系并畫出R的哈斯圖。例設(shè)S={1,2,…,10},
是S上的整除關(guān)系,畫出<S,
>的哈斯圖。例畫出集合A＝{2,3,4,6,7,8,9}上整除關(guān)系的哈斯圖。例設(shè)集合A={0,1,2,3,4,5},R={<0,0>,<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<2,3>,<3,1>,<3,2>,<3,3>,<4,4>,<4,5>,<5,4>,<5,5>},試用關(guān)系圖驗(yàn)證R是A上的等價(jià)關(guān)系。例A={1,2,3},R為A上關(guān)系,關(guān)系矩陣為
,(1)畫出關(guān)系圖。(2)求R
R,R-1。(3)求r(R),s(R),t(R)；(4)指出R具有的性質(zhì)。(5)R是偏序關(guān)系嗎？若是畫出哈斯圖。第三篇圖論連通性判斷,通路數(shù)的計(jì)算例有向圖G如下圖所示:(1)寫出此圖的鄰接矩陣表示。（4分）(2)v1到v3長(zhǎng)為3的通路有多少條？v1到自身長(zhǎng)為3的回路有多少條？（4分）(3)G中長(zhǎng)為3的通路共有多少條？其中回路多少條？（4分）例具有四個(gè)節(jié)點(diǎn)的有向圖G如下圖所示:寫出此圖的鄰接矩陣。（3分）G是單向連通還是強(qiáng)連通？（3分）長(zhǎng)為4的通路共有多少條?其中有多少條回路?（4分）例已知有向圖G的鄰接矩陣為A=（1）畫出圖并說出此圖有幾條邊。（2）v4到v2長(zhǎng)為3的通路有多少條？v1到自身長(zhǎng)為3的回路有多少條？（3）此圖是強(qiáng)連通還是單向連通圖？例G是具有四個(gè)節(jié)點(diǎn)的有向圖,它的鄰接矩陣表示如下畫此圖并說明該圖共有幾條邊？G是單向連通還是強(qiáng)連通？分別求出從v4到v4長(zhǎng)度小于4的回路條數(shù)及從v1到v2.從v1到v3、v1到v4長(zhǎng)度是3的通路數(shù)。例已知有向圖G的鄰接矩陣為A=（1）畫出圖G并說出此圖有幾條邊。（2）v1到v3,v4到v2長(zhǎng)為3的通路有多少條？v1到自身長(zhǎng)為3的回路有多少條？（3）此圖是強(qiáng)連通還是單向連通圖？哈密爾頓圖的充分條件及其簡(jiǎn)單應(yīng)用例一次會(huì)議有10人參加,其中每個(gè)人都在其中有不下6個(gè)朋友。這10人圍成一圓桌入席。有沒有可能使任意相鄰而坐的兩個(gè)人都是朋友？為什么？計(jì)算例已知無向圖G有12條邊,1度頂點(diǎn)有2個(gè),2度、3度、5度頂點(diǎn)各1個(gè),其余頂點(diǎn)度數(shù)均為4,求4度頂點(diǎn)的個(gè)數(shù)。例一棵樹有兩個(gè)結(jié)點(diǎn)度數(shù)為2,一個(gè)結(jié)點(diǎn)度數(shù)為3,三個(gè)結(jié)點(diǎn)度數(shù)為4,其余結(jié)點(diǎn)度數(shù)均為1,問它有幾個(gè)度數(shù)為1的結(jié)點(diǎn)？例已知無向樹T中,有1個(gè)3度頂點(diǎn),2個(gè)2度頂點(diǎn),其余頂點(diǎn)全是樹葉。試求樹葉數(shù)。例無向樹
有8片樹葉,2個(gè)3度分支點(diǎn),其余的分支點(diǎn)都是4度頂點(diǎn),問
有幾個(gè)4度分支點(diǎn)？求出下圖的一棵最小生成樹,并計(jì)算其權(quán)。12312345678910求最優(yōu)二元樹及其權(quán)例求以1,3,4,5,6為權(quán)的最優(yōu)2元樹,要求寫出步驟并計(jì)算它的權(quán)。例(1)求以2,3,5,7,8,9為權(quán)的最優(yōu)2元樹
,(2)求
,（3)求
的高度
,(4)求
的樹葉有多少？(5)求
的2度頂點(diǎn),3度頂點(diǎn),4度頂點(diǎn)各有多少？例給定權(quán)1,4,9,16,25,36,49,64,81,100,構(gòu)造一棵最優(yōu)二叉樹。利用最優(yōu)二元樹進(jìn)行編碼例設(shè)7個(gè)字母在通信中出現(xiàn)的頻率如下:a:35%,b:20%,c:15%,d:10%,e:10%,f:5%,g:5%用Huffman算法求傳輸它們的前綴碼.要求畫出最優(yōu)樹,指出每個(gè)字母對(duì)應(yīng)的編碼。并指出傳輸10n(n≥2)個(gè)按上述頻率出現(xiàn)的字母,需要多少個(gè)二進(jìn)制數(shù)字。例在通信中,設(shè)八進(jìn)制數(shù)字出現(xiàn)的頻率(%)如下:0:25,1:20,2:15,3:10,4:10,5:10,6:5,7:5采用2元前綴碼,求傳輸數(shù)字最少的2元前綴碼(稱作最佳前綴碼),并求傳輸100個(gè)按上述比例出現(xiàn)的八進(jìn)制數(shù)字需要多少個(gè)二進(jìn)制數(shù)字？若用等長(zhǎng)的(長(zhǎng)為