形式邏輯/謂詞邏輯/模型

← 非正式約定

↑ 謂詞邏輯

滿足 →

模型

解釋

我們之前說過，對於像${\mathcal {L_{S}}}\,\!$（現在是${\mathcal {L_{P}}}\,\!$）這樣的形式語言的形式語義分為兩部分。

• 指定解釋的規則。一個解釋為形式語法中非邏輯符號分配語義值。就像一個賦值是對命題語言的解釋一樣，一個模型是對謂詞語言的解釋。

• 為語言中較大的表示式分配語義值的規則。命題語言${\mathcal {L_{S}}}\,\!$的所有公式都是句子。這使得能夠直接為較大的公式分配真值。對於謂詞語言${\mathcal {L_{P}}}\,\!$，情況更加複雜。並非${\mathcal {L_{P}}}\,\!$的所有公式都是句子。我們需要定義輔助概念滿足，並在分配真值時使用它。

模型

一個模型是對謂詞語言的解釋。它包括兩個部分：域和解釋函式。在此過程中，我們將逐步指定一個示例模型${\mathfrak {M}}\,\!$.

域

• 一個域是一個非空集合。

直觀地說，域包含當前考慮的所有物件。它包含量詞範圍內的所有物件。$\forall x\,\!$然後解釋為“對於域中的任何物件$x\,\!$…”；$\exists x\,\!$解釋為“存在域中的至少一個物件$x\,\!$，使得…”。我們的謂詞邏輯要求域是非空的，即它至少包含一個物件。

我們示例模型${\mathfrak {M}}\,\!$的域，記為$|{\mathfrak {M}}|\,\!$，是 {0, 1, 2}。

解釋函式

• 解釋函式是將語義值分配給每個運算子字母和謂詞字母的函式。

模型 ${\mathfrak {M}}\,\!$ 的解釋函式是 $I_{\mathfrak {M}}\,\!$。

運算子字母

• 對每個常數符號（即零元運算子字母）分配一個域中的成員。

直觀地，常數符號命名該物件，該物件是域中的一個成員。如果域是上面的 $|{\mathfrak {M}}|\,\!$ 並且 $a_{0}^{0}\,\!$ 被分配到 0，那麼我們認為 $a_{0}^{0}\,\!$ 命名 0，就像名字'蘇格拉底'命名蘇格拉底這個人，或者數字'0'命名數字 0 一樣。將 0 分配給 $a_{0}^{0}\,\!$ 可以表示為

$I_{\mathfrak {M}}(a_{0}^{0})=0\ .\,\!$

• 對每個n元運算子字母，其中n大於零，分配一個n+1元函式，該函式以物件（域中的成員）的有序n元組作為其引數，並以物件（域中的成員）作為其值。該函式必須在域中的所有n元組上定義。

假設域是上面的 $|{\mathfrak {M}}|\,\!$，我們有一個二元運算子字母 $f_{0}^{2}\,\!$。分配給 $f_{0}^{2}\,\!$ 的函式必須在域中的每個有序對上定義。例如，它可以是函式 ${\mathfrak {f}}_{0}^{2}\,\!$，使得

${\mathfrak {f}}_{0}^{2}(0,0)=2,\quad {\mathfrak {f}}_{0}^{2}(0,1)=1,\quad {\mathfrak {f}}_{0}^{2}(0,2)=0,\,\!$

${\mathfrak {f}}_{0}^{2}(1,0)=1,\quad {\mathfrak {f}}_{0}^{2}(1,1)=0,\quad {\mathfrak {f}}_{0}^{2}(1,2)=2,\,\!$

${\mathfrak {f}}_{0}^{2}(2,0)=0,\quad {\mathfrak {f}}_{0}^{2}(2,1)=2,\quad {\mathfrak {f}}_{0}^{2}(2,2)=1\ .\,\!$

對運算子的賦值寫成

$I_{\mathfrak {M}}(f_{0}^{2})={\mathfrak {f}}_{0}^{2}\ .\,\!$

假設 $a_{0}^{0}\,\!$ 如上所述賦值為 0，並且 $b_{0}^{0}\,\!$ 賦值為 1。 然後我們可以直觀地認為非正式書寫形式 $f(a,b)\,\!$ 代表（指代、具有值）1。 這類似於 “蘇格拉底最著名的學生” 代表（指代）柏拉圖，或 “2 + 3” 代表（具有值）5。

謂詞符號

• 每個句子符號（即零元謂詞符號）都被分配一個真值。 對於 $\pi \,\!$ 一個句子符號，要麼

$I_{\mathfrak {M}}(\pi )=\mathrm {True} \,\!$

或

$I_{\mathfrak {M}}(\pi )=\mathrm {False} \ .\,\!$

這與句子符號在命題邏輯中所接受的處理方式相同。 直觀地說，句子是真還是假，取決於句子符號是否被賦值為 “真” 或 “假”。

• 每個n元謂詞符號，其中n大於零，都被分配一個n元關係（一個域成員的有序n元組集）。

直觀地說，謂詞對分配集中每個n元組都是真的。 令域為 $|{\mathfrak {M}}|\,\!$ 如上，並假設賦值

$I_{\mathfrak {M}}(\mathrm {F_{0}^{2}} )\ =\ \{\langle 0,\ 1\rangle ,\ \langle 1,\ 2\rangle ,\ \langle 2,\ 1\rangle \}.$

假設$a_{0}^{0}\,\!$被賦值為0，$b_{0}^{0}\,\!$被賦值為1，$c_{0}^{0}\,\!$被賦值為2。然後直觀地，$\mathrm {F} (a,b)\,\!$，$\mathrm {F} (b,c)\,\!$和$\mathrm {F} (c,b)\,\!$都應該是真的。然而，$\mathrm {F} (a,c)\,\!$等應該為假。這類似於“是否鷹鉤鼻”對蘇格拉底為真，而“是否大於”對$\langle 2,3\rangle$為真。

摘要

這個定義穿插著例子，因此比較分散。這裡是一個更緊湊的總結。模型由兩個部分組成：域和解釋函式。

• 一個域是一個非空集合。

• 一個解釋函式是將語義值賦予每個運算子字母和謂詞字母。此分配按以下步驟進行

• 將每個常量符號（即零元運算子字母）分配給域中的一個成員。
• 將每個n元運算子字母（n大於零）分配給一個n+1元函式，該函式以物件的有序n元組（域的成員）作為其引數，並以物件（域的成員）作為其值。
• 將每個句子字母（即零元謂詞字母）分配給一個真值。
• 將每個n元謂詞字母（n大於零）分配給一個n元關係（一個有序n元組的集合），這些關係都是域中的成員。

例子

一個有限模型

一個例子模型在上面以片段的形式指定。這些片段，在${\mathfrak {M}}\,\!$這個名字下收集在一起，是

$|{\mathfrak {M}}|\ =\ \{0,\ 1,\ 2\}\ .\,\!$

$I_{\mathfrak {M}}(a_{0}^{0})\ =\ 0\ .\,\!$

$I_{\mathfrak {M}}(b_{0}^{0})\ =\ 1\ .\,\!$

$I_{\mathfrak {M}}(c_{0}^{0})\ =\ 2\ .\,\!$

$I_{\mathfrak {M}}(f_{0}^{2})\ =\ {\mathfrak {f}}_{0}^{2}\ {\mbox{such that:}}\quad {\mathfrak {f}}_{0}^{2}(0,0)=2,\ {\mathfrak {f}}_{0}^{2}(0,1)\ =\ 1,\ {\mathfrak {f}}_{0}^{2}(0,2)=0,\,\!$

${\mathfrak {f}}_{0}^{2}(1,0)=1,\ {\mathfrak {f}}_{0}^{2}(1,1)\ =\ 0,\ {\mathfrak {f}}_{0}^{2}(1,2)=2,\ {\mathfrak {f}}_{0}^{2}(2,0)=0,\,\!$

${\mathfrak {f}}_{0}^{2}(2,1)=2,\ {\mbox{and}}\ {\mathfrak {f}}_{0}^{2}(2,2)=1\ .\,\!$

$I_{\mathfrak {M}}(\mathrm {F_{0}^{2}} )\ =\ \{\langle 0,\ 1\rangle ,\ \langle 1,\ 2\rangle ,\ \langle 2,\ 1\rangle \}.$

我們還沒有定義生成較大表達式語義值的規則。但是，我們可以看到一些我們希望該定義能夠實現的簡單結果。已經描述了一些這樣的結果。

$f(a,b)\ {\mbox{resolves to}}\ 1\ \mathrm {in} \ {\mathfrak {M}}\ .\,\!$

$\mathrm {F} (a,b),\ \mathrm {F} (b,c),\ {\mbox{and}}\ \mathrm {F} (c,b)\ {\mbox{are True in}}\ {\mathfrak {M}}\ .\,\!$

$\mathrm {F} (a,a)\ {\mbox{is False in}}\ {\mathfrak {M}}\ .\,\!$

