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

注意解題思路清論入手)分析問題,再按正向思寫出證明過程2全書知識(shí)網(wǎng)絡(luò)命題邏命題邏謂詞邏數(shù)理邏輯二元關(guān)集二元關(guān)集合初

函函<YX,~,∩,∪,－,,°,-n元運(yùn)n元運(yùn)形式語言與 復(fù)習(xí)重第一章命題邏輯(約聯(lián)結(jié)詞的定義(含義及真值表定義)和聯(lián)結(jié)詞全功能集會(huì)命題符號(hào)化式的證明和蘊(yùn)涵式的證明,記住并能熟練應(yīng)用常用公式等價(jià)公式的證明,記住并能熟練應(yīng)用常用公式（P9基本 掌握對(duì)偶的定義、會(huì)求命題公式的（主）范式,能應(yīng)（主）范式解決問題（極大項(xiàng)和極小項(xiàng)的概念 第二章謂詞邏輯（約準(zhǔn)確掌握有關(guān)概念會(huì)命題符號(hào)化（尤其注意特性謂詞的使用）.(如P39-例2.1-掌握常用的等價(jià)公式 蘊(yùn)涵式.包括帶量詞的公式在論域內(nèi)展開式,量詞否定,量詞轄域擴(kuò)充,量詞分配公式(P46§2.3).會(huì)用等價(jià)公式求謂詞公式的真值.(代換實(shí)例、公式的解釋P4例題和章后相關(guān)習(xí)題)了解掌握謂詞邏輯推理5第三章集合的基本概念與運(yùn)算（約集合的表示,冪集,全集,空集集合的三種關(guān)系(包含,相等,真包含)的定義及證明集合的五種運(yùn)算（交、并、相對(duì)補(bǔ)（差）、絕對(duì)補(bǔ)、對(duì)稱差）及相關(guān)性質(zhì).集合代數(shù)的算律（P61-集合中元素的計(jì)數(shù)、會(huì)應(yīng)用包含排斥原理6第四章二元關(guān)系和函數(shù)（約關(guān)系的概念,表示方法（集合、關(guān)系矩陣、關(guān)系圖二元關(guān)系的性質(zhì)的定義,熟練掌握性質(zhì)的判斷及證明關(guān)系的運(yùn)算：掌握定義域、值域和域的概念、掌握關(guān)系的復(fù)合（注意：中定義的復(fù)合為左復(fù)合）,求逆及閉包運(yùn)算(計(jì)算方法及有關(guān)性質(zhì))掌握等價(jià)關(guān)系的判斷,證明,求等價(jià)類和商集偏序關(guān)系的判斷,會(huì)畫Hasse圖,會(huì)求一個(gè)子集的極小(大元,最小(大)元,上界與下界,最小上界及最大下界函數(shù)的定義和性質(zhì)（單、滿、雙射會(huì)計(jì)算函數(shù)的復(fù)合(左復(fù)合),求反函數(shù).知道有關(guān)性質(zhì)7第五~論（約掌握?qǐng)D的基本概念（無向圖、有向圖、有限圖、頂點(diǎn)、無向邊、有向邊、n階圖、零圖、平凡圖、關(guān)聯(lián)、相鄰等）。熟練掌握?qǐng)D中關(guān)于結(jié)點(diǎn)度數(shù)的概念和定理(會(huì)應(yīng)用掌握通路、回路及其相關(guān)概念和定理（P123-124）掌握連通、強(qiáng)連通、距離、連通分支及連通分支數(shù)的概念和點(diǎn)、邊割集的概念.會(huì)求圖的矩陣（有向、無向圖的關(guān)聯(lián)矩陣和有向圖的鄰接矩陣（ 的意義）、有向圖的可達(dá)矩陣）.掌握二部圖及相關(guān)概念（二部圖、匹配、極大匹配、最大匹配、完備匹配、完美匹配等）、會(huì)使用相異性條件和條件判定匹配的存在性。8會(huì)判 圖和漢密爾頓圖會(huì)判定平面圖,掌 公式會(huì)畫平面嵌入的對(duì)偶圖基本回路系統(tǒng)和基本割集系統(tǒng)、Huffman樹及編碼應(yīng)用第8章組合分析初步（約允許重復(fù)（多重集）的排列和組合（重點(diǎn)9 復(fù) 復(fù)各章內(nèi)容及例題選第一章命題邏定義了六個(gè)邏輯聯(lián)結(jié)詞，分別是(1)否定 (2)合取(3)析取 (4)異（排斥）或“(5)蘊(yùn)涵 (6)等價(jià)要熟練掌握這五個(gè)聯(lián)結(jié)詞在自然語言中所表示的含義以及它們的真值表的定義。：否示“不∧：合取表示“不但…,而且...”“并且∨：析取表示：異或：蘊(yùn)涵表示“如果…,則 可以將這六個(gè)聯(lián)結(jié)詞看成六種“運(yùn)算”聯(lián)結(jié)詞的定義(包括真值表和含義 P 特別要注意“或者”的二義性,即要區(qū)分給定的“或”是“可兼取或∨”還是“不可兼取的

”“”的用法，它既表示“充分條件”也表示“必要條件”,即要弄清哪個(gè)作為前件,哪個(gè)作為后件.會(huì)命題符號(hào)化例如P:我有時(shí)間 Q:我上街 R:我在家表示P是Q的充分條件:如果p,則Q.只要P,就Q.PQ表示P是Q的必要條件:僅當(dāng)P,才Q.只有P,才Q.QP如果P,則Q;否則R.(PQ)(PR)式的證明方法1.列真值表方法2.用公式的等價(jià)變換,化簡成例如證明(R(QR)(PQ))P 式證:上式(R(QR) (公式的否定公式((R(QR)) (結(jié)合律((RQ)(RR))((PP)(QP)(分配律(RQ)(QP)RQQP1(互補(bǔ),同一律)001011100111001011100111 蘊(yùn)涵B.方法1.列真值表方法3.假設(shè)后件假,推出前件假.(即反證法 證:假設(shè)后件(PQ)(PR)假,則PQ為1,PR為0,于是P為1,R為0,進(jìn)而又得Q為1.所以QR為0,所以前件P(QR)為0.所以(P(QR))((PQ)(PR))為式 (原命題的真假性與逆否命題的真假性一致對(duì)于給定一個(gè)題,究竟是用哪種方法,原則上哪種都可以但是哪個(gè)方法簡單,要根據(jù)具體題而定 等價(jià)公式的證明,記住常用的公式方法1.列真值表方法2.用公式的等價(jià)變換例如:P(QR)(P∧Q)RP(QR)P(QR(PQ)R(PQ)∨R注意:不論是證明蘊(yùn)涵式,還是證明等價(jià)公式必須一些常用的公如:蘊(yùn)涵式、共同蘊(yùn)含式（推理定律和推理規(guī)則）:P23-24,(等值公式):6.析取范式:A1∨A2∨...∨An(n≥1)Ai(i=1,2..n)是合取式合取范式:A1∧A2∧...∧An(n≥1)Ai(i=1,2..n)是析取式析取范式與合取范式的寫法極小極小項(xiàng)的性質(zhì)PQ0000010100101001001110006)極大其性質(zhì)PQ000111011011101101111110主析取范式A1∨A2∨...∨An主合取范式A1∧A2∧...∧AnAi(i=1,2..n)極小項(xiàng)Ai(i=1,2..n)極大項(xiàng)9).9)..QR求下面命題公式的范式0001方法1.列真值表00001110110110001011主析取范11110101(P∧Q∧R)∨(P∧Q∧R∨(P∧Q∧R)∨(P∧Q∧R主合取范(P∨Q∨R)∧(P∨Q∨R方法2.用公式的等價(jià)變換主析取范式;A(P,Q,R)(P∨Q)∨R(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R∨(P∧Q∧R)∨(P∧Q∧R主合取范式:A(P,Q,R)(P∨Q)∨R(P∨R(P∨(Q∧Q)∨R(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨Rm0,m3,m4,m5,m7求它的主合取范式.解:G的主合取范式中含有大項(xiàng):M1,M2G(P∨Q∨R*范式的應(yīng)如P35習(xí)題1.141.15會(huì)用推理方法,進(jìn)行邏輯推理例如:((A∧B)C)∧D∧(C∨D直接推理 前提引 前提引 前提引 拒取 等值置((A∧B)C)∧D∧(C∨D)條件（附加前提）論證適用于結(jié)論是蘊(yùn)涵式A∨B 附 前提引 等值置 假言推 前提引 前提引 ((A∧B)C)∧D∧(C∨D)反證（歸謬）法 ⑴等值置 前提引 （3）假言推 前提引 前提引 （5）（6）析 合取引第二章謂詞邏準(zhǔn)確掌握有關(guān)概念會(huì)命題符號(hào)化掌握常用的等價(jià)公式 蘊(yùn)涵式.包括帶量詞的公式在論域內(nèi)展開式,量詞否定,量詞轄域擴(kuò)充,量詞分配公式.會(huì)用等價(jià)公式求謂詞公式的真值了解謂詞邏輯推理第二章謂詞邏準(zhǔn)確掌握有關(guān)概念客體量詞全 域前束范式 會(huì)命題符號(hào)化.(如P38-41例題命題的符號(hào)表達(dá)式與論域有關(guān)。當(dāng)論域擴(kuò)大時(shí)，需要添加用來表示客體特性的謂詞，稱此謂詞為特性謂詞特性謂詞往往就是給定命題中量詞后邊的那個(gè)名詞。如“所有自然數(shù)...”、“有些大學(xué)生...”。如何添加特性謂詞，這是個(gè)十分重要的問題，這與前邊的量詞有關(guān)。（P39***式）另外有些命題里有的客體在句中沒有明確的量詞,而在寫它的符號(hào)表達(dá)式時(shí),必須把隱含的量詞明確的寫出來.例如⑴金子閃光,但閃光的不一定都是金子設(shè)G(x):x是金子.F(x):x閃光⑵沒有大學(xué)生不懂外語S(x):x是大學(xué)生F(x):x外語.K(x,y):x懂得⑶有些液體可以溶解所有固體F(x):x是液體.S(x):x是固體.D(x,y):x可溶解⑷每個(gè)大學(xué)生 一些文體活動(dòng) y,C(x):x是文娛活動(dòng)， 掌握常用的等價(jià)公式 蘊(yùn)涵式.包括帶量詞的公式在論域內(nèi)展開式,量詞否定,量詞轄域擴(kuò)充,量詞分配公式.設(shè)論域?yàn)?,an}，1). 2). 1).2).1).2).3).4).5).6).7).8).1).2).3).4).會(huì)用等價(jià)公式求謂詞公式的真值例設(shè)論域?yàn)閧1,2},A(x,y):x+y=xy,求xyA(x,y)的真值xyA(x,y)(11)(10) (去xF(x,y)yG(y) xF(x,y)yG(y) (量詞否定xF(x,zyG(y) (變?cè)獡Q名xyu((F(x,zG(y) (轄域擴(kuò)充6.了解謂詞邏輯推理注意使用ES、US、EG、UG的限制條件,特別是對(duì)于同一個(gè)客體變?cè)扔袔б灿袔У那疤?，去量詞時(shí)，應(yīng)先去后去，這樣才可以特指同一個(gè)客體c.3)去量詞時(shí)，該量詞必須是公式的最左邊的量詞，且此量詞的前邊無任何符號(hào)，它的轄域作用到公式末尾下面的作法是錯(cuò)誤的xP(x)→xQ(x)前提引P(c)→xQ(x)US⑴實(shí)際上x的轄域擴(kuò)充量詞改成為正確作法xP(x)→xQ(x)前提引 ⑴置 ⑵置 置⑸ ⑸置下面的作法是錯(cuò)誤的 前提引 實(shí)際上⑴中量詞不x而是⑴xyP(x,y)前提引⑵xP(x,c)

正確作法⑴xP(x)前提引⑵ ⑶ ⑴xyP(x,y提引 4)添加量詞時(shí)，也要加在公式的最左邊，(即新加的量詞前也無任何符號(hào)！！)且其轄域作用到公式的末尾。例如下面作法是錯(cuò)誤的: ⑴xPx→Q(c)前提引入⑵xP(x)→yQ(y)第三章集合論集合的表示,冪集,全集,空集集合的三種關(guān)系(包含,相等,真包含)的定義及證明集合的五種運(yùn)算及相關(guān)性質(zhì)應(yīng)用包含排斥原理第三章集合的基本概念與運(yùn)基本概念:集合與元素,子集與真子集空集全集冪集,并集,交集,相對(duì)補(bǔ)集(差集),絕對(duì)補(bǔ)集(補(bǔ)集)集合的表示,集合的三種表示方法枚舉法:一一列出集合中的元素謂詞描述法:用謂詞描述集合中元素的性質(zhì)文氏圖用一個(gè)平面區(qū)域表示.ABx(x∈Ax∈B)A=BABBAx(x∈Ax∈B)3空集,全集冪空集φ:無元素的集合.x∈Φ 式.(空集是唯一的全集E:包含所討論所有集合的集合.(全集不唯一) 冪集:由A的所有子集構(gòu)成的集合 x∈A∩Bx∈A∧x∈BA∪B={x|x∈A∨x∈B} x∈A∪Bx∈A∨x∈BA-B={x|x∈A∧xB} x∈A-Bx∈A∧xB~A=E- A-B=A∩例1.已知全集E={Φ,{Φ}},AE,計(jì)算 解:a)因?yàn)槿魏渭螦AA=Φ所因?yàn)棣礎(chǔ)Φ~A即Φ∈P(A)Φ∈P(~A)所P(~{{Φ}})=P({Φ})=P(E)-P(~{{Φ}}))={Φ,{Φ},{{Φ}},{Φ,{Φ}}}-例2證明A-B)-C=A方法1A-B)-C=(A~B)~C=A∩~B∩=A∩~(B∪C)=A-方法2.任取x∈(A-B)-x∈A∧(xB∧xC)x∈A∧(x∈A∧(x∈B∪C)x∈A∧xB∪Cx∈A-所以(A-B)-C=A例3.令全集E為信息學(xué)院的學(xué)生的集合,C表示計(jì)算機(jī)專“學(xué)習(xí)了離散數(shù)學(xué)和數(shù)據(jù)結(jié)構(gòu)課的學(xué)生,一定是計(jì)算機(jī)專業(yè)的非一年級(jí)的學(xué)生”.解 例5.在什么條件下，下面命題為真(A-B)∪(A-解.(A-B)∪(A-C)=A∩~(B∩C)=A-所以滿足此式的充要條件是：A∩B∩C=(A-B)∪(A-解.(A-B)∪(A-C)A-(B∩C)=Φ充要條件是：A解.(A-B)∩(A-C)A∩~(B∪C)=A 充要條件是:A(A-B)(A-解.且僅當(dāng)A=B，才有AB=Φ所以滿足此式的充要條件是:A-B=A-C例6有14位學(xué)生參加考試,9位同學(xué)數(shù)學(xué)得了優(yōu);5位同學(xué)物解.令A(yù)、B、C分別表示數(shù)學(xué)、物理、化學(xué)得優(yōu)同學(xué)集合.全集為E.于是有4 9 5 4 于是得到優(yōu)的人數(shù)是10人優(yōu)的人數(shù)是14-10=4恰有兩門得優(yōu)的人數(shù):(|A∩B|-第四章二元關(guān)系與函關(guān)系的概念,表示方法二元關(guān)系的性質(zhì)的定義,熟練掌握性質(zhì)的判斷及證明掌握關(guān)系的復(fù)合,求逆及閉包運(yùn)算(計(jì)算方法及有關(guān)性質(zhì)掌握等價(jià)關(guān)系的判斷,證明,求等價(jià)類和商集偏序關(guān)系的判斷,會(huì)畫Hasse圖,會(huì)求一個(gè)子集的極小(大元,最小(大)元,上界與下界,最小上界及最大下界注意本章證明題的證明過程的一.關(guān)系的概念,表示方法,三個(gè)特殊關(guān)系集合的笛卡爾積A×B={<x,y>|x∈A∧y∈B}|A|=m,|B|=n設(shè)A={0,1}，B={a,b}，求AB二定義1:設(shè)A、Ｂ是集合,如果ＲA×B,則稱R是一個(gè)從AB的二元關(guān)系。如果RA×A,則稱R是A上的二元關(guān)系如果|A|=m|B|=n則可以確定2mn個(gè)從A到B的不同關(guān)系.關(guān)系的表示方枚舉即將關(guān)系中所有序偶一一列舉出，寫在大括號(hào)內(nèi).如:R={<1,2>,<3,4>,<4,2>}2).(描述法)謂詞公式法即用謂詞公式描述序偶中元素的關(guān)系。有向圖法 1 R1 2 c3 c4

R2

1 4 矩陣表示法：(實(shí)際上就是圖論中的鄰接矩陣設(shè)A={a1a2am}，B={b1b2bn}是個(gè)有 若

若

空關(guān)系ΦA(chǔ)×B，(或ΦA(chǔ)×A)，即無任何元素的關(guān)系它的關(guān)系圖中只有結(jié)點(diǎn),無任何邊；它的矩陣中全是0完全關(guān)系(全域關(guān)系)A×B(或A×A)本身是一個(gè)從A到B(或A上)的完全關(guān)系即含有全部序偶的關(guān)系。它的矩陣中全是1恒等關(guān)系IAA×A,且IA={<x,x>|x∈A}稱之為A上的恒等關(guān)系。例如A={1,2,3},則IA={<1,1>,<2,2>,<3,3>}A上的Φ、完全關(guān)系A(chǔ)×A及IA的關(guān)系圖及矩陣如下1 12

12。2。

000000

111111

MIA

100100

二.關(guān)系的性質(zhì)熟練掌握性質(zhì)的判斷及證明自反定義:設(shè)R是集合A中的關(guān)系，如果對(duì)于任意x∈A都<x,x>∈R(xRx)，則稱R是A中自反關(guān)系。即反自反定義：設(shè)R是集合A中的關(guān)系，如果對(duì)于任意的x∈A都<x,x>R，則稱R為A中的反自反關(guān)系。R是A中反自反的對(duì)稱定義:R是集合A中關(guān)系,若對(duì)任何x,y∈A,如果有xRy,必有R是A上對(duì)稱的xy((xAyAxRy)稱定義:設(shè)R為集合A中關(guān)系,若對(duì)任何x,y∈A,如果有xRy,和 稱關(guān)系。R是A 稱的xy((xAyAxRyyRx)傳遞定義R是A中關(guān)系，對(duì)任何x,y,z∈A,如果有xRy,和yRz,就有xRz則稱R為A中傳遞關(guān)系。即R在A上傳這些性質(zhì)要求會(huì)判斷,會(huì)證明這里特別要注意的是些定義都是蘊(yùn)涵式以當(dāng)蘊(yùn)涵式當(dāng)前件為假時(shí),此蘊(yùn)涵式為真,即此性質(zhì)成立!!性質(zhì)判定從關(guān)系的有從關(guān)系的矩自反每個(gè)結(jié)點(diǎn)都主對(duì)角線全是反自反每個(gè)結(jié)點(diǎn)都主對(duì)角線全是對(duì)稱不同結(jié)點(diǎn)間如果有邊稱的位置不會(huì)同時(shí)為傳遞或者使得前件為假判斷下面關(guān)系的性質(zhì)12。12。12。12。自反反自反對(duì)稱稱傳遞YNNYYNYNYNYNYNYYNYYY12。12。12。12。自反反自反對(duì)稱稱傳遞NYNYYNNYNNNNNNNNYYYY關(guān)系性質(zhì)當(dāng)證明方法歸納:設(shè)R是A上關(guān)系證明R的自反性方法1用自反定義證：任x∈A,證出方法2用恒等關(guān)系IA證：證出IA方法3用自反閉包證：證出r(R)=R,即證明R的反自反性方法1用反自反定義證：任x∈A,證出證明R的對(duì)稱性方法1用對(duì)稱定義證x,y∈A,設(shè)<x,y>∈R,方法用求逆關(guān)系證：證出R-方法用對(duì)稱閉包證：證出即R∪R-證明R 稱性方法1用定義1證x,y∈A,設(shè)<x,y>∈R<y,x>∈R.x=y。x,y∈A,x≠y,設(shè)<x,y>∈R,證出<y,x>R.方法3用相關(guān)結(jié)論證R∩R-1IA.證明R的傳遞性方法1用傳遞定義證任取x,y,z∈A,設(shè)<x,y>∈R,<y,z>∈R,證出方法2用傳遞閉包證R∪R2∪R3∪方法3用相關(guān)結(jié)論證

Ro可以根據(jù)具體情況,選用相應(yīng)方法證明.握的是用基本定義證明:設(shè)RY×Z，SX×YR°SX×Z。R°S={<x,z>|xXzZy(yY<x,y>S<y,z>R)}(俗稱過河拆橋法⑴枚舉法⑵有向

RSa 。 。cc c

a 。 。c 。⑶矩M

=

性

R°

011

=滿足結(jié)合律 SB×CRC×D ⑴R°⑵R°R°IB=IA°R=R推論:RA×A,則R°IA=IA° (IA是運(yùn)算°的幺元關(guān)系的乘冪R0 Rm°Rn=(Rm)n (m,n為非負(fù)整數(shù)關(guān)定義:設(shè)RX×Y，R的逆關(guān)系R-<y,x>∈R-1計(jì)算方 R-1R-1的有向圖:是將R的有向圖的所有邊的方向顛倒R-1的矩陣MR-1 即為R矩陣的轉(zhuǎn)性令R、S都是從X到Y(jié)的關(guān)系1).(R-1)-1=2)(R∪S)-1R-1∪S-13)(R∩S)-1R-1∩S-1(R－S)-1R-1－S-1 RSR-1S-16).(~R)-1=~R-令R是從X到Y(jié)的關(guān)系，S是YZ的關(guān)系，則(R°S)-1=S-1R-1。R是AR是對(duì)稱的，當(dāng)且僅R-1⑵R 稱的，當(dāng)且僅當(dāng)R∩R-1IA(三).閉包運(yùn)定義：給定A中關(guān)系R,若A上另一個(gè)關(guān)系R’，滿足：⑴⑵R’是自反的(對(duì)稱的、傳遞的 的關(guān)系R”,如果RR”,就有R’R”。則稱R’是R的自反(對(duì)稱、傳遞)閉包。記作r(R)、s(R)、t(R)計(jì)算方法A中關(guān)系Rs(R)=R∪R-1t(R)=R∪R2∪R3∪...閉包的運(yùn)算有三種形式 RA×A r(R)=R∪IAs(R)=R∪RC ={<a,b>,<b,c>,<c,a>,<a,c>,<b,a>,<c,b>.<b,b>, R

R

∪

矩陣形式

=M

R-

∨

M1(R)=R

∨R∨R3

=

∨100

=性R是A⑴R是自反的，當(dāng)且僅當(dāng)R是對(duì)稱的，當(dāng)且僅當(dāng)R是傳遞的，當(dāng)且僅當(dāng)R是A⑴R是自反的，則s(R)和t(R)R是對(duì)稱的，則r(R)和t(R)也對(duì)稱⑶R是傳遞的，則r(R)也傳遞*3).設(shè)R是A上關(guān)系，⑴⑵⑶四.等價(jià)關(guān)掌握等價(jià)關(guān)系的判斷,證明,求等價(jià)類和商了解集合的劃分與覆蓋的概念例 A4={{1,2},{2,3}},A1A2,A3,A4是覆蓋A1A2,A3也是劃分等價(jià)關(guān)系定義:設(shè)R是A上關(guān)系,若R是自反的、對(duì)稱的和傳，則稱R是A中的等價(jià)關(guān)系。等價(jià)關(guān)系R的有向圖:可能由若干個(gè)獨(dú)立子圖構(gòu)成的，每個(gè)獨(dú)立子圖都是完全關(guān)系圖。12。

1 2。

12等價(jià)類稱集合[a]R為由a形成的R等價(jià)類由等價(jià)關(guān)系圖求等價(jià)類：R圖中每個(gè)獨(dú)立子圖上的點(diǎn)構(gòu)成一個(gè)等價(jià)類。不同的等價(jià)類個(gè)數(shù)=獨(dú)立子圖個(gè)數(shù)等價(jià)類性 R是A上等價(jià)關(guān)系，任意⑴同一個(gè)等價(jià)類中的元素，彼此有等價(jià)關(guān)系R⑵[a]R∩[b]R=Φ，當(dāng)且僅當(dāng)<a,b>R[a]R=[b]R當(dāng)且僅<a,b>∈R⑷.A中任何元素a,a必屬于且僅屬于一個(gè)等價(jià)類⑸.任意兩個(gè)等價(jià)類要么[a]R=[b]R，要么[a]R∩[b]R=Φ⑹R的所有等價(jià)類構(gòu)成的集合是A的一個(gè)劃分商集定義：R是A上等價(jià)關(guān)系，由R的所有等價(jià)類構(gòu)成的集合稱之為A關(guān)于R的商集。記作R。即{[a]Ra∈A}1按照集合的等勢(shì)關(guān)系(是等價(jià)關(guān)系)“~”對(duì)集合族S進(jìn)行劃分，得到商集，進(jìn)而得到基數(shù)類的概念。無元 1個(gè)元 2個(gè)元 3個(gè)元素可數(shù)集不可數(shù)集無向圖結(jié)點(diǎn)之間的連通關(guān)系是個(gè)等價(jià)關(guān)系令G=<V,E>是無向圖R是V上連通關(guān)系例.給定圖G如右上圖所示:

°g 圖的同構(gòu)關(guān)系≌是個(gè)等價(jià)關(guān)系 ° 令上述圖構(gòu)成的集合A={a,b,c,d,e,f,g,h,i,j,},求商集 .R和S都是A上等價(jià)關(guān)系,下面哪個(gè)是A上等價(jià)關(guān)系證明或舉反例說明a) b c)~R即A×A-d)R- e)R-解.a)cd0)不是請(qǐng)看反例b。Rb。Sb。b。b。b。b。bR∩S是等價(jià)關(guān)系證明：1明R∩S方法1用自反定義證：任x∈A,(證出因R和S都自反，所以有<x,x>∈R，<x,x>∈S<x,x>∈R∩S，所以R∩S也自反方法2用恒等關(guān)系IA證：(證出IA因R和S都自反，所IAR，IAS，所以IA所以R∩S方法3用自反閉包證(證出r(R∩S)=R∩S,(R∩S)∪IAR∩S)因R和S都自反，所以r(R)=R,r(S)=S,r(R∩S)=(R∩S)∪IA=(R∪IA)∩(S∪IA) 所以R∩S也自反證明R∩S的對(duì)稱性方法1用對(duì)稱定義證x,y∈A,設(shè)<x,y>∈R∩S,(則<x,y>∈R，<x,y>∈S，因?yàn)镽和S對(duì)稱，所以<y,x>∈R，<y,x>∈S，于是<y,x>∈R∩S?！郣∩S對(duì)稱方法2用求逆關(guān)系證：((R∩S)-1=R∩S.)因?yàn)镽和S對(duì)稱，所以有R-1=RS-1=S，而(R∩S)-1=R-1∩S-1=R∩SR∩S對(duì)稱。方法3用對(duì)稱閉包證(s(R∩S)=R∩S因?yàn)镽和S對(duì)稱，所以s(R∩S)=(R∩S)∪(R∩S)c=(R∪R-1)∩(R∪S-1)∩(S∪S-1)∩(S∪R-=(s(R)∩(R∪S-1))∩(s(S)∩(S∪R-=(R∩(R∪S-1))∩(S∩(S∪R-1))=R∩S(吸收律∴R∩S對(duì)稱證明R∩S的傳遞性方法1用傳遞定義證：任設(shè)<x,y>∈R∩S,<y,z>∈R∩S,(證出(<x,y>∈R∧<y,z>∈R)∧(<x,y>∈S<x,z>∈R∧<x,z>∈S（因?yàn)镽、S傳遞<x,z>∈R∩S e)證明.R2是等價(jià)關(guān)系方法1.如果R自反和傳遞,則R2=R,所R2也是等價(jià)關(guān)系方法2.①證R2自反任取a∈A,因?yàn)镽自反,所以<a,a>∈R,根據(jù)關(guān)系的復(fù)合得<a,a>∈RR,即<a,a>∈R2,所以R2②證R2對(duì)稱 (由R對(duì)稱得Rc=R)∴R2對(duì)③證R2傳遞(d∈A∧<a,d>∈R∧<d,b>∈R)∧(e∈A∧<b,e>∈R∧<e,c>∈R)由于R傳遞,所以有<a,b>∈R,<b,c>∈R∴<a,c>∈R2所以R2傳遞。最后得R2是等價(jià)關(guān)系。g).R是A上等價(jià)關(guān)系,則R-1也是A上等價(jià)關(guān)系證明1)證R-1自反因?yàn)槿稳∈A,因R自反，所以<x,x>∈R,∴<x,x>∈R-R對(duì)稱，證R-1也對(duì)稱因?yàn)镽對(duì)稱，所以R-1=RR-1也對(duì)稱R傳遞，證R-1也傳遞方法1.任取x,y,z∈A且有<x,y>∈R-1,<y,z>∈R-1于<y,x>∈R,<z,y>∈R，因R傳遞，∴<z,x>∈R,于是<x,z>∈R-1，∴R-1傳遞方法2t(R-1)=R-1∪(R-1)2∪(R-=R-1∪(R2)-1∪(R3)-1∪…=(R∪R2∪R3∪…)-t(R))-1=R- 所以R-1所以R-1是A上等價(jià)關(guān)系練習(xí)2.五.設(shè)X={1,2,3}Y={1,2}在X的冪集P(X)上定義二元關(guān)系R如下:對(duì)于任何A,B∈P(X),ARB當(dāng)且僅畫出關(guān)系R的有向圖R是等價(jià)關(guān)系嗎?如果是,請(qǐng)寫出商集P(X)/R.如果不是請(qǐng)解.1.關(guān)系R的有向圖

2.從R有向圖看出R有 稱和傳遞性,故是等價(jià)關(guān)五.偏序關(guān)系判斷,會(huì)畫Hasse圖,會(huì)求一個(gè)子集的極(大)元,最小(大)元,上界與下界,最小上界及最大下界 x與y是可比較的：<A,≤>是偏序集，x,y∈A，如果要么x≤y,要么y≤x,則稱x與y是可比較的。定義：<A,≤>是偏序集，任何x,y∈A，如果x與y都是可比較的，則稱≤是全序關(guān)系(線序、鏈)。偏序集Hasse圖的畫法<A,≤>是偏序集用“°”表示A中元素如果x≤y,且x≠y，則結(jié)點(diǎn)y要畫在結(jié)點(diǎn)x的上方如果x≤y,且y蓋住x，x與y之間連一直線從最下層結(jié)點(diǎn)(全是射出的邊與之相連，逐層向上畫，直到最上層結(jié)點(diǎn)(全是射入的邊與之相連)。1 。2 。６。４

1 。2 。４２ ２１ １重要元y是B的極小元(在B中沒有比y更小的元素了，y就是極小元y是B的極大元(在B中沒有比y更大的元素了，y就是極大元y是B的最小元y(y∈B∧x(x∈B(最小元y是B中元素，該元素比B中所有元素都y是B的最大元y(y∈B∧x(x∈By是B的上界y(y∈A∧x(x∈Bx≤y))(上界y是A中元素，該元素比B中所有元素都y是B的下界y(y∈A∧x(x∈B(下界y是A中元素，該元素比B中所有元素都y是B的上界，并且對(duì)B的所有上界x,都有y≤x,則稱是B的最小上界(上確界)，記作LUBB=y。(即y是上界中最小的。如果B有上確界，則是唯一稱y是B的最大下界(下確界)，記作GLBB=y(即y是下界中最大的。如果B有上確界，則是唯一例如

12

18B的極小元 極大元:

62。下確界 上確界 １ 函數(shù)函數(shù)的定義函數(shù)的類型,會(huì)判斷,會(huì)證明會(huì)計(jì)算函數(shù)的復(fù)合(左復(fù)合),求逆函數(shù).知道有關(guān)性質(zhì)一.概定義：與Y集合，f是從X到Y(jié)的關(guān)系，如果任何x∈X，都存在唯一y∈Y，使得<x,y>∈,則稱f是從X到Y(jié)的函數(shù)，變換、)，記作f:XY.如果f:XX是函數(shù)也稱f是X上的函數(shù).函數(shù)相等: 從X到Y(jié)函數(shù)的集合YX：YX={f|YX：它是由所有的從X到Y(jié)函數(shù)構(gòu)成的集合特殊函常值函數(shù)：函數(shù)f:XY，如果y0∈Y使得對(duì)x∈X,有f(x)=y0,即ranf={y0},稱f是常值函數(shù)。之為恒等函數(shù)。顯然對(duì)于x∈X，有IX(x)=x。 函數(shù)的類型,會(huì)判斷,會(huì)證明滿射的：f:XYR0=Y,則稱f是滿射的。證明方法:任取y∈Y,看是否能夠找到對(duì)應(yīng)的自變?cè)獂∈X,y=f(x).映內(nèi)的：f:XY是函數(shù)，如果R0Y則稱0是映內(nèi)的入射的：f:XY是函數(shù)，如果對(duì)于任何x1,x2∈X如果x1≠x2有f(x1)≠f(x2),(或者若f(x1)=f(x2),則x1=x2),則稱f是入射的，也稱f是單射的，也稱f是一對(duì)一的。證明的方法:如定義中所說雙射的：f:XY是函數(shù)，如果f既是滿射的，又是f是雙射的，也稱f是一一對(duì)應(yīng)的。雙射是個(gè)重要概念,我們 上述五個(gè)關(guān)系中，哪些是從R到R的函數(shù)。如果是函數(shù)說明它是屬于什么類型的（指滿射、入射、雙射）如果不是函數(shù)，說明理由 解.R1不是從R到R的函數(shù),x是負(fù)數(shù) 無定義,另外當(dāng)x>0時(shí),有兩個(gè)y值與之對(duì)R2是從R到R的函數(shù),是雙射的R5不是從R到R的函數(shù),因?yàn)閨x|>2時(shí),無定義.|x|<2時(shí)對(duì)應(yīng)的函數(shù)值不唯一. 79二.會(huì)計(jì)算函數(shù)復(fù)合(左復(fù)合),求逆函數(shù).知道有關(guān)性質(zhì)函數(shù)的復(fù)1)定義f:XYg:YZ是函數(shù),則定gf={<x,z>|xXzZy(yYgf為f與g的復(fù)合函數(shù)(左復(fù)合注意:這里把g寫在f的左邊了.所以叫左復(fù)合gf:XZ,即gf是X到Z的函數(shù).這樣寫是為了 :gf(x)=g(f(x)) 復(fù)合函數(shù)的計(jì)計(jì)算方法同復(fù)合關(guān)系的計(jì)算.但要注意是左復(fù)合函數(shù)復(fù)合的性滿足可結(jié)合性f:XYg:YZ,h:ZW是函數(shù),(h°g)°f=h°(g°定理5-2.2f:XYg:YZ是兩個(gè)函數(shù)a).如果f和g是滿射的，則gf也是滿射的；b).如果f和g是入射的gf也是入射的；c).如果f和g是雙射的gf也是雙⑴如果g°f是滿射的，則g是滿射的⑵如果g°f是入射的，則f是入射的⑶如果g°f是雙射的，則0是入射的和g是滿射的f:XY是函數(shù),則f°IX= 且IY°f=ff:XX是函數(shù),f°IX=IX°f=0。IX是運(yùn)算“°”的幺反函定義：設(shè)f:Xy是雙射的函數(shù)，f-1:YX也是函數(shù)稱f的反函數(shù)。f-1存在，也稱f可逆。性設(shè)f:Xy是雙射的函數(shù)，則(f-1)-10設(shè)f:XY是雙射的函數(shù)，則有f-1f=IXff-1IYf:XYg:YX是兩個(gè)函數(shù)如g°f= 且f°g= ,則g=f-1f:XY,g:YX是兩個(gè)雙射函數(shù),(g°f)-1=f-1°g-第五~一.圖的概圖的定義有向邊,無向邊,平行邊,環(huán)鄰接點(diǎn),鄰接邊,孤立結(jié)點(diǎn)有向圖無向圖,簡單圖,混合圖,零圖,平凡圖,多重圖,完全圖,子圖,生成子圖,補(bǔ)圖,結(jié)點(diǎn)的度結(jié)點(diǎn)的出度結(jié)點(diǎn)的入度,圖所有結(jié)點(diǎn)度數(shù)總和與邊的關(guān)系出度和與入度和關(guān)系二.路與回路,回路,跡,閉跡,通路,無向圖的連通性:連通圖,連通分支,連通分支數(shù)W(G),點(diǎn)割集,割點(diǎn),點(diǎn)連通度結(jié)點(diǎn)間的距離,圖的直徑有向圖的連通性:可達(dá)性強(qiáng)連通,單側(cè)連通,弱連通強(qiáng)分圖,單側(cè)分圖,弱分圖.(會(huì)三.圖的矩鄰接矩陣A:結(jié)點(diǎn)與結(jié)點(diǎn)之間的鄰接關(guān)系矩陣根據(jù)鄰接矩陣判斷:各結(jié)點(diǎn)的度,有向圖結(jié)點(diǎn)出,入度.可達(dá)矩陣P:結(jié)點(diǎn)u到結(jié)點(diǎn)v的可達(dá)性的矩陣用P可以判定:各結(jié)點(diǎn)的度有向圖的強(qiáng)分圖.用M判定:各結(jié)點(diǎn)的 判定有 路的充要條件:無或有兩個(gè)奇數(shù)度的結(jié)點(diǎn).有 回路的充要條件:所有結(jié)點(diǎn)度數(shù)均為偶數(shù).必要條件V的任何非空子集,有W(-充分條件:每對(duì)結(jié)點(diǎn)的度數(shù)和≥|=n五.平面公式:nm+r=2.平面圖的判定 基定理定理8.13G是平面圖G中不含與K5同胚的子圖也不含與K3,3同胚的子圖定理 G是平面圖G中無可收縮為K5的子圖也無可收縮為K3,3的子圖六.對(duì)偶會(huì)畫平面嵌入的對(duì)偶圖七二部握相異性條件和t條件（會(huì)應(yīng)用八、基本回路系統(tǒng)和基本割集系統(tǒng)的概念，Huffman樹的概念及應(yīng)用。練習(xí)請(qǐng)畫出K5的所有解K5的生成樹1邊數(shù)為4,1的度數(shù)和為 ° 今有a,b,c,d,e,0,g七個(gè)人,已知下列事 c:會(huì)講英語,意大利語和俄語d:會(huì)講日語和漢語e:會(huì)講德語和意大利 f: 語,日語,俄g: 語和德語試問能否將這七個(gè)人適當(dāng)安排座位,使得每個(gè)人都能和他兩邊的人直接交談?若能,請(qǐng)給予安排.若不能,說明理由.解以a,b,c,d,e,f,g為結(jié)點(diǎn),如果兩個(gè)從此圖中找到H回路:按照此回路坐成一個(gè)圓圈,就可

使得每個(gè)人都可以和它兩邊的人直接交談圖?哪些可能構(gòu)成漢密爾頓圖?哪些可能是完全圖哪些可能是樹?如果能.請(qǐng)畫出一個(gè)那樣的圖如果不能 d.(2,3,3,4,4) 解.a.(1,2,3,3)不能構(gòu)成無向連通圖的結(jié)點(diǎn)度數(shù)序列因?yàn)榇诵蛄兄杏腥齻€(gè)奇數(shù),不附和握手定理 b.(3,3,3,3)可以是個(gè)完全圖K3,是個(gè)H圖. c.(1,1,1,1,2,4)可以是棵d.(2,3,3,4,4)構(gòu)成無向連通圖

結(jié)點(diǎn)度數(shù)序列,是個(gè)H圖 e.(2,3,4,4,5可構(gòu)成連通圖的結(jié)點(diǎn)序列.但不是簡單圖,5個(gè)結(jié)點(diǎn)中有一個(gè)結(jié)點(diǎn)度為,所以不是有環(huán),就是有平行邊. f.(2,2,2,2,4)是 圖 ° 第8合分析的復(fù)習(xí)課件另考試樣題考試樣題樣題中未包含選擇題和填空題，正式考試試卷中有這兩種題型和證明題，此外樣題覆蓋的范圍也不全面。樣題的示范作用主要體現(xiàn)在題目的難度和綜合性上。一.試將下面命題符號(hào)化僅當(dāng)天不如 出差，那么小王和小兩人中要有一個(gè)出差每個(gè)大學(xué)生 一些文體活動(dòng) 沒有大學(xué)生不懂外語。(S(x):x是大學(xué)生懂得yf(x):x是外語。命題公P→Q)→P取范式。三求下面謂詞公式的真值。要求有解題的過程。x(PQ(x))∨R(a),