谓词演算

**一階邏輯**是使用於數學、哲學、語言學及電腦科學中的一種形式系統，也可以稱為：**一階斷言演算**、**低階斷言演算**、**量化理論**或謂詞邏輯。一階邏輯和命題邏輯的不同之處在於，一階邏輯包含量詞。

高階邏輯和一階邏輯不同之處在於，高階邏輯的斷言符號可以有斷言符號或函數符號當做引數，且容許斷言量詞或函數量詞。在一階邏輯的語義中，斷言被解釋為關係。而高階邏輯的語義裡，斷言則會被解釋為集合的集合。

在通常的語義下，一階邏輯是可靠（所有可證的敘述皆為真）且完備（所有為真的敘述皆可證）的。雖然一階邏輯的邏輯歸結只是半可判定性的，但還是有許多用於一階邏輯上的自動定理證明。一階邏輯也符合一些使其能通過證明論分析的元邏輯定理，如勒文海姆–斯科倫定理及緊緻性定理。

一階邏輯是數學基礎中很重要的一部份。許多常見的公理系統，如一階皮亞諾公理、馮諾伊曼 - 博內斯 - 哥德爾集合論和策梅洛 - 弗蘭克爾集合論都是一階理論。然而一階邏輯不能控制其無窮模型的基數大小，因根據勒文海姆–斯科倫定理和康托爾定理，可以構造出一種「病態」集合論模型，使整個模型可數，但模型內卻會覺得自己有「不可數集」。類似地，可以證明實數系的普通一階理論既有可數模型又有不可數模型。這類的悖論被稱為斯科倫悖論。但一階的直覺主義邏輯裡，勒文海姆–斯科倫定理不可證明，故不會有以上之現象。

## 簡介

在命題邏輯裡，「蘇格拉底是哲學家」、「柏拉圖是哲學家」只能簡單標記為 $p$ 及 $q$ 。

而一階邏輯先設符號 ${\text{Phil}}(x)$ 意為 「 _x_ 是哲學家」，然後以 $s$ 代表蘇格拉底、 $b$ 代表柏拉圖，則 ${\text{Phil}}(s)$ 對應 $p$ ； ${\text{Phil}}(b)$ 對應 $q$ 。也就是賦予**斷言符號**「 ${\text{Phil}}(x)$ 」**語意的解釋。**這個解釋預設一個「所有人類的群體」（也就是語義解釋的論域），並將變數 $x$ 解釋為自群體中取出來的某人。

斷言符號可以包含一個以上的變數。例如：設 ${\text{Cp}}(x,\,y)$ 意為「 x 與 y 是夫妻」，則 ${\text{Cp}}(s,\,y)$ 意為「蘇格拉底和 _y_ 是夫妻」。

一階邏輯和命題邏輯相同，斷言符號和變數還能與邏輯符號組成更複雜的敘述。例如：設斷言符號 ${\text{Schol}}(x)$ 意為 $x$ 是學者。則「若 _x_ 為哲學家，則 _x_ 為學者」可表示為：

　
: ${\text{Phil}}(x)\Rightarrow {\text{Schol}}(x)\,$

而「對所有 _x_ ，若 _x_ 為哲學家，則 _x_ 為學者」則記為：

　
: $\forall x({\text{Phil}}(x)\Rightarrow {\text{Schol}}(x))$

也就是自左方開始閱讀，以 $\forall x$ 表示「對於所有 _x_ 」，可以將之理解為「對於所有 _x_ ， $\forall x$ 右方的敘述為真。」其中， $\forall x$ 這個符號被稱為 $x$ 的全稱量詞。

直觀上有「若所有 _x_ 是哲學家，那 _x_ 的長子也會是哲學家」這樣「合理」的敘述。若設 ${\text{Son}}(x)$ 意為 「 _x_ 的長子」，那麼這段「合理」敘述可記為：

　
: $\forall x{\text{Phil}}(x)\Rightarrow {\text{Phil}}[{\text{Son}}(x)]$

 $\Rightarrow $ 表示「與 $x$ 有唯一對應的那個物件」，被稱為**函數符號**。這段直觀為真的敘述，經過適當的擴展以後就是一階邏輯其中的一條公理。

而對於「有 _x_ 是哲學家」這一敘述，則引入另一種量詞表記為：

　
: $\exists x({\text{Phil}}(x))$

自左方開始閱讀，以 $\exists x$ 代表「存在 _x_ 」，可以將之理解為「有 _x_ 使 $\exists x$ 右方的敘述為真」。其中， $\exists x$ 被稱為 $x$ 的存在量詞。全稱量詞和存在量詞一起被簡稱為**量詞**。

直觀上，「並非所有 _x_ 不是哲學家」，和「有 _x_ 是哲學家」是等價的；且「不存在 _x_ 不是學者」也與「所有的 _x_ 是學者」等價。所以只要有「否定」這個邏輯概念，那麼一階邏輯就能以全稱量詞為基礎，作以下的符號定義（ $\neg $ 解釋為 「否定」， 而 ${\mathcal {A}}$ 代表一段＂敘述＂）：

　
: $\exists x{\mathcal {A}}:=\neg [\forall x(\neg {\mathcal {A}})]$

