La satisfiabilité et la validité sont des concepts élémentaires de la sémantique. Une formule est satisfiable s'il est possible de trouver une interprétation (modèle) qui la rend vraie.  Une formule est valide si toutes les interprétations la rendent vraie.

Le principe de satisfiabilité booléenne (parfois appelé problème de satisfiabilité propositionnelle et abrégé SATISFIABILITÉ ou problème SAT) est le problème consistant à déterminer s’il existe une interprétation qui satisfait une formule booléenne donnée.