A Computational Structure for the Propositional Calculus

Abstract

Despite the long history and descriptive simplicity of the propositional calculus, practical aspects of its implementation on the computer remain an active area of study. We propose a representation of the propositional calculus which is straightforward, yet compact and sufficiently flexible to circumvent the combinatorial difficulties posed by many problems. The methodology does not involve term-rewriting, production systems, or similar, symbol-oriented approaches, but, rather, relies on a non-canonical representation in disjunctive normal form. It has been implemented in PASCAL, and efficiently solves what are described in the literature as difficult problems. The approach, which is simple and highly structured, and perhaps more procedural than many others, may be recommended for its ease of interpretation and for incorporation as a tool in larger systems.