Boolesche Formel in Shannon Normalform

[BlackSpike666]

Hey ho,
muss mich gerade mit BDDs und so rumschlagen und würde gerne wissen wie eine boolesche Formel in die Shannon Normalform konvertiert. Z.B.:

a&b&d|b&c&!d|d&!b|!c&!d := (d?(b?(a?true: false): true): (c?(b?true: false): true))

Kann mir jemand so einfach wie möglich erklären, wie man das berechnet?

Vielen Dank!

[sontyp]

Uff. Erstma aufn Zettel aufschreiben. Wat meinste mit den Fragezeichen?
Habt ihr schon KV Diagramme behandelt?

Genau genommen versteh ich den ganzen rechten Teil der Gleichung nicht. Sieht wie Java aus...lol
Solln das die Wahrheitswerte sein?

[H4x0r007]

Hi,

genau kenne ich die formalen Bestimmungen nicht, aber ich versuche es mal, zu interpretieren.
Der komische Ausdruck auf der rechten Seite besteht anscheinend aus ternären Operatoren, wie sie z.B. in C vorkommen.
Also z.B. (a>2) ? b = 1 : b = 3 ist äquivalent zu

if(a > 2) {
   b = 1;
} else {
   b = 3;
}

Jetzt wandeln wir den gesamten Ausdruck: (d?(b?(a?true: false): true): (c?(b?true: false): true)) in Pseudocode:

if d:
    if b:
        if a:
            true
        else:
            false
    true
else:
    if c:
        if b:
            true
        else:
            false
    else:
        true

Auf die Shannon-Normalform komme ich, indem ich mir die Pfade anschaue, die zu True werden:
(D und B und A) oder (D und Nicht B) oder (Nicht D und C und B) oder (Nicht D und Nicht C). Die Klammern dienen nur der Übersicht.

Wenn ich das jetzt umsortiere zu
(A und B und D) oder (B und C und Nicht D) oder (D und Nicht B) oder (Nicht C und Nicht D), komme ich auf den angegebenen Term:

a&b&d|b&c&!d|d&!b|!c&!d

Das Ganze hat keinen formalen Anspruch und zeigt nur, wie ich mir das hergeleitet habe. Ob das deinen Professoren so reicht, weiß ich nicht ;-)

[BlackSpike666]

Uff. Erstma aufn Zettel aufschreiben. Wat meinste mit den Fragezeichen?
Habt ihr schon KV Diagramme behandelt?

Genau genommen versteh ich den ganzen rechten Teil der Gleichung nicht. Sieht wie Java aus...lol
Solln das die Wahrheitswerte sein?

Die Fragezeichen und der Doppelpunkt, sind wie H4x0r007 schon geschrieben hat, ternären Operatoren (Abkürzung für if, then, else)

Jetzt wandeln wir den gesamten Ausdruck: (d?(b?(a?true: false): true): (c?(b?true: false): true)) in Pseudocode:

if d:
    if b:
        if a:
            true
        else:
            false
    true
else:
    if c:
        if b:
            true
        else:
            false
    else:
        true

Auf die Shannon-Normalform komme ich, indem ich mir die Pfade anschaue, die zu True werden:
(D und B und A) oder (D und Nicht B) oder (Nicht D und C und B) oder (Nicht D und Nicht C). Die Klammern dienen nur der Übersicht.

Wenn ich das jetzt umsortiere zu
(A und B und D) oder (B und C und Nicht D) oder (D und Nicht B) oder (Nicht C und Nicht D), komme ich auf den angegebenen Term:

a&b&d|b&c&!d|d&!b|!c&!d

Klasse, die Erklärung hat mir echt viel geholfen!


Also:
1. Boolesche Formel anschauen und die Pfade raussuchen, die zu True werden.
2. Pfade so konventieren das durch ternären Operatoren, die gesamten Pfade widergespiegelt werden.


Falls noch jemand Tipps zu dem ganzen Thema hat, würde ich mich freuen

Und Danke dir nochmal H4x0r007!

[sontyp]

Ok, dann hab ichs ja doch richtig vermutet. Kenne ternäre Operatoren bisher nur aus Java und das hat es ja bestimmt von C übernommen.
Demnach ist H4x0r007's Erklärung ja super.

Du sagtest, ihr macht auch BDDs. N Trick ist auch immer, sich das BDD aufzumalen und daraus die Normalform abzulesen. Hat mir immer geholfen.
Die nächste Frage die sich dann bei euch stellen könnte, ist dann obs konjunktiv oder disjunktiv. Da hilft dir dann deMorgan weiter mit doppelter Negation ;-)