Informatik - Wiki

Boolsche Algebra - Grundlagen

Die Boolesche Algebra wurde von dem englischen Mathematiker George Boole entwickelt und in dessen berühmter Veröffentlichung "An Investigation of the Laws of Thought" beschrieben.

Im Grunde ist die Boolsche Algebra eine Art der Mengenalgebra.

Neben George Boole haben sich noch weitere Mathematiker mit dieser Thematik auseinander gesetzt, insbesondere Claude E. Shannon. Sein Verdienst war es, die Möglichkeiten der Verwendung der Booleschen Algebra zur Berechung von Schaltnetzen erkannt zu haben.

Das von Claude Shannon grundlegend behandelte Spezialgebiet der Booleschen Algebra wird heute als Schaltalgebra bezeichnet.

Die Boolesche Algebra ist in vereinfachter Form ein System von Regeln (Postulaten und Theoremen). Dabei werden die Operationen als Boolesche Funktionen bezeichnet.

Diese Booleschen Funktionen zeichnen sich durch zwei Eigenschaften aus:

1. Jeder Operand kann nur den Wert 0 oder 1 annehmen.

2. Der Funktionswert (d.h. das Ergebnis) kann ebenfalls nur den Wert 0 oder 1 annehmen.

Zahlensystem

1 - Allgemein

Die Aufgabe der Digitaltechnik ist die ziffernmäßige Darstellung und Verarbeitung von Informationen (Informationsverarbeitung). Nun stellt sich die Frage, wie viele Zeichen benötigt werden, um zum einen Informationen unterschiedlichster Art darzustellen und zum anderen den technischen Realisierungsaufwand in Grenzen zu halten. Um zu einem Ergebnis zu gelangen, bedient sich die Mathematik unterschiedlicher Zahlensysteme. Der Mensch ist beispielsweise sehr gut mit dem dezimalen Zahlensystem vertraut. Die Verwendung dieses Zahlensystems würde jedoch einer einfachen technischen Realisierung entgegen wirken. Daher wird ein Zahlensystem mit einer in Bezug auf den Ziffernaufwand optimalen Basis gesucht.

Die Antwort auf diese Frage finden wir in der Realisierung durch einen eingeschränkten Zeichensatz, der auf eine Minimalform reduziert wurde. Dabei werden zur Informationsdarstellung nur zwei Wertigkeiten bzw. Zeichen verwendet. Die Eigenschaft, jeweils einen von zwei Werten oder Zuständen annehmen zu können, wird als "binär" (lat.: aus zwei Einheiten bestehend) bezeichnet. Die Werte, um die es sich handelt, sind die "0" und die "1". Die kleinste binäre Nachrichtenmenge, das Binärzeichen, wird als "Bit" bezeichnet, was der englischen Bezeichnung "binary digit" entstammt.

Der Vorteil einer Binärstelle liegt darin, dass sie technisch leicht durch zweiwertige Bauelemente z.B. Relais, Diode oder Transistor realisiert werden kann und das es eine ausgereifte mathematische Theorie gibt, die sich mit dem zweiwertigen Zahlensystem beschäftigt: die Boole’sche Algebra.

Eine Binärstelle reicht jedoch nicht aus, um unterschiedliche Zahlen (z.B. 0-9) darstellen zu können. Daher werden hierzu mehrere Binärstellen benötigt. Wie viele Stellen benötigt werden, hängt dabei von den Zahlen ab, die dargestellt werden sollen.

2 - Umrechnung

Eine Basis B benötigt K Stellen, um N unterschiedliche Zahlen darstellen zu können. Dabei berechnet sich N durch die Formel:

N = B hoch K

Beispiel: Mit 4 Binärstellen lassen sich

N = 2⁴

verschiedene Zahlen darstellen, nämlich die Zahlen

0 ... 15 und

0,0 ... 1,5 aber auch

-8 ... 7

Der Ziffernaufwand für die Darstellung von N Zahlen beträgt dabei dann

K = ln(N) / ln(B).

2.1 - Dezimal nach Binär

Ganze Zahlen:

Dezimalzahl 97 -> Binärzahl

97 : 2 = 48Rest 1Position 7
48 : 2 = 24Rest 0Position 6
24 : 2 = 12Rest 0Position 5
12 : 2 = 6Rest 0Position 4
6 : 2 = 3Rest 0Position 3
3 : 2 = 1Rest 1Position 2
1 : 2 = 0Rest 1Position 1

97(dez) = 1100001(bin)

Fliesskomma Zahlen:

Dezimalzahl 0,78125 -> Binärzahl

0,78125 * 2 = 1,5625= 0,5625 + 1Position 1
0,5625 * 2 = 1,125= 0,125 + 1Position 2
0,125 * 2 = 0,25= 0,25 + 0Position 3
0,25 * 2 = 0,5= 0,5 + 0Position 4
0,5 * 2 = 1,0= 0,0 + 1Position 5

