述詞邏輯的語意

有了L這個語言的structure，先把這個structure叫$\mathit{M}$好了，我們就可以判斷這個語言中沒有自由變元（free variable）的語句（sentence），在$\mathit{M}$裡是真的還是假的。

以$\mathit{L}\prime$這個有$\mathit{a},\mathit{b},\mathit{P},\mathit{Q},\mathit{f},\mathit{g}$這些非邏輯符號的語言為例，其中$\mathit{a},\mathit{b}$是常數，$\mathit{P}$是一元述詞，$\mathit{Q}$是二元述詞，$\mathit{f}$是一元函數，$\mathit{g}$是二元函數。我們設計一個$\mathit{L}\prime$的structure $\mathit{A}$如下：

$\mathit{U}=\left\{0,1,2\right\}$
${\mathit{a}}^{\mathit{A}}=0$
${\mathit{b}}^{\mathit{A}}=1$
${\mathit{P}}^{\mathit{A}}=\left\{0,2\right\}$
${\mathit{Q}}^{\mathit{A}}=\left\{\left(0,1\right),\left(1,2\right),\left(2,1\right)\right\}$
${\mathit{f}}^{\mathit{A}}=\left\{\left(0,2\right),\left(1,2\right),\left(2,0\right)\right\}$
——意思是，${\mathit{f}}^{\mathit{A}}\left(0\right)=2,{\mathit{f}}^{\mathit{A}}\left(1\right)=2,{\mathit{f}}^{\mathit{A}}\left(2\right)=0$
${\mathit{g}}^{\mathit{A}}=\{\left(0,0,0\right),\left(0,1,1\right),\left(0,2,2\right),\left(1,0,1\right),\left(1,1,1\right),\left(1,2,1\right),$ $\left(2,0,1\right),\left(2,1,0\right),\left(2,2,1\right)\}$
—— 意思是，${\mathit{g}}^{\mathit{A}}\left(0,0\right)=0,{\mathit{g}}^{\mathit{A}}\left(0,1\right)=1,{\mathit{g}}^{\mathit{A}}\left(0,2\right)=2,\cdots$

原子語句（atomic sentence）的真假值

在$\mathit{A}$這個structure裡，$\mathit{P}\left(\mathit{a}\right)$是真的還是假的？我們先看${\mathit{a}}^{\mathit{A}}$指到什麼東西，再看看${\mathit{a}}^{\mathit{A}}$指到的東西是不是在$\mathit{P}$的詮釋裡。在裡面，那麼$\mathit{P}\left(\mathit{a}\right)$是真的；不在裡面，那麼$\mathit{P}\left(\mathit{a}\right)$就是假的。${\mathit{a}}^{\mathit{A}}$指到$0$，而且$0\in {\mathit{P}}^{\mathit{A}}$，所以$\mathit{P}\left(\mathit{a}\right)$在$\mathit{A}$裡是真的。$\mathit{P}\left(\mathit{a}\right)$在$\mathit{A}$裡是真的，通常會記為$\mathit{A}\models \mathit{P}\left(\mathit{a}\right)$或${\models }_{\mathit{A}}\mathit{P}\left(\mathit{a}\right)$。

而$\mathit{P}\left(\mathit{b}\right)$因為$1\notin {\mathit{P}}^{\mathit{A}}$，便是假的。$\mathit{P}\left(\mathit{b}\right)$在$\mathit{A}$中為假，則記為$\mathit{A}⊭\mathit{P}\left(\mathit{b}\right)$或${⊭}_{\mathit{A}}\mathit{P}\left(\mathit{b}\right)$。$\mathit{Q}\left(\mathit{a},\mathit{b}\right)$是真的，記為$\mathit{A}\models \mathit{Q}\left(\mathit{a},\mathit{b}\right)$，因為$\left(0,1\right)\in {\mathit{Q}}^{\mathit{A}}$。$\mathit{A}⊭\mathit{Q}\left(\mathit{a},\mathit{a}\right)$，因為$\left(0,0\right)\notin {\mathit{Q}}^{\mathit{A}}$。

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

