Introduction to Digital Logic
Learning Objectives
- Explain what digital logic is and why binary (0/1) representation underlies all digital systems.
- State the core Boolean operators (AND, OR, NOT, XOR) and build truth tables for each.
- Identify the seven basic logic gates and predict their output for any input combination.
- Distinguish combinational circuits from sequential circuits by whether they have memory.
- Build a half adder from AND and XOR gates and trace its behavior for all input pairs.
- Recognize a D flip-flop as the simplest memory element and explain what "clocked" means.
Quick Answer
Digital logic is the set of rules and circuits that represent and manipulate information using only two values, 0 and 1 (binary). Instead of continuous voltages, digital systems treat "low" and "high" voltage as discrete states, which makes them far more reliable and noise-resistant than analog electronics. Every operation a computer performs — arithmetic, memory storage, branching — ultimately reduces to combinations of simple logic gates (AND, OR, NOT, and their derivatives) acting on these binary signals. Digital logic matters because it's the bridge between the physics of transistors and the software abstractions programmers work with: understanding it explains why computers can only do exactly what their circuits allow, and it's the foundation for computer architecture, embedded systems, and hardware design.
What Is Digital Logic?
Digital logic refers to the use of logical operations and circuits to represent and process information in binary format — 0s and 1s, corresponding to "off/on" or "low/high" voltage levels. It's the foundation upon which every digital system operates, from a pocket calculator to a supercomputer.
Why binary instead of, say, base 10? Because two clearly separated voltage levels are easy to distinguish reliably even with electrical noise, manufacturing variation, and temperature drift. A circuit only has to answer "is this closer to 0V or to 5V?" — a much easier engineering problem than reliably distinguishing ten different voltage levels. That reliability is what let engineers scale from a handful of transistors to billions on a single chip.
Boolean Algebra: The Math Behind the Circuits
Digital logic is built on Boolean algebra, developed by George Boole in the 1850s — decades before anyone built an electronic circuit. Boolean algebra manipulates only two values (true/false, 1/0) using a small set of operators:
- AND (∧) — true only if both operands are true
- OR (∨) — true if at least one operand is true
- NOT (¬) — flips true to false and vice versa
- XOR (⊕) — true if the operands differ
Every digital circuit, no matter how complex, is ultimately an arrangement of these operators. A 64-bit adder inside a CPU is just AND, OR, and XOR gates repeated and connected cleverly — there's no additional "magic" beyond that.
Truth Tables
A truth table lists every possible combination of inputs and the output for each — it's the complete, unambiguous specification of what a gate or circuit does. With n binary inputs there are always 2ⁿ rows. Truth tables matter because they let you verify a circuit's behavior by exhaustive checking rather than trusting an explanation in words.
The Seven Basic Logic Gates
AND Gate
Output is 1 only if all inputs are 1.
| Input 1 | Input 2 | Output |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Real-world analogy: a two-key safe deposit box that needs both the bank's key AND the customer's key turned simultaneously to open.
OR Gate
Output is 1 if at least one input is 1.
| Input 1 | Input 2 | Output |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Real-world analogy: a room light controlled by two switches (one at each door) — flipping either one turns the light on.
NOT Gate (Inverter)
Output is the opposite of the single input.
| Input | Output |
|---|---|
| 0 | 1 |
| 1 | 0 |
NAND Gate (NOT-AND)
Output is 0 only when all inputs are 1 — the exact inverse of AND.
| Input 1 | Input 2 | Output |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
NAND is special: it's a universal gate — any other gate (AND, OR, NOT, XOR) can be built using only NAND gates. This is why real chips are often built almost entirely from NAND gates — manufacturing one gate type repeatedly is cheaper and more consistent.
NOR Gate (NOT-OR)
Output is 1 only when all inputs are 0 — the exact inverse of OR.
| Input 1 | Input 2 | Output |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
NOR is also universal, for the same reason NAND is.
XOR Gate (Exclusive OR)
Output is 1 if the inputs differ.
| Input 1 | Input 2 | Output |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Why it matters: XOR is the "difference detector" gate. It's the core of binary addition (it produces the sum bit ignoring carry) and is heavily used in parity checking and simple encryption (XOR cipher).
XNOR Gate (Exclusive NOR)
Output is 1 if the inputs are the same — the inverse of XOR.
| Input 1 | Input 2 | Output |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Visualizing the Gates
Combinational vs. Sequential Circuits
This is the single most important classification in digital logic, so it's worth being precise about it.
Combinational circuits produce an output that depends only on the current inputs. Feed the same inputs in twice, and you always get the same output — there is no memory of what happened before. Plain logic gates wired together (AND, OR, NOT, etc.) are combinational.
Sequential circuits produce an output that depends on the current inputs and the circuit's previous state. They contain memory elements (flip-flops or latches) and usually a clock signal that governs when the stored state updates. A counter is sequential — the same "count" input pulse produces a different output depending on what number the counter is currently holding.
Worked Example: The Half Adder (Combinational)
A half adder adds two single-bit binary numbers and produces a Sum and a Carry. It needs one XOR gate (for the sum) and one AND gate (for the carry).
| Input A | Input B | Sum | Carry |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
Trace it by hand for A=1, B=1: XOR(1,1) = 0, so Sum = 0; AND(1,1) = 1, so Carry = 1. That's exactly "1 + 1 = 10 in binary" — Sum 0, Carry 1, just like carrying a 1 in decimal addition.
Worked Example: The D Flip-Flop (Sequential)
A D flip-flop stores one bit. It has a data input (D), a clock input, and an output (Q). On the rising edge of the clock, whatever value is on D gets "latched" into Q and held there — even after D changes — until the next clock edge.
| Clock edge | D | Q (after edge) |
|---|---|---|
| rising | 0 | 0 |
| rising | 1 | 1 |
| (no edge) | X | unchanged |
Notice the crucial difference from the AND/OR gates above: Q's value depends on when the clock ticked, not just on D's current value. That's memory.
Why This Matters
Every processor, memory chip, and digital sensor is built from exactly these primitives — gates for computation, flip-flops for memory. When you understand that a CPU's arithmetic logic unit is just a very large, cleverly arranged network of ANDs, ORs, XORs, and flip-flops, computer architecture stops feeling like magic and starts feeling like an engineering puzzle you can reason about.
Key Terms
| Term | Definition |
|---|---|
| Bit | A single binary digit, 0 or 1; the smallest unit of digital information. |
| Boolean algebra | The mathematical system (AND, OR, NOT, etc.) used to describe and simplify digital logic. |
| Logic gate | A physical or symbolic device that implements one Boolean function on one or more binary inputs. |
| Truth table | A table listing every input combination and the corresponding output(s) of a gate or circuit. |
| Universal gate | A gate (NAND or NOR) from which any other logic gate can be constructed. |
| Combinational circuit | A circuit whose output depends only on the present inputs, with no memory. |
| Sequential circuit | A circuit whose output depends on present inputs and stored past state (memory). |
| Half adder | A combinational circuit that adds two single bits, producing a Sum and a Carry. |
| Flip-flop | A basic memory element that stores one bit and updates on a clock edge. |
| Clock signal | A periodic signal that synchronizes when sequential circuits update their stored state. |
Common Mistakes
Misconception 1: "NOT gates need two inputs like the other gates." Why it's wrong: Students often pattern-match NOT to AND/OR and assume every gate takes two inputs. Correct: NOT is unary — it takes exactly one input and inverts it. Only AND, OR, XOR, NAND, NOR, XNOR are typically shown with two (or more) inputs.
Misconception 2: "A circuit with logic gates but no clock can still 'remember' a value if you wire the output back to an input." Why it's wrong: Feedback loops built purely from combinational gates (like a cross-coupled NOR latch) actually do create memory — but that memory only exists because of the loop's feedback structure, and it is unclocked, making the classification "combinational" wrong. Correct: A feedback loop of gates (e.g., an SR latch) is technically sequential, not combinational, precisely because its output depends on more than the current instantaneous inputs — the structure itself introduces state, even without an explicit clock signal.
Misconception 3: "XOR and OR are basically the same thing." Why it's wrong: For inputs (0,0) and (1,0)/(0,1) they agree, so it's easy to assume they're interchangeable. Correct: They diverge exactly at (1,1): OR outputs 1, XOR outputs 0. XOR specifically detects "exactly one input is 1" (a difference), while OR detects "at least one input is 1." This distinction is the whole reason XOR exists as a separate gate.
Comparison and Connections
| Concept | Combinational Circuit | Sequential Circuit |
|---|---|---|
| Depends on | Current inputs only | Current inputs + stored past state |
| Has memory? | No | Yes (flip-flops/latches) |
| Needs a clock? | No | Usually yes |
| Example | Half adder, multiplexer | D flip-flop, counter, register |
| Output for same input | Always identical | Can differ based on history |
| Gate | Output is 1 when... | Universal? |
|---|---|---|
| AND | all inputs are 1 | No |
| OR | at least one input is 1 | No |
| NAND | not all inputs are 1 | Yes |
| NOR | all inputs are 0 | Yes |
| XOR | inputs differ | No |
| XNOR | inputs match | No |
Practice Questions
Recall
- What are the two possible values a bit can hold, and what do they typically represent physically? Answer guidance: 0 and 1, representing low and high voltage (e.g., 0V and 5V or 3.3V).
- Name the two "universal" logic gates. Answer guidance: NAND and NOR.
Understanding
- Explain why NAND is called a universal gate. Answer guidance: Any Boolean function, including AND, OR, and NOT, can be constructed using only NAND gates — so a chip built entirely of NAND gates can implement any digital logic.
- Why does a combinational circuit never need a clock signal? Answer guidance: Its output is a pure function of the present inputs; there's no stored state to synchronize or update, so there's nothing for a clock to trigger.
Application
- Design a circuit (state the gates used) that outputs 1 only when exactly one of two switches is flipped on. What gate is this? Answer guidance: This is exactly the XOR gate's behavior — one two-input XOR gate does the job.
- A half adder is given inputs A=1, B=0. Trace through the XOR and AND gates to find Sum and Carry. Answer guidance: XOR(1,0)=1 → Sum=1; AND(1,0)=0 → Carry=0. Result: 1 + 0 = 01 in binary.
Analysis
- A student claims: "Since a D flip-flop has only one data input, it must be a combinational circuit like a NOT gate." Evaluate this claim. Answer guidance: False — input count doesn't determine the classification. The D flip-flop's output (Q) depends on the clock history, not just the current D value, so it's sequential regardless of having one input.
- Compare AND and OR gates using their truth tables: at which input combination(s) do they produce different outputs, and why does that make sense given their definitions? Answer guidance: They differ at (0,1) and (1,0) — AND outputs 0 because not all inputs are 1; OR outputs 1 because at least one input is 1. They only agree at (0,0)→0 and (1,1)→1.
FAQ
Q: Why do computers use binary instead of decimal? A: Binary states (voltage high/low) are far easier to distinguish reliably than ten discrete voltage levels would be, making circuits cheaper, faster, and much less error-prone.
Q: What's the difference between a gate and a circuit? A: A gate is a single basic logic operation (AND, OR, etc.). A circuit is a collection of gates wired together to perform a more complex function, like addition or memory storage.
Q: Is NAND really used to build everything in real chips? A: In principle yes — NAND is functionally complete. In practice, manufacturers use a mix of gate types optimized for speed, power, and area, but the "NAND-only" property is a foundational theoretical result used in digital design courses and in some standard-cell libraries.
Q: How is a truth table different from Boolean algebra? A: A truth table exhaustively lists every input/output pair for a specific circuit. Boolean algebra is the symbolic notation and rule set (like De Morgan's laws) used to manipulate and simplify the underlying expressions without listing every case.
Q: Do I need to memorize every gate's truth table for exams? A: Yes, at minimum for AND, OR, NOT, XOR, NAND, and NOR — they come up constantly, and being able to derive one quickly from its definition (rather than memorizing rows) will save you on exams with unfamiliar variations.
Quick Revision
- Digital logic represents information using only two states: 0 and 1 (binary).
- Boolean algebra (AND, OR, NOT, XOR) is the mathematical foundation of all digital circuits.
- A truth table fully specifies a gate/circuit's behavior for all 2ⁿ input combinations.
- AND = 1 only if all inputs are 1. OR = 1 if any input is 1. NOT = inverts its single input.
- NAND and NOR are "universal gates" — any other gate can be built from just one of them.
- XOR = 1 when inputs differ; XNOR = 1 when inputs match. XOR is the basis of binary addition.
- Combinational circuits: output depends only on current inputs, no memory.
- Sequential circuits: output depends on current inputs + stored past state, usually clocked.
- A half adder (XOR + AND) adds two bits, producing Sum and Carry.
- A D flip-flop stores one bit, updating Q to match D only on a clock edge.
- Feedback loops of pure combinational gates (like SR latches) actually create sequential behavior.
- Every digital system — from calculators to CPUs — is built from these same basic building blocks.
Related Topics
Prerequisites: Binary number systems, basic set theory/logic (propositional logic helps but isn't required).
Related Topics: Boolean algebra simplification, De Morgan's laws, number systems (binary, hex).
Next Topics: 2. Combinational Circuits, 3. Sequential Circuits, 4. Digital Design Tools