Lesson 4
1.
In this lesson, I shall explain the relationship between Prolog, formal
logic, and English, giving rules for translating between them.
2.
Let's begin with unconditional facts like
event( 1756, mozarts_birth ).
loves( joe, mary ).
teaches_at( joseph, st_annes ).
colour( grass, green ).
legs( sheep, 4 ).
costs_pence( mars_bar, 21 ).
is_a( sheep, mammal ).
As explained in Supplement 1, these are composed of a PREDICATE and two
ARGUMENTS. The predicate is the part before the bracket. What it does is
to name some relation that holds between the two arguments. The
arguments come between the brackets, and are separated by a comma.
The most common use of a predicate is to state a relationship between
two objects. You can also use predicates to say that an object has a
certain property, to say that an object belongs to a certain class, or
to give the result of operating on the object in a certain way.
3.
Technically, names like "joe" and "mary" are called ATOMS. That's
because their internal structure (i.e. their spelling) is irrelevant to
Prolog; all that matters about two atoms is whether they are spelt the
same as one another or not.
Atoms must start with a small letter, and may continue with small
letters, underlines, and digits. So these are all atoms:
fred elizabeth_2
am_using z
In most programs, atoms are used in one of three ways:
To name individuals: fred elizabeth_2 burger_247
To name properties: small brown
To name classes: gerbil cheeseburger deadly_sin
4.
You have also seen a few numbers. Technically, there are two kinds of
numbers: INTEGERS or whole numbers:
1 39 10
and REALS, or non-whole numbers:
2.3 -390.001 0.0088341
The distinction between them is important to computer scientists, but it
will not matter to you, and you can use them as you wish. If you want to
write a real number that's smaller than 1, you must put a zero before
the decimal point, as I have above.
5.
As well as atoms, you have seen many facts that contain VARIABLES.
Variables must start with a large letter, and may continue with either
case of letter, underlines, and digits. So these are all variables:
Fred Who X23
X What_dog Pizza2Go.
6.
Now, in the rest of this lesson, we will work upwards in complexity.
Let's begin with UNCONDITIONAL FACTS, i.e. facts with no "if" part. We
already know what is meant by the kind of fact I showed in section 2,
where you have numbers or atoms as arguments.
But you can also have variables as arguments, something we haven't done
before. What does this mean? Well, try it.
If you're already in Prolog, quit it to make sure that you have nothing
left in your knowledge base. Then start it up again, and enter the fact
loves( mary, X ).
Having done this, try some questions like
loves( mary, john ).
loves( mary, bert ).
loves( mary, a_small_piece_of_green_blutack ).
7.
You should have found that no matter what you put in the second argument
of your question, Prolog replies "yes". That suggests that the fact
loves( mary, X ).
could be translated as
Mary loves everything.
and indeed, that's the way the designers of Prolog intended it to be
used.
In the jargon of formal logic, we say that the variable X is UNIVERSALLY
QUANTIFIED. For those who don't know formal logic, this means that we
can translate the fact into (stilted) English by sticking the words "for
all X" in front of it:
For all X, Mary loves X.
8.
Similarly, if you add the fact
hates( Y, idi ).
to your knowledge base, Prolog will answer questions like
hates( amit, idi ).
hates( asfah, idi ).
by "Yes". Try it and see.
The fact holds for all Y, no matter what, so we say again that the Y is
UNIVERSALLY QUANTIFIED. As above, we can translate this fact by sticking
a "for all Y" in front of it:
For all Y, Y hates Idi.
9.
Members of Balliol traditionally share a reputation for intellectual
arrogance (in place of actual intellect, I suppose), as this piece of
doggerel about a former master illustrates:
I am the master of this College
And what I don't know isn't knowledge.
Type in an unconditional fact meaning "Jowett knows everything", and
test it with suitable questions.
10.
So far, I have only had one variable in an unconditional fact. What if
there is more than one? For example, what would the fact
loves( X, Y ).
mean? Experiment by deleting any facts about "loves" that you already
have, and typing in this one with VED. Then ask any questions about
"loves" that you want to.
11.
You should have found Prolog answered every question with "Yes", no
matter what the arguments were. That's not surprising, it's a straight
extension of what we said in sections 6 and 7. You can translate this
fact into English by sticking a "for all X and for all Y" on the front
of it:
For all X and for all Y, X loves Y
i.e. everyone loves everyone else.
In terms of formal logic, we say that both the X and the Y are
universally quantified.
12.
How would you write "everything depends on everything else" in Prolog?
13.
Now, what happens if both variables are the same? What does
admires( X, X ).
mean? As above, we translate into English by sticking a "for all X" on
the front:
For all X, X admires X.
i.e. everyone admires him or her self.
If you enter this fact, you'll find that questions with both arguments
the same, like
admires( jo, jo ).
are answered with "Yes", but questions like
admires( jo, jim ).
with both arguments different are answered "No.".
14.
To recap, I've talked about what unconditional facts mean. I have said
that they can contain variables. You translate such facts into English
by sticking a "For all V", where V is the variable, on the front. Do
this as many times as there are different variables.
15.
Those who don't know formal logic can skip the next two sections.
For the others, if you know it already, you will realise that this is
equivalent to the transformations:
\--/
hates( Y, idi ) --> \/ Y hates( Y, idi ).
\--/
knows( jowett, X ) --> \/ X knows( jowett, X ).
\--/ \--/
loves( X, Y ) --> \/ X \/ Y loves(X,Y)
\--/
admires( X, X ) --> \/ X admires(X,X)
where the thing before the variables is the nearest I can get to writing
the "universal quantifier", usually printed as an inverted A. So to
translate unconditional facts into formal logic, apply a universal
quantifier to each variable (if any) that they contain.
16.
So this demonstrates a difference between Prolog and formal logic. In
Prolog, you don't have to write the universal quantifiers (and in fact,
Prolog won't let you). In formal logic, you must quantify every variable
as universal or existential.
17.
Now I'm going to leave unconditional facts and go onto conditional
ones: those with a ":-" in them.
Consider a fact like
is_a( socrates, mortal ) :- is_a( socrates, human ).
It consists of two parts: that before the :-, and that after it. Prolog
programmers call the first part the HEAD, and the second part the TAIL.
Remember these names: like PREDICATE and ARGUMENT, I shall use them a
lot from now on.
To translate the fact into English, you translate each part separately,
and join them by an "if":
Socrates is mortal if Socrates is human.
Make sure you do this the right way round. It DOES NOT mean
Socrates is human if Socrates is mortal.
(Harold might be mortal, but he's not human, he's my pet swiss-cheese
plant).
18.
That's all there is to translating conditional facts containing no
variables.
How are variables translated? It depends on whether or not they occur in
the head of the fact. Let's deal first with facts where every variable
they contain occurs in the head.
To translate these, you translate the fact into English as above, and
then stick a "for all" in front:
is_a( X, mortal ) :- is_a( X, human ).
becomes
For all X, X is mortal if X is human
i.e. anyone is mortal if they're human.
19.
What about facts with a comma in the tail?
loves( mary, X ) :- likes( X, beer ), likes( X, chip_butties ).
Each predicate/argument combination is called a SIMPLE GOAL. The parts
are called goals because they give Prolog the goal (i.e. objective) of
discovering whether something is true, and simple because you can't
decompose them into simpler goals.
20.
To translate conditional facts that contain commas in the tail, first
replace the comma by an "and". Then follow the same rules as above.
Here, there's a variable X in the head of the fact, so we must put a
"for all X" in front:
For all X, Mary loves X if X likes beer and X likes chip butties.
21.
This works for more than one variable, provided they all occur in the
head:
is_son_of( X, Y ) :- is_a( X, male ), is_parent_of( Y, X ).
becomes
For all X, for all Y,
X is a son of Y if X is a male and Y is a parent of X.
Now, please ensure you understand all this before reading further.
22.
I'm now going to talk about variables that don't occur in the head, but
only in the tail. They must be treated differently. Consider
is_a( X, wife ) :- is_a( X, female ), is_married( X, Y ).
Here, the X occurs in the head and in the tail. The Y occurs only in
the tail. The conventions of Prolog say that the X can be translated by
"for all"; this won't work for the Y.
In fact it, and other variables that occur only in the tail must be
translated by using the words "there exists". Put them just before the
predicate where the variable first appears:
For all X, X is a wife if
X is a female and there exists a Y such that X is married to Y.
23.
Notice that the fact does NOT mean what I've written below:
For all X, X is a wife if
X is a female and for all Y, X is married to Y.
It would imply that to be a wife, X has to be married to EVERYONE!
24.
How would you translate the following into English (and into formal
logic, if you're studying that).
deserves( X, damnation ) :-
committed( X, Y ),
is_a( Y, deadly_sin ),
doesnt_repent( X, Y ).
25.
Skip this one if you're not interested in formal logic.
In formal logic, we say that variables like Y above are EXISTENTIALLY
QUANTIFIED. Logicians write the universal quantifier as an inverted A;
they write the existential quantifier as a back-to-front E.
To translate Prolog facts with existentially quantified variables into
formal logic, we write the existential quantifier before the variable:
A X deserves( X, damnation ) :-
E Y committed( X, Y ),
is_a( Y, deadly_sin ),
doesnt_repent( X, Y ).
Here, I've used a normal A and E; but imagine them as upside-down or
back-to-front.
26.
You should now be able to translate from Prolog into either English or
formal logic, any Prolog fact that you know how to write. How about
questions? Let's think about lesson 1 again. Assume you have these
facts:
loves( bill, mary ).
loves( adrian, robin ).
loves( bill, jo ).
and you ask
loves( X, mary ).
Try it, just to remind yourself of the result.
27.
Now, the question might mean
Is it true that, for all X, X loves Mary?
i.e.
Does everyone love Mary?
Or it might mean
Is it true that there exists an X such that X loves Mary?
i.e.
Does anyone love Mary?
From the answers Prolog gives, which is it?
28.
Well, Prolog answers "Yes" as long as at least one person loves Mary.
That's obvious really, because it is happy as long as it can find you
one value for the variable X. As you may have realised by now, the way
Prolog does this is to search from the top of the knowledge base
downwards, until it finds a fact with the same predicate, the same
number of arguments, and which makes your question true.
So all variables that occur in questions are existentially quantified,
and should be prefixed by "there exists" when translating into English.
29.
In fact, questions behave exactly like the tails of conditional facts.
That's quite reasonable. If Prolog knows the facts
(10) is_a( fred, human ).
(20) is_a( X, mortal ) :- is_a( X, human ).
and you ask it
is_a( fred, mortal ).
then it proves that (20) is true by trying to prove its tail. And
proving its tail entails asking a kind of internal question, one which
happens to be answered by fact (10).
30.
Actually, when Prolog answers a question like
loves( X, mary ).
it not only tells you whether it's true; if it is true, then it tells
you what value of X makes it so. So my interpretation as
Is it true that there exists an X such that X loves Mary?
might be more accurately written as
Find an X such that X loves Mary, and tell me its value.
31.
Before I leave this lesson, there are two more points. Prolog lets you
write predicates that have more than two or fewer than two arguments,
just by putting more or fewer arguments into the brackets, so writing a
predicate with 1723 arguments would give no more difficulty (other than
extreme boredom) than writing one with two.
To demonstrate this, please "showlib" the file ph.pl.
You will see that you have about 25 unconditional facts, each having
four arguments.
32.
Can you devise Prolog questions to:
(1) Find all pubs in Cowley?
(2) Find all pubs supplied by Halls?
33.
Imagine now that there is a pub called Heaven's Gate, located in
Paradise Street, and supplied by Angel's Brewery. Add a fact to describe
it.
Now, using one of the editing commands, replace or change this fact so
that the pub is supplied not by ONE brewery but by EVERY brewery there
is. Test this fact by asking questions about whether it's supplied by
Morrells, Hook Norton, Archers, etc.
34.
Hint: your fact should contain one universally quantified variable, i.e.
a variable that appears in its head.
35.
This database brings up a point about ATOMS. I said in section 3 that
they must contain only letters, digits, and underlines. This hardly
makes for natural looking names. As you'll see in a later lesson, Prolog
does provide facilities for writing messages and other things (it
wouldn't be much good otherwise). But imagine how unnatural the output
would look if it was all stored as in the "ph" knowledge base.
There is, luckily, a way to represent such things. Restore the "phq"
knowledge base, and look at it. This demonstrates a more natural way of
writing names such as pub names and road names than by stuffing them
with underlines. Here, the atoms are enclosed in quotes. More on this in
the next section.
36.
You must be careful not to get confused between atoms and variables.
Anything in upper case with no quotes round it is a variable.
Anything in lower case with no quotes round it is an atom.
Anything with quotes round it is an atom, regardless of what's between
them.
Why use quotes for some atoms and not others? Well, every variable MUST
start with a capital letter. This is a rule of Prolog grammar that can't
be changed. So suppose you want to make an atom that names John, in
upper case. You can't write just
John
because Prolog would take that to be a variable.
But Prolog's designers did not want to prevent people from using
upper-case atoms, and so they adopted the convention of using quotes, to
"insulate" the name from its context.
37.
To summarise:
X is a variable
'X' is an atom
A name is not an atom, but a variable followed by an atom.
'A name' is an atom
x is an atom
'x' is the same atom
'a_1' is an atom
a_1 is the same atom
An atom can, if enclosed in quotes, have any name at all between the
quotes. If that name contains only little letters and digits and
underlines, and if it starts with a little letter, the quotes are not
necessary. Typically, quoted atoms are used when writing names to appear
in messages, so that the computer can address you as Fred Bloggs and not
fred_bloggs.
38.
That's almost the end of the lesson. To summarise:
Facts can be UNCONDITIONAL or CONDITIONAL.
If the arguments of an unconditional fact are VARIABLES, then they are
UNIVERSALLY QUANTIFIED.
You translate such facts into formal logic by taking each distinct
variable, and writing it prefaced by a universal quantifier (the
inverted-A symbol) before the Prolog version of the fact.
You translate such facts into English by taking each variable and
writing it prefaced by "For all" before the "X loves Y" form of the
fact. Then if you want, you can rewrite the result so it reads more
naturally.
39.
A conditional fact is made from a HEAD and a TAIL, separated by the :-
symbol, which means "if".
The head looks like an unconditional fact.
The tail can contain one or more SIMPLE GOALS separated by commas.
The goals look like unconditional facts, and the comma means "and".
To translate such facts into formal logic, take every variable that
appears in the head, and preface it by a universal quantifier as for
unconditional facts. Take every other variable (i.e those appearing only
in the tail), and preface by an EXISTENTIAL QUANTIFIER (the backwards E
symbol).
To translate into English, do the same, but use the words "There exists"
instead of the existential quantifier, and "For all" instead of the
universal one. Replace the ":-" by "if", and the commas by "and".
40.
Questions translate in the same way as the tails of conditional facts.
When you ask a question, its variables are EXISTENTIALLY QUANTIFIED:
"married(jim,X)" means "does there exist an X loved by Jim?" and not
"are all X's loved by Jim?".
When Prolog answers a question, it not only says "Yes" or "No", but also
shows you the values of the variables.
So you can think of questions as (e.g.) "find me an X loved by Jim, and
show me its value".