Logik und Diskrete Strukturen (LDS, SoSe 2026)

Vorlesung, 3-std., Blanchette; Übungen 2-std., Desharnais-Schäfer, Toth

Inhalt

Die Vorlesung führt in grundlegende mathematische Konzepte zum Umgang mit endlichen oder abzählbaren Strukturen ein sowie in grundlegende Konzepte der Logik. Unter anderem werden behandelt: Mengen, Relationen, Ordnungen, Modulare Arithmetik, Kombinatorik, Gruppen und Körper, Aussagenlogik und Prädikatenlogik, Gentzen-Kalküle und Resolution.

Organisation

• Umfang: 3+2 Semesterwochenstunden

• Vorlesung: Prof. Dr. Jasmin Blanchette

• Übung: Dr. Martin Desharnais-Schäfer, Balazs Toth

Vorlesung

Die Vorlesung wird als Präsenzveranstaltung durchgeführt. Sie findet dienstags von 11:15 Uhr bis 13:45 Uhr im Hörsaal E 120 (Großen Aula) im Hauptgebäude statt, mit bis zu zwei 15-minütigen Pausen.

Das Material zur Vorlesung wird unter Material bereitgestellt.

Übungsbetrieb

Die Übungen werden zu den unter Zeit und Ort angegebenen Terminen durchgeführt. Die Übungen starten am Mittwoch, dem 15.04.2026. Es ist keine Anmeldung zu den Übungsgruppen erforderlich.

An allen gesetzlichen Feiertagen sowie in der Pfingstwoche (25.05.–29.05.2026) finden keine Tutorien statt.

Die Übungsaufgaben werden immer an einem Dienstag über Moodle veröffentlicht, von Mittwoch bis Freitag in den Übungen besprochen, und Sie haben dann bis zum Ende der folgenden Woche Zeit zur Bearbeitung der Hausaufgaben.

Die Übungsgruppe 1 wird hybrid in Präsenz und via Zoom stattfinden:
https://lmu-munich.zoom-x.de/j/66215008328?pwd=uf892fTq9sljVaksQbi786UAJ10vFe.1
Meeting ID: 662 1500 8328
Passcode: 696378

Zeit und Ort

Material

• Folien:
  Kapitel 0: Organisatorisches (auch mit Animationen)
  Kapitel 1: Grundlagen (auch mit Animationen)
  Kapitel 2: Ordnungen und Verbände (auch mit Animationen)
  Kapitel 3: Zahlentheorie und Arithmetik (auch mit Animationen)
  Kapitel 4: Algebra (auch mit Animationen)
  Kapitel 5: Kombinatorik (auch mit Animationen)
  Kapitel 6: Aussagenlogik (auch mit Animationen)
  Kapitel 7: Prädikatenlogik erster Stufe (auch mit Animationen)
  Kapitel 8: Weitere Logiken (auch mit Animationen)

• Übungsblätter und Lösungen:
  Siehe Moodle.

• Klausuren von 2025:
  Reguläre Klausur (Lösungen), Wiederholungsklausur (Lösungen)

• Klausuren von 2024:
  Reguläre Klausur (Lösungen), Wiederholungsklausur (Lösungen)

