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?
Index | x | y | z | Funktion f_bsp |
0 | 0 | 0 | 0 | 1 |
1 | 0 | 0 | 1 | 0 |
2 | 0 | 1 | 0 | 0 |
3 | 0 | 1 | 1 | 0 |
4 | 1 | 0 | 0 | 1 |
5 | 1 | 0 | 1 | 1 |
6 | 1 | 1 | 0 | 1 |
7 | 1 | 1 | 1 | 1 |
LG
mike