15-819K: Logic Programming Lecture 1 Logic Programming

In this first lecture we give a brief introduction to logic programming. We also discuss administrative details of the course, although these are not included here, but can be found on the course web page. 1 1.1 Computation vs. Deduction Logic programming is a particular way to approach programming. Other paradigms we might compare it to are imperative programming or functional programming. The divisions are not always clear-cut—a functional language may have imperative aspects, for example—but the mindset of various paradigms is quite different and determines how we design and reason about programs. To understand logic programming, we first examine the difference between computation and deduction. To compute we start from a given expression and, according to a fixed set of rules (the program) generatee a result. For example, 15 + 26 → (1 + 2 + 1)1 → (3 + 1)1 → 41. To deduce we start from a conjecture and, according to a fixed set of rules (the axioms and inference rules), try to construct a proof of the conjecture. So computation is mechanical and requires no ingenuity, while deduction is a creative process. For example, a n + b n � = c n for n> 2,... 357 years of hard work..., QED. Philosophers, mathematicians, and computer scientists have tried to unify the two, or at least to understand the relationship between them for centuries. For example, George Boole 2 succeeded in reducing a certain clas