由此，存在量詞被定義為全稱量詞的衍伸。

## 形式理論

一階邏輯的形式理論可分成幾個部份：

1. 語法：決定哪些符號組合是合式公式。（直觀上的「文法無誤的敘述」）
2. 推理規則：由合式公式符號組合出新合式公式的規則（直觀上的「推理」）
3. 公理：一套合式公式（直觀上的基本假設）

### 基本符號

一套理論能容許多少符號，取決於人類根據物理定律能塑造多少符號。但以目前無法確知宇宙是不是有限，或是是否可無限制分割。雖然所有的公理化集合論都以量詞的形式隱晦的承認無窮的存在（如 ZF 集合論的無窮公理），甚至以這樣自然數意義上的無窮為基礎，去建構出不可數的實數。但將之對應到現實，還是會回到同樣的物理問題。

謹慎起見，以下各種類的符號沒有特別聲明，數量將會是有限個。

#### 邏輯符號

詞彙表中存在若干個邏輯符號，通常包括：

1. 量化符號 $\forall $ 及 $\exists $
  * 某些作者會把 $\exists $ 符號定義為 $\exists x{\mathcal {A}}:=\neg [\forall x(\neg {\mathcal {A}})]$ ，如此便只需要 $\forall $ 做為基礎符號。
2. 邏輯聯結詞：以下為可能的表示符號（關于波蘭表示法下的邏輯連接詞，請參見邏輯運算的波蘭記法）：
  * 否定： $\neg $ 或 $\sim $
  * 條件： $\Rightarrow $ 或 $\rightarrow $ 或 $\supset $
  * 且： $\land $ 或 $\&$
  * 或： $\lor $ 或 _||_
  * 雙條件： $\Leftrightarrow $ 或 $\leftrightarrow $
  * 某些作者會作如下的符號定義：
　
: : ${\mathcal {A}}\wedge {\mathcal {B}}:=\neg ({\mathcal {A}}\Rightarrow (\neg {\mathcal {B}})),$

　
: ${\mathcal {A}}\vee {\mathcal {B}}:=(\neg {\mathcal {A}})\Rightarrow {\mathcal {B}},$

　
: ${\mathcal {A}}\Leftrightarrow {\mathcal {B}}:=({\mathcal {A}}\Rightarrow {\mathcal {B}})\wedge ({\mathcal {B}}\Rightarrow {\mathcal {A}}),$

　
: 如此一來只需要否定和條件做為基礎符號。
3. 標點符號：括號、逗號及其他，依作者的喜好有所不同。
  * 為了更有效的將括號做配對，通常還會採用**大括號 { }**跟**中括號 [ ]**。
4. 至多跟自然數一樣多的**變數**，通常標記為英文字母末端的小寫字母 _x_、_y_、_z_、…，也常會使用下標（或上標、上下標兼有）來區別不同的變數：_x_0、_x_1、_x_2、…（特別注意 c 有時候會被當成常數符號而引起混淆）。
5. 等式符號： $=$
  * 有作者會因為語義上對「相等」的不同解釋，而將等式符號視為雙元斷言符號、甚至是某種合式公式的簡寫。
6. 符號相等： $\asymp $
  * 為了將**符號辨識上區別等同**和等式符號，某些作者會額外採用這個符號。

注意：並非所有的符號都是必需的。比如，在比較極端的情況中，因為謝費爾豎線（或互斥或）的布林代數完備性使得所有不含量詞的邏輯公理都可以用謝費爾豎線表述，而大幅減少基礎的邏輯聯結詞。

另外，一些作者並沒有將語義學和形式理論劃分清楚，而會將真值常數納入符號的一環：用 T 、V_pq_ 或 $\top $ 來表示「真」，並用 F 、 O_pq_ 或 $\bot $ 來表示「假」。

#### 斷言符號

「他們兩人是夫妻」，是一個關於兩個「物件」的斷言，而「他是人」、「三點共線」則表明斷言容許一個或者多個物件。所以對於自然數 $n$ 、 $j$ 約定：

　
: $A_{j}^{n}(x_{1},\,x_{2},\,...,\,x_{n})$

為一階邏輯的合法詞彙。它在直觀上表示一個有 $n$ 個「物件」的斷言，稱為 $n$ **元斷言符號**。下標的自然數 $j$ 只是拿來和其他同為 $n$ 元的斷言符號作區別。

實用上只要有申明，不至於和其他詞彙引起混淆的話，可以用任意的形式簡寫一個斷言符號。如：公理化集合論裡的雙元斷言符號 $A_{1}^{2}(x,\,y)$ 也可以表示為 $x\in y$ 。

#### 函數符號

「物體的顏色」、「夫妻的長子」這種斷言說明了一組物件所**唯一**對應的物件。但不同的夫妻有不同的長子；不同的物體有不同的顏色。據此，形式上對於自然數 $n$ 、 $j$ 約定：

　
: $f_{j}^{n}(x_{1},\,x_{2},\,...,\,x_{n})$

