1. 離散數(shù)學(xué)第二章到底在講什么1.1 從“集合”到“關(guān)系”這一章的核心脈絡(luò)離散數(shù)學(xué)第二章絕大多數(shù)教材安排的都是關(guān)系。但很多人翻開書第一眼看到的卻是“二元關(guān)系”“笛卡爾積”“自反閉包”這些詞直接就被勸退了。我當(dāng)初學(xué)這一章的時(shí)候也是這個(gè)感覺——明明第一章命題邏輯還能靠真值表硬推到了第二章突然全是符號(hào)和定義完全不知道在干什么。后來刷了幾套題、又回頭把章節(jié)從頭捋了一遍才發(fā)現(xiàn)這一章的脈絡(luò)其實(shí)非常清晰集合是基礎(chǔ)笛卡爾積是工具關(guān)系是主角閉包和等價(jià)關(guān)系是應(yīng)用。整章就是圍繞“兩個(gè)集合里的元素之間怎么建立聯(lián)系”這件事展開的。你把這條線抓住后面那些定義就不是孤立的了。具體來說這一章要解決的核心問題是給定兩個(gè)集合A和B它們之間的元素可以按照某種規(guī)則配對這些配對構(gòu)成的整體就是“關(guān)系”。然后我們關(guān)心這個(gè)關(guān)系有什么性質(zhì)自反、對稱、傳遞能不能通過運(yùn)算得到新的關(guān)系復(fù)合、逆以及怎么把一個(gè)不滿足性質(zhì)的關(guān)系“修補(bǔ)”成滿足性質(zhì)的關(guān)系閉包。最后落到兩類特殊關(guān)系上等價(jià)關(guān)系和偏序關(guān)系它們分別對應(yīng)“分類”和“排序”這兩種最基本的數(shù)學(xué)操作。提示如果你用的是國內(nèi)常見的那幾本教材第二章的標(biāo)題可能叫“二元關(guān)系”也可能叫“關(guān)系”但內(nèi)容范圍基本一致。先翻目錄確認(rèn)一下章節(jié)邊界別把第三章的函數(shù)內(nèi)容混進(jìn)來。1.2 為什么這一章讓這么多人卡住我觀察下來卡住的原因主要有三個(gè)。第一個(gè)是符號(hào)密度突然變大。第一章命題邏輯雖然也有符號(hào)但好歹還能翻譯成大白話。到了關(guān)系這一章一個(gè)定義里能出現(xiàn)五六個(gè)新符號(hào)比如“R?A×B”“?a∈A, (a,a)∈R”這種讀起來像天書。其實(shí)這些符號(hào)拆開看都不難難的是它們堆在一起的時(shí)候大腦處理不過來。第二個(gè)是定義之間的依賴關(guān)系沒理清。比如“自反”和“反自反”是互斥的但不是互補(bǔ)的一個(gè)關(guān)系可以既不自反也不反自反“對稱”和“反對稱”也是類似的情況。很多人學(xué)到后面把前面的定義忘了做題的時(shí)候張冠李戴。第三個(gè)是覺得這東西沒用。我當(dāng)初也這么想——關(guān)系關(guān)系跟我寫代碼有什么關(guān)系后來做數(shù)據(jù)庫的范式分析、做編譯原理的語法分析才發(fā)現(xiàn)關(guān)系代數(shù)那套東西全是這一章的地基。甚至你平時(shí)用的Excel篩選、SQL的JOIN操作底層都是二元關(guān)系在撐著。這么一想學(xué)它的動(dòng)力就足多了。1.3 學(xué)完這一章你應(yīng)該具備什么能力給自己定個(gè)驗(yàn)收標(biāo)準(zhǔn)學(xué)完這一章你應(yīng)該能做到以下幾件事給定一個(gè)具體的關(guān)系比如“整除關(guān)系”“模3同余關(guān)系”能判斷它是否滿足自反、對稱、傳遞等性質(zhì)能計(jì)算兩個(gè)關(guān)系的復(fù)合和逆關(guān)系能求一個(gè)關(guān)系的自反閉包、對稱閉包、傳遞閉包能判斷一個(gè)關(guān)系是不是等價(jià)關(guān)系如果是能寫出它的等價(jià)類能畫出一個(gè)偏序關(guān)系的哈斯圖并找出極大元、極小元、最大元、最小元能把關(guān)系用集合、矩陣、有向圖三種方式表示并在它們之間自由轉(zhuǎn)換這六條你要是都能做到這一章就算過關(guān)了。下面我按這個(gè)目標(biāo)來拆解每個(gè)知識(shí)點(diǎn)的核心細(xì)節(jié)。2. 核心概念逐個(gè)拆解2.1 有序?qū)εc笛卡爾積關(guān)系的原材料有序?qū)褪莾蓚€(gè)元素按固定順序放在一起記作(a,b)。關(guān)鍵在“有序”兩個(gè)字——(a,b)和(b,a)是不同的除非ab。這個(gè)看起來簡單但后面很多性質(zhì)的判斷都依賴這一點(diǎn)。笛卡爾積A×B就是把A中每個(gè)元素和B中每個(gè)元素配對所有可能的配對構(gòu)成一個(gè)集合。比如A{1,2}B{x,y}那A×B{(1,x),(1,y),(2,x),(2,y)}。如果A有m個(gè)元素B有n個(gè)元素A×B就有m×n個(gè)元素。這里有個(gè)容易踩的坑A×B和B×A一般不一樣。上面那個(gè)例子B×A{(x,1),(x,2),(y,1),(y,2)}跟A×B完全不同。只有當(dāng)AB或者其中一個(gè)為空集的時(shí)候兩者才可能相等。我當(dāng)初做課后題的時(shí)候就在這上面栽過題目問A×BB×A的條件我直接寫了AB其實(shí)還要考慮空集的情況。注意空集參與笛卡爾積的規(guī)則是A×???×B?。這個(gè)在證明題里經(jīng)常用到別記反了。2.2 關(guān)系的定義與三種表示法關(guān)系R就是從A×B中取一個(gè)子集。如果(a,b)∈R就說a和b有關(guān)系R記作aRb。如果AB就說R是A上的關(guān)系。關(guān)系的三種表示法必須都會(huì)因?yàn)椴煌}目用不同表示法做起來效率差很多集合表示法最直接就是把所有有序?qū)α谐鰜?。適合元素少的情況元素一多就寫不下了。矩陣表示法關(guān)系矩陣適合判斷性質(zhì)和做復(fù)合運(yùn)算。行對應(yīng)A的元素列對應(yīng)B的元素如果(a?,b?)∈R矩陣第i行第j列就是1否則是0。判斷自反就看主對角線是不是全1判斷對稱就看矩陣是不是對稱矩陣。復(fù)合運(yùn)算直接做布爾矩陣乘法比一個(gè)個(gè)配對快得多。有向圖表示法適合直觀理解。每個(gè)元素畫一個(gè)節(jié)點(diǎn)如果(a,b)∈R就畫一條從a到b的有向邊。自反就是每個(gè)節(jié)點(diǎn)都有自環(huán)對稱就是每條邊都有反向邊傳遞就是如果有a→b和b→c就一定有a→c。我個(gè)人的習(xí)慣是判斷性質(zhì)用矩陣?yán)斫夂x用圖寫證明用集合。三種切換著來效率最高。2.3 五大性質(zhì)自反、反自反、對稱、反對稱、傳遞這五個(gè)性質(zhì)是這一章的核心考點(diǎn)必須爛熟于心。我逐個(gè)說清楚順便把容易混淆的地方標(biāo)出來。自反性對A中每個(gè)元素a都有(a,a)∈R。關(guān)鍵詞是“每個(gè)”。只要有一個(gè)元素沒有自環(huán)就不滿足自反。反自反性對A中每個(gè)元素a都有(a,a)?R。關(guān)鍵詞還是“每個(gè)”。注意自反和反自反不是互補(bǔ)的——一個(gè)關(guān)系可以既不自反也不反自反。比如A{1,2,3}R{(1,1),(2,2)}它既不是自反的3沒有自環(huán)也不是反自反的1和2有自環(huán)。對稱性如果(a,b)∈R那么(b,a)∈R。注意這里不要求a≠b所以自環(huán)不影響對稱性。反對稱性如果(a,b)∈R且(b,a)∈R那么ab。換句話說除了自環(huán)之外不能有雙向邊。這里最容易搞混的是“反對稱”不是“不對稱”——反對稱允許自環(huán)存在只是不允許兩個(gè)不同元素之間有雙向邊。傳遞性如果(a,b)∈R且(b,c)∈R那么(a,c)∈R。這個(gè)性質(zhì)判斷起來最麻煩因?yàn)橐獧z查所有可能的三元組。用矩陣表示的話就是M2的每個(gè)非零位置在M中也是非零的。我整理了一個(gè)速查表做題的時(shí)候?qū)φ罩葱再|(zhì)集合語言矩陣特征圖特征自反?a∈A, (a,a)∈R主對角線全1每個(gè)節(jié)點(diǎn)有自環(huán)反自反?a∈A, (a,a)?R主對角線全0每個(gè)節(jié)點(diǎn)無自環(huán)對稱(a,b)∈R→(b,a)∈R矩陣對稱邊成對出現(xiàn)反對稱(a,b)∈R∧(b,a)∈R→ab非對角元不能同時(shí)為1不同節(jié)點(diǎn)間無雙向邊傳遞(a,b)∈R∧(b,c)∈R→(a,c)∈RM2≤M布爾有路徑必有直達(dá)邊實(shí)操心得判斷傳遞性的時(shí)候先看有沒有長度為2的路徑。如果沒有直接判定滿足傳遞性。如果有再檢查每條長度為2的路徑是否都有對應(yīng)的直達(dá)邊。這樣比盲目檢查所有三元組快很多。2.4 復(fù)合運(yùn)算與逆關(guān)系關(guān)系的復(fù)合本質(zhì)上就是“接力”R是從A到B的關(guān)系S是從B到C的關(guān)系那R°S就是從A到C的關(guān)系定義為{(a,c) | ?b∈B, (a,b)∈R且(b,c)∈S}。這里有個(gè)符號(hào)方向的坑。不同教材對復(fù)合的記法可能不同有的寫R°S表示先R后S有的反過來。做題之前先確認(rèn)你用的教材是哪種約定不然結(jié)果會(huì)反。我當(dāng)初換了一本參考書就對不上了折騰了好久。用矩陣做復(fù)合最方便R的矩陣乘以S的矩陣乘法用布爾運(yùn)算加法是邏輯或乘法是邏輯與得到的就是復(fù)合關(guān)系的矩陣。元素少的時(shí)候手算也不容易出錯(cuò)。逆關(guān)系就是把所有有序?qū)Ψ催^來R?1{(b,a) | (a,b)∈R}。矩陣表示就是轉(zhuǎn)置圖表示就是把所有邊反向。逆關(guān)系有個(gè)好用的性質(zhì)(R°S)?1S?1°R?1注意順序要反過來。2.5 閉包把關(guān)系“修補(bǔ)”成想要的樣子閉包這個(gè)概念第一次看會(huì)覺得抽象其實(shí)用一句話就能說清楚給一個(gè)關(guān)系加上最少的元素讓它滿足某個(gè)性質(zhì)。自反閉包r(R)R∪I_A其中I_A是恒等關(guān)系{(a,a) | a∈A}。就是把所有缺失的自環(huán)補(bǔ)上。對稱閉包s(R)R∪R?1。就是把所有單向邊變成雙向邊。傳遞閉包t(R)最復(fù)雜需要反復(fù)加邊直到?jīng)]有新的長度為2的路徑為止。手工計(jì)算的時(shí)候用Warshall算法最靠譜雖然名字聽起來嚇人但步驟很機(jī)械照著做就行。Warshall算法的核心思想是對于每個(gè)中間節(jié)點(diǎn)k檢查所有節(jié)點(diǎn)對(i,j)如果i能到k且k能到j(luò)就讓i能到j(luò)。用矩陣表示就是三重循環(huán)代碼寫出來不到十行def warshall(M, n): # M是n×n的布爾矩陣 for k in range(n): for i in range(n): for j in range(n): M[i][j] M[i][j] or (M[i][k] and M[k][j]) return M這個(gè)算法的時(shí)間復(fù)雜度是O(n3)對于手工計(jì)算來說n一般不超過5完全夠用。注意傳遞閉包的計(jì)算容易漏邊。我的經(jīng)驗(yàn)是每輪迭代后把矩陣畫出來標(biāo)出新增的1下一輪基于新矩陣?yán)^續(xù)。別跳步跳步必錯(cuò)。3. 兩類特殊關(guān)系等價(jià)與偏序3.1 等價(jià)關(guān)系與集合的劃分等價(jià)關(guān)系就是同時(shí)滿足自反、對稱、傳遞三個(gè)性質(zhì)的關(guān)系。它之所以重要是因?yàn)樗汀皠澐帧笔且灰粚?yīng)的。給定一個(gè)等價(jià)關(guān)系R我們可以把集合A分成若干個(gè)等價(jià)類。每個(gè)等價(jià)類里的元素互相等價(jià)不同等價(jià)類之間的元素不等價(jià)。所有等價(jià)類構(gòu)成的集合就是A的一個(gè)劃分。舉個(gè)最經(jīng)典的例子模3同余關(guān)系。在整數(shù)集上定義aRb當(dāng)且僅當(dāng)a-b能被3整除。這是一個(gè)等價(jià)關(guān)系它把整數(shù)分成了三個(gè)等價(jià)類余0的、余1的、余2的。這三個(gè)類互不相交并起來正好是全體整數(shù)。判斷等價(jià)關(guān)系的關(guān)鍵是三個(gè)性質(zhì)缺一不可。我見過有人只驗(yàn)證了自反和對稱就下結(jié)論結(jié)果傳遞性不滿足整個(gè)判斷就錯(cuò)了。傳遞性的驗(yàn)證不能偷懶。3.2 偏序關(guān)系與哈斯圖偏序關(guān)系是同時(shí)滿足自反、反對稱、傳遞三個(gè)性質(zhì)的關(guān)系。注意這里是對稱換成了反對稱。偏序關(guān)系描述的是“排序”的概念但不是所有元素都能比較。比如集合的包含關(guān)系?就是一個(gè)偏序關(guān)系A(chǔ)?A自反A?B且B?A則AB反對稱A?B且B?C則A?C傳遞。但兩個(gè)集合之間可能互不包含所以不是任意兩個(gè)元素都能比較。哈斯圖是偏序關(guān)系的專用圖示法畫法有講究去掉所有自環(huán)因?yàn)樽苑词悄J(rèn)的去掉所有由傳遞性產(chǎn)生的邊只保留“直接覆蓋”關(guān)系把方向隱含在位置中——如果ab就把a(bǔ)畫在b下面畫哈斯圖的時(shí)候?qū)蛹?jí)關(guān)系要搞清楚。如果ab且中間沒有其他元素c使得acb就說b覆蓋a哈斯圖里畫一條從a到b的線。這個(gè)“覆蓋”的概念是畫圖的關(guān)鍵。在哈斯圖上找特殊元素極大元沒有比它更大的元素可能在最上層但最上層可能有多個(gè)極小元沒有比它更小的元素最大元比所有元素都大如果存在一定唯一且一定是極大元最小元比所有元素都小如果存在一定唯一且一定是極小元最大元和極大元的區(qū)別是高頻考點(diǎn)。最大元要求跟所有元素都可比較且最大極大元只要求沒有比它更大的。一個(gè)偏序集可能有多個(gè)極大元但沒有最大元。4. 常見問題與排查技巧4.1 性質(zhì)判斷的典型錯(cuò)誤我整理了幾個(gè)最容易出錯(cuò)的地方做題的時(shí)候重點(diǎn)檢查錯(cuò)誤一把“反自反”當(dāng)成“不自反”。反自反要求每個(gè)元素都沒有自環(huán)不自反只需要有一個(gè)元素沒有自環(huán)就行。這兩個(gè)條件強(qiáng)弱完全不同。錯(cuò)誤二反對稱和對稱搞混。對稱是“有a→b就有b→a”反對稱是“有a→b和b→a就說明ab”。一個(gè)關(guān)系可以既對稱又反對稱比如恒等關(guān)系。錯(cuò)誤三傳遞性驗(yàn)證不完整。只檢查了部分三元組就下結(jié)論。必須檢查所有滿足前件的情況。錯(cuò)誤四閉包計(jì)算時(shí)順序搞錯(cuò)。求傳遞閉包的時(shí)候每加一條邊都可能產(chǎn)生新的長度為2的路徑必須迭代到不動(dòng)點(diǎn)為止。4.2 復(fù)合運(yùn)算的排查方法復(fù)合運(yùn)算R°S出錯(cuò)通常是因?yàn)橹虚g集合B的元素沒對齊復(fù)合順序搞反了布爾矩陣乘法當(dāng)成了普通乘法排查方法先用集合表示法手動(dòng)配幾對再用矩陣驗(yàn)證。如果兩種方法結(jié)果一致基本就不會(huì)錯(cuò)了。4.3 哈斯圖繪制的注意事項(xiàng)哈斯圖畫錯(cuò)通常是因?yàn)橥巳サ魝鬟f邊層級(jí)位置畫錯(cuò)導(dǎo)致方向混亂覆蓋關(guān)系判斷錯(cuò)誤我的建議是先用集合表示法列出所有有序?qū)θ缓笾饌€(gè)判斷覆蓋關(guān)系最后再畫圖。畫完之后從下往上檢查一遍看有沒有遺漏的覆蓋關(guān)系。5. 我踩過的坑和總結(jié)的技巧5.1 符號(hào)系統(tǒng)的統(tǒng)一不同教材的符號(hào)約定可能不同比如復(fù)合的記法、閉包的記法、甚至自反閉包的符號(hào)都有差異。我的建議是以你上課用的教材為準(zhǔn)其他參考書只用來對照理解不要混用符號(hào)。我當(dāng)初就是看了兩本書符號(hào)混著用做題的時(shí)候自己都搞不清在寫什么。5.2 從具體例子入手遇到抽象的定義先找一個(gè)具體的例子套進(jìn)去。比如學(xué)等價(jià)關(guān)系的時(shí)候先用模3同余這個(gè)例子把定義走一遍再回頭看抽象定義就清楚多了。學(xué)偏序關(guān)系的時(shí)候先用集合包含關(guān)系走一遍。具體例子是理解抽象概念的最短路徑。5.3 三種表示法的轉(zhuǎn)換練習(xí)我強(qiáng)烈建議做這樣一個(gè)練習(xí)隨便寫一個(gè)關(guān)系分別用集合、矩陣、圖表示出來然后從每種表示法出發(fā)判斷五個(gè)性質(zhì)。這個(gè)練習(xí)做上五六組這一章的核心內(nèi)容就通了。我當(dāng)時(shí)是找了課后習(xí)題里所有的關(guān)系題每組都畫了矩陣和圖雖然費(fèi)時(shí)間但做完之后做題速度明顯上來了。5.4 等價(jià)類與劃分的對應(yīng)關(guān)系等價(jià)關(guān)系和劃分是一一對應(yīng)的這個(gè)結(jié)論在做題的時(shí)候非常有用。如果題目讓你求一個(gè)等價(jià)關(guān)系對應(yīng)的劃分你只需要把等價(jià)類找出來就行。反過來如果給你一個(gè)劃分讓你構(gòu)造對應(yīng)的等價(jià)關(guān)系你就把每個(gè)劃分塊里的元素兩兩配對再加上自環(huán)就得到了等價(jià)關(guān)系。這個(gè)對應(yīng)關(guān)系在數(shù)據(jù)庫的范式分解里也有應(yīng)用不過那是后話了。5.5 傳遞閉包的快速計(jì)算手工計(jì)算傳遞閉包的時(shí)候Warshall算法雖然機(jī)械但容易算錯(cuò)。我的技巧是先把關(guān)系矩陣寫出來然后逐列處理。處理第k列的時(shí)候看這一列哪些行是1這些行對應(yīng)的行向量全部按位或到其他行上。這樣比三重循環(huán)手算快而且不容易漏。舉個(gè)例子如果第2列的第1行和第3行是1那就把第1行和第3行分別或到所有行上。這個(gè)操作可以批量做比一個(gè)個(gè)元素檢查快得多。5.6 偏序關(guān)系中的特殊元素找極大元、極小元、最大元、最小元的時(shí)候直接在哈斯圖上操作最直觀極大元沒有向上的邊連出去的節(jié)點(diǎn)極小元沒有向下的邊連進(jìn)來的節(jié)點(diǎn)最大元如果存在一個(gè)節(jié)點(diǎn)能到達(dá)所有其他節(jié)點(diǎn)沿向上的路徑它就是最大元最小元如果存在一個(gè)節(jié)點(diǎn)能被所有其他節(jié)點(diǎn)到達(dá)它就是最小元注意最大元/最小元可能不存在但極大元/極小元一定存在有限偏序集。這一章的內(nèi)容看起來多但核心就是“關(guān)系”這一個(gè)概念在不同角度下的展開。把定義吃透把三種表示法練熟把等價(jià)和偏序這兩類特殊關(guān)系搞清楚后面第三章的函數(shù)就是水到渠成的事。我當(dāng)初在這一章花了大概兩周時(shí)間前一周完全在云里霧里后一周把課后題刷了一遍才突然通透。所以如果你現(xiàn)在也覺得懵別急多做題做著做著就明白了。