Diskrete Mathematik: Lernpaket

Formelsammlungen, die wichtigsten Lösungsschritte zu jedem Thema und 8 Übungsaufgaben, mit vollständigen Lösungen am Ende.

Neue Aufgaben Zurück zum Kurs

Wähle im Druckfenster „Als PDF speichern“, um eine Kopie auf deinem Gerät zu behalten.

1Formeln und Methoden

Aussagenlogik & Beweise

Zeilen einer Wahrheitstafel: 2ⁿ
Implikation: p → q ≡ ¬p ∨ q ≡ ¬q → ¬p
Negierte Implikation: ¬(p → q) ≡ p ∧ ¬q
Äquivalenz (Bikonditional): p ↔ q ≡ (p → q) ∧ (q → p)
De Morgan: ¬(p ∧ q) ≡ ¬p ∨ ¬q, ¬(p ∨ q) ≡ ¬p ∧ ¬q
Distributivgesetze: p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r), p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
Negierte Quantoren: ¬∀x P(x) ≡ ∃x ¬P(x), ¬∃x P(x) ≡ ∀x ¬P(x)
Modus ponens, Modus tollens: p → q, p ⊢ q; p → q, ¬q ⊢ ¬p

Methode

Zähle die verschiedenen Variablen: Die Wahrheitstafel hat 2ⁿ Zeilen und beginnt mit lauter Einsen.
Gib jeder Teilformel eine eigene Spalte und fülle die Spalten von innen nach außen.
Wende die Regel jedes Junktors an: → ist nur bei 1 → 0 gleich 0, ↔ ist 1, wenn beide Seiten übereinstimmen.
Vergleiche bei Äquivalenzen die letzten Spalten Zeile für Zeile; schau bei einem Argument nur auf die Zeilen, in denen alle Prämissen 1 sind.
Um eine quantifizierte Aussage zu negieren, ziehe ¬ nach innen, vertausche ∀ und ∃ und negiere die innere Formel.

Mengen, Relationen & Funktionen

Zwei Mengen: |A ∪ B| = |A| + |B| − |A ∩ B|
Drei Mengen: |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|
Differenz und Komplement: A − B = A ∩ B′, |A′| = |U| − |A|
Potenzmenge und Produkt: |𝒫(A)| = 2^|A|, |A × B| = |A|·|B|
Teilmengen der Größe k: C(n, k) = n!/(k!(n − k)!)
Funktionen A → B: nᵐ; injective n!/(n − m)!; surjective Σ (−1)ᵏ C(n, k)(n − k)ᵐ
Relationen auf n Elementen: 2^n²; reflexive 2^{n² − n}; symmetric 2^n(n+1)/2
Verkettung: (g ∘ f)(x) = g(f(x))

Methode

Zeichne ein Venn-Diagramm und entscheide Bereich für Bereich, was zum Mengenausdruck gehört.
Fülle bei Zählaufgaben die Bereiche von der Mitte nach außen: erst alle Mengen, dann Paare, dann einzelne Mengen, dann das Äußere.
Nutze das Inklusions-Exklusions-Prinzip als Kontrolle: |A ∪ B| = |A| + |B| − |A ∩ B|.
Prüfe bei einer Relation jede Eigenschaft an jedem Paar und gib ein Gegenbeispiel an, wenn sie nicht gilt.
Zähle bei einer Funktion die Pfeile, die bei jedem Element von B ankommen: höchstens einer heißt injektiv, mindestens einer surjektiv.

Graphentheorie

Handschlaglemma: Σ deg(v) = 2|E|
Vollständige Graphen: |E(K_n)| = n(n − 1)/2, |E(K_m,n)| = m·n
Regulärer Graph: |E| = n·k/2
Baum und Wald: |E| = n − 1, |E| = n − c
Blätter eines Baums: L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
Euler: Kreis: alle Grade gerade; Weg: genau 2 ungerade Grade
Hamilton-Kreise in K_n: (n − 1)!/2
Dijkstra-Aktualisierung: d(v) = min(d(v), d(u) + w(u, v))
Wege der Länge L: (Mᴸ)_ij

Methode

Schreibe den Grad jedes Knotens auf; die Grade summieren sich zum Doppelten der Kantenzahl.
Prüfe bei Euler-Aufgaben, ob der Graph zusammenhängend ist, und zähle die Knoten mit ungeradem Grad.
Verwende bei Bäumen n − 1 Kanten und das Handschlaglemma.
Führe bei Dijkstra eine Tabelle der vorläufigen Abstände und schließe in jeder Runde den kleinsten noch offenen Knoten ab.
Sortiere für einen minimalen aufspannenden Baum die Kanten nach Gewicht und überspringe jede Kante, die einen Kreis schließt (Kruskal), oder lass einen Baum von einem Startknoten aus wachsen (Prim).

Zahlentheorie & modulare Arithmetik

