Structurae & Interpretationes 结构与解释
〔定义 2.1〕：
设 $S$ 为符号集，$S$–结构（$S$-structure）是具有下述性质的二元组 $\mathfrak A=(A,\,\mathfrak a)$：
(α) $A$ 是非空集合，称为 $\mathfrak A$ 的论域（domain）或全集（universe）；
(β) $\mathfrak a$ 是定义于 $S$ 的映射，满足以下条件：
(1) 对任一 $n$ 元关系符号 $R\in S$，$\mathfrak a(R)$ 为 $A$ 上的 $n$ 元关系；
(2) 对任一 $n$ 元函数符号 $f\in S$，$\mathfrak a(f)$ 为 $A$ 上的 $n$ 元函数；
(3) 对任一常元 $c\in S$，$\mathfrak a(c)$ 为 $A$ 的元素．
后文将 $\mathfrak a(R),\,\mathfrak a(f),\,\mathfrak a(c)$ 分别记为 $R^\mathfrak A,\,f^\mathfrak A,\,c^\mathfrak A$ 或 $R^A,\,f^A,\,c^A$．结构 $\mathfrak A,\,\mathfrak B,\,\cdots$ 的论域相应地记作 $A,\,B,\,\cdots$．结构 $\mathfrak A=(A,\,\mathfrak a)$ 中的映射 $\mathfrak a$ 将会写成符号集中对应符号的值列表，如 $\{R,\,f,\,c\}$–结构记作 $\mathfrak A=(A,\,R^\mathfrak A,\,f^\mathfrak A,\,c^\mathfrak A)$．
〔定义 2.2〕：
设 $\mathfrak A$ 为 $S$–结构，映射 $\beta:\{v_n\mid n\in\mathbb N\}\to A$ 将变元映射为 $A$ 中的元素，称为 $\mathfrak A$ 的一个赋值（assignment）．
$S$–解释（interpretation）$\mathfrak I$ 是指含有一个 $S$–结构 $\mathfrak A$ 与其中的一个赋值 $\beta$ 的二元组 $(\mathfrak A,\,\beta)$ ．
若 $\beta$ 是 $\mathfrak A$ 的一个赋值，$a\in A$ 且 $x$ 为变元，则 $\beta\tfrac ax$ 表示将 $x$ 映射为 $a$，而将与 $x$ 相异的元素如同 $\beta$ 一样映射的赋值，即
对于 $\mathfrak I=(\mathfrak A,\,\beta)$，记 $\mathfrak I\tfrac ax=(\mathfrak A\tfrac ax,\,\beta)$．
Relatio Satisfactionis Consequentiaeque 满足关系与推论关系
〔定义 2.3〕：
定义 $\mathfrak I=(\mathfrak A,\,\beta)$ 为 $S$–解释，函数 $\mathfrak I(t)$ 将每个项 $t$ 映射为 $A$ 的元素，即
(α) 对变元 $v$，$\mathfrak I(v):=\beta(v)$；(β) 对常元 $c$，$\mathfrak I(c):=c^\mathfrak A$；
(γ) 对 $n$ 元函数符号 $f\in S$，以及项 $t_1,\,\cdots,\,t_n$，$\mathfrak I(ft_1\cdots t_n)=f^\mathfrak A(\mathfrak I(t_1),\,\cdots,\,\mathfrak I(t_n))$．
对公式 $\varphi$ 归纳，可如下定义关系「$\mathfrak I$ 是 $\varphi$ 的模型（model）」，其中 $\mathfrak I$ 是任意的解释．「$\mathfrak I$ 是 $\varphi$ 的模型」可以等价地称为「$\mathfrak I$ 满足（satisfies）$\varphi$」或「$\varphi$ 在 $\mathfrak I$ 中成立（holds）」，并记作 $\mathfrak I\models\varphi$．
〔定义 2.4〕：
$\begin{aligned}
\mathfrak I\models t_1\equiv t_2 &\quad\text{:iff}& \mathfrak I(t_1)=\mathfrak I(t_2)\\
\mathfrak I\models Rt_1\cdots t_n &\quad\text{:iff}& R^\mathfrak A\mathfrak I(t_1)\cdots\mathfrak I(t_n)\\
\mathfrak I\models \neg\varphi &\quad\text{:iff}& \mathfrak I\models\varphi\,不成立\\
\mathfrak I\models (\varphi\land \psi) &\quad\text{:iff}& \mathfrak I\models\varphi\,且\,\mathfrak I\models\psi\\
\mathfrak I\models (\varphi\lor \psi) &\quad\text{:iff}& \mathfrak I\models\varphi\,或\,\mathfrak I\models\psi\\
\mathfrak I\models (\varphi\to \psi) &\quad\text{:iff}& 若\,\mathfrak I\models\varphi\,则\,\mathfrak I\models\psi\\
\mathfrak I\models (\varphi\leftrightarrow \psi) &\quad\text{:iff}& \mathfrak I\models\varphi\,当且仅当\,\mathfrak I\models\psi\\
\mathfrak I\models \forall x\varphi &\quad\text{:iff}&\,对所有\,a\in A,\;\mathfrak I\tfrac ax\models\varphi\\
\mathfrak I\models \exists x\varphi &\quad\text{:iff}&\,存在\,a\in A\,使得\,\mathfrak I\tfrac ax\models\varphi
\end{aligned}$
易知，$\mathfrak I\models\varphi$ 当且仅当 $\varphi$ 在 $\mathfrak I$ 解释下为真命题．
对于 $S$–公式集合 $\varPhi$，若对任意 $\varphi\in\varPhi$，均有 $\mathfrak I\models\varphi$，则称 $\mathfrak I$ 是 $\varPhi$ 的模型（$\mathfrak I$ 满足 $\varPhi$），并记作 $\mathfrak I\models\varPhi$．
〔定义 2.5〕：
令 $\varPhi$ 为公式集合，$\varphi$ 为公式．$\varphi$ 是 $\varPhi$ 的推论（consequence），当且仅当满足 $\varPhi$ 的所有解释亦满足 $\varphi$，记作 $\varPhi\models\varphi$．
设 $\psi$ 为公式，$\{\psi\}\models\varphi$ 简记作 $\psi\models\varphi$．
〔定义 2.6〕：
公式 $\varphi$ 是有效的（valid），当且仅当 $\varnothing\models\varphi$，记作 $\models\varphi$．因此公式有效当且仅当其在所有解释下均成立．
公式 $\varphi$ 是可满足的（satisfiable），当且仅当存在满足 $\varphi$ 的解释，记作 $\operatorname{Sat}\varphi$．公式集合 $\varPhi$ 是可满足的，当且仅当对于任意 $\varphi\in\varPhi$，均有 $\operatorname{Sat}\varphi$，记作 $\operatorname{Sat}\varPhi$．
〔引理 2.a〕：
对于任意公式集合 $\varPhi$ 及任意公式 $\varphi$，$\varPhi\models\varphi$ 当且仅当 $\operatorname{Sat}\varPhi\cup\{\neg\varphi\}$ 不成立．
特别地，$\varphi$ 有效当且仅当 $\{\neg\varphi\}$ 不可满足．
〔证明〕：
$\varPhi\models\varphi$
当且仅当所有满足 $\varPhi$ 的解释亦满足 $\varphi$，
当且仅当不存在满足 $\varPhi$ 而不满足 $\varphi$ 的解释，
当且仅当不存在满足 $\varPhi\cup\{\neg\varphi\}$ 的解释，
当且仅当 $\operatorname{Sat}\varPhi\cup\{\neg\varphi\}$ 不成立．
■