為一階邏輯的合法詞彙，直觀上表示 $n$ 個「物件」所對應到的東西，稱它為 $n$ **元函數符號**。**需要特別注意**，這種「唯一對應」的直觀想法，必須配上關於「等式」的性質（詳見下面的等式定理章節），才能在形式理論中被實現。

與斷言符號一樣，只要不引起混淆，就可以用任何的形式簡寫函數符號。如：公理化集合論裡的 $x\cup y$ 是依據聯集公理而定義的新函數符號（請參見下面函數符號與唯一性章節），也可以冗長的表記為 $f_{j}^{2}(x,\,y)$ 。

#### 常數符號

「刻度 0」、「原點」、「蘇格拉底」是直觀上＂唯一不變＂的物件。據此，對自然數 $j$ 約定

　
: $c_{j}$

為一階邏輯的合法詞彙，直觀上表示一個「唯一不變」的物件，稱為**常數符號**。同樣的。「常數的不變性」需配上等式的性質（詳見下面等式定理）才能被實現。

為了不和變數的表記混淆，常數符號一樣可以用任何的形式簡寫，如公理化集合論裡的 $\varnothing $ 是根據空集公理和函數符號與唯一性，而定義的新常數符號。亦可冗長的表示為 $c_{j}$ 。

### 語法

和自然語言（如英語）不同，一階邏輯的語言以明確的遞迴定義判斷一個給定的詞彙是否合法。大致上來說，一階邏輯以「項」代表討論的物件，而對「項」的斷言組成了最基本的**原子（合式）公式**；而原子公式和邏輯符號組成了更複雜的合式公式（也就是「敘述」）。

#### 項

「那對夫妻的長子的職業」、「 $(x+y)\times z$ 」、「 $x\cup \varnothing $ 」代表變數可以與函數符號組成更一般的物件。據此形式，遞迴地規定一類合法詞彙 —— **項**為：

習慣上以大寫的西方字母（如英文字母、希伯來字母、希臘字母）代表項，如果變數不得不採用大寫字母，而可能跟項引起混淆的話，需額外規定分辨的辦法。

#### 原子公式

為了比較簡潔地規定甚麼是合式公式，先規定原子公式為：（若 $T_{1},\,....,\,T_{n}$ 是項）

　
: $A_{j}^{n}(T_{1},\,....,\,T_{n})$

這樣的形式。

#### 公式

一階邏輯的**合式公式**（簡稱公式或 $wf$ ）以下面的規則遞迴地定義：

另外成對的中括弧跟大括弧，符號辨識上視為成對的小括弧，而**草書的大寫西方字母**為公式的代號。

舉例來說，

　
: $\{(\forall y)A_{1}^{2}[x,\,f_{1}^{1}(y)]\}$

是公式而

　
: $\forall x\,x\Rightarrow $

則不是公式。

而接下來只要對任意公式 ${\mathcal {A}}$ 、 ${\mathcal {B}}$ 與變數 $x$ ，做以下符號定義

這樣所有的邏輯連接詞與量詞就納入了合式公式的規範。

#### 施用

所謂的**施用** / **作用**，是以下公式形式的口語說法：（其中 ${\mathcal {A}}$ 與 ${\mathcal {B}}$ 都是公式）

 * $(\neg {\mathcal {A}})$ 稱為 $\neg $ 施用於 ${\mathcal {A}}$ 上。
* $({\mathcal {A}}\Rightarrow {\mathcal {B}})$ 稱為 $\Rightarrow $ 施用於 ${\mathcal {A}}$ 和 ${\mathcal {B}}$ 上。
* $({\mathcal {A}}\wedge {\mathcal {B}})$ 稱為 $\wedge $ 施用於 ${\mathcal {A}}$ 和 ${\mathcal {B}}$ 上。
* $({\mathcal {A}}\vee {\mathcal {B}})$ 稱為 $\vee $ 施用於 ${\mathcal {A}}$ 和 ${\mathcal {B}}$ 上。
* $({\mathcal {A}}\Leftrightarrow {\mathcal {B}})$ 稱為 $\Leftrightarrow $ 施用於 ${\mathcal {A}}$ 和 ${\mathcal {B}}$ 上。
* $(\forall x{\mathcal {A}})$ 稱為 $\forall x$ 施用於 ${\mathcal {A}}$ 上。
* $(\exists x{\mathcal {A}})$ 稱為 $\exists x$ 施用於 ${\mathcal {A}}$ 上。

就類似於運算子作用在它們身上。

#### 自由變數和約束變數

量詞所施用的公式被稱為量詞的**範圍**（scope）。同一個變數在公式一般來說不只出現一次，若變數 $x$ 出現在 $\forall x$ 的範圍內，稱這樣出現的 $x$ 為**不自由** / **被約束的** $x$ （not free/bounded）；反過來說，不出現在 $\forall x$ 的範圍內的某個 $x$ 被稱為**自由的** $x$ 。

例如，對於公式：

　
: $\{(\forall x)[A_{1}^{1}(x)\Rightarrow A_{2}^{1}(y)]\}$

 $[A_{1}^{1}(x)\Rightarrow A_{2}^{1}(y)]$ 就是量詞 $\forall x$ 的範圍；而 $A_{1}^{1}(x)$ 裡的 $x$ 就是不自由的；反之 $A_{2}^{1}(y)$ 裡的 $y$ 就是自由的。

