· 

Die konjunktive Normalform (KNF)

1. Einführung

Bei der konjuktiven Normalform (KNF) hat man zunächst eine bestimmte Anzahl sogenannter Maxterme, also ausschließlich durch das logische Oder verknüpfte Aussagen. Diese elementaren Aussagen nennt man auch Atome. Die Maxterme werden durch das logische Und miteinander verknüpft. Deshalb stellt die KNF auch eine Konjunktion von Disjunktionen bzw. ein Minterm aus Maxtermen dar. Eine aussagenlogische Formel in KNF sieht z. B. wie folgt aus: $$\overbrace{\underbrace{(A\vee \overline{B}\vee C)}_{\text{Maxterm}} \wedge \underbrace{(\overline{A}\vee \overline{B}\vee C)}_{\text{Maxterm}} \wedge \underbrace{(A\vee B\vee \overline{C})}_{\text{Maxterm}}}^{\text{Minterm}}$$

2. Wie liest man die KNF aus einer Wahrheitstafel ab?

Dafür gibt es einen einfachen Algorithmus, der als Eingabe eine Wahrheitstafel erhält und als Ausgabe eine aussagenlogische Formel in KNF ausgibt. Der Algorithmus läuft in \(4\) einfachen Schritten ab:
Algorithmus: Wahrheitstafel in KNF

Eingabe: Wahrheitstafel
Ausgabe: Aussagenlogische Formel in KNF
  1. Markiere alle Einträge in der Tabelle, die eine \(0\) in der letzten Spalte haben.
  2. Sorge durch die Negation dafür, dass in jeder markierten Zeile in allen Spalten eine \(0\) steht.
  3. Erzeuge aus den in Schritt \(1\) markierten Zeilen jeweils Maxterme, indem du die alle Variablen, die ggf. negiert wurden, um überall eine \(0\) herauszubekommen, mit dem logischen Oder verknüpfst.
  4. Verknüpfe alle in Schritt \(3\) erzeugten Maxterme durch das logische Und.
Das Ergebnis des Algorithmus ist nicht zwangsläufig minimal. Für die Minimierung von aussagenlogischen Formeln kann man z. B. das sogenannte KV-Diagramm nutzen.

3. Beispiel

Wir werden diesen Algorithmus nun anhand der folgenden Wahrheitstafel nachvollziehen: $$ \begin{array}{|c|c|c|c|}\hline A&B&C&Out \\\hline 0&0&0&1 \\\hline 0&0&1&0 \\\hline 0&1&0&0 \\\hline 0&1&1&0 \\\hline 1&0&0&1 \\\hline 1&0&1&1 \\\hline 1&1&0&1 \\\hline 1&1&1&0 \\\hline \end{array} $$
Im ersten Schritt werden die Zeilen identifiziert, in denen in der Output-Spalte eine \(0\) stehen. Das sind die Zeilen \(2,3,4\) und \(8\).
  • Um in der \(2.\) Zeile überall eine \(0\) stehen zu haben, muss \(C\) negiert werden. Wir bilden den Maxterm also durch \(A\vee B\vee \overline{C}\).
  • Um in der \(3.\) Zeile überall eine \(0\) stehen zu haben, muss \(B\) negiert werden. Wir bilden den Maxterm also durch \(A\vee \overline{B}\vee C\).
  • Um in der \(4.\) Zeile überall eine \(0\) stehen zu haben, müssen \(B\) und \(C\) negiert werden. Wir bilden den Maxterm also durch \(A\vee \overline{B}\vee \overline{C}\).
  • Um in der \(8.\) Zeile überall eine \(0\) stehen zu haben, müssen \(A,B\) und \(C\) negiert werden. Wir bilden den Maxterm also durch \(\overline{A}\vee \overline{B}\vee \overline{C}\).
Diese Maxterme werden nun durch das logische Und miteinander verknüpft und man erhält so die KNF für die gegebene Wahrheitstafel. $$(A\vee B\vee \overline{C}) \wedge (A\vee \overline{B}\vee C) \wedge (A\vee \overline{B}\vee \overline{C}) \wedge (\overline{A}\vee \overline{B}\vee \overline{C}) $$

Kommentar schreiben

Kommentare: 0