Die disjunktive Normalform (DNF)


1

1. Einführung

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

2. Wie liest man die DNF 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 DNF ausgibt. Der Algorithmus läuft in \(4\) einfachen Schritten ab:

Algorithmus: Wahrheitstafel in DNF überführen

Eingabe: Wahrheitstafel

Ausgabe: Aussagenlogische Formel in DNF

1. Markiere alle Einträge in der Tabelle, die eine \(1\) in der letzten Spalte haben.
2. Sorge durch die Negation dafür, dass in jeder markierten Zeile alle Spalten eine \(1\) steht.
3. Erzeuge aus den in Schritt \(1\) markierten Zeilen jeweils Minterme, indem du die alle Variablen, die ggf. negiert wurden, um überall eine \(1\) herauszubekommen, mit dem logischen Und verknüpfst.
4. Verknüpfe alle in Schritt \(3\) erzeugten Minterme durch das logische Oder. \(\diamond\)

Das Ergebnis des Algorithmus ist nicht zwangsläufig minial. 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 \(1\) stehen. Das sind die Zeilen \(1,5,6\) und \(7\).

1. Um in der \(1.\) Zeile überall eine \(1\) stehen zu haben, müssen \(A,B\) und \(C\) negiert werden. Wir bilden den Minterm also durch \(\overline{A}\wedge\overline{B}\wedge\overline{C}\).
2. Um in der \(5.\) Zeile überall eine \(1\) stehen zu haben, müssen \(B\) und \(C\) negiert werden. Wir bilden den Minterm also durch \(A\wedge\overline{B}\wedge\overline{C}\).
3. Um in der \(6.\) Zeile überall eine \(1\) stehen zu haben, muss \(B\) negiert werden. Wir bilden den Minterm also durch \(A\wedge\overline{B}\wedge C\).
4. Um in der \(7.\) Zeile überall eine \(1\) stehen zu haben, muss \(C\) negiert werden. Wir bilden den Minterm also durch \(A\wedge B\wedge\overline{C}\).

Diese Minterme werden nun durch das logische Oder miteinander verknüpft und man erhält so die DNF für die gegebene Wahrheitstafel. $$(\overline{A}\wedge\overline{B}\wedge\overline{C}) \vee (A\wedge\overline{B}\wedge\overline{C}) \vee (A\wedge\overline{B}\wedge C) \vee (A\wedge B\wedge\overline{C}) $$

 

Community Artikel, geschrieben vor 3 Wochen, 3 Tage
andré dalwigk, verified
Student, Punkte: 4206
 
Kommentar schreiben Diesen Artikel melden
0 Antworten