CmSc 310 Artificial Intelligence
Lesson 1: Prolog basics: Facts, Rules and Queries.
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.
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
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.
This is equivalent to the predicate calculus statement
" x, even(X) à divisible_by_two(x)
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:
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.
mother(X,Y):- parent(X,Y), female(X).
grandmother(X,Y):- mother(X,Z), mother(Z,Y).
grandmother(X,Y):- mother(X,Z), father(Z,Y).
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
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 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).