Antwort mit KI erzeugt
Induktion über Formalaufbau: Transformation NNF in KNF
Zunächst definieren wir die relevanten Begriffe und erläutern den Plan, um die Aufgabe systematisch zu lösen.
Negationsnormalform (NNF): Eine aussagenlogische Formel ist in Negationsnormalform (NNF), wenn Negationen nur unmittelbar vor den Variablen stehen und die einzigen verwendeten logischen Operationen $\land$ (Konjunktion) und $\lor$ (Disjunktion) sind.
Konjunktive Normalform (KNF): Eine Formel ist in konjunktiver Normalform (KNF), wenn sie eine Konjunktion von Disjunktionen von Literalen ist. Ein Literal ist eine Aussagenvariable oder die Negation einer Aussagenvariable.
Die Induktion über den Formelaufbau bedeutet, dass wir für jede Konstruktion einer Formel in NNF zeigen werden, dass diese in eine Formel in KNF transformiert werden kann.
Induktionsbasis:
1.
Atomare Fälle (Basisfälle): Eine einzelne Variable \(p\) oder eine negierte Variable \(\neg p\) ist bereits eine gültige KNF, da es sich dabei um eine Disjunktion mit nur einem Glied handelt, die wiederum innerhalb einer impliziten Konjunktion nur eines Gliedes liegt.
Induktionsschritt:
Zu zeigen ist, dass, wenn die Teilausdrücke einer Formel \(F\) in NNF in eine KNF transformierbar sind, dies auch für \(F\) gilt. Wir betrachten folgende Konstruktionen:
1.
Konjunktion \(\land\): Angenommen, \(F = A \land B\), wobei \(A\) und \(B\) in NNF sind und bereits in KNF transformiert wurden. Die KNF der Gesamtformel ist einfach die Konjunktion der KNFs von \(A\) und \(B\), daher ist \(F\) in KNF.
2.
Disjunktion \(\lor\): Für eine Disjunktion \(F = A \lor B\), mit \(A\) und \(B\) in KNF, müssen wir die Distributivität nutzen, um eine KNF zu erreichen. Da \(A\) und \(B\) Konjunktionen von Disjunktionen sind, verwenden wir die Regel \(p \lor (q \land r) = (p \lor q) \land (p \lor r)\), um \(F\) in die entsprechende KNF zu transformieren.
Beispielhaftes Vorgehen im Induktionsschritt für die Disjunktion:
Angenommen, \(A\) und \(B\) seien die KNFs \(A = (p \lor q)\) und \(B = (r \land s)\), dann ist:
\(
F = A \lor B = (p \lor q) \lor (r \land s)
\)
Durch Anwenden der Distributivität erhalten wir:
\(
F = ((p \lor q) \lor r) \land ((p \lor q) \lor s)
\)
Diese Formel ist nun eine Konjunktion von Disjunktionen von Literalen, also in KNF.
Abschlussgedanke:
Für den negativen Fall, wo \(\neg F\) betrachtet wird, ist bei NNF der Negationsoperator nur direkt auf Variablen anwendbar und somit bereits in einer akzeptablen Form für die KNF. Außerdem bleiben die Transformationsregeln für \(\land\) und \(\lor\) durch die Konstruktion der NNF unberührt.
Zusammengefasst haben wir gezeigt, dass jede Formel in NNF systematisch in eine äquivalente Formel in KNF transformiert werden kann, und somit ist die angegebene Behauptung durch Induktion über den Formelaufbau bewiesen.
