Disjunktion von Booleschen Literalen.

Eine Boolesche Klausel aus \({{\mathfrak{A}}}_{n}\) (Boolescher Ausdruck) ist von der Form \({x}_{{i}_{1}}^{{\varepsilon }_{1}}\vee \ldots \vee {x}_{{i}_{k}}^{{\varepsilon }_{k}}\) mit \({\varepsilon }_{j}\in \{0,1\}(\forall j\in \{1,\ldots, k\})\), wobei \({x}_{j}^{1}\) das positive Boolesche Literal x_j und \({x}_{j}^{0}\) das negative Boolesche Literal \(\bar{{x}_{j}}\) bezeichnet. Eine Boolesche Klausel heißt vollständige Boolesche Klausel, wenn sie jede Boolesche Variable aus \(\{{x}_{1},\ldots, {x}_{n}\}\) entweder als positives oder als negatives Boolesches Literal enthält. Die meisten Anwendungen gehen hierbei davon aus, daß eine Klausel jede Variable höchstens einmal enthält, entweder als positives oder als negatives Literal.