Formale Grundlagen der Informatik Repetitorium PDF Herbst-/Wintersemester 2024

Formale Grundlagen der Informatik Repetitorium Carl Seela, Konrad Peeck, Elsa Pham - Herbst-/Wintersemester 2024...

Formale Grundlagen der Informatik Repetitorium Carl Seela, Konrad Peeck, Elsa Pham - Herbst-/Wintersemester 2024 Folien in Anlehung an Rebecca Armbruster, Bhavika Sharma, Adam Bednar, Julian Steigerwald (HWS2020) und Jonathan Kobbe (HWS2016) Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 1 / 150 Überblick 1 Aussagenlogik 2 Beweise und Beweismethoden 3 Mengen 4 Relationen 5 Äquivalenzrelationen 6 Halbordnungsrelationen 7 Abbildungen 8 Kombinatorik 9 Graphen 10 Algebraische Strukturen 11 Endliche Automaten 12 Reguläre Ausdrücke Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 2 / 150 Disclaimer Alle hier getätigten Aussagen und dargestellten Informationen erheben keinerlei Anspruch auf Vollständigkeit oder Korrektheit. Im Zweifel haben einzig und allein die von Seiten des Lehrstuhls gemachten Angaben verbindlichen Charakter. Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 3 / 150  Aussagenlogik Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 4 / 150 Belegung Definition Eine Belegung ordnet jeder Aussagevariablen einen Wahrheitswert zu. Bn bezeichnet die Menge aller möglichen Belegungen von Aussagevariablen X1 ,..., Xn. Beispiel F = X 1 → ¬X 2 X 1 = 1, X 2 = 0 ist eine Belegung. (Kurzschreibweise: (1,0)) B2 = {(0,0), (0,1), (1,0), (1,1)} F ((1,0)) = 1 → ¬0 = 1 → 1 = 1. Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 5 / 150 Äquivalenz von zusammengesetzten Aussagen Definition Zwei zusammengesetzte Aussagen F und G heißen äquivalent (F ↑ G), falls sie über den gleichen Variablen definiert sind und identische Wahrheitstafeln aufweisen. d.h. F (b) = G(b) gilt für alle Belegungen b dieser Variablen. Beispiel F = ¬(X 1 ↓ X 2 ) , G = X 1 ↔ ¬X 2 X1 X2 X 1 ↓ X 2 ¬(X 1 ↓ X 2 ) ¬X 2 X 1 ↔ ¬X 2 0 0 1 0 1 0 0 1 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 0 Es gilt also F ↑ G Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 6 / 150 Wichtige Regeln I Seien F, G und H aussagenlogische Formeln. Kommutativität F ↔G ↑G↔F F →G ↑G→F Assoziativität (F ↔ G) ↔ H ↑ F ↔ (G ↔ H) (F → G) → H ↑ F → (G → H) Distributivität F ↔ (G → H) ↑ (F ↔ G) → (F ↔ H) F → (G ↔ H) ↑ (F → G) ↔ (F → H) Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 7 / 150 Wichtige Regeln II F : Es regret G : Straße nass De Morgan ¬(F ↔ G) ↑ ¬F → ¬G ¬(F → G) ↑ ¬F ↔ ¬G Kontraposition F ↓ G ↑ ¬G ↓ ¬F Implikation F ↓ G ↑ ¬F → G Beweis Hin- und Rückrichtung F ↗ G ↑ (F ↓ G) ↔ (G ↓ F ) Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 8 / 150 Wichtige Regeln III Idempotenz F ↔F ↑F F →F ↑F Identität F ↔1↑F F ↔0↑0 F →1↑1 F →0↑F Komplementarität F → ¬F ↑ 1 ¬(¬F ) ↑ F F ↔ ¬F ↑ 0 Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 9 / 150 Tautologie und Kontradiktion Definition Eine Formel F heißt Tautologie, falls F ↑ 1. Das heißt für jede mögliche Belegung b gilt: F(b)=1 VbeB" F(b) : = 1 Beispiele Auf F → ¬F (F ↔ (F ↓ G)) ↓ G Definition Eine Formel F heißt Kontradiktion bzw. widersprüchlich, falls F ↑ 0. Das heißt für jede mögliche Belegung b gilt: F(b)=0 Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 10 / 150 Erfüllbar Definition Eine Formel F heißt erfüllbar, falls F nicht widersprüchlich ist. Das heißt, es existiert eine Belegung, sodass F (b) = 1. IbeB" : F(b) 1 = Definition Eine Formelmenge F = {F1 ,..., Fm } heißt erfüllbar, falls sie nicht widersprüchlich ist. -- D.h. es existiert mind. eine Belegung b, sodass F1 (b) = F2 (b) =... = Fm (b) = 1. - - O Beispiele X1 ↔ ¬X2 X1 ↓ X2 F1 = {X1 ↔ ¬X2 }, F2 = {X1 ↓ X2 } ist hingegen nicht erfüllbar. Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 11 / 150 Folgerung Sei F = {F1 ,..., Fm } eine Menge von Formeln. (F1F21... 1 Fn) - Definition m C ! Wir sagen, dass eine Aussage G aus F folgt, falls die Formel Fi ↓ G eine Tautologie i=1 ist. Das heißt, für alle Belegungen b von F gilt, dass G(b) = 1 aus - F1 (b) = · · · = Fm (b) = 1 folgt. Beispiel Sei F = {X1 ↓ X2 , X1 ↘ X2 }. (Die einzige Belegung, die die Formelmenge erfüllt, ist b = (0, 1)). Dann ist G = X1 → X2 eine Folgerung von F, da 0 → 1 = 1. Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 12 / 150  Beweise und Beweismethoden Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 13 / 150 Beweismethoden Beim direkten Beweis versucht man die Behauptung durch Umformen zu beweisen. Beim indirekten Beweis: 1 Man negiert die Behauptung des Satzes. 2 Man versucht dann den Beweis zu einem Widerspruch zu führen. 3 Da der Beweisgang legitim und logisch war, muss die Annahme falsch gewesen sein, also folgt die Behauptung des Satzes. Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 14 / 150 Vollständige Induktion - Vorgehen Beweisverfahren, um eine Aussage für eine Teilmenge der ganzen Zahlen zu beweisen. (Hier: Für alle n ≃ N+ ) Hinweis: Unterscheidung zwischen N+ und N E O (Induktionsanfang) n = 1 : Zeige die Aussage für die erste Zahl (durch Einsetzen von 1). G (Induktionsvoraussetzung) Schreibe: Die Behauptung gelte für ein beliebiges, festes n ≃ N +. -IN , IR , Q O (Induktionsschluss) nu0 1 + Ersetze n durch (n+1) in der linken Seite der Behauptung. - - Forme um und wende die Behauptung an (Begründung: IV). Forme um, bis die rechte Seite der Behauptung dasteht, nur mit (n+1) statt n. Erläuterung Im Induktionsschluss zeigt man, dass die Aussage für eine beliebige Zahl stimmt, falls sie für deren Vorgänger stimmt. Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 15 / 150 1 = 1 heINE~ ⑪ beliebigen aber fixierten Die Behauptung gelte für ein ⑮ non + 1 +( + ( +1 ) = =(n)2 + Vollständige Induktion - Kleiner Gauß n ! n·(n+1) Behauptung: →n ↑ N+ : i= 2 i=1 Beweis: 1 ! 2 1·(1+1) IA (n=1): i =1= 2 = 2 i=1 IV: Die Behauptung gelte für ein beliebiges, festes n ↑ N+. IS: n+1 " n " IV n · (n + 1) i= i + (n + 1) = + (n + 1) 2 i=1 i=1 n · (n + 1) + 2 · (n + 1) (n + 2) · (n + 1) = = 2 2 (n + 1) · ((n + 1) + 1) = 2 Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 16 / 150 Summenzeichen 5 ! 2i = 22 + 23 + 24 + 25 i=2 Wichtige Rechenregeln b ! c ! b ! Aufspalten: f (i) = f (i) + f (i) - i=a i=a i=c+1 !b b ! aX1 + aXz + aXz" Faktor herausziehen: c · f (i) =O c· f (i) i=a !b b ! i=a b ! a(x1 + xz - Addieren: f (i) + g(i) = (f (i) + g(i)) i=a i=a i=a !b b+k ! Indexshift: f (i) = f (i ↓ k ) i=a i=a+k !b Summe über einer Konstanten: c = (b ↓ a + 1) · c i=a Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 17 / 150  Mengen Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 18 / 150 Kardinalität Sei A eine Menge. A =0 934 , Definition Die Kardinalität |A| von A ist die Anzahl von Elementen in A (falls A endlich ist). Beispiele |{1,2,3,4}| = 4 |{{1,2},{3,4},{5,6}}| = 3 & |↔| = 0 Anmerkung ↔ oder {} ist die sog. leere Menge. = > Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 19 / 150 Teilmenge Seien A, B Mengen. Definition (Teilmenge) ⑰ A ↗ B :↘ →x ↑ A : x ↑ B Beispiele {1,2,5} ↗ {1,2,3,4,5} - - N↗Z {2,3} ↗ {2,3} - Anmerkung Die leere Menge ist Teilmenge jeder Menge. - Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 20 / 150 Komplement Sei A eine Menge bezüglich eines UniversumsO U. Anmerkung Das Universum ist die Menge aller betrachteten Elemente. Meistens ist es implizit - vorgegeben und wird nicht explizit erwähnt. Definition (Komplement) Ā := {x ↑ U | x ↑ - - / A} Beispiele Sei U = N M := {x ↑ N |x ist gerade} ≃ M̄ = {x ↑ N |x ist ungerade} MUM = 21 - N̄ = ↔ Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 21 / 150 Durchschnitt und Vereinigung Seien A, B Mengen. Definition (Durchschnitt) A ⇐ B := {x | x ↑ A ⇒ x ↑ B} Definition (Vereinigung) A ⇑ B := {x | x ↑ A ⇓ x ↑ B} Beispiele {1,2,3} ⇐ {2,3,4,5} = {2,3} {1,2,3} ⇑ {2,3,4,5} = {1,2,3,4,5} A⇐↔=↔ A⇑↔=A Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 22 / 150 (Symmetrische) Mengendifferenz Seien A, B Mengen. Definition (Mengendifferenz) A \ B := {x | x ↑ A ⇒ x ↑ / B} Definition (Symmetrische Differenz) A⇔B := {x | x ↑ A ↖ x ↑ B} Beispiele &. {1,2,3} \ {2,3,4,5} = {1} {1,2,3}⇔{2,3,4,5} = {1,4,5} Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 23 / 150 Disjunktheit Seien A, B Mengen. Definition A und B heißen disjunkt, falls A ⇐ B = ↔. Beispiele Die Mengen {1,2} und {4,5} sind disjunkt. Die Mengen {1,2,3} und {2,3,4,5} sind nicht disjunkt. - Eine beliebige Menge und die leere Menge sind immer disjunkt. Anmerkung Wenn M, N endlich und disjunkt sind, dann gilt |M ⇑ N| = |M| + |N|. - - Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 24 / 150 Potenzmenge Sei M eine Menge. Definition (Potenzmenge) Die Potenzmenge P(M) einer Menge M ist die Menge aller Teilmengen von M. Bemerkung: P(M) = {N | N ↗ M} Satz (m) Falls M endlich ist, gilt |P(M)| = 2|M|. (P(M)) = 2 Beispiel Sei M = {1,2,3}. Dann ist P(M) =- {↔, {1},{2},{3},{1,2},{2,3},{1,3},{1,2,3}}. - |P(M)| = 23 = 8 Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 25 / 150 Partition Sei M eine nichtleere Menge. Definition Eine Familie {Mi , i ↑ I} ↗ P(M) von nichtleeren Teilmengen von M heißt Partition von M, falls Mi , Mj disjunkt für alle i ↙= j ↑ I und # Mi = M. i→I Beispiel Sei M = {1,2,3,4,5,6,7}. Eine Partition von M könnte so aussehen: { {1}, {2,5}, {3,4,6},{7} } { {1}, {2}, {4,5,6,7} } - keine Partition von M (3 nicht enthalten) { {1,2,3,5}, {3,4,6},{7} } - keine Partition von M (3 doppelt enthalten) Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 26 / 150 Karthesisches Mengenprodukt Seien M, N Mengen. (Reihenfolge wichtig) &Reihenfolge eges 3 Definition (Karthesisches Mengenprodukt) M ∝ N := {(x,y ) | x ↑ M ⇒ y ↑ N} M n := M ∝ M ∝... ∝ M Satz Für alle natürlichen Zahlen n ′ 1 und alle nichtleeren Mengen M1 ,M2 ,...,Mn gilt, dass |M1 ∝ M2 ∝... ∝ Mn | = |M1 | · |M2 | ·... · |Mn | Beispiel Sei M = {1,2,3} und N = {3,4} - - M ∝ N = {(1,3), (1,4), (2,3), (2,4), (3,3), (3,4)} - - - - - - -2 - Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 27 / 150  Relationen Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 28 / 150 Grundlegende Definition Seien M, N Mengen. S Definition Eine Relation R zwischen M und N ist eine Teilmenge von M ∝ N. Schreibweise xRy :↘ (x,y ) ↑ R Wenn die Relation aus dem Kontext klar ist, schreibt man oft x ∞ y. Beispiel Kleiner-Relation auf den natürlichen Zahlen: ( Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 40 / 150 Maximales, minimales Element, Maximum, Minimum Sei R eine Halbordnungsrelation auf X, U ↗ X. Definition u ↑ U heißt maximales (minimales) Element , falls →v ↑ U \ {u} : (u,v ) ↑ / R ((v ,u) ↑ = / R). Definition uG ↑ U heißt Maximum (Minimum) , falls →v ↑ U : (v ,u) ↑ R ((u,v ) ↑ R) (u , (21123 v) , 913) #R Beispiel Betrachte ↗ auf P(Q). Sei U = {{1},{2}, {1,2}}. Maximales Element: {1,2}, minimale Elemente: {1},{2} Maximum: {1,2}, Minimum: nicht vorhanden. ⑫ Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 41 / 150 Schranken Sei R eine Halbordnungsrelation auf X, U ↗ X. Definition 00 s ↑ X heißt obere (untere) Schranke von U, falls →u ↑ U : (u,s) ↑ R ((s,u) ↑ R) Definition Eine obere (untere) Schranke x ↑ X heißt Supremum (Infimum) von U, falls für alle oberen (unteren) Schranken s von U gilt: (x,s) ↑ R ((s,x) ↑ R). Beispiel Betrachte ∈ auf Q. Sei U = { n1 | n ↑ N+ }. Obere Schranken: 1, 2, 20,... Untere Schranken: 0, -1, -20,... Supremum: 1, Infimum: 0 Maximum: 1, Minimum: Existiert nicht Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 42 / 150 Veranschaulichung der Begriffe mit R∈ Maximale (minimale) Elemente in U: Kein anderes Element in U ist größer (kleiner). Maximum (Minimum) in U: Größer (kleiner) als jedes Element in U. Obere (untere) Schranke in X: Größer (kleiner) als jedes Element in U. Supremum (Infimum) in X: Kleinste obere Schranke (größte untere Schranke). Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 43 / 150 Veranschaulichung der Begriffe 2 Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 44 / 150 Veranschaulichung der Begriffe 2 Supremum und Infimum in U O ⑨ Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 44 / 150 Veranschaulichung der Begriffe 2 Supremum und Infimum in U Supremum und Infimum nicht in U O d & & & Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 44 / 150  Abbildungen Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 45 / 150 Partielle Abbildungen Seien X, Y nichtleere Mengen, R ↗ X ∝ Y eine Relation. Definition R heißt partielle Abbildung von X nach Y, falls zu jedem x ↑ X höchstens ein y ↑ Y mit > (x,y ) ↑ R existiert. Beispiele Die Relation ∈ ist keine partielle Abbildung auf R, da 3 ∈ y für mehr als ein y ↑ R gilt. = ist eine partielle Abbildung und wird als Identität (id) bezeichnet. Merke Jedem X-Wert wird höchstens ein Y-Wert zugeordnet. - - Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 46 / 150 Bild und Urbild Sei R ↗ X ∝ Y eine partielle Abbildung. Definition (Urbildbereich) Der Urbildbereich (Domain) dom(R) ↗ X von R enthält alle x ↑ X , für die ein y ↑ Y mit (x,y ) ↑ R existiert - Definition (Bildbereich) Der Bildbereich (Image) im(R) ↗ Y enthält alle y ↑ Y , für die ein x ↑ X mit (x,y ) ↑ R existiert Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 47 / 150 Bild und Urbild Merke Urbildbereich: Von dort wird abgebildet. Bildbereich: Dorthin wird abgebildet. Beispiele Die Funktion x 2 hat als maximalen Urbildbereich R, der maximale Bildbereich ist jedoch R+ 2 0 (da x ′ 0). Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 48 / 150 Abbildungen Sei R ↗ X ∝ Y eine partielle Abbildung. Definition R heißt Abbildung von X nach Y, falls zu jedem x ↑ X genau ein Element y ↑ Y mit - - - (x,y ) ↑ R existiert. (Sprich: R ist eine Abbildung, falls eine Partielle Abbildung mit dom(R) = X ist) = Schreibweise: [ R:X ∋Y Beispiele R : R ∋ R mit (x,y ) ↑ R :↘ y = ln(x) ist keine Abbildung, da ln(↓1) nicht definiert ist. Es ist jedoch eine partielle Abbildung. R : R+ ∋ R mit gleichem R ist eine Abbildung. Merke Jedem X-Wert wird genau ein Y-Wert zugeordnet. Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 49 / 150 Injektivität Sei f : X ∋ Y eine Abbildung. Definition f heißt injektiv, falls zu jedem y ↑ Y höchstens ein x ↑ X mit f (x) = y existiert. Merke Jeder Y-Wert wird höchstens einmal angenommen. f (x) f : R+ 2 0 ∋ R, x △∋ x - x Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 50 / 150 Surjektivität Sei f : X ∋ Y eine Abbildung. Definition f heißt surjektiv, falls zu jedem y ↑ Y mindestens ein x ↑ X mit f (x) = y existiert, d.h., falls im(f ) = Y. - Merke Jeder Y-Wert wird mindestens einmal angenommen. f (x) f : R ∋ R+ 2 0 , x △∋ x Mini x Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 51 / 150 Bijektivität Sei f : X ∋ Y eine Abbildung. Definition f heißt bijektiv, falls f injektiv und surjektiv ist. Merke Jeder Y-Wert wird genau einmal angenommen. f (x) f : R+ + 2 - 0 ∋ R0 , x △∋ x - x Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 52 / 150 Komposition f : X.... ∋ Y,g : Y ∋ Z Definition (g ▽ f )(x) := g(f (x)) Beispiel f (x) = x 2 , g(y ) = sin(y ) + y ≃ (g ▽ f )(x) = g(f (x)) = g(x 2 ) = sin(x 2 ) + x 2 Satz g, f injektiv ≃ g ▽ f injektiv. g, f surjektiv ≃ g ▽ f surjektiv. Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 53 / 150 Gleichmächtigkeit Definition Zwei Mengen X, Y heißen gleichmächtig, falls es eine bijektive Abbildung f : X ∋ Y gibt. Beispiel N und M := {x ↑ N | x ist gerade} sind gleichmächtig. Mögliche Bijektion: f : N ∋ M, x △∋ 2 · x. Satz Für X , Y endlich gilt: X , Y gleichmächtig ↘ |X | = |Y | Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 54 / 150 Abzählbarkeit Definition Eine Menge M heißt abzählbar, falls sie endlich oder gleichmächtig zu N ist. Beispiel Die Menge der geraden Zahlen ist abzählbar, siehe Folie vorher. Satz Existiert eine injektive Abbildung f : X ∋ N, so ist X abzählbar. X abzählbar ≃ Y ↗ X ist abzählbar. 1 X, Y abzählbar ≃ X ∝ Y ist abzählbar.. Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 55 / 150 Überabzählbarkeit Definition Eine Menge M heißt überabzählbar, falls sie nicht abzählbar ist. Beispiele P(N) ist überabzählbar. R ist überabzählbar. Q ist abzählbar (also nicht überabzählbar). Satz (Satz von Cantor) Für alle nichtleeren Mengen M ↙= ↔ gilt: M ↙∞ P(M). zim ! Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 56 / 150 Abzählbarkeit, Überabzählbarkeit Zusammenfassung Abzählbarkeit einer Menge Eine Menge M ist also entweder 1 endlich (und damit abzählbar) oder 2 unendlich und abzählbar oder 3 unendlich und überabzählbar. Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 57 / 150 Ein paar Tipps für die Herangehensweise Ist die Menge endlich? (Kardinalität berechnen mit Methoden aus der Kombinatorik) (Über-)Abzählbarkeit der Menge aus VL bekannt? N, Q, R Ist die Menge eine Teilmenge oder Obermenge einer bekannten Menge? Ist die Menge Potenzmenge einer bekannten unendlich, abzählbaren Menge? (Satz von Cantor hilfreich beim Nachweis einer überabzählbaren Menge) Ist die Menge ein karthesisches Produkt aus abzählbaren Mengen? Können Ideen aus den Übungsaufgaben angewendet werden? (Menge der n22 Abbildungen von [n] ∋ N ist abzählbar, andererseits von N ∋ [n] ist überabzählbar) Hilft alles nichts... ∋ Annahme treffen ∋ Bijektion in bekannte, (über-)abzählbare Menge bilden Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 58 / 150 Übungsaufgabe 1: Abzählbarkeit = Definiere eine bijektive Funktion g : A ∋ B, wobei - - g(a b) (Di A = N2 = - , B = {0,1} ∋ N - - Hinweis: Die Definition muss nur exakt festlegen, wie einem Paar (a,b) ↑ N2 eine Funktion f : {0,1} ∋ N zugeordnet wird. Überlege Dir zunächst ein paar Beispiele von = Funktionen in {0,1} ∋ N. - Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 59 / 150 Übungsaufgabe 2: Abzählbarkeit Bestimme, ob die folgenden Mengen abzählbar oder überabzählbar sind: a) N3 b) R ∝ N c) Die Menge aller Abbildungen {0,1} ∋ R d) Die Menge aller Abbildungen N ∋ {0,1,2} e) Die Menge aller Abbildungen von {0,1,2} ∋ N Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 60 / 150 2a): N3 INXIN XI (m ,, na ( ny) ~N abzählbarer Das Kartesische Mengenprodukt auch abzehlbar. Mengen ist Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 61 / 150 2b): R ∝ N (r , n) Aberebichlbar Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 62 / 150 2c): Die Menge aller Abbildungen {0,1} ∋ R f(0) = r f(x) = re irn , => überbzählbar Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 63 / 150 2d): Die Menge aller Abbildungen N ∋ {0,1,2} => überebzählbar -Y 1...n ) (... x m) *) (y | m = = 10. 1, 23/) = 3 - Satz von Canto => üb. ah. => üerbzählbar ~ Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 64 / 150 2e): Die Menge aller Abbildungen von {0,1,2} ∋ N 8 20 , 1 , 23 IN : - > f(0) = n- y() = ncf(2) = us (n , nz , ns) ~ IN /N 23 N3 , = /N XIX IN Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 65 / 150  Kombinatorik Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 66 / 150 Binomialkoeffizient Definition (Binomialkoeffizient) $n % Für alle natürlichen Zahlen n ′ 0 und k , 0 ∈ k ∈ n, bezeichne k die Anzahl der k-elementigen Teilmengen einer n-elementigen Menge In der Kombinatorik Die Anzahl der Möglichkeiten, k Elemente aus einer Grundmenge mit n Elementen ohne Zurücklegen und ohne Beachtung der Reihenfolge auszuwählen. Satz $n % (n) (vi") n! Für alle natürlichen Zahlen n, k mit 0 ∈ k ∈ n gilt: k = k !(n↑k )!. = + Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 67 / 150 Stirlingzahl zweiter Art Definition & ' Für n ′ 1 und 1 ∈ k ∈ n bezeichnet kn die Stirling-Zahl zweiter Art bzgl. n, d.h. die Anzahl der Partitionen einer n-elementigen Menge in k nichtleere Teilmengen. Satz { kn } = { kn↑1 n↑1 ↑1 } + k { k }, für alle 3 ∈ k < n o { n1 } = { nn } = 1 { n2 } = 2n↑1 ↓ 1 Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 68 / 150 Bell Number Definition (Bell Number) Für n ′ 1 bezeichnet Bn die Bell-Zahl bzgl n, d.h. die Anzahl aller Partitionen einer n-elementigen Menge. Satz n ! Bn = { kn } k =1 Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 69 / 150 Anzahl Abbildungen Seien M, N nichtleere Mengen. Satz Falls M, N endlich sind, gilt: |M ∝ N| = |M| · |N| |M N | = |M||N| , hierbei steht M N für die Abbildungen von N nach M - Nu > M Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 70 / 150 Quiz - Anzahl Injektionen von {1,2,3} nach {A,B,C,D,E} ⑳D = 10 - 6 Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 71 / 150 Quiz - Anzahl Surjektionen von {A,B,C,D,E} nach {1,2,3} 957 = 25 - : 3 6 = ! 15] Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 72 / 150  Graphen Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 73 / 150 Graph Definition Ein gerichteter Graph ist ein Tupel (V, E) mit V = {v1 , v2 ,...vn } Menge von Knoten und E = {(v ,w) | v , w ↑ V ⇒ v ↙= w} Menge von Kanten. Beispiel V = {1,2,3}, E = {(1,2), (2,1), (1,3)} 2 3 1 Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 74 / 150 Grad Sei G = (V , E) ein gerichteter Graph und v ↑ V. Definition (Ingrad) indegG (v ) = |{u ↑ V | (u, v ) ↑ E}| Anzahl Kanten nach V. - Definition (Ausgrad) outdegG (v ) = |{u ↑ V | (v , u) ↑ E}| Anzahl Kanten von V. Beispiel G: 2 U-TV ingrad : 1 3 1 indegG (1) = 1, outdegG (1) = 2 Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 75 / 150 Wege und Kreise Sei G = (V ,E) ein gerichteter Graph. Definition Eine Folge von s ′ 1 aufeinanderfolgender Kanten p = ((v1 ,v2 ),(v2 ,v3 ),...,(vs ,vs + 1)) heißt Weg der Länge s von v1 nach vs+1 Ein Weg p heißt Kreis, falls v1 = vs+1 und s ′ 2 w ↑ V heißt erreichbar von v ↑ V aus in G ̸≃ (v = w oder ein Weg in G von v ↓ nach w existiert) - Wir schreiben v ↓ ∋w -- G Beispiel 2 1 i 3 4 ((1, 3), (3, 2), (2, 1)) ist ein Kreis. Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 76 / 150 Starker Zusammenhang Sei G = (V , E) ein gerichteter Graph. Definition ↓ ↓ Zwei Knoten v ,w ↑ V heißen stark zusammenhängend falls v ↓ ∋ w und w ↓ ∋ v. Wir G G ↓ ↓ schreiben dann v ← ∋ w. Die Relation {(x,y ) ↑ VxV : x ← ∋ y } ist eine Äquivalenzrelation G G auf V Definition ↓ Die Äquivalenzklassen von v ← ∋ w heißen die starken Zusammenhangskomponenten G von G. 7 Definition S G heißt stark zusammenhängend, wenn V genau eine starke Zusammenhangskomponente ist. Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 77 / 150 Ungerichteter Graph Definition Ein ungerichteter Graph ist ein Tupel (V, E) mit # V = {v1 , v2 ,...vn } Menge von Knoten und E = {{v ,w} | v , w ↑ V ⇒ v ↙= w} Menge von Kanten. Beispiel 2 ! 1 3 V = {1,2,3},E = {{1,2},{1,3}} Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 78 / 150 Ungerichteter Graph Definition - Eine Folge von s ′ 1 aufeinanderfolgender Kanten p = ({v1 ,v2 },{v2 ,v3 },...,{vs ,vs + 1}) heißt Weg der Länge s von v1 nach vs+1 Ein Weg heißt Kreis, falls v1 = vs+1 für s ′ 3 und alle Kanten auf dem Weg untereinander verschieden sind. Definition (Grad) Der Grad degg (v ) eines Knotens v ↑ V in einem ungerichteten Graphen G = (V ,E) ist die Anzahl der Kanten in E, die v enthalten. Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 79 / 150 Zusammenhang Sei G = (V ,E) ein ungerichteter Graph. Definition Zwei Knoten v ,w ↑ G heißen zusammenhängend in G, falls v = w oder falls in G ein Weg von v nach w existiert. Im ungerichteten Graphen folgt daraus auch, dass ein Weg von w nach v existiert, d.h. wir schreiben v ∀↓G w. ↓ Die Äquivalenzklassen von v ← ∋ w heißen die Zusammenhangskomponenten von G. G Bemerkung: Zwischen zwei verschiedenen ZHK im ungerichteten Graphen existieren keine Kanten! Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 80 / 150 Bäume und Wälder Sei G = (V , E) ein ungerichteter Graph. ①--- Definition G heißt zusammenhängend, wenn G genau eine Zusammenhangskomponente hat. Definition G heißt kreisfrei, falls G keine Kreise als Untergraphen enthält Definition G heißt ungerichteter Baum, wenn G kreisfrei und zusammenhängend ist. Baum Definition G heißt Wald, wenn G kreisfrei ist. D.h. falls alle Zusammenhangskomponenten Bäume sind. Barm-Wald Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 81 / 150 ⑨p Beispiel 2 3 4 1 5 V = {1,2,3,4,5}, E = {{1,2},{1,3},{4,5}} Menge der Äquivalenzklassen ist {G ,G } wobei G = G = G = {1,2,3} G = G = {4,5} Da wir 2 Äquivalenzklassen haben, ist G kein Baum aber wohl ein Wald, da G kreisfrei. Wenn wir noch die Kante {2,3} reinnehmen, ist G auch kein Wald mehr (Warum?!) Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 82 / 150 Struktursatz Bäume Satz (Struktursatz) Sei G = (V , E) ein ungerichteter Graph mit |V | ′ 3. Dann gelten die folgenden ⑳ Implikationen: |E| ′ |V | ≃ G nicht kreisfrei |E| ∈ |V | ↓ 2 ≃ G nicht zusammenhängend G zusammenhängend und |E| = |V | ↓ 1 ≃ G kreisfrei Daraus lässt sich ableiten, dass G genau dann ein Baum ist, wenn mindestens zwei der folgenden Bedingungen erfüllt sind: (1) G kreisfrei, ① (2) G zusammenhängend, (3) |E| = |V | ↓ 1 > - ② Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 83 / 150 Azyklische Graphen und gerichtete Bäume Sei G = (V , E) ein gerichteter Graph. Definition · G heißt azyklisch, falls G keine gerichteten Kreise enthält. D.h. aus v ∀↓G w folgt v = w Definition G heißt gerichteter Baum mit Wurzel s ↑ V , falls jeder Knoten in V auf genau einem Weg von s aus erreichbar ist. D.h. jeder gerichtete Baum ist azyklisch. Definition (Tiefe und Höhe) depthG (v ) = Länge des Weges von s nach v. depth(G) = Maximum aller Tiefen. heightG (v ) = Länge eines längsten Weges von v zu einem Blatt. Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 84 / 150 Beispiel eines gerichteten Baumes G: G-Wurzel s depth(G) = 2 D - 1 2 3 4 5 6 Die “Endknoten” (rot) heißen Blätter. Weiterhin gilt für die Tiefen der Knoten: depthG (s) = 0 depthG (1) = depthG (2) = depthG (3) = 1 depthG (4) = depthG (5) = depthG (6) = 2 Für die Höhen gilt: heightG (s) = 2 heightG (2) = heightG (3) = 1 heightG (1) = heightG (4) = heightG (5) = heightG (6) = 0 Es gilt also: depth(G) = heightG (s). Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 85 / 150 Binärbaum Sei G = (V , E) ein gerichteter Baum mit Wurzel s. Definition G heißt binär, falls →v ↑ V : outdegG (v ) ∈ 2 Definition Ein Binärbaum der Tiefe d heißt vollständig, wenn er 2d Blätter und 2d+1 ↓ 1 Knoten hat. (Mehr ist nicht möglich.) Vollständiger Binärbaum: s 1 2 3 4 5 6 11/1/1/ Ef Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 86 / 150 K-näre Bäume Definition Sei k ↑ N+ mit k ′ 2. Ein gerichteter Baum T = (V ,E) heißt k-när, falls outdeg(v ) ∈ k für alle v ↑ V. Jeder Binärbaum ist ein 2-närer Baum, sprich jeder Knoten hat höchstens 2 Nachfolger. Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 87 / 150 K-näre Bäume Satz a Ein k-närer Baum der Tiefe d hat maximal k d Blätter und insgesamt maximal 1↑k d+1 1↑k Knoten. Beweis. d ! 1↑k d+1 Zuerst erinnern wir uns an die geometrische Summenformel: (k i ) = 1↑k. Die i=0 gesuchte Formel steht bereits da. Nun müssen wir uns anschauen, wie die Anzahl der Knoten mit der obigen Summe zusammenhängt. Die Wurzel hat maximal k Nachfolger. Ein k-närer Baum der Tiefe 1 hat somit maximal k + 1 Knoten. Jeder von diesen Knoten hat auch maximal k Nachfolger. Somit gibt es auf der nächsten Ebene höchstens k · k Knoten, zusammen 1 + k + k 2. Per Induktion kommt man auf die obige Formel. Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 88 / 150 Faktorgraphen Definition Sei G = (V , E) ein gerichteter Graph und sei V = V1 ⇑ V2 ⇑... ⇑ Vs die Partition von V in die starken Zusammenhangskomponenten. S Dann bezeichnet der folgende Graph Ḡ = (V̄ , Ē) den Faktorgraphen von G: V̄ = {v1 ,...,vs } →i ↙= j mit i,j ↑ {1,..s} muss gelten (vi ,vj ) ↑ Ē ↘ ∃(v ,v ↔ ) ↑ E, mit v ↑ Vi , v ↔ ↑ Vj ≃ Der resultierende Faktorgraph Ḡ ist stets azyklisch! Informell: Alle Knoten aus der jeweiligen Äquivalenzklasse fassen wir zu einem Knoten vi zusammen und betrachten die Kante (vi ,vj ) nur falls ein Knoten in vi mit einem Knoten in vj verbunden ist. Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 89 / 150 SCC Beispiel D↳ ↳ Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 90 / 150  Algebraische Strukturen Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 91 / 150 Operation xoy + M = zeM Definition Eine Abbildung ▽ : M ∝ M ∋ M heißt Operation auf M. Definition Eine Operation ▽ heißt... (N +)2, +3 = 3 +2 kommutativ, wenn →x,y ↑ M : x ▽ y = y ▽ x. assoziativ, wenn →x,y ,z ↑ M : (x ▽ y ) ▽ z = x ▽ (y ▽ z). =2213 Beispiele + ist sowohl kommutativ, als auch assoziativ. ↓ ist weder kommutativ, noch assoziativ, z.B. 10 ↓ (5 ↓ 2) = 7 ↙= 3 = (10 ↓ 5) ↓ 2. x+y Das arithmetische Mittel m(x,y ) := 2 ist kommutativ, aber nicht assoziativ. Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 92 / 150 Halbgruppe Sei M eine Menge und ▽ eine Operation, die auf Elementen aus M ausgeführt wird. Definition (M, ▽) heißt Halbgruppe, wenn ▽ assoziativ ist. Beispiele (N+ , +) (Z, ·) ({0,1}, ⇒) wobei ⇒ : {0,1} ∝ {0,1} ∋ {0,1},(x,y ) △∋ x ⇒ y Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 93 / 150 Neutrales Element, Monoid Sei (M, ▽) eine Halbgruppe. Definition e ↑ M heißt neutrales Element in M, falls →m ↑ M : e ▽ m = m ▽ e = m. (M, ▽) heißt Monoid, falls M ein neutrales Element besitzt. Beispiele (N, +) mit e = 0. (N, ·) mit e = 1. (Z, +) mit e = 0. ↑ ({0,1}, ⇒) mit e = 1 da 0 ⇒ e = e ⇒ 0 = 0 und 1 ⇒ e = e ⇒ 1 = 1 Kein Monoid: (N+ , +), wobei N+ = N \ {0} Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 94 / 150 Inverses Element, Gruppe (2ya 08 + 1 = + - 80 Sei (M, ▽) ein Monoid mit neutralem Element e. Sei m ↑ M. a +c = 0 Definition m↔ ↑ M heißt invers zu m, falls m ▽ m↔ = m↔ ▽ m = e. Multiplikative Schreibweise: m↑1 , additive Schreibweise: ↓m M ↓ ist also die Menge aller Elemente aus M, die ein inverses Element in M besitzen. M heißt Gruppe falls jedes Element in M ein Inverses in M besitzt. Beispiele (Z, +) Gruppe, da →z ↑ Z : -z ist invers zu z. 2 · (Z, ·) ist keine Gruppe, da 2 · z = 1 als Gleichung in Z nicht erfüllbar ist. Itz Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 95 / 150 Zusammenfassung - Gruppe Menge mit Verknüpfung !! (G, ▽) ist eine Gruppe, wenn... G eine nichtleere Menge ist, ▽ assoziativ ist, G ein neutrales Element beinhaltet und jedes Element g in G ein Inverses g ↑1 in G besitzt. alle müssen gelben ! Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 96 / 150 Zusammenfassung Bezeichnung Assoziativität Neutrales Inverse Element Elemente Halbgruppe ↭ Bsp.: (N+ ,+) Bsp.: (N,+), mit neutr. Element e = 0 Bsp.: (Z,+), mit neutr. Element e = 0 und inversen Elementen x →1 = ↑x Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 97 / 150 Zusammenfassung Bezeichnung Assoziativität Neutrales Inverse Element Elemente Halbgruppe ↭ Bsp.: (N+ ,+) Monoid Bsp.: (N,+), ↭ O↭ mit neutr. Element e = 0 Bsp.: (Z,+), mit neutr. Element e = 0 und inversen Elementen x →1 = ↑x Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 97 / 150 Zusammenfassung Bezeichnung Assoziativität Neutrales Inverse Element Elemente Halbgruppe ↭ Bsp.: (N+ ,+) Monoid ↭ ↭ Bsp.: (N,+), mit neutr. Element e = 0 Gruppe ↭ ↭ ↭ Bsp.: (Z,+), mit neutr. Element e = 0 und inversen Elementen x →1 = →x Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 97 / 150 Restklassenmodulo Modulo →a, m ↑ N0 , b ↓= 0 : a mod m ist der Rest der Division a ÷ m. a Es gilt: a mod m = a ↔ ↗ m ↘ · m. Anschauung der Restklassen Zm , m ≃ 2 Zm := Z/RMODm = {,...,[m ↔ 1]}, bezeichnet die Menge aller Restklassen,die jeweils alle Zahlen mit gleichem Rest bei Division durch m zusammenfassen. D.h. die Restklasse ↑ Zm z.B. enthält alle z ↑ Z, die ohne Rest durch m teilbar sind. 25 Gl E E3 [433 = , , , , Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 98 / 150 Beispiel zu Restklassenmengen Solange ihr über 0 kommt - 4 + 3 +3 - 4 mod3 = 2 Beispiel Sei m = 3. Dann existieren die folgenden Restklassen mit den entsprechenden Elementen: = {..., ↔ 3,0,3,6,9,12,...} (↔3) mod 3 = (↔3) ↔ ↗ →3 3 ↘ · 3 = (↔3) ↔ (↔1) · 3 = 0 = {..., ↔ 2,1,4,7,10,13,...} (↔2) mod 3 = (↔2) ↔ ↗ →2 3 ↘ · 3 = (↔2) ↔ (↔1) · 3 = 1 = {..., ↔ 1,2,5,8,11,14,...} (↔1) mod 3 = (↔1) ↔ ↗ →1 3 ↘ · 3 = (↔1) ↔ (↔1) · 3 = 2 D.h. Z3 = {,,} Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 99 / 150 Verträglichkeit Definition (Verträglichkeit) Sei (M, ⇐) eine Halbgruppe und R eine Äquivalenzrelation auf M. Die Operation ⇐ heißt verträglich mit R, falls →x,y ,x ↑ ,y ↑ ↑ M gilt: x ⇒R x ↑ ⇑ y ⇒R y ↑ ⇓ x ⇐ y ⇒R x ↑ ⇐ y ↑ Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 100 / 150 Verträglichkeit Satz Sei (M, ⇐) eine Halbgruppe und R eine Äquivalenzrelation auf M, sodass ⇐ verträglich mit R ist. Dann erhalten wir mit der Operation ⇐ die folgende Halbgruppenstruktur (M/R,⇐) auf der Menge der Äquivalenzklassen M/R: [x]R ⇐ [y ]R := [x ⇐ y ]R Ist (M,⇐) ein Monoid mit neutralem Element e, so ist auch (M/R,⇐) ein Monoid mit neutralem Element [e]R. Ist x ↑ (M,⇐)↓ und x →1 das Inverse zu x, dann gilt [x]R ↑ (M/R,⇐)↓ und [x →1 ]R ist das Inverse von [x]R Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 101 / 150 Verträglichkeit - Das Beispiel! Multiplikative Monoiden auf Restklassenmengen Auf den zuvor definierten Restklassenmengen Zm lassen sich ebenfalls Operationen durchführen. Zusammen mit der Multiplikation ergibt sich daraus das Monoid (Zm , ·). Wir rechnen: [i] · [j] = [(i · j) mod m], →i,j ↑ Zm (siehe Verträglichkeit) Beispiel Sei m = 3, d.h. Z3 = {,,}. Dann gilt: · = [(1 · 2) mod 3] = [2 mod 3] = · = [(2 · 2) mod 3] = [4 mod 3] = Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 102 / 150 Multiplikative Gruppe (Zm , ·)⇔ Definition Per Definition muss jedes Element einer Gruppe, auch ein Inverses in dieser besitzen. In der multiplikativen Gruppe (Zm , ·)↓ sind also alle Elemente aus Zm enthalten, die auch ein inverses Element in Zm besitzen. Es gilt also: Z↓m = {[g] ↑ Zm | [g]→1 ↑ Zm } Satz Für alle m ↑ N+ , m ≃ 2, gilt Z↓m = {[b] | ggT(m,b) = 1}. Die Menge Z↓m enthält also alle Elemente [b], für die gilt, dass der größte gemeinsame Teiler von m und b die 1 ist. Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 103 / 150  ifby, Multiplikative Gruppe (Zm , ·)⇔ to, i Wie bestimmt man nun, welche Elemente in (Zm , ·)↓ enthalten sind? Wir betrachten die Menge der Zahlen {1,..,m ↔ 1} und prüfen, für welche Zahlen ggT (x,m) = 1 gilt. Dazu kann man sich die Primfaktorzerlegung von m anschauen und alle Zahlen streichen, die ein Vielfaches von mindestens einer Primzahl sind. Konkret betrachte (Z12 , ·)↓. Dann liefert die Primfaktorzerlegung 12 = 3 · 2 · 2. Alle Zahlen, die durch 3 oder durch 2 teilbar sind, streichen wir. Es ergibt sich (Z12 , ·)↓ = {,,,}. Für große m ↑ N+ prüfen wir mit dem euklidischen Algorithmus, ob x ↑ (Zm , ·)↓. Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 104 / 150 Gruppentafel von (Z12 , ·)⇔ - Sudoku-Regel 12 2. , Es [E] ET] Es EES E] E] #1] EA] EF] En] ENJE] EJ El] Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 105 / 150 Euklidischer Algorithmus - ggT Bestimme ggT(544, 391): Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 106 / 150 Euklidischer Algorithmus - ggT Bestimme ggT(544, 391): 544 : 391 = 1 Regt 153 391 : 153 = 2 Rest 85 153 : 85 = 1 Rest 68 85 : 68 = 1 Rest 17 68 : 17 = 4 Rest O Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 106 / 150 Euklidischer Algorithmus - ggT Bestimme ggT(544, 391): 544 : 391 = 1 Rest 153 Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 106 / 150 Euklidischer Algorithmus - ggT Bestimme ggT(544, 391): 544 : 391 = 1 Rest 153 391 : 153 = Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 106 / 150 Euklidischer Algorithmus - ggT Bestimme ggT(544, 391): 544 : 391 = 1 Rest 153 391 : 153 = 2 Rest 85 Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 106 / 150 Euklidischer Algorithmus - ggT Bestimme ggT(544, 391): 544 : 391 = 1 Rest 153 391 : 153 = 2 Rest 85 153 : 85 = Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 106 / 150 Euklidischer Algorithmus - ggT Bestimme ggT(544, 391): 544 : 391 = 1 Rest 153 391 : 153 = 2 Rest 85 153 : 85 = 1 Rest 68 Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 106 / 150 Euklidischer Algorithmus - ggT Bestimme ggT(544, 391): 544 : 391 = 1 Rest 153 391 : 153 = 2 Rest 85 153 : 85 = 1 Rest 68 85 : 68 = Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 106 / 150 Euklidischer Algorithmus - ggT Bestimme ggT(544, 391): 544 : 391 = 1 Rest 153 391 : 153 = 2 Rest 85 153 : 85 = 1 Rest 68 85 : 68 = 1 Rest 17 Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 106 / 150 Euklidischer Algorithmus - ggT Bestimme ggT(544, 391): 544 : 391 = 1 Rest 153 391 : 153 = 2 Rest 85 153 : 85 = 1 Rest 68 85 : 68 = 1 Rest 17 68 : 17 = Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 106 / 150 Euklidischer Algorithmus - ggT Bestimme ggT(544, 391): 544 : 391 = 1 Rest 153 391 : 153 = 2 Rest 85 153 : 85 = 1 Rest 68 85 : 68 = 1 Rest 17 68 : 17 = 4 Rest 0 Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 106 / 150 Euklidischer Algorithmus - ggT Bestimme ggT(544, 391): 544 : 391 = 1 Rest 153 391 : 153 = 2 Rest 85 153 : 85 = 1 Rest 68 85 : 68 = 1 Rest 17 68 : 17 = 4 Rest 0 ⇓ Division geht auf. Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 106 / 150 Euklidischer Algorithmus - ggT Bestimme ggT(544, 391): 544 : 391 = 1 Rest 153 391 : 153 = 2 Rest 85 153 : 85 = 1 Rest 68 85 : 68 = 1 Rest 17 68 : 17 = 4 Rest 0 ⇓ Division geht auf. ⇓ Die Zahlen sind nicht teilerfremd. Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 106 / 150 Euklidischer Algorithmus - ggT Bestimme ggT(544, 391): 544 : 391 = 1 Rest 153 391 : 153 = 2 Rest 85 153 : 85 = 1 Rest 68 85 : 68 = 1 Rest 17 68 : 17 = 4 Rest 0 ⇓ Division geht auf. ⇓ Die Zahlen sind nicht teilerfremd. ⇓ Der gemeinsame Teiler ist 17. ⇓ Da der ggT (544,391) ↓= 1 hat kein Inverses in Z544 Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 106 / 150 Beispiel) Yio di Yiry Yi-1 = - Gesucht: Inverses von 32 in (Z147 , ·), falls existent. Live Rechnung: " = ES]. S Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 107 / 150 Erweiterter Eukl. Algorithmus - Inverses in (Zm , ·) Erweiterter euklidischer Algorithmus zur Berechnung des Inversen von 71 in (Z256 , ·): i 0 1 2 3 4 5 6 7 8 ai 256 71 43 28 15 13 2 1 0 yi 0 1 -3 4 -7 11 -18 119 -256 di ↖ 3 1 1 1 1 6 2 Hinweise Wir sehen, dass der Algorithmus bei i = 8 terminiert, da a8 = 0. Den ggT von 71 und 256 können wir bei a7 ablesen, es gilt also: ggT (256, 71) = 1. Das Inverse von 71 in (Z256 , ·) können wir deshalb bei y7 ablesen, d.h. 71→1 = 119 Wir sehen, dass y8 = ↔256 ⇓ Zur Probe können wir im Falle der Existenz des Inversen prüfen, ob yi = ±m, wenn der Algorithmus bei i terminiert. Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 108 / 150 Untergruppe Definition Sei G = (G, ⇐) eine Gruppe mit neutralem Element e. H ↙ G heißt Untergruppe von G, falls e ↑ H und (H, ⇐) Gruppe mit neutralem Element e. Bemerkung Aus der Definition der Untergruppe folgt, dass H eine Untergruppe von G ist, genau dann wenn gilt H ist abgeschlossen d.h. →u,v ↑ H : u ⇐ v ↑ H H besitzt ein neutrales Element eU d.h. ∝eH ↑ H : →u ↑ H : eH ⇐ u = u ⇐ eH = u jedes Element in H besitzt ein Inverses in H d.h. →u ↑ H : ∝u ↑ ↑ H : u ⇐ u ↑ = u ↑ ⇐ u = eH Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 109 / 150 Nützliche Sätze zu Untergruppen Lagrange : Sei (G,⇐) eine endliche Gruppe und H ↙ G eine Untergruppe von G. Dann gilt |H| teilt |G| Untergruppenkriterium: Sei (G,⇐) eine Gruppe. Sei H eine nichtleere Teilmenge von G und →x,y ↑ H gilt x ⇐ y →1 ↑ H, dann ist H eine Untergruppe. Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 110 / 150 Beispiel zu Untergruppen Beispiel U := {z ↑ Z | z ist gerade} ist eine Untergruppe von (Z, +), da Abgeschlossenheit: →u, v ↑ U : u + v ↑ U 2+ 4 = 6 - > auch gerade Neutrales Element: 0 mod 2 = 0 ⇓ 0 ↑ U 3 + 3 = - nicht abgeschlo S Inverse Elemente: →u ↑ Z : u mod 2 = 0 ⇓ ↔u mod 2 = 0. D.h. →u ↑ U : ↔u ↑ U Beispiel Mit Untergruppenkriterium: Seien x,y ↑ U beliebig so gilt x + y →1 = x + (↔y ) = x ↔ y und Differenz von geraden Zahlen ist gerade (2m ↔ 2n = 2 · (m ↔ n)). Daraus folgt x ⇐ y →1 ↑ U. Außerdem U ↓= ′ da 0 ↑ U. Mit dem UG Kriterium folgt dass U eine Untergruppe von (Z,+) ist. Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 111 / 150 Ordnung at 2 = 2 2 2. in Gruppen : conocou Lintual. Sei G = (G, ⇐) eine Gruppe mit neutralem Element e. Sei a ↑ G. Definition (ak ) a0 := e und ak +1 := ak ⇐ a für alle k ↑ N0. Das entspricht i.A. nicht dem gewohnten Verständnis von Potenzen. In additiven Gruppen können wir auch schreiben: a · k. ( f 23 = 2 +2 + 2 = 2 3. Definition (Ordnung) Die Ordnung k = ordG (a) bezeichnet die kleinste natürliche Zahl k ↑ N + , sodass ak = e. Falls ↓ ∝ k ↑ N + mit ak = e, so ist ordG (a) = ∞. D.h. die Ordnung ist also die kleinste natürliche Zahl k > 0, sodass die k -fache Verknüpfung von g mit sich selbst dem neutralen Element e entspricht Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 112 / 150 Beispiel zur Gruppenordnung (i) Wir betrachten die additive Gruppe G = (Z6 ,+), mit Z6 = {,,,,,} neutralem Element e = 0. Für jedes Element a ↑ G können wir nun die Ordnung ordG (a) bestimmen. Zur Erinnerung: In einer additiven Gruppe schreiben wir für die k -fache Verknüpfung eines Elements a ↑ G auch a · k := a + a + a.... ⇓ = · 1 EJo = to 3 ⇓ ordG () = 1 6 ⇓ + + + + + = · 6 = ∈ ha6 ⇓ ordG () = 6 ⇓ + + = · 3 = ∈ ⇓ ordG () = 3 6 ⇓ + = · 2 = ∈ ⇓ ordG () = 2 6 ⇓ + + = · 3 = ∈ ⇓ ordG () = 3 6 ⇓ + + + + + = · 6 = ∈ ⇓ ordG () = 6 Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 113 / 150 Ordnung (24 , +) Satz Für die Ordnung von a ↑ G gilt außerdem: ! (i) ordG (a) ! |G| d.h. die Ordnung eines jeden Elements in G ist ein Teiler der Kardinalität von G (|G|) ei (ii) g s·ordG (a) = e, →s ↑ N+ · (iii) g |G| = e Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 114 / 150 Beispiel zur Gruppenordnung (ii) 1(20 , ) 1 2 3y einzigeKandidaten * = 6 ,, (i) An unserem Beispiel können wir uns veranschaulichen, dass die Ordnung jedes Elements der Gruppe G = (Z6 ,+)↓ ein Teiler der Kardinalität von Z6 (|Z6 | = 6) ist: ! ordG () = 1 ⇓ 1!!6 ordG () = 6 ⇓ 6!!6 ordG () = 3 ⇓ 3!!6 ordG () = 2 ⇓ 2!!6 ordG () = 3 ⇓ 3!!6 ordG () = 6 ⇓ 6!6 Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 115 / 150 Beispiel zur Gruppenordnung (iii) (ii) Wir sehen außerdem, dass die Verknüpfung eines Elements g ↑ G = (Z6 ,+) um ein Vielfaches s seiner Ordnung (hier s = 3) ebenfalls das neutrale Element ergibt: ordG () = 1 ⇓ 3·1 = 3 = + + = 6 ordG () = 6 ⇓ 3·6 = 18 = · 18 = ∈ 20 6 ordG () = 3 ⇓ 3·3 = 9 = · 9 = ∈ 6 ordG () = 2 ⇓ 3·2 = 6 = · 6 = ∈ 6 ordG () = 3 ⇓ 3·3 = 9 = · 9 = ∈ 6 ordG () = 6 ⇓ 3·6 = 18 = · 18 = ∈ Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 116 / 150 Beispiel zur Gruppenordnung (iv) (iii) Wir sehen zuletzt, dass die |Z6 |-fache Verknüpfung jedes Elements der Gruppe G = (Z6 ,+)↓ mit sich selbst dem neutralen Element entspricht: · 6 = 6 · 6 = ∈ 6 · 6 = ∈ 6 · 6 = ∈ 6 · 6 = ∈ 6 · 6 = ∈ ↑ Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 117 / 150 Erzeugte Untergruppen Sei G = (G, ⇐) eine Gruppe mit neutralem Element e. Sei a ↑ G. Definition ∋a△ bezeichnet die kleinste Untergruppe in G, die a enthält. Satz Falls ordG (a) endlich, gilt ∋a△ = {e, a, a2 ,..., aordG (a)→1 " →1 }. # Falls ordG (a) unendlich, gilt ∋a△ = {a | k ↑ N} ▽ (a )k | k ↑ N k Somit gilt ∋a△ = ordG (a). Definition G heißt zyklisch, falls ein g ↑ G existiert, so dass ∋g△ = G. In diesem Fall heißt g Erzeugendes von G. d.h. g heißt Erzeugendes, falls g jedes Element aus G erzeugen kann. Es gilt außerdem für jedes Element g ↑ G, dass g Erzeugendes von ∋g△ ist. Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 118 / 150 Beispiel zu erzeugten Untergruppen (i) In unserem Beispiel können wir die folgenden Untergruppen erzeugen: ordG () = 1 ⇓ ∋△ = {} ordG () = 6 , Ei e" 12, 13 ⇓ ∋△ = {, · 1, · 2, · 3, · 4, · 5} = {,,,,,} G De ordG () = 3 ⇓ ∋△ = {, · 1, · 2} = {,,} ordG () = 2 30 - ⇓ ∋△ = {, · 1} = {,} ordG () = 3 6 ⇓ ∋△ = {, · 1, · 2} = {,,} ∈ {,,} ordG () = 6 ⇓ ∋△ = {, · 1, · 2, · 3, · 4, · 5} = G 6 = {,,,,,} ∈ {,,,,,} Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 119 / 150 Beispiel zu erzeugten Untergruppen (ii) In unserem Beispiel sehen wir, dass gilt ∋△ = ∋△ = Z6. D.h. und sind Erzeugende von G = (Z6 ,+). Außerdem können wir die übrigen erzeugten Untergruppen ∋△ = {,} und ∋△ = ∋△ = {,,} in Gruppentafeln darstellen: e = to] " - E] + + Löy" : 0 Li = E] Wir sehen, dass die erzeugten Untergruppen wiederum zyklische Gruppen sind. Die erzeugenden Elemente der Gruppe ({,,},+) sind die Elemente und. Die ist erzeugendes Element der Gruppe ({,},+). Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 120 / 150 Gruppenisomorphismus f(x) 1 +(2 3) y() = = + + - (3) : 2 Seien G = (G, ⇐), G↑ = (G↑ , ⇐↑ ) Gruppen mit neutralen Elementen e, e↑. Definition f : G ̸ G↑ heißt Gruppenhomomorphismus, falls die folgenden Bedingungen erfüllt sind: f (e) = e↑ →x,y ↑ G : f (x ⇐ y ) = f (x) ⇐↑ f (y ). Ist f auch bijektiv, so stellt f einen Gruppenisomorphismus dar. Die beiden Gruppen G und G↑ heißen dann isomorph zueinander. G Tutorenteam 2024 (Universität Mannheim) ⑧ Formale Grundlagen der Informatik HWS 2024 121 / 150 Beispiel Gruppenisomorphismen f(z + y) = f(x) f(y) · Beispiel exp : (R, +) ̸ (R+ , ·), x 7̸ ex ist ein Gruppenisomorphismus, denn exp ist bijektiv (Umkehrabbildung: ln(x)) e(R,+) = 0, e(R+ ,·) = 1 ⇓ exp(e(R,+) ) = exp(0) = 1 = e(R+ ,·) f exp(x + y ) = ex+y = ex · ey = exp(x) · exp(y ) Die beiden Gruppen sind folglich isomorph. Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 122 / 150 Permutationen ⑮s 3 ! Definition = 3. 2. 1 Balzn ! Sei X eine endliche Menge. Dann heißt ω : X ̸ X Permutation, falls ω bijektiv ist. Die Menge aller Permutationen in {1,...,n} nennt man Sn. Darstellung Permutationen lassen sich auf unterschiedliche Weise darstellen. Im Folgenden betrachten wir ein Beispiel für S5 : Zuordnungen: 1 7̸ 2, 2 7̸ 3, 3 7̸ 1, 4 7̸ 5, 5 7̸ 4 $1 2 3 4 5% ↳LinkeSeit Zweizeilenform: wi 2 3 1aut + 54 - Zyklendarstellung: (1 2 3)(4u5) Wic Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 123 / 150 Inverse von Permutationen Allgemeine Strategie: Wir betrachten & die untere Zeile der Permutation ' und schauen für 1 2 3 4 5 6 7 jede Zahl, was oben steht. Sei ε = 3 4 7 1 2 5 6 Goe (123 i)... e= id Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 124 / 150 Inverse von Permutationen - Solution vertauschen Reihenfolge sortieren Zeilen -- & ' & ' Sei ε = I 1 2 3 4 5 6 7 3 4 7 1 2 5 6 Dann gilt ε →1 = 1 2 3 4 5 6 7 4 5 1 2 6 7 3 und es gilt ε ⇐ ε →1 = id. Als Probe muss zunächst gelten, dass in der unteren Zeile jede Zahl genau ein mal vorkommt (gilt immer!). Ferner muss zu jeder Spalte von ε eine vertauschte Spalte in ε →1 existieren. 600" =()... G(Öh)) G(y) = = 1 Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 125 / 150 Zyklendarstellung Strategie: Wir beginnen mit der 1 und schauen uns die ’Reise’ von der 1 an. Als nächstes wählen wir ein Element, das bisher nicht besucht wurde und machen dasselbe. & ' Sei ε = G 1 2 3 4 5 6 7 3 4 7 6 1 2 5. Wir sehen 1 ̸ 3 ̸ 7 ̸ 5 ̸ 1. Damit ist die ’Reise’ von 1 beendet. Die 2 wurde noch nicht besucht: 2 ̸ 4 ̸ 6 ̸ 2. Daraus ergibt sich die (disjunkte) Zyklendarstellung ε = (1375)(246) ---- Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 126 / 150 Komposition von Permutationen Satz (Sn , ⇐) ist bezüglich der Komposition ⇐ eine Gruppe. Beispiel & ' & ' ε= & 2 GONGO48 1 2 3 4 5 6 5 4 3 1 6 ω= 1 2 3 4 5 6 6 3 5 1 4 2 & ' 1 2 3 4 5 6 ε⇐ω = = ε(ω(1)) ε(ω(2)) ε(ω(3)) ε(ω(4)) ε(ω(5)) ε(ω(6)) - 28) Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 127 / 150 Komposition von Permutationen Satz (Sn , ⇐) ist bezüglich der Komposition ⇐ eine Gruppe. Beispiel & ' & ' 1 2 3 4 5 6 1 2 3 4 5 6 ε= ω= 2 5 4 3 1 6 6 3 5 1 4 2 & ' 1 2 3 4 5 6 ε⇐ω = ε(ω(1)) ε(ω(2)) ε(ω(3)) ε(ω(4)) ε(ω(5)) ε(ω(6)) & ' 1 2 3 4 5 6 = ε(6) ε(3) ε(5) ε(1) ε(4) ε(2) Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 127 / 150 Komposition von Permutationen Satz (Sn , ⇐) ist bezüglich der Komposition ⇐ eine Gruppe. Beispiel & ' & ' 1 2 3 4 5 6 1 2 3 4 5 6 ε= ω= 2 5 4 3 1 6 6 3 5 1 4 2 & ' 1 2 3 4 5 6 ε⇐ω = ε(ω(1)) ε(ω(2)) ε(ω(3)) ε(ω(4)) ε(ω(5)) ε(ω(6)) & ' 1 2 3 4 5 6 = ε(6) ε(3) ε(5) ε(1) ε(4) ε(2) & ' 1 2 3 4 5 6 = 6 4 1 2 3 5 Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 127 / 150 Ordnung von Permutationen mal Amaz 1 mal TOMOTOxid Definition um -mach 43) Gut Sei ω ↑ Sn eine Permutation. Die Ordnung ordSn (ω) ist die kleinste natürliche Zahl k > 0 für die gilt ω k = id. Satz Ordnung von Permutationen Für alle n ≃ 1 und Permutationen ω ↑ Sn gilt, dass ordSn (ω) = kgV(|Z1 |,|Z2 |,...,|Zt |), wobei ω = Z1 ⇐ Z2 ⇐... ⇐ Zt die eindeutig bestimmte Zyklendarstellung von ω ist und |Zj |, 1 ∀ j ∀ t, die Länge des Zyklus Zj bezeichnet. Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 128 / 150 Ordnung von Permutationen Strategie: Wir bestimmen die Zyklendarstellung der Permutation und bestimmen die Länge der einzelnen Zyklen. Danach berechnen wir das kgV der Längen. & ' Sei ε = Dinit-- 1 2 3 4 5 6 7 3 4 7 6 1 2 5 = (1375)(246). Es gilt ord(ε) = kgV (4,3) = 12 Aufgabe: Finde eine Permutation ε ↑ S8 , für die ord(ε) = 15 gilt. (12345)(6 78) Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 129 / 150 Beispiel zu Permutationen 10 Gefangenen sind von 1-10 durchnummeriert. Die Nummern der Gefangenen wurden in 10 Boxen platziert. In jeder Box befindet sich eine andere Nummer. Die Boxen sind auch von 1-10 durchnummeriert. Die Gefangenen werden nacheinander zu den Boxen geschickt und dürfen maximal 5 Boxen öffnen. Falls es jeder Gefangene schafft, seine Nummer zu finden, werden alle freigelassen. Bei einer zufälligen Wahl ergibt sich die 5 10 Wahrscheinlichkeit 10 = 2110 = 1024 1 , dass jeder seine Nummer findet. Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 130 / 150 Prison Break Die Gefangenen haben aber in FGdI die Permutationen gelernt und entwickeln folgende Strategie. Jeder Gefangene öffnet zuerst die Box mit seiner Nummer und wählt als nächstes die Box mit der Nummer, die er in der vorherigen Box gefunden hat. Mögliche & Belegung der Boxen wäre ' 1 2 3 4 5 6 7 8 9 10 ε= = (1357)(248)(910)(6) 3 4 5 8 7 6 1 2 10 9 wobei der längste Zyklus die Länge 4 hat. Jeder Gefangene findet also nach maximal 4 Versuchen seine Nummer ohne zu raten! Im allgemeinen Fall scheitert diese Strategie nur falls die Permutation mind. ein Zyklus die Länge ≃ 6 hat. Es lässt sich zeigen, dass die Wahrscheinlichkeit, dass alle befreit werden, etwa 30% beträgt, was deutlich besser ist als zufälliges Ziehen! Quelle: http://www.eurocg.org/tizian.cs.uni- bonn.de/Lehre/Seminare/PSAchilles08/Ausarbeitungen/Gefangene.pdf Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 131 / 150  Endliche Automaten Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 132 / 150 Alphabet, Wort, Sprache E Definition (Alphabet) Ein Alphabet ! ist eine endliche Menge von Symbolen. Definition (Wörter und Sprachen) Für alle natürlichen Zahlen n ≃ 1 bezeichnen wir n-Tupel x = (x1... xn ) aus !n als Worte der Länge |x| = n über !. Mit ϑ bezeichnen wir das leere Wort der Länge 0. ( n Die Menge !↓ = {ϑ} ▽ ↔ n=1 ! wird als Menge der Wörter über ! bezeichnet. Teilmengen L ↙ !↓ heißen (formale) Sprachen über dem Alphabet !. Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 133 / 150 Operationen auf Sprachen Definition (Operationen auf Sprachen) Für zwei Sprachen L1 und L2 sind folgende Operationen definiert: Komplement: L = !↓ \ L = {w | w ↑ !↓ ⇑ w ↓↑ L} Vereinigung: L1 ▽ L2 = {w | w ↑ L1 ∃ w ↑ L2 } Durchschnitt: L1 ¬ L2 = {w | w ↑ L1 ⇑ w ↑ L2 } Konkatenation: ( p-0 L L1 · L2 = {uv | u ↑ L1 ⇑ v ↑ L2 } n 0 , Kleene-Stern: L↓ = ↔ n=0 L , wobei L = {ϑ} Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 134 / 150 DFA - deterministic finite automaton Definition Ein deterministischer endlicher Automat A = (Q,q0 ,F , ϖ) über einem endlichen Alphabet ! ist definiert durch: eine endliche Zustandsmenge Q einen Anfangszustand q0 ↑ Q O eine Menge akzeptierender Zustände F ↙ Q und eine Zustandsüberführungsfunktion ϖ : Q ∅ ! ̸ Q Of gonze-a 0,1 0,1 ! = {0,1} 000 Q = {q0 , q1 , q2 } F = {q2 } 0 ↗ ϖ = Pfeile start q0 q1 q2 Tutorenteam 2024 (Universität Mannheim) 1 Formale Grundlagen der Informatik HWS 2024 135 / 150 Reguläre Sprache Definition Eine Sprache L ℜ !↓ heißt regulär, wenn es einen DFA A über ! gibt, der L berechnet, d.h. für den L(A) = L gilt. Lemma 11.8 Jede endliche Sprache ist regulär. Beispiel Die Sprache {ϑ, 11, 1111, 111111,...} ist regulär, da sie durch folgenden DFA berechnet 0,1 1 0 start q0 q1 q2 1 wird: 0 Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 136 / 150 Präfixsprache Seien L ↙ !↓ eine Sprache, ! ein endl. Alphabet und x ↑ !↓ ein Wort. Definition Die Präfixsprache Lx ↙ !↓ von L ist definiert als Lx = {y ↑ !↓ | xy ↑ L}. Der Index von L ist definiert als ind(L) = |{Lx | x ↑ !↓ }| (Anzahl der Präfixsprachen bzgl. L) Beispiel L beinhalte alle deutschen Wörter, ! alle deutschen Buchstaben. Lku = {chen, gel, bieren, nst, h, mulativ ,...} Lxo = ′ Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 137 / 150 Nerode-Relation Seien L ↙ !↓ eine Sprache über einem endlichen Alphabet ! und x, x ↑ ↑ !↓ Wörter. Definition (Nerode-Äquivalenz) x, x ↑ heißen Nerode-äquivalent bezüglich L (x ⇒L x ↑ ), wenn Lx = Lx ↑ Beispiel L := {0i 1j | i,j ↑ N0 }, wobei 00 = 10 = ϑ 0 ⇒L 00, da L0 = L00 = L. :Exo13 v Zur Erinnerung: L = L = {ϑ, 0, 00, 000,...} 001 ⇒L 01111, da L001 = L01111 = {1j | j ↑ N}. Ve - - - 110 ⇒L 010, da L110 = L010 = ′. ind(L) = 3 = Anzahl Äquivalenzklassen bzgl. ⇒L - Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 138 / 150 Nerode-Automat Ziel: Konstruktion eines minimalen DFAs zu einer regulären Sprache L Satz Eine Sprache L ist regulär ℑ ind(L) < ∞ L regulär ⇓ ind(L) ist min. Anz. an Zuständen eines DFA für L. Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 139 / 150 NFA - nondeterministic finite automaton Definition M = (Q, q0 , F , ϖ) heißt NFA über !, falls... ! endliches Eingabealphabet Q endliche Zustandsmenge Bei DFAs : 8: ExQ-7Q q0 ↑ Q Anfangszustand F ↙ Q Menge akzeptierender Zustände ϖ : ! ∅ Q ̸ P(Q) Zustandsüberführungsfunktion 0,1 0,1 1 1 start q0 q1 q2 Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 140 / 150 Simulation von NFAs durch DFAs Satz Jeder NFA N = (Q, q0 , F , ϖ) über ! kann durch einen DFA A mit höchstens 2|Q| Zuständen simuliert werden. Potenzmengenkonstruktion Grundidee 1 Starte im Startzustand des NFA. 2 Bestimme für jedes Zeichen des Alphabets, in welche Zustände (Menge von Zuständen!) der NFA übergehen kann. 3 Bestimme für jede der im vorherigen Schritt erzeugte Zustandsmengen und jedes Zeichen des Alphabets, in welche (bereits erzeugte oder neue) Zustandsmenge der NFA übergehen kann. 4 Wiederhole das, bis alle Zustandsübergänge gefunden wurden und keine neuen Zustandsmengen mehr erzeugt werden. Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 141 / 150  in M ⑳ X ⑭ M 9 O Ey03 3003 39413 390 413 3903 E90 , 91 423 I , , 540 , 401423390 923 91 1 423 , 490 , (90191 923 9+ 1423 , T E  Reguläre Ausdrücke Tutorenteam 2024 (Universität Mannheim) Formale Grundlagen der Informatik HWS 2024 142 / 150 Reguläre Ausdrücke Reguläre Ausdrücke beschreiben eine reguläre Sprache. Man verknüpft dabei Wörter mit den Operatoren... Nicht 0* - beliebig oft 0 in wie Java !! 0 · 1 - 01 0 + 1 - entweder 0 oder 1 0 or 1 Beispiel