##EasyReadMore##

4.14.2013

述詞邏輯的語法

我們學英文這門語言時,首先會學這個英文有哪些符號(a, b, c, ...),然後學單字(apple, water, ...),再學怎麼組成合文法的句子。

述詞邏輯也是一門語言,所以我們先學這個語言有哪些符號,然後學term,再學well-formed formula(合文法的句式,有人翻成完構式,簡稱wff)長什麼樣。

符號
邏輯符號(所有述詞邏輯的語言都會有這些符號,而且這些符號的詮釋是規定好的,不開放任意詮釋)
  • 變元(variable):$v_1, v_2, ⋯$ (有時會用$x, y, z, u, v$之類的)
  • 連接詞(connective):$¬, ∧, ∨, →, ↔$
    $¬$的其他寫法:$~$
    $∧$的其他寫法:$·$
    $→$的其他寫法:$⊃$
    $↔$的其他寫法:$≣$
  • 量限詞(quantifier):$∃, ∀$(有些人認為量限詞是非邏輯符號才對)
  • 等號:$=$(有些人認為等號是非邏輯符號才對)
  • 括號,或叫分段符號:(, ), [, ], {, } 
非邏輯符號(不是所有述詞邏輯的語言都會有這些符號)
  • 常元(constant):$a, b, c, ⋯, c_1, c_2, ⋯$ (長相不固定,如果有某個述詞邏輯的語言就是要拿「這個是放在,荷花的左邊」當常元,我們也沒辦法)
  • 述詞(predicate):$A, B, C, ⋯, P_1, P_2, ⋯, ∈, <, ⋯$(長相不固定)
  • 函數(function):$f, g, h, ⋯, f_1, f_2, ⋯, +, -, ×, ÷, ⋯$(長相不固定)
在以上這些符號之外的東西,就不是述詞邏輯這門語言的符號了。

Term
  1. 所有變元和常元都是term。
  2. 如果$f$是一個$n$元函數,那麼把$f$的參數位置都用term填滿後得到的東西,也是term。
  3. 以上兩點之外的東西都不是term。
所以,如果語言$L$有$c$這個常元和$g$這個二元函數,那麼下列都是這個語言的term:
  • $g(x, c)$
  • $g(g(x,c), c)$
  • $g(g(x,c), g(y, c))$
  • $g(g(g(x, y), c ), g(c, z))$
下列這些都不是這個語言的term:
  • $g(c, x, c)$($L$裡沒有三元的函數$g$)
  • $g(a, c)$($L$裡沒有符號$a$)
  • $g(c)$($L$裡沒有一元的函數$g$)
  • $cc$
Well-formed formula
  1. 如果$P$是一個$n$元述詞,那麼把$P$的參數位置都用term填滿後得到的東西,就是wff。這種wff有個特定的名字叫atomic formula(原子句式),是最簡單的wff。
  2. 如果$α,β$都是wff,$v$是隨便哪個變元,那麼下列這些也都是wff:$(¬α)$, $(α∧β)$, $(α∨β)$, $(α→β)$, $(α↔β)$, $(∃vα)$, $(∀vα)$。(有時會適度省略一些括號)
  3. 以上兩點以外的東西都不是wff。
所以,如果語言$L$有$c$這個常數,和$g$這個二元函數,和$Q$這個二元述詞,那麼下列都是這個語言的wff:
  1. $Q(c, c)$
  2. $Q(x, y)$
  3. $Q(c, z)$
  4. $Q(x, y)∧Q(x, y)$
  5. $∃zQ(x, y)$
  6. $∃x∀y[∃zQ(x, y)→¬Q(x, y)]$
我們會把裡面沒有出現自由(free)變元的formula稱為sentence。上列六個formula中,只有第一個和第六個是sentence。

下列都不是這個語言的wff:

  • $Q(c, c)= Q(c, c)$(等號是述詞,述詞的參數位置要放term,不是放formula)
  • $Q(Q(x,y), c)$($Q$是述詞,述詞的參數位置要放term,不是放formula)
  • $Q(c)$($L$裡沒有一元的述詞$Q$)
  • $∧Q(x, y)$
  • $Q(x, y)∃z$

述詞邏輯的語意

有了L這個語言的structure,先把這個structure叫$M$好了,我們就可以判斷這個語言中沒有自由變元(free variable)的語句(sentence),在$M$裡是真的還是假的。

以$L'$這個有$a, b, P, Q, f, g$這些非邏輯符號的語言為例,其中$a, b$是常數,$P$是一元述詞,$Q$是二元述詞,$f$是一元函數,$g$是二元函數。我們設計一個$L'$的structure $A$如下:
$U=\{0, 1, 2\}$
$a^A=0$
$b^A=1$
$P^A=\{0, 2\}$
$Q^A=\{(0,1), (1,2), (2,1)\}$
$f^A=\{(0,2), (1,2), (2,0)\}$
——意思是,$f^A(0)=2, f^A(1)=2, f^A(2)=0$
$g^A=\{(0,0,0), (0,1,1),(0,2,2), (1,0,1), (1,1,1), (1,2,1),$ $(2,0,1), (2,1,0), (2,2,1)\}$
—— 意思是,$g^A(0,0)=0, g^A(0,1)=1, g^A(0,2)=2, ⋯$
原子語句(atomic sentence)的真假值
在$A$這個structure裡,$P(a)$是真的還是假的?我們先看$a^A$指到什麼東西,再看看$a^A$指到的東西是不是在$P$的詮釋裡。在裡面,那麼$P(a)$是真的;不在裡面,那麼$P(a)$就是假的。$a^A$指到$0$,而且$0∈P^A$,所以$P(a)$在$A$裡是真的。$P(a)$在$A$裡是真的,通常會記為$A⊨P(a)$或$⊨_AP(a)$。

而$P(b)$因為$1∉P^A$,便是假的。$P(b)$在$A$中為假,則記為$A⊭P(b)$或$⊭_AP(b)$。$Q(a,b)$是真的,記為$A⊨Q(a,b)$,因為$(0,1)∈Q^A$。$A⊭Q(a,a)$,因為$(0,0)∉Q^A$。

至於P(f(a))在$A$裡的真假值,就把$a^A$指到的東西輸進$f^A$裡,看輸出的東西是不是在$P^A$裡。$a^A$指到$0$,$0$輸入$f^A$會輸出$2$(因為$(0,2)∈f^A$,其中$0$是輸入,$2$是輸出),而$2∈P^A$,所以$A⊨P(f(a))$。而$A⊭P(g(b,a))$,因為往$g^A$的第一個參數位置輸入$1$,第二個位置輸入$0$後,輸出的$1$不在$P^A$裡。

有連接詞的語句的真假值
和語句邏輯的計算方式差不多。例如
  • $A⊭P(g(b,a))$,所以$A⊨¬P(g(b,a))$。$A⊨P(a)$,故$A⊭¬P(a)$。
  • $P(a)∧P(g(b,a))$只會在$P(a)$和$P(g(b,a))$都為真的情況下為真,所以$A⊭P(a)∧P(g(b,a))$。
有量限詞(quantifier)的句子的真假值
$∀xP(x)$的意思是,所有domain裡的東西都有$P$這個性質。目前$U=\{0,1,2\}$,也就是說,$∀xP(x)$的意思是$0∈P^A$而且$1∈P^A$而且$2∈P^A$。因為$1∉P^A$,所以$A⊭∀xP(x)$。

$∃xP(x)$的意思是,至少有一個domain裡的東西有$P$這個性質。也就是說,$∃xP(x)$的意思是$0∈P^A$或者$1∈P^A$或者$2∈P^A$。所以$A⊨∃xP(x)$。

$∀x∃yQ(x,y)$的意思是,所有domain裡的東西,都和domain裡至少一個東西有$Q$這個關係。要講得具體一點以幫助理解的話,我們可以先把$Q$視為某個二元關係,例如$x$喜歡$y$(這不代表$Q$這個述詞就是$x$喜歡$y$的意思,$Q$就只是某個述詞符號,$Q^A$僅僅是某個由二元序列構成的集合。就像國小或幼稚園老師教$1+1=2$的時候,把「$1$這個自然數,填進+這個函數的兩個參數位置後,就會輸出$2$」生動地講成,一個蘋果和另一個蘋果放在一起就是兩個蘋果那樣。雖然$1+1=2$和蘋果半毛關係也沒有,但這樣舉例子比較容易理解),那麼$∀x∃yQ(x,y)$的意思便是,每個東西都至少喜歡一個東西。

不過句子太複雜或太長的話,我們可能沒辦法用舉實例的方式,理解句子的意思。不過還有別的辦法。也可以這樣理解$∀x∃yQ(x,y)$:$∀x∃yQ(x,y)$是指所有domain裡的東西都滿足$∃yQ(x,y)$,也就是
$∃yQ(x,y)[^x_0]$而且$∃yQ(x,y)[^x_1]$而且$∃yQ(x,y)[^x_2]$
$∃yQ(x,y)[^x_0]$的意思是$∃yQ(x,y)$中的$x$會指到domain裡的$0$。我們不能直接寫$∃yQ(0,y)$是由於,$0$不是term,所以$∃yQ(0,y)$不是合文法的字串。(私底下想把$∃yQ(x,y)[^x_0]$腦補成$∃yQ(0,y)$是沒問題,但別在正式場合這麼做)

