Logic and digital circuits
Computers process bits using logic gates, tiny circuits that combine inputs according to Boolean logic. Combined in billions, they perform every computation.
Boolean logic
George Boole developed an algebra of logic in the 1850s using true and false values. Claude Shannon showed in 1937 that Boolean algebra could describe electrical switching circuits, linking logic to hardware. In computers, true is 1 and false is 0.
Basic logic gates
An AND gate outputs 1 only if both inputs are 1. An OR gate outputs 1 if at least one input is 1. A NOT gate (inverter) flips its input. NAND and NOR gates are AND and OR followed by NOT. An XOR (exclusive OR) gate outputs 1 if exactly one input is 1.
Truth tables
A truth table lists every combination of inputs and the resulting output. For two inputs there are 4 combinations: for AND, outputs are 0, 0, 0, 1; for OR, 0, 1, 1, 1; for XOR, 0, 1, 1, 0. Truth tables precisely define any logic function.
Universal gates
NAND gates are universal: any logic circuit can be built using only NAND gates, and the same is true of NOR. This simplifies chip manufacturing. For example, NOT A can be made as A NAND A.
Building an adder
A half adder adds two bits: the sum is A XOR B, and the carry is A AND B. A full adder adds three bits (including a carry-in). Chaining full adders creates circuits that add multi-bit numbers, the basis of a processor's arithmetic logic unit (ALU).
Memory circuits
Logic gates can also store bits. A flip-flop or latch uses feedback, connecting outputs back to inputs, to hold a 0 or 1 until changed. Registers inside processors are built from flip-flops. Main memory (DRAM) instead stores bits as charges in tiny capacitors that must be refreshed.
From gates to chips
Modern chips contain billions of transistors arranged into gates. Combinational circuits, such as adders, produce outputs from current inputs only; sequential circuits, such as counters and memory, also depend on stored state and a clock signal that coordinates timing.
Worked example
Evaluate the circuit (A AND B) OR (NOT C) for A = 1, B = 0, C = 0. A AND B = 0; NOT C = 1; 0 OR 1 = 1. For A = 1, B = 1, C = 1: A AND B = 1; NOT C = 0; 1 OR 0 = 1. For A = 0, B = 1, C = 1: 0 OR 0 = 0. A truth table would list all 8 input combinations.
Key takeaways
Boole created logical algebra; Shannon linked it to circuits. AND, OR, NOT, NAND, NOR, and XOR are basic gates, defined by truth tables. NAND and NOR are universal gates. Half and full adders, built from XOR and AND, perform binary addition in the ALU. Flip-flops store bits using feedback; DRAM uses capacitors. Chips combine billions of gates into combinational and sequential circuits coordinated by a clock.
Flashcard
Algebra of true and false
Check your understanding
For inputs A = 1 and B = 1, which gate outputs 0?