A Definition-Driven Theorem Prover
Proceedings of the Third International Joint Conference on Artificial Intelligence. Theorem Proving and Logic: 1. Pages 51-54.
© 1973 International Joint Conferences on Artificial Intelligence
Abstract
This paper describes a theorem prover, running on a PDP-10-TENEX system, that can prove some theorems whose statements involve a relatively large number of definitions. Such theorems require special methods because (1) their statements contain a large number of clauses and (2) their proofs are quite long although straight-forward. A theorem is proven by first subdividing it into "simple" subgoals and then using a standard resolution theorem prover to prove the subgoals. The first part of this process involves the substitution of definitions for defined quantities and the use of logical simplification. This process which is more similar to a natural deduction system than a resolution system, is shown to be complete when restricted to first-order logic. However, the theorem prover can deal with some interesting higher-order theorems as is shown by an example.
- Bledsoe, W. W., "Splitting and Reduction Heuris- tics in Automatic Theorem Proving," Artificial Intelligence 2, 1971, pp. 55-77.
- Ernst, G. W., "The Utility of Independent Subgoals in Theorem Proving," Information and Control, April, 1971.
- Ernst, G. W., "A Definition-Driven Theorem Prover, " Report No. 1124, Computing and Informa- tion Sciences, Case Western Reserve University, 1973. •
- Huet, G. P., "The Undecidability of the Ext stence of a Unifying Substitution in the Simple Theory of Types," Report 1120, Jennings Computing Center, Case Western Reserve University, 1972.
- Nevins, A. J., "A Human Oriented Logic for Auto- matic Theorem Proving," AI Memo No. 268, Mass. Inst. of Tech., Cambridge, Mass., 1972.
- Norton, L. M., "Adept: A Heuristic Program for Proving Theorems of Group Theory," Report MAC-TR- 33, Mass . Inst. of Tech., Cambridge, Mass., 1966.
- Slagle, J. R., and Koniver, D., "Finding Resolu- tion Graphs and Using Duplicate Goals in AND/OR Trees," Information Sciences, Vol. 3, No. 4, Oct., 197., pp. 315-342.
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
The motivation for this research stems from our view of how theorem provers will be used in solving real-life problems. We believe that the first few ap plications of theorem provers will be man-machine oriented because, at the current state of the art, theorem provers can only solve relatively easy problems and it will probably be quite a while before they can solve truly difficult problems on their own.
It also seems to us that theorem provers will be faced with a large number of problem-oriented predi cates due to diversity of real world data. Some of these predicates will be sufficiently basic that they will of necessity be built into the theorem prover. However, most of them, due to their abundance, will have to be defined in terms of ·the basic predicates and logical connectives.
On the basis of these assumptions, we feel that the role of the machine will be primarily a big data filter, doing the relatively straight-forward part of the theorem proving which might be quite lengthy. For the most part, this amounts to "wading" through defini tions and previously proven theorems (and perhaps meta theorems), many of which are quite long and tedious; proving the easy parts and isolating the non-trivial parts. The man then would select a non-trivial part to work on next and would give the machine "hints" on how to go about proving it. The hints will be of various forms, such as conjecturing induction hypothesis, lemmas, the value of important variables, etc.
This paper describes a theorem prover, TPI, that can prove some lengthy but straightforward theorems whose statement contains defined quantities. Although TPI is a totally mechanical, and not a man-machine theorem prover, the types of problems for which it is designed are similar to what we feel will be the kind of problems that a machine should do in a man-machin~ application of theorem proving. Since the approach of TPI is somewhat different than a standard resolution
*There are 3 differences between (l) and the formula given to TPI: An example of the first is that Gr(G,+,-,0) is given to the machine as (Gr G +- 0). The second is that infix notation is used in (1) and thirdly parentheses are omitted in (l) if their omission causes no ambiguity.
A DEFINITION-DRIVEN THEOREM PROVER
George W. Ernst Department of Computing and Information Sciences Case Western Reserve University Cleveland, Ohio 44106
theorem prover, in the next section we will give an example of how it proved a particular theorem. This will motivate Sec. 3 which describes TPI in fair de tail.
2. An Example of TPI
In this section we give an example of how TPI proved the theorem that the direct product of 2 groups is a group. The statement of this theorem is*
The operator and inverse of the product group are o and J, respectively, and are defined below. In the first line of (1) (G univ) indicates that G is some element of the universe,a1d (+(FN G G G)) indicates that + is a binary operator on G. The remainder of the first line indicates that -:G + G and 0 is some element of G. The second line of (1) states the same things about H,*,I and E. Thus the first two lines univer sally quantify 8 variables subject to the restrictions that they must lie in certain domains. Gr is a de fined predicate having 4 arguments, a group, its oper ·ator, its inverse and its identity, respectively. Thus, the last line of (1) states that, if G and Hare groups then so is GXH (cartesian product of G and H). The operator o of the latter is
In this expression A is the usual operator of abstrac tion. The meaning of (2) is that it is a two-place function. The string (u GXH) indicates that the first argument wh~£h 9ets substituted for u must be in the set GXH. 1 {u) is the first element of the ordered pair u while 2nd(u) is the second element of u. The , in (2) is the operator which takes two terms and makes an ordered pair out of them. An example of the use of (2) is aob. This expression is defined if both a and b are in GXH and the term aob evaluates to the ordered pair (1St(a)+lSt(b),2nd(a)*2nd(b)). Note that G, H, +, * are free variables in (2) which are quantified by the quantifiers in (l) because o occurs in (1).
The inverse J of the product group is defined in a manner similar to (2) as
The identity of the product group is given in (1) as the ordered pair (O,E).
To prove (1), TPI must know the definition of group, 1st, etc. TPI has a repertoire of definitions and previously proven theorems which includes these definitions and other definitions, such as definition of homomorphism, that are not relevant to proving (1). We will not state the definitions because their con tent will become clear by their use.
First of all, TPI simplifies (l) which in this
case involves putting Skolem functions versally quantified variables in (1). purposes we will use the same names as and thus (1) becomes in for the uni For notational the variables
In this formula G, +, etc. are constants and their domains ~re kn~wn because of the first 2 lines of (1), e.g.,+ 1s a b1nary operator on G. Next, TPI sees from the definition of group that it is sufficient to prove ~hat o .is a~soci~tive; J is a right inverse; and (O,E) 1s a r1ght 1dent1ty. The resulting formula is imme diately simplified and stated as the following three subgoals (or lemmas) which TPI will work on separately:
(7)
In these formulae a, b, c, d, e are Skolem functions t~at are elements of GXH. (5), (6), (7) state respec ~lvely that (O:El is a.ri~ht identity, J is a right 1nverse and o 1s assoc1at1ve. The reader will note that (5), (6) and (7) are more complicated than text book formulae because they contain terms that can ob viously be simplified such as lst(o,E) which is just 0. How~v~r: these formulae were produced directly from the def1n1t1on of a group and such simplification will oc cur later in the proof.
. TPI next processes (5) in much the same way that 1 t processed ( 1). It sees from the definition of an o~dered pair that two ordered pairs are equal if their f1rst components are equal and if their second compon ents are equal. Using this definition on (5), the following two new subgoals are produced:
When TPI processes (8) it notes that (8) cannot be further divided into subgoals, and thus calls on a resolution-based theorem prover called the subgoal solver (SGS), to solve it. But first it replaces de fined quantities by their definitions and then reduces the formula to normal form. Fig. 1 gives the result of processing (8) in this way. In Fig.l the variable x is restricted to be in G. This information is checked implicitly in TPI whereas a standard resolution theo ~em prover would append an XfG to each clause contain lng an x, e.g., the first clause in Fig. 1 would be XfG V x+O=x. Similarly y is restricted to be in H while u and v are not restricted.
The definition of a group indicates that + and * are associative. Instead of representing this infor mation as clauses, the operators are "flagged" and the SGS processes them as n-ary operators.
As the reader can easily see, Fig. 1 gives a contradiction in just two steps. From clauses 9 and 12 in Fig. 1 we get lSt(a)+O~lSt(a). From this and clause 1 in Fig. 1 we get lSt(a)~lst(a) which is contradictio~
. T~I processes (9) almost identically to the way in wh1ch 1t processed (8). The normal form of (9) is the fi~st 11 clauses in Fig. 1 and 2nd(a)+2nd(O,E)~2nd(a) wh1ch also has a two-step contradiction ~
TPI then proceeds to (6) and uses the definition of ordered pair to divide (6) and into the following two subgoals:
(10) equates the first components of the left and right sides of the= in (6) while (11) equates their 2nd com ponents.
Since {10) cannot be divided into subgoals, it is reduced to normal form, which is just the first 11 clauses in Fig. 1 and
This is passed to the SGS which easily solves it in 3 steps. From (12) and clause 9 in Fig. 1, lSt(b)+-{lSt (~))~lst{O,E) is de~uced. This and clause 3 in Fig. 1 g1ves O~lst(O,E) wh1ch by clause 9 in Fig. 1 implies 0~0 which is a contradiction .
. TPI . process~s (11) in much the same way as (10) prov1ng 1t also 1n three steps. Proceeding onto {7) TPI breaks it into 2 subgoals by separately equating' the two components of the left and right of the = in {7). Since the generation of these subgoals is so sim ilar to the generation of the above subgoals we will not state the subgoals in this paper. Also their pr~ofs will be omitted because they are just 3 steps ap1ece.
~h~s conclu~es the proof of (1). In summary then, TPI d1v1des (1) 1nto 6 terminal subgoals or lemmas and proves these 6 subgoals independently which constitutes a proof of (1). The purpose (5), (6) and {7), which a~e intermediate s~bgoals, is to facilitate the genera tlon of the 6 term1nal subgoals; i.e., (5), (6) and (7) are not directly proven by the SGS.
3. Description of TPI
The purpose of this section is to describe the in ternal mechanisms of TPI which is a LISP program cur rently running on a PDP-10 under TENEX. Due to space limitations, the description will be very brief. For this reason the interested reader is referred to 3 which is a fairly detailed description of TPI.
TPI operates from a repertoire of definitions not all of which are needed in any particular theorem. Cur· rently, there are over a dozen defined quantities in TPI's repertoire. Incorporated into the definitions are also some previously proven theorems. All of this information is contained on two lists BD (backward de finitions) and FD {forward definitions).
All statements on BD are of the form Q(A~B) while FD statements are of the form Q(B=C). B is the defined quantity and Q is a string of restricted quantifiers. A together with C comprises the definition of B. In ad dition, certain previously proven theorems about B may also be incorporated into these statements as described in Sec. 4. As an example, consider the definition of a group-on BD. In this case B is Gr(G;+,-,0) and A is and Q is V((G univ)(+{FN G G G))(-(FN G G))(O G)). The intent of these formulae should be clear from the dis cussion in the previous section. FN and univ are pri mitives whose semantics are built into TPI. Although the relationship between A and B in this example is 'if and only if', in general, A will only imply B for the statements on BD.

Since the relationship is 'if and only if' we could use the same statement on FD, i.e., we could put Q(B=A) on FD. Note that our use of restricted quanti fication is somewhat non-standard. The restrictions are processed as if they are conjuncts of the second argument of=· For example, V((x a)(y b))E=F is taken to mean Vxy(E = X£a & y£b & F).
TPI attempts to prove theorems by generating an AND/OR tree of subgoals in much the same way as de scribed in 2 · The root of the tree is the theorem to be proven. TPI processes a node in the tree by first applying some logical simplifications such as "\ conversion," transforming a theorem of the form D+(E+F) into D&E+F, and removing quantifiers at the outermost level by putting in Skolem functior;s. (Note that, since the theorem has not been negated, the Skolem functions are put in for universally quantified vari ables instead of existentially quantified variables.) Then, if the simplified theorem is of the form E+(F 1 &F2& ... ), the subgoals E+F 1 , E+F2··· are generated prov1dea that the Fi have no variables in common.
Next for each subgoal of the form G+Fi· TPI gen erates the subgoals G+crijAij where Oij(Aij+Bij) are statements on BD and Oij is the most general unifier of Bij and Fi. These are subnodes of an OR node while the above subgoals come from an AND node. Fig. 2 shows the subgoal tree generated so far. Now the whole process is repeated for the subgoals: logical simplification, generation of AND subnodes, generation of OR subnodes via BD.
Actually this picture is highly simplified. The most notable omission is that TPI checks that the re stricted quantification of Qij is satisfied. Experi ence has shown that most of tne variables are known to be in the right domain (this is always the case in the example in Sec. 2) but for the others separate subgoals must be generated to prove that they are fn the correct domain. Examples of such suqgoals are given in Sec. 5.
TPI attempts to prove the terminal nodes in the subgoal tree as follows: Each occurrence of a B in the subgoal is replaced by crC where Q(B'=C) is an element of the FD list and cr is the most general unifier of B and B'. The restrictions on the variables specified by Q are checked and appropriate literals are added to the subgoals when the restrictions are not already known to be satisfied. The replacement of defined quantities, as specified by FD, is a recursive process since the definition of a quantity may contain other defined quantities. In addition, some defined quantities can not be removed and the definitions of such quantities are added to the subgoal. For example, the definition of ordered pair was added to the subgoals of the ex ample of Sec. 2 because the , operator could not be removed.
The above process is continued until all pertinent definitions have been incorporated into the subgoal. Then it is converted into clause form which is passed to a resolution-based theorem prover, called the sub goal solver (SGS), for proof. Note that the SGS never refers to FD and BD. Instead TPI, selects, via gener ating the tree of subgoals, the relevant elements of FD and BD to be incorporated into the terminal subgoals before they are passed to the SGS. This is important because most of FD and BD are not used in proving any one theorem.
It is quite easy to see the conditions under which the TPI is complete. Suppose that for each defined quantity B, there is an entry on both BD and FD and one of the entries Q·(Ai+B) on BD has the property that Oi(B+A·) is also 1 true. ~hen some subtree.o~ the AND/OR subgoa~ tree will be equ1valent to the or1g1nal theorem, in the sense that it is valid if and only if all of the terminal nodes in the subtree are valid. The reason is that each OR node has a subnode which is equivalent to it by the above assumption. Since the elements on FD all have= as a main connective, the clause form of a terminal node which is passed to the SGS, is equivalent to the node.
The above is a brief argument showing that TPI is complete if the SGS is complete and the ~n~fication ~1gorithm is complete. Both of these cond1t1ons are Vl olated by the current version of TPI. The SGS does not process equality in a complete way:-~ diffic~lty which can easily be removed. The d1ff1culty w1th ~he unification algorithm can only be removed.by remo~1~g all higher-order variables because there 1s ~ unlflca tion algorithm for higher-order logic. 4 Although TPI is not complete, its underlying approach (i:e·~ a~ AND OR tree of subgoals) is complete. We feel 1t 1s lmpor tant that we know in what ways TPI is incomplete and what are the difficulties in the way of making TPI com plete.
4. Formulation of BD and FD
This section discusses certain pragmatic considerations in the formulating of FD and BD. .
Consider modifying the definition of group in ~ec. 3 by "anding" right cancellation to {13). W~u~d.thls make TPI's job easier or harder? If the def1n1t1on on BD were modified this way TPI would always have to do more work. The reason is that BD is only used when trying to prove that something is a group, i.e., when Gr( ... ) is the consequent of some subgoal. It would.be ridiculous to try to prove right cancellation in addl tion to the 3 conjuncts of {13) since the latter are sufficient. Thus, a statement on BD should be "minimal" in the sense that removing any conjunct from its ante cedent causes the statement to become invalid.
Adding right cancellation to the definition of group on FD may be quite useful because thi~ statement is used when TPI is "given" that something 1s a group. Thus this modification will allow the SGS of TPI to use ;ight cancellation of the given group in proving a subgoal. In general, for any definition Q{B=C) on FD~ a ~eviously proven theorem of the form 9(~+~) can be ln corporated into FD by using the new def1n1t1on Q(B=C&D) on FD. Note that the logical conne~tive of this new definition is still =· Of course, 1f too many previously proven theorems are incorporated into a de finition on BD, .TPI may become bogged down. But adding a few carefully selected previously proven theorems can be very beneficial. . .
Another beneficial way to express th1ngs lS to re move certain existential quantifiers from definitions. Although quantifiers cannot be "moved across" an = (which statements on FD contain) extra par~meter~ can be added to definitions which allow the ex1stent1al quantifiers to be removed. For example, suppose we de fined group as a predicate with two arguments: set and operator. Then the definiens would contain "there . exists an identity and an inverse such that ... " M~k1ng the identity and the inverse arguments to the predl cate as in Sec. 3, removes these two existential quan tifi~rs. This formulation allows one to give TPI id~n tities and inverses in the statement of theorems a~ ~n Sec. 2. But more importantly, it allows other deflnl tions to refer to these quantities. For example, the predicate subgroup can be defined by
If group werea 2-place predicate this definition would not be possible.
5. An Example with More Complex Higher-Order Terms
Although TPI processes higher-order variables incompletely, it can still handle the example, below, which is to prove that the set of homomorphisms from one abelian group to another is a group. For readabi lity quantifiers and domains of quantified variables will be omittted from the formulae b~low . Rather we will note in the text the domain of variables and con stants whenever this information is important.
The theorem is
In the above, u and v are homomorphisms , xcG, and Ab is the predicate stating its first argument is an abelian group with respect to its other 3 arguments. Similarly Gr is the group predicate (see Section 2).
The definition of homomorphism (on both FD and BD) states
where f :G ~ H.
In (19) we have used for arguments of homo, the same names as used in (15) for readability, but in BD and FD the arguments of homo are universally quantified.
The theorem (15) is eventually broken into the 6 terminal subgoals shown in Fig. 3. Space only permits us to describe the highlights of the generation of these subgoals.
The generation of 2 in Fig. 3 is typical of the generation of the first 3 subgoals. From the defini tion of group we get the AND subnode whose consequent is
where u is any homomorphism. This just states that S is the inverse, and by "\ -conversion" immediately sim plifies to
Both the left and the right of (21) are functions from G to H; i.e., their domain are (FN G H). As mentioned in Sec. 3, FN is a primitive built into TPI . To prove that two functions are equal TPI invokes functional ex tensionality,
an axiom built into TPI. This produces the subgoal
where a is a constant in G. (23) immediately simpli fies to f(a) *I(f(a))=E.
Subgoals 4, 5, and 6 in Fig . 3 are generated be cause the terms substituted for the variables in the definition of a group are not known to be in the re quired domain. We will describe the generation of sub goal 5, which is typical of the other two. The domain
where of s is required to be a function from homomorphisms to homomorphisms according to the definition of a group on BD. However, according to (17), TPI only knows that the domain of S is (FN(FN G H)(FN G H).Thus the subgoal Sc(FN homo(G,H,+,*)homo(G,H,+,*)) is gen erated. TPI uses the built-in axiom, Vx(xcA~f(x) c B) ~ f c(FN A B), to generate the subgoal,
where f is a constant homomorphism. Simplifying (24) with "\-conversion" we get
Replacing homo by its definition and simplifying we get subgoal 5 in Fig. 3.
Currently, TPI cannot prove (15) because the com mutativity axioms give rise to too many resolvants at each step. Although this is no problem for the first 4 subgoals in Fig . 3, it prevents the SGS from proving 5 and 6. We have included this example because the emphasis in this work has been on the generation of simple subgoals which TPI does in this example. We be lieve that existing resolution theorem provers can prove 5 and 6 in Fig. 3 and thus if TPI had a more sophisticated SGS, it could prove (15).
6. Conclusion
Most contemporary theorem provers have difficulty proving a theorem whose proof is relatively long or whose statement is relatively long (i.e., large number of clauses). The goal of our research is to develop a theorem prover which is somewhat insensitive to the length of the proof and the length of the statement of the theorem.
The three main methods in TPI for achieving this goal are: (l) dividing the theorem into independent subgoals, (2) the special treatment of definitions, and (3) implicit use of restricted quantification. The purpose of (l) is to make TPI sensitive to the length of the proof of the "longest " subgoal as opposed to the length of the total theorem. Empirical results indi cate that (l) achieves this purpose quite well.
The main purpose of (2) is to disregard those de finitions that are not necessary for the proving the orem. Currently, TPI is given 14 definitions and no theorem has used more than 4. Thus, the extraneous definitions are considerably longer than the theorem and the pertinent definitions. The processing of de finitions also interfaces very nicely with (1), al lowing TPI to subdivide subgoals into independent sub
goals. The purpose of (3) is to give high priority to in ferences which prove that variables are in the correct domain. This heuristic allows TPI to discover longer proofs because such inferences are done implicitly. Of course, the price paid for this ability is an increase in the amount of time for each explicit inference.
The example in Sec. 2 shows that TPI has achieved, to some extent, its goal. The statement of the theo rem given to TPI (including extraneous definitions) is 48 clauses, and the shortest proof that we know of is 27 binary resolutions.
The methods of TPI form a complete system of first-order logic. Although TPI cannot process higher order terms in a complete way, its methods are suffi cient for some interesting theorems containing higher terms. Initial results indicate that the use of lambda notation and \-normal-form are very powerful theorem proving techniques.
Other theorem provers have used methods which are quite similar to those of TPI. Subdividing a theorem into parts has been used by Bledsoe, 1 Nivens, 5 Norton, 6 and Slagle and Koniver, 7 and probably others. Norton 6
uses definitions in a way which is very similar to TPI and Bledsoe's' use of definitions is somewhat similar. Although the overall characteristics of all these theo rem provers (including TPI) are quite different, they all proved some relatively impressive theorems. In particular, each can prove theorems that the others cannot prove. However, this author believes that in each case much of the power stems from the same few basic principles even though the methods of these theo rem provers were independently developed along quite different 1 ines.
Acknowledgments
This research was supported by the National Science Foundation under grant GJ-1135, and the Air Force Office of Scientific Research under grant AFOSR7l-2110C.
@inproceedings{ijcai1973p8,
title = {A Definition-Driven Theorem Prover},
author = {Ernst, George W.},
booktitle = {Proceedings of the Third International Joint Conference on
Artificial Intelligence, {IJCAI-73}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Nils J. Nilsson},
pages = {51--54},
year = {1973},
month = {8},
note = {Theorem Proving and Logic: 1},
url = {https://ijcai.org/proceedings/1973/8},
}
TY - CPAPER TI - A Definition-Driven Theorem Prover AU - Ernst, George W. T2 - Proceedings of the Third International Joint Conference on Artificial Intelligence, IJCAI-73 PB - International Joint Conferences on Artificial Intelligence PY - 1973 SP - 51 EP - 54 UR - https://ijcai.org/proceedings/1973/8 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: