Go backward to
Structural Induction
Go up to
Top
Go forward to
Simultaneous Induction
Example
E: Expression
E ::= zero | E
1
* E
2
| (E)
Proposition
All members of Expression have the same number of left parentheses as the number of right parentheses.
Proof
zero: left(
E
) = 0 = right(
E
).
E
1
*E
2
: left(
E
) = left(
E
1
) + left(
E
2
) = right(
E
1
) + right(
E
2
) = right(
E
).
(E')
: left(
E
) = 1 + left(
E'
) = 1 + right(
E'
) = right(
E
).
Author:
Wolfgang Schreiner
Last Modification: October 13, 1997
