Logic programming

The main idea of logic programming is that deduction can be viewed as a form of computation (Sterling and Shapiro, 1994). The declarative statement

$$H \Leftarrow B_1 \land B_2 \land B_3$$ (5.1)

can be interpreted procedurally as ``to solve $H$, solve $B_1$ and $B_2$ and $B_3$'', or shortly $H \leftarrow B_1,B_2,B_3$. A logic programme is thus a set of logical axioms and it is run by querying for a proof of some goal statement. The closed world assumption (Reiter, 1978) is used, that is, everything that cannot be proven to be true, is assumed to be false.

Normally the statements in a logic programme are restricted to be of the form $H \leftarrow B_1,\dots ,B_n$, that is, they are so-called Horn clauses. This ensures that the proof for the goal statement has a simple tree structure. Atom $H$ is called the head of the clause and the atoms $B_1,\dots ,B_n$ form the body of the clause. Statements with $n=0$ are called facts because the proof of the head does not require solving any more statements.

Logic programming uses first-order logic. This means that an atom can be structured as a predicate followed by a number of arguments in brackets. Some of the arguments can be variables.^5.1An example of a rule (or clause) that uses first-order logic is $\mathrm{son}(X,Y) \leftarrow \mathrm{parent}(Y,X), \mathrm{male}(X)$, that is, $X$ is the son of $Y$ if $Y$ is the parent of $X$ and $X$ is male. $X$ and $Y$ are logical variables that can represent any object (people in this case). Variables are written in upper case to avoid confusion. Atoms that do not contain any variables are called ground. Completeness theorem by Gödel (1929) states that in first-order predicate calculus every logically valid formula is provable. Second-order logic allows variables as predicates, but completeness does not hold anymore.

A logic programme that contains the rule $\mathrm{son}(X,Y) \leftarrow \mathrm{parent}(Y,X), \mathrm{male}(X)$ and some ground facts such as $\mathrm{parent}(mary,robert)$ and $\mathrm{male}(robert)$, can answer a query $\mathrm{son}(X,mary)$. The solver finds the rule and tries to solve the body of the rule, that is $\mathrm{parent}(mary,X)$ and $\mathrm{male}(X)$. The only solution is $X=robert$ which is returned as the output of the programme.

Prolog is the best-known logic programming language. Sterling and Shapiro (1994) wrote a good book on logic programming and Prolog in specific. Logic programming differs somewhat from traditional procedural programming. The clearest difference is that the values of variables are fixed once set. Where procedural programmes tend to have for-loops, logic programmes use recursion instead. The strong areas of logic programming include handling structured data, symbolic manipulation, and self-changing programmes. In inductive logic programming, rules in logic programmes are learned from examples.