Boolesche Algebren kanonisch definiert - Boolean algebras canonically defined

Boolesche Algebren sind Modelle der Gleichungstheorie zweier Werte; diese Definition ist äquivalent zu den Gitter- und Ringdefinitionen.

Die Boolesche Algebra ist ein mathematisch reicher Zweig der abstrakten Algebra . So wie sich die Gruppentheorie mit Gruppen befasst und die lineare Algebra mit Vektorräumen , sind Boolesche Algebren Modelle der Gleichungstheorie der beiden Werte 0 und 1 (deren Interpretation nicht numerisch sein muss). Booleschen Algebren, Gruppen und Vektorräumen gemeinsam ist die Vorstellung einer algebraischen Struktur , einer Menge, die unter null oder mehr Operationen abgeschlossen ist, die bestimmte Gleichungen erfüllen.

So wie es grundlegende Beispiele für Gruppen gibt, wie die Gruppe Z von ganzen Zahlen und die Permutationsgruppe S n von Permutationen von n Objekten, gibt es auch grundlegende Beispiele für Boolesche Algebra wie die folgenden.

Die Boolesche Algebra erlaubt somit die Anwendung der Methoden der abstrakten Algebra auf die mathematische Logik , die digitale Logik und die mengentheoretischen Grundlagen der Mathematik .

Im Gegensatz zu Gruppen endlicher Ordnung , die Komplexität und Diversität aufweisen und deren Theorie erster Ordnung nur in speziellen Fällen entscheidbar ist, teilen alle endlichen Booleschen Algebren die gleichen Theoreme und haben eine entscheidbare Theorie erster Ordnung. Stattdessen werden die Feinheiten der Booleschen Algebra zwischen der Struktur unendlicher Algebren und der algorithmischen Komplexität ihrer syntaktischen Struktur aufgeteilt.

Definition

Die Boolesche Algebra behandelt die Gleichungstheorie der maximalen zweielementigen finitären Algebra, die als Boolescher Prototyp bezeichnet wird , und die Modelle dieser Theorie, die als Boolesche Algebren bezeichnet werden . Diese Begriffe sind wie folgt definiert.

Eine Algebra ist eine Familie von Operationen auf einer Menge, die der Algebra zugrunde liegende Menge genannt wird. Wir nehmen die zugrunde liegende Menge des Booleschen Prototyps als {0,1} an.

Eine Algebra ist endlich, wenn jede ihrer Operationen nur endlich viele Argumente benötigt. Beim Prototyp ist jedes Argument einer Operation entweder 0 oder 1 , ebenso wie das Ergebnis der Operation. Die maximale solche Algebra besteht aus allen endlichen Operationen auf {0,1}.

Die Anzahl der Argumente, die von jeder Operation verwendet werden, wird als Arität der Operation bezeichnet. Eine Operation auf {0,1} der Arität n oder eine n- äre Operation kann auf jeden von 2 n möglichen Werten für seine n Argumente angewendet werden . Für jede Auswahl von Argumenten kann die Operation 0 oder 1 zurückgeben , daher gibt es 2 2 n n- äre Operationen.

Der Prototyp hat daher zwei Operationen ohne Argumente, die als nulläre oder nulläre Operationen bezeichnet werden, nämlich null und eins. Es hat vier unäre Operationen , von denen zwei konstante Operationen sind, eine andere ist die Identität, und die am häufigsten verwendete, genannt Negation , gibt das Gegenteil ihres Arguments zurück: 1 wenn 0 , 0 wenn 1 . Es hat sechzehn binäre Operationen ; wieder sind zwei davon konstant, ein anderer gibt sein erstes Argument zurück, ein anderer gibt sein zweites zurück, eines heißt Konjunktion und gibt 1 zurück, wenn beide Argumente 1 sind und ansonsten 0, ein anderes heißt Disjunktion und gibt 0 zurück, wenn beide Argumente 0 sind und ansonsten 1 , und so weiter. Die Anzahl der ( n + 1) -ären Operationen im Prototyp ist das Quadrat der Anzahl der n- ären Operationen, also gibt es 16 2 = 256 ternäre Operationen, 256 2 = 65.536 quaternäre Operationen und so weiter.

Eine Familie wird durch einen Indexsatz indiziert . Im Fall einer Familie von Operationen, die eine Algebra bilden, werden die Indizes Operationssymbole genannt und bilden die Sprache dieser Algebra. Die von jedem Symbol indizierte Operation wird als Bezeichnung oder Interpretation dieses Symbols bezeichnet. Jedes Operationssymbol spezifiziert die Stelligkeit seiner Interpretation, daher haben alle möglichen Interpretationen eines Symbols die gleiche Stelligkeit. Im Allgemeinen ist es für eine Algebra möglich, verschiedene Symbole mit derselben Operation zu interpretieren, dies ist jedoch nicht der Fall für den Prototyp, dessen Symbole mit seinen Operationen in Eins-eins-Entsprechung stehen. Der Prototyp hat daher 2 2 n n- äre Operationssymbole, die als Boolesche Operationssymbole bezeichnet werden und die Sprache der Booleschen Algebra bilden. Nur wenige Operationen haben konventionelle Symbole wie ¬ für Negation, ∧ für Konjunktion und ∨ für Disjunktion. Es ist bequem , die zu berücksichtigen i -te n seinen ary Symbol n f i , wie in dem Abschnitt über getan unter Wahrheitstabellen .

Eine Gleichungstheorie in einer gegebenen Sprache besteht aus Gleichungen zwischen Termen, die aus Variablen unter Verwendung von Symbolen dieser Sprache aufgebaut sind. Typische Gleichungen in der Sprache der Booleschen Algebra sind x ∧ y = y ∧ x , x ∧ x = x , x ¬ x = y ¬ y und x ∧ y = x .

Eine Algebra erfüllt eine Gleichung, wenn die Gleichung für alle möglichen Werte ihrer Variablen in dieser Algebra gilt, wenn die Operationssymbole wie von dieser Algebra spezifiziert interpretiert werden. Die Gesetze der Booleschen Algebra sind die Gleichungen in der Sprache der Booleschen Algebra, die der Prototyp erfüllt. Die ersten drei der obigen Beispiele sind Boolesche Gesetze, aber nicht das vierte, da 1∧0 ≠ 1 .

Die Gleichungstheorie einer Algebra ist die Menge aller Gleichungen, die von der Algebra erfüllt werden. Die Gesetze der Booleschen Algebra bilden daher die Gleichungstheorie des Booleschen Prototyps.

Ein Modell einer Theorie ist eine Algebra, die die Operationssymbole in der Sprache der Theorie interpretiert und die Gleichungen der Theorie erfüllt.

Eine Boolesche Algebra ist ein beliebiges Modell der Gesetze der Booleschen Algebra.

Das heißt, eine Boolesche Algebra ist eine Menge und eine Familie von Operationen darauf, die die Booleschen Operationssymbole interpretieren und die gleichen Gesetze wie der Boolesche Prototyp erfüllen.

Wenn wir ein Homolog einer Algebra als Modell der Gleichungstheorie dieser Algebra definieren, dann kann eine Boolesche Algebra als jedes Homolog des Prototyps definiert werden.

Beispiel 1 . Der Boolesche Prototyp ist eine Boolesche Algebra, da er trivialerweise ihre eigenen Gesetze erfüllt. Sie ist somit die prototypische Boolesche Algebra. Wir haben es anfangs nicht so genannt, um jeden Anschein von Zirkularität in der Definition zu vermeiden.

Basis

