邏輯白話談（二）. 命題邏輯：語法 - Rex

命題邏輯的運算元有除了「→」以外，還有「¬」、「∧」、「∨」和「↔」。

我承認他們長得有點怪。

先複習一下，「→」的意思是「蘊含（material ... HomeNotificationsListsStoriesWrite邏輯白話談（二）命題邏輯：語法看完上一集，現在你應該對命題邏輯有大略的印象了，不過命題邏輯絕對不只有這樣而已！除了「如果(__)，那麼(__)」的結構（還記得他的符號就是「→」），我們很合理也有其他不是這樣結構的想法，為了要表達其他的句子，命題邏輯裡面也有其他幾種結構。

結合這些結構，我們可以做出很複雜的句子，例如：「如果要考試而且沒有唸書，那麼就會被罵或者被當」。

那除此之外，還有哪些結構？這個問題，就是這篇文章的核心。

在這篇裡，我們會正式來看命題邏輯的語法。

先別擔心這個是什麼東西，請容我娓娓道來。

運算元我先介紹剛剛才提到，命題邏輯剩下來的結構。

首先，正確來講，這些結構在命題邏輯裡面叫作「運算元（operator）」（或是「連結詞（connective）」）。

而既然現在大家都已經知道命題邏輯是作用在符號上的，我們就直接用他們的符號來看了。

命題邏輯的運算元有除了「→」以外，還有「¬」、「∧」、「∨」和「↔」。

我承認他們長得有點怪。

先複習一下，「→」的意思是「蘊含（materialimplication）」。

「若φ則ψ」寫作「φ→ψ」。

「¬」的意思是「非（negation）」。

如果把「唸書」用φ替代，「沒有唸書」就是「¬φ」。

跟「→」不同的是，他前面沒有放東西，只有後面放一個。

只接受一個東西的運算元，叫做「一元（unary）」的運算元。

所以你大概也猜到「→」就是一個「二元（binary）」的運算元了。

「∧」的意思是「而且（conjunction）」，他是二元運算元。

把「唸書」用φ替代，「要考試」用ψ取代，「要考試而且沒有唸書」就是「ψ∧¬φ」。

「∨」的意思是「或者（disjunction）」，他也是二元運算元。

一樣把「唸書」用φ替代，「要考試」用ψ取代，「要考試而且沒有唸書」就是「ψ∨¬φ」。

「↔」唸起來比較潮一點，叫作「等價（materialequivalence）」，也是個二元運算元。

不過跟前幾個比較不一樣的是，像是「→」在中文裡面通常用「如果(__)，那麼(__)」或「若(__)，則(__)」表達，而「↔」通常唸作「(__)若且唯若(__)」（ifandonlyif）。

按照上面的取代方式，「要考試若且唯若要唸書」，就是「ψ↔φ」。

光是看「若且唯若」這四個字，你可能還是搞不太清楚，這個符號的「意義」到底是什麼。

這是因為我目前提到的都只是「語法」；不用擔心，之後會講到他們的「語意」，也就是上一篇稍微提過的「真假值」。

有了這些知識後，我們終於可以回過頭來，用命題邏輯的符號，寫出在一開始我承諾大家的複雜句子「如果要考試而且沒有唸書，那麼就會被罵或者被當」。

一開始，發現他「如果(__)，那麼(__)」的結構，馬上可以切成「要考試而且沒有唸書」→「會被罵或者被當」。

再來先研究前半部的「要考試而且沒有唸書」，發現他有個「而且」的結構，馬上改寫成「要考試」∧「沒有唸書」。

至於看到後半部的「會被罵或者被當」，發現他有個「或者」的結構，就能改寫成「會被罵」∨「被當」。

「要考試」、「沒有唸書」、「會被罵」、「被當」都不能再切分了，因此我們拿符號來代換，在這邊我用英文字母P、Q、R、S。

「如果要考試而且沒有唸書，那麼就會被罵或者被當」完整翻譯的結果就是「P∧Q→R∨S」。

語法在一個語言裡面，符號結合的規則就叫做他的語法（syntax）。

我們學英文的時候，討論的「文法」規則，像是「句子至少要有主詞和動詞」，就是英文的語法之一。

當我們要有條理、有系統的，用符號清楚表達一系列事物時，我們就需要語法。

數學算術也有他的語法，例如傳統上，加法符號「+」是寫在兩個數字之間，像是「1+2」而不是「＋12」或「12+」，這也是算數的語法之一。

我們通常用語法來規定那些合理的句子，所以有了語法，我們就可以知道哪些是「合法（well-fromed）」的句子，例如「+1-」就很明顯不是一個合法的數學式，因為他違反了語法。

所以啦，命題邏輯是一個符號系統，那他自然也就有他的語法。

命題邏輯的語法規則是，一個合法邏輯式（formula）有幾種可能的形式：他是一個基本的原子式（atom）。

原子式通常用符號P、Q、R…代表。

這些原子式是命題邏輯的基本單位，不能再被切分。

所有的原子式都合法。

他是用¬運算元，加上一個合法邏輯式φ做出來的複合式（compound）。

而φ可能是原子式，也可能是複合式。

組合的方式是「¬φ」。

他是用∧運算元，加上兩個合法邏輯式φ和ψ做出來的複合式。

而φ和ψ可能是原子式，也可能是複合式。

組合的方式是「φ∧ψ」。

他是用∨運算元，加上兩個合法邏輯式φ和ψ做出來的複合式。

而φ和ψ可能是原子式，也可能是複合式。

組合的方式是「φ∨ψ」。

他是用→運算元，加上兩個合法邏輯式φ和ψ做出來的複合式。

而φ和ψ可能是原子式，也可能是複合式。

組合的方式是「φ→ψ」。

他是用↔運算元，加上兩個合法邏輯式φ和ψ做出來的複合式。

而φ和ψ可能是原子式，也可能是複合式。

組合的方式是「φ↔ψ」。

而其他的組合方式通通都不合法。

你可能發現後面幾項有點冗長，但把他們清楚定義出來，會讓我們之後要做的事情輕鬆得多。

另外，你可能發現到，複合式的定義是遞歸式（recursive）的定義；如果你是資工或是數學背景，這絕對不陌生，但你大概也不需要讀這篇文章了。

所以要是那個部分你看不太懂，可以參考下一個小節的解釋。

另外，就如同算術裡面，「1+2×3×(4−5)÷6+7」這個式子中的運算元符號有先後順序（precedence）（或是「連結力（bindingpower）」），如果把順序明寫出來，這個式子會是「((1+(((2×3)×(4−5))÷6))+7)」，因為括號最大，再來乘除先於加減，而同樣順序的則是越往左越先。

我們的命題邏輯裡面也有同樣的先後順序，順序最大的是一樣是括號，再來是¬，之後是∧和∨，最後則是→和↔。

因此「P∧Q→R∨S」代表「(P∧Q)→(R∨S)」。

遞歸遞歸（recursion）是一種讓你可以用很簡潔的語言，去描述可能龐大（甚至無限）的東西的方法。

想像這個情況：今天有一排人在排隊買票，而我要描述什麼叫做「一排人」，並且能夠有結構的去做一些運算（例如算數）。

一個很直覺的做法是，我可以用自然數1,2,3,4…來描述這排人。

但很快地，你會發現這樣我們其實沒辦法區分排隊前後的順序，頂多描述這排人的「人數」而已。

再換一個方法，要是用高中學到的「序列（sequence）」呢？例如一排人可以用[小明,小華,小美]表示。

這看起來不錯，但我們能夠寫出他的「語法」嗎？假設我們說一排人的表示是[x,y,z]，立刻遇到的問題就是要是這排人的人數不是三個怎麼辦？畢竟排隊的人數很自然可以是0≤人數