構造と充足

$L$ の構造 $\mathcal{M}$ とは、空でない集合 $M$（領域）と、次の解釈の組である。

• 各定数記号 $c$ に元 $c^{\mathcal{M}}\in M$。
• 各 $n$ 変数関数記号 $f$ に関数 $f^{\mathcal{M}}:M^n\to M$。
• 各 $n$ 変数関係記号 $R$ に部分集合 $R^{\mathcal{M}}\subseteq M^n$。

変数への割り当てとは、写像 $s:\{\text{変数}\}\to M$ である。項 $t$ の値 $t^{\mathcal{M}}[s]\in M$ を、変数 $x$ には $s(x)$、定数 $c$ には $c^{\mathcal{M}}$、$f(t_1,\ldots,t_n)$ には $f^{\mathcal{M}}(t_1^{\mathcal{M}}[s],\ldots,t_n^{\mathcal{M}}[s])$ と定める。

論理式 $\varphi$ について、$\mathcal{M}$ は $s$ のもとで $\varphi$ を満たす($\mathcal{M}\models\varphi[s]$) を次で定める。

1. $\mathcal{M}\models(t_1=t_2)[s]$ $\iff$ $t_1^{\mathcal{M}}[s]=t_2^{\mathcal{M}}[s]$（領域の元として等しい）。
2. $\mathcal{M}\models R(t_1,\ldots,t_n)[s]$ $\iff$ $(t_1^{\mathcal{M}}[s],\ldots,t_n^{\mathcal{M}}[s])\in R^{\mathcal{M}}$。
3. $\mathcal{M}\models\neg\varphi[s]$ $\iff$ $\mathcal{M}\not\models\varphi[s]$。
4. $\mathcal{M}\models(\varphi\to\psi)[s]$ $\iff$ $\mathcal{M}\not\models\varphi[s]$ または $\mathcal{M}\models\psi[s]$。
5. $\mathcal{M}\models\forall x\,\varphi\,[s]$ $\iff$ $M$ のすべての元 $a$ について $\mathcal{M}\models\varphi[s(x\mapsto a)]$。ここで $s(x\mapsto a)$ は $x$ だけ値を $a$ に替えた割り当てである。