Klausel-Normalform

Klausel-Normalform

Die Klauselform oder Klauselnormalform beschreibt in der Logik eine Formel in konjunktiver Normalform (KNF), bei der die Konjunktionen jeweils in Mengenschreibweise zusammengefasst wurden.

Eine Formel in Klauselform (selten auch Klausenform) ist eine logische Verknüpfung von Literalen, notiert als disjunktive Normalform oder konjunktive Normalform, wobei festgelegt ist, dass die leere verallgemeinerte Disjunktion interpretiert den Wahrheitswert falsch ergibt und die leere verallgemeinerte Konjunktion interpretiert den Wahrheitswert wahr ergibt.

Klauselnormalformen sind über eine Transformation erstellbar und dienen zur maschinellen Beweisführung über logischen Formeln.

Inhaltsverzeichnis

Beispiel 1

((a \vee b) \wedge (b \vee c) \wedge (a \vee \neg d \vee \neg e) \wedge d)

ist eine Formel in KNF, welche in Klauselform einfach so dargestellt wird:

\{ \{a,b\}, \{b,c\}, \{a, \neg d, \neg e\}, \{d\} \}

Diese Schreibweise ist kompakter und erleichtert beispielsweise den Test auf (Un)Erfüllbarkeit mittels Resolution.

Beispiel 2

Die aussagenlogische Formel  \neg(P\or (\neg(P\and Q)\and \neg R)) soll in konjunktive Klauselform transformiert werden (verallgemeinerte Konjunktion):


\{\neg(P\or (\neg(P\and Q) \and \neg R))\}

\{\{\neg P\}, \{\neg(\neg(P \and Q)\and \neg R)\}\}

\{\{\neg P\}, \{\neg \neg (P \and Q) , \neg \neg R\}\}

\{\{\neg P\}, \{(P \and Q), R\}\}

\{\{\neg P\}, \{P,R\}, \{Q, R\}\}

Hornklauseln

Hornklauseln stellen eine spezielle Klauselnormalform dar, bei der jede Klausel maximal ein positives Literal enthält.

  • negative Hornklausel: Klausel enthält kein positives Literal
  • positive Hornklausel: Klausel enthält ein positives Literal

Diese Schreibweise ist deswegen beliebt, da sich Hornklauseln schnell in eine Menge von Implikationen umformen lassen.

Beispiel

  • Hornklausel: \{ \{a, \neg b\}, \{ \neg c, \neg d\}, \{b\} \}
  • Äquivalenter Ausdruck:  (\neg a \Rightarrow \neg b) \wedge (c \Rightarrow \neg d) \wedge (true \Rightarrow b)
  • Weitere mögliche Schreibweise: (b \Rightarrow a) \wedge (c \wedge d \Rightarrow false) \wedge (true \Rightarrow b)

siehe auch: Horn-Formel


Wikimedia Foundation.

Игры ⚽ Нужен реферат?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Normalform — Unter einer Normalform (auch kanonische Form) versteht man eine Darstellung mit bestimmten vorgegebenen Eigenschaften. Mitunter ist die Darstellung eindeutig. Formal ist eine Normalform ein letztes Element in einer Kette von einer wohlfundierten… …   Deutsch Wikipedia

  • Klausel (Logik) — Ein Disjunktionsterm (auch als Klausel bezeichnet) ist eine Boolesche Funktion, die ausschließlich durch die disjunktive Verknüpfung von Literalen gebildet wird. Ihre allgemeine Form sieht so aus: , wobei Ein Disjunktionsterm, der sämtliche n… …   Deutsch Wikipedia

  • Skolem-Normalform — Skolemform ist ein Begriff der Prädikatenlogik und bezeichnet eine prädikatenlogische Formel, die sich in einer Normalform nach Albert Thoralf Skolem befindet. Für Formeln in Skolemform existiert ein berechenbarer Test auf Erfüllbarkeit. Dies ist …   Deutsch Wikipedia

  • Horn-Klausel — Horn Formeln sind eine spezielle Teilmenge der aussagenlogischen Formeln. Benannt wurden sie nach dem US amerikanischen Logiker Alfred Horn. Inhaltsverzeichnis 1 Definition mit Horn Klauseln 1.1 Beispiele 1.2 Darstellungsformen von Horn Klauseln… …   Deutsch Wikipedia

  • Konjunktive Normalform — Als konjunktive Normalform (kurz KNF, engl. CNF für conjunctive normal form) wird in der Aussagenlogik eine bestimmte Form von Formeln bezeichnet. Inhaltsverzeichnis 1 Definition 2 Kanonische konjunktive Normalform 3 Bildung …   Deutsch Wikipedia

  • Kanonische Form — Unter einer Normalform versteht man eine Darstellung, die bestimmte vorgegebene Eigenschaften hat. Insbesondere bezeichnet Normalform in der Mathematik eine Darstellung eines Objektes, die bestimmte vorgegebene Eigenschaften hat und für alle… …   Deutsch Wikipedia

  • Skolemformel — Skolemform ist ein Begriff der Prädikatenlogik und bezeichnet eine prädikatenlogische Formel, die sich in einer Normalform nach Albert Thoralf Skolem befindet. Für Formeln in Skolemform existiert ein berechenbarer Test auf Erfüllbarkeit. Dies ist …   Deutsch Wikipedia

  • Skolemisierung — Skolemform ist ein Begriff der Prädikatenlogik und bezeichnet eine prädikatenlogische Formel, die sich in einer Normalform nach Albert Thoralf Skolem befindet. Für Formeln in Skolemform existiert ein berechenbarer Test auf Erfüllbarkeit. Dies ist …   Deutsch Wikipedia

  • Skolemnormalform — Skolemform ist ein Begriff der Prädikatenlogik und bezeichnet eine prädikatenlogische Formel, die sich in einer Normalform nach Albert Thoralf Skolem befindet. Für Formeln in Skolemform existiert ein berechenbarer Test auf Erfüllbarkeit. Dies ist …   Deutsch Wikipedia

  • Skolemform — ist ein Begriff der Prädikatenlogik und bezeichnet eine prädikatenlogische Formel, die sich in einer Normalform nach Albert Thoralf Skolem befindet. Für Formeln in Skolemform existiert ein berechenbarer Test auf Erfüllbarkeit. Dies ist nützlich,… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”