384 pages 10x7 inches w/ CDROM
December 2003 Hardcover
ISBN 1-58949-023-1


     Buy It

This book is rare -- perhaps the only one of its type -- in that it simultaneously provides the basis for diverse courses in logic, mathematics, and automated reasoning; teaches how research can be successfully conducted; and presents results that had eluded various masters for many decades. Key to obtaining these results is the use of strategies and methodologies, detailed in this volume, and the marvelous program OTTER (featured here) -- which automates logical reasoning, deducing millions of conclusions that follow inevitably from the hypotheses supplied by the user. In this book, various aspects of the newly discovered Hilbert's twenty-fourth problem are addressed. The included CD-ROM offers OTTER in various forms, numerous input files, and a large number of proofs that are new. By experimenting with these offerings, both the new researcher and the expert alike may experience the excitement of attacking deep open questions and discovering missing and elegant proofs.


1 Challenge and Reward
  1.1 Unwitting Foundation for Automation
  1.2 The Arrival of Automated Reasoning
     1.2.1 Representing Information, Language
     1.2.2 Drawing Conclusions, Inference Rules
     1.2.3 Controlling Reasoning, Strategy 
2 Methodology, Strategy and a Significant Proof

  2.1 Lemma Adjunction
  2.2 Term Avoidance
  2.3 The Role of Prior Knowledge
  2.4 Proof Contraction
  2.5 Three Short Proofs for the Lukasiewicz 23-Letter Formula
3 Attacking Hilbert's Twenty-Fourth Problem

  3.1 A Basis for Refinement Methodologies
  3.2 A Tidy Approach for Abridging the Meredith Proof
  3.3 A Most Intriguing Proof
  3.4 Other Methodologies, Other Types of Refinement
4 Other Logics

  4.1 Lukasiewicz's Infinite-valued Sentential Calculus
  4.2 Equivalential Calculus
  4.3 Revisiting Propositional Calculus
  4.4 Modal Logic
  4.5 Relevance Logic
  4.6 Intuitionistic Logic
5 Equality

  5.1 Group Theory
     5.1.1 The Commutator-Normal Subgroup Problem
     5.1.2 Single Axioms
     5.1.3 Groups of Odd Exponent 
     5.1.4 Groups of Even Exponent 
  5.2 Lattice Theory
  5.3 Quasilattice Theory
  5.4 Moufang Loops
  5.5 Boolean Algebra
  5.6 Ring Theory
  5.7 Combinatory Logic
  5.8 Ortholattices
 6 Missing Proofs Classified
  6.1 Curiosity and Incentive
  6.2 Shorter Proofs 
  6.3 Variable Richness 
  6.4 Proof Complexity
  6.5 Term Structure
  6.6 Lemma Avoidance
  6.7 Proof Size
  6.8 Proofs Other Than Axiomatic
  6.9 Proof-Tree Level   
  6.10 Proofs Not Fully Detailed  
  6.11 Generality 
  6.12 Conjectures
  6.13 Axiom Dependency
  6.14 Fully Automated Proofs
  6.15 Axiomatic Deductive Power 
7 New Fine Wines, Recent Discoveries, and Questions Still Open

  7.1 Stories, Myths and Insights
  7.2 Successes, Challenges and Open Questions
     7.2.1 Lattice Theory and Related Fields
     7.2.2 Equivalential Calculus
     7.2.3 Boolean Algebra
     7.2.4 Modal Logic
     7.2.5 Group Theory  
     7.2.6 Propositional Calculus
     7.2.7 Combinatory Logic
     7.2.8 Relevance Logic
     7.2.9 BCK Algebras
     7.2.10 Lukasiewicz's Infinite-Valued Sentential Calucus
     7.2.11 Strategy, Methodology and Pedagogy 
8 Introducing OTTER

  8.1 Lists
  8.2 Parameters
  8.3 Options 
  8.4 An Example
9 Hilbert, Turing and The Future of Automated Reasoning

  9.1 Proof Presentation: The Hilbert-Turning Test
  9.2 Proof Discovery: The Grand Turning Test
  9.3 Automated Reasoning vs. Artificial Intelligence 



Larry Wos, a senior mathematician at Argonne National Laboratory, is a world leader in automated reasoning. His introduction of the use of strategies and methodologies in the field has enabled significant advances in diverse areas of mathematics and logic, including the answering of open questions that had challenged researchers for more than seven decades. Dr. Wos (with his colleague Steve Winker) received the first prize for current achievement in automated theorem proving awarded by the American Mathematical Society in 1983, and in 1992 he received the first Herbrand Award in Automated Deduction. He is author of several books, including Automated Reasoning: 33 Basic Research Problems and The Automation of Reasoning: an Experimenter's Notebook with OTTER Tutorial. Dr. Wos is a poker player.

