F l S hFormale Sprachen

Mathematische Grundlageng

Rudolf FREUND, Marian KOGLER

Elementare Mengentheorie

GEORG CANTOR (1845 - 1918)G O G C O ( 8 5 9 8)

„Eine Menge ist eine Zusammenfassung von bestimmtenwohlunterschiedenen Objekten unseres Denkens oderunserer Anschauung (welche die Elemente der Mengegenannt werden) zu einem Ganzen “genannt werden) zu einem Ganzen.1874: Über eine Eigenschaft des Inbegriffs aller reellen

algebraischen Zahlenalgebraischen Zahlen.J. reine angew. Math., 77, 258-262

Elementare Mengentheorie

Eine Menge ist eine Gruppe von Objekten, die als Einheitä ti t drepräsentiert werden.

Mengen können beliebige Typen von ObjektenMengen können beliebige Typen von Objektenbeinhalten, inklusive Zahlen, Symbole, und auch andereMengen.g

Die Objekte einer Menge bezeichnet man als Elemente.

Um einige Konzepte zu veranschaulichen, verwenden wirU e ge o epte u e a sc au c e , e e deVenn-Diagramme. Dabei werden Mengen als Kreisedargestellt.

Mengentheorie - Zugehörigkeit

Mengen können formal auf verschiedene Arten beschrieben werden.

Ei Mö li hk it b t ht d i di El t f li tEine Möglichkeit besteht darin, die Elemente aufzulisten:

{7 21 57} enthält die Elemente 7 21 57{7,21,57} enthält die Elemente 7,21,57

Notation: ∈ ... Mengen-Zugehörigkeit 7 ∈ {7,21,57}

∉ Nicht Zugehörigkeit 5 ∉ {7 21 57}∉ ... Nicht-Zugehörigkeit 5 ∉ {7,21,57}

Mengentheorie - (Multi-) Mengen

Die Reihenfolge der Elemente und auch derenDie Reihenfolge der Elemente und auch derenWiederholung in einer Menge ist nicht von Bedeutung.

{7,7,57,7,21} = {7,21,57}

Bemerkung:

{7} d {7 7} i d id ti h M b t hi dli h{7} und {7,7} sind identische Mengen, aber unterschiedliche Multimengen (multisets).

Mengentheorie – Kardinalität von MengenEine unendliche Menge enthält unendlich viele Elemente.Beispiel:M d tü li h Z hl N {0 1 2 3 }Menge der natürlichen Zahlen: N = {0, 1, 2, 3,...}Menge der natürlichen Zahlen ≥ k: Nk = {k, k+1, k+2,...} Menge der natürlichen Zahlen zwischen k und m: [k m]Menge der natürlichen Zahlen zwischen k und m: [k..m]Besteht eine Menge aus den Elementen a1,...,an für n ≥ 1,dann schreibt man A = {a1,...,an } (endliche Menge).{ 1, , n } ( g )

Die Anzahl der Elemente einer endlichen Mengebezeichnet man als Kardinalität, geschrieben als card(M).

Die Menge, die keine Elemente enthält, wird als leereMenge bezeichnet und geschrieben als { } oder Ø

bezeichnet man als Kardinalität, geschrieben als card(M).

Menge bezeichnet und geschrieben als { } oder Ø.

Beispiel: card(A) = n card(Ø) = 0Beispiel: card(A) = n card(Ø) = 0

Mengentheorie – Mengenvorschrift

Mengen können auch durch eine Mengenvorschriftangegeben werden:g g

{ x | E(x) } Menge der Objekte x für die E(x) gilt

{ x ∈ A | E(x) } Menge der Objekte aus der Menge A für die E(x) giltfür die E(x) gilt

{ x ∈ A | E(x) } ist äquivalent zu { x | E(x) und x ∈ A } { | ( ) } q { | ( ) }

Beispiel: { n | n = m2 für m ∈ N }Beispiel: { n | n = m2 für m ∈ N }

Mengentheorie - (echte) TeilmengenFür zwei Mengen A und B gilt:

A ist eine Teilmenge von B wenn jedes Element von AA ist eine Teilmenge von B, wenn jedes Element von Aauch ein Element von B ist.

BA ⊆ B A

B

A ist eine echte Teilmenge von B, wenn A eine Teilmenge von B ist die nicht gleich B istvon B ist, die nicht gleich B ist.

A ⊂ B

A = B wenn A ⊆ B und B ⊆ A

Mengentheorie – Operationen auf Mengen

Vereinigung: A ∪ B := { x | x ∈ A oder x ∈ B } A B

Vereinigung endlich vieler Mengen M1,..,Mn∪i {1 }Mi∪i ∈ {1,...,n}Mi

Vereinigung abzählbar unendlich vieler Mengen M1,M2,...g g g 1 2

∪ i ∈ N1Mi bzw. ∪ i ∈ N1

Mi

M { | M fü i i N }∪ i ∈ N1Mi = { x | x ∈ Mi für ein i ∈ N1 }

Für beliebige Mengen A, sodass Ma für jedes a ∈ A eineg g a jMenge ist, definiert man

∪ i ∈ A Ma= { x | x ∈ Ma für ein a ∈ A }i ∈ A a { | a ü e a }

Mengentheorie – Operationen auf Mengen

Durchschnitt: A ∩ B := { x | x ∈ A und x ∈ B }A B

Durchschnitt: A ∩ B : { x | x ∈ A und x ∈ B }

analog ∩ i ∈ {1,...,n}Mi , ∩ i ∈ N1Mi , ∩ i ∈ A Ma A B

A und B sind disjunkt wenn A ∩ B = ∅

A BDifferenzmenge: A – B := { x | x ∈ A und x ∉ B }

A B

BGilt A ⊆ B, so nennt man B – A das

A_

G ⊆ , so e a dasKomplement von A (bezüglich B), geschrieben A oder Acgeschrieben A oder A

Sequenzen und TupelEine Sequenz von Objekten ist eine geordnete Liste vonObjekten.

Beispiel: (7,21,57) ist eine andere Sequenz als (7,57,21)oder auch (7 7 21 57)oder auch (7,7,21,57)

Endliche Sequenzen werden auch Tupel genannt.Eine Sequenz mit k Elementen wird k-Tupel genannt;(7,21,57) ist also ein 3-Tupel oder Tripel; ein 2-Tupel wird

h P tauch Paar genannt.

Mengen und Tupel können auch Elemente von anderenMengen und Tupeln sein.

Mengentheorie – Operationen auf Mengen

Potenzmenge von A: Menge aller Teilmengen von A 2A bzw. ℘(A)Menge aller Teilmengen von A 2 bzw. ℘(A)

Beispiel:A = { 0,1 } 2A = { { }, {0}, {1}, {0,1} }

Kartesisches Produkt (Kreuzprodukt): A × B := { x | x = (a,b) mit a ∈ A und b ∈ B }{ | ( ) }M1 ×...× Mn := { x | x = (x1,...,xn) mit xi ∈ Mi für 1 ≤ i ≤ n }

card(A) = n, card(B) = m card(2A) = 2n card(A × B ) = nm( ) ( )

Relationen und FunktionenRelation R auf S: R ⊆ S × S

(Definitionsbereich (domain) × Wertebereich (range))M P ( b) b i i B i h i hMenge von Paaren (a,b), wobei eine Beziehung zwischen a und b aus S besteht oder nicht besteht.Schreibweise: aRbSchreibweise: aRb

Eigenschaften von Relationen1 Reflexiv wenn aRa für alle a aus S gilt1. Reflexiv wenn aRa für alle a aus S gilt2. Irreflexiv wenn aRa für alle a aus S falsch ist3. Transitiv wenn aRc aus aRb und bRc folgt4 Symmetrisch wenn bRa aus aRb folgt4. Symmetrisch wenn bRa aus aRb folgt5. Asymmetrisch wenn aRb impliziert, dass bRa nicht gilt.

Beispiel:

Ordnungsrelation < auf der Menge der ganzen Zahlen ist g g gtransitiv und asymmetrisch (und daher irreflexiv )

Relationen und Funktionen

Äquivalenzrelation:Relation, die reflexiv, symmetrisch und transitiv ist.

Wichtige Eigenschaft einer Äquivalenzrelation R auf S: S wird durch R in disjunkte, nichtleere Äquivalenzklassen unterteilt.S wird durch R in disjunkte, nichtleere Äquivalenzklassen unterteilt. S = S1 ∪ S2 ∪ ... , wobei für i und j mit i ≠ j gilt:

1 S ∩ S = {}1. Si ∩ Sj = {}2. Für jedes a und b aus Si ist aRb wahr3. Für jedes a aus Si und b aus Sj ist aRb falsch

Beispiel: Kongruenz modulo einer ganzen Zahl m

i ≡ j (mod m) falls i und j ganze Zahlen sind mit derEigenschaft, dass i - j durch m teilbar ist.

Relationen und FunktionenHüllen von RelationenE..Menge von Eigenschaften von Relationen über S.E Hülle von R ist die kleinste Relation R‘ die alle Paare von R enthältE-Hülle von R ist die kleinste Relation R , die alle Paare von R enthält und die Eigenschaften aus E besitzt

Transitive Hülle von R geschrieben R+:Transitive Hülle von R, geschrieben R :1. Falls (a,b) in R ist, so ist (a,b) auch in R+

2. Falls (a,b) und (b,c) in R+ sind, so ist (a,c) auch in R+

3. Nichts ist in R+, außer es folgt aus 1. und 2.

Reflexive und Transitive Hülle von R geschrieben R*:Reflexive und Transitive Hülle von R, geschrieben R :R+ ∪ {(a,a) | a ∈ S }

Beispiel: Sei R = { (1,2),(2,2),(2,3) } Relation auf {1,2,3}

R+ = { (1,2),(2,2),(2,3),(1,3) } { ( , ),( , ),( , ),( , ) }

R* = { (1,1),(1,2),(1,3),(2,2),(2,3),(3,3) }

Relationen und Funktionen

Unter einer Funktion oder Abbildung f: X → Y einer MengeX i i M Y (f t l t d h f X Y) t htX in eine Menge Y (festgelegt durch f ⊆ X × Y) verstehtman eine Vorschrift, die jedem Element x von X eineindeutig bestimmtes Element y aus Y zuordnet: f(x)=yeindeutig bestimmtes Element y aus Y zuordnet: f(x) y(f(x) ist der Funktionswert von f an Stelle x)

Funktionswerte von f (range):rng(f) = { y | (x,y) ∈ f für ein x ∈ X}

f: X → Y und g: X → Y heißen gleich, symbolisch f ≡ g,wenn f(x) = g(x) für alle x ∈ Xwenn f(x) = g(x) für alle x ∈ X.

Relationen und Funktionen

Man nennt f• surjektiv von X auf Y wenn rng(f) =Y;• surjektiv von X auf Y, wenn rng(f) =Y;• injektiv wenn für beliebige x1,x2 ∈ X aus f(x1) = f(x2)

auch x1= x2 folgt;auch x1 x2 folgt;• bijektiv wenn f sowohl surjektiv als auch injektiv ist.

BeweiseEin Beweis ist ein überzeugendes logisches Argument,dass eine Aussage wahr ist.

Beweis durch KonstruktionViele Sätze behaupten die Existenz von bestimmtenViele Sätze behaupten die Existenz von bestimmtenTypen von Objekten. Ein Weg, solche Sätze zu beweisen,besteht darin, zu zeigen, wie man diese Objektekonstruiert.

Indirekter Beweis (Beweis durch Widerspruch)Indirekter Beweis (Beweis durch Widerspruch)Wir nehmen an, dass der Satz wahr ist, und zeigen dann,dass diese Annahme zu einer offensichtlich falschendass diese Annahme zu einer offensichtlich falschenKonsequenz, einem Widerspruch, führt.

Beweise

CARL FRIEDRICH GAUSS (1777 1855)CARL FRIEDRICH GAUSS (1777-1855)

Die Lehrer von Gauss waren sehr erstaunt, als dieser bereits im Alter von sieben Jahren die Zahlen von 1 bis 100 im Handumdrehen summieren konnte.