而$∃yQ(x,y)[^x_0]$可以理解成,至少有一個domain裡的東西會滿足$Q(x,y)[^x_0]$,也就是,
$Q(x,y)[^x_0,^y_0]$或者$Q(x,y)[^x_0,^y_1]$或者$Q(x,y)[^x_0,^y_2]$。
所以,$∃yQ(x,y)[^x_0]$而且$∃yQ(x,y)[^x_1]$而且$∃yQ(x,y)[^x_2]$的意思就會是:
【$Q(x,y)[^x_0,^y_0]$或者$Q(x,y)[^x_0,^y_1]$或者$Q(x,y)[^x_0,^y_2]$】而且
【$Q(x,y)[^x_1,^y_0]$或者$Q(x,y)[^x_1,^y_1]$或者$Q(x,y)[^x_1,^y_2]$】而且
【$Q(x,y)[^x_2,^y_0]$或者$Q(x,y)[^x_2,^y_1]$或者$Q(x,y)[^x_2,^y_2]$】。
也就是
【$0$喜歡$0$,或者$0$喜歡$1$,或者$0$喜歡$2$】而且
【$1$喜歡$0$,或者$1$喜歡$1$,或者$1$喜歡$2$】而且
【$2$喜歡$0$,或者$2$喜歡$1$,或者$2$喜歡$2$】
因為domain裡的每個東西的確都喜歡至少一個東西,所以$A⊨∀x∃yQ(x,y)$。

有自由變元的句式(formula)的真假值
有自由變元的句式,基本上沒辦法判斷真假值。試想以下幾個句式:
  • $1=1$
  • $2=1$
  • $x=1$
第一個句式顯然是真的,第二個顯然是假的,但第三個就難辦了,因為我們不知道$x$到底是指哪個數,所以無從判斷$x$是不是等於$1$。

既然問題的根源在於,不知道$x$到底是指什麼,那麼就發派一個東西給$x$去指不就得了。負責這項指派業務的玩意兒,就是一元的assignment function(我不知道這個東西有沒有固定的中文譯名,如果硬要翻的話,就叫指派函數好了)。這個函數和邏輯語言裡那個非邏輯符號的函數的詮釋不一樣。Assignment function的定義域是所有變數的集合(而不是structure的domain,和對非邏輯符號的函數的詮釋不一樣),值域是structure的domain裡的某一個東西。也就是,只要我們輸入某個變數給assignment function,問它這個變數是指啥,它就會輸出一個structure的domain裡的東西,回答我們此變數是指structure的domain裡的這個東西。

問不同的assignment function同一個問題,可能會得到不同的答案。例如$h_1(x)=1$但$h_2(x)=2$之類的。這時在$h_1$這個assignment function的指派之下,$P(x)$在$A$中為假,因為$1∉P^A$,記為$A⊭P(x)[h_1]$,而在$h_2$的的指派之下,$P(x)$在$A$中為真,因為$2∈P^A$,記為$A⊨P(x)[h_2]$。

有時我們會看到一些長相比較奇特的assignment function,例如$h^x_1$。$h^x_1$是指,我們已經有一個assignment function $h$,而$h^x_1$是個這樣的函數:輸入$x$會輸出$1$,輸入$x$以外的變數會輸出和$h$一樣的東西;也就是
$h^x_1(v)=1$    , if $v=x,$($v$是variable的意思)
$h^x_1(v)=h(v)$, if $v≠x$
依此類推,
$h^x_1^y_2(v)=1$    , if $v=x, $
$h^x_1^y_2(v)=2$    , if $v=y, $
$h^x_1^y_2(v)=h(v)$, if $v≠x$ and $v≠y$

重要概念
  1. 某個structure $M$讓某個句子$φ$為真的話,我們就會就說$M$這個structure是$φ$的模型(model)。(不過structure和mode這兩個字常混用就是了)
  2. 某個語言$L$中的句子$φ$是可滿足的(satisfiable),若且唯若,至少有一個$L$的structure,和一個該structure的assignment function(如果$φ$裡有自由變元的話會用上,沒有的話,assignment function就只是來插花的)會讓$φ$為真。
  3. 某個語言$L$中的句子$φ$是邏輯真理(logical truth),記為$⊨φ$,若且唯若,所有$L$的structure,和所有該structure的assignment function都會讓$φ$為真。
    也就是,任選一個$L$的structur和它的隨便那個assignment function,$φ$在裡面都會是真的。
  4. 某個語言$L$中的語句集合$Γ$,蘊含(imply)該語言的某個句子$φ$,記為$Γ⊨φ$,若且唯若,所有會讓$Γ$裡全部句子都為真的$L$的structure,和所有該structure的assignment function,也都會讓$φ$為真。
    也就是,$Γ$裡全部句子都為真的時候,$φ$也會為真。
第3點,是第4點中的$Γ$取為空集合而產生的特例。

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判斷句子是真的還是假的?請見述詞邏輯的語意