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