Er erkannte nämlich sofort, dass diese Summe aus 50 Zahlenpaaren bestand, die jeweils 101 ergaben.p , j g

Beweise: InduktionUm eine Aussage A(n) für alle n ∈ N (bzw. für alle n ∈ Nk)zu beweisen: (A(n) hängt von der ganzen Zahl n ≥ k ab.)

Induktionsbasis:A(m) ist für m = k richtig.( ) g

Induktionshypothese:( ) fNehme an, A(m) gilt für m = n.

Induktionsbehauptung:Induktionsbehauptung:Zeige, A(m) gilt dann auch für m = n+1.

Induktionsprinzip:Dann ist die Aussage A(m) für alle m ≥ k richtig.

Beweise: InduktionB i i lBeispiel: Aussage: Für alle positiven natürlichen Zahlen gilt:

1+2+ +n = (n (n+1))/21+2+...+n (n (n+1))/2 Induktionsbasis:A(n) ist offensichtlich für n = 1 richtig: 1 = (1*2)/2( ) g ( )Induktionshypothese:1 + 2 +...+ n = (n (n+1))/2Induktionsbehauptung:1 + 2 +...+ n + n + 1 = ((n + 1) (n+1 + 1))/2 Einsetzen und Umformen ergibt: 1 + 2 +...+ n + n + 1 = (n (n+1))/2 + n + 1 = ( 1)(( /2) 1) ( 1)(( 2)/2) (( 1) ( 1 1))/2Somit haben wir mittels Induktion bewiesen:1+2+ +n = (n (n+1))/2 gilt für alle natürlichen Zahlen n ≥1

(n+1)((n/2)+1) = (n+1)((n+2)/2) = ((n + 1) (n+1 + 1))/2

1+2+...+n = (n (n+1))/2 gilt für alle natürlichen Zahlen n ≥1.

Beweise: Induktion - Aufgaben

Aufgabe INDA: Zeigen Sie mittels Induktion, dass für alle positiven natürlichen Zahlen n gilt: p g13+23+...+n3 = ((n (n+1))/2)2

Aufgabe INDB**: Zeigen Sie mittels Induktion nach n, dass für alle positiven natürlichen Zahlen n und k gilt:

k k k1k+2k+...+nk = ((n (n+1))/2) pk(n)wobei pk(x) ein Polynom vom Grad k-1 in x ist.

Aufgabe INDC: Zeigen Sie mittels Induktion nach n, dass eine Zahl k so gewählt werden kann, dass für alledass eine Zahl k so gewählt werden kann, dass für alle positiven natürlichen Zahlen n ≥ k gilt: n! ≥ 2n ( n! = n * (n-1) … 2 *1 )n! 2 ( n! n * (n 1) … 2 *1 )

Beweise: Generalisierung

Kann man für jede beliebig gewählte natürlich Zahl n (≥k) zeigen, dass die Aussage A(n) gilt, dann gilt sie für ( ) g , g ( ) g , galle natürlichen Zahlen n (≥k) .

Beispiel: Es gibt beliebig große PrimzahllückenBeispiel: Es gibt beliebig große Primzahllücken.

Wir nehmen eine beliebige natürlich Zahl n ≥ 1 und zeigen, dass es n 1 aufeinanderfolgende Zahlen gibt die alledass es n-1 aufeinanderfolgende Zahlen gibt, die alle keine Primzahlen sind: Betrachten! + k für k = 2,…, n, ,Klarerweise gilt k/(n!+k), da k ein Faktor von n! ist. q.e.d.

GraphenSeien V und W endliche Mengen. Ein markierter gerichteter Graphg über V und W ist ein Tripel (K,E,L) wobei- K die Menge der KnotenK die Menge der Knoten- E ⊆ K × K × W die Menge der Kanten- L: K → V die Knotenmarkierungsfunktion ist.

Ein Element (x,w,y) ∈ E stellt eine gerichtete Kante vom Knoten x zum Knoten y mit Markierung w dar.

