SAT (Erfüllbarkeitsproblem)

SAT (Satisfiability) ist die Sprache aller erfüllbaren aussagenlogischen Formeln.
Gegeben eine Formel $F$ mit Booleschen Variablen, ist $F\in SAT$, wenn es eine Belegung der Variablen mit $\{0,1\}$ gibt, sodass $F$ zu $1$ (wahr) ausgewertet wird.