動機
一個邏輯表達式可以有多種寫法,卻在每種情況下表達相同判斷。真值表把這種含義逐行列清楚,子句形式則便於系統尋找滿足賦值。不過這些表示的大小不一定相近:直接列出的表可能比原公式大得多,甚至以指數級增長。
本節構造兩種完全等價的範式,證明歸結消元恰好保留可擴張的賦值,再謹慎引入輔助變量。緊湊編碼可以保留是否存在解,卻不一定是同一組變量上的等價公式。
賦值與等價
定義 12.1.1
(賦值、等價、可滿足與有效)
固定一個有限的互不相同的布爾(Boole)變量列表。賦值為每個所列變量指定假或真。連接詞 、、 按通常的真值規則計算;常量 和 分別表示假和真。定義蘊含與雙條件為
若對出現在兩個公式中任一處的所有變量的每個賦值,公式 、 取值相同,就稱它們等價,記為 。至少有一個賦值使公式為真時稱其可滿足;每個賦值都使其為真時稱其有效。因此 當且僅當 有效。
把較大公式中的子公式替換為一個等價式,較大公式的值不變:可對周圍連接詞作歸納證明。
定義 12.1.2
(文字、子句、項與範式)
文字是變量或變量的否定。子句是有限多個文字的析取,項是有限多個文字的合取。合取範式(CNF)是子句的合取;析取範式(DNF)是項的析取。重複文字或重複子句可刪去。一個子句若同時含變量和其否定,就恆真,可從合取中刪去;一個項若同時含二者,就恆假,可從析取中刪去。
空子句是 ,空項是 。零個子句的空合取是 ;零個項的空析取是 。這些約定也使無變量公式和消元邊界一致。
定理 12.1.3
(每個真值表都有兩種精確範式)
對所聲明的 個變量上的任何公式,都可構造僅用同一列表變量且與原式等價的 DNF 和 CNF。規範 DNF 為每個取真的行構造一項,規範 CNF 為每個取假的行構造一個子句。總共有 行,包括 時的一行。
如何構造範式
證明
(逐行分離)
對每個賦值 ,構造一個項:在 下為真的變量正向出現,為假的變量取否定。該項恰好只在行 為真。把屬於真行的項全部析取,結果就與原式有相同真值表。如果沒有真行,使用空析取 。
構造 CNF 時則令子句恰在 為假:行中為真的變量取否定,為假的變量正向出現。把所有假行對應的子句合取。任何不同賦值都滿足該假行對應的子句,所以結果恰好拒絕原式的所有假行。若沒有假行,使用空合取 。當 時,唯一一行按情況產生空項或空子句。
證明透視
一行就是一次精確檢驗
這裏只有一個想法:用一次檢驗就能分離出一行。由真行 構造的項是與 完全吻合的文字的合取,所以它在 為真,在其他行都為假:任何其他行至少在一個變量上與 不同,使相應文字為假。由假行構造的子句則使用相反的符號,所有文字在 取假,因此子句恰在該行為假;其他行在不同的變量上滿足相應文字。符號相反,是因為合取只要一個文字失敗就失敗,而析取要所有文字都失敗才失敗。論證以真值表決定公式作結:把全部真行的項析取,或把全部假行的子句合取,就重現每一行。只用到變量列表有限這一點。
這個構造既證明存在,也給出明確算法,但可能寫出多達 次文字出現。簡短公式可能有更短的非規範範式;真值表構造只給上界,不聲稱表達式最短。反過來,任何必須顯式輸出大範式的算法都要支付輸出成本,無論輸入多短。
若要否定一個等價斷言,只需給出兩式取值不同的一個賦值;若用真值表證明等價,則必須檢查每一行,包括只在其中一個公式出現的變量的賦值。這樣,代數式的改寫是否正確就成為可檢驗的語義問題。
常見恆等式 和 也可逐一檢查相應兩輸入或三輸入真值表的所有行。隨後利用等價替換可在較大公式內應用。此類改寫很有用,但某個分配步驟次序不保證結果最短。
歸結與精確消元
定義 12.1.4
(歸結式)
設 與 是子句,其中 、 均不含 。它們的歸結式是子句 。
歸結式由兩個父子句蘊含:滿足兩個父子句的賦值必滿足歸結式,因為若 和 都為假,兩個父子句就分別要求 為真和為假。
概念視角幾何
子句是被禁止的子立方體
把 個賦值看作 維立方體的頂點。一個含 個文字、且文字取自不同變量的子句,恰好禁止使其所有文字為假的賦值,這些賦值構成 維子立方體;CNF 恰由避開所有被禁止子立方體的頂點滿足。在這個圖像中, 與 的歸結式禁止 、 都為假的頂點,而每個這樣的頂點已落在第一個父子句( 為假時)或第二個父子句( 為真時)所禁止的區域內。歸結的可靠性就是說,新增的禁止區域已被兩個舊區域覆蓋。
定義 12.1.5
(消去一個變量)
給定 CNF,先刪去恆真子句和重複文字。消去 時,保留所有不含 的子句,並對每個 與每個 的配對加入歸結式。然後刪除所有含 或 的子句,並刪去恆真的歸結式。如果正、負兩族有一族為空,就沒有配對。空子句必須保留。
定理 12.1.6
(歸結給出存在量化投影)
對剩餘變量的每個賦值,消元後的 CNF 為真,當且僅當存在一個 的取值使原 CNF 為真。因此消元保留可滿足性;所有變量都消去後,原 CNF 不可滿足當且僅當剩下空子句。
證明
(為被消去的變量選值)
正方向通過構造 的值證明。固定一個滿足所有保留子句和歸結式的剩餘變量賦值。若某個正父子句的 為假,則每個負父子句的 都必須為真,否則它與該正父子句的歸結式為假。令 為真:正父子句全部滿足,負父子句則因各自的 滿足。若沒有任何正父子句的 為假,令 為假:正父子句靠其 滿足,負父子句靠 滿足。這也覆蓋正族或負族為空的情形。
反過來,若某個 的值滿足原 CNF,則所有保留子句和所有歸結式都為真,因為每個歸結式都由兩個父子句蘊含。這證明逐賦值的投影結論。依次消去全部變量就保留是否存在模型。最後沒有文字可用,剩餘結果只能是空合取(真),或含有空子句的合取(假)。每個生成的歸結式都是先前子句的邏輯後果;若生成空子句,其生成歷史就是有限反駁證書。
證明透視
歸結式是唯一的障礙
不顯眼的一步,是把歸結式讀成選擇 時唯一的障礙。令 為真可行,當且僅當每個負父子句的 都為真;令 為假可行,當且僅當每個正父子句的 都為真。兩種選擇都失敗,只在某個正父子句的 為假、且某個負父子句的 為假時發生,這時它們的歸結式 為假。、 不含 這個假設,保證它們的值不依賴 的選擇。被刪去的恆真歸結式本來就為真;任何一側的子句族為空時,相應的選擇自動可行,所以證明不需要另外處理邊界情形。
一對父子句也可能產生 這樣的恆真歸結式;刪除它不會增加約束。最壞情況下,兩兩配對可能產生很多子句,所以這個證明沒有給出一般 SAT 的多項式時間算法。變量消去次序會影響中間大小,但不會改變最終可滿足性。
反例模式
同時對兩個變量歸結是不可靠的
聲稱:由 與 可以同時消去兩對相反文字,推出空子句。賦值 使兩個子句皆真,而空子句在任何賦值下都為假,所以這個推導不可靠。歸結式的定義一次只對一個變量進行;這裏 與 含有第二個變量,對 的歸結式是恆真式 ,不帶任何資訊。
輔助變量保證的事情不同
設公式由一個有向無環表達式圖表示,共有 個 AND、OR 或 NOT 門。為每個門引入一個全新變量,用子句強制該變量等於其門的計算值。例如 等價於
OR 和 NOT 同理使用常數個子句,再以單文字子句要求輸出門為真。常量、文字作為輸出及空門圖可直接處理。在每門扇入為常數、只計門和使用到的輸入引用時,子句數及文字出現數為 。
定理 12.1.7
(門編碼在存在投影下是精確的)
設公式由有向無環的門圖給出, 是由每個門的定義子句再加上要求輸出門為真的單子句組成的 CNF。對原變量的每個賦值 ,恰有一個門變量賦值滿足所有門定義子句;並且 有滿足的擴張,當且僅當原公式在 下為真。
證明
(按拓撲順序計算各門)
對於原變量的每個賦值,按拓撲順序計算各門,為門變量給出恰好一個滿足全部門定義的賦值。此時輸出單子句為真,當且僅當原公式為真。反過來,任何滿足編碼子句的賦值都必須與這些門值一致。因此,原公式在某輸入賦值下為真,當且僅當存在其擴張使新 CNF 為真。
這比整體上僅有可滿足性等價更強,但並不表示對新增變量的任意賦值兩個公式都等價。
反例模式
全新變量不能當成無條件替換
公式 和 都可滿足,因而可滿足性等價。但它們在合併後的變量上並不等價:令 真、 假便能區分。存在合適擴張是帶量詞的結論,不能任意指定新變量還聲稱等價。
例題
例題 12.1.8
(按行構造異或)
對於變量 ,異或在 和 兩行取真。其規範 DNF 為 。假行是 與 ,得到規範 CNF 。
例題 12.1.9
(消去一個變量)
從 消去 ,得到單個子句 。若 和 均為假,原式要求 同時取兩個值;否則可選一個值使兩個子句都真。把 也計入賦值時,原式與結果並不等價:結果只記錄是否存在合適的 。
例題 12.1.10
(完整反駁)
子句 、 和 在 上分別歸結出 與 ,再在 上歸結出空子句。所以原來三個子句沒有滿足賦值;這些歸結步驟是可檢查的推導,不只是搜尋失敗記錄。
常見錯誤與範圍
常見錯誤
(消元不是等價變換)
從 消去 得 。當 、 為真而 為假時,它為真,原公式卻為假。消元保留的是存在合適 的值,而非 取每個固定值時原公式的值。
常見錯誤
(消元尚未完成就停下)
從 消去 ,保留 並加入歸結式 。結果不含空子句,原來的子句卻不可滿足:要消去 之後才出現空子句。歸結反駁能證明不可滿足,但中途沒有空子句並不能說明任何事情。
也不要因找到一個滿足行就斷言有效,更不要把 CNF 讀成單個析取:只要有一個子句為假,CNF 就為假。
這裏的構造針對有限命題公式與有限變量列表,不直接證明多項式 SAT 算法、一階完備性或最小等價 CNF 的大小界。輔助門編碼的輸出大小對表達式圖線性,但判定其可滿足性仍是另一問題。
小結
真值表的行構造出只用原變量的等價 DNF 和 CNF。歸結逐個消去變量,精確保留可擴張的賦值。全新門變量給出緊湊 CNF,其存在投影是原公式;若要斷言等價,不能忽略新增變量的取值。
練習
快速檢查
(寫出變量為 時 的規範 CNF,並指出其假行。)
解答 · 答案
蘊含只在 真、 假時為假。其規範 CNF 是單個子句 ,恰在該行取假。
快速檢查
(從 消去 。解釋為甚麼無需加入歸結式。)
解答 · 答案
沒有含 的負父子句,所以沒有配對,也沒有歸結式。刪去兩個正父子句並保留 。只要 為真,無論 如何取值都可令 真來滿足原子句; 為假時任何 都無用。
快速檢查
(空變量列表上的 的規範 DNF、CNF 是甚麼?從子句 和 消去 後剩下甚麼?)
解答 · 答案
空列表恰有一個賦值, 在該行取假。其規範 DNF 是空析取 ;規範 CNF 是一個空子句的合取,仍為 。單文字子句 與 歸結得到空子句,消元後保留它。
快速檢查
(在定義 的三個子句中, 為假時 唯一可取甚麼?為甚麼編碼作為 上的公式不等價於 ?)
解答 · 答案
若 為假, 強制 為假;此時另兩個子句無論 取甚麼值都成立。作為三個變量上的公式,門定義在 全假時為真,而 為假。要求輸出為真的單子句才選擇出門值為真的輸入。