计算机科学家逻辑/谓词逻辑/语义

定义 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$