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".