Die Operationen müssen nicht alle explizit angegeben werden. Eine Basis ist jede Menge, aus der die verbleibenden Operationen durch Komposition erhalten werden können. Eine "Boolesche Algebra" kann aus einer von mehreren verschiedenen Basen definiert werden. Drei Basen für die Boolesche Algebra sind gebräuchlich, die Gitterbasis, die Ringbasis und die Sheffer-Strich- oder NAND-Basis. Diese Grundlagen verleihen dem Subjekt jeweils einen logischen, einen arithmetischen und einen sparsamen Charakter.

  • Die Gitterbasis entstand im 19. Jahrhundert mit der Arbeit von Boole , Peirce und anderen, die eine algebraische Formalisierung logischer Denkprozesse suchten.
  • Der Ring Basis entstand im 20. Jahrhundert mit der Arbeit von Zhegalkin und Stein und wurde von einem Hintergrund die Grundlage der Wahl für Algebraiker auf das Thema in den kommenden abstrakten Algebra . Die meisten Behandlungen der Booleschen Algebra gehen von der Gitterbasis aus, eine bemerkenswerte Ausnahme bildet Halmos [1963], dessen Hintergrund der linearen Algebra ihm offenbar die Ringbasis beliebt machte.
  • Da alle finitären Operationen auf {0,1} durch das Sheffer-Stroke- NAND (oder sein duales NOR) definiert werden können, ist die daraus resultierende wirtschaftliche Grundlage die Basis der Wahl für die Analyse digitaler Schaltungen , insbesondere von Gate-Arrays in der digitalen Elektronik .

Die gemeinsamen Elemente der Gitter- und Ringbasen sind die Konstanten 0 und 1 und eine assoziative kommutative binäre Operation , genannt treffen x ∧ y in der Gitterbasis und Multiplikation xy in der Ringbasis. Die Unterscheidung ist nur terminologisch. Die Gitterbasis hat die weiteren Operationen verbinden , x ∨ y und Komplement , ¬ x . Die Ringbasis hat stattdessen die arithmetische Operation x ⊕ y der Addition (das Symbol ⊕ wird vor + verwendet, da letzteres manchmal die Boolesche Lesart von Join erhält).

Eine Basis zu sein bedeutet, alle anderen Operationen durch Komposition zu ergeben, weshalb zwei beliebige Basen ineinander übersetzbar sein müssen. Die Gitterbasis übersetzt x ∨ y an die Ringbasis als x ⊕ y ⊕ xy und ¬ x als x ⊕1 . Umgekehrt wird der Ring Basis übersetzt x ⊕ y der Gitterbasis als ( x ∨ y ) ¬ ( x ∧ y ) .

Beide Basen ermöglichen die Definition von Booleschen Algebren über eine Teilmenge der Gleichungseigenschaften der Booleschen Operationen. Für die Gitterbasis genügt es , eine Boolesche Algebra als definieren distributive Gitter befriedigend x ¬ x = 0 und x ∨¬ x = 1 , eine so genannte komplementierten distributive Gitter. Die Ringbasis macht aus einer Booleschen Algebra einen Booleschen Ring , nämlich einen Ring mit x 2 = x .

Emil Post stellte eine notwendige und hinreichende Bedingung für eine Reihe von Operationen als Grundlage für die nicht nullen Booleschen Operationen. Eine nichttriviale Eigenschaft wird von einigen, aber nicht allen Operationen, die eine Basis bilden, geteilt. Post listete fünf nichttriviale Eigenschaften von Operationen auf, die mit den fünf Post-Klassen identifizierbar sind , die jeweils durch Komposition erhalten bleiben, und zeigte, dass eine Menge von Operationen eine Grundlage bildete, wenn die Menge für jede Eigenschaft eine Operation enthielt, der diese Eigenschaft fehlte. (Das Gegenteil von Posts Theorem, das "if" zu " wenn und nur wenn " erweitert, ist die einfache Beobachtung, dass eine Eigenschaft von diesen fünf, die jede Operation auf einer Kandidatenbasis hält, auch für jede Operation gilt, die durch Komposition aus diesem Kandidaten gebildet wird , weshalb der Kandidat aufgrund der Nichttrivialität dieser Eigenschaft nicht als Grundlage dienen kann.) Die fünf Eigenschaften von Post sind:

  • monoton , kein 0-1-Eingangsübergang kann einen 1-0-Ausgangsübergang verursachen;
  • affin , darstellbar mit Zhegalkin-Polynomen , denen bilineare oder höhere Terme fehlen, zB x ⊕ y ⊕1, aber nicht xy ;
  • selbstdual , so dass das Komplementieren aller Eingaben die Ausgabe ergänzt, wie bei x oder dem Medianoperator xy ⊕ yz ⊕ zx oder deren Negationen;
  • strikt (Abbilden der ausschließlich aus Nullen bestehenden Eingabe auf Null);
  • costrict (alle-Einsen auf eins abbilden).

Das NAND (dually NOR) Operation fehlt alle diese, damit eine Grundlage für sich bildet.

Wahrheitstabellen

Die finitären Operationen auf {0,1} können als Wahrheitstabellen dargestellt werden , wobei man sich 0 und 1 als die Wahrheitswerte false und true vorstellt . Sie können einheitlich und anwendungsunabhängig so gestaltet werden, dass wir sie individuell benennen oder zumindest nummerieren können. Diese Namen bieten eine bequeme Abkürzung für die booleschen Operationen. Die Namen der n- ären Operationen sind Binärzahlen von 2 n Bits. Da es 2 2 n solcher Operationen gibt, kann man keine prägnantere Nomenklatur verlangen. Beachten Sie, dass jede finitäre Operation als Schaltfunktion bezeichnet werden kann .

Dieses Layout und die damit verbundene Benennung von Operationen wird hier vollständig für Stellen von 0 bis 2 dargestellt.

Wahrheitstabellen für die booleschen Operationen von arity bis 2
Konstanten
0 1
Unäre Operationen
0 0 1 0 1
1 0 0 1 1
Binäre Operationen
0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

Diese Tabellen werden bei höheren Stellen mit 2 n Zeilen bei Stellen n fortgesetzt, wobei jede Zeile eine Bewertung oder Bindung der n Variablen x 0 ,... x n −1 angibt und jede Spalte mit der Überschrift n f i den Wert n f i ( x 0 , ..., x n -1 ) die i - te n ary Operation zu dieser Bewertung. Die Operationen umfassen die Variablen, zum Beispiel 1 f 2 ist , x 0 während 2 f 10 ist x 0 (als zwei Kopien der unären Gegenstück) und 2 f 12 ist x 1 (ohne unären Gegenstück). Negation oder Komplement ¬ x 0 erscheint als 1 f 1 und wieder als 2 f 5 , zusammen mit 2 f 3 ( ¬ x 1 , die nicht an Stelle 1), Disjunktion oder Vereinigung x 0 ∨ x 1 als 2 f 14 , Konjunktion oder Schnittmenge x 0 ∧ x 1 als 2 f 8 , Implikation x 0 → x 1 als 2 f 13 , exklusive oder symmetrische Differenz x 0 ⊕ x 1 als 2 f 6 , Setze Differenz x 0 − x 1 als 2 f 2 , und so weiter.

Als kleineres Detail, das mehr für seine Form als für seinen Inhalt wichtig ist, sind die Operationen einer Algebra traditionell als Liste organisiert. Obwohl wir hier die Operationen einer Booleschen Algebra durch die finitären Operationen auf {0,1} indizieren, ordnet die obige Wahrheitstabellendarstellung die Operationen zufällig zuerst nach Arität und zweitens nach dem Layout der Tabellen für jede Arität. Dies ermöglicht die Organisation der Menge aller booleschen Operationen im traditionellen Listenformat. Die Listenreihenfolge für die Operationen einer gegebenen Stelle wird durch die folgenden zwei Regeln bestimmt.

