Boolean Reasoning

This book is about the logic of Boolean equations. Such equations were central in the "algebra of logic" created in 1847 by Boole [12, 13] and devel­ oped by others, notably Schroder [178], in the remainder of the nineteenth century. Boolean equations are also the language by which digital circuits are described today. Logicians in the twentieth century have abandoned Boole's equation­ based logic in favor of the more powerful predicate calculus. As a result, digital engineers-and others who use Boole's language routinely-remain largely unaware of its utility as a medium for reasoning. The aim of this book, accordingly, is to is to present a systematic outline of the logic of Boolean equations, in the hope that Boole's methods may prove useful in solving present-day problems. Two Logical Languages Logic seeks to reduce reasoning to calculation. Two main languages have been developed to achieve that object: Boole's "algebra of logic" and the predicate calculus. Boole's approach was to represent classes (e. g. , happy creatures, things productive of pleasure) by symbols and to represent logical statements as equations to be solved. His formulation proved inadequate, however, to represent ordinary discourse. A number of nineteenth-century logicians, including Jevons [94], Poretsky [159], Schroder [178], Venn [210], and Whitehead [212, 213], sought an improved formulation based on ex­ tensions or modifications of Boole's algebra. These efforts met with only limited success.

1 Fundamental Concepts. - 1. 1 Formulas. - 1. 2 Propositions and Predicates. - 1. 3 Sets. - 1. 4 Operations on Sets. - 1. 5 Partitions. - 1. 6 Relations. - 1. 7 Functions. - 1. 8 Operations and Algebraic Systems. - 2 Boolean Algebras. - 2. 1 Postulates for a Boolean Algebra. - 2. 2 Examples of Boolean Algebras. - 2. 3 The Stone Representation Theorem. - 2. 4 The Inclusion-Relation. - 2. 5 Some Useful Properties. - 2. 6 n-Variable Boolean Formulas. - 2. 7 n-Variable Boolean Functions. - 2. 8 Boole s Expansion Theorem. - 2. 9 The Minterm Canonical Form. - 2. 10 The Löwenheim-Müller Verification Theorem. - 2. 11 Switching Functions. - 2. 12 Incompletely-Specified Boolean Functions. - 2. 13 Boolean Algebras of Boolean Functions. - 2. 14 Orthonormal Expansions. - 2. 15 Boolean Quotient. - 2. 16 The Boolean Derivative. - 2. 17 Recursive Definition of Boolean Functions. - 2. 18 What Good are Big Boolean Algebras? . - 3 The Blake Canonical Form. - 3. 1 Definitions and Terminology. - 3. 2 Syllogistic & Blake Canonical Formulas. - 3. 3 Generation of BCF(f). - 3. 4 Exhaustion of Implicants. - 3. 5 Iterated Consensus. - 3. 6 Multiplication. - 4 Boolean Analysis. - 4. 1 Review of Elementary Properties. - 4. 2 Boolean Systems. - 4. 3 Reduction. - 4. 4 The Extended Verification Theorem. - 4. 5 Poretsky s Law of Forms. - 4. 6 Boolean Constraints. - 4. 7 Elimination. - 4. 8 Eliminants. - 4. 9 Rudundant Variables. - 4. 10 Substitution. - 4. 11 The Tautology Problem. - 5 Syllogistic Reasoning. - 5. 1 The Principle of Assertion. - 5. 2 Deduction by Consensus. - 5. 3 Syllogistic Formulas. - 5. 4 Clausal Form. - 5. 5 Producing and Verifying Consequents. - 5. 6 Class-Logic. - 5. 7 Selective Deduction. - 5. 8 Functional Relations. - 5. 9 Dependent Sets of Functions. - 5. 10 Sum-to-One Subsets. - 5. 11 Irredundant Formulas. - 6 Solution of Boolean Equations. - 6. 1 Particular Solutions andConsistency. - 6. 2 General Solutions. - 6. 3 Subsumptive General Solutions. - 6. 4 Parametric General Solutions. - 7 Functional Deduction. - 7. 1 Functionally Deducible Arguments. - 7. 2 Eliminable and Determining Subsets. - 8 Boolean Identification. - 8. 1 Parametric and Diagnostic Models. - 8. 2 Adaptive Identification. - 9 Recursive Realizations of Combinational Circuits. - 9. 1 The Design-Process. - 9. 2 Specifications. - 9. 3 Tabular Specifications. - 9. 4 Strongly Combinational Solutions. - 9. 5 Least-Cost Recursive Solutions. - 9. 6 Constructing Recursive Solutions. - A Syllogistic Formulas. - A. 1 Absorptive Formulas. - A. 2 Syllogistic Formulas. - A. 3 Prime Implicants. - A. 4 The Blake Canonical Form.