Boyer / Moore / Rheinboldt A Computational Logic Handbook

Formerly Notes and Reports in Computer Science and Applied Mathematics
1. Auflage 2014
ISBN: 978-1-4832-7778-3
Verlag: Elsevier Science & Techn.
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 426 Seiten, Web PDF

Perspectives in Computing: A Computational Logic Handbook contains a precise description of the logic and a detailed reference guide to the associated mechanical theorem proving system, including a primer for the logic as a functional programming language, an introduction to proofs in the logic, and a primer for the mechanical theorem. The publication first offers information on a primer for the logic, formalization within the logic, and a precise description of the logic. Discussions focus on induction and recursion, quantification, explicit value terms, dealing with features and omissions, elementary mathematical relationships, Boolean operators, and conventional data structures. The text then takes a look at proving theorems in the logic, mechanized proofs in the logic, and an introduction to the system. The text examines the processes involved in using the theorem prover, four classes of rules generated from lemmas, and aborting or interrupting commands. Topics include executable counterparts, toggle, elimination of irrelevancy, heuristic use of equalities, representation of formulas, type sets, and the crucial check points in a proof attempt. The publication is a vital reference for researchers interested in computational logic.

Autoren/Hrsg.

Boyer, Robert S.

Moore, J Strother

Rheinboldt, Werner

Siewiorek, Daniel

Inhaltsverzeichnis

1;Front Cover;1
2;A Computational Logic Handbook;4
3;Copyright Page;5
4;Table of Contents;6
5;Preface;12
6;Part I:
The Logic;18
6.1;Chapter 1. Introduction;20
6.1.1;1.1. A Summary of the Logic and Theorem Prover;21
6.1.2;1.2. Some Interesting Applications;22
6.1.3;1.3. The Organization of this Handbook;26
6.2;Chapter 2. A Primer for the Logic;32
6.2.1;2.1. Syntax;33
6.2.2;2.2. Boolean Operators;34
6.2.3;2.3. Data Types;35
6.2.4;2.4. Extending the Syntax;43
6.2.5;2.5. Conventional Data Structures;45
6.2.6;2.6. Defining Functions;49
6.2.7;2.7. Recursive Functions on Conventional Data Structures;54
6.2.8;2.8. Ordinals;58
6.2.9;2.9. Useful Functions;60
6.2.10;2.10. The Interpreter;62
6.2.11;2.11. The General Purpose Quantifier;70
6.3;Chapter 3. Formalization Within the Logic;74
6.3.1;3.1. Elementary Programming Examples;77
6.3.2;3.2. Elementary Mathematical Relationships;82
6.3.3;3.3. Dealing with Omissions;85
6.3.4;3.4. Dealing with Features;93
6.3.5;3.5. Nondeterminism;103
6.3.6;3.6. Embedded Formal Systems;105
6.4;Chapter 4. A Precise Description of the Logic;110
6.4.1;4.1. Apologia;110
6.4.2;4.2. Outline of the Presentation;111
6.4.3;4.3. Formal Syntax;112
6.4.4;4.4. Embedded Propositional Calculus and Equality;118
6.4.5;4.5. The Shell Principle and the Primitive Data Types;122
6.4.6;4.6. Explicit Value Terms;128
6.4.7;4.7. The Extended Syntax—Abbreviations I;129
6.4.8;4.8. Ordinals;141
6.4.9;4.9. Useful Function Definitions;142
6.4.10;4.10. The Formal Metatheory;145
6.4.11;4.11. Quantification;153
6.4.12;4.12. SUBRPs and non-SUBRPs;155
6.4.13;4.13. Induction and Recursion;156
6.5;Chapter 5. Proving Theorems in the Logic;160
6.5.1;5.1. Propositional Calculus with Equality;161
6.5.2;5.2. Theorems about IF and Propositional Functions;164
6.5.3;5.3. Simple Theorems about NIL, CONS, and APPEND;166
6.5.4;5.4. The Associativity of APPEND;170
6.5.5;5.5. Simple Arithmetic;174
6.5.6;5.6. Structural Induction;179
7;Part II: Using the System;182
7.1;Chapter 6. Mechanized Proofs in the Logic;184
7.1.1;6.1. The Organization of Our Theorem Prover;184
7.1.2;6.2. An Example Proof—Associativity of TIMES;187
7.1.3;6.3. An Explanation of the Proof;190
7.2;Chapter 7. An Introduction to the System;194
7.2.1;7.1. The Data Base of Rules;194
7.2.2;7.2. Logical Events;196
7.2.3;7.3. A Summary of the Commands;197
7.2.4;7.4. Errors;199
7.2.5;7.5. Aborting a Command;199
7.2.6;7.6. Syntax and the User Interface;199
7.2.7;7.7. Confusing Lisp and the Logic;201
7.3;Chapter 8. A Sample Session with the Theorem Prover;204
7.4;Chapter 9. How to Use the Theorem Prover;224
7.4.1;9.1. REVERSE-REVERSE Revisited—Cooperatively;225
7.4.2;9.2. Using Lisp and a Text Editor as the Interface;230
7.4.3;9.3. The Crucial Check Points in a Proof Attempt;232
7.5;Chapter 10. How the Theorem Prover Works;236
7.5.1;10.1. The Representation of Formulas;237
7.5.2;10.2. Type Sets;238
7.5.3;10.3. Simplification;239
7.5.4;10.4. Elimination of Destructors;242
7.5.5;10.5. Heuristic Use of Equalities;243
7.5.6;10.6. Generalization;244
7.5.7;10.7. Elimination of Irrelevancy;245
7.5.8;10.8. Induction;245
7.6;Chapter 11. The Four Classes of Rules Generated from Lemmas;248
7.6.1;11.1. REWRITE;250
7.6.2;11.2. META;261
7.6.3;11.3. ELIM;264
7.6.4;11.4. GENERALIZE;265
7.7;Chapter 12. Reference Guide;268
7.7.1;12.1. Aborting or Interrupting Commands;268
7.7.2;12.2. ACCUMULATED-PERSISTENCE;270
7.7.3;12.3. ADD-AXIOM;271
7.7.4;12.4. ADD-SHELL;271
7.7.5;12.5. BOOT-STRAP;272
7.7.6;12.6. BREAK-LEMMA;274
7.7.7;12.7. BREAK-REWRITE;281
7.7.8;12.8. CH;283
7.7.9;12.9. CHRONOLOGY;285
7.7.10;12.10. COMPILE-UNCOMPILED-DEFNS;285
7.7.11;12.11. DATA-BASE;286
7.7.12;12.12. DCL;290
7.7.13;12.13. DEFN;291
7.7.14;12.14. DISABLE;293
7.7.15;12.15. DO-EVENTS;295
7.7.16;12.16. ELIM;296
7.7.17;12.17. ENABLE;297
7.7.18;12.18. Errors;297
7.7.19;12.19. Event Commands;299
7.7.20;12.20. EVENTS-SINCE;299
7.7.21;12.21. Executable Counterparts;299
7.7.22;12.22. Explicit Values;301
7.7.23;12.23. Extensions;302
7.7.24;12.24. FAILED-EVENTS;302
7.7.25;12.25. File Names;302
7.7.26;12.26. GENERALIZE;306
7.7.27;12.27. MAINTAIN-REWRITE-PATH;306
7.7.28;12.28. MAKE-LIB;307
7.7.29;12.29. META;307
7.7.30;12.30. Names—Events, Functions, and Variables;307
7.7.31;12.31. NOTE-LIB;308
7.7.32;12.32. NQTHM Mode;309
7.7.33;12.33. PPE;309
7.7.34;12.34. PROVE;309
7.7.35;12.35. PROVEALL;310
7.7.36;12.36. PROVE-LEMMA;311
7.7.37;12.37. R-LOOP;317
7.7.38;12.38. REDUCE-TERM-CLOCK;323
7.7.39;12.39. REWRITE;324
7.7.40;12.40. Root Names;324
7.7.41;12.41. Rule Classes;324
7.7.42;12.42. Time Triple;325
7.7.43;12.43. THM Mode;325
7.7.44;12.44. TOGGLE;325
7.7.45;12.45. TOGGLE-DEFINED-FUNCTIONS;326
7.7.46;12.46. TRANSLATE;326
7.7.47;12.47. UBT;327
7.7.48;12.48. UNBREAK-LEMMA;327
7.7.49;12.49. UNDO-BACK-THROUGH;328
7.7.50;12.50. UNDO-NAME;328
7.8;Chapter 13. Hints on Using the Theorem Prover;332
7.8.1;13.1. How to Write "Good" Definitions;332
7.8.2;13.2. How To Use REWRITE Rules;334
7.8.3;13.3. How to Use ELIM Rules;350
7.9;Chapter 14. Installation Guide;352
7.9.1;14.1. The Source Files;352
7.9.2;14.2. Compiling;353
7.9.3;14.3. Loading;355
7.9.4;14.4. Executable Images;356
7.9.5;14.5. Example Installation;357
7.9.6;14.6. Installation Problems;360
7.9.7;14.7. Shakedown;363
7.9.8;14.8. Packages;364
7.9.9;14.9. Example Event Files;365
8;Appendix I:
A Parser for the Syntax;368
8.1;I.1. Some Preliminary Conventions;370
8.2;I.2. The Formal Definition of READ;372
8.3;I.3. The Formal Definition of TRANSLATE;382
8.4;I.4. EXSYN;398
9;Appendix II: The Primitive Shell Axioms;400
9.1;II.1. The Natural Numbers;401
9.2;II.2. The Ordered Pairs;403
9.3;II.3. The Literal Atoms;404
9.4;II.4. The Negative Integers;406
10;Appendix III: On the Difficulty of Proofs;408
11;References;414
12;Index;418
13;Perspectives in Computing;426