Beispiel: g = ({1,2}, {(1,u,2),(2,v,2)}, {(1,a),(2,b)}) ist ein markierter gerichteter Graph über W ⊇ {a,b} und V ⊇ {1,2}ist ein markierter gerichteter Graph über W ⊇ {a,b} und V ⊇ {1,2}

a b1 2

uÜbergangsmatrix:

δ u va bu

v

δ

1 {2} { }2 { } {2}

Graphen: Isomorphie und ÄquivalenzZwei markierte gerichtete Graphen g = (K,E,L) und g‘= (K‘,E‘,L‘) über V und W heißen isomorph, wenn es i bij kti Abbild f K K‘ ibt d fü lleine bijektive Abbildung f: K → K‘ gibt, sodass für alle

k,l ∈ K und w ∈ W gilt:(k w l) ∈ E ↔ (f(k) w f(l)) ∈ E‘ 1 2 x(k,w,l) ∈ E ↔ (f(k),w,f(l)) ∈ E .

a b1 2

u

v

r

u

Gilt ß d L(k) L‘(f(k)) fü ll k K

v u

y sGilt außerdem L(k)=L‘(f(k)) für alle k ∈ K, so heißen g und g‘ äquivalent.

yv

y xa b1 2

u b ay x

u

v v

Mächtigkeit von Mengen

Zwei Mengen A und B heißen gleichmächtig, wenn es eine bijektive Abbildung von A nach B gibteine bijektive Abbildung von A nach B gibt.

Jede Menge, die gleichmächtig mit N ist, heißt eine g g gabzählbare Menge.

J d dli h i ht b ählb M h ißtJede unendliche, nicht abzählbare Menge heißt überabzählbar.

Beispiel: Die Menge aller reellen Zahlen ist gleichmächtig mit der Menge der reellen Zahlen in jedem beliebigen Intervall (a,b) = { x | x reell und a < x < b}.B id M i d i ht b ählbBeide Mengen sind nicht abzählbar.

DiagonalverfahrenSei M = {0,1}N die Menge aller Funktionen f: N→ {0,1} .Dann ist M nicht abzählbar.

Cantorsches DiagonalverfahrenAngenommen, es gibt eine bijektive Funktion g: N → M.g , g j gSei dann die Funktion h: N → {0,1} folgendermaßendefiniert: h(n) = ([g(n)] (n) +1 (mod 2)), i.e.,

1 falls [g(n)](n) = 0h(n) = 0 falls [g(n)](n) = 1Dann ist h eine Funktion von N in {0,1}, die somit in M sein müsste, allerdings wurde h so definiert, dass für kein

N h ( ) i k d fü j d N iltn ∈ N h = g(n) sein kann, denn für jedes n ∈ N gilt h(n) ≠ [g(n)](n), was aber h ∉ M bedeutet. Somit ergibt sich aber ein Widerspruch zur AnnahmeSomit ergibt sich aber ein Widerspruch zur Annahme, dass die Menge M abgezählt werden kann.

Cantorsches Diagonalverfahren

g(1)≠ h

g(2)≠ h

… g(n)≠ h

…≠ h ≠ h ≠ h

1 [g(1)](1)≠ h(1)

[g(2)](1) … [g(n)](1) …≠ h(1)

2 [g(1)](2) [g(2)](2)≠ h(2)

… [g(n)](2) …≠ h(2)

… … … … … …

n [g(1)](n) [g(2)](n) … [g(n)](n)h( )

…≠ h(n)

… … … … … …

Folgerung

Sei A eine abzählbar unendliche Menge. Dann ist 2A

überabzählbar.überabzählbar.

Sei A = {xn | n ∈ N } und für jede Teilmenge M ⊆ A die{ n | } j g ⊆Funktion χM: N→ {0,1} durchχM = 0, falls xn ∉ M und

1 f ll MχM = 1, falls xn ∈ M,definiert; χM ist die charakteristische Funktion bezüglichA Dann ist durch g: 2A → {0 1}N mit g(m) = χ eineA. Dann ist durch g: 2 → {0,1} mit g(m) = χM einebijektive Abbildung zwischen 2A und {0,1}N definiert und2A nach dem vorigen Satz somit ebenfalls überabzählbar.g

