Formale Systeme, Winter semester 2011/2012

Department of Computer Sciences, University of Salzburg

Lecturer (VO):      Dr. A. Sokolova, ana.sokolova"at"cs.uni-salzburg.at, office 2.17

Instructions (PS):      Dr. A. Sokolova, ana.sokolova"at"cs.uni-salzburg.at, office 2.17 (Group 1) and A. Haas, dra.haas"at"gmail.com, office 2.17 (Group 2)

Schedule:      Lectures (VO) Wednesdays 1pm-2pm, room T01 and Thursdays 1pm-3pm, room T01
Instructions (PS) Thursdays 10am-12am, room T02 (Group 1) and Thursdays 3pm-5pm, room T01 (Group 2)
Tutorium Wednesdays 12am-1pm, room T02 (with Guenther Eder and Ann-Christin Knoll)

Office hours:      Tuesdays 2pm-3pm or on other days upon email appointment.

First meeting:    Wednesday, 5.10.2011, 1pm, room T01

First PS meeting:    Thursday, 13.10.2011

Language:      German (slides, book, and web info in English)

Course description: This is a first-semester obligatory course on basics of theoretical computer science: logic and sets. More information on the course content will be added here before the course starts.

Literature:

Textbook: Logical Reasoning: A First Course by Rob Nederpelt and Fairouz Kamareddine. King's College London Publications, 2007. The book can be ordered via Amazon.com . Several copies should be available at the department library in October.
Additional literature links will also be assembled here as needed, during the semester.
- After finishing Part II (Reasoning) of the book, you may want to read the following nice text by Bas Luttik, What is (in) a proof?

Thanks: Many thanks to Bas Luttik from TU/e for helpful discussions and for letting me use some of his course material.

What is theory good for? A typical question asked by (practically oriented) students. Luca Aceto has compiled a nice webpage answering this question. Click on the corresponding link on the left to get to the needed subpage.

Prerequisites: None, the course material is self-contained, as is the textbook.

Exam: At the bottom of this page there is some detailed information regarding the exam rules and grading (in German).
Exam dates: The first partial exam (Test 1) will be held on Friday, 2.12.2011, in T01, starting at 12 noon. The second partial exam (Test 2) will be held on Monday, 13.2.2012, in T01, starting at 1pm. The first regular (full) exam will be held on Tuesday, 28.2.2012, in T01, starting at 1pm. The second full exam will be held on Wednesday, 2.5.2012, in T01, starting at 1:30pm. The third full exam will be held on Monday, 9.7.2012, in T02, starting at 1:30pm.

Slides: Occasionaly (see e.g. Week1 below) slides will be used during the lecture. Whenever slides are used, they will be made available on this webpage (as in e.g. Week1 below). The slides are by no means complete and only serve as occasional help for better presentation. Much more material is covered during the class (on the blackboard) than is visible on the slides.

Announcements: On Wednesday 7.12.2011, we will have an additional class: instead of the usual 1pm-2pm in T01, we will do 12noon-2pm. This is for the lost class on the 13th of October (due to room problems).

Schedule:

