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

T-79.144 Logic in Computer Science: Foundations (2 cr)

Autumn 2002

[General Information] [Lectures] [Home assignments] [Feedback] [Examinations] [TOPI]

Previous years: [Autumn 2001] [Autumn 2000] [Autumn 1999] [Autumn 1998] [Autumn 1997] [Autumn 1996]

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

  • Lectures by D.Sc.(Tech.) Tomi Janhunen: Tuesdays 12-14, Mellin hall (in the main building)
  • Tutorials by Lic.Sc.(Tech.) Toni Jussila, M.A. Misa Keinänen, and Stud.(Tech.) Emilia Oikarinen: Mondays, 12-13, hall T3, or Tuesdays, 16-17, hall T2, or Wednesdays, 9-10, hall T2, or Thursdays, 11-12, hall T2.
  • Course material: lecture notes in Finnish.
  • In order to pass the course one has to
    • pass the three compulsory home assignments and
    • pass the exam (with a grade greater than 0).
  • Brochure (.ps 66kB/ .pdf 53kB) in Finnish and English
  • Office hours: please see the lecturer's home page.
  • Contacts via email: the alias t79144 at tcs.hut.fi is recommended. Please mention your student ID!
  • Newsgroup: opinnot.tik.logiikka
  • Please register for the course using TOPI. We will accept at most 400 participants this autumn.
Back to menu.

Lecture Notes

  • Slides from the lectures in Finnish:
  • Exercises and some solutions will be also provided.
  • Lecture notes can be ordered using [TOPI].
  • Please avoid unnecessary printing of the material to save printers, paper and thus nature !!!

Further Reading

  • A textbook by A. Nerode and R. Shore: Logic for Applications, Springer, 1997, 456 p.
  • Chapters I-III are recommended as base material for foreign students.
  • The first edition of the book (1993, 365 p.) can also be used (Errata).

Schedule for Autumn 2002

September 10: Lecture 1
Registration
Practical arrangements (.ps.gz 51kB / .pdf 106kB)
Introduction and prerequisites (.ps.gz 88kB / .pdf 226kB)
Tutorial 1 (.ps.gz / .pdf)
September 17: No lecture nor tutorials this week
September 24: No lecture nor tutorials this week
October 1: Lecture 2 (slides 1-27)
Syntax and semantics of propositional logic
Tutorial 2 (.ps.gz / .pdf)
October 8: Lecture 3 (slides 28-54)
Basic semantical definitions, introduction to semantic tableaux
Tutorial 3 (.ps.gz / .pdf)
October 15: Lecture 4 (slides 55-81)
Semantic tableaux: properties and use
Tutorial 4 (.ps.gz / .pdf)
October 18: Lecture 5 (slides 82-110)
Alternative proof systems (by Hilbert and Suppes), normal forms
Tutorial 5 (.ps.gz / .pdf)
October 22: Lecture 6 (slides 111-143)
Clausal form, resolution and computational complexity
Tutorial 6 (.ps.gz / .pdf)
October 25: Lecture 7 (slides 1-31)
Syntax and semantics of predicate logic
Tutorial 7 (.ps.gz / .pdf)
October 29: Lecture 8 (slides 32-59)
Semantic tableaux for predicate logic
Tutorial 8 (.ps.gz / .pdf)
November 5: Lecture 9 (slides 60-86)
Counter models, Hilbert's system, normal forms, knowledge representation
Tutorial 9 (.ps.gz / .pdf)
November 12: Lecture 10 (87-115)
Knowledge representation (continued), Herbrand structures and models
Tutorial 10 (.ps.gz / .pdf)
November 19: Lecture 11 (116-139)
Herbrand's theorem, Unification, Resolution
Tutorial 11 (.ps.gz / .pdf)
November 26: Lecture 12 (140-147, 1-22)
Resolution (continued), Applications
Tutorial 12 (.ps.gz / .pdf)
December 3: Lecture 13 (23-45)
Applications (continued)
Tutorial 13 (.ps.gz / .pdf)
Back to menu.

Home Assignments

  • Each student receives three personal home assignments during the autumn term.
  • Grading is on the scale passed / not passed.
  • Observe: one must pass all the three home assignments before attending exams.
  • Assignments are delivered through our home assignment server.
  • Solutions are checked automatically
    • daily 16:00 and 24:00 (the first two home assignments) and on
    • daily 8:00, 14:00 and 20:00 (the third home assignment).
  • Those who participated the course last year, but dit not pass all the three home assignments, are supposed to go on correcting their answers and/or doing any undone assignments.

Schedule

  • The first home assignment was launched on October 15, 2002. Deadline: October 31, 2002.
  • The second home assignment was launched on November 6, 2002. Deadline: November 24, 2002.
  • The third home assignment was launched on November 20, 2002. Deadline: December 8, 2002.

Help for the Third Home Assignment

  • If the third home assignment turns out to be too difficult for you, you may attend special office hours to get help.
  • These events were arranged on November 26, 27, and 29, and on December 2, 3, 5, and 10.
  • Similar events will be arranged spring 2003.
  • We expect that you make your first electronic submission (or at least a sketch of the definitions by hand) before attending these events.

Results

  • List of students (310/326/424) who have passed their first home assignment (October 31, 2002, 24:00).
  • List of students (247/333/425) who have passed their first two home assignments (November 24, 2002, 24:00).
  • List of students (275/368/436) who have passed their all home assignments (October 2, 2003, 24:00).
  • These lists will not be updated.
  • Explanation for the numbers: (#passed/#active/#students)
  • Those who failed to pass are supposed to complete their home assignments according to requirements of the next study year.
Back to menu.

Feedback

We welcome your opinion on this course. Please use our feedback form.

Examinations

Back to menu.
[TCS main] [Contact Info] [Personnel] [Research] [Publications] [Software] [Studies] [News Archive] [Links]
Latest update: 11 October 2005. Tomi Janhunen