Dozent	Jasmin Buck
Semester	zweites Semenster Software Engineering (SEB2)
Umfang	4 SWS Vorlesung
Vorkenntnisse	keine
Prüfung	Leistungsnachweis durch Klausur, 90 Minuten, keine Hilfsmittel.
Termine	Montag 9:45-11:15 und 12:15-13:45 in A210
Beginn	Montag 4.10.
Mail Verteiler

Leistungsnachweis durch 90 minütige Klausur. Es sind keine Hilfsmittel (Taschenrechner, Formelsammlung, usw.) erlaubt. Gegenstand der Klausur ist der Inhalt der Vorlesung, der Inhalt des Skripts (mit Ausnahme des Anhangs) und der Inhalt der Übungen.

Nachfolgend finden Sie eine thematisch sortierte Sammlung von Hausaufgaben und alten Klausuraufgaben.

• Mengenlehre, (Lösungen)
• Potenzmengen, (Lösungen)
• Paare und Kartesische Produkte, (Lösungen)
• Relationen, (Lösungen)
• Äquivalenzrelationen, (Lösungen)
• Umkehrrelationen, (Lösungen)
• Funktionen, (Lösungen)
• Komposition von Funktionen, (Lösungen)
• Surjektiv, Injektiv, Bijektiv, (Lösungen)
• Umkehrfunktion, (Lösungen)
• Abzählbarkeit, (Lösungen)
• Prädikatenlogik, (Lösungen)

Während des Semesters erscheint einmal pro Woche ein Blatt mit Hausaufgaben im Netz.

Für Korrekturen und Verbesserungsvorschläge bin ich sehr dankbar!

• Skript.
• Kurze Zusammenfassung
• Folien zum Halteproblem.

Im wesentlichen hat die Vorlesung zwei Ziele:

• Systematisches logisches Denken lernen.
• Das Denken auf Maschinen übertragen.

Der erste Schritt wird Ihnen wahrscheinlich trivial erscheinen, der zweite unlösbar. Tatsächlich wird aber der schwierigere Teil der Vorlesung im ersten Schritt liegen. Wenn wir in der Lage sind, unsere Gedanken exakt zu formulieren und eine gewisse Systematik in unsere Schlussfolgerungen zu bringen, ist es nicht mehr schwer, diese in Form von Algorithmen auf den Rechner zu übertragen.

Die Realität ist sehr komplex - um eine radikale Vereinfachung kommen wir daher nicht herum. Diese Vereinfachung ist die Mathematik: Es gibt hier nur wahr und falsch und jeder Begriff ist unmissverständlich und exakt definiert - in der Regel sogar mit wenigen Worten. Wir beginnen also damit, die Realität so gut es eben geht mit mathematischen Begriffen zu beschreiben. Die wichtigsten Begriffe sind wie folgt:

• Mengen. Unsere Datenstrukturen. Jedes Objekt, mit dem wir uns beschäftigen werden, ist letztlich eine Menge.
• Relationen. Durch Relationen werden Eigenschaften von Objekten sowie Beziehungen zwischen Objekten beschrieben.
• Funktionen. Ein absolutes "must have". Ist Ihnen schon mal aufgefallen, dass es unendlich viele (reale und imaginäre) Dinge gibt, aber nur endlich viele Worte? Eine Sprache mit unendlich vielen Worten wäre schlicht nicht erlernbar. Der Ausweg sind Funktionen. Die Zahl 3.14159265... hat aufgrund ihrer Bedeutung den Namen Pi erhalten. Hierauf kann sie zurecht stolz sein, denn für die nicht weniger wichtige Zahl 2 Pi hat man sich kein neues Wort ausgedacht, sondern benutzt die Multiplikationsfunktion. Ähnlich ist es z.B. mit Zeitpunkten: Eigentlich hat nur Mitternacht bei Christi Geburt einen Namen alle anderen ergeben sich durch eine ziemlich unsinnig komplizierte Addition von Jahren, Monaten, Tagen, usw.

Wenn die Begriffe soweit klar sind, wenden wir uns dem eigentlichen Denken zu. Zuerst die stark vereinfachte Aussagenlogik (wahr, falsch, und, oder, nicht...) und dann die wesentlich aussagekräftigere Prädikatenlogik, bei der Relationen und Funktionen erwartungsgemäß eine zentrale Rolle spielen. Mit dieser Maschinerie wird es erstmals möglich sein, exakt zu definieren was eine logische Schlussfogerung (d.h. ein einfacher Gedanke) tatsächlich ist. Es ist dann nicht mehr schwer, die Ausführung von Schlussfolgerungen auf Maschinen zu übertragen. Der zugrundeliegende Algorithmus heißt Resolutionsmethode.

• A. Turing, Computing Machinery and Intelligence, Mind 1950
• G. Chaitin, Grenzen der Berechenbarkeit, 2004
• Warum Logik wichtig für Informatiker ist
• Michael R. Genesereth, Nils J. Nilsson: Logische Grundlagen der Künstlichen Intelligenz, Vieweg 1989
• Manfred Brill: Mathematik für Informatiker, Hanser 2005.
  Viele Anwendungsbeispiele aus der Kryptographie, Datenbanken und Computer Grafik.
• Logic and Mathematics von Stephen G. Simpson
• Programs with Common Sense von John McCarthy, 1959
• Zermelo Fraenkl Set Theory
• Geschichte der Mengentheorie
• Bruno Buchberger, Franz Lichtenberger: Mathematik für Informatiker 1, Springer 1981
• Werner Nehrlich: Diskrete Mathematik, Basiswissen für Informatiker, Fachbuchverlag Leipzig 2003