~1
LOGIC PROGRAMMING LESSON 4
In this lesson, I shall explain the relationship between Prolog, formal
logic, and English, giving rules for translating between them.
This lesson and those following it will all be done in Prolog. So please
switch your logic programming tutor to Prolog mode by typing
prolog.
~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 and Lesson 3, 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.
Delete any facts you have for "loves" by typing
delete loves.
Then add 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, 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. 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.
The Logic Programming Tutor recognises a command, "analyse", that will
do this for you. What it does is to write facts in Logic syntax, and to
stick the necessary "For all's" on the front.
It works just like "show", so you can do
analyse 10.
analyse all.
analyse ctc 10/200.
and so on.
Try it with some of the facts you have so far. For example, if you have
loves(X,Y)
as fact number 30, try
analyse 30.
~15
If you try changing modes between Logic and Prolog, you will see that
"analyse" always displays an English-like form, whichever mode you use
it in. Note that you can't enter facts in this form, only display them.
~16
Those who don't know formal logic can skip sections 16 and 17.
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.
~17
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.
~18
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).
~19
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 in section
17, 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.
Try entering the fact above and then using "analyse" on it.
~20
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.
~21
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.
If you tried out "analyse", the line above is what it would have shown
you.
~22
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.
~23
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.
Try typing in the fact and using "analyse" to confirm this.
~24
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!
~25
The following fact was used in the exercises at the end of Lesson 3.
deserves( X, damnation ) :-
committed( X, Y ),
is_a( Y, deadly_sin ),
doesnt_repent( X, Y ).
How would you translate it into English (and into formal logic, if
you're studying that)?
~26
As with sections 16 and 17, 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.
~27
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.
~28
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?
~29
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.
~30
You can confirm this by the special command
analyse q.
Your teacher may have explained already, when showing you the "change"
or "edit" commands, that the Tutor always saves the last question you
asked it. You can ask it to analyse that question, i.e. to translate it
into formal logic, by using the letter "q" instead of something like 10
or "all".
So ask a question with some variables in it, and then type
analyse q.
~31
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.
~32
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.
~33
Before I leave this lesson, there are two more points. In Lesson 3, I
said that Prolog lets you write predicates that have more than two or
fewer than two arguments. This was awkward before you knew Prolog,
because there was only room for two arguments, one each side of the
predicate:
john loves mary.
^ ^
But in Prolog, all the arguments go in brackets after the predicate:
loves( john, mary )
^ ^
so writing a predicate with 1723 arguments would give no more difficulty
(other than extreme boredom) than writing one with two.
~34
To demonstrate this, please restore the file "ph".
You will see that you have about 25 unconditional facts, each having
four arguments.
~35
Can you devise Prolog questions to:
(1) Find all pubs in Cowley?
(2) Find all pubs supplied by Halls?
~36
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.
~37
Hint: your fact should contain one universally quantified variable, i.e.
a variable that appears in its head.
~38
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.
~39
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.
~40
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.
~41
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 Logic form of the fact. Then
if you want, you can rewrite the result so it reads more naturally.
~42
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".
~43
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".
~44
You have now reached the end of Lesson 4. Before going on to Lesson 5,
please have a look at Supplement 4.