The Logician and the Engineer

Preface xi

1 What You Need to Know to Read This Book 1

Notes and References 5

2 Introduction 6

Notes and References 14

3 George Boole and Claude Shannon: Two Mini-Biographies 17

- 3.1 The Mathematician 17

- 3.2 The Electrical Engineer 28

- Notes and References 39

4 Boolean Algebra 43

- 4.1 Boole's Early Interest in Symbolic Analysis 43

- 4.2 Visualizing Sets 44

- 4.3 Boole's Algebra of Sets 45

- 4.4 Propositional Calculus 48

- 4.5 Some Examples of Boolean Analysis 52

- 4.6 Visualizing Boolean Functions 59

- Notes and References 65

5 Logical Switching Circuits 67

- 5.1 Digital Technology: Relays versus Electronics 67

- 5.2 Switches and the Logical Connectives 68

- 5.3 A Classic Switching Design Problem 71

- 5.4 The Electromagnetic Relay and the Logical NOT 73

- 5.5 The Ideal Diode and the Relay Logical AND and OR 76

- 5.6 The Bi-Stable Relay Latch 81

- Notes and References 84

6 Boole, Shannon, and Probability 88

- 6.1 A Common Mathematical Interest 88

- 6.2 Some Fundamental Probability Concepts 89

- 6.3 Boole and Conditional Probability 96

- 6.4 Shannon, Conditional Probability, and Relay Reliability 99

- 6.5 Majority Logic 106

- Notes and References 110

7 Some Combinatorial Logic Examples 114

- 7.1 Channel Capacity, Shannon's Theorem, and Error-Detection Theory 114

- 7.2 The Exclusive-OR Gate (XOR) 122

- 7.3 Error-Detection Logic 127

- 7.4 Error-Correction Theory 128

- 7.5 Error-Correction Logic 132

- Notes and References 137

8 Sequential-State Digital Circuits 139

- 8.1 Two Sequential-State Problems 139

- 8.2 The NOR Latch 142

- 8.3 The Clocked RS Flip-Flop 146

- 8.4 More Flip-Flops 154

- 8.5 A Synchronous, Sequential-State Digital Machine Design Example 158

- Notes and References 160

9 Turing Machines 161

- 9.1 The First Modern Computer 162

- 9.2 Two Turing Machines 164

- 9.3 Numbers We Can't Compute 168

- Notes and References 173

10 Beyond Boole and Shannon 176

- 10.1 Computation and Fundamental Physics 176

- 10.2 Energy and Information 178

- 10.3 Logically Reversible Gates 180

- 10.4 Thermodynamics of Logic 184

- 10.5 A Peek into the Twilight Zone: Quantum Computers 188

- 10.6 Quantum Logic--and Time Travel, Too! 197

Notes and References 205

Epilogue

For the Future: The Anti-Amphibological Machine 210

Appendix

Fundamental Electric Circuit Concepts 219

Acknowledgments 223

Index 225