Automatic Case Analysis in Proof by Induction
Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence. Automated Reasoning. Pages 88-93.
© 1993 International Joint Conferences on Artificial Intelligence
Abstract
We propose a new procedure for proof by induction in conditional theories where case analysis is simulated by term rewriting. This technique reduces considerably the number of variables of a conjecture to be considered for applying induction schemes (inductive positions). Our procedure is presented as a set of inference rules whose correctness has been formally proved. Moreover, when the axioms are ground convergent and the defined functions are completely defined over free constructors, it is possible to apply the system for refuting conjectures. The procedure is even refutationally complete for conditional equations with boolean preconditions (under the same hypotheses). The method is entirely implemented in the prover SPIKE . This system has proved interesting examples in a completely automatic way, that is, without interaction with the user and without ad-hoc heuristics. It has also proved the challenging Gilbreath card trick, with only, 5 easy lemmas.
- [Bevers, 1993] E. Bevers. Automated Reasonning in Condi- tional Algebric Specifications: Termination and Proof by Consistency. PhD thesis, Katholieke Universiteit Leuven, Belgium, 1993.
- [Bouhoula et al., 1992a] A. Bouhoula, E. Kounalis, and M. Rusinowitch . Automated mathematical induction. Technical Report 1636, INRIA, 1992.
- [Bouhoula et al., 1992b] A. Bouhoula, E. Kounalis, and M. Rusinowitch. Spike: an automatic theorem prover. In Proceedings of LPAR '92, volume 624 of LNAI, Saint Pe- ters bourg, Russia, July 1992. Springer-Verlag.
- [Boyer and Moore, 1979] R. S. Boyer and J. S. Moore. A Computational Logic. Academic Press, New York, 1979.
- [Bronsard and Reddy, 1990] F. Bronsard and S. Reddy. Con- ditional rewriting in focus. InS. Kaplan and M. Okada, ed- itors, Proceedings of the 2nd Workshop on Conditional and Typed Rewriting Systems, volume 516 of LNCS. Springer- Verlag, 1990.
- [Bundy et al., 1989] A. Bundy, F. van Harmelen, A. Smaill, and A. Ireland. Extensions to the rippling-out tactic for guiding inductive proofs. In M. E. Stickel, editor, 10th In- ternational Conference on Automated Deduction, volume 449 of LNAI, pages 132-146. Springer-Verlag, July 1989.
- [Chadha and Plaisted, 1992] R. Chadha and D.A. Plaisted. Mechanizing mathematical induction. Presented at the 94 Automated Reasoning Second International Symposium on Artificial Intelligence and Mathematics, Fort Lauderdale, Florida, 1992.
- [Dershowitz and Jouannaud, 1990] N. Dershowitz and J .-P. Jouannaud. Rewrite systems. In J. van Leuven, editor, Handbook of Theoretical Computer Science. Elsevier Sci- ence Publishers North-Holland, 1990.
- [Dershowitz et al., 1988] N. Dershowitz, M. Okada, and G. Sivakumar. Canonical conditional rewrite systems. In Proceedings 9th International Conference on Automated Deduction, Argonne {fll., USA}, volume 310 of LNCS. Springer-Verlag, May 1988.
- L. Fribourg. A strong restriction of the in- ductive completion procedure. In Proceedings 13th Inter- national Colloquium on Automata, Languages and Pro- gramming, volume 226 of LNCS, pages 105-115. Springer- Verlag, 1986.
- [Huber, 1991] M. Huber. Test-set approaches for ground re- ducibility in term rewriting systems, characterizations and new applications. Master's thesis, Technische Universitii.t Berlin, 1991.
- [Huet and Hullot, 1982] G. Huet and J.-M. Hullot. Proofs by induction in equational theories with constructors. Journal of Computer and System Sciences, 25(2) :239-266, October 1982.
- [Huet, 1991] G. Huet. The Gilbreath trick: a case study in axiomatisation and proof development in the coq proof assistant. Technical Report 1511, INRIA, 1991.
- [Jouannaud and Kounalis, 1986] J.-P. Jouannaud and E. Kounalis. Proof by induction in equational theories with- out constructors. In Proceedings 1st IEEE Symposium on Logic in Computer Science, Cambridge (Mass., USA), pages 358-366, 1986.
- [Kounalis and Rusinowitch, 1990a] E. Kounalis and M. Ru- sinowitch. A mechanization of conditional reasoning. In First International Symposium on Artificial Intelligen ce and Mathematics, Fort Lauderdale, Florida, January 1990.
- [Kounalis and Rusinowitch, 1990b] E. Kounalis and M. Ru- sinowitch. Mechanizing inductive reasoning. In Proceed- ings of the American Association for Artificial Intelligen ce Conference, Boston, pages 240-245. AAAI Press and MIT Press, July 1990.
- [Kounalis, 1990] E. Kounalis. Testing for inductive (co)- reducibility. In A. Arnold, editor, Proceedings 15th CAAP, Copenhagen (Denmark}, volume 431 of LNCS, pages 221- 238. Springer-Verlag, May 1990.
- [Musser, 1980] D. R. Musser. On proving inductive proper- ties of abstract data types. In Proceedings 7th ACM Symp . on Principles of Programming Languages, pages 154-162. Association for Computing Machinery, 1980.
- [Reddy, 1990] U. S. Reddy. Term rewriting induction. In M. E. Stickel, editor, Proceedings 10th International Con- ference on Automated Deduction, Kaiserslautern {Ger- many), volume 449 of LNCS, pages 162-177. Springer- Verlag, 1990.
- [Zhang et al., 1988] H. Zhang, D. Kapur, and M. S. Krish- namoorthy. A mechanizable induction principle for equa- tional specifications. In E. Lusk and R. Overbeek, editors, Proceedings 9th International Conference on Automated Deduction, Argonne {fll., USA}, volume 310 of LNCS, pages 162-181. Springer-Verlag, 1988.
- [Zhang, 1993] H. Zhang Implementing Contextual Rewriting Proceedings of the 9rd CTRS Workshop, volume 656 of LNCS. Springer-Verlag, 1993.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1 Introduction
Formal methods are more and more frequently adopted by industry for hardware and software verification. They require efficient automatic tools to relieve designers and programmers of the related proof obligations. Mathe matical induction is essential as a technique for building formal proofs in this context. Its power is expressed by the successes of Nqthm [Boyer and Moore, 1979] that has been for many years the only significant automated theorem proving system for induction. However Nqthm requires a lot of interaction with the user. For instance many lemmas need to be given to N qthm as milestones even for simple proof tasks.
Another direction for automating induction was pro posed in the early eighties, the inductionless induc tion technique [Musser, 1980; Huet and Hullot, 1982] whose principle is to simulate induction by term rewrit ing. This method is refutational and does not require human interaction. While very limited at the begin ning, its domain of application has widened considerably, thanks to the contributions of [Jouannaud. and Kounalis, 1986] who relaxed the conditions on constructor sym bols and of [Fribourg, 1986] who showed that only lin ear derivations were needed. More recently the method has been completely freed from the completion frame work [Kounalis an.d Rusinowitch, 1990a; Reddy, 1990]. It has now become possible to apply it to conditional equational theories [Koun.alis and Rusinowitch, 1990b; Bouhoula et al., 1992:a]. Inductionless induction in our new setting reduces to firstly instanciatin.g conjectures by induction schemes called test sets and secondly sim plifying them by axioms, other conjectures or induc tion hypotheses. Every iteration generates new lemmas that are processed in the same way as the initial con jectures. The method does not require any hierarchy between the lemmas. They are all stored in a list and using conjectures for mutual simplification simulates si multaneous induction. The system SPlKE has been de veloped [Bouhoula et a/., 1992b] on this principle and incorporates many optimizations such as powerful sim plification techniques. To our knowledge, this system is the only one that can prove and disprove inductive the orems in conditional theories without any interaction.
However computer experiments have convinced us of the .necessity of introducing a proper rule to perform case reasoning. Case analysis is a fundamental reason ing technique. A typical instance of it is the cut rule that consists in splitting a goal formula A along an other formula C for generating two subgoals C => A and ·C => A. The main difficulty, already recognized by lo gicians a long time ago, relies in the choice of the cut for mula C. A natural solution when dealing with theories axiomatized by Horn clauses (or conditional equations) is to use the negative literals of the axioms as cut for mulas. This approach is frequently used in the context of conditional rewrite system when a conditional rule C => I - r may reduce a goal A to sub goals C => A[r / /] (i.e. term I is replaced by r in A) and ·C => A.
The problem is now that one of the subgoals is not smaller than the initial goal and a lot of control is needed to avoid divergence of the process since a similar case analysis can be applied again to ·C => A. This has motivated us to introduce a new case analysis rule that allows one to split a goal A into subgoals Ct => A[ltfrt] and VtCi . Since in the context of conditional rewrite system all subgoals are strictly smaller than the initial goal the search space is much more controlled. Related approaches were rroposed independently by [Bronsard and Reddy, 1990 and [Bevers, 1993]. However, since their inference systems are unable to handle non Horn clauses, they cannot prove the ViCi formulas otherwise than by external means. On the contrary, our proof technique applies to non Horn clauses as well. The dis junction ViCi is added to the other conjectures and does not require particular treatment. Therefore our setting is very homogeneous and permits one to extend our basic inference rules by various optimizations without loosing correctness and completeness. In particular we have a notion of inductive positions defining the subset of vari ables of a conjecture that can be instanciated by induc tion schemes and we have proved that these positions are the only ones needed for completeness. The restric tion of induction to these positions reduces drastically the search space. The importance of such restrictions was recognized a long time ago by [Boyer and Moore, 1979].
The paper is organized as follows . In Section 2 we introduce the basic definitions about term rewriting. In Section 3 we define the notions of inductive theory and inductive rewriting, which is a fundamental tool for prov ing inductive theorems. We define in section 4 inductive positions and test sets. Section 5 presents our technique of simulating case reasoning by rewriting. This tech nique reduces considerably the number of inductive po sitions to be considered. The strategy can be embedded in a correct set of inference rules described in Section 6. When the axioms are ground convergent and the de fined functions are completely defined then it is possible to apply the system for refuting conjectures (subsection 6.3). In Section 7, the strategy is even proved refuta tionally complete for conditional equations with boolean preconditions (under previous hypotheses). Computer experiments with SPIKE are discussed in Section 8.
2 Basic concepts
We assume that the reader is familiar with the basic notions of rewrite systems. We introduce the essential terminology below and refer to [Dershowitz and Jouan naud, 1990] for more detailed presentations.
2.1 Terms and substitutions
A many sorted signature E is a pair (S, F) where Sis a set of sorts and F is a finite set of function symbols. We assume that we have a partition ofF in two subsets, the first one, C, contains the constructor symbols and the second, D, is the set of defined symbols.
Let X be a family of free sorted variables and let T(F, X) be the set of well-sorted F-terms. Var(t) stands for the set of all variables appearing in t and U(x, t) de notes the number of occurrences of the variable x in t . A variable x intis lineariffU(x,t) = 1. IfVar(t) is empty then t is a ground term. By T(F) we denote the set of all ground terms. From now on, we assume that there exists at least one ground term of each sort .
For any term t, occ(t) ~ N* denotes its set of positions and the expression tfu denotes the subterm of t at a position u. We write t[s)u (resp. t[s] ) to indicate that s is a subterm oft at position u (resp. at some position) . The root position is written c A E - substitution assigns E - terms of appropriate sorts to variables. Composition of substitution u and 17 is written by u17. The E- term t17 obtained by applying a substitution 17 to t is called an instance oft. If 17 is a ground substitution (i.e. 17( x) is ground for every x), we say that t17 is a ground instance oft.
2.2 Conditional Equations and Clauses
Let E = (S, F) be a signature. A E-equation is a pair e = e' where e, e' E T(F, X) are terms of the same sort. A conditional E-equation is either a E-equation or an ex pression of one of the following forms: elf\ ... /\en ::} e, or e11\ .. . I\ en ::}, or ::} where e, e1, ... en are E-equations. Given a conditional E-equation , e1, . .. en are the condi tions and e is the conclusion. A E-clause is an expression of the form ...,e1 V ...,e2 V ... V -,en V e~ V . .. V e~. When E is clear from the context we omit the prefix E. A clause is positive if ..., does not occur in it.
In this paper axioms are built from conditional equa tions and goals to be proved are clauses, i.e. disjunction of equational literals, since = is the only predicate 1 . The symbol = is used for syntactic equality between two objects.
2.3 Rewrite Relations
2.3.1 Preliminaries
Given a binary relation -+, -+* denotes its reflexive and transitive closure. Let a and b be two terms, we say that a ! b, if there exists c such that a -+* c and b -+* c. A relation -+ is noetherian if there is no infinite sequence t 1 -+ t2 -+ .... In the following we suppose given a reduction ordering >- on the set of terms, that is, a tran sitive irreflexive relation that is noetherian, monotonic (s >- t implies w[s] >- w[t]) and stable (s >- t implies su >- tu). We also assume that the ordering >- can be extended when adding new constants to the signature. The multiset extension of an ordering >- will be denoted by~.
A conditional equation a1 = b1 1\ . . . an = bn ::} s = t will be written as a1 = b1 1\ ... an = bn ::} s -+ t if { su} ~ { tu, a1 u, b1 u, . .. , anu, bnu} for all ground sub stitutions u; in that case we say that a1 = b1 1\ ... an = bn ::} s -+ t is a conditional rule. The term s is the left-hand side of the rule. A set of conditional rules is a rewrite system.
2.3.2 Conditional Rewriting
The idea of rewriting is to impose a direction when using equations in proofs. This direction is indicated by an arrow when it is independent from the instantiation: I-+ r means that we can replace I by r in any context . When an instance of a conditional equation is orientable and has a valid conditional part it can be applied as a rule. The conditions are checked recursively. Termina tion is ensured by requiring the conditions to be smaller (w.r.t. the reduction ordering>-) than the conclusion.
1 we identify a conditional equation and its corresponding representation as a Horn clause
Definition 2.1 (Conditional Rewriting) Let R be a set of conditional equations. Let a be a term and u a position in a. We write: a[so-]u -+R a[to-]u if there is a substitution o- and a conditional equation /\?=1 a; = b; => s = t in R such that:
A term t is reducible w.r.t . to -+R ifthere is a term t' such that t -+ R t'. Otherwise we say t is R-irreducible. The system R will be qualified as ground convergent if Va, bE T(F) (R f= a= b implies a !R b) .
Note that when R is a rewrite system the relation -+ R is similar to the notion of decreasing rewriting of Dershowitz, Okada and Sivakumar [Dershowitz et a/., 1988).
2.3.3 Sufficient completeness
When for all possible arguments the result of a de fined operator can be expressed with constructors only we say that this operator is completely defined w.r .t. the constructors. This requirement is very natural when building specifications in a structured way. Here is a more formal definition:
Definition 2.2 Let C be a set of constructors, let R be a rewrite system and D be a set of defined operator. The operator f E D is completely defined w. r. t. C iff for all t 1 , .. . , tn in T( C), there exists t in T( C) such that f(tl , ... , tn) -+R t .
Although this property is in general undecidable, SPIKE offers facilities to check and complete definitions.
3 Induction
3.1 Inductive theory
Given a set of conditional equations Ax, the theory of Ax, which is the one we are interested in, is the class of sentences that are true in the minimal Herbrand model of Ax. Every element in the domain of a Her brand model is denoted by a ground term built on the signature of Ax. But since ground terms can be well-ordered, induction is available as a natural technique to prove sentences in this model. We call inductive consequence of Ax any sentence C that is valid in the minimal Herbrand model of Ax and we denote this by Ax Find C . In the following we assume that Ax can be oriented as a rewrite system R (w.r.t . ~ ).
3.2 Inductive rewriting
To simplify goals we extend the conditional rewriting relation 2.1, so that we can check the conditions of a rule to be applied to a clause C with inductive hypothesis, other conjectures and the premisses of C, considered as an implication formula.
Let us first introduce a few notations. Let C = ...,( a1 = bl) V ... V ...,(an = bn) V (c1 = dl) V ... V (em = dm)· Then we denote by prem(C) the set {a;= b;};=l,n· The expression (a = b )e denotes the literal a = b if£ = + and the literal ...,(a = b) if£ = - . The skolemized clause C of C is the clause obtained by substituting every variable of C by a new constant.
Definition 3.1 (Inductive rewriting) Let R and W be two sets of conditional equations. Consider a clause C = (a = bY V r and its skolemized version C :: (a = 'by V r . We write: a -+R[W];r a' if a~ a; and:
either a -+prem(F) a''
or there exists a position u in a, a substitution o- and a conditional equation /\?= 1 a; = b; => s = t in R such that:
where =prem(r) is the congruence generated by prem(r) .
The set Win the definition is intended to contain induc tion hypotheses in the proof system described below.
Inductive rewriting can be viewed as a powerful generalization of both the rewriting relation defined in [Kounalis and Rusinowitch, 1990b] and contextual rewriting [Zhang, 1993] .
4 Selection of Induction Schemes
To perform a proof by induction, it is necessary to pro vide some induction schemes. In our framework these schemes are defined first by a function which, given a conjecture, selects the positions of variables where in duction will be applied and second by a special set of terms called a test set. In general the selection of good inductive positions leads to drastic improvements. We shall not discuss test sets here but just recall their main properties.
Let us consider first the problem of choosing the posi tions where variables need to be instanciated by induc tion schemes. In order to define the set of these variables, we introduce V L( s), the set of linear variables of a term s and Def(f), the set of terms with root symbol f.
Definition 4.1 Given a rewrite system R on T(F, X) the set of inductive positions for a function symbol f is: Occ..i.nd(R, f) = { uj there exists p => g -+ d E R such that g E Def(f), u E Occ(g) \ {c} and gfu fl. V L(g)}.
Given a term s, an induction variable of s is a vari able that occurs at a position u .v of s such that v is an inductive position of the root of tju (if s is a variable then it is considered as an induction variable). Given a term s and a set of terms TS, o- is a TS-substitution for s, if it maps any induction variable of s to an element of TS of the same sort. When no subterm oft matches a left-hand side of the rewrite system R we say that t is strongly R-irreducible.
Proposition 4.1 If R is a rewrite system, then a test set S(R) for R is a finite set of R-irreducible terms that has the following properties:
- for any R-irreducible ground term s there exists a term t in S( R) and a ground substitution rr such that trr = s;
b. lets be a term and let rr be a S(R)-substitution for s; if srr is strongly R-irreducible then there is a ground instance srrp such that srrp is strongly R-irreducible.
The first property allows us to prove theorems by in duction on the domain of irreducible terms rather than on the whole set of terms. Sets of terms with the property a. are usually called cover sets in the litera ture [Reddy, 1990; Zhang et al., 1988]. However they cannot be used to refute theorems. The second property b. of test sets is fundamental for this purpose.
It is possible to compute test sets for equational theo ries (see [Kounalis, 1990; Huber, 1991]). Unfortunately no algorithm exists for the general case of conditional theories. However, in [Kounalis and Rusinowitch, 1990b] a method is described for computing test sets in condi tional theories defined over a free set of constructors.
The role of test sets for refutation is shown by the fol lowing definition that gives a falsity criteria for positive clauses:
Definition 4.2 Suppose that we are given a rewrite sys tem R and a test set S(R). Then a clause C :: g1 = d1 V . . . V Yn = dn is quasi-inconsistent with respect to R if there is a S(R)-substitution rr of C such that for al/1 :::; j :::; n , girr "¥= dirr and the maximal elements of {gjrr, djrr} w. r. t. >- are strongly R-irreducible.
We recall the next theorem from [Kounalis and Rusi nowitch, 1990a]. In its proof, the condition b of propo sition 4.1 plays a crucial role.
Theorem 4.1 Let R be a ground convergent rewrite sys tem. If a positive clause C is quasi-inconsistent then C is not an inductive consequence of R.
5 Automatic Case Analysis
We shall introduce now the Case rewriting relation that allows one to reduce goals with conditional rules with out attempting to check their· preconditions. The pre conditions are appended to the goal as a context . Case rewriting can be viewed as an implementation of case analysis that is well adapted to the given conditional axioms. We have found this rule absolutely necessary for proving non trivial conjectures with our automatic system. Moreover it is the basis of a refutationally com plete system for boolean systems. In this section we first discuss the problems with former case rewriting rules. Then we propose a new rule that is easier to automate and has given much better results on experiments. A first version of case rewriting was proposed in [Kounalis and Rusinowitch, 1990b]. Given a term t and a rule p => g - d such that g matches a sub term oft with sub stitution rr, this rewriting is expressed by the following inference rule :
However an important control problem with this tech nique lies in the choice of the rule to apply during the proof by induction. This can be illustrated by the next example.
Example 5.1 The following rules define odd and even for nonnegative integers. A test set here is {0, s(O), s(s(x)), T, F} .
Let us prove:
by the case rewriting rule above. Clause 7 can be split according to axiom 4 in the two following clauses:
8 is a tautology and 9 is equivalent to:
Now splitting clause 10 with axiom 5 yields:
11 simplifies to:
' that can be proved an inductive consequence of R. 12 is equivalent to:
Note that the same case analysis can be applied infinitely often to 14. A possible way to avoid divergence is to limit application of the case analysis rule. Case rewriting in [Kounalis and Rusinowitch, 1990b] is controlled by conditions for avoiding infinite applications of the same rule. However, when adding these technical conditions the proof of 14 diverges.
These problems have motivated us to introduce a new case rewriting technique that rewrites a term t simul taneously to several terms t 1 , ... , tn each reduction be ing respectively valid in different contexts c1 , .. . , Cn . In other words, given a term t, we consider all the way to rewrite it w.r.t. to axioms and positions. We must then prove that the disjunction DP of the conditions of the applied rules is inductively valid. Note that DP is usu ally a non Horn clause. Our approach to inductive proofs is non hierarchical: we can prove DP by simply adding it to the set of conjectures to be further processed.
Definition 5.1 (Case rewriting) Let R be a rewrite system and C = (a = bY V r be a clause. We define G as the set { < a[drr]u, Prr >; there exists P => g - d in R, a position u in a such that aju = grr, grr is R irreducible and does not contain an inductive variable}. Then Case_rewriting ((a= bY, r) is the following set of clauses:
Example 5.2 (example 5.1 continued)
With our method, the proof of 7 is as follows: we ap ply case rewriting to get :
We must prove:
15 is a tautology, 16 is simplified by R into:
The instances of 18 by elements 0 and s(O) from the test set yield clauses that are simplified by R and subsumed by an axiom. The instance of 18 by s(s(y)) gives a clause that is simplified by R and subsumed by 18 which has become an induction hypothesis. In the same way 17 can easily be proved.
Example 5.3 Consider the system R = {p( x, 0, z) = T, p(x , s(y), z) = p(x, y, z) , p(y, x, z) = T => f(x, y, z) = 0}. To prove f(x, y, z) = 0 with the method of [Kounalis and Rusinowitch, 1990a], we instanciate x,y and z by 0 and s(x) (from S(R)) in all possible ways. We obtain 8 equations and the proof of some of them diverges. With the method we present here, thanks to case rewriting, we do not need to consider all these inductive positions. We have: Ocdnd(p) = {2} and Ocdnd(f) = 0. To prove f(x, y, z) = 0, we apply case rewriting to get p(y, x, z) = T => 0 = 0 and p(y, x, z) = T. The first clause is a tautology and the second one is proved by instanciating x by 0 and s(x).
Other authors have applied case rewriting techniques for inductive theorem proving. Among them [Bronsard and Reddy, 1990] and [Bevers, 1993] propose an approach related to ours but their methods cannot be considered as automatic since they cannot check the applicability of case rewriting rules due to the fact that 'their provers are restricted to Horn clauses.
To conclude, we think that our new case rewriting rule avoids many drawbacks of the previously defined ones. It allows to prove a larger class of theorems. Last but not least it does not require human interaction or call to an external theorem prover.
6 A Proof Procedure for Conditional Theories
6.1 Inferences rules
We present the procedure for proof by induction as a set of inference rules to be applied fairly to the goals. Let R be a rewrite system. The procedure modifies incremen tally two sets of clauses E and H, where E contains the conjectures to be checked and H contains clauses, previ ously in E, that have been reduced and can therefore be used as inductive hypotheses. This procedure is refuta tional in essence, and performs implicit induction w.r.t. to >- . Its correctness is obtained by very simple argu ments about the existence of a minimal counterexample. We think that our correctness rroof is much simpler than the related ones [Reddy, 1990 . As a consequence it was easy for us to add many optimizations to the procedure
generate: (Eu{CE} ,H) 1-r (Eu(u .. E .. ),Hu{CE}) if CE =(a= b)· V rand for every S(R)-substitution u of CE : either CEu is a tautology and E .. = 0 or au --+R(HuE);rv a' and E .. = {(a'= bu)· V ru} otherwise E .. = ca·e-rewriting((a = b)·u, ru) case simplify: (Eu{(a=b)· v r},H) 1- 1 (EuE',H) if E' = ca·e..rewriting((a =b)", r) simplify: (EU{(a=b)·vr} ,H) 1-r (EU{(a'=b)"vr},H) if a--+ R(HuE);r a' or a[·],. --+ HuE[R);r a': a[t],. and u "t f complement : (Eu{-,(au=bu)vr},H) 1- 1 (Eu{(au=b'u)vr},H) if -,(b = b') E R, a= b V a= b' E E u Hand bu!:: b 1 u . delete: (Eu{cE},H) 1-r (E,H) if CE is a tautology. fail: (E,H) 1-r o if no other rule applies to (E, H)
and show that they do not affect correctness. The infer ence system for induction I contains the rules given in figure l.The generate rule allows to derive lemmas and initiates induction steps. The case simplify rule simpli fies a conjecture with conditional rules and adds to the result the contexts where the respective reductions are valid. The simplify rule reduces a clause C with ax ioms from R, induction hypotheses from H and other conjectures (therefore we can simulate simultaneous in duction). The premisses of C considered as a conditional axiom can also help to check that the preconditions of a rule being applied to C are valid. The complement rule transforms negative clauses to positive clauses that are easier to refute. The role of deletion is obvious. The fail rule is applied to ( E, H) if no other rule can be applied to (E, H).
An !-derivation is a sequence of states:
An !-derivation fails if it terminates with the rule fail.
6.2 Correctness of the procedure
The correctness of I is obtained by defining a well founded ordering on clauses and a notion of fair deriva tion. Fairness roughly means that every clause in the set of conjectures will be eventually modified by some inference. More formally, a derivation (Eo, H0) l-1 (E1 , H1) h ... is fair if either it fails or the set of per sisting clauses (Ui ni >i Ej) is empty. Then we reason by contradiction: if a non valid clause is generated in a non failed derivation then a minimal one is generated too. We show that no inference step can apply to this clause. In other words, this clause persists in the deriva tion. This is a contradiction with the fairness hypothesis. Hence we have:
Theorem 6.1 (correctness) Let R be a rewrite sys tem and let (E0 ,0) l-1 (E1 ,H1) l-1 ... be a fair! derivation. If it does not fail then R Find Ea.
Since every !-derivation from (E, 0) to (0, H), where H is some set of clauses, is fair then the conjectures of E are inductive consequences of R. This remark is important from a practical point of view.
6.3 Refutation of conjectures
In this subsection R is a ground convergent rewrite sys tem such that all its defined symbols are completely de fined. From now on, we assume that every left-hand side of a conditional rule has a defined symbol. Let us call J the set of inference rules obtained by adding to I the rule:
disproof: (Eu{cE},H) 1- 1 Disproof
if CE is positive and generate cannot be applied to ( { CE}, H).
The inference system J allows to refute conjectures: If disproof is applied at some step k then a quasi inconsistent clause is detected and therefore, from the orem 4.1, we can conclude that some conjecture in Ek is false. Then by induction on the number of steps (k) , this implies that some conjecture from Eo is false too. Hence we have:
Theorem 6.2 Let R be a ground convergent rewrite sys tem such that every defined symbol is completely defined and let (E0 , 0) 1-J (E1 ,H1) 1-J ... be a ]-derivation. If there exists j such that disproof applies to ( Ej, Hi) then R~ Ea.
7 A refutationally complete procedure for theories with boolean preconditions
In this section we shall consider axioms that are con ditional rules with boolean preconditions. More pre cisely we assume there exists a sort boo/ with two nullary free constructors {T, F} . Every rule in R is of type: /\;'= 1 Pi = p: => s --+ t where for all i in [1 ... n], p: E {T, F}. Such a system R is called a boolean rewrite system. For a E {T, F} we denote by a- the comple mentary boo/ symbol of a. Conjectures will be boolean clauses, that is clauses whose negative literals are of type ·(p = p') where p' E {T, F} .
We also assume that any function symbol p with boolean values is completely defined. In other words, the following is inductively valid:
We can then define a new inference system K from I by reformulating the complement as follows:
complement: (Eu{~(a=a)vr},H) 1-K (Eu{(a=a-)vr} ,H)
and replacing the fail rule by:
disproof: (E,H) 1-K Disproof
if no other rule applies to (E, H)
A K-derivation fails if it ends with disproof Note first that the only rule that permits to introduce negative clauses is case_rewriting. Since the axioms have boolean preconditions, all the clauses generated in a K deriva tion (such that Eo only contains boolean clauses) are boolean. So the new inference system K can be proved refutationally complete for boolean clauses too.
Theorem 7.1 Let R be a ground convergent boolean rewrite system such that every defined symbol is com pletely defined and let (Eo, 0) 1-K (E1 , Hi) 1-K . . . be a fair K-derivation such that Eo only contains boolean clauses. Then R ~ind Eo iff the derivation fails .
8 Computer Experiments
Our prototype SPIKE (written in Cam! Light) is de signed to prove the validity of a set of clauses in a con ditional theory. The first step in a proof session is to check if all defined functions are completely defined. If this step is successful then we can use a more efficient version of the case rewriting rule. The second step is to check the ground convergence of the set of axioms. If the first two steps are successful then we can refute false conjectures. The third step is to compute test sets and inductive positions. After these preliminary tasks (detailed in [Bouhoula et a/., 1992a]), the proof starts.
Example 8.1 Consider the specification of lists of nat ural numbers with an "insert" operation and a "sorted" predicate on l~sts that is true iff a list is ordered. SPIKE can prove the conjecture sorted( insert( x , /)) = sorted(/) in a completely automatic way. Note that RRL [Zhang et al., 1 988} is unable to succeed with this example unless the user suggests some well-chosen lemmas.
Example 8.2 An interactive proof of Gilbreath Cards Trick was first given by G. Huet [Huet, 1 991} using the COQ proof assistant. B. Boyer has used NQTHM to de rive another proof A similar but much faster proof was obtained by H. Zhang with RRL. These two "automatic" proofs require many lemmas, some of them being non obvious. For instance, B. Boyer introduces a predicate "silly" that is "only defined to force a certain weird in duction" {here we quote B. Boyer). The same predicate appears in Zhang's experiment. On the other hand, our proof is based on 5 lemmas easy to understand. These lemmas have been suggested by a first unsuccessful proof attempt with SPIKE. The source of failure was identi fied by the impossibility of reducing a family of patterns. Hence we have introduced the adequate lemmas for sim plifying them. This was enough to derive a proof
The proof has taken more real time than Boyer's (and Zhang's). However, it is difficult to compare these ap proaches from the efficiency point of view, since we have spent much less time to get the right lemmas. On the other hand, the differences between programming lan guages lead also to some discrepancy in the performance.
The following array compare users inputs in the proof of Gilbreath Card Trick for NQTHM, RRL and SPIKE:
| NQTHM | RRL | SPIKE | |
|---|---|---|---|
| Exphcit definitions | 6 | 8 | 9 |
| Implicit definitions | 2 | 1 | 0 |
| Induction scheme definition | 1 | 1 | 0 |
| Lemmas | 17 | 23 | 5 |
9 Conclusion
We have proposed a new procedure for proof by induc tion in conditional theories. Our procedure relies on the implicit induction paradigm and puts the stress on simplification and case analysis. As our previous pro cedure [Bouhoula et al. , 1992a], it allows simplification of conjectures by conjectures and has been extended to handle non-orientable equations. It can also refute non valid conjectures. A meaningful contribution of this pa per is that our strategy is refutationally complete for a class of rewrite systems that can specify numerous inter esting examples. This class contains the boolean ground convergent rewrite systems with completely defined func tions over free constructors. In other words with our pro cedure every false conjecture will be disproved in finite time. However, our method remains valid even when the functions are not completely defined. Note that our correctness and completeness proofs do not require an elaborated notion of fairness. It is compatible too with many simplification rules that were not discussed here for lack of space. An extension to theories that are pre sented by non Horn clauses is also easy.
The method is entirely implemented in the prover SPIKE. This system has proved non trivial examples in a completely automatic way, that is, without interac tion with the user and without ad-hoc heuristics. It has also proved the challenging Gilbreath card trick, with only 5 lemmas.
We plan to enhance the system with recent tech niques developed for interactive provers such as the ones in [Bundy et al., 1989; Chadha and Plaisted, 1992].
Acknowledgement: We thank Helene Kirchner for her comments.
@inproceedings{ijcai1993p13,
title = {Automatic Case Analysis in Proof by Induction},
author = {Bouhoula, Adel and Rusinowitch, Michaël},
booktitle = {Proceedings of the Thirteenth International Joint Conference on
Artificial Intelligence, {IJCAI-93}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Ruzena Bajcsy},
pages = {88--93},
year = {1993},
note = {Automated Reasoning},
url = {https://ijcai.org/proceedings/1993/13},
}
TY - CPAPER TI - Automatic Case Analysis in Proof by Induction AU - Bouhoula, Adel AU - Rusinowitch, Michaël T2 - Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence, IJCAI-93 PB - International Joint Conferences on Artificial Intelligence PY - 1993 SP - 88 EP - 93 UR - https://ijcai.org/proceedings/1993/13 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: