E-Book Overview
This book deals with the presentation and systematic design of mathematical proofs, including correctness proofs of algorithms. Its purpose is to show how completeness of argument, an important constraint especially for the correctness of algorithms, can be combined with brevity. The author stresses that the use of formalism is indispensible for achieving this. A second purpose of the book is to discuss matters of design. Rather than addressing psychological questions, the author deals with more technical questions like how analysis of the shape of the demonstrandum can guide the design of a proof. This technical rather than psychological view of heuristics together with the stress on exploiting formalism effectively are two key features of the book. The book consists of two independently readable parts. One part includes a number of general chapters discussing techniques for clear exposition, the use of formalism, the choice of notations, the choice of what to name and how to name it, and so on. The other part consists of a series of expositional essays, each dealing with a proof or an algorithm and illustrating the use of techniques discussed in the more general chapters.
E-Book Content
Lecture Notes in Computer Science Edited by G. Goos and J. Hartmanis
445
A.J.M. van Gasteren
On the Shape of Mathematical Arguments
Springer-Verlag
Lecture Notes in Computer Science Edited by G. Goos and J. Hartmanis
445
A.J.M. van Gasteren
On the Shape of Mathematical Arguments Foreword by Edsger W. Dijkstra
Springer-Verlag Berlin Heidelberg New York London Paris Tokyo Hong Kong Barcelona
Editorial Board
D. Barstow W. Brauer P. Brinch Hansen D. Gries D. Luckham C. Moler A. Pnueli G. Seegmiiller J. Stoer N. Wirth Author
Antonetta J. M. van Gasteren University of Groningen, The Netherlands
and University of Utrecht, The Netherlands
Correspondence address: Edelweislaan 20 5582 BWWaalre, The Netherlands
CR Subject Classification (1987): F.3.1, D.2.4
o'-3..s
ISBN 3-540-52849-0 Springer-Verlag Berlin Heidelberg New York ISBN 0-387-52849-0 Springer-Verlag New York Berlin Heidelberg
o-a
M.0
a00.0
(0.6
This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting, reproduction on microfilms or in other ways, and storage in data banks. Duplication of this publication or parts thereof is only permitted under the provisions of the German Copyright Law of September 9, 1965, in its version of June 24, 1985, and a copyright fee must always be paid. Violations fall under the prosecution act of the German Copyright Law. C Springer-Verlag Berlin Heidelberg 1990 Printed in Germany CC)
Printing and binding: Druckhaus Beltz, Hemsbach/Bergstr. 2145/3140-543210 - Printed on acid-free paper
Foreword While current curricula extensively teach existing mathematics, they pay scant attention to the doing of mathematics, i.e., to the question of how
to design and to present solutions. If any attention to these issues is paid at all, they are treated separately: design of solutions, i.e., "problem solving" or "mathematical invention", is viewed as a psychological issue, as a matter of mathematical intuition, while presentation is viewed ran
as a matter of personal style or as an issue of education. Most mathematicians consider psychology and pedagogy as sciences too soft to be respectable, and consequently the subject of how to do mathematics has almost been tabooed.
P,,
`-t-
C1.
.'1
The great merit of A.J.M. van Gasteren's work is to have br