A Man-Machine Theorem-Proving System
Proceedings of the Third International Joint Conference on Artificial Intelligence. Theorem Proving and Logic: 1. Pages 56-65.
© 1973 International Joint Conferences on Artificial Intelligence
Abstract
This paper describes a man-machine theorem proving system at the University of Texas (Austin) which has been used to prove a few theorems in general topology. The theorem (or subgoal) being proved is presented on the scope in its natural form so that the user can easily comprehend it and, by a series of interactive commands, can help with the proof when he desires. A feature called DETAIL is employed which allows the human to interact only when needed and only to the extent necessary for the proof. The program is built around a modified form of IMPLY, a natural-deduction-like theorem proving technique which has been described earlier. A few examples of proofs are given.
- W. w. Bledsoe, R. S. Boyer, and W. H. Henneman, Computer Proofs of Limit Theorems, Artificial Intelligence 3 (1972), 27-60. IJCAI
- W. W. Bledsoe, Splitting and Reduction Heuristics in Automatic Theorem Proving, Artificial Inte lli gence 2 (1971), 55-77.
- J. R. Guard, F. C. Oglesby, J. H. Bennett, and L. G. Settle, Semi-automated Mathematics, JACM 16 (1969), 49-62.
- John Allen and David Luckham, An Interactive Theorem-Proving Pro gram, Mach ine Intelligence 5 (1970), 321-336.
- G. P. Huet, Experiments with an Interactive Prover for Logic with Equality, Report 1106, Jennings Computing Center, Case Western Reserve University.
- John McCarthy, Computer Progr ams for Checking Mathematical Proofs, Proc. Amer. Ma th. Soc. on Recursive function Theory, held in Ney York, April, 1961.
- Paul w. Abrahams, Mach ine Ve rification of Mathe- matical Proof, Doctoral Dissertation in Mathematics, MIT, May, 1963.
- w. w. Bledsoe and E. J. Gilbert, Automatic Theorem Proof-Checking in Set Theory: A Preliminary Report, Sandia Corp. Report SC-RR-67-525, July, 1967.
- Arthur J. Nevins, A Human Oriented Lo gic for Automatic Theorem Proving, MIT AI Memo No. 268, October, 1972.
- Raymond Reiter, The Use of Models in Automatic Theorem Proving, Dept. of Computer Science, University of British Columbia, September, 1972.
- TAURUS, described in Users Manual, Computation Center, University of Texas, Austin.
- Pe ter Bruell, A Description of the Functions of The Man-Machine Topology Theorem Prover, (under preparation).
- John L. Kelley, General Topology , van Nostrand, 1955.
- James R. Slagle, Automatic Theo rem Proving with Built-in Theories Including Equality, Partial Ordering, and Sets, JACM 19 (1972), 120-135.
- Robert Boyer, Locking: A Restriction on Resolution, Ph.D. Dissertation, Mathematics Dept., University of Texas, Austin, 1971.
- Dallas S. Lankford, Equality Atom Term Locking, Ph.D. Dissertation, Mathematics Dept., University of Texas, Austin, 1972.
- George Ernst, The Utility of independent subgoals in Theorem Proving, Information and Control, val. 18, 3, 1971.
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.
Some workers in automatic theorem proving, in cluding the authors, believe that it will be many years (if ever) before machines alone can prove difficult theorems in mathematics. Thus some, who hope to see machines used as practical assistants to pure mathematicians, have redirected their attention to man-machine theorem provers [3, 4, 5] and theorem proof checking [6, 7, 8] .
The present paper describes a man-machine theo rem proving system at the University of Texas which has been used to prove a few theorems in general topology. Our system is organized in the same general way as those of Guard [3], Luckham [4], and Huet [5], but with many major differences. For example, Luckham and Huet use variations of Resolution as their principal rules of inference whereas we use a modified form of IMPLY [1], which is a natural-deduc tion-type method.
Also our system displays formulas on the scope in a natural, easy to read, manner and has available a variety of interactive commands the user can employ to help with the proof. Among these is a feature called DETAIL which allows the human to interact only when needed and only as much as is required for the proof-.---
As yet this system has proved no new theorem in topology. The program is still in the state of devel opment and it will be sometime before we can deter mine whether it can materially help a mathematician prove new theorems.
This paper describes the facility, the inter active commands available to the user mathematician, the modified version of IMPLY which is used, and gives a few examples of proofs of theorems.
2. The Facility and Interactive Commands.
The facility consists of a Datapoint 3300 ter minal connected to the CDC 6600 computer via the UT interactive (time-sharing) system TAURUS [11] . A mathematician (the user) sits at the terminal, types in a theorem to be proved and occasionally helps the program with the proof by providing information he feels is needed and answering questions the program poses.
The computer program consists of a large auto matic theorem prover and a subroutine for interacting with the mathematician. The theorem prover, which is described in Section 3, is written in LISP and is based on IMPLY (see Section 4 of [1]) and the methods given in [1] and [2]. It has the ability to prove theorems on its own; human intervention is used to increase its power and speed up proofs. The DETAIL Feature.
--- One of the principal difficulties with most man machine provers is in knowing when and how the man should intervene. Firstly the human may have trouble in reading and comprehending the text on the scope, and secondly, he doesn't know when the machine should be helped, and how much he should do. He does not want to make a lot of unneeded entries, and if he makes a mistake he wants to easily recover.
The first difficulty is solved in the system described here by employing the human oriented lan guage IMPLY and in displaying the theorem on the scope in a "pretty-print" form. This is further described below.
The second difficulty is handled by a procedure which allows the computer by itself to first try to prove the theorem (or subgoal) . If it succeeds, then all is well, but if it fails within a prescribed time limit, it prints on the scope the statement of the theorem and the word "FAILURE" and awaits a command from the user. If he commands "DETAIL" then it will proceed (again) with its proof to the point where the current goal is split into subgoals. At that point it prints on the scope the statement of the new subgoal for which it failed and stops, and the whole process can be repeated.
At any of these stops the user can employ a variety of other commands such as DEFN, PUT, USE, etc. (which are described below) to help with the proof. In this way he can easily isolate the difficulty and make only those entries needed by the machine in its proof. Indeed he can start the machine on the proof of a theorem without enough hypotheses (reference theorems) and supply them only when and if they are needed in the proof .
The following is a symbolic example for explain ing the DETAIL process. Real examples are given in Section 4.
Suppose the machine is able to convert the example (H ~ C) into two subgoals (H ~ D) and (H ~E) by defining C as (D ~ E) and suppose it can prove (H ~D) but not (H ~E), but that it can prove (H ~ H 2 ~E). Then the dialogue would be as follows:
| Human: | (H ~ C) (H ~ C) FAILED | |
|---|---|---|
| Machine: | (1) | |
| Human: | DETAIL | |
| Machine : | (11) | (H ~ D ~ E) (H ~D) PROVED |
| Human: | GO | |
| Machine: | (12) | (H ~E) FAILED |
| Human: | DETAIL | |
| Machine: | (12) | (H ~E) FAILED |
| Human : | USE H 2 | PRETTY-PRINT | TP It prints the theorem | ||||
|---|---|---|---|---|---|---|---|
| Machine | (not e : her e H2 is some l emma or axiom) : (12) (H ~ H + E) on the scope in a easi l y r eadable form (see Example below). | ||||||
| Machine : help was | (1) given only when needed | PROVED 2 (H A H2 + C) PROVED . the only r eal human intervention was . TP F If PUT F ; ( ) has been used earlier , it print s the theorem on the scope wi th each occurrence of ( ) re | TP F G | Similarly for F, G, e t c | |||
| Notice that at the s t ep where he commanded (USE H 2 ), and that placed by the symbol F . | |||||||
| The Interactive Commands. The following is a listing of some of the inter TPC F Simi l arly for conclu sion only . | |||||||
| active commands avai lable to the user . A few of these are further exp lained below and in [12]. In the following the word "theorem" is some times used to r epresent the current subgoa l being proved. TPH F Simi l ar l y for hypo thes i s only. | |||||||
| NAME OF COMMAND | USER TYPES | THE MACHINE 'S RESPONSE | HISTORY RUN HISTORY | The machine r edoes the steps in the pr oof down to the current point, but eliminat es unproductive s t eps . | |||
| PUT | PUT x ; ( | The machine each | r ep l aces occurrence in the theorem being proved by ( ) . ADD-REDUCE | ADD -REDUCE | ( is (permanently) added to the REDUCE t ab l e. | ||
| DEFN | D A | It replaces al l occurr ences of A by it s (s | tored) definition . ADD -PAI RS | ADD -PAIRS | ( is (permanently) added t o the PAI RS Table | ||
| USE | USE N | It fetches theor em numbe r N from memory and adds it t o the hypothesis of the cur r ent theor em. | ADD-DEFN Comput | ADD -DEFN (A | ( )) ( ) is added t o the definition table as the definition of the atom A. stopped at any point by | ||
| LEMMA | USE | It adds ( hypo | ) to the thesis . the us e of an to r e turn t o | ation can a interrupt the beginning | lso be which wi ll cause the program of the function IMPLY and | ||
| LEMMA ( | It first proves ) and then call s USE ( | ). halt. Most of the commands described above table. If a command has changed the | ar e r etr ac | ||||
| PROCEED | GO | It proceeds with the proof wi th no changes by the user . | theorem in any way the machine displays the changed vers i on and then asks "OK??? " The program will then make the change permanent only i f the user t ypes "OK." The machine theor em prover used in thi s sys t em has been revised (from [1]) to provide a more parallel type of search | . This | i s.described below. | ||
| DETAIL | DETAIL | (see explana tion above) It find s the fi r s t sub goa l of the current goa l, displays it on the scope, and s tops. | As in [2] the pr esentation of the theor em on the scope is in its original na tural form for easy r eading by the mathematician. No unna tural conver s ions, such as changing (A + B) to (~A v B) , ar e made. Add itionally, when a symbol, say F, has been r eplaced s ion ( ), the mathematician can, | ||||
| COUNT | CNT N | It increases the time limi t on the current | subgoa l by a factor N. by a l ong expres by t yping TP F, t o be in t erms easier for him | cause of F t o | the pr esentation on the screen ins t ead of ( ), thus making it comprehend. | ||
| FAIL | F | It fails the current subgoa l (i. e ., returns NIL) . | Such conveniences ar e necessar y to make possible real-time communication be t ween the mathema tician and the comput er's prover. | ||||
| ASSUME | A | It assumes the current subgoa l t o be proved and proceeds . | Skol em functions ar e used to eliminat e quantifiers but the expr ess ions are l ef t in their natural form (seep. 37 of [1 ] and p. 18 of [ 10] ) , easi l y r eadable by the human. Printing of theorems and subgoals on | ||||
| BACKUP | REJECT | It r eturns NIL and backs up in the proof t o the previous goa l. | the scope is done with sko l em argument s suppr essed t o furthe r improve readability. PUT. One of the principal difficulties encountered i n aut omatic theorem proving (indeed i n human theorem | ||||
| REORDER | (N + M) | It reorders the goa l, placing hypothesis number N f irs t and conclusion number M | proving) i s the problem of instantiating a variabl e . For example, it is essentially trivial to ins t antia t e the variabl e x as x 0 in (x A + j x (x A))~' | ||||
| DELETE | DELETE N M .. | . fi r st. It deletes hypo theses number N, M, . .. | ~•The quantifier " " is r etained | 0 € | € here for ease of | ||
but it is far more difficult to find an acceptable value for G in the expression
where H is a given hypothesis. In such a situation a machine prover might eventually find and verify a satisfactory G, depending on the nature of H, but it9 work can be tremendously reduced if the mathe matician would indicate a value for G. For example, he might put
Then (1) becomes
which can now be split (by the computer) into three subgoals . The first subgoal of (3) becomes
which i s converted to
This is again split; the first subgoal becomes
closed) which is reduced by the computer to
and then to
The subgoal (5) is now easily proved by the com puter referring to a REDUCE table (see p. 57 of [2] and Section 3) which shows that Closure A is always closed.
Similarly, the second subgoal of (4) is r educed to
which again is easily proved if H contains the hypothesis
The other subgoals of (3) are handled similarly, using other hypotheses from H.
Thus the very difficult problem (1) has been re duced to a series of easier problems by the human action (2) and some machine manipulations. It is true that the mathematician is required to provide the most difficult step in the proof but then the computer does the rest, proving a series of smaller theorems and verifying that the mathematician's choice for G was indeed correct . If he made a wrong choice at (2) he might want to intervene later, backup, and try a different value for G.
The PUT feature, though quite simple, is a very powerful device. It alone makes a tremendous differ ence in the number of theorems the computer program can prove.
DEFN. When the mathematician desires that a certain expression, such as "Reg .", be defined, he types
and the machine immediately replaces each occurrence of "Reg" (in the subgoal being proved) by· its defini tion.
When an expression is replaced by its definition, the particular skolemization of that definition will depend on its position in the formula. For exampl e, the expression
would be . replaced by
whereas
would be replaced by
An option is provided so that DEFN can be applied to only parts of the expression. Thus for example, "Reg" might be replaced by its definition in the conclusion but not the hypothesis.
PRETTY-PRINT. The command TP causes the machine to print the current theorem (subgoal) in a parsed, easy to read form. For example , if the theorem is
the command TP will cause to be printed on the scope:
(OC (F))
(REG)
(OCLFR)
(CC G)
(REF G(F))
(LF G)
Note that the skolem constant (FSDl) has been printed as (F), though its complete form is retained by the program.
Now if the command
is used, the conclusion of (1) is altered accordingly. The command TPC if issued now will cause
to be printed, whereas TPC G causes
+
(H + Reg)
to be printed.
HISTORY. If commanded the program keeps a record ~istory) of each step it has taken in the proof of a theorem, including steps where the human intervenes but excluding unproductive steps. This history can be used by the mathematician later, upon the command "RUN HISTORY N", to rerun all or part of the proof without interruption, and to try if desired a different line of proof at any step.
3. The Machine Prover
·rhe prover used by this system consists mainly of a modified form of IMPLY (Section 4 of [1]), with the addition of REDUCE (seep. 57 of [2]), and other concepts from [2] and [17].
Two of the principal differences in the present version is that IMPLY is now the main routine (instead of CYCLE), and REDUCE is now applied inside IMPLY. The SPLIT functions (p. 56 of [2]) are an integral part of IMPLY itself. Also IMPLY has been given a breadth-first search capacity (see below), and the back-up feature (see Footnote 11 of [1]) has been removed and replaced by a human back-up capability. IMPLY. IMPLY is a natural deduction type system which processes formulas in their "natural" form (see also [9, 10]). It consists partially of a few rewrite
rules such as
which convert the expression being proved from one form to another . Its main function is to split a goal into subgoals
backchain, substitute equals, and forward chain (new addition). A fundamental part of IMPLY is a matching routine (unification): if T is a most general unifier of A and A' then the subgoal
is judged "TRUE" with T being returned to be applied to further subgoals.
REDUCE. REDUCE consists wholly of a set of rewrite rules which converts parts of formulas. It contains special heuristics for set theory, topology, etc. For example
*Since REDUCE is now called from inside IMPLY, it (RE DUCE) must eliminate quantifiers and skolemize in the course of reducing formulas. As was explained in Sec tion 2 under DEFN, the exact form of this skolemization depends on the position of the expression in the theorem.
etc.
REDUCE helps convert expressions into forms which are more easily provable by IMPLY. It also is a con venient place to store facts that can be used by the machine as they are needed. For example REDUCE returns "TRUE" when applied to such formulas as (Closed Clsr A), (Open X), (Open 0), (Open interior A), (0 <:: A), etc.
Forward Chaining. It seems that unrestrained forward chaining is a poor idea in automatic theorem proving because it tends to produce an excessive number of useless hypotheses (lemmas). Consequently, our earlier versions of IMPLY relied heavily on backward chaining. However, the use of the man-machine system (especially the PUT feature) on theorems in topology has brought to our attention the power of forward chaining in many proofs, especially in cases where the chaining expression is a ground (all constant) formula. We therefore have provided ground forward chaining as a new rule in IMPLY .
RULE (forward chaining). If P 0 is a ground expres sion (i.e ., contains no variable~which is an instance of P(i.e., there is a substitution T for which
P 0 = PT) then the goal
is converted to the new goal
This rule need only be applied at the time some thing new is added to the hypothesis, such as when an expression (H + (A+ B)) is converted to (H A A +B), or when another forward chaining step has just been completed.
This rule has been further extended in the system to provide for so-called "PEEK forward chaining",
which works as follows:
RULE (PEEK forward chaining). If P is a ground expression, P 0 = PT, A has the de~inition (P + Q), then the goal
is converted to the new goal
Note that the machine "peeks" at the definition of A to see if forward chaining is possible, but then returns A to its original form. This variation is very useful (see Example 2, (111 Hl)). Returning A to its original form makes the theorem much easier to comprehend for the mathematician reading the display on the scope.
Forward chaining still tends to clutter up the scope with useless hypotheses, and the user occasion ally finds it useful to remove some of them by the command DELETE. More importantly the user, when he gives the computer a theorem to prove, need not list all required lemmas but can give them only as they are needed in the proof, and thereby can eliminate much irrelevant forward chaining.
Breadth-First-Search. One of the difficulties with the previous version of IMPLY was that its search was essentially "depth-first." For example, in proving
it would back chain off of
and try to prove H(x 0 ) , before finally getting around to the trivial proof (P(x 0 ) + P(x 0 )).
0 A more serious difficulty is encountered in instantiating definitions , in that not enough direc tion is provided as to which definition to instantiate first. As a general rule, an expression such as "reg" should not be replaced by its definition unless it will "do some good." Otherwise a glut of new symbols hamper both man and machine. Also it is usually better to instantiate definitions in the conclusion before those in the hypothesis, and to instantiate definitions of "strange" terms such as "paracompact" before those of ordinary terms such as " closed" or "c ."
- A human, acting more intelligently, would casually glance across the hypotheses, and notice P(x) before trying to establish H(x 0 ).
We have attempted to remedy these two diffi culties and have also added another feature called "PAIRS" which tries if possible to apply that hypothesis which is like the desired conclusion, ~ when a complete match cannot be made.
---- The following is a rather sketchy description of the revised IMPLY program, which gives only the flavor of it. A detailed description is given in [ 12].
When a theorem (or subgoal)
is given for IMPLY to prove, it first calls REDUCE, then applies its own rewrite rules, and SPLITS it if appropriate. Next it does a breadth-first search by trying the following seven steps in the order indicated . If any step fails it goes to the next; the success of a step usually results in another call to the function IMPLY.
- Match
- Match and Backchain
- PAIRS
- PEEK
- Define c
- Define strange terms
- Define any term.
These are described in more detail below. With the exception of step 5 each of the steps listed involves a call from IMPLY to a function called HOA. What basically happens is that IMPLY splits the theorem into subgoals on the basis of the OR-AND structure of C , and HOA attempts to use the hypo theses to prove these subgoals.
- Try matching the conjuncts of H with C. That is if H is of the form H 01 ~ H 2 ~ H 3 it tries to match C with one f the H ..
- Same as 1., except that backchaining is ~ allowed. For example, in
it would first try matching C and H 1 , and then if that failed, it would try to match C and C' and backchain.
- Try PAIRS. If the main connective of C matches the main H. of H (but C ~ then consult the which would yield connective of a conjunct and H. do not match), ~ PAIRS table for conditions
and try to prove those conditions . For example, given
(here (Ref Glo) means that Go is a r e - finement of F 0), PAIRS would consult the PAIRS table and find
there. If it can establish this new subgoal, the proof is concluded. If that fai ls it will look for another entry on the PAIRS t ab le concerning Ref.
- PEEK at definitions in H. Here we do not arbitrarily instantiate definitions of ex pressions in H, but rather do so only if we find in a conjunctive position of H a possible match for C. For example, in
we first look at the definition of reg and find no reference to "cover", so we leave reg as it was and try the definition of open cover F 0 , which is
Since "cover" appears in a conjunctive posi tion, we reta in this definition, and our theorem becomes
Starting again at Step 1 we eventually con sider PAIRS (Step 3) on
which may or may not succeed. If it fails, the theorem is returned to its original form
and Step 5 is then tried.
- Instantiate the definition of the main con nective of C.
- Instantiate the definition of the first "strange" symbol in H.
- Instantiate the definition of any symbol in C. Equality Substitution. IMPLY employs a form of equal ity substitution whereby if given the goa l
the program first tries to prove
where A' and C' are obtained from A and C by replacing all occurrences of a by b, and then if that fails, tries repl acing b by a.
This has been sufficient for many applications, but more sophisticated methods may be needed such as those used by Nevins in [9], Slagle in [14], or the "equality-term-locking" of [ 16], or others, which pro vide guidance for which of a or b should be re placed by the other.
~· Exampl es .
The examples we have exp lored ar e mostly from Kelley's Genera l t opology [13], though in fact any reasonably precise t ext wou l d do .
We have taken examples from various parts of the book . Exampl e 2 i s a theor em about paracompactness . The examp l es tried so far have been about just one topology . This i s convenient since it al l ows f i xed symbols T and X for the topology T on the space X. The space X is assumed to be non- empty. The definitions used by the computer ar e stored (perma nently) in its memory.
The theorem l abe ls used in the following examples ar e also those used by the computer. They help inform the user wher e he is in the pr oof. For examp l e, if a goal has theor em l abe l (1 2) and it SPLITS, then the two parts will be l abe l ed (1 2 1) and (1 2 2). If back chaining is us ed on a theorem l abeled L, then the two s t eps are l abe l ed (LB) and (LH) .
The presentation on the scope is al ways in the "pretty- print" forma t depicted on page 11. But to conserve space we have her e shown our examples in a more compact f orm, and some lines of the proo f are omitted.
In this present ation, an "h" a t the l eft indi cates a human input, an "Ed" indicates an editorial connnent, and an "m" indicates machine output. The m's ar e omitted in our description aft er the firs t few lines of each exampl e .
In the examples
The expression
T
Cover G
Oc G
cc G
Reg
Lf G
Ref G F
Oclfr
Occlfr
Nb N x
subsets A
aG
Means
The topology (family of open sets) on the ·space X
X c U A
- A€G
G c T ~ Cover G
G c Closed ~ Cover G
The topology is r egular (defined below)
G i s locally finite
G i s a r efinement of F
Ever y ·open cover of X has an open l ocally f inite refinement
Every open cover of X has a closed locally finite r ef inement
N i s a neighborhood of x
The set of subset s of A
U A
A€G
- EXAMPLE 1. (Theorem 1, p. 38 of [ 13 ]). A set is open if and only if i t contains a nei ghborhood of each of its points .
DIALOGUE
- h (Open A H x € A + 3N(Nb N x ~ N C:: A)
- Ed This is the statement of the theorem to be proved.
- m (1) (Open A ._ x € A + 3 N (Nb N x ~ N C:: A) FAILED TIMELIMIT ..
- Ed The two do ts, .. , indica ted that the mac hine has stopped for human input. The computer has fai l ed to prove (1) in its prescribed time limit.
- h DETAIL
- Ed The computer has taken the skolemi zed expr ess i on (1 1) as the fi r s t half of (1) . A 0 and x 0 are skolem constants and N i s a var~able for which a value must be found tha t sat i sf ies the conelusion.
- h DETAIL
h DETAIL
h GO
h GO
h GO
- Ed This was proved by REDUCE which knows that A c A for any A.
h GO
- Ed This is the second hal f of (1). Note that the sko lemi zation i s dif ferent f rom that in (1 1) .
- h DETAIL
- Ed The machine (at Step 5 of IMPLY), "de fines " open. No t e tha t in this case a use ful char acteri zation is given in place of a bonafide definition.
- (1 2 1) ( ( FAILED ) + F c:; T A A 0 = aF)
- h DETAIL
- (121 1) (( )+Fc:;T)
- FAILED
- Ed At this point the human user realizes that he must help the machine by giving a value for F.
- h PUT F = T n subsets A 0
- (121 1) ((x € A 0 + Nb N(x)x A N(x) c:; A 0 ) + ( Tn subsets A 0 ) C:: T) PROVED
h GO
- (121 2) ((x € A 0 + Nb N(x)x A N(x) c:; A 0 ) + A 0 = a (r n subsets A 0 )) FAILED
- h DETAIL
- Ed t € ~O is forward chained into the e~istLng hypothesis to yield (Nb N(tn)t 0 A N~t 0 ) c:; A 0 ) which is added to the fiypothesLs.
- Ed where N is written for the skolem
- expressi9n N(t 0 ).
- Ed It now "peeks" into the definition of "Nb", finds "open" there, and hence uses the definition of Nb.
- PROVED h GO
- Ed This subgoal easily follows by the trans itivity of "c:". Such a rule could be build in as in [14], or we could use a locked axiom as in Chapter 7 of [15]. Another possibility is to "forward chain" (A 1 c:; N 0 ) into (N 0 c:; A 0 ) to get (A 1 c:; A 0 ). Some such device will probably be used in future programs, but here we employed the command "USE", and the program easily completed the proof. ·
- h USE (A '= B A B ::: c + A '= C)
EXAMPLE 2 . (Theorem 28(b +c), p. 156 of [13]). If X is a regular topological space and each open cover of X has a locally finite refinement, then each open cover of X has a closed locally finite refinement.
DIALOGUE
- h (Reg A Oclfr + Occlfr)
- m (1) (Reg A Oclfr + Occlfr)
- m (FAILED TIMELll1IT ..
- Ed The computer has tried and failed to prove (1) in its prescribed timelimit.
- h DETAIL
- (1 1) (Reg A Oclfr A Oc F 0 + cc G) FAILED TIMELIMIT
- Ed The computer has defined Occlfr, moved the expression Oc F 0 to the hypothesis, and split the conclusion, giving (1 1) as the first subgoal of (1) on which it failed.
- Ed Here F 0 is a skolem constant and G is a variable which is to be chosen to satisfy the theorem. The most important and hardest thing the program has to do is to find an acceptable G.
- h DETAIL (Reg A Oclfr A Oc F 0 +Cover G A G c: Closed)
- (1 1 1) (Reg A Oclfr A Oc F 0 + Cover G) FAILED ..
- Ed At this point the human operator realizes that he must help by giving a value for G. He does this in three steps below, by first asking that the expression Oclfr be defined, and then giving values for the variables F' and G.
- h D Oclfr
- h PUT F 1 = (B 1 : Open B 1 A :f B (B € F 0 A Clsr B 1 C:: B)}
- Ed In this writeup we have denoted by G 0 the skolem expression G(F 1 ). The machine retains its complete skolem expressions but prints only (G) on the scope for ease of reading.
- Ed Since the new entry [*] in the hypothesis is an implication, and since F 1 has been given a value, the machine first tries proving OcF 1 before proceeding. This is done in (111 H) below. If it succeeds it will then retain the hypothesis
instead of [*].
- m TRY PROVING HYPOTHESIS
- (111 H) (Reg A Oc F 0 * Oc F 1 )
- Ed We are writing F 1 here but the machine retains the value of F 1 given above .
- (111 H) (Reg A Oc F 0 * Oc F 1 ) FAILED TIMELIMIT
- h CNT 4
- Ed The operator has increased the timelimit by a factor of 4 (for this goal only) and this causes success. More details of this part of the proof will be given below.
- (111 H) (Reg A Oc F 0 * Oc F 1 )
- m ESTABLISHED HYPOTHESIS
- (1 1 1) (Reg A [Cover G 0 A Ref G 0 F 1 A Lf G 0 ] A A OcF 0 *Cover G)
- Ed It is now ready to continue with the proof of (1 1 1). The human makes his final input. Bar G 0 is the set of closures of members of G 0 .
- h PUT G = Bar G 0
- (1 1 1) (Reg A Cover G 0 A Ref G 0 F 1 A Lf G 0 A Oc F 0 *Cover (Bar G 0 ))
- m TRY PAIRS (cover)
- (111 P) (Reg A Ref G 0 F 1 A Lf G 0 A Oc F 0 *Ref G 0 (Bar G 0 ))
- Ed When PAIRS is presented with (COVER G 1 * Cover G 2 ) it suggests trying Ref G 1 G 2 . Ref G 1 G 2 _ means that G 1 is a ref~nement of· G 2 , Le., each member of G 1 is a subset of a member of G 2 ·
- Ed (111 P) is proved by REDUCE which has on its table that Ref F(Bar F) for any F.
- (1 1 1) (Reg A Cover G 0 A Ref Gl 1 A Lf G 0 A Oc F 0 * Cover (Bar G 0 )) PROVED
- h GO
- (1 1 2) (Reg A Cover G 0 A Ref G 0 F 1 A Lf G 0 A Oc F 0 * (Bar G 0 ) C:: Closed) PROVED
- Ed Note that the new value (Bar G ) is given for G, and also the thre~ new hy potheses obtained for the proof of (1 1 1) are retained in (1 1 2).
- Ed Again REDUCE proves (1 1 2) since it knows that BarF c Closed for any F.
- h GO
- (1 1) (Reg A Cover G 0 A Ref G 0 F 1 A Lf G 0 A Oc F 0 * cc (Bar G 0 )) PROVED
- h GO
- (1 2) (Reg A Cover G 0 A Ref G 0 F 1 A Lf G 0 A Oc F 0 * Ref (Bar G 0 )F 0 )
- m TRY PAIRS (Ref)
- Ed The machine uses PAIRS as before to easily complete the proof of (1 2).
- (1 3) (Reg A Cover G 0 A Ref G 0 F 1 A Lf G 0 A Oc F 0 * Lf (Bar G 0 ))
- Ed This is the last subgoal of (1). Lf F means the family F is locally finite
- m TRY PAIRS (Lf)
- Ed When PAIRS tries (Lf F * Lf G) it suggests trying to prove that (G = Bar F) because it knows that (Lf F * Lf Bar F). If such an entry had not been on the PAIRS table then the user might have inter vened with the command (USE (Lf F * Lf(Bar F)) which would have produced the same result. The PAIRS table is a con venient way to store such Lemmas.
- (1 3) (Reg A " * Lf (Bar G 0 )) PROVED
- h GO
- (Reg A Oclfr * Occlfr) PROVED
- Ed Q.E.D.
- Ed We now list some (but not all) details of the proof of (111 H). Recall the value of F 1 ·
- (111 H) (Reg A Oc F 0 * Oc F 1 )
m
h
m
m
- Ed When the expression x 0 € X is switched over to the hypothesis, forward chaining is performed by the machine (see Section 3). It PEEKS into the definition of Oc F 0 , and finds h
- Ed It therefore substitutes x 0 for x and obtains the addi tional hypOthesis (B (x 0 ) € F 0 A x 0 € B (x 0 )). Thus (1') be-
- Ed Where is the skolem expression B(x 0 ). The add ition of B 1 € F 0 to the hypothesis causes further forward chaining into (D € F + open D) of ('h~) to yield open B 1 , wh~ch in turn, with x 0 € B 1 , is forward chained into
to yield three more hypotheses. Thus writing B 2 for B(x 0 ,B 1 ), (111 Hl) becomes
- Ed Which is now easily proved by the program
The following example is given to show the use of PUT, ADD-DEF, ADD-REDUCE, REDUCE, and the PEEK feature of REDUCE. Many (most) steps of the dialogue are omitted in the writeup.
EXAMPLE 3. (Th. 15, P. 49 of [8]). Suppose the topo logy T has a countable base . Then each open cover of a set has a countable subcover .
At this point the user reali zes that the computer does not have the definition of Range.
Here the machine knows nothing about A expressions so it can reduce neither domain f nor f(A 1 ). So the user gives the following information.
Now the machine in trying to reduce (domain "peeks" at the definition of f, finds it to be a A-expressio~ and reduces (domain f) to F 1 . f)
In converting f(A ) it again "peeks" at definition of f to red~ce f(A 1 ) to (Choice A 1 :::B)) .
FAILED
(ADD-REDUCE (choice A € B) (A::: B)
PROVED
GO
(· · · + cbl Range f)
m
h
FAILED
(USE V f 1 (function f 1
+ cbl Range f 1 )
A cbl domain f 1
5. Remarks.
Many of the abilities which are built into this man-machine facility have been developed only after a period of trial and error. In fact the reason for many of these is to provide for more ease in checking ·out and changing the program. We expect the program to continue to change as it is tried on more and more examples, hopefully evolving into a system which will be useful to the researcher in topology. So far this is not the case, we have handled only well known theorems. Our next step involves work on the system by some practicing topologist. This should help determine whether such a system might have any practical value in the near future.
An interesting point is this. Even though the mathematician is able to intervene at any point in the proof, he is nevertheless very annoyed when he has to do so in a trivial way. When, for example, he PUTS the values for F' and G in Example 2, he feels he has done enough and rightfully expects the computer to do the rest. Thus even in a man-machine system, the theorems that the machine alone is required to prove are far from trivial. In fact experience so far shows that they are on a par with the hardest theorems being proved today by automatic theorem provers.
Therefore, it is felt that any improvement in machine-alone programs is truly worthwhile to the man-machine effort.
Acknowledgment.
Various people both at U.T. and elsewhere have greatly influenced our thinking about automatic theorem proving and interactive systems. We want to especially thank Bill Henneman, Robert Anderson, Dave Luckham, Vesko Marinov, Bill Bennett, Mike Ballentyne, and Howard Ludwig.
This work was supported in part by NSF Grant GJ-32269 and NIH Grant 5801 GM 157-69-05.
@inproceedings{ijcai1973p9,
title = {A Man-Machine Theorem-Proving System},
author = {Bledsoe, W. W. and Bruell, Peter},
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 = {56--65},
year = {1973},
month = {8},
note = {Theorem Proving and Logic: 1},
url = {https://ijcai.org/proceedings/1973/9},
}
TY - CPAPER TI - A Man-Machine Theorem-Proving System AU - Bledsoe, W. W. AU - Bruell, Peter T2 - Proceedings of the Third International Joint Conference on Artificial Intelligence, IJCAI-73 PB - International Joint Conferences on Artificial Intelligence PY - 1973 SP - 56 EP - 65 UR - https://ijcai.org/proceedings/1973/9 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: