KNF Vereinfachung < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:52 Mo 02.11.2009 | | Autor: | extasic |
| Aufgabe | Bilde die KNF ![[]](/images/popup.gif) dieser Funktion und minimiere sie mit den gültigen Umformungen so weit wie möglich. |
Die KNF habe ich direkt aus der Funktion abgelesen:
[mm] (x_1 [/mm] + [mm] x_2 [/mm] + [mm] x_3 [/mm] + [mm] x_4)(x_1 [/mm] + [mm] x_2 [/mm] + [mm] x_3 [/mm] + [mm] x_4')(x_1 [/mm] + [mm] x_2 [/mm] + [mm] x_3' [/mm] + [mm] x_4)
[/mm]
[mm] (x_1 [/mm] + [mm] x_2 [/mm] + [mm] x_3' [/mm] + [mm] x_4')$\\$(x_1' [/mm] + [mm] x_2 [/mm] + [mm] x_3 [/mm] + [mm] x_4')(x_1' [/mm] + [mm] x_2 [/mm] + [mm] x_3' [/mm] + [mm] x_4')
[/mm]
[mm] (x_1' [/mm] + [mm] x_2' [/mm] + [mm] x_3 [/mm] + [mm] x_4')(x_1' [/mm] + [mm] x_2' [/mm] + [mm] x_3' [/mm] + [mm] x_4')
[/mm]
Leider bin ich beim Vereinfachen nicht weiter gekommen. Mittels Vereinigung habe ich das ganze weiter zu vereinfachen. Da ich nicht weiter gekommen bin, habe ich es mit der DNF versucht und bin auf [mm] "x_2 [/mm] + [mm] x_4'" [/mm] gekommen, was auch gut aussieht.
Allerdings bekomme ich die KNF partout nicht in diese Form umgewandelt. Könnt ihr mir bitte hier weiterhelfen?
Danke im Voraus!
|
|
| |
|
Hallo exstasic,
ich komme mit Deiner Notation nicht klar.
Kannst Du das mal in diese übersetzen? Ich habe ernsthaft den Eindruck, dass sich das Problem damit schon löst.
In Deiner Notation - die ich anhand der Wertetabelle ja sinnvoll übersetzen kann, wenn ich Deine KNF damit vergleiche - stimmt aber die DNF nicht.
Dafür gilt (wieder unter Beibehaltung Deiner Notation) z.B.:
[mm] (x_1+x_2+x_3+x_4)(x_1+x_2+x_3+x_4')=x_1+x_2+x_3
[/mm]
Oder verstehe ich Dich doch völlig falsch?
lg
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:37 Di 03.11.2009 | | Autor: | extasic |
Erst einmal Danke für die Antwort!
> ich komme mit Deiner Notation nicht klar.
Die Notation stellt ein "+" für das logische "ODER" und ein "*" für das logische "UND".
> In Deiner Notation - die ich anhand der Wertetabelle ja
> sinnvoll übersetzen kann, wenn ich Deine KNF damit
> vergleiche - stimmt aber die DNF nicht.
> Dafür gilt (wieder unter Beibehaltung Deiner Notation)
> z.B.:
>
> [mm](x_1+x_2+x_3+x_4)(x_1+x_2+x_3+x_4')=x_1+x_2+x_3[/mm]
>
> Oder verstehe ich Dich doch völlig falsch?
>
das fürchte ich fast. Ich habe als DNF
[mm] x_1' x_2 x_3' x_4' [/mm] + [mm] x_1' x_2 x_3' x_4 [/mm] +
[mm] x_1' x_2 x_3 x_4' [/mm] + [mm] x_1' x_2 x_3 x_4 [/mm] +
[mm] x_1 x_2' x_3' x_4' [/mm] + [mm] x_1 x_2' x_3 x_4' [/mm] +
[mm] x_1 x_2 x_3' x_4' [/mm] + [mm] x_1 x_2 x_3 x_4'
[/mm]
und die vereinfacht zu [mm] "x_2 \vee \neg x_4". [/mm] Das war in der Aufgabe aber nicht gefordert, sondern ich habe es nur als Selbstkontrolle gemacht um zu sehen, wo ich hinkommen muss mit der vereinfachten KNF. Das Ergebnis kann man kontrollieren; es ist richtig (siehe Funktion).
Mir ist nicht ganz klar warum die Notation das Problem sein soll deiner Meinung nach. Wir müssen diese Notation verwenden, und auch in unserem Lehrbuch wird sie verwendet.
> Kannst Du das mal in diese übersetzen?
Die KNF in "deiner" Notation:
[mm] (x_1 \vee x_2 \vee x_3 \vee x_4)\wedge(x_1 \vee x_2 \vee x_3 \vee \neg x_4)\wedge
[/mm]
[mm] (x_1 \vee x_2 \vee \neg x_3 \vee x_4)\wedge(x_1 \vee x_2 \vee \neg x_3 \vee \neg x_4)\wedge
[/mm]
[mm] (\neg x_1 \vee x_2 \vee x_3 \vee \neg x_4)\wedge(\neg x_1 \vee x_2 \vee \neg x_3 \vee \neg x_4)\wedge
[/mm]
[mm] (\neg x_1 \vee \neg x_2 \vee x_3 \vee \neg x_4)\wedge(\neg x_1 \vee \neg x_2 \vee \neg x_3 \vee \neg x_4)
[/mm]
Siehst Du jetzt wo mein Fehler liegt bzw. wie ich die KNF so umwandeln kann, dass sie minimal wird?
|
|
|
| |
|
Hallo extasic,
> und die vereinfacht zu [mm]"x_2 \vee \neg x_4".[/mm] Das war in der
> Aufgabe aber nicht gefordert, sondern ich habe es nur als
> Selbstkontrolle gemacht um zu sehen, wo ich hinkommen muss
> mit der vereinfachten KNF. Das Ergebnis kann man
> kontrollieren; es ist richtig (siehe Funktion).
Bei deiner Minimalfunktion gilt [mm]m(0,0,0,0)=0+\bar{0}=0+1=1[/mm]. Das entspricht nicht dem [mm]f\![/mm] aus der Tabelle.
Tipp: Schreibe die Werte von [mm]f\![/mm] für [mm]x_1=0[/mm] und für [mm]x_1=1[/mm] nebeneinander statt untereinander. Stell' dir [mm]x_1[/mm] als einen "Umschalter" vor.
Die KNF kannst du mit Boolescher Algebra umwandeln. Ich würde dir raten am Anfang nach jedem (schwierigeren) Umformungsschritt den neuen Booleschen Term anhand einer Wertetabelle mit der ursprünglichen Wertetabelle abzugleichen, um jeden Rechenfehler sofort zu erkennen anstatt diesen dann später mühevoll suchen zu müssen.
Viele Grüße
Karl
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:39 Di 03.11.2009 | | Autor: | extasic |
Danke für Deine schnelle Reaktion!
> Bei deiner Minimalfunktion gilt [mm]m(0,0,0,0)=0+\bar{0}=0+1=1[/mm].
> Das entspricht nicht dem [mm]f\![/mm] aus der Tabelle.
>
> Tipp: Schreibe die Werte von [mm]f\![/mm] für [mm]x_1=0[/mm] und für [mm]x_1=1[/mm]
> nebeneinander statt untereinander. Stell' dir [mm]x_1[/mm] als einen
> "Umschalter" vor.
>
Wie meinst du das?
> Die KNF kannst du mit
> Boolescher Algebra
> umwandeln. Ich würde dir raten am Anfang nach jedem
> (schwierigeren) Umformungsschritt den neuen Booleschen Term
> anhand einer Wertetabelle mit der ursprünglichen
> Wertetabelle abzugleichen, um jeden Rechenfehler sofort zu
> erkennen anstatt diesen dann später mühevoll suchen zu
> müssen.
>
Das ist ja genau die Aufgabe und mein Problem. Und genau da bin ich ja nicht weitergekommen. Ich habe die Aufgabe mit TeX gemacht, also übersichtlich und ordentlich. Trotzdem komme ich auf keinen grünen Zweig, daher dieser Thread ;)
Irgenwelche Tipps wie ich die KNF (meine ist doch jetzt richtig, oder?) in die Minimalform bekomme? Wie es theoretisch geht ist mir klar, aber ich bekomme es praktisch nicht hin...
|
|
|
| |
|
Hallo extasic,
also entweder verwechselst Du KNF und DNF, oder Du verwechselt die Verwendung Deiner Notation. So, wie Du sie oben definiert hast, kenne ich sie auch. Dann aber kann ich mit Deinen beiden ausgeführten Normalformen nichts mehr anfangen, sie haben auch nichts mit der Wertetabelle zu tun, da bei beiden UND und ODER vertauscht sind.
Wenn Du das erstmal korrigierst, klappt sicher auch die Vereinfachung mittels Boolescher Algebra.
Karls Tipp, jede Umformung anhand der Wertetabelle zu überprüfen, kann ich dabei nur wärmstens unterstützen.
Viel Erfolg!
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:52 Di 03.11.2009 | | Autor: | extasic |
> Wenn Du das erstmal korrigierst, klappt sicher auch die
> Vereinfachung mittels Boolescher Algebra.
hmm, dann der nächste Versuch. Ich bilde die KNF:
[mm] (x_1 \vee x_2 \vee x_3 \vee x_4) \wedge (x_1 \vee x_2 \vee x_3 \vee \neg x_4)\wedge(x_1 \vee x_2 \vee \neg x_3 \vee x_4) \wedge(x_1 \vee x_2 \vee \neg x_3 \vee \neg x_4) \wedge(\neg x_1 \vee x_2 \vee x_3 \vee \neg x_4) \wedge(\neg x_1 \vee x_2 \vee \neg x_3 \vee \neg x_4) \wedge(\neg x_1 \vee \neg x_2 \vee x_3 \vee \neg x_4) \wedge(\neg x_1 \vee \neg x_2 \vee \neg x_3 \vee \neg x_4) [/mm]
Als ersten Schritt würde ich dann die Vereinigung anwenden:
[mm] (x_1 \vee x_2 \vee x_3)\wedge (x_1 \vee x_2) \wedge (\neg x_1 \vee x_2 \vee \neg x_4) \wedge (\neg x_1 \vee \neg x_2 \vee \neg x_4)
[/mm]
und gleich noch einmal:
[mm] (x_1 \vee x_2 \vee x_3)\wedge (x_1 \vee x_2) \wedge (\neg x_1 \vee \neg x_4) [/mm]
dann Absorption:
[mm] (x_1 \vee x_2)\wedge(\neg x_1 \vee \neg x_4)
[/mm]
und jetzt? kann ich das ganze noch weiter vereinfachen? ist meine Rechnung richtig?
|
|
|
| |
|
Hallo extasic,
> > Wenn Du das erstmal korrigierst, klappt sicher auch die
> > Vereinfachung mittels Boolescher Algebra.
>
> hmm, dann der nächste Versuch. Ich bilde die KNF:
>
> [mm](x_1 \vee x_2 \vee x_3 \vee x_4) \wedge (x_1 \vee x_2 \vee x_3 \vee \neg x_4)\wedge(x_1 \vee x_2 \vee \neg x_3 \vee x_4) \wedge(x_1 \vee x_2 \vee \neg x_3 \vee \neg x_4) \wedge(\neg x_1 \vee x_2 \vee x_3 \vee \neg x_4) \wedge(\neg x_1 \vee x_2 \vee \neg x_3 \vee \neg x_4) \wedge(\neg x_1 \vee \neg x_2 \vee x_3 \vee \neg x_4) \wedge(\neg x_1 \vee \neg x_2 \vee \neg x_3 \vee \neg x_4)[/mm]
Jetzt stimmt's. So kannst Du dann auch in Eurer Notation schreiben...
> Als ersten Schritt würde ich dann die Vereinigung
> anwenden:
>
> [mm](x_1 \vee x_2 \vee x_3)\wedge (x_1 \vee x_2 \red{\vee \neg x_3}) \wedge (\neg x_1 \vee x_2 \vee \neg x_4) \wedge (\neg x_1 \vee \neg x_2 \vee \neg x_4)[/mm]
Der rote fehlte noch. Dadurch wird's aber einfacher, weil Du den nächsten Schritt faktisch überspringst:
> und gleich noch einmal:
>
> [mm](x_1 \vee x_2 \vee x_3)\wedge (x_1 \vee x_2) \wedge (\neg x_1 \vee \neg x_4)[/mm]
>
...und dieser hier gar nicht mehr nötig ist:
> dann Absorption:
...weil direkt dieses herauskommt:
> [mm](x_1 \vee x_2)\wedge(\neg x_1 \vee \neg x_4)[/mm]
>
> und jetzt? kann ich das ganze noch weiter vereinfachen?
Du kannst es umformen und dadurch anders schreiben, aber nicht mehr kürzer.
> ist
> meine Rechnung richtig?
(s.o.)
lg
rev
|
|
|
|
![[]](http://img204.imageshack.us/img204/1328/funktion.png){kind=small}
dieser Funktion
