使用者:C44986054/數理邏輯/命題邏輯

本篇是數理邏輯的第一章，下一章是形式理論

首先我們用一個簡單的邏輯系統來介紹一些必要的符號。

在這個簡單的系統裡，關注於敘述之間的推理關係，不去煩惱敘述的構成細節。因為如此所以我們稱這個邏輯系統為命題邏輯(Propositional calculus)。我們用英文大寫字母$\displaystyle A_1, A_2, A_3$來代表一段基本敘述，稱為敘述字母(statement letter)，並可以下標數碼來進一步分辨。(事實上就是承認自然數先於邏輯而存在)。另外我們假設每段敘述都有真假之分，分別以$\top$代表真；和$\bot$代表假。

$\mathcal{A}\asymp\mathcal{B}$代表代表兩者完全相等(也就是符號辨識的意義上相等)。

符號定義(有時稱為形式定義)是以另一組符號去簡記原來的符號。我們以$\mathcal{A}:=\mathcal{B}$代表符號上$\mathcal{A}$是$\mathcal{B}$的簡記。

否定

在邏輯上最簡單的概念就是否定(negation)了，否定一段敘述字母$\displaystyle A$我們用$\neg A$代表。我們用一個表稱為真值表(truth table)描述它在邏輯上的真假狀況。真值表的意思是，"如果$\displaystyle A$是假的，那否定$\displaystyle A$的敘述是真的"。

$\displaystyle A$ $\neg A$ $\top$ $\bot$ $\bot$ $\top$

實質條件

日常對話裡常常會說，"開了電視才會看到新聞"；或是"加熱夠久以後會沸騰"。但事實上沒看電視一樣可以上網看新聞；就算沒有加熱也會沸騰(如常溫下的液態氮)。這說明了有$\displaystyle A$則$\displaystyle B$($A\Rightarrow B$)的直觀邏輯意義，也就是$\displaystyle A$是真的話必會得到$\displaystyle B$為真，但$\displaystyle A$為假的情況下$\displaystyle B$的真假無法確定。這個邏輯運算的觀念稱為實質條件(material conditional )，以真值表表示就是：

$\displaystyle A$ $\displaystyle B$ $A\Rightarrow B$ $\top$ $\top$ $\top$ $\bot$ $\bot$ $\top$ $\top$ $\bot$ $\bot$ $\bot$ $\top$ $\top$

直觀看起來，實質條件的定義，似乎跟日常生活中的"若....則"不一樣。但是假想一個情況，你跟朋友在玩猜數字，你跟朋友打賭"如果你的數字$\displaystyle n$是奇數，則我可以對$\displaystyle x^n+y^n$因式分解"；這顯然是個必贏的賭局，因為依照普通日常的邏輯，你朋友挑偶數的話，因為你有言在先，說如果"挑奇數的話"，所以你會自動勝利。而這個日常邏輯正跟我們的實質條件相符合，儘管如果他取偶數的話會讓$\displaystyle x^n+y^n$無法因式分解，但你的"斷言"在邏輯上是無懈可擊的。

一般日常所說的因果關係，會額外要求如果$\displaystyle B$是真的話，那$\displaystyle A$也要為真(而且會要求時間的先後順序)。但這正對應著我們下面會提到的實質雙條件。而且一般的數學推理，並不是總是能找到如因果關係這樣完美的推理關係。

且和或

我們可以直觀的從真值表定義下面兩個邏輯連接詞：

$\displaystyle A$ $\displaystyle B$ $A\wedge B$ $\top$ $\top$ $\top$ $\bot$ $\bot$ $\bot$ $\top$ $\bot$ $\bot$ $\bot$ $\top$ $\bot$

$\displaystyle A$ $\displaystyle B$ $A\vee B$ $\top$ $\top$ $\top$ $\bot$ $\bot$ $\bot$ $\top$ $\bot$ $\top$ $\bot$ $\top$ $\top$

$A\wedge B$就是所謂的且，也可以形式的定義為不可能$\displaystyle A$是對的情況下推出$\displaystyle B$是錯的，也就是

$A\wedge B:=\neg( A\Rightarrow \neg B)$

另一方面，或($A\vee B$)也可以形式的定義為若$\displaystyle A$是錯的則$\displaystyle B$是對的，也就是

$A\vee B:=\neg A\Rightarrow B$

讀者可以自行畫出真值表，證明這個形式定義跟真值表一致。