Division mit Rest: a = q·n + r, 0 ≤ r < n
Euklid: gcd(a, b) = gcd(b, a mod b)
Kleinstes gemeinsames Vielfaches: lcm(a, b) = a·b/gcd(a, b)
Inverse: a·a⁻¹ ≡ 1 (mod n), gcd(a, n) = 1
Lineare Kongruenz: a·x ≡ b → x ≡ a⁻¹·b (mod n)
Eulersche φ-Funktion: φ(n) = n·∏(1 − 1/p), φ(pᵏ) = pᵏ − pᵏ⁻¹
Fermat: aᵖ⁻¹ ≡ 1 (mod p)
RSA: n = pq, φ = (p − 1)(q − 1), d = e⁻¹ mod φ, c = mᵉ mod n, m = cᵈ mod n

Methode

Reduziere zuerst jede Zahl modulo n; die Reste liegen zwischen 0 und n − 1.
Teile für einen ggT wiederholt mit dem euklidischen Algorithmus; der letzte Rest ungleich null ist der ggT.
Führe für ein Inverses den erweiterten Algorithmus aus und behalte den Koeffizienten von a; addiere n, falls er negativ ist.
Löse a·x ≡ b, indem du mit a⁻¹ multiplizierst; kombiniere zwei Kongruenzen, indem du x = r₁ + m₁k schreibst.
Schreibe bei Potenzen den Exponenten binär und quadriere wiederholt; bei RSA gilt d = e⁻¹ mod φ(n) mit φ(n) = (p − 1)(q − 1).

2Übungsaufgaben

1.Aussagenlogik & BeweiseMittel

In wie vielen der 8 Zeilen ihrer Wahrheitstafel ist (q ∧ (r ∨ p)) ∨ (p ∨ ¬(q → ¬r)) wahr? Nenne diese Zahl N.

(q ∧ (r ∨ p)) ∨ (p ∨ ¬(q → ¬r))

N =

2.Aussagenlogik & BeweiseSchwer

Wie viele der 16 Zeilen der Wahrheitstafel machen (¬s → (p ∨ q)) → (q ∨ (r ↔ ¬s)) wahr? Nenne diese Zahl N.

(¬s → (p ∨ q)) → (q ∨ (r ↔ ¬s))

N =

3.Mengen, Relationen & FunktionenMittel

Genau ein Bereich des Venn-Diagramms ist die Menge (B ∩ A) ∩ (A − C). Klicke seine Nummer an.

(B ∩ A) ∩ (A − C)

1Bereich 1
2Bereich 2
3Bereich 3
4Bereich 4
5Bereich 5
6Bereich 6
7Bereich 7
8Bereich 8

4.Mengen, Relationen & FunktionenSchwer

Eine Äquivalenzrelation R auf {1, …, 6} hat die Klassen {2}, {1, 4, 6}, {3, 5}. Wie viele geordnete Paare enthält R? Nenne die Zahl |R|.

{2}{1, 4, 6}{3, 5}

|R| =

5.GraphentheorieMittel

Wie viele verschiedene Hamilton-Kreise H hat der vollständige Graph K₄? Kreise, die sich nur im Startknoten oder in der Richtung unterscheiden, zählen als gleich.

K₄

H =

6.GraphentheorieSchwer

Der Dijkstra-Algorithmus läuft von A aus. Klicke den Knoten an, der in Runde 5 abgeschlossen (endgültig gemacht) wird; A selbst ist Runde 1.

Start: ARunde 5

7.Zahlentheorie & modulare ArithmetikMittel

Bestimme das Inverse von 34 modulo 59: die Zahl x mit 0 < x < 59 und 34·x ≡ 1 (mod 59).

a = 34n = 59

34⁻¹ mod 59 =

8.Zahlentheorie & modulare ArithmetikSchwer

Wie viele Lösungen N hat 28x ≡ 36 (mod 58) in {0, 1, …, 57}?

28x ≡ 36 (mod 58)

N =

3Lösungen

1.Aussagenlogik & Beweise

Antwort: N = 5

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.

Wahrheitstafel Zeile für Zeile

p = 1, q = 1, r = 1: r ∨ p = 1, q ∧ (r ∨ p) = 1, ¬r = 0, q → ¬r = 0, ¬(q → ¬r) = 1, p ∨ ¬(q → ¬r) = 1, (q ∧ (r ∨ p)) ∨ (p ∨ ¬(q → ¬r)) = 1

p = 1, q = 1, r = 0: r ∨ p = 1, q ∧ (r ∨ p) = 1, ¬r = 1, q → ¬r = 1, ¬(q → ¬r) = 0, p ∨ ¬(q → ¬r) = 1, (q ∧ (r ∨ p)) ∨ (p ∨ ¬(q → ¬r)) = 1

p = 1, q = 0, r = 1: r ∨ p = 1, q ∧ (r ∨ p) = 0, ¬r = 0, q → ¬r = 1, ¬(q → ¬r) = 0, p ∨ ¬(q → ¬r) = 1, (q ∧ (r ∨ p)) ∨ (p ∨ ¬(q → ¬r)) = 1

