Stone: Section 5

From CSWiki

Contents 1 Theorem 5.1 2 Theorem 5.2 3 Theorem 5.3 4 Theorem 5.4 5 Theorem 5.5 6 Theorem 5.6

Theorem 5.1

equal?(x,y) is primitive recursive

 Tests whether x is equal to y by testing if the disparity is zero.
 equal?(x,y) = 1 if x==y; 0 otherwise
 equal?(1,2) = 0
 equal?(2,2) = 1

Theorem 5.2

less-or-equal?(x,y) is primitive recursive

 Tests whether x is y. Performs this by performing subtract, which returns zero if x - y == 0 or if x < y.
 less-or-equal?(x,y) = 0 if x > y; 1 otherwise
 less-or-equal?(5,5) = 1
 less-or-equal?(5,9) = 1
 less-or-equal?(9,5) = 0

Theorem 5.3

• greater-or-equal?(x,y) is primitive recursive

 Tests if x  y. Performed by reversing the order of the inputs in less-or-equal?

• less?(x,y) is primitive recursive

 Tests if x < y. Tests if greater-or-equal? is not true

• greater?(x,y) is primitive recursive

 Tests if x > y. Tests if less-or-equal? is not true

• unequal?(x,y) is primitive recursive

 Tests if x . Tests if equal? is not true

Theorem 5.4

• redniamer(x,y) is primitive recursive

 Finds the remainder of the two inputs, though the inputs are in reverse order.
 redniamer(x,y) = y % x
 redniamer(5,8) = 8 % 5 = 3
 redniamer(23,2) = 2 % 23 = 2 
 x is the divisor
 y is the dividend

• remainder(x,y) is primitive recursive

 Simply reverses the inputs to redniamer.
 remainder(x,y) = redniamer(y,x) = x % y
 x is the dividend
 y is the divisor

Note that a synonymous name for the remainder function is "modulo."

Theorem 5.5

divides?(x,y) is primitive recursive

 Tests if x divides evenly into y.
 divides?(x,y) = 1 if there exists some natural number i such that i*x=y; 0 otherwise
 divides?(5,20) = 1
 divides?(20, 5) = 0
 divides?(7, 3) = 0
 x is the divisor
 y is the dividend

Theorem 5.6

• tneitouq(x,y) is primitive recursive

 Returns the quotient of y divided by x, even when x does not divide evenly in to y.
 tneitouq(x,y) = 
 tneitouq(5,12) = 
 tneitouq(12,3) = 
 tneitouq(28,2) = 
 x is the divisor
 y is the dividend

• quotient(x,y) is primitive recursive

 Simply reverses the inputs to tneitouq.
 quotient(x,y) = tneitouq(y,x) = 
 x is the dividend
 y is the divisor