Hantao Zhang - Böcker

In the 1970s, Boyer and Moore built one of the first automated theorem provers that was capable of proofs by mathematical induction. Today, the Boyer-Moore theorem prover remains the most successful in the field. For a long time, the research on automated mathematical induction was confined to very few people. In recent years, as more people realize the importance of automated inductive reasoning to the use of formal methods of software and hardware development, more automated inductive proof systems have been built. In 1992, the interested researchers in the field formed two consortia on automated inductive reasoning - the MInd consortium in Europe and the IndUS consortium in the United States. The two consortia organized three joint workshops in 1992-1995. There will be another one in 1996. This text documents advances in the understanding of the field and in the power of the theorem provers that can be built. In the first of six papers, the reader is provided with a tutorial study of the Boyer-Moore theorem prover. The other five papers present novel ideas that could be used to build theorem provers more powerful than the Boyer-Moore prover.

It has been shown how the common structure that defines a family of proofs can be expressed as a proof plan [5]. This common structure can be exploited in the search for particular proofs. A proof plan has two complementary components: a proof method and a proof tactic. By prescribing the structure of a proof at the level of primitive inferences, a tactic [11] provides the guarantee part of the proof. In contrast, a method provides a more declarative explanation of the proof by means of preconditions. Each method has associated effects. The execution of the effects simulates the application of the corresponding tactic. Theorem proving in the proof planning framework is a two-phase process: 1. Tactic construction is by a process of method composition: Given a goal, an applicable method is selected. The applicability of a method is determined by evaluating the method's preconditions. The method effects are then used to calculate subgoals. This process is applied recursively until no more subgoals remain. Because of the one-to-one correspondence between methods and tactics, the output from this process is a composite tactic tailored to the given goal. 2. Tactic execution generates a proof in the object-level logic. Note that no search is involved in the execution of the tactic. All the search is taken care of during the planning process. The real benefits of having separate planning and execution phases become appar­ ent when a proof attempt fails.