Page 371 - Discrete Mathematics and Its Applications

350 5 / Induction and Recursion

∗
The basis step of the recursive definition of strings says that the empty string belongs to .
The recursive step states that new strings are produced by adding a symbol from to the end of
∗
strings in .At each application of the recursive step, strings containing one additional symbol
are generated.
∗
EXAMPLE 6 If ={0, 1}, the strings found to be in , the set of all bit strings, are λ, specified to be in ∗
in the basis step, 0 and 1 formed during the first application of the recursive step, 00, 01, 10,
and 11 formed during the second application of the recursive step, and so on. ▲

Recursive definitions can be used to define operations or functions on the elements of
recursively defined sets. This is illustrated in Definition 2 of the concatenation of two strings
and Example 7 concerning the length of a string.

DEFINITION 2 Two strings can be combined via the operation of concatenation. Let be a set of symbols
∗
and the set of strings formed from symbols in . We can define the concatenation of two
strings, denoted by ·, recursively as follows.
BASIS STEP: If w ∈ , then w · λ = w, where λ is the empty string.
∗
∗
∗
RECURSIVE STEP: If w 1 ∈ and w 2 ∈ and x ∈ , then w 1 · (w 2 x) = (w 1 · w 2 )x.

The concatenation of the strings w 1 and w 2 is often written as w 1 w 2 rather than w 1 · w 2 .By
repeated application of the recursive definition, it follows that the concatenation of two strings
w 1 and w 2 consists of the symbols in w 1 followed by the symbols in w 2 . For instance, the
concatenation of w 1 = abra and w 2 = cadabra is w 1 w 2 = abracadabra.

EXAMPLE 7 Length of a String Give a recursive definition of l(w), the length of the string w.

Solution: The length of a string can be recursively defined by

l(λ) = 0;
∗
l(wx) = l(w) + 1if w ∈ and x ∈ .
▲
Another important use of recursive definitions is to define well-formed formulae of various
types. This is illustrated in Examples 8 and 9.

EXAMPLE 8 Well-Formed Formulae in Propositional Logic We can define the set of well-formed for-
mulae in propositional logic involving T, F, propositional variables, and operators from the set
{¬, ∧, ∨, →, ↔}.
BASIS STEP: T, F, and s, where s is a propositional variable, are well-formed formulae.

RECURSIVE STEP: If E and F are well-formed formulae, then (¬E), (E ∧ F), (E ∨ F),
(E → F), and (E ↔ F) are well-formed formulae.
For example, by the basis step we know that T, F, p, and q are well-formed formulae,
where p and q are propositional variables. From an initial application of the recursive step,
we know that (p ∨ q), (p → F), (F → q), and (q ∧ F) are well-formed formulae. A sec-
ond application of the recursive step shows that ((p ∨ q) → (q ∧ F)), (q ∨ (p ∨ q)), and
((p → F) → T) are well-formed formulae. We leave it to the reader to show that p¬Ð q ,
pq∧, and ¬Ð pq are not well-formed formulae, by showing that none can be obtained using
the basis step and one or more applications of the recursive step. ▲