Loading AI tools
使用於數學、哲學、語言學及電腦科學中的一種形式系統 来自维基百科,自由的百科全书
一阶逻辑是使用於数学、哲学、语言学及電腦科學中的一种形式系统,也可以稱為:一阶斷言演算、低階斷言演算、量化理論或谓词逻辑。一階邏輯和命題邏輯的不同之處在於,一階邏輯包含量詞。
![]() |
![]() | 此條目的语调或风格或許不合百科全書。 (2022年6月15日) |
高階邏輯和一階邏輯不同之處在於,高階邏輯的斷言符號可以有斷言符號或函數符號當做引數,且容許斷言量詞或函數量詞[1]。在一階邏輯的語義中,斷言被解釋為關係。而高階邏輯的語義裡,斷言則會被解釋為集合的集合。
在通常的語義下,一階邏輯是可靠(所有可證的敘述皆為真)且完備(所有為真的敘述皆可證)的。雖然一階邏輯的邏輯歸結只是半可判定性的,但還是有許多用於一階邏輯上的自動定理證明。一階邏輯也符合一些使其能通過證明論分析的元邏輯定理,如勒文海姆–斯科倫定理及緊緻性定理。
一階邏輯是數學基礎中很重要的一部份。許多常見的公理系統,如一階皮亞諾公理、冯诺伊曼-博内斯-哥德尔集合论和策梅洛-弗蘭克爾集合論都是一階理論。然而一階邏輯不能控制其無窮模型的基數大小,因根據勒文海姆–斯科倫定理和康托爾定理,可以構造出一種“病態”集合論模型,使整個模型可數,但模型內卻會覺得自己有「不可數集」。類似地,可以證明實數系的普通一階理論既有可數模型又有不可數模型。這類的悖論被稱為斯科倫悖論。但一階的直覺主義邏輯裡,勒文海姆–斯科倫定理不可證明[2],故不會有以上之現象。
命題邏輯顧名思義,會將「蘇格拉底是哲學家」、「柏拉圖是哲學家」之類直觀上有真有假的敘述簡記為 及 (也就是有真有假的命題),然後討論 (非p)、(若p則q)、(p且q)與(p或q)之間的推理關係。
但一階邏輯嘗試從一些比較基礎的詞彙去建構「句子」,比如說,可用符號 代表 「 x 是哲學家」,也就是賦予斷言符號「 」語意的解釋。這個解釋預設一個「所有人類的群體」(也就是下面標準語義一節會說到的论域),并將變數 對應為自群體中取出來的某人。
以此類推,斷言符號可以包含一個以上的變數。例如:可以將 解釋為「 x 與 y 是夫妻」。
一階邏輯類似於命題邏輯,可以將斷言符號與 (非)、(則)、(且)和 (或)組成更複雜的敘述,例如:把斷言符號 解釋成「 是學者」,那「若 x 為哲學家,則 x 為學者」可表示為:
但相較之下,一階邏輯又加入了描述「所有」與「存在」的量詞,比如說「對所有 x ,若 x 為哲學家,則 x 為學者」可記為:
也就是自左方開始閱讀,將 解釋成「对所有 x 有…」。 這個符號被称为全稱量詞。
而對於「有 x 是哲學家」这一叙述,一階邏輯則引入另一種量詞:
也就是自左方開始閱讀,將 解釋成「存在 使…」。 這個符號被称为存在量詞。
順帶一提「並非所有 x 不是哲學家」等價於「有 x 是哲學家」;且「不存在 x 不是學者」也等價於「所有的 x 是學者」。所以可以用「否定」和「全稱量詞」來組合出「存在量詞」。換句話說,可作以下的符號定義( 代表一段「敘述」):
一階邏輯也考慮到「相等」這個概念在敘述中的重要性,例如想表達「若所有是哲學家,那的長子也會是哲學家」,可先把 解釋為 「 x 的長子」,那么這段敘述可記為:
換句話說, 被解釋成「與 有特定且唯一對應關係」的某對象(被稱為函數符號)。換句話話說,只要「就是」,那「的長子也會是的長子」。換句話說:
這些性質被一階邏輯視為「理所當然」。
類似地,敘述中也有一些「不變的實體」,如苏格拉底,表示這些「實體」的符號被稱為常數符號。例如將 解釋為苏格拉底,那「苏格拉底為哲學家」就可以寫成:
所謂的「不變」隱含的代表:
換句話說
這兩個性質也被一階邏輯視為「理所當然」。
一階邏輯的形式理論可分成幾個部份:
一套理論能容許多少符號,取決於人類能運用物理定律來塑造多少符號,但目前無法確知宇宙是不是有限,或是以可無限制地分割。雖然所有的公理化集合論都以量詞的形式隱晦的承認跟自然數一樣多的無窮(如ZF集合論的無窮公理),甚至以這樣的可數無窮為基礎,去建構出不可數的實數,但將抽象的理論對應到現實時,還是需要回答物理上有沒有可數或不可數的無窮。所以謹慎起見,如果沒有特別申明的話,以下各種類符號的數目上限都是有限的。
一階邏輯通常擁有以下的符號:
並非所有的符號都不可或缺的,像謝費爾豎線「」(或異或)可以用來定義量詞以外的所有邏輯符號,換句話說:
符號定義 —
另外,一些作者不區分語義解釋和形式理論,所以會將表示真值的符號納入形式理論裡,也就是說,用 T 、Vpq 或 來表示「真」,並用 F 、 Opq 或 來表示「假」。
「他們兩人是夫妻」,是一個關於兩個“對象”的斷言,而「他是人」、「三點共線」则表明斷言容許一個或者多個對象。所以對於自然數 、 約定:
為一階邏輯的合法詞彙。它在直觀上表示一個有 個“對象”的斷言,稱為 元斷言符號。下標的自然數 只是拿來和其他同為 元的斷言符號作區別。
實用上只要有申明,不至於和其他詞彙引起混淆的話,可以用任意的形式簡寫一個斷言符號。如:公理化集合論裡的雙元斷言符號 也可以表示为 。
「物體的顏色」、「夫妻的長子」这种断言說明了一组對象所唯一對應的對象。但不同的夫妻有不同的長子;不同的物體有不同的顏色。據此,形式上對於自然數 、 約定:
為一階邏輯的合法詞彙,直觀上表示 個“對象”所對應到的東西,稱它為 元函數符號。需要特別注意,這種“唯一對應”的直觀想法,必須配上關於“等式”的性質(詳見下面的等式定理章节),才能在形式理論中被實現。
与斷言符號一样,只要不引起混淆,就可以用任何的形式簡寫函數符號。如:公理化集合論裡的 是依據聯集公理而定義的新函數符號(請參見下面函數符號與唯一性章節),也可以冗長的表記為 。
「刻度0」、「原點」、「蘇格拉底」是直觀上"唯一不變"的對象。據此,對自然數 約定
為一階邏輯的合法詞彙,直觀上表示一個“唯一不變”的對象,稱為常數符號。同樣的。“常數的不變性”需配上等式的性質(詳見下面等式定理)才能被實現。
為了不和變數的表記混淆,常數符號一樣可以用任何的形式簡寫,如公理化集合論裡的 是根據空集公理和函數符號與唯一性,而定義的新常數符號。亦可冗長的表示為 。
和自然語言(如英語)不同,一階邏輯的語言以明確的遞迴定義判斷一個給定的詞彙是否合法。大致上來說,一階邏輯以「項」代表討論的對象,而對「項」的斷言組成了最基本的原子(合式)公式;而原子公式和邏輯符號組成了更複雜的合式公式(也就是“敘述”)。
「那對夫妻的長子的職業」、「」、「」代表變數可以與函數符號組成更一般的物件。據此形式,遞迴地規定一類合法詞彙——項為:
遞迴定義 —
習慣上以大寫的西方字母(如英文字母、希伯來字母、希臘字母)代表項,如果變數不得不採用大寫字母,而可能跟項引起混淆的話,需額外規定分辨的辦法。
為了比較簡潔地規定甚麼是合式公式,先規定原子公式為:(若 是項)
這樣的形式。
一階邏輯的合式公式(簡稱公式或 )以下面的規則遞迴地定義:
遞迴定義 —
另外成對的中括弧跟大括弧,符號辨識上視為成對的小括弧,而草書的大寫西方字母為公式的代號。
舉例來說,
是公式而
則不是公式。
而接下來只要對任意公式 、 與變數 ,做以下符號定義
符號定義 —
(同樣美觀起見 )
這樣所有的邏輯連接詞與量詞就納入了合式公式的規範。
所謂的施用/作用,是以下公式形式的口語說法:(其中 與 都是公式)
就类似于運算子作用在它們身上。
量詞所施用的公式被稱為量詞的範圍(scope)。同一個變數在公式一般來說不只出現一次,若變數 出現在 的範圍內,稱這樣出現的 為不自由/被約束的 (not free/bounded);反過來說,不出現在 的範圍內的某個 被稱為自由的 。
例如,對於公式:
就是量詞 的範圍;而 裡的 就是不自由的;反之 裡的 就是自由的。
說 於公式 完全自由,意為於 出現的 都是自由的;反之,說 於公式 完全不自由/完全被約束,意為 內根本沒有 ,或是 內沒有自由的 。若 內所有的變數都完全不自由, 特稱為封閉公式/句子(closed formula/sentence)。
括弧是為了保證語意解釋符合預期,但太多的括弧書寫不易,為此規定以下的“重構法”(反過來就是“簡寫法”),從表面上不合法的一串符號找出作者原來想表達的公式:
舉例來說
的重構過程如下
可以被重構為公式的一串符號則寬鬆的認定為“合式公式”。(最明顯的例子就是合式公式最外層的括弧可以省略)
波蘭表示法將邏輯連接詞前置於被施用的公式而非傳統的中間。如果沿用以上的"施用順序",這個表示法允許捨棄所有括弧。如公式
轉成波蘭表示法的過程如下
一階邏輯通常只有以下的推理規則(因為將普遍化視為推理規則會有不直觀的限制)
MP律 — 對於公式 和 有
直觀意義非常明顯,就是p=>q且p可以推出q。
在只以謝費爾豎線「」為基礎邏輯連接詞的公理系统裡,MP律會被改寫成
修改的MP律 — 對於公式 、 和 有 和 組合出 。
公理 — 如果、、都是公式,則:
都是公理。
它们实际上是公理模式,代表著“跟自然數一樣多”條的公理。
在有(A1)與(A2)的前提下,(A3)等價於以下的公理模式:(證明請參見下面否定一節。)
(T1) —
另外,在只以謝費爾豎線「」為基礎邏輯連接詞的公理系统裡,上面三條公理模式等價於下面這條公理模式[3]:
公理 — 如果 、、 、 和 都是公式,則:
都是公理。
公理 — 為任意變數, 、 為任意公式,則
它们实际上也是公理模式。
根據不同作者的看法,甚至是理論本身的需求,「等式」在形式理論裡可能是斷言符號或是一段公式(如 a 等於 b 可定義為對所有的 x , x 屬於 a 等價於 x 屬於 b )。而如何刻劃直觀上「等式的性質」,有一開始就將「等式的性質」視為公理(模式),但也有視為元定理的另一套處理方法,以下暫且以公理模式的方式處理。以元定理處理的方法會在等式定理詳述。
公理 — 是一段變數 、 完全自由,且型式完全被確定的公式 的簡寫。要求:
事實上這兩個公理模式也確保了函數符號“唯一對應”和常數符號的“唯一性”,但證明這些性質需要一些元定理,簡便起見合併於下面的等式定理一節講述。
一階邏輯的標準語義源於波蘭邏輯學家阿尔弗雷德·塔斯基所著《On the Concept of Truth in Formal Languages》。根據上面語法一節,公式是由原子公式遞迴地添加邏輯連結詞而來的,而原子公式是由斷言符號與項所構成的。所以要檢驗一條公式在特定的論域下正不正確,就要規定項的取值,然後檢驗這樣的取值會不會落在斷言符號所對應的關係裡。由此延伸出所有公式的“真假值“。
也就是一套一階邏輯的語義解釋,要包含
通常一套解釋方法(簡稱為解釋)會以代號 表示。
量詞的解釋需要指明變數取值範圍的論域——也就是一個集合 。而變數可能跟自然數一樣多,換句話說,所有變數在論域 取的值可以依序以自然數標下標——也就是一個在 取值的數列。如果以 的代號(不一定是變數本身的表示符號)來列舉變數,那麼從 的某套變數取值就以
或較直觀的符號
來表示。
一套解釋 會將 元函數符號 解釋成某個 的 元函數;而常數符號 解釋成特定的 (亦稱為 的取值為 ),這樣就可以用上面語法一節定義項的方式,遞迴地規定項的取值:
元定義 — 在解釋 下的某套變數取值下,一列項 的取值分別為 ,則這套變數取值下,項 的取值規定為
直觀上要解釋關係最直接的方法,就是列舉所有符合關係的對象;例如如果想說明夫妻關係,可以列舉所有(老公, 老婆)的雙元有序對,但並非所有的人類有序對都會在這個關係中。
以此為基礎,若以 代表所有以 個 中的元素構成的 元有序對的集合(也就是 元笛卡兒積) ,那一套解釋 會將 元斷言符號 解釋為一個
的 元有序對子集合。
這樣就可以依據語法的遞迴定義,以下面的規則對每條公式賦予真值。(這種賦值方式稱為T-模式,取名於邏輯學家阿尔弗雷德·塔斯基)
元定義 — 在一套解釋 下:
更進一步的來說
另一種一階邏輯語義的方法可經由命題邏輯的林登鮑姆-塔斯基代數擴展而成。有如下幾種類型:
塔斯基和葛范德於1987年證明,沒有超過包在三個以上的量化內的原子句子的部份一階邏輯,其表示力和關係代數相同。上述部份一階邏輯令人十分地感到有興趣,因為它已足夠表示皮亞諾算術和公理化集合論,包括典型的ZFC。他們亦證明了,具有簡單有序對的一階邏輯和具有兩個有序的投影函數的關係代數等價。
上述的語義解釋都要求論域為非空集合。但在如自由邏輯之中,設定空論域是被允許的。甚至代數結構的類包含一個空結構(如空偏序集),當允許空論域時,這個類只能是一階邏輯中的一個基本類,不然就要將空結構由類中移除。
不過,空論域存在著一些難點:
因此,若空論域是被允許的,通常也必須被視成特例。不過,大多數的作家會簡單地將空論域由定義中排除。
以下介紹一些基本用語和符號
元定義 — 在一階邏輯理論 下, 代表有一列公式 滿足:
口語上會稱公式 (或 ) 為 下的定理(theorem)。而這列 會稱為 的證明。
例如定理 的證明:
證明 —
以上其實是蘊含了無限多定理的元定理的證明(因為沒有給出合式公式的明確形式)。方便起見,這種元定理還是會稱為定理並以同樣的形式來表達。
直觀上的證明,總是會有一些“前提假設”,對此,若以 代表一列有限數目的公式,那
元定義 — 代表有一列公式 滿足:
這樣稱 為在前提 下, 的證明;或是說 是 的推論結果。
若要特別凸顯 裡的一條"前提條件" 對"證明過程"的重要性,可以用 的符號去特別凸顯。若 裡的公式列舉出來有 ,那亦可表示為
證明過程沒有被引用的公式盡可能不寫出來。另一方面從以上對於證明定義可以發現,依怎樣的順序列舉前提條件,對於證明本身是不會有任何影響的。
本節所介紹的符號,在引用哪個理論很顯然的情況下, 的下標 可以省略。
實際的證明常常會"引用"別的(元)定理,嚴格來說,就是照抄(元)定理的證明過程,然後作一些修改使符號一致。為了節省證明的篇幅,引用時只會單單列出配合引用(元)定理所得出的公式(形式),並在後面註明引用的(元)定理代號。
從公理(A1)和(A2)會得出不但直觀且實用的演繹元定理:
元定理 —
一階邏輯理論 下,若有 ,則有
證明 |
---|
(注意這是元邏輯下的證明): 假設 為條件所說 的證明,如果 是 裡的公式或 的公理,那根據(A1) 所以由MP律有 若 是 ,那因為 所以有 至此的部分證明完畢。 接下來要用歸納法;假設對 都有 。 若 是公理、或從 來的、或是根本就是 ,仿造上面 的部分就有 剩下沒考慮的狀況是由MP律組合出 的狀況,也就是有 使 是 。 由公理A2有 套用歸納法的假設,加上MP律,就會發現 如此可以一路歸納到 也就是 的情況,故元定理得證。 |
因為 代表的是有限條公式,所以透過演繹元定理可以將證明過程必要的前提條件遞迴地移到 後,直到不需要任何前提為止;然後由MP律可以知道,若有 ,則有 ,如此一來透過演繹元定理搬到推論結果的合式公式,也可以任意的搬回來。所以 等價於某定理 。因此也會將 稱為一個定理。
而從演繹元定理和MP律,會有以下直觀且實用的元定理
元定理 —
(D1)
(D2)
以下如果需要將引用的定理以演繹元定理進行"搬移",會省略掉搬移的過程並在搬移後得到的結果後標註(D)。如果引用以上的(D1)和(D2)也會省略過程,單有結果和代號標註。
以下的證明會分成使用(A3)的部分跟將公理(A3)取代為(T1)的部分,用以證明兩者的等價性。
(DNe) Double negation, elimination —
證明(使用A3) |
---|
(1) (A3) (2) (I) (3) (D2 with 1, 2) (4) (A1) (5) (D1 with 3, 4) |
證明(使用T1) |
---|
(1) (A1) (2) (Hyp) (3) (MP with 2, 1) (4) (MP with 3, T1) (5) (MP with 4, T1) (6) (MP with 2, 5) |
(DNi) Double negation, introduction —
證明(使用A3) |
---|
(1) (A3) (2) (MP with DNe, 1) (3) (A1) (4) (D1 with 2,3) |
證明(使用T1) |
---|
(1) (DNe) (2) (MP with 1, T1) |
上面兩定理表達了雙否定推理上等價於於原公式,引用兩者任一會都以(DN)簡寫。
(T1) Transposition-1 —
證明(使用A3) |
---|
(1) (A3) (2) (Hyp) (3) (MP with 1, 2) (4) (A1) (5) (D1 with 3, 4) |
(T2) Transposition-2 —
證明(使用T1) |
---|
(1) (DN) (2) (Hyp) (3) (D with 1, 2) (4) (DN) (5) (D1 with 3,4) (6) (T1, D) (7) (MP with 5, 6) |
注意到(T2)的證明引用了(T1)+(DN),但之前已經證明了(A1)+(A2)+(A3)可以推出(T1);還有(A1)+(A2)+(T1)也可以推出(DN),所以註明使用(T1)即可。
以上二定理說明 推理上等價於 ,引用這兩個定理中任一都以(T)表示。
至此,已經可以證明(A1)+(A2)+(T1)可以推出(A3):
(T1)可推出(A3)的證明 |
---|
由MP律顯然有
(1) (對上面的定理使用兩次演繹元定理) (2)(D1 with 1, T2) (3)(MP with A2, 2) (4)(MP with I, 3) (5)(MP with T1, 4) (6)(Hyp) (7)(Hyp) (8)(MP with T2, 7) (9)(D1 with 6, 8) (10)(D1 with DN, 9) (11)(MP with 5, 10) |
所以綜合以上所述,在有(A1)+(A2)的前提下,公理(T1)等價於公理(A3)。
由(T)可以得到類似於公理(A3)的定理
(A3') —
證明 |
---|
(1) (A3) (2) (T, D) (3) (Hyp) (4) (MP with 2, 3) (5) (MP with 1, 4) (6) (T, D) (7) (Hyp) (8) (MP with 6, 7) (9) (MP with 5, 8) |
以下的定理重現了實質條件的直觀理解。
(M0)material condition —
(也就是)
證明 |
---|
(1) (Hyp) (2) (Hyp) (3) (A3) (4) (A1) (5) (MP with 4, 1) (6) (A1) (7) (MP with 6, 2) (8) (MP with 3,5) (9) (MP with 8,7) |
(M1)material condition —
證明 |
---|
首先注意到 (MP) (1) (0, D) (2) (T) (3) (Hyp) (4) (MP with 1, 3) (5) (MP with 2, 4) (6) (Hyp) (7) (MP 5, 6) |
(M2)material condition —
證明 |
---|
(1) (A1) (2) (T) (3) (MP with 1, 2) (4) (Hyp) (5) (MP with 3, 4) |
(M3)material condition —
證明 |
---|
(1) (M0, D) (2) (T) (3) (MP with 1, 2) (4) (Hyp) (5) (MP with 3,4) (6) (MP with 5, DN) |
(C1)Proof by Contradiction —
證明 |
---|
(1) (T, D) (2) (Hyp) (3) (MP with 1, 2) (4) (Hyp) (5) (MP with DN, 4) (6) (MP with 3, 5) |
(C2)Proof by Contradiction —
以下為邏輯與的交換性
元定理 —
證明 |
---|
(1) (C1, D) (2) (T, D) (3) (MP with 1,2) |
類似的,(C2)正是邏輯或的交換性:
元定理 —
(C2, D)
"且"的直觀意義是實質條件元定理的直接結果
(AND)Intuitive meaning of And —
(M1)
(M3)
(M2)
從(AND)和 的符號定義可知, 的證明可以拆成兩部分;習慣上會以「( ) 」標示 部分的證明,而「( ) 」標示 部分的證明。
類似的,"或"的直觀意義是(M0)跟(D)的直截結果
(OR)Intuitive meaning of OR —
(M0, DN)
(A1, D)
(D)
(交換性, D)
以下的定理則是(A3')的直截結果
(DisJ)Disjunction —
證明 |
---|
(1) (Hyp) (2) (Hyp) (3) (D1 with 1, 2) (4) (Hyp) (5) (A3' with 3, 4) |
對於"且",展開符號定義後,可以從直觀意義輕鬆地得到
(ASO-AND)Associativity of AND —
"或"也有類似的性質
(ASO-OR)Associativity of OR —
"且"和"或"之間還有分配律
(DIS-1)Distribution —
證明 |
---|
() (1) (Hyp) (2) (MP with 1, AND) (3) (MP with 1, AND) (4) (Hyp) (5) (MP with 4, DN) (6) (D1 with 3, 5) (7) (MP with 2, 5) (8) (MP twice with 2, 7, AND) 也就是
再套用(D)就會得到
() (1) (Hyp) (2) (D1 with 1, AND) (3) (D1 with 1, AND) (4) (MP with 2, C2) (5) (MP with 3, C2) (6) (D1 with 4, AND) (7) (D1 with 4, AND) (8) (A3' with 6, I) (9) (MP twice with 7, 8, AND) 也就是
|
(DIS-2)Distribution —
證明 |
---|
() (1)(Hyp) (2) (D1 with 1, AND) (3) (D1 with 1, AND) (4)(MP twice with 2, 3,AND) 也就是
() (1) (Hyp) (2) (MP with 1, AND) (3) (MP with 1, AND) (4) (Hyp) (5) (MP with 2,4) (6) (MP with 3,4) (7) (MP twice with 5, 6, AND) 也就是
再使用一次推論元定理會得到
|
以下的元定理的名字來自於英國邏輯學家奧古斯塔斯·德摩根。
De Morgan I —
證明 |
---|
()
()
|
De Morgan II —
證明 |
---|
()
()
|
公理模式(A7)可以稍加延伸成以下的元定理
定理的普遍化 —
對任意變數 ,若 則有 。
證明 |
---|
假設 就是 的證明,那 一定是公理,根據(A7)可以得到
若對 都有 ,如果 是公理的話顯然 。 若有 使得 那根據歸納法的假設跟(A6)有 上式配上 就可以得到 以此歸納到 也就是 ,故本元定理得證。 |
更進一步,有以下元定裡
(GEN) —
在 裡變數 都完全被約束,若
則有
證明 |
---|
以下對前提條件的數量 做歸納。 若 ,根據前提有 以(D)將 往前搬,再套用定理的普遍化,會得到 再根據(A5)和MP律,就可以得到 也就是本元定理要求的結果。 現在假設 的情況下元定理會成立。元定理的前提條件根據(D)可以寫為 則根據歸納法的假設 上式配上(A5),本元定理在 的情況就可以得到證明,故本元定理得證。 |
(GEN)可以稍加修飾,以套用在含有存在量詞的公式上
(GENe) —
若變數 在 的公式和 裡都完全被約束則
(1) 若 則
(2) 若 則
以下的定理,說明兩條「等價」的公式可以互相代換
證明 |
---|
以下的證明都會用到這三條公式:
(a) (from ) (b) (MP with AND, a) (c) (MP with AND, a) 1. (1) (MP with T, b) (2) (MP with T, c) (3) (AND with 3, 5) 2. () (1) (Hyp) (2) (D1 with 1, b) () (1) (Hyp) (2) (D1 with 1, c) 3. () (1) (Hyp) (2) (MP with T, 1) (3) (MP with T, c) (4) (D1 with 2, 3) (5) (MP with T, 4) () (1) (Hyp) (2) (MP with T, 1) (3) (MP with T, b) (4) (D1 with 2, 3) (5) (MP with T, 4) 4. () (1)(GEN with , a) (2)(MP with A6 , 1) () (1)(GEN with , c) (2)(MP with A6 , 1) |
這些定理通常是混合使用,以達到「等價代換」的結果,例如,考慮到「邏輯與」是以下的符號定義:
那如果假設 ,就有:
換句話說,從「 」可以得到「 」,直觀上相當於,把 都代換成 則兩式等價。日後像這樣遞迴地套用上述定理來得到「代換則某兩式等價」,都簡單地以「引用(Equv)」來表示這段實際的推演過程。
由普遍化,很容易證明以下關於"交換性"的定理
元定理 —
(1)
(2)
(3)
注意最後(3)一般來說是不能反向的,只要想到"對每個 ,都有一個數(也就是 ),使 ",但是任取一個 的數 和任意的數 , 並不一定會為零。
數學中常常有 "對所有 有...",或是 "存在 使的..."。而兩句話比較清晰,接近一階邏輯語言的說法是 "對所有 ,只要 則..." 與 "存在 , 且..."。「大於」直觀上是一個二元关系,也就是說,在公理化集合論裡對應於一條 ( 或 ) 在裡面完全自由的合式公式。據此,可做以下的符號定義
符號定義 —
如果變數 和 都於合式公式 裡完全自由,那
但直觀上也會說 "對所有 和 有...",這樣連續,帶有條件的全稱量詞也是有"交換性"的。 為了討論這個問題,首先需要一些前置的定理
(abb) —
這樣就可以證明以下定理
元定理 —
如果變數 和 都於合式公式 和 裡完全自由,若項 裡沒有 那
證明 |
---|
()
()
|
如果再加上 "項 裡沒有 " 那就是 "對所有 和 有...",也就是以上所討論的情況了。以這個定理配上全稱量詞本身的交換性定理,那這句話就可以等價的說成 "對所有 和 若 且 則...",所以根據"且"的可交換性,可以進一步的說成 "對所有 和 有...",所以連續帶有條件的全稱量詞是"可交換的"。也就是說
元定理 —
如果變數 和 都於合式公式 和 裡完全自由,若項 裡沒有 ,且項 裡沒有 則
但對於帶條件的存在量詞,首先可以得到以下非等價的定理。
元定理 —
這是因為一般來說, 不總是能推出 。雖說如此,只要對公式做出一些限制,就會有以下交換的直觀定理:
(Ce)-Commutativity of existential quantification —
若變數 於公式 完全被約束,且 是另外一條公式,則:
也就是直觀上,「存在x使得 x>0 且 y>0」與「y>0 且存在x使得 x>0」是一樣的意思。
一般來說,等式 會被視為某個合式公式 的簡寫。若使用元定理的形式刻劃等式的性質,會作如下的定義
元定義 —
說一階邏輯理論 帶相等符號 意為( 、 和 都是 的任意變數)
並在這種狀況下,規定 為 的簡寫。
上面的定義符合函數符號直觀上的"唯一對應"。為了證明常數符號的"唯一性",需要以下元定理
元定理 —
說一階邏輯理論 帶相等符號 ,等同於要求:
證明 |
---|
() 從(E1)+(E2')+(E2")+(E3)推出(E2)的過程分成幾個階段推廣(E2') (1)含有常數符號的原子公式
(2)含有任意項的原子公式
(3)任意的公式
最後,取代 個 的狀況,就是取代 後再取代一次。所以可以由歸納法,從推廣後的(E2')推出(E2) ( ) 首先(E2')顯然只是(E2)的特例;要得到(E2")只要注意到由(E2)有 然後對(E1)使用(GEN)再配合(A4)使用MP律有 所以對上面兩式套用(D2)就有(E2")。 至於(E3),注意到由(E2)有 那這樣對上式和(E1)套用(D2)就有(E3) |
從上面可以得知,如果等式符號僅僅為斷言符號,那等式和它的公理一節的等式公理模式,是等價於本節的(E1)+(E2')+(E2")。
由上面的元定理,對帶有等式符號的 可以證明以下的等式性質
元定理 —
若 、 與 為 的任意項,則有
證明提示:
對任意常數符號 ,上列元定理確保了
也就是常數符號的"唯一性"。
數學討論中,常常唯一存在某個符合特定條件的數,像是「存在唯一的實數 使的對所有的实数 , 」;更精確地來說,這句話的意思是:
這樣一般來說,可以對任意變數 和合式公式 做以下的符號定義:
符號定義 —
(其中 必須是展開以上定義時首次出現的變數; 是將 內自由的 都取代成 所形成的新公式。)
注意到要能定義唯一性,一階邏輯理論一定要帶有等號。
上節所提到的例子,實際上就是所謂的實數 ,但常數符號不能憑空從理論中冒出來,所以仔細來說,「定義實數 」的過程應該是在原來的理論添加新的常數符號「 」與以下的公理:
這樣的話,「 」就是一條含有新常數符號的敘述,它應等價於:
也就是說,添加「 」創造了一套新理論,新理論的每條新敘述會對應到舊理論的某條舊敘述,且照理來說,新的對舊的也會對,反之亦然。
更一般的來說,如果新的一階邏輯理論,是在舊的理論增添一些新符號跟新公理(並額外要求新符號與舊公理相容),那為了讓新舊理論等效,對於任意新理論的合式公式 ,都要有某條相應的舊理論公式 滿足以下條件[5]:
新舊理論的等價條件 —
( 代表舊理論可以推出; 代表新理論可以推出。)
(1)若 本來就內含在舊理論裡,則 就是 。
(2)
(3)若 ,則有 。
從條件(2)事實上就可以推出「若 ,則有 」,因為 的話, 新理論只是擴張舊理論而沒改變舊理論固有的定理,所以有 ,但這樣根據條件(2)跟MP律就會有 。所以條件(2)事實上是比「舊的對那新的也對」強的條件,但在之後的推導上(2)會比較方便。
在以嚴謹的方式實踐以上提及的直觀動機前,需要一個預備定理
元定理 —
變數 在和合式公式 與 完全自由,則有
(Aux)
證明 |
---|
()
()
|
一般來說,如果變數 在 完全自由,且舊理論裡有:
那所謂的新理論,就是添加一個函數符號 和以下的新公理:
如果僅僅是:
的話,添加的是常數符號 與以下的新公理:
添加常數符號的情況可視為添加函數符號情況的特例,因為常數符號可以視為「零變數」的函數符號。
但不管如何,還需假設 和新理論的邏輯公理、量詞公理相容,也就是所有公理模式須涵蓋內含 的項。特別像是(A4)這種將自由變數代換成項的公理模式,也就是說,若項 內含 ,且公式 內自由的 都不在 的變數的量詞範圍內,那
仍然是新理論的公理。
另外還需要考慮到 與等號的相容性(換句話說,新理論仍須是帶等號的一階邏輯理論),這樣的話,考慮到上面等式定理所述的條件(E2''),需額外假設:
新理論的額外假設 —
對任何介於 與 的下標 和變數
是公理 (若是添加常數符號的特例,就不須額外假設以上的公理)
這樣就有以下直觀的定理
元定理 —
對變數 有
(E)
證明 |
---|
()
()
|
換句話說,「 」在新理論裡等價於 「對所有的實數 , 」。
下面列出了一些重要的元逻辑定理。
用自然语言表达的概念必须在一阶逻辑(FOL)可以为为其效力之前必须被转换到FOL,而在这种转换中可能有一些潜在的缺陷。在FOL中,意味着“要么p要么q要么二者”,就是说它是“包容性”的。在英语中,单词“or”有时是包容性的(比如,“加牛奶或糖?”),有时是排斥性的(比如,“喝咖啡或茶?”,通常意味着取其中一个或另一个但非二者)。类似的,英语单词“some”可以意味着“至少一个,可能全部”,有时意味着“不是全部,可能没有”。英语单词“and”有时要按“or”转换(比如,“男人和女人可以申请”)。 [6]
所有数学概念都有它的强项和弱点;下面列出一阶逻辑的一些问题。
带有等式的FOL不包含或允许定义if-then-else斷言或函数if(c,a,b),这裡的c是表达为公式的条件,而a和b是要么都是项要么都是公式,并且它的结果是a如果c为真,或者b如果它为假。问题在于FOL中,斷言和函数二者只接受(“非布尔类型”)项作为参数,而条件的明确表达是(“布尔类型”)公式。这是不幸的,因为很多数学函数是依据if-then-else而方便的表达的,而if-then-else是描述大多数计算机程序的基础。
在数学上,有可能重定义匹配公式算子的新函数的完备集合,但是这是非常笨拙的。[7] 斷言if(c,a,b)如果重写为就可以在FOL中表达,但是如果条件c是复杂的这就是笨拙的。很多人扩展FOL增加特殊情况斷言叫做“if(条件,a, b)”(这里a和b是公式)和/或函数“ite(条件,a, b)”(这裡的a和b是项),它们都接受一个公式作为条件,并且等于a如果条件为真,或b如果条件为假。这些扩展使FOL易于用于某些问题,并使某类自动定理证明更容易。[8] 其他人进一步扩展FOL使得函数和斷言可以在任何位置接受项和公式二者。
除了在公式(“布尔类型”)和项(“非布尔类型”)之间的区别之外,FOL不包括类型(种类)到自身的概念中。 某些人争辩说缺乏类型是巨大优点 [9],而很多其他人发觉了定义和使用类型(种类)的优点,比如帮助拒绝某些错误或不想要的规定 [10]。 想要指示类型的那些人必须使用在FOL中可获得的符号来提供这种信息。这么做使得这种表达更加复杂,并也容易导致错误。
单一参数斷言可以用来在合适的地方实现类型的概念。例如:
斷言Man(x)可以被认为是一类“类型断言”(就是说,x必须是男人)。 斷言还可以同指示类型的“存在”量词一起使用,但这通常应当转而与逻辑合取算子一起来做,比如:
容易写成,但这将等价与(“存在不是男人的事物或者存在是人类的事物”),这通常不是想要的。类似的,可以做一个类型是另一个类型的子类型的断言,比如:
从Löwenheim–Skolem定理得出在一阶逻辑中不可能刻画有限性或可数性。若一階理論有任意有限大的模型,則也有無窮大的模型,所以說不能刻劃有限性。[11]:1而若理論有某個無窮基數大小的模型,則也必有任意更大的模型,所以不能刻劃可數性。[12]:45另一個例子,是無法用一階語言將實數系公理化,因為不論用何種一階理論描述,既然該理論有實數系此種無窮模型(大小為),所以必有比實數系更大(比如)的另一個模型,從而該理論不是(唯一地)刻劃實數系的性質。實數系滿足的公理中,有上确界性质一項,它声称实数的所有有界的、非空集合都有上确界。一階邏輯祗能對元素量化,但此公理中,要對模型的全部子集量化,这就需要二阶逻辑了。[13]:30
很多情况可以被建模为节点和有向连接(边)的图。例如,效验很多系统要求展示不能从“好”状态触及到“坏”状态,而状态的相互连接经常可以建模为图。但是,可以证明这种可及性不能用斷言逻辑完全表达。换句话说,没有斷言逻辑公式f,带有u和v作为它的唯一自由变量,而R作为它唯一的(2元)斷言符号,使得f在一个有向图中成立,如果在这个图中存在从关联于u的节点到关联于v的节点的路径。[14]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.