Algebraische Strukturen

Sei A eine nichtleere Menge und ○: A x A → A eine binäre Operation auf A. Dann heißt die algebraische S k (A ) G idStruktur (A,○) Gruppoid.In (A,○) können folgende Gesetzmäßigkeiten gelten:(1) Assoziativgesetz: Für alle a,b,c aus A gilt:

(a ○ b) ○ c = a ○(b ○ c)(2) Existenz eines neutralen Elements: Es gibt ein

Element e aus A derart, dass für alle a aus A gilt:e ○ a = a ○ e = a

(3) Existenz inverser Elemente: Für alle a aus A gibt esi El t ‘ A itein Element a‘ aus A mit:

a ○ a‘ = a‘ ○ a = e(4) K t ti t Fü ll b A ilt(4) Kommutativgesetz: Für alle a,b aus A gilt:

a ○ b = b ○ a

Gruppe, Monoid

Eine algebraische Struktur (A,○) heißt(1) Halbgruppe, wenn sie assoziativ ist;(2) M id i i H lb ( l i i )(2) Monoid, wenn sie eine Halbgruppe (also assoziativ)

ist und ein neutrales Element besitzt;(3) Gruppe wenn sie ein Monoid ist und zu jedem(3) Gruppe, wenn sie ein Monoid ist und zu jedem

Element aus A ein inverses Element in A existiert.

Kommutative Gruppen werden auch als AbelscheGruppen bezeichnet.

Beispiel: (N,+) und (N,.) sind kommutative Monoide.Beispiel: (Z,+) und (Q \ {0},.) sind Abelsche Gruppen.p ( ) ( { } ) ppBeispiel: (Σ*, ⋅ ) ist ein nichtkommutatives Monoid mit demLeerwort als neutralem Element; Σ* wird auch als freies;Monoid über dem Alphabet Σ bezeichnet.

Semiringe

Eine algebraische Struktur (A,+,.) mit den beiden binären Operationen + (Addition) und . (Multiplikation)

f A h iß S i i F l d ilauf A heißt Semiring, wenn Folgendes gilt:(1) (A,+) ist eine kommutative Halbgruppe.(2) (A ) ist eine Halbgruppe(2) (A,.) ist eine Halbgruppe.(3) Es gelten die Distributivgesetze:

Für alle a,b,c aus A gilt:, , g(a+b).c = a.c + b.c und c.(a+b) = c.a + c.b

Besitzt der Semiring ein neutrales Element bezüglich derBesitzt der Semiring ein neutrales Element bezüglich derAddition, so nennt man dieses Nullelement.Besitzt der Semiring ein neutrales Element bezüglich derBesitzt der Semiring ein neutrales Element bezüglich derMultplikation, so nennt man dieses Einselement.

Semiringe

Beispiel:(N,+,.) ist ein kommutativer Semiring mit Nullelement 0

B i i l

und Einselement 1.

Beispiel:Die Menge der formalen Sprachen über einem Alphabet T bildet daher einen nichtkommutativen Semiring mit derbildet daher einen nichtkommutativen Semiring mit der Vereinigung als Addition und dem neutralen Element {} sowie mit der Konkatenation als Multiplikation und dempEinheitselement {ε}.

Ringe, Körper

Eine algebraische Struktur (A,+,.) heißt Ring, wenn sie ein Semiring ist und (A,+) sogar eine (kommutative) G iGruppe ist. Ein Ring (A,+,.) mit Einselement 1 (ungleich dem Nullelement 0) in dem jedes Element ungleich 0 einNullelement 0), in dem jedes Element ungleich 0 ein inverses Element besitzt, heißt Schiefkörper. Ist (A,+,.) ein Ring und auch (A,.) eine Abelsche ( , , ) g ( , )Gruppe, so heißt (A,+,.) Körper.

B i i l (Z + ) i t i k t ti Ri it Ei l t

Beispiel: (Q,+,.) ist ein Körper.

Beispiel: (Z,+,.) ist ein kommutativer Ring mit Einselement.