Introduction to
Logic Programming


This book is an introductory textbook on Logic Programming. It is intended primarily for use at the undergraduate level. However, it can be used for motivated secondary school students, and it can be used at the start of graduate school for those who have not yet seen the material.

There are just two prerequisites. The book presumes that the student understands sets and set operations, such as union, intersection, and so forth. The book also presumes that the student is comfortable with symbolic mathematics, at the level of high-school algebra or beyond. Nothing else is required.

While experience in computational thinking is helpful, it is not essential. And prior programming experience is not necessary. In fact, we have observed that some students with programming backgrounds have more difficulty at first than students who are not accomplished programmers! It is almost as if they need to unlearn some things in order to appreciate the power and beauty of Logic Programming.

The approach to Logic Programming taken here emerged from more than 30 years of research, applications, and teaching of this material in both academic and commercial settings. The result of this experience is an approach to the subject matter that differs somewhat from the approach taken in other books on the subject in two essential ways.

First of all, in this volume, we take a model-theoretic approach to specifying semantics rather than the traditional proof-theoretic approach. We begin with the fundamental notion of datasets, i.e. sets of ground atoms. Given this fundamental notion, we introduce classic logic programs as view definitions, written using traditional Prolog notation but with semantics given in terms of datasets rather than implementation. (We also talk about implementation, but it comes later in the presentation.)

Another difference from other books on Logic Programming is that we treat change on an equal footing with state. Having talked about datasets, we introduce the fundamental notion of updates, i.e. additions and deletions of ground atoms. Given this fundamental notion, we introduce dynamic logic programs as sets of action definitions, where actions are conceptualized as sets of simultaneous updates. This extension allows us to talk about logical agents as well as static logic programs. (A logical agent is effectively a state machine in which each state is modeled as a dataset and each arc is modeled as a set of updates.)

In addition to the text of the book in print and online, there is a website with automatically graded online exercises, programming assignments, Logic Programming tools, and a variety of sample applications. The website ( is free to use and open to all.

In conclusion, we first of all want to acknowledge the influence of two individuals who had a profound effect on our work here - Jeff Ullman and Bob Kowalski. Jeff Ullman, our colleague at Stanford, inspired us with his popular textbooks and helped us to appreciate the deep relationship between Logic Programming and databases. Bob Kowalski, co-inventor of Logic Programming, listened to our ideas, nurtured our work, and even collaborated on some of the material presented here.

We also want to acknowledge the contributions of a former graduate student - Abhijeet Mohapatra. He is a co-inventor of dynamic logic programming and the co-creator of many of the programming tools associated with our approach to Logic Programming. He helped to teach the course, worked with students, and offered invaluable suggestions on the presentation and organization of the material.

Finally, our thanks to the students who have had to endure early versions of this material, in many cases helping to get it right by suffering through experiments that were not always successful. It is a testament to the intelligence of these students that they seem to have learned the material despite multiple mistakes on our part. Their patience and constructive comments were invaluable in helping us to understand what works and what does not.