Symbolic Logic and Mechanical Theorem Proving

Symbolic Logic and Mechanical Theorem Proving

1st Edition - May 28, 1973

Write a review

  • Authors: Chin-Liang Chang, Richard Lee
  • Hardcover ISBN: 9780121703509
  • eBook ISBN: 9780080917283

Purchase options

Purchase options
DRM-free (PDF)
Sales tax will be calculated at check-out

Institutional Subscription

Free Global Shipping
No minimum order


This book contains an introduction to symbolic logic and a thorough discussion of mechanical theorem proving and its applications. The book consists of three major parts. Chapters 2 and 3 constitute an introduction to symbolic logic. Chapters 4-9 introduce several techniques in mechanical theorem proving, and Chapters 10 an 11 show how theorem proving can be applied to various areas such as question answering, problem solving, program analysis, and program synthesis.


Senior college students, and first-year graduate students studying mathematics.

Table of Contents

  • Preface


    1. Introduction

    1.1 Artificial Intelligence, Symbolic Logic, and Theorem Proving

    1.2 Mathematical Background


    2. The Propositional Logic

    2.1 Introduction

    2.2 Interpretations of Formulas in the Propositional Logic

    2.3 Validity and Inconsistency in the Propositional Logic

    2.4 Normal Forms in the Propositional Logic

    2.5 Logical Consequences

    2.6 Applications of the Propositional Logic



    3. The First-Order Logic

    3.1 Introduction

    3.2 Interpretations of Formulas in the First-Order Logic

    3.3 Prenex Normal Forms in the First-Order Logic

    3.4 Applications of the First-Order Logic



    4. Herbrand's Theorem

    4.1 Introduction

    4.2 Skolem Standard Forms

    4.3 The Herbrand Universe of a Set of Clauses

    4.4 Semantic Trees

    4.5 Herbrand's Theorem

    4.6 Implementation of Herbrand's Theorem



    5. The Resolution Principle

    5.1 Introduction

    5.2 The Resolution Principle for the Propositional Logic

    5.3 Substitution and Unification

    5.4 Unification Algorithm

    5.5 The Resolution Principle for the First-Order Logic

    5.6 Completeness of the Resolution Principle

    5.7 Examples Using the Resolution Principle

    5.8 Deletion Strategy



    6. Semantic Resolution and Lock Resolution

    6.1 Introduction

    6.2 An Informal Introduction to Semantic Resolution

    6.3 Formal Definitions and Examples of Semantic Resolution

    6.4 Completeness of Semantic Resolution

    6.5 Hyperresolution and the Set-of-Support Strategy: Special Cases of Semantic Resolution

    6.6 Semantic Resolution Using Ordered Clauses

    6.7 Implementation of Semantic Resolution

    6.8 Lock Resolution

    6.9 Completeness of Lock Resolution



    7. Linear Resolution

    7.1 Introduction

    7.2 Linear Resolution

    7.3 Input Resolution and Unit Resolution

    7.4 Linear Resolution Using Ordered Clauses and the Information of Resolved Literals

    7.5 Completeness of Linear Resolution

    7.6 Linear Deduction and Tree Searching

    7.7 Heuristics in Tree Searching

    7.8 Estimations of Evaluation Functions



    8. The Equality Relation

    8.1 Introduction

    8.2 Unsatisfiability under Special Classes of Models

    8.3 Paramodulation—An Inference Rule for Equality

    8.4 Hyperparamodulation

    8.5 Input and Unit Paramodulations

    8.6 Linear Paramodulation



    9. Some Proof Procedures Based on Herbrand's Theorem

    9.1 Introduction

    9.2 The Prawitz Procedure

    9.3 The V-Resolution Procedure

    9.4 Pseudosemantic Trees

    9.5 A Procedure for Generating Closed Pseudosemantic Trees

    9.6 A Generalization of the Splitting Rule of Davis and Putnam



    10. Program Analysis

    10.1 Introduction

    10.2 An Informal Discussion

    10.3 Formal Definitions of Programs

    10.4 Logical Formulas Describing the Execution of a Program

    10.5 Program Analysis by Resolution

    10.6 The Termination and Response of Programs

    10.7 The Set-of-Support Strategy and the Deduction of the Halting Clause

    10.8 The Correctness and Equivalence of Programs

    10.9 The Specialization of Programs



    11. Deductive Question Answering, Problem Solving, and Program Synthesis

    11.1 Introduction

    11.2 Class A Questions

    11.3 Class B Questions

    11.4 Class C Questions

    11.5 Class D Questions

    11.6 Completeness of Resolution for Deriving Answers

    11.7 The Principles of Program Synthesis

    11.8 Primitive Resolution and Algorithm A (A Program-Synthesizing Algorithm)

    11.9 The Correctness of Algorithm A

    11.10 The Application of Induction Axioms to Program Synthesis

    11.11 Algorithm A (An Improved Program-Synthesizing Algorithm)



    12. Concluding Remarks


    Appendix A

    A.1 A Computer Program Using Unit Binary Resolution

    A.2 Brief Comments on the Program

    A.3 A Listing of the Program

    A.4 Illustrations


    Appendix B



Product details

  • No. of pages: 331
  • Language: English
  • Copyright: © Academic Press 2014
  • Published: May 28, 1973
  • Imprint: Academic Press
  • Hardcover ISBN: 9780121703509
  • eBook ISBN: 9780080917283

About the Authors

Chin-Liang Chang

Affiliations and Expertise

Lockheed Missiles & Space Company, Inc., Menlo Park, CA

Richard Lee

Affiliations and Expertise

National Tsing Hua University, Hsinchu, Taiwan

Ratings and Reviews

Write a review

There are currently no reviews for "Symbolic Logic and Mechanical Theorem Proving"