Page 372 - Discrete Mathematics and Its Applications

5.3 Recursive Definitions and Structural Induction 351

EXAMPLE 9 Well-Formed Formulae of Operators and Operands We can define the set of well-formed
formulae consisting of variables, numerals, and operators from the set {+, −, ∗, /, ↑} (where ∗
denotes multiplication and ↑ denotes exponentiation) recursively.
BASIS STEP: x is a well-formed formula if x is a numeral or a variable.
RECURSIVE STEP: If F and G are well-formed formulae, then (F + G), (F − G), (F ∗ G),
(F/G), and (F ↑G) are well-formed formulae.
For example, by the basis step we see that x, y, 0, and 3 are well-formed formulae (as is
any variable or numeral). Well-formed formulae generated by applying the recursive step once
include (x + 3), (3 + y), (x − y), (3 − 0), (x ∗ 3), (3 ∗ y), (3/0), (x/y), (3↑x), and (0↑3).
Applying the recursive step twice shows that formulae such as ((x + 3) + 3) and (x − (3 ∗ y))
are well-formed formulae. [Note that (3/0) is a well-formed formula because we are concerned
only with syntax matters here.] We leave it to the reader to show that each of the formulae x3 +,
y ∗+ x, and ∗ x/y is not a well-formed formula by showing that none of them can be obtained
from the basis step and one or more applications of the recursive step. ▲

We will study trees extensively in Chapter 11. A tree is a special type of a graph; a graph
is made up of vertices and edges connecting some pairs of vertices. We will study graphs in
Chapter 10. We will briefly introduce them here to illustrate how they can be defined recursively.

DEFINITION 3 The set of rooted trees, where a rooted tree consists of a set of vertices containing a distin-
guished vertex called the root, and edges connecting these vertices, can be defined recursively
by these steps:
BASIS STEP: A single vertex r is a rooted tree.
RECURSIVE STEP: Suppose that T 1 ,T 2 ,...,T n are disjoint rooted trees with roots
r 1 ,r 2 ,...,r n , respectively. Then the graph formed by starting with a root r, which is not
in any of the rooted trees T 1 ,T 2 ,...,T n , and adding an edge from r to each of the vertices
r 1 ,r 2 ,...,r n , is also a rooted tree.

In Figure 2 we illustrate some of the rooted trees formed starting with the basis step and applying
the recursive step one time and two times. Note that infinitely many rooted trees are formed at
each application of the recursive definition.

Basis step

Step 1

Step 2

• • • • • •

FIGURE 2 Building Up Rooted Trees.