Boolesche Algebra

Stichpunkte

Allgemein
	Komplement abstrahiert
	Vereinigung
	die die Eigenschaften der logischen Operatoren UND
	ODER
	NICHT sowie die Eigenschaften der mengentheoretischen Verknüpfungen Durchschnitt
	In der Mathematik ist eine boolesche Algebra (oder ein boolescher Verband) eine spezielle algebraische Struktur
	der sie im 19
	Sie ist benannt nach George Boole
	um algebraische Methoden in der Aussagenlogik anwenden zu können
	Jahrhundert definierte
	Er publizierte eine erste Fassung der Algebra 1847
	Sie wurde später von John Venn
	W
	Stanley Jevons und Charles Peirce erweitert
	wobei die Oder-Operation exklusiv war
	Oder- und Nicht-Operationen
	Boole arbeitet mit Und-
	Peirce führte 1867 die inklusive Oder-Operation ein und bezeichnete sie mit einem Plus-Zeichen
	Claude Shannon benutzte Boolesche Algebren erstmals zur Beschreibung elektrischer Schaltungen
	Heute werden sie vielfach bei der Entwicklung elektronischer Schaltungen angewandt
	Die Operatoren boolescher Algebren werden auf verschiedene Weisen geschrieben
	NICHT (bzw
	Oft schreibt man sie als UND
	ODER
	OR
	NOT)
	∨
	¬ (bzw. ^
	~ in manchen Texten)
	AND
	v
	abgekürzt mit ∧
	NOR (NOT OR) und XOR (exklusives Oder)
	In Schaltkreisen benutzt man oft die Verknüpfungen NAND (NOT AND)
	Mathematiker schreiben oft + für ODER
	· für UND (aufgrund ihrer Ähnlichkeit zur Addition und Multiplikation in anderen algebraischen Strukturen) und stellen mit einem Überstrich die Verknüpfung NICHT dar
	"Verbergen") 1 Definition 2 Beispiele 2.1 Zweielementige boolesche Algebra 2.2 Andere Beispiele 3 Homomorphismen 4 Boolesche Ringe
	Hier verwenden wir die Operatoren ∧
	∨ und ¬. Inhaltsverzeichnis showTocToggle("Anzeigen"
	Ideale und Filter 5 Repräsentation boolescher Algebren [Bearbeiten]
Definition
	es ist eindeutig bestimmt 1 ist das neutrale Element von ∧
	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
	Vereinigung <math>cup<math>) sowie einer einstelligen Verknüpfung ¬ (Negation nicht
	∧
	Komplement)
	x ∨ ¬x = 1 Aus diesen Bedingungen folgt 0 ist das neutrale Element von ∨
	die durch Ersetzung von 0 durch 1 und ∧ durch ∨ und umgekehrt entsteht
	x ∨ x = x ∨ ist auch distributiv über ∧: x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z) x ∧ 0 = 0
	Durchschnitt <math>cap<math>) und ∨ (Disjunktion oder
	x ∨ (x ∧ y) = x und zusätzlich: Nach unten beschränkt: Es gibt ein Element 0 (Nullelement)
	¬(x ∨ y) = ¬x ∧ ¬y Jede Aussage innerhalb einer booleschen Algebra hat eine duale Aussage
	∨) ist ein Verband
	x ∨ 1 = 1 ¬(¬x) = x ¬1 = 0
	für die gilt: (S
	d.h. ∧ und ∨ sind assoziativ und kommutativ Absorptionsgesetze: x ∧ (x ∨ y) = x
	es ist eindeutig bestimmt Booleschen Kongruenzen (Idempotenzgesetze): x ∧ x = x
	¬0 = 1 De Morgansche Regeln: ¬(x ∧ y) = ¬x ∨ ¬y
	Eine boolesche Algebra ist eine Menge S mit zwei darauf definierten zweistelligen Verknüpfungen ∧ (Konjunktion und
	so dass a ∨ 0 = a für alle a Nach oben beschränkt: Es gibt ein Element 1 (Einselement)
	dann auch ihre duale Aussage (z.B. das zweite Distributivgesetz)
	Ist die eine Aussage gültig
	Eine boolesche Algebra ist also ein distributiver komplementärer Verband
	denn die Verknüpfung eines Elementes mit seinem Komplement liefert das neutrale Element der anderen Verknüpfung
	Man beachte
	dass die Komplemente nichts mit inversen Elementen zu tun haben
	bei der je zwei Elemente ein Supremum und ein Infimum haben. [Bearbeiten]
	Wie im Artikel Verband erläutert
	kann man auf S eine partielle Ordnung definieren
Beispiele
	[Bearbeiten]
Zweielementige boolesche Algebra
	Die wichtigste boolesche Algebra hat nur die zwei Elemente 0 und 1
	wo 0 als "falsch" und 1 als "wahr" interpretiert werden
	Die Verknüpfungen sind 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
	¬ entsprechen den logischen Verknüpfungen UND
	∨
	NICHT
	Die Verknüpfungen ∧
	ODER
	Ausdrücke in dieser Algebra heißen boolesche Ausdrücke
	Auch für elektrische Schaltungen wird diese Algebra verwendet
	Hier entsprechen 0 und 1 zwei Spannungszuständen
	Das Eingangs-Ausgangs-Verhalten jeder möglichen elektrischen Schaltung kann durch einen booleschen Ausdruck modelliert werden
	0 und 1 durch ∧
	wenn sie in der zweielementigen Algebra für jede Variablenbelegung erfüllt ist (was man einfach durchtesten kann)
	in der nur Variablen
	da jede Gleichung
	Die zweielementige boolesche Algebra ist auch wichtig für die Theorie allgemeiner boolescher Algebren
	∨ und ¬ verknüpft sind
	genau dann in einer beliebigen booleschen Algebra für jede Variablenbelegung erfüllt ist
	Zum Beispiel gelten die folgenden 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) [Bearbeiten]
Andere Beispiele
	Die Potenzmenge P(S) einer Menge S wird mit Durchschnitt und Vereinigung zu einer booleschen Algebra
	Dabei ist 0 die leere Menge 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 koendlichen Teilmengen von N0 bildet mit Durchschnitt und Vereinigung eine boolesche Algebra
	Für jede natürliche Zahl n ist die Menge aller positiven Teiler von n mit den Verknüpfungen ggT und kgV ein distributiver beschränkter Verband
	Dabei ist 1 das Nullelement und n das Einselement
	wenn n quadratfrei ist
	Der Verband ist boolesch genau dann
	Dieser Verband heißt Teilerverband von n
	Für jeden topologischen Raum X ist die Menge aller offenen abgeschlossenen Teilmengen eine boolesche Algebra mit Durchschnitt und Vereinigung
	dann definieren wir die Menge A = { e in R : e2 = e und ex = xe für alle x in R } aller idempotenten Elemente des Zentrums
	Ist R ein Ring
	e ∧ f = ef wird A zu einer booleschen Algebra
	Mit den Verknüpfungen e ∨ f = e + f − ef
	Siehe auch Aussagenlogik
	Boolesche Funktion. [Bearbeiten]
	Schaltalgebra
Homomorphismen
	Ein Homomorphismus zwischen booleschen Algebren 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
	B ist ein Verbandshomomorphismus f: A -> B
	d.h. für alle a
	dass f(¬a) = ¬f(a) für alle a aus A
	der 0 auf 0 und 1 auf 1 abbildet
	Die Klasse aller booleschen Algebren wird mit diesem Homomorphismenbegriff eine Kategorie
	dann heißt f Isomorphismus und A und B heißen isomorph. [Bearbeiten]
	Ist ein Homomorphismus f zusätzlich bijektiv
Boolesche Ringe, Ideale und Filter
	<math>land<math>
	<math>lor<math>) wird zu einem Ring (A
	+
	Jede boolesche Algebra (A
	*)
	indem man definiert: a + b = (a <math>land<math> ¬b) <math>lor<math> (b <math>land<math> ¬a) (diese Operation nennt man "symmetrische Differenz" bei Mengen und XOR in der Aussagenlogik) und a * b = a <math>land<math> b. Das Nullelement dieses Ringes entspricht der 0 der booleschen Algebra; das neutrale Element der Multiplikation ist die 1 der booleschen Algebra
	Dieser Ring hat die Eigenschaft
	können wir ihn in eine boolesche Algebra umwandeln
	indem wir definieren: x <math>lor<math> y = x + y − xy und x <math>land<math> y = xy
	dass a * a = a für alle a in A; Ringe mit dieser Eigenschaft werden Boolesche Ringe genannt. Umgekehrt
	wenn ein boolescher Ring A gegeben ist
	Da diese zwei Operationen invers zueinander sind
	dass jeder boolesche Ring aus einer booleschen Algebra entsteht
	und umgekert
	können wir sagen
	Weiterhin ist eine Abbildung f : A → B ein Homomorphismus boolescher Algebras
	wenn und nur wenn sie ein Homomorphismus boolescher Ringe ist
	Die Kategorien boolescher Ringe und boolescher Algebras sind äquivalent. Ideale und Filter noch aus dem englischen Artikel zu übersetzen. [Bearbeiten]
Repräsentation boolescher Algebren
	so dass B zu P(X) isomorph ist
	Zu jeder endlichen booleschen Algebra B gibt es eine endliche Menge X
	dass die Mächtigkeit jeder endlichen booleschen Algebra eine Zweierpotenz ist
	Insbesondere folgt daraus
	Text über das "Stone Repräsentationstheorem" ist noch aus dem englischen Artikel zu übersetzen. bg:Булева алгебра en:Boolean algebra es:Ã?lgebra de Boole fr:Algèbre de Boole he:×?לגברה בולי×?נית it:Algebra di Boole ja:ブール代数 lt:BÅ«lio algebra nl:Booleaanse algebra pl:Algebra Boole'a pt:Ã?lgebra Booleana sl:Boolova algebra sv:Boolesk algebra zh:布尔代数

Dieser Artikel basiert auf dem Artikel Boolesche Algebra aus der freien Enzyklopädie wikipedia und steht unter der GNU Lizenz für freie Dokumentation. In der wikipedia ist eine Liste der Autoren verfügbar.