Week 1: Wednesday, 5.10.2011, Introduction, Chapter 1. Thursday, 6.10.2011, Abstract propositions and truth tables, Book sections 2.1. - 2.5. and 3.1 - 3.4. (slides week1)
Week 2: Wednesday, 12.10.2011, Truth tables, section 3.5., Boolean behavior of propositions, section 4.1. and 4.2. Thursday, 13.10.2011, Boolean behavior of propositions (continued), Sections 4.3 and 4.4. (slides week2) APOLOGY: Due to unannounced room booking (for interview talks) we had to leave the room on Thursday one hour earlier. We will catch up for this one hour during the semester (find extra time).
Week 3: Wednesday, 19.10.2011, Standard equivalences, Chapter 5. Thursday, 20.10.2011, Standard equivalences (continued) and Working with equivalent propositions, Chapter 6. (slides week3)
Week 4: Wednesday, 26.10.2011, no class, national holiday. Thursday, 27.10.2011, Strengthening and weakening, Chapter 7.
Week 5: Wednesday, 2.11.2011, no class, holiday. Thursday 3.11.2011, Predicates and quantifiers, Chapter 8, Sections 8.1-8.4.
Week 6: Wednesday, 9.11.2011 Predicates and Quatifiers, Section 8.5, and Equivalences with quantifiers, Chapter 9, Section 9.1. Thursday, 10.11.2011, Equivalence with quantifiers, Sections 9.2 - 9.8. (slides week6)
Week 7: Section 9.8. (continued), Tautologies and contradictions with quantifiers, Section 9.9. Thursday, 17.11.2011, Other binders of variables, Chapter 10, and general discussion about the material so far. The material for the first test exam ends here.
Week 8: Wednesday 23.11.2011, Reasoning Chapter 11. (slides week8) Thursday, 24.11.2011, Reasoning with conjunction and implication, the structure of the context, Chapter 12 and Chapter 13.
Week 9: Wednesday 30.11.2011, Reasoning with other connectives, Chapter 14, Sections 14.1 - 14.5. Thursday, 1.12.2011, Reasoning with other connectives, continued, Sections 14.5 - 14.7, and reasoning with quantifiers, Chapter 15, Sections 15.1 and 15.2.
Week 10: Wednesday 7.12.2011, EXTRA class from 12noon-2pm (one extra class) for the lost class on the 13th of October. Reasoning with quantifiers, continued, Section 15.3, and sets, Chapter 16, Sections 16.1-16.3. No class on Thursday 8.12.2011, due to a national holiday.
Week 11: Wednesday 14.12.2011, sets, Sections 16.4-16.6. Thursday 15.12.2011, sets, Sections 16.7-16.9 and relations, Section 17.1.
Week 12: Wednesday 21.12.2011, relations, equivalence relations, Sections 17.2 - 17.4. No class on Thursday 22.12.2011, Christmas break starts.
Week 13: Wednesday 11.1.2012, equivalence relations, equivalence classes, Sections 17.4 - 17.5. Thursday 12.1.2012, partitions, correspondence of partitions and equivalences (not in the book), composing relations, reflexive and transitive closure, and mappings/functions, Sections 17.6-17.7, 18.1-18.2.
Week 14: Wednesday 18.1.2012, image and source, special functions, Sections 18.3 - 18.4. Thursday 12.1.2012, special functions (examples and properties), the inverse function, composite mappings, equality of mappings, Sections 18.4-18.7, and sorts of numbers, the structure of natural numbers, Sections 19.1-19.2.
Week 15: Wednesday 25.1.2012, induction. Thursday 26.1.2012, induction continued and cardinality. Till the end of Chapter 19.

Exercises for the instructions:

As usual, there is no PS in the first week of the semester.
Week 2
Week 3
Week 4
Week 5
Week 6
Week 7
Week 8
PS exercises for week 9 are: 11.7, 12.1, 12.2, 12.3, 12.4, 13.1, and 13.2 from the book.
No PS in week 10 of this semester (the 8th of December is a natonal holiday).
PS exercises for week 11 are: 14.1, 14.6, 14.7, 15.3, 15.4, 15.6, 15.9, and 15.10.
No PS in week 12 of this semester (on the 22nd of December Christmas break starts).
PS exercises for week 13 (12.1.2012, after the Christmas break) are: 16.1, 16.4, 16.5, 16.6, 16.8, 16.10, 16.12, 17.1, 17.3, and 17.5 from the book.
PS exercises for week 14 are: 17.1, 17.3, 17.5, 17.7, 17.8, 17.9, 18.1, 18.3, and 18.4 from the book.
PS exercises for week 15 are: 18.3, 18.4, 18.8, 18.9, 18.10, 18.11, 19.4, and 19.13 from the book.
Here is an example-task set for the second test exam.

Solutions of some exercises from the instructions:

