0 Daumen
19 Aufrufe

Ich beschäftige mich gerade mit OBDD's und bin beim lesen eines Vorlesungskripts auf die Anzahl der Eingaben z gestoßen für die eine boolsche Funktion, realisiert in einem OBDD, den Funktionswert 1 annimmt. Für den Startknoten ist diese Anzahl z = 2^n, also es existieren 2^n Belegungen für die Quelle.

Meine Frage ist dann daher wie man jetzt die Anzahl der Eingaben berechnet die man dann an der Einssenke mit dem Funktionswert 1 abliest. Da steht man soll wenn man einen Knoten zum ersten Mal betritt mit z Eingaben, zu den Anzahlen seiner beiden Nachfolger jeweils z/2 hinzuaddieren und dann an der Einssenke die Eingaben ablesen, die den Funktionswert 1 erzeugen. Die Anzahl der Eingaben der Knoten halbieren sich ja von oben nach unten.

Habe selber versucht bei einem Beispiel OBDD von oben nach unten mich durchzuarbeiten und die Eingaben jeweils zu notieren und zu berechnen aber iwie komme ich auf Zahlen wie 12 oder 16 obwohl offensichtlich anhand einer Wahrheitstabelle 5 Belegungen bzw Eingaben den Funktionswert 1 annehmen

Wie würde man jetzt für diese Beispielfunktion die Eingaben z berechnen, die den Funktionswert 1 annehmen?

IndexxyzFunktion f_bsp
00001
10010
20100
30110
41001
51011
61101
71111


LG

mike

von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community