CmSc 310 Artificial Intelligence

Prolog MiniTutorial

Lesson 1: Prolog basics: Facts, Rules and Queries.

  1. Introduction

    2. Declarative logic programming language

    Prolog is a logic programming language designed to describe properties of objects, relations between objects and if-then rules concerning the properties and relations. Prolog has a built-in mechanism to make inferences using these descriptions.

    Prolog Inference mechanism

    Prolog is based on First Order Predicate Logic ---sometimes abbreviated to FOPL.

    First order predicate logic implies the existence of a set of predicate symbols along with a set of connectives.
    First order predicate logic implies that there are no means provided for "talking about'' the predicates themselves.

    Prolog is based on FOPL but uses a restricted version of statements in FOPL, called Horn clause form.

    Horn Clauses

    Consider If (P1 L P2 L …L Pn) then Q.

    The statement Q will be true if all statements P1, P2, … Pn are true.

    In disjunctive normal form the implication will be represented as:

    Q V ~P1 V ~P2 V …. V ~P3

    Expressions of this type are called Horn clauses. All Prolog statements are instances of Horn clauses.

    The inference in Prolog is based on the modus ponens syllogism

    (1) If P(x) then Q(x)
    (2) P(a)
    (3) Therefore Q(a)

    Example:

    If human(X) then mortal(X).
    human(socrates)
    Therefore: mortal(socrates)

    A Prolog program consists of logical expressions of type (1) and (2), represented as Prolog clauses (discussed below).

  2. Building blocks

    3.

    A Prolog program consists of clauses.

    A clause is a term.
    Term: constant | variable | structure
    Constants: atoms | integers
    Atoms: strings of characters starting with a lower case letter, representing names of objects or relations.

    Examples: member, part_of, iowa, john, t12
    Note: if we need the first letter to be a capital letter, we need to enclose the string in single quotes: 'John'
     Variables: strings of characters, starting with a capital letter
    Structure: a predicate with a name (functor) and fixed number of arguments. Each argument is a term, i.e. a constant, a variable, or a structure.

    Example of a structure: mother(mary,X).

    Types of clauses:

    Rules - if-then logical expressions, Horn clauses.

    Facts - predicates with 0 or more arguments.

    Rules: structure with functor ' :- ' and two arguments: head and body.

    <rule> ::= <rule_head >:- <rule_body>

    <rule_head> ::= structure

    <rule_body>::= sequence of structures, separated by commas or ;

    Facts: rules with an empty body.

    Example:

    divisible_by_two(X):- even(X).

    This is equivalent to the predicate calculus statement

    " x, even(X) à divisible_by_two(x)

    Semantics:

    Here is an informal version of the procedural semantics for the example above:

    If we can find a value of X that satisfies the goal even(X) then we have also found a number that satisfies the goal divisible_by_two(X).

    The declarative semantics is:

    If an integer X is even then X is divisible by two.
    Note that there is an implicit universal quantification here. That is, for all objects those that are even are also divisible by two.

    Another example: divisible_by_six(X):- divisible_by_two(X), divisible_by_three(X).

    Thus each rule

    Q:- P1, P2, …., Pn

    corresponds to an implication in predicate logic of the type:

    P1 L P2 . L …. Pn à Q

    The head of the rule (Q) is the predicate in the right part of the implication.

    The body of the rule (P1, P2, …., Pn) contains the predicates in the left part of the implication.

    The left part is a conjunction.

    Conjunction of predicates is represented as a sequence of structures, separated by commas.

    Disjunction in Prolog:
    1. using ; to separate structures
    2. using separate clauses

    Example:
    1. siblings(X,Y):- brother(X,Y) ; sister(X,Y).

    2. siblings(X,Y):- brother(X,Y).
      siblings(X,Y):- sister(X,Y).

    Negation: the built-in predicate for negation is not.
    For example, in the definition of the predicate "brother(X,Y)" we would not like to have same values for X and Y, and we write:

    brother(X,Y):- male(X), parent(Z,X), parent(Z,Y), not X = Y.

     We may negate any predicate, as in:
    odd(X):- not even(X).

    Defining predicates by means of clauses

    Each predicate can be defined by one or more clauses of any of the two types - rules and facts.

    Example:

    mother(X,Y):- parent(X,Y), female(X).

    mother(mary,john).

    grandmother(X,Y):- mother(X,Z), mother(Z,Y).

    grandmother(X,Y):- mother(X,Z), father(Z,Y).

    or

    grandmother(X,Y):- mother(X,Z), parent(Z,Y).

    Scope of Variables

    The scope rule for Prolog is that two uses of an identical name for a logical variable only refer to the same object if the uses are within a single clause. Therefore in

    happy(X):-healthy(X).
    wise(X):- old(X).

    the two references to X in the first clause do not refer to the same object as the references to X in the second clause.

  3. How Prolog works

    4. Queries and Goals

    A Prolog program is initiated by a query - a predicate or a sequence of predicates to be proved.
    The predicate to be proved is called a goal.

    Prolog tries to match the goal to the head of some fact or some rule.

    If a match is found with a rule, Prolog continues with proving each predicate in the body of the rule.

    Unification

    Unification is the name given to the way Prolog does its matching. We will not do more than sketch the basic ideas here. Basically, an attempt can be made to unify any pair of valid Prolog entities or terms.

    Unification is more than simple matching. It implies mutual coercion.
    There is an attempt to alter both the target and the current source object to make them look the same.
     Unification is a two-way matching process.

    Prolog's Search Strategy

    Search is a major issue. There are many ways to search for the solution to a problem and it is necessary to learn suitable algorithms that are efficient. Prolog provides a single method of search for free. This method is known as depth first search (to be continued).
Back to Prolog page
Created by Lydia Sinapova