Diskrete Mathematik: Übungsaufgaben und Prüfungsfragen

Die Mathematik der Informatik und jedes Beweises: Aussagenlogik und Quantoren, Mengen, Relationen und Funktionen, Graphen mit kürzesten Wegen und aufspannenden Bäumen sowie Zahlentheorie bis RSA. In Prüfungen sind exakte Antworten gefragt, daher zählen eine sorgfältige Tabelle oder Skizze mehr als ein Taschenrechner.

Diesen Kurs kostenlos übenDiesen Kurs übenProbeklausur schreibenJeden Tag 5 kostenlose Aufgaben. Keine Kreditkarte nötig.

Lernpaket (PDF)Formelsammlungen, Lösungsschritte und Übungsaufgaben mit vollständigen Lösungen, druckfertig.

Themen in diesem Kurs

  1. Aussagenlogik & BeweiseWahrheitstafeln · Äquivalenzen und Beweismethoden · Quantoren und ArgumenteRechenaufgaben
  2. Mengen, Relationen & FunktionenVenn-Diagramme und Teilmengen · Inklusion–Exklusion und Relationen · Funktionen und AbzählenRechenaufgaben
  3. GraphentheorieGrade und Kanten · Euler-Wege und Bäume · kürzeste Wege und aufspannende BäumeRechenaufgaben
  4. Zahlentheorie & modulare ArithmetikggT und Reste · Inverse und Kongruenzen · modulare Potenzen und RSARechenaufgaben

Prüfungstipps für Diskrete Mathematik

  • Schreibe die Wahrheitstafel oder das Venn-Diagramm aus: Die meisten Fehler entstehen, wenn man eine Zeile oder einen Bereich überspringt.
  • Um eine Behauptung zu widerlegen, genügt ein Gegenbeispiel; um sie zu beweisen, musst du alle Fälle prüfen oder allgemein argumentieren.
  • Reduziere in der modularen Arithmetik nach jedem Schritt und halte die Reste zwischen 0 und n − 1.

Beispielaufgaben

Aussagenlogik & BeweiseLeicht
pq¬(p ∨ q) → q11100100

Genau eine Zeile der Wahrheitstafel macht ¬(p ∨ q) → q falsch. Klicke diese Zeile an.

¬(p ∨ q) → q
  1. 1p = 1, q = 1
  2. 2p = 1, q = 0
  3. 3p = 0, q = 1
  4. 4p = 0, q = 0
Tipps anzeigen
  1. a → b ist nur 0, wenn a = 1 und b = 0. ¬a kehrt den Wert um. a ∨ b ist nur 0, wenn beide 0 sind.
  2. Bestimme zuerst den Hauptjunktor: Wie müssen seine beiden Seiten aussehen, damit die ganze Formel 0 ist?
  3. Gib jedem Teil eine eigene Spalte: p ∨ q; ¬(p ∨ q); ¬(p ∨ q) → q.
Antwort und Erklärung anzeigen

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: p ∨ q = 1, ¬(p ∨ q) = 0, ¬(p ∨ q) → q = 1
p = 1, q = 0: p ∨ q = 1, ¬(p ∨ q) = 0, ¬(p ∨ q) → q = 1
p = 0, q = 1: p ∨ q = 1, ¬(p ∨ q) = 0, ¬(p ∨ q) → q = 1
p = 0, q = 0: p ∨ q = 0, ¬(p ∨ q) = 1, ¬(p ∨ q) → q = 0

Die Zeile

p = 0, q = 0 → ¬(p ∨ q) → q = 0

Antwort

p = 0, q = 0
Mengen, Relationen & FunktionenMittel
UMPC

Von 53 Studierenden im ersten Jahr haben 35 Mathematik (M), 28 Physik (P) und 29 Chemie (C) bestanden. 20 haben M und P bestanden, 18 M und C, 10 P und C, und 6 haben alle drei bestanden. Wie viele liegen in keiner der drei Mengen?

|U| = 53

Gesucht: |(M ∪ P ∪ C)′|

Tipps anzeigen
  1. Fülle das Venn-Diagramm von der Mitte nach außen: zuerst alle drei, dann die Paare, dann die einzelnen Mengen.
  2. Nur M und P (nicht C): 20 − 6 = 14. Nur M: 35 − 14 − 12 − 6 = 3.
  3. Mindestens eine Menge: 35 + 28 + 29 − 20 − 18 − 10 + 6 = 50.
Antwort und Schritt-für-Schritt-Lösung anzeigen

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

Mitte und Paare

M ∩ P ∩ C: 6
M ∩ P nur: 20 − 6 = 14
M ∩ C nur: 18 − 6 = 12
P ∩ C nur: 10 − 6 = 4

Einzelne Mengen

M nur: 35 − 14 − 12 − 6 = 3
P nur: 28 − 14 − 4 − 6 = 4
C nur: 29 − 12 − 4 − 6 = 7

Antwort

|M ∪ P ∪ C| = 50
|(M ∪ P ∪ C)′| = 53 − 50 = 3

Antwort

|(M ∪ P ∪ C)′| = 3

So funktioniert das Üben

  • „Diesen Kurs üben“ mischt Aufgaben aus allen Themen des Kurses, wie in einer echten Prüfung.
  • Jede Aufgabe hat neue Werte, so lernst du den Lösungsweg statt einer Antwort.
  • Du hängst fest? Öffne zuerst einen kleinen Tipp und die vollständige Erklärung erst, wenn du sie brauchst.
  • Probeklausuren haben ein Zeitlimit und keine Tipps, und am Ende bekommst du deine Punktzahl und eine vollständige Auswertung.

Verwandte Kurse

Grundlagen der InformatikAlgorithmen und DatenstrukturenAnalysis 1Einführung in die StatistikHöhere Mathematik für IngenieureStatistik 2: Schließende StatistikDifferentialgleichungenIngenieurmathematik 2
Diesen Kurs kostenlos übenDiesen Kurs übenProbeklausur schreibenJeden Tag 5 kostenlose Aufgaben. Keine Kreditkarte nötig.