可以新增一些更多期望的結果

$\mathrm {F} (a,f(a,b))\ {\mbox{is True in}}\ {\mathfrak {M}}\ .\,\!$

$\mathrm {F} (f(a,b),a)\ {\mbox{is False in}}\ {\mathfrak {M}}\ .\,\!$

$\mathrm {F} (c,b)\rightarrow \mathrm {F} (a,b)\ {\mbox{is True in}}\ {\mathfrak {M}}\ .\,\!$

$\mathrm {F} (c,b)\rightarrow \mathrm {F} (b,a)\ {\mbox{is False in}}\ {\mathfrak {M}}\ .\,\!$

我們可以暫時假設數字 '0'、'1' 和 '2' 被新增到 ${\mathcal {L_{P}}}\,\!$ 並分別為它們分配數字 0、1 和 2。那麼我們想要

$(1)\quad \mathrm {F} (0,1)\rightarrow \mathrm {F} (1,0)\quad {\mbox{False in}}\ {\mathfrak {M}}\ .\,\!$

$(2)\quad \mathrm {F} (1,2)\land \mathrm {F} (2,1)\quad {\mbox{True in}}\ {\mathfrak {M}}\ .\,\!$

由於 (1)，我們希望得到這樣的結果

$\forall x\,\forall y\,(\mathrm {F} (x,y)\rightarrow \mathrm {F} (y,x))\ {\mbox{is false in }}\ {\mathfrak {M}}\ .\,\!$

由於 (2)，我們希望得到這樣的結果

$\exists x\,\exists y\,(\mathrm {F} (x,y)\land \mathrm {F} (y,x))\ {\mbox{is true in}}\ {\mathfrak {M}}\ .\,\!$

一個無限模型

域 $|{\mathfrak {M}}|\,\!$ 只有有限多個成員；準確來說是 3 個。域可以有無限多個成員。下面是一個具有無限大域的示例模型 ${\mathfrak {M}}_{2}\,\!$ 。

域 $|{\mathfrak {M}}_{2}|\,\!$ 是自然數的集合

$|{\mathfrak {M}}_{2}|=\{0,1,2,...\}\,\!$

對單個常量符號的賦值可以與之前相同

$I_{{\mathfrak {M}}_{2}}(a_{0}^{0})\ =\ 0\ .\,\!$

$I_{{\mathfrak {M}}_{2}}(b_{0}^{0})\ =\ 1\ .\,\!$

$I_{{\mathfrak {M}}_{2}}(c_{0}^{0})\ =\ 2\ .\,\!$

例如，可以將二元運算子字母 $f\,\!$ 賦值為加法函式

$I_{{\mathfrak {M}}_{2}}(f_{0}^{2})\ =\ {\mathfrak {f}}_{0}^{2}\ {\mbox{such that}}\ {\mathfrak {f}}_{0}^{2}(u,v)=u+v\ .\,\!$

例如，可以將二元謂詞字母 $\mathrm {F_{0}^{2}} \,\!$ 賦值為 *小於* 關係

$I_{{\mathfrak {M}}_{2}}(\mathrm {F_{0}^{2}} )\ =\ \{\langle x,\ y\rangle :\ x<y\}\ .\,\!$

擴充套件模型的規範應該產生一些結果。

$f(a,b)\ {\mbox{resolves to}}\ 1\ \mathrm {in} \ {\mathfrak {M}}_{2}\ .\,\!$

$\mathrm {F} (a,b)\ {\mbox{and}}\ \mathrm {F} (b,c)\ {\mbox{are True in}}\ {\mathfrak {M}}_{2}\ .\,\!$

$\mathrm {F} (c,b)\ {\mbox{and}}\ \mathrm {F} (a,a)\ {\mbox{are False in}}\ {\mathfrak {M}}_{2}\ .\,\!$

對於每個 *x*，都存在一個 *y* 使得 *x* < *y*。因此我們希望得到的結果是

$\forall x\,\exists y\,\mathrm {F} (x,y)\ {\mbox{is true in}}\ {\mathfrak {M}}_{2}\ .\,\!$

不存在 *y* 使得 *y* < 0 （記住，我們把自己限制在沒有小於 0 的數字的域中）。因此，並非對於每個 *x* 來說，都存在一個 *y* 使得 *y* < *x*。因此我們希望得到的結果是

$\forall x\,\exists y\,\mathrm {F} (y,x)\ {\mbox{is false in}}\ {\mathfrak {M}}_{2}\ .\,\!$