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\vee B\vee \bar{C})\wedge (A\vee B\vee C)$

$$\begin{array}{ll}{x}_1+x_2+\left(1-x_3\right)\ge 1& \left(D_1=\{1,2\},E_1=\{3\}\right)\\ x_1+x_2+x_3\ge 1& \left(D_2=\{1,2,3\},E_2=\varnothing \right)\\ x\in \{0,1{\}}^3& \end{array}$$