Benutzer:Rolf b/boolescheAlgebra

Aus SELFHTML-Wiki
Wechseln zu: Navigation, Suche

Boolesche Algebra bezeichnet im Rahmen der Programmierung die Regeln, nach denen sich die grundlegenden logischen Operationen UND, ODER und NICHT im Zusammenhang mit den logischen Werten TRUE und FALSE verhalten. Der Begriff an sich ist deutlich umfangreicher, bei Interesse sei auf den Wikipedia-Artikel zur Booleschen Algebra [1] verwiesen.

Einführung

Bei den üblichen Programmierproblemen steht man vor der Aufgabe, fachliche oder technische Situationen zu identifizieren, um dann je nach Situation das Richtige zu tun. Eine einzelne Situation wird erkannt, indem man beliebige Werte miteinander vergleicht und so Wahrheitswerte enthält. Gelegentlich werden ermittelte Wahrheitswerte auch in Variablen gespeichert und später wieder verwendet (solche Variablen nennt man Schalter oder Flag).

Zumeist ist aber nicht nur ein Wahrheitswert, sondern mehrere zu betrachten, und konkrete Situationen erkennt man durch Verknüpfungen dieser Wahrweitswerte im Sinne von "Wenn dies, aber nicht das - es sei denn JENES ist der Fall - DANN haben wir den Fall 17c und müssen dieses und jenes tun". Die Booleschen Algebra hilft dabei, den WENN Teil dieser Regeln besser zu verstehen.

Um komplexe Bedingungsgefüge übersichtlich darstellen zu können, gibt es ein Hilfsmittel, auf das in einem weiteren Artikel eingegangen werden soll: Entscheidungstabellen.

Zunächst aber wollen wir einzelne logische Operationen betrachten.

Wahrheitstabellen

Eine gängige Methode, eine logische Operation zu beschreiben, ist die Wahrheitstabelle. In einer solchen Tabelle notiert man die an der Operation beteiligten Wahrheitswerte und schreibt dazu auf, für welche Kombination dieser Wahrheitswerte das Ergebnis der logischen Operation wahr sein soll. Die beteiligten Wahrheitswerte kann man auf unterschiedliche Weise notieren, beispielsweise durch false und true, durch FALSCH und WAHR, oder auch durch Buchtaben wie F und W oder N und J (für Nein und Ja).

Die möglichen Kombinationen der Eingangswerte schreibt man dabei systematisch auf, um keine zu übersehen. Je mehr Eingangswerte es gibt, desto mehr Kombinationen sind möglich: für N Eingangswerte gibt es 2N Kombinationen. Zumeist schreibt man die Kombinationen zeilenweise auf. Wahrheitstabellen können komplexe Zusammenhänge darstellen:

Wahrheitstabelle für „mindestens 2 Eingangswerte sind wahr“ 
     A        B        C         >= 2
   false    false    false      false
   false    false    true       false
   false    true     false      false
   false    true     true       true
   true     false    false      false
   true     false    true       true
   true     true     false      true
   true     true     true       true

Um zu beschreiben, wie man die durch eine solche Wahrheitstabelle vorgegebene Logik programmieren kann, müssen wir zuerst auf die logischen Operationen eingehen.

Grundlegende logische Operatoren

In den gängigen Programmiersprachen findet man zwei Arten von Operationen auf Wahrheitswerten, die durch spezielle Symbole – die Operatoren – ausgedrückt werden.

einstellige Operatoren
sie erzeugen aus einem Wahrheitswert einen anderen. In JavaScript oder PHP gibt es den NOT Operator, der zu einem Wahrheitswert sein Gegenteil liefert.
zweistellige Operatoren
sie verknüpfen zwei Wahrheitswerte und liefern einen neuen. JavaScript oder PHP kennen Operatoren für das logische UND und das logische ODER.

Operatoren auf Wahrheitswerten werden logische Operatoren genannt, die Wahrheitswerte selbst auch logische Werte.

Das Verhalten der logischen Operatoren ist über so genannte Wahrheitstabellen definiert. Dabei werden alle Kombinationen möglicher Eingangswerte betrachtet und der daraus entstehende Ergebniswert notiert.

