##EasyReadMore##

4.13.2013

述詞邏輯的structure

語句邏輯的句子是用真值表來判斷真假值,述詞邏輯的句子則是用structure來判斷。Structure是由domain和對非邏輯符號的詮釋(interpretation)構成的;至於要詮譯哪些非邏輯符號,就看語言中的非邏輯符號有哪些,詮釋那些就可以了。

以某個有$c_1, c_2, P_1, P_2, f_1, f_2$這些非邏輯符號的語言為例,其中$c_1, c_2$是常數,$P_1$是一元述詞,$P_2$是二元述詞,$f_1$是一元函數,$f_2$是二元函數此處符號的下標和述詞及函數是幾元一模一樣只是偶然),這個語言的structure大致會長成這樣:$M=(U, c_1^M, c_2^M, P_1^M, P_2^M, f_1^M, f_2^M)$。以下一一介紹這些符號的意思。

Structure的名字
$M=(U, c_1^M, c_2^M, P_1^M, P_2^M, f_1^M, f_2^M)$中的$M$和上標的$^M$顯示了這個structure的名字是$M$,意思是model。取名時通常會用大寫英文字母,有時會用特殊字形呈現,以示區隔,例如$M$的花體字是$\fr M$。

Domain
$U$指structure的domain,$U$是universe的意思。有些人不會寫$U$來表示domain,而是寫$D$,或dom($M$),或$|M|$(最後兩個寫法和structure的名字有關。不過$|M|$這個寫法可能會讓人誤以為你想談的是$M$的domain的基數(cardinality),也就是domain裡有幾個東西)。或者structure的名字用特殊字形,然後domain就用一般字形呈現,例如$\fr A$這個structure的domain就用$A$表示

當我們在說structure的大小、structure有多大時,我們指的是它的domain的基數。

Domain是一個集合,而且不能是空集合。我們可以把structure理解成是某個世界,domain則決定了這個世界上有哪些東西。你可以依自己喜好往domain這個集合裡加進任何東西,例如數字、英文字、中文字、人、幾何圖案;加無限個東西進去也行,例如讓domain是所有實數的集合。以下是一些domain這個集合可能的長相:
  • $\{0, 1, 2\}$ 
  • {$0, △, @, a$, Doctor House, 嗨!, 飛天麵條神}
不過為了書寫方便起見,通常只會放數字或英文字。我們暫定$M$的domain是$\{0, 1, 2\}$。

常數的詮釋
$c_1^M$是指,$c_1$這個常數在$M$裡的詮釋。$c_1^M∈U$,也就是,$c_1^M$會等於domain裡的某一個成員。我們可以把常數理解成domain裡某個東西的名字;一個東西可以有很多個常數當作名字,就像一個人可以有很多個綽號類似;但一個常數不能指到一個以上的東西,因為重名的話,我們就不知道那到底是在叫誰了。以下是一些$c_1, c_2$這兩個常數在$M$中可能的詮釋:
  • $c_1^M = 0, c_2^M = 1$
  • $c_1^M = 0, c_2^M = 0$
述詞的詮釋
$P_1^M$是指,$P_1$這個述詞在$M$裡的詮釋。我們對述詞的詮釋是外延(extension)式的。如果$P$是一個$n$元述詞,那麼$P^M⊆U^n$。$P^M$也是一個集合,而和domain不同的是,述詞的詮釋可以是空集合。

$U^n$是$U×⋯×U$乘$n$次的意思。$A×B$是一個由二元序列(tuple)構成的集合,序列中的第一個東西來自$A$,第二個來自$B$,把所有符合此條件的序列蒐集起來形成的集合,就是$A$×$B$。例如,
若$A=\{1,2\}, B=\{3,4\}$,則$A×B=$ $\{(1,3), (1,4), (2,3), (2,4)\}$。
$A×B×C$則是由許多三元序列構成的集合,序列中的第一個東西來自$A$,第二個來自$B$,第三個來自$C$,把所有符合此條件的序列蒐集起來形成的集合,就是$A×B×C$。例如,
若$A=\{1,2\}, B=\{3,4\}$,$C=\{5,6\}$,則$A×B×C=$ $\{(1,3,5), (1,4,5), (2,3,5), (2,4,5), (1,3,6), (1,4,6), (2,3,6), (2,4,6)\}$
在序列裡,東西的順序很重要,$(1,2)$和$(2,1)$是不同的序列,這點和集合很不一樣,$\{1,2\}$和$\{2,1\}$都是同一個集合。(也有人用角括號表示序列,但是我還沒弄清楚怎麼在blogger上打出角括號)