說 $x$ 於公式 ${\mathcal {A}}$ 完全自由，意為於 ${\mathcal {A}}$ 出現的 $x$ 都是自由的；反之，說 $x$ 於公式 ${\mathcal {A}}$ 完全不自由 / 完全被約束，意為 ${\mathcal {A}}$ 內根本沒有 $x$ ，或是 ${\mathcal {A}}$ 內沒有自由的 $x$ 。若 ${\mathcal {A}}$ 內所有的變數都完全不自由， ${\mathcal {A}}$ 特稱為**封閉公式 / 句子**（closed formula/sentence）。

#### 括弧的簡寫

括弧是為了保證語意解釋符合預期，但太多的括弧書寫不易，為此規定以下的「重構法」（反過來就是「簡寫法」），從表面上不合法的一串符號找出作者原來想表達的公式：

* 若整串符號的括弧不成對，直接視為**無法重構**。
* 以 $\lnot ,\,\land ,\,\lor ,\,\forall ,\,\exists ,\,\Rightarrow ,\,\Leftrightarrow $ （左至右）的施用順序重構括弧。
* 相鄰的邏輯連接詞或量詞無法決定施用順序的話，以右邊為先。
* 重構施用的順序，以被成對括弧包住的部分為優先施用，其次才是落單的斷言符號。

舉例來說

　
: $\lnot [\forall xA_{1}^{1}(x)]\Rightarrow \exists x\lnot A_{2}^{1}(x)$

的重構過程如下

　
: 1. $\{\lnot [\forall xA_{1}^{1}(x)]\}\Rightarrow \exists x[\lnot A_{2}^{1}(x)]$ （優先施用 $\lnot $ ）
2. $\{\lnot [\forall xA_{1}^{1}(x)]\}\Rightarrow \{\exists x[\lnot A_{2}^{1}(x)]\}$ （施用 $\exists $ ）
3. $\{\{\lnot [\forall xA_{1}^{1}(x)]\}\Rightarrow \{\exists x[\lnot A_{2}^{1}(x)]\}\}$ （最後施用 $\Rightarrow $ ）

可以被重構為公式的一串符號則寬鬆的認定為「合式公式」。（最明顯的例子就是合式公式最外層的括弧可以省略）

#### 波蘭表示法

波蘭表示法將邏輯連接詞前置於**被施用的公式**而非傳統的中間。如果沿用以上的＂施用順序＂，這個表示法允許捨棄所有括弧。如公式

　
: $\forall x\forall y\{A_{1}^{1}[f_{1}^{1}(x)]\Rightarrow \neg \{A_{1}^{1}(x)\Rightarrow A_{1}^{3}[f_{1}^{1}(y),x,z]\}\}$

轉成波蘭表示法的過程如下

　
: $\forall x\forall y\Rightarrow A_{1}^{1}f_{1}^{1}x\neg \Rightarrow A_{1}^{1}xA_{1}^{3}f_{1}^{1}yxz$ （轉成波蘭表示法的順序）

　
: $\Pi x\Pi y{\text{C}}A_{1}^{1}f_{1}^{1}x{\text{N}}{\text{C}}A_{1}^{1}xA_{1}^{3}f_{1}^{1}yxz$ （邏輯連結詞的符號轉換）

### 推理規則

#### MP 律

對於公式 ${\mathcal {A}}$ 和 ${\mathcal {B}}$ ：

　
: ${\mathcal {A}}\Rightarrow {\mathcal {B}}$ 和 ${\mathcal {A}}$ 組合出 ${\mathcal {B}}$ 。

直觀意義非常明顯，就是 _p_=>_q_ 且 _p_ 可以推出 _q_。

### 公理

#### 邏輯公理

它們實際上是公理模式，代表著「跟自然數一樣多」條的公理。

#### 量詞公理

以下的 $x$ 為任意變數， ${\mathcal {B}}$ 、 ${\mathcal {C}}$ 為任意公式。

它們實際上是公理模式。

#### 等式和它的公理

根據不同作者的看法，甚至是理論本身的需求，「等式」在形式理論裡可能是斷言符號或是一段公式（如 _a_ 等於 _b_ 可定義為對所有的 _x_ ， _x_ 屬於 _a_ 等價於 _x_ 屬於 _b_ ）。而如何刻劃直觀上「等式的性質」，有一開始就將「等式的性質」視為公理（模式），但也有視為元定理的另一套處理方法，以下暫且以公理模式的方式處理。以元定理處理的方法會在等式定理詳述。

事實上這兩個公理模式也確保了函數符號「唯一對應」和常數符號的「唯一性」，但證明這些性質需要一些元定理，簡便起見合併於下面的等式定理一節講述。

## 標準語義