Die Wahrheitstabelle eines einstelligen Operators wie NOT sieht so aus:

A NOT A
TRUE FALSE
FALSE TRUE

Diese Tabelle liest sich so: Es gibt einen Eingangswert, bezeichnet als A, und einen Ausgangswert, der als „NOT A“ bezeichnet wird. Für jeden Wert von A wird angegeben, welchen Wert „NOT A“ dann annehmen soll.

Zweistellige Operatoren wie UND benötigen eine umfangreichere Wahrheitstabelle, weil es zwei Eingangwerte gibt und damit vier Kombinationen möglich sind. Es ist auch möglich, in einer Wahrheitstabelle das Verhalten mehrerer logischer Operationen parallel darzustellen. Die folgende Tabelle zeigt die Definition der Operatoren UND und ODER

A B A UND B A ODER B
TRUE TRUE TRUE TRUE
TRUE FALSE FALSE TRUE
FALSE TRUE FALSE TRUE
FALSE FALSE FALSE FALSE

Weil es bei zwei Operanden vier Zeilen gibt, sind insgesamt 24=16 unterschiedliche zweistellige logische Operatoren möglich. Eine Übersicht dazu folgt weiter unten.

Für die weitere Beschreibung sollen die in den Sprachen der C-Familie gängigen Symbole ! für NOT, && für UND und || für ODER verwendet werden. Manche Programmiersprachen verwenden & und | statt && und ||, aber diese Symbole haben in Sprachen wie JavaScript, PHP oder C eine andere Bedeutung und würden hier nur verwirren.

Boole? Wer ist Boole?

George Boole war ein englischer Mathematiker, der sich mit Aussagenlogik beschäftigt hat und erkannte, dass sich das mathematische Konzept der Algebra darauf anwenden lässt. Seine Erkenntnisse wurden von Peano[2] weiterentwickelt und sind die Grundlage für die heutigen logischen Operatoren. Die Begriffe logischer Operator und boolescher Operator werden synonym verwendet.

Grundregeln

Genau wie bei den arithmetischen Operationen gibt es auch für logische Operationen bestimmte grundlegende Eigenschaften. Diese muss man kennen, um logische Ausdrücke umformen und vereinfachen zu können.

Grob gesagt kann man sich die Rechnung mit booleschen Werten so vorstellen, als würde FALSE der Zahl 0 entsprechen und TRUE der Zahl 1. Dann ist NOT a die Rechnung 1 - a und a AND b entspricht der Multiplikation a∙b. Die ODER Operation fällt aus dem Rahmen. Ansatzweise hat a OR b die Entsprechung a + b, aber weil man mit 1 + 1 = 2 den erlaubten Wertebereich verlassen würde, muss man eine Sonderregel einführen und definieren, dass 1 + 1 den Wert 1 ergibt.

Kommutativgesetz und Assoziativgesetz

Für UND (&&) und ODER (||) gilt ein Kommutativgesetz (Reihenfolge der Operatoren) und ein Assoziativgesetz (Auswertungsreihenfolge):

Kommutativgesetz

A && B = B && A
A || B = B || A

Assoziativgesetz

( A && B ) && C = A && ( B && C )
( A || B ) || C = A || ( B || C )
Beachten Sie: Diese Regeln gelten beim Programmieren nur dann, wenn Ihre Wahrheitswerte in Variablen gespeichert sind oder sich aus Berechnungen ergeben, deren Werte aus Variablen stammen. Oft ist es aber auch so, dass man Funktionen aufruft, die einen Wahrheitswert zurückliefern. Wenn solche Funktionen Nebenwirkungen aufweisen, ist die Reihenfolge der Auswertung möglicherweise nicht mehr beliebig.

Manche Programmiersprachen nehmen sich die Freiheit, die Reihenfolge nicht festzulegen, in der die beteiligten Werte in einem Ausdruck ermittelt werden. Stammen die Werte dann aus Funktionsaufrufen, ist auch die Reihenfolge dieser Aufrufe nicht mehr gegeben. In JavaScript oder PHP ist das nicht so, hier ist für jeden Operator eine Assoziativität festgelegt, die für die logischen Operatoren bestimmt, dass gleichrangige Operatoren von links nach rechts ausgewertet werden.

