How to Facilitate the Proof of Theorems by Using the Induction-matching, and by Generalization
Proceedings of the Ninth International Joint Conference on Artificial Intelligence. Theorem Proving. Pages 1208-1212.
© 1985 International Joint Conferences on Artificial Intelligence
Abstract
In this paper, we show how we conceive the proof of theorems by sructural induction. Our aim is to facilitate the proof of the theorems which can Iead, in a context of automatic theorem proving, to very lengthy ( or even impossible) proofs. We use a very simple tool, the i-matching or inductionmatching, which allows us, on the one hand to deftne an original procedure of generalization, and on the other hand tu deftne an original way of generating Iemmas .
- Aubln R. : "Mechanlzlng structurallnduction ". Ph.D ; thesls. Univ. Edlnburgh (1976) .
- Boyer R.S and Moore J S. : "A computatlonal loglc ". Academlc Press (1980) .
- Burstall R. : "Proving propretles of program by struc- turallnductlon" . Computer J. 12 ( 1) ( 1969) p 41 -48.
- Kodratoti Y. and Castaing J. : "Trivializlng the proof of trivial theorems ". IJCAI (1983) . Kaisruhe West Germany . Proceedings of the eight international joint conference on Artlficial lntelllgence p 930.
- Huet G. and Hutlot J-M. : "Proofs by induction in Equa- tlonal theorles wlth constructors" . 21th IEEE Symposium on Foundatlons of computer Science (1980) .
- Wegbreit B. : "Goal directed program transformation ".IEEE Trans . Softw. Eng. SE -2,2 (j 71) p 69-80 .
- Manna, et al. : "lnductive methods for proving proper- tles of programs ". CACM, vol16, no 8, (1973).
- Abdali, et al. : "Generallzatlon heurlstics for theorems Related to recurslvely Defined Functions ". Proc . 4th Na- tional Conf. on Artlficial lntelligence, Austin, ( 1984) .
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
In Kodratoff-Castaing [ 4] , we presented an automatic theon:m proving based on the principle of structural in duction (3]. We followed on from the works clone by Boyer and Moore [2], Aubin (1] and Huet and Hullot [5J . Our method is now implemented in Lisp (Vax) .
Generally, when we want to prove a theorem using struc tural induction, we ftrst have to prove one or more basic cases and then, one or more induction steps. In our mt!thod we try a new and we hope an original approach, to prove the induction steps. We use a very simple tool which we call hnatchirng (induction -matching) . Brietly, it is u.sed as follows (for a more detailed explanation see our previous article [4]): Iet M => N be any induction steps to be proven, M be any hypothesis and N the associated con clusion. If there is any substitution a suchthat : a(M) = N, and the induction variables chosen do not belong to the domain of substi tution, then the induction step M => N is proved. Such a substitution a characterizes the induction -matching. It also shows that the hypothesis M is general enough to consider the conclusion N as an lnstance of M, and to put N an1ong all the accepted hypotheses .
lt is obviou.s that only easy theorems can be proved by in duction- matching. If the matehing of M toward N fails , we try to remove the causes of the matehing failures ei ther by generalizing the theorem, or by generating inter mediate Iemmas. So, provlng theorems in our method is in fact solving the problems of matching.
In this article we intend to show how we understand the problern of the generalization of the theorems. We shall propose two examples . With this help, we shall demoostrate that the solution we propose is :
- 1 clearly justified by our aim of facilitating the proof of theorems
- 2 clearer than the solutions proposed by Boyer and Moore, Aubin, and also includes them.
2 The formal system
We suppose that all the conditions which allow us to manipulate the theorems, and to prove them by using in ductlon in abstract data types are verified . That' s to say:
- 1 the domain (type support) is generated by a family of constructors supposed not tobe related. We can define, on this domain, the following well-founded ordering, denoted by .:: :
- x <: y iff x is a subterm of y.
- 2 the functions are completly defined by a set of ax ioms (5]. From these axioms, one can obtain a canonical rewrlte system named R.
- 3 the particular properties of the functions given by the users are contained in the set of e9uations E.
In this paper, we apply our method to the following two examples :
t 1 : (e9l (app x (app x x)) (app(app x x) x))
t2 : (e9l {rev x) (foo x nil)).
The first theorem shows that the function app ( append in Lisp) is associative. The second shows the e9uivalence between two programs which compute the reverse of a list. The domain is the set of lists of integers , denoted by List. It ls generated by the two constructors (nil , cons), where cons is the binary operator cons : Int x List -> List (Int denotes the set of natural integers, generated by the two constructors zero and succ) . The proof of theorem t 1 (t 2) is carried out, if we prove :
- 1 the basic case t 1 (nll) (t2(nll))
- 2 the induction step t 1 (x) => t 1 (x <- (cons a x)) (t2 (x) => t 2 (x <- (cons a x)) ).
The canonlcal rewrlte system contains the following rules:
- r 1: (eql x x) -> true
- r 2 : (eql nil (cons b y)) -> false
- r 3 : (eql (cons a x) nil)) -> false
- r": (eql (cons a x) (cons b y)) -> (and (eqn ab) (eql x y))
- r 0 : (and true y) -> y
- r 6 : (and false y) -> true
- 1'7 : (eqn x x )-> true
- r 6 : (eqn zero (succ y))-> false
- r 9 : (eqn (succ x) zero)) -> false
- r 10 : ( eqn (succ x) (succ yJ) -> (eqn x y)
- r 11 : (rev nll)-> nil
- r 12 : (rev (cons a x)) -> (app (rev x) (cons a nil))
- r 13 : (app nil y) -> y
- r 14 : (app (cons a x) y) -> (cons a (app x y))
- r 10 : (foo nily) -> y
- r 16 : (foo (cons a x) y) -> (foo x(cons a nll))
The set of equations E only contains the equation ( app X nil) =X.
When we dispese of a canonlcal rewrite system, we can evaluate any term M and tlnd its normal form, denoted by M!, by applying the rules in any order. But, it may happen in some particular case, that we have to detlne a precise order in the application of the rewrite rules . In this arti cle, we use call- by- need evaluation [7]. We show how we can apply it .
We proceed by steps . First, we try to reduce M at the empty sequence of occurrences, Le, we try to apply one of the rewrite rules which gives the definition of the leftmost function symbol in M. If we succeed, we reduce M and ob tain a new term M' to which we apply again the same pro cess of evaluation. lf we fall. we Iet (u1 ..... «p) be the se quence of the occurrences of subterms of M, which must be evaluated in order to apply one of the previous rewrite rules . Then, we reduce M successively at the oc currences u 1, ... t.~p by applying the same process of evaluation .
The call-by-need evaluation stops either in the case where the normal form of M is an element of the domain, or in the case where the subterms of M to the occurrences u 1, ... ,«p ,denoted by M/u1, ... , Ml«p. are variables . In this case , to use Aubin's terminology, we say that these vari ables are recursion variables, or are in the recursion posi tion. Generally, we can also say that the subterms of M which must be evaluated in the call-by-need rule, are in the recursion position.
Example:
We evaluate the term M = (eql (app x (app x x)) (app(app x x) x)).
Step-1 : we try to reduce M at the empty sequence of oc currences. We have to evaluate the subterms of M at the occurrences 1 and 2, in order to apply one of the four rules r 1, ... , r", which give the detlnition of eql.
Step-2 : for evaluating the subterm M/1, we must instanci ate the variable at the occurrence 1.1. For evaluating the subterm M/2, we must evaluate the subterm M/2.1.
Step-3: we have to instanciate the variable at the oc currence 2.1. 1.
The two occurrences of the variable x, 1.1 and 2. 1.1, are in the recursion position.
3 Generalization : existant solutions
The need for an e!Iiclent procedure of generalization has been expressed in [1,2,4,8]. In such a procedure , we have to detlne a criterion of choice of the subterms to be generalized in a theorem, verify the new proposition ob tained, and give a new way of proceeding lf the general ized proposition obtained is a false one. Otherwise, the method proposed faUs .
We now analyse Boyer and Moore 's and Aubin's solu tions .
Boyer and Moore choose the subterms to be general ized ;according to their syntax. They replace, in the theorem to be proved, some syntatically identical sub terms by the same new variables. This simple procedure suits the proving of a !arge dass of theorems, because it is used in a framewerk of the strategy of cross fertllization [2]. This strategy reduces the induction steps P' = Q' => P =h (Q') where P' ,Q' and P are recursive ly deflned functions , to a new Iemma P = h(P') to be proved. If the term P is defined by g(P'), then the new theorem to be proved g(P') = h(P') can be generalized to g(u) = h(u) , where u is a new variable. We must be careful if we want to extend the application of this principle, be cause the new proposition obtained can be a false one. For example, if we generalize the theorem t 1 by this prin ciple, the new theorem obtained by replacing the sub terms (app x x) by a variableu is in fact a false one .
Thus, we can make some remarks about the Boyer and Moore 's solution. Their princ!ple does not indicate how to go on if the proposition obtained is a false one. Their prin ciple cannot be fully justified. One can only establish that very often, the generalized theorem can now be proved.
Aubin proposes two heuristics of generalization in ord er to improve on the Boyer and Moore 's principle. In these two heuristics, he chooses the subterms to be gen eralized according to thelr position in the theorem. He distinguishes a recurslve functlon from a tail-recursive function. In practice, the distinction between these two kinds of functions is the presence in a tail-recursive func tion of accumulators which are variables, whose role is to contain the partial result of the evaluation of the function. For example, the function foo whose definition is given in the paragraph above, ls a tail-recurslve function, because the variable y is an accumulator, while the function app is a recursively defined one.
For recursive functions, he uses the same criterion for selecting induction variables, and for choosing the sub terms to be generalized. He chooses the induction vari ables among the recurslon ones. So, he selects among the set of occurrences of the same subterm in the theorem, those whlch are in position of recurslon, and gives them the same name.
For example, he generalizes the theorem t 1 by replacing the occurrences 1.1 and 2.1.1 of the samevariable x, by a new variable u. He thus obtains the new proposition to be proved, (egl (app u (app x x)) (app (app u x) x)).
Generally, if the new proposition obtained is a false one, he analyses the subterms which are left in the theorem, and tries to generalize those which are syntati cally identical to the recursion subterms.
For tail-recursive functions, Aubin generalizes the con stants which are in the position of accumulators. The prin ciple used is called "indirect generalization", because.the subterms to be generalized are now in the accumulator position, and not in the recursion position.
Aubin justifies his choice by the following remark : if the theorem tobe proved is an eguivalence one, the presence of these constants causes the failure of the proof by cross-fertilization.
Let us verify this remark with the help of theorem t 2 .
Example:
t 2 = (egl (rev x) (foo x nil)) .
Let M = t 2 (x): Let N = t 2 (x <- (cons a x))! = (egl (app (rev x) (cons a nil)) (foo x (cons a nil))) .
The induction step is M => N. To cross-fertilize is to apply the hypothesis as a rewrite rule. We can extract two rewrite rules from M. The first one, (foo x nil) -> (rev x), can not be applied, the presence of the constant nil in the accumulator position of the function foo, Ieads the mateh ing of (foo x nil) with (foo x (cons a nil)) to fail. The second rule, (rev x) -> (foo x nil) reduces the induction step to a new Iemma, t 3 = (egl (app (foo x nil) (cons a nil)) (foo x (cons a nil))) .
In order to prove t 3, we have to prove the induction step t 3 (x) => t 3 (x <- (cons b x)). By applying again the same strategy of cross-fertilization, we can now establish that the presence of the constants nil and (cons a nil) at the occurrences 1.1.2 and 2.2 prevents us from using the hy pothesis as a rewrite rule. So, the proof of t 2 fails accord ing to the argument given by Aubin.
If the new proposltion obtained by replacing the same constants by a new variable is a false one, (and that is the ease in our example, the proposition obtained (egl (rev x) (foo x v)) being a false one), Aubin proposes to make ap-
pear some new eonstants in the theorem, that he also generalizes. We deseribe how he proeeeds.
He matehes M "'ith N and Iooks for the other causes of the failure . Let us suppose that the matehing fails beeause the substitution ls attempted on a funetion symbol. He tries to remove this failure by applying a proeedure ealled a proeedure of expanslon [6]. He introduees in M the func tion symbol which is responsible for the failure, and eom pletes its definition in order to obtain a new hypothesis M' eguivalent to M. This last condition is satisfied if the func tion introduced has a neutral element.
Example:
M = (egl (rev x) (foo x nil)).
N = (egl (app (rev x) (cons a nil)) (foo x (cons a nil))).
The matehing of M with N fails at the oeeurrenee 1, be cause the substltution is attempted on the function sym bols rev and app, and fails at the oeeurrenee 2.2, for the reason glven by Aubin.
Aeeording to the procedure of expansion, Aubin intro duees at the oeeurrenee 1 the symbol app, and eompletes lts definition by adding the term (rev x) followed by the neutral element of app which is nil.
The new hypothesis obtained is M' = (egl (app (rev x) nil) (foo x nil)). Now, the generalized expression of M', ( egl (app (rev x) v) (foo x v)), ls the new theoremtobe proved.
The two solutions glven by Aubin allow us to extend the dass of theorems which ean be proved. But, we ean point out some weaknesses .
The heuristic used for reeursive funetions is not fully justified. Indeed, the new variable introdueed in the theorem is considered as an induetion variable at the next step, when the same method is applied again : we do not know whether the proof of the new theorem obtained ean now be facilitated or even carried out. Moreover, we do not like the eombinatorial aspeet whieh is associated to the ehoice of the subterms to be generalized.
The seeond heuristie proposed is more interesting. It is justified by the intention of its autor to use the hypothesis as a rewrite rule. On the other hand, we think that the Aubin's way of eontinuing, when the generalized proposi tion ls a false one, ean be extended without considering the different kinds of funetions. The real purpose ls to re move the eauses of the failure of the matehing of M with
- We now show, using theorem t 1 as an example, that the subterms choosen by Aubln, at the occurrences 1.1 and 2.1.1, are in fact a part of all the subterms which are responsible for the matehing failure.
Example:
M = t 1 (x) = (eql (app x (app x x)) (app (app x x) x)). N = t1 (x <- (cons a x))! = (eql (app x (cons a (app x (cons a x)))) (app (app x (cons a x)) (cons a x))) by applying the rules r 4 , r 1 , r~. r 14. The matehing of M with N falls for the following reasons :
- 1 we detect a contradictory substitution on the vari able x, x <- x and x <- (cons a x) at the occurrences 1.1, 2.1.1, 2.1.2, 2.2.
- 2 the substitution is attempted on the function sym bols cons and app at the occurrence 1.2. The subterms responsible for the matehing failure are at the occurrences 1.1, 1.2, 2.1.1, 2.1.2, 2.2. Aubin general izes the subterms at the occurrences 1.1, 2.1.1, which are only two causes of the matehing failure .
Our method systematizes this approach.
4 Our solution
lt consists of two steps. the first one will be exemplitied by the proof of theorem t 1, the second one by the proof of theorem t 2 .
We assume that the baslc cases are proved.
Let M => N be any induction step. If M i-matches with N then the induction step M => N is proved. Let us suppose that the l-matching falls. As we have already indlcated in the introduction, the i-matching is a particular matehing such that the induction variables do not belong to the domain of of the substltution. So, we can deduce that ei ther the matehing falls, or one of the induction variable belongs to the domain of the Substitution.
We put in the two lists 1M and LN, all the subterms of M and N which are responsible for this failure, each of them being labelled by its occurrence in M or in N.
Let LM = [(Miu1, u .1), .. . , (Miu 9 , uq)] and LN = [(Niu1, ul), .. . , (Niuq. Uq)] be the.lists of these subterms.
A. First step : generalization
Detinition-1 : We say that we "savagely" generalize the term M at the occurrences u 1, .. . , uq, lf we replace the subterms of M at these o.ccurrences by new distinct vari ables v 1, ... ,vq.
Definition-2 : Let Mlu. be an element of the Iist LM. Let MI Uj~o .. .. MI u.;". be the set of all the subterms of M which are syntatically identical to the subterm MI u. . If we general ize M to the occurrences u. 1, ... , u.;". . we call the new vari ables introduced, v 1, ... , vn, separated variables.
Detinition-3 : We collect a set of separated variables v1, ... ,v~;, if we give them the samevariable name, let be u. The susbtitution T = ( v 1 <- u, .. . , v~; <- u) symbolizes this collection.
Basicidea
Broadly speaking, we .apply a strategy which general izes too much, and then find for particular values of the variables, the conditlons which make the generalization true. So, we savagely generalize M at the occurrences u 1 , ... ,uq, given in the !ist LM. Let MG (X. v 1, ... ,vq) be the generalized expression obtained, where X is the set of all the variables of M different from the v, 's. Generally. this expression is a false proposltion. We Iook for the condi tions on the variables v, · s. so that MG (X,v 1, .. . ,vq) can now be specialized in a new proposition which is true, and upon which we apply our method of proof once again.
In practice, it is very ditl'icult to find the conditions on the v, 's. If M contains a predicate of equality, to special lze MG (X. v 1 ... .. v 9 ) ls in fact to solve some equations of diophantine type. So, we Iimit ourselves to simply tinding the equallty relations between the variables v; 's. We now show how we proceed.
Practical application
We conslder the first cause of failure in LM, m = Ml u 1.
- 1 We savagely generalize M at the occurrences of all the subterms of M which are syntatically identical to m. Let v ,, .. . ,vn be the sequence of separated variables intro duced in M. We successlvely glve the particular values e ,, ... , em to the variables of X, and we compute the normal forms MG-1 =MG (X<- e,, v~o ... . 11n) . ... . MG-rn= MG (X< em, v1, .. . , vn)· These particular expresslons only contain separ ated variables .
- 2 Let l = 1. We apply the call-by-need evaluation to the term MG-!. Let VR, = (v0 , ... ,11il:) be all the recursion variables of MG-!.
- 3 Let VR,' = (v,, ... ,vn)- VR; bethe set of all separated variables whlch are left (if any are left) . We first collect the variables of VR, by giving them the same name u, then we also collect the variables of Wi';' by giving them the same name v. Let T be the Substitution which symbolizes these two collections.
- 4 If Mg = T (MG (X, v 1, ... , vn) is a proposition which is evaluated as true for the particular values of its variables, then Mg is a new theorem to be proved. Otherwise, we go on specializing MG (X, v 1 , ... , vn) further. We proceed as follows :
- Iet j be the particular value given to the variable u which falsifies Mg. We instanciate all the variables of VR, to the value j, and we compute the new normal form : MG i-j =MG (v" <- j, ... , vik <- j)! which only contains separat ed variables of VRj. We apply once more the call-by-need evaluation to MG-i-j. Let VR,i be the set of recursion vari ables in MG-i-j. Let VR, = VR; u VR;i be the union of the two sets VR; and VR,i. We go on to 3.
It is obvious that this procedure of specialization stops either in the case where the new proposition obtained Mg is now verified, or in the case where we have to collect all the separated variables v 1, ... , vn. In this case, we consider the next term MG-i+l upon which we apply the same pro cess again. If all the subterms MG-l, ... ,MG-m have been considered, we consider the second cause of failure which is distinct from m and we go on to 1. lf there is no cause left, the procedure of generalization fails, and we go on to the next step.
Example: M = t 1 (x) = (e9l (app x (.app x x)) (app (app x x) x)). N = t 1 (x <- (cons a x))! = (e9l (app x (cons a (app x (cons a x)))) (app (app x (cons a x)) (cons a x))). LM = [(x, 1.1), (x, 2.11), (x, 2.1.2), (x, 2.2), ((app x x), 1.2)] m=x
- 1 We savagely generalize M at the occurrences of all the subterms which are syntatically identical to x. We ob tain MG (v 1 , ... ,v 6 ) = (e9l (app v 1 (app V2 vs)) (app (app v4 v 5 ) v 6)). This expression only contains separated vari ables.
- 2 We apply the call-by-need evaluation to MG (v 1 , ... ,v 6 ). The set of recursion variables VR, contains the variables v 1 and v4 . So, we collect v 1 and v4 : let u = v 1 = v 4 . We collect all the separated variables which are left : Iet v = v 2 = v 3 = v 5 = v 6. Let T = (v 1 <- u, v4 <- u, v2 <- v, v 3 <- v, v 0 <- v, v 6 <- v) be the substitution which symbol izes these two collections.
- 3 Let Mg = T (MG (v 1, ... ,v 6)) = (e9l (app u (app v v)) (app (app u v) v)) . Mg is a proposition evaluated as true for particular values of its variables, so, Mg is a new theorem to be proved.
Let us show how we can prove Mg by using the i-matching. The basic case Mg (u <- nil)! is reduced to true by our rewrite system. The induction step Mg (u) => Mg (u < (cons a u))' is simplitied, by our rewrite system, to the form : (e9l (app u (app v v)) (app (app u v) v)) => (e9l (app u (app v v)) (app (app u v) v)). The hypothesis i matcbes the conclusion, so, the induction step is proved, and we have facilitated the proof of tbeorem t 1.
B. Second step : generati.ng lem..mas
We only consider the subterms of M and N which are put in lists LM and LN, and which are not variables . The presence of these subterms in lists LM and LN shows that the substitution has been attempted on the function sym bols. We propose to remove them from these lists either by using the Iemmas given in the set of e9uations E or by using the hypothesis.
Using lem..mas given in E
Let M/«.o and Nlu, be two subterms of M and N put in Usts LM and LN suchthat the function symbols /; = M ( u..) and g, = N ( u.) at the occurrences u. of M and N are dis tinct. If we find in E an e9uation of the form x = (g; x e), we reduce M at the occurrence u. using the rule x <- (g, x e). So, we make appear the function symbol g; in M. We proceed in the sarne way as Aubin, when he applies the procedure of expansion. Let M' be the new hypothesis ob tained by reducing M to the different occurrences given in LM and LN. The new induction step is now M' => N. If M' i matches with N, the proof of the induction step is com pleted, and so is the proof of M => N. Otherwise, we put in the two new lists LM' and LN all the causes of this failure, and we come back to the first step, after removing from E all the e9uations of the form x = (g, x e) which have been used.
If the e9uations in E do not allow us to reduce M, we go on now, uslng the induction hypothesis.
Using the induction hypothesis
General case :
Let M = (P m 1, ... ,mp) and N = (P n 1, ... , np), where Pis a predicate to be proved. Let us suppose that one subterm m; I-matches with the subterm n,, with the substitution u. It is obvious that M i-matches with the term N' = (P u (m 1 ) ... u (mp)) . So, if we are able to prove the p-1lemmas u ( mi) = ni, we will have proved the induction step M => N.
Partiewar case :
Let M = (P m 1 mz) and N = P (n 1 n2), where Pisa predi cate of e9uallty. Let us suppose that m 1 and n1 are put in Usts LM and LN, and that m 1 has one occurrence in n 1. We reduce N to a new term N' by applying the rewrite rule m 1 -> m 2 to the occurrence of the subterm m1 in n 1. We are left with a new theorem to be proved upon which we apply the sarne method of proof again. As the reader can remark, we proceed as Boyer and Moore do when they cross-fertilize.
Exarnple:
M = t 2 (x) = (e9l (rev x) (foo x nil)). N = t 2 (x <- (cons a x))! = (e9l (app (rev x) (cons a nil)) (foo x ( cons a nil)))
LM = [((rev x), 1), (nll. 2.2)].
LN= [((app (rev x) (cons a nll)), 1), ((cons a nll), 2.2)].
E = [(app x nll) = x].
As the reader can remark, we fall on generallzlng t 2. So, we reduce M at the occurrence 1 by the rule x -> (app x nll) . We obtaln the new hypothesls M' = (eql (app (rev x) nll) (foo x nll)) . The l-matching of M' with N falls, and LM' ls [(nil. 1.2), (nil. 2.2)]. We come back to the first step after removing the equatlon (app x nll) = x from E. So, E is now an empty set.
We savagely generallze the term M' at the occurrences 1.2 and 2.2. We obtain MG (x, v 1, v2) = (eql (app (rev x) v 1) (foo x v2)) . We give to the variable x the particular value x = nll, and the normal form of MG (x <- nil. v 1, v2) becomes (eql v 1 v2). We collect these two variables which are re curslon variables : v = v 1 = v 2. The new theorem to be proved ls now t 3 = (eql (app (rev x) v) (foo x v)) .
Let us prove theorem t 3. The baslc case t3 (x <- nil) ls re duced to true by our rewrlte system. The lnduction step ls M => N, where
M = t 3 (x) = (eql (app (rev x) v) (foo x v))
N = t 3 (x <- (cons a x))! = (eql (app (app (rev x) (cons a nll)) v) (foo x (cons a v))).
The subterm (foo x v) I-matches with the subterm (foo x (cons a v)) with the substitution a = (v <- (cons a v)) (x does not belong to the domain of a) . So, the new theorem tobe proved ls now t 4 = (eql (app (rev x) (cons a v)) (app (app (rev x) (cons a nll)) v)). Our procedure of generallza tlon proposes as a new theorem t 0 = ( eql ( app u ( cons a v)) (app (app u (cons a nil)) v)), which can now be proved by using the i-matching. We have facilitated the proof of theorem t2.
Conclusion
We can now specify the reasons whkh allow us tothink that our method lncludes those of Boyer and Moore and Aubln.
- 1 Our procedure of generallzation contains the two heuristlcs used by Aubln for the choice of the subterms to be generalized.
- 2 :we use · the same strategy of proof as these autors when we apply the procedure of expansion, or when we cross-fertilize.
6 Heferences
- Aubln R. : "Mechanlzlng structurallnduction ". Ph.D ; thesls. Univ. Edlnburgh (1976) .
- Boyer R.S and Moore J S. : "A computatlonal loglc ". Academlc Press (1980) .
- Burstall R. : "Proving propretles of program by struc turallnductlon" . Computer J. 12 ( 1) ( 1969) p 41 - 48.
- [ 4] Kodratoti Y. and Castaing J. : "Trivializlng the proof of trivial theorems ". IJCAI (1983) . Kaisruhe West Germany. Proceedings of the eight international joint conference on Artlficial lntelllgence p 930.
- (5] Huet G. and Hutlot J-M. : "Proofs by induction in Equa tlonal theorles wlth constructors" . 21th IEEE Symposium on Foundatlons of computer Science (1980) .
- Wegbreit B. : "Goal directed program transformation ".IEEE Trans. Softw. Eng. SE -2,2 (j 71) p 69-80.
- Manna, et al. : "lnductive methods for proving proper tles of programs ". CACM, vol16, no 8, (1973).
- f8] Abdali, et al. : "Generallzatlon heurlstics for theorems Related to recurslvely Defined Functions ". Proc . 4th Na tional Conf. on Artlficial lntelligence, Austin, ( 1984) .
@inproceedings{ijcai1985p244,
title = {How to Facilitate the Proof of Theorems by Using the Induction-matching, and by Generalization},
author = {Castaing, Jacqueline},
booktitle = {Proceedings of the Ninth International Joint Conference on
Artificial Intelligence, {IJCAI-85}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Aravind Joshi},
pages = {1208--1212},
year = {1985},
note = {Theorem Proving},
url = {https://ijcai.org/proceedings/1985/244},
}
TY - CPAPER TI - How to Facilitate the Proof of Theorems by Using the Induction-matching, and by Generalization AU - Castaing, Jacqueline T2 - Proceedings of the Ninth International Joint Conference on Artificial Intelligence, IJCAI-85 PB - International Joint Conferences on Artificial Intelligence PY - 1985 SP - 1208 EP - 1212 UR - https://ijcai.org/proceedings/1985/244 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: