計算機科學家邏輯/謂詞邏輯/語義

定義 4 (謂詞邏輯語義 - 解釋)

解釋是一個對${\mathcal {I}}=(U_{\mathcal {I}},A_{\mathcal {I}})$，其中

• $U_{\mathcal {I}}$ 是一個任意非空集合，稱為域或宇宙。
• $A_{\mathcal {I}}$ 是一個對映，它將
  • 一個$k$-元謂詞符號，一個$k$-元謂詞，作用於$U_{\mathcal {I}}$，
  • 一個$k$-元函式符號，一個$k$-元函式，作用於$U_{\mathcal {I}}$，以及
  • 一個變數，一個來自域的元素。

令$F$ 為一個公式，且${\mathcal {I}}=(U_{\mathcal {I}},A_{\mathcal {I}})$ 是一個解釋。我們稱${\mathcal {I}}$ 是$F$ 的解釋，如果${\mathcal {A}}_{\mathcal {I}}$ 為每個謂詞和函式符號以及$F$ 中自由出現的每個變數定義。

示例：令 $F=\forall xp(x,f(x))\land q(g(a,z))$，並假設符號的種類如所寫。 接下來我們將給出 $F$ 的兩種解釋。

• ${\mathcal {I}}_{1}=(N_{0},A_{1})$，使得
  • $A_{1}(p)=\{(m,n)\mid m,n\in N_{0}{\text{ and }}m<n\}$
  • $A_{1}(q)=\{n\in N_{0}\mid n{\text{ is prime}}\}$
  • $A_{1}(f)(n)=n+1\;\forall n\in N_{0}$
  • $A_{1}(g)(m,n)=m+n\;\forall n,m\in N_{0}$
  • $A_{1}(a)=2$
  • $A_{1}(z)=3$

  在這種解釋下，公式 $F$ 可以被解讀為“每個自然數都小於它的後繼數，並且 $2$ 和 $3$ 的和是一個質數”。

• ${\mathcal {I}}_{2}=(U_{2},A_{2})$，使得
  • $U_{2}=\{a,f(a),g(a,a),f(g(a,a)),g(f(a),f(a)),\cdots \}$
  • $A_{2}(f)(t)=f(t)$ 對於 $t\in U_{2}$
  • $A_{2}(g)(t_{1},t_{2})=g(t_{1},t_{2})$，如果 $t_{1},t_{2}\in U_{2}$
  • $A_{2}(a)=a$
  • $A_{2}(z)=f(f(a))$
  • $A_{2}(p)=\{p(a,a),p(f(a),f(a)),p(f(f(a)),f(f(a)))\}$
  • $A_{2}(q)=\{g(t_{1},t_{2})\mid t_{1},t_{2}\in U_{2}\}$

對於給定的解釋 ${\mathcal {I}}=(U,A)$ 我們在以下內容中寫 $p^{\mathcal {I}}$ 而不是 $A(p)$；相同縮寫將用於函式符號和變數的賦值。

定義 5 (謂詞邏輯語義 - 公式求值)

設 $F$ 為一個公式，並且 ${\mathcal {I}}$ 是 $F$ 的一個解釋。對於可以用 $F$ 中符號組成的項 $t$，值 ${\mathcal {I}}(t)$ 由下式給出

• ${\mathcal {I}}(x)=x^{\mathcal {I}}$
• ${\mathcal {I}}(f(t_{1},\cdots ,t_{k}))=f^{\mathcal {I}}({\mathcal {I}}(t_{1}),\cdots ,{\mathcal {I}}(t_{k}))$, 如果 $t_{1},\cdots ,t_{k}$ 是項，而 $f$ 是一個 $k$ 元函式符號。（這在 $k=0$ 的情況下同樣適用。）

公式 $F$ 的值 ${\mathcal {I}}(F)$ 由下式給出：

• ${\mathcal {I}}(p(t_{1},\cdots ,t_{k}))={\begin{cases}\;\;\,true&{\text{ if }}({\mathcal {I}}(t_{1}),\cdots ,{\mathcal {I}}(t_{k}))\in p^{\mathcal {I}}\\\;\;\,false&\;otherwise\end{cases}}$

