Proceedings

A Definition-Driven Theorem Prover

Download BibTeX Cite

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.

  1. Bledsoe, W. W., "Splitting and Reduction Heuris- tics in Automatic Theorem Proving," Artificial Intelligence 2, 1971, pp. 55-77.
  2. Ernst, G. W., "The Utility of Independent Subgoals in Theorem Proving," Information and Control, April, 1971.
  3. Ernst, G. W., "A Definition-Driven Theorem Prover, " Report No. 1124, Computing and Informa- tion Sciences, Case Western Reserve University, 1973. •
  4. 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.
  5. Nevins, A. J., "A Human Oriented Logic for Auto- matic Theorem Proving," AI Memo No. 268, Mass. Inst. of Tech., Cambridge, Mass., 1972.
  6. Norton, L. M., "Adept: A Heuristic Program for Proving Theorems of Group Theory," Report MAC-TR- 33, Mass . Inst. of Tech., Cambridge, Mass., 1966.
  7. 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.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards