Links und Funktionen
Sprachumschaltung
Navigationspfad
Sie sind hier: Startseite / Lehre / SS 2013 / Logik und Diskrete Strukturen
Inhaltsbereich

Logik und Diskrete Strukturen

Vorlesung, 3-std., Di 12-14, Mi 8-10, Hofmann; Übungen 2-std., Jost
Inhalt | Organisation | Zeit und Ort | Planung | Übungen | Klausur | Literatur | Weitere Informationen

Bitte beachten Sie: Aktuelle Hinweise & Termine zur Veranstaltung finden Sie am rechten Rand dieser Vorlesungshomepage. Sie können dazu auch einen RSS-Feed abonnieren.

Wenn Sie jetzt am rechten Rand keine Termine & Nachrichten sehen, dann ändern Sie bitte Ihre Spracheinstellung mit einem Klick auf "Deutsch".

Inhalt

Das Modul 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, Gruppen und Körper, Aussagenlogik und Prädikatenlogik, Sequenzenkalkül und Resolution, Gödels Unvollständigkeitssatz.

Organisation

Zur Teilnahme ist eine Anmeldung bei UniworX zwingend erforderlich (ab 4. März 2013).

    Zeit und Ort

    VeranstaltungZeitOrtBeginn
    Vorlesung Di, 12 - 14 Uhr Hörsaal B U101 (Oettingenstr. 67) 16.04.2013
    Vorlesung Mi, 8 - 10 Uhr Hörsaal B U101 (Oettingenstr. 67) 17.04.2013
    Übung Mo, 14 - 16 Uhr Raum A 022 (Hauptgebäude) 22.04.2013
    Übung Mo, 16 - 18 Uhr Raum B 046 (Theresienstr. 39) 22.04.2013
    Übung Mi, 16 - 18 Uhr Raum A 022 (Hauptgebäude) 24.04.2013
    Übung Mi, 18 - 20 Uhr Raum A 022 (Hauptgebäude) 24.04.2013

    Planung

    Da die Vorlesung trotz der gebuchten 4 Semesterwochenstunden nur den Umfang 3+2 hat, entfallen einige Vorlesungstermine. Die Übungen finden dagegen durchgehend statt. Zur Zeit ist für die Vorlesung folgende Planung vorgesehen. Die Angaben der Form (Sx.x.x) im ersten Teil beziehen sich auf das Buch von Steger.  Der zweite Teil richtet sich nach dem Skriptum zur Vorlesung  "Logik fuer Informatiker" im SS2008 http://www2.tcs.ifi.lmu.de/lehre/SS08/Logik/kap1-4.pdf.

    Nr. Datum Thema Hinweise
    1. 16.04. Organisation. Mengen, Relationen  (Wdh. Lin.Alg.)(S0.1,S0.2).
    Es wurden die Übungsaufgaben 3, 5, 6, 7 aus der Vorlesung Lineare Algebra für Informatiker und Statistiker WS2012/13  vorgerechnet. Angaben und Musterlösungen finden sich dort.
    2. 23.04. Wdh. Äquivalenzrelationen, Abbildungen (Ü 10, 12).  Beweise, vollständige Induktion (S0.3)
    3. 24.04. Bsp zur vollst Induktion.
    4. 30.04. Kombinatorik (S1.3.1-1.3.3), Ordnungen und Verbände. (S1.4)
    5. 07.05. Verbände (S1.4) ohne Distributivität. Graphen (S2.1) Definition und Satz 2.1
    6. 08.05. Graphen (S2.2, S2.4, ohne Matching).
    7. 15.05. Wdh. Graphen, planare Graphen, Primzahlen, ggT, kgV,  Euklidischer Algorithmus  (S3.2.2)
    8. 28.05. Modulare Arithmetik, Chinesischer Restesatz. In der Vorlesung wurde konstruktiv durch Induktion ueber k bewiesen, dass stets eine Lsg existiert. Mit dem Argument surj=inj bei gleicher Maechtigkeit wurde daraus die Eindeutigkeit gefolgert (dies analog zum Beweis bei Steger). (S3.2.1, S3.2.3).
    9. 29.05. Polynome (S3.3.1). Gruppen (S5.3.1 1.Teil (Beispiele, aber noch keine Ordnungen)
    10. 18.06. Gruppen: Elementordnungen einschl Korollar 5.56 aber mit einfacherem Beweis (ord(a)=m und ord(b)=n. Falls ggT(m,n)=1, so ist ord(ab)=mn. Ansonsten ist ord(a^ggT(m,n)b)=kgV(m,n). Also existiert stets ein Gruppenelement x mit ord(x)=kgV(m,n). 5.56 folgt unmittelbar. (S5.3.1). Untergruppen (S5.3.2) ohne "Satz von Euler", stattdessen "Satz von Fermat" (S3.2.4). Endliche Koerper: Definitionen und Beispiele (S5.4.1), noch ohne Satz 5.8.4. 
    11. 19.06. Endliche Körper in Auszügen: Die Sätze 5.8.4 (Existenz primitiver Elemente). 5.9.2 (Konstruktion von Körpern mit irreduziblem Polynom) und 5.9.3. (Klassifikation der endlichen Körper) wurde behandelt.
    Die korrigierte Bestimmung eines Inversen zu ax+b in Q[x]/x2-2 findet sich hier.
    12. 25.06. Aussagenlogik: Einführung, Syntax, Semantik informell. Modellierung mit Aussagenlogik. Skript bis Seite 10
    13. 26.06. Semantik mit Belegungen, Äquivalenz, Boole'sche Algebra,  Allgemeingültigkeit, Erfüllbarkeit, KNF. Skript bis Seite 15, aber noch ohne DNF.
    14. 02.07. DNF, Formel aus Wahrheitstafel konstruieren, Sequenzenkalkül zur Haelfte, Demo PVS. Skript bis Seite  21 + Regeln für \/ und /\.
    15. 03.07. Sequenzenkalkül Korrektheit und Vollständigkeit, Resolution. Skript bis Seite 29.  Kompaktheit wurde noch nicht behandelt.
    16. 09.07. Resolution fertig,  Kompaktheit anders als im Skript über Resolution bewiesen. Prädikatenlogik: Motivation, Syntax. Skript bis S. 37
    17. 10.07. Syntax und Semantik der Prädikatenlogik Skript bis S. 41
    18. 16.07. Sequenzenkalkül für die Prädikatenlogik. Beispiele sowohl an Tafel als auch mit PVS. Korrektheit und Vollständigkeit (Beweise nur mündlich grob skizziert. Kommen nicht in der Klausur dran).
    19. 17.07. Pränex-Normalform, Kompaktheit, Satz von Herbrand, Resolution für die Prädikatenlogik

    Hinweis: 

    Da sich im Vergleich zum letzten Jahr einige inhaltliche Änderungen an dieser Veranstaltung ergeben haben, sind die Vorlesungsvideos des letzten Jahres leider nur  eingeschränkt zu empfehlen.

    Übungen

    Das wöchentliche Übungsblatt wird jeweils am Freitag per UniworX zum Download erscheinen. Die Aufgaben sind üblicherweise in Präsenzaufgaben und Hausaufgaben unterteilt. Eine aufmerksame Verfolgung der Vorlesung sollte Ihnen als Vorbereitung für die Präsenzaufgaben ausreichen. Die Präsenzaufgaben sind zum herumprobieren gedacht. Falls bei Präsenzaufgaben mal stecken bleiben sollten, was sicher mal vorkommen wird, so diskutieren Sie das Problem mit Ihren Kommilitonen. Bei hartnäckigen Problemen oder Unklarheiten fragen Sie einfach Ihren Übungsgruppen-Tutor oder Assistenten. Lernen Sie daraus!

    Die Hausaufgaben müssen Sie dagegen alleine bearbeiten, was ohne größere Schwierigkeiten möglich sein sollte. Ihre Lösungen zu den Hausaufgaben müssen Sie üblicherweise innerhalb einer Woche, also bis Montag 8:00h morgens, mit UniworX abgeben. Zur Abgabe der Hausaufgaben ist eine Anmeldung in UniworX bei der entsprechenden Übungsgruppe Vorlesung notwendig. Ungefähr eine Woche nach Ende des Abgabezeitraums sollte Ihre Abgaben korrigiert worden sein; die Korrektur erhalten Sie ebenfalls uber UniworX. Hinweise zum Klausurbonus finden Sie im Abschnitt Klausur.

    Klausur

    Erstklausur

    Die Erstklausur fand am Donnerstag, 25.07.2013 16-19h statt. Die Klausureinsicht dazu fand am 01.08.2013 von 11-12h.

    Nachholklausur

    • Anmeldezeitraum: ab sofort bis spätestens 15.09.2013 per UniworX. Eine Anmeldung ist zur Teilnahme zwingend erforderlich!
    • Termin: Montag, 07.10.2013 16-19h. Die Bearbeitungszeit beträgt 120 Minuten.
    • Ort: Theresienstr. 39 
    • Raumeinteilung: Entsprechend des Anfangsbuchstabens Ihres Nachnamens
      • A-G: B051
      • H-Z: C123

      Hinweise zum Klausurablauf

      • Eine Klausuranmeldung per UniworX ist zur Teilnahme zwingend erforderlich.
      • Jeder Student muss einen gültigen Lichtbildausweis und seinen Studentenausweis mitbringen.
      • Es sind keine Hilfsmittel zugelassen. Am Platz darf sich nur Schreibzeug und eventuell ein paar Nahrungsmittel befinden. Papier wird von uns gestellt und darf nicht mitgebracht werden. Taschen und Jacken müssen vorne an der Tafel abgelegt werden. Sollte jemand ein Telefon, mp3-Player, oder Ähnliches am Platz haben, ist das ein Täuschungsversuch, der dem Prüfungsausschuss gemeldet wird. Sollte ein Telefon klingeln, ist das eine Störung des Prüfungsablaufs und hat den Ausschluss von der weiteren Teilnahme zur Folge.
      • Gehen Sie rechtzeitig vor Beginn gemäß der Raumeinteilung in Ihren zugewiesenen Raum! Die Raumeinteilung finden Sie etwas weiter oben auf dieser Webseite.

      Hausaufgabenklausurbonus

      Die meisten Hausaufgaben sind mit Punkten gekennzeichnet. Mit diesen Punkten kann ein Bonus auf die Klausurnote erzielt werden: Wer die Klausur bestanden, aber noch nicht die volle Punktzahl erzielt hat, kann die Klausurnote durch diesen Bonus verbessern. Der Bonus beeinflusst also nicht, ob man bestanden hat oder durchgefallen ist. Der maximale Klausurbonus wird ungefähr einer Klausuraufgabe entsprechen (ca. 12% der Gesampunktzahl der Klausur). Wer x% der Summe aller Hausaufgabenpunkte erzielt hat, erhält x% der maximalen Klausurbonuspunktzahl. Wer also die Hälfte aller Hausaufgaben richtig bearbeitet, könnte also noch mit einer halben Klausuraufgabe weniger die Bestnote erreichen.
       
      Da die Klausur eine Einzelleistung sein muss, und der Hausaufgabenbonus zur Klausur zählt, sind die Hausaufgaben ausschließlich alleine zu bearbeiten! Falls unser System ein Abschreiben entdeckt, kann Ihnen bereits im ersten Fall der gesamte Klausurbonus gestrichen werden, in schweren Fällen kann es auch zum Nichtbestehen des gesamten Moduls kommen. Weitere Details finden Sie unter www.medien.ifi.lmu.de/lehre/Plagiate-IfI.pdf.
       
      Der Klausurbonus gilt nur für die Erstklausur oder die Wiederholungsklausur. Der Bonus verfällt für alle Wiederholungen. Der Klausurbonus errechnet sich selbstverständlich aus allen Übungsblättern, die Hausuafgaben mit Punkten enthalten.

      Literatur

      • Angelika Steger: Diskrete Strukturen. Band 1: Kombinatorik, Graphentheorie, Algebra.
        2. Auflage, Springer 2007, 978-3-540-46660-4

        In der Studentenbibliothek sowie in der Mathematik-Bibliothek sind einige Exemplare des Buchs vorhanden. Es gibt auch eine Online-Version. Voraussetzung für die Leseberechtigung der Online-Version ist, dass der Zugriff über eine MWN-Verbindung (Münchner Wissenschaftsnetz) erfolgt und passende Browser-Einstellungen konfiguriert sind. Auf den CIP-Rechnern des Instituts für Informatik sind das normalerweise die Standardeinstellungen. Auf dem eigenen Rechner kann man ein VPN-Client-Programm installieren, um auch von außerhalb über eine MWN-Verbindung zugreifen zu können.
      • Martin Hofmann: Vorlesungsskript zur Vorlesung "Logik für Informatiker"

      Weitere Informationen

       

      Artikelaktionen

      Funktionsleiste