1.4.3 Boolean Algebra
1.4.3(a) Logic Gates
Logic gates are the fundamental building blocks of digital circuits. All computer processors are built from combinations of these simple gates.
Definition
A logic gate is an electronic circuit that performs a logical operation on one or more binary inputs and produces a single binary output.
NOT Gate
Definition
The NOT gate (inverter) has one input and outputs the opposite value.
Example
Truth Table:
Symbol: Triangle with circle at output
Expression: Q = ¬A
| A | NOT A |
|---|---|
| 0 | 1 |
| 1 | 0 |
Expression: Q = ¬A
AND Gate
Definition
The AND gate outputs 1 only when ALL inputs are 1.
Example
Truth Table:
Expression: Q = A ∧ B
| A | B | A AND B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
OR Gate
Definition
The OR gate outputs 1 when AT LEAST ONE input is 1.
Example
Truth Table:
Expression: Q = A ∨ B
| A | B | A OR B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
XOR Gate (Exclusive OR)
Definition
The XOR gate outputs 1 when inputs are DIFFERENT.
Example
Truth Table:
Expression: Q = A XOR B
| A | B | A XOR B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
NAND Gate
Definition
The NAND gate is AND followed by NOT - outputs 0 only when ALL inputs are 1.
Example
Truth Table:
NAND is a "universal gate" - can create any other gate using only NANDs.
| A | B | A NAND B |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
NOR Gate
Definition
The NOR gate is OR followed by NOT - outputs 1 only when ALL inputs are 0.
Example
Truth Table:
NOR is also a "universal gate" - can create any other gate using only NORs.
| A | B | A NOR B |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
Key Point
| Gate | Output rule | Expression |
|---|---|---|
| NOT | Inverts single input | Q = ¬A |
| AND | 1 only if all inputs are 1 | Q = A ∧ B |
| OR | 1 if at least one input is 1 | Q = A ∨ B |
| XOR | 1 if inputs are different | Q = A ⊕ B |
| NAND | NOT(AND), 0 only if all inputs are 1 | Q = ¬(A ∧ B) |
| NOR | NOT(OR), 1 only if all inputs are 0 | Q = ¬(A ∨ B) |
1.4.3(b) Boolean Expressions and Algebra
Boolean expressions can be simplified using algebraic rules, making circuits cheaper and faster.
Boolean Algebra Laws
Key Point
| Law family | OR form | AND form |
|---|---|---|
| Identity | A ∨ 0 = A | A ∧ 1 = A |
| Null | A ∨ 1 = 1 | A ∧ 0 = 0 |
| Idempotent | A ∨ A = A | A ∧ A = A |
| Complement | A ∨ ¬A = 1 | A ∧ ¬A = 0 |
| Involution | ¬¬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) |
| Absorption | A ∨ (A ∧ B) = A | A ∧ (A ∨ B) = A |
De Morgan's Laws
Key Point
| Original expression | Equivalent expression | In words |
|---|---|---|
| ¬(A ∧ B) | ¬A ∨ ¬B | NOT (A AND B) = (NOT A) OR (NOT B) |
| ¬(A ∨ B) | ¬A ∧ ¬B | NOT (A OR B) = (NOT A) AND (NOT B) |
Worked Example
Worked Example: Simplifying a Boolean Expression
Simplify: Q = A ∧ B ∨ A ∧ ¬B ∨ ¬A ∧ B
Step 1: Factor out common terms
Q = A ∧ (B ∨ ¬B) ∨ ¬A ∧ B
Step 2: Apply complement law (B + B̅ = 1)
Q = A ∧ 1 ∨ ¬A ∧ B
Step 3: Apply identity law (A.1 = A)
Q = A ∨ ¬A ∧ B
Step 4: Apply absorption (or expand and simplify)
Q = A ∨ ¬A ∧ B
= (A ∨ ¬A) ∧ (A ∨ B) [Distributive law]
= 1 ∧ (A ∨ B) [Complement law]
= A ∨ B [Identity law]
Answer: Q = A ∨ B (much simpler circuit!)
Simplify: Q = A ∧ B ∨ A ∧ ¬B ∨ ¬A ∧ B
Step 1: Factor out common terms
Q = A ∧ (B ∨ ¬B) ∨ ¬A ∧ B
Step 2: Apply complement law (B + B̅ = 1)
Q = A ∧ 1 ∨ ¬A ∧ B
Step 3: Apply identity law (A.1 = A)
Q = A ∨ ¬A ∧ B
Step 4: Apply absorption (or expand and simplify)
Q = A ∨ ¬A ∧ B
= (A ∨ ¬A) ∧ (A ∨ B) [Distributive law]
= 1 ∧ (A ∨ B) [Complement law]
= A ∨ B [Identity law]
Answer: Q = A ∨ B (much simpler circuit!)
1.4.3(c) Karnaugh Maps
Definition
A Karnaugh map (K-map) is a graphical method for simplifying Boolean expressions by grouping adjacent cells containing 1s.
Key Point
K-Map Rules:
• Group 1s in powers of 2 (1, 2, 4, 8)
• Groups must be rectangular
• Make groups as large as possible
• Groups can wrap around edges
• Each 1 must be in at least one group
• Larger groups = simpler expression
• Group 1s in powers of 2 (1, 2, 4, 8)
• Groups must be rectangular
• Make groups as large as possible
• Groups can wrap around edges
• Each 1 must be in at least one group
• Larger groups = simpler expression
Worked Example
Worked Example: 2-Variable K-Map (clear grouping)
Step 1: Start from the truth table.
Step 2: Fill the K-map (rows = A, columns = B).
Step 3: Form largest valid groups (powers of 2).
Notes:
• Overlap is allowed (cell A=0,B=1 is used in both groups).
• Grouping larger pairs reduces expression size.
Final simplified expression:
Q = ¬A ∨ B
Step 1: Start from the truth table.
| A | B | Q |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
| A\B | 0 | 1 |
|---|---|---|
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| Group | Cells used | Constant term |
|---|---|---|
| G1 (top row pair) | (A=0,B=0) and (A=0,B=1) | ¬A |
| G2 (right column pair) | (A=0,B=1) and (A=1,B=1) | B |
• Overlap is allowed (cell A=0,B=1 is used in both groups).
• Grouping larger pairs reduces expression size.
Final simplified expression:
Q = ¬A ∨ B
1.4.3(d) D-Type Flip-Flops
Flip-flops are the basic memory units in digital circuits - they can store one bit of data.
Definition
A D-type flip-flop is a memory device that captures the value of the D input at a specific moment (the clock edge) and holds it at the Q output.
Key Point
D Flip-Flop Signals:
• D (Data) - The input value to be stored
• CLK (Clock) - Controls WHEN to capture D
• Q - The output (stored value)
• ¬Q - The inverted output (complement of Q)
• D (Data) - The input value to be stored
• CLK (Clock) - Controls WHEN to capture D
• Q - The output (stored value)
• ¬Q - The inverted output (complement of Q)
Worked Example
Worked Example: D Flip-Flop Behaviour
Rising-edge triggered flip-flop:
At each rising edge (↑):
• Q takes the value currently on D
• Q then holds that value until the next clock edge
• Changes to D between clock edges are ignored
Key point: The flip-flop only samples D when the clock edge occurs.
Rising-edge triggered flip-flop:
| Clock edge | D at edge | Q after edge |
|---|---|---|
| T1 (↑) | 1 | 1 |
| T2 (↑) | 0 | 0 |
| T3 (↑) | 1 | 1 |
| T4 (↑) | 1 | 1 |
| T5 (↑) | 0 | 0 |
• Q takes the value currently on D
• Q then holds that value until the next clock edge
• Changes to D between clock edges are ignored
Key point: The flip-flop only samples D when the clock edge occurs.
Key Point
Flip-Flop Applications:
• Registers - Store multiple bits (8 flip-flops = 8-bit register)
• Counters - Count clock pulses
• Memory - Building block of RAM
• State machines - Store current state
• Frequency division - Divide clock speed by 2
• Registers - Store multiple bits (8 flip-flops = 8-bit register)
• Counters - Count clock pulses
• Memory - Building block of RAM
• State machines - Store current state
• Frequency division - Divide clock speed by 2
Exam Tip
D flip-flop exam phrasing:
• "Q takes the value of D on the active clock edge"
• "Q holds that value between edges"
• "Changes on D between edges do not affect Q"
• "Q takes the value of D on the active clock edge"
• "Q holds that value between edges"
• "Changes on D between edges do not affect Q"