An Automatic Theorem Prover Generating a Proof in Natural Language
Proceedings of the Sixth International Joint Conference on Artificial Intelligence. .
© 1979 International Joint Conferences on Artificial Intelligence
Abstract
An automatic theorem prover which displays a proof in system proves properti~s of recursive programs, and the proof. Then it translates the tree into the proof traverse. The proof written by this system is easy to instead of notations of logics, and some redundant and natural language is described. This constructs a proof tree corresponding to text in English by means of the tree read, because the English text is placed trivial statements are disappeared.
- Chester, D. "The proofs into English." (1976) 261-278. translation of formal ~ Intell. 7: 3
- King, J.C. "A program verit'ier." PhD thesis, Carnegie-Mellon Univ . , 1969.
- Nishimura, T. "Gentzen-type formal sys t em representing properties of functions." Comment . ~ ~ ~ Pauli. 23 : 1 (1974) 37-44 .
- Nishimura, T., Nakanishi, M., Nagata, M. and Iwamaru, Y. "Gentzen-type formal system representing properties of functions and its implementation." In~ IJCAI-75. Tbilisi , SeP•t 1975, pp. 57-64.
- Suzuki, N. "Verifying programs by alge- braic and logical reduction." In~ ~ ~ ~ Reliable Software. 1975, pp. 473-481 .
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
Many automatic theorem provers have been implemented to verify programs or to prove properties of programs [2,5]. Some of them are based on a formal system in logics. However, users of such theorem provers are often confused by technical terms of logics appeared in the proof. And so it is desired that the system should display the proof in natural language without proper terms of logics. Chester [1] gives an algorithm which translates formal proofs into English. But we rarely find the systems which have such facilities. An algorithm to generate statements which are suitable to the context of a proof for a Gentzen-type formal system representing properties of functions is described.
TKP (Tsukuba-Keio Prover) is a family of theorem provers based on the formal system. As an ordinary prover, it combines a sequent calculus (decomposing a complicated theorem into parts which are easier to prove). The sequent is decomposed by applying the rules of inference. TKP displays a proof figure if the proof of a given theorem is completed. The proof figure consists of logical symbols and terms which are used properly in logics. Though these terms are important tools to prove theorems automatically, they are regarded as codes which only logicians or experts in artificial intelligence can read.
In this paper, we describe the method for displaying proofs in natural language without proper terms of logics.
2. OUTLINE .Qf. .I.Kf
The original version, TKP1 [4], proves properties of recursive programs and generates the~ figures. TKP2, described in this paper, generates effective proofs in natural languase furthermore. The formal system of TKP includes the propositional calculus of Gentzen's LK and additional rules to prove properties of recursive programs. Its com pleteness is shown by T. Nishimura [3].
Our processor accepts a sequent to be proved and user supplied knowledge, then it generates a tree of the proof of the given problem.
~: A sequent is called a ~.
~: If A is a sequent decomposed from B by applying a rule, the name of the rule is the indicator from B to A.
~: A ~ ~ is defined as follows. 1. A node is a proof tree.
- If m is a sequent, t1,t2, ··· ,tn are proof trees and i1,i2, ··· ,in are indicators from m to t1,t2, ··· ,tn respectively, then

·---- tn
- The only proof trees are those given by 1 and 2.
If TKP proves the given problem, the proof tree will be generated (see APPENDIX in [4]). The later passes (analysis, reduction, generation) , converts it into an English text.
3. 4NALYSIS ~ REPUCTION
In analysis, each proposition, called a P-tvoe formula, is valuated and formulas of each node are simplified, and an analyzed ~ is generated.
.DJU:: An illl:di:Qillllellt is a list of pairs of a P-type formula and the truth value. The initial state of the environment is empty.
The algorithm of analysis is as follows:
Traverse the given proof tree from its root.
When a sequent S including the P-type formula p which does not occur in the environment, split the tree T whose root is s. Analyze T recursively in the new environment which is appended the pair of p and true to the environment E. Next, analyze T in the environment which is appended the pair of p and false to E. Construct a new tree T' whose root is S simplified in E and, whose subtrees are the above two analyzed trees (Fig. 1).

