純粹語法推論

 

Photo by Thomas Jensen on Unsplash

假設有套語言只有 a, b, c 三個符號,以及由這三個符號組成的符號串(符號可重覆、符號串不一定有齊三個符號)。這套語言可以做推論,它有一條公理和三條推論規則:
公理:cabcba
a-規則:如果第一個符號是 a ,在結尾加上 cac 並刪走頭三個符號
b-規則:如果第一個符號是 b ,在結尾加上 bab 並刪走頭三個符號
c-規則:如果第一個符號是 c ,在結尾加上 ca 並刪走頭三個符號
問題:透過這公理和推論規則,這套語言總共可以推論出哪些符號串?

讓我先解釋怎樣用公理和規則做推論。所有推論都要由公理開始。首先,公理 cabcba 的第一個符號是 c ,所以要用 c-規則,在結尾加上 ca 使之變成 cabcbaca ,然後刪走頭三個符號,成了 cbaca 。由此,連公理在內有兩個符號串:
  1. cabcba
  2. cbaca
第二個符號串可繼續用 c-規則,如此類推,總共能得到八個符號串。哪八個?

...

假設有套語言只有 ☆ 和 ◎ 兩個符號,裡面只有 ☆ 開頭的符號串合乎文法。這套語言的公理和推論規則如下:
符號:☆, ◎
公理:☆◎◎◎
合規式(合乎文法的式子, wff ):只有以 ☆ 開頭的符號串
☆◎-規則:頭兩個符號是 ☆◎ 的符號串,可推論出結尾為 ☆◎ 的符號串
問題:
  1. ☆◎◎◎ 可推論出 ☆☆◎ ?
  2. ☆◎ 可推論出 ☆◎?
  3. ☆◎◎☆ 可推論出 ☆◎◎☆ ?
  4. ☆◎☆☆☆☆ 可推論出 ◎◎☆☆◎ ?
  5. ☆☆☆☆☆ 可推論出甚麼?
. . .

在第一套語言,你不需知道 a, b, c 是甚麼意思,也不需知道 cabcba 以及其他符號串代表甚麼;你只需知道怎樣用那三條規則從最初的 cabcba 推論出其他符號串。在第二套語言,你不需要知道 ☆ 和 ◎ 代表甚麼,不需知道 ☆◎◎◎ 的意思,你也能夠分辨哪些可以從 ☆◎◎◎ 推論出來、哪些不可以,甚至乎,哪幾個符號串可以推論出哪幾個符號串。

這些推論過程是語法上的證明,與符號的語意完全無關。

. . .

學習形式邏輯通常由古典命題邏輯(classical propositional logic)的翻譯着手,接着是命題邏輯的真值表(truth table),再接着是命題邏輯的自然演繹法(natural deduction)。自然演繹法就是語法上的證明,從某些符號串推論另一些符號串,整個過程只看符號串的形式,與符號串的意思完全無關。舉例來說,最常見的推論規則「肯定前項(modus ponens)」由兩個前提推導一個結論:
1. P→Q
2. P
3. Q (from 1 and 2)
我們通常會為方便理解,替這個推論配上詮釋,例如將「P→Q」理解成「如果下雨,則地濕」或是「如果一件事發生,則(另)一件事也發生」。然而,在自然演繹法,這個推論依賴的不是「P」、「→」、「Q」的意思;它靠的是「P」、「→」、「Q」的形式:只要在證明過程出現「P→Q」和「P」兩個符號串,就可以在之後加上「Q」這個符號串。情況好比剛才使用 a/b/c-規則和 ☆◎-規則,我們其實沒有理會本來的符號串是甚麼意思,我們只是根據本來符號串的形狀而寫上新的符號串。

命題邏輯的真值表和自然演繹法分別代表形式系統的兩個面向:真值表是語意上的詮釋(interpretation),自然演繹法是語法上的證明(proof)。下列兩句, 1 的根據是符號串在語意方面的詮釋, 2 述說的是語法上的證明規則:
  1. 當「P→Q」和「P」都為真,「Q」也必定為真
  2. 當「P→Q」和「P」在證明過程出現,之後的證明可加上「Q」
古典命題邏輯有妥當定理(soundness theorem)和完備定理(completeness theorem),保證 1 和 2 必定互相掛勾。不過,並非每套邏輯系統都已找到這兩個定理的證明。後設邏輯(metalogic)其中一個課題就是學習怎樣證明一套形式系統的妥當定理和完備定理,因此,對形式邏輯有興趣,還是及早將「詮釋」和「證明」區分開來。

...

第一套語言:
  1. cabcba
  2. cbaca
  3. caca
  4. aca
  5. cac
  6. ca
  7. a
  8. c
第二套語言:
  1. 可以
  2. 可以
  3. 不可以
  4. 不可以( ◎◎☆☆◎ 不是以 ☆ 開頭,根本不是合乎文法的符號串。)
  5. 甚麼都推論不出。
...


技術提供:Blogger.