Stichpunkte

Allgemein
	NICHT sowie die Eigenschaften der mengentheoretischen Verknüpfungen Durchschnitt
	Vereinigung
	die die Eigenschaften der logischen Operatoren UND
	In der Mathematik ist eine boolesche Algebra (oder ein boolescher Verband) eine spezielle algebraische Struktur
	ODER
	Komplement abstrahiert
	Sie ist benannt nach George Boole
	der sie im 19
	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
	Oder- und Nicht-Operationen
	Boole arbeitet mit Und-
	wobei die Oder-Operation exklusiv war
	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
	~ in manchen Texten)
	∨
	¬ (bzw. ^
	v
	NOT)
	abgekürzt mit ∧
	OR
	AND
	NOR (NOT OR) und XOR (exklusives Oder)
	In Schaltkreisen benutzt man oft die Verknüpfungen NAND (NOT AND)
	· für UND (aufgrund ihrer Ähnlichkeit zur Addition und Multiplikation in anderen algebraischen Strukturen) und stellen mit einem Überstrich die Verknüpfung NICHT dar
	Mathematiker schreiben oft + für ODER
	∨ und ¬. Inhaltsverzeichnis showTocToggle("Anzeigen"
	"Verbergen") 1 Definition 2 Beispiele 2.1 Zweielementige boolesche Algebra 2.2 Andere Beispiele 3 Homomorphismen 4 Boolesche Ringe
	Ideale und Filter 5 Repräsentation boolescher Algebren [Bearbeiten]
	Hier verwenden wir die Operatoren ∧
Definition
	¬(x ∨ y) = ¬x ∧ ¬y Jede Aussage innerhalb einer booleschen Algebra hat eine duale Aussage
	für die gilt: (S
	¬0 = 1 De Morgansche Regeln: ¬(x ∧ y) = ¬x ∨ ¬y
	es ist eindeutig bestimmt Booleschen Kongruenzen (Idempotenzgesetze): x ∧ x = x
	die durch Ersetzung von 0 durch 1 und ∧ durch ∨ und umgekehrt entsteht
	d.h. ∧ und ∨ sind assoziativ und kommutativ Absorptionsgesetze: x ∧ (x ∨ y) = x
	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 ∧ y) = x und zusätzlich: Nach unten beschränkt: Es gibt ein Element 0 (Nullelement)
	Komplement)
	x ∨ ¬x = 1 Aus diesen Bedingungen folgt 0 ist das neutrale Element von ∨
	∨) ist ein Verband
	es ist eindeutig bestimmt 1 ist das neutrale Element von ∧
	Eine boolesche Algebra ist eine Menge S mit zwei darauf definierten zweistelligen Verknüpfungen ∧ (Konjunktion und
	Vereinigung <math>cup<math>) sowie einer einstelligen Verknüpfung ¬ (Negation nicht
	Durchschnitt <math>cap<math>) und ∨ (Disjunktion oder
	x ∨ 1 = 1 ¬(¬x) = x ¬1 = 0
	∧
	so dass a ∨ 0 = a für alle a Nach oben beschränkt: Es gibt ein Element 1 (Einselement)
	x ∨ x = x ∨ ist auch distributiv über ∧: x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z) x ∧ 0 = 0
	Ist die eine Aussage gültig
	dann auch ihre duale Aussage (z.B. das zweite Distributivgesetz)
	Eine boolesche Algebra ist also ein distributiver komplementärer Verband
	Man beachte
	dass die Komplemente nichts mit inversen Elementen zu tun haben
	denn die Verknüpfung eines Elementes mit seinem Komplement liefert das neutrale Element der anderen Verknüpfung
	Wie im Artikel Verband erläutert
	bei der je zwei Elemente ein Supremum und ein Infimum haben. [Bearbeiten]
	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
	Die Verknüpfungen ∧
	ODER
	∨
	NICHT
	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
	in der nur Variablen
	genau dann in einer beliebigen booleschen Algebra für jede Variablenbelegung erfüllt ist
	Die zweielementige boolesche Algebra ist auch wichtig für die Theorie allgemeiner boolescher Algebren
	wenn sie in der zweielementigen Algebra für jede Variablenbelegung erfüllt ist (was man einfach durchtesten kann)
	da jede Gleichung
	0 und 1 durch ∧
	∨ und ¬ verknüpft sind
	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
	Mit den Verknüpfungen e ∨ f = e + f − ef
	e ∧ f = ef wird A zu einer booleschen Algebra
	Boolesche Funktion. [Bearbeiten]
	Siehe auch Aussagenlogik
	Schaltalgebra
Homomorphismen
	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
	Ein Homomorphismus zwischen booleschen Algebren A
	d.h. für alle a
	der 0 auf 0 und 1 auf 1 abbildet
	dass f(¬a) = ¬f(a) für alle a aus A
	B ist ein Verbandshomomorphismus f: A -> B
	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>lor<math>) wird zu einem Ring (A
	<math>land<math>
	*)
	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
	wenn ein boolescher Ring A gegeben ist
	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
	Dieser Ring hat die Eigenschaft
	können wir sagen
	und umgekert
	Da diese zwei Operationen invers zueinander sind
	dass jeder boolesche Ring aus einer booleschen Algebra entsteht
	wenn und nur wenn sie ein Homomorphismus boolescher Ringe ist
	Weiterhin ist eine Abbildung f : A → B ein Homomorphismus boolescher Algebras
	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
	Insbesondere folgt daraus
	dass die Mächtigkeit jeder endlichen booleschen Algebra eine Zweierpotenz ist
	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.