Real World: Circuit Design

Math for CS · Axiom Academy

From Boolean algebra to physical hardware: AND, OR, NOT, XOR, NAND, NOR Every logical connective has a physical counterpart: a logic gate . Gates are electronic circuits built from transistors that take binary inputs (0 or 1, representing false or true) and produce a binary output. All digital computers are built from combinations of these gates. Output 1 only if both inputs are 1 Output 1 if at least one input is 1 Fewer gates = cheaper circuit = less heat = faster operation. Use equivalence laws to simplify: A half adder adds two single-bit numbers. It has two outputs: Sum and Carry . A full adder adds two bits plus a carry-in from the previous column (just like carrying in long addition). Any Boolean function can be implemented using only NAND gates : NOT from NAND: (A, A) = A (feed the same signal to both inputs) AND from NAND: ( (A,B),\, (A,B)) = A B OR from NAND: ( (A,A),\, (B,B)) = A B Every logical connective maps to a physical gate built from transistors. Boolean algebra simplification directly reduces gate count in hardware. The half adder (XOR + AND) and full adder are the building blocks of arithmetic in CPUs. NAND is universal — any circuit can be built from NAND alone, which is why it dominates chip manufacturing.

This is the written version of the interactive lesson above. See the full Math for CS course.