Ones and Zeros Understanding Boolean Algebra,

This book explains, in lay terms, the surprisingly simple system of mathematical logic used in digital computer circuitry. Anecdotal in its style and often funny, it follows the development of this logic system from its origins in Victorian England to its rediscovery in this century as the foundation of all modern computing machinery. ONES AND ZEROS will be enjoyed by anyone who has a general interest in science and technology.

John R. Gregg is the author of Ones and Zeros: Understanding Boolean Algebra, Digital Circuits, and the Logic of Sets, published by Wiley.

BEFORE WE BEGIN

xiii

CHAPTER 0 NUMBER SYSTEMS AND COUNTING

1

(21)

0.1 Numbers: Some Background

1

(1)

0.2 The Decimal System: A Closer Look

2

(1)

0.3 Other Bases

3

(2)

0.4 Converting from Base 7 to Base 10

5

(2)

0.5 Converting from Base 10 to Base 7

7

(3)

0.6 Addition in Other Bases

10

(2)

0.7 Counting

12

(2)

0.8 The Binary Number System

14

(2)

0.9 Combinatoric Examples

16

(6)

0.9.1 U.S. Presidential Election Example

16

(1)

0.9.2 Pizza Example

16

(1)

0.9.3 Hypercube Example

17

(2)

0.9.4 Binary Trees

19

(3)

CHAPTER 1 THE BASIC FUNCTIONS OF BOOLEAN ALGEBRA: AND, OR, AND NOT

22

(15)

1.1 Boolean Functions

24

(1)

1.2 AND

25

(5)

1.2.1 Logical Interpretation of Bits

25

(1)

1.2.2 Truth Table for AND

26

(1)

1.2.3 Numbering of Rows in Truth Tables

27

(1)

1.2.4 The Principle of Assertion

28

(1)

1.2.5 Some Notational Conventions

28

(1)

1.2.6 Circuit Symbol for AND

29

(1)

1.3 OR

30

(3)

1.3.1 Truth Table for OR

31

(1)

1.3.2 Circuit Symbol for OR

31

(2)

1.4 NOT

33

(4)

1.4.1 Truth Table for NOT

33

(1)

1.4.2 Circuit Symbol for NOT

34

(3)

CHAPTER 2 COMBINATIONAL LOGIC

37

(22)

2.1 AND and NOT

37

(2)

2.2 Grouping with Parentheses

39

(8)

2.3 AND and OR with More Than Two Inputs

47

(1)

2.4 Algebraic Examples of Arbitrary-Input AND and OR Functions

48

(1)

2.5 Truth Tables for Arbitrary-Input AND and OR Functions

48

(2)

2.6 Creating Arbitrary-Input AND and OR Gates from the Old Two-Input Kind

50

(1)

2.7 An Arbitrary-Input AND Gate

51

(2)

2.8 An Arbitrary-Input OR Gate

53

(6)

CHAPTER 3 THE ALGEBRA OF SETS AND VENN DIAGRAMS

59

(18)

3.1 The Set

59

(1)

3.2 Venn Diagrams

60

(1)

3.3 Set Complementation

61

(1)

3.4 The Null Set

62

(1)

3.5 Subsets and Supersets

62

(1)

3.6 Intersection

63

(2)

3.7 Union

65

(1)

3.8 Example of Union and Intersection

66

(1)

3.9 Combinatorics of Venn Diagrams

66

(2)

3.10 Numbering Regions in Venn Diagrams

68

(2)

3.11 Combinational Logic in Venn Diagrams

70

(1)

3.12 Set Algebraic Interpretation of Combinational Logic

71

(6)

CHAPTER 4 OTHER BOOLEAN FUNCTIONS

77

(24)

4.1 The Constant Functions 0 and 1

78

(1)

4.2 NAND

79

(2)

4.3 NOR

81

(1)

4.4 XOR

81

(3)

4.5 COIN

84

(4)

4.5.1 Interesting Properties of XOR and COIN

86

(2)

4.6 Implication

88

(8)

4.6.1 Arithmetic Interpretation of Implication

90

(1)

4.6.2 Algebraic Realization of Implication

91

(1)

4.6.3 Circuit Symbol for Implication

91

(1)

4.6.4 Asymmetry of the Implication Function

92

(1)

4.6.5 Interpreting Implication of Terms of the Algebra of Sets

93

(3)

4.7 Other Complete Systems

96

(5)

4.7.1 XOR, NOT, and 1 as a Complete System

96

(1)

4.7.2 NAND as a Complete System

97

(4)

CHAPTER 5 REALIZING ANY BOOLEAN FUNCTION WITH AND, OR, AND NOT

101

(25)

5.1 Minterms

101

(6)

5.1.1 Decoder Example

104

(3)

5.2 Realizing Any Boolean Function Using Minterms

107

(2)

5.3 Sum-of-Products Expressions

109

(2)

5.3.1 Realization of Any Boolean Function Using a Decoder

110

(1)

5.4 The Seven-Segment Display

111

(6)

5.5 Maxterms

117

(3)

5.6 Realizing Any Boolean Function with Maxterms

120

(2)

5.7 Product-of-Sums Expressions

122

(1)

5.8 The Three-Input Majority Voter

123

(3)

CHAPTER 6 MORE DIGITAL CIRCUITS

126

(24)

6.1 The Multiplexer: Data Versus Control

126

(8)

6.1.1 AND as Controllable Pass-Through Gate

128

(1)

6.1.2 Decoder-Based Realization of the Multiplexer

129

(1)

6.1.3 Multiplexer with the Decoder Built In

130

(1)

6.1.4 Realizing Any Boolean Function with a Multiplexer

131

(3)

6.2 Vectors and Parallel Operations

134

(3)

6.3 The Adder

137

(5)

6.3.1 Adding in Base 10

137

(1)

6.3.2 Adding in Base 2

138

(1)

6.3.3 The Binary Adder Function

139

(3)

6.4 The Comparator

142

(3)

6.5 The ALU

145

(5)

CHAPTER 7 LAWS OF BOOLEAN ALGEBRA

150

(23)

7.1 Sets of Axioms

151

(1)

7.2 Perfect Induction

152

(7)

7.2.1 Special Properties of 0 and 1

153

(1)

7.2.2 The Complementation Laws

154

(1)

7.2.3 The Law of Involution

155

(1)

7.2.4 Commutative Laws of AND and OR

155

(1)

7.2.5 Distributive Laws of AND and OR

156

(3)

7.3 Deduction

159

(1)

7.4 Allowed Manipulations of Boolean Equations

159

(10)

7.4.1 Idempotence

160

(3)

7.4.2 Absorption Laws

163

(1)

7.4.3 Associativity Laws

164

(1)

7.4.4 DeMorgan's Laws

165

(4)

7.5 Principle of Duality

169

(4)

CHAPTER 8 BOOLEAN LOGIC

173

(30)

8.1 Opposition

173

(1)

8.2 Consensus

174

(2)

8.3 Canonical Form

176

(2)

8.4 Blake Canonical Form

178

(2)

8.5 Prime Implicants

180

(2)

8.6 A New Realization of the Implication Function

182

(1)

8.7 Syllogistic Reasoning

182

(2)

8.8 Premises That Are Not Implications

184

(3)

8.9 Clausal Form

187

(2)

8.10 Video Game Example

189

(4)

8.11 Equivalent Formulations of Results

193

(1)

8.12 Specific Results Derived from General Results

193

(2)

8.13 Karnaugh Maps

195

(8)

8.13.1 Gray Code

195

(8)

APPENDIX A: COUNTING IN BASE 2

203

(1)

APPENDIX B: POWERS OF 2

204

(1)

APPENDIX C: SUMMARY OF BOOLEAN FUNCTIONS

205

(8)

FREE SHIPPING

Amazon no longer offers textbook rentals. We do!

Ones and Zeros Understanding Boolean Algebra, Digital Circuits, and the Logic of Sets

Summary

Author Biography

Table of Contents

Supplemental Materials