Boolean reasoning. The logic of Boolean equations. (English) Zbl 0719.03002

Brown, Frank Markham

Boston, MA etc.: Kluwer Academic Publishers. xviii, 273 p. (1990).

Chapters 1 through 4 of this book outline the mathematical basis for Boolean reasoning. Chapter 1, included to make the book self-contained, is a brief survey of fundamental concepts such as propositions, predicates, sets, relations, functions and algebraic systems. Chapter 2 treats the classical Boole-Schröder algebra of logic via Huntington’s postulates. Several examples of Boolean algebras are discussed, and important theorems are presented; among the latter are the Stone representation theorem, Boole’s expansion theorem, and the Löwenheim- Müller verification theorem. Boolean formulas and Boolean functions are defined and the distinction between these two concepts is emphasized. Orthonormal expansions are defined and their utility is examined. The utility of “big” Boolean algebras (those comprising more than two elements) is discussed. Chapter 3 outlines Blake’s theory of canonical formulas, and the employment of such formulas in deriving and verifying consequents of Boolean equations. Several methods are presented for constructing the Blake canonical form. The Blake form is employed frequently in the remainder of the book; a number of theorems concerning this form, based on Blake’s dissertation, are given in Appendix A. Chapter 4 introduces the basic operations from which reasoning procedures may be composed. Among such operations are reduction, elimination, expansion, division, and substitution.
Chapters 5 through 7 treat two categories of Boolean reasoning: syllogistic (Chapter 5) and functional (Chapters 6 and 7). Syllogistic reasoning, a direct approach to the solution of problems in propositional logic, is based on constructing a simplified representation of the consequents of the Boolean equation \(f=0\). Functional reasoning, on the other hand, produces functional equations, i.e., statements of the form \(x=g(y,z,...)\), related to the equation \(f(x,y,z,...)=0\). Functional antecedents, solutions of \(f=0\), were investigated by Boole and have been the object of much study since. Functional consequents, on the other hand, seem to have received little attention; we discuss the theory of such consequents as well as a number of their applications.
The last two chapters present applications of Boolean reasoning in digital technology. Chapter 8 discusses the identification of a Boolean “black box” by means of an input-output experiment. Chapter 9 concerns multiple-output combinational switching circuits. Emphasis is placed on the problem of specification; the design-problem is formulated as one of solving the specification. A particular class of solutions, which we call recursive, corresponds to loop-free circuits which may employ output- signals to help in generating other output-signals.
Proofs are supplied for new results; a proof is given for an established result, however, only if it is particularly instructive. The Boolean calculations entailed in the examples - and those underlying the new results - were carried out using a set of software-tools which the author calls BORIS (Boolean Reasoning In Scheme); these tools are programmed in PC Scheme, a microcomputer-based dialect of Lisp available from Texas Instruments, Inc. BORIS has been invaluable in the exploration and testing of conjectures, building confidence in good conjectures and rudely puncturing bad ones.

MSC:

03-01	Introductory exposition (textbooks, tutorial papers, etc.) pertaining to mathematical logic and foundations
03G05	Logical aspects of Boolean algebras
06E30	Boolean functions
94C10	Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
03-04	Software, source code, etc. for problems pertaining to mathematical logic and foundations
06E05	Structure theory of Boolean algebras

Keywords:

Boolean reasoning; Boole-Schröder algebra of logic; Boolean algebras; Stone representation theorem; Boole’s expansion theorem; Löwenheim- Müller verification theorem; Boolean formulas; Boolean functions; Boolean equations; Blake canonical form; Syllogistic reasoning; Functional reasoning; combinational switching circuits; specification; loop-free circuits; software-tools