eBook
Available on Compatible NOOK devices, the free NOOK App and in My Digital Library.
Related collections and offers
Overview
A systematic treatment of Boolean reasoning, this concise, newly revised edition combines the works of early logicians with recent investigations, including previously unpublished research results.
For the benefit of readers without formal training in mathematics, the text starts with an overview of elementary mathematical concepts and outlines the theory of Boolean algebras, based on Huntington's postulate. It defines operators for elimination, division, and expansion, providing a coherent and systematic basis for subsequent discussions of syllogistic reasoning, the solution of Boolean equations, and functional deduction.
Examples and end-of-chapter problems appear throughout the book, many taken from the design for switching systems. Two concluding chapters deal with applications; one applies Boolean reasoning to diagnostic problems, and the other discusses the design of multiple-output logic-circuits.
Product Details
| ISBN-13: | 9780486164595 |
|---|---|
| Publisher: | Dover Publications |
| Publication date: | 02/10/2012 |
| Series: | Dover Books on Mathematics |
| Sold by: | Barnes & Noble |
| Format: | eBook |
| Pages: | 304 |
| File size: | 11 MB |
| Note: | This product may take a few minutes to download. |
About the Author
Read an Excerpt
BOOLEAN REASONING
The Logic of Boolean Equations
By FRANK MARKHAM BROWN
Dover Publications, Inc.
Copyright © 2003 Frank Markham BrownAll rights reserved.
ISBN: 978-0-486-16459-5
CHAPTER 1
Introduction
This book is about the logic of Boolean equations. Such equations were central in the "algebra of logic" created in 1847 by Boole and developed by others, notably Schroder, in the remainder of the nineteenth century.
Contemporary logicians have abandoned Boole's equation-based logic in favor of predicate logic, which encompasses a wider range of discourse. Nevertheless, many people, notably engineers designing digital systems, make daily use of Boolean equations. Few of them seem aware, however, that one may reason systematically using such equations. The aim of this book, accordingly, is to provide an outline—accessible to readers with a general background in engineering, physical science, or mathematics—of Boolean inference-techniques and their applications. To further that aim, numerous examples and exercises are provided to aid in teaching and self-study.
1.1 Two Logical Languages
Symbolic 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, Peirce, Poretsky, Schröder, Venn, and Whitehead, sought an improved formulation based on extensions or modifications of Boole's algebra. These efforts met with only limited success. A different approach was taken in 1879 by Frege, whose system is the ancestor of the predicate calculus. The latter language has superseded Boolean algebra as a medium for general symbolic reasoning.
The elementary units of discourse in the predicate calculus are the predicates, or atomic formulas. These are statements such as "X likes Mary," and "X >Y + 2," which, depending on the values of their variables, are either true or false. The variables in a predicate may be quantified, by the [for all] symbols ("for all") or [there exists] ("there exists"), to form statements such as [for all]X (X likes Mary) or there exists X (X likes Mary); these statements mean, respectively, "everyone likes Mary" and "someone likes Mary." Predicates may be assembled into more complex structures, called well-formed formulas, by means of logical connectives such as conjunction (AND), disjunction (OR), and negation (NOT).
1.2 Boolean Reasoning
Boolean reasoning builds on the Boole-Schröder algebra of logic, which is based on Boolean equations, rather than on the predicate calculus. Although Boolean equations are predicates—statements that are either true or false for any values of their arguments—almost none of the apparatus of predicate logic is employed in Boolean reasoning. Neither the disjunction of two Boolean equations nor the negation of a Boolean equation is a Boolean equation; thus neither of these operations is generally allowed in Boolean reasoning (see Rudeanu [153, Chapt. 10] for results concerning disjunction and negation of Boolean equations). As shown by Boole, however, the conjunction of two or more Boolean equations is a Boolean equation. The conjunction of a system of equations is therefore expressed by its equivalent single equation, rather than by a symbolic conjunction of equations. Thus the only well-formed formulas of interest in Boolean reasoning are Boolean equations.
Boole and other nineteenth-century logicians based symbolic reasoning on an equation of the 0-normal form, i.e.,
f(x1, ..., xn) = 0. (1)
derived from, and equivalent to, a given system of Boolean equations (the 1-normal form, i.e., f'(x1, ..., xn) = 1, is equivalent). A dissertation published in 1937 by A. Blake showed that the consequents of (1) are readily derived from the prime implicants of f. The concept of a prime implicant was rediscovered (and named) in 1952 by W.V.O. Quine, who investigated the problem of minimizing the complexity of Boolean formulas. Quine established the theoretical foundations of minimization-theory in a series of papers in the 1950s. The theory of prime implicants has thus arisen independently to serve two quite different ends, viz., Boolean reasoning (Blake) and formula-minimization (Quine).
The approach to Boolean reasoning outlined in this book owes much to Blake's work. Blake's formulation (outlined in Appendix A) anticipates, within the domain of Boolean algebra, the widely-applied resolution principle in predicate logic, given in 1965 by Robinson. Blake's "syllogistic result," for example, corresponds to Robinson's "resolvent."
1.3 Boolean Algebra and Switching Theory
Although Boole's algebra did not succeed in expressing, as he had intended, "those operations of the mind by which reasoning is performed" [10, p. 1], it remains in daily use to deal with the simpler mentality of switching circuits. The possibility of applying Boolean algebra to the design of switching systems was first suggested in 1910 by the distinguished physicist P. Ehrenfest, who proposed in a review of a text by Couturat that Boolean algebra be used in the design of automatic telephone exchanges. Ehrenfest did not, however, supply details as to how it might be done. Papers providing such details appeared independently between 1936 and 1938 in Japan, the United States, and the Soviet Union (it seems that only the results published in the Soviet Union, by Shestakov, were based on Ehrenfest's suggestion). The most influential of these papers was Shannon's "Symbolic Analysis of Relay and Switching Circuits", based on his M.S. thesis at the Massachusetts Institute of Technology. Shannon formulated a "calculus of switching circuits," which he showed to be analogous to the calculus of propositions. In a paper published in Japan in 1937, Nakasima identified the same switching calculus with the algebra of sets. Nakasima's paper, the earliest to apply Boolean algebra to switching theory, discussed methods of solving Boolean equations, with the aim of finding an unknown component switching-path when the composite path is known. Nakasima's work seems to have been little noticed outside Japan. In the U.S. and Europe, a number of papers appeared in the 1950s describing applications of Boolean equation-solving to the design of switching systems.
Motivated by problems arising in the design of switching circuits, A. Svoboda proposed construction of a "Boolean Analyzer," a hardware-adjunct to a general-purpose computer, specialized to solve Boolean equations. The applications of such a unit, and of APL programs for solving Boolean equations, are described in Svoboda and White.
Klir and Marin have stated that "The most powerful tool of the modern methodology of switching circuits seems to be the Boolean equations. Their importance for switching theory reminds one of the application of differential equations in electric circuit theory." There remains a curious difference, however, between the way differential equations and Boolean equations are typically applied: Boolean equations are rarely solved. They are manipulated in form but are seldom employed for systematic reasoning. Contemporary research on Boolean methods in switching tends instead to emphasize formula-minimization. Many writers on applications of Boolean methods believe in fact that the only useful thing to do with Boolean formulas is to simplify them. A widely-used text [70, p. 60] announces that "Almost every problem in Boolean algebra will be found to be some variation of the following statement: 'Given one of the 22n functions of n variables, determine from the large number of equivalent expressions of this function one which satisfies some criteria for simplicity.'" Boole would doubtless deem that meager employment for the algebra he designed as an instrument for reasoning.
Although Boolean reasoning procedures should for practical reasons avoid unnecessarily complex formulas, minimization is a topic essentially distinct from reasoning. Minimization is therefore not emphasized in this book, notwithstanding its importance both theoretically and in practice. See Brayton, et al., for a treatment of minimization and its applications in the design of VLSI (Very Large-Scale Integration) circuits.
1.4 An Approach to Boolean Problem-Solving
The central idea in Boolean reasoning, first described by Boole, is to reduce a given system of logical equations to a single equivalent equation of standardized form (e.g., f = 0), and then to carry out the desired reasoning on that equation. Because of this preliminary abstraction, the processes of reasoning are independent of the form of the original equations.
The primary tactic employed by Boole and later nineteenth-century logicians was to solve f (x, y, ...) = 0 for certain of its arguments in terms of others. A solution of an equation is a particular kind of antecedent, however, and not necessarily a consequent, of the equation. An important advance was made in 1937 by Blake, who showed that the consequents of f = 0 are represented economically in the disjunction of the prime implicants of f. We call this disjunction the Blake canonical form for f and denote it by BCF(f).
The task of solving a problem based on a collection of Boolean equations may thus be carried out in three major steps:
1. Reduction. Condense the equations into a single Boolean equation of the form f = 0.
2. Development. Construct the Blake canonical form for f, i.e., generate the prime implicants of f.
3. Reasoning. Apply a sequence of reasoning-operations, beginning with the Blake form, to solve the problem.
Steps 1 and 2 are independent of the problem to be solved and are readily automated. The sequence of operations to be applied in Step 3, on the other hand, is dependent upon the problem. To employ Boolean reasoning, therefore, the principal task is to select an appropriate sequence of operations to apply to the formula BCF(f). The operational (i.e., functional) basis of Boolean reasoning differentiates it from from the predicate calculus, whose basis is relational. Other differences between the two languages are discussed below.
1.5 Boolean Reasoning vs. Predicate Logic
The need to incorporate systematic reasoning into the design of switching systems has attracted the attention of engineers to the theorem-proving methods of the predicate calculus. Design based on these methods is summarized by Kabat and Wojcik as follows: "The basic philosophy of the design approach using theorem proving is to represent the elements of the design process as a set of axioms in a formal system (a theory), state the problem of realizability of the target function as a theorem, and prove it in the context of the theory. Once the theorem is proved, an automatic procedure for the recovery of the logic circuit is to be executed to complete the design."
Boolean reasoning differs from the theorem-proving methodology of predicate logic in a number of important ways. Predicates (propositional functions) and propositions are two-valued. Boolean functions, on the other hand, take on values over an underlying set, the carrier of the associated Boolean algebra; the number of elements in the carrier may be 2 or any higher power of 2. The following properties—valid in propositional logic—do not hold in other than two-valued Boolean algebras:
F + G = 1 [??] F = 1 or G = 1
F ≠ [??] F = 0.
Applying propositional calculation-rules to Boolean problems can therefore lead to incorrect results. The denial of a biconditional in propositional logic, for example, can be expressed as a biconditional; thus [logical not](a<->b) is equivalent to a<-> [logical not]b. The denial of a Boolean equation, however, cannot in general be expressed as a Boolean equation; denying the Boolean equation a = b is not the same as asserting the equation a = b'.
The principal problem-solving technique in predicate logic is theorem-proving via refutation. Sometimes called reductio ad absurdum, this technique entails denying the theorem to be proved. As noted above, however, the denial of a Boolean equation is not a Boolean equation; thus refutation-based reasoning is not possible in Boolean algebras having other than two values.
Problem-solving in predicate logic entails assigning values to variables over some domain. Any set, e.g., {5, John, [??], cat, *}, may be the domain for a problem in predicate logic. The domain in a Boolean problem, however, is an ordered structure—the carrier of a Boolean algebra. Consequently, the information produced by Boolean reasoning is typically expressed by intervals (cf. Section 3.4.1).
1.6 Outline
Chapters 2 through 5 of this book outline the mathematical basis for Boolean reasoning. Chapter 2, 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 3 treats the classical Boole-Schroder 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 4 outlines Blake's theory of canonical formulas as well as methods 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 5 introduces the basic operations from which reasoning procedures may be composed. Among such operations are reduction, elimination, expansion, division, and substitution.
Chapters 6 through 8 treat two categories of Boolean reasoning: syllogistic (Chapter 6) and functional (Chapters 7 and 8). Syllogistic reasoning, a direct approach to the solution of Boolean or propositional, problems, 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; see Rudeanu for an authoritative survey and an extensive bibliography. 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 9 discusses the identification of a Boolean "black box" by means of an input-output experiment. Chapter 10 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 Scheme, a dialect of Lisp. BORIS has been invaluable in the exploration and testing of conjectures, building confidence in good conjectures and rudely puncturing bad ones.
CHAPTER 2Fundamental Concepts
This chapter surveys basic mathematical ideas and language needed in the remainder of the book. (Readers familiar with the concepts and terminology of modern algebra may wish to proceed directly to the next chapter.) The discussion is informal and only those topics directly applicable to Boolean reasoning are considered. The sets discussed in this chapter are restricted to be finite, i.e., to comprise only a finite number of elements. A text such as that by Halmos should be consulted for a general treatment of the theory of sets.
2.1 Formulas
If we begin typing at a keyboard, we will produce a formula or expression. If we strike only the parenthesis-keys, some of the formulas we might type are the following:
() (2.1)
)() (2.2)
(()(())) (2.3)
((((())) (2.4)
Formulas may be discussed in terms of two attributes. The first is syntax, which is concerned with the way the symbols in a formula are arranged; the second is semantics, which is concerned with what the symbols mean. An important question of syntax is whether a formula in a given class is well-formed, i.e., grammatical or legal according to the rules governing that class. We will discuss the syntax of well-formed parenthesis-strings later in this chapter; our experience with parentheses should tell us, however, that formulas (2.1) and (2.3) are well-formed, whereas (2.2) and (2.4) are not.
(Continues...)
Excerpted from BOOLEAN REASONING by FRANK MARKHAM BROWN. Copyright © 2003 Frank Markham Brown. Excerpted by permission of Dover Publications, Inc..
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.
Table of Contents
Contents
Dedication,Preface to the Dover Edition,
1 Introduction,
2 Fundamental Concepts,
3 Boolean Algebras,
4 The Blake Canonical Form,
5 Boolean Analysis,
6 Syllogistic Reasoning,
7 Solution of Boolean Equations,
8 Functional Deduction,
9 Boolean Identification,
10 Combinational Circuits: Specification & Optimization,
A Syllogistic Formulas,
Bibliography,
Index,