• Videoaufzeichnungen durch PD Dr. Jan Johannsen aus Pandemiezeiten:

  Die Nutzung dieser Videos erfolgt auf eigene Verantwortung. Der Inhalt der diesjährigen Vorlesung kann von den Inhalten in den vorherigen Jahren abweichen. Insbesondere haben sich einige Notationen geändert. Allein der Inhalt der Präsenzvorlesung ist für die Prüfung verbindlich. Folgende Abweichungen sind bekannt, aber es könnte auch mehr geben:

  In der Vorlesung	In den Videos
  (f ∘ g)(x) = f(g(x))	(g ∘ f)(x) = f(g(x))
  {x | P(x)}	{x ; P(x)}
  Vollständige Induktion hat Basisfall 0	Vollständige Induktion hat Basisfall 1
  Starke Induktion hat keinen Basisfall	Starke Induktion hat einen Basisfall
  Γ ⊢ Δ	Γ ⇒ Δ
  t[x := u]	t[x : u]

  Mengen · Relationen · Funktionen · Beweise · Induktion · Partielle Ordnungen · Verbände · Teilbarkeit · Primzahlen · Euklidischer Algorithmus · Modulare Arithmetik · Kongruenzen · Algebraische Strukturen · Homomorphismen · Halbgruppen und Monoide · Gruppen · Ordnung · Zyklische Gruppen · Untergruppen und Nebenklassen · Ringe · Körper · Polynome · Polynomdivision · Körpererweiterung · Kombinatorik · Schubfachprinzip · Aussagenlogik · Aussagenlogik: Semantik · Negations-Normalform · Disjunktive und Konjunktive Normalform · Sequenzenkalkül · Sequenzenkalkül: Vollständigkeit · Resolution · Tseitin-Expansion · SAT-Solving · Prädikatenlogik: Syntax · Prädikatenlogik: Semantik · Pränex-Normalform · Sequenzenkalkül für die Prädikatenlogik · Sequenzenkalkül für die Prädikatenlogik: Vollständigkeit (nicht klausurrelevant) · Quantifizierte Aussagenlogik · Modallogik · Temporale Logik · Prädikatenlogik zweiter Stufe · Intuitionistische Logik

Chat

Für die Vorlesung gibt es einen Zulip-Chatraum, in dem Sie sowohl organisatorische als auch inhaltliche Fragen stellen können. Bitte verwenden Sie wenn möglich diesen Chatraum, anstatt uns E-Mails zu schreiben, damit Ihre Mitstudierenden auch von den Antworten profitieren können.

Zulip-Server: https://chat.ifi.lmu.de
Stream: TCS-26S-LDS

Literatur

• Angelika Steger: Diskrete Strukturen 1. Kombinatorik, Graphentheorie, Algebra, 2. Auflage, Springer Verlag, 2007
  (Kostenlos als E-Book in der Universitätsbibliothek erhältlich.)

• Ronald L. Graham, Donald E. Knuth und Oren Patashnik: Concrete Mathematics: A Foundation for Computer Science, Pearson Education, 1994

• Uwe Schöning: Logik für Informatiker, 5. Auflage, Spektrum Akademischer Verlag, 2000

Klausuren

Es wird eine reguläre und eine Wiederholungsklausur in diesem Semester geben; beide werden schriftlich sein. Die Klausursprache ist Deutsch; die Antworten dürfen aber entweder auf Deutsch oder Englisch geschrieben werden. Die Bearbeitungszeit beträgt 120 Minuten. Sie benötigen

• Studierendenausweis,
• Ausweisdokument mit Bild (z.B. neuen Studierendenausweis),
• Schreibmaterial (dokumentenechter Stift, weder rot noch grün).

Hilfsmittel sind nicht erlaubt. Auch das Mitführen ausgeschalteter elektronischer Geräte wird als Betrugsversuch gewertet. Die Klausuren werden sich strukturell und inhaltlich an denen von 2025 orientieren (siehe Material), aber wir behalten uns natürlich beliebige Änderungen vor.

Falls Sie einen Nachteilsausgleich in Anspruch nehmen möchten, melden Sie sich bitte mindestens eine Woche im Voraus bei Prof. Dr. Jasmin Blanchette.

Reguläre Klausur

Die reguläre Klausur wird am 22.07.2026 um 15 Uhr in folgenden Räumen stattfinden:

• Großhad. Str. 9, Raum N 00.001
• Butenandtstr. 13, Raum F 0.001 (Buchner)
• Butenandtstr. 13, Raum F 0.002 (Liebig)

Die Zuteilung der Studierenden auf die Räume wird später bekanntgegeben.

Wiederholungsklausur

Das Datum und die Räume der Wiederholungsklausur wird später bekanntgegeben.