一階邏輯的標準語義源於波蘭邏輯學家阿爾弗雷德・塔斯基所著《On the Concept of Truth in Formal Languages》。根據上面語法一節，公式是由原子公式遞迴地添加邏輯連結詞而來的，而原子公式是由斷言符號與項所構成的。所以要檢定一條公式在特定的論域下正不正確，就要規定**項的取值**，然後檢定這樣的取值會不會落在斷言符號所對應的關係裡。由此延伸出所有公式的「真假值「。

也就是一套一階邏輯的語義解釋，要包含

1. 變數取值的論域
2. 如何解釋函數符號（為論域中的某個函數）與常數符號（為論域中的某特定元素），以便從特定的變數取值得出項的取值。
3. 如何將斷言符號與論域裡的某關係做對應。

通常一套解釋方法（簡稱為**解釋**）會以代號 $M$ 表示。

### 項的取值

量詞的解釋需要指明變數取值範圍的論域 —— 也就是一個集合 $D$ 。而變數可能跟自然數一樣多，換句話說，所有變數在論域 $D$ 取的值可以依序以自然數標下標 —— 也就是一個在 $D$ 取值的數列。如果以 $x_{1},\,x_{2},\,x_{3},\,\cdots $ 的代號（不一定是變數本身的表示符號）來列舉變數，那麼從 $D$ 的某套變數取值就以

　
: $\left\langle a_{k}\right\rangle _{k\in \mathbb {N} }$

或較直觀的符號

　
: $\left\langle a_{1},\,a_{2},\,a_{3},\,\cdots \right\rangle $

來表示。

一套解釋 $M$ 會將 $n$ 元函數符號 $f_{i}^{n}$ 解釋成某個 ${(f_{i}^{n})}^{M}:D^{n}\to D$ 的 $n$ 元函數；而常數符號 $c_{l}$ 解釋成特定的 ${c_{l}}^{M}\in D$ （亦稱為 $c_{l}$ 的取值為 ${c_{l}}^{M}$ ），這樣就可以用上面語法一節定義項的方式，遞迴地規定**項的取值**：

### 真假的賦值

直觀上要解釋關係最直接的方法，就是列舉所有符合關係的物件；例如如果想說明**夫妻關係**，可以列舉所有（老公，老婆）的雙元有序對，但並非所有的人類有序對都會在這個關係中。

以此為基礎，若以 $D^{m}$ 代表所有以 $m$ 個 $D$ 中的元素構成的 $m$ 元有序對的集合（也就是 $m$ 元笛卡兒積） ，那一套解釋 $M$ 會將 $m$ 元斷言符號 $A_{j}^{m}$ 解釋為一個

　
: ${(A_{j}^{m})}^{M}\subseteq D^{m}$

的 $m$ 元有序對子集合。

這樣就可以依據語法的遞迴定義，以下面的規則對每條公式賦予真值。（這種賦值方式稱為 T - 模式，取名於邏輯學家阿爾弗雷德・塔斯基）

更進一步的來說

### 代數化語義

另一種一階邏輯語義的方法可經由命題邏輯的林登鮑姆 - 塔斯基代數擴展而成。有如下幾種類型：

* 圓柱代數，由阿爾弗雷德・塔斯基和其同事提出；
* 多元代數，由保羅・哈爾莫斯提出。
* 斷言函子邏輯，主要是基於威拉德・范・奧曼・奎因的工作成果。

這些代數都是純粹擴展兩元素布林代數而成的格。

塔斯基和葛范德於 1987 年證明，沒有超過包在三個以上的量化內的原子句子的部份一階邏輯，其表示力和關係代數相同。上述部份一階邏輯令人十分地感到有興趣，因為它已足夠表示皮亞諾算術和公理化集合論，包括典型的 ZFC。他們亦證明了，具有簡單有序對的一階邏輯和具有兩個有序的投影函數的關係代數等價。

### 空論域

上述的語義解釋都要求論域為非空集合。但在如自由邏輯之中，設定空論域是被允許的。甚至代數結構的類包含一個空結構（如空偏序集），當允許空論域時，這個類只能是一階邏輯中的一個基本類，不然就要將空結構由類中移除。

不過，空論域存在著一些難點：

* 許多常見的推理規則只在論域被要求是非空時才為有效的。一個例子為，當 _x_ 不是 $\phi \,$ 內的自由變數時， $\phi \lor \exists x\psi $ 會薀涵 $\exists x(\phi \lor \psi )$ 。這個用來將公式寫成前束範式的規則在非空論域中是可靠的，但在允許空論域時則是不可靠的。
* 在使用變數賦值函數的解釋中，真值的定義不能和空論域一起運作，因為不存在範圍為空的變數賦值函數。（相似地，也無法將解釋賦予上常數符號。）在甚至是原子公式的真值可被定義之前，都必須選定一個變數賦值函數。然後一個句子的真值即可在任一個變數賦值之下定義出其真值，且可證明其真值不依選定的賦值而變。這個做法在賦值函數不存在時不能運作；除非將其改成配上空論域。

因此，若空論域是被允許的，通常也必須被視成特例。不過，大多數的作家會簡單地將空論域由定義中排除。

## 常用的推理性質

#### 定理與證明

以下介紹一些基本用語和符號

口語上會稱公式 ${\mathcal {A}}$ （或 $\vdash _{\mathcal {L}}{\mathcal {A}}$ ） 為 ${\mathcal {L}}$ 下的定理（theorem）。而這列 ${\mathcal {C}}_{i}\,\,(1\leq i\leq n)$ 會稱為 $\vdash _{\mathcal {L}}{\mathcal {A}}$ 的**證明**。

例如定理 $(I)$ $\vdash _{\mathcal {L}}{\mathcal {B}}\Rightarrow {\mathcal {B}}$ 的證明：

以上其實是蘊含了無限多定理的元定理的證明 (因為沒有給出合式公式的明確形式)。方便起見，這種元定理還是會稱為定理並以同樣的形式來表達。

直觀上的證明，總是會有一些「前提假設」，對此，若以 $\Gamma $ 代表一列有限數目的公式，那

這樣稱 ${\mathcal {C}}_{i}\,\,(1\leq i\leq n)$ 為在前提 $\Gamma $ 下， ${\mathcal {A}}$ 的**證明**；或是說 ${\mathcal {A}}$ 是 $\Gamma $ 的**推論結果**。

若要特別凸顯 $\Gamma $ 裡的一條＂前提條件＂ ${\mathcal {B}}$ 對＂證明過程＂的重要性，可以用 $\Gamma ,\,{\mathcal {B}}\vdash _{\mathcal {L}}{\mathcal {A}}$ 的符號去特別凸顯。若 $\Gamma $ 裡的公式列舉出來有 ${\mathcal {B}}_{1},...,{\mathcal {B}}_{n}$ ，那亦可表示為

　
: ${\mathcal {B}}_{1},...,{\mathcal {B}}_{n}\vdash _{\mathcal {L}}{\mathcal {A}}$

證明過程沒有被參照的公式盡可能不寫出來。另一方面從以上對於證明定義可以發現，依怎樣的順序列舉前提條件，對於證明本身是不會有任何影響的。

本節所介紹的符號，在參照哪個理論很顯然的情況下， $\vdash _{\mathcal {L}}$ 的下標 ${\mathcal {L}}$ 可以省略。

實際的證明常常會＂參照＂別的（元）定理，嚴格來說，就是照抄（元）定理的證明過程，然後作一些修改使符號一致。為了節省證明的篇幅，參照時只會單單列出配合參照（元）定理所得出的公式（形式）**，並在後面註明參照的（元）定理代號。**

#### 演繹元定理

從公理（A1）和（A2）會得出不但直觀且實用的**演繹元定理**：

因為 $\Gamma $ 代表的是有限條公式，所以透過演繹元定理可以將證明過程必要的前提條件遞迴地移到 $\vdash $ 後，直到不需要任何前提為止；然後由 MP 律可以知道，若有 $\Gamma \vdash _{\mathcal {L}}{\mathcal {B}}\Rightarrow {\mathcal {C}}$ ，則有 $\Gamma ,{\mathcal {B}}\vdash _{\mathcal {L}}{\mathcal {C}}$ ，如此一來透過演繹元定理搬到推論結果的合式公式，也可以任意的搬回來。所以 **$\Gamma \vdash _{\mathcal {L}}{\mathcal {B}}$ 等價於某定理 $\vdash _{\mathcal {L}}{\mathcal {C}}$** 。因此也會將 $\Gamma \vdash _{\mathcal {L}}{\mathcal {B}}$ 稱為一個**定理**。

而從演繹元定理和 MP 律，會有以下直觀且實用的元定理

以下如果需要將參照的定理以演繹元定理進行＂搬移＂，會省略掉搬移的過程並在搬移後得到的結果後標註（D）。如果參照以上的（D1）和（D2）也會省略過程，單有結果和代號標註。

#### 否定

上面兩定理表達了雙否定推理上等價於於原公式，參照兩者任一會都以（DN）簡寫。

以上二定理表說明 ${\mathcal {B}}\Rightarrow {\mathcal {A}}$ 推理上等價於 $\neg {\mathcal {A}}\Rightarrow \neg {\mathcal {B}}$ ，參照這兩個定理中任一都以（T）表示。

由（T）可以得到形式上類似於公理（A3）的定理

#### 實質條件

以下的定理重現了實質條件的直觀理解。

#### 反證法

#### 邏輯與和邏輯或

##### 交換性

以下為＂且＂的交換性

類似的，（C2）正是＂或＂的＂可交換性＂：

##### 直觀意義

＂且＂的直觀意義是實質條件元定理的直接結果

從（AND）和 $\Leftrightarrow $ 的符號定義可知， $\vdash {\mathcal {B}}\Leftrightarrow {\mathcal {C}}$ 的證明可以拆成兩部分；習慣上會以「（ $\Rightarrow $ ） 」標示 $\vdash {\mathcal {B}}\Rightarrow {\mathcal {C}}$ 部分的證明，而「（ $\Leftarrow $ ） 」標示 $\vdash {\mathcal {C}}\Rightarrow {\mathcal {B}}$ 部分的證明。

類似的，＂或＂的直觀意義是（M0）跟（D）的直截結果

以下的定理則是（A3'）的直截結果

