動機
本章的圖歸約以三文字子句為起點。為甚麼這種看似受限的輸入能表達任意布爾(Boole)公式?反覆使用分配律,可能產生巨大的等價合取範式。多項式歸約需要另一種中間結果表示。
核心辦法是為每個子公式的值命名,用少量子句約束局部計算,再用最後一個子句要求整個公式為真。下面證明變換保留哪些賦值,特別說明新變量和短子句的作用。
定義
定義 4.2.1
(布爾公式與賦值)
布爾公式是一棵有限有根樹,葉子為變量或常量,內部節點為一元否定、二元合取或二元析取。大小 是節點數;同一子公式寫兩次就佔兩個子樹。賦值為每個出現的變量指定布爾值,並從葉到根計算。
定義 4.2.2
(文字、子句與 3-SAT)
文字是變量或其否定,子句是若干文字出現的析取,CNF 是子句的合取。空子句為假,零個子句的合取為真。本節 3-SAT 要求每個子句恰有三個文字出現,允許變量或文字重複,與配套圖歸約按出現位置構造的約定一致。
定義 4.2.3
(新變量與賦值擴張性質)
輔助變量必須另取:既不同於原變量,也不同於其他節點或子句的輔助變量。若 使用原變量 和輔助變量 ,稱它對 有賦值擴張性質,是指對每個 上的賦值 ,
這不只說明兩個公式同時可滿足或同時不可滿足,還明確了目標滿足賦值如何投影回原變量。若任意獨立選擇輔助值,較大公式並不一定與原公式等價。
定理/命題
定理 4.2.4
(局部邏輯閘子句強制精確的閘值)
以下子句分別等價於所示的布爾等式:
為每個非變量節點命名,加入這些等式,並對常量節點加入單位子句,則每個原賦值恰有一個輔助擴張。再要求根標籤為真,便得到原公式的賦值擴張性質。
定理 4.2.5
(到恰三次文字出現的多項式變換)
對有 個節點的公式,邏輯閘構造後再填充短子句,得到至多 個子句的恰三文字出現 CNF,並保持賦值擴張性質。另一種直接辦法把長度 的非空子句,換成使用 個新變量的 個三文字子句,對原變量保持同樣性質。空子句與空合取另按下文處理。
定理 4.2.6
(明確起點後的 3-SAT 完全性)
恰三文字出現的 3-SAT 屬於 NP。公式變換給出 SAT 到本版本 3-SAT 的多項式時間多對一歸約。因此,以 SAT 的標準 NP 完全性為前提,本版本 3-SAT 是 NP 完全的。建立 SAT 起點的計算到公式定理仍是引入的依賴,並未由這裏的變換證明。
所引起點可見 Stephen Cook 的官方 P 與 NP 問題說明第2節第5頁。下面在本課程內完整證明限制公式形狀的這一步。
證明思路
邏輯閘等式的兩個方向都要約束
對每個非變量節點 引入 ,變量葉子保留原標籤。常量一加入子句 ,常量零加入 。連接詞節點採用上述子句,自己的標籤作輸出,子節點標籤作輸入。最後加入只含根標籤的單位子句。若公式就是一個變量,根標籤就是該變量,只需最後這個子句。
證明
(邏輯閘子句算出各節點的值)
AND 閘的前兩個子句說明 迫使 ,第三個說明 迫使 ,合起來恰好給出合取值,而不是僅有一個蘊含。OR 閘的前兩個子句使任一輸入為一時 必為一,第三個排除輸入都零但輸出一。NOT 閘的兩個子句排除輸入輸出同為零或同為一,只留下相反取值。
給定原賦值,計算整棵樹並令每個 等於節點值,便滿足全部邏輯閘和常量子句。反過來,從子節點向父節點歸納,每個滿足這些子句的賦值都必須採用相同節點值。因此加入根斷言之前輔助擴張唯一;加入之後,當且僅當原根值為一時存在擴張。限制任一目標滿足賦值到原變量,也就給出原公式的滿足賦值,反方向同樣成立。
證明透視
局部一致與全局接受分別需要條件
即使最後結果為假,邏輯閘子句仍能描述一次真實計算。根單位子句要求這次計算接受。為不同節點分別另取變量,使各處計算可以共存,不會意外把無關值認作同一變量。反方向依賴每個局部等式,不能假設提交證書的人已誠實填寫所有輔助標籤。
同時控制短子句和長子句
每個邏輯閘至多給出三個長度不超過三的子句,常量給一個,根斷言再給一個。非變量節點至多 個,故總數至多 。把單位子句 換成 ,把二文字子句 換成 。重複文字不改變真假、不增加變量,因而保持擴張性質,並使每個子句恰有三次文字出現。
概念視角組合
把閘子句看成被禁止的行
含三個不同變量的子句,在它們的八種賦值中恰好有一種使它為假,所以它禁止那一行。等式 在 的八行中有四行成立,其餘四行必須被禁止。子句 禁止行 ;子句 與 合起來禁止 、、 三行。這四行恰好就是不一致的行。
若輸入已經是 CNF,可以直接處理長子句。對 ,,引入 ,使用
證明
(子句鏈保持可擴張性)
原文字全假時,首子句迫使 ,中間子句依次迫使所有後續輔助變量為一,最終子句卻為假。原子句至少有一個真文字時,令 當且僅當前 個原文字全假。首子句由此成立。中間子句若 已成立;否則,要麼該原文字真,要麼下一輔助變量為一。若最後的輔助變量為一,原子句為真便迫使最後兩個文字至少一個真。因此全部新子句成立。兩端子句加上 個中間子句,共 個; 時中間族為空。
證明透視
為甚麼輔助變量標記的是一段假文字的前綴
每個輔助變量 都像一面旗,表示前 個原文字全為假。第一個子句在 都為假時把旗升起;每個中間子句把旗傳下去,除非下一個原文字為真;最後一個子句在旗傳到 之後,要求 之中有一個為真。「原子句為假則不可滿足」這個方向只用到旗被一路強制升起。
不顯而易見的是另一個方向中 的取法。旗必須在第一個為真的文字之後恰好放下:若把所有 都設為 ,當唯一為真的文字是 時就會失敗,因為此時最後的子句中 為假,而 也都為假。證明最後分別檢查三種子句形式,這就是兩端子句與中間子句要分開處理的原因。
不同原子句使用不同輔助變量,才能組合各自的擴張。長度一、二的子句按前法填充,長度三保持。若原 CNF 含任一空子句,整個公式不可滿足,直接輸出固定矛盾 。若原來零個子句,則可滿足,可以保留為空目標合取。這些邊界均是構造的一部分。
歸約既要正確,也要有規模界
證明
(多項式規模與屬於 NP)
邏輯閘構造沒有用分配律展開子樹,而是每節點寫常數個子句。設原編碼位元長度為 ,用節點編號命名新變量,並與一致重新命名後的原變量區分。每次原變量出現只被複製常數次,新編號用 位元,因此目標位元長度為 。解析、命名和寫出都可在多項式時間內完成。直接 CNF 構造在邏輯層面也只與原文字出現次數成線性關係,編碼長度仍多項式有界。
格式錯誤的原字串送到固定矛盾,使歸約對所有輸入有定義,而無須先解可滿足性。擴張性質給出所需的肯定與否定答案等價。驗證 NP 成員關係時,證書為每個不同目標變量提供一個位元,變量數不超過文字出現數;解析、檢查證書長度、計算所有子句都只需輸入編碼長度的多項式時間。空目標合取用空證書即可接受。成員關係和歸約共同把已聲明的 SAT 困難性傳遞到 3-SAT。
例題詳解
例題 4.2.7
(沿節點標籤計算公式)
對 ,用 、、。邏輯閘子句分別有三、二、三個,再加根單位子句,共九個,填充前後數量不變。 時唯一擴張為 ,滿足根斷言。 時唯一擴張為 ,不滿足根子句。不能換一組輔助值來修補這個假的原賦值。
例題 4.2.8
(拆分五文字子句)
對 ,使用 、、。在 時,前兩個子句迫使 ,末子句因 而成立。若 也變零,五個原文字全假,同樣被迫的輔助值就使末子句失敗,不存在滿足擴張。
例題 4.2.9
(短子句與空子句各有明確含義)
子句 變為 , 變為 。空原子句在公式層面換成上述兩個矛盾子句,因為它已使整個合取為假。沒有任何子句的 CNF 卻為真。把空子句與空子句集合混同,會在應用任何構造前就把答案顛倒。
例題 4.2.10
(擴張不一定總是唯一)
四文字子句 拆成 。若四個原變量全真, 的兩個值都可行。鏈編碼保留擴張是否存在,卻可能引入多個擴張。完整邏輯閘編碼則有前面證明的唯一性。可滿足性歸約本身不保證保留滿足賦值的數量。
常見錯誤
反例模式
單向邏輯閘約束可能接受假的原賦值
對 ,若只用 約束內層標籤 ,外層標籤 保留正確 NOT 子句並斷言 。當 時,選 可滿足全部弱化約束,原公式卻為假。缺失的子句 恰好排除此錯誤內層值。每個邏輯閘都需要完整的等式約束。
常見錯誤
(不同構件之間重用新變量)
新變量不能在互不相關的構件之間重用。每個原子句或邏輯閘都需要自己的輔助變量,這樣不同構件各自選取的擴張才互相獨立,可以合併在一起。
常見錯誤
(用分配律展開而不是為子公式命名)
歸約需要多項式的輸出規模。直接對 用分配律展開,會為「從每一對中各取一個變量」的每種選法產生一個子句,共 個子句。這種展開不能說明歸約是多項式的;為每個子公式命名,則每個節點只寫常數個子句。
常見錯誤
(以為三個文字必須是不同的變量)
這裏採用的慣例是「恰好三個文字出現位置,容許重複」。若要求三個文字來自不同變量,需要另外的構造,本節並未悄悄包含。
總結
新節點標籤與完整邏輯閘等式描述唯一計算,根斷言篩選結果為真的計算。重複填充不改變短子句的含義,長析取鏈保留擴張存在性。多項式編碼界與 NP 驗證共同完成 SAT 到 3-SAT 的歸約,SAT 的起點完全性仍明確作為前提。
練習
快速檢查
(分別考慮 與 ,證明 OR 閘的三個子句強制 。)
三個子句是 、 與 。
解答 · 答案
時,前兩個子句變成 與 ,迫使兩個輸入都為零;第三個子句已經成立。 時,前兩個子句成立,第三個子句要求 。這正是 等於析取的各種情形;反過來,這些情形滿足全部子句。
快速檢查
(給出 的恰好三個文字出現位置的邏輯閘編碼,並驗證哪些原賦值能擴張為滿足的目標賦值。)
把 NOT 節點命名為 ,並在根上斷言 。
解答 · 答案
取新標籤 及子句 、 和 。 時, 滿足它們。 時,NOT 子句迫使 ,與輸出子句矛盾,所以沒有擴張。重複文字補足長度三,而不改變任何一個蘊涵關係。
練習 4.2.11
(寫出六個文字的子句所對應的鏈。證明原文字全為假時產生矛盾,並說明原子句為真時的滿足擴張。)
核心
解答(3)
- 1
寫出子句鏈
、、 以及 。
依據: 時有 個輔助變量和 個子句。
- 2
處理全為假的情形
關鍵一步
若所有 都為假,第一個子句迫使 ,接著第二個迫使 ,第三個迫使 ,最後的子句 變為假。沒有任何擴張能滿足這條鏈。
依據: 每個子句都迫使下一個輔助變量取一。
- 3
處理原子句為真的情形
令 當且僅當 全為假。第一個子句成立,因為 全為假時 。中間子句在 時成立;若 ,則要麼 為真,要麼 全為假,從而 。若 ,則 都為假,所以原子句中為真的文字是 或 ,最後的子句成立。
快速檢查
(某個編碼對每個邏輯閘都用了正確的子句,卻漏掉根節點的斷言。它的可滿足性能否推出原公式可滿足?請給出反例,並說明為甚麼僅憑子句數目的界不能建立正確的歸約。)
試試 。
解答 · 答案
不能。對 ,每個原賦值仍然有對所有節點的如實求值,儘管根的值永遠為零。沒有根的單位子句時,邏輯閘約束是可滿足的,而原公式不可滿足。多項式規模與語義正確性是兩項各自獨立的證明責任;要得到所需的對應關係,必須有根的子句。