Knowledge Representation, Reasoning and Inference

Knowledge Representation, Reasoning and Inference

Q1.             Give ONE (1) own example for each of the followings:

a.                  Priori knowledge

b.                  Posteriori knowledge

c.                   Tacit knowledge

d.                  Explicit knowledge

e.                  Declarative knowledge

A1. 

a. Knowledge that are universally true, hence they cannot be denied. e.g. All dead will decay.

b. Knowledge that are derived from senses, and they can be true or false e.g. All nice smelling food taste sweet.

c. Unconscious knowledge that cannot defined or expressed in languages e.g. heart breathing, eye blinking

d. Documented knowledge found in books e.g. Economic theories, History of Malaysia.

e. Passive knowledge expressing facts about world e.g. the sun rises in the East.

Q2.             Besides the techniques you have learned in class, knowledge can also be represented in a form of decision table and decision tree.  Explore these two techniques and describe them (if necessary, give examples) in one page length.

A2.

 Fig. 2.0: Typical diagram of a developed Decision table.

Steps to create a Decision table are summarily given as follows:

1.      List all causes in the decision table. 2.  Calculate the number of possible combinations. 3. Fill columns with all possible combinations. 4. Reduce test combinations. 5. Check covered combinations. 6. Add effects to the table.

(NOTE: The adequate information to work on using this technique will be provided)

Application areas of Decision table are: Business Analysis, Programming, Testing, Hardware Design, etc.

Decision tree is a tree-like diagrammatic expression drawn to classify any object (information given) with a view of making decision from the result. It is also one of the techniques in representing knowledge. It aids decision especially when there is a need to plan and organise a sequence of decision and take into account how the choices made at earlier stages and the outcome of possible external events determine the types of decisions and events at later stages of that sequence.  In this technique, the classification is done by testing for the values of certain properties associated with the given information.

Decision tree consists of three nodes (points), with distinctive shapes which give different meaning:

1.      Decision node is represented by square; this is a point when decision has to be taken.

2.      Chance/ Uncertainty node is represented by circle; this is an external event which has an uncertain result.

3.      Result node is represented by triangle; this is the end point of the analysis giving the result of the steps earlier taken.

Q1.           Q3.  Create a frame-based representation for object vehicle.  You must have one super class and two instances.  You are free to determine the slots but their numbers must be 10. The slots must be a combination of single and multi-facets slots.  Your instances must not have the same facets for all slots, however, similarities are allowed to some of the slots.  Your representation must also show that the instances inherit some of their parent’s properties.  At the same time, they must also have their unique properties.

 Q4.             Consider the following story:

”All people that are not poor and are smart are happy.  Those people that can read are smart.  John is wealthy.  Helen can read and is wealthy.  Happy people have exciting lives.  Wealthy people are not poor”. 

a.                  Translate the story into predicate calculus expressions.

b.                  Find someone with an exciting life using the expressions in (a).

A4. a

