解釋 (邏輯)

解釋是一種將形式語言中的符號賦予意義的行為。許多使用於數學邏輯理論電腦科學的形式語言都會以純句法的方式定義,且直到給予某些解釋之前,不含有任何意義。一般研究形式語言的解釋的學科稱為形式語義學

最常研究的形式邏輯為命題邏輯謂詞邏輯及其衍生的邏輯,且此類的邏輯都已經有標準的方式來給出解釋。在這些情況下,解釋是一個可以提供目標語言的符號及符號字串外延函數。例如,一個解釋函數可作用在謂詞T(表示「高」)上,並賦予其一個外延{a}(表示「小明」)。須注意的是,上述解釋只是將外延{a}賦予在非邏輯常數T 之上,但沒有宣稱T是否表示「高」,a 是否表示「小明」。同樣地,邏輯解釋也沒有對「和」、「或」及「否定」之類的邏輯聯結詞作宣稱。雖然人們習慣上可能會把這些符號拿來代表特定的事物或概念,但這不是由解釋函數來決定的。

解釋通常(但不總是)會提供一個方法來決定語言中句子真值。若一給定解釋賦予一個句子或理論的真值為真,則這個解釋即稱為此一句子或理論的模型

形式語言

形式語言是由一組固定句子(依上下文不同,也稱為詞或公式)所組成的,這些句子則是由一套固定的字母或符號所組成。用來定義語言的字母清單稱之為字母表。形式語言的重要特性之一在於,其句法不需要指涉解釋即可定義。例如,(PQ) 是一個合式公式,即使不知道真值是真是假。

為了區分形式語言中的符號字串和隨意符號字串之間的不同,前者有時被稱為合式公式。

例子

定義一個形式語言 ,其字母表為α = {  ,   }。一個詞可以說是在  裡,若這個詞開始於 ,且僅由  所組成。

  的一可能解釋在,賦予  十進位位元「1」及賦予  「0」。因此,       的解釋下標記為101。

邏輯常數

在命題邏輯和謂詞邏輯裡,形式語言的字母表可以分為兩個部份:邏輯符號(邏輯常數)及非邏輯符號。邏輯常數此一術語的由來是因為邏輯符號不論在哪個研究主題中都有著相同的意義,而非邏輯符號則會隨著研究領域的不同而有不同的意義。

邏輯常數在每個標準類型的解釋之下,都會給出相同的意義來,因此只有非邏輯符號的意義會改變。邏輯常數包括量化符號∀ 及∃、邏輯聯結詞、括號及其他群組符號,以及(在許多論述中的)等式符號=。

真值函數解釋的一般性質

許多常見的解釋對形式語言中的每個句子都有著一個單一的真值,其值不是真就是假。此類解釋稱之為真值函數的;這些解釋包含了在命題邏輯及一階邏輯中常見的解釋。若一個句子在某一解釋下為真,則稱這個句子滿足於這個解釋。

不存在一個句子可以在同一解釋下同時為真及假,但相同句子在不同解釋下有不同的真值則是可能的。一個句子稱為相容的,若它至少在一個解釋下為真;反之則稱為不相容的。一個句子φ 稱為邏輯有效的,若它滿足於每一個解釋(若φ 滿足於每一個滿足ψ 的解釋,則稱φ 為ψ 的邏輯結論)。

邏輯聯結詞

語言中的部份邏輯符號(不包含量化)為真值函數聯結詞,表現為一真值函數。此函數的參數為真值,亦傳回真值(換句話說,為在句子的真值上的運算)。

真值函數聯結詞讓複合句子可以由較簡單的句子中建構而成。如此,複合句子的真值即可定義為一真值函數,其參數為較簡單句子的真值。聯結詞通常被視為邏輯常數,意指其意義不因公式中其他符號的解釋為何而有所不同。

命題邏輯的定義方法如下:

  • ¬Φ 為真,若且唯若Φ 為假。
  •   為真,若且唯若Φ 為真且Ψ 為真。
  •   為真,若且唯若¬(¬Φ & ¬Ψ) 為真。
  •   為真,若且唯若(¬Φ 為真   Ψ 為真)。
  •   為真,若且唯若  為真且  為真。

因此,在所有句子字母Φ 及Ψ 的特定解釋之下(即賦予每個句子字母真值後),即可以將所有以這些句子字母做為組成部份的公式視為邏輯聯結詞的函數,來決定其真值。下列表格會顯示這個方式是如何運作的。前兩列表示句子字母在四個可能解釋下的真值。其他列則顯示由這些句子字母建構成的公式的真值。公式的真值可以由此遞歸地決定。

