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.2.1 The Algebra of Classes (Subsets of a Set).- 2.2.2 The Algebra of Propositional Functions.- 2.2.3 Arithmetic Boolean Algebras.- 2.2.4 The Two-Element Boolean Algebra.- 2.2.5 Summary of Examples.- 2.3 The Stone Representation Theorem.- 2.4 The Inclusion-Relation.- 2.4.1 Intervals.- 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.9.1 Truth-tables.- 2.9.2 Maps.- 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.13.1 Free Boolean Algebras.- 2.14 Orthonormal Expansions.- 2.14.1 Löwenheim’s 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.5.1 Quine’s method.- 3.5.2 Successive extraction.- 3.6 Multiplication.- 3.6.1 Recursive multiplication.- 3.6.2 Combining multiplication and iterated consensus.- 3.6.3 Unwanted syllogistic formulas.- 4 Boolean Analysis.- 4.1 Review of Elementary Properties.- 4.2 Boolean Systems.- 4.2.1 Antecedent, Consequent, and Equivalent Systems.- 4.2.2 Solutions.- 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.- 4.11.1 Testing for Tautology.- 4.11.2 The Sum-to-One Theorem.- 4.11.3 Nearly-Minimal SOP Formulas.- 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.5.1 Producing Consequents.- 5.5.2 Verifying Consequents.- 5.5.3 Comparison of Clauses.- 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 and Consistency.- 6.2 General Solutions.- 6.3 Subsumptive General Solutions.- 6.3.1 Successive Elimination.- 6.3.2 Deriving Eliminants from Maps.- 6.3.3 Recurrent Covers and Subsumptive Solutions.- 6.3.4 Simplified Subsumptive Solutions.- 6.3.5 Simplification via Marquand Diagrams.- 6.4 Parametric General Solutions.- 6.4.1 Successive Elimination.- 6.4.2 Parametric Solutions based on Recurrent Covers.- 6.4.3 Löwenheim’s Formula.- 7 Functional Deduction.- 7.1 Functionally Deducible Arguments.- 7.2 Eliminable and Determining Subsets.- 7.2.1 u-Eliminable Subsets.- 7.2.2 u-Determining Subsets.- 7.2.3 Calculation of Minimal u-Determining Subsets.- 8 Boolean Identification.- 8.1 Parametric and Diagnostic Models.- 8.1.1 Parametric Models.- 8.1.2 The Diagnostic Axiom.- 8.1.3 Diagnostic Equations and Functions.- 8.1.4 Augmentation.- 8.2 Adaptive Identification.- 8.2.1 Initial and Terminal Specifications.- 8.2.2 Updating the Model.- 8.2.3 Effective Inputs.- 8.2.4 Test-Procedure.- 9 Recursive Realizations of Combinational Circuits.- 9.1 The Design-Process.- 9.2 Specifications.- 9.2.1 Specification-Formats.- 9.2.2 Consistent Specifications.- 9.3 Tabular Specifications.- 9.4 Strongly Combinational Solutions.- 9.5 Least-Cost Recursive Solutions.- 9.6 Constructing Recursive Solutions.- 9.6.1 The Procedure.- 9.6.2 An Implementation using BORIS.- A Syllogistic Formulas.- A.1 Absorptive Formulas.- A.2 Syllogistic Formulas.- A.3 Prime Implicants.- A.4 The Blake Canonical Form.