Family trees in Prolog

Got it! This site uses cookies. You consent to this by clicking on "Got it!" or by continuing to use this website.nbsp; Note: This appears on each machine/browser from which this site is accessed.

Logic languages, such as Prolog and Datalog, are often used for expert systems applications, semi-formal specifications, and rapid prototyping, all of which are often found in areas of software engineering.

Logical implications can be derived from a precise model of facts and rules. Such an understanding that is obtained by studying expert systems and declarative specification techniques.

Facts and rules are axioms of the system.
Queries are the theorems to be proved.

A collection of facts (and rules) is called a database.

Facts express relationships between atoms (names) that are assumed to be true.

A person is a male or a female.
A person may be specified as a parent of another person.

Facts are a database of people in the family.

Rules place conditions on the use of facts to satisfy a query. Rules specify relationships among people, but do not refer to specific people.

A mother is a parent of a person, and the mother is female.
An uncle is a sibling of a parent, and the uncle is male, and the uncle is not a parent of the person.

Queries require specific relationships to be determined using the facts and rules.

List all females.
List all pairs of cousins.

Ways to run Prolog: (if the system allows it)

Interactive method
Text file specification method (used here)
GUI method (if available)

Multi-line comments start with "/*" and end with "*/".

/* This is a multi-line comment */

A comment should explain every fact and rule that is not clear from context.

A single line comments starts with a "%" and continues to the end of the line.

% this is a single-line comment.

female is an atom,
eve is an atom,
male is an atom, and
adam is an atom.

Atoms are words that start with lower case letters. One can also use single-quoted character strings as atoms (in most Prolog systems).

/* eve is female */ female(eve). /* adam is male */ male(adam).

Question: In a Prolog/Datalog system, how does the system know that Eve is a female from the fact female(eve)? Explain.

The system does not know.

The syntax of the language allows specification of facts and rules as text. Do not forget the period at the end of each fact, rule, and query.

/* eve is a parent of cain */ parent(eve,cain). /* adam is a parent of cain */ parent(adam,cain).

/* P is the child of Q */ child(P,Q) :- parent(Q,P).

The symbol ":-" is pronounced "if".

Note: Some systems allow the word "if" to be used. In Prolog, whichever symbol you use first in a program should be used throughout the entire program.

P and Q are logical variables. In Prolog/Datalog, the term variable means a logical variable. Variables start with an upper case letter and act as placeholders to be filled in (sooner or later).

Within a clause, variables refer to the same value (or lack of value) and can be renamed to any variable name not already in that clause.

/* P is the child of Q */ child(P,Q) :- parent(Q,P). /* X is the child of Y */ child(X,Y) :- parent(Y,X).

Note: Do not use both of these in the same program file as the mutual recursion will cause problems.

/* X is a sibling of Y */ sibling(X,Y) :- child(X,Z) , child(Y,Z).

The symbol ",", pronounced "and", is often used instead of "and".

In "Datalogs", whichever symbol you use first in a program must be used throughout the entire program.

and

Problem: One is sibling of oneself.

Answer: The rule must incorporate the desired knowledge.

/* X is a sibling of Y */ sibling(X,Y) :- child(X,Z), child(Y,Z), X \== Y.

/* X is a sibling of Y */ sibling(X,Y):- child(X,Z), child(Y,Z), X \== Y.

Note the free form syntax.

There may be more than one way to specify a rule.

/* X is a grandparent of Y */ grandparent(X,Y) :- parent(X,Z), parent(Z,Y).

Here are some rules for mother and father.

mother(A, B) :- parent(A, B), female(A). father(A, B) :- parent(A, B), male(A).

The previous rule for grandparent can be rewritten as follows. The rule uses four rules using implicit "or" (disjunction) as follows.

/* X is a grandparent of Y */ grandparent(X,Y) :- mother(X,Z), mother(Z,Y). grandparent(X,Y) :- mother(X,Z), father(Z,Y). grandparent(X,Y) :- father(X,Z), mother(Z,Y). grandparent(X,Y) :- father(X,Z), father(Z,Y).

The same set of rules can be expressed as follows using an explicit "or" (disjunction).

/* X is a grandparent of Y */ grandparent(X,Y):- (mother(X,Z), mother(Z,Y)) ; (mother(X,Z), father(Z,Y)) ; (father(X,Z), mother(Z,Y)) ; (father(X,Z), father(Z,Y)).

The symbol ";", pronounced "or", is often used instead of "or".

A query is a question to be answered.

The symbol "?-" starts a query and is pronounced "For what" if there are variables in the query. Otherwise, the query symbol can be pronounced "Is it true that".

Prolog is relational language in that queries can be posed in many different forms and the system will try to answer the query.

/* for what X is it true that X is the child of adam */ ?- child(X,adam).

/* for what X is it true that cain is the child of X */ ?- child(cain,X).

/* is cain the child of adam? */ ?- child(cain,adam).

/* for what X and Y is it true that X is the child of Y */ ?- child(X,Y).

When we can ask a query in different ways, we are said to be able to ask relational queries.

male(adam). female(eve). male(cain). male(abel). male(seth). go:- male(X), print(X), print(" is a male"), nl, fail. :- solve(go).

String literals can be delimited by either double quotes or single quotes.

For our purposes, the following are the same string literals.

"Hello, World" 'Hello, World'

Common errors:

Forgetting the period at the end of a fact, rule, or query.
Mixing names starting with a lower case letter (atoms) and an upper case letter (variables).

Negation by failure rule (non-monotonic logic):

If something cannot be proved true within the system, it is assumed to be false.
If you forget to include one of your cousins as a fact in your database, the system will say no to the question, "Is this person your cousin.".