好幾天沒寫了，因為這幾天回到了北京，比較亂。
上海找工作依然沒着落，再從北京看看。待好運！
命題邏輯的主要規則已經說完了。
對于邏輯學來說，一個很重要的部分就是“為什麼這樣”？
要證明一個邏輯系統是正确的，需要證明兩部分：它的可靠性和它的完備性。
今天先來說可靠性。
下面的内容可能要求你對前面的課程很熟悉才比較友善。
前面說了數學歸納法。歸納法是出現使得我們通過假設一些正确的前提就能得到正确的結論。
是以我們現在可以這樣來證明一個結論：
φ1, φ2, . . . , φn |- ψ
當命題φ1, φ2, . . . , φn都是正确的時候，如果可以得出ψ，則ψ就是正确的結論。
那麼你有沒有疑問：會不會出現這種情況，如果在真值表中前提假設都是正确的卻能得出結論是錯誤的？
你可能會想當然的認為：不可能吧。但是why？
你的确說對了：不可能的。怎麼證明呢？
要證明這個結論，我們需要在真值表中把前提都指派為T，看能否出現結論為F的情況。
當然了，你一下子就想到了：需要把宇宙中的全部相繼式都嘗試過才能得出這個結論。
太扯淡了是吧！咋辦呢？
還記得“語意繼承關系嗎”？在數理邏輯之合式公式中我們說過這個概念：如果某個（或某些）合式公式Θ1, Θ2, Θ3, …, Θn每次求值為T的時候都能使公式Ψ為T，則稱它們之間是語意繼承關系或語意蘊含關系，記作
Θ1, Θ2, Θ3, …, Θn |= Ψ
考慮如下例子：
p ∧ q |= p成立嗎？
p ∨ q |= p成立嗎？
¬q, p ∨ q |= p成立嗎？
p |= q ∨¬q成立不？
第一個例子當合取為T時子式肯定為T，是以成立；
第二個就不一定了，因為析取為T，隻要任意一個為T就可以，不能得出某個子式為T；
第三個因為¬q為T是以q為F了，又析取為T是以p為T，成立；
第四個p為T是右邊不影響，因為總是對的（這種公式稱為重言式）。
是以我們的證明變成了另一種方式：如果相繼關系成立，則語意繼承關系成立。即
如果φ1, φ2,..., φn |- ψ 成立，則 φ1, φ2,..., φn |= ψ 成立。
可就是說我們不去考慮公式的真值表了，去看看它的相繼關系成不成立就行了。
上面這個稱為命題邏輯的可靠性。
證明：
由于相繼關系成立，我們有ψ可由φ1, φ2,..., φn導出。
我們的證明需要對證明的長度使用數學歸納法。
所謂證明的長度就是它的行數。
在使用歸納法前我們先提一個斷言M(k)：
如果φ1, φ2,..., φn |- ψ 成立(其中n>0，相繼關系的證明行數為k)，則 φ1, φ2,..., φn |= ψ 成立
在看一個例子（别嫌啰嗦，否則直接證明就暈倒了）：
相繼關系p ∧ q → r |- p → (q → r)的證明如下：
一共有7行。如果去掉最後一行，最外層的盒子的結論就沒有了，我們改寫一下：
我去掉了最外面的框，這樣第二行就變成了前提。
當然了上面的證明過程是針對p ∧ q → r, p |- p → r的，這時候p ∧ q → r, p |= p → r也成立。
而且p ∧ q → r |= p → (q → r)也是成立的。why？
（如果你還記得一般相繼式和定理的關系可能會有些釋然）
我們的歸納假設是這樣的：對于任意k'，k'<k，M(k')成立。我們希望能證明M(k)成立。
歸納基礎：當k=1時，相繼關系是這樣的：ψ |- ψ,這時候語意繼承關系ψ |= ψ成立，因為左邊指派T則右邊也是T（當然了左邊是F右邊也是F，不過我們不關心）；
歸納步驟：假設相繼關系φ1, φ2,..., φn |- ψ的證明過程是k行，并且所有小于k行的證明過程都是成立的。
證明過程的結構是這樣的：
這個描述中有兩點令人疑惑：一是在n個前提寫完之後到結論得出前發生了什麼；二是結論的得出使用了什麼規則。
第一個疑惑數學歸納法幫我買解決了。第二個問題是大大的問題，證明過程基本花費在上面了。
由于不确定最後使用的什麼規則，我們隻能一個一個的來證明了。
假設最後的規則是合取引入（∧i），則ψ的形式是ψ1 ∧ψ2，并且合取引入規則使用在第k行。必然在k之上有兩行是ψ1和ψ2，假設它們的行号是k1和k2。那麼一定有相繼關系φ1, φ2,..., φn |- ψ1和φ1, φ2,..., φn |- ψ1成立，它們的證明行數分别是k1和k2。根據歸納假設，有φ1, φ2,..., φn |= ψ1和φ1, φ2,..., φn |= ψ1成立。是以φ1, φ2,..., φn |= ψ成立（為啥？）；
假設最後的規則是析取消去（∨e），則ψ之前必有形式是ψ1∨ψ2，得出結論的行号是k'(k'<k)。這樣存在一個短證明φ1, φ2,..., φn |- ψ1∨ψ2，根據析取消去規則必有兩個盒子分别證明φ1, φ2,..., φn,ψ1 |- ψ和φ1, φ2,..., φn,ψ2|- ψ。根據歸納假設，φ1, φ2,..., φn |= ψ1∨ψ2和φ1, φ2,..., φn,ψ1 |= ψ和φ1, φ2,..., φn,ψ2|= ψ都成立。這足以保證φ1, φ2,..., φn |= ψ成立（為啥？）；
其他規則類似。
<!--[if !supportLineBreakNewLine]-->
<!--[endif]-->