實質雙條件

我們很直觀的把$\displaystyle A$跟$\displaystyle B$間的實質雙條件(material biconditional)定義為$\displaystyle A$可以推出$\displaystyle B$且$\displaystyle B$可以推出$\displaystyle A$，也就是

$A \Leftrightarrow B:= (A\Rightarrow B)\wedge(B\Rightarrow A)$

以真值表表示就是

$\displaystyle A$ $\displaystyle B$ $A\Leftrightarrow B$ $\top$ $\top$ $\top$ $\bot$ $\bot$ $\top$ $\top$ $\bot$ $\bot$ $\bot$ $\top$ $\bot$

合式公式

跟一般的語言一樣，數學敘述有一定的文法規則才能清楚表達。這樣在一套數學理論裡符合文法規則的敘述稱為合式公式(well-formed formulas)，簡寫為$\displaystyle wf$。在命題邏輯裡我們用以下的文法規則規定甚麼是一段合式公式：

$\displaystyle (1)$敘述字母是$\displaystyle wf$。

$\displaystyle (2)$如果$\mathcal{A},\mathcal{B}$是$\displaystyle wf$，則$\neg\mathcal{A},\,\mathcal{A}\Rightarrow \mathcal{B}$也都是 $\displaystyle wf$。而$\neg,\Rightarrow$被稱為命題連接詞(propositional connectives)

$\displaystyle (3)wf$只能透過上面兩個規則建構出來。

記住我們第二條文法規則可以這麼簡單，是因為其他的命題連結詞可以用否定跟實質條件組合出來。我們習慣用草寫的大寫英文字母去表達合式公式。

就像一般的語言一樣，符合文法規則讓人聽得懂的話，是有真有假的，合式公式也是有真有假。不管組成的它的敘述字母的真假怎麼取，一段合式公式如果都是真的稱為恆等式(tautology)，反之都是假的合式公式則稱為矛盾(contradiction)。例如對敘述字母$\displaystyle A$

$A\Rightarrow A$

就是恆等式；而

$A\wedge(\neg A)$

就是矛盾。

對於合式公式的恆等式，我們有以下最直觀，但重要的modus ponens律，簡稱MP律：

元定理(MP律)：

若$\mathcal{A}$, $\mathcal{A}\Rightarrow\mathcal{B}$兩個都是恆等式，則$\mathcal{B}$也是恆等式。

這個"元定理"以後抽象化以後，將在命題邏輯的形式理論裡被當成唯一的推理規則。

事實上我們還可以從合式公式去稍稍推廣邏輯推理的觀念；回憶一下我們一開始就假設組成合式公式的敘述字母都是有真有假，它們的真假可以決定合式公式的真假，所以如果每個讓$\mathcal{A}$為真的真假組合，都會讓$\mathcal{B}$是真的話，我們稱$\mathcal{A}$在邏輯上推出$\mathcal{B}$($\mathcal{A}$logically implies $\mathcal{B}$) 。讀者可以自己簡單證明，$\mathcal{A}$在邏輯上推出$\mathcal{B}$等價於$\mathcal{A}\Rightarrow\mathcal{B}$是恆等式。

另外我們說$\mathcal{A}$在邏輯上等價於$\mathcal{B}$($\mathcal{A}$is logically equivalent to $\mathcal{B}$)，如果任何的敘述字母的真假組合，都會讓兩者同為真或是同為假，一樣可以證明$\mathcal{A}$在邏輯上等價於$\mathcal{B}$當且僅僅當$\mathcal{A}\Leftrightarrow\mathcal{B}$是恆等式。

括弧規則

為了讓合式公式的書寫更加便捷，我們做以下的規定：

$\displaystyle (1)$從左方開始判斷

$\displaystyle (2)$括弧內的命題連接詞是最優先施用的。

$\displaystyle (3)$作用於同個敘述字母(或是以括弧包起來的$\displaystyle wf$)的命題連接詞，我們依照$\neg,\,\wedge,\,\vee,\,\Rightarrow,\,\Leftrightarrow$的順序施用。

$\displaystyle ex.$

$\neg A\wedge B$的完整表示法是$(\neg A)\wedge B$。

$A\wedge (D\Rightarrow E)\vee (\neg C)$的完整表示法是$[A\wedge (D\Rightarrow E)]\vee (\neg C)$

$\displaystyle (4)$以上規則都無法判別施用順序的話，以最靠近左端的命題連接詞為先施用。