0,78125(dez) = 0,11001(bin)

2.2 - Binär nach Dezimal

Hornerschema

111000,00011(bin) -> Dezimalzahl

Vorkommaanteil:

111000(bin) = 1 * 2⁵ + 1 * 2⁴ + 1 * 2³ + 0 * 2² + 0 * 2¹ + 0 * 2⁰

d = (((((1 * 2) + 1) * 2 + 1) * 2 + 0) * 2 + 0) * 2 + 0

d0 = 1= 1Position 1 (2⁵)
d1 = d0 * 2 + 1 = 1 * 2 + 1= 3Position 2 (2⁴)
d2 = d1 * 2 + 1 = 3 * 2 + 1= 7Position 3 (2³)
d3 = d2 * 2 + 0 = 7 * 2 + 0= 14Position 4 (2²)
d4 = d3 * 2 + 0 = 14 * 2 + 0= 28Position 5 (2¹)
d5 = d4 * 2 + 0 = 28 * 2 + 0= 56Position 6 (2⁰)

111000(bin) = 56(dez)

Nachkommaanteil:

0,00011(bin) = 0 * 2⁻¹ + 0 * 2⁻² + 0 * 2⁻³ + 1 * 2⁻⁴ + 1 * 2⁻⁵

d = (((((1 / 2) + 1) / 2 + 0) / 2 + 0) / 2 + 0) / 2

d5 = 1= 1Position 6 (2⁻⁵)
d4 = d5 / 2 + 1 = 1 / 2 + 1= 1,5Position 5 (2⁻⁴)
d3 = d4 / 2 + 0 = 1,5 / 2 + 1= 0,75Position 4 (2⁻³)
d2 = d3 / 2 + 0 = 0,75 / 2 + 0= 0,375Position 3 (2⁻²)
d1 = d2 / 2 + 0 = 0,375 / 2 + 0= 0,1875Position 2 (2⁻¹)
d0 = d1 / 2 + 0 = 0,1875 / 2 + 0= 0,09375Position 1 (2⁰)

0,00011(bin) = 0,09375(dez)

Arten von logischen Verknüpfungen

1 - Disjunktion [OR]

f(a,b) = a ∨ b

Die Operation a ∨ b genau dann eine 1, wenn mindestens ein Argument den Wert 1 besitzt.

Hierzu die Funktionstabelle:

abf(a,b)
000
011
101
111

Und das Schaltbild:

2 - Konjunktion [AND]

f(a,b) = a ∧ b

Die Operation a ∧ b genau dann eine 1, wenn beide Argumente den Wert 1 besitzen.

Funktionstabelle:

abf(a,b)
000
010
100
111

Schaltbild:

3 - Komplementation [NOT]

f(a,b) = a ∧ b

Die Operation a ∧ b genau dann eine 1, wenn beide Argumente den Wert 1 besitzen.

Funktionstabelle:

abf(a,b)
000
010
100
111

Schaltbild:

4 - Verknüpfung NOT und OR[NOR]

f(a,b) = a ∨ b

Die Operation a ∨ b genau dann eine 1, wenn beide Argumente den Wert 1 besitzen.

Funktionstabelle:

abf(a,b)
000
010
100
111

Schaltbild:

5 - Verknüpfung NOT und AND [NAND]

f(a,b) = a ∧ b

Die Operation a ∧ b genau dann eine 1, wenn beide Argumente den Wert 1 besitzen.

Funktionstabelle:

abf(a,b)
000
010
100
111

Schaltbild:

Boolsche Postulate und Theoreme

1 - Die Booleschen Postulate

Grundlage der Booleschen Algebra ist die Menge A mit den Elementen 0 und 1, in der die zweielementigen Operationen "∨" und "∧" (bzw. "OR" und "AND") definiert sind, so dass gilt:

  • 1: a = 0 oder a = 1 mit a ∈ A
  • 2: 0 ∧ 0 = 0
  • 3: 1 ∨ 1 = 1
  • 4: 0 ∨ 0 = 0
  • 5: 1 ∧ 1 = 1
  • 6: 1 ∧ 0 = 0 ∧ 1 = 0
  • 7: 1 ∨ 0 = 0 ∨ 1 = 1

2 - Die Booleschen Theoreme

Ein Theorem in der Booleschen Algebra ist eine Regel, die es erlaubt, logische Schaltungen in vielfältiger Form zu manipulieren bzw. zu vereinfachen.

2.1 - Kommutativgesetz (Vertauschungsgesetz)

  • a ∧ b = b ∧ a
  • a ∨ b = b ∨ a

Es ist offenbar gleich, in welcher Reihenfolge die Variablen a und b disjunktiv ("∨") bzw. konjunktiv ("∧") verknüpft werden.

2.2 - Assoziativgesetz (Zusammenfassungsgesetz)

  • (a ∧ b) ∧ c = a ∧ (b ∧ c)
  • (a ∨ b) ∨ c = a ∨ (b ∨ c)

