Mathematics for Computer Science

6.5. Induction in Computer Science 189

Problems for Section 6.1

Class Problems

Problem 6.1.
Prove that for all stringsr;s;t 2 A

.r
s/
tDr
.s
t/:

Problem 6.2.
Thereversalof a string is the string written backwards, for example, rev.abcde/D
edcba.

(a)Give a simple recursive definition of rev.s/based on the recursive defini-
tion 6.1.1 ofs 2 Aand using the concatenation operation 6.1.3.

(b)Prove that

rev.s
t/Drev.t/
rev.s/;

for all stringss;t 2 A.

Problem 6.3.
The Elementary 18.01 Functions (F18’s) are the set of functions of one real variable
defined recursively as follows:
Base cases:
 The identity function, id.x/WWDxis an F18,

 any constant function is an F18,

 the sine function is an F18,

Constructor cases:

Iff;gare F18’s, then so are

1.fCg,fg, 2 g,

2. the inverse functionf^1 ,


3. the compositionfıg.
   (a)Prove that the function1=xis an F18.

Warning:Don’t confuse1=xDx^1 with the inverse id^1 of the identity function
id.x/. The inverse id^1 is equal to id.