取代

事實上判別一段合式公式真假值的時候，不用每次都以敘述字母為基礎去判定，我們有以下兩個"元定理"(metatheorem)描述命題邏輯取代的性質

元定理：

如果合式公式$\mathcal{T}$是恆等式，內含的敘述字母是$\displaystyle A_1,A_2,....,A_n$。如果取一組合式公式$\mathcal{A}_1,\mathcal{A}_2,....,\mathcal{A}_n$去依序取代$\displaystyle A_1,A_2,....,A_n$，得到新的合式公式$\mathcal{T}'$，則$\mathcal{T}'$也會是恆等式。

元定理：

合式公式$\mathcal{T}_A$裡內含合式公式$\mathcal{A}$，設合式公式$\mathcal{T}_B$是把$\mathcal{T}_A$裡內含的$\mathcal{A}$都取代成$\mathcal{B}$而生成的。那麼$[(\mathcal{A}\Leftrightarrow\mathcal{B})\Rightarrow(\mathcal{T}_A\Leftrightarrow\mathcal{T}_B)]$是恆等式。

(此元定理可以推論出如果$\mathcal{A},\mathcal{B}$在邏輯上等價，則$\mathcal{T}_A,\mathcal{T}_B$在邏輯上也是等價的。)

以上兩個元定理都可以透過命題連結詞的定義去簡單證明，在此不贅述。

真值函數

在進入形式的邏輯理論之前，我們岔題一下，去討論一個在電腦的設計上很有用的結果。

想抽象一點，我們可以把前面所介紹的命題連接詞當成一種"神奇的黑箱"，只要給它敘述字母的真假值，就會給你邏輯關係是真是假的結果。更抽象的來說，我們可以把命題連接詞當成一種"對應"，每一組敘述字母的真假值都對到唯一的一個真假值，就像每個商品都有自己的價格一樣。事實上這就是數學上函數的概念。

思考一下，我們定義"函數"的時候，是要指定是哪一群東西(一堆商品)被對應到哪一群東西(代表價格的數字們)。這個"一群"的概念在數學上對應著集合的概念；也就是我們要能區分每一個個體(每個商品從外觀都很容易的區分)，而且還要有一個準則去劃分它們是哪個群體的(商品的意思是，在商店裡可以用錢交換而得到的任何物體)。但有些龜毛的數學家發現，有些劃分群體的準則會造成自相矛盾的結果，像著名的羅素悖論。所以我們想要討論"集合"這個觀念的話，我們必須小心翼翼地羅列出劃分群體需要遵守的規則，也就是集合論的公理。但小心翼翼討論這些公理所需要的邏輯規則，我們還沒完全學完。所以在這裡討論"真值函數"，也就是剛剛提到的敘述字母的真假值跟邏輯關係真假的對應關係，要採用一種半直觀的方法討論，等到有一個正式的公理化集合論，就可以輕鬆地把這些直觀的觀念嚴謹化。

回憶一下我們用實質條件跟否定，就可以形式的定義"且"和"或"。那一般來說，一個內含敘述字母$\displaystyle A_1,A_2,....,A_n$的任意合式公式$\mathcal{T}$，它的真值函數$f_{\mathcal{T}}$如果用真值表表示成下面這個樣子：

$\displaystyle A_1$ $\displaystyle A_2$ .... $\displaystyle A_n$ $\mathcal{T}$ $\top$ $\top$ .... $\top$ $f_{\mathcal{T}}(\top,\top,....,\top)$ $\bot$ $\bot$ .... $\bot$ $f_{\mathcal{T}}(\bot,\bot,....,\bot)$ $\cdot$ $\cdot$ .... $\cdot$ $\cdot$ $\cdot$ $\cdot$ .... $\cdot$ $\cdot$ $\cdot$ $\cdot$ .... $\cdot$ $\cdot$ $\cdot$ $\cdot$ .... $\cdot$ $\cdot$

$f_{\mathcal{T}}(\top,\top,....,\top)$的意思只是照函數$f_{\mathcal{T}}$的規則下，"輸入"$\top,\top,....,\top$所得到的對應值。那它能不能被命題連接詞組合出來呢? 如果真值表的第$\displaystyle i$列($i\le 2^n$)的真值函數值為真；為了要湊出$\top$，我們在這列取$\bot$值的敘述字母前面加$\neg$，然後跟其他敘述字母用"$\wedge$"接起來，寫清楚就是

