|
Logic Programming
(V3 + Ü2, SS 2015)
|
|
If you have any question, please write to lp15@i2.informatik.rwth-aachen.de!
News
-
There is a new version of the course notes (of October 19, 2015) where some small errors
have been fixed.
-
The results of the second exam are now available. You can find your score and grade in your personal overview in the exercise system.
The exam inspection takes place on Monday, September 21st 2015, 2:00-3:30 pm in our seminar room (4201b).
-
The second exam will take place on Monday, September 14th 2015, 3:00-5:00 pm in Aula 2.
Please be there on time!
-
The results of the first exam are now available. You can find your score and grade in your personal overview in the exercise system.
The exam inspection takes place on Wednesday, August 26th 2015, 2:00-3:30 pm in room 5052.
-
The exam will take place on Wednesday, August 19th 2015, 2:00-4:00 pm in
- AH 4 for all students participating in the V3B version of the exam,
- Aula 2 for those students participating in the V3M version of the exam with an immatriculation number smaller than 342900,
- AH 5 for those students participating in the V3M version of the exam with an immatriculation number greater than 342900,
- AH 5 for those students participating in the V3B and V3M version of the exam.
Please be there on time!
- Exam admissions: We finished correcting all exercise sheets and determined the final scores.
You can find the status of your admission in your personal overview in the exercise system.
If you notice any problems, please send us a mail.
-
We have added links to old exams for the lecture. Please use them when preparing for the
exam.
-
The last lecture took place on July 3. On July 10 at 10:15, there will be the last
exercise course (for V3M).
Language
English
Course Notes
The course notes are available here (in German): Course Notes (Version of October 19, 2015).
You can also find inofficial video recordings of the lecture in 2013 provided by Fachschaft I/1 MPI.
Contents
In addition to a short introduction to the programming language Prolog, the
lecture deals with the foundations of logic programming, with programming
techniques in these languages, with the implementation of logic
programming languages, and with their application in several areas.
More precisely, these are the topics of the lecture:
- Prerequisites from predicate logic
- Unification
- Resolution
- Horn clauses and SLD-resolution
-
Logic programs
- Operational and denotational semantics
- Evaluation strategies
-
The programming language Prolog
- Syntax and semantics
- Negation as failure
- Non-logical components of Prolog
- Programming techniques
- Applications and extensions of logic programming
Versions of the Lecture
Not all material of the lecture is needed for all students. More precisely, there are two versions of the lecture:
- V3B This version consists of a subset of the full lecture (with 3 hours per week). It
is relevant for students in Bachelor Informatik, Master Mathematik, and Master TK.
The following material is missing
in V3B:
- Section 4.2 (universality of logic programming)
- Section 6 (constraint logic programming)
- V3M This version also consists of a subset of the full lecture (with 3 hours per week). It
is relevant for students in Master Informatik and Master SSE. This is also the version that is relevant for those students in Bachelor Informatik who already want to attend the master-version of this course (they can transfer the credits obtained here as soon as they enter the master program).
The following material is missing
in V3M:
- Section 5.5 (input and output)
- Section 5.6 (meta programming)
- Section 5.7 (difference lists and definite clause grammars)
References
- K. R. Apt: From logic programming to Prolog, Prentice Hall, 1997.
- I. Bratko: Prolog Programming for Artificial Intelligence, Addison-Wesley, 2011.
- W. F. Clocksin, C. S. Mellish: Programming in Prolog, Springer, 2013.
- T. Frühwirth, S. Abdennadher:
Essentials of Constraint Programming, Springer, 2010.
- M. Hanus: Problemlösen mit Prolog, Teubner, 1987.
- J. W. Lloyd: Foundations of Logic Programming, Springer, 2013.
- K. Marriott, P. J. Stuckey:
Programming with Constraints, MIT Press, 1998.
- P. H. Schmitt: Theorie der logischen Programmierung, Springer, 1992.
- U. Schöning: Logik für Informatiker, Spektrum Akademischer Verlag, 2000.
- L. Sterling, E. Shapiro: The art of Prolog, MIT Press, 2000.
Area
Theoretical Computer Science, Area of Specialization, Theoretical Foundations of SSE
(Core Subjects)
Software
To write Prolog-programs, we recommend the SWI Prolog System.
An alternative to SWI-Prolog is GNU
Prolog:
The exercises have to be solved in groups of two or three.
50% of the points on the exercise sheets are
needed in order to take part in the final written exam. The written exam will be on
August 19, 2015. If you fail this exam, there will be a second written exam on
September 14, 2015. There will not be any extra oral exams, i.e., you need to take part in
the written exams in August or September 2015.
In order to take part in the exercises, please sign
up here until Friday, April 17.
- Sheet 1 / Solutions
- Sheet 2 / Solutions (lists.pl)
- Sheet 3 / Solutions
- Sheet 4 / Solutions
Here, the answer
substitution is computed as follows. Consider an SLD resolution proof from a
negative clause N of the
form N, R1, R2, ..., Rm,
where Rm is the empty clause □. So R1
is the resolvent of N and a definite clause from the input set. Similarly, R2 is the
resolvent of R1 and a definite clause from the input set, etc. Moreover, assume that
no variable renamings have been applied
to N, R1, R2, ..., Rm.
In the
first resolution step, let σ1 be the used mgu. In the second resolution step, one
used the mgu σ2, etc. Then the answer substitution is σm ○ ... ○
σ2 ○ σ1, i.e., σ1 is applied first in this composition of
substitutions. Moreover, the answer substitution is restricted to those variables that
occur in the original negative clause N.
- Sheet 5 / Solutions
- Sheet 6 / Solutions
- Sheet 7 / Solutions
- Sheet 8 / Solutions (arith.pl)
Depending on your SWI-Prolog version, for exercise 1d) you might need to add :- use_module(library(arithmetic)). as the first line of your pl-file.
- Sheet 9 / Solutions
- Sheet 10 / Solutions
- Sheet 11 / Solutions
Transparencies
Here are the transparencies used in the lecture.
- Slide 1 (April 10, 2015)
- Slide 2 (April 10, 2015)
- Slide 3 (April 13, 2015)
- Slide 4 (April 17, 2015)
- Slide 5 (April 24, 2015)
- Slide 6 (April 27, 2015)
- Slide 7 (April 27, 2015)
- Slide 8 (May 8, 2015)
- Slide 9 (May 8, 2015)
- Slide 10 (May 15, 2015)
- Slide 11 (May 18, 2015)
- Slide 12 (May 22, 2015)
- Slide 13 (June 1, 2015)
- Slide 14 (June 1, 2015)
- Slide 15 (June 15, 2015)
- Slide 16 (June 19, 2015)
- Slide 17 (June 22, 2015)
- Slide 18 (June 26, 2015)
- Slide 19 (June 26, 2015)
Here are the notes from the lecture.
- 1. Introduction (April 10, 2015)
- 2.1 Syntax of Predicate Logic (April 10, 2015)
- 2.2 Semantics of Predicate Logic (April 13, 2015)
- 3.1 Skolem Normal Form (April 17, 2015)
- 3.2 Herbrand Structures (April 17, 2015)
- 3.3 Ground Resolution (April 24 + 27, 2015)
- 3.4 Resolution in Predicate Logic and Unification (April 27 + May 4 + May 8, 2015)
- 3.5 Restrictions of Resolution (May
8, 2015)
- 4.1 Syntax and Semantics
of Logic Programs (May
8 + 15 + 18, 2015)
- 4.2 Universality of Logic Programming (May
22, 2015)
- 4.3 Indeterminism
and Evaluation Strategies (June 1 + 5, 2015)
- 5.1 Arithmetic
(June 5 + 8, 2015)
- 5.2 Lists
(June 8 + 12, 2015)
- 5.3 Operators
(June 12, 2015)
- 5.4 The Cut Predicate and Negation
(June 15, 2015)
- 5.5 Input and Output
(June 19, 2015)
- 5.6 Meta-Programming
(June 19 + 22, 2015)
- 5.7 Difference Lists and Definite Clause Grammars
(June 26, 2015)
- 6.1 Syntax and Semantics of Constraint Logic Programs
(June 26 + July 3, 2015)
- 6.2 CLP in Prolog
(July 3, 2015)
Here you find exams from the 2006, 2008, 2010, and 2013 lectures on logic
programming (partially in German).
However, as the computer science curriculum has been changed after
the 2008 lecture took place, the conditions for the 2006 and 2008 exams were different from
the ones since 2010. First, the old exams were not
designed to determine the final grade for the logic programming course, but only for the
acquisition of the Übungsschein. Second, they only took 90 minutes, while the exams since
2010 take 120 minutes. Third, we will have two different exams
(according to the two versions of the lecture) instead of just one in 2006 and 2008 or
three in 2010. Keep these differences in mind when practising with the old
exams. Furthermore, we strongly recommend that you solve the old exams without looking
into the solutions first and that you also respect the time limit
(90 minutes for the exams of 2006 and 2008, 120 minutes for the exams of 2010 and 2013).
- Exam 2006, Solution 2006
- Exam 2008, Solution 2008
- Exam V3B 2010, Solution V3B 2010
- Exam V3M 2010, Solution V3M 2010
- Exam V4 2010, Solution V4 2010
- Exam V3B 2010 (2nd), Solution V3B 2010 (2nd)
- Exam V3M 2010 (2nd), Solution V3M 2010 (2nd)
- Exam V4 2010 (2nd), Solution V4 2010 (2nd)
- Exam V3B 2013, Solution V3B 2013
- Exam V3M 2013, Solution V3M 2013
- Exam V3B 2013 (2nd), Solution V3B 2013 (2nd)
- Exam V3M 2013 (2nd), Solution V3M 2013 (2nd)
- Exam V3B 2015, Solution V3B 2015
- Exam V3M 2015, Solution V3M 2015
