Prolog exam question help

Hi Guys and Gals,

I'm going through some past papers for a Logic and Semantics course
(Bath Uni). Included are questions on Prolog and it'd be great if any of
you could help me out - particularly as there are no example solutions
to these past papers.

a(X, 0, X)
a(X, s(Y), s(Z)) :- a(X, Y, Z).

b(0, 0)
b(s(s(X)), s(Y)) :- b(X, Y).

c(s(0), 0)
C(s(s(X)), s(Y)) :- b(s(s(X)), Z),
c(Z, Y).
c(s(s(X)),s(Y)) :- b(s(X), Z),
b(U, s(s(X))),
b(U, s(s(X)), W),
c(s(W), Y).

For the above program the questions I'm needing help on are:

- What is the meaning of the predicate a(X, Y, Z)?
- What is the meaning of the predicate b(X, Y)?
- What is the meaning of the predicate c(C, Y)?

Cheers,

Jack

Jack Higgs wrote:
> Hi Guys and Gals,
>
> I'm going through some past papers for a Logic and Semantics course
> (Bath Uni). Included are questions on Prolog and it'd be great if any of
> you could help me out - particularly as there are no example solutions
> to these past papers.
>
> a(X, 0, X)
> a(X, s(Y), s(Z)) :- a(X, Y, Z).
>
> b(0, 0)
> b(s(s(X)), s(Y)) :- b(X, Y).
>
> c(s(0), 0)
> C(s(s(X)), s(Y)) :- b(s(s(X)), Z),
> c(Z, Y).
> c(s(s(X)),s(Y)) :- b(s(X), Z),
> b(U, s(s(X))),
> b(U, s(s(X)), W),
> c(s(W), Y).
>
> For the above program the questions I'm needing help on are:
>
> - What is the meaning of the predicate a(X, Y, Z)?
> - What is the meaning of the predicate b(X, Y)?
> - What is the meaning of the predicate c(C, Y)?
>
> Cheers,
>
> Jack

Hi!

Have you tried to feed your queries to a prolog interpreter (for your
exam you should be able to do the inferences in your head, but for
checking, it is just fine)? There are some typos in cour code (missing
dots at the end of the facts, C instead of c, and b is only a two place
predicate, not a three place one - perhaps it should read "a" instead?).

I've done this with swi prolog and got these results(added the newlines):

?- a(X,Y,Z).
X = Z,
Y = 0 ;

Y = s(0),
Z = s(X) ;

Y = s(s(0)),
Z = s(s(X)) ;

Y = s(s(s(0))),
Z = s(s(s(X))) ;

Y = s(s(s(s(0)))),
Z = s(s(s(s(X)))) ;

Y = s(s(s(s(s(0))))),
Z = s(s(s(s(s(X))))) ;


[and so on]

?- b(X,Y).
X = 0,
Y = 0 ;

X = s(s(0)),
Y = s(0) ;

X = s(s(s(s(0)))),
Y = s(s(0)) ;

X = s(s(s(s(s(s(0)))))),
Y = s(s(s(0))) ;

X = s(s(s(s(s(s(s(s(0)))))))),
Y = s(s(s(s(0)))) ;

[and so on]

Some questions:
1) Do you know what the prolog output means?
2) If yes, do you recognise a pattern?
3) Try to do the inferences by hand, perhaps the pattern is easier to
see then? (since you have to do this in your exam, this should be a good
exercise anyway)
4) Try to compare the prolog code to recursive definitions: there is one
or more base case(s) and some inductive steps. Seeing the similarities
can also help finding out what a predicate describes.
5) If you have some lecture notes, variants of these definitions are
very likely to be in them, since they describe very basic properties of
natural numbers. Try to compare them to your exam tasks.



[Hint: try to think of s as the successor function, and 0 as the
constant 0 - s(s(s(0))) can then be seen as a representation of a
certain natural number]

hth Martin