The Little Prover
The Little Prover
Daniel P. Friedman
Carl Eastlund
Drawings by Duane Bibby
Foreword by J Strother Moore
Afterword by Matthias Felleisen
The MIT Press
Cambridge, Massachusetts
London, England
© 2015 Massachusetts Institute of Technology
All rights reserved. No part of this book may be reproduced in any form by any electronic
or mechanical means (including photocopying, recording, or information storage and
retrieval) without permission in writing from the publisher.
MIT Press books may be purchased at special quantity discounts for business or sales
promotional use. For information, please e-mail special_sales@mitpress.mit.edu.
This book was set in Computer Modern by the authors using LATEX. Printed and bound
in the United States of America.
Library of Congress Cataloging-in-Publication Data
Friedman, Daniel P.
The little prover / Daniel P. Friedman and Carl Eastlund; drawings by Duane Bibby.
p.
cm.
Includes bibliographical references and index.
ISBN 978-0-262-52795-8 (pbk. : alk. paper)
1. Automatic theorem proving. 2. LISP (Computer program language) I. Eastlund,
Carl II. Title.
QA76.9.A96F745
511.3′6028563—dc23
2015
10 9 8 7 6 5 4 3 2 1
2015001271
To Mary, Robert, Shannon, Rachel, Sara,
Samantha, Brooklyn, Chase, Aria, and
to the memory of Brian (1969–1993).
To Mom, Dad, Sharon, Paul Ragnar,
Grace, Claire, Paul Duncan, and Ruth.
((Contents)
(Foreword ix)
(Preface xi)
(((1. Old Games, New Rules) 2) (Examples 181))
(((2. Even Older Games) 14) (Examples 182))
(((3. What’s in a Name?) 32) (Proofs 183))
(((4. Part of This Total Breakfast) 42) (Proofs 184))
(((5. Think It Over, and Over, and Over) 58) (Proofs 185))
(((6. Think It Through) 76) (Proofs 187))
(((7. Oh My, Stars!) 88) (Proofs 188))
(((8. Learning the Rules) 106) (Proofs 192))
(((9. Changing the Rules) 114) (Proofs 193))
(((10. The Stars Are Aligned) 138) (Proofs 196))
((A. Recess) 164)
((B. The Proof of the Pudding) 180)
((C. The Little Assistant) 202)
((D. Restless for More?) 216)
(Afterword 221)
(Index 222))