Kanonische Normalform

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

Beispiele

Anwendungsmöglichkeiten

Um die Äquivalenz zweier aussagenlogischer Formeln \alpha und \beta 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(\alpha ) und KNF(\beta ) transformiert werden; beide Formeln sind äquivalent genau dann, wenn KNF(\alpha ) = KNF(\beta ).

Außerdem können Fragen die Erfüllbarkeit und Allgemeingültigkeit einer Formel \gamma betreffend mithilfe von kanonischen Normalformen beantwortet werden: so ist eine aussagenlogische Formel \gamma erfüllbar genau dann, wenn KNF(\gamma ) \neq KNF(0) und \gamma ist allgemeingültig genau dann, wenn KNF(\gamma ) = 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^{{2^{n}}} 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 F_{n}, die Länge der Reed-Muller-Normalform wächst dagegen nur polynomiell für F_{n} mit größer werdendem n.

Trenner
Basierend auf einem Artikel in: Extern Wikipedia.de
Seitenende
Seite zurück
©  biancahoegel.de
Datum der letzten Änderung:  Jena, den: 13.11. 2020