(i) Die i- te Zeile in der linken Hälfte der Tabelle ist die binäre Darstellung von i mit seinem niederwertigsten oder 0- ten Bit auf der linken Seite ("Little-Endian"-Reihenfolge, ursprünglich von Alan Turing vorgeschlagen , also würde es es nicht unvernünftig sein, es Turing-Ordnung zu nennen).
(ii) Die j- te Spalte in der rechten Hälfte der Tabelle ist die binäre Darstellung von j , wiederum in Little-Endian-Reihenfolge. In der Tat der Index der Operation ist die Wahrheitstabelle dieser Operation. In Analogie zur Gödelschen Nummerierung berechenbarer Funktionen könnte man diese Nummerierung der Booleschen Operationen Boolesche Nummerierung nennen.

Beim Programmieren in C oder Java wird bitweise Disjunktion bezeichnet x | ja, Verbindung x & y, und Verneinung ~ x. Ein Programm kann also beispielsweise die Operation x ∧( y ∨ z ) in diesen Sprachen darstellen alsx &( y | z ), vorher eingestellt x  = 0xaa, y  = 0xcc, und z  = 0xf0 (das "0x" gibt an, dass die folgende Konstante hexadezimal oder zur Basis 16 gelesen werden soll, entweder durch Zuweisung an Variablen oder als Makro definiert. Diese Ein-Byte-(Acht-Bit-)Konstanten entsprechen den Spalten für die Eingangsvariablen in der Erweiterung der Diese Technik wird fast universell in Rastergrafikhardware verwendet, um eine flexible Vielfalt von Möglichkeiten zum Kombinieren und Maskieren von Bildern bereitzustellen, wobei die typischen Operationen ternär sind und gleichzeitig auf Quell-, Ziel- und Maskenbits wirken.

Beispiele

Bit-Vektoren

Beispiel 2 . Alle Bitvektoren einer gegebenen Länge bilden eine Boolesche Algebra "punktweise", was bedeutet, dass jede n- äre Boolesche Operation auf n Bitvektoren eine Bitposition nach der anderen angewendet werden kann . Zum Beispiel ist das ternäre ODER von drei Bitvektoren mit jeweils der Länge 4 der Bitvektor der Länge 4, der durch ODER-Verknüpfung der drei Bits in jeder der vier Bitpositionen gebildet wird, also 0100 1000 1001 = 1101 . Ein weiteres Beispiel sind die obigen Wahrheitstabellen für die n- ären Operationen, deren Spalten alle Bitvektoren der Länge 2 n sind und die daher punktweise kombiniert werden können, wodurch die n- ären Operationen eine Boolesche Algebra bilden. Dies funktioniert gleichermaßen gut für Bitvektoren endlicher und unendlicher Länge, wobei die einzige Regel darin besteht, dass die Bitpositionen alle durch denselben Satz indiziert werden, damit die "entsprechende Position" gut definiert ist.

Die Atome einer solchen Algebra sind die Bitvektoren, die genau eine 1 enthalten. Im Allgemeinen sind die Atome einer Booleschen Algebra die Elemente x , für die x ∧ y nur zwei mögliche Werte x oder 0 hat .

Potenzalgebra

Beispiel 3 . Die Potenzmenge Algebra , wobei der Satz 2 W aller Teilmengen eines gegebenen Satzes W . Dies ist nur das getarnte Beispiel 2, wobei W dazu dient, die Bitpositionen zu indizieren. Jede Untermenge X von W kann als Bitvektor mit Einsen in nur den Bitpositionen angesehen werden, die durch Elemente von X indiziert sind . Somit ist der All-Null-Vektor die leere Teilmenge von W, während der All-Ones-Vektor W selbst ist, dies sind die Konstanten 0 bzw. 1 der Potenzmengenalgebra. Das Gegenstück der Disjunktion x ∨ y Union ist X ∪ Y , während die der Verbindung x ∧ y ist Kreuzung X ∩ Y . Aus Negation ¬ x wird ~ X , Komplement zu W . Es gibt auch Einstelldifferenzdruck X ∖ Y  = X ∩ ~ Y , symmetrische Differenz ( X ∖ Y ) ∪ ( Y ∖ X ) , ternäre Union X ∪ Y ∪ Z , und so weiter . Die Atome hier sind die Singletons, diese Teilmengen mit genau einem Element.

Beispiele 2 und 3 sind Spezialfälle eines allgemeinen Konstrukt der Algebra genannt direkte Produkt , anwendbar nicht nur auf Boolesche Algebra , sondern alle Arten von Algebra einschließlich Gruppen, Ringe, etc. Das direkte Produkt von jeder Familie B i der Booleschen Algebren wo i erstreckt sich über eine Indexmenge I (nicht unbedingt endlich oder gar abzählbar) ist eine Boolesche Algebra, die aus allen I- Tupeln (... x i ,...) besteht, deren i- tes Element aus B i entnommen wird . Die Operationen eines direkten Produkts sind die entsprechenden Operationen der konstituierenden Algebren, die innerhalb ihrer jeweiligen Koordinaten wirken; insbesondere operiert die Operation n f j des Produkts auf n I- Tupeln, indem die Operation n f j von B i auf die n Elemente in der i- ten Koordinate der n Tupel für alle i in I angewendet wird .

Wenn alle auf diese Weise multiplizierten Algebren dieselbe Algebra A sind , nennen wir das direkte Produkt eine direkte Potenz von A . Die Boolesche Algebra aller 32-Bit-Bitvektoren ist die Zwei-Elemente-Boolesche Algebra, die in die 32. Potenz erhoben wird, oder Potenzmengenalgebra einer 32-Elemente-Menge, die mit 2 32 bezeichnet wird . Die Boolesche Algebra aller Mengen von ganzen Zahlen ist 2 Z . Alle bisher gezeigten Booleschen Algebren waren direkte Potenzen der Booleschen Algebra mit zwei Elementen, was den Namen "Potenzmengenalgebra" rechtfertigt.

Darstellungssätze

Es kann gezeigt werden, dass jede endliche Boolesche Algebra isomorph zu einer Potenzmengenalgebra ist. Daher ist die Kardinalität (Anzahl der Elemente) einer endlichen Booleschen Algebra eine Potenz von 2 , nämlich eine von 1,2,4,8,...,2 n ,... Dies wird als Darstellungssatz bezeichnet, da er Aufschluss gibt in die Natur der endlichen Boolesche Algebra durch eine Angabe Darstellung von ihnen als Potenzmenge Algebren.

Dieser Darstellungssatz erstreckt sich nicht auf unendliche Boolesche Algebren: Obwohl jede Potenzmengenalgebra eine Boolesche Algebra ist, muss nicht jede Boolesche Algebra isomorph zu einer Potenzmengenalgebra sein. Während es insbesondere keine abzählbar unendlichen Potenzalgebren geben kann (die kleinste unendliche Potenzalgebra ist die Potenzalgebra 2 N von Mengen natürlicher Zahlen, die von Cantor als unabzählbar gezeigt werden ), existieren verschiedene abzählbar unendliche Boolesche Algebren.

Um über Potenzmengenalgebren hinauszugehen, benötigen wir ein weiteres Konstrukt. A Subalgebra einer Algebra A ist eine beliebige Teilmenge von A unter den Operationen geschlossen A . Jede Subalgebra einer Booleschen Algebra A muss immer noch die Gleichungen von A erfüllen , da jede Verletzung eine Verletzung für A selbst darstellen würde. Daher ist jede Subalgebra einer Booleschen Algebra eine Boolesche Algebra.

Eine Subalgebra einer Potenzmengenalgebra heißt Körper von Mengen ; äquivalent ist ein Körper von Mengen eine Menge von Teilmengen einer Menge W einschließlich der leeren Menge und W und abgeschlossen unter endlicher Vereinigung und Komplement bezüglich W (und damit auch unter endlichem Durchschnitt). Der Darstellungssatz von Birkhoff [1935] für Boolesche Algebren besagt, dass jede Boolesche Algebra isomorph zu einem Körper von Mengen ist. Nun kann der HSP-Satz von Birkhoff für Varietäten so formuliert werden, dass jede Klasse von Modellen der Gleichungstheorie einer Klasse C von Algebren das homomorphe Bild einer Subalgebra eines direkten Produkts von Algebren von C ist . Normalerweise werden alle drei von H, S und P benötigt; was der erste dieser beiden Birkhoff-Theoreme zeigt, ist, dass für den Spezialfall der Vielfalt der Booleschen Algebren Homomorphismus durch Isomorphismus ersetzt werden kann . Das HSP-Theorem von Birkhoff für Varietäten im Allgemeinen wird daher zum ISP-Theorem von Birkhoff für die Varietät boolescher Algebren.

Andere Beispiele

Es ist bequem , wenn man über einen Satz spricht X der natürlichen Zahlen es als Folge sehen x 0 , x 1 , x 2 , ... von Bits, mit x i  = 1 , wenn und nur wenn i ∈ X . Dieser Gesichtspunkt wird es einfacher machen, über Subalgebren der Potenzmengenalgebra 2 N zu sprechen , die dieser Gesichtspunkt zur Booleschen Algebra aller Bitfolgen macht. Es passt auch gut zu den Spalten einer Wahrheitstabelle: Wenn eine Spalte von oben nach unten gelesen wird, stellt sie eine Folge von Bits dar, kann aber gleichzeitig als Menge dieser Bewertungen angesehen werden (Zuordnungen zu Variablen im linken Bereich). Hälfte der Tabelle), bei der die durch diese Spalte dargestellte Funktion zu 1 ausgewertet wird.

Beispiel 4 . Letztendlich konstante Abläufe . Jede boolesche Kombination von letztendlich konstanten Folgen ist letztendlich konstant; daher bilden diese eine Boolesche Algebra. Wir können diese mit den ganzen Zahlen identifizieren, indem wir die Folgen von letztendlich Null als nichtnegative Binärzahlen (Bit 0 der Folge ist das niederwertige Bit) und die Folgen von schließlich Eins als negative Binärzahlen betrachten (denken Sie an die Zweierkomplementarithmetik mit den All- Einsenfolge ist −1 ). Dies macht die ganzen Zahlen zu einer Booleschen Algebra, wobei die Vereinigung bitweise ODER und das Komplement −x−1 ist . Da es nur abzählbar viele ganze Zahlen gibt, ist diese unendliche Boolesche Algebra abzählbar. Die Atome sind die Zweierpotenzen, nämlich 1,2,4, .... Eine andere Art, diese Algebra zu beschreiben, ist die Menge aller endlichen und kofiniten Mengen natürlicher Zahlen, wobei die letztendlich alle Einsen-Folgen der kofiniten entsprechen Mengen, die nur endlich viele natürliche Zahlen weglassen.

Beispiel 5 . Periodische Folge . Eine Folge heißt periodisch, wenn es eine Zahl n > 0 gibt , die als Zeuge der Periodizität bezeichnet wird, so dass x i  = x i + n für alle i ≥ 0 gilt . Die Periode einer periodischen Folge ist ihr kleinster Zeuge. Die Negation lässt die Periode unverändert, während die Disjunktion zweier periodischer Folgen periodisch ist, wobei die Periode höchstens das kleinste gemeinsame Vielfache der Perioden der beiden Argumente ist (die Periode kann so klein wie 1 sein , wie es bei der Vereinigung einer beliebigen Folge und ihrer ergänzen). Somit bilden die periodischen Folgen eine Boolesche Algebra.

Beispiel 5 ähnelt Beispiel 4 darin, dass es zählbar ist, unterscheidet sich jedoch darin, dass es atomlos ist. Letzteres liegt daran, dass die Konjunktion einer beliebigen periodischen Folge x ungleich null mit einer Folge größerer Periode weder 0 noch x ist . Es kann gezeigt werden, dass alle abzählbar unendlichen atomlosen Booleschen Algebren isomorph sind, d. h. bis auf Isomorphie gibt es nur eine solche Algebra.

Beispiel 6 . Periodische Folge mit Periode einer Zweierpotenz . Dies ist eine echte Subalgebra von Beispiel 5 (eine echte Subalgebra entspricht dem Schnittpunkt ihrer selbst mit ihrer Algebra). Diese können als endliche Operationen verstanden werden, wobei die erste Periode einer solchen Folge die Wahrheitstabelle der Operation liefert, die sie repräsentiert. Zum Beispiel hat die Wahrheitstabelle von x 0 in der Tabelle der binären Operationen, nämlich 2 f 10 , die Periode 2 (und kann so erkannt werden, dass sie nur die erste Variable verwendet), obwohl 12 der binären Operationen die Periode 4 haben . Wenn die Periode 2 n beträgt, hängt die Operation nur von den ersten n Variablen ab, in welchem ​​Sinne die Operation endlich ist. Auch dieses Beispiel ist eine abzählbar unendliche atomlose Boolesche Algebra. Daher ist Beispiel 5 isomorph zu einer echten Subalgebra von sich selbst! Beispiel 6 und damit Beispiel 5 bilden die freie Boolesche Algebra auf abzählbar vielen Generatoren, dh die Boolesche Algebra aller finitären Operationen auf einer abzählbar unendlichen Menge von Generatoren oder Variablen.

Beispiel 7 . Letztlich periodische Sequenzen , Sequenzen, die nach einem anfänglichen endlichen Anfall von Gesetzlosigkeit periodisch werden. Sie bilden eine richtige Erweiterung von Beispiel 5 (was bedeutet, dass Beispiel 5 eine richtige Subalgebra von Beispiel 7) und auch von Beispiel 4 ist, da konstante Folgen mit Periode eins periodisch sind. Folgen können unterschiedlich sein, wann sie sich beruhigen, aber jede endliche Menge von Folgen wird sich schließlich alle spätestens nach ihrem am langsamsten zu beruhigenden Mitglied beruhigen, wodurch letztendlich periodische Folgen unter allen Booleschen Operationen geschlossen werden und so eine Boolesche Algebra bilden. Dieses Beispiel hat die gleichen Atome und Co-Atome wie Beispiel 4, daher ist es nicht atomlos und daher nicht isomorph zu Beispiel 5/6. Es enthält jedoch eine unendliche atomlose Unteralgebra , nämlich Beispiel 5, und ist daher nicht isomorph zu Beispiel 4, von dem jede Unteralgebra eine Boolesche Algebra endlicher Mengen und ihrer Komplemente und daher atomar sein muss. Dieses Beispiel ist isomorph zum direkten Produkt der Beispiele 4 und 5, was eine weitere Beschreibung davon liefert.

Beispiel 8 . Das direkte Produkt einer periodischen Folge (Beispiel 5) mit einer endlichen, aber nicht trivialen Booleschen Algebra. (Die triviale Ein-Element-Boolesche Algebra ist die einzigartige endliche atomlose Boolesche Algebra.) Dies ähnelt Beispiel 7 darin, dass es sowohl Atome als auch eine atomlose Unteralgebra hat, unterscheidet sich jedoch dadurch, dass es nur endlich viele Atome hat. Beispiel 8 ist in der Tat eine unendliche Familie von Beispielen, eines für jede mögliche endliche Anzahl von Atomen.

Diese Beispiele erschöpfen keineswegs die möglichen Booleschen Algebren, auch nicht die abzählbaren. Tatsächlich gibt es unzählige nicht-isomorphe abzählbare Boolesche Algebren, die Jussi Ketonen [1978] vollständig nach Invarianten, die durch bestimmte erblich abzählbare Mengen darstellbar sind, klassifiziert hat.

