Logic Programming

A restricted form of predicate logic wffs, called Horn clauses, can be used as a programming language to solve computing problems as well as database queries. A Horn clause is one of the following forms:

  1. Fact: p(c1,...,cn).
    where p is a predicate symbol (arity=n) and c1, ..., cn are constant symbols.

    Example: the following are some facts: 

    eat(bear,fish).
eat(bear,fox).
eat(fox,rabbit).
eat(deer,grass).
animal(bear).
animal(fish).
animal(fox).
animal(rabbit).
animal(deer).
plant(grass).
  2. Rule: p :- q1, ..., qk.
    where p, q1, ..., qk are atomic formulas with constants or variables as arguments. Note: In general, these atomic formulas can have other types of arguments called function terms, but for simplicity we restrict the arguments to be constants or variables.

    Example: the following are some rules: 

    prey(X) :- eat(Y,X), animal(X).
hunted(X) :- prey(X).
inFoodChain(X,Y) :- eat(X,Y).
inFoodChain(X,Y) :- eat(X,Z), inFoodChain(Z,Y).
    The rules are interpreted as follows:

    (∀ X)(∀ Y)(eat(X,Y) ∧ animal(X) → prey(X))

    (∀ X)(prey(X) → hunted(X))

    (∀ X)(∀ Y)(eat(X,Y) → inFoodChain(X,Y))

    (∀ X)(∀ Y)(eat(X,Z) ∧ inFoodChain(Z,Y) → inFoodChain(X,Y))

    i.e. all variables are universally quantified within each rule at the outermost level and the rule itself is treated as an implication.

  3. Query: :- q1, ..., qk.
    where q1, ..., qk are atomic formulas with constants or variables as arguments.

    Example: the following are some queries: 

    :- animal(bear).
:- animal(X).
:- eat(bear,X).
:- eat(X,Y), plant(Y).
:- prey(X).
:- inFoodChain(bear,Y).
A logic program consists of facts and rules and the program is invoked/run by executing a query. The logic programming interpreter executes the query by performing a series of deductions from the given facts and rules and tries to infer the query. For example, to prove inFoodChain(bear,rabbit) from the given program, the logic programming system may use the following proof:
  1. (∀ X)(∀ Y)(eat(X,Y) → inFoodChain(X,Y)), Given
  2. eat(fox,rabbit) → inFoodChain(fox,rabbit), 1, UI twice
  3. eat(fox,rabbit), Given
  4. inFoodChain(fox,rabbit), 2,3, MP
  5. (∀ X)(∀ Y)(eat(X,Z) ∧ inFoodChain(Z,Y) → inFoodChain(X,Y)), Given
  6. eat(bear,fox) ∧ inFoodChain(fox,rabbit) → inFoodChain(bear,rabbit)), 5, UI thrice
  7. eat(bear,fox), Given
  8. eat(bear,fox) ∧ inFoodChain(fox,rabbit), 7,4 Conjunction
  9. inFoodChain(bear,rabbit), 6,8, MP

Prolog

Prolog is an implementation of Logic Programming paradigm and the interpreter on tinman.cs.gsu.edu server can be invoked by running the command pl, as shown in the following screen capture: 
[~][5:32pm] pl
Welcome to SWI-Prolog (Multi-threaded, Version 5.4.7)
Copyright (c) 1990-2003 University of Amsterdam.
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to redistribute it under certain conditions.
Please visit http://www.swi-prolog.org for details.

For help, use ?- help(Topic). or ?- apropos(Word).

?- ['foodChain.pl'].
% foodChain.pl compiled 0.00 sec, 2,388 bytes

Yes
?- animal(bear).

Yes
?- animal(X).

X = bear ;

X = fish ;

X = fox ;

X = rabbit ;

X = deer ;

No
?- eat(bear,X).

X = fish ;

X = fox ;

No
?- eat(X,Y), plant(Y).

X = deer
Y = grass ;

No
?- prey(X).

X = fish ;

X = fox ;

X = rabbit ;

No
?- inFoodChain(bear,Y).

Y = fish ;

Y = fox ;

Y = rabbit ;

No
?- halt.
[~][5:33pm]
The file foodChain.pl contains the following program (facts and rules) 
eat(bear,fish).
eat(bear,fox).
eat(fox,rabbit).
eat(deer,grass).
animal(bear).
animal(fish).
animal(fox).
animal(rabbit).
animal(deer).
plant(grass).
prey(X) :- eat(_,X), animal(X).
hunted(X) :- prey(X).
inFoodChain(X,Y) :- eat(X,Y).
inFoodChain(X,Y) :- eat(X,Z), inFoodChain(Z,Y).
and the program is read by the Prolog interpreter by the command ['foodChain.pl']. Queries are then presented to the system and the responses are shown on the screen. The first answer is shown immediately; to get subsequent answers, the user has to type a semi-colon.