命題邏輯 是邏輯學 的一個分支。[ 1] 它也稱為命題演算 、句子演算 、句子邏輯 ,有時也稱為零階邏輯 。它涉及命題 (可以是真或假)和命題 之間的關係,包括基於它們的論證的構建。複合命題是通過邏輯連接詞連接命題 而形成的。不包含邏輯連接詞的命題稱為原子命題 。 與一階邏輯 不同,命題邏輯不處理非邏輯對象、以及關於它們的謂詞 或量詞 。然而,命題邏輯的所有機制都包含在一階邏輯 和高階邏輯 中。從這個意義上說,命題邏輯是一階邏輯 和高階邏輯 的基礎。
在邏輯 和數學 裡, 命題邏輯 是一個形式系統 , 有可以由以邏輯運算符 結合原子命題來構成代表「命題 」的公式,以及允許某些公式建構成「定理」的一套形式「證明規則」。
一般地說,演算是一個形式系統 ,包括一套語法表示式(合式公式 )、這些表示式的一個特定子集(公理)和一套定義了特定的二元關係 的形式規則,這個二元關係可解釋為表示式空間上的邏輯等價 關係。
若形式系統會作為一個邏輯系統 ,其表示式會被解釋成數學陳述,且其規則,被稱之為「推理規則」,則一般會是保真的。在此設定下,規則(可能也包括公理 )可以被用來,從給定為真的陳述的公式中,推導出表示真的陳述的公式來。
公理的集合可能為空集、非空有限集、可數無限集或由公理模式所給定。形式文法 遞迴地定義了語言 的表示式和合式公式。之外,有時也可以給定一個語義 ,用以定義真值和賦值 (或解釋 )。
命題運算的語言 包括:(1)一套原始符號,被稱之為「原子公式 」、「占位符」、「命題字母」或「命題變量」;(2)一套運算符號,被稱之為「邏輯運算符 」。一個合式公式 是任一原子公式,或任一以運算符號依文法規則由原子公式建立起的公式。
在下文中我們描述一種標準命題演算。很多不同的公式系統存在,它們都或多或少等價但在下列方面不同:(1)它們的語言(就是說哪些原始符號和運算符號是語言的一部分);(2)它們有哪些(如果有的話)公理;(3)採用了哪些推理規則。
命題演算 是一個形式系統
L
=
L
(
A
,
Ω
,
Z
,
I
)
{\displaystyle {\mathcal {L}}={\mathcal {L}}\ (\mathrm {A} ,\ \Omega ,\ \mathrm {Z} ,\ \mathrm {I} )}
,它的公式按如下方式構造:
A
{\displaystyle \mathrm {A} \!}
集合是由名為「命題符號」或「命題變量 」之元素所組成的有限集合,一個「命題變量 」可取值為集合裡的「命題符號」。語法上來說,它們是形式語言
L
{\displaystyle {\mathcal {L}}}
最基本的元素,亦被稱之為「原子公式 」或「終端元素」。在接著的例子中,
A
{\displaystyle \mathrm {A} \!}
內的元素一般寫作字母
p
{\displaystyle p}
,
q
{\displaystyle q}
,
r
{\displaystyle r}
之類的形式。
Ω
{\displaystyle \Omega \!}
是名為「算子符號 」或「邏輯運算符 」之元素所組成的有限集合。集合
Ω
{\displaystyle \Omega \!}
被劃分 成如下等不相交的子集:
Ω
=
Ω
0
∪
Ω
1
∪
…
∪
Ω
j
∪
…
∪
Ω
m
{\displaystyle \Omega =\Omega _{0}\cup \Omega _{1}\cup \ldots \cup \Omega _{j}\cup \ldots \cup \Omega _{m}\,}
。
在此一劃分中,
Ω
j
{\displaystyle \Omega _{j}\!}
是指元數 為
j
{\displaystyle j\!}
的算子符號所構成的集合。
在更熟知的命題演算中,
Ω
{\displaystyle \Omega \!}
一般被劃分如下:
Ω
1
=
{
¬
}
,
{\displaystyle \Omega _{1}=\{\lnot \}\,,}
Ω
2
⊆
{
∧
,
∨
,
→
,
↔
}
{\displaystyle \Omega _{2}\subseteq \{\land ,\lor ,\rightarrow ,\leftrightarrow \}\,}
。
一種常用的做法是把常數邏輯值 當作一種零元算子,即:
Ω
0
=
{
⊤
,
⊥
}
{\displaystyle \Omega _{0}=\{\top ,\ \bot \}\,}
。
有些作者會用 ~ 來替代
¬
{\displaystyle \neg }
,也有的用 & 或
⋅
{\displaystyle \cdot }
來取替
∧
{\displaystyle \land }
。邏輯值所構成的集合也有許多不同的符號表示,如 {假,真} 、{F,T} 或 {0,1} 來取替 {
⊥
{\displaystyle \bot }
,
⊤
{\displaystyle \top }
},這些都常見於各個論著之中。
Z
{\displaystyle \mathrm {Z} \!}
集合是「轉換規則」(當作為邏輯應用時則稱之為「推理規則 」)之所構成的有限集合。
Z
{\displaystyle \mathrm {Z} \!}
集合的「轉換規則」是用「原子公式 」和「邏輯運算符 」構成的。
I
{\displaystyle \mathrm {I} \!}
是「起始點」(當得到邏輯解釋時則稱之為「公理 」)所構成的有限集合。
依據所使用的精確形式文法或文法形式化,可能需要以左括號"("和右括號")"作語法上的輔助,用來完成公式的構造。
L
{\displaystyle {\mathcal {L}}}
的語言,亦稱之為「公式」或「合式公式 」的集合,可由如下規則集合被歸納 或遞迴 地定義:
基本元素:
A
{\displaystyle \mathrm {A} \!}
內的任何元素都是
L
{\displaystyle {\mathcal {L}}}
的公式。
如果
p
1
,
p
2
,
…
,
p
j
{\displaystyle p_{1},p_{2},\ldots ,p_{j}}
是公式 和
f
{\displaystyle f}
屬於
Ω
j
{\displaystyle \Omega _{j}}
, 則
(
f
p
1
p
2
…
p
j
)
{\displaystyle \left(fp_{1}p_{2}\ldots p_{j}\right)}
也是公式.
封閉性:其他都不會是
L
{\displaystyle {\mathcal {L}}}
的公式。
透過重複應用這三個規則,可以建構出複雜的公式來。例如:
依規則1,
p
{\displaystyle p}
是公式。
依規則2,
¬
p
{\displaystyle \neg p}
是公式。
依規則1,
q
{\displaystyle q}
是公式。
依規則2,
(
¬
p
∨
q
)
{\displaystyle (\neg p\lor q)}
是公式。
設
L
1
=
L
(
A
,
Ω
,
Z
,
I
)
{\displaystyle {\mathcal {L}}_{1}={\mathcal {L}}\ (\mathrm {A} ,\ \Omega ,\ \mathrm {Z} ,\ \mathrm {I} )}
,這裡的
A
,
Ω
,
Z
,
I
{\displaystyle \mathrm {A} ,\ \Omega ,\ \mathrm {Z} ,\ \mathrm {I} }
定義如下:
A
{\displaystyle \mathrm {A} \!}
是個含有足夠多元素以應付討論所需的有限集合,如:
A
=
{
p
,
q
,
r
,
s
,
t
,
u
}
{\displaystyle \mathrm {A} =\{p,q,r,s,t,u\}\,}
。
功能齊全的套裝 邏輯運算符(邏輯連接詞和否定)的Ω如下。
Ω
{\displaystyle \Omega \!}
邏輯運算符 集合。 在合取 、析取 和蘊涵 (∧、∨和→)這三個運算符之中,可以將其中一個拿來當做基本的,而另兩個則以其和否定(
¬
{\displaystyle \neg }
)來定義。實際上,所有的邏輯運算符都可以用自足算子 的方式來定義。而雙條件(↔)當然可由合取和薀涵來定義,亦即
a
↔
b
{\displaystyle a\leftrightarrow b}
可被定義為
(
a
→
b
)
∧
(
b
→
a
)
{\displaystyle (a\rightarrow b)\land (b\rightarrow a)}
。
採用否定和薀涵做為命題演算的兩個基本運算,相當於把omega集
Ω
=
Ω
1
∪
Ω
2
{\displaystyle \Omega =\Omega _{1}\cup \Omega _{2}}
劃分如下:
Ω
1
=
{
¬
}
{\displaystyle \Omega _{1}=\{\lnot \}\,}
。
Ω
2
=
{
→
}
{\displaystyle \Omega _{2}=\{\rightarrow \}\,}
。
I
{\displaystyle \mathrm {I} \!}
公理系統集合。 有一個公理系統是揚·武卡謝維奇 所發現的,而這系統可以如下地公式化為此語言中的命題演算。各個公理都是由下列的公理模式作代換所得。
p
→
(
q
→
p
)
{\displaystyle p\to (q\to p)}
(
p
→
(
q
→
r
)
)
→
(
(
p
→
q
)
→
(
p
→
r
)
)
{\displaystyle (p\to (q\to r))\to ((p\to q)\to (p\to r))}
(
¬
p
→
¬
q
)
→
(
q
→
p
)
{\displaystyle (\neg p\to \neg q)\to (q\to p)}
Z
{\displaystyle \mathrm {Z} \!}
推理規則集合。 其推理規則為肯定前件 (即可由
p
{\displaystyle p}
和
(
p
→
q
)
{\displaystyle (p\rightarrow q)}
導出
q
{\displaystyle q}
)。而
a
∨
b
{\displaystyle a\lor b}
和
a
∧
b
{\displaystyle a\land b}
則是分別被定義為
¬
a
→
b
{\displaystyle \neg a\rightarrow b}
和
¬
(
a
→
¬
b
)
{\displaystyle \neg (a\rightarrow \neg b)}
。
設
L
2
=
L
(
A
,
Ω
,
Z
,
I
)
{\displaystyle {\mathcal {L}}_{2}={\mathcal {L}}\ (\mathrm {A} ,\ \Omega ,\ \mathrm {Z} ,\ \mathrm {I} )}
,這裡的
A
,
Ω
,
Z
,
I
{\displaystyle \mathrm {A} ,\ \Omega ,\ \mathrm {Z} ,\ \mathrm {I} }
定義如下:
A
{\displaystyle \mathrm {A} \!}
是個含有足夠多元素以應付討論所需的有限集合,如:
A
=
{
p
,
q
,
r
,
s
,
t
,
u
}
{\displaystyle \mathrm {A} =\{p,q,r,s,t,u\}\,}
。
Ω
=
Ω
1
∪
Ω
2
{\displaystyle \Omega =\Omega _{1}\cup \Omega _{2}}
劃分為如下:
Ω
1
=
{
¬
}
{\displaystyle \Omega _{1}=\{\lnot \}\,}
。
Ω
2
=
{
∧
,
∨
,
→
,
↔
}
{\displaystyle \Omega _{2}=\{\land ,\lor ,\rightarrow ,\leftrightarrow \}\,}
。
在此命題演算的例子中,轉換規則被解釋為所謂的「自然演繹系統 」下之推理規則。這裡表述的特定系統沒有起始點,這意味着它對邏輯應用的解釋是從空公理集合中推導出其定理 的。
起始點的集合是空的,亦即
I
=
∅
{\displaystyle \mathrm {I} =\varnothing \,}
。
轉換規則的集合
Z
{\displaystyle \mathrm {Z} \!}
描述如下:
此命題演算有十個推理規則 。這些規則允許我們從給定的一組假定為真的公式中推導出其他為真的公式。前九個只是簡單地指我們可以從其他合式公式推論出特定的合式公式。但是最後一個規則使用了假言(hypothetical)推理,這意味着在規則的前提中,我們可以臨時的假定一個(未證明的)假設作為推導出的公式集合的一部分,來查看我們是否能推導出一個特定的其他公式。因為前九個規則不是這樣而通常被描述為「非假言」規則,而最後一個則被稱為「假言」規則。
否定介入 :從
ϕ
→
¬
ψ
{\displaystyle \phi \rightarrow \neg \psi }
和
ϕ
→
ψ
{\displaystyle \phi \rightarrow \psi }
中可推出
¬
ϕ
{\displaystyle \neg \phi }
。
雙重否定除去 :從
¬
¬
ϕ
{\displaystyle \neg \neg \phi }
中可推出
ϕ
{\displaystyle \phi }
。
合取介入 :從
ϕ
{\displaystyle \phi }
和
ψ
{\displaystyle \psi }
中可推出
(
ϕ
∧
ψ
)
{\displaystyle (\phi \land \psi )}
。
合取除去 :從
(
ϕ
∧
ψ
)
{\displaystyle (\phi \land \psi )}
中可推出
ϕ
{\displaystyle \phi }
和
ψ
{\displaystyle \psi }
。
析取介入 :從
ϕ
{\displaystyle \phi }
中可推出
(
ϕ
∨
ψ
)
{\displaystyle (\phi \lor \psi )}
。
析取除去 :從
(
ϕ
∨
ψ
)
{\displaystyle (\phi \lor \psi )}
、
(
ϕ
→
χ
)
{\displaystyle (\phi \rightarrow \chi )}
和
(
ψ
→
χ
)
{\displaystyle (\psi \rightarrow \chi )}
可推出
χ
{\displaystyle \chi }
。
雙條件介入 :從
(
ϕ
→
ψ
)
{\displaystyle (\phi \rightarrow \psi )}
和
(
ψ
→
ϕ
)
{\displaystyle (\psi \rightarrow \phi )}
中可推出
(
ϕ
↔
ψ
)
{\displaystyle (\phi \leftrightarrow \psi )}
。
雙條件除去 :從
(
ϕ
↔
ψ
)
{\displaystyle (\phi \leftrightarrow \psi )}
中可推出
(
ϕ
→
ψ
)
{\displaystyle (\phi \rightarrow \psi )}
和
(
ψ
→
ϕ
)
{\displaystyle (\psi \rightarrow \phi )}
。
肯定前件 (條件除去):從
ϕ
{\displaystyle \phi }
和
(
ϕ
→
ψ
)
{\displaystyle (\phi \rightarrow \psi )}
中可推出
ψ
{\displaystyle \psi }
。
條件證明 (條件介入):若假定
ϕ
{\displaystyle \phi }
為真可證明出
ψ
{\displaystyle \psi }
,可推出
(
ϕ
→
ψ
)
{\displaystyle (\phi \rightarrow \psi )}
。
以下推導將用編號後的行的列表來表示,在每行之上有一個單一的公式和一個理由(justification)。論證的各個前提會在列表的首行給出。結論將在最後一行。一個推導稱為完備的,若所有行都是通過正確的應用一個規則而從前面的行得出的。
下面是(語法上的)證明的一個例子:
要證明:
A
→
A
{\displaystyle A\rightarrow A}
證明:
編號
公式
理由
1
A
{\displaystyle A}
前提
2
A
∨
A
{\displaystyle A\lor A}
析取介入自(1)
3
(
A
∨
A
)
∧
A
{\displaystyle (A\lor A)\land A}
合取介入自(1)和(2)
4
A
{\displaystyle A}
合取除去自(3)
5
A
⊢
A
{\displaystyle A\vdash A}
總結(1)到(4)
6
⊢
A
→
A
{\displaystyle \vdash A\rightarrow A}
條件證明自(5)
A
⊢
A
{\displaystyle A\vdash A}
可解釋為「假定
A
{\displaystyle A}
,推導出
A
{\displaystyle A}
」。
⊢
A
→
A
{\displaystyle \vdash A\rightarrow A}
為「不假定任何東西,推導出
A
{\displaystyle A}
蘊涵
A
{\displaystyle A}
」,或者「
A
{\displaystyle A}
蘊涵
A
{\displaystyle A}
是重言式」,或者「
A
{\displaystyle A}
蘊涵
A
{\displaystyle A}
是永真的」。
以上規則的關鍵特性是它們是可靠 的和完備 的。非形式的說,這意味着規則都是正確的並且不再需要其他規則。這些要求可以如下這樣正式的提出。
我們定義真值指派為把命題變量映射到真 或假 的函數 。非形式的,這種真值指派可以被理解為對事件的可能狀態(或可能世界 )的描述,在這裡特定的陳述是真而其他為假。公式的語義因而可以被形式化,通過定義哪些"事件狀態"是設定為真的。
我們通過如下規則定義這種真值指派
A
{\displaystyle A}
在什麼時候滿足特定公式:
A
{\displaystyle A}
滿足命題變量
P
{\displaystyle P}
當且僅當
A
(
P
)
=
{\displaystyle A(P)=}
真
A
{\displaystyle A}
滿足
¬
ϕ
{\displaystyle \neg \phi }
當且僅當
A
{\displaystyle A}
不滿足
ϕ
{\displaystyle \phi }
A
{\displaystyle A}
滿足
(
ϕ
∧
ψ
)
{\displaystyle (\phi \land \psi )}
當且僅當
A
{\displaystyle A}
滿足
ϕ
{\displaystyle \phi }
與
ψ
{\displaystyle \psi }
二者
A
{\displaystyle A}
滿足(φ ∨ ψ)當且僅當
A
{\displaystyle A}
滿足
ϕ
{\displaystyle \phi }
和
ψ
{\displaystyle \psi }
中至少一個
A
{\displaystyle A}
滿足(φ → ψ)當且僅當並非
A
{\displaystyle A}
滿足
ϕ
{\displaystyle \phi }
但不滿足
ψ
{\displaystyle \psi }
的情況
A
{\displaystyle A}
滿足(φ ↔ ψ)當且僅當
A
{\displaystyle A}
滿足
ϕ
{\displaystyle \phi }
與
ψ
{\displaystyle \psi }
二者,或則不滿足它們中的任何一個
通過這個定義,我們現在可以形式化公式
ϕ
{\displaystyle \phi }
被特定公式集合
S
{\displaystyle S}
蘊涵的意義。非形式的,就是在使給定公式集合
S
{\displaystyle S}
成立的所有可能情況下公式
ϕ
{\displaystyle \phi }
也成立。這引申出下面的形式化定義:我們說公式集合
S
{\displaystyle S}
語義蘊涵 特定的公式
ϕ
{\displaystyle \phi }
,條件是滿足在
S
{\displaystyle S}
中的公式的所有真值指派也滿足
ϕ
{\displaystyle \phi }
。
最後我們定義語法蘊涵 ,
ϕ
{\displaystyle \phi }
被
S
{\displaystyle S}
語法蘊涵,當且僅當我們可以在有限步驟內使用我們提出的上述推理規則推導出它。這允許我們精確的公式化推理規則的可靠性和完備性的意思:
可靠性 :如果公式集合
S
{\displaystyle S}
語法蘊涵公式
ϕ
{\displaystyle \phi }
,則
S
{\displaystyle S}
語義蘊涵
ϕ
{\displaystyle \phi }
完備性 :如果公式集合
S
{\displaystyle S}
語義蘊涵公式
ϕ
{\displaystyle \phi }
,則
S
{\displaystyle S}
語法蘊涵
ϕ
{\displaystyle \phi }
上述的兩個例子都滿足可靠性和完備性。
(對於多數邏輯系統,這是相對「簡單」的證明方向)
符號約定:設
G
{\displaystyle G}
是命題集合。設
ϕ
{\displaystyle \phi }
、
ψ
{\displaystyle \psi }
和
χ
{\displaystyle \chi }
是命題。我們把「
G
{\displaystyle G}
語法蘊涵
ϕ
{\displaystyle \phi }
」寫成「
G
{\displaystyle G}
證明
ϕ
{\displaystyle \phi }
」,還有把「
G
{\displaystyle G}
語義蘊涵
ϕ
{\displaystyle \phi }
」寫成「
G
{\displaystyle G}
蘊涵
ϕ
{\displaystyle \phi }
」。
我們要展示:
(
∀
ϕ
)
(
∀
G
)
{\displaystyle (\forall \phi )(\forall G)}
(如果
G
{\displaystyle G}
證明
ϕ
{\displaystyle \phi }
,則
G
{\displaystyle G}
蘊涵
ϕ
{\displaystyle \phi }
)
我們注意到「
G
{\displaystyle G}
證明
ϕ
{\displaystyle \phi }
」有一個歸納定義,這給予我們直接的辦法來驗證「如果
G
{\displaystyle G}
證明
ϕ
{\displaystyle \phi }
,則……」形式的斷言。所以我們的證明是用歸納法進行的。
I.基礎。驗證:如果
ϕ
{\displaystyle \phi }
是
G
{\displaystyle G}
的成員則
G
{\displaystyle G}
蘊涵
ϕ
{\displaystyle \phi }
II.基礎。驗證:如果
ϕ
{\displaystyle \phi }
是公理,則
G
{\displaystyle G}
蘊涵
ϕ
{\displaystyle \phi }
III.歸納步驟(對證明的長度
n
{\displaystyle n}
作歸納)
(a)假定對於任意的
G
{\displaystyle G}
和
ϕ
{\displaystyle \phi }
,如果
G
{\displaystyle G}
在
n
{\displaystyle n}
或更少的步數能證明
ϕ
{\displaystyle \phi }
,則
G
{\displaystyle G}
蘊涵
ϕ
{\displaystyle \phi }
。
(b)對於在第
n
+
1
{\displaystyle n+1}
步時,根據推理規則,由
G
{\displaystyle G}
及其
n
{\displaystyle n}
步以內證明的命題,可以推導出新的命題。驗證:對於任意的這樣的新命題
ψ
{\displaystyle \psi }
,
G
{\displaystyle G}
蘊涵
ψ
{\displaystyle \psi }
。
需要注意的是,對於自然演繹 系統,基礎步驟II可以省略,因為它們根本沒有公理。基本上,基礎步驟II是要展示每個公理都是(語義上的)邏輯真理。
基礎步驟證實了對於任何
G
{\displaystyle G}
,來自
G
{\displaystyle G}
的最簡單的可證明的語句都被
G
{\displaystyle G}
所蘊涵。(這是簡單的,因為集合蘊涵它的任何一個成員,是個平凡的語義事實)。歸納步驟將有系統的覆蓋所有的進一步的可證明的命題--通過考慮我們能夠使用推理規則達成邏輯結論的每種情況--並展示如果一個新命題是可證明的,它也是在邏輯上被蘊涵的。(例如,可能有一個規則,使得從
ϕ
{\displaystyle \phi }
可以推導出「
ϕ
{\displaystyle \phi }
或
ψ
{\displaystyle \psi }
」。在III.(a)中我們假定如果
ϕ
{\displaystyle \phi }
是可證明的則它也是被蘊涵的。我們也知道如果
ϕ
{\displaystyle \phi }
是可證明的,則「
ϕ
{\displaystyle \phi }
或
ψ
{\displaystyle \psi }
」是可證明的。接着,我們必須驗證「
ϕ
{\displaystyle \phi }
或ψ」也是被蘊涵的。我們求助於語義的定義和我們所做的假定來完成。我們假定了
ϕ
{\displaystyle \phi }
是可以從
G
{\displaystyle G}
證明出來的,所以它也被
G
{\displaystyle G}
所蘊涵。所以任何使
G
{\displaystyle G}
全部為真的指派,都使
ϕ
{\displaystyle \phi }
為真。此外通過「或」的語義定義,使
ϕ
{\displaystyle \phi }
為真的任何指派都使「
ϕ
{\displaystyle \phi }
或
ψ
{\displaystyle \psi }
」為真。所以任何使
G
{\displaystyle G}
的全部為真的指派,都使「
ϕ
{\displaystyle \phi }
或
ψ
{\displaystyle \psi }
」為真。所以「
ϕ
{\displaystyle \phi }
或
ψ
{\displaystyle \psi }
」被蘊涵了。)一般的,歸納步驟的證明會較長,但不過是對所有推論規則按例分析,去展示每個規則都能「保持」語義蘊涵。
通過可證明性的定義,除了
G
{\displaystyle G}
的成員、公理、或從規則推導出的命題之外,沒有別的命題是可證明的;而這些命題都是語義上被蘊涵的,所以演繹演算是可靠的。
(這通常是相對地困難不少的證明方向。)
我們採用同上面一樣的符號約定。
我們要展示:如果
G
{\displaystyle G}
蘊涵
ϕ
{\displaystyle \phi }
,則
G
{\displaystyle G}
證明
ϕ
{\displaystyle \phi }
。我們通過反證法來進行:我們轉而展示如果
G
{\displaystyle G}
不證明
ϕ
{\displaystyle \phi }
,則
G
{\displaystyle G}
不蘊涵
ϕ
{\displaystyle \phi }
。
I. 假設
G
{\displaystyle G}
不證明
ϕ
{\displaystyle \phi }
。
II.如果
G
{\displaystyle G}
不證明
ϕ
{\displaystyle \phi }
,則我們可以構造一個(有限的)"最大化的集合"
G
∗
{\displaystyle G^{*}}
,它是
G
{\displaystyle G}
的超集並且不證明
ϕ
{\displaystyle \phi }
。
(a)把這個語言中的所有命題上加置一個「次序」。(比如,字母表次序),並把它們編號為
E
1
,
E
2
,
⋯
{\displaystyle E_{1},E_{2},\cdots }
(b)歸納的定義集合
(
G
0
,
G
1
,
⋯
)
{\displaystyle (G_{0},G_{1},\cdots )}
的一個序列
G
n
{\displaystyle G_{n}}
為如下。
(i)
G
0
=
G
{\displaystyle G_{0}=G}
。
(ii)如果
G
k
∪
{
E
k
+
1
}
{\displaystyle G_{k}\cup \{E_{k+1}\}}
證明
ϕ
{\displaystyle \phi }
,則
G
k
+
1
=
G
k
{\displaystyle G_{k+1}=G_{k}}
。
(iii)如果
G
k
∪
{
E
k
+
1
}
{\displaystyle G_{k}\cup \{E_{k+1}\}}
不證明
ϕ
{\displaystyle \phi }
,則
G
k
+
1
=
G
k
∪
{
E
k
+
1
}
{\displaystyle G_{k+1}=G_{k}\cup \{E_{k+1}\}}
。
(c)定義
G
∗
{\displaystyle G^{*}}
為所有
G
n
{\displaystyle G_{n}}
的併集。(就是說,
G
∗
{\displaystyle G^{*}}
在任何
G
n
{\displaystyle G_{n}}
中的所有命題的集合)
(d)可以容易地驗證
(i)
G
∗
{\displaystyle G^{*}}
包含(是其超集)
G
{\displaystyle G}
(通過(b.i));
(ii)
G
∗
{\displaystyle G^{*}}
不證明
ϕ
{\displaystyle \phi }
(因為如果它證明
ϕ
{\displaystyle \phi }
,則某些命題被增加到某個
G
n
{\displaystyle G_{n}}
上而導致它證明了
ϕ
{\displaystyle \phi }
;但是這被定義所排除);
(iii)
G
∗
{\displaystyle G^{*}}
是(關於
ϕ
{\displaystyle \phi }
)"最大化的集合":如果任何更多的命題不管怎樣的被增加到
G
∗
{\displaystyle G^{*}}
,它就會證明
ϕ
{\displaystyle \phi }
。(因為如果有可能增加任何更多的命題,再次根據定義,在構造
G
n
{\displaystyle G_{n}}
期間被遇到的時候它們就應當已經被增加進去了。)
III.如果
G
∗
{\displaystyle G^{*}}
是(關於
ϕ
{\displaystyle \phi }
)的最大化集合,則它是"類真理的"。這意味着它包含命題
ψ
{\displaystyle \psi }
,只在它不包含
¬
ψ
{\displaystyle \neg \psi }
的命題的條件下;如果它包含
ψ
{\displaystyle \psi }
並且包含「如果
ψ
{\displaystyle \psi }
則
χ
{\displaystyle \chi }
」,則它也包含
χ
{\displaystyle \chi }
;以此類推。
IV.如果
G
∗
{\displaystyle G^{*}}
是類真理的,則有「
G
∗
{\displaystyle G^{*}}
-規範」的指派:它使在
G
∗
{\displaystyle G^{*}}
中每個命題為真而在
G
∗
{\displaystyle G^{*}}
之外的所有命題為假,而仍然遵守在這個語言的語義合成的法則。
V.
G
∗
{\displaystyle G^{*}}
-規範的命題將使我們最初的集合
G
{\displaystyle G}
中的命題全部為真,而使
ϕ
{\displaystyle \phi }
為假。
VI.如果有在
G
{\displaystyle G}
其上是真而
ϕ
{\displaystyle \phi }
是假的指派,則
G
{\displaystyle G}
不(語義上)蘊涵
ϕ
{\displaystyle \phi }
。Q.E.D.
下面定義的命題演算通過公理的方式定義了多數邏輯算子的語法並且它只使用一個推理規則。它也叫做標準命題演算。
設
ϕ
{\displaystyle \phi }
、
χ
{\displaystyle \chi }
和
ψ
{\displaystyle \psi }
表示合式公式。(wff自身將不包含任何希臘字母,而只包含大寫羅馬字母、連結算子和圓括號)。公理有
THEN-1:
ϕ
→
(
χ
→
ϕ
)
{\displaystyle \phi \rightarrow (\chi \rightarrow \phi )}
THEN-2:
(
ϕ
→
(
χ
→
ψ
)
)
→
(
(
ϕ
→
χ
)
→
(
ϕ
→
ψ
)
)
{\displaystyle (\phi \rightarrow (\chi \rightarrow \psi ))\rightarrow ((\phi \rightarrow \chi )\rightarrow (\phi \rightarrow \psi ))}
AND-1:
ϕ
∧
χ
→
ϕ
{\displaystyle \phi \land \chi \rightarrow \phi }
AND-2:
ϕ
∧
χ
→
χ
{\displaystyle \phi \land \chi \rightarrow \chi }
AND-3:
ϕ
→
(
χ
→
(
ϕ
∧
χ
)
)
{\displaystyle \phi \rightarrow (\chi \rightarrow (\phi \land \chi ))}
OR-1:
ϕ
→
ϕ
∨
χ
{\displaystyle \phi \rightarrow \phi \lor \chi }
OR-2:
χ
→
ϕ
∨
χ
{\displaystyle \chi \rightarrow \phi \lor \chi }
OR-3:
(
ϕ
→
ψ
)
→
(
(
χ
→
ψ
)
→
(
ϕ
∨
χ
→
ψ
)
)
{\displaystyle (\phi \rightarrow \psi )\rightarrow ((\chi \rightarrow \psi )\rightarrow (\phi \lor \chi \rightarrow \psi ))}
NOT-1:
(
ϕ
→
χ
)
→
(
(
ϕ
→
¬
χ
)
→
¬
ϕ
)
{\displaystyle (\phi \rightarrow \chi )\rightarrow ((\phi \rightarrow \neg \chi )\rightarrow \neg \phi )}
NOT-2:
ϕ
→
(
¬
ϕ
→
χ
)
{\displaystyle \phi \rightarrow (\neg \phi \rightarrow \chi )}
NOT-3:
ϕ
∨
¬
ϕ
{\displaystyle \phi \lor \neg \phi }
公理THEN-2可以被看作是「蘊涵關於蘊涵的分配律」。公理AND-1和AND-2對應於「合取除去」。在AND-1和AND-2之間的關係反映了合取算子的交換律。公理AND-3對應於「合取介入」。公理OR-1和OR-2對應於「析取介入」。在OR-1和OR-2之間的關係反映了析取算子的交換律。公理NOT-1對應於反證法 。公理NOT-2說明了「從矛盾中可以推導出任何東西」。公理NOT-3叫做排中律 (拉丁語 tertium non datur :「排除第三者」)並反映了命題公式的語義求值:公式的真值要麼是真要麼是假。至少在經典邏輯中,沒有第三個真值。直覺邏輯 不接受公理NOT-3。
推理規則是肯定前件 :
ϕ
,
ϕ
→
χ
⊢
χ
{\displaystyle \phi ,\ \phi \rightarrow \chi \vdash \chi }
.
如果還使用雙箭頭的等價算子的話,則要增加如下"自然"推理規則:
IFF-1:
ϕ
↔
χ
⊢
χ
→
ϕ
{\displaystyle \phi \leftrightarrow \chi \vdash \chi \rightarrow \phi }
IFF-2:
ϕ
→
χ
,
χ
→
ϕ
⊢
ϕ
↔
χ
{\displaystyle \phi \rightarrow \chi ,\ \chi \rightarrow \phi \vdash \phi \leftrightarrow \chi }
設一個推導被表示為相繼式 ,各個假設在十字轉門(turnstile)的左側,而結論在十字轉門的右側。則演繹定理 可以被陳述如下:
如果相繼式
ϕ
1
,
ϕ
2
,
.
.
.
,
ϕ
n
,
χ
⊢
ψ
{\displaystyle \phi _{1},\ \phi _{2},\ ...,\ \phi _{n},\ \chi \vdash \psi }
已經被證明了,則也有可能證明相繼式
ϕ
1
,
ϕ
2
,
.
.
.
,
ϕ
n
⊢
χ
→
ψ
{\displaystyle \phi _{1},\ \phi _{2},\ ...,\ \phi _{n}\vdash \chi \rightarrow \psi }
。
這個演繹定理(DT)自身沒有公式化為命題演算:它不是命題演算的定理,而是關於命題演算的一個定理。在這個意義上,它是元定理,相當於關於命題演算可靠性和完備性的定理。
在另一方面,DT對於簡化語法上的證明過程是如此的有用以至於它看作和用做推理規則,同肯定前件一起使用。在這個意義上,DT對應於自然條件證明 推理規則,它是在本條目中提出的第二個例子的命題演算的一部分。
DT的逆定理也是有效的:
如果相繼式
ϕ
1
,
ϕ
2
,
.
.
.
,
ϕ
n
⊢
χ
→
ψ
{\displaystyle \phi _{1},\ \phi _{2},\ ...,\ \phi _{n}\vdash \chi \rightarrow \psi }
已經被證明了,則也有可能證明相繼式
ϕ
1
,
ϕ
2
,
.
.
.
,
ϕ
n
,
χ
⊢
ψ
{\displaystyle \phi _{1},\ \phi _{2},\ ...,\ \phi _{n},\ \chi \vdash \psi }
實際上,DT的逆定理的有效性相對於DT而言是平凡的:
如果
ϕ
1
,
.
.
.
,
ϕ
n
⊢
χ
→
ψ
{\displaystyle \phi _{1},\ ...,\ \phi _{n}\vdash \chi \rightarrow \psi }
則
1:
ϕ
1
,
.
.
.
,
ϕ
n
,
χ
⊢
χ
→
ψ
{\displaystyle \phi _{1},\ ...,\ \phi _{n},\ \chi \vdash \chi \rightarrow \psi }
2:
ϕ
1
,
.
.
.
,
ϕ
n
,
χ
⊢
χ
{\displaystyle \phi _{1},\ ...,\ \phi _{n},\ \chi \vdash \chi }
並且可以演繹自(1)和(2)
3:
ϕ
1
,
.
.
.
,
ϕ
n
,
χ
⊢
ψ
{\displaystyle \phi _{1},\ ...,\ \phi _{n},\ \chi \vdash \psi }
通過肯定前件的方式,Q.E.D.
DT的逆命題有着強有力的蘊涵:它可以用來把公理轉換成推理規則。例如,公理AND-1
⊢
ϕ
∧
χ
→
ϕ
{\displaystyle \vdash \phi \wedge \chi \rightarrow \phi }
可以通過演繹定理的逆定理的方式被轉換成推理規則
ϕ
∧
χ
⊢
ϕ
{\displaystyle \phi \wedge \chi \vdash \phi }
這是合取除去 ,是前面給出的自然演繹命題演算中使用的十個推理規則中的一個。
下面是(語法上)證明的一個例子,只涉及到公理THEN-1和THEN-2:
要證明:
A
→
A
{\displaystyle A\rightarrow A}
(蘊涵的自反性)。
證明:
1.
(
A
→
(
(
B
→
A
)
→
A
)
)
→
(
(
A
→
(
B
→
A
)
)
→
(
A
→
A
)
)
{\displaystyle (A\rightarrow ((B\rightarrow A)\rightarrow A))\rightarrow ((A\rightarrow (B\rightarrow A))\rightarrow (A\rightarrow A))}
公理THEN-2通過
ϕ
=
A
{\displaystyle \phi =A}
,
χ
=
B
→
A
{\displaystyle \chi =B\rightarrow A}
,
ψ
=
A
{\displaystyle \psi =A}
2.
A
→
(
(
B
→
A
)
→
A
)
{\displaystyle A\rightarrow ((B\rightarrow A)\rightarrow A)}
公理THEN-1通過
ϕ
=
A
{\displaystyle \phi =A}
,
χ
=
B
→
A
{\displaystyle \chi =B\rightarrow A}
3.
(
A
→
(
B
→
A
)
)
→
(
A
→
A
)
{\displaystyle (A\rightarrow (B\rightarrow A))\rightarrow (A\rightarrow A)}
得自(1)和(2)通過肯定前件。
4.
A
→
(
B
→
A
)
{\displaystyle A\rightarrow (B\rightarrow A)}
公理THEN-1通過
ϕ
=
A
{\displaystyle \phi =A}
,
χ
=
B
{\displaystyle \chi =B}
5.
A
→
A
{\displaystyle A\rightarrow A}
得自(3)和(4)通過肯定前件。
前面的公理化命題演算是希爾伯特風格演繹系統 的一個例子。在這種命題系統中公理是用邏輯連結詞構建的項,而唯一的推理規則是肯定前件。等式邏輯 在高等學校的抽象代數教學中被作為正式的標準,它是不同於希爾伯特系統的一類不同的演算。它的定理是等式而它的推理規則表達出等號的性質,也就是在容許代換的項上的相等關係。
上述的經典命題演算等價於布爾代數 ,而直覺命題演算 等價於海廷代數 。等價性是通過在兩個方向上轉換各自系統的定理來證明的。經典命題演算或直覺命題演算的定理Φ被分別轉換為布爾代數或Heyting代數的等式
Φ
=
1
{\displaystyle \Phi =1}
。反過來布爾代數或Heyting代數的定理
x
=
y
{\displaystyle x=y}
被分別轉換為定理經典名義演算或直覺命題演算的定理
(
x
→
y
)
∧
(
y
→
x
)
{\displaystyle (x\rightarrow y)\land (y\rightarrow x)}
,它的標準簡寫是
x
≡
y
{\displaystyle x\equiv y}
。在布爾代數的情況下,
x
=
y
{\displaystyle x=y}
還可以被轉換為
(
x
∧
y
)
∨
(
¬
x
∧
¬
y
)
{\displaystyle (x\land y)\lor (\neg x\land \neg y)}
,但在直覺命題演算的情況下中不能這麼轉換。
在布爾代數和Heyting代數中,可以使用不等式
x
≤
y
{\displaystyle x\leq y}
代替等式。等式
x
=
y
{\displaystyle x=y}
可以被表達為一對不等式
x
≤
y
{\displaystyle x\leq y}
和
y
≤
x
{\displaystyle y\leq x}
。反過來不等式
x
≤
y
{\displaystyle x\leq y}
可被表達為等式
x
∧
y
=
x
{\displaystyle x\land y=x}
或
x
∨
y
=
y
{\displaystyle x\lor y=y}
。不等式的重要性在於它對應於希爾伯特系統的演繹或蘊涵符號
⊢
{\displaystyle \vdash }
。蘊涵
ϕ
1
,
ϕ
2
,
…
,
ϕ
n
⊢
ψ
{\displaystyle \phi _{1},\ \phi _{2},\ldots ,\ \phi _{n}\vdash \psi }
被轉換為代數框架下的不等式
ϕ
1
∧
ϕ
2
∧
…
∧
ϕ
n
≤
ψ
{\displaystyle \phi _{1}\ \land \ \phi _{2}\ \land \ \ldots \ \land \ \phi _{n}\ \ \leq \ \ \psi }
反過來代數不等式
x
≤
y
{\displaystyle x\leq y}
被轉換為蘊涵
x
⊢
y
{\displaystyle x\ \vdash \ y}
在實質條件(implication)
x
→
y
{\displaystyle x\rightarrow y}
和不等式或者蘊涵(entailment)
x
≤
y
{\displaystyle x\leq y}
或
x
⊢
y
{\displaystyle x\ \vdash \ y}
之間的區別在於,前者是內在於邏輯的,而後者是外在的。在兩個項之間內在的實質條件是同類的另一個項。在兩個項之間的外在的蘊涵表達了在邏輯語言之外的元真理,並被認為是元語言 的一部分。即使所研究的邏輯是直覺的,蘊涵都通常經典的理解為二值的:要麼左側蘊涵(或小於等於)右側,要麼不蘊涵之。
同代數邏輯之間類似但更加複雜的相互轉換,對於自然演繹系統和相繼式演算 也是可能的。後者的轉換可以被釋義為二值的,但是更有洞察力的釋義是作為集合,它的元素可以被理解為由範疇 的態射組成的抽象證明。在這種釋義下相繼式演算的切規則對應於範疇的複合。
命題演算大概是在所有當前使用的邏輯演算中最簡單的一種。(亞里士多德的「三段論」演算,在現代邏輯中在很大程度上被替代了,它與命題邏輯相比在某些方面更簡單--但在其他方面更加複雜)。它可以按很多方式來擴展。
最直接的方式是開發一個更加複雜的邏輯演算,介入對所用於的句子的更精細的細節敏感的規則。在命題邏輯中的原子句子 被分解成項 、變量 、謂詞 和量詞 的時候,它們就生成了一階邏輯 ,或者叫做一階謂詞邏輯,它保留命題邏輯的所有規則並增加了一些新規則。(例如,從「所有的狗都是動物」我們可以推出「如果Rover是狗,則Rover是動物」)。
通過一階邏輯的工具,有可能公式化一些理論,要麼帶有顯式的公理要麼通過推理規則,而把它們自身當作邏輯演算。算術 是其中最周知的理論;其他的還包括集合論 和分體論 。
模態邏輯 也提供了一種推理的變體,它不能在命題演算中捕獲。例如,從「必然地p」我們可以推出p。從p我們可以推出「可能地p」。
多值邏輯 是允許句子有除了「真」和「假」之外的值的邏輯。(例如,「都不」和「都是」是標準的「額外值」;「連續統邏輯」允許每個句子有任何的在「真」和「假」之間的表示「真實程度」的無限個值)。這些邏輯經常要求與命題邏輯非常不同的運算設備。
Brown, Frank Markham (2003), Boolean Reasoning: The Logic of Boolean Equations, 1st edition, Kluwer Academic Publishers, Norwell, MA. 2nd edition, Dover Publications, Mineola, NY.
Chang, C.C. , and Keisler, H.J. (1973), Model Theory, North-Holland, Amsterdam, Netherlands.
Kohavi, Zvi (1978), Switching and Finite Automata Theory, 1st edition, McGraw–Hill, 1970. 2nd edition, McGraw–Hill, 1978.
Korfhage, Robert R. (1974), Discrete Computational Structures, Academic Press, New York, NY.
Lambek, J. and Scott, P.J. (1986), Introduction to Higher Order Categorical Logic, Cambridge University Press, Cambridge, UK.
Mendelson, Elliot (1964), Introduction to Mathematical Logic, D. Van Nostrand Company.
恆真 (
⊤
{\displaystyle \top }
)
與非 (
↑
{\displaystyle \uparrow }
)
反蘊涵 (
←
{\displaystyle \leftarrow }
)
蘊涵 (
→
{\displaystyle \rightarrow }
)
或 (
∨
{\displaystyle \lor }
)
非 (
¬
{\displaystyle \neg }
)
異或 (
⊕
{\displaystyle \oplus }
)
雙條件 (
↔
{\displaystyle \leftrightarrow }
)
命題
或非 (
↓
{\displaystyle \downarrow }
)
非蘊涵 (
↛
{\displaystyle \nrightarrow }
)
反非蘊涵 (
↚
{\displaystyle \nleftarrow }
)
與 (
∧
{\displaystyle \land }
)
恆假 (
⊥
{\displaystyle \bot }
)