$\displaystyle\mathcal{C}_i:=(\bigwedge_{A_k=\top}A_k)\wedge[\bigwedge_{A_j=\bot}(\neg A_j)]$

我們偷懶的用大寫的"$\wedge$"符號代表連續用"且"連接而成的合式公式，大寫的"$\wedge$"下面說明被連接的$\displaystyle A_k$們需要滿足甚麼條件，而不用麻煩的列舉他們；同樣的偷懶寫法對"$\vee$"也適用。那麼這樣定義的合式公式$\mathcal{C}_i$在第$\displaystyle i$列一定為真；另一方面只要稍稍跟這列的真假值組合不同，就會導致$\mathcal{C}_i$為假。把這些取函數值為真的列所生成的$\mathcal{C}_i$用"或"連接起來，就是我們尋找的$\mathcal{T}$一般表達式。說清楚一點，以$\displaystyle f_i$代表第$\displaystyle i$列的真值函數值，那麼

$\displaystyle\mathcal{T}\Leftrightarrow(\bigvee_{f_i=\top}\mathcal{C}_i)$

是恆等式，也就是兩者在邏輯上等價。因為"或"只要一者為真結果就為真；但另一方面為，函數值為假的某列，它的真假值組合代進任意的$\mathcal{C}_i$都必然為假，而且假用"或"連結起來還是假的，所以這條合式公式的確重現$\mathcal{T}$真值表的狀況；一方面也證明了任意的真值函數可以用$\neg,\wedge,\vee$三者構造出來。

那麼更進一步的，有沒有一個"雙元"的命題連接詞(也就是像"或"一樣吃兩個"輸入值")，可以構造出所有的真值函數呢?這個問題的重要性在於，電腦是基於二進位演算的"黑箱子"；我們可以把$\top$當成$\displaystyle 1$；$\bot$當成$\displaystyle 0$，由此可以把電腦所有的功能拆成真值函數，如果能確定真值函數可以用更少的命題連接詞構成，那用電晶體去組合出邏輯電路的時候，可以依據一定的運算規則減少需要使用的電晶體數量。

如果一個"雙元"命題連接詞可以配出所有的真值函數，第一個要配的就是$\neg$；唯一配的方法就是重複輸入同一個敘述字母的真假值來構造。假設這個命題連接詞用符號"$\star$"代表，那

$\displaystyle A$ $\displaystyle B$ $A\star B$ $\top$ $\top$ $\bot$ $\bot$ $\bot$ $\top$ $\top$ $\bot$ $\displaystyle ?$ $\bot$ $\top$ $\displaystyle ?$

要完全決定這個命題連接詞，只剩下真值組合不相等的兩個部分；如果把兩個$\displaystyle ?$取為相異值，可以發現不是$(A\star B)$邏輯上等價於$(\neg A)$；不然就是$(A\star B)$邏輯上等價於$(\neg B)$。但依照我們上面的討論，$\neg$是不足以構築出所有真值函數的；故兩個$\displaystyle ?$只能取相同值。

如果取的是$\top$的話，我們稱為NAND或是謝費爾豎線(Sheffer stroke)，以"$\mid$"代表

$A$ $B$ $A\mid B$ $\top$ $\top$ $\bot$ $\bot$ $\bot$ $\top$ $\top$ $\bot$ $\top$ $\bot$ $\top$ $\top$

事實上它就是

$\neg(A\wedge B)$

這就是它的名子"NAND"的來源。然後注意到，$(A\vee B)$邏輯上等價於$[\neg(\neg A\wedge\neg B)]$("或"就是不可能全部都是假的)，所以NAND的確可以構造出所有的真值函數。

如果取的是$\bot$，我們稱它為NOR，以$\downarrow$代表它

$A$ $B$ $A\downarrow B$ $\top$ $\top$ $\bot$ $\bot$ $\bot$ $\top$ $\top$ $\bot$ $\bot$ $\bot$ $\top$ $\bot$

事實上它就是

$\neg(A\vee B)$

然後讀者自己畫表驗證，$A\vee B$邏輯上等價於$[(\neg A)\downarrow(\neg B)]$，然後因為剛剛說過"且"可以用"或"跟否定拼湊出來，所以NOR也可以生成所有真值函數。

我們在這裡提供一個網站，可以根據你寫出的合式公式計算真值表

https://www.erpelstolz.at/gateway/formular-uk-zentral.html

use MathJax