邏輯聯結詞
解釋 Φ Ψ ¬Φ (Φ & Ψ)   Ψ)   Ψ)   Ψ)
#1 T T F T T T T
#2 T F F F T F F
#3 F T T F T T F
#4 F F T F F T T

現在來看一個公式為邏輯有效的條件為何就比較簡單了。舉公式F: (Φ   ¬Φ) 為例。若解釋函數令Φ 為真,則¬Φ 因否定聯結詞而為假。因為F 中的一部份Φ 在此解釋下為真,所以F 為真。現在,只存在另外一種可能的解釋,即令Φ 為假,則¬Φ 因否定聯結詞而為真。結果,F 還是為真,因為F 中的一部份~Φ 在此解釋下為真。既然這兩種對F 的解釋是唯一可能存在的邏輯解釋,F 在每個解釋下皆為真,因此稱之為邏輯有效的,或重言式

理論的解釋

理論的解釋是指一個理論與某個論題之間的關係,是一個在理論中的某些基本敘述與和論題相關的某個敘述之間的多對一對應關係。若每個理論中的基本敘述都找得到一個對應,則稱之為完全解釋;若其中有些無法找到對應,則稱之為部份解釋[1]

命題邏輯的解釋

命題邏輯的形式語言是由以命題符號(亦稱為句子符號、句子變數及命題變數)和邏輯聯結詞建構成的公式所組成的。在此形式語言中,唯一的非邏輯符號只有通常會標記為大寫字母的命題符號。為了要使這個形式語言夠精確,一些特定的命題符號必須要先確定。

此類形式語言中的標準解釋為一個將每一命題符號映射至真值的真或假之中其中一個的函數。此函數稱為真值賦值函數。在許多的表述中,這個函數就於字面上的意思會賦予一個真值,但在部份的表述中,這個函數賦予的是另一種真值載體的概念。

對有著n 個不同的命題變數的語言,存在2n 個不同的可能解釋。舉任意一個變數a 為例,存在21=2 個可能解釋:1) a 賦值為「真」,或2) a 賦值為「假」。對一對ab 來說,存在22=4 個可能解釋:1) 兩者皆賦值為「真」,2) 兩者皆賦值為「假」,3) a 賦值為「真」且b 賦值為「假」,或4) a 賦值為「假」且b 賦值為「真」。

給定一組命題符號的真值賦值,對所有由這些變數建構成的公式,即只存在唯一一個解釋的擴展。這個擴展解釋可以利用上面討論過的邏輯聯結詞的真值表,來遞歸地定義。

一階邏輯

不像命題邏輯,每個語言除了選定的命題變數不同之外,其他都一樣,一階邏輯則存在著許多不同的一階語言。每個一階語言都可以由標識來定義。標識是由一組非邏輯符號所組成的,且將每個符號識別為常數符號、函數符號或謂詞符號。在函數符號及謂詞符號裡,也會被指派給一個自然數元數。這類形式語言的字母表即是由邏輯常數、等式關係符號 = 、所有在標識中的符號,以及額外一組無限多的符號(稱為變數)所組成的。

例如,在的語言裡,有常數符號0 和1、兩個二元函數符號+ 和·,且沒有二元關係符號。(此處,等式關係被視成是一個邏輯常數。)

一階邏輯的形式語言

給定一標識σ,其對應的形式語言即為由σ-公式組成的集合。每個σ-公式都是由原子公式以邏輯聯結詞的方式建構而成的;原子公式則是由使用了謂詞符號的項建構而成的。σ-公式的集合的形式定義以另一種方向得出:首先,由常數和函數符號,以及變數集結為項。然後,項可以使用標識中的謂詞符號(關係符號)或表示等式的特殊謂詞符號「=」來結合成原子公式。最後,此語言的公式即可由使用邏輯聯結詞和量化的原子公式集結而成。

一階語言的解釋

為了將意義賦於一階語言的所有句子之中,下列的資訊是必需的。

  • 一個論域[2]D,通常需要是非空的。
  • 對每個常數符號,將D 中的一個元素做為其解釋。
  • 對每個n 元函數符號,將一個由D 映射至Dn 元函數做為其解釋(亦即,一個函數Dn → D)。
  • 對每個n 元謂詞符號,將一個在D 上的n 元關係做為其解釋(亦即,一個Dn 的子集)。

