Eigenschaft eines Ausdrucks aus einem logischen Kalkül.

Ein aussagenlogischer Ausdruck ϕ ist erfüllbar, wenn es eine Belegung der Aussagenvariablen mit Wahrheitswerten gibt, so daß ϕ bei dieser Belegung wahr wird.

Ein prädikatenlogischer Ausdruck ϕ(x₁, …, x_n) ist erfüllbar, wenn es eine algebraische Struktur \({\mathcal{A}}\) und Elemente a₁, …, a_n in der Trägermenge der Struktur gibt, so daß \begin{eqnarray}{\mathcal{A}}\models \varphi ({\mathop{a}\limits_{\_}}_{1},\ldots,{\mathop{a}\limits_{\_}}_{n})\end{eqnarray} (elementare Sprache).