Section 3.1 Recursive Definitions
165
and structural induction helps us deal with this “spread” of values in the set.
Recursively Defined Operations
Certain operations performed on objects can be defined recursively, as in Examples
9 and 10.
example 9
A recursive definition of the exponentiation operation a
n
on a nonzero real number
a, where n is a nonnegative integer, is
1. a
0
= 1
2. a
n
= (a
n − 1
)a for n ≥ 1
example 10
A recursive definition for multiplication of two positive integers m and n is
1. m(1) = m
2. m(n) = m(n − 1) + m for n ≥ 2
■
PRaCtiCe 8 Let x be a string over some alphabet. Give a recursive definition for the operation x
n
(concatenation of x with itself n times) for n ≥ 1.
In Section 1.1, we defined the operation of logical disjunction on two statement
letters. This definition can serve as the basis step for a recursive definition of the
disjunction of n statement letters, n ≥ 2:
1. A 1 ~ A 2 defined as in Section 1.1
2. A 1 ~ c~ A n = (A 1 ~ c~ A n−1 ) ~ A n for n > 2
(2)
Using this definition, we can generalize the associative property of disjunction
(tautological equivalence 2a) to say that in a disjunction of n statement letters,
grouping by parentheses is unnecessary because all such groupings are equivalent
to the general expression for the disjunction of n statement letters. In symbolic
form, for any n with n ≥ 3 and any p with 1 ≤ p ≤ n − 1,
(A 1 ~ c~ A p ) ~ (A p+1 ~ c~ A n ) 3 A 1 ~ c~ A n
This equivalence can be proved by induction on n. For n = 3,
A 1 ~ (A 2 ~ A 3 ) 3 (A 1 ~ A 2 ) ~ A 3
(by equivalence 2a)
= A 1 ~ A 2 ~ A 3
(by equation (2))
01
λ
10
1100
0100 1010
0011