VNF, DNF und KNF < Technische Inform. < Praktische Inform. < Hochschule < Informatik < Vorhilfe
|
Hallöchen 
Ich hätte da noch eine Frage.. ich soll eine Formel in DNF (KNF) bringen... Also VNF (die verneinte Normalform) habe ich so verstanden - hoffentlich richtig, daß sie nur die Operatoren [mm] \wedge [/mm] bzw. [mm] \vee [/mm] enthalten und keinen Operator [mm] \to [/mm] oder [mm] \gdw...
[/mm]
Den Unterschied zu DNF und KNF bzw. habe ich nicht verstanden. Könnte mir da vielleicht jmd. auf die Sprünge helfen?
Herzlichen Dank
RoterBlitz
|
|
| |
|
Hallo RoterBlitz,
Bei der VNF kann ich dir nicht helfen aber zur DNF und KNF kann ich etwas beitragen.
> Den Unterschied zu DNF und KNF bzw. habe ich nicht verstanden. Könnte mir da vielleicht jmd. auf die Sprünge helfen?
Du kannst jede Boolesche Funktion in DNF oder KNF bringen, solange sie für mindestens einen Inputwert definiert ist (Ich denke, man könnte sich auch eine Funktion vorstellen, bei der in der Wertetabelle nur "don't cares" stehen, aber eine solche Funktion macht eigentlich eh wenig Sinn. ).
Sei also [m]f:\left\{ {0,1} \right\}^n \to \left\{ {0,1} \right\};\;f\left( {x_1 , \ldots ,x_n } \right) = y[/m] eine beliebige Boolesche Funktion, die für mindestens einen ihrer Werte definiert ist (kein "don't care"). Du mußt dir nun die Wertetabelle dieser Funktion betrachten. Alle Werte in der Tabelle, die 0 ergeben, bilden die Variablendarstellung in der KNF Form:
[m]f: = \left( {x_1 + \ldots + x_n } \right) \cdot \left( {x_1^{'} + \ldots + x_n^' } \right) \cdot \ldots \cdot \left( {x_1^{' \cdots '} + \ldots + x_n^{' \cdots '} } \right)[/m]
Dabei sollen die Striche bei den Variablen nur andeuten, daß hier verschiedene Fälle aus der Wertetabelle betrachtet werden sollen. Gilt z.B. für den Fall 101 für $n = 3: f(1,0,1) = 0, f(1,1,0) = [mm] 0\!$ [/mm] und sonst bei keinem anderen Fall in der Tabelle, so gilt [m]f: = \left( {\overline {x_1 } + x_2 + \overline {x_3 } } \right) \cdot \left( {\overline {x_1 } + \overline {x_2 } + x_3 } \right)[/m].
Bei der DNF (disjunktive Normalform) ist's genau umgekehrt:
[m]f: = x_1 \cdot \ldots \cdot x_n + x_1^{'} \cdot \ldots \cdot x_n^{'} + \ldots + x_1^{' \cdots '} \cdot \ldots \cdot x_n^{' \cdots '}[/m]. Sei z.B. $f(1,0,1) = 1, f(1,1,0) = [mm] 1\!$ [/mm] und sonst überall [mm] $\ne [/mm] 0$, dann gilt [m]f: = x_1 \overline {x_2 } x_3 + x_1 x_2 \overline {x_3 }[/m].
Viele Grüße
Karl
|
|
|
| |
|
Hi, nochmal..
ähh.. also ehrlich gesagt, mit Definitionen bin ich nicht so gut drauf ;-(
Ich habe folgendes Problem:
Folgende Formel ist in VNF, DNF und KNF umzuwandeln:
F = (A [mm] \vee \neg(B \wedge [/mm] C)) [mm] \to [/mm] (D [mm] \vee [/mm] E)
[mm] \equiv \neg( [/mm] A [mm] \vee \neg [/mm] (B [mm] \vee [/mm] C)) [mm] \vee [/mm] (D [mm] \vee [/mm] E) - versteh ich auch noch
[mm] \equiv (\neg [/mm] A [mm] \wedge \neg \neg [/mm] (B [mm] \wedge [/mm] C)) [mm] \vee [/mm] D [mm] \vee [/mm] E - wieso wird aus dem (A oder plötzlich ein A und??)
LÖSUNG F' = [mm] \equiv (\neg [/mm] A [mm] \wedge [/mm] B [mm] \wedge [/mm] C) [mm] \vee [/mm] D [mm] \vee [/mm] E
Frage1: wann weiß ich, wann die VNF erreicht ist und ich aufhören kann?
Frage2: Die Lösung F' ist gleichzeitig auch in DNF - woran erkenne ich das?
Frage3: Die Lösung für KNF ist folgende - wie erreiche ich das, was ist das Ziel, um die KNF zu erhalten, wann weiß ich, wenn ich "fertig" bin?
KNF = [mm] (\neg [/mm] A [mm] \vee [/mm] D [mm] \vee [/mm] E) [mm] \wedge [/mm] (B [mm] \vee [/mm] D [mm] \vee [/mm] E) [mm] \wedge [/mm] (C [mm] \vee [/mm] D [mm] \vee [/mm] E)
Danke und schönen Abend,
RoterBlitz
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 03:22 So 09.01.2005 | | Autor: | wluut |
Kuck mal, das habe ich bei http://de.wikipedia.org gefunden:
"Eine logische Formel ist in Negationsnormalform, falls die Negationsoperatoren in ihr nur direkt über atomaren Aussagen vorkommen."
Aha. Ich kannte die Bezeichnung VNF vorher auch nicht, aber die ist wahrscheinlich gemeint, oder?
Also:
[mm] $\neg(x\wedge [/mm] y)$ ist NICHT in VNF, weil das Negationszeichen VOR der Klammer steht. Um das Negationszeichen in die Klammer zu kriegen, braucht man De Morgan (Wichtige Regel, braucht man immer wieder!):
[mm] $\neg(x\wedge [/mm] y) [mm] \gdw \neg x\vee\neg [/mm] y$
Man beachte: Wenn man das "Nicht" in die Klammer zieht, drehen sich "Und" bzw. "Oder" um!
So gilt auch:
[mm] $\neg(x\vee [/mm] y) [mm] \gdw \neg x\wedge\neg [/mm] y$
So, aber weiter mit Wikipedia. Da steht nämlich auch noch:
"In klassischer Logik kann jede Formel in diese Form gebracht werden, indem man Implikations- und Äquivalenzoperatoren durch ihre Definitionen ersetzt, mit den De Morganschen Gesetzen die Negationen nach innen verschiebt und doppelte Negationen eliminiert. Eine Formel in Negationsnormalform kann in die stärkere konjunktive oder disjunktive Normalform gebracht werden, indem man die Distributivgesetze anwendet."
Na bitte, schon wieder De Morgan. Damit solltest du schon ganz gut mit den Formeln klarkommen.
Konkret:
> [mm]\F = (A \vee \neg(B \wedge C)) \to (D \vee E)[/mm]
> [mm]\equiv \neg( A \vee \neg (B \vee C)) \vee (D \vee E)[/mm] -
> versteh ich auch noch
> [mm]\equiv (\neg A \wedge \neg \neg (B \wedge C)) \vee D \vee E[/mm]
> - wieso wird aus dem (A oder plötzlich ein A
> und??)
De Morgan. Das Nicht wird in die Klammer gezogen, dadurch wird Oder zu Und.
> Frage1: wann weiß ich, wann die VNF erreicht ist und ich
> aufhören kann?
Wenn kein "Nicht" mehr vor einer Klammer steht, sondern nur noch direkt vor einer Variablen. (Und sonst nur noch "Und" und "Oder" vorkommen.)
> Frage2: Die Lösung F' ist gleichzeitig auch in DNF - woran
> erkenne ich das?
Definition der DNF. Siehe die obige Antwort.
Manchmal schreibt man auch + für "Oder" und $*$ für "Und", dann sieht eine DNF z.B. so aus:
(abc)+(de)+(f)+(ghij)
In den Klammern stehen nur "Und" (evtl. auch "Nicht"),
dazwischen nur "Oder"
KNF sieht z.B. so aus:
(a+b)(d+e+f+g)(h+i)
In den Klammern steht "Oder" (evtl. auch "Nicht"),
dazwischen nur "Und".
> Frage3: Die Lösung für KNF ist folgende - wie erreiche ich
> das, was ist das Ziel, um die KNF zu erhalten, wann weiß
> ich, wenn ich "fertig" bin?
Siehe oben.
Ich hoffe, das hilft dir ein bisschen. Wenn man sich dran gewöhnt hat, ist es meist gar nicht so schlimm.
n8
wluut
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:31 So 09.01.2005 | | Autor: | RoterBlitz |
Hallo!
Also ich muß ja sagen, ich bin total begeistert von diesem Forum, daß die Mithilfe so toll klappt!! Ich wünschte, ich bin auch bald so weit, daß ich andere Kollegen unterstützen kann.
LG,
RoterBlitz
|
|
|
|
