Denselben Sachverhalt kann man auf verschiedene Weisen ausdrücken. Es gibt also unterschiedliche Arten, ein und dieselbe Sache zu formulieren. Mit anderen Worten, Dinge können so oder so gesagt werden. Damit ist gemeint, dass sich Aussagen drehen und wenden lassen, ohne sie zu ändern. Insbesondere stimmt es nicht, dass es nur eine Möglichkeit gibt, etwas auszusprechen. This means that there are different ways of saying the same thing. Phrased differently, there is an endless supply of different formulations for a single thought\dots
Ohne die Möglichkeit, Dinge auf verschiedene Arten auszudrücken wäre die Literatur wahrlich fade und öde. Sprache lebt davon, dass man mit Ihr spielt, dass man durch geschickte Wendungen und Formulierungen Akzente setzt, den Dingen Leben einhaucht. Was für die Lyrik gut ist, muss nicht unbedingt auch für die Informatik und die Logik wohltuend sein. Java-Programme und aussagenlogische Formeln sind schließlich keine Liebesgedichte (wobei while(true)System.out.print("I love you. "); der Sache schon recht nahe kommt).
Bei logischen Formeln ist es oftmals sehr natürlich danach zu fragen, ob man nicht eine einfachere Formulierung für eine gegebene Formel finden kann. Ein klassisches Beispiel ist die doppelte Verneinung, die man einfach weglassen kann: Statt »Es ist nicht der Fall, dass es nicht der Fall ist, dass a gilt« kann man auch einfacher sagen »a gilt«. Mathematisch geschrieben: \neg \neg a \equiv a. Es gibt aber auch komplexere Fälle, die nicht so offensichtlich sind: »Es ist nicht der Fall, dass nicht a und auch nicht b gelten« lässt sich auch schreiben als »a oder b«, mathematisch \neg (\neg a \land \neg b) \equiv a \lor b.
In diesem Kapitel geht es darum, was passiert, wenn man solche Vereinfachungen bis zum bitteren Ende durchführt. Dabei ist zunächst gar nicht klar, wo denn das bittere Ende sein wird. Gibt es Formeln, die sich nicht weiter vereinfachen lassen? Sicherlich wird die doch recht minimalistische Formel $a$ diese Eigenschaft haben. Genauso aber auch a \lor b, es geht wirklich nicht simpler. Bei einer Formel wie (a \lor b) \land (c \lor d) ist aber schon nicht mehr klar, ob hier jetzt das Ende der Fahnenstange erreicht ist.
Normalformen sind »Formen von Formeln«, die einen solchen Zustand der maximalen Vereinfachung erreicht haben. Originellerweise gibt es gleich zwei Arten von Normalformen für aussagenlogische Formeln: die disjunktive Normalform und die konjunktive Normalform. Dass es zwei Arten gibt, liegt nicht daran, dass sich ein Normierungsgremium nicht einigen konnte, sondern daran, dass es eben auf den Standpunkt oder die Anwendung ankommt, was die »einfachste« Fassung einer Formel ist.
Das Konzept, Dinge so lange zu vereinfachen bis etwas »in Normalform« herauskommt, wird Ihnen in Ihrem Studium noch häufig begegnen. Sie werden Normalformen für reguläre Grammatiken kennen lernen, mehrere Normalformen für kontextfreie Grammatiken, ja sogar Normalformen für Computerprogramme. Das Studium der Normalformen bringt dabei manchmal etwas wunderliche Resultate hervor - wenn Sie beispielsweise verschachtelte Schleifen nicht mögen, so wird es sie sicherlich beruhigen zu erfahren, dass Sie jedes Javaprogramm so »vereinfachen« können, dass alle While- und For-Schleifen durch eine einzige While-Schleife ersetzt werden.