有連接詞的語句的真假值

和語句邏輯的計算方式差不多。例如

• $\mathit{A}⊭\mathit{P}\left(\mathit{g}\left(\mathit{b},\mathit{a}\right)\right)$，所以$\mathit{A}\models \neg \mathit{P}\left(\mathit{g}\left(\mathit{b},\mathit{a}\right)\right)$。$\mathit{A}\models \mathit{P}\left(\mathit{a}\right)$，故$\mathit{A}⊭\neg \mathit{P}\left(\mathit{a}\right)$。
• $\mathit{P}\left(\mathit{a}\right)\wedge \mathit{P}\left(\mathit{g}\left(\mathit{b},\mathit{a}\right)\right)$只會在$\mathit{P}\left(\mathit{a}\right)$和$\mathit{P}\left(\mathit{g}\left(\mathit{b},\mathit{a}\right)\right)$都為真的情況下為真，所以$\mathit{A}⊭\mathit{P}\left(\mathit{a}\right)\wedge \mathit{P}\left(\mathit{g}\left(\mathit{b},\mathit{a}\right)\right)$。

有量限詞（quantifier）的句子的真假值

$\forall \mathit{x}\mathit{P}\left(\mathit{x}\right)$的意思是，所有domain裡的東西都有$\mathit{P}$這個性質。目前$\mathit{U}=\left\{0,1,2\right\}$，也就是說，$\forall \mathit{x}\mathit{P}\left(\mathit{x}\right)$的意思是$0\in {\mathit{P}}^{\mathit{A}}$而且$1\in {\mathit{P}}^{\mathit{A}}$而且$2\in {\mathit{P}}^{\mathit{A}}$。因為$1\notin {\mathit{P}}^{\mathit{A}}$，所以$\mathit{A}⊭\forall \mathit{x}\mathit{P}\left(\mathit{x}\right)$。

$\exists \mathit{x}\mathit{P}\left(\mathit{x}\right)$的意思是，至少有一個domain裡的東西有$\mathit{P}$這個性質。也就是說，$\exists \mathit{x}\mathit{P}\left(\mathit{x}\right)$的意思是$0\in {\mathit{P}}^{\mathit{A}}$或者$1\in {\mathit{P}}^{\mathit{A}}$或者$2\in {\mathit{P}}^{\mathit{A}}$。所以$\mathit{A}\models \exists \mathit{x}\mathit{P}\left(\mathit{x}\right)$。

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

不過句子太複雜或太長的話，我們可能沒辦法用舉實例的方式，理解句子的意思。不過還有別的辦法。也可以這樣理解$\forall \mathit{x}\exists \mathit{y}\mathit{Q}\left(\mathit{x},\mathit{y}\right)$：$\forall \mathit{x}\exists \mathit{y}\mathit{Q}\left(\mathit{x},\mathit{y}\right)$是指所有domain裡的東西都滿足$\exists \mathit{y}\mathit{Q}\left(\mathit{x},\mathit{y}\right)$，也就是

$\exists \mathit{y}\mathit{Q}\left(\mathit{x},\mathit{y}\right){[}_0^{\mathit{x}}]$而且$\exists \mathit{y}\mathit{Q}\left(\mathit{x},\mathit{y}\right){[}_1^{\mathit{x}}]$而且$\exists \mathit{y}\mathit{Q}\left(\mathit{x},\mathit{y}\right){[}_2^{\mathit{x}}]$

$\exists \mathit{y}\mathit{Q}\left(\mathit{x},\mathit{y}\right){[}_0^{\mathit{x}}]$的意思是$\exists \mathit{y}\mathit{Q}\left(\mathit{x},\mathit{y}\right)$中的$\mathit{x}$會指到domain裡的$0$。我們不能直接寫$\exists \mathit{y}\mathit{Q}\left(0,\mathit{y}\right)$是由於，$0$不是term，所以$\exists \mathit{y}\mathit{Q}\left(0,\mathit{y}\right)$不是合文法的字串。（私底下想把$\exists \mathit{y}\mathit{Q}\left(\mathit{x},\mathit{y}\right){[}_0^{\mathit{x}}]$腦補成$\exists \mathit{y}\mathit{Q}\left(0,\mathit{y}\right)$是沒問題，但別在正式場合這麼做）

