DNF / KNF bei einer Tautologie < Aussagenlogik < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:07 Di 07.08.2012 | | Autor: | Lunatikz |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo,
Erstmal vorab, es geht hier um keine Hausaufgabe oder ähnliches..
Meine Frage lautet, wie die Darstellung einer Tautologie in minimaler KNF ist.
Folgendes Szenario: Ich habe eine Funktion, welche eine Tautologie ist, daraus folgt dass das Komplement leer sein muss.
Die DNF lautet also TRUE..
um die dnf in eine eine knf umzuwandeln, kann ich ja true einfach negieren, so dass es false ist.
aber ist das wirklich richtig ?
Der hintergund hinter dem ganzen, ist die aussagenlogische minimierung..also ich hab ein programm geschrieben, welches den Espresso algorithmus simuliert, zusätzlich wandele ich das Ergebnis des Algorithmus (binäre kodierung von variablen) in eine logische Formel um.
wenn ich nun eine minimale knf bilden will.. erhalte ich als ergebnis eine sum-of-prodcuts expression..als ergebnis in sop erhalte ich false.
diese muss per de morgan in eine products-of-sum expression (knf) umgewandelt werden, was aber wiederum true zurück gibt.
kurz gesagt, wenn ich eine tautologie als funktion habe, erhalte ich als minimale dnf true, und als minimale knf auch true.. aufgrund der umwandlung der formen der aussagen.. aber das kann doch nicht richtig sein oder ?
|
|
| |
|
Hi,
Wie ist bei dir eine KNF definiert?
Falls eine KNF bei dir [mm]L=l_1\wedge l_2 \wedge \ldots \wedge l_k[/mm] mit Literalen [mm]l_i = y_1 \vee \ldots \vee y_j[/mm] und atomaren [mm]y_i\in \{x_1,\neg x_1,\ldots x_m,\neg x_m\}[/mm] ist.
So wäre eine Tautologie offensichtlich [mm](x\vee \neg x)[/mm]. Das hängt aber auch sehr stark von deiner Art die KNF zu definieren ab. Ich habe auch schon gesehen, dass manche in einem Literal stets paarweise verschiedene [mm]x_i,\neq x_i[/mm] nur zulassen. Da geht es dann nicht.
Manch einmal für man auch ein Symbol "1" ein. Dann wäre die KNF 1.
> kurz gesagt, wenn ich eine tautologie als funktion habe,
> erhalte ich als minimale dnf true, und als minimale knf
> auch true.. aufgrund der umwandlung der formen der
> aussagen.. aber das kann doch nicht richtig sein oder ?
Oben ist bei mir auch die minimale KNF die minimale DNF.
> Der hintergund hinter dem ganzen, ist die aussagenlogische
> minimierung..also ich hab ein programm geschrieben, welches
> den Espresso algorithmus simuliert, zusätzlich wandele ich
> das Ergebnis des Algorithmus (binäre kodierung von
> variablen) in eine logische Formel um.
Da bin ich überfragt. Hoffe trotzdem, dass sich das Problem geklärt hat.
Gruß
wieschoo
|
|
|
|
