Disjunktive Normalform

10.04.2011, 13:56	Sorex	Auf diesen Beitrag antworten »
Disjunktive Normalform Meine Frage: Gegeben ist folgende Wahrheitstabelle: a 0 0 0 0 1 1 1 1 b 0 0 1 1 0 0 1 1 c 0 1 0 1 0 1 0 1 f(a,b,c) 0 1 0 0 1 0 1 0 Jetzt zu meiner Frage: Wie kommt man auf die Werte der Zeile f(a,b,c)? Meine Ideen: Steh momentan total auf dem Schlauch und hab so gar keine Ahnung wie ich an die Sache rangehen könnte. Wär für eine möglichst anfängerfreundliche Erklärung sehr dankbar ;-D MfG Sorex
11.04.2011, 10:47	Hubert1965	Auf diesen Beitrag antworten »
Ich interpretiere 0 als falsch und 1 als wahr. Falls es andersherum gemeint war (0=wahr, 1=falsch) musst du eben den Input vorher mit "nicht" verknüpfen, und dann den Output ebenfalls. Die Lösung heißt: Anschauen und Zusammenhänge suchen. Mir fällt z.B. auf, dass die letzten vier Werte der Funktion (1010) genau der Negation von c entsprechen. Und die letzten vier Werte sind genau jene Positionen, wo a gleich 1 ist. Das kann man schon mal so formulieren: Wenn a, dann nicht-c Wenn man das mal hat, und diesen Ansatz weiterverfolgen will, muss man noch den "sonst"-Zweig von "wenn a" behandeln. Also schauen wir uns die ersten vier Spalten der Wahrheitstabelle an: Da fällt mir auf, dass f(a,b,c) nur einmal 1 aber dreimal 0 enthält. Das trifft auch auf eine UND-Verknüpfung zu. Aber bei "b UND c" würde die 1 an einer anderen Stelle stehen (nämlich innder vierten Spalte). Kann man das irgendwie an die richtige Stelle rücken? Ja, man kann: Man muss dafür sorgen, dass zwei Werte so verknüpft werden, dass in der zweiten Spalte zwei Einsen zusammentreffen, sonst aber nirgendwo. Das ist genau dann der Fall, wenn ich statt "b" "nicht-b" in die Und-verknüpfung einsetze. Also: nicht-b UND c Jetzt beide Teile zusammen: Wenn a, dann nicht-c, sonst (nicht-b UND c) Eigentlich wäre das schon die fertige Lösung, aber in der Schule wird die wenn-dann-Konstruktion nicht immer anerkannt. Da will man meist irgendetws haben, das nur aus UND, ODER und NICHT besteht. Dabei hilft diese Formel: Wenn a, dann X, sonst Y = (a UND X) ODER (nicht-a UND Y) Jetzt nur noch in X und Y unsere gefundenen Zusammenhänge einsetzen: Wenn a, dann nicht-c, sonst (nicht-b UND c) = (a UND nicht-c) ODER (nicht-a UND (nicht-b UND c)) bzw mit den richtigen Zeichen: $\begin{eqnarray} f(a,b,c) = (a \land \neg c) \lor (\neg a \land (\neg b \land c)) \end{eqnarray}$ Diese Lösung kann man vielleicht noch vereinfachen, indem man mit de-Morgan drüberfährt oder andere Äquivalenzregeln anwendet, aber sie ist auf jeden Fall schon mal richtig.
11.04.2011, 12:06	Roman Oira-Oira	Auf diesen Beitrag antworten »
Das, was Hubert geschrieben hat, wird wohl korrekt so sein (ich habe es im Detail nicht überprüft). Es scheint mir allerdings zu viel "Überlegung" auf den einzelnen Fall dabei zu sein. Ich gehe solche Aufgaben immer rein mechanisch an, ohne viele Einzelüberlegung. Du nennst ja selbst in der Überschrift den entsprechenden Hinweis: Erstelle die disjunktive Normalform! Du kannst die disjunktive Normalform rein mechanisch aufstellen, in dem Du nur die Spaltenkombinationen von $\begin{eqnarray} a, b, c \end{eqnarray}$ betrachtest, die zum Ergebnis $\begin{eqnarray} f(a,b,c)=1 \end{eqnarray}$ führen. Nun schreibst Du eine Konjunktion auf, in der für jede $\begin{eqnarray} 1 \end{eqnarray}$ in der Spalte die entsprechende unveränderte Variable verwendet wird, und für jede $\begin{eqnarray} 0 \end{eqnarray}$ die negierte Variable. Dies machst Du für jede Spalte, die zum Ergebnis $\begin{eqnarray} 1 \end{eqnarray}$ führt und verbindest die Konjunktionen zu einer Disjunktion. Beispiel für die ersten beiden Spalten mit Ergebnis $\begin{eqnarray} 1 \end{eqnarray}$ (von links nach rechts): Spalte 2: $\begin{eqnarray} (a,b,c) = (0,0,1) \end{eqnarray}$ führt zu $\begin{eqnarray} (\overline{a} \wedge \overline{b} \wedge c) \end{eqnarray}$ Spalte 5: $\begin{eqnarray} (a,b,c) = (1,0,0) \end{eqnarray}$ führt zu $\begin{eqnarray} (a \wedge \overline{b} \wedge \overline{c}) \end{eqnarray}$ Dies führt zur Disjunktion $\begin{eqnarray} (\overline{a} \wedge \overline{b} \wedge c) \vee (a \wedge \overline{b} \wedge \overline{c}) \end{eqnarray}$ Und so weiter, für jede Spalte, die zum Ergebnis $\begin{eqnarray} 1 \end{eqnarray}$ führt. Je nach Aufgabenstellung kannst Du dann die disjunktive Normalform weiter vereinfachen bzw. umformen, indem Du die Dir bekannten Rechenregeln der boolschen Algebra anwendest (z.B. Regeln nach de'Morgan, Distributivgesetze, etc.).

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »