[TI] Musterklausuren: Frage zu OBDDs

[foogy]

Hi,
leider kann ich nicht zu den Frontalübungen, und habe daher nur eine Musterlösung kopieren können.
Kann mir jemand erklären, warum in der Klausur von 2002 in Aufgabe 12a) nur , und anzukreuzen sind, nicht aber ?

Denn laut OBDD spielt das in bestimmten Pfaden keine Rolle (ist also nicht eingezeichnet). führt aber hier ebenso zur 1 wie , der Unterschied ist hier nur, dass einmal 1 ist und einmal 0. Also ist es egal.

Was genau ist denn laut Aufgabenstellung mit "disjunktiver Darstellung" gemeint? Also wie ist die definiert, dass der eine Term drin vorkommt, der andere aber nicht? Würde man von der DNF sprechen, dann müsste mein fraglicher Term ja auch angekreuzt werden. Aber ist die DNF nicht auch selbst nur eine disjunktive Form?

Bei der 12b) ergibt sich ein analoges Problem.
Ist bestimmt ganz einfach und mir fehlt einfach nur die Begründung aus der Frontalübung.

Danke für die Hilfe!

[Pillenfresser]

führt aber hier ebenso zur 1 wie , der Unterschied ist hier nur, dass einmal 1 ist und einmal 0. Also ist es egal.

Nicht ganz richtig, denn ist in enthalten:


Die Fälle für und sind also zusammengefasst. Daher braucht man die in der disjunktiven Form auch nicht einzeln angeben, sondern kann den kleineren Term wählen.

Edit: 12 b) analog.

[foogy]

Ja das meinte ich eigentilch ("zusammengefasst").
Wäre es denn nach definition keine disjunktive Form mehr, wenn man trotzdem beide Terme angibt? Ich behaupte ja nicht, dass es sinnvoll ist, sowohl den längeren als auch den hier gleichwertigen kürzeren Term anzugeben.

[Pillenfresser]

Ich hab mal das Buch befragt:
Es wäre zwar theoretisch eine disjunktive Form, würde dann allerdings disjunktive Normalform (DNF) heißen (jeder Term ist ein Minterm / jeder Term enthält alle Variablen). Jetzt kommt's:

"Die Terme einer beliebigen disjunktiven Form von enthalten im Allgemeinen weniger als Variablen."

Dabei geht's auch um Kostenminimierung.

Pauschal würde ich dir raten, die Terme so aufzuschreiben, wie sie im OBDD stehen. Wenn das auf dem Weg zur 1 nicht vorkommt, dann lass sie weg.

Ich hoffe, damit kannst du was anfangen.

[foogy]

Ja, dann werde ich das zu meiner eigenen Sicherheit wohl tun. Aber grundsätzlich ist mir die Formulierung zu schwammig und im Zweifelsfall würde ich da in der Einsicht heftigst gegen protestieren.
Denn meine DF hätte zumindest den einen Term ohne alle 3 Variablen und wäre somit keine DNF mehr.
Naja, belassen wir's dabei. Wollte nur wissen ob ich da total falsch mit liege. Danke!

[Stasik]

Es ist ja nicht nach der Normalform gefragt, oder?

[foogy]

ES ist ja nicht nach der Normalform gefragt, oder?

Richtig, es ist nach Termen gefragt, "die in der disjunktiven Darstellung der Funktion, die aus dem angegebenen OBDD ablesbar ist, vorkommen".
Ok, vielleicht kann man das damit begründen, dass x2 in diesem speziellen Pfad des OBDD nicht eingezeichnet ist. Letzendlich wurde es durch Vereinfachung rausgeworfen, da der Wert von x2 in diesem Pfad nicht relevant ist.

[AGo]

"die in der disjunktiven Darstellung der Funktion, die aus dem angegebenen OBDD ablesbar ist, vorkommen".

das ist genau der Punkt, wo es exakt formuliert ist. Keiner hat hier was von einer NF gesagt, geschweige denn das alle X enthalten sein müssen.
Ausnahmsweise kann man dem LS hier keine Vorwürfe machen, wir dürfen nur nicht soviel reininterpretieren (hatte den Fehler beim ersten mal auch gemacht)