Logic Gates
A1.2.3 - Describe the purpose and use of logic gates. A1.2.4 - Construct and analyse truth tables (including Karnaugh maps and algebraic simplification). A1.2.5 - Construct logic diagrams.
Key Concepts
The Seven Fundamental Gates (A1.2.3)
A logic gate is an electronic component that takes one or more binary inputs (0 or 1) and produces a single binary output according to a fixed rule. Every digital circuit - from a calculator to a supercomputer - is built from combinations of these seven gates.
AND Gate
The AND gate outputs 1 only when both inputs are 1. Think of it as two switches in series: both must be closed for current to flow.
Boolean expression: Q = A AND B or Q = A · B
| A | B | A AND B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
OR Gate
The OR gate outputs 1 when at least one input is 1. Think of it as two switches in parallel: either one lets current flow.
Boolean expression: Q = A OR B or Q = A + B
| A | B | A OR B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
NOT Gate (Inverter)
The NOT gate has a single input and flips it. Input 0 becomes 1; input 1 becomes 0. It is the only single-input gate.
Boolean expression: Q = NOT A or Q = ¬A or Q = A'
| A | NOT A |
|---|---|
| 0 | 1 |
| 1 | 0 |
NAND Gate
The NAND gate is an AND gate followed by a NOT - it outputs 0 only when both inputs are 1. In all other cases, it outputs 1.
Boolean expression: Q = NOT (A AND B) or Q = ¬(A · B)
| A | B | A NAND B |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
NOR Gate
The NOR gate is an OR gate followed by a NOT - it outputs 1 only when both inputs are 0.
Boolean expression: Q = NOT (A OR B) or Q = ¬(A + B)
| A | B | A NOR B |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
XOR Gate (Exclusive OR)
The XOR gate outputs 1 when the inputs are different. If both are the same, it outputs 0.
Boolean expression: Q = A XOR B or Q = A ⊕ B
| A | B | A XOR B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
XNOR Gate (Exclusive NOR)
The XNOR gate is the inverse of XOR - it outputs 1 when both inputs are the same.
Boolean expression: Q = NOT (A XOR B) or Q = ¬(A ⊕ B)
| A | B | A XNOR B |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Introduction to AND, OR, NOT gates - how they work and their truth tables.
Logic Gates in a Computer (A1.2.3)
Inside a computer, each bit is a voltage on a wire: a low voltage stands for 0 and a high voltage for 1. A gate is a small circuit of transistors, tiny switches that the input voltages turn on and off, and its output is again a 0 or a 1. One gate’s output can therefore feed the next gate’s input, so gates combine into larger circuits. A circuit only has to tell two voltage levels apart, which it can do reliably even when a voltage drifts a little. This is one reason computers work in binary.
Combinations of gates do the work inside the processor and memory:
- Adding. An XOR gate gives the sum bit of two bits, and an AND gate gives the carry; together they make a half adder. Two half adders and an OR gate make a full adder, which also takes in the carry from the column before. Full adders chained through their carries let the ALU add whole binary numbers (see Half Adder and Full Adder).
- Comparing. An XNOR gate outputs 1 when its two input bits are the same. Comparing each pair of bits in two numbers and joining the results with AND tells the ALU whether the numbers are equal.
- Deciding. AND, OR and NOT combine conditions in hardware in the same way as
&&,||and!in Java (and,orandnotin Python). Control circuits in everyday devices are built like this, such as the quiz buzzer circuit in Example 4. - Decoding instructions. The control unit uses AND gates, with NOT gates on some inputs, that output 1 for one bit pattern only. For example,
A AND (NOT B) AND Cis 1 only for the pattern 101, so it can switch on the circuit for the instruction with that code. - Storing bits. Two gates whose outputs feed back into each other hold a 0 or a 1 until it is changed. Registers and cache memory are built from circuits like this (see Flip-Flops).
Boolean Algebra Rules (A1.2.5)
Boolean algebra provides a set of rules for simplifying logic expressions, just as ordinary algebra simplifies numeric expressions. The key difference: variables can only be 0 or 1.
Summary of Laws
| Law | AND form | OR form |
|---|---|---|
| Identity | A · 1 = A | A + 0 = A |
| Null | A · 0 = 0 | A + 1 = 1 |
| Complement | A · ¬A = 0 | A + ¬A = 1 |
| Idempotent | A · A = A | A + A = A |
| Commutative | A · B = B · A | A + B = B + A |
| Associative | (A · B) · C = A · (B · C) | (A + B) + C = A + (B + C) |
| Distributive | A · (B + C) = A·B + A·C | A + (B · C) = (A+B) · (A+C) |
De Morgan’s Theorems
These two theorems are essential for simplifying expressions and converting between gate types:
- Theorem 1:
¬(A · B) = ¬A + ¬B- the complement of AND equals the OR of complements - Theorem 2:
¬(A + B) = ¬A · ¬B- the complement of OR equals the AND of complements
In plain English: “break the bar, change the sign.” When you negate an entire expression, you negate each variable individually and swap AND for OR (or vice versa).
Karnaugh Maps (A1.2.4)
A Karnaugh map (K-map) is a visual method for simplifying Boolean expressions. It arranges truth table outputs in a grid so that adjacent cells differ by only one variable, making it easy to spot groups that simplify.
2-Variable K-map
For two variables A and B, the K-map is a 2x2 grid:
B=0 B=1
┌──────┬──────┐
A=0 │ m0 │ m1 │
├──────┼──────┤
A=1 │ m2 │ m3 │
└──────┴──────┘
Each cell holds the output value (0 or 1) from the truth table. The minterms are: m0 = ¬A·¬B, m1 = ¬A·B, m2 = A·¬B, m3 = A·B.
3-Variable K-map
For three variables A, B, C, the K-map is a 2x4 grid. The columns use Gray code ordering so adjacent cells differ by one variable:
BC=00 BC=01 BC=11 BC=10
┌──────┬──────┬──────┬──────┐
A=0 │ m0 │ m1 │ m3 │ m2 │
├──────┼──────┼──────┼──────┤
A=1 │ m4 │ m5 │ m7 │ m6 │
└──────┴──────┴──────┴──────┘
Note the column order: 00, 01, 11, 10 (not 00, 01, 10, 11). This Gray code order ensures adjacent cells share variables.
Grouping Rules
- Group only 1s - circle groups of cells containing 1
- Group sizes must be powers of 2 - groups of 1, 2, 4, or 8 cells
- Groups must be rectangular - horizontal or vertical rectangles
- Groups can wrap around - the left edge is adjacent to the right edge; top to bottom
- Make groups as large as possible - larger groups give simpler expressions
- Every 1 must be in at least one group - groups may overlap
Reading the Simplified Expression
For each group, identify which variables stay constant across all cells in the group:
- If a variable is 1 in every cell of the group, include it as-is (e.g.,
A) - If a variable is 0 in every cell of the group, include it negated (e.g.,
¬A) - If a variable changes within the group, it cancels out - omit it
The final expression is the OR of all group terms.
How to use K-maps to simplify Boolean expressions and minimise logic circuits.
Operator Precedence (A1.2.5)
When evaluating compound Boolean expressions, operators follow a strict order of precedence, just like arithmetic has multiplication before addition:
- NOT is evaluated first (highest precedence)
- AND is evaluated next
- OR is evaluated last (lowest precedence)
For example, the expression A AND B OR NOT A AND C is evaluated as (A AND B) OR ((NOT A) AND C), not A AND (B OR NOT A) AND C. The two readings give different truth tables: the correct one outputs 1 in four of the eight rows, the wrong one in only one.
Operator precedence is an easy place to go wrong in Boolean logic. Always evaluate NOT first, then AND, then OR. When in doubt, add brackets to make the order explicit.
Worked example: Evaluate A AND B OR NOT A AND C when A=1, B=1, C=0:
- NOT A = NOT 1 = 0
- A AND B = 1 AND 1 = 1 (AND before OR)
- NOT A AND C = 0 AND 0 = 0 (AND before OR)
- (A AND B) OR (NOT A AND C) = 1 OR 0 = 1
A common mistake is working from left to right instead of following precedence: A AND B = 1, then 1 OR NOT A = 1 OR 0 = 1, then 1 AND C = 1 AND 0 = 0. Working from left to right gives 0 instead of the correct answer 1, so ignoring precedence changes the result.
Logic Diagrams (A1.2.5)
A logic diagram (circuit diagram) shows how gates connect to process inputs into outputs. Reading and drawing these diagrams is a core IB skill.
From Expression to Diagram
To draw a diagram from Q = (A + B) · ¬C:
The gate names under the symbols are a reading aid; a logic diagram shows the symbols alone.
Steps:
- Identify the outermost operation (here, AND) - this is the final gate before the output
- Work inward: the AND gate takes two inputs - the result of
A + B(an OR gate) and¬C(a NOT gate) - Connect input wires A and B to the OR gate, and C to the NOT gate
From Diagram to Expression
Read from inputs to output, writing the operation at each gate:
- Follow each input wire to the first gate it enters
- Write that gate’s operation on its inputs
- Continue until you reach the output
Enrichment: NAND Universality
This goes beyond the IB syllabus, so it is not assessed.
The NAND gate is called a universal gate because any other gate can be built using only NAND gates:
- NOT from NAND: Connect both inputs of a NAND gate to the same signal:
¬A = A NAND A - AND from NAND: Take the output of an AND-equivalent and invert it:
A AND B = NOT(A NAND B)- two NAND gates - OR from NAND: By De Morgan’s theorem,
A + B = ¬(¬A · ¬B)- three NAND gates (two to invert, one to combine)
This property is significant in chip manufacturing because a single gate type simplifies fabrication. Real-world processors are often built primarily from NAND and NOR gates.
Enrichment: Flip-Flops
This goes beyond the IB syllabus, so it is not assessed.
So far, all circuits have been combinational - the output depends only on the current inputs. A flip-flop is a sequential circuit that can “remember” a single bit.
The simplest type is the SR (Set-Reset) flip-flop (strictly speaking an SR latch), built from two cross-coupled NOR gates:
Each gate’s output feeds back into the other gate’s input. A 1 on a NOR gate’s input forces that gate’s output to 0, so S=1 forces Q’ to 0, which lets Q become 1.
- Setting S=1, R=0 stores a 1 (Q=1)
- Setting S=0, R=1 stores a 0 (Q=0)
- Setting S=0, R=0 holds the previous value - the circuit “remembers”
Flip-flops are the building blocks of registers (in CPUs) and SRAM (static RAM used in cache). This is the connection between logic gates and primary memory.
Watch: Video Resources
How logic gates combine to perform binary addition - from transistors to arithmetic.
TED-Ed animation showing how transistors switch on and off to process binary data.
How the ALU uses logic gates to perform arithmetic and logical operations.
From individual transistors to logic gates to a full CPU - the building blocks explained.
How billions of transistors are etched onto chips using extreme ultraviolet light.
Try it yourself: the binary & logic playground lets you flip real bits, race conversions against your own best streak, and check truth tables against a live circuit.
Worked Examples
Example 1: Build a Truth Table
Problem: Construct the truth table for Q = (A AND C) OR (B NOR C).
Step 1: List all input combinations. With 3 inputs, there are 2^3 = 8 rows.
Step 2: Calculate intermediate values column by column. A AND C is 1 only when A and C are both 1; B NOR C is 1 only when B and C are both 0.
| A | B | C | A AND C | B NOR C | (A AND C) OR (B NOR C) |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 1 |
| 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | 0 | 1 |
Key insight: Break compound expressions into intermediate columns. Evaluate the inner operations first (AND, NOR), then combine them with the outer operation (OR).
Example 2: Simplify with a K-map
Problem: Simplify Q = ¬A·¬B·C + ¬A·B·C + A·¬B·C + A·B·C
Step 1: Identify which minterms produce output 1. The expression has four minterms where Q=1:
| A | B | C | Q |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |
Step 2: Fill in the 3-variable K-map:
BC=00 BC=01 BC=11 BC=10
┌──────┬──────┬──────┬──────┐
A=0 │ 0 │ 1 │ 1 │ 0 │
├──────┼──────┼──────┼──────┤
A=1 │ 0 │ 1 │ 1 │ 0 │
└──────┴──────┴──────┴──────┘
Step 3: Group the 1s. All four 1s form a single group of 4 (the two middle columns across both rows).
Step 4: Read the simplified expression. In this group:
- A changes (0 and 1) - cancel out A
- B changes (0 and 1) - cancel out B
- C stays 1 in all cells - keep C
Result: Q = C
The original four-term expression simplifies to a single variable. This makes sense: Q is 1 whenever C is 1, regardless of A or B.
Example 3: Draw a Logic Diagram
Problem: Draw the logic diagram for Q = (A + B) · ¬C
Step 1: Identify the outermost operation. The expression is an AND of two sub-expressions: (A + B) and ¬C.
Step 2: Break down each sub-expression:
A + Brequires an OR gate with inputs A and B¬Crequires a NOT gate with input C
Step 3: Connect them to the AND gate:
The OR and NOT gates work on the inputs first; the AND gate combines their outputs.
Reading it back: Inputs A and B feed into an OR gate. Input C feeds into a NOT gate. The outputs of the OR gate and NOT gate feed into an AND gate, producing Q. This confirms: Q = (A + B) · ¬C.
Example 4: From a Problem Description to a Truth Table
Problem: In a class quiz, each of three teams has a buzzer. After a question is read out, an answer light L should come on if exactly one team has pressed its buzzer. If two or three teams press at the same moment, the light stays off and the question is read again. Construct the truth table for L, then write a Boolean expression for it.
Step 1: Name the inputs and the output, and say what 1 means for each.
A,B,C: 1 means that team has pressed its buzzer; 0 means it has not.L(output): 1 means the answer light is on; 0 means it is off.
Step 2: Decide what kind of rule the description gives. This rule depends on how many inputs are 1, not on which ones, so the quickest way to build the table is to count the 1s in each row and apply the rule to the count.
Step 3: List all input combinations (three inputs give 2^3 = 8 rows), count the buzzers pressed, and fill in L.
| Row | A | B | C | Buzzers pressed | L |
|---|---|---|---|---|---|
| 1 | 0 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 1 | 1 | 1 |
| 3 | 0 | 1 | 0 | 1 | 1 |
| 4 | 0 | 1 | 1 | 2 | 0 |
| 5 | 1 | 0 | 0 | 1 | 1 |
| 6 | 1 | 0 | 1 | 2 | 0 |
| 7 | 1 | 1 | 0 | 2 | 0 |
| 8 | 1 | 1 | 1 | 3 | 0 |
Step 4: Write the expression from the rows where L = 1. Each of those rows becomes an AND of all three inputs, with NOT on every input that is 0 in that row. The rows are then joined with OR.
- Row 2 gives
¬A · ¬B · C - Row 3 gives
¬A · B · ¬C - Row 5 gives
A · ¬B · ¬C
L = ¬A · ¬B · C + ¬A · B · ¬C + A · ¬B · ¬C
On a K-map, no two of these three cells are next to each other, so grouping does not shorten this expression.
Step 5: Check the answer against the description, and against a tempting wrong answer. “Exactly one” can sound like XOR, and A XOR B XOR C does give 1 in rows 2, 3 and 5. But a chain of XOR gates outputs 1 whenever an odd number of inputs is 1, so it also gives 1 in row 8, when all three teams press together. The description says the light stays off then, so A XOR B XOR C is wrong for this problem.
Key insight: there are two ways to get from a description to a truth table. When the description joins conditions with words such as “and”, “or”, “not” and “unless”, turn each condition into gates and work out the columns. When the rule counts or compares the inputs (“exactly one”, “at least two”, “the two readings differ”), fill in the output row by row from the rule, then read the expression off the rows where the output is 1. Either way, check a few rows against the original wording before you finish.
Quick Check
Q1. A gate has this truth table. Which gate is it?
| A | B | Q |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |Q2. What is the output of an XOR gate when A=1 and B=0?
Q3. By De Morgan's theorem, ¬(A · B) is equivalent to:
Q4. Which of the following is NOT a valid group size in a Karnaugh map?
Q5. How many rows does a truth table have for a circuit with 4 inputs?
Complete the Truth Table
Trace the following multi-gate circuit for all 8 input combinations. The circuit has two intermediate signals:
X = A AND BY = X OR C
Fill in the values of X and Y for each row.
| A | B | C | X = A AND B | Y = X OR C |
|---|---|---|---|---|
| 0 | 0 | 0 | ||
| 0 | 0 | 1 | ||
| 0 | 1 | 0 | ||
| 0 | 1 | 1 | ||
| 1 | 0 | 0 | ||
| 1 | 0 | 1 | ||
| 1 | 1 | 0 | ||
| 1 | 1 | 1 |
Spot the Error
A student is simplifying a Boolean expression using De Morgan's theorem. They wrote the following steps. Select the buggy line, then pick the fix.
Pick the correct fix for the De Morgan's step:
Fill in the Blanks
Complete the summary of the seven fundamental logic gates by filling in the gate name or Boolean symbol:
Gate Summary
============
1. gate: Q = A · B → output 1 only when BOTH inputs are 1
2. gate: Q = A + B → output 1 when AT LEAST ONE input is 1
3. NOT gate: Q = → flips the input
4. NAND gate: Q = ¬(A · B) → output 0 only when inputs are 1
5. NOR gate: Q = ¬(A + B) → output 1 only when both inputs are
6. XOR gate: Q = A B → output 1 when inputs are DIFFERENT
7. XNOR gate: Q = ¬(A ⊕ B) → output 1 when inputs are
De Morgan's Theorems
====================
Theorem 1: ¬(A · B) = ¬A ¬B
Theorem 2: ¬(A + B) = ¬A ¬BPredict the Output
A circuit implements Q = (A XOR B) AND C. Given the inputs A=1, B=0, C=1, what is the output Q?
Inputs: A = 1, B = 0, C = 1
Circuit: Q = (A XOR B) AND C
Step 1: A XOR B = ?
Step 2: Q = (result) AND C = ?What is the value of Q?
Practice Exercises
Core
-
[Core]Truth tables[7 marks]Draw the truth table for each of the 7 fundamental gates (AND, OR, NOT, NAND, NOR, XOR, XNOR). For the two-input gates, each table should have 4 rows; for NOT, 2 rows. -
[Core]Truth tables[4 marks]Construct the truth table forQ = (A OR B) AND (NOT A). List all 4 input combinations and identify which rows produce Q = 1. -
[Core]Simplification[6 marks]Apply De Morgan’s theorem to simplify each of the following:¬(X · Y)¬(P + Q)¬(¬A · B)
Extension
-
[Extension]Truth tables[5 marks]Build a complete truth table (8 rows) for the circuitQ = (A AND B) OR (B AND C) OR (A AND C). This circuit is called a majority gate; explain why that name fits. -
[Extension]Simplification[6 marks]The following truth table defines a function of three variables. Use a K-map to find the simplified Boolean expression.A B C Q 0 0 0 1 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 0 1 1 1 1 -
[Extension]Logic diagrams[4 marks]The following logic diagram shows a circuit. Write the Boolean expression it represents:
Challenge
[Challenge]Logic diagrams[9 marks]A home alarm system has three binary inputs:D(door sensor: 1 = door open),W(window sensor: 1 = window open),S(system armed: 1 = armed). The alarmQshould sound when the system is armed AND either the door or window is open. Write the Boolean expression, draw the truth table (8 rows), simplify it using Boolean algebra or a K-map, and describe the logic diagram.
Connections
- Prerequisites: None (foundational topic)
- Next: CPU Architecture - how gates build processors (ALU, CU, registers)
- Related: Primary Memory - flip-flops explain how memory stores data
- Forward: Information Layer - number systems use the binary that gates process