Boolean Logic
What is Boolean Logic?
• Boolean logic is used in computer science and electronics to make logical decisions
• Boolean operators are either
TRUE or
FALSE, often represented as
1 or
0• Inputs and outputs are given letters to represent them (e.g. A, B, C)
• Special symbols are used to write expressions more concisely
Evaluating Boolean Expressions
• Expressions are evaluated in a specific order — similar to BIDMAS in maths:
1.
Brackets (parentheses first)
2.
NOT 3.
AND 4.
OR• Using brackets can alter the standard order of operations
• Example: NOT(TRUE AND FALSE) = NOT(FALSE) = TRUE
Logic Gates
Logic gates are a visual way of representing a Boolean expression. The four gates covered in this course are:
AND (Conjunction)
• Symbol: ∧
• Returns
TRUE only if both inputs are TRUE• TRUE AND TRUE = TRUE; otherwise = FALSE
• Has the
second highest precedence (after NOT) — executes before OR
OR (Disjunction)
• Symbol: ∨
• Returns
TRUE if either input is TRUE• FALSE OR FALSE = FALSE
• Has the
lowest precedence — executes after NOT and AND
NOT (Negation)
• Symbol: ¬
•
Inverts the input value
• NOT TRUE = FALSE; NOT FALSE = TRUE
• Has the
highest precedence — executes before AND and OR
XOR (Exclusive Disjunction)
• Symbol: ⊕
• Outputs
TRUE if the inputs are different• Outputs
FALSE if they are the same
Karnaugh Maps
What is a Karnaugh Map?
• A
Karnaugh map (KMap) is a tool used to simplify Boolean algebra expressions
• It offers a
visual method of grouping together expressions with common factors
• The format makes it easy to identify and eliminate redundant terms
• Used in digital logic design to simplify circuits
Steps for Using a Karnaugh Map
1.
Create the map — each cell in the grid corresponds to a term in the Boolean expression; fill cells with 1s and 0s for the output of that term
2.
Grouping — group the 1s in the grid. Each group must be a
rectangle and the size must be a
power of 2 (1, 2, 4, or 8). A cell can be in multiple groups
3.
Simplifying — write a simplified Boolean expression for each group. The simplified expression consists of the
variables that remain constant throughout the group
4.
Final expression — combine the simplified expressions from each group using OR
Creating a 2-Variable KMap (example: A ∨ B)
• Add variable A across the top (0, 1) and B down the side (0, 1)
• For each subterm, put a
1 in every cell where that term is TRUE
• For A ∨ B: put a 1 wherever A=1 OR B=1 (all cells except A=0, B=0)
Gray Codes
• In a 3-variable KMap, the binary sequence across the top must change only
1 bit at a time• This is called
Gray Code: 00, 01,
11, 10 (note: NOT 00, 01, 10, 11)
• This ensures adjacent cells differ by only one variable
Simplifying with a 3-Variable KMap
Example: simplify ¬A∧¬B∧C ∨ ¬A∧B∧¬C ∨ A∧¬B∧C ∨ A∧BStep 1 — Split the long expression at each OR to get four subterms:
• ¬A ∧ ¬B ∧ C
• ¬A ∧ B ∧ ¬C
• A ∧ ¬B ∧ C
• A ∧ B
Steps 2–5 — Place a 1 in the KMap for each subterm where the term is TRUE.
Making the groups:• Groups must be
rectangular• Groups must be as
large as possible• Groups must contain
8, 4, 2, or 1 ones
• Groups
can overlap (a cell can be in multiple groups)
• The KMap
wraps round in all directions
Reading the groups:• For each group, identify which variable(s) remain
constant throughout all cells in the group
• That constant variable (or its NOT) represents the group
•
Group 1 (where A=1 in all cells): represents
A•
Group 2 (where B=0 in all cells, with wrap-around): represents
¬BFinal simplified expression: A ∨ ¬B
Boolean Algebra
What is Boolean Algebra?
• Boolean algebra is a
mathematical system used to manipulate Boolean values
• Complex expressions can be simplified using the rules of Boolean algebra
• More powerful than Karnaugh maps — can simplify expressions that KMaps cannot
• Combining rules can reduce complex expressions to much simpler ones
General Rules
| Rule | AND version | OR version |
|---|
| Identity | X ∧ 1 = X | X ∨ 0 = X |
| Null | X ∧ 0 = 0 | X ∨ 1 = 1 |
| Idempotent | X ∧ X = X | X ∨ X = X |
| Complement | X ∧ ¬X = 0 | X ∨ ¬X = 1 |
De Morgan's Law
What is De Morgan's Law?
• A strategy for simplifying expressions that include a
negation of a conjunction or disjunction• Allows simplification by
inverting all variables and swapping AND/OR• Useful because it means circuits can be built using only
NAND or NOR gates, which simplifies microprocessor construction (e.g. flash drives)
The Two Laws
| Law | Statement |
|---|
| First Law | NOT(A AND B) = (NOT A) OR (NOT B) |
| Second Law | NOT(A OR B) = (NOT A) AND (NOT B) |
Applying De Morgan's Law (step by step)
Example: prove NOT(A AND B) = NOT A OR NOT B1. Change AND to OR (or vice versa): ¬(A ∨ B)
2. NOT the terms either side of the operator: ¬(¬A ∨ ¬B)
3. NOT everything that has changed: ¬¬(¬A ∨ ¬B)
4. Get rid of any double negation: (¬A ∨ ¬B)
5. Remove unnecessary brackets:
¬A ∨ ¬B
Distribution
What is Distributive Law?
• Explains how
AND and OR interact with each other
• Similar to factorising in regular maths
| Rule | Expression |
|---|
| AND over OR | A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C) |
| OR over AND | A ∨ (B ∧ C) = (A ∨ B) ∧ (A ∨ C) |
Real-life example: "You can pick one subject from group A and either one from group B or group C" is the same as "You can pick A and B, or A and C."
Association
What is Associative Law?
• Explains how variables
group in expressions of more than two variables
• Allows us to
remove brackets and regroup variables
| Rule | Expression |
|---|
| AND | (A ∧ B) ∧ C = A ∧ (B ∧ C) = A ∧ B ∧ C |
| OR | (A ∨ B) ∨ C = A ∨ (B ∨ C) = A ∨ B ∨ C |
Real-life example: "Zarmeen and her friends Zahra and Ella" is the same as "Zarmeen, Zahra, and Ella."
Commutation
What is Commutative Law?
• States that the
order of variables does not change the truth value
| Rule | Expression |
|---|
| AND | A ∧ B = B ∧ A |
| OR | A ∨ B = B ∨ A |
Real-life example: "Fynn and George won gold medals" is the same as "George and Fynn won gold medals."
Double Negation
What is Double Negation?
• States that
negating a variable twice returns the original variable
• NOT(NOT(A)) = A
Real-life example: "I don't
not want to visit the castle" = "I
do want to visit the castle."
Worked Simplification Example
Simplify (A ∨ B) ∧ (A ∨ C)| Step | Rule Used | Expression |
|---|
| Start | — | (A ∨ B) ∧ (A ∨ C) |
| Step 1 | Distribution | (A ∧ A) ∨ (B ∧ A) ∨ (A ∧ C) ∨ (B ∧ C) |
| Step 2 | General rules (X ∧ X = X) | A ∨ (B ∧ A) ∨ (A ∧ C) ∨ (B ∧ C) |
| Step 3 | Commutation (B ∧ A → A ∧ B) | A ∨ (A ∧ B) ∨ (A ∧ C) ∨ (B ∧ C) |
| Step 4 | General rules (A ∨ (A ∧ B) = A) | A ∨ (A ∧ C) ∨ (B ∧ C) |
| Step 5 | General rules (A ∨ (A ∧ C) = A) | A ∨ (B ∧ C) |
D-Type Flip-Flops
What is a D-Type Flip-Flop?
• A fundamental component in digital circuits and computer memory
• Also called
Positive Edge Triggered• A type of
bistable circuit — has two stable states
• Used to
store the state of 1 bit of data
• Changes state on the
rising edge of the clock pulse
Components
| Component | Description |
|---|
| D | Data input |
| CLK | Clock input |
| Q | Output |
| ¬Q | Inverted output (NOT Q) |
Operation
• On the
rising edge of the clock pulse:
- If D = 1: Q goes
high (1) and ¬Q goes
low (0)
- If D = 0: Q goes
low (0) and ¬Q goes
high (1)
• The state of Q
holds (remembers) its value until the next rising clock edge
• You do
not need to recall the internal logic gates that make up a D-type flip-flop
Use Cases
• Forms the basis of most flip-flops and latches
• Used in
shift registers,
counters, and
memory units• Helpful in edge-triggered devices, synchronous circuits, and data storage
Answering Flip-Flop Timing Diagrams
• The output Q wants to
follow the input D• But Q can
only change on the rising edge of the clock pulse
• Between clock edges, Q stays constant regardless of what D does
Adder Circuits
Half Adder
What is a Half Adder?• Basic digital circuit used to add
two single-bit numbers• Has
two inputs: A and B
• Produces
two outputs:
Sum (S) and
Carry out (Cout)Key formulas:•
S = A XOR B•
Cout = A AND BHow to remember the truth table:• Add A and B together as binary numbers
• Write the result as a 2-bit number: the tens bit is Cout, the units bit is S
• e.g. 1+1=2 which is
10 in binary → Cout=1, S=0
Drawing a Half Adder:1. Draw two inputs:
A and
B2. Connect both to an
XOR gate → output is
S (Sum)3. Connect both to an
AND gate → output is
Cout (Carry)
Full Adder
What is a Full Adder?• Extends the half adder to handle
three bits• Has
three inputs: A, B, and
Cin (carry in)
• Produces
two outputs:
Sum (S) and
Carry out (Cout)| A | B | Cin | Cout | S |
|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 |
| 1 | 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 | 1 |
Key formulas:•
S = XOR of inputs A, B, and Cin
•
Cout = TRUE if
at least two of A, B, Cin are TRUE
How to remember the truth table:• Add A + B + Cin together (result can be 0, 1, 2, or 3)
• Write the result as a 2-bit binary number: tens bit = Cout, units bit = S
• e.g. Row 4: 0+1+1=2 =
10 in binary → Cout=1, S=0
• e.g. Last row: 1+1+1=3 =
11 in binary → Cout=1, S=1
Drawing a Full Adder:1. Use
two half adders and one
OR gate2. First half adder: inputs A and B → outputs Sum1 and Carry1
3. Second half adder: inputs Sum1 and Cin → outputs S (final sum) and Carry2
4. OR gate: inputs Carry1 and Carry2 → output is
Cout