Kapitel 2 - Grundbegriffe aus Mengenlehre und Algebra
 
 
 
2.1 Mengen, Relationen und Funktionen zurück

Jede mathematische Theorie beginnt mit der Definition ihrer primitiven Einheiten, aus denen sie ihre zusammengesetzten Einheiten aufbaut. Die Logik basiert u. a. auf der Mengentheorie. Unsere primitiven Einheiten sind somit Mengen, Objekte, die wir mit a, b, c, ... bezeichnen wollen., sowie die Relation Î, die als "ist enthalten in" zu lesen ist. Als Menge, symbolisiert durch Großbuchstaben, werden Aufsammlungen von Objekten bezeichnet, die Elemente dieser Mengen heißen. Wir schreiben a A, falls a Element der Menge A ist, andernfalls schreiben wir a A.

Das mathematische Mengenkonzept ist infolge unserer alltäglichen Erfahrungen unmittelbar einsichtig: "Wir müssen es als eine grundlegende Fähigkeit des menschlichen Geistes ansehen, gegebene Objekte gedanklich zu einem Ganzen zusammenfassen zu können." (Heuser 1990:17). Dieser exemplifizierende Bezug ist in der Logik sicher nicht immer möglich, woran wir erkennen, dass Logik eine formale, mathematische Disziplin ist. Dieser Bezug ergibt sich allerdings dort, wo die Logik als Repräsentationssprache (etwa in der Sprachwissenschaft) Verwendung findet.

Wir unterscheiden die folgenden, aus der Mengenlehre wohl bekannten Symbole:

    "a A" steht für "a ist Element von A"

    "" steht für "daraus folgt, dass"

    "" bzw. "iff" steht für "genau dann, wenn"

    "=def" steht für "wird definiert durch" (bisweilen verwenden wir auch die Schreibweise "=")

    "{a | P}" steht für "die Menge aller Entitäten mit der Eigenschaft P" 

Andere Symbole werden ja nach Bedarf eingeführt.

