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.

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.