Was Ihnen in JavaScript oder PHP aber passieren kann, ist eine Kurzschluss-Auswertung. Wenn der Ausdruck A || B auszuwerten ist und sich A als WAHR ergibt, ist das Ergebnis auf jeden Fall WAHR und B wird nicht mehr ermittelt. Das heißt: falls sich B durch einen Funktionsaufruf ergibt, wird die Funktion nicht mehr aufgerufen. Das Gleiche gilt in A && B, wenn A den Wert FALSCH hat.

Auflösen von Klammern 1: Distributivgesetze

In der Zahlenmathematik kann man lediglich die Multiplikation ausklammern. In der booleschen Algebra geht das überraschenderweise sowohl mit UND als auch mit ODER, deshalb gibt es zwei Distributivgesetze. Wenn Sie das nicht glauben, dann stellen Sie die Wahrheitstabelle auf und prüfen es nach.

( A && B ) || C = ( A || C ) && ( B || C )
( A || B ) && C = ( A && C ) || ( B && C )

Auflösen von Klammern 2: Gesetze von De Morgan

Darüber hinaus gibt es den Fall, dass die NOT-Operation auf eine in Klammern gesetzte UND oder ODER Operation trifft. In solchen Fällen kann der Wunsch bestehen, die Klammern aufzulösen. Diese Umformung folgt Regeln, die dem englischen Mathematiker Augustus De Morgan[3] zugeschrieben werden, obwohl William of Ockham sie bereits im 13. Jahrhundert formuliert hat.

Salopp formuliert lauten sie: Wird eine NOT-Klammer um einen UND oder ODER Term aufgelöst, wird aus dem UND ein ODER und aus ODER ein UND.

!(A && B) = !A || !B
!(A || B) = !A && !B

Beim Auflösen einer NOT-Klammer werden die De Morgan Regeln leider zu oft übersehen. Ihre Richtigkeit wird durch die nachfolgenden Wahrheitstabellen belegt:

Wahrheitstabelle für De Morgan 1
A B A && B  !(A && B)  !A  !B  !A || !B
FALSE FALSE FALSE TRUE TRUE TRUE TRUE
FALSE TRUE FALSE TRUE TRUE FALSE TRUE
TRUE FALSE FALSE TRUE FALSE TRUE TRUE
TRUE TRUE TRUE FALSE FALSE FALSE FALSE
Wahrheitstabelle für De Morgan 2
A B A || B  !(A || B)  !A  !B  !A && !B
FALSE FALSE FALSE TRUE TRUE TRUE TRUE
FALSE TRUE TRUE FALSE TRUE FALSE FALSE
TRUE FALSE TRUE FALSE FALSE TRUE FALSE
TRUE TRUE TRUE FALSE FALSE FALSE FALSE

Vorrangregeln in Programmiersprachen

Wichtig zu wissen ist auch, dass Programmiersprachen Regeln definieren, nach denen bestimmte Operatoren Vorrang vor anderen haben. Beim Rechnen wissen wir, dass 2+3⋅4 als 2+(3⋅4) zu interpretieren ist und nicht als (2+3)⋅4. Bei den logischen Operationen gilt, dass NOT die höchste Rangstufe hat, AND die zweithöchste und OR die niedrigste. Der Ausdruck A || !B && C ist demzufolge als A || ( ( !B) && C) zu lesen.

Weitere logische Operationen

Wie in der Einleitung erwähnt, sind mehr als nur die grundlegenden booleschen Operationen möglich. Es gibt vier einstellige Operationen, 16 zweistellige und - wenn man sie definieren möchte - 256 mögliche dreistellige Operationen.

Einstellige Operationen

Außer der bekannten NOT Operation gibt es noch die Identität (sie liefert ihre Eingabe zurück), die Tautologie ┬ (sie liefert immer TRUE) und die Kontradiktion ┴ (immer FALSE)

A true false Bezeichnung JavaScript
ID A true false Identität A
NOT A false true Negierung !A
┬ true true Tautologie true
┴ false false Kontradiktion false