Definition 2.1.1 Es gelten folgende Beziehungen zwischen Mengen, hierbei sei U das betrachtete Universum (i. e. die Menge aller betrachteten Objekte):

    1. = {} ist die leere Menge, also die Menge, die keine Elemente enthält.

    2. A B iff ( a A (a B ).

    3. A = B iff A B und B A.

    4. Das Kreuzprodukt: A x B =def { < a, b > | a A und b B }.

    5. Die Vereinigung: A B =def { < ).

    6. Der Durchschnitt: A ∩ B =def { a U | a A und a B }.

    7. Die Differenz: A - B = def { a U | a A und a B }.

    8. Die Summe: A + B =def ( A B ) - ( A ∩ B).

    9. Das Komplement von A: Ac =def {a U | a A }.

Anmerkung 2.1.1 Die Mengen A und B heißen disjunkt iff A ∩ B = . Falls A B, dann heißt A Teilmenge von B und falls A = B, dann heißen A und B äquivalent. A x B heißt Kreuzprodukt, A B Vereinigung, A ∩ B Durchschnitt, A + B Summe und A - B Differenz von A und B. Schließlich nennt man Ac das Komplement von A. Für A x ... x A (n-fach) steht kurz An. Für A1 ... schreibt man

Ai.
i=1,...,n

entsprechend steht ∩i=1,...,nvAi für A1 ... An.

Anmerkung 2.1.2 Zum Kreuzprodukt (auch: Cartesisches Produkt): Sei M eine Teilmenge eines Cartesischen Produktes zweier Mengen. Dann kann man nach den kleinsten Teilmengen A, B dieser Mengen fragen, so dass A x B = M. Hierzu definiert man: A = { a | < a, b > M für ein b } und B = { b | < a, b > für ein a }. Die Mengen A, B heißen die Projektionen von M auf die ersten und zweiten Koordinaten.

Beispiel 2.1.1 Seien A = { a, c, d } und B = { b, d, e }zwei Mengen über dem Universum U = { a, b, c, ..., z }. Dann gilt:

    1. A x B = { < a, b >, < a, d >, < a, e >, < c, b >, < c, d >, < c, e >, < d, b >, < d, d >, < d, e > }.

    2. A ∩ B = { d }.

    3. A B = { a, b, c, d, e }.

    4. A + B { a, c, b, e }.

    5. A - B = { a, c }.

    6. Ac = U - A.

Definition 2.1.2 < a, b > =def {{ a }, {a, b }} ist das geordnete Paar der Elemente a, b.

Anmerkung 2.1.3 < a, b > definiert eindeutig eine Ordnung der Elemente der Menge { a, b }. Daher ist < a, b > ≠ < b, a >, da {{ a }, {{a, b }} ≠ { a }, {{ a, b }} (vorausgesetzt a ≠ b).

In der Mengentheorie gelten folgende grundlegende Gesetze:

    1. Idempotenz: A A = A; A ∩ A = A.

    2. Kommutativität: A B = B A; A ∩ B = B ∩ A;

    3. Assoziativität: A ( B C ) = ( A B ) C; A ∩ ( B ∩ C ) = ( A ∩ B ) ∩ C;

    4. Distributivität: A ( B ∩ C ) = ( A B ) ∩ ( A C ); A ∩ ( B C ) = ( A ∩ B ) ( A ∩ C );

    5. Identitätsgesetze: A = A; A U = U, A ∩ = A ∩ U =A

    6. Komplementgesetze: A Ac = U; A ∩ Ac = ; ( Ac )c = A; A - B = A ∩ Bc;

    7. De Morgansche Gesetze: ( A B )c = Ac ∩ Bc; ( A ∩ B )c = Ac Bc;

    8. Konsistenzprinzip: A B iff A B = B; A B iff A ∩ B = A.

Definition 2.1.3 R heißt n-stellige Relation über A1, ..., An iff R A 1 x ... x An.

Definition 2.1.4 Sei R A x A eine zweistellige Relation, R heißt

    1. reflexiv iff für alle a A gilt: < a, a > R.

    2. irreflexiv iff für alle a A gilt: < a, a > R.

    3. symmetrisch iff < a, b > R < b, a > R.

    4. antisymmetrisch iff ( < a, b > R und < b, a > R ( a = b ) ).

    5. asymmmetrisch iff < a, b > R < b, a > R.

    6. transitiv iff ( < a, b > R und < b, c > R ) 8 < a, c > R ).

    7. linear iff < a, b > R oder < b, a > R.

    8. Äquivalenzrelation iff R ist reflexiv, symmetrisch und transitiv.

    9. Ordnungsrelation iff R ist reflexiv, antisymmetrisch und transitiv.

    10. Toleranzrelation iff R ist reflexiv und symmetrisch.

Sei R A x A eine Äquivalenzrelation über A2 und sei a A. Dann heißt | a | =def { b | < a, b > R } Äquivalenzklasse von a. Für alle c A gilt dann: entweder | c | = | a | (falls < c, a > R ) oder | c ∩ | a | = . Darüber hinaus ist die Vereinigung aller Äquivalenzklassen äquivalent zu A. Eine Äquivalenzrelation teilt also eine Menge in disjunkte Teilmengen auf.

Definition 2.1.5 Sei R eine Relation. Die kleinste transitive Relation R' heißt transitive Hülle von R.

Definition 2.1.6 Eine Relation F A x B heißt Funktion von A nach B iff

( < a, b > F und < a, c > F ) ( b = c ).

Für Funktionen F schreibt man auch F : A B. A heißt Definitionsbereich und B Wertebereich von F. Die Menge F ( a ) =def { b | < a, b > F } heißt Bild von a und besteht aus höchstens einem Objekt.

Definition 2.1.7 Eine Funktion F : A B, A U, B U, heißt

    1. partiell iff es gibt mindestens ein a U, für das F undefininiert ist, das heißt das Bild von mindestens einem A ist leer.

    2. total iff für alle a U gilt: F ( a ) ≠ .

    3. injektiv iff ( F ( a ) = F ( b )) ( a = b ).

    4. surjektiv iff für jedes b B existiert ein a A, so daß F ( a ) = b.

    5. bijektiv iff F ist injektiv und surjektiv.

Beispiel 2.1.2 Sei A die Menge aller europäischen Hauptstädte, N die Menge der natürlichen Zahlen, F : A eine Funktion, die jeder Stadt die Anzahl ihrer Einwohner zu einem fixierten Zeitpunkt t in diesem Jahrhundert zuordnet und R A x A eine Relation, mit < a, b > R iff die Stadt a hat (zum Zeitpunkt t) genauso viele Einwohner wie die Stadt b. Schließlich sei Q die Relation aller geordneten Paare von Städten, deren wechselseitige Entfernung unterhalb von 500 Kilometern liegt. Dann gilt:

    1. F ist eine Funktion: Jede Hauptstadt hat eine bestimmt Zahl von Einwohnern (und nicht etwa mehrere Einwohnerzahlen).

    2. F ist total: Es gibt keine Hauptstadt ohne Einwohner.

    3. F ist nicht injektiv: Mehrere Hauptstädte können die gleiche Zahl von Einwohnern aufweisen.

    4. F ist nicht surjektiv: Z. B. gibt es keine Hauptstad mit 1 Mrd. Einwohnern.

    5. R ist reflexiv: Jede Hauptstadt hat so viele Einwohner wie sie selbst.

    6. R ist symmetrisch: Falls a so viele Einwohner hat wie b, dann gilt auch das Umgekehrte.

    7. R ist transitiv: Falls a so viele Einwohner hat wie b, das so viele Einwohner hat wie c, dann haben a und c die gleiche Anzahl von Einwohnern.

    8. R ist folglich eine Äquivalenzrelation: Mit Hilfe von R kann die Menge aller europäischen Hauptstädte in Äquivalenzklassen von Städten mit gleicher Einwohnerzahl geteilt werden. Die Vereinigung dieser Äquivalenzklassen entspricht A.

    9. Q ist eine Toleranzrelation.

Definition 2.1.8 Das Komplement einer Relation R A x B ist definiert als

Rc = ( A x B ) - R

Definition 2.1.9 Die Inverse R-1einer Relation R ist definiert als

R-1 = { < b, a > | < a, b > R }

Definition 2.1.10 A : { 0, 1 } heißt charakteristische Funktion von A, falls A ( x ) = 1 für x A und 0 sonst.

Definition2.1.11 Seien f : A B und g ; B C zwei Funktionen. Dann ist f ο g : A C eine Funktion, genauer: Die Komposition von f und g, mit: f ο g ( x ) = g ( f ( x )).

Definition 2.1.12 Die Funktion idA : A A, mit idA ( x ) = x für alle a A, heißt Identitätsfunktion auf A.

Definition 2.1.13 BA = { f | f : A B } ist die Menge aller Funktionen von A nach B.

Definition 2.1.14 Die Menge aller Teilmengen von A heißt Potenzmenge von A und wir mit Pot ( A ) symbolisiert.

 
2.2 Boolesche Algebren zurück

Definiton 2.2.1 Für jede natürliche Zahl n 0 und jede Menge A heißen die Funktionen f : An → A n-stellige Operationen auf A. Die Menge aller n-stelligen Operationen auf A wird mit Opn ( A ) bezeichnet.

Definition 2.2.2 Sei F eine Menge von Operationen beliebiger Stelligkeit über der Menge A. : F N { 0 } ist eine Funktion, die jedem f F, mit f Opn ( A ), dessen Stelligkeit ( f ) = n zuordnet.

Definition 2.2.3 Eine Algebra A ist ein Tupel < A, f1, ..., fn, c1, ..., ck>, für das gilt:

    1. Die Menge A heißt Universum von A.

    2. f1, ..., fn sind Operationen über A, das heißt fi : Asi A für alle i { 1, ..., n }. ( fi ) = si ist die Stelligkeit der Operation fi.

    3. ci, ..., ck A ist eine Menge von Konstanten (mit der Stelligkeit 0).

Anmerkung 2.2.1 Als Algebren gelten somit Entitäten von zunächst "allgemeiner Natur": Die wichtigste Festlegung besteht darin, dass eine Menge vorliegt, über der eine oder mehrere Funktionen definiert sind, deren Wertebereich wieder Teilmenge der Ausgangsmenge ist. Eine Algebra formalisiert also eine Menge zusammen mit Operationen auf dieser Menge, die angeben, wie man mit den Elementen dieser Menge "rechnen" kann.

Definition 2.2.4 Der Typ einer Algebra A = < A, f1, ..., fn, ...> ist ein geordnetes Paar ( F, σ ), wobei F = { f1, ..., fn } und σ : F N { 0 } eine Funktion ist, die jedem fi F dessen Stelligkeit σ ( fi ) zuordnet. Man nennt fi dann σ ( fi ) -stellige Operation.

Definition 2.2.5 Zwei Algebren A, B sind von demselben Typ, falls die in ihnen definierten Operationen paarweise die selbe Stelligkeit haben, das heißt die i-te Operation fi aus A hat die selbe Stelligkeit wie die i-te Operation gi aus B.

Beispiel 2.2.1 Sei 0 = { 0 } die Menge aller natürlichen Zahlen beginnend mit 0, dann ist < N0, +, 0 > eine wohlbekannte Algebra mit 0 als neutralem Element bezüglich der Addition (da für alle x gilt: x + 0 = x ) als einzige (zweistellige) Operation.

Beispiel 2.2.2 Ist < 0, *, 1 > eine Algebra ('*' symbolisiert die Multiplikation)? Ist < 0, /, 1 > eine Algebra ('/' symbolisiert die Division)?

Definition 2.2.6 Seien A, B Algebren desselben Typs mit den Universen A, B. Eine Abbildung h : A B heißt Homomorphismus von A und B iff:

(Hom) h [ fiA ( a1, ..., asi)] = fiB [ h ( a1 ), ..., h ( asi )]fiA für alle i { 1, ..., n }.

n ist die Anzahl von Operationen der Algebren A und B. si ist die Stelligkeit der i-ten Operation fiA aus A bzw. fiB aus B.

Beispiel 2.2.3 Sei A = < A, ... > eine Algebra und idA die Identitätsabbildung auf A. Ist dann idA : A A ein Homomorphismus?

Anmerkung 2.2.2 Falls h : A B ein Homomorphismus von A = < A, F1 > nach B = < B, F2 > ist, dann ist h eigentlich als Abbildung zwischen den Universen A, B beider Algebren zu verstehen, das heißt h : A B. Dennoch findet man (wie auch hier) vielfach die Schreibweise: h : A B. Strenggenommen müßten beide Schreibweisen unterschieden werden. Aus Vereinfachungsgründen verwenden wir beide Schreibweisen.

Beispiel 2.2.4: Sei A = < 0, +, 0 > und B = < Z 0, , 0 >, mit a b = a + b - 1 für alle a, b Z0. Ferner sei h eine Funktion, mit h ( a ) = a + 1 für alle a 0. Ist h : A B ein Homomorphismus?

Homomorphismen sollen nun mit Hilfe von Graphen veranschaulicht werden. Das hat den Vorteil, dass die Struktur von Graphen gewissermaßen "visualisiert" werden kann. Graphen sind aber keine Algebren, da die Relation der Kanten eines Graphen keine Relation darstellt. Wir müssen also zunächst Graphen gesondert definieren:

Definition 2.2.7 Sei V eine nicht-leere Menge. Sei ferner E V2. Das geordnete Paar < V, E > heißt gerichteter Graph.

Definition 2.2.8 Seien G1 = < V1, E1 >, G2 = < V2, E2 zwei Graphen. φ : G1 G2 heißt Homomorphismus von G1 nach G2, falls für alle e = < a, b > gilt:

 φ ( e ) = ( φ ( a ), φ ( b )) E2

Beispiel 2.2.5 Seien A = { 1, 2, 3, 4 } und B = { F, S, Q } zwei Mengen. Es gelte nun G1 = < A, {( 1, 4 ), ( 1, 2 ), ( 2, 2 ), ( 2, 3 )}> sowie G2 = < B, {( S, Q ), (S, F ), ( F, F )}>. G1, G2 sind Graphen und es kann ein Homomorphismus h : G1 G 2 definiert werden mit h ( 1 ) = S, h ( 2 ) = h ( 3 ) = F, h ( 4 ) = Q.

Definition 2.2.9 Seien A, B zwei Algebren desselben Typs und sei h ein Homomorphismus von A nach B. Dann heißt h Isomorphismus von A nach B, falls h eine bijektive Abbildung ist. A, B heißen dann isomorph, und man schreibt hierfür A B.

Anmerkung 2.2.3 Liegt ein Isomorphismus zwischen zwei Algebren vor, so kann die eine Algebra aus der anderen sozusagen durch Umbenennungen gewonnen werden.

Anmerkung 2.2.4 Falls A = < A1, f1, ..., fn > eine Algebra mit n verschiedenen Operationen ist, so kann A der Einfachheit halber auch mittels < A, F > wiedergegeben werden, wobei F = { f1, ..., fn }. Ferner: Wenn A = < A, f1, ..., fn > eine Algebra mit endlich vielen Operationen ist, dann notiert man den Typ dieser Algebra auch in der Form ( σ1, ..., σn ), wobei σi die Stelligkeit der Operation fi ist für i { 1, ..., n }.

Anmerkung 2.2.5 Was soll man vor dem Hintergrund der in 2.2.1 gegebenen Definition für Operationen unter einer nullstelligen Operation verstehen? Man kann An als die Menge aller Abbildungen g : { 0, 1, ..., n - 1 } A definieren. Auf der Basis dieser Interpretation repräsentieren wir jedes n-Tupel aus An durch eine solche Funktion g. Gilt nun für ein g An und i { 0, 1, ..., n - 1 } : g ( i ) = a A, so bedeutet das, dass ein Tupel < a0, ..., ai, ..., an-1 > existiert, so dass aj A für alle j { 0, ..., n - 1 } und g ( i ) = a = ai.

Unter diesen Voraussetzungen ist dann A0 = { g | g : A }. Es gibt aber nur eine Abbildung g : A, nämlich g = . Warum? Man erinnere sich, dass Funktionen spezielle Relationen waren; Relationen sind aber nichts anderes als Mengen. Die Abbildung g : A kann also wiedergegeben werden als g = { < x, g ( x ) > | x B } und für B = also g = . Also gilt schließlich A0 = { }.

An = { g | g : { 0, ..., n - 1 } A } ist dann der Definitionsbereich einer n-stelligen Operation, die An auf A abbildet und eine nullstellige Operation f ist daher eine Abbildung f : { } A. Dieses Abbildungen entsprechen aber exakt den Elementen aus A, denn f ist durch das Element f { } A eindeutig bestimmt und zu jedem a A gibt es genau eine Abbildung fa : { } A mit fa { } = a. Dieser Eigenschaft nullstelliger Operationen wegen nennt man diese auch Konstanten. Anstelle von fa schreibt man einfach a. Die in der Definition von Algebren enthaltenen Konstanten können also vollständig durch nullstellige Operationen wiedergegeben werden.

Es ist üblich, auf der Basis vorhandener mathematischer Strukturen neue Strukturen abzuleiten bzw. zu entwickeln. Im Bereich der allgemeinen Algebra kann dies mit Hilfe sogenannter Subalgebren (Auch Unteralgebren genannt) geschehen. Der Vorteil abgeleiteter Strukturen besteht darin, dass ihre Eigenschaften durch Bezug auf bzw. Einschränkung von (strukturellen) Eigenschaften bereits bekannter Strukturen definierbar sind.

Definition 2.2.10 Sei A = < A, f1A, ..., fnA > eine Algebra vom Typ ( F, σ ). Sie ferner B A. Die Algebra

B = < B, f1B, ..., fnB >

heißt dann Subalgebra von A, wobei fiB : Bni B für alle i { 1, ..., n } die Einschränkung von fiA auf die Menge B ist. Das heißt: Für alle i { 1, ..., n } und alle < a1, ..., an > Bni gilt:

f1B ( a1, ..., ani ) = f1A ( a1, ..., ani ) B.

Es gilt weiterhin: σ ( f1B ) = σ ( f1A ) = ni. Falls B eine Subalgebra von A ist, dann schreibt man B ≤ A. Die Menge aller Universen von Subalgebren einer Algebra A ist Sub ( A ) = { B | B = < B, F > ≤ A }.

Eine Teilmenge B A ist also genau dann das Universum einer Unteralgebra von A = < A, F >, falls B unter allen (fundamentalen, dass heißt nicht abgeleiteten) Operationen von A abgeschlossen ist.

Beispiel 2.2.6 Sei die Algebra N = < 0, + 0 > aus Beispiel 2.2.1 gegeben. Wir können dann folgende Subalgebra N' von N konstruieren: N' = < { 0 }, +, 0 >. Offensichtlich ist die Menge { 0 } abgeschlossen unter der Addition. Weiterhin ist N' die einzige Subalgebra von N mit endlichem Universum, denn falls M ≠ { 0 } irgend eine echte Teilmenge von N0 ist und ferner max ( M ) = m das größte Element der Menge M ist, dann gilt sicherlich m + m M.

Wir wollen an dieser Stelle eine einfache Eigenschaft von Subalgebren beweisen, um ein wenig Gespür für diesen Vorgang zu gewinnen. Natürlichsprachlich formuliert lautet der zu beweisende Satz: Das System der Subalgebren einer Algebra ist unter der Durchschnittsbildung ( das heißt unter der Operation " ∩ " abgeschlossen. Mathematisch formuliert wird hieraus:

Satz 2.2.1 Sei A = < A, F > eine Algebra mit Operationen f F. Dann gilt:

1. A Sub ( A ).

2. Sei der Ausdruck " ∩ " für eine beliebige, nicht leere Teilmenge X Sub ( A ) definiert als ∩ X =def ∩ {B | B X }. Es gilt dann: ∩ X Sub ( A ).

Beweis: Teilsatz (1) folgt unmittelbar aus der Definition für Subalgorithmen: Es gilt für alle Algebren A = < A, F > : A ≤ A. Und daher: A Sub ( A ). Teilsatz (2) ist etwas schwieriger zu beweisen. Wir überlegen uns zunächst, was genau wir zu beweisen haben: ∩ X Sub ( A ) für alle ≠ X Sub ( A ), das heißt ∩ X muss das Universum einer Subalgebra X ≤ A sein und daher unter den Operationen von A abgeschlossen sein, andernfalls wäre ∩ X nicht in Sub ( A ) enthalten. Mit anderen Worten: Es ist zu zeigen, dass ∩ X unter allen fundamentalen Operationen f von A abgeschlossen ist.

Sei nun f F eine solche Operation mit Stelligkeit σ ( f ) = n. Wir können nun zunächst aus dem Umstand b1, ..., bn ∩ X = ∩ { B | B X } folgern, dass b1, ..., bn B für alle B X. Da alle B X Grundmengen von Subalgebren von A darstellen (denn es gilt X Sub ( A )), sind diese allesamt unter den fundamentalen Operationen von A abgeschlossen und also gilt: f ( b1, ..., bn ) B für alle B X und somit f (b1, ..., bn ∩ X. Also ist unter den gemachten Voraussetzungen auch ∩ X abgeschlossen unter den Operationen aus F.

Natürlich kann für das Beweisen von mathematischen Sätzen kein "Rezept" (das heißt Algorithmus) angegeben werden, so dass die Befolgung des Algorithmus den gesuchten Beweis automatisch herzuleiten gestattet. Mathematische Beweise stellen vielmehr komplexe Gebilde dar, zu deren Herleitung bisweilen ein Höchstmaß an Kreativität erforderlich ist. In unserem Fall reicht es allerdings aus, Satz und Definition der durch den Beweis betroffenen Entitäten "genau zu studieren". Jeder Schritt des Beweises ist dann eine unmittelbare Folgerung aus den Behauptungen des Satzes, den Festlegungen der entsprechenden Definitionen und/oder aber eine Folgerung aus aus einem vorangehenden Beweisschritt, für den die selbe Überlegung angestellt werden kann.

Definition: 2.2.11 Ein Verband ist eine Algebra V = < V, , > vom Typ ( 2, 2 ), wobei folgende Gesetze gelten: für alle a, b V gilt:

1. a b = b a, a b = b a (Kommutativität);

2. a ( b c ) = ( a b ) c, a ( b c ) = ( a b ) c (Assoziativität);

3. ( a b ) b = b, ( a b ) b = b (Absorption).

Anstelle von Verbänden können wir auch folgende, einfacher definierte Struktur betrachten:

Definition 2.2.12 Eine verbandsgeordnete Menge ist ein Tupel < V, ≤ >, das heißt eine Struktur aus einer Menge und einer Ordnungsrelation ≤ V x V über dieser Menge, das heißt es gilt stets für alle a, b, c V:

1. a ≤ a (Reflexivität);

2. wenn a ≤ b und b ≤ a, so a = b (Antisymmetrie);

3. wenn a ≤ b und b ≤ c, so a ≤ c (Transitivität).

4. Für je zwei Elemente a, b V existieren sup ( a, b ) V (kleinste obere und größte untere Schranke bezüglich ≤). sup ( a, b ) ist das kleinste Element c V, für das gilt: a ≤ c und b ≤ c. Falls also ein Element d ≠ sup ( a, b ) existiert, so dass a ≤ d und b ≤ d, so folgt hieraus: sup ( a, b ) ≤ d. inf ( a, b ) ist entsprechend das größte c V, für das gilt: c ≤ a und c ≤ b.

inf und sub können auch auf Teilmengen von V bezogen werden: Sei A V, dann ist inf A = ( { b | b A }) V dadurch bestimmt, dass inf A ≤ b für alle b A und ferner: falls für ein c V, c ≠ inf A gilt, dass c ≤ b für alle b A, so folgt hieraus: c ≤ inf A. Entsprechend definiert man sup B = sup ( { b | b A }). Schließlich schreibt man inf V = und sup V = .

Beispiel 2.2.7 Sei I = [ 0, 1 ] das Einheitsintervall, das heißt die Menge aller realen Zahlen, die größer-gleich 0 bzw. kleiner-gleich 1 sind. ≤ sie die bekannte Relation über der Menge der realen Zahlen, wobei < a, b > ≤ iff a ≤ b iff a ist eine kleinere Zahl als b. < I, ≤ > ist eine verbandsgeordnete Menge mit = 1 und = 0.

Zwischen verbandsgeordneten Mengen und Verbänden besteht folgender Zusammenhang:

Satz 2.2.2 (1) Wenn V = < V, , > ein Verband ist, und ≤ V2 erklärt ist durch a ≤ b iff a b = a ( iff a b = b ), dann ist B ( V ) = < V, ≤ > eine verbandsgeordnete Menge. (2) Wenn B = < V, ≤ > eine verbandsgeordnete Menge ist, und wenn die beiden Operationen und erklärt sind duch a b = sup ( a, b ) sowie a b = inf ( a, b ), dann ist V ( B ) = < V, , > ein Verband. Anmerkungen zu Satz 2.2.2

Wir sind nun in der Lage die für die klassische Logik so fundamentale Struktur der Booleschen Algebren einzuführen:

Definition 2.2.13 Eine Boolesche Algebra ist eine Algebra < A, , , > mit den Zusatzbedingungen:

1. < A, , > ist ein Verband. Ferner gilt für alle a, b A:

2. a ( b c ) = ( a b ) ( a c ), a ( b c ) = ( a b ) ( a c )

3. ( a a ) b = b, ( a a ) b = b.

a heißt Komplement von a.

Anmerkung 2.2.6 Die dritte Bedingung der Definition für Boolesche Algebren impliziert die Existenz von und , nämlich: = a a und = a a. Man schreibt für und auch 1 und 0.

Anmerkung 2.2.7 Die Aristotelische Logik beansprucht u. a. die Geltung des Gesetzes vom ausgeschlossenen Drittel (ungefähr so: "Eine beliebige Aussage ist wahr oder falsch, ein Drittes gibt es nicht.") sowie diejenige des Gesetzes vom ausgeschlossenen Wiederspruch ("Eine beliebige Aussage ist nicht gleichzeitig wahr oder falsch."). In ihrer algebraischen Notation (auf der Grundlage Boolescher Algebren) können diese beiden Gesetze mittels a a = bzw. ( a a ) = (für alle a des betrachteten Universums) formuliert werden. Erstere Formel gilt unmittelbar in allen Booleschen Algebren (siehe letztere Anmerkung). Die zweite Formel gilt ebenso in allen Booleschen Algebren: In allen Booleschen Algebren gelten die Beziehungen ( a b ) = a b und a = a ( was wir hier nicht beweisen wollen). Somit kann ( a a ) mit a a = a a = a a = wiedergegeben werden. M. a. W.: Die zwei hier zitierten Aristotelischen Gesetze stellen fundamentale Eigenschaften Boolescher Algebren dar. Anders ausgedrückt: Boolesche Algebren sind gerade so konstruiert, dass letztere beiden Gesetze für sie gelten.

Bevor wir einige Beispiele Boolescher Algebren kennen lernen werden, soll zunächst noch eine wichtige Eigenschaft dieser Klasse von Algebren bewiesen werden, nämlich die Idempotenz:

Satz 2.2.3 Sei A = < A, , , , > eine Boolesche Algebra, dann gilt für alle a A: a a = a und a a = a ( Idempotenz von und ).

Beweis: Wir wollen nur die Eigenschaft a a = a (für alle a a) betrachten. Es gilt: ( a a ) a = a (3. Definitionsbedingung Boolescher Algebren). Da Boolesche Algebren kommutativ und distributiv sind, kann letzterer Ausdruck zunächst zu a ( a a = a und weiterhin zu ( a a ) ( a a ) umgeformt werden. Der Ausdruck links des Gleichheitszeichens entspricht nun aber genau dem linken Teilausdruck aus der Definitionsbewegung (3) Boolescher Algebren. Also kann man ersetzen und erhält a a = a ( ganz analog zeigt man a a = a). D. h. in jeder Booleschen Algebra gilt die Idempotenz von und .

Dieser Beweis zeigt gerade, dass unabhängig davon, welche Boolesche Algebra man auch vorliegen haben mag, von der Geltung der Idempotenz ihrer beiden fundamentalen zweistelligen Operationen ausgegangen werden kann, da diese allgemein für alle Booleschen Algebren gilt: Die Eigenschaft der Idempotenz wurde für die Klasse der Booleschen bewiesen und gilt nunmehr für jede ihrer Instanzen.

Beispiel 2.2.8 Sei U eine beliebige Menge, dann ist PU = < Pot ( U ), , ∩, c > eine Boolesche Algebra und es gilt: U = sowie = . Denn: ist eine Ordnungsrelation über Pot ( U ) und < Pot ( U )), > daher eine verbandsgeordnete Menge. Dann ist aber (gemäß Satz (2.2.2)) inf ( B, C ) = B ∩ und sup ( B, C ) = B C für alle B, C Pot ( U ). Ferner gilt: Die Distributivität ist ein mengentheoretisches Gesetz. Schließlich gilt stets: B ∩ ( C Cc ) = B ∩ U = B und ( C ∩ Cc ) = B = B.

Beispiel 2.2.9 Sei ΞA = { Xx | X Pot ( A ) }, i. e. die Menge aller charakteristischen Funktionen der Teilmengen der Menge A, gegeben. Dann ist < ΞA, , , > mit:

1. XA XB = XA B,

2. XA XB = XA ∩ B und

3. XA = XAc

Eine Boolesche Algebra und man kann einen Homomorphismus h : PA ΞA mit h ( X ) = Xx definieren. h ist ein Homorphismus, denn:

1. h ( A B ) = XA B = XA XB = h ( A ) h ( B ).

2. h ( A ∩ B ) = XA ∩ B = XA XB = h ( A ) h ( B ).

3. h ( Ac ) = XAc = XA = h ( A ).

Beispiel 2.2.10 Sei die Algebra = < { 0, 1 }, , , > mit der Signatur ( 2, 2, 1 ) gegeben. Die einzelnen Operationen sind wie folgt definiert: Für alle a, b { 0, 1 } ist

1. a b min ( a, b );

2. a b max ( a, b );

3. a = 1 - a.

ist eine Boolesche Algebra.

 
2.3 Monoide zurück

Definition 2.3.1 Ein Monoid ist eine Algebra < A, ο, ε > mit der Signatur ( 2, 0 ), die folgende Gleichungen für alle a, b, c A erfüllt:

1. ( a ο b ) ο c = a ο ( b ο c ) (Assoziativität)

2. ε ο a = a ο ε = a (neutrales Element)

Beispiel 2.3.1 Sei die Algebra < 0, +, 0 > aus Beispiel 2.2.1 gegeben. < 0, +, 0 > ist ein Monoid.

Definition 2.3.2 Sei A eine beliebige Menge und sei con eine Funktion mit con ( a, b ) = a b (die "Hintereinanderschreibung" von a und b) für alle a, b A. Sei ferner con assoziativ und es gelte für ein ε A { ε } (das "leere" Wort): con ( a, ε ) = con ( ε, a ) = a, dann heißt con Konkatenationsoperation.

Definition 2.3.3 Sei A eine beliebige Menge. Sei z. B. A eine Menge von Symbolen. Es kann nun mit Hilfe von con ein Monoid F ( A ) = < A*, con, ε > konstruiert werden, welches als das durch A determinierte freie Monoid bezeichnet wird. A* heißt Kleene-Hülle von A und wird wie folgt definiert:

A0 = { ε }

A1 = A

A1 = AA = { x y | x, y A }

An = An-1A = { x y | x An-1 und y A }

Man hat dann:

A* = Ai.
i=0,∞

Die Menge A wird auch als Alphabet bezeichnet. A* ist die Menge aller endlichen Strings aus Elementen der Menge A.

Beispiel 2.3.2 Sei A die Menge der Buchstaben des deutschen Alphabets. Dann gilt etwa: Computerlinguistik A*, baab A*, etc.

Das rekursive Konstruktionsprinzip, welches der Ableitung der Kleene-Hülle zugrunde liegt, kann als ein grundlegendes Prinzip (unter anderen) zum Aufbau der Syntax formaler Sprachen verstanden werden. Natürlich schränkt man bei der Bildung formaler Sprachen die Menge syntaktisch wohlgeformter Ausdrücke durch Angabe zusätzlicher Bildungsregeln ein. Das rekursive Konstruktionsmuster werden wir aber vielfach erhalten geblieben sehen.