Transcript Logic Programming Languages

Logic Programming
Tarik Booker
What will we cover?
 Introduction
 Definitions
 Predicate
Calculus
 Prolog
 Applications
What is Logic Programming?
 Simply
programming that uses a form of symbolic
logic (predicate calculus) as a programming
language
 Languages
based on this type of programming are
called Logic Programming Languages
 (Also
known as declarative languages)
Definitions (1)
Predicate Calculus:
 Proposition – a logical statement that may or may
not be true
 Atomic
– consist of compound terms
 Compound Terms
– element of a mathematical
relation
– function symbol that names the relation
 Ordered list – parameters
 Functor
man(bob)
like(bob, steak)
Definitions (2)
Clausal Form: B1  B2  B3  A1  A2  A3
– right side of a clausal form
 Consequent – left side of a clausal form
 Antecedent
Semantics – there is a simple way to
determine the meaning of each statement
 Declarative
Prolog
Logic Programming Language
 Definitions:

Term – a constant, variable or structure
 Constant – only an atom (synbolic value) or an integer
 Variable – any string of letters, digits, or underscores that begins
with an uppercase letter
 Structure – atomic propositions of predicate calculus



Ex: mystruct(parameter list)
Instantiation – a binding of a value to a variable
Sample Prolog (Fact Statements)
Fact Statements:
 male(bill).
 male(jack).
 father(bill,
jack).
Which is Correct?
 Bill
is Jack’s father?
 Jack is Bill’s father?
(Answer)
 Either
way!
 There are no intrinsic semantics in Prolog (just like
Predicate Calculus)
 Can be interpreted by the programmer in any way
he/she likes.
Sample Prolog (Rule Statements)
 Consequence_1
:- Antecedent_expression
 Examples:
 female(shelley),
child(shelley).
 ancestor(mary, shelley) :- mother(mary, shelley).
(If Mary is the mother of Shelley, then Mary is the
ancestor of Shelley)
Goal Statements
 Queries
are known as goals in Prolog.
 Example:
father(jason, freddy).
father(X, freddy).
Inferencing
 You
want a goal.
 When the goal is a compound proposition, each of
the facts (structures) is called a subgoal
 To prove a goal is true, the inferencing process
muse connect the goal to one or more facts in the
database
 Proving a subgoal is known as satisfying the
subgoal
Inferencing Example

Database contains:
father(bob).
 man(X) :- father(X).


Your goal (query):

man(bob).
Forward Chaining – bottom-up resolution (start with facts,
find goal)
 Backward Chaining – top-down resolution(start with goal,
find facts)

Inferencing (2)
Forward Chaining: better when the number of possible
correct answers is large
 Backward Chaining: better when there is a reasonable
small set of candidate answers
 When goal has more than one structure, we must search:

Depth-first – finds a proof for the first subgoal beforw working
on the others
 Breadth-first – works on all subgoals in parallel
 Prolog uses depth-first, because it utilizes fewer resources
 Backing up in a goal to a previously proven subgoal is known as
backtracking

Applications of Logic Programming
 Relational
Database Management Systems
 Expert Systems – emulate human expertise in
some particular domain
 Natural Language Processing
Resources Used
Sebesta, Robert W.
Concepts of Programming Languages
(4th Edition)