Vereinfachung Boolescher Algebra

[kingofbrain]

Hallo zusammen,

ich habe in einem Teilbereich einer bestehenden Software eine kaskadierende if/else-if Abfrage, die ich gerne vereinfachen würde. Allerdings ist boolesche Algebra schon ein bisschen her bei mir und jetzt wollte ich meinen Lösungsentwurf zur Diskussion stellen, damit ich weiß, ob ich richtig liege. Hier mal in Pseudocode die Abfrage:

if (A) {

  if ( {

    foo();

  }

} else {

  if (¬ {

    foo();

  } else {

    if (C) {

      foo();

    }

  }

}

[/code]




Man sieht, dass an allen drei Stellen foo() passiert, also immer das selbe. Ich habe also den o.g. Ausdruck in folgendem booleschen beschrieben: 

[code](A ⋀ ⋁ ¬B ⋁ C

Ist diese Überführung korrekt? Dann habe ich versucht, den o.g. booleschen Ausdruck zu vereinfachen:

(A ⋀  ⋁ ¬B ⋁ C

((A ⋀  ⋁ ¬ ⋁ C

((A ⋁ ¬ ⋀ (B ⋁ ¬) ⋁ C

((A ⋁ ¬ ⋀ 1) ⋁ C

A ⋁ ¬B ⋁ C

[/code]

Ich habe also im ersten Schritt das ¬B in die Klammer gezogen, danach B ⋁ ¬B zu 1 vereinfacht und aus dem UND-Ausdruck entfernt, da X ⋀ 1 = X. Danach überflüssige Klammern entfernt und fertig.

Könnt Ihr die einzelnen Schritte nachvollziehen? Sind diese korrekt?

Vielen Dank fürs Drüberschauen und schöne Grüße,

Peter

[flashpixx]

Also meiner Ansicht nach ist da nur ein kleiner Fehler:

if (a) if b => ergiben richtig "A und B"

dann hast Du einmal "nicht(b)" , was auch in Ordnung ist

Nur sobald Dein C ins Spiel kommt müsstest Du, da sich das C aus dem else-Zweig des nicht( ergibt ganz korrekt "C und nicht(nicht()" schreiben.

Damit würde ich von: (A && || !B || (C && !! ausgehen. Wobei die Klammern kannst Du weg lassen, da && stärker bindet als ||.

Wenn ich mich jetzt nicht verrechnet habe, müsste dann nach meinem Ausdruck folgendes raus kommen: * = &&, + == ||

A*B + !B + C*!!B

A*B + !B + C*B     

(A+C) * B + !B    // getauscht und ausgeklammert

!!( (A+C) *  + !B  //DeMorgan anwenden

!!(A+C) + !B + !B //idempotente Terme zusammen fassen

!!(A+C) + !B  //Negation auflösen

(A+C) + !B

A + !B + C

[/code]

Hoffe, dass ich das g'rade richtig gemacht habe, bitte noch mal kontrollieren

[kingofbrain]

Guten Morgen flashpixx,

vielen Dank für Deine Anmerkungen. Ich habe gestern einen Schritt bei der Überführung meines if-else-Konstrukts in die Boolesche Formel nicht erläutert. Das hole ich schnell nach:

if (A) {

  if ( {

    foo();

  }

} else {

  if (¬ {

    foo();

  } else {

    if (C) {

      foo();

    }

  }

}

[/code]


Die ursprüngliche Verzweigung kann ich in meinen Augen vereinfachen als

[code] if (A) { if ( { foo(); } } else if (¬ { foo(); } else if (C) { foo(); }

Deshalb kam ich auf den dreifach verODERten Ausdruck. Allerdings wäre das Ergebnis Deiner und meiner Umwandlung ja das selbe. Nur kann ich einen Schritt in Deiner Umwandlung nicht nachvollziehen. Kannst Du mir dabei bitte noch kurz helfen:

A*B + !B + C*!!B

A*B + !B + C*B     

(A+C) * B + !B    // getauscht und ausgeklammert, sehe ich genau so

!!( (A+C) *  + !B  // DeMorgan anwenden, ebenfalls

[COLOR="Red"]!!(A+C) + !B + !B[/COLOR] // idempotente Terme zusammen fassen, [COLOR="Red"]hier habe ich das Gefühl, als würde eine der Negationen noch vor der Klammer stehen bleiben müssen, also in meinen Augen wäre das Ergebnis eher so:[/COLOR] 

!(!(A+C) + ! + !B

[/code]

Und dann komme ich nicht mehr weiter, weil ich die Negation nicht so elegant auflösen kann wie Du. Könntest Du mir hier bitte noch mal kurz auf die Sprünge helfen?

Vielen Dank und schöne Grüße,

Peter

[etreu]

Die Korrektheit lässt sich einfach mit den Wahrheitswertetabellen ermitteln.

Was die Umformung des Codes in die Algebra angeht, muss ich anmerken, dass die Semantik von if-else in Programmiersprachen einem XOR entspricht.

[kingofbrain]

Guten Morgen etreu,

um die Aufstellung von Wahrheitstabellen wollte ich mich in diesem Fall drücken. Ich finde die immer recht umständlich in der Handhabung schon bei wenigen Variablen im Booleschen Ausdruck.

Und mit dem XOR hast Du natürlich recht, allerdings ist das für diesen Fall nicht von Bedeutung. Ich kann fachlich die Ausdrücke auch so umformen, dass es keine if/else-if Bedingungen sind, sondern mehrere if-Ausdrücke auf der selben Ebene. Aber danke für den Hinweis!

Ich bin die Ausdrücke jetzt mit den fachlich Verantwortlichen durchgegangen und habe die Bedingungen komplett umformuliert. Das sollte passen (JUnit sagt "grün").

Vielen Dank für Eure Hilfe und bis die Tage!

Peter