134.19.105.142: /* Beispiele */

2024-01-24T15:18:36Z

Beispiele

Neue Seite

{{Dieser Artikel| beschreibt die Kanonische Normalform in der Logik. Zur Kanonische Normalform in der Regelungstechnik siehe [[Jordansche Normalform]].}}
Eine [[Aussagenlogik|aussagenlogische]] Formel ist die '''kanonische Normalform''' (KNF, nicht zu verwechseln mit „[[Konjunktive Normalform]]“ (auch CNF); 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 Normalform]]en sind im Allgemeinen nicht kanonisch, aber die ''maximale bzw. erweiterte disjunktive Normalform'' (eine disjunktive Normalform, die nur [[Minterm]]e enthält, in denen alle Variablen vorhanden sind, jede Variable genau einmal vorkommt und deren Minterme alle voneinander verschieden sind) ist kanonisch.
* [[Konjunktive Normalform]]en sind im Allgemeinen nicht kanonisch, aber die ''maximale bzw. erweiterte konjunktive Normalform'' (eine konjunktive Normalform, die nur [[Maxterm]]e 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äres Entscheidungsdiagramm|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 [[Logische Äquivalenz|Äquivalenz]] zweier aussagenlogischer Formeln <math>\alpha</math> und <math>\beta</math> aufzuzeigen, können beide Formeln mit sämtlichen möglichen [[Interpretation (Logik)|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(<math>\alpha</math>) und KNF(<math>\beta</math>) transformiert werden; beide Formeln sind äquivalent genau dann, wenn KNF(<math>\alpha</math>) = KNF(<math>\beta</math>).

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

== Größe kanonischer Normalformen ==
Es gilt, dass kanonischen Normalformen ein ''exponentieller Blow-Up'' [[Inhärenz|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 <math>2^{2^n}</math> ist. Dann gilt: <math>\lim_{n \to \inf} \frac{a(n)}{B(n)} = 0</math>.

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 [[Determinismus (Algorithmus)|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'' <math>F_n = x_1 \otimes ... \otimes x_n</math> exponentiell länger als <math>F_n</math>, die Länge der Reed-Muller-Normalform wächst dagegen nur polynomiell für <math>F_n</math> mit größer werdendem n.

[[Kategorie:Mathematische Logik]]
[[Kategorie:Normalform]]

Kanonische Normalform - Versionsgeschichte

134.19.105.142: /* Beispiele */