Frage zu Substitution (das mit den Hypercubes)

Also irgendwie werd ich nicht schlau draus... hab das Verstehen, warum das so geht wies zu gehn scheint aber mittlerweile aufgegeben, daher fänd ichs cool, wenn mir jemand bestätigt, dass ich den Algorithmus aus den Folien richtig abgeleitet habe:

1. bestimme ON(f)
2. bestimme DC(g), also die Stellen im Hypercube, bei denen das Ergebnis der Fkt. g != der letzten Position _ (x1,x2,x3,_) ist

3. finde Minimale Überdeckung (Primimplikanten?) wobei
-die Elemente aus ON(f), die auch in DC(g) sind nicht betrachtet werden müssen, aber dürfen (um z.B. einen kleineren Implikanten zu finden)
-nicht alle Elemente der Menge DC(g) überdeckt werden müssen
-auf jeden Fall alle Elemente von ON(f), die nicht in DC(g) sind überdeckt werden müssen

Ausserdem fänd ichs gut, wenn jemand, der in der ÜG mitgeschrieben hat oder das selbst gerechnet hat, die Lösungen der Aufgabe 1c vom Blatt 3 posten könnte - meine eigenen Mitschriebe sind irgendwie inkonsistent...

Und schließlich noch: Wenn sowas in der Klausur drankommen sollte, bekommen wie Hypercube Vordrücke? Und welche Farben darf man benutzen beim Malen?


viele Grüße,
Dosn

dosn Wrote:
-------------------------------------------------------
> Also irgendwie werd ich nicht schlau draus... hab
> das Verstehen, warum das so geht wies zu gehn
> scheint aber mittlerweile aufgegeben, daher fänd
> ichs cool, wenn mir jemand bestätigt, dass ich den
> Algorithmus aus den Folien richtig abgeleitet
> habe:

Joah, das ist im grobem das, was der Algorithmus macht.

> Ausserdem fänd ichs gut, wenn jemand, der in der
> ÜG mitgeschrieben hat oder das selbst gerechnet
> hat, die Lösungen der Aufgabe 1c vom Blatt 3
> posten könnte - meine eigenen Mitschriebe sind
> irgendwie inkonsistent...

Mit dem o.b. Vorgehen müsste es doch machbar sein, seine Mitschriebe zu rekonstruieren, will heißen: neu zu rechnen. Dann die Ergebnisse hier posten und dann mal gucken/auf Feedback warten, ob die richtig sind. Ich glaub, der Lerneffekt ist so rum größer.

> Und schließlich noch: Wenn sowas in der Klausur
> drankommen sollte, bekommen wie Hypercube
> Vordrücke? Und welche Farben darf man benutzen
> beim Malen?

Aller Wahrscheinlichkeit nach alles außer rot und grün (und ähnliche Farben... orange, oliv, terracotta-gold etc.), sowieso natürlich auch keinen Bleistift.
Man könnte aber auch versuchen andere Lösungswege zu benutzen (über Funktionstabelle, KV-Diagramme), so dass man erst gar nicht in die Verlegenheit kommt, Farben zu benutzen.

Grüße,
Sven

Ok, also ich hab mich mal dran versucht, dabei ist sind mir 2 Sachen aufgefallen:

1. man kann wohl nicht immer kleiner werden (irgendwie auch logisch)
2. f_2 und f_3 lassen sich auch so schon verkleinern (?)

Also meine Ergebnisse (g bezeichnet die jeweils 2.fkt, also nach dem "mit"):

f1 mit f2: keine Verbesserung, ursprgl. fkt --> Kosten 6
f1 mit f3: g' + x1x2 --> Kosten 3
f2 mit f1: x1x2' + x2x3' --> Kosten 4
f2 mit f3: wie oben
f3 mit f1: g' + x1x2 --> Kosten 3
f3 mit f2: x3' + x1'x2' + x1x2 --> Kosten 5

Falls das stimmen sollte... f3 mit f1 ist symmetrisch zu f1 mit f3 --> zufall? oder immer so? Und irgendwie dreht man sich da ja im kreis, also fürn Teil d) wo man das dann realisisern soll?!

Insgesamt Also Kosten... 10? oder 12, wenn man die normale Minimierung von f3 macht?

Verwirrt,
Dosn

dosn Wrote:
-------------------------------------------------------
> 1. man kann wohl nicht immer kleiner werden
> (irgendwie auch logisch)

Jap, hängt natürlich von den Funktionen ab, ob man sie mit Hilfe dieser Minimierung verkleinern kann. Man sollte aber immer mindestens eine Lösung finden, die genausogut ist, wie die Originalfunktion.


> 2. f_2 und f_3 lassen sich auch so schon
> verkleinern (?)

Ja, in dem Beispiel waren die Funktinen f_2 und f_3 nicht minimiert. Die Aufgabe bestand hier aber darin diese Funktion mit Hilfe der zweistufigen Logikminimierung zu verbessern. Ich denke in der Klausur werden die Aufgaben nicht so spitzfindig/zweideutig.


> Also meine Ergebnisse (g bezeichnet die jeweils
> 2.fkt, also nach dem "mit"):

sind alles mögliche Lösungen - gibt für einige Funktionen mehrere minimale Lösungen.
Wobei man für f_1 mit f_2 und die f_2-Funktionen die zweistufigen Lösungen noch finden sollte, auch wenn sie schlechter sind. Aber wie gesagt, ich denke in der Klausur werden die Funktionen schon so gestellt sein, dass derartige Lösungen nicht auftauchen.
Zu f3_f2 gibt es auch noch eine zweistufige Lösung, die genauso gut ist, wie die hier angegebene.

> Falls das stimmen sollte... f3 mit f1 ist
> symmetrisch zu f1 mit f3 --> zufall? oder immer
> so?

Ist wohl eher Zufall. Die Funktionen sind halt zufällig so gewählt, dass diese Symmetrie zustande kommt. Im allgemeinen Fall ist dies nicht immer so. Man sollte hier z.B. für f_1 mit f_2 und f_2 mit f_1 eine derartige Symmetrie nicht vorfinden.


> Und irgendwie dreht man sich da ja im kreis,
> also fürn Teil d) wo man das dann realisisern
> soll?!

Eine Lösung bei der man sich im Kreis dreht ist nicht zulässig/möglich. Man kann sich das einfach mal aufmalen, wie das auszusehen hätte - man sollte schnell feststellen, dass dies nicht nur verwirrend ist, sondern auch unmöglich zu realisieren.

> Insgesamt Also Kosten... 10? oder 12, wenn man die
> normale Minimierung von f3 macht?

Ja, mach doch mal ein paar konkrete Lösungsvorschläge, die möglichst nur Funktionen enthält, die mit Hilfe der zweistufigen Logikminimierung entstanden sind (d.h. Lösungen, die nicht aus einfaches minimieren der Funktionen f_2 und f_3 entstanden sind) und Kosten, wie in der Aufgabenstellung verlangt, nicht mehr als 15 hat.


Grüße,
Sven

F1 = f1^f3; cost(F1) = 3
F2 = f2; cost(F2) = 6
F3 = f3^f1; cost(F3) = 3
cost(F1+F2+F3) = 12

stimmt das so?

Nostradamus Wrote:
-------------------------------------------------------
> F1 = f1^f3; cost(F1) = 3
> F3 = f3^f1; cost(F3) = 3

Das ist genau der Fall, der oben beschrieben ist. Das geht ausdrücklich NICHT.

Nehme man z.B. f1^f3. Wie sieht dort die Funktion f3 aus mit deren Hilfe man ja f1 ausdrückt? Naja, f3 drückt man ja aus mit f3^f1. Man setze für f3 also f3^f1 ein. Nun das Problem: jetzt hat man plötzlich wieder f1 in der eingesetzten Funktion f3^f1. Und wie sieht f1 aus? Naja, hat man mittels f1^f3 gekürzt... man ist wieder am Beginn. Das setzt sich rekursiv fort. Man drückt f1 mit f3 und f3 mit f1 aus. Am Ende bleibt die berühmte Huhn-Ei-Frage: wo ist der Ursprung? Bei f1 oder f3? Ist das klar, warum das nicht geht?
Muss irgendwie anders gehen... und es geht auch anders.

Grüße,
Sven

Nur nochmal zur Sicherheit,
man darf eine Funktion (bspw. F1) nicht "abdecken"
wenn die Funktion mit der man sie abdeckt (bspw. F2)
selbst durch die zu abdeckende Funktion (F1) abgdeckt
wird?
Soweit hab ich das denke ich verstanden. Was ist nun,
wenn wir denn Fall hätten:
(1)
F1 = f1^f2;
F2 = f2^f3;
F3 = f3^f1;
oder analog
(2)
F1 = f1^f3;
F2 = f2^f1;
F3 = f3^f2;
setzt sich dass ganze dann fort? Also da wir bspw. F1 (aus 1)
durch mit Hilfe von f2 abdecken (dazu wiederum f3 benötigen
(und für f3 wiederum f1)), dass das gar nicht geht?
Denn schließlich minmieren wir das F1 letztlich wieder mit F1?
Stimmt das so, oder überhaupt gar nicht?

Könnte man sagen es darf kein Zykle entstehen?