Introduction to Logic
Programming
Contents
● What is Logic Programming
● History of Logic Programming
● What is a logic
● Examples of Logic Programs
2
Logic Programming
Logic programming is a computer programming
paradigm.
Logic programming is a way of writing computer
programs using languages that are based on formal
logic.
Logic programs are declarative rather than
procedural, which means that only the specifications
of the desired results are stated rather than detailed
procedures for producing them.
Programs in logic programming languages are
collections of facts and rules.
Languages used for logic programming are
called declarative languages, because programs
written in them consist of declarations rather than
assignments and control flow statements.
Language used for logic programming: Prolog.
Aspects of Logic Programming
● Programs are written in the language of some logic.
● Execution of a logic program is a theorem proving
process; that is, computation is done by logic
inferences
● Prolog (PROgramming in LOGic) is a
representative logic language
6
History of Logic Programming (LP)
● Formulated in 1974 by a professor at Univ. of
Edinburgh.
● First system implemented in 1995 by a research
group in France.
● First compiler built in 1997 by a PhD student also in
Edinburgh.
● Japan’s fifth generation computer project
announced in 1980.
● Efficiency improved in recent years
● Interfaces with other languages such as C/Java.
7
Applications of logic programming
1: parsing
2: relational database management system
3: expert system
4: natural language processing solving
5: symbolic equation solving
6: planning
7: prototyping
8: simulation
9: programming language implementation
10:Intelligent Database Retrieval
11:Machine Learning
12:Robot Planning
13:Automation System
14:Problem Solving
logic programming languages
Some logic programming languages are given below −
ALF (algebraic logic functional programming language).
ASP (Answer Set Programming)
CycL
Datalog
FuzzyCLIPS
Janus
Parlog
Prolog
Prolog++
ROOP
Logic and Functional Programming
Why Prolog is not as popular as C/Java
● Not yet as efficient as C
● Support to Prolog takes effort, resources; companies are
not willing to pay for it
● Its value not recognized by industry.
1
2
What is a logic
● A logic is a language. It has syntax and semantics.
More than a language, it has inference rules.
● Syntax: the rules about how to form formulas; this is
usually the easy part of a logic.
● Semantics: about the meaning carried by the formulas,
mainly in terms of logical consequences.
● Inference rules describe correct ways to derive
conclusions.
1
3
Use logic to do reasoning
Example:
Given information about fatherhood and motherhood, determine
grand parent relationship.
E.g. Given the information called facts
John is father of Lily
Kathy is mother of Lily
Lily is mother of Bill
Ken is father of Karen
Who are grand parents of Bill?
Who are grand parents of Karen?
1
4
Example of Prolog program
In Prolog, we write the following for the given facts:
father(john,lily).
mother(kathy,lily).
mother(lily,bill).
father(ken, karen).
● In logic, words like father, mother are called predicates
● A statement like father(john,lily) is called an atomic formula,
called an atom, stating a true fact
1
5
Programs as logic formulas
Express the grand parent relationship:
grandparent(X,Z) :- parent(X,Y), parent(Y,Z).
parent(X,Y) :- father(X,Y).
parent(X,Y) :- mother(X,Y).
These are called conditional statements.
Capital letters denote variables, meaning “for any”.
E.g., the first formula above reads:
For any X,Y,Z,
if X is a parent of Y, and Y is a parent of Z,
then X is a grand parent of Z. 9
A complete program
Putting all together, we have a Prolog program:
grandparent(X,Z) :- parent(X,Y), parent(Y,Z).
parent(X,Y) :- father(X,Y).
parent(X,Y) :- mother(X,Y).
father(john,lily).
mother(kathy,lily).
mother(lily,bill).
father(ken, karen).
17
Ask Prolog to do something for you
Provide a query to Prolog; e.g.
?- grandparent(john,bill)
Prolog uses your program to do reasoning and answer the
query, in this case, the answer by Prolog is YES.
If you post your query as:
?- grandparent(Q,karen)
Meaning who are grand parent of karen, Prolog answers NO
18
Ask Prolog to do something for you
You can ask Prolog the question: who are the grand
parents of bill by posting a query
?- grandparent(Q,bill)
Prolog answers
Q = john
Q = kathy
19
Ask Prolog to do something for you
You can ask Prolog the question: who are the grand
children of john by posting
?- grandparent(john,W)
Prolog answers
W = bill
20
Prolog
programs
● In general, a Prolog program is a collection of clauses of the
form
A :- B1, B2, ..., Bn.
where A and Bi's are atoms.
● :- replaces logic implication (usually written as )
● If the right hand side of a clause is empty, we simply write
A.
21
Another Example
Given a list of integers, get the sum.
We will define a predicate
sum(L,R)
Where L is a given list, and R will be used to hold the result.
For example, a query like
?- sum([3,5,2],Q)
to Prolog should return answer:
Q = 10.
22
Some of the basic elements of Prolog
Term
Fact statements
Rule statements
Term: A Prolog term is a constant, a variable, or a
structure.
A constant is either an atom or an integer.
Atoms are the symbolic values of Prolog and are
similar to their counterparts in LISP. In particular, an
atom is either a string of letters, digits, and
underscores that begins with a lowercase letter or a
string of any printable ASCII characters delimited by
apostrophes.
Fact statements: A fact statement is simply a
proposition that is assumed to be true.
For example:
female(khushi). , it states Khushi is a female.
mother(varsha, khushi). , it states Varsha is Mother of
Khushi
The fact is predicate that is true, for example, if we
say, “Tom is the son of Jack”, then this is a fact.
3. Rule Statements: Rule statements state rules of implication
between propositions.
For example: ancestor(varsha, khushi) :- mother(varsha, khushi).,
it states that if Varsha is the mother of Khushi, then Varsha is an
ancestor of Khushi.
Rules are extinctions of facts that contain conditional clauses. To
satisfy a rule these conditions should be met. For example, if we
define a rule as −
grandfather(X, Y) :- father(X, Z), parent(Z, Y)
Prolog program for sum
The program consists of two clauses
sum([ ],0).
sum([A|L], R) :- R is A+R1, sum(L,R1).
● R is A+R1 is Prolog’s way of saying “R is the result of A+R1.
● [A|L] is a notation for a list whose first element is A and the
rest of the list is L
● The two clauses read:
the first: the sum of an empty list is 0.
the second: the sum of the list [A|L] is the result of
adding A with the sum of L.
27
Execution
With the program:
sum([ ],0).
sum([A|L], R) :- R is A+R1, sum(L,R1).
You may post a query
?- sum([3,5,2],Q).
Prolog will answer: Q=10.
28
Summary
In logic programming,
● Programs are logic formulas of certain
form
● Computations are logic inferences.
29