The following file (thanks to Bas Luttik) contains solutions of chosen exercises of Week 1-5
Here is the solution of an exercise of Week 6
Here are the solutions of two exercises of Week 7
Here are the solutions of the first five exercises (example test) of Week 8
Here are the solutions of some exercises of Week 9 - Week 15. More solutions of tasks of Part II and Part III of the book you can find (thanks to Bas Luttik again) here:
Here are the solutions of the example test 2

Pruefung: VORLESUNG: Die Vorlesungspruefung besteht aus einem schriftlichen und einem optionalen muendlichen Teil. Es gibt zwei Moeglichkeiten, den schriftlichen Pruefungsteil zu absolvieren:

(1) Durch die Teilnahme an zwei Zwischentests im Laufe des Wintersemesters. Der Stoff fuer diese Tests beschraenkt sich auf die bis dahin vorgetragenen Inhalte der Vorlesung.

(2) Durch das Ablegen einer Klausur. Fuer die Klausur werden drei Termine im Sommersemester angeboten.

Die genauen Termine werden rechtzeitig in der Vorlesung und auf dieser Seite bekanntgegeben. Der Stoff der Pruefungen sind Uebungsbeispiele, wie sie im Proseminar gerechnet werden, und die Theorie, die in der Vorlesung vorgetragen wurde. Die Anmeldung zur schriftlichen Pruefung erfolgt ueber Plus-Online. Zum Bestehen der schriftlichen Pruefung sind 55% der Gesamtpunkteanzahl notwendig. Wenn man mit dem Ergebnis der schriftlichen Pruefung zufrieden ist, ist keine muendliche Pruefung notwendig. Ohne einer zusaetzlichen muendlichen Pruefung ist die beste erreichbare Note ein "Gut(2)".

Hat man den schriftlichen Pruefungsteil positiv absolviert, und moechte seine Note veraendern(!), insbesondere also wenn man ein "Sehr Gut (1)" erreichen moechte, so kann man eine muendliche Pruefung absolvieren.

Stoff der muendlichen Pruefung ist der Stoff der Vorlesung. Die Anmeldung zur muendlichen Pruefung ist bis spaetestens eine Woche nach der Bekanntgabe der schriftlichen Note per E-Mail moeglich. Termine nach Vereinbarung.

PROSEMINAR: Der Proseminarmodus ist "Kreuzluebungen", d.h.:

(1) Sie bekommen woechentlich fuer das jeweils naechste Proseminar Aufgaben, und loesen diese zu Hause.

(2) Vor dem Proseminar kreuzln Sie auf einer Liste jene Beispiele an, die Sie loesen konnten UND gemeinsam mit dem notwendigen theoretischen Umfeld soweit verstanden haben, dass Sie sie vernuenftig erklaeren koennen.

(3) In dem Proseminar ruft der Proseminarleiter zu den Aufgaben jemanden auf, der die jeweilige Aufgabe dann an der Tafel praesentiert. Im Idealfall machen wir alle Beispiele durch, meistens werden wir ungefaehr 3/4 der gestellten Aufgaben schaffen.

Die Beurteilung richtet sich nach zwei Komponenten, naemlich der Anzahl der angekreuzten Beispiele und der Qualitaet ihrer Praesentationen an der Tafel.

Notwendig fuer eine positive Note sind zwei positive Tafelleistungen und 60 Prozent angekreuzte Beispiele.

NACHBRINGEN VERSAEUMTER PROSEMINARE:

Sie koennen ohne weitere Begruendung ein Proseminar versaeumen und diese dann nachholen. Dazu vereinbaren Sie mit Ihrem Proseminarleiter einen Termin, wo Sie dann kommen und ein paar Aufgaben des versaeumten Proseminars praesentieren. Nachgebrachte Proseminare erhoehen die Anzahl der Kreuzl, zaehlen aber nicht als Tafelleistung.

Sollten Sie aus triftigen Gruenden (z.B. Spitalsaufenthalt) mehrere Proseminare versaeumen und diese nachbringen wollen, dann besprechen Sie das im Einzelfall mit dem Proseminarleiter.