Erfüllbarkeitsproblem der Aussagenlogik
Erfüllbarkeitsproblem der Aussagenlogik
Das Entscheidungsproblem SAT stellt die Frage ob Aussagenlogischen Formeln erfüllbar sind.
Als Sprache formuliert:
$$ \textrm{SAT} = \left\{\langle\phi\rangle\mid \phi\text{ ist eine erfüllbare }\textrm{KNF}\right\}$$