Es ist offenbar gleich, in welcher Reihenfolge die Variablen a und b disjunktiv ("∨") bzw. konjunktiv ("∧") verknüpft werden.

2.3 - Distributivgesetz (Verteilungsgesetz)

  • a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c)
  • a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c)

Der Ausdruck a ∧ (b ∨ c) ist genau dann wahr, wenn a wahr ist und wenn b oder c wahr ist. (a ∧ b) ∨ (a ∧ c) ist genau dann wahr, wenn einer der beiden Klammerausdrücke wahr ist.

Der Ausdruck a ∨ (b ∧ c) ist genau dann wahr, wenn a wahr ist oder wenn b und c wahr ist. (a ∨ b) ∧ (a ∨ c) ist genau dann wahr, wenn beide Klammerausdrücke wahr sind.

2.4 - Idempotenzgesetz (Identitätsgesetz)

  • a ∧ a = a
  • a ∨ a = a

Die Menge ist bezüglich einer disjunktiven bzw. konjunktiven Verknüpfung mit sich selbst unverändert.

2.5 - Absorptionsgesetz (Verschmelzungsgesetz, Redundanzgesetz)

  • a ∧ (a ∨ b) = a
  • a ∨ (a ∧ b) = a

Der Ausdruck a ∧ (a ∨ b) ist genau dann wahr, wenn a wahr ist. Ist a falsch, so ist der gesamte Ausdruck falsch. Der Ausdruck wird also stets durch a bestimmt, b ist irrelevant.

Der Ausdruck a ∨ (a ∧ b) ist genau dann wahr, wenn a wahr ist. Ist a falsch, so ist der gesamte Ausdruck falsch. Der Ausdruck wird also stets durch a bestimmt, b ist irrelevant.

2.6 - Null- und Eins-Gesetz

  • 0 ∨ a = a
  • 0 ∧ a = 0
  • 1 ∨ a = 1
  • 1 ∧ a = a

2.7 - Komplement-Gesetz

  • a ∧ a = a
  • a ∨ a = a

Zu jedem Element a existiert ein komplementäres Element a. a wird Komplement von a genannt.

2.8 - Das De Morgansches Theorem

  • a ∨ b = ab
  • a ∧ b = ab

Die Umwandlung von NOR- zu UND-Schaltungen bzw. von NAND- zu ODER-Schaltungen ist unmittelbar möglich.

Dualität: Jedes Gesetz der Schaltalgebra bleibt gültig, wenn 0 und 1 sowie ∧ und ∨ vertauscht werden

Informationsgehalt und Redundanz

1 - Redundanz

In diesem Abschnitt geht es um Informationen und deren Wesentlichkeit (Informationsgehalt).

Gegeben sei ein festgelegtes Reservoir an Informationen. Diese informationen sollen im Binärsystem dargestellt werden. Mit einer Binärstelle lassen sich genau 2 Zustände (bzw. Informationen) darstellen. Also lässt sich die Anzahl der Informationen durch eine Potenz von 2 darstellen.

  • N = 2 hoch k
  • k = ln (N) / ln (2)

Für eine Information aus einem Reservoir von N = 100 Informationen ergibt sich der Informationsgehalt

  • k = ln (100) / ln (2) = 6,64 bit

Da jedoch nur eine ganzzahlige Binärstellenanzahl realisiert werden kann, muss im vorliegenden Fall für k = 7 gewählt werden. Nun lassen sich jedoch mit k = 7 Binärstellen 2 hoch 7 = 128 verschiedene Informationen darstellen, von denen jedoch nur 100 ausgenutzt werden. Also verbleiben noch 28 Binärstellen, denen keine informationen zugewiesen sind. Diesen Überschuss bezeichnet man als Redundanz.

Es gilt:

  • Redundanz = k(gesamt) - k(genutzt)

Daher ergibt sich für unser Beispiel eine Redundanz von

  • Redundanz = (7 bit – 6,64 bit) = 0,36 bit.

Die redundanten Bits eines Systems können zur Fehlererkennung genutzt werden.

1.1 - Parity Bit

Das ungerade Parity-Bit (odd)
ist immer dann gleich eins, wenn die Summe aller Einsen der Informationsbits gerade, bzw. die Summe aller Einsen des gesamten Informations-Wortes einschließlich des Parity-Bits ungerade ist. Anders ausgedrückt, ergänzt das ungerade Parity-Bit die Summe der Einsen zu einer ungeraden Anzahl.

Das gerade Parity-Bit (even)
ist immer dann gleich eins, wenn die Summe aller Einsen der Informationsbits ungerade, bzw. die Summe aller Einsen des gesamten Informations-Wortes einschließlich des Parity-Bits gerade ist. Anders ausgedrückt, ergänzt das gerade Parity-Bit die Summe der Einsen zu einer geraden Anzahl.

top