• ${\mathcal {I}}(F\land G))={\begin{cases}\;\;\,true&{\text{ if }}{\mathcal {I}}(F)=true{and}{\mathcal {I}}(G)=true\\\;\;\,false&otherwise\end{cases}}$
• ${\mathcal {I}}((F\lor G))={\begin{cases}\;\;\,true&{\text{ if }}{\mathcal {I}}(F)=true{or}{\mathcal {I}}(G)=true\\\;\;\,false&otherwise\end{cases}}$

• ${\mathcal {I}}(\lnot F)={\begin{cases}\;\;\,true&{\text{ if }}{\mathcal {I}}(F)=false\\\;\;\,false&otherwise\end{cases}}$
• ${\mathcal {I}}(\forall G)={\begin{cases}\;\;\,true&{\text{ if for every }}d\in U\;:\;{\mathcal {I}}_{[x/d]}(G)=true\\\;\;\,false&otherwise\end{cases}}$
• ${\mathcal {I}}(\exists G)={\begin{cases}\;\;\,true&{\text{ if there is a }}d\in U\;:\;{\mathcal {I}}_{[x/d]}(G)=true\\\;\;\,false&otherwise\end{cases}}$

where, $f_{[x/d]}(y)={\begin{cases}\;\;\,f(y)&{\text{ if }}x\neq y\\\;\;\,d&otherwise\end{cases}}$

可滿足性、有效性和 $\models$ 的概念是根據命題邏輯情況定義的 (語義 (命題邏輯)).

注意，謂詞邏輯是命題邏輯的擴充套件：假設只有 $0$-元謂詞符號和一個不包含變數的公式，即在合式公式中不可能有項和量詞。

另一方面，謂詞邏輯可以擴充套件：如果允許對謂詞和函式符號進行量化，我們就會得到二階謂詞邏輯。例如：

$\forall p\exists f\;p(f(x))$

二階公式的另一個例子是來自 歸納法 的歸納原理。

問題

問題 1 (謂詞)

解釋${\mathcal {I}}={\text{ is given }}(U_{\mathcal {I}},A_{\mathcal {I}})$ 如下所示

$U_{\mathcal {I}}=\mathbb {N}$
$p^{\mathcal {I}}={(m,n)\mid m<n}$
$f^{\mathcal {I}}(m,n)=m+n$
$x^{\mathcal {I}}=5;y^{\mathcal {I}}=7$

確定以下術語和公式的值

1. ${\mathcal {I}}(f(f(x,x),y))$
2. ${\mathcal {I}}(\forall x\forall y(p(x,y)\lor p(y,x))$
3. ${\mathcal {I}}(p(x,x)\to p(y,x))$
4. ${\mathcal {I}}(\exists xp(y,x))$

$\Box$

問題 2（謂詞）

解釋${\mathcal {I}}={\text{ is given }}(U_{\mathcal {I}},A_{\mathcal {I}})$ 如下所示

$U_{\mathcal {I}}=\mathbb {R}$

$P^{\mathcal {I}}={z\mid z\geq 0}$
$f^{\mathcal {I}}(z)=z^{2}$
$x^{\mathcal {I}}={\sqrt {2}}$
$E^{\mathcal {I}}={(x,y)\mid x=y}$
$g^{\mathcal {I}}(x,y)=x+y$

$y^{\mathcal {I}}=-1$

確定以下術語和公式的值

$1.{\mathcal {I}}(g(f(x),f(y)))$
$2.{\mathcal {I}}(\forall x\,P(f(x)))$
$3.{\mathcal {I}}(\exists z\forall x\forall y\,E(g(x,y),z))$
$4.{\mathcal {I}}(\forall y(E(f(x),y)\to P(g(x,y))))$

$\Box$

問題 3（謂詞）

給出以下公式

$F=\forall x\forall y\forall z\,R(h(h(x,y),z),h(x,h(y,z)))\ \land \ \exists x\exists y\,\lnot R(h(x,y),h(y,x))$

指示一個結構 ${\mathcal {A}}$，它是 $F$ 的一個模型，以及一個結構 ${\mathcal {B}}$，它不是 $F$ 的模型！
$\Box$