Up !
Illner Solutions




3. 2. 2  Boolesche Algebra  B


In diesem Abschnitt kommt die Mathematik zur klassischen zweiwertigen Aussagenlogik AL2.
Durch die Betrachtung als algebraische Struktur kann man besser verstehen, weshalb die logischen Operatoren so funktionieren, wie sie es tun.

Eine boolesche Algebra braucht nicht zweiwertig zu sein, doch diese ist die bekannte boolesche Algebra. Sie findet ihre Anwendung in der Schaltalgebra für digitale Schaltungen.





3. 2. 2. 1  Definition

3. 2. 2. 2  Zweielementige boolesche Algebra

3. 2. 2. 3  Vierelementige boolesche Algebra

3. 2. 2. 4  Anwendung als Schaltalgebra






3. 2. 2. 1  Definition

Die Algebra, Teilgebiet der Mathematik, konstruiert aus Mengen Strukturen, indem sie diese mit inneren Verknüpfungen versieht, z.B. Rechenoperationen bei Zahlenmengen. Eine boolesche Algebra[WP] ist ein komplementärer distributiver Verband. Die Anzahl der Elemente ist nicht festgelegt. Sie wurde ab dem 19. Jh. von Nachfolgern George Booles ausgearbeitet.
Sie stellt eine allgemeinere Formulierung der klassischen Aussagenlogik AL2 dar. Sie umfasst außerdem die einfache Mengenlehre.

Eine boolesche Algebra besteht zunächst aus einer Menge an Elementen, mit denen etwas gemacht werden soll, der Trägermenge. Man kann zeigen, dass die Trägermengen die Mächtigkeit 2^n haben müssen.
=> Mögliche Mächtigkeiten: 1, 2, 4, 8, ...
Der Spezialfall mit zwei Elementen ist die bekannte Schaltalgebra, welche isomorph zur Aussagenlogik AL2 ist.

Zurück zur Algebra, eine boolesche Algebra ist also ein komplementärer distributiver Verband. Ein Verband hat zwei Verknüpfungen, die ein Minimum und ein Maximum in der Trägermenge bestimmen. Distributiv meint zusätzlich, man kann mit den Verknüpfungen Klammern ausmultiplizieren. Komplementär bedeutet, die Elemente haben zwar keine Inversen, aber sog. Komplemente über die beiden Verknüpfungen hinweg. Die beiden Verknüpfungen sind also verzahnt.

Eine Menge B wird zu einem komplementären distributiven Verband bzw. einer booleschen Algebra, wenn man zwei Operatoren (Verknüpfungen) mit bestimmten Eigenschaften definiert.


(B, +, 0, *, 1) ist ein komplementärer distributiver Verband, gdw.

1)  (B, +, *) ist ein Verband.

1.1)  (B, +) ist eine kommutative Halbgruppe.
– (B, +) ist abgeschlossen, assoziativ (Reihenfolge egal) und kommutativ (symmetrisch).

1.2)  (B, *) ist eine kommutative Halbgruppe.
– (B, *) ist abgeschlossen, assoziativ (Reihenfolge egal) und kommutativ (symmetrisch).

1.3)  Bei (B, +, *) gelten die Absorptionsgesetze.
- dann auch Idempotenzgesetze ?
– ..., vollständig, kompakt, beschränkt ?

2)  (B, +, *) ist distributiv.
– Wechselwirkung bzgl. Ausmultiplizieren.

3)  (B, +, 0, *, 1) ist komplementär. (Es reicht nicht zu den Inversen, dann wäre B ein Körper wie die Zahlen Q und R.)

3.1)  (B, +, *) ist beschränkt.
– Es gibt Nullelement und Einselement: je ein neutrales Element, das mit der Partner-Operation absorbierend ist.
– Ein endlicher (nichtleerer) Verband ist immer vollständig und somit auch beschränkt.

3.2)  zu jedem Element gibt es (mindestens) ein Komplement.
– ergibt einmal 0 und einmal 1.


=>  In einem distributiven komplementären Verband gibt es immer genau ein Komplement a-quer. (Aus dem Komplement wird der Nicht-Operator von AL2 kontruiert).

Die obigen Eigenschaften lassen sich für die Praxis reduzieren auf das Axiomensystem der booleschen Algebra nach Huntington:

Es gibt eine Menge B mit zwei zweistelligen Verknüpfungen. Diese haben die folgenden Eigenschaften:

1)  2 x Kommutativität: (1) und (1’) [ <- Nr.n aus Regel-Liste vermutlich]
2)  2 x Distributivität: (4) und (4’)
3)  2 x Existenz neutraler Elemente: Es gibt Elemente 0 ∈ B und 1 ∈ B, so dass (5) und (5’)
4)  Existenz von Komplementen: Zu jedem a ∈ B gibt es ¬ a ∈ B, so dass (9) und (9’)



3. 2. 2. 2  Zweielementige boolesche Algebra

Die kleinste boolesche Algebra hat nur ein Element. Da passiert aber noch nichts, da die Junktoren nichts ausrichten.
Die kleinste sinnvolle boolesche Algebra hat eine zweielementiger Trägermenge. Dies ist die minimale echte boolesche Algebra B2, mit den beiden Elementen 0 und 1. Das bedeutet, sie besteht nur aus dem Null- und Einselement ihrer beiden Verknüpfungen. Hier wird also nicht gerade klassisch gerechnet, sondern zwischen zwei Werten gependelt. Das ist die zweiwertige Logik.


