為甚麼帶量詞的規格不只需要真值表
「每個頂點都有一個出鄰點」是一句話,但它的真假取決於所討論的圖:有向圈滿足它,刪去一條邊後卻可能不再滿足。命題邏輯可以用一個布爾(Boole)變量代表整句話,卻不能說明它為甚麼對某些頂點成立、對另一些頂點不成立。謂詞邏輯提供了這種內部結構:關係表示邊,變量表示頂點,量詞說明哪些選擇必須成功。
把規格變成證明或程式時,這些結構尤其重要。先看到頂點,再為它選擇鄰點,鄰點可以依賴於頂點;若要求同一個鄰點服務所有頂點,就必須在不知道具體頂點時把它選定。混淆這兩種要求,會把正確的逐輸入算法變成一個根本不可能兌現的固定輸出承諾。
本節討論初等的關係型一階邏輯。我們建立可靠的推理規則和精確的有限求值算法;並不聲稱給出了完整的一階證明演算。
結構、賦值與變量作用域
定義 12.2.1
(關係結構與項)
固定一個非空論域 。關係語言列出謂詞符號及其元數,例如一元符號 和二元符號 。一個結構把 解釋成 的子集,把 解釋成 的子集。等號表示論域元素真正相等。我們容許常量符號,每個常量命名一個指定的論域元素;本節不需要函數符號。一個項就是變量或常量。
定義 12.2.2
(賦值與量化公式的真假)
一個賦值 為每個變量指定論域中的值。原子式 在 下為真,當且僅當 屬於所解釋的關係。常量使用結構中固定的解釋。聯結詞像命題邏輯那樣組合真假值。對於量詞,用 表示只把 改為 的賦值:
定義 12.2.3
(約束變量、自由變量與句子)
變量的一次出現,若處在量化該變量的量詞作用域內,就是約束出現;否則是自由出現。若有多個這樣的量詞,以最內層的量詞為準。因此,在 中,第一個 自由,第二個 受約束,而 自由。沒有自由變量的公式稱為句子。句子的真假取決於結構,卻不取決於賦值:對公式作結構歸納可知,只有自由變量的值才可能影響真假。
常見錯誤
(用嵌套量詞遮蔽變量)
不同的角色最好使用不同的變量名。句子 在語法上沒有問題,但內層量詞遮蔽了外層變量。由於 非空,它只表示某個元素有自環,並不表示每個頂點都有自環。只把內層約束變量改名,就得到 ,原先失去的依賴關係便清楚了。
定義 12.2.4
(在結構中為真、有效與蘊含)
討論一個公式在某結構中為真時,論域與關係已經固定。若一個句子在其語言的每個結構中都為真,就稱它有效;這裏始終採用非空論域約定。若每個使前提集合 全部為真的結構與賦值也使結論 為真,就說 蘊含 。檢驗一幅圖,只能確定該圖中的真假,不能證明關於所有圖的有效性。
代入必須保留變量原來的意義
定義 12.2.5
(避免捕獲的代入)
用 表示把 的自由出現替換成項 ; 的約束出現不動。代入前,若某個約束變量會捕獲 中的變量,就先給它換一個新名字。改名必須在其作用域內一致進行,並採用未使用的名字,所以不改變意義。有限公式只用有限多個變量名,總能找到新名字。
例題 12.2.6
(一次意外改變問題的代入)
設 ,要用變量 替換自由的 。直接按文字替換得到 ,它問的是有沒有自環。應先把約束變量改為 ,得到 ,再代入為 ;正確結果問的是目前自由變量 所指的頂點有沒有出鄰點。取只有一條邊 的雙頂點圖,並令 ,則正確結果為真,被捕獲的版本卻為假。
定理 12.2.7
(避免捕獲的代入究竟表示甚麼)
設 為變量或常量,並按上述方法避免變量捕獲。公式 在賦值 下為真,當且僅當 在 下為真;其中 是項 在原賦值下的值。
證明
(對公式結構歸納)
對原子式,替換只改變原先由自由 佔據的參數位置,兩邊因而檢驗同一個元組。聯結詞情形由歸納假設組合而得。遇到約束 的量詞時,代入停止,而且這個量化公式的真假與進入時 的值無關。遇到約束另一個變量 的量詞時,必要時先改名,使 不出現在 中。這樣,改變 不會改變 的值;對不同變量 的賦值更新也可以交換次序。對每個 使用歸納假設,再使用相同的全稱或存在條件,就完成了公式結構歸納。
這個引理解釋了代入規則為甚麼需要附帶條件:語法上的替換必須對應某個精確的賦值變化。變量捕獲破壞了這種對應,屬於數學錯誤,而不是書寫風格上的偏好。
四條量詞規則及其條件
全稱消去:從 推出 ,其中代入必須避免捕獲。全稱命題在項 所指的值上成立,而代入引理說明所得公式正是這個實例。
存在引入:從 推出 。項 的值就是所需見證。以上兩條規則都要求 確實指向論域中的元素;沒有定義的表達式不是合法實例。
全稱引入:引入一個新參數 ,不依賴任何專門限制 的額外假設,證明 ,然後推出 。準確地說, 不能出現在尚未解除的前提或原公式中。參數是一個新常量,其解釋可以任意選擇。
存在消去:假設前提蘊含 。用新參數 暫時假設 ,並推出結論 。若 沒有出現在 、其他尚未解除的前提或原公式 中,就可以解除這個臨時假設,推出 。
命題 12.2.8
(四條量詞規則的可靠性)
四條規則在所述附帶條件下都是可靠的:凡滿足前提的結構與賦值,也滿足結論。
證明
(為甚麼新參數條件給出可靠性)
全稱消去:全稱命題在項 所指的值上成立,而代入引理說明所得公式正是這個實例。存在引入:項 的值提供所需見證。
全稱引入:固定滿足前提的結構及任意 ,把 解釋成 。前提沒有提到 ,所以仍然成立, 的證明因而說明 在 上成立。 是任意的,所以 在每個元素上成立。
存在消去:固定滿足原前提的結構。前提蘊含 ,選一個見證並把 解釋成它,於是 成立。臨時推導證明 ;而 不提到 ,所以這仍是關於原結構的結論。
證明透視
任意元素與未知見證各有不同的任務
全稱引入要求證明對新名字的每一種解釋都成立。存在消去只需使用一種滿足見證性質的解釋,但最終結論不能依賴這個名字。新參數的限制使這兩個語義論證成立。如果已有假設限制了 ,補寫一句「令 任意」並不能取消那個限制。
例題 12.2.9
(把存在命題通過一個全稱蘊含傳遞)
假設 和 ,要證 。暫時命名一個見證 ,使 成立。全稱消去給出 ,於是得到 。存在引入給出 。這個結論不含 ,所以存在消去容許解除臨時的見證假設。我們沒有找出某個預先命名的元素滿足 ,而是證明了某個元素滿足它。
反例模式
見證不會自動變成某個指定常量
令 , 只在 上成立,而已有常量 表示 。此時 為真, 卻為假。從存在命題跳到某個事先指定元素的命題,是無效推理。同樣,若臨時假設 尚未解除,就不能從它全稱引入 :所謂任意參數實際上已經受到限制。
否定、受限論域與見證依賴
命題 12.2.10
(量詞否定)
對任何公式 ,
證明
(借語義條款否定量詞)
第一個等價式不要求每個值都失敗:只要一個值使公式體為假,全稱命題就失敗。第二個等價式說明,沒有見證正是每個值都失敗。
每次處理一個量詞,可得
常見錯誤
(否定全稱—存在句子需要頂點,而不是一條邊)
右側要求找到一個沒有任何出邊的頂點,而不只是找到一條缺失的邊。一個缺失的有向點對只能反駁更強的命題 。
定義 12.2.11
(受限量詞)
對於子集 ,受限量詞是下面的縮寫:
其中 表示屬於 。
常見錯誤
(用合取限制全稱量詞)
若 為空,受限全稱式為真,受限存在式為假,即使背景論域 非空也是如此。若改用合取來寫全稱式,就是錯誤: 要求每個論域元素既屬於 又滿足 ,所以只要 為空它就為假。全稱限制中必須使用蘊含。
命題 12.2.12
(交換全稱量詞與存在量詞)
對任何公式 ,句子 蘊含 。反方向的蘊含一般不成立。
證明
(同一個見證適用於每個 x)
在 中, 的見證可以依賴 ;在 中,同一個見證必須適用於每個 。若第二句以 為見證成立,則無論選了哪個 ,同一個 都是第一句的見證。
反例模式
在 x 之後選取的見證未必適用於每個 x
取論域 ,令 表示 。則 為真:取 。但 為假: 在 處失敗, 在 處失敗。沒有一個值能同時等於兩個元素,所以反方向的蘊含不成立。
若句子由一串量詞和一個不含量詞的公式體構成,每次存在選擇可以依賴此前的選擇,卻不能依賴稍後的全稱選擇。這是嵌套語義條件的直接含義,不是容許提前猜中未來的資訊。
概念視角結構
把見證看作此前選擇的函數
在有限論域上, 恰好表示存在函數 ,使對每個 都有 ;而 表示這個函數可以取為常數函數。一般而言,每個存在變量的見證是排在它之前的全稱變量的函數,而不依賴排在它之後的任何變量。這個讀法解釋了為甚麼常數函數給出上面的蘊含,也解釋了為甚麼按此前選擇索引的見證表可能比公式本身大得多。
給定有限結構上的精確算法
假設可以明確枚舉 的全部 個元素。給定公式及其自由變量的值,在輸入關係中求原子式的真假,遞歸計算聯結詞,並用有限迴圈實作量詞。對於全稱量詞,依次把 賦成每個論域值並計算公式體;遇到假就立即返回假,迴圈全部完成才返回真。對於存在量詞,遇到真就返回真,全部失敗才返回假。進入作用域時保存 的舊賦值,離開時恢復;當同一個變量名還有外層意義時,這一步不可省略。
定理 12.2.13
(有限求值的正確性與終止性)
上述遞歸求值器對每個公式、每個這樣的有限結構以及每個自由變量賦值,都返回語義規定的真假值。設公式語法樹大小為 ,最大嵌套量詞深度為 ,項求值和關係成員查詢都為單位成本,則最壞時間為 。若一個論域索引可放入一個機器字,則除已儲存的模型和唯讀公式外,深度優先實作只需 個工作機器字。
證明
(歸納證明正確性與成本計數)
按公式結構歸納證明正確性。原子式直接使用結構中的解釋。每個聯結詞對遞歸得到的正確結果應用相應真值函數。對於全稱量詞,迴圈恰好在語義規定的賦值下訪問每個 ;一次失敗就反駁全稱命題,全部完成則證明每種情形。存在量詞同理,或者提前找到見證,或者所有選擇都失敗。恢復賦值保證一個遞歸調用不會改變兄弟分支的意義。遞歸只進入嚴格較小的公式節點,每個迴圈又都是有限的,因此必然終止。
對於時間界,一條路徑上的每個量詞至多帶來 倍的重複。所以一個特定語法樹節點至多被求值 次,而節點總數為 。局部布爾運算與迴圈管理的總工作量也滿足同一界。深度優先遍歷最多保存 層調用、變量值和迴圈位置,不必把整棵選擇樹留在記憶體中。關係表、輸入編碼以及查詢元組的實際成本,需要與這裏的單位成本模型分開計算。
若公式固定, 就固定,因此在所述模型下,這是關於論域大小的多項式界。若公式也作為可變輸入, 可以隨輸入增長,所示界並不是統一的多項式時間保證。正確的有限求值器也不因此能判定所有有限及無限結構上的有效性;它回答的是一個給定公式在一個給定結構和賦值中的真假。
例題 12.2.14
(有向圈、見證表與失敗證據)
設 ,邊恰為 、、。檢驗 時,可以為 分別記錄見證 ,所以句子為真。但 為假:候選 可用 反駁, 可用 反駁, 可用 反駁,因為這些對角邊都不存在。再刪去 ,第一句也變為假;反例是 ,並附上所有 都失敗的事實。
真的全稱命題通常沒有一個像存在命題那樣的單獨見證。在這裏,全稱—存在句子需要給每個頂點提供一個見證。反過來,反駁存在—全稱句子,可能需要為每個存在候選分別給出一個失敗的全稱實例。即使程式只返回布爾值,明確這種依賴仍有助於理解它證明了甚麼。
練習
快速檢查
(找出 的自由變量。給約束變量改名,使自由角色與約束角色不再混淆。)
解答 · 答案
自由變量是 :自由 出現在左邊的析取支,自由 出現在右邊。清楚的改名結果是 。右邊量詞只約束自己作用域中的 ,不會越過析取符去約束左邊的 。
快速檢查
(設 、,且 只在 上成立。比較 與 。如果 為空,又會怎樣?)
解答 · 答案
使用蘊含的句子為真:在 處後件為真,在 處前件為假。使用合取的句子為假,因為公式體在 處已經失敗。若 為空,每個蘊含都為真,每個合取都為假。因此受限全稱式為真,但使用合取的句子在這個非空論域中仍為假。
快速檢查
(證明 。若把兩邊的合取都換成析取,是否仍然等價?)
解答 · 答案
若每個元素同時滿足兩個謂詞,那麼每個謂詞都在全部元素上成立。反之,若兩個獨立的全稱命題成立,任取一個元素,它就同時滿足二者,從而得到合取的全稱命題。對析取,從 到 的方向成立,反方向卻失敗。取 ,讓 只在 為真, 只在 為真;每個元素都滿足其中一個謂詞,但兩個謂詞都不普遍成立。
快速檢查
(某證明寫道:「假設 ,把一個見證叫作 ,所以 ,所以 。」指出無效的一步,給出雙元素反模型。如果另有前提 ,可以有效地推出甚麼含 的結論?)
解答 · 答案
無效的是全稱引入: 是關於存在見證的臨時假設, 並非不受限制。取 、,則存在為真而全稱為假。若另有全稱蘊含,可用臨時見證推出 ,再引入 ,最後解除見證假設。所得結論不含 ,滿足存在消去的要求。
快速檢查
(在 上令 表示 。判斷 和 ,分別給出見證或反駁數據,並給出簡單嵌套迴圈求值器檢驗任一句子時所需原子成員查詢次數的上界。)
解答 · 答案
第一句為真: 時選 , 時選 。第二句為假:無論預先選哪個 ,全稱選擇都可取 ,使原子式為假。兩句都有至多兩種外層選擇、每種至多兩種內層選擇,所以任一句都至多需要四次成員查詢;提前停止可能減少次數。第二句不容許先看到 再選 ,因為存在選擇在全稱選擇的外層。