Disjunktionsterm

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Ein Disjunktionsterm (auch als Disjunktionsglied oder Klausel bezeichnet) ist eine Boolesche Funktion, die ausschließlich durch die disjunktive Verknüpfung von Literalen gebildet wird. Ihre allgemeine Form sieht so aus:

X_1 \vee X_2 \vee ... \vee X_k, wobei  X_i \in \lbrace 0, 1 \rbrace

Ein Disjunktionsterm, der sämtliche Indizes der betrachteten Booleschen Funktion F: \{0;1\}^n \rightarrow \{0;1\} enthält, wird auch als Maxterm bezeichnet. Fügt man mehrere Disjunktionsterme durch Konjunktionen zusammen, so erhält man eine Konjunktive Normalform.

Die entsprechende konjunktive Verknüpfung von Literalen bezeichnet man als Konjunktionsterm.

Einige Beispiele für Disjunktionsterme, wobei A_i jeweils Atome seien:

\neg A_0 \vee A_1
A_0 \vee A_1 \vee A_2
\neg A_0 \vee \neg A_1 \vee \neg A_2