Gail Pieper is a technical writer and editor at Argonne National Laboratory. She has worked closely with Dr. Wos and has collaborated with him on two books: A Fascinating Country in the World of Computing: Your Guide to Automated Reasoning and the two-volume edition of The Collected Works of Larry Wos. Dr. Pieper is also on the Communication Arts faculty at Benedictine University, where she teaches editing, professional writing, and ancient Mediterranean literature. Dr Pieper is managing editor of the international Journal of Automated Reasoning.


The Mining of Missing Treasure

Most appealing - and sometimes even stirring - is a well-constructed case showing that, without doubt,  some given assertion holds. Typically, such a case is based on logical and flawless reasoning, on a sequence of steps that follow inevitably from the hypotheses used to deduce each. In other words, a proof is given establishing that the assertion under consideration indeed holds.

Such proofs are clearly crucial to logic and to mathematics. Not so obvious, but true, proofs are crucial to circuit design, program writing, and, more generally, to various activities in which reasoning plays a vital role. Indeed, most desirable is the case in which no doubt exists regarding the absence of flaws in the design of a chip, in the structure of a computer program, in the argument on which an important decision is based. Such careful reasoning is even the key factor in games that include chess and poker.

This book features one example after another of flawless logical reasoning the context is that of finding proofs absent from the literature. The means for finding the missing proofs is reliance on a single computer program, William McCune's automated reasoning program OTTER.

One motivating force for writing this book is to interest others in automated reasoning, logic and mathematics. As the text strongly indicates, we delight in using OTTER equally in two quite distinct activities: finding a proof where none is offered by the literature, and finding a proof far more appealing than any the literature provides. We believe that many other individuals, if introduced to this program, will also derive substantial enjoyment. Further, we believe that the challenge offered by the type of problem featured in this book can be as engrossing as solving puzzles and playing various games that appeal to the mind. Indeed, sometimes inexpressible is the excitement engendered when seeking a proof with fewer steps than was found by one of the great minds of the twentieth century. Some proofs are simply beautiful to behold.

A second motivating force resets with our obvious enjoyment of the type of research featured in this book. Like the fancier of fine wines, we continually seek new open questions to attack, whether (at one end of the spectrum) they concern the settling of a conjecture or (at the other end) the focus is on proof betterment. We encourage readers to send us additional open questions and challenging problems.

Another factor that motivated us was our wish to collect in a single volume a surprisingly large number of proofs, most of which were previously absent from the literature. In some cases, no proof was offered of any type; in some cases, the proof that was offered was far from axiomatic. And even where an axiomatic proof was presented, we have found and offer in many, many cases a proof that is in one or more ways a refinement: fewer steps, the absence of thought-to-be-required lemmas, the avoidance of certain types of term, and the like. We present axiomatic proofs only, some in the text and many more on the included CD-ROM. None of the proofs rely on induction, or on meta argument, or on higher-order logic. In one sense, the book can serve as an encyclopedia of proofs -- many new and many improved - a work that sometimes extends, sometimes replaces, and sometimes supplements the research of more than a century. These proofs offer the implicit challenge of finding others that are further improvements.

In a a rather different sense, the book may serve as the key to eventually answering one open question after another, whether the context is logic, mathematics, design, synthesis, or some other area relying on sound reasoning. In that regard, we include in detail numerous diverse methodologies we have found effective for settling a conjecture or for refining a proof. The methodologies are themselves intriguing. For an example, one methodology asks for two independent paths that lead to success and, rather than emphasizing what is common to both (their intersection), instead heavily focuses on what is not shared (their symmetric difference). A quite different and counterintuitive example (in effect) has the program avoid the attack successfully taken by one of the masters.

Although the emphasis here is on their use in the context of logic and mathematics, we conjecture that the methodologies we offer will prove most useful in a far wider context. We also suspect that, especially for those who enjoy solving puzzles and unraveling the mysteries of science, the nature of the strategies and methodologies will provide substantial stimulation.

If we succeed, this volume will introduce some readers to the excitement of discovering new results, increase the intrigue of those already familiar with such excitement, and (for the expert) add to the arsenal of weapons for attacking deep questions and hard problems.