Es klingt unsinnig, Operationen außer NOT überhaupt zu erwähnen. Im Rahmen funktionaler Programmierung, wo Funktionen zur Laufzeit zu komplexeren Funktionen komponiert werden können, kann es aber durchaus zweckmäßig werden, Identität, Tautologie oder Kontradiktion als Bausteine in einem vorgefertigten Ablauf einzusetzen.

Zweistellige Operationen

Die folgende kombinierte Wahrheitstabelle zeigt alle 16 möglichen zweistelligen logischen Operatoren im Überblick. Damit die Tabelle nicht zu breit wird, sind die Zeilen und Spalten gegenüber üblichen Wahrheitstabellen vertauscht. Die meisten dieser Operatoren werden von JavaScript (oder auch anderen Sprachen) nicht direkt unterstützt, daher wurde eine Spalte „JavaScript“ angefügt, die zeigt, wie man diesen Operator mit JavaScript formulieren muss.

A true true false false
B true false true false Bezeichnungen JavaScript
Operation
 ┬ true true true true Tautologie true
A || B true true true false Logisches ODER A || B
B ⇒ A true true false true B ⇒ A (Implikation, aus B folgt A) A || !B
A true true false false Immer A A
A ⇒ B true false true true A ⇒ B (Implikation, aus A folgt B) !A || B
B true false true false Immer B B
A ⇔ B true false false true Äquivalenz A ⇔B A == B
A && B true false false false Logisches UND A && !B
NAND false true true true Negiertes UND !(A && B), !A || !B
A ⊕ B false true true false A ⊕ B (XOR, Entweder-Oder) A != B
!B false true false true Not B !B
 !(A ⇒ B) false true false false Negierte Implikation A && !B
!A false false true true Not A !A
 !(B ⇒ A) false false true false Negierte Implikation !A && B
NOR false false false true Negiertes ODER !(A || B), !A && !B
┴ false false false false Kontradiktion false

Die meisten dieser Operatoren sind relativ gut verstehbar. Es gibt die klassischen Operatoren UND, ODER, ENTWEDER-ODER (A⊕B, XOR) und GENAU-WIE (Äquivalenz, A⇔B), es gibt die Negation von UND und ODER (auch NAND und NOR genannt), es gibt Projektions-Operatoren, die nur einen Operanden verwenden und dann seine Identität oder seine Negation liefern (A, B, !A, !B), es gibt natürlich Tautologie und Kontradiktion

Es gibt aber auch 4 Operatoren, die etwas schwieriger zu verstehen sind. Die Schreibweise A ⇒ B ist als mathematische Schlussfolgerung zu lesen, d.h. A ⇒ B ist TRUE, wenn eine korrekte mathematische Folgerung vorliegt. Wenn A den Wert FALSE hat, ist die Implikation immer richtig (aus etwas falschem kann man alles folgern), und wenn A den Wert TRUE hat, muss auch B gleich TRUE sein, damit die Implikation richtig ist.

Herleiten von logischen Ausdrücken

In vielen Fällen benötigt man für eine Programmentscheidung nur eine oder zwei Bedingungen und kann sie direkt aufschreiben.

Kommen dagegen mehrere Bedingungen zusammen, steht man vor einer Fülle möglicher Kombinationen, deren Strukturierung nicht leicht ist. Hier gibt es mehrere Hilfsmittel.

Karnaugh-Veitch Diagramm

Kommen wir noch einmal auf das "2 aus 3" Beispiel vom Anfang zurück.

Wahrheitstabelle für „mindestens 2 Eingangswerte sind wahr“ 
   A   B   C    >=2
   F   F   F     F
   F   F   W     F
   F   W   F     F
   F   W   W     W
   W   F   F     F
   W   F   W     W
   W   W   F     W
   W   W   W     W

Möchte man diese Wahrheitstabelle mit den in JavaScript oder PHP verfügbaren Operatoren !, && und || abbilden, wird die Darstellung schnell unübersichtlich. Es gibt 4 Zeilen, deren Ergebnis WAHR ist, und wenn man naiv herangeht, müsste man die Abfrage so schreiben:

if ((!A && B && C) || (A && B && !C) || (A && !B && C) || (A && B && C)) ...

Wie vereinfacht man das - systematisch? Dazu gibt es die so genannten Karnaugh-Vietch Diagramme[4] oder kurz KV-Diagramme. Ein solches Diagramm stellt eine Wahrheitstabelle mit 3 oder 4 Eingangswerten so dar, dass man logisch zusammenhängende Blöcke direkt sieht. Man beginnt mit einem einfachen Diagramm für eine Variable:

A=false A=true
0 1

Eine Wahrheitstabelle mit nur einer Variablen und 2 Zeilen würde man nun so in das Diagramm übertragen, dass Zeile 1 in Zelle 0 kommt und Zeile 2 in Zelle 1. Aber für eine Variable lohnt sich ein KV-Diagramm nicht.

Für eine zweite Variable spiegeln wir dieses Rechteck nach unten. Im gespiegelten Bereich addieren wir 2 zu den Zellnummern:

A=false A=true
B=false 0 1
B=true 2 3

Das reicht schon für eine Wahrheitstabelle mit zwei Variablen und 4 Zeilen. Für eine dritte Variable spiegeln wir nach rechts und addieren im gespiegelten Bereich 4 auf die Zellnummern:

C=false C=true
A=false A=true A=true A=false
B=false 0 1 5 4
B=true 2 3 7 6

Für eine vierte Variable spiegelt man nochmals nach unten und addiert 8 - dafür sei auf den referenzierten Wikipedia-Artikel verwiesen.

Die Nummern in den Zellen entsprechen der Zeilennummer in der Wahrheitstabelle (ab 0 gezählt). Wenn wir die "2 aus 3" Wahrheitstabelle in ein KV-Diagramm eintragen, erhalten wir:

C=false C=true
A=false A=true A=true A=false
B=false false false true false
B=true false true true true

Um nun herauszufinden, wie sich mit möglichst wenig Abfragen der grüne Bereich abdecken lässt, versuchen wir, ihn mit Quadraten oder mit Rechtecken abzudecken. Rechtecke müssen dabei aber eine Zellenzahl bedecken, die einer Zweierpotenz entspricht. Dabei ist es erlaubt, ja sogar erwünscht, wenn diese Quadrate und Rechtecke sich überlappen.

In unserem Beispiel könnte man das 1x2 Rechteck in Spalte 3 wählen, sowie in Zeile 2 das 2x1 Rechteck ab der 2. Spalte und das 2x1 Rechteck ab der 3. Spalte. Was all diese Rechtecke gemeinsam haben, ist die Zelle mit der Nummer 7 (hier sind A, B und C true). Wir verwenden nun die Logikanteile, die die verwendeten Flächen gemeinsam haben:

  • Rechteck in Zeile 2, ab Spalte 2: A=true UND B=true
  • Rechteck in Spalte 2: A=true UND C=true
  • Rechteck in Zeile 2, ab Spalte 3: B=true UND C=true

Diese UND-Gruppen werden nun durch ODER kombiniert: 

  istMindestens2 = (A && B) || (A && C) || (B && C);

Das ist deutlich kürzer als der naiv gefundene Logikausdruck. Durch Anwendung des Distributivgesetzes könnte man daraus noch dies machen: 

  istMindestens2 = A && (B || C) || (B && C);

Aber die Anzahl der Logikoperationen wird dadurch nicht geringer.

Diese Darstellung (UND-Gruppen durch ODER verbunden) nennt man die disjunktive Form eines Logikausdrucks („Disjunktion“ ist in der Aussagenlogik ein Begriff für ODER).

Entscheidungstabellen

Entscheidungstabellen sind eine Technik, um ein Regelwerk tabellarisch darzustellen. Dafür schreibt man zunächst alle Bedingungen auf, die für die benötigte Entscheidung vorausgesetzt sind. Darunter folgen dann alle Aktionen, die abhängig von diesen Bedingungen auszuführen sind. Entdeckt man dabei, dass eine Bedingung einen Wert verwendet, der erst von einer Aktion der Entscheidungstabelle bestimmt wird, so muss man die Tabelle in zwei ETs teilen.