p = 1, q = 0, r = 0: r ∨ p = 1, q ∧ (r ∨ p) = 0, ¬r = 1, q → ¬r = 1, ¬(q → ¬r) = 0, p ∨ ¬(q → ¬r) = 1, (q ∧ (r ∨ p)) ∨ (p ∨ ¬(q → ¬r)) = 1

p = 0, q = 1, r = 1: r ∨ p = 1, q ∧ (r ∨ p) = 1, ¬r = 0, q → ¬r = 0, ¬(q → ¬r) = 1, p ∨ ¬(q → ¬r) = 1, (q ∧ (r ∨ p)) ∨ (p ∨ ¬(q → ¬r)) = 1

p = 0, q = 1, r = 0: r ∨ p = 0, q ∧ (r ∨ p) = 0, ¬r = 1, q → ¬r = 1, ¬(q → ¬r) = 0, p ∨ ¬(q → ¬r) = 0, (q ∧ (r ∨ p)) ∨ (p ∨ ¬(q → ¬r)) = 0

p = 0, q = 0, r = 1: r ∨ p = 1, q ∧ (r ∨ p) = 0, ¬r = 0, q → ¬r = 1, ¬(q → ¬r) = 0, p ∨ ¬(q → ¬r) = 0, (q ∧ (r ∨ p)) ∨ (p ∨ ¬(q → ¬r)) = 0

p = 0, q = 0, r = 0: r ∨ p = 0, q ∧ (r ∨ p) = 0, ¬r = 1, q → ¬r = 1, ¬(q → ¬r) = 0, p ∨ ¬(q → ¬r) = 0, (q ∧ (r ∨ p)) ∨ (p ∨ ¬(q → ¬r)) = 0

Zähle die Zeilen mit dem Wert 1

(q ∧ (r ∨ p)) ∨ (p ∨ ¬(q → ¬r)): 1, 1, 1, 1, 1, 0, 0, 0

N = 5

Antwort

N = 5

2.Aussagenlogik & Beweise

Antwort: N = 13

Spalten

¬s; p ∨ q; ¬s → (p ∨ q); r ↔ ¬s; q ∨ (r ↔ ¬s); (¬s → (p ∨ q)) → (q ∨ (r ↔ ¬s))

Nach p aufteilen

p = 1: 6

p = 0: 7

N = 6 + 7 = 13

Antwort

N = 13

3.Mengen, Relationen & Funktionen

Antwort: Bereich 1

Mengen und Venn-Diagramme: A ∪ B enthält die Elemente in A oder B (oder beiden), A ∩ B die Elemente in beiden, A − B die Elemente von A, die nicht in B liegen, und das Komplement A′ alles in U, was nicht in A liegt. In einem Venn-Diagramm ist jeder Mengenausdruck eine Vereinigung von Bereichen, zähle ihn also Bereich für Bereich. Inklusion–Exklusion: |A ∪ B| = |A| + |B| − |A ∩ B| und |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|.

Innerhalb oder außerhalb jeder Menge

A ∩ B ∩ C′

Der Bereich

Bereich 1

Antwort

Bereich 1

4.Mengen, Relationen & Funktionen

Antwort: |R| = 14

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.

Paare je Klasse

|R| = 1² + 3² + 2² = 14

Antwort

|R| = 14

5.Graphentheorie

Antwort: H = 3

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.

Zählen

H = (4 − 1)!/2 = 6/2 = 3

Antwort

H = 3

6.Graphentheorie

Antwort: D

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.

Dijkstra Runde für Runde

1. A (0): B: 11, C: 13

2. B (11): C: 12, D: 14, E: 24

3. C (12): E: 13

4. E (13)

5. D (14): F: 19

6. F (19)

Runde 5

Antwort

7.Zahlentheorie & modulare Arithmetik

Antwort: 34⁻¹ mod 59 = 33

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).

Erweiterter euklidischer Algorithmus

Jeder Rest r wird als r ≡ t·34 (mod 59) geschrieben.

r = 59, t = 0

r = 34, q = 1, t = 1

r = 25, q = 1, t = −1

r = 9, q = 2, t = 2

r = 7, q = 1, t = −5

r = 2, q = 3, t = 7

r = 1, q = 2, t = −26

Inverse

1 ≡ −26·34 (mod 59)

x = 33

Probe: 34·33 = 1122 = 19·59 + 1

Antwort

34⁻¹ mod 59 = 33

8.Zahlentheorie & modulare Arithmetik

Antwort: N = 2

Durch den ggT teilen

gcd(28, 58) = 2

14x ≡ 18 (mod 29)

Die reduzierte Kongruenz lösen

14⁻¹ ≡ 27 (mod 29) → x ≡ 22 (mod 29)

Lösungen modulo 58

x ∈ {22, 51}

N = 2

Antwort

N = 2

ExamProblems · examproblems.com/courses/discrete-mathematics