Eindeutigkeit von KNF bzw. DNF - Suche Beweis

Wissenschaft Informatik
#1

Hallo,
ich bin auf der Suche nach einem Beweis für die Eindeutigkeit der disjunktiven /bwz. konjunktiven Normalform.
Eine plausible Begründung würde mir auch genügen, wer kann mir (möglichst schnell) weiterhelfen??

Gruß,
Patricia

#2

Bitteschön
Hallo,

die Begriffe „Konjunktive NF“ bzw. „Disjunktive NF“ werden nicht einheitlich verwendet. Oft wird eine Formel bereits als in KNF vorliegend bezeichnet, wenn sie aus einer Konjunktion von Disjunktionen von Literalen besteht, für die DNF entsprechend. In diesem Fall sind KNF und DNF nicht eindeutig. Stattdessen gibt es dann den Begriff der kanonischen KNF bzw. DNF, die eindeutig ist.

Eine aussagenlogische Formel, die n verschiedene Atome A1,…,An enthält, liegt in (kanonischer) KNF [DNF] vor, wenn jede der einzelnen Disjunktionen [Konjunktionen] alle n Atome genau einmal als positives oder negatives Literal enthält.

Diese Form ist deshalb eindeutig, weil sie die Wahrheitstabelle der Funktion direkt (KNF) oder indirekt (DNF) angibt. Beispiel (ohne tieferen Sinn):

Gegeben sei eine aussagenlogische Funktion f(A1,A2,A3) durch folgende Wertetabelle:

A<sub>1</sub> A<sub>2</sub> A<sub>3</sub> f(A<sub>1</sub>,A<sub>2</sub>,A<sub>3</sub>)
0 0 0 0
0 0 1 1 (\*)
0 1 0 1 (\*)
0 1 1 0
1 0 0 1 (\*)
1 0 1 0
1 1 0 1 (\*)
1 1 1 1 (\*)

Die KNF erhalten wir direkt aus den mit (*) markierten Zeilen, in denen die Funktion wahr wird:

(~A<sub>1</sub>~A<sub>2</sub>A<sub>3</sub>) + (~A<sub>1</sub>A<sub>2</sub>~A<sub>3</sub>) + (A<sub>1</sub>~A<sub>2</sub>~A<sub>3</sub>) + (A<sub>1</sub>A<sub>2</sub>~A<sub>3</sub>) + (A<sub>1</sub>A<sub>2</sub>A<sub>3</sub>)

Die DNF erhalten wir, indem wir die KNF für die negierte Funktion bilden und negieren. Anders gesagt: wir bilden eine KNF aus den Zeilen, in denen die Funktion falsch wird und schreiben ein ‚~‘ davor:

~( (~A<sub>1</sub>~A<sub>2</sub>~A<sub>3</sub>) + (~A<sub>1</sub>A<sub>2</sub>A<sub>3</sub>) + (A<sub>1</sub>~A<sub>2</sub>A<sub>3</sub>) )

Ausrechnen ergibt die DNF

(A<sub>1</sub> + A<sub>2</sub> + A<sub>3</sub>)(A<sub>1</sub> + ~A<sub>2</sub> + ~A<sub>3</sub>)(~A<sub>1</sub> + A<sub>2</sub> + ~A<sub>3</sub>)

Damit ist klar, daß die DNF bzw. KNF einer Formel eindeutig sein muss, denn zwei verschiedene KNF bzw. DNF über der gleichen Menge von Atomen beschreiben zwei verschiedene Wahrheitstabellen, also zwei verschiedene Funktionen.

Uff, jetzt hoffe ich aber auch, dass das weiterhilft…

Gruß, Ralf