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.