CmSc 310 Artificial Intelligence

**
**

**Prolog MiniTutorial**

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

- Introduction: logical foundations
Horn Clauses - Building blocks: Facts and Rules
Conjunction, disjunction, and negation in Prolog

Scope of Prolog variables - How Prolog works: Queries and Goals

- Introduction
- Building blocks
- using ; to separate structures
- using separate clauses
- siblings(X,Y):- brother(X,Y) ; sister(X,Y).
- siblings(X,Y):- brother(X,Y).

siblings(X,Y):- sister(X,Y). - How Prolog works

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 **F**irst **O**rder **P**redicate **L**ogic
---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

(2) P(a)

(3) Therefore Q(a)

**Example:**

human(socrates)

Therefore: mortal(socrates)

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

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.

**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 ofXthat satisfies thegoaleven(X)then we have also found a number that satisfies the goaldivisible_by_two(X).

The **declarative semantics** is:

If an integerXis even thenXis divisible by two.

Note that there is an implicit universal quantification here. That is,for all objectsthose 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:

Example:

**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:

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.

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