ein Boolescher Ausdruck \(w\in {{\mathfrak{A}}}_{n}\), der eine Boolesche Funktion φ(w) darstellt (Boolescher Ausdruck), für die es wenigstens eine Variablenbelegung α ∈ {0, 1}ⁿ mit \begin{eqnarray}\phi (w)({\alpha }_{1},\ldots,{\alpha }_{n})=1\end{eqnarray} gibt.

Die ON-Menge der Booleschen Funktionφ(w) heißt Erfüllbarkeitsmenge des Booleschen Ausdrucks w. Ein Verfahren, das entscheidet, ob die Erfüllbarkeitsmenge eines Booleschen Ausdrucks w nicht leer ist, wird Erfüllbarkeitstest genannt.