ASSORTED PRIMITIVE RECURSIVE FUNCTIONS:

*****************************

Minus(x,y)

Returns x-y (or 0 whenever y>=x).

First define minus_r which takes the arguments in reverse order

Example: 4-1 minus_r(1,4) =3

Minus_r(0,x) = p1-1(x)

Minus_r (y+1,x) =dec(P23(y,minus(y,x),x))

Minus(x,y) = minus(P22(x,y),P12(x,y))

******************************

Equal(x,y) = not(or(lev(minus(x,y)),lev(minus(P22(x,y)P12(x,y)))))

Not_equal(x,y) = not(equal(x,y))

The above two can be reversed getting rid of the extra not.

******************************

Mult

Mult(0,y) = Zero(y)

Mult (x+1,y) =add(P23(x,mult(x,y),y),P33(x,mult(x,y),y))

******************************

Guard: returns 0 if x equals 0 and returns y otherwise.

Guard (0,y) = zero(y)

Guard (x+1,y) =P33(x,Guard(x,y),y)

******************************

Lev: returns 1 if x is anything but zero.

Lev(0) = zero(0)

Lev(x+1) = succ(Zero(P13(x,lev(x))))

***********

Leví : opposite of above.

Lev(0) = succ(0)

Lev(x+1) = zero(P12(x,lev(x)))

******************************

Max

Max(x,y) = add(x,Minus(y,x))

******************************

Fact

Fact((0) = succ(o)

Fact(x+1) = mult(succ(x),fact(x))

 

Exponent is called pow and pow(x,y) is y^x

Pow(0,y) = succ(zero(y))

Pow(x+1,y) = Mult(P22(x,y),pow(x,y))

 

Min(x,y) = Minus(P12(x,y),Minus(x,y))