Ergebnis 1 bis 5 von 5
  1. #1
    Trojaner Avatar von BlackSpike666
    Registriert seit
    28.08.2007
    Beiträge
    66

    Standard Boolesche Formel in Shannon Normalform

    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!
    Geändert von BlackSpike666 (06.06.2017 um 18:26 Uhr)

  2. #2
    Trojaner Avatar von sontyp
    Registriert seit
    16.09.2016
    Beiträge
    67

    Standard AW: Boolesche Formel in Shannon Normalform

    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?
    Geändert von sontyp (07.06.2017 um 06:19 Uhr)

  3. #3
    Be root - Use Linux Avatar von H4x0r007
    Registriert seit
    27.06.2007
    Beiträge
    1.878

    Standard AW: Boolesche Formel in Shannon Normalform

    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
    Code:
    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:


    Code:
    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 ;-)
    Geändert von sn0w (07.06.2017 um 13:56 Uhr) Grund: Farbe angepasst
    Bald 14 Jahre auf Free-Hack. Krass wie die Zeit vergeht...
    "Drei Dinge sind unendlich - das Universum, die menschliche Dummheit und die WinRAR-Testversion"

  4. Folgende Benutzer haben sich für diesen Beitrag bedankt:

    BlackSpike666 (07.06.2017)

  5. #4
    Trojaner Avatar von BlackSpike666
    Registriert seit
    28.08.2007
    Beiträge
    66

    Standard AW: Boolesche Formel in Shannon Normalform

    Zitat Zitat von sontyp Beitrag anzeigen
    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)



    Zitat Zitat von H4x0r007 Beitrag anzeigen

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


    Code:
    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!

  6. #5
    Trojaner Avatar von sontyp
    Registriert seit
    16.09.2016
    Beiträge
    67

    Standard AW: Boolesche Formel in Shannon Normalform

    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 ;-)

Berechtigungen

  • Neue Themen erstellen: Nein
  • Themen beantworten: Nein
  • Anhänge hochladen: Nein
  • Beiträge bearbeiten: Nein
  •