• Created in the 1970s
  • Prolog = “PROgramming in LOGic”
  • There are many different implementations, e.g. SWI-Prolog and GNU Prolog
  • Prolog is a logic programming language and declarative in nature
  • Prolog is turing-complete (

Example Program (Reference)

  • A Prolog program consists of predicates which define relations between arguments
% move(N,X,Y,Z) - move N disks from peg X to peg Y, with peg Z being the
%                 auxilliary peg
% Strategy:
% Base Case: One disc - To transfer a stack consisting of 1 disc from
%    peg X to peg Y, simply move that disc from X to Y
% Recursive Case: To transfer n discs from X to Y, do the following:
         Transfer the first n-1 discs to some other peg X
         Move the last disc on X to Y
         Transfer the n-1 discs from X to peg Y

     move(1,X,Y,_) :-
         write('Move top disk from '),
         write(' to '),
     move(N,X,Y,Z) :-
         M is N-1,
  • A clause consists of a head and a body
% a simple clause
Head :- Body.
  • This means: if Body is true, then Head is true
  • Since Prolog is declarative, we specify the result we are interested in and not the concrete steps to compute a result
  • We are not concerned how Prolog finds these results

Logical Foundations of Prolog

Resolution is based on the idea of proof by contradiction: To prove a logical consequence of a set of axioms, we assume the opposite of what we want to prove, and show that this contradicts the axioms which we take for granted

  • There are different evaluation strategies for resolution



  • Prolog is dynamically typed and has a single data type called the term
  • All data and programs are represented by terms
  • Terms are either atoms, numbers, variables or compound terms
  • Atoms and numbers are sometimes grouped together and called atomic terms


  • An atom is just a name that can serve multiple purposes
  • It consists of a sequence of letters, if it contains spaces, you need to use quotes
  • Uppercase atoms must also be put into quotes, otherwise they would be treated as variables

Compound Terms

  • Consist of a functor (a Prolog atom) and a number of arguments (Prolog terms) enclosed in parentheses and separated by commas


  • Each predicate has
    • Name: which is an atom
    • Zero or more Arguments: is an arbitrary term
  • A predicate with name Pred and N arguments is denoted by Pred/N
  • That notation is called a predicate indicator
  • N is called the arity of the predicate
  • A predicate is defined by a collection of clauses
  • A clause is either a rule or a fact
  • Clauses denote logical alternatives: If any clause is true, then the whole predicate is true


  • A rule is of the form Head :- Body.
  • The notation of the head of a rule depends on the number of arguments:
    • If the predicate has zero arguments, then the head is only the name of the predicate
    • If a predicate has N arguments, then the head is written as PredName(Arg1, Arg1, ...)
  • The body of each rule is a Prolog goal
  • A goal is a term that denotes the predicate and its arguments
  • Rules can be recursive


  • A fact is written as Head.
  • This is equivalent to the rule Head :- true.
  • A fact is always true


  • After a Prolog program is compiled, you submit queries to the interpreter
  • A query has the same structure as the body of a rule
    • It is a sequence of predicates separated by commas and terminated by a dot
?- small(X), green(X), smily(X).