Erfüllbarkeitsproblem der Aussagenlogik

Meistens in Conjunctive Normal Form.

Ist in NPC und exponentiell (worst case) in der Anzahl der Variablen lösbar, zum Beispiel durch das aufstellen einer Wahrheitstabelle.

Beispiel

(A∨B∨Cˉ)∧(A∨B∨C)(A \vee B \vee \bar{C}) \wedge(A \vee B \vee C) x1+x2+(1−x3)≥1(D1={1,2},E1={3})x1+x2+x3≥1(D2={1,2,3},E2=∅)x∈{0,1}3\begin{array}{ll} x_{1}+x_{2}+\left(1-x_{3}\right) \geq 1 & \left(D_{1}=\{1,2\}, E_{1}=\{3\}\right) \\ x_{1}+x_{2}+x_{3} \geq 1 & \left(D_{2}=\{1,2,3\}, E_{2}=\emptyset\right) \\ x \in\{0,1\}^{3} & \end{array}