而$\exists \mathit{y}\mathit{Q}\left(\mathit{x},\mathit{y}\right){[}_0^{\mathit{x}}]$可以理解成，至少有一個domain裡的東西會滿足$\mathit{Q}\left(\mathit{x},\mathit{y}\right){[}_0^{\mathit{x}}]$，也就是，

$\mathit{Q}\left(\mathit{x},\mathit{y}\right){[}_0^{\mathit{x}}{,}_0^{\mathit{y}}]$或者$\mathit{Q}\left(\mathit{x},\mathit{y}\right){[}_0^{\mathit{x}}{,}_1^{\mathit{y}}]$或者$\mathit{Q}\left(\mathit{x},\mathit{y}\right){[}_0^{\mathit{x}}{,}_2^{\mathit{y}}]$。

所以，$\exists \mathit{y}\mathit{Q}\left(\mathit{x},\mathit{y}\right){[}_0^{\mathit{x}}]$而且$\exists \mathit{y}\mathit{Q}\left(\mathit{x},\mathit{y}\right){[}_1^{\mathit{x}}]$而且$\exists \mathit{y}\mathit{Q}\left(\mathit{x},\mathit{y}\right){[}_2^{\mathit{x}}]$的意思就會是：

【$\mathit{Q}\left(\mathit{x},\mathit{y}\right){[}_0^{\mathit{x}}{,}_0^{\mathit{y}}]$或者$\mathit{Q}\left(\mathit{x},\mathit{y}\right){[}_0^{\mathit{x}}{,}_1^{\mathit{y}}]$或者$\mathit{Q}\left(\mathit{x},\mathit{y}\right){[}_0^{\mathit{x}}{,}_2^{\mathit{y}}]$】而且
【$\mathit{Q}\left(\mathit{x},\mathit{y}\right){[}_1^{\mathit{x}}{,}_0^{\mathit{y}}]$或者$\mathit{Q}\left(\mathit{x},\mathit{y}\right){[}_1^{\mathit{x}}{,}_1^{\mathit{y}}]$或者$\mathit{Q}\left(\mathit{x},\mathit{y}\right){[}_1^{\mathit{x}}{,}_2^{\mathit{y}}]$】而且
【$\mathit{Q}\left(\mathit{x},\mathit{y}\right){[}_2^{\mathit{x}}{,}_0^{\mathit{y}}]$或者$\mathit{Q}\left(\mathit{x},\mathit{y}\right){[}_2^{\mathit{x}}{,}_1^{\mathit{y}}]$或者$\mathit{Q}\left(\mathit{x},\mathit{y}\right){[}_2^{\mathit{x}}{,}_2^{\mathit{y}}]$】。

也就是

【$0$喜歡$0$，或者$0$喜歡$1$，或者$0$喜歡$2$】而且
【$1$喜歡$0$，或者$1$喜歡$1$，或者$1$喜歡$2$】而且
【$2$喜歡$0$，或者$2$喜歡$1$，或者$2$喜歡$2$】

因為domain裡的每個東西的確都喜歡至少一個東西，所以$\mathit{A}\models \forall \mathit{x}\exists \mathit{y}\mathit{Q}\left(\mathit{x},\mathit{y}\right)$。

有自由變元的句式（formula）的真假值

有自由變元的句式，基本上沒辦法判斷真假值。試想以下幾個句式：

• $1=1$
• $2=1$
• $\mathit{x}=1$

第一個句式顯然是真的，第二個顯然是假的，但第三個就難辦了，因為我們不知道$\mathit{x}$到底是指哪個數，所以無從判斷$\mathit{x}$是不是等於$1$。

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

問不同的assignment function同一個問題，可能會得到不同的答案。例如${\mathit{h}}_1\left(\mathit{x}\right)=1$但${\mathit{h}}_2\left(\mathit{x}\right)=2$之類的。這時在${\mathit{h}}_1$這個assignment function的指派之下，$\mathit{P}\left(\mathit{x}\right)$在$\mathit{A}$中為假，因為$1\notin {\mathit{P}}^{\mathit{A}}$，記為$\mathit{A}⊭\mathit{P}\left(\mathit{x}\right)\left[{\mathit{h}}_1\right]$，而在${\mathit{h}}_2$的的指派之下，$\mathit{P}\left(\mathit{x}\right)$在$\mathit{A}$中為真，因為$2\in {\mathit{P}}^{\mathit{A}}$，記為$\mathit{A}\models \mathit{P}\left(\mathit{x}\right)\left[{\mathit{h}}_2\right]$。

有時我們會看到一些長相比較奇特的assignment function，例如${\mathit{h}}_1^{\mathit{x}}$。${\mathit{h}}_1^{\mathit{x}}$是指，我們已經有一個assignment function $\mathit{h}$，而${\mathit{h}}_1^{\mathit{x}}$是個這樣的函數：輸入$\mathit{x}$會輸出$1$，輸入$\mathit{x}$以外的變數會輸出和$\mathit{h}$一樣的東西；也就是

${\mathit{h}}_1^{\mathit{x}}\left(\mathit{v}\right)=1$    , if $\mathit{v}=\mathit{x},$（$\mathit{v}$是variable的意思）
${\mathit{h}}_1^{\mathit{x}}\left(\mathit{v}\right)=\mathit{h}\left(\mathit{v}\right)$, if $\mathit{v}\ne \mathit{x}$

依此類推，

${{\mathit{h}}_1^{\mathit{x}}}_2^{\mathit{y}}\left(\mathit{v}\right)=1$    , if $\mathit{v}=\mathit{x},$
${{\mathit{h}}_1^{\mathit{x}}}_2^{\mathit{y}}\left(\mathit{v}\right)=2$    , if $\mathit{v}=\mathit{y},$
${{\mathit{h}}_1^{\mathit{x}}}_2^{\mathit{y}}\left(\mathit{v}\right)=\mathit{h}\left(\mathit{v}\right)$, if $\mathit{v}\ne \mathit{x}$ and $\mathit{v}\ne \mathit{y}$

重要概念

1. 某個structure $\mathit{M}$讓某個句子$\mathit{\phi }$為真的話，我們就會就說$\mathit{M}$這個structure是$\mathit{\phi }$的模型（model）。（不過structure和mode這兩個字常混用就是了）
2. 某個語言$\mathit{L}$中的句子$\mathit{\phi }$是可滿足的（satisfiable），若且唯若，至少有一個$\mathit{L}$的structure，和一個該structure的assignment function（如果$\mathit{\phi }$裡有自由變元的話會用上，沒有的話，assignment function就只是來插花的）會讓$\mathit{\phi }$為真。
3. 某個語言$\mathit{L}$中的句子$\mathit{\phi }$是邏輯真理（logical truth），記為$\models \mathit{\phi }$，若且唯若，所有$\mathit{L}$的structure，和所有該structure的assignment function都會讓$\mathit{\phi }$為真。
   也就是，任選一個$\mathit{L}$的structur和它的隨便那個assignment function，$\mathit{\phi }$在裡面都會是真的。
4. 某個語言$\mathit{L}$中的語句集合$\mathit{\Gamma }$，蘊含（imply）該語言的某個句子$\mathit{\phi }$，記為$\mathit{\Gamma }\models \mathit{\phi }$，若且唯若，所有會讓$\mathit{\Gamma }$裡全部句子都為真的$\mathit{L}$的structure，和所有該structure的assignment function，也都會讓$\mathit{\phi }$為真。
   也就是，$\mathit{\Gamma }$裡全部句子都為真的時候，$\mathit{\phi }$也會為真。

第3點，是第4點中的$\mathit{\Gamma }$取為空集合而產生的特例。