標籤: 暫無標籤

高階邏輯又稱廣義謂詞邏輯。它是一階邏輯(見一階理論及其元邏輯)的推廣。

1 高階邏輯 -高階邏輯

 

2 高階邏輯 -正文

  又稱廣義謂詞邏輯。它是一階邏輯(見一階理論及其元邏輯)的推廣。在一階邏輯中,量詞只能用於個體變元,即只有個體約束變元,並且只有個體變元能作謂詞變元的主目(見謂詞邏輯)。這樣就限制了一階邏輯的語言的表達能力。如果去掉一階邏輯中的上述限制,命題變元和謂詞變元也能作約束變元,即受量詞約束,並且作謂詞變元的主目,以此構造起來的邏輯系統就是高階邏輯。它包括二階邏輯、三階邏輯……以至無窮階邏輯。
  二階邏輯  一階邏輯的一個很自然的推廣是二階邏輯。修改一階邏輯中與量詞有關的形成規則:如果A(α)是合式公式,α是自由變元(個體變元、命題變元或謂詞變元),則凬αA(α)和ヨαA(α)是合式公式;同時,確定適當的公理和變形規則,所得到的系統就是一個二階邏輯(二階謂詞演算)。例如,凬XF(x)∨塡F(x)】是一階邏輯中的合式公式,凬F凬x【F(x)∨塡F(x)】就是一個二階邏輯的合式公式,它表示凬x【F(x)∨塡F(x)】對一切性質F都成立。二階邏輯具有比一階邏輯更強的表達能力。例如,對於數學歸納原則:「如果一公式對數0成立,並且如果它對某一個數成立則對該數的後繼也成立,那末這個公式就對所有的(自然)數成立」,就不能在一階邏輯陳述的算術理論中,用一個公式表達。而在二階邏輯中,由於有了謂詞量詞,就可以用一個公式把該數學歸納原則表示為:
  凬FF(0)∧凬x(F(x)→F(x+1))→凬xF(x)】。
  簡單類型論  進一步推廣二階邏輯,可以構造出三階邏輯、四階邏輯等等,而對於每一自然數 n,可以構造 n階邏輯。三階邏輯是在二階邏輯中引進謂詞的謂詞。在一階和二階邏輯中,謂詞表示個體的性質或個體間的關係,以個體常元(個體的名字)或個體變元作主目。這樣的謂詞稱為一層謂詞;一階和二階邏輯中的謂詞變元稱為一層謂詞變元。有的謂詞不是表示個體的性質或個體間的關係,而是表示某個謂詞的性質或關係。例如,對一個關係 R,我們說R是對稱的,即如果R(x,y),則R(y,x);或者說是傳遞的,即如果R(x,y)且R(y,z),則R(x,z)。而這種對稱性、傳遞性等都是關於關係的性質。用sym(R)、tr(R)表示關係R是對稱的、傳遞的,而symtr都以一層謂詞作主目。主目中包括一層謂詞(謂詞變元)的謂詞(謂詞變元)稱為二層的。一個包括二層謂詞變元,但二層謂詞變元只作為自由變元出現的邏輯系統,就是三階邏輯。在三階邏輯中,不但引進二層謂詞變元,而且還要區別謂詞變元(一層的、二層的)的不同的型。個體變元的型為i;一層謂詞變元F(x)的型為(i),G(x,y)的型為(i,i);二層謂詞sym(R),其主目R的型為(i,i),sym的型為[(i,i)];二層謂詞變元H[G(x,y),i)]的型為[(i,i),i)],等等。對三階邏輯的形成規則,不但要考慮到新增加的二層謂詞變元,還要根據謂詞變元的型的區分,對二階邏輯的形成規則加以修改,並確定適當的公理和變形規則。如果修改三階邏輯的形成規則,而且允許二層謂詞變元也作約束變元,並且確定適當的公理和變形規則,就得到四階邏輯。類似地,還可以引入三層謂詞變元、四層謂詞變元等,構造五階邏輯、六階邏輯,等等。這樣,就可以構造出所有有窮階邏輯。簡單類型論就是ω階邏輯,它是把所有有窮階邏輯總匯在一起的系統。簡單類型論的公理,除了有一階邏輯、二階邏輯等的公理外,還包括另外兩條公理,即外延公理和選擇公理。這兩條公理與公理集合論中的外延公理和選擇公理相當。
  一階邏輯與高階邏輯  一階邏輯具有完全性,即系統中的普遍有效的公式都是系統中可證明的。這是一階邏輯的一個重要特徵。此外,一階邏輯還有兩個重要的定理,即緊緻性定理和勒文海姆-司寇倫定理(見司寇倫定理)。一階邏輯還有一個區別於高階邏輯的重要性質,即一階邏輯是在運算塡,∧,ョ下封閉的唯一能夠滿足緊緻性定理和勒文海姆-司寇倫定理的邏輯。 雖然一階邏輯的表達能力是受限制的,但也已很強了,特別是有了公理集合論以後,用一階邏輯的語言可以陳述當今數學的全部分支。因此,有許多邏輯學家認為,除一階邏輯而外無需研討高階邏輯。然而,用一階邏輯陳述許多相當簡單的定義和證明顯得十分複雜,而通過高階邏輯陳述這些定義和證明則要簡單得多。儘管通過集合論可以把高階邏輯歸納到一階邏輯,但卻造成定義和證明的大大複雜化。高階邏輯的表達力和易推導性比一階邏輯強有力得多。因此,在數理邏輯中高階邏輯仍是有生命力的。
  高階邏輯的一個重大不足是沒有完全性,它的任何公理系統,都不能證明系統中的全部普遍有效公式。

 

3 高階邏輯 -配圖

 

4 高階邏輯 -相關連接

上一篇[粗糙集]    下一篇 [樺樹皮酒壺]

相關評論

同義詞:暫無同義詞