Es sei ${\displaystyle {}V}$ eine Menge von Aussagenvariablen und ${\displaystyle {}L^{V}}$ die zugehörige aussagenlogische Sprache. Eine Teilmenge ${\displaystyle {}\Gamma \subseteq L^{V}}$ heißt erfüllbar, wenn es eine Wahrheitsbelegung ${\displaystyle {}\lambda }$ mit zugehöriger Interpretation ${\displaystyle {}I}$ derart gibt, dass ${\displaystyle {}I(\alpha )=1}$ für alle ${\displaystyle {}\alpha \in \Gamma }$ gilt.