Institut for Matematik og Datalogi Odense Universitet March 1, 1996

JFB

DM11 – F96 – Lecture 5

Lecture, February 28

We finished sections 2.5, 3.1, and 3.2 in the textbook and began on section 3.3.

Lecture, March 6

We will cover section 3.3 and structural induction. We will skip sections 3.4 and 3.5, since they are covered in other courses. We may begin on chapter 4.

Lecture, March 13

We will cover sections 4.1 through 4.5 of chapter 4.

Problems to be discussed in week 11

• 6, 10, 12, 16, 18, 24, 28, 30, 32, 36, and 38 from section 3.3.

12 is probably the hardest. Note that you should use structural induction for 24 and 28. Note that a palindrome is a string which is the same as its reverse.

• Use structural induction to show that if a well-formed formula of variables, numerals, and operators from {+, −, ∗, /, ↑} has n operators, the sum of the number of variables and numerals is n + 1.

• Show that concatenation is an associative operation, i.e. (x ⊙ y) ⊙ z = x ⊙ (y ⊙ z). Use the definitions given in the notes below.

• Give a recursive definition of binary trees with height h, where the height of the tree is defined to be the number of nodes on the longest path from the root to a leaf. Use structural induction to show that a binary tree of height h has at most 2^{h} − 1 nodes.

Structural Induction

In computer science, recursively defined sets occur in many places. The wellformed formulae and strings defined in section 3.3 of the textbook by Rosen are good examples, but binary trees are perhaps an even better known example. When a set X is defined recursively, a set of basis elements S_{0} is defined, along with a finite set of operators, and together these define an infinite sequence of sets {S_{i} | i ≥ 0}. S_{i+1} will contain all of the objects in S_{i}, plus all of the objects which can be obtained from objects in S_{i} by applying one of the operators. Then, the set X being defined is the union of all of the sets S_{i}. For example, the set of strings Σ^{∗} over an alphabet Σ contains the basis elements S_{0} = {λ}, where λ is the empty string, and the operations are concatenation on the right by the different elements of Σ. Thus, if x ∈ Σ^{∗} and a ∈ Σ, then xa ∈ Σ^{∗}. So S_{n} is the set of all strings of length at most n, and Σ^{∗} contains all strings of finite length. When Σ^{∗} is defined in this recursive manner, then the concatenation of strings should also be defined recursively. It can be done as follows: Suppose x, y ∈ Σ^{∗} and a ∈ Σ. Then x ⊙ λ = x, and x ⊙ ya = (x ⊙ y)a. Example 12 in section 3.3 is an example of what is called structural induction, which often used for proving properties of recursively defined sets. It is no different from the mathematical induction defined in the text, with the inductive hypothesis being that something holds for every element in the set S_{n}, and the inductive step being to show that then it must also hold for S_{n+1}. Structural induction. Suppose X is a recursively defined set with basis elements S_{0}. Let {S_{i} | i ≥ 0} be the sequence of sets defined by the basis elements and operators. Let P be a propositional function defined on the elements of X (so X is a subset of the universe of discourse). To prove P (x) holds for all x ∈ X:

• Basis step: Prove that P (y) holds for all y ∈ S_{0}.

• Inductive step: Show that if P (y) holds for all y ∈ S_{n}, then P (z) also holds for all z ∈ S_{n+1}.

Proving the inductive step is the same as proving, for each operator ⊕ in the recursive definition, that if P holds for some elements x_{1}, x_{2},..., x_{k} (where k = 1 if the operator is unary), then P holds for the element ⊕(x_{1}, x_{2}, ..., x_{k}). When using structural induction to prove a proposition P concerning strings over an alphabet Σ, one proves that P holds for the empty string as the basis step. Then, one shows that if it holds for some string y, it holds for every string ya where a ∈ Σ.

Example with strings: Let [a] denote the string consisting only of a. The reverse of a string can be defined as follows: λ^{R} = λ, (xa)^{R} = [a] ⊙ (x^{R}), if x ∈ Σ^{∗} and a ∈ Σ. Note that the notation [a] is used to make it clear when a is being used as an element of Σ and when it is being used as a string. In xa, it is the last element of a string. In [a] ⊙ (x^{R}), it must be a string since it is the first operand in a concatenation operation. To prove that applying the reverse operation twice to a string gives the original string, we first prove the following claim: Claim: For all strings x over Σ and all a ∈ Σ, ([a] ⊙ x)^{R} = x^{R}a. Pf. (By structural induction on x.) Basis step: x = λ. ([a] ⊙ x)^{R} = ([a] ⊙ λ)^{R} = (λa)^{R} = [a] ⊙ (λ)^{R} = [a] ⊙ λ = λa = λ^{R}a = x^{R}a. √ Inductive step: Assume that for some string y, for all a ∈ Σ, ([a] ⊙ y)^{R} = y^{R}a. Consider any string x = yb where b ∈ Σ. Then ([a] ⊙ x)^{R} = ([a] ⊙ yb)^{R} = (([a] ⊙ y)b)^{R} = [b] ⊙ ([a] ⊙ y)^{R} = [b] ⊙ (y^{R}a) (the last equality is by the induction hypothesis). But, by the definitions of concatenation and reverse, [b] ⊙ (y^{R}a) = ([b] ⊙ y^{R})a = (yb)^{R}a = x^{R}a. √ The claim follows by structural induction. □ Thm. For all strings x over Σ, (x^{R})^{R} = x. Pf. (By structural induction on x.) Basis step: x = λ. (x^{R})^{R} = (λ^{R})^{R} = λ^{R} = λ. √ Inductive step: Assume that (y^{R})^{R}. Consider any string x = ya where a ∈ Σ. Then (x^{R})^{R} = ((ya)^{R})^{R} = ([a] ⊙ (y^{R}))^{R} = (y^{R})^{R}a = ya = x. √ The theorem follows by structural induction. □ As mentioned earlier, the binary tree is probably the best known example of a set defined recursively. Def. A binary tree is either empty or it consists of a node called the root together with two binary trees called the left subtree and the right subtree of the root. A node is a leaf if its left and right subtree are empty; otherwise it is an internal node. When using structural induction to prove a proposition P concerning binary trees, one proves that P holds for the empty tree as the basis step. Then one shows that if P holds for two subtrees L and R, it holds for the tree with root r, left subtree L, and right subtree R. As an example, consider the following:

Thm. A binary tree with n internal nodes has at most n + 1 leaves. Pf. (By structural induction.) Basis step: The empty tree has zero internal nodes and zero leaves. √ Inductive step: Suppose L is a binary tree with n_{1} internal nodes and at most n_{1} + 1 leaves and R is a binary tree with n_{2} internal nodes and at most n_{2} + 1 leaves. Consider the tree T with root r, left subtree L and right subtree R. If both L and R are empty, then r is a leaf, so there are zero internal nodes and one leaf. √ Otherwise, r is an internal node of T, the internal nodes of L and R are also internal nodes of T, and the leaves of L and R are the leaves of T. Thus T has 1 + n_{1} + n_{2} internal nodes and no more than (n_{1} + 1) + (n_{2} + 1) = 2 + n_{1} + n_{2} (i.e. at most one more than the number of internal nodes) leaves. √ The theorem follows by structural induction. □