Nun muss man Regeln formulieren. Man betrachtet eine Aktion, und überlegt sich, welche Bedingungen dafür wichtig sind und ob sie dafür Wahr oder Falsch ein müssen. Eine Regel kennt also drei Zustände: Wahr (W), Falsch (F) oder Irrelevant (-). Jede Regel, die man für eine Aktion formulieren kann, schreibt man neben den Bedingungen und Aktionen als Spalte auf. Bei den Bedingungen W, F oder -, und bei der Aktion ein X. Die anderen Aktionen bekommen erstmal ein "-".

Beispielsweise könnte man folgendes aufschreiben. "Vorsichtig fahren" soll bedeuten: Die Ampel ist kaputt, man muss die Kreuzung selbstständig überqueren.

Beispiel 
Rot leuchtet        J - - - -
Gelb leuchtet       - J - - - 
Grün leuchtet       - - J - -
Kreuzung ist frei   - - - N -

Anhalten            X - - X -
Gas geben           - X - - -
Ruhig weiterfahren  - - X - -
Vorsichtig fahren   - - - - X
Adhoc notiertes Regelwerk zum Überqueren einer Ampelkreuzung.

Die letzte Regel in dieser Adhoc-Tabelle ist eine Else-Regel, die ausgeführt wird, wenn keine andere Regel zutrifft. Man sieht recht schnell, dass diese ET nicht funktioniert. Zum Beispiel würde man bei Rot-Gelb nicht wissen, was man tun soll, weil zwei Regeln zutreffen. Die Tabelle gibt zwar die „Prinzipien“ der Ampelsteuerung wieder, ist aber für eine autonome Fahrzeugsteuerung unbrauchbar.

Der nächste Schritt besteht also darin, diese Widersprüche zu finden und zu entscheiden, was nun wirklich zu tun ist. Als Hilfestellung dazu kann man sich überlegen, dass eine Regel mit Irrelevanzmarkern in Wahrheit nicht eine Regel darstellt, sondern eine Zusammenfassung mehrerer Regeln. Eine Regel (J,J,J,-) repräsentiert eigentlich die Regeln (J,J,J,J) und (J,J,J,N). Die erste Regel der obigen Entscheidungstabelle steht für 8 ausformulierte Regeln, von denen vier ein J bei "Ampel zeigt Gelb" haben und daher mit der zweiten Regel kollidieren. Die folgende ET spezifiziert die Regeln genauer und stellt den Widerspruch deutlicher dar:

Beispiel 
Rot leuchtet        J J   J N   -   -   -
Gelb leuchtet       N J   J J   -   -   - 
Grün leuchtet       - -   - -   J   -   -
Kreuzung ist frei   - -   - -   -   N   -

Anhalten            X X   - -   -   X   -
Gas geben           - -   X X   -   -   -
Ruhig weiterfahren  - -   - -   X   -   -
Vorsichtig fahren   - -   - -   -   -   X
Der Widerspruch zwischen Regel 1 und Regel 2

Man sieht, dass Regel 2 dieser ET falsch ist: Bei Rot-Gelb fährt man los, statt anzuhalten. Diese Regel wird also gestrichen. Aber natürlich ist das nicht der einzige Widerspruch gewesen.

Statt auf diese Weise mühsam alle Widersprüche zu identifizieren, kann man eine andere Vorgehensweise wählen. Die ist ebenfalls mühsam, führt aber sicherer zum Ziel. Vor allem hat sie den Vorteil, dass man sich alle möglichen Kombinationen der Eingangsbedingungen systematisch vor Augen führt und damit sicher ist, keine zu übersehen.

Sich ausgehend von den Aktionen Bedingungen zu überlegen, ist in einer Brainstorming-Phase sinnvoll, in der es darum geht, die Bedingungen zu finden, die für die Entscheidungsfindung relevant sind. Hat man diese Bedingungen, kann man zur systematischen Analyse übergehen, indem man alle möglichen Regeln aufschreibt. Bei vier Ja/Nein Regeln sind es 16 Stück. Und dann kreuzt man für jede Regel an, welche Aktion zutrifft.

