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[Bearbeiten]

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 Werte miteinander vergleicht und so Wahrheitswerte enthält. Gelegentlich werden ermittelte Wahrheitswerte auch abgespeichert 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.

In den gängigen Programmiersprachen findet man zwei Arten von Operatoren auf Wahrheitswerten:

  • einstellige Operatoren - sie erzeugen aus einem Wahrheitswert einen anderen. Bekannt ist der NOT Operator, der zu einem Wahrheitswert sein Gegenteil liefert.
  • zweistellige Operatoren - sie verknüpfen zwei Wahrheitswerte und liefern einen neuen. Beispiele sind UND und 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 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

Insgesamt sind 16 zweistellige Operationen auf logischen Werten möglich. Eine Übersicht dazu folgt weiter unten.

Für die weitere Beschreibung sollen die in vielen Programmiersprachen gängigen Symbole ! für NOT, && für UND und || für ODER verwendet werden. Man könnte auch & und | statt && und || schreiben, aber diese Symbole haben in Sprachen wie JavaScript, PHP oder C eine andere Bedeutung.

Grundregeln[Bearbeiten]

Kommutativgesetz und Assoziativgesetz[Bearbeiten]

Genau wie bei den arithmetischen Operationen gibt es auch für logische Operationen bestimmte grundlegende Eigenschaften. Beispielsweise gilt für UND und ODER ein Kommutativgesetz und ein Assoziativgesetz:

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

Auflösen von Klammern 1: Distributivgesetze[Bearbeiten]

Zum Umformen von Kombination von UND und ODER gibt es zwei Distributivgesetze. Das ist anders als beim Rechnen - beim Rechnen mit plus und mal gibt es nur eins.

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

Auflösen von Klammern 2: Gesetze von De Morgan[Bearbeiten]

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 den Gesetzen von De Morgan. Salopp formuliert: Wird eine NOT-Klammer aufgelöst, wird aus UND ein ODER und aus ODER ein UND.

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

Vorrangregeln in Programmiersprachen[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

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 ID NOT
TRUE TRUE FALSE TRUE FALSE
FALSE FALSE TRUE TRUE FALSE

Es klingt unsinnig, diese Operationen ü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[Bearbeiten]

Die folgende kombinierte Wahrheitstabelle zeigt alle 16 möglichen zweistelligen logischen Operatoren im Überblick.

A B A||B B⇒A A A⇒B B A⇔B A&&B NAND A⊕B !B *1 !A *2 NOR
TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE
TRUE FALSE TRUE TRUE TRUE TRUE FALSE FALSE FALSE FALSE TRUE TRUE TRUE TRUE FALSE FALSE FALSE FALSE
FALSE TRUE TRUE TRUE FALSE FALSE TRUE TRUE FALSE FALSE TRUE TRUE FALSE FALSE TRUE TRUE FALSE FALSE
FALSE FALSE TRUE FALSE TRUE FALSE TRUE FALSE TRUE FALSE TRUE FALSE TRUE FALSE TRUE FALSE TRUE FALSE

Die meisten dieser Operatoren sind relativ gut verstehbar. Es gibt die klassischen Operatoren UND, ODER, ENTWEDER-ODER (A⊕B, XOR, A!=B) und GENAU-WIE (A⇔B, 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). Die Spalte „Vereinfacht“ in der folgenden Tabelle zeigt, wie man die genannten Operationen auf die Standardoperationen von Javascript oder PHP zurückführen kann.

Operation Lesart Vereinfacht
A ⇒ B „Aus A folgt B“, „wenn A, dann auch B“ !A || B
B ⇒ A „Aus B folgt A“, „wenn B, dann auch A“ A || !B
*1 !(A⇒B), „A, aber nicht B“ A && !B
*2 !(B⇒A), „B, aber nicht A“ !A && B

Herleiten von logischen Ausdrücken[Bearbeiten]

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.

Entscheidungstabellen[Bearbeiten]

Entscheidungstabellen sind eine Variante der Wahrheitstabellen. Um Logik als Entscheidungstabelle darzustellen, 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 davon abhängt, dass eine bestimmte Aktion ausgeführt wurde, so muss man die Tabelle in zwei ETs teilen. Eventuell ist die Bedingung auch überflüssig, weil die Aktion ja ihrerseits von anderen Bedingungen abhängig war.

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
Ampel zeigt Rot     J - - - -
Ampel zeigt Gelb    - J - - - 
Ampel zeigt Grün    - - 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
Ampel zeigt Rot     J J J N - - -
Ampel zeigt Gelb    N J J J - - - 
Ampel zeigt Grün    - - - - 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. Anstatt sich für jede Aktion eine Regel nach der anderen zu überlegen, schreibt man zunächst alle möglichen Regeln auf. Bei vier Ja/Nein Regeln sind es 16 Stück. Und dann kreuzt man für jede Regel an, welche Aktion zutrifft.

Beispiel
Ampel zeigt Rot     J J J J  J J J J  N N N N  N N N N
Ampel zeigt Gelb    J J J J  N N N N  J J J J  N N N N 
Ampel zeigt Grün    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.

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 == Operator 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[Bearbeiten]

Weblinks[Bearbeiten]

Verwendete Bezüge[Bearbeiten]

  1. Boolesche Algebra Wikipedia-Artikel