When a sequent S including P-type formulas which occur in the environment is encountered, simplify S (the rules of simplification is in Fig. 3). However, if S is transformed from S1 by the user supplied knowledge or the induction hypothesis, and P-type formulas occur in S by the replacement, simplify S except the formula replaced. The new node is named S·. Next, analyze the tree whose root is S, append the indicator VAL and the analyzed tree to S' (Fig. 2).

In reduction, the analyzed tree is reduced and a final .tree is recomposed by removing redun dant nodes or subtrees from the analyzed tree.
The algorithm of reduction is as follows:
Traverse the analyzed tree.
If a node is identical to its son, remove
the node together with the branch. If a node satisfies either (I) or (II), remove the subtree connected with the node. (I) The node becomes a logical axiom · (II) r -> ~ is already proved and The node is r -> ~1,~,~ 1: P-type foraula3 are replaced by their truth value, if exist in the environment. 2: Formulas and sequents a) A&t,t&A,fvA,Avt ··> A b) A&f , f&A , \t ··> r c) Avt , tvA , \t ··> t dl r1,t,rz -> 6 =·> r1,r2 -> 6 ·> r ;.> 61,t,62 .. > r -> 61,62
Fig. 3 Rules of simplification
4. GENERATION .Qf. A .fRQQf. Im
Finally, the proof text in English is generated. A skeleton of the proof text is prepared for each type of tree. A skeleton is a rule of conversion of a tree to strings of characters. A typical skeleton is shown in Fig. 5. Traversing the reduced proof tree, a proof text is constructed by applying the skeletons.
In principle, a tree is traversed from root to leaf. A tree free from branch, however, is traversed from leaf to root (Fig. 4).
APPENDIX II is generated from the final proof tree in APPENDIX I which is the reduced proof tree of the proof shown in [4).


5. CONCLUSION
Our system is implemented in about 1000 lines of LiSP program. In actual program, analysis, reduction and generation are executed at the same time. These are implemented in about 600 lines. Our algorithm, except for the last pass, is independent of languages, then TKP2 can write in other language by changing the skeletons of the statements.
The proof written by this 'prover is very easy to read, because the English sentences are placed instead of the logical symbols, and some redundant or trivial statements are disappear ed. We believe that this system will be used as a training tool of program verification.
ACKNOWLEDGEMENT
We would like to thank Prof. T0 shio Nishimura for several very helpful comments.
APPENDIX I
F<?>(K) -> G<?>(K,1) \L-v ·--F<O>(K) -> G<?>(K,1) \L-V ·--F<N+1 >(K) -> G<?>(K,1) \R-V ·--F<N+1 >(K) -> G<N+1 >(K,1) \D-1 ·--P(K)&1 v \ P(K)&KxF<N>(K-1) -> G<N+1>(k,1) \P. t ·--1 -> G<N+1 >(K ,1) \D-2 ·--1 -> P(K)&1 v \ P(K)&G<N>(K-1,Kx1) \VAL ·--1 - > 1 P.f ·--KxF<N>(K-1) -> G<N+1 >(K,1) \HYP ·- -KxG<N>(K-1,1) -> G<N+1 >(K,1) \D-2 ·--KxG<N>(K-1,1) - > P(K)&1 v \ P(K)&G<N>(K-1,Kx1) \VAL ·--KxG<N>(K-1,1) -> G<N>(K-1 ,Kxl) \T-1 ·--G<N>(K-1,Kx1) -> G<N>(K-1,Kx1)
APPENDIX II

@inproceedings{ijcai1979p139,
title = {An Automatic Theorem Prover Generating a Proof in Natural Language},
author = {Nakanlshi, Masakazu and Nagata, Morio and Ueda, Kenji},
booktitle = {Proceedings of the Sixth International Joint Conference on
Artificial Intelligence, {IJCAI-79}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Bruce G. Buchanan},
year = {1979},
month = {8},
url = {https://ijcai.org/proceedings/1979/139},
}
TY - CPAPER TI - An Automatic Theorem Prover Generating a Proof in Natural Language AU - Nakanlshi, Masakazu AU - Nagata, Morio AU - Ueda, Kenji T2 - Proceedings of the Sixth International Joint Conference on Artificial Intelligence, IJCAI-79 PB - International Joint Conferences on Artificial Intelligence PY - 1979 UR - https://ijcai.org/proceedings/1979/139 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: