Boolean Functions

Modern systems engineering (e. g. switching circuits design) and operations research (e. g. reliability systems theory) use Boolean functions with increasing regularity. For practitioners and students in these fields books written for mathe­ maticians are in several respects not the best source of easy to use information, and standard books, such as, on switching circuits theory and reliability theory, are mostly somewhat narrow as far as Boolean analysis is concerned. Further­ more, in books on switching circuits theory the relevant stochastic theory is not covered. Aspects of the probabilistic theory of Boolean functions are treated in some works on reliability theory, but the results deserve a much broader interpre­ tation. Just as the applied theory (e. g. of the Laplace transform) is useful in control theory, renewal theory, queueing theory, etc. , the applied theory of Boolean functions (of indicator variables) can be useful in reliability theory, switching circuits theory, digital diagnostics and communications theory. This book is aimed at providing a sufficiently deep understanding of useful results both in practical work and in applied research. Boolean variables are restricted here to indicator or O/l variables, i. e. variables whose values, namely 0 and 1, are not free for a wide range of interpretations, e. g. in digital electronics 0 for L ==low voltage and 1 for H == high voltage.

1 Notation and Glossary of Fundamental Terms and Symbols.- 2 Fundamental Concepts.- 2.1 Boolean Indicator Variables and All Their Functions of One and Two Variables.- 2.1.1 The Functions of One Variable.- 2.1.2 The Functions of Two Variables.- 2.2 Axioms and Elementary Laws of Boolean Algebra.- 2.2.1 Axioms.- 2.2.2 Elementary Laws.- 2.2.3 Complete Systems of Operators.- 2.3 Polynomials, Vectors, and Matrices with Boolean Elements.- 2.3.1 Polynomials with Boolean Coefficients.- 2.3.2 Boolean Vector/Matrix Calculus.- Exercises.- 3 Diagrams for Boolean Analysis.- 3.1 Standard Graphical Representation of Boolean Functions.- 3.2 Binary Decision Diagrams.- 3.3 Karnaugh Maps.- 3.4 Switching Network Graphs (Logic Diagrams) and Syntax Diagrams.- 3.5 Venn Diagrams.- 3.6 State Transition Graphs.- 3.7 Communications Graphs.- 3.8 Reliability Block Diagrams.- 3.9 Flowcharts.- 3.10 Petri Nets.- Exercises.- 4 Representations (Forms) and Types of Boolean Functions.- 4.1 Negation (Complement).- 4.2 Special Terms.- 4.3 Normal Forms and Canonical Normal Forms.- 4.3.1 Elementary Theory.- 4.3.2 Description of Connectivity Properties of Graphs.- 4.4 Disjunctive Normal Forms of Disjoint Terms.- 4.4.1 Fundamentals.- 4.4.2 A set-addition algorithm.- 4.4.3 The Shannon Decomposition Algorithm.- 4.4.4 A Binary Decision Tree Algorithm.- 4.4.5 Comparison of DDNF Algorithms.- 4.5 Boolean Functions with Special Properties.- 4.6 Recursive Definition of Boolean Functions.- 4.7 Hazards.- Exercises.- 5 Minimal Disjunctive Normal Forms.- 5.1 General Considerations.- 5.2 Finding All Prime Implicants of a Boolean Function.- 5.2.1 The Quine-McCluskey Procedure.- 5.2.2 The Concensus Procedure of Quine.- 5.2.3 The Double Negation Procedure of Nelson.- 5.3 Minimization.- 5.3.1 Optimal Choice of Subsets.- 5.3.2 Shortest Disjunctive Normal Forms.- 5.3.3 Incompletely Specified Boolean Functions.- Exercises.- 6 Boolean Difference Calculus.- 6.1 Exclusiv-Disjunction Form Without Negated Variables.- 6.2 Concepts of Boolean Differences.- 6.3 Basic Rules of Boolean Difference Calculus.- 6.4 Diagnosing Permanent Faults in Switching Networks.- Exercises.- 7 Boolean Functions Without Boolean Operators.- 7.1 Fundamental Concepts and Consequences.- 7.2 Transformation of Boolean Functions of Indicator Variables to Multilinear Form.- 7.3 Coherence Revisited.- Exercises.- 8 Stochastic Theory of Boolean Functions.- 8.1 Probability of a Binary State.- 8.2 Probability of the Value 1 of a Boolean Function.- 8.2.1 Expected Value of a Boolean Function.- 8.2.2 Probabilities of Arguments (States) in the Homogeneous Markov Model.- 8.3 Approximate Probability of the Value 1.- 8.3.1 Principle of Inclusion-Exclusion.- 8.3.2 Approximation with a Given Error Bound.- 8.4 Moments of Boolean Functions.- Exercises.- 9 Stochastic Theory of Boolean Indicator Processes.- 9.1 Mean Duration of States in the Markov Model.- 9.2 Mean Duration of Boolean Functions’ Values.- 9.3 Mean Frequency of Changes of Functions’ Values.- 9.4 The Distribution of Residual Life Times.- Exercises.- 10 Some Algorithms and Computer Programs for Boolean Analysis.- 10.1 Computing Values of a Boolean Function.- 10.2 Canonical Representations of a Boolean Function.- 10.2.1 The Canonical Disjunctive Normal Form.- 10.2.2 The Canonical Multilinear Polynominal Form.- 10.3 Probability of a Given Value of a Boolean Function.- 10.4 Algorithms for Making the Terms of a Given DNF Disjoint.- 10.5 Selected Set Manipulations.- Exercises.- 11 Appendix: Probability Theory Refresher.- 11.1 Boolean Algebra of Sets.- 11.2 Elementary Probability Calculus.- 11.3 Random Variables and Random Processes.- 11.4 Elementary Renewal Theory.- 11.5 Laplace Transform Refresher.- Exercises.- Solutions of the exercises for §§ 2 through 11.- References.