帶有這些資訊的物件即稱為結構,或「模型」。

解釋中指定的資訊可提供足夠的訊息,在每個自由變數都替代為論域中的元素後,以決定任意一個原子公式的真值。然後,任意句子的真值即可使用T-模式遞歸地定義。T-模式使用真值表如上所述來解釋邏輯聯結詞。因此,舉例來說,φ & ψ會被滿足,若且唯若φ 和ψ 都會被滿足。

接下來剩下要如何解釋x φ(x) and x φ(x) 之類形式的公式。論域會形成這些量化的值域, 其概念如下:句子x φ(x) 在一解釋下為真,只在每個φ(x) 中的x 被某個論域中的元素取代而成的置換實例都能被滿足。公式x φ(x) 能被滿足,若至少有一個在論域中的元素d ,能使得φ(d) 被滿足。

嚴格來說,上面所敘之公式的置換實例φ(d) 並不是φ 原本所在這個形式語言中的公式,因為d 是論域中的元素。這個技術上的問題有兩種處理的方法。第一種是擴展至較大的語言,將論域中的每個元素都命名為一個常數符號。第二種是將賦予每個變數到一個論域中的元素的函數加入解釋之中。然後,T-模式即可在和原解釋相比,變數賦值函數有些不同的修訂解釋之上量化,以取代在置換實例上的量化。

一些作者會允許一階邏輯中出現命題變數,因此也必須被解釋。命題變數可以視自身為一原子公式。一個命題變數的解釋即是真值的「真」或「假」的其中之一[3]

因為這裡敘述的一階解釋是定義在集合論裡的,這些解釋並沒有將每個謂詞符號與性質[4](或關係)相關連,而是將其與性質(或關係)的外延相關連。換句話說,這些一階解釋是外延的,而非內涵的。

一階解釋的例子

一階邏輯的解釋可舉例敘述如下:

  • 論域:西洋棋組
  • 分別的常數:白王a、黑后b 及白兵c
  • F(x):x 是棋子
  • G(x):x 是兵
  • H(x):x 為黑
  • I(x): x 為白
  • J(x, y): x 能吃到y

在此解釋下:

  • 下列敘述為真:F(a)、G(c)、H(b)、I(a)、J(b, c),
  • 下列敘述為假:J(a, c)、G(a)。

非空論域的需求

如上所述,一階邏輯通常需要指定一個非空集合做為其論域,原因在於下面的雙條件句需要是邏輯有效的。

 ,

其中,x 不是φ 的自由變數。這個等價在每個具有非空論域的解釋下皆是成立的,但若允許空論域的話就不一定了。例如,雙條件句

 

在任一具有空論域的結構中都無法是邏輯有效的。因此,若允許空結構的存在,一階邏輯的證明論會變得較複雜。而且因為人們研究的理論的預期及有興趣的解釋都有非空論域,允許空論域所能獲得的幾乎可以忽略[5][6]

等式的解釋

等式關係在一階邏輯和其他謂詞邏輯中通常會被特別地對待,主要有兩種方法。

第一種方法是將等式視同其他的二元關係。如此,若等式符號包含在標識之中,則通常需要增加幾個有關等式的公理至公理系統之中(例如,替換公理敘述,若a = bR(a) 成立,則R(b) 也會成立)。這個方法通常用在研究那些不包括等式關係的標識時最為有效,如集合論二階算術的標識,在二階算術中只存在數字的等式關係,但沒有數字集合間的等式關係。

第二種方法是將等式視為一個邏輯常數,必須在所有解釋下解釋為實在的等式關係。如此解釋等式的解釋稱之為正規模型,所以第二種方法和只研究為正規模型的解釋是同樣的意思。此一方法的優勢在於,和等式有關的公理會自動滿足於每一個正規模型,且因此不需要明確述明包含於一階理論之中。第二種方法有時稱為「具等式的一階邏輯」,但有許多作者會不另敘明即直接採用此一方法。

將研究一階邏輯限縮至正規模型中還有一些其他的理由。首先可以知道的是,每個等式可以解釋為一個等價關係,且滿足替換公理的一階解釋,都可縮減至在原論域的子集之上的一個基本等價解釋。因此,研究非正規模型,只需要對正規模型做一點額外的廣義化即可。第二,若考慮非正規模型,則每個相容理論都會有個無限模型;這會影響如勒文海姆–斯科倫定理之類結論的敘述,此類結論通常是在假定只考慮正規模型之下敘述的。

