Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenMontag, 17. Dezember 2018 

Boolesche Algebra


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.
In der Mathematik ist eine Boolesche Algebra (oder ein Boolescher Verband ) eine spezielle algebraische Struktur die die Eigenschaften der logischen Operatoren UND ODER NICHT sowie die der mengentheoretischen Verknüpfungen Durchschnitt Vereinigung Komplement abstrahiert.

Sie ist benannt nach George Boole der sie im 19. Jahrhundert definierte algebraische Methoden in der Aussagenlogik anwenden zu Er publizierte eine erste Fassung der Algebra 1847 . Sie wurde später von John Venn Stanley Jevons und Charles Peirce erweitert. Boole arbeitet mit Und- Oder- und Nicht -Operationen wobei die Oder-Operation exklusiv war. Peirce 1867 die inklusive Oder-Operation ein und bezeichnete mit einem Plus-Zeichen. Claude Shannon benutzte Boolesche Algebren erstmals zur Beschreibung Schaltungen. Heute werden sie vielfach bei der elektronischer Schaltungen angewandt.

Die Operatoren Boolescher Algebren werden auf Weisen geschrieben. Oft schreibt man sie als ODER NICHT (bzw. AND OR NOT) abgekürzt ∧ ∨ ¬ (bzw. ^ v ~ manchen Texten). In Schaltkreisen benutzt man oft Verknüpfungen NAND (NOT AND) NOR (NOT OR) XOR (exklusives Oder). Mathematiker schreiben oft + ODER · für UND (aufgrund ihrer Ähnlichkeit Addition und Multiplikation in anderen algebraischen Strukturen) und stellen einem Überstrich die Verknüpfung NICHT dar.

Hier verwenden wir die Operatoren ∧ und ¬.

Inhaltsverzeichnis

Definition

Eine Boolesche Algebra ist eine Menge S mit zwei darauf definierten zweistelligen Verknüpfungen ∧ ( Konjunktion und Durchschnitt <math>\cap</math>) und ∨ ( Disjunktion oder Vereinigung <math>\cup</math>) sowie einer einstelligen Verknüpfung ¬ ( Negation nicht Komplement) für die gilt:

( S ∧ ∨) ist ein Verband d.h.

  • ∧ und ∨ sind assoziativ und kommutativ
  • Absorptionsgesetze: x ∧ ( x y ) = x x ∨ ( x y ) = x
und zusätzlich:
  • Nach unten beschränkt: Es gibt ein 0 ( Nullelement ) so dass a ∨ 0 = a für alle a
  • Nach oben beschränkt: Es gibt ein 1 ( Einselement ) so dass a ∧ 1 = a für alle a
  • ∧ ist distributiv über ∨: x ∧ ( y z ) = ( x y ) ∨ ( x z )
  • Existenz der Komplemente : x ∧ ¬ x = 0 x ∨ ¬ x = 1

Aus diesen Bedingungen folgt

  • 1 ist das neutrale Element von ∨ es ist eindeutig bestimmt
  • 0 ist das neutrale Element von ∧ es ist eindeutig bestimmt
  • Booleschen Kongruenzen (Idempotenzgesetze): x x = x x x = x
  • ∨ ist auch distributiv über ∧: x ∨ ( y z ) = ( x y ) ∧ ( x z )
  • x ∧ 0 = 0 x ∨ 1 = 1
  • ¬(¬ x ) = x
  • ¬1 = 0 ¬0 = 1
  • De Morgansche Regeln : ¬( x y ) = ¬ x ∨ ¬ y ¬( x y ) = ¬ x ∧ ¬ y

Jede Aussage innerhalb einer Booleschen Algebra hat eine duale Aussage die durch Ersetzung von 0 durch und ∧ durch ∨ und umgekehrt entsteht. die eine Aussage gültig dann auch ihre Aussage (z.B. das zweite Distributivgesetz).

Eine boolesche Algebra ist also ein komplementärer Verband.

Man beachte dass die Komplemente nichts inversen Elementen zu tun haben denn die Verknüpfung Elementes mit seinem Komplement liefert das neutrale der anderen Verknüpfung.

Wie im Artikel Verband erläutert kann man auf S eine partielle Ordnung definieren bei der je zwei Elemente Supremum und ein Infimum haben.