##### 結合律

對於＂且＂，展開符號定義後，可以從直觀意義輕鬆地得到

＂或＂也有類似的性質

##### 分配律

＂且＂和＂或＂之間還有分配律

#### 德摩根定理

以下的元定理的名字來自於英國邏輯學家奧古斯塔斯・德摩根。

#### 普遍化元定理

公理模式（A7）可以稍加延伸成以下的元定理

更進一步，有以下元定裡

（GEN）可以稍加修飾，以套用在含有存在量詞的公式上

#### 量詞的可交換性

由普遍化，很容易證明以下關於＂交換性＂的定理

注意最後（3）一般來說是不能反向的，只要想到＂對每個 $a$ ，都有一個數（也就是 $-a$ ），使 $a+(-a)=0$ ＂，但是任取一個 $a$ 的數 $(-a)$ 和任意的數 $b$ ， $b+(-a)$ 並不一定會為零。

#### 量詞的簡寫

數學中常常有 ＂對所有 $\epsilon >0$ 有...＂，或是 ＂存在 $\delta >0$ 使的...＂。而兩句話比較清晰，接近一階邏輯語言的說法是 ＂對所有 $\epsilon $ ，只要 $\epsilon >0$ 則...＂ 與 ＂存在 $\delta $ ， $\delta >0$ 且...＂。「大於」直觀上是一個二元關係，也就是說，在公理化集合論裡對應於一條 $\epsilon $ （ 或 $\delta $ ） 在裡面完全自由的合式公式。據此，可做以下的符號定義

但直觀上也會說 ＂對所有 $n>0$ 和 $m>0$ 有...＂，這樣連續，帶有條件的全稱量詞也是有＂交換性＂的。 為了討論這個問題，首先需要一些前置的定理

這樣就可以證明以下定理

如果再加上 ＂項 $S$ 裡沒有 $x$ ＂ 那就是 ＂對所有 $n>0$ 和 $m>0$ 有...＂，也就是以上所討論的情況了。以這個定理配上全稱量詞本身的交換性定理，那這句話就可以等價的說成 ＂對所有 $m$ 和 $n$ 若 $n>0$ 且 $m>0$ 則...＂，所以根據＂且＂的可交換性，可以進一步的說成 ＂對所有 $m>0$ 和 $n>0$ 有...＂，所以連續帶有條件的全稱量詞是＂可交換的＂。也就是說

但對於存在量詞，仿造上面的證明過程，只能得出以下非等價的定理。

這是因為一般來說， $(\exists y){\mathcal {D}}$ 不總是能推出 ${\mathcal {D}}$ 。所以帶有條件的存在量詞是沒有交換性的。

#### 等式定理

一般來說，等式 $(x=y)$ 會被視為某個合式公式 ${\mathcal {E}}(x,\,y)$ 的簡寫。若使用元定理的形式刻劃等式的性質，會作如下的定義

上面的定義符合函數符號直觀上的＂唯一對應＂。為了證明常數符號的＂唯一性＂，需要以下元定理

從上面可以得知，如果等式符號僅僅為斷言符號，那等式和它的公理一節的等式公理模式，是等價於本節的（E1）+（E2'）+（E2＂）。

由上面的元定理，對帶有等式符號的 ${\mathcal {L}}$ 可以證明以下的等式性質

對任意常數符號 $c$ ，上列元定理確保了

　
: $\vdash _{\mathcal {L}}(c=c)$

　
: $(x=c),\,(y=c)\vdash _{\mathcal {L}}(x=y)$

也就是常數符號的＂唯一性＂。

## 函數符號與唯一性

## 一階邏輯的元定理

下面列出了一些重要的元邏輯定理。

1. 不像命題演算，一階邏輯是不可判定性的。對於任意的公式 P，可以證實沒有判定過程，判定 P 是否有效，（參見停機問題）。（結論獨立的來自於邱奇和圖靈。）
2. 有效性的判定問題是半可判定的。按哥德爾完備性定理所展示的，對於任何**有效的**公式 P, P 是可證明的。
3. 一元斷言邏輯（就是說，斷言只有一個參數的斷言邏輯）是可判定的。

## 轉換自然語言到一階邏輯

用自然語言表達的概念必須在一階邏輯（FOL）可以為為其效力之前必須被轉換到 FOL，而在這種轉換中可能有一些潛在的缺陷。在 FOL 中， $p\lor q$ 意味著「要麼 p 要麼 q 要麼二者」，就是說它是「包容性」的。在英語中，單詞「or」有時是包容性的（比如，「加牛奶或糖？」），有時是排斥性的（比如，「喝咖啡或茶？」，通常意味著取其中一個或另一個但非二者）。類似的，英語單詞「some」可以意味著「至少一個，可能全部」，有時意味著「不是全部，可能沒有」。英語單詞「and」有時要按「or」轉換（比如，「男人和女人可以申請」）。

## 一階邏輯的限制

所有數學概念都有它的強項和弱點；下面列出一階邏輯的一些問題。

### 難於表達 if-then-else