Beispiel 
Rot leuchtet        J J J J  J J J J  N N N N  N N N N
Gelb leuchtet       J J J J  N N N N  J J J J  N N N N 
Grün leuchtet       J J N N  J J N N  J J N N  J J N N
Kreuzung ist frei   J N J N  J N J N  J N J N  J N J N

Anhalten            - X - X  - X X X  - X - X  - X - X
Gas geben           - - X -  - - - -  - - X -  - - - -
Ruhig weiterfahren  - - - -  - - - -  - - - -  X - - - 
Vorsichtig fahren   X - - -  X - - -  X - - -  - - X -
Regelwerk zum Überqueren einer Ampelkreuzung, systematisch aufgebaut.

Diese Matrix sieht sehr nach dem Zweiersystem aus. Ein "J" kann ein Eins-Bit in einer Binärzahl sein, ein "N" ein Null-bit. "Rot" könnte man also den Wert 8 zuordnen, "Gelb" die 4, "Grün" die 2 und "Frei" die 1. Damit hätte die erste Regel den Wert 15, die zweite die 14, und so weiter. Dann könnte man direkt losprogrammieren:

Beispiel

Binärmethode zur Realisierung von Entscheidungstabellen

Und tatsächlich gibt es Entscheidungstabellentools, die exakt auf diese Weise vorgehen. Dieses Vorgehen ist aber nicht unbedingt das effizienteste, weil die Regeln oftmals so aussehen, dass für bestimmte Aktionen längst nicht alle Bedingungen von Bedeutung sind. Man kann aber in jeden Zweig einen Zähler einbauen und dann im Test beweisen, dass die Testfälle alle Entscheidungszweige der Tabelle abdecken.

Eine effizientere Implementierung, die nur die nötigen Bedingungen abfragt, beginnt damit, zunächst einmal die Tabelle nach Aktionen zu sortieren und dann zu schauen, welche Regeln sich nur in einer Bedingung unterscheiden, aber die gleiche Aktion auslösen.

Übereinstimmungen, Runde 1 
Rot leuchtet        J J N N  N   J N   J J  J J J  N N  N N
Gelb leuchtet       J N J N  N   J J   J J  N N N  J J  N N 
Grün leuchtet       J J J N  J   N N   J N  J N N  J N  J N
Kreuzung ist frei   J J J J  J   J J   N N  N J N  N N  N N
                                                            
Anhalten            - - - -  -   - -   X X  X X X  X X  X X
Gas geben           - - - -  -   X X   - -  - - -  - -  - -
Ruhig weiterfahren  - - - -  X   - -   - -  - - -  - -  - - 
Vorsichtig fahren   X X X X  -   - -   - -  - - -  - -  - -

Übereinstimmungen   A   A        B B   C C    D D  E E  F F

Rot leuchtet        - J N  N   -   J  J J  N  N
Gelb leuchtet       J N N  N   J   J  N N  J  N 
Grün leuchtet       J J N  J   N   -  J N  -  -
Kreuzung ist frei   J J J  J   J   N  N -  N  N
                                                            
Anhalten            - - -  -   -   X  X X  X  X
Gas geben           - - -  -   X   -  - -  -  -
Ruhig weiterfahren  - - -  X   -   -  - -  -  - 
Vorsichtig fahren   X X X  -   -   -  - -  -  -



Die Aufgabe, Widersprüche zu suchen, wird nun durch die Aufgabe ersetzt, Irrelevanzen zu finden. Dafür betrachtet man zwei Regeln, bei denen die gleichen Aktionen angekreuzt sind. Unterscheiden sie sich nur an einer Stelle, so ist diese Bedingung irrelevant. Das ist beispielsweise bei den Regeln 1 und 5 oder 2 und 6 der Fall.

