Tik-79.144 Logic in Computer Science: Foundations
This is an introductory course on logic and its applications in
computer science. Subjects covered are: propositional and predicate
logic, model theory, proof theory, semantic/analytic tableaux,
resolution.
[General Information]
[Material]
[Examinations]
[Home Assignments]
[Lectures]
[TOPI]
- Registration is still possible by contacting the lecturer
- Lectures by
Tomi Janhunen
- Tutorials by Tommi Syrjänen
- Office hours: see the lecturer's home page
- The course consists of
- In order to pass the course one has to pass
- the three home assignments
- the exam (with a grade greater than 0)
- Newsgroup:
opinnot.tik.logiikka
- Brochure in Finnish
- Textbook:
A. Nerode and R. Shore:
Logic for Applications, Springer, 1997, 456 p.
- Chapters I, II and III in the extent presented at lectures
- some specimen are available at the bookstore now
- the first edition of the book (1993, 365 p.) can also be used
(Errata)
- Lecture Notes (opetusmonisteet)
- Questions from tutorials and answers to the questions
- Slides from the lectures (4 slides per page)
- You should register for the course in order to get
your home assignments.
- Here is the list of
accepted assignments
which will be updated after next deadline (see below).
The list contains students with at least one assignment accepted.
- If your home assignment was rejected, you can fetch
your answers from our secretary (Ulla Kangasniemi, room TB336),
attach your corrections and make a resubmission.
- Home assignments can be fetched from a pigeonhole outside room TB336,
or otherwise from the lecturer during office hours.
- Home assignments are personal
(your name and student ID are printed on your sheet).
Please preserve the alphabethical order of assignments !!!
- In case you need advice, please attend any tutorial
or office hour and ask for it.
- RESUBMISSION DEADLINE: the 14th of May
- See more detailed instructions
to submit the third home assignment.
- Answers to questions (including the question sheet) are returned
to a white mailbox outside room TB336.
Please avoid unnecessary printing of the material to save printers,
paper and thus nature. The slides and tutorials can be ordered as
lecture notes (opetusmonisteet).
Timetable and contents
-
September 15: Lecture 1
- Introduction, syntax of propositional logic (pages 1-16)
tutorial
(in English),
solutions
(in English)
-
September 22: Lecture 2
- Truth tables, semantic tableaux (pages 17-36)
tutorial
(in English),
solutions
(in English)
-
September 29: Lecture 3
- Soundness and completeness of semantic tableaux,
Hilbert-style axiomatizations, normal forms (pages 37-49)
tutorial
(in English),
solutions
(in English)
-
October 6: Lecture 4
- Resolution in propositional logic (pages 50-68)
tutorial
(in English),
solutions
(in English)
-
October 13: No lecture
- Help for home assignments
tutorial
(in English),
solutions
(in English)
-
October 20: Lecture 5
- Predicate logic and its semantics (pages 81-99)
tutorial
(in English),
solutions
(in English)
-
October 27: Lecture 6
- Semantic tableaux for predicate logic (pages 108-126)
tutorial
(in English),
solutions
(in English)
-
November 3: Lecture 7
- Hilbert-style axiomatization, normal forms, skolemization,
Herbrand's theorem (pages 127 - 137)
tutorial
(in English),
solutions
(in English)
-
November 10: Lecture 8
- Unification and resolution (pages 138-158)
tutorial
(in English),
solutions
(in English)
-
November 17: Lecture 9
- Knowledge representation using predicate logic,
theorem prover
OTTER
tutorial
(in English),
solutions
(in English)
-
November 24: Lecture 10
- Resolution in PROLOG, negation as failure (pages 69-80,159-202)
tutorial
(in English),
solutions
(in English)
-
December 1: Lecture 11
- Computational complexity, some applications of logic,
review of the lectures 1-10
Latest update: September 2, 1999 by
Tomi Janhunen