Diskrete Mathematik: Lernpaket

Wahrheitstafeln: Eine Formel mit n verschiedenen Variablen hat 2ⁿ Zeilen, eine für jede Kombination von Wahrheitswerten (1 = wahr, 0 = falsch). Arbeite von innen nach außen und gib jeder Teilformel eine eigene Spalte. ¬a kehrt den Wert um; a ∧ b ist nur 1, wenn beide 1 sind; a ∨ b ist nur 0, wenn beide 0 sind; a → b ist nur 0, wenn a = 1 und b = 0; a ↔ b ist 1, wenn beide Seiten gleich sind.

Quantoren und Argumente: ¬∀x P(x) ≡ ∃x ¬P(x) und ¬∃x P(x) ≡ ∀x ¬P(x). Ziehe eine Negation nach innen, vertausche jeden Quantor, den sie passiert, und negiere die innere Formel mit den aussagenlogischen Gesetzen, etwa ¬(a → b) ≡ a ∧ ¬b. Ein Argument ist gültig, wenn die Konklusion in jeder Zeile 1 ist, in der alle Prämissen 1 sind. Eine einzige Zeile mit wahren Prämissen und falscher Konklusion ist ein Gegenbeispiel und zeigt, dass das Argument ungültig ist.

Relationen: Eine Relation R auf einer Menge X ist eine Menge geordneter Paare (x, y). R ist reflexiv, wenn (x, x) ∈ R für jedes x in X; symmetrisch, wenn zu (x, y) ∈ R immer (y, x) ∈ R gehört; antisymmetrisch, wenn (x, y) und (y, x) nur dann beide in R liegen, wenn x = y; und transitiv, wenn (x, y) und (y, z) in R (x, z) ∈ R erzwingen. Eine Äquivalenzrelation ist reflexiv, symmetrisch und transitiv und zerlegt X in disjunkte Klassen.

Funktionen und Abzählen: Eine Funktion f: A → B ordnet jedem Element von A genau ein Bild in B zu. f ist injektiv (eineindeutig), wenn verschiedene Elemente verschiedene Bilder haben, surjektiv (auf), wenn jedes Element von B ein Bild ist, und bijektiv, wenn beides gilt. Mit |A| = m und |B| = n gibt es nᵐ Funktionen, n!/(n − m)! injektive (m ≤ n) und nach Inklusion–Exklusion Σ (−1)ᵏ·C(n, k)·(n − k)ᵐ surjektive. |𝒫(A)| = 2ᵐ und |A × B| = m·n.

Euler, Hamilton und Bäume: Ein zusammenhängender Graph hat einen Euler-Kreis (jede Kante einmal, zurück zum Start), wenn jeder Knoten geraden Grad hat, und einen Euler-Weg, der kein Kreis ist, wenn genau zwei Knoten ungeraden Grad haben; der Weg verläuft dann von einem ungeraden Knoten zum anderen. Ein Hamilton-Kreis besucht jeden Knoten einmal; K_n hat (n − 1)!/2 davon. Ein Baum mit n Knoten hat n − 1 Kanten, und ein zusammenhängender Graph mit m Kanten behält einen aufspannenden Baum, wenn man m − n + 1 Kanten entfernt.

Kürzeste Wege und aufspannende Bäume: Der Dijkstra-Algorithmus schließt in jeder Runde einen Knoten ab: den offenen Knoten mit dem kleinsten vorläufigen Abstand. Sein Abstand ist dann endgültig, und jeder Nachbar v erhält d(v) = min(d(v), d(u) + w(u, v)). Der Kruskal-Algorithmus baut einen minimalen aufspannenden Baum auf, indem er die Kanten von leicht nach schwer nimmt und jede Kante überspringt, die einen Kreis schließen würde; der Prim-Algorithmus lässt einen Baum von einem Startknoten aus wachsen, indem er immer die leichteste Kante hinzufügt, die aus ihm herausführt. Ein aufspannender Baum mit n Knoten hat n − 1 Kanten.

Inverse und Kongruenzen: a hat genau dann ein Inverses modulo n, wenn ggT(a, n) = 1. Der erweiterte euklidische Algorithmus schreibt 1 = s·n + t·a, und dann ist a⁻¹ ≡ t (mod n). Eine Kongruenz a·x ≡ b (mod n) mit ggT(a, n) = 1 hat die Lösung x ≡ a⁻¹·b. Zwei Kongruenzen x ≡ r₁ (mod m₁) und x ≡ r₂ (mod m₂) mit teilerfremden Moduln haben eine Lösung modulo m₁·m₂ (chinesischer Restsatz). Eulers φ(n) zählt die Zahlen von 1 bis n, die zu n teilerfremd sind: φ(n) = n·∏(1 − 1/p).

Modulare Potenzen und RSA: Berechne aᵏ mod n durch wiederholtes Quadrieren: Schreibe k binär, quadriere, reduziere nach jedem Schritt und multipliziere die Potenzen, deren Bit 1 ist. Fermat: aᵖ⁻¹ ≡ 1 (mod p) für eine Primzahl p, die a nicht teilt, der Exponent lässt sich also modulo p − 1 reduzieren. RSA: Wähle Primzahlen p und q, n = p·q und φ(n) = (p − 1)(q − 1); der öffentliche Exponent e ist teilerfremd zu φ(n), und der private Exponent ist d = e⁻¹ mod φ(n). Verschlüssele mit c = mᵉ mod n und entschlüssele mit m = cᵈ mod n.