## CS 5315 Homework #1

**Date Assigned:** Tuesday, January 18, 2005
**Due Date:** Thursday, January 20, 2005

1. In the class, we proved that the function "previous" defined as
a-1 if a>0 and 0 otherwise is primitive recursive. Use this result to
prove that "subtraction" defined as sub(a,b)=a-b if a>b and 0
otherwise is also primitive recursive.

Answer:
Once the function prev(n) (previous) is described as primitive
recursive, we can describe the desired function sub as follows:
sub(n,0)=n
sub(n,m+1)=prev(sub(n,m))

2. Prove that in the standard interpretation of Boolean variables (0
means false and 1 means true) logical operations "not", "and", and
"or" are primitive recursive functions.
Answer:
It is easy to check that and(n,m)=n*m, and we already know that
multiplication is a primitive recursive function.
To prove that "or" is primitive recursive, we can use the de Morgan
rule, according to which or(n,m)=not(and(not(n),not(m))). We already
know that "not" and "and" are primitive recursive, so their
composition - "or" - is also primitive recursive.