多類一階邏輯

對一階邏輯廣義化的方法之一為考慮具一個以上類型之變數的語言。其想法為,不同類型的變數可用來表示不同類型的物件。每個類型的變數都能被量化;因此多類語言的解釋會對每種變數都會有不同範圍(每個類型都會有無限多個變數)、相分別的論域。函數和關係符號,除了有元數外,它們的每個參數也都會指明需哪個類型。

多類邏輯的一個例子為平面歐氏幾何:具有兩個類型(點和線),有對點的等式關係符號、對線的等式關係符號,及一個以一個點變數與一個線變數為參數的二元重合關係E。這個語言的預期解釋有其範圍為歐氏平面上所有點的點變數、範圍為平面上所有線的線變數,及重合關係E(p,l) 會成立,若且唯若點p 在線l 上。

高階謂詞邏輯

高階謂詞邏輯的形式語言看起來很像一階邏輯的形式語言。不同之處在於,高階謂詞邏輯有許多不同類型的變數。一些變數相對至論域的元素,如一階邏輯一般。其他的變數對應至較高的類型:論域的子集、論域的函數、取論域的子集為參數,傳回從論域映射至論域子集之函數的函數、…等。所有此類類型的變數都可被量化。

一般常見用於高階邏輯的有兩種解釋。完全語義學需要一旦論域被滿足,高階變數即涵蓋所有可能的正確類型(所有論域的子集、所有從論域映射至自身的函數、…等)的元素。因此,指定一個完全解釋,和指定一個一階解釋的方法相同。亨金語義學在實質上為一個多類一階語義學,需要解釋將每個類型的高階變數指定一個分別的論域。因此,亨金語義學的解釋包括一個論域D、一堆D 的子集、一堆從D 映射至D 的函數、…等。上述兩個語義學的關係在高階邏輯中是很重要的課題。

非傳統解釋

上面所述的命題邏輯和謂詞邏輯的解釋並非唯一可能的解釋。尤其是,還存在其他類型的解釋,使用在非傳統邏輯(如直覺主義邏輯)和模態邏輯的研究上。

使用在非傳統邏輯研究上的解釋包括拓撲模型布林值模型關係語義模態邏輯也使用關係語義。

預期解釋

形式語言通常會有預期的特定解釋,這亦是當初研究該形式語言的動機。例如,集合論的一階標識包括一個二元關係∈,預期用來表示集合的元素關係;自然數的一階理論中的論域預期為一自然數的集合。不過,也總是存在其他「非預期解釋」,其論域或非邏輯符號不是由其預期意義所給定。

皮亞諾算術之中,其預期解釋稱為算術的標準模型,由自然數及其一般四則運算所組成。所有同構於上述模型的模型都稱為是標準的;這些模型也都滿足皮亞諾公理。當然,也存在皮亞諾公理的非標準模型,其中包含與自然數不相關連的元素。

解釋的其他概念

除了將形式語言賦予上意義外,「解釋」還有其他不同的意思。

在模型論中,稱結構A 解釋結構B,若存在一個A 的可定義子集D,和D 上的可定義關係與函數,使得B 同構於具論域D 及之上函數與關係的結構。若需要更多的說明,請見解釋 (模型論)

稱理論T 解釋理論S,若存在一個T 的有限定義擴展T′,使得S 包含於T′ 。

另見

參考資料

  1. ^ Curry, Haskell, Foundations of Mathematical Logic p.48
  2. ^ 有時稱為「論述全集」
  3. ^ Mates, Benson, Elementary Logic, Second Edition, New York: Oxford University Press: p. 56, 1972, ISBN 019501491X 
  4. ^ 性質的外延是一堆相區別的個體,所以可將性質理解為一元關係,如「黃色」及「主要」等性質都是一元關係。
  5. ^ Hailperin, Theodore, Quantification theory and empty individual-domains, The Journal of Symbolic Logic (Association for Symbolic Logic), 1953, 18 (3): 197–200, JSTOR 2267402, doi:10.2307/2267402, MR0057820 
  6. ^ Quine, W. V., Quantification and the empty domain, The Journal of Symbolic Logic (Association for Symbolic Logic), 1954, 19 (3): 177–179, JSTOR 2268615, doi:10.2307/2268615, MR0064715 

外部連結