Boolesche Algebren von Booleschen Operationen

Die n- ären Booleschen Operationen selbst bilden eine Potenzmengenalgebra 2 W , nämlich wenn W als die Menge von 2 n Bewertungen der n Eingaben genommen wird. Hinsichtlich des Benennungssystems der Operationen n f i , wobei i im Binärformat eine Spalte einer Wahrheitstabelle ist, können die Spalten mit Booleschen Operationen beliebiger Art kombiniert werden, um andere in der Tabelle vorhandene Spalten zu erzeugen. Das heißt, wir können jede Boolesche Operation der Stelligkeit m auf m Boolesche Operationen der Stelligkeit n anwenden , um eine Boolesche Operation der Stelligkeit n für jedes m und n zu erhalten .

Die praktische Bedeutung dieser Konvention sowohl für Software als auch für Hardware besteht darin, dass n- äre Boolesche Operationen als Wörter geeigneter Länge dargestellt werden können. Beispielsweise kann jede der 256 ternären Booleschen Operationen als vorzeichenloses Byte dargestellt werden. Aus den verfügbaren logischen Verknüpfungen wie UND und ODER können dann neue Verknüpfungen gebildet werden. Wenn wir x , y und z ( vorerst ohne tiefgestellte Variablen) als 10101010 , 11001100 und 11110000 nehmen (170, 204 und 240 dezimal, 0xaa , 0xcc und 0xf0 hexadezimal), sind ihre paarweisen Konjunktionen x ∧ y  = 10001000 , y ∧ z  = 11000000 und z ∧ x  = 10100000 , während ihre paarweise Disjunktionen sind x ∨ y  = 11101110 , y ∨ z  = 11111100 und z ∨ x  = 11111010 . Die Disjunktion der drei Konjunktionen ist 11101000 , die zufällig auch die Konjunktion von drei Disjunktionen ist. Wir haben also mit etwa einem Dutzend logischer Operationen auf Bytes berechnet, dass die beiden ternären Operationen

und

sind eigentlich die gleiche Operation. Das heißt, wir haben die Gleichungsidentität . bewiesen

,

für die zweielementige Boolesche Algebra. Nach der Definition der "Booleschen Algebra" muss diese Identität daher in jeder Booleschen Algebra gelten.

Diese ternäre Operation bildete übrigens die Grundlage für Graus [1947] ternäre Boolesche Algebren, die er hinsichtlich dieser Operation und Negation axiomatisierte. Die Operation ist symmetrisch, dh ihr Wert ist unabhängig von einem der 3! = 6 Permutationen seiner Argumente. Die beiden Hälften der Wahrheitstabelle 11101000 sind die Wahrheitstabellen für ∨ , 1110 und ∧ , 1000 , so kann der Vorgang wie beschrieben werden kann , wenn z dann x ∨ y sonst x ∧ y . Da es symmetrisch ist , kann sie ebenso gut als entweder formuliert werden , wenn x dann y ∨ z else y ∧ z , oder , wenn Y dann z ∨ x else z ∧ x . Als Beschriftung des 8-Scheitel-3-Würfels betrachtet, ist die obere Hälfte mit 1 und die untere Hälfte mit 0 bezeichnet; Aus diesem Grund hat es sich die genannte Medianoperator , mit dem offensichtlichen Verallgemeinerung auf jede ungerade Anzahl von Variablen (ungerade, um die Bindung zu vermeiden , wenn genau die Hälfte die Variablen 0) gewonnen .

Axiomatisierende Boolesche Algebren

Die Technik, die wir gerade verwendet haben, um eine Identität der Booleschen Algebra zu beweisen, kann auf systematische Weise auf alle Identitäten verallgemeinert werden, was als eine solide und vollständige Axiomatisierung oder als axiomatisches System für die Gleichungsgesetze der Booleschen Logik angesehen werden kann . Die übliche Formulierung eines Axiomensystems besteht aus einer Reihe von Axiomen, die mit einigen anfänglichen Identitäten "die Pumpe anregen", zusammen mit einer Reihe von Inferenzregeln zum Ableiten der verbleibenden Identitäten aus den Axiomen und zuvor bewiesenen Identitäten. Grundsätzlich ist es wünschenswert, endlich viele Axiome zu haben; aus praktischen Gründen ist dies jedoch nicht notwendig, da es genauso effektiv ist, ein endliches Axiomenschema mit unendlich vielen Instanzen zu haben, von denen jede, wenn sie in einem Beweis verwendet wird, leicht als legale Instanz verifiziert werden kann, der Ansatz, den wir hier verfolgen.

Boolesche Identitäten sind Behauptungen von der Form s  = t , wo s und t sind n - ary Begriffe, mit denen wir hier Begriffe , deren Variablen bedeuten soll beschränken sich auf x 0 bis x n-1 . Ein n- ärer Term ist entweder ein Atom oder eine Anwendung. Eine Anwendung , m f i ( t 0 , ..., t m -1 ) ist ein Paar , bestehend aus einem m - ary Betrieb m f i und eine Liste oder m -Tupel ( t 0 , ..., t m -1 ) von m n -ären Termen, die Operanden genannt werden .

Jedem Term ist eine natürliche Zahl zugeordnet, die als Höhe bezeichnet wird . Atome haben die Höhe Null, während Anwendungen die Höhe Eins plus die Höhe ihres höchsten Operanden haben.

Was ist nun ein Atom? Herkömmlicherweise ist ein Atom entweder eine Konstante (0 oder 1) oder eine Variable x i mit 0 i < n . Für die Beweistechnik hier ist es zweckmäßig, Atome stattdessen als n- äre Operationen n f i zu definieren , die, obwohl sie hier als Atome behandelt werden, dennoch dasselbe bedeuten wie gewöhnliche Terme der exakten Form n f i ( x 0 ,..., x n -1 ) (genau insofern, als die Variablen in der angegebenen Reihenfolge ohne Wiederholung oder Auslassung aufgelistet werden müssen). Dies ist keine Einschränkung, denn Atome dieser Form umfassen alle gewöhnlichen Atome, nämlich die Konstanten 0 und 1, die hier als n- äre Operationen n f 0 und n f −1 für jedes n (Abkürzung 2 2 n −1 bis −1 ) und die Variablen x 0 ,..., x n -1, wie aus den Wahrheitstabellen ersichtlich ist, wobei x 0 sowohl als unäre Operation 1 f 2 als auch als binäre Operation 2 f 10 erscheint, während x 1 erscheint als 2 f 12 .

Das folgende Axiomenschema und drei Inferenzregeln axiomatisieren die Boolesche Algebra von n- ären Termen.

A1 . m f i ( n f j 0 , ..., n f j m -1 ) = n f i o ĵ wobei ( i o ĵ ) v  = i ĵ v , mit ĵ wobei j transponiert, definiert durch ( ĵ v ) u  = ( j u ) v .
R1 . Ohne Prämissen folgere t  = t .
R2 . Von s  = u und t  = u infer s  = t , wo s , t und u sind n - ary Bedingungen.
R3 . Aus s 0  = t 0 ,..., s m -1  = t m -1 folgern m f i ( s 0 ,..., s m -1 ) = m f i ( t 0 ,..., t m -1 ) , wo alle Begriffe s i , t i sind n - ary.

Die Nebenbedingung auf A1 bedeutet, dass i o ĵ die 2 n- Bit-Zahl ist, deren v- tes Bit das ĵ v- te Bit von i ist , wobei die Bereiche jeder Größe u : m , v : 2 n . sind , j u : 2 2 n , und ĵ v : 2 m . (Also ist j ein m- Tupel von 2 n- Bit-Zahlen, während ĵ als Transponierte von j ein 2 n- Tupel von m- Bit-Zahlen ist. Sowohl j als auch ĵ enthalten daher m 2 n Bits.)

