Code & Robots, level 13
🔌 Logic Gates
How can a machine made of tiny switches do arithmetic?
- How can a machine made of tiny switches do arithmetic? It relies on logic gates, the elementary building blocks of every modern computer. The Computer History Museum explains that computer circuits are built from simple elements called gates, made from either mechanical or electronic switches, and that just three operations, AND, OR and NOT, can perform all logic functions. These operations come from the system of reasoning that the English mathematician George Boole set out in the nineteenth century, which is now called Boolean logic in his honor. In 1937, Claude Shannon's master's thesis at the Massachusetts Institute of Technology showed how Boolean algebra could be applied to the design of circuits built from electrical relays. Inside a modern processor, enormous numbers of microscopic transistors serve as the switches, operating far faster than any relay, but the underlying logic remains essentially the same logic that Boole originally described more than a century and a half ago.
- Each gate takes inputs that are either 1, meaning on or true, or 0, meaning off or false, and it produces an output according to a fixed rule. An AND gate outputs 1 only when both of its inputs are 1, which matches the everyday meaning of a sentence such as 'it is sunny and it is warm.' An OR gate outputs 1 when at least one input is 1, so it outputs 0 only when both of its inputs are 0. A NOT gate, by contrast, has a single input and simply reverses it, turning 1 into 0 and 0 into 1. Engineers summarize each rule in a truth table, which lists every possible combination of inputs alongside the output that results. With two inputs there are exactly four combinations, namely 0 and 0, 0 and 1, 1 and 0, and 1 and 1, so the truth table for an AND gate has four rows, and only the final row produces a 1, whereas the truth table for an OR gate produces a 1 in three of its four rows.
- Gates can be combined to perform addition. When you add two single binary digits, there are four possible cases: 0 plus 0 is 0, 0 plus 1 and 1 plus 0 are both 1, and 1 plus 1 is 2, which binary writes as 10, meaning a sum digit of 0 with a 1 carried into the next column. Look carefully and you will notice that the carry digit is 1 only when both inputs are 1, which is precisely the AND rule. The sum digit is 1 only when exactly one input is 1, a rule that can be assembled from the three basic gates as (A OR B) AND NOT (A AND B). This small circuit, which engineers call a half adder, handles a single column of the addition. Engineers extend the same idea into circuits that also accept a carry from the previous column, and connecting a long row of those lets a processor add lengthy binary numbers using nothing more than combinations of AND, OR and NOT.
Try it at home: Make a truth table together for AND and OR using two light switches (on is 1, off is 0), then add 1 plus 1 in binary.
Questions and answers
Logic Gates
- According to the Computer History Museum, which three operations can perform all logic functions? AND, OR and NOT
- 📜 The system of logic behind computer gates is named after which mathematician? George Boole (George Boole set out the rules in the nineteenth century, now called Boolean logic.)
- Claude Shannon's 1937 master's thesis showed how Boolean algebra could be used to design circuits built from… electrical relays
- 🔌 When does an AND gate output 1? Only when both inputs are 1
- When does an OR gate output 0? Only when both inputs are 0 (An OR gate outputs 1 if at least one input is 1, so 0 only when both are 0.)
- 🔄 A NOT gate receives the input 1. What does it output? 0 (A NOT gate reverses its single input, so 1 becomes 0.)