Stone: Section 4

From CSWiki

True or False

Here we declare that 0 will be recognized as false and 1 as true. For all of the functions that we write that return true or false, they should return 1 or 0, respectively. We will also recognize any positive number to be "truish," which for all intents and purposes, will be treated as true.

Theorems

Theorem 4.1: zero?(x) is primitive recursive

 Tests whether the given input is zero
 zero?(x) = 1 if x==0; 0 otherwise
 zero?(0) = 1
 zero?(63454) = 0

Theorem 4.2: not(x) is primitive recursive

 Negates a given input. Note that this is identical to zero?
 not(x) = 1 if x==0; 0 otherwise
 not(0) = 1
 not(1) = 0
 not(23243) = 0

Theorem 4.3: positive?(x) is primitive recursive

 Checks if given input is positive. As positivity is the definition of "truish," this function will sometimes be called truish?
 positive?(x) = 0 if x==0; 1 otherwise
 positive?(0) = 0
 positive?(233) = 1

Theorem 4.4: even?(x) is primitive recursive

 Tests if given input is even (a multiple of 2).
 even?(x) = 1 if there exists some natural number, y, such that 2*y=x; 0 otherwise
 even?(0) = 1
 even?(16) = 1
 even?(7) = 0

Theorem 4.5: and(x,y) is primitive recursive

 Tests if the two given input are both true. If either were false, when we multiplied them together, the output would be false (0). 
 Therefore, we test if the output of multiplying them together is truish (not-false).
 and(x,y) = truish?(x * y) = 0 if x == 0 || y == 0; 1 otherwise
 and(50,23) = truish?(50 * 23) = 1
 and(0, 8) = truish?(0 * 8) = truish?(0) = 0

Theorem 4.6: or(x,y) is primitive recursive

 Tests if either (or both) of the inputs are true. Note that as we are testing both inputs, both inputs must halt. 
 or(x,y) = not(and(not(x), not(y))) =  = 1 if x > 0 || y > 0; 0 otherwise
 or(5,0) = 
 or(0,0) = 
 or(9,7) = 

Theorem 4.7: case construction (if-then) is primitive recursive

 The if construction is actually just a macro. All inputs are tested, so they must all halt. 
 In the future, we will use the format ¿ n where n is the valence of p (described below).
 Tests if the outcome of some function, p, is truish. If so, returns the output of function, f, on same input. 
 If p is false, returns the output of function, g, on same input.
 Let h = [¿ ]
 h(1) = predecessor(1) = 0
 h(76) = successor(76) = 77
 h(1003) = predecessor(1003) = 1002