Transcript KNW_2004_3,4

Lectures 3,4
PROLOG
LOGic PROgramming
Logic: what is it?

Philosophical logic
– fundamental questions

Mathematical logic
– theory of correct reasoning

Computational logic
– effectiveness of reasoning

Language of scientific thinking
Logic Programming
Logic programming uses a form of
symbolic logic and a logical inference
process
 Languages based on symbolic logic
are called logic programming
languages or declarative languages
 Prolog is the most widely used logic
language

Predicate Calculus

Formal logic is the basis for logic programming
 Key Points
– Proposition:
• a logical statement that may or may not be true
– Symbolic logic used for three purposes
• express propositions
• express the relationships between propositions
• describe how new propositions may be inferred
– Predicate calculus is the form of symbolic logic
used for logic programming
Propositions
Atomic propositions

Objects in logic programming propositions
are
– Constants: symbols that represent an object
– Variables: symbols that can represent different
objects at different times

Atomic propositions are the simplest
propositions and consist of compound terms
– Compound term: an element of a mathematical
relation, written in form of function notation, which
is an element of the tabular definition of a function
Compound terms

Compound term has two parts
– Functor: symbol that names the relation
– An ordered list of parameters

Compound term with a single parameter is
called a 1-tuple; with two – a 2-tuple, etc.
 Example:
man (jake)
{jake} is a 1-tuple in relation man
like (bob, steak)
{bob, steak} is a 2-tuple in like
Facts and queries
Simple terms in propositions – man, jake,
bob, and steak – are constants
 These propositions have no intrinsic
semantics

– like (bob, steak) could mean several things

Propositions are stated in two modes
– Fact:
one in which the proposition is defined to be true
– Query:
one in which the truth of the proposition is to be determined
Logical operators
Name
Symbol
Example
Meaning

a
conjunction
 ()
ab
a and b
disjunction
 ()
ab
a or b
equivalence
 ()
ab
a is eqv to b
implication
 ()
 ()
ab
ab
a implies b
b implies a
negation
not a
Compound propositions

Compound proposition examples:
abc
abd

equivalent to (a ( b))  d
Precedence of logical connectors:

highest precedence
, ,  next
, 
lowest precedence
Quantifiers

Variables may appear in propositions –
only when introduced by symbols called
quantifiers
Name

Example Meaning
Universal X.P
For all X, P is true
existential X.P
There exists a value of
X such that P is true
Note: The period separates the variable
from the proposition
Quantifiers

Examples of propositions with quantifiers
– X.(woman(X)  human(X))
For any value of X, if X is a woman, then X is human
– X.(mother(mary, X)  male (X))
There exists a value of X, such that mary is the mother
of X and X is a male

Note: Quantifiers have a higher precedence
than any of the logical operators
Example of Logic 
Predicate Calculus

0 is a natural number.
natural (0)

2 is a natural number.
natural (2)

For all X, if X is a natural number, then
so is the successor of X.
X.natural (X)  natural (successor (X))
Logic Statement to P.C.
A horse is a mammal.
 A human is a mammal.
 Mammals have four legs and no arms,
or two legs and two arms.
 A horse has no arms.
 A human has arms.
 A human has no legs.

Solution:
First Order Predicate Calculus
mammal (horse).
 mammal (human).
 X. mammal (X)  legs (X,4) 
arms (X,0)  legs (X,2)  arms (X,2)
 arms (horse, 0).
 arms (human, 2) or  arms (human, 0).
 legs (human, 0).

Clausal forms
General statement

Redundancy is a problem with predicate
calculus
– there are many different ways of stating
propositions that have the same meaning
– not a problem for logicians

For computerized system, this is a problem
 Clausal form is one standard form of
propositions used for simplification:
B1  B2  ...  Bn  A1  A2  ...  Am
Meaning:
If all As are true, then at least one B is true
Characteristics






