LERNZIELE:
Am Ende dieser Lektion wird der Student in der Lage sein:

1. Die Definition von Literal sowie der konjunktiven und disjunktiven Normalform zu erinnern.
2. Die Strukturen eines Ausdrucks in KNF und DNF zu identifizieren.
3. KNF oder DNF anzuwenden, um Ausdrücke der Aussagenlogik zu vereinfachen.

INHALTSVERZEICHNIS
DEFINITION VON LITERAL
DEFINITION VON NORMFORMEN
SATZ ÜBER DIE NORMFORMEN

Ein interessantes und nützliches Resultat der Aussagenlogik steht im Zusammenhang mit den Normformen. Um auf diese Aspekte näher einzugehen, müssen wir zunächst einige Konzepte überprüfen.

Definition von Literal

Ein Literal ist jeder atomare Ausdruck oder die Negation eines atomaren Ausdrucks. In diesem Sinne sprechen wir von negativen oder positiven Literalen, je nachdem, ob es sich um atomare Ausdrücke mit oder ohne vorangestellter Negation handelt. Zum Beispiel: A wäre ein positives Literal und \neg A wäre ein negatives Literal.

Definition von Normformen

Ein Ausdruck F ist in konjunktiver Normalform (KNF), wenn er als Konjunktion von Disjunktionen von Literalen geschrieben werden kann, das heißt:

\displaystyle F=\bigwedge_{i=1}^n \left( \bigvee_{j=1}^m L_{ij}\right)

Und analog dazu liegt eine disjunktive Normalform (DNF) vor, wenn der Ausdruck als Disjunktion von Konjunktionen von Literalen geschrieben wird.

\displaystyle F=\bigvee_{i=1}^n \left(\bigwedge_{j=1}^m L_{ij}\right)

Satz über die Normformen

Alle Ausdrücke der Aussagenlogik sind äquivalent zu einem Ausdruck in DNF und einem in KNF.

BEWEIS:

Dies lässt sich durch Induktion über die Komplexität der Formeln F beweisen.

• Induktionsanfang: Wenn F ein atomarer Ausdruck ist, dann kann er gleichzeitig in KNF und DNF geschrieben werden, da gilt: F\equiv F_D \equiv F_C, wobei F_C:=((F\vee F)\wedge (F\vee F)) und F_D:=((F\wedge F)\vee (F\wedge F))
• Induktionsschritt: Seien G und H zwei beliebige Ausdrücke, für die die Aussage des Satzes gilt, das heißt, es existieren H_C und G_C in KNF sowie H_D und G_D in DNF, sodass

  G\equiv G_D \equiv G_D

  H\equiv H_D \equiv H_D

  Daher können wir schreiben:

  \displaystyle G_D := \bigvee_{i=1}^n \bigwedge_{j=1}^m L_{ij}^{GD} ; \displaystyle G_C := \bigwedge_{i=1}^n \bigvee_{j=1}^m L_{ij}^{GC}

  \displaystyle H_D := \bigvee_{i=1}^n \bigwedge_{j=1}^m L_{ij}^{HD} ; \displaystyle H_C := \bigwedge_{i=1}^n \bigvee_{j=1}^m L_{ij}^{HC}

  Ohne Allgemeinheit einzuschränken, kann man sehen, dass wenn F:= \neg G, dann gilt unter Anwendung des Substitutionstheorems und der verallgemeinerten De-Morgan-Gesetze:

  \displaystyle F:= \neg G \equiv \left\{ \begin{matrix} \neg G_D := \neg \bigvee_{i=1}^n \bigwedge_{j=1}^m L_{ij}^{GD} \equiv\bigwedge_{i=1}^n \neg \bigwedge_{j=1}^m L_{ij}^{GD} \equiv \bigwedge_{i=1}^n \bigvee_{j=1}^m \neg L_{ij}^{GD} \\ \\ \neg G_C := \neg \bigwedge_{i=1}^n \bigvee_{j=1}^m L_{ij}^{GC} \equiv \bigvee_{i=1}^n \neg \bigvee_{j=1}^m L_{ij}^{GC} \equiv \bigvee_{i=1}^n \bigwedge_{j=1}^m \neg L_{ij}^{GC} \end{matrix}\right.

  Andererseits, wenn F:=G\wedge H, dann ergibt sich nach dem Substitutionstheorem:

  \displaystyle F:=G\wedge H \equiv G_C \wedge H_C := \bigwedge_{i=1}^n \bigvee_{j=1}^m L_{ij}^{GC} \wedge \bigwedge_{i=1}^{n^\prime} \bigvee_{j=1}^{m^\prime} L_{ij}^{HC}

  was eine konjunktive Normalform ist. Und ganz analog gilt: Wenn F:=H\vee G, dann:

  \displaystyle F:=G\wedge H \equiv G_D \vee H_D := \bigvee_{i=1}^n \bigwedge_{j=1}^m L_{ij}^{GD} \vee \bigvee_{i=1}^{\overline{n}} \bigwedge_{j=1}^{\overline{m}} L_{ij}^{HD}

  das heißt, eine disjunktive Normalform.

  Daher ist die Induktion vollständig und alle Ausdrücke der Aussagenlogik können in DNF und KNF geschrieben werden.

Das Studium der konjunktiven (KNF) und disjunktiven (DNF) Normalformen in der Aussagenlogik ist grundlegend für die Vereinfachung und Lösung komplexer Probleme in Mathematik und Informatik. Der Satz, dass jeder logische Ausdruck sowohl in DNF als auch in KNF geschrieben werden kann, ist von großer Bedeutung, da er eine standardisierte und handhabbare Strukturierung von Aussagen ermöglicht und so deren Analyse und Verarbeitung erleichtert. Die Relevanz dieses Resultats liegt in seiner fundamentalen Rolle für die Gestaltung von Algorithmen, die Optimierung logischer Ausdrücke und die effiziente Problemlösung in verschiedenen Wissensbereichen wie der künstlichen Intelligenz und der Softwareverifikation. Darüber hinaus verstärkt die zum Beweis dieses Satzes verwendete Induktionstechnik das Verständnis der grundlegenden Eigenschaften logischer Ausdrücke und deren Anwendbarkeit in anderen mathematischen Kontexten.