Boolean Logic, Truth Tables and Circuit Simplification

Three representations of one thing. A logic circuit can be described as a diagram of gates, as a truth table listing the output for every combination of inputs, or as a Boolean expression. Exam questions move between the three, and the skill is to convert reliably. From a diagram to a table: label every intermediate wire, then evaluate row by row, working from inputs to output. From a table to an expression: take each row whose output is 1, write it as an AND of the inputs (using NOT for inputs that are 0 in that row), and join the rows with OR. From an expression to a diagram: draw one gate per operator, innermost first. A table for n inputs has 2ⁿ rows; write the inputs in binary counting order so that no row is missed.

The half adder as the standard example. Adding two one-bit numbers needs two outputs: the sum bit S = A XOR B and the carry bit C = A AND B. The row 1 + 1 gives S = 0, C = 1, because 1 + 1 = 10 in binary. Two half adders and an OR gate make a full adder that also accepts a carry in, and chaining full adders builds the circuit that adds whole binary numbers inside the processor. This is why gates matter: every arithmetic operation the CPU performs is ultimately a network of these circuits.

Simplification and why it is worth doing. Two expressions with identical truth tables are equivalent, and the simpler one needs fewer gates. Fewer gates means lower cost, faster operation (fewer gate delays between input and output), less heat and fewer components to fail. The laws used most: X OR NOT X = 1; X AND NOT X = 0; X OR (X AND Y) = X (absorption); distribution, so that (A AND B) OR (A AND NOT B) = A AND (B OR NOT B) = A; and De Morgan's laws, NOT (A AND B) = NOT A OR NOT B, and NOT (A OR B) = NOT A AND NOT B. After simplifying, always rebuild the truth table of the new expression and check it matches the original — a simplification that changes the table is a mistake, not a simplification.

NAND is enough. Every gate can be built from NAND gates alone: NOT A = A NAND A; A AND B = NOT (A NAND B); A OR B = (NOT A) NAND (NOT B) by De Morgan. This is called functional completeness (NOR has the same property), and it is why manufacturers can mass-produce a single gate type and wire it into anything. The exam version of this idea is a question that gives you a circuit and asks you to rebuild it with NAND only, or asks why a designer might prefer to.