Beispiele

Zweielementige Boolesche Algebra

Die wichtigste Boolesche Algebra hat nur zwei Elemente 0 und 1. Die Verknüpfungen wie folgt definiert:
Konjunktion
0 1
0 0 0
1 0 1
 
Disjunktion
0 1
0 0 1
1 1 1
 
Negation
  ¬
0 1
1 0

Diese Algebra hat Anwendungen in der Logik wo 0 als "falsch" und 1 "wahr" interpretiert werden. Die Verknüpfungen ∧ ∨ entsprechen den logischen Verknüpfungen UND ODER NICHT. in dieser Algebra heißen Boolesche Ausdrücke .

Auch für elektrische Schaltungen wird diese verwendet. Hier entsprechen 0 und 1 zwei Spannungszuständen . Das Eingangs-Ausgangs-Verhalten jeder möglichen elektrischen Schaltung durch einen Booleschen Ausdruck modelliert werden.

Die zweielementige Boolesche Algebra ist auch für die Theorie allgemeiner Boolescher Algebren da Gleichung in der nur Variablen 0 und durch ∧ ∨ und ¬ verknüpft sind dann in einer beliebigen Booleschen Algebra für Variablenbelegung erfüllt ist wenn sie in der Algebra für jede Variablenbelegung erfüllt ist (was einfach durchtesten kann). Zum Beispiel gelten die beiden Aussagen (engl. Name: Consensus Theorems ) in jeder Booleschen Algebra:

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

Andere Beispiele

Die Potenzmenge P( S ) einer Menge S wird mit Durchschnitt und Vereinigung zu Booleschen Algebra. Dabei ist 0 die leere und 1 ist S selbst. Dieser Verband heißt Teilmengenverband oder Mengenalgebra von S . Alle Teilverbände eines Teilmengenverbandes sind distributiv.

Die Menge aller endlichen oder ko-endlichen von N 0 bildet mit Durchschnitt und Vereinigung eine Algebra.

Für jede natürliche Zahl n ist die Menge aller positiven Teiler n mit den Verknüpfungen ggT und kgV distributiber beschränkter Verband. Dabei ist 1 das und n das Einselement. Der Verband ist Boolesch dann wenn n quadratfrei ist. Dieser Verband heißt Teilerverband von n .

Für jeden topologischen Raum X ist die Menge aller offenen abgeschlossenen eine Boolesche Algebra mit Durchschnitt und Vereinigung.

Ist R ein Ring dann definieren wir die Menge

A = { e in R : e 2 = e und ex = xe für alle x in R }
aller idempotenten Elemente des Zentrums. Mit Verknüpfungen e ∨ f = e + + ef e ∧ f = ef A zu einer Booleschen Algebra.

Siehe auch Aussagenlogik Schaltalgebra .

Homomorphismen

Ein Homomorphismus zwischen Booleschen Algebren A B ist ein Verbands-Homomorphismus f : A -> B der 0 auf 0 und 1 1 abbildet d.h. für alle a b aus A gilt:

  • f ( a b ) = f ( a ) ∨ f ( b )
  • f ( a b ) = f ( a ) ∧ f ( b )
  • f (0) = 0
  • f (1) = 1

Es folgt daraus dass f a ) = ¬ f ( a ) für alle a aus A . Die Klasse aller Booleschen Algebren wird mit diesem eine Kategorie . Ist ein Homomorphismus f zusätzlich bijektiv dann heißt f Isomorphismus und A und B heißen isomorph .

Boolesche Ringe Ideale und Filter

Noch aus dem englischen Artikel zu übersetzen.

Repräsentation Boolescher Algebren


Zu jeder endlichen Booleschen Algebra B gibt es eine endliche Menge X so dass B zu P( X ) isomorph ist. Insbesondere folgt daraus dass Mächtigkeit jeder endlichen Booleschen Algebra eine Zweierpotenz

Text über das "Stone Repräsentations-Theorem" ist noch dem englischen Artikel zu übersetzen.



Bücher zum Thema Boolesche Algebra

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

ImpressumLesezeichen setzenSeite versendenSeite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Boolesche_Algebra.html">Boolesche Algebra </a>