Das Erfüllbarkeitsproblem der Booleschen Algebra scheint, zumindest auf den ersten Blick, sehr einfach zu sein: Gegeben sei ein Ausdruck wie und es soll eine Zuordnung von Wahrheitswerten (0 oder 1) für die Booleschen Variablen x ₁, x ₂, x ₃, x ₄ gefunden werden, so daß der gesamte Ausdruck wahr ist. Dies bedeutet, daß jede der Klauseln wie \({{x}_{1}} + {{{\bar{x}}}_{3}} + {{x}_{4}}\) wahr sein (den Wert 1 haben) muß. Wenn wir eine Zuordnung suchen, die den oben wiedergegebenen Ausdruck erfüllt, könnten wir z.B. x ₁ = 1, x ₂ = 1, x ₃ = 1, x₄ = 1 versuchen, um dann festzustellen, daß die Klausel \({{{\bar{x}}}_{1}} + {{x}_{2}} + {{x}_{4}}\) bei dieser Zuordnung den Wert 0 + 0 + 0 = 0 besitzt, was die Bedingung verletzt, daß jede der Klauseln wahr sein muß. Daher folgt hieraus, daß diese Zuordnung den Ausdruck nicht erfüllt. Wenn wir jedoch die Werte x ₁ = 0, x ₂ = 1, x ₃ = 1, x ₄ =1 versuchen, stellen wir fest, daß bei dieser Zuordnung alle Klauseln wahr sind und die Zuordnung den Ausdruck „erfüllt“. Ausdrücke, welche die obige Form besitzen, bezeichnet man als in Summenprodukt-Form.