Computing and Reasoning with Piecewise Algebraic Functions
Michael Bulmer
mrb@maths.uq.edu.au
University of Queensland
Australia
Desmond Fearnley-Sander
dfs@hilbert.maths.utas.edu.au
University of Tasmania
Australia
Tim Stokes
stokes@prodigal.murdoch.edu.au
Murdoch University
Australia
Abstract
A main concern of elementary algebra is the interplay between algorithms and their associated functions. For example, the identity
x^2-1 = (x-1)(x+1)
captures the fact that two different algorithms have the same input-output behaviour. We advocate adoption of this perspective in the teaching of algebra. In the present paper, we address a question that then suggests itself: can the calculus of polynomials be extended in a simple way to take in other basic algebraic functions such as the absolute value function. The theory of Boolean affine combinations, which we introduced in [1], supports such an extension.
While the theory is applicable to arbitrary (many-sorted) universal algebras, our presentation here focusses on real piecewise-defined polynomials, and is illustrated by simple algebraic proofs of theorems such as ||x|| = |x| and the triangle inequality. A prototype system has been implemented (in Mathematica), which supports both the evaluation of piecewise-defined algebraic functions and automatic reasoning about the properties of such functions. The trace of a session with this package is included.
References: [1] M. Bulmer, D. Fearnley-Sander and T. Stokes, `Towards a Calculus of Algorithms', Bull. Austral. Math. Soc., 50 (1994), pp. 81--89.
[2] H. Ehrig and B. Mahr, Fundamentals of algebraic specification, EATCS monographs on theoretical computer science, v. 6 (Springer-Verlag, Berlin, 1985).
[3] H. Lausch and W. Nobauer, Algebra of polynomials, North-Holland Mathematical Library 5 (North-Holland, Amsterdam, 1973).
[4] A.G. Pinus, `Boolean Constructions in Universal Algebra', Russ. Math. Surv. 47, 4 (1992), 157--198.
Key Words: algebraic computation, Boolean affine combination, Boolean power, piecewise polynomial, Mathematica.
© ATCM, Inc. 2001. |
