Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
2 Fragen zu OBBDs
Und zwar geht es um die OTRS Klausur vom 6.10.00
Aufgabe 7
Z=ba + c + de*(a*b)
a) Nehmen sie als Variablenordnung die Reihenfolge des Auftauchens in dem AUsdruck an. Ist mit dieser Ordnung ein OBDD erstellbar? Begründen sie ihre Antwort!
Isch 'abe keine Ahnung…
d) Erläutern sie in kurzen Worten, wann und warum ein ROBDD günstig für die Darstellung boolscher Funktiuonen ist. Unter welchen Umständen wir die Darstellung mit ROBDD ungünstig?
Also den ersten Teil sollte ich noch irgendwie hinbekommen (optimiert, kanonisch&Sparsam, blabla…) aber wann wird die Darstellung ungünstig?
Wäre wirklich nett, wenn mir das mal jemand erklären könnte, ich schau mir das jetzt schon zum dritten Mal an, und hab immer noch keinen Plan…
[edit: Nachdem ich mich mal durch Yves Skript gewühlt habe, habe ich wenigstens mal zwei Fragen weniger, der Rest interessiert mich aber immernoch…]
Achja, noch eine Frage:
Dieses verf**** Äquivalenzzeichen, ich verstehe schon was das heisst, aber irgendwie hab ich keine Ahnung, was das in einer Schaltfunktion zu suchen hat?
ist das:
= ! 0 1
–±----
0 ! 1 0
1 ! 0 1
die Wahrheitstafel von Äquivalenz? Das wäre dann ja XNOR, oder?
wenn dann nxor 
aber ja. das ist äquivalenz 
quasi gleichheit… äquivalenz stell ich mir immer genre durch modolu-rechnungen vor:
2 = 4 (mod 2)
also, hier mal meine 2 cents:
ich wuerde sagen: jein. wenn man den ausdruck nicht veraendern darf, ist das nicht moeglich, weil man dann die ordnung b, a, c, d, e haette und man beim 3. ausdruck am schluss dann das ab nicht mehr pruefen koennte.
wenn man veraendern darf, kann man den 3. teil einfach weglassen, weil dafuer ja schon mal ab noetig ist und dieses ja schon in der 1. konjunktion abgeprueft wird - dann sind die werte von e und d egal!
da habe ich auch k. a… lustigerweise verstehe ich noch nicht mal, warum robdds kanonisch sind! sparsam und optimiert ist klar, aber kanonisch hatte ich gedacht sind minterme, d. h. jede variable muss genau einmal pro term vorkommen. das ist aber bei den robbds nicht der fall. vielleicht kann mir jemand helfen?!
ja, das ist sie! und eem hat recht, das waere not(xor), wobei das doch viel zu kompliziert ist. der ausgang dieser schaltfunktion ist genau dann gleich 1, wenn entweder beide eingaenge gleich 0 oder beide eingaenge gleich 1 sind - wenn sie eben gleich sind (–> aequivalenz)! verstanden?
hth,
-steppenwolf
[QUOTE]ich wuerde sagen: jein. wenn man den ausdruck nicht veraendern darf, ist das nicht moeglich, weil man dann die ordnung b, a, c, d, e haette und man beim 3. ausdruck am schluss dann das ab nicht mehr pruefen koennte.
wenn man veraendern darf, kann man den 3. teil einfach weglassen, weil dafuer ja schon mal ab noetig ist und dieses ja schon in der 1. konjunktion abgeprueft wird - dann sind die werte von e und d egal! [/QUOTE]
Ja, aber eine Konjunktion ist doch eigentlich distributiv, oder? Dann wäre ja schon ein OBDD möglich.
Sorry, hab mich ungünstig ausgedrückt, ROBDDs erlauben eine kanonische Darstellung einer Funktion, dh es gibt nur eine Möglichkeit ein ROBBD zu erstellen.
(Falls ich das jetzt richtig verstanden habe, aber so stehts zumindest in dem Script von Yves)
Achja, und es heisst XNOR (eXclusiveNOR) und nicht NXOR 
du sprichts in raetseln g! was willst du damit sagen, dass eine konjunktion distributiv ist? ich weiss bloss, dieser term ist eine disjunktion aus konjunktionen …
ich habe mich auch noch mit anderen leuten etwas besprochen und wir sind zu dem schluss gekommen, dass jeder boolesche ausdruck als (r)obdd mit jeder variablenordnung darstellbar ist - er wird halt nur entsprechend kompliziert bei unguenstiger ordnung? andere meinungen?
es heisst auf jeden fall aus nxor - xor hat die ergebnisse 0 1 1 0, das ganze durch not invertiert = 1 0 0 1 - eben genau die wertetabelle der aequivalenzoperation. dein exclusivenor hab ich immer noch nicht verstanden, ist aber auch egal…
Aaaalsooo…
zuerstmal @robert, ist das nicht MEIN skript, sondern nach wie vor dal cin’s. ich hab seins nur in EINE pdf-datei zusammengefasst und ein paar ganz wenige rechtschreib- und layoutfehler korrigiert. fällt imo aber gar nicht weiter auf 
dann @steppenwolf, ist ja nur die reihenfolge bestimmt, mit der du die variablen prüfen musst. also prüfst du zuerst b, dann a, dann c, d, e. und wenn du die werte für b und a einmal angenommen hast, gelten die ja auch für nochmalige vorkommen dieser variablen woanders im term. also musst du das (a*b) später gar nicht mehr extra prüfen, weil du’s ja vorher schon festgelegt hast. ok?
also lässt sich das teil sehr wohl als OBDD darstellen. wie übrigens alles, glaub ich…
und hört bitte auf, euch über {X|N}OR zu streiten… es gibt beide nicht, es gab sie noch nie und ihr werdet sie bestimmt auch nicht erfinden. :rolleyes:
@Steppenwolf, ich wollte nur sagen, dass ein Produktterm (ba) auch (ab) geschrieben werden kann, aber ist eh egal, inzwischen hab ich die ROBDDS kapiert, am Anfang hab ich nur alles versucht nach dem Schema im Script zu machen… (=> Grosser Fehler…)
PS: Es heisst XNOR, so stehts zumindest im “Logic and Computer Design Fundamentals” 
Also würdest Du den Ausdruck umstellen, dann kannst Du aber die Variablenordnung nicht mehr exakt einhalten. Meiner Meinung nach kannst du das OBDD nur bis zu (ab) aufstellen. Also ich denke Du kannst es nicht mit der gegeben Variablenordnung aufstellen.
Hmmm, also wenn man sich einfach mal die gegebene Variablenordnung ganz stur hinschreibt:
b < a < c < d < e < a < b
Nach dieser Variablenordnung kannst du kein OBDD aufstellen, da z.B. a nicht gleichzeitig kleiner und größer sein kann als c (oder d,e).Gleiches gilt für b
Würde es allerdings heißen:
b < a < c < d < e
dann ginge es ohne probleme!
Yepp, aber die Ordnung heist b<a<c<d<e, weil mehrfach auftretende Variablen nicht gezählt werden, du entwickelst ja gleich am Anfang nach b und dann nach a, also sind die hinten auch weg.
Also ein OBDD ist auf jeden Fall machbar, einzig am Aufwand macht sich die Ordnung bemerkbar.