Logic levels, gates, and Boolean algebra
Digital systems represent information with two voltage levels and process it with logic gates. Boolean algebra gives the rules for designing and simplifying them.
Analogue and digital
Analogue signals vary continuously, like a microphone's voltage. Digital signals take only discrete values, usually two: low (0) and high (1). Digital circuits tolerate noise because any voltage within a range counts as the same value; for 3.3 V CMOS logic, inputs below about 0.8 V read as 0 and above about 2.0 V read as 1, with a forbidden zone between.
Noise margins
Outputs are guaranteed to be lower than the low-input threshold and higher than the high-input threshold by safety margins called noise margins. A signal degraded by noise on its way to the next gate is still read correctly if the noise stays within the margin, and each gate restores clean levels, so digital signals can pass through millions of gates without accumulating errors.
Basic gates
Logic gates implement Boolean functions. NOT (inverter) outputs the opposite of its input. AND outputs 1 only if all inputs are 1; OR outputs 1 if any input is 1. NAND and NOR are AND and OR followed by NOT. XOR outputs 1 when its inputs differ, and XNOR when they are the same. In CMOS, NAND and NOR are the simplest gates to build.
Boolean algebra
George Boole's 1854 algebra of logic provides identities for manipulating expressions: A + 0 = A, A x 1 = A, A + A' = 1, A x A' = 0 (where ' means NOT), A + AB = A (absorption), and distributive laws. In 1937 Claude Shannon showed that this algebra describes switching circuits, founding digital circuit design.
De Morgan's theorems
De Morgan's theorems state that (AB)' = A' + B' and (A + B)' = A'B': the complement of an AND is the OR of complements, and vice versa. They allow AND-OR circuits to be converted into NAND-only or NOR-only forms. Since NAND gates are universal, any logic function can be built from NAND gates alone.
Truth tables and sum of products
A truth table lists a function's output for every input combination: n inputs give 2^n rows. Any truth table can be written as a sum of products: OR together one AND term for each row where the output is 1. For example, a function that is 1 when exactly one of A and B is 1 is A'B + AB', which is XOR.
Simplification and Karnaugh maps
Simpler expressions need fewer gates, less power, and less delay. Karnaugh maps, introduced by Maurice Karnaugh in 1953, arrange truth-table values in a grid where adjacent cells differ in one variable; grouping adjacent 1s in blocks of 1, 2, 4, or 8 reveals minimal sum-of-products expressions for functions of up to about four or five variables. Software tools minimise larger functions.
Worked example
A car alarm should sound (Y = 1) when the system is armed (A) and either a door is open (D) or motion is detected (M): Y = A(D + M) = AD + AM. The truth table has 8 rows, with Y = 1 for ADM = 101, 110, and 111. By De Morgan, the same function can be built from NAND gates: Y = ((AD)'(AM)')', three two-input NAND gates.
Key takeaways
Digital signals use discrete levels, typically 0 and 1, with thresholds such as 0.8 V and 2.0 V for 3.3 V CMOS. Noise margins let gates restore clean levels. Gates include NOT, AND, OR, NAND, NOR, XOR, and XNOR; NAND and NOR are natural in CMOS and universal. Boole's 1854 algebra, applied to circuits by Shannon in 1937, provides identities for simplification. De Morgan's theorems swap AND and OR with complements. Truth tables with 2^n rows convert to sum-of-products form. Karnaugh maps (1953) and software minimise logic.
Flashcard
Takes discrete values such as 0 and 1
Check your understanding
By De Morgan's theorem, what is the complement of (A + B)?