Existential quantifiers are not required
Universal quantifiers are implicit in the
use of variable in the atomic propositions
Only the conjunction and disjunction
operators are required
Disjunction appears on the left side of
the casual form and conjunction on the
right side
The left side is called the consequent
The right side is called the antecedent
Examples

Proposition 1:
likes (bob, trout)  likes (bob, fish)  fish (trout)

Meaning:
if bob likes fish and a trout is a fish, then bob likes trout

Proposition 2:
father(louis, al)  father(louis, violet)  father(al, bob)
 mother(violet, bob)  grandfather(louis, bob)

Meaning:
if al is bob’s father and violet is bob’s mother and
louis is bob’s grandfather, then louis is either al’s
father or violet’s father
Resolution
Proving theorems
One of the most significant
breakthroughs in automatic theoremproving was the discovery of the
resolution principle by Robinson in 1965
 Resolution is an inference rule that
allows inferred propositions to be
computed from given propositions

– Resolution was devised to be applied to
propositions in clausal form
Basic idea

The concept of resolution is the following:
Given two propositions:
P1  P2
Q1  Q2
 Suppose P1 is identical to Q2 and we rename
them as T. Then
T  P2
Q1  T
 Since P2 implies T and T implies Q1, it is
logically obvious that P2 implies Q1, that is
Q1  P2
Example

Consider the two propositions:
older (joanne, jake)  mother (joanne, jake)
wiser (joanne, jake)  older (joanne, jake)
 We can conclude that
wiser (joanne, jake)  mother (joanne, jake)
 The mechanics of this resolution construction
is one of cancellation of the common term
when both left sides are combined and both
right sides are combined
Expanded Example
father(bob, jake)  mother(bob,jake)
 parent (bob,jake)
 grandfather(bob,fred)
 father(bob,jake)  father(jake,fred)
 Resolution process cancels common
term on both the left and right sides:
 mother(bob,jake)  grandfather(bob,fred)
 parent (bob,jake)  father(jake,fred)

Most important laws

Unification: The process of determining
useful values for variables in propositions to
find values for variables that allow the
resolution process to succeed.
 Instantiation: The temporary assigning of
values to variables to allow unification.
 Inconsistency detection: A critically
important property of resolution is its ability to
detect any inconsistency in a given set of
propositions. This property allows resolution
to be used to prove theorems.
Horn clauses
Basics

When propositions are used for resolution,
only a restricted kind of clausal form can be
used
 Horn clauses
– special kind of clausal form to simplify resolution
– two forms:
• single atomic proposition on the left side, or
• an empty left side
– left side of Horn clause is called the head
– Horn clauses with left sides are called headed
Horn clauses
Relationships and facts

Headed Horn clauses are used to state
relationships:
likes(bob, trout)  likes (bob, fish)  fish(trout)

Headless Horn clauses are used to state
facts:
father(bob,jake)

Most propositions may be stated as Horn
clauses
Logic Programming
Brief history
Resolution principle (Robinson 1965)
 Prolog language (Colmerauer 1972)
 Operational semantics (Kowalski 1974)
 Prolog compiler (Warren 1977, 1983)
 5th generation project (Japan 1981--)
 Constraint LP (Jaffar & Lassez 1987)

Brief basics
Robert Kowalski says:
Algorithm = Logic + Control
 Prolog is the most popular logic
programming language
 A Prolog program is a collection
of Horn clauses

Declarative languages

Languages used for logic programming are
called declarative languages
 Programming with declarative languages is
nonprocedural
– programs do not state exactly how a result is to be
computed but rather describe the form of the result
– it is assumed that the computer can determine
how the result is to be obtained
– one needs to provide the computer with the
relevant information and a method of inference for
computing desirable results
Important issues

Program
– knowledge about the problem in the form
of logical axioms

Call of the program
– provide a problem description (as a logical
statement)

Execution
– attempt to prove the given statement
(given the program)

Constructive proofs essential
– can you prove sort([2,3,1], x)?
– non-constructive answer: “Yes I can”
– constructive answer: “Yes, with x = [1,2,3]”
PROLOG
Notation
English
Predicate Calculus
Prolog
and
 ()
,
or
 ()
;
only if
 ()
:-
not

not(...)
???
(query specification)
?-
Example

/* simple rules for deductions */
sees(X,Y):person(X),object(Y),open(eyes(X)),in_front_of(X,Y).
sees(X,Y):person(X),event(Y),watching(X,film_of(Y)).
person(mother(nikos)).
event(birthday(kostas)).
event(graduation(nikos)).
watching(mother(nikos),film_of(graduation(nikos))).
person(kostas). open(eyes(kostas)).
in_front_of(kostas,tv). object(tv).

/* questions */
/* does the mother of nikos see his graduation? */
?-sees(mother(nikos),graduation(nikos)).
General characteristics





A program uses terms such as constant
symbols, variables, or functional terms
Queries may include conjunctions,
disjunctions, variables, and functional terms
A program consists of a sequence of
sentences, implicitly conjoined
All variables have implicit universal
quantification
Prolog uses a negation as failure operator:
a goal not P is assumed proved if the
system fails to prove P
Basic elements
Terms

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
– Atoms begin with a lowercase letter

Variables begin with an uppercase letter
– not bound to types by declarations
– binding of a value and type is an instantiation
– Instantiations last only through completion of goal

Structures represent the atomic propositions
of predicate calculus
– form is functor (parameter list)
Fact statements

Fact statements are used to construct
hypotheses (database) from which new
information may be inferred
 Fact statements are headless Horn clauses
assumed true
 Examples:
male(bill).
female(mary).
male(jake).
father(bill, jake).
mother(mary, jake).
Rule statements
Rule statements are headed Horn
clauses for constructing the database
 The RHS is the antecedent (if), and
the LHS is the consequent (then)
 Consequent is a single term because
it is a Horn clause
 Conjunctions may contain multiple
terms that are separated by logical
ANDs denoted by commas, e.g.:

female(shelley), child (shelley).
Rule statements

General form of the Prolog headed Horn
clause
consequence_1 :- antecedent_expression

Example:
ancestor(mary, shelley) :- mother(mary, shelley).

Demonstration of the use of variables:
parent(X, Y) :- mother (X, Y).
parent(X, Y) :- father(X, Y).
grandparent(X, Z) :- parent(X, Y), parent (Y, Z).
sibling(X,Y) :- mother(M,X), mother(M,Y),
father(F,X), father(F,Y).
universal objects are X, Y, Z, M, and F
Goal statements

Because goal and some nongoal statements
have the same form (headless Horn clauses),
it is imperative to distinguish between the two
 Interactive Prolog implementations do this by
simply having two modes, indicated by
different prompts: one for entering goals and
one for entering fact and rule statements
 Some versions of Prolog use ?- for goals
Goal statements

Facts and rules are used to prove or disprove
a theorem that is in the form of a proposition
(called goal or query)
 Syntactic form of Prolog goal statement is
identical to headless Horn clauses, e.g.
man (fred).
to which the system will respond yes or no
 Conjunctive propositions and propositions
with variables are also legal goals, e.g.
father ( X, mike).

When variables are present, the system
identifies the instantiations of the variables
that make the goal true
Example

Database:
likes(george,kate).
likes(george,susie).
likes(george,wine).
likes(susie,wine).
likes(kate,gin).
likes(kate,susie).
Example

Query:
?-likes(george,X).
X = kate
;
X = susie
;
X = wine
;
no
Example

Database:
likes(george,kate). likes(george,susie).
likes(george,wine). likes(susie,wine).
likes(kate,gin). likes(kate,susie).
friends(X,Y) :- likes(X,Z), likes(Y,Z).

Query:
?- friends(george,susie)
yes
Inference process
General scheme

Goals (queries) may be compound
propositions; each of facts (structures) is
called a subgoal
 The inference process must find a chain of
rules/facts in the database that connect the
goal to one or more facts in the database
 If Q is the goal, then either Q must be found
as fact in the database or the inference
process must find a sequence of propositions
that give that result
Matching

The process of proving (or satisfying) a
subgoal by a proposition-matching process
 Consider the goal or query:
man (bob).

If the database includes the fact man(bob),
the proof is trivial
 If the database contains the following fact
and inference
father (bob).
man (X) :- father (X)
then Prolog would need to find these and
infer the truth. This requires unification to
instantiate X temporarily to bob
Matching

Consider the goal:
man(X).

Prolog must match the goal against the
propositions in the database
 The first found proposition with the form of
the goal, with an object as its parameter,
will cause X to be instantiated with that
object’s value and this result displayed
 If there is no proposition with the form of
the goal, the system indicates that the goal
can’t be satisfied
Solution search approaches

Depth-first
– Finds a complete sequence of propositions (a proof)
for the first subgoal before working on the others

Breadth-first
– Works on all subgoals of a given goal in parallel

Backtracking
– When the system finds a subgoal it cannot prove, it
reconsiders the previous one to attempt to find an
alternative solution and then continue the searchmultiple solutions to a subgoal result from different
instantiations of its variables
Backtracking example

Suppose we have the following compound goal:
?- male (X), parent (X, shelley)

Is there an instantiation of X, such that X is a
male and X is a parent of shelley?
 The search
– Prolog finds the first fact in the database with male as
its functor
– It instantiates X to the parameter of the found fact,
say john
– It attempts to prove that parent(john, shelley) is true
– If it fails, it backtracks to the first subgoal, male(X)
and attempts to satisfy it with another alternative to X

More efficient processing possible
Simple arithmetic

Suppose we know the average speeds of
several automobiles on a particular racetrack
and the amount of time they are on the track:
speed(chevy, 105).
speed(dodge, 95).
time(ford, 20).
time(chevy, 21).

We can calculate distance with this rule:
distance(X,Y) :speed(X, Speed), time(X,Time), Y is Speed * Time

Query
distance(chevy, Chevy_Dist).
will instantiate Chevy_Dist as 105*21 = 2205
Tracing
Tracing the process

Consider the following example:
likes(jake, chocolate).
likes(jake, apricots).
likes(darcie, licorice).
likes(darcie, apricots).
?-likes(jake,X), likes(darcie,X).

Trace Process:
(1)
(1)
(2)
(2)
(1)
(1)
(2)
(2)
Call:
Exit:
Call:
Fail:
Redo:
Exit:
Call:
Exit:
likes(jake, _0)?
likes(jake, chocolate)
likes(darcie, chocolate)?
likes(darcie,chocolate)
likes(jake, _0)?
likes(jake, apricots)
likes(darcie, apricots)?
likes(darcie, apricots)
X = apricots
Example
imokay :- youreokay,
hesokay
youreokay :- theyreokay
hesokay.
theyreokay.
hesnotokay :- imnotokay
shesokay :- hesnotokay
shesokay :- theyreokay
hesnotokay :- shesokay
shesokay
Example
imokay :- youreokay,
hesokay
youreokay :- theyreokay
hesokay.
theyreokay.
hesnotokay :- imnotokay
shesokay :- hesnotokay
shesokay :- theyreokay
hesnotokay :- shesokay
shesokay
Example
imokay :- youreokay,
hesokay
youreokay :- theyreokay
hesokay.
theyreokay.
hesnotokay :- imnotokay
shesokay :- hesnotokay
shesokay :- theyreokay
hesnotokay :- shesokay
shesokay
hesnotokay
Example
imokay :- youreokay,
hesokay
youreokay :- theyreokay
hesokay.
theyreokay.
hesnotokay :- imnotokay
shesokay :- hesnotokay
shesokay :- theyreokay
hesnotokay :- shesokay
shesokay
hesnotokay
Example
imokay :- youreokay,
hesokay
youreokay :- theyreokay
hesokay.
theyreokay.
hesnotokay :- imnotokay
shesokay :- hesnotokay
shesokay :- theyreokay
hesnotokay :- shesokay
shesokay
hesnotokay
shesokay
Example
imokay :- youreokay,
hesokay
youreokay :- theyreokay
hesokay.
theyreokay.
hesnotokay :- imnotokay
shesokay :- hesnotokay
shesokay :- theyreokay
hesnotokay :- shesokay
shesokay
hesnotokay
shesokay
LOOPS
List structures
Basics

Lists can be created with a simple structure:
new_list([apple, prune, grape]).
where new_list is a relation like male(jake)
 Prolog uses the special notation [ X | Y ] to
indicate head X and tail Y
 In query mode, the elements of new_list can
be dismantled:
new_list([New_List_Head | New_List_Tail]).
It instantiates
New_List_Head with apple
New_List_Tail with [prune, grape]
Append
append(([bob, jo], [jake, darcie], Family).
produces the output
Family = [bob, jo, jake, darcie]
and
Yes
Reverse
reverse ([bob, jo, jake, darcie], Rev_list).
prints
Rev_List = [darcie, jake, jo, bob]
and
Yes
Member
Member function is used to determine
if a given symbol is in a given list
 Example:

member( bob, [darcie, jo, jim, bob, alice]).
The system responds with
Yes
Performance control
Resolution order control

Prolog always matches in the same order:
starting at the beginning and at the left
end of a given goal
 Therefore, the user can affect efficiency
by ordering the database statements to
optimize a particular application
 If certain rules are more likely to succeed
than others during an execution, placing
those rules first makes the program more
efficient
Problems with control

The ability to tamper with control flow in a
Prolog program is a deficiency because it is
detrimental to one of the advantages of logic
programming: programs do not specify how
to find solutions
 Using the ability for flow control, clutters the
simplicity of logic programs with details of
order control to produce solutions
 Frequently used for the sake of efficiency
Negation
Example

Consider the following:
parent(bill, jake).
parent(bill, shelley).
sibling(X,Y) :- parent(M,X), parent(M,Y).
?-sibling(X,Y).

Prolog’s result is
X = jake
Y = jake
Example

Consider the following:
parent(bill, jake).
parent(bill, shelley).
sibling(X,Y) :- parent(M,X), parent(M,Y), not(X=Y).
?-sibling(X,Y).

Prolog’s result is
X = jake
Y = shelley
Problems with „not”
Logical „not” cannot be a part of Prolog
primarily because of the form of the Horn
clauses
B :- A1  A2  ...  Am
 If all the A propositions are true, it can be
concluded that B is true.
 But regardless of the truth or falseness of any
or all of the As, it cannot be concluded that B
is false.
 Prolog can prove that a given goal is true, but
it cannot prove that a given goal is false.

Applications
Logic Programming and RDBMS

RDBMs store data in tables and queries are
often stated in relational calculus
 Query languages are nonprocedural
 Obvious facility of Prolog to represent
tables(facts) and relationships between
tables(rules) with the retrieval process being
inherent in the resolution operation
 Advantages
– only a single language is required
– deductive capability is built in to the RDBMS with
inference rules
Expert Systems

Expert Systems are designed to emulate
human expertise. They consist of a database
of facts, an inference process, some
heuristics about the domain, and some
friendly human interface.
 Prolog provides the facilities of using
resolution for query processing, adding facts
and rules to provide the learning capability,
and using trace to inform the user of the
reasoning behind a given result.
Natural Language Processing

Forms of logic programming have been found
to be equivalent to context-free grammars to
describe language syntax
 Some semantics of natural languages can be
modeled with logic programming
 Research in logic-based semantics networks
has shown that sets of sentences in natural
languages can be expressed in clausal form
Education

Extensive experiments in using micro-Prolog
to teach children logic programming language
 Advantages
– introduces computation at an early age
– teaches logic which results in clearer thinking and
expression
– assists students with mathematics and other
subjects

Experiments have produced an interesting
result:
– it is easier to teach logic programming to a
beginner than to a programmer with a significant
amount of experience in an imperative language