A1 ist eher ein Axiom-Schema als ein Axiom, da es Metavariablen enthält , nämlich m , i , n und j 0 bis j m-1 . Die eigentlichen Axiome der Axiomatisierung erhält man, indem man die Metavariablen auf bestimmte Werte setzt. Nehmen wir zum Beispiel m  = n  = i  = j 0  = 1 , können wir die beiden Bits von i o ĵ aus i 1  = 0 und i 0  = 1 berechnen , also i o ĵ  = 2 (oder 10, wenn geschrieben als eine Zwei-Bit-Zahl). Die resultierende Instanz, nämlich 1 f 1 ( 1 f 1 ) = 1 f 2 , drückt das bekannte Axiom ¬¬ x  = x der Doppelnegation aus. Regel R3 erlaubt uns dann, ¬¬¬ x  = ¬ x abzuleiten, indem wir s 0 zu 1 f 1 ( 1 f 1 ) oder ¬¬ x 0 , t 0 zu 1 f 2 oder x 0 und m f i zu nehmen sei 1 f 1 oder ¬ .

Für jedes m und n gibt es nur endlich viele Axiome, die A1 instanziieren , nämlich 2 2 m × (2 2 n ) m . Jede Instanz wird durch 2 m + m 2 n Bits spezifiziert .

Wir behandeln R1 als Inferenzregel, obwohl es wie ein Axiom ist, weil es keine Prämissen hat, weil es zusammen mit R2 und R3 eine domänenunabhängige Regel ist, die allen Gleichungsaxiomatisierungen gemeinsam ist, sei es von Gruppen, Ringen oder jeder anderen Varietät. Die einzige für Boolesche Algebren spezifische Entität ist das Axiomschema A1 . Auf diese Weise können wir, wenn wir über verschiedene Gleichungstheorien sprechen, die Regeln als unabhängig von den jeweiligen Theorien beiseite schieben und die Aufmerksamkeit auf die Axiome als den einzigen Teil des Axiomensystems beschränken, der die jeweilige Gleichungstheorie charakterisiert.

Diese Axiomatisierung ist vollständig, dh jedes Boolesche Gesetz s  = t ist in diesem System beweisbar. Man zeigt zunächst durch Induktion über die Höhe von s, dass jedes Boolesche Gesetz, für das t atomar ist, beweisbar ist, indem man R1 für den Basisfall verwendet (da verschiedene Atome nie gleich sind) und A1 und R3 für den Induktionsschritt ( s eine Anwendung). Diese Beweisstrategie läuft auf ein rekursives Verfahren hinaus, um s auszuwerten , um ein Atom zu erhalten. Um s  = t im allgemeinen Fall zu beweisen, wenn t eine Anwendung sein kann, verwenden Sie die Tatsache, dass, wenn s  = t eine Identität ist, s und t auf dasselbe Atom evaluieren müssen, nennen Sie es u . Beweisen Sie also zuerst s  = u und t  = u wie oben, dh werten Sie s und t mit A1 , R1 und R3 aus und rufen Sie dann R2 auf, um s  = t abzuleiten .

In A1 , wenn wir die Zahl betrachten n m als Funktionstyp m → n und m n als Anwendungs m ( n ) , können wir die Zahlen neu zu interpretieren i , j , ¼ und i o ĵ als Funktionen von Typ i : ( m → 2) → 2 , j :  m → (( n → 2) → 2) , ĵ : ( n → 2) → ( m → 2) , und i o ĵ : ( n → 2) → 2 . Die Definition ( i o ĵ ) v  = i ĵ v in A1 übersetzt sich dann in ( i o ĵ )( v ) = i ( ĵ ( v )) , d.h. i o ĵ ist definiert als Zusammensetzung von i und ĵ verstanden als Funktionen. Der Inhalt von A1 läuft also darauf hinaus, den Begriff Anwendung im Wesentlichen als Komposition zu definieren, modulo die Notwendigkeit, das m- Tupel j zu transponieren , damit die Typen für die Komposition geeignet übereinstimmen. Diese Zusammensetzung ist diejenige in Lawveres zuvor erwähnter Kategorie von Powersets und ihren Funktionen. Auf diese Weise haben wir die kommutierenden Diagramme dieser Kategorie als die Gleichungstheorie der Booleschen Algebren in die Gleichungsfolgen von A1 als logische Darstellung dieses speziellen Zusammensetzungsgesetzes übersetzt.

Unterliegende Gitterstruktur

Jeder Booleschen Algebra B liegt eine partiell geordnete Menge oder Poset ( B ,≤) zugrunde . Die partielle Ordnung Beziehung definiert ist durch x ≤ y nur , wenn x  = x ∧ y , oder äquivalent , wenn y  = x ∨ y . Vorgegeben eine Menge X von Elementen einer booleschen Algebra, eine obere Schranke für X ist ein Element , y , so daß für jedes Element x aus X , x ≤ y , während eine untere Schranke für X ist ein Element , y , so daß für jedes Element x von x , y ≤ x .

Ein sup von X ist eine kleinste obere Schranke von X , nämlich eine obere Schranke von X , die kleiner oder gleich jeder oberen Schranke von X ist . Dually ein ( inf ) von X ist eine größte untere auf gebunden X . Die sup von x und y existieren immer in dem zugrunde liegenden poset einer Boolesche Algebra, wobei x ∨ y , und ebenfalls ihre inf existiert, nämlich x ∧ y . Das leere sup ist 0 (das untere Element) und das leere inf ist 1 (oben). Daraus folgt, dass jede endliche Menge sowohl eine sup als auch eine inf hat. Unendliche Teilmengen einer Booleschen Algebra können ein sup und/oder ein inf haben oder nicht; in einer Potenzalgebra tun sie es immer.

Jedes Poset ( B ,≤), so dass jedes Paar x , y von Elementen sowohl ein sup als auch ein inf hat, heißt Gitter . Wir schreiben x ∨ y für sup und x ∧ y für inf. Das zugrundeliegende Poset einer Booleschen Algebra bildet immer ein Gitter. Das Gitter heißt distributiv, wenn x ∧( y ∨ z ) = ( x ∧ y )∨( x ∧ z ) oder äquivalent wenn x ∨( y ∧ z ) = ( x ∨ y )∧( x ∨ z ) , da jedes Gesetz das andere in einem Gitter impliziert. Dies sind Gesetze der Booleschen Algebra, weshalb das zugrunde liegende Poset einer Booleschen Algebra ein Verteilungsgitter bildet.

Gegeben ein Gitter mit einem unteren Element 0 und einem oberen Element 1 heißt ein Paar x , y von Elementen komplementär, wenn x ∧ y  = 0 und x ∨ y  = 1 ist , und wir sagen dann, dass y ein Komplement von x ist und umgekehrt umgekehrt. Jedes Element x eines distributiven Gitters mit oben und unten kann höchstens ein Komplement haben. Wenn jedes Element eines Gitters ein Komplement hat, heißt das Gitter komplementär. Daraus folgt, dass in einem komplementierten Verteilungsgitter das Komplement eines Elements immer existiert und eindeutig ist, was das Komplement zu einer einären Operation macht. Außerdem bildet jedes komplementierte Verteilungsgitter eine Boolesche Algebra, und umgekehrt bildet jede Boolesche Algebra ein komplementiertes Verteilungsgitter. Dies liefert eine alternative Definition einer Booleschen Algebra, nämlich als jedes komplementierte Verteilungsgitter. Jede dieser drei Eigenschaften kann mit endlich vielen Gleichungen axiomatisiert werden, wodurch diese Gleichungen zusammengenommen eine endliche Axiomatisierung der Gleichungstheorie der Booleschen Algebren darstellen.

In einer Klasse von Algebren, die als alle Modelle eines Gleichungssatzes definiert ist, ist es normalerweise der Fall, dass einige Algebren der Klasse mehr Gleichungen erfüllen als nur diejenigen, die sie für die Klasse benötigen. Die Klasse der Booleschen Algebren ist insofern ungewöhnlich, als mit einer einzigen Ausnahme jede Boolesche Algebra genau die Booleschen Identitäten erfüllt und nicht mehr. Die Ausnahme ist die einelementige Boolesche Algebra, die notwendigerweise jede Gleichung erfüllt, sogar x  = y , und wird daher manchmal als inkonsistente Boolesche Algebra bezeichnet.

Boolesche Homomorphismen

Ein Boolescher Homomorphismus ist eine Funktion h : A → B zwischen Booleschen Algebren A , B derart, dass für jede Boolesche Operation m f i :

Die Kategorie Bool der Booleschen Algebren hat als Objekte alle Booleschen Algebren und als Morphismen die Booleschen Homomorphismen dazwischen.

Es existiert ein eindeutiger Homomorphismus von der zweielementigen Booleschen Algebra 2 zu jeder Booleschen Algebra, da Homomorphismen die beiden Konstanten beibehalten müssen und dies die einzigen Elemente von 2 sind . Eine Boolesche Algebra mit dieser Eigenschaft wird als initiale Boolesche Algebra bezeichnet. Es kann gezeigt werden , dass zwei beliebige Anfangs Boolesche Algebra isomorph sind, so bis auf Isomorphie 2 ist die anfängliche Boolesche Algebra.

In der anderen Richtung kann es viele Homomorphismen von einer Booleschen Algebra B zu 2 geben . Jeder solche Homomorphismus zerlegt B in jene Elemente, die auf 1 abgebildet sind, und solche auf 0. Die Teilmenge von B, die aus ersterem besteht, wird Ultrafilter von B genannt . Wenn B endlich ist, paaren sich seine Ultrafilter mit seinen Atomen; ein Atom wird auf 1 und der Rest auf 0 abgebildet. Jeder Ultrafilter von B besteht also aus einem Atom von B und allen Elementen darüber; daher befinden sich genau die Hälfte der Elemente von B im Ultrafilter, und dort sind so viele Ultrafilter wie Atome.

Für unendliche Boolesche Algebren wird der Begriff des Ultrafilters erheblich heikler. Die Elemente, die größer oder gleich einem Atom sind, bilden immer einen Ultrafilter, aber auch viele andere Gruppen; zum Beispiel bilden in der Booleschen Algebra der endlichen und kofiniten Mengen von ganzen Zahlen die kofiniten Mengen einen Ultrafilter, obwohl keine von ihnen Atome sind. Ebenso hat die Potenzmenge der ganzen Zahlen unter ihren Ultrafiltern die Menge aller Teilmengen, die eine gegebene ganze Zahl enthalten; es gibt zählbar viele dieser "Standard"-Ultrafilter, die mit den ganzen Zahlen selbst identifiziert werden können, aber es gibt unzählig viele weitere "Nicht-Standard"-Ultrafilter. Diese bilden die Grundlage für die Nicht-Standard-Analyse , die Darstellungen für solche klassisch inkonsistenten Objekte wie Infinitesimals und Delta-Funktionen liefert.

Unendliche Erweiterungen

Erinnern Sie sich an die Definition von sup und inf aus dem obigen Abschnitt über die zugrunde liegende Teilordnung einer Booleschen Algebra. Eine vollständige Boolesche Algebra ist eine Algebra, bei der jede Teilmenge sowohl eine sup als auch eine inf hat, sogar die unendlichen Teilmengen. Gaifman [1964] und Hales [1964] zeigten unabhängig voneinander, dass keine unendlichen freien vollständigen Booleschen Algebren existieren. Dies legt nahe, dass eine Logik mit unendlichen Operationen in Mengengröße viele Terme haben kann – genauso wie eine Logik mit endlichen Operationen unendlich viele Terme haben kann.

Es gibt jedoch einen anderen Ansatz, um unendliche Boolesche Operationen einzuführen: Lassen Sie einfach "finitär" aus der Definition der Booleschen Algebra weg. Ein Modell der Gleichungstheorie der Algebra aller Operationen auf {0,1} der Stelligkeit bis zur Kardinalität des Modells wird als vollständige atomare Boolesche Algebra oder CABA bezeichnet . (Anstelle dieser umständlichen Einschränkung der arity könnten wir jeder arity erlauben, was zu einer anderen Unbeholfenheit führt, dass die Signatur dann größer als jede Menge, also eine richtige Klasse, wäre. Ein Vorteil des letzteren Ansatzes besteht darin, dass er die Definition des Homomorphismus zwischen CABAs unterschiedlicher Kardinalität .) Eine solche Algebra kann äquivalent als eine vollständige Boolesche Algebra definiert werden , die atomar ist , was bedeutet, dass jedes Element eine sup einer Menge von Atomen ist. Freie Cabas existieren für alle Kardinalitäten eines Satzes V von Generatoren , nämlich die Leistung eingestellt Algebra 2 2 V , das die offensichtliche Verallgemeinerung der endlichen freien Boolesche Algebra ist. Dies rettet die unendliche boolesche Logik ordentlich vor dem Schicksal, dem das Ergebnis von Gaifman-Hales sie zuzuschreiben schien.

Die Nichtexistenz freier vollständiger Boolescher Algebren kann auf das Versäumnis zurückgeführt werden, die Gleichungen der Booleschen Logik angemessen auf alle Gesetze zu erweitern, die für die unendliche Konjunktion und Disjunktion gelten sollten, insbesondere die Vernachlässigung der Distributivität bei der Definition der vollständigen Booleschen Algebra. Eine vollständige Boolesche Algebra heißt vollständig distributiv, wenn beliebige Konjunktionen über beliebige Disjunktionen verteilen und umgekehrt. Eine Boolesche Algebra ist genau dann eine CABA, wenn sie vollständig und vollständig distributiv ist, was eine dritte Definition von CABA ergibt. Eine vierte Definition ist eine beliebige Boolesche Algebra, die isomorph zu einer Potenzmengenalgebra ist.

Ein vollständiger Homomorphismus ist einer, der alle existierenden sups beibehält, nicht nur die endlichen sups, und ebenso für infs. Die Kategorie CABA aller CABAs und ihrer vollständigen Homomorphismen ist dual zur Kategorie der Mengen und ihrer Funktionen, dh sie ist äquivalent zum Gegenteil dieser Kategorie (der Kategorie, die sich aus der Umkehrung aller Morphismen ergibt). Es ist nicht so einfach, dass die Kategorie Bool der Booleschen Algebren und ihrer Homomorphismen, die Marshall Stone tatsächlich gezeigt hat (obwohl ihm sowohl die Sprache als auch der begriffliche Rahmen fehlten, um die Dualität explizit zu machen), dual zur Kategorie der völlig unverbundenen kompakten Hausdorff ist Räume , die später als Steinräume bezeichnet werden .

Eine weitere unendliche Klasse zwischen Booleschen Algebren und vollständigen Booleschen Algebren ist der Begriff einer Sigma-Algebra . Dies ist analog zu vollständigen Booleschen Algebren definiert, jedoch mit sups und infs beschränkt auf abzählbare Stelligkeit. Das heißt, eine Sigma-Algebra ist eine Boolesche Algebra mit allen zählbaren Sups und Infs. Da die sups und infs von beschränkter Kardinalität sind , gilt im Gegensatz zur Situation mit vollständigen Booleschen Algebren das Gaifman-Hales-Ergebnis nicht und es existieren freie Sigma-Algebren . Anders als bei CABAs ist die frei abzählbar generierte Sigma-Algebra jedoch keine Potenzmengenalgebra.

Andere Definitionen von Boolesche Algebra

Wir sind bereits mehreren Definitionen der Booleschen Algebra begegnet, als Modell der Gleichungstheorie der Zwei-Elemente-Algebra, als komplementäres Verteilungsgitter, als Boolescher Ring und als produkterhaltender Funktor aus einer bestimmten Kategorie (Lawvere). Zwei weitere erwähnenswerte Definitionen sind:.

Stein (1936)
Eine Boolesche Algebra ist die Menge aller clopen Mengen eines topologischen Raums . Es ist keine Einschränkung zu verlangen, dass der Raum ein total unzusammenhängender kompakter Hausdorff-Raum oder Stone-Raum ist , d. h. jede Boolesche Algebra entsteht auf diese Weise bis auf Isomorphie . Darüber hinaus sind die beiden Booleschen Algebren, die als clopen-Mengen zweier Stone-Räume gebildet werden, isomorph, so sind es auch die Stone-Räume selbst, was bei beliebigen topologischen Räumen nicht der Fall ist. Dies ist genau die umgekehrte Richtung der zuvor erwähnten Dualität von Booleschen Algebren zu Steinräumen . Diese Definition wird durch die nächste Definition konkretisiert.
Johnstone (1982)
Eine Boolesche Algebra ist ein gefilterter Kolimit endlicher Boolescher Algebren.

(Die Zirkularität in dieser Definition kann beseitigt werden, indem "endliche Boolesche Algebra" durch "endliche Potenzmenge" ersetzt wird, die mit den Booleschen Operationen ausgestattet ist, die standardmäßig für Potenzmengen interpretiert werden.)

Um dies zu relativieren, entstehen unendliche Mengen als gefilterte Colimits endlicher Mengen, unendliche CABAs als gefilterte Grenzen endlicher Potenzmengenalgebren und unendliche Steinräume als gefilterte Grenzen endlicher Mengen. Wenn man also mit den endlichen Mengen beginnt und fragt, wie diese zu unendlichen Objekten verallgemeinern, gibt es zwei Möglichkeiten: "Addieren" ergibt gewöhnliche oder induktive Mengen, während "Multiplizieren" Steinräume oder profinite Mengen ergibt . Für endliche Potenzmengenalgebren besteht die gleiche Wahl wie für die Dualen endlicher Mengen: Addition liefert Boolesche Algebren als induktive Objekte, während Multiplikation CABAs oder Potenzalgebren als profinite Objekte liefert.

Ein charakteristisches Unterscheidungsmerkmal besteht darin, dass die zugrundeliegende Topologie so konstruierter Objekte, wenn sie als Hausdorff definiert wird, für induktive Objekte diskret und für profinite Objekte kompakt ist . Die Topologie endlicher Hausdorff-Räume ist immer sowohl diskret als auch kompakt, während sich bei unendlichen Räumen "diskret" und "kompakt" gegenseitig ausschließen. Wenn also endliche Algebren (jeglicher Art, nicht nur Boolesche) zu unendlichen verallgemeinert werden, sind "diskrete" und "kompakte" Teile der Gesellschaft, und man muss wählen, welche Algebren beibehalten werden soll. Die allgemeine Regel für endliche und unendliche Algebren lautet, dass endliche Algebren diskret sind, während ihre Dualen kompakt sind und unendliche Operationen aufweisen. Zwischen diesen beiden Extremen gibt es viele dazwischenliegende unendliche Boolesche Algebren, deren Topologie weder diskret noch kompakt ist.

Siehe auch

Verweise

  • Birkhoff, Garrett (1935). „Über die Struktur abstrakter Algebren“. Proz. Kamm. Phil. Soz . 31 (4): 433–454. Bibcode : 1935PCPS...31..433B . doi : 10.1017/s0305004100013463 . ISSN  0008-1981 .
  • Boole, George (2003) [1854]. Eine Untersuchung der Denkgesetze . Prometheus-Bücher. ISBN 978-1-59102-089-9.
  • Dwinger, Philipp (1971). Einführung in die Boolesche Algebren . Würzburg: Physica Verlag.
  • Gaifman, Haim (1964). "Unendliche Boolesche Polynome, I" . Fundamenta Mathematicae . 54 (3): 229–250. doi : 10.4064/fm-54-3-229-250 . ISSN  0016-2736 .
  • Givant, Steven; Halmos, Paul (2009). Einführung in die Boolesche Algebren . Bachelortexte in Mathematik . Springer. ISBN 978-0-387-40293-2.
  • Grau, AA (1947). "Ternäre Boolesche Algebra" . Stier. Bin. Mathematik. Soz . 33 (6): 567–572. doi : 10.1090/S0002-9904-1947-08834-0 .
  • Hales, Alfred W. (1964). "Über die Nichtexistenz freier vollständiger Boolescher Algebren" . Fundamenta Mathematicae . 54 : 45–66. doi : 10.4064/fm-54-1-45-66 . ISSN  0016-2736 .
  • Halmos, Paul (1963). Vorlesungen über Boolesche Algebren . van Nostrand. ISBN 0-387-90094-2.
  • Givant, Steven; Halmos, Paul (1998). Logik als Algebra . Dolciani Mathematische Ausstellung. Mathematische Vereinigung von Amerika . ISBN 978-0-883-85327-6.
  • Johnstone, Peter T. (1982). Steine ​​Räume . Cambridge, Großbritannien: Cambridge University Press. ISBN 978-0-521-33779-3.
  • Ketonen, Jussi (1978). „Die Struktur der zählbaren Booleschen Algebren“. Annalen der Mathematik . 108 (1): 41–89. doi : 10.2307/1970929 . JSTOR  1970929 .
  • Koppelberg, Sabine (1989) "General Theory of Boolean Algebras" in Monk, J. Donald und Bonnet, Robert, Hrsg., Handbook of Boolean Algebras, Vol. 2, No. 1 . Nordholland. ISBN  978-0-444-70261-6 .
  • Peirce, CS (1989) Schriften von Charles S. Peirce: Eine chronologische Ausgabe: 1879-1884 . Klösel, CJW, hrsg. Indianapolis: Indiana University Press. ISBN  978-0-253-37204-8 .
  • Lawvere, F. William (1963). "Funktionale Semantik algebraischer Theorien" . Verfahren der Nationalen Akademie der Wissenschaften . 50 (5): 869–873. Bibcode : 1963PNAS...50..869L . doi : 10.1073/pnas.50.5.869 . PMC  221940 . PMID  16591125 .
  • Schröder, Ernst (1890–1910). Vorlesungen über die Algebra der Logik (exakte Logik), I–III . Leipzig: BG Teubner.
  • Sikorski, Roman (1969). Boolesche Algebren (3. Aufl.). Berlin: Springer-Verlag. ISBN 978-0-387-04469-9.
  • Stein, MH (1936). „Theorie der Darstellung für Boolesche Algebren“. Transaktionen der American Mathematical Society . 40 (1): 37–111. doi : 10.2307/1989664 . ISSN  0002-9947 . JSTOR  1989664 .
  • Tarski, Alfred (1983). Logik, Semantik, Metamathematik , Corcoran, J., Hrsg. Hackett. 1956 1. Auflage herausgegeben und übersetzt von JH Woodger, Oxford Uni. Drücken Sie. Enthält englische Übersetzungen der folgenden zwei Artikel:
  • Wladimirow, D. A. (1969). булевы алгебры (Boolesche Algebren, in Russisch, deutsche Übersetzung Boolesche Algebren 1974) . Nauka (deutsche Übersetzung Akademie-Verlag).