Das Finden von Irrelevanzen ist übrigens nicht unbedingt nötig. Man kann das, was in dieser ausformulierten Entscheidungstabelle steht, sofort programmieren. Es wird nur sehr viel Schreibarbeit sein, und der Code ist nicht unbedingt der schnellste. Man verwendet dafür die sogenannte "disjunktive Normalform" für logische Ausdrücke, in der man mehrere Teilbedingungen mit ODER verknüpft. Innerhalb einer Teilbedingung wird nur UND und NICHT verwendet. Das entspricht genau den Entscheidungstabellen-Regeln: Die Bedingungen innerhalb einer Regel sind durch UND verbunden, und eine Aktion wird ausgeführt, wenn diese ODER jene ODER eine dritte Regel zutreffen. Die Aktion "Vorsichtig fahren" könnte man also durch diesen logischen Ausdruck erkennen:

Beispiel 
if (  (rot && gelb && grün && frei)
  || (rot && !gelb && grün && frei)
  || (!rot && gelb && grün && frei)
  || (!rot && !gelb && !grün && frei))
{
// vorsichtig fahren
}

Wenn man beachtet, dass für Regel 1 und 5 die Prüfung auf gelb irrelevant ist, verkürzen sich die beiden ersten Vierfach-UND zu einem Dreifach-UND. Darüber hinaus kann man nun das Distributivgesetz anwenden und die Teilbedingung && frei ausklammern:

Beispiel 
if ( frei && ((rot && grün) || (!rot && gelb && grün) || (!rot && !gelb && !grün)) )
{
// vorsichtig fahren
}

Ein weiterer scharfer Blick zeigt, dass man !rot aus den Teilbedingungen 2 und 3 ausklammern kann:

Beispiel 
if ( frei && ( (rot && grün) || !rot && ((gelb && grün) || (!gelb && !grün))) )
{
// vorsichtig fahren
}

Und NUN lohnt sich noch eine Kenntnis der zweistelligen Operationen; das, was nach Ausklammern von !rot übrig geblieben ist, stellt die Äquivalenzrelation ⇔ dar, die sich durch den Gleichheitsoperator abbilden lässt. Ohne Kenntnis der zu Grunde liegenden Entscheidungstabelle versteht man kaum noch, wie diese Bedingung zu Stande gekommen ist, daher lohnt es sich, die ET im Code als Kommentar zu dokumentieren.

Beispiel 
//            -----------------------------------------
//           |                   --------------------  |
//           |  .---------.     |        .----------.| |
if ( frei && ( (rot && grün) || !rot && (gelb == grün) ) )
{
// vorsichtig fahren
}

Manchmal ist es auch nicht so leicht, zu erkennen, in welcher Richtung man Redundanzen zusammenfasst. Ein Beispiel sind die Regeln 5, 6 und 7. Man kann nicht alle 3 zusammenfassen, und müsste sich für 5+7 oder 6+7 entscheiden. Schaut man weiter, findet man, dass 5+7 die bessere Idee ist, weil nämlich die Regeln 1,3,5,7,9,11,13 und 15 eine Achtergruppe bilden, die nur noch von der Bedingung "rot" abhängt. Für die Systematisierung solcher Überlegung gibt es Standardalgorithmen der Informatik. Einer davon sind Karnaugh-Veitch Diagramme, die im folgenden Abschnitt vorgestellt werden sollen.

Schwieriger ist es, wenn Regeln mehrere Aktionen auslösen. Es stellt sich dann die Frage, ob man die Regeln mit gleichem Aktionsmuster zusammenzufassen versucht und die Abfragebedingung dafür optimiert, oder ob man - wie im Fall der Regel "Anhalten" oben, die Bedingungen nur einer dieser Aktionen prüft. Oft hilft hier nur, beide Möglichkeiten zu betrachten und das bessere Ergebnis zu verwenden.

Optimieren von logischen Ausdrücken

Weblinks

Verwendete Bezüge

  1. ↑ Boolesche Algebra Wikipedia-Artikel
  2. ↑ Wikipedia: Peano-Axiome der booleschen Algebra
  3. ↑ Wikipedia: Augustus De Morgan
  4. ↑ Wikipedia: Karnaugh-Veitch Diagramm
Abgerufen von „http://wiki.selfhtml.org/index.php?title=Benutzer:Rolf_b/boolescheAlgebra&oldid=96247“