1.      ᵾW(people(W) ʌ ¬are(W,poor) ʌare(W,smart)→are (W,happy)

2.      ᵾX(people(X) ʌ can(X,read) → are(X,smart)

3.      is(john,wealthy)

4.      can(helen,read) ʌ is(helen,wealthy)

5.      ᵾY(people (Y) ʌare(Y,happy)) → have(Y,exciting_lives)

6.      ᵾZ(people (Z) ʌ are(Z,wealthy)) → ¬are(Z,poor)

b.

Starting from statement 1:

ᵾW(people(W) ʌ ¬are(W,poor) ʌare(W,smart))→are (W,happy)

with statement 2 made above, we can say: W;X / X;W, also with the rule made, we can now have:

ᵾX(people(X) ʌ¬are(X,poor) ʌcan(X,read)) → are(X,happy)

with statement 5 made above, we can say X;Y/ Y;X, also with the rule made, we can now have:

ᵾY(people(Y) ʌ¬are(Y,poor) ʌcan(Y,read)) → have(Y,exciting_lives)

with statement 6 made above, we can say Y;Z / Z;Y, also with the rule, we can now have:

ᵾZ(people(Z) ʌare(Z,wealthy) ʌ can(Z,read)) →have(Z,exciting_lives)

with statement 4 made above, we can say Z;helen, so we can now have:

is(helen,wealthy) ʌ can(helen,read) → have(helen,exciting_lives)

So, Helen is the someone with exciting life. 

   Q5.             The following story is quoted from N. Wirth’s “Algorithms + data structures = programs” (Wirth, 1976).

“I married a widow (lets call her W) who has a grown-up daughter (call her D).  My father (F), who visited us quite often, fell in love with my step-daughter and married her.  Hence my father became my son-in-law and my step-daughter became my mother.  Some months later, my wife gave birth to a son (S1), who became the brother-in-law of my father, as well as my uncle.  The wife of my father, that is, my step-daughter, also had a son (S2).”

Create a set of predicate calculus expressions that represent the above situation.  Add expressions defining basic family relationships, e.g. the definition of father-in-law.  Use Modus Ponens to prove the conclusion that “I am my own grandfather”.

A5.

marry (I,W) ʌ mother(W,D) → step_daughter(I,D)

(fell_in_love(F,D) ʌ marry (F,D)) → (son_in_law(F,I) ʌ mother (D,I))

give_birth(W,S1) → brother_in_law(S,F) ʌ uncle (S,I)

give_birth(D_S2)

grandmother (W,S2)

grandfather(I,I)

           Q6.             You are given some facts as below:

ride(tom,bicycle) ride(X,scooter) ride(X,Y) ride(tom,Scooter,yellow) ride(tom,Y)

Explain, in your own words, the meaning of unification.  Your explanation should reflect your understanding on both pattern matching and instantiation concepts.  You can only use the predicates given above as examples in your explanation.  You may use some or all the predicates.

1.ride(tom,bicycle) 2.ride(X,scooter) 3.ride(X,Y) 4.ride(tom,Scooter,yellow)  5.ride(tom,Y)

A6.  Unification is one of the reasoning and inference concepts; it encompasses the other two concepts which are: Pattern matching and Instantiation. This means before we can conclude that two predicates unify they must have been pattern matched and /or instantiated. Looking at the set of facts/ predicates given below:

Considering predicate number 1 and 3; since both have identical string of symbol; ‘ride’, then both are said to match. Hence, X and Y can be instantiated with constants; tom and bicycle respectively. Conclusively, we say both predicates unify. This is also applicable to predicate number 2 and 5.

Q7.             Consider the rules and facts below: 

(1)     eats(X, meat) Ù walks_on(X, 2_legs) ® is(X, theoropoda)

(2)     eats(X, plant) Ù walks_on(X, 4_legs) ® is(X, sauropoda)

(3)     eats(X, plant) Ù walks_on(X, 2_legs) ® is(X, ornithopoda)

(4)     (is(X, sauropoda) Ú is(X, theoropoda) Ù similar_to(hipbones, modern_crocodiles) ® is(X, saurischia)

(5)     is(X, ornithopoda) Ù resemble(of(hipbones,X), of(hipbones,modern_birds)) ® is(X, ornithischia)

(6)     eats(dino, meat)

(7)     eats(dino, plant)

(8)     walks_on(dino, 2_legs)

(9)     resemble(of(hipbones,dino), of(hipbones,modern_birds))

a.                  Convert the above rules into clausal forms.

b.                  Use resolution to prove that the Dino is an Ornithischia.

 A7. a

1.      ¬ eats(X,meat) ᴠ ¬ walks_on(X,2_legs) ᴠ is(X,theoropoda)

2.      ¬ eats(X,plant) ᴠ ¬ walks_on(X,4_legs) ᴠ is(X,sauropoda)

3.      ¬ eats(X,plant) ᴠ ¬ walks_on(X,2_legs) ᴠ is(X,ornithopoda)

4.       ¬ is(X,sauropoda) ᴠ ¬similar_to(hipbones,modern_crocodiles) ᴠ is(X,saurischa)

5.      ¬ is(X,theoropoda ᴠ ¬similar_to(hipbones,modern_crocodiles) ᴠ is(X,saurischa)

6.      ¬ is(X,ornithipoda) ᴠ ¬ resemble(of(hipbones,X), of(hipbones,modern_birds)) ᴠ is(X,ornithischia)

7.        eats(dino,meat)

8.         eats(dino,plant)

9.         walks_on(dino,2_legs)

10.    resemble(of(hipbones,dino), of(hipbones,modern_birds))

b.

(a)   Resolution to prove that Dino is an Ornithischia: is(dino,ornithischia)

The goal is:   ¬ is(dino,ornithischa)

OVERVIEW OF PROLOG

OVERVIEW OF PROLOG

·         INTRODUCTION

·         A FIRST LOOK AT PROLOG

·         THE BASIC OF PROLOG

·         BASIC DATA STRUCTURES

·         FACTS

·         QUESTIONS

·         VARIABLES

·         RULES

·         MORE ON PATTERN MATCHING (UNIFY)

·         BACKTRACKING

·         DECLARATIVE AND PROCEDURAL VIEWS OF PROLOG  PROGRAMS

·         RECURSION

INTRODUCTION

Prolog stands for PROgramming in LOGic.

The language originated at the University of Marseille in about 1970 by a mathematician Alain Colmerauer with the initial purpose of translating natural languages.

In 1977, David Warren of the University of Edinburgh successfully implemented a very efficient version of Prolog, called Prolog-10 (also known as Edinburgh Prolog). Warren’s various experiments on Prolog-10 demonstrated the power of Prolog in many applications, ranging from sophisticated artificial intelligence applications to productive software engineering.

In 1983, Japan published plans for ambitious national project involving the design production of fifth generation computers, for which Prolog was chosen as the fundamental system language.

Today, Prolog is a very important tool in programming artificial intelligence applications and in the development of expert systems.

The demand for more "user friendly" and intelligent programs is another reason for Prolog's growing popularity.

A FIRST LOOK OF PROLOG

A prolog program consists of a set of facts and a set of rules.

There are no type declarations, initializations or any other stuff like that. Just some facts and rules.

Some prolog facts are:

   lectures(alison, ai).

   lectures(john, databases).

   female(alison).

   age(alison, 29).                       

   office(alison, s134).

   animal(lion).

   animal(sparrow).

   has_feathers(sparrow).

Facts consist of:

• A predicate name (or functor) such as lectures, female, and office. This must begin with a lower case letter.
• Zero or more arguments, such as alison, ai3, and s134.

Note that facts (and rules, and questions) must end with a full stop.

Some prolog rules are:

bird(X) :-

     animal(X),

     has_feathers(X).

grandparent(X, Y) :-

     parent(X, Z),

     parent(Z, Y).

Note:

1.    That variables are NOT treated in the same manner as in conventional programming languages - for example, they don't have to have values.

2.    Any constant should NOT begin with a capital letter else it will be treated as a variable. So, given the fact capital(Scotland, Edinburgh) both arguments would be treated as unbound variables.

Running a prolog program involves asking Prolog questions (having loaded in your set of facts and rules). For example, you could ask:

   ?- lectures(alison, ai).

And prolog would give the answer ``yes''. If we ask a sequence of questions we might get:

   ?- lectures(alison, ai).

   yes

   ?- lectures(alison, databases).

Questions can have variables in them, which may get instantiated (ie, get bound to particular values) when prolog tries to answer the question. So we might have:

   ?- lectures(alison, Course).

   Course = ai

We can also ask the question the other way around, like:

   ?- lectures(Someone, ai).

   Someone = alison

Note that the variables Course and Someone can both take values of any type.

We can find out who lectures what by asking:

   ?- lectures(Someone, Something).

   Someone = alison

   Something = ai ;

   Someone = john

   Something = databases ;

   no

By typing a semicolon after Prolog prints out the first set of bindings, we can see if there are any other possible bindings.

Prolog systematically goes through all its facts and rules and tries to find all the ways it can associate variables with particular values so that the initial query is satisfied.

However, as an example of how rules are used, suppose we ask the question:

   ?- bird(B).

and we have the facts and rule:

   animal(lion).

   animal(sparrow).

   has_feathers(sparrow).

   bird(X) :-

     animal(X),

     has_feathers(X).

Prolog will respond with

   B = sparrow.

Prolog matches bird (B) against the head of the rule (bird(X)), and sets as new questions first animal(B) and that has_feathers (B).

Animal(B) can be satisfied by binding B to lion.

However, has_feathers(lion) isn't true, so that doesn't work.

Prolog goes back (backtracks) and tries B = sparrow. has_feathers(sparrow) is true, so that all works and prolog returns with B = sparrow as a possible solution.

THE BASIC OF PROLOG

Prolog is a computer language for solving problems involving objects & the relationships between objects.

Prolog allows good reasoning about objects & their relationships.

Prolog is a language for symbolic, non-numeric programming

Nature of Prolog

• the Prolog programming language is based on three main concepts:

·         pattern matching

·         tree-based data structuring

·         automatic backtracking

Elements of Prolog

• basic elements: facts, questions, variables, conjunctions and rules -clauses.
• advanced elements: lists and recursion.

Programming in Prolog

Computer programming in Prolog consists of:

• declaring facts about objects and their relationships
• defining some rules about objects and their relationships
• asking questions about objects and their relationships

Consider Prolog as a store of facts and rules which are used to answer questions.

So that programming in Prolog consists of supplying all the facts and rules and then making inferences from fact to another.

BASIC DATA STRUCTURES

The fundamental data structure in Prolog is the term. Prolog terms include:

a. Atoms

such as sparrow, x, 'Alison Cawsey', a102, -. These generally represent specific single entities in the world and cannot be separated into parts. They normally begin with a lower-case letter, but arbitrary characters can be used if they are quoted. Symbols (such as ``-'') and sequences of symbols (e.g., ``:-'') are also atoms.

b. Numbers

such as 29, 1.2, 3000, -2.

c. Variables

such as X, Person, _Var. Variables begin either with a capital letter or an underline character.

d. Structured Objects:

such as:

book(title(lord_of_the_rings), author(tolkien))

bicycle(owner(alison), parts(gears(number(18), type(shimano))))

The full stop makes a term a clause.

FACTS

A fact describes the relationship between some objects. e.g.

             likes(michael, chocolate).

             owns(michael, house, car, tv, hi_fi).

Syntax for Facts

• names of relationships & objects must be atoms.
• the relationship is written first then the objects
• the full stop character, '.' must come at the end of a fact

Order of Objects

• order is arbitrary BUT once given takes on a meaning - must be consistent
• likes(michael, chocolate) is not the same as likes(chocolate, michael).

   

fact                                          possible interpretation

valuable(gold).                         gold is valuable

female(jane).                           Jane is female

gives(joe, money, michael).      Joe gives (the) money to Michael

QUESTIONS

Once we have some facts, we can ask questions about them.

Asking

A question has the same form as a fact but with a question mark and hyphen in front. e.g.

     ?- likes(michael, chocolate).    (does Michael like chocolate?)

Answering

Prolog answers a query using the following procedure:

• Prolog searches the database (its facts base)
• Prolog looks for facts that match the fact in the question
• if a match is found - Prolog answers yes else Prolog answers no

Matching

Two facts match if:

• their predicates are the same and
• their corresponding arguments are the same

Given the facts:

likes(michael, chocolate).

likes(michael, cake).

likes(mary, chocolate).

likes(michael, gina).

doesnt_like(gina, michael).

we can pose the following questions and get the corresponding answers:

?- likes(gina, michael).

no

?- likes(michael, money).

no

?- likes(michael, cake).

yes

Note that an answer of 'no' doesn't mean false.

An answer of 'no' means Prolog doesn't know, i.e. it can't answer the question as being true.

Maybe Michael does like money but Prolog doesn't have any facts to match that.

Note that the fact doesnt_like(gina, michael) is not a match to the question.

The predicates 'likes' and 'doesnt_like' are not the same and Prolog has no way of telling that 'doesnt_like' is equivalent to not('likes'). So that it is possible to have two facts:

          likes(gina, michael).

          doesnt_like(gina, michael).

VARIABLES

When we do not want to specify a particular object but wish to cover arange of such objects we can use a variable.

For example, it would be tiresome to ask:

          does Michael like Gina?

does Michael like Joan?

does Michael like Ann? .....

It would be more sensible to ask:

             who/what does Michael like?

In Prolog this would be phrased as:

             does Michael like X?

Prolog then determines what X is.

Instantiation

A variable may be instantiated or uninstantiated. A variable is instantiated when there is an object for which the variable stands.

Syntax

A variable starts with a capital letter.

Matching

We can pose a question using a variable but a variable cannot be used for the relationship, i.e. the predicate. We can't ask

        ?- X(michael, ann).

When asked a question containing a variable, Prolog:

• searches the database for a fact that matches the question by matching the predicates
• instantiates the variable by matching it (binding it) to a corresponding argument in the fact

Using the above facts we can ask

?- likes(michael, Something).   (does Michael like Something?)

Prolog answers:

Something = chocolate

and waits for further instructions.

Order of Searching

Prolog searches for facts in the order they occur in the database. Usually that is the order in which they are typed.

So in the above example, the fact likes(michael, chocolate) is found first.

The variable Something now stands for chocolate, i.e. Something is instantiated to chocolate.

Finding More Matches

After finding a match, we said that Prolog waits for instructions.

If we want more matches we type in a semi-colon, ';' followed by a CR (return).

Prolog then resumes its search from where it left off.

It attempts to re-satisfy the question. If it is successful the variable will be instantiated to a new value.

Example:

?- likes(X, chocolate).  (What likes chocolate?)

X = michael; first answer - we type ';'

X = mary; second answer - we type ';'

no (means no more answers)

Anonymous Variable

Suppose we want to find out whether Hezel is a mother but we don’t care whose mother she is.

?- mother(hazel,_).

The underscore stands for Anonymous Variable.

What is Anonymous Variable?

a.    a special variable that matches everything, but never takes on a value.

b.    Never printed out in response to a query

c.    Sucessive anonymous variables in the same clause do not take on the same value; they behaves as different variables.

When to use Anonymous Variable?

         

Whenever a variable occurs only once in a clause and its value is never put to any use.

Example:

is_a_grandmother (X) :-

          mother(X,Y),

          parent(Y,Z).

is exactly equivalent to:

is_a_grandmother (X) :-

          mother(X,Y),

          parent(Y,_).

But is less work for the computer because no value need be assigned to the anonymous variable.

X and Y cannot be replaced with A.V. because each of them has to occur in 2 places with the same values.

Exercise 1.1:

1.  Blue_eyed_non_grandparent(X) :-

            blue_eyed(X),

            not (parent(X,Y),parent(Y,Z)).

     Put A.V. in the approriate place.

2.    Why isn't the following a proper defn of grandparent?

   Grandparent (G,C) :- parent(G,_), parent (_,C).

Conjunctions

Usually we want to ask questions about more complex relationships.

Given the facts:

size(bear, big).

size(elephant, big).

size(mouse, small).

colour(bear, brown).

colour(mouse, grey).

colour(elephant, grey).

we may want to ask

What is it that is big and grey?

Asking Complex Questions

The above question may be formulated as:

What something has size = big where that something also has colour = grey?

In Prolog, with the above facts, this would take the form

             ?- size(X, big), colour(X, grey).

This question has two goals, which are separated by a comma. The comma is pronounced as and. It stands for the conjunction of goals and may be used to separate any number of goals.

The answer to the above question will be:

             X = elephant

On the other hand, the answer to the question:

             ?- size(X, small), colour(X, brown).

will be: ?

RULES

If something depends on a group of facts then we can express this as a rule. In Prolog a rule has the form:

        goal (is true) if subgoals (are all true)

Examples:

I get up if it is a working day and it is later than 7.00 a.m. I stay in bed if it is a weekend and it is earlier than 10 a.m. it is a bird if it is an animal and it has feathers

Syntax and Terminology

A rule in Prolog has the following syntax:

     gaol(goal_arguments) :-

                   subgoal1(subgaol1_arguments),

                   subgoal2(subgaol2_arguments),

                   ...

                   subgoaln(subgaoln_arguments).

The left-hand side (LHS) or conclusion of a rule is called the head of the rule whereas the right-hand side (RHS) or conditions is called the body of the rule.

The head and the body are separated by the if symbol, i.e. the colon and hyphen, ':-'.

A rule must be terminated by a full stop.

The placing of the conditions in the body on separate lines is for formatting only and does not affect the running of Prolog.

Given the above rule examples the Prolog form could be:

action(get_up) :- 

      day_of_week(weekday),

      time(T),

      T > 7.0.

action(stay_in_bed) :-

day_of_week(weekend),

time(T), T < 10.0.

bird(X) :-

animal(X),

has_feathers(X).

Note that a variable in the same rule stands for the same object. Variables are local to rules.

That is, variables in different rules stand for objects determined by the rule.

So that the same symbol, e.g. 'X' used in different rules may stand for different objects.

In the above rule examples, the variable 'T' is instantiated from a match with the fact time(T) where 'T' will have some value.

Also note that where an expression uses a variable whose value is to be evaluated or used in a computation, that variable must be instantiated before use.

Uses Of Rules

Rules may be used to express definitions as in:

             X is a bird if:

                          X is an animal and

                          X has feathers

with the Prolog form as given previously

X is a sister of Y if:

X is female and X and

Y have the same parents

with a Prolog form as follows:

sister(X, Y) :-

female(X),

parents(X, M, F),

parents(Y, M, F),

not(X = Y). (this is necessary to prevent someone

 being their own sister)

Truth Relationships

Rules may be used to express inverse truth relationships as in:

             X is false if:

                          X is not true

with a Prolog form as follows:

false(X) :-

not(X).

or alternatively

false(X) :-

X,

fail.

false(_).

doesnt_like(X, Y) :-

not(likes(X,Y)).

Note however that the above expressly states that if X likes Y is false then X doesn't like Y.

There is no taking into account that X may be indifferent to Y.

Causality Relationship

Rules may be used to express causal relationships as in:

X rusts if:

   X is steel and

  X exposed to water and oxygen

with a Prolog form as follows:

rusts(X) :-

steel(X),

exposed_to(X, water),

exposed_to(X, oxygen).

Spatial Relationships

Rules may be used to express spatial relationships as in:

             block A is on top of block B:

                          block A is above block B and

                          block A and block B are face-to-face

with a Prolog form as follows:

on_top(block(A), block(B)) :-

above(block(A), block(B)),

touching(block(A), block(B)).

MORE ON PATTERN MATCHING (UNIFY)

As we have seen, Prolog tries to prove (answer) a query by looking for facts which match that query, or rules whose heads match the query and whose body can be proved. The way prolog matches terms is therefore crucial.

Example:

             book(title(programming_in_logic), author(bratco)).

             famous (bratco).

             has_famous_author(Title) :-

                          book(title(Title), author(Author)),

                          famous(Author).

and asked the query:

   ?- has_famous_author(programming_in_logic).

matches:

book(title(programming_in_logic), author(bratco))

with bindings:

      Name   = programming_in_logic

      Author = bratco

Prolog matches expressions in a purely structural way, with no evaluation of expressions, so:

     ?- 1+2 = 3

     no

[Note: In prolog ``='' means ``matches with''. ]

Similarly the following won't match, as the two expressions have different structures:

    ?- X + 2 = 3 * Y.

    no

However, the following match as they have the same structure:

    ?- X+Y = 1+2.

    X = 1

    Y = 2

    ?- 1+Y = X + 3.

    X = 1

    Y = 3

Note that there can be variables in both sides of a matched expression, as in the second example above.

For non-arithmetic examples, we have:

    ?- lectures(X, ai) = lectures(alison, Y).

    X = alison

    Y = ai

    ?- book(title(X), author(Y)) = book(Z, author(bratco)).

    Z = title(X)

    Y = tolkien

(Actually, in prolog you'd get something looking a bit more complex in response to the above query, with maybe Z = title(_0) and X = _0, as prolog creates its own internal variables. This is equivalent to the bindings given above.)

Of course, prolog will normally be doing lots of matches in a row, as it tries to prove different subgoals in a rule. It then needs to use the variable bindings obtained in the matches so far when it does the next match. So we might have:

    ?- X+Y = 1+5, X=Y.

    no

[Note: We can ask several queries in a row, with a comma in between them, just like in the body of a Prolog rule.]

X and Y get instantiated (bound) to 1 and 5 respectively in the first match (X+Y = 1+5), so the second match is effectively 1=5, which fails. However, the following will succeed:

    ?- X+Y = 1+5, Z = X.

    Z = 1

    Y = 5

    X = 1

    ?- book(author(X)) = book(author(bratco)),

       famous(X) = famous(bratco).

       X = tolkien

    ?- X=Y, Y = alison.

    X = alison

    Y = alison

Note that if two uninstantiated (unbound) variables are matched (and therefore instantiated to each other) then as soon as one becomes instantiated to some term then the other automatically becomes instantiated to that term.

BACKTRACKING

Given a query to prove (answer), Prolog goes down its list of facts and rules, from top to bottom, looking for facts or rule heads which match the query (given any existing variable bindings).

When it finds one, it stores the place in the fact/rule base it had got to in its search, so if the first match it finds is no good it can carry on and look for more possibilities. So, suppose we have the facts:

    bird(type(sparrow), name(steve))).

    bird(type(penguin), name(tweety))).

    bird(type(penguin), name(percy)).

and give the query:

 ?- bird(type(penguin), name(X)).

Prolog will first try matching the query with the first fact, but fail because sparrow doesn't match penguin.

It will then try matching with the second fact, and succeed with X = tweety.

However, it will put a pointer to the place it got to, so if it turns out that a later query/subgoal fails, it will go back to the saved position, and look for more solutions (ie, X = percy).

So, if we had a fact/rule base such as:

    animal(leo).

    animal(tweety).

    animal(percy).

    animal(peter).

    has_feathers(percy).

    has_feathers(peter).

    tame(peter).

    bird(X) :-

             animal(X),

             has_feathers(X).

   

    tame_bird(X) :-

             bird(X),

             tame(X).

and gave the query

    ?-  bird(Bird)

The following are the steps in staisfying the query:

1.       Prolog would go down the facts and rules until it reached the first rule, and would match bird(Bird) against bird(X).

2.       The variable Bird would then be instantiated to the variable X.

3.       Prolog then tries to prove the body of the rule. The subgoal animal(X) succeeds with X=leo. Prolog keeps a pointer of how far its got in checking for animal(X), and tries has_feathers(leo).

4.       It goes down the facts/rules looking for one that matches, but doesn't find anything. It therefore goes back to the last thing it tried to match (animal(X)), starts from where it left off, and matches with animal(tweety). But has_feathers(tweety) still doesn't match.

5.       So it goes back again and finds animal(percy). has_feathers(percy) matches, so the whole thing succeeds, with final bindings Bird = percy.

Now, if we give the query:

     ?- tame_bird(B),

Things get a little more complex.

1.    Prolog first tries to satisfy bird(X) as above. But then tame(percy) fails.

2.    It therefore has to try to resatisfy bird(X). It will do this by first trying to resatisfy has_feathers(percy) as that was the last goal it tried. But there is no other way of satisfying it.

3.    So it goes back yet again to animal(X), finding X = peter. has_feathers(peter) succeeds, so bird(X) can succeed a second way with X = peter.

4.    tame(peter) succeeds, so tame_bird(B) succeeds with B = peter.

In the above example, prolog is just bactracking through facts.

But in general there may be more than one rule which prolog could try, for example:

    animal(percy).            % fact1

    has_feathers(percy). % fact2

    penguin(tweety).        %fact3

    penguin(peter).                % fact4

    tame(peter).                     % fact5

    bird(X) :-                             % rule1

       penguin(X).              

    bird(X) :-                             % rule2

       animal(X),

       has_feathers(X).

    tame_bird(X) :-                  % rule3

       bird(X),

       tame(X).

Given a query:

?- bird(B).

1.       prolog would first use the first rule (and third fact) and get B=tweety.

2.       If it then had to backtrack it would match penguin(X) with the fourth fact to get B = peter.

3.       If it bactracks again it will run out of penguin clauses so have to try the second bird rule, and (using the first and second fact) get B = percy.

You can type a ``;'' (or click on ``next'') to force backtracking, we get:

   ?- bird(B).

   B = tweety ;

   B = peter ;  

   B = percy ;

   no

BACKTRACKING AND RE-SATISFYING

HOW PROLOG WORKS

Given the facts:

             size(bear, big).

             size(elephant, big).

             size(mouse, small).

             colour(bear, brown).

             colour(mouse, grey).

             colour(elephant, grey).

             eats(bear, honey).

             eats(mouse, cheese).

             eats(elephant, peanuts).

            

if we ask

?- colour(X, grey), size(X, big), eats(X, N).

Prolog will proceed as follows:

1.        it will match the first goal, colour(X, grey), to the fact colour(mouse, grey)

2.        goal colour(X, grey) succeeds

3.        the variable X is instantiated to mouse, i.e X = mouse

4.        it will proceed to the next goal, size(mouse, big), and try to match it to a fact

5.        this goal, size(mouse, big), fails, there is no match

6.        Prolog returns to the previous goal, colour(X, grey)

7.        the variable X is uninstantiated and an attempt is made to resatisfy the goal colour(X, grey)

8.        the goal now matches the fact colour(elephant, grey)

9.        goal colour(X,grey) succeeds

10.     the variable X is instantiated to elephant, i.e X = elephant

11.     it proceeds to the next goal, eats(elephant, N)

12.     it tries to match it to the fact eats(elephant, N)

13.     this goal succeeds, it matches the fact eats(elephant, peanuts)

14.     the variable N is instantiated to peanuts, i.e N = peanuts

15.     the conjunction succeeds, X = elephant and N = peanuts

Exercise 1.2  (terms, matching and backtracking)

1.  Which of the following are valid Prolog terms:

·         23

·         foo(X, bar(+(3,4)))

·         Foo(x)

·         +(fred, jim)

·         1+2.

·         Alison Cawsey

2.      Which of the following match, and for the ones that match, what are the resultant bindings.

·         a(1, 2) = a(X, X).

·         a(X, 3) = a(4, Y).

·         a(a(3, X)) = a(Y).

·         1+2 = 3.

·         X = 1+2.

·         a(X, Y) = a(1, X).

·         a(X, 2) = a(1, X).

3.      For the following (silly) program, state what order the solutions will be returned given the query flies(X). (Your answer should be of the form X=soln1; X=soln2; etc).

  aeroplane(concorde).

  aeroplane(jumbo).

  on(fred, concorde).

  on(jim, no_18_bus).

  bird(percy).

  animal(leo).

  animal(tweety).

  animal(peter).

  has_feathers(tweety).

  has_feathers(peter).

  flies(X) :- bird(X).

  flies(X) :- aeroplane(X).

  flies(X) :- on(X, Y), aeroplane(Y).

 

  bird(X) :- animal(X), has_feathers(X).

Once you have worked out the answers by hand, check them using Prolog.

DECLARATIVE AND PROCEDURAL VIEWS OF PROLOG PROGRAMS

There are generally two ways to look at any Prolog rule - as a

a.      declarative statement about what is true, or

b.      procedural statement about how to do something.

Declarative statement is concerned only with the relations defined by the program.

Procedural statement determines how this output is obtained ie. how the relations are evaluated.

One of the claimed advantages of Prolog is that it is often possible to think of programs purely declaratively.

Declarative part are more easier to understand than the procedural part.

How Prolog proves things should be of less concern.

However, for any reasonably complex program, as we discussed earlier, it often becomes important to think about how it executes the program.

For example:

·         the order of subgoal execution may be crucial to the efficiency of the program, and variables may be used in a way that does not have a simple declarative reading.

·         Prolog also allows non-logical statements, like write statements and assertions. When these are included in a program it becomes even more important to think about what Prolog is doing.

What does declarative and procedural readings of programs means?

If we have a rule:

   p :- q, r.

The declarative reading is: ``p is true if q is true and r is true''.

The procedural reading can be stated as ``to solve problem p, first solve problem q and then solve problem r'', or alternatively ``to satisfy p, first satisfy q and then r''.

RECURSION

Almost any non-trivial prolog program involves recursive predicates - predicates that call themselves.

Recursion is a way to implement task-within-a-task algorithm such as tree searching and Quicksort.

The basic idea should be familiar from recursive function definitions in functional languages.

For example we want to print a table of the integers 1 to 5 and their squares:

1.           1

2.           4

3.           9

4.           16

5.           25

Can be written in pascal:

for i:=1 to 5 do

          writeln(i,'  ',i*i);

The recursive form:

procedure printsquares(i: integer);

begin

          if i < 5 then

                   begin

                             writeln (i,'  ',i*i);

                             printsquares(i+1);

                   end

          end;

However, as Prolog is not based on function application, the way recursive predicates are used and written is slightly different.

print_squares(I) :-                             %base case

          I > 5, !.

print_squares(I) :-                             %recursive case

          S is I*I,

          write(I),

          write (S), n1,

          newI is I+1

          Print_squares(NewI).

We can query:  ?- print_squares(1).

Exercise 1.3:

Define predicate print_stars which, given an integer as an argument, prints that number of asterisks:

?- print_stars(10).

**********

yes.

Hint: Consider carefully whether you should count up or down.

Another example the factorial program:

function factorial (N:integer):integer;

begin

if N=0 then

          factorial := 1

else

          factorial := N * factorial(N-1);

end;

How to write in Prolog?

factorial (0,1) :- !.

factorial(N,FactN) :-

          N > 0,

          M is N-1,

factorial(M,FactM),

          FactN is N*FactM.

The following steps happen:

1.    The procedure factorial call itself to compute the next smaller integer

2.    Use the result to compute the factorial of the integer that you originally ask for.

3.    The recursion stops when the number whose factorial is to be computed is 0.

Exercise 1.4:

Define a recursive predicate sum(J,K,N) that instantiates N to the sum of the integers from J to K inclusive:

?- sum(-1,1,What).

What = 0

?- sum(1,3,What).

What = 6

?- sum(6,7,What).

What = 13.

Iterative algorithm to compute factorials (in Pascal):

Function factorial (N:integer):integer;

Var     I,J : integer;

Begin

          I:=0;

          J:=1;                              {initialize}

          While I < N do

                   Begin           {loop}

                             I:=I+1;

                             J:=J*I

                   End;

          Factorial := J                  {return result}

End;

In Prolog (better way, called tail recursive):

factorial(N,FactN) :- fact_iter(N,FactN,0,1).

fact_iter(N,FactN,I,J) :- !.                   % I = N, FactN is J

fact_iter(N,factN,I,J) :-

          I<N,

          NewI is I+1,

NewJ is J*NewI,

fact_iter(N,FactN,NewI,NewJ).

How to express iterative algorithm in Prolog?

1.     Transform any kind of loops into while loop.

2.     Break the computation into 3 stages:

i.             initialization

ii.            the loop itself

iii.           any final computation to return a result

3.     Express the loop as a Tail Recursive clause with the while condition at the beginning.

4.     Place the final computations in another non-recursive clause of the same procedure that is setup so that it executes only after the loop is finished.

5.     Finally, hide the whole thing behind a front-end procedure (factorial in this example). The front-end procedure passes its arguments into tail recursive procedure with the initial values of state variables.

Exercise 1.5:

1.    A reverse number is a number with the order of all its digits reversed. If the input is 3456, the answer should be:

The Reversed Number is 6543.

Convert the following C program into prolog using tail recursive:

main

          {

                   int x,y;

                   printf ("Enter a number:  ");

                   scanf ("%d",&x);

                   y = 0;

                   while (x != 0)

                      {

                             y = y*10+x%10;

                             x = x/10;

                       }

                   printf ("The reverse number is %d ",y);

                   return;

             }

2.    The Fibonacci series is the series of numbers obtained by starting and forming each subsequent member by adding the previous two: <1,1,2,3,5,8,13,21…>. The following procedure computes the Nth. Fibonacci number in an elegant but inefficient way:

fib(1,1) :- !.

fib(2,1) :- !.

fib(N,F) :-

          N > 2,

          N1 is N-1, fib(N1,F1),

N2 is N-2, fib(N2,F2),

          F is F1+F2.

Write a more efficient procedure (name fib2) that uses state variables (accumulators) to remember the previous two Fibonacci numbers when computing each one. Example:

?- fib(3,F).

F=2

?- fib(5,F).

F=5

?- fib(7,F).

F=13

Suppose we want to write a Prolog procedure to determine whether someone is an ancestor of someone else.

This has a natural recursive definition.

X is Y's ancestor if

X is Y's parent

OR

Z is Y's parent and X is Z's ancestor.

This can be written as follows:

   ancestor(Person, Ancestor) :-      % Rule 1: Base case

      parent(Person, Ancestor).

   ancestor(Person, Ancestor) :-      % Rule 2: Recursive case

      parent(Person, Parent),

      ancestor(Parent, Ancestor).

Note how the base case of the recursive definition is a separate rule, preceding the recursive case.

All recursive predicates must have a base case, otherwise they would either fail or recurse for ever.

Consider what happens if we also have the following facts:

  parent(alison, david).          % fact 1

  parent(alison, kathleen).     % fact 2

  parent(david, harold).         % fact 3

  parent(david, ida).           % fact 4

  parent(kathleen, john).        % fact 5

  ancestor(Person, Ancestor) :-      % Rule 1: Base case

        parent(Person, Ancestor).

  ancestor(Person, Ancestor) :-      % Rule 2: Recursive case

       parent(Person, Parent),

       ancestor(Parent, Ancestor).

and we ask:

   ?- ancestor(alison, harold).

Prolog will do the following:

1.       match the query against rule 1, and try to prove parent(alison, harold).

2.       This will fail, so Prolog will backtrack and try the second rule.

3.       parent(alison, Parent) first succeeds with Parent = david, so Prolog tries to prove ancestor(david, harold).

4.       Matching this new term against the head of the first rule, and sucessfully proving parent(david, harold), the whole query succeeds.

If we try to prove ancestor(alison, john) things get a bit more complex as Prolog has to backtrack.

 parent(alison, david) is no good, as it won't be able to prove ancestor(david, john).

It will have to backtrack, finding parent(alison, kathleen), and proving ancestor(kathleen, john).

It is probably wise not to think TOO hard about what happens when Prolog backtracks through complex recursive predicate definitions.

 They can often be easily understood declaratively, and you should soon get a feel for what will happen, without having to trace everything out in detail.

Suppose for example we give the following query, and force backtracking (e.g., by typing a semicolon).

   ?- ancestor(alison, Ancestor).

   Ancestor =                      ;

   Ancestor =                      ;

   Ancestor =                      ;

   Ancestor =                      ;

   Ancestor =                      ;

   no

Prolog first finds all the facts that match with the subgoal of the base case (Ancestor = david; kathleen).

Then finds all david's ancestors (harold; ida), then all kathleen's ancestors (john).

If we added a fact parent(harold, fred) then Ancestor = fred would be given after Ancestor = ida, as Prolog tried to find all harold's ancestors.

Exercises 1.6 (Recursion)

1.     For the following facts and recursive predicate, state what order solutions to the given query are returned:

on_top_of(prolog_book, desk).

on_top_of(ai_notes, prolog_book).

on_top_of(time_table, ai_notes).

on_top_of(ai_book, desk).

above(X,Y) :- on_top_of(X,Y).

above(X,Y) :- on_top_of(X,Z),

         above(Z,Y).

?- above(Object, desk).

2.     What will happen if you try the following program/query:

above(prolog_book, desk).

above(ai_notes, prolog_book).

above(time_table, ai_notes).

above(X,Y) :- above(X,Z),

         above(Z,Y).

?- above(desk, ai_notes).

 3.     A one way road links 6 towns. Write a program that can work out if you can travel on that road. For example. Here are two sample program behaviours. 

town1----->-----town2---->----town3---->----town4--->----town5---->---town6

?- can_get(town2,town5).

yes

?- can_get(town3,town1).

no