Beweise, dass KNF und DNF aus Wahrheitstafel konstruierbar sind.

Question

Zu beweisendes Theorem:

Ist die Wahrheitstafel einer Formel F gegeben, kann zu F eine KNF und DNF hergestellt werden:

-zu F äquivalente DNF: Jede Zeile der Wahrheitstafel mit Wert wahr trägt zu einem Disjunktionsglied bei. Die Literale dieser Konjunktion bestimmen sich wie folgt: Falls die Belegung von Ai,j in der betreffenden Zeile w ist, wo wird Ai,j als Literal eingesetzt, sonst nichtAi,j

-zu F äquivalente KNF: Vertausche im Verfahren für die DNF die Rollen von w und f sowie von Konjunktion und Disjunktion

Mein Beweis:

-für die DNF müssen die Wahrheitswerte der Variablen immer w sein
-alle Wahrheitswerte müssen zusammen nämlich w sein
-also ist die Negation von falschen Variablen nötig, um sie wahr zu bekommen

-für die KNF müssen die Wahrheitswerde der Variablen immer f sein
-alle Wahrheitsweite müssen zusammen nämlich f sein
-also ist die Negation von wahren Variablen nötig, um sie falsch zu bekommen

Stimmt mein Beweis so?

Answer 1

Muss da nicht noch ein Bezug zur Disjunktion ( eine Disjunktion ist nur dann

falsch, wenn alle Teilterme falsch sind.) und entsprechend zur Konjunktion mit rein ?

Comments

Hört sich gut an, ja