離散算法處理的是可以被精確區分的對象:字串、子集、整數、頂點或有限序列。一個證明必須說明哪些對象是容許的輸入、程序承諾了甚麼,以及為何每個容許的輸入都能得到所承諾的結果。邏輯與計數為這些陳述提供了語言,同時也能揭露僅憑少數幾次成功執行無法發現的錯誤。
動機
假設我們要計算長度為 、且不含兩個相鄰 1 的二進制字串的數目。對較小的 ,逐一列舉全部 個字串是可行的,但這會掩蓋其中的結構。更好的做法是按結尾將合法字串分類,並以較小輸入的計數來表示所求的計數。在實作這個遞推式之前,我們應當弄清楚:這些情形為何涵蓋了所有字串,為何它們互不重疊,以及空字串會出現甚麼情況。
正確性證明中也有同樣的責任。一個更新兩個計數的迴圈可能看似合理,但一個錯誤的初始值就會悄悄地令整個序列發生偏移。不變量把程式所儲存的值與它們本應計算的數學對象連繫起來,隨後歸納法再把這種連繫化為對所有輸入長度都成立的證明。
這些想法始於對量詞的仔細處理。「對每個輸入都存在一個正確答案」不同於「存在一個對每個輸入都正確的答案」。同樣,令字串合法的充分條件不一定刻劃了所有合法字串。在公式或算法變得複雜之前就做好這些區分,會令離散數學的學習事半功倍。
定義
定義 12.3.1
(蘊含、逆命題與逆否命題)
命題是在所討論的情境中具有真值的陳述。蘊含 僅當 為真而 為假時才不成立。它的逆否命題 與之等價;它的逆命題 則不一定等價。雙條件 要求兩個方向都成立。
定義 12.3.2
(量詞、否定與空論域)
量詞總是帶有論域。 的否定是 ;存在陳述的否定是全稱的失敗陳述。因此,要反駁「每個合法輸入都會終止」這一斷言,必須給出一個不終止的合法輸入。落在指定論域之外的畸形輸入並不能反駁該斷言。
如果論域為空,其上的全稱命題為真:沒有論域元素違反斷言。存在命題則為假,因為找不到可用的見證。這一約定由否定規則決定,並不是規則的例外。這也說明算法規格應交代實際容許哪些輸入;對空輸入類作出的保證,並不會產生一個解對象。
定義 12.3.3
(基數、雙射與劃分)
對有限集合 ,以 表示其基數。雙射 透過不遺漏、不重複地配對對象來證明 。分割把一個集合分成若干互不相交的部分,其聯集為整個集合。加法法則用於計算一個分割;乘法法則用於計算相繼的選擇,前提是每一個先前的選擇都有所述數目的可能後續。
定義 12.3.4
(迴圈不變量與正確性)
迴圈不變量是關於輸入、程式狀態與迭代指標的命題,在迴圈的前置條件下,它在每次迭代之前都成立。要在證明中使用它,需要建立初始化、保持性,以及離開迴圈時的推論。部分正確性是指:任何終止的、被容許的執行都給出所要求的答案。完全正確性在此基礎上加上終止性,而終止性通常藉一個每次迭代都嚴格遞減的非負整數量來證明。
定義 12.3.5
(合法二進制字串的計數)
設 為長度為 、由 構成且不含相鄰 1 的字串的數目。空字串只有一個,所以 ;長度為一的字串給出 。空字串是被計算的一個對象,並不表示沒有計數問題。
定理/命題
定理 12.3.6
(有限集合的容斥原理)
對某有限全集的子集 ,
這些子集不必互不相交,並且公式中的所有交集都是必需的。
定理 12.3.7
(遞推式及其經過驗證的迭代計算)
對 ,合法字串的計數滿足 。對每個整數輸入 ,下面的程序都返回 :若 ,返回 1;否則由 開始,恰好重複 次 (右邊使用舊值),然後返回 。
同時更新的約定是算法的一部分。若把它換成兩條賦值語句,而第二條意外地重用了剛更新過的第一個座標,程序就改變了。證明所驗證的是一個確切的程式,而不是一族含糊相似的更新規則。
證明思路或證明
證明
(單一元素的淨貢獻)
對於容斥原理,考察全集中單個元素 的貢獻。若它不屬於任何一個集合,則它在兩邊的貢獻都為零。若它恰屬於 個集合,則它出現在 個由 個集合構成的交集中。它在右邊的淨貢獻為
這是因為 。因此它在兩邊都恰好貢獻一次。對有限全集求和即證明該恆等式。這個論證是針對單個元素的局部論證,它解釋了為何出現三重重疊時,僅僅減去兩兩交集是不夠的。
證明
(按最後一個符號劃分)
對於遞推式,按最後一個符號分割長度為 的合法字串。以 0 結尾的字串,唯一地來自在長度為 的合法字串後面添加 0。以 1 結尾的字串必然以兩符號區塊 結尾,並唯一地來自在長度為 的合法字串後面添加該區塊。兩種構造都保持合法性,都有相應的逆操作(刪除),並且它們的像互不相交。兩者的計數相加即得所求總數。
證明透視
遞推式既需要分割,也需要逆構造
僅僅描述製造某些合法字串的兩種方式是不夠的。刪除操作證明每個目標字串都來自所提出的來源,而唯一重構則防止同一情形內部重複計算。按最後一個符號的分割則防止不同情形之間重疊。這些正是遞推式成為等式、而不僅僅是上界或下界的確切原因。
證明
(迴圈的狀態不變量)
對於程式,把已執行的更新按 編號。經過 次更新之後的不變量是 。當 時,由兩個初始計數知它成立。若它在 次更新後成立,則同時賦值給出 (由遞推式),所以不變量得以保持。經過 次更新後,。單獨的 分支返回正確的初始值。剩餘的更新次數是每次減一的非負整數,從而保證了終止性。
這一證明展示了透過程式狀態進行的普通歸納。強歸納法在邏輯上有同等效力,但容許歸納步驟使用所有更小的輸入。對遞推式本身而言,需要用到前面的兩個計數,因此既可以使用強歸納法,也可以把兩個相繼的斷言合併為一個不變量。選擇得宜的命題可以令證明更簡單,而不會令結論變弱。
歸納法為何能涵蓋每個情形
設 是關於整數 的命題。普通歸納法要求先證明基礎情形 ;再對任意 證明蘊含 。假設 只是暫時的,只能在證明該蘊含時使用。基礎情形開啟一條有效的蘊含鏈,因此每個固定的、不小於 的整數都能經過有限步到達。檢查許多單獨的情形,或只證明蘊含而沒有基礎情形,都不能提供這條鏈。
強歸納法則在證明 時,假設對每個滿足 的整數 , 都成立。當 時沒有這樣的 ,所以該步驟必須不借助假設就建立基礎情形。實際證明時,也可以先單獨證明若干初始情形,之後才使用強歸納步驟。兩種形式的效力相同:對命題 使用普通歸納,其中 斷言對所有 都有 。強歸納步驟就把 推廣為 。
同樣的推理也可用良序原理表述:每個非空的非負整數集合都有最小元素。如果強歸納步驟成立,但某個 不成立,就從失敗下標的偏移量 所成的非負整數集合中選取最小元素,並以 表示相應下標。所有更早的斷言都成立,因而該步驟又證明了這個據稱失敗的斷言,產生矛盾。這說明為何在這裏可以「選取最小反例」;沒有下界的一般整數集合未必有最小元素。
例題 12.3.8
(用強歸納法證明質因數分解的存在性)
質數是大於一、且正因數只有一和自身的整數。每個整數 都是一個或多個質數的乘積。當 時顯然成立。假設由 至 的每個整數都滿足該斷言。如果 是質數,由單個因子 構成的乘積即可。否則 ,其中整數 滿足 。由歸納假設, 和 都可分解為質數乘積;把兩個有限乘積接起來便得到 的分解。因此由強歸納法斷言成立。例如 。這裏證明的是分解的存在性,不是唯一性;唯一性需要進一步論證。
反例模式
歸納步驟不能彌補缺少的起始情形
考慮對所有 的錯誤斷言 :「 是偶數」。蘊含 為真, 也為真,但它們只能到達偶數下標。要到達奇數下標,還需要單獨的情形 ,而它是假的。每次前進兩步的步驟需要兩個起始情形才能涵蓋兩條奇偶鏈;僅驗證一個是不夠的。
對於算法,當遞歸調用可能有幾種不同的較小輸入規模時,強歸納證明很有用。證明必須說明每個調用的規模都更小,且仍屬於所述論域,然後才能對這些調用使用歸納假設。證明終止性還須考慮控制流程:如果每次調用只做有限的局部工作、發起有限次調用,且每次調用都令非負整數規模嚴格減小,那麼不可能有無限調用鏈,計算因而終止。僅證明返回時的值正確,並不能保證終止。
例題詳解
例題 12.3.9
(量詞的次序會改變命題)
對整數而言, 為真:取 。顛倒次序後的命題 為假:對於任何給定的 ,取 即可。要證明第一個命題,見證元可以依賴於被全稱選定的輸入;第二個命題則要求一個固定的見證元,它獨立於每一個輸入而成立。用算法的語言來說,由輸入計算得出的輸出不同於聲稱能解決每個實例的某個常數輸出。
例題 12.3.10
(透過重複計算的修正來計數)
在一至三十的整數中,設 為二的倍數, 為三的倍數。 中有十五個, 中有十個,交集有五個,即六的倍數。因此有二十個數可被二或三整除,有十個數二者都不能整除。若把十五與十相加而不減去五,則每個六的倍數被計了兩次。全集很重要:改變區間會改變取整的計數,儘管容斥恆等式保持不變。
例題 12.3.11
(追蹤經過驗證的狀態,而不是猜測序列)
對 ,由 開始。四次更新依次給出 、、 和 ,所以答案是十三。第三次更新之後,狀態的意思是 且 ;這並不表示兩個分量都在計算長度為五的字串。把這一詮釋始終與狀態綁在一起,可以在把停止條件翻譯成程式碼時避免差一錯誤。
迭代算法中算術加法的次數關於 是線性的,但其數值會增長。我們有 ,所以它們至多使用 個二進制位元。在通常的逐位元加法下,總的位元運算成本以 的某個常數倍為界,因而是 。這個兩變量狀態使用 個位元。只有在明確地把任意大小的整數暫存器都算作單個單位時,才可以把它描述為「常數空間」。算術運算與位元運算之間的分別在數論算法中還會再次出現。
常見錯誤
常見錯誤
(以幾個算出的情形代替證明)
若干個算出的情形是有用的檢驗,但並不能證明一個全稱命題。反過來,一個合法的反例就足以推翻它。當歸納嘗試失敗時,應當先檢查歸納命題與基礎情形,再考慮修改定理。使用 的遞推式需要足夠多的初始值,才能到達其第一個有效步驟。
常見錯誤
(誤用乘法法則)
乘法法則並不要求各選擇在概率意義上相互獨立;它要求的是關於每個階段後續數目的計數陳述。如果這個數目是變化的,就應當對相應的計數求和,而不是乘上某個方便的數值。計算有序選擇與計算無序子集所得的對象也不同:在計數之後忽略次序,需要每個對象對應的排列數是一個有依據的常數。
反例模式
順序賦值可能令正確的遞推式失效
若把更新實作為 之後再執行 ,則第二條指令使用的是新的 。由 開始,得到的是 而不是 。數學上的遞推式是正確的,只是實作不再與它一致。使用暫存變量或同時賦值即可修復該程式。
總結
量詞規定了由誰選擇每個對象,以及哪些量可以依賴於輸入。分割與雙射為精確計數提供依據;容斥原理修正重疊。歸納法證明遞推恆等式,而不變量則把這些恆等式與變化中的程式狀態連繫起來。終止性與所選取的成本模型是另外的責任,應當與答案一併清楚地呈現。
練習
快速檢查
(寫出陳述「對每個整數 ,存在一個長度為 、以 1 結尾的合法二進制字串」的否定,並判斷該陳述是否為真。)
逐個量詞取否定,再檢驗 。
解答 · 答案
否定是:存在整數 ,使得每個長度為 的合法字串都不以 1 結尾。它在 時為真,因為唯一的長度為零的字串是空字串,它沒有最後一個符號。因此原來的全稱斷言為假。把它限制在 即可修復:由 個 0 後接一個 1 構成的字串是合法的。
快速檢查
(計算一至六十的整數中,至少能被二、三、五之一整除的數目。寫出所有容斥項。)
把單個集合的計數相加,減去兩兩交集,再加回三重交集。
解答 · 答案
單個集合的計數分別為三十、二十和十二。兩兩交集的大小為十、六和四,分別來自能被六、十和十五整除的數。三重交集的大小為二,來自三十的倍數。因此聯集有 個元素。三重重疊需要加回,因為兩兩相減時把它減去的次數過多。
練習 12.3.12
(一個程式透過由 開始、把 恰好加倍 次來計算 元集合的子集數目。陳述並證明一個不變量,包括 的情形。)
核心
解答(3)
- 1
陳述不變量
關鍵一步
經過 次加倍後,,即前 個元素的子集數目。
- 2
驗證初始化與保持
起初 、,空集恰有一個子集。加入一個新元素時,每個舊子集給出兩種互不相交的可能:包含或不包含該元素,所以加倍保持了這一詮釋。
- 3
讀出離開時的值並證明終止
當 時,答案是 。記錄剩餘迭代次數的計數器每次減一,由此證明終止性,包括 時立即終止的情形。
快速檢查
(解釋為何以 1 結尾的合法字串僅當 時才由 計算,並計算 。)
想想刪去末尾的區塊 需要甚麼條件。
解答 · 答案
當 時,以 1 結尾的字串只有單個符號 1,前面沒有可刪除的 0。因此兩符號後綴的論證從 開始。基礎值 處理這一單獨的情形。利用經過驗證的遞推式,。
練習 12.3.13
(用強歸納法證明:每個整數 都是互不相同的二的非負整數次冪之和。寫出 的一個這樣的表示。)
核心證明
解答(4)
- 1
基礎情形
。
- 2
分出奇偶
關鍵一步
對 ,令 、,則 ,且 為零或一。
- 3
對 應用歸納假設
是互不相同的二的冪之和。將其加倍,得到 的表示,其中各冪的指數都至少為一。
依據: 假設涵蓋由 至 的每個整數。
- 4
補上餘數
∎若 ,再加上 ,不會重複任何冪。因此結論對 成立。例如 。這個論證證明了存在性,但沒有證明唯一性。