Trägermenge  B2  =  { 0, 1 }

1) (B2, +, *) ist ein Verband: 2 x kommutative Halbgruppe, 2 x Absorptionsgesetze.

1.1) (B2, +) ist eine kommutative Halbgruppe.
- (B2, +) ist abgeschlossen, assoziativ (Reihenfolge egal) und kommutativ (symmetrisch).

1.2) (B2, *) ist eine kommutative Halbgruppe.
- (B2, *) ist abgeschlossen, assoziativ (Reihenfolge egal) und kommutativ (symmetrisch).

1.3) Bei (B2, +, *) gelten die Absorptionsgesetze:
- a + (a*b)  =  a  und  a * (a+b)  =  a

2) (B2, +, *) ist distributiv:
- a + (b*c)  =  (a+b) * (a+c)
- a * (b+c)  =  (a*b) + (a*c)

3) (B2, +, *) ist komplementär:
- 0-quer = 1  und  1-quer = 0


Die zweiwertige boolesche Algebra ist gerade die Schaltalgebra, auf der digitale Schaltungen und sämtliche Mikrochips beruhen.
Die Schaltalgebra ist isomorph zur Aussagenlogik AL2, wobei (B, +, 0, *, 1) einfach (L, ∨, F ,∧ ,W) genannt wird.



3. 2. 2. 3  Vierelementige boolesche Algebra

Die nächstgrößere boolesche Algebra hat eine vierelementiger Trägermenge. mit n = 2^2 = 4. Nach [Quelle] ist jede mögliche boolesche Algebra isomorph? zu einer Mengenalgebra. Hier nimmt man die Potenzmenge einer Grundmenge als Elemente der Algebra. Krass oder ?

Doch Contenonce(?). Zur Konstruktion der vierelementigen booleschen Algebra nimmt man eine Menge  M  =  {a, b}
→  Trägermenge  B4  =  { 0, {a}, {b}, {a, b} }
So erhalten wir vier Elemente. Hätten wir minimalistisch nur M = {a} gewählt, hätten wir eine ismorphe? Struktur zu B2 mit { 0, {a} } erhalten. Als Verknüpfungen +, * haben wir bei der Mengenalgebra Vereinigung und Durchschnitt, um auf ein anderes Element zu kommen.

Die Komplemente sind (remember: die Verknüpfungen mit den Komplementen sollen das je andere neutrale Element bilden):

KomplementUND beiderODER beider
0{a, b}0{a, b}
{a}{b}0{a, b}
{b}{a}0{a, b}
{a, b}00{a, b}


[ Anmerkung: Ist das bereits unsere später gesuchte vierwertige Aussagenlogik ? Leider nein, denn unsere dortigen Verknüpfungen erzeugen nicht zu allen vier Werten Komplemente. Wir werden jedoch später sehen, dass es eine ähnliche algebraische Struktur wie die boolesche Algebra gibt, die dafür adäquat ist. ]



3. 2. 2. 4  Anwendung als Schaltalgebra

Die zweite große Anwendung der zweiwertigen booleschen Algebra ist neben der Aussgenlogik die Schaltalgebra für digitale Schaltungen. Sie wurde hauptsächlich in der Diplomarbeit(!) von Claude Shannon von 1937 ausgearbeitet.
Sie dient zur Berechnung in Schaltnetzen und Schaltwerken (digitale Speicher?).

Die technische Realisierung von digitalen Schaltungen bzw. Gattern[WP] begann im 19. Jh. mit elektromechanischen Relais. Ab 1900 benutzte man Elektronenröhren[WP], dann kamen Transistoren[WP], die stetig in integrierten Schaltungen (Chips) zusammengefasst werden konnten. (2000 hatte der Pentium 4 bereits 42 mio Transistoren, 2014 hatte man auf einem Mikroprozessor bereits einige mrd Transistoren bzw. ... Nand-Gatter.)


Schaltnetze

Schaltnetze[WP] sind Netze von elektrische Schaltungen bzw. Gattern, die durch logische Schaltungen bzw. Schaltglieder modelliert werden. Es gibt Eingänge, an denen Strom anliegt bzw. die den Wert 1 bzw. W haben. Wenn kein Strom anliegt, so haben sie den Wert 0 bzw. F. Der oder die Eingänge werden zu einem Ausgangssignal kombiniert, das wieder als Eingangssignal für weitere Gatter dient.
Mit Schaltnetzen werden boolesche Funktionen realisiert, bei denen mehrere Eingänge zu einem definierten Ausgangsergebnis abgebildet bzw. berechnet werden. Das entspricht genau der Auswertung einer aussagenlogischen Formel.

Es werden ein einstelliges Gatter und sechs zweistellige Gatter verwendet. Diese lassen sich auf die drei Operatoren der booleschen Algebra zurückführen:
Wie schon in [3.2.1.2] erwähnt genügen auch nur NAND-Gatter oder nur NOR-Gatter, um ... denn sie sind funktional vollständig.


Schaltwerke

Schaltwerke[WP] sind Schaltnetze mit einer zeitverzögerten Rückkopplung, d.h. einige Ausgangssignale werden einen Takt später wieder zu Eingangssignalen vorgelagerter Gatter.
Das ist genial, denn so kann ein speichernder Charakter realisiert werden.




Erstmals kreiert am – Donnerstag, 19. Oktober 2006
Letzrmals geändert am – Samstag, 04. Januar 2020
Autor: Korgüll

Copyright 2006 – 2020  Illner Solutions