TCS / Studies / T-79.3001 Logic in Computer Science: Foundations
Helsinki University of Technology, Laboratory for Theoretical Computer Science

T-79.3001

Logic in Computer Science: Foundations

(4 cr)

Spring 2008 (periods III and IV)

Navigation: [General Information] [Course Material] [Lectures] [Tutorials] [Home Assignments] [Feedback] [Examinations] [TOPI]

Previous years: [Spring 2007] [Spring 2006] [Autumn 2004]

This is an introductory course on logic and its applications in computer science. Subjects covered: propositional logic, predicate logic, induction principle, model and proof theory, semantic/analytic tableaux, resolution, and some examples of applications.

General Information

  • Registration for the course will begin on the 14th of January (12:00 hours). The deadline for registrations is the 28th of January (14:00 hours).
  • Lectures are given by Docent, D.Sc.(Tech.) Tomi Janhunen: Mondays 10—12, hall T1, starting on the 21st of January, 2008
  • Tutorials are held by Lic.Sc.(Tech.) Emilia Oikarinen and M.Sc.(Tech.) Antti Hyvärinen:
    • Wednesdays, 10—12, T3, or
    • Thursdays, 16—18, T1, or
    • Fridays, 14—16, T1.
    Tutorials start on the 30th of January, 2008.
  • Course material: new lecture notes in Finnish (Edita).
  • In order to pass the course one has to
    • pass three compulsory home assignments and
    • pass an exam (with a grade greater than 0).
    The grade may be affected by bonus points (see tutorials and course feedback for details).
  • Brochure in Finnish
  • Office hours: please see the lecturer's home page.
  • Contacts via email: the alias t793001 at tcs.hut.fi is recommended. Please do not forget to mention your student ID!
  • Newsgroup: opinnot.tik.logiikka (using nntp) at news.tky.fi

For Students from Previous Years:

  • The last exam based on course requirements for Spring 2007 is arranged in March 2008.
  • Any unfinished home assignments can be completed by then.
  • Bonus points earned by doing tutorial exercises in Spring 2008 apply to examinations arranged after March 2008.
Back to menu.

Course Material

Lecture Notes

  • The material presented at lectures
    1. Propositional logic (parts I and II) in print only
    2. Predicate logic (parts III and IV) in print only
  • Solutions to some demonstration problems from tutorials
  • Lecture notes can be ordered from Edita using the TOPI system. Parts I—IV have been delivered (as of Apr 24).
  • Please avoid unnecessary printing of the material to save printers, paper and thus nature !!!

English Track

Lectures are mainly based on two textbooks that we recommend as the main references for foreign students:

Copies of both textbooks are available in the main library as well as the CS library. The material presented at tutorials will be translated into English (which enables English speaking students to attend).

Back to menu.

Lectures

Period III

Propositional Logic

Tentative schedule for lectures:
  • The full material is only available in print (lecture notes)!
  • Chapters 1—15 below refer to lecture notes.
Introduction (Jan 21, 2008)
Registration, practical arrangements
Lecture 1 (Jan 28, 2008)
Syntax and semantics of propositional logic (chapters 1—2)
Lecture 2 (Feb 4, 2008)
Basic semantical concepts (chapter 3)
Lecture 3 (Feb 11, 2008)
Semantic tableaux (chapter 4)
Lecture 4 (Feb 18, 2008)
Classical proof systems (chapter 5)
Lecture 5 (Feb 25, 2008)
Normal forms and resolution (chapter 6—section 7.4)
Lecture 6 (Mar 3, 2008)
Resolution (continued), computational complexity (section 7.5—chapter 8)

Period IV

Predicate Logic

Lecture 7 (Mar 17, 2008)
Syntax and semantics of predicate logic (chapter 9—section 10.1)
No lecture (Mar 24, 2008)
Easter holidays
Lecture 8 (Mar 31, 2008)
Semantical concepts and normal forms (section 10.2—chapter 11)
Lecture 9 (Apr 7, 2008)
Semantic tableaux (chapter 12)
Lecture 10 (Apr 14, 2008)
Knowledge representation (chapter 13)
Lecture 11 (Apr 21, 2008)
Herbrand's theorem, unification, and resolution (chapter 14.1—14.4)
Lecture 12 (Apr 28, 2008)
Program verification (sections 14.5 and 15.1—15.2)
Lecture 13 (May 5, 2008)
Program verification (sections 15.3—15.5); Getting prepared for the exam.
Back to menu.

Tutorials

In each two-hour tutorial, there will be three tutorial problems to be solved by students on their own beforehand and two or three demonstration problems. Tutorials are not compulsory but bonus points for exams will be awarded on the basis of them. If you want to solve tutorial problems, please get registered for one of the tutorial groups using TOPI by January 28, 2008 (to enable the bookkeeping of your tutorial points).

Period III Period IV
T1Week 5 Jan 30—Feb 1
T2Week 6 Feb 6—8
T3Week 7 Feb 13—15
T4Week 8 Feb 20—22
T5Week 9 Feb 27—29
T6Week 10/11Mar 5,and 13—14
T7 Week 12/13Mar 19, and 27—28
T8 Week 14Apr 2—4
T9 Week 15Apr 9—11
T10Week 16Apr 16—18
T11Week 17Apr 23—25
T12Week 18Apr 29—30 and May 2

Each tutorial problem is worth one tutorial point which implies the maximum of 36 tutorial points. In order to earn one tutorial point, you are supposed solve one problem on your own and to declare it as done at the respective tutorial session. Accordingly, you may be asked to present your solution at the white board.

Tutorial Exercises

Tutorial Points

Tutorial points are converted into bonus points using the following scheme:

Tutorial points Bonus points
0—5 -2
6—11 -1
12—17 0
18—23 +1
24—29 +2
30—36 +3

Back to menu.

Home Assignments

  • Each student receives three personal home assignments (HAs) during the spring term.
  • Grading is done using the scale passed / not passed.
  • Please observe: one must pass all the three HAs before attending exams.
  • Assignments will be delivered through our home assignment server.
  • Tentative schedule for spring 2008:

    HA Launch date Deadline
    1 Feb 12, 2008 Feb 26, 2008, 24:00
    2 Apr 7, 2008 Apr 17, 2008, 24:00
    3 Apr 7, 2008 Apr 24, 2008, 24:00

  • Results: lists of students who had pased one, two, three home assignments by the respective deadlines. A bonus point was granted to those who did all three home assignments on time, i.e., is mentioned in each of the three lists.
  • Special office hours were organised Apr 21—24. If you still need help with your home assignments please attend the lecturer's office hours on May 5, 15:00-16 or May 12, 15:00-17 in room TB335. It is highly recommended that you have submitted your solution before attending these events (bring a copy of your solution on paper).
  • It is still possible to make corrections to all three home assignments (in order to attend exams).

Back to menu.

Feedback

  • Students who answered the first, the second, the third, and the fourth questionnaire about the new lecture notes on time. A bonus point was granted to those who answered all four questionnaires on time.
  • Since questionnaires are only available in Finnish (the material is in Finnish) you may alternatively earn this bonus point by doing your three home assignments on time. This is also applicable to students who have not ordered the new lecture notes from Edita.
  • General course feedback is now being collected in Finnish, Swedish, and English (open Apr 28—May 20, 24:00, 2008).
  • A bonus point was granted to those who filled in the feedback form on time.

Back to menu.

Examinations

Back to menu.

[TCS main] [Contact Info] [Personnel] [Research] [Publications] [Software] [Studies] [News Archive] [Links]
Latest update: 17 April 2009. Tomi Janhunen