Kanonische Normalform

Kanonische Normalform

Eine aussagenlogische Formel ist die kanonische Normalform (KNF; engl.: canonical normal form) zu einer weiteren aussagenlogischen Formel, wenn sie

  • eine Normalform dieser aussagenlogischen Formel ist, d.h. eine zu dieser Formel äquivalente aussagenlogische Formel, die bestimmten syntaktischen Restriktionen unterliegt und
  • für äquivalente aussagenlogische Formeln identisch und eindeutig ist.

Beispiele

  • Disjunktive Normalformen sind im Allgemeinen nicht kanonisch, aber die maximale, bzw. erweiterte disjunktive Normalform (eine Disjunktive Normalform, die nur Minterme enthält, in denen alle Variablen vorhanden sind, jede Variable genau einmal vorkommt und deren Minterme alle voneinander verschieden sind) ist kanonisch
  • Konjunktive Normalformen sind im Allgemeinen nicht kanonisch, aber die maximale, bzw. erweiterte konjunktive Normalform (eine Konjunktive Normalform, die nur Maxterme enthält, in denen alle Variablen vorhanden sind, jede Variable genau einmal vorkommt und deren Maxterme alle voneinander verschieden sind) ist kanonisch
  • Die Ringsummennormalform (auch Reed-Muller-Normalform genannt) ist kanonisch
  • Für eine feste Variablenordnung ist die reduzierte Shannon-Normalform kanonisch (Anwenden der Shannon-Zerlegung bei fester Variablenordnung und anschließendes Eliminieren redundanter Teilformeln). Diese Eigenschaft ist beispielsweise wichtig bei Binären Entscheidungsdiagrammen (BDDs), deren Grundlage die Shannon-Zerlegung bildet: Boolesche Operationen auf reduzierten geordneten BDDs (ROBDDs) bewahren hier stets die kanonische Normalform solcher Diagramme.

Anwendungsmöglichkeiten

Um die Äquivalenz zweier aussagenlogischer Formeln α und β aufzuzeigen, können beide Formeln mit sämtlichen möglichen Interpretationen ausgewertet werden; liefern alle Interpretationen bei beiden Formeln jeweils denselben booleschen Wert, sind beide Formeln äquivalent.

Alternativ können beide Formeln auch in kanonische Normalformen KNF(α) und KNF(β) transformiert werden; beide Formeln sind äquivalent genau dann, wenn KNF(α) = KNF(β).

Außerdem können Fragen die Erfüllbarkeit und Allgemeingültigkeit einer Formel γ betreffend mithilfe von kanonischen Normalformen beantwortet werden: so ist eine aussagenlogische Formel γ erfüllbar genau dann, wenn KNF(γ) \neq KNF(0) und γ ist allgemeingültig genau dann, wenn KNF(γ) = KNF(1).

Größe kanonischer Normalformen

Es gilt, dass kanonischen Normalformen ein exponentieller Blow-Up inhärent ist; das heißt, eine kanonische Normalform ist im Allgemeinen exponentiell größer als diejenige aussagenlogische Formel, die in eine solche überführt wird; dies besagt das Aufzählungstheorem von Claude Elwood Shannon:

Sei a(n) die Zahl derjenigen aussagenlogischen Formeln mit n Variablen, deren kanonische Normalform nur polynomiell größer ist, dann steht dieser Zahl die Zahl sämtlicher möglicher Boolescher Funktionen B(n) mit n Variablen gegenüber, die 2(2n) ist. Dann gilt: \lim_{n \to \inf} \frac{a(n)}{B(n)} = 0.

Daraus folgt, dass die meisten kanonischen Normalformen exponentiell länger sind als eine beliebige aussagenlogische Formel, die in eine solche überführt wird; insbesondere steigt die Wahrscheinlichkeit, dass eine aussagenlogische Formel nur in eine exponentiell längere kanonische Normalform transformiert werden kann mit der Zahl der involvierten Variablen an; aufgrund dessen ist es auch nicht möglich, das Erfüllbarkeitsproblem der Aussagenlogik mithilfe von kanonischen Normalformen deterministisch mit polynomiellem Zeitaufwand zu lösen.

Unterschiedliche kanonische Normalformen können für eine bestimmte aussagenlogische Formel ein unterschiedliches Verhalten ihre Größe betreffend aufweisen: So ist zum Beispiel die kanonische disjunktive Normalform für die sog. Paritätsfunktion F_n = x_1 \otimes ... \otimes x_n exponentiell länger als Fn, die Länge der Reed-Muller-Normalform wächst dagegen nur polynomiell für Fn mit größer werdendem n.


Wikimedia Foundation.

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

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

  • 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

  • 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

  • kanonische Form — 1. K.F. eines linearen Gleichungssystems: Jedes zu dem betrachteten linearen Gleichungssystem äquivalente kanonische lineare Gleichungssystem. 2. K.F. eines linearen NN Gleichungssystems: Jedes zu dem betrachteten NN Gleichungssystem äquivalente… …   Lexikon der Economics

  • Kanonische Jordanform — Jordano norminė forma statusas T sritis automatika atitikmenys: angl. Jordan canonical form; Jordan normal form vok. Jordansche Normalform, f; Kanonische Jordanform, f rus. жорданова нормальная форма, f; каноническая форма Жордана, f pranc. forme …   Automatikos terminų žodynas

  • Disjunktive Normalform — Als disjunktive Normalform (kurz DNF) wird in der Booleschen Algebra eine in besonderer Weise normierte Funktionsdarstellung Boolescher Funktionen bezeichnet. Inhaltsverzeichnis 1 Definition 2 Erläuterung 3 Bildung …   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

  • Jordansche Normalform — Jordano norminė forma statusas T sritis automatika atitikmenys: angl. Jordan canonical form; Jordan normal form vok. Jordansche Normalform, f; Kanonische Jordanform, f rus. жорданова нормальная форма, f; каноническая форма Жордана, f pranc. forme …   Automatikos terminų žodynas

  • KDNF — Als disjunktive Normalform (kurz DNF) wird in der Booleschen Algebra eine in besonderer Weise normierte Funktionsdarstellung Boolescher Funktionen bezeichnet. Inhaltsverzeichnis 1 Definition 2 Erläuterung 3 Bildung 4 Beispiel für die Bildung der… …   Deutsch Wikipedia

  • Produktterm — Als disjunktive Normalform (kurz DNF) wird in der Booleschen Algebra eine in besonderer Weise normierte Funktionsdarstellung Boolescher Funktionen bezeichnet. Inhaltsverzeichnis 1 Definition 2 Erläuterung 3 Bildung 4 Beispiel für die Bildung der… …   Deutsch Wikipedia

  • Sum of products — Als disjunktive Normalform (kurz DNF) wird in der Booleschen Algebra eine in besonderer Weise normierte Funktionsdarstellung Boolescher Funktionen bezeichnet. Inhaltsverzeichnis 1 Definition 2 Erläuterung 3 Bildung 4 Beispiel für die Bildung der… …   Deutsch Wikipedia

Share the article and excerpts

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