完全沒弄懂前面$P^M$ ⊆ $U^n$是什麼鬼玩意的人別擔心,先來看幾個例子。我們可以把一元述詞$P_1$的詮釋想成,我們想讓domain裡的哪些東西有$P_1$這個性質,我們就把那些東西放到$P_1^M$這個集合裡。$P_1$在$M$裡幾個可能的詮釋:
  • $\{1\}$ 
  • $\{0, 2\}$ 
  • $\{0, 1, 2\}$ 
我們可以把二元述詞$P_2$的詮釋想成,我們想讓domain裡哪兩個東西有$P_2$這個關係,就把那兩個東西放到$P_2^M$這個集合裡。或者更生動一點地說(就像國小或幼稚園老師教$1+1=2$的時候,把「$1$這個自然數,填進+這個函數的兩個參數位置後,就會輸出$2$」生動地講成,一個蘋果和另一個蘋果放在一起就是兩個蘋果那樣。雖然$1+1=2$和蘋果半毛關係也沒有,但這樣舉例子比較容易理解),把$P_2$想成某個二元關係,例如$x$喜歡$y$,我們想讓domain裡的$0$喜歡自己的話,就把$(0,0)$放進$P_2^M$這個集合裡,想讓domain裡的$1$喜歡domain裡的$2$的話,就把$(1,2)$放進去。

$P_2$在$M$裡幾個可能的詮釋:
  • $\{(0,0), (0,1), (0,2)\}$ ($0$喜歡domain裡的所有東西,$1$和$2$則什麼東西都不喜歡)
  • $\{(0,1), (1,0), (2,0)\}$ ($0$和$1$互相喜歡,$2$單戀$0$)
  • ∅(每個東西都不喜歡每個東西)
如果我們遇到的是三元述詞,而且這個述詞的詮釋不是空集合的話,集合裡的東西會長得像$(□,□, □)$,其中空格的部分各填進一個domain裡的東西。總的來說,如果遇到的是$n$元述詞,而且述詞的詮釋不是空集合的話,集合裡的東西會長得像$(□, ...,□)$,共$n$個空格,其中每個格子都填進一個domain裡的東西。

等號這個述詞非常特別,它是邏輯符號(不過有些邏輯學家不這麼認為,但目前先當作等號是邏輯符號),所以一般而言等號的詮釋已經規定好了,不是我們想要讓哪兩個domain裡的東西相等,就可以把那兩個東西組成的序列丟進等號的詮釋裡。等號的詮釋這個集合裡,放的東西一律是,每個domain裡的東西,自己和自己構成的序列,也就是,$\{(x,x)|x∈domain\}$。現在domain$=\{0,1,2\}$,所以$=^M=\{(0,0), (1,1), (2,2)\}$。

函數的詮釋
$f_1^M$是指,$f_1$這個函數在$M$裡的詮釋。如果函數$f$是$n$元的,則它的定義域是$U^n$,值域是$U$。

我們有個把函數轉成集合的辦法:函數是$n$元,我們就弄出$n+1$元的序列,序列的前面$n$格放輸入值,最後一格放輸出值。例如$g(x)=x+1$這個定義在自然數上的一元函數,轉成集合後會長這樣:$\{(0,1), (1,2), (2,3), ...\}$。

函數的定義是,如果輸入值在定義域裡的話,就一定要有輸出值,而且輸出值只能有一個。所以在詮釋函數時也要符合這條規定。

所以,$f_1^M$的定義域是$\{0, 1, 2\}$,因為$f_1$是一元函數。而$f_1^M$會長這樣:$\{(0,□), (1,□), (2,□)\}$,其中每個空格都填進一個domain裡的東西,就能得到一個可能的詮釋。所有空格都填同一個東西也沒關係。

$f_2^M$的定義域是$\{(0,0), (0,1),(0,2), (1,0), (1,1), (1,2), (2,0), (2,1), (2,2)\}$,因為$f_2$是二元函數。而$f_2^M$會長這樣:$\{(0,0,□), (0,1,□),(0,2,□), (1,0,□),$ $(1,1,□), (1,2,□), (2,0,□), (2,1,□), (2,2,□)\}$,其中每個空格都填進一個domain裡的東西。

如何用structure判斷句子是真的還是假的?請見述詞邏輯的語意

0 feedback:

Post a Comment

為了避免辛辛苦苦寫的留言送出後就不見,你可以在送出前把它複製到別處。
如果留言一直沒顯示,可能是被系統當成垃圾留言擋下來。你可以寄信到右上角的信箱叫我處理。