Equational Logic

Publisher Website
Google Scholar
Abstract
A combinational circuit realizing the switching function f(x) may be regarded as a solution verifier for the Boolean equation f(x) = 1. (*) The output of the circuit is 1, that is, if and only if the input-vector x is a solution for (*). We use the term "equational logic" to denote an approach to circuit synthesis based on (*) rather than on the function f(x). The central problem of equational logic is to find a system of equations gi(x) = hi(x) (i = 1,2,...,k), of the simplest possible form, that has the same solutions as (*). Given such a k-equation system, f(x) may be realized as the output of a k-wide digital comparator whose inputs are the 2k g's and h's constituting the system. The problem of finding a simple system of equations equivalent to a given equation was investigated more than a century ago by Willian Stanley Jevons, who called it "the inverse problem of logic." It was thought by Jevons and other 19th century logicians that the inverse problem is "always tentative," i.e., that it does not admit of algorithmic solution. It is shown in this paper, however, that the inverse problem may be solved as a covering problem by use of the "table of consequences" of Poretsky. As presently formulated, this approach is limited in practical utility by the large size of the tables involved. It appears that a practical solution technique requires a reformulation of the inverse problem.

This publication has 0 references indexed in Scilit: