[Overview] [Previous] [Next]

Examples I

The following examples show how these can be used to define more complicated functions. My examples are taken from those in the textbook, but I prefer the notation s(x) to the abbreviation x+1.

Example. Addition of two numbers.
Strictly according to the form, this is:

add(x, z(x)) = g1(x)
add(x, s(y)) = h(g2(x,y), g3(add(x,y)))

By choosing g1=p1, g2=p1, g3=s, and h=p2, we get

add(x, z(x)) = p1(x)
add(x, s(y)) = p2(p1(x,y), s(add(x,y))) which simplifies to add(x, z(x)) = x
add(x, s(y)) = s(add(x,y))

For example, add(3,2) works as follows: add(s(s(s(z(x)))), s(s(z(x))))
s(add(s(s(s(z(x)))), s(z(x))))
s(s(add(s(s(s(z(x)))), z(x))))

Copyright 1996 by David Matuszek
Last modified Apr 18, 1996