帶有等式的 FOL 不包含或允許定義 if-then-else 斷言或函數 if（c,a,b），這裡的 c 是表達為公式的條件，而 a 和 b 是要麼都是項要麼都是公式，並且它的結果是 a 如果 c 為真，或者 b 如果它為假。問題在於 FOL 中，斷言和函數二者只接受（「非布林類型」）項作為參數，而條件的明確表達是（「布林類型」）公式。這是不幸的，因為很多數學函數是依據 if-then-else 而方便的表達的，而 if-then-else 是描述大多數電腦程式的基礎。

在數學上，有可能重定義匹配公式算子的新函數的完備集合，但是這是非常笨拙的。
斷言 if（c,a,b）如果重寫為 $(c\wedge a)\lor (\neg c\wedge b)$ 就可以在 FOL 中表達，但是如果條件 c 是複雜的這就是笨拙的。很多人擴充 FOL 增加特殊情況斷言叫做「if（條件，a, b）」（這裡 a 和 b 是公式）和／或函數「ite（條件，a, b）」（這裡的 a 和 b 是項），它們都接受一個公式作為條件，並且等於 a 如果條件為真，或 b 如果條件為假。這些擴充使 FOL 易於用於某些問題，並使某類自動定理證明更容易。
其他人進一步擴充 FOL 使得函數和斷言可以在任何位置接受項和公式二者。

### 類型（種類）

除了在公式（「布林類型」）和項（「非布林類型」）之間的區別之外，FOL 不包括類型（種類）到自身的概念中。
某些人爭辯說缺乏類型是巨大優點
，而很多其他人發覺了定義和使用類型（種類）的優點，比如幫助拒絕某些錯誤或不想要的規定
。
想要指示類型的那些人必須使用在 FOL 中可獲得的符號來提供這種訊息。這麼做使得這種表達更加複雜，並也容易導致錯誤。

單一參數斷言可以用來在合適的地方實現類型的概念。例如：

　
: $\forall x(Man(x)\rightarrow Mortal(x))$ ，

斷言 Man（x）可以被認為是一類「類型斷言」（就是說，x 必須是男人）。
斷言還可以同指示類型的「存在」量詞一起使用，但這通常應當轉而與邏輯合取算子一起來做，比如：

　
: $\exists x(Man(x)\wedge Mortal(x))$ （「存在既是男人又是人類的事物」）。

容易寫成 $\exists xMan(x)\rightarrow Mortal(x)$ ，但這將等價與 $\exists x\neg Man(x)\lor \exists xMortal(x)$ （「存在不是男人的事物或者存在是人類的事物」），這通常不是想要的。類似的，可以做一個類型是另一個類型的子類型的斷言，比如：

　
: $\forall x(Man(x)\rightarrow Mammal(x))$ （「對於所有 x，如果 x 是男人，則 x 是哺乳動物）。

### 難於刻畫模型大小

從 Löwenheim–Skolem 定理得出在一階邏輯中不可能刻畫有限性或可數性。若一階理論有任意有限大的模型，則也有無窮大的模型，所以說不能刻劃有限性。而若理論有某個無窮基數大小的模型，則也必有任意更大的模型，所以不能刻劃可數性。另一個例子，是無法用一階語言將實數系公理化，因為不論用何種一階理論描述，既然該理論有實數系此種無窮模型（大小為 $2^{\aleph _{0}}$ ），所以必有比實數系更大（比如 $2^{2^{\aleph _{0}}}$ ）的另一個模型，從而該理論不是（唯一地）刻劃實數系的性質。實數系滿足的公理中，有上確界性質一項，它聲稱實數的所有有界的、非空集合都有上確界。一階邏輯祗能對元素量化，但此公理中，要對模型的全部子集量化，這就需要二階邏輯了。

### 圖可及性不能表達

很多情況可以被建模為節點和有向連接（邊）的圖。例如，效驗很多系統要求展示不能從「好」狀態觸及到「壞」狀態，而狀態的相互連接經常可以建模為圖。但是，可以證明這種可及性不能用斷言邏輯完全表達。換句話說，沒有斷言邏輯公式 f，帶有 u 和 v 作為它的唯一自由變數，而 R 作為它唯一的（2 元）斷言符號，使得 f 在一個有向圖中成立，如果在這個圖中存在從關聯於 u 的節點到關聯於 v 的節點的路徑。

## 參見

## 參考文獻

### 參照

### 來源

## 外部連結

* _Stanford Encyclopedia of Philosophy_：＂Classical Logic（頁面存檔備份，存於網際網路檔案館） -- by Stewart Shapiro. Covers syntax, model theory, and metatheory for first order logic in the natural deduction style.
* _forall x: an introduction to formal logic（頁面存檔備份，存於網際網路檔案館）_ , by P.D. Magnus, covers formal semantics and proof theory for first-order logic.
* Metamath（頁面存檔備份，存於網際網路檔案館）：an ongoing online project to reconstruct mathematics as a huge first order theory, using first order logic and the axiomatic set theory ZFC. _Principia Mathematica_ modernized and done right.
* Podnieks, Karl. _Introduction to mathematical logic.（頁面存檔備份，存於網際網路檔案館）_