Automation of Reasoning: 1: Classical Papers on Computational Logic 1957–1966

Description

"Kind of crude, but it works, boy, it works!" Alan Newell to Herb Simon, Christmas 1955 In 1954 a computer program produced what appears to be the first computer generated mathematical proof: Written by M. Davis at the Institute of Advanced Studies, USA, it proved a number theoretic theorem in Presburger Arithmetic. Christmas 1955 heralded a computer program which generated the first proofs of some propositions of Principia Mathematica, developed by A. Newell, J. Shaw, and H. Simon at RAND Corporation, USA. In Sweden, H. Prawitz, D. Prawitz, and N. Voghera produced the first general program for the full first order predicate calculus to prove mathematical theorems; their computer proofs were obtained around 1957 and 1958, about the same time that H. Gelernter finished a computer program to prove simple high school geometry theorems. Since the field of computational logic (or automated theorem proving) is emerging from the ivory tower of academic research into real world applications, asserting also a definite place in many university curricula, we feel the time has come to examine and evaluate its history. The article by Martin Davis in the first of this series of volumes traces the most influential ideas back to the 'prehistory' of early logical thought showing how these ideas influenced the underlying concepts of most early automatic theorem proving programs. The article by Larry Wos and Larry Henschen in the second volume covers the period of 1965 to 1970, when most of the early theorem proving systems emerged; the article by S. Maslov provides an overview of Russian and Eastern European work during this period. This series of volumes, the first covering 1957 to 1966 and the second 1967 to 1970, contains those papers, which have shaped and influenced the field of computational logic and makes available the classical work, which in many cases is difficult to obtain or had not previously appeared in English. However, the main purpose of this series is to evaluate the ideas of the time and to select those papers, which can now be regarded as classics after more than a decade of intensive research. Editors Preface •••.•.••.••••••••••••.•..•••••••••..•.••••........ IX M. Davis: The Prehistory and Early History of Automated Deduction •.•••••••••••••••.•••••••••••••••••••••••••••..•.•.•.•• 1 s. Yu. Maslov, .G.E. Mints and V.P. Orevkov: Mechanical Proof Search and the Theory of Logical Deduction in the USSR ...••..•.. 29 1957 M. Davis: A Computer Program for Presburger's Algorithm •.••....••.. 41 * A. Newell, J.C. Shaw, H. A. Simon: Empirical Explorations with the Logic Theory Machine: A Case Study in Heuristics ••••••. 49 A. Robinson: Proving a Theorem (as Done by Man, Logician or Machine) •.••.•••••••..•.••.••••••••.••................••..••• 7 4 1958 E.W. Beth: On Machines Which Prove Theorems ..••............•....... 79 1959 B. Dunham, R. Fridshal and G.L. Sward: A non-heuristic Program for Proving Elementary Logical Theorems •.•••............ 93 * H. Gelernter: Realization of a Geometry-Theorem Proving Machine •.•••••••••••......•••••.••••..••....•.•...•..•.•••.....• ·99 1960 * M. Davis, H. Putnam: A Computing Procedure for Quantification Theory •••.•.•••••••••.•••....•.•.....•...•....... 1 25 H. Gelernter, J.R. Hansen, b.w. Loveland: Empirical Explorations of the Geometry-Theorem Proving Machine .•..•......• 140 P.C. Gilmore: A Proof Method for Quantification Theory: Its Justification and Realization •.•••.••••.•••••.•..•••.•..•..• 151 * D. Prawi tz: An Improved Proof Procedure .•.•....••.•••.......•.....• 1 6 2 D. Prawitz, H. Prawitz and N. Voghera: A Mechanical Proof Procedure and its Realization in an Electronic Computer ......... 202 H. Wang: Proving Theorems by Pattern Recognition - I •.............• 229 e. Wang: Toward Mechanical Mathematics ....••...................... 244 1962 M. Davia, G. Logemann and D. Loveland: A Machine Program for Theorem Proving •.••.••..••••..••••••••••••••••...•........•. 267 B. Dunham, J.H. North: Theorem Testing by Ccmputer ••.•..•...•.•.... 271 B. Dunham, R. Fridshal, J.H. North: Exploratory Mathematica by Machine ••••..••••••••••••••.•••......••••.••.•••• 276 ff. Gelernter: Machine-Generated Problem-Solving Graphs ...••.••••••• 288 1963 * M. Davis: Eliminating the Irrelevant frcm Mechanical Proofs ........ 315 J. Friedman: A Semi-Decision Procedure for che Functional Calculus .••..••••••••••••.•••••••.•.•••••••••••••••..•...•...••. 331 J. Friedman: A Computer Program for a Solvable Case of the Decision Problem .•••.•••••••••.•••••••••.•••••••••••••.•.••. 355 S. Kanger: A Simplified Proof Method for Elementary Logic .••••••••. 364 J.A. Robinson: Theorem-Proving on the Canputer •..••••••..•..•.••.•• 372 1964 * L.T;W'.ls, t'.F.Carson and G.A. Robinson: The Unit Preference Strategy in Theorem Proving ••.........•.•.•••••...••••.•...••••• 387 1965 * J.A. Robinson: A Machine Oriented Logic Baaed on the Resolution Principle •••••.••.•.••...•...•••.•••.......•......... 397 * J.A. Robinson: Automatic Deduction with Hyper-Resolution ...•.••.••. 416 N.A. Shanin, G.V. Davydov, S. Yu. Maalov, G.E. Minta, V.P. Orevltov and A.O. Sliaenko: An Algorithm for a Machine Search of a Natural Logical Deduction in a Propositional Calculus ••••••.••.•••••••.••.•••••..•••.••...•..•• 424 * L.T.W'.ls, G.A. Robinson and D.F. Carson: Efficiency and Completeness of the Set of Support Strategy in Theorem Proving •••.••..•.•......••.••••••.......••..•••••.•..••. 484 1966 B. Meltzer: Theorem-Proving for Computers: Sane Results on Resolution and Renaming ..••••••••..•••••••••••...........•... 493 Bibliography on C0111putational Logic •••.••......•....•••.•........••• 497