Logic Gates

IB Syllabus: A1.2.3 — Describe the fundamental logic gates. A1.2.4 — Construct a Karnaugh map and deduce a Boolean expression from it. A1.2.5 — Construct a logic diagram from a given Boolean expression, and vice versa.

Table of Contents

  1. Key Concepts
    1. The Seven Fundamental Gates (A1.2.3)
      1. AND Gate
      2. OR Gate
      3. NOT Gate (Inverter)
      4. NAND Gate
      5. NOR Gate
      6. XOR Gate (Exclusive OR)
      7. XNOR Gate (Exclusive NOR)
    2. Boolean Algebra Rules (A1.2.5)
      1. Summary of Laws
      2. De Morgan’s Theorems
    3. Karnaugh Maps (A1.2.4)
      1. 2-Variable K-map
      2. 3-Variable K-map
      3. Grouping Rules
      4. Reading the Simplified Expression
    4. Logic Diagrams (A1.2.5)
      1. From Expression to Diagram
      2. From Diagram to Expression
    5. Enrichment: NAND Universality
    6. Enrichment: Flip-Flops
  2. Worked Examples
    1. Example 1: Build a Truth Table
    2. Example 2: Simplify with a K-map
    3. Example 3: Draw a Logic Diagram
  3. Quick Code Check
  4. Trace Exercise
  5. Spot the Error
  6. Fill in the Blanks
  7. Predict the Output
  8. Practice Exercises
    1. Core
    2. Extension
    3. Challenge
  9. Connections

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

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

  1. Group only 1s — circle groups of cells containing 1
  2. Group sizes must be powers of 2 — groups of 1, 2, 4, or 8 cells
  3. Groups must be rectangular — horizontal or vertical rectangles
  4. Groups can wrap around — the left edge is adjacent to the right edge; top to bottom
  5. Make groups as large as possible — larger groups give simpler expressions
  6. 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.

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:

  A ──┐
      ├──[ OR ]──┐
  B ──┘          ├──[ AND ]── Q
  C ──[ NOT ]────┘

Steps:

  1. Identify the outermost operation (here, AND) — this is the final gate before the output
  2. Work inward: the AND gate takes two inputs — the result of A + B (an OR gate) and ¬C (a NOT gate)
  3. 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:

  1. Follow each input wire to the first gate it enters
  2. Write that gate’s operation on its inputs
  3. Continue until you reach the output

Enrichment: NAND Universality

This goes beyond the IB syllabus but helps build understanding.

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 but helps build understanding.

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, built from two cross-coupled NOR gates:

  S ──[ NOR ]──┬── Q
        ┌──────┘
        └──────┐
  R ──[ NOR ]──┴── Q'
  • 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.

Worked Examples

Example 1: Build a Truth Table

Problem: Construct the truth table for Q = (A AND B) OR (NOT 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 B C A AND B NOT C (A AND B) OR (NOT C)
0 0 0 0 1 1
0 0 1 0 0 0
0 1 0 0 1 1
0 1 1 0 0 0
1 0 0 0 1 1
1 0 1 0 0 0
1 1 0 1 1 1
1 1 1 1 0 1

Key insight: Break compound expressions into intermediate columns. Evaluate inner operations first (AND, NOT), then combine 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 + B requires an OR gate with inputs A and B
  • ¬C requires a NOT gate with input C

Step 3: Connect them to the AND gate:

  A ────────┐
            ├──[ OR ]────────┐
  B ────────┘                ├──[ AND ]──── Q
  C ────────[ NOT ]──────────┘

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.

Quick Code 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?

Trace Exercise

Trace the following multi-gate circuit for all 8 input combinations. The circuit has two intermediate signals:

  • X = A AND B
  • Y = X OR C

Fill in the values of X and Y for each row.

ABCX = A AND BY = X OR C
000
001
010
011
100
101
110
111

Spot the Error

A student is simplifying a Boolean expression using De Morgan's theorem. They wrote the following steps. Click the buggy line, then pick the fix.

1Original: Q = ¬(A + B) · C 2Step 1: Apply De Morgan's to ¬(A + B) 3 ¬(A + B) = ¬A + ¬B ← De Morgan's 4Step 2: Q = (¬A + ¬B) · C 5Result: Q = ¬A·C + ¬B·C

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  ¬B

Predict 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

  1. Complete All Truth Tables — 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, the table should have 2 rows.

  2. Expression to Truth Table — Construct the truth table for Q = (A OR B) AND (NOT A). List all 4 input combinations and identify which rows produce Q = 1.

  3. De Morgan’s Practice — Apply De Morgan’s theorem to simplify each of the following:

    • ¬(X · Y)
    • ¬(P + Q)
    • ¬(¬A · B)

Extension

  1. 3-Input Circuit — Build a complete truth table (8 rows) for the circuit: Q = (A AND B) OR (B AND C) OR (A AND C). This circuit is called a “majority gate” — explain why.

  2. K-map Simplification — 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

  3. Diagram to Expression — The following logic diagram shows a circuit. Write the Boolean expression it represents:

      A ──[ NOT ]──┐
               ├──[ AND ]──┐
  B ───────────┘           ├──[ OR ]── Q
  C ───────────────────────┘

Challenge

  1. Alarm System Design — 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 alarm (Q) should 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 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

Back to top

© EduCS.me — A resource hub for IB Computer Science

This site uses Just the Docs, a documentation theme for Jekyll.