Theoretische und technische Informatik - ganz praktisch - Letzte Fragen in BIN-AG

BDD Wahrheitstabelle bei Variablen "Wegfall"

Fri, 10 Feb 2017 17:24:20 +0000

Hallo,

Erstellt man das BDD und verkürzt es, so kann es ja sein, dass Variablen der unteren Äste "wegfallen", da sie nicht benötigt werden, weil sie bei jeder Eingabe auf das gleiche Element zeigen.

Nun ist die Frage: Sei eine Funktion f(a,b,c) und das c würde unter einem der beiden b's nicht mehr benötigt werden, ist der Wert dieses c's in der Wahrheitstabelle egal für f(a,b,c)=1 ?

(Bsp. Kap. BDD A18)

Binary Decision Diagram Aufgabe 20 b)

Fri, 10 Feb 2017 17:01:29 +0000

Hallo, ich habe 3 Fragen zu der Lösung.

in der zweiten Zeile wird zweimal a'bc' in der eckigen Klammer verwendet, ist dies erlaubt?

in der vierten Zeile wird acd in der eckigen Klammer verwendet, aber trotzdem dahinter aufgeschrieben, ist dies auch erlaubt?

Und in der fünften Zeile wird aus [a'bcd' + bc'] a'cd' , müsste es aber nicht abd' sein ?

Aufgabenteil b) Vereinfachung der DNF

Thu, 02 Feb 2017 20:08:01 +0000

Guten Abend,

in der drittletzten Zeile der Vereinfachung der DNF verstehe ich den ersten Umformungsschritt nicht.
Hier wird folgende Umformung vorgenommen:

a'bcd' + bc' wird umgeformt zu bc' + a'cd'

Für die Belegung a=0, b=0, c=1 und d=0 liefert mir der erste Ausdruck allerdings eine 0, wohingegen der zweite Ausdruck eine 0 liefert, was die Gleichheit dieser beiden Ausdrücke widerlegt.

Müsste die Umformung nicht wie folgt aussehen:

a'bcd' + bc' wird umgeformt zu bc' + a'bd'

Wo liegt mein Denkfehler?

Vielen Dank und liebe Grüße!

Auch mit Button-up-Prinzip vereinbar?

Thu, 13 Nov 2014 10:24:55 +0000

Wäre das mit dem Button-up-Prinzip vereinbar, oder wäre es besser das erst wie in der Musterlösung später zu machen?

Ich fände es einfacher das am Anfang zu machen, aber deshalb Punkte abgezogen zu bekommen wenn man es nach Button-Up machen sollte wäre schlecht :)

Alternativer Lösungsansatz

Thu, 13 Nov 2014 10:22:09 +0000

Warum verschmelze ich nicht als erstes den ganz rechten Teilbaum (Wurzel c) mit dem ganz links? Diese sind doch identisch, oder irre ich mich da?

Booleschen Ausdruck aus reduzierten Baum ablesen

Thu, 13 Nov 2014 10:19:55 +0000

Unabhängig von der Aufgabe:

Ich verstehe im Allgemeinen nicht, wie ich den booleschen Ausdruck aus dem reduzierten Baum ablesen kann. Gibt's da ein Schema oder wie kommt man darauf?

Oder muss ich immer eine Wahrheitstafel aufstellen, DNF ablesen und umformen?

Danke