Chapter 3 - Recursive Definitions

Chapter 3: Recursive Definitions
---------------------------------------------------------
EVEN - the set of all even positive integers Rule 1: 2 is in EVEN
Rule 2: if x is in even, then x + 2 is in EVEN Note - a more succinct mathematical way of saying it: Rule 1: 2 Î EVEN
Rule 2: x Î EVEN Þ x + 2 Î EVEN Examples: 2, 4, 6,

---------------------------------------------------------
POLYNOMIAL - all polynomials (variable x)

Rule 1: any number Î POLYNOMIAL
Rule 2: the variable x Î POLYNOMIAL
Rule 3: p, q Î POLYNOMIAL Þ p + q, p - q, pq, (p) Î POLYNOMIAL Examples: x, xx, x - x, 2, 2xxx, (xxx2 - 3xx)xx

---------------------------------------------------------
AE - arithmetic expressions

Rule 1: any unsigned number Î AE
Rule 2: x Î AE Þ (x), -x Î AE
Rule 3: x,y Î AE Þ x + y, x – y, x*y, x/y, x**y Î AE different from the book's; avoids "if the first symbol is not + or -" nuisance statement by distinguishing between unary - (negation) and binary – (subtraction). Allows such expressions as "a + -b".

Examples: 3.14, 2 – 3, 4 + 5/2, (4 + 5)/2, (4 + 5)**(-4)

---------------------------------------------------------
WFF - Well-Formed (logical) Formulas

Rule 1: any letter a, b, c, … Î WFF
Rule 2: p Î WFF Þ (p), Øp Î WFF
Rule 3: p, q Î WFF Þ p ® q Î WFF Examples: a, (a), Øa, a ® b, Øa ® (a ® b)

Some Math (use it for HW)

Observation: Every natural number x < 2ⁿ is the sum of at most n powers of 2.

Let's show it for n = 5.

Think of the binary representation of such a number. 2⁵ = 32 can be represented in binary as:

32's position 16's position 8's position 4's position 2's position 1's position

1 0 0 0 0 0

Any number < 32 can be represented by at most 5 1's in positions not including the 32's position. E.g. 27 is:

32's position 16's position 8's position 4's position 2's position 1's position

XXX 1 1 0 1 1

That is, 27 = 2⁴ + 2³ + 2¹ + 2⁰

Hosted by www.Geocities.ws

32's position	16's position	8's position	4's position	2's position	1's position
1	0	0	0	0	0