Produce truth tables for logic circuits including half adders and full adders
Show understanding of flip-flops (SR, JK) and draw logic circuits for them
Understand the role of flip-flops as data storage elements
Show understanding of Boolean algebra and apply De Morgan's laws
Simplify logic circuits/expressions using Boolean algebra
Show understanding of Karnaugh maps (K-maps) and their benefits
Solve logic problems using Karnaugh maps
🌟 Prior Knowledge Required
Understanding of logic gates: NOT, AND, OR, NAND, NOR, XOR
Ability to construct truth tables for simple logic circuits
Knowledge of binary number system and binary addition
Understanding of Boolean operators and basic logic circuit design
Familiarity with truth table construction for multiple inputs
📖 What is Boolean Algebra?
Boolean algebra is a form of mathematics that deals with statements and their Boolean values. In Boolean algebra, variables and functions take on one of two values: TRUE (1) or FALSE (0). It is named after the mathematician George Boole and is based on logical operations.
1. Boolean Operators and Notation
The notation used to represent Boolean operators follows standard conventions that map directly to logic gates:
📖 Boolean Operators
Ā or NOT A or A' - Inverts the value (NOT gate)
A.B or A AND B - Both must be true (AND gate)
A+B or A OR B - At least one must be true (OR gate)
1.1 Boolean Algebra Laws
Boolean algebra follows specific laws that allow us to simplify and manipulate expressions. Understanding these laws is crucial for exam success.
Law Name
AND Form
OR Form
Identity
1.A = A
0+A = A
Null
0.A = 0
1+A = 1
Idempotent
A.A = A
A+A = A
Inverse
A.Ā = 0
A+Ā = 1
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
(A.B)' = Ā + B̄
(A+B)' = Ā.B̄
💡 Important Rule to Remember
In Boolean algebra: 1 + 1 = 1, 1 + 0 = 1, and Ā̄ = A (double complement). These follow directly from logic gate truth tables you studied previously!
2. Boolean Algebra Simplification
Simplifying Boolean expressions is a key skill. The goal is to reduce the number of gates needed to implement a logic circuit.
📝 Example 1: Simplify A + B + Ā + B̄
Solution:
Using associative laws: A + B + Ā + B̄ = (A + Ā) + (B + B̄)
Factor out common terms: B.C.(Ā + A) + B.C̄.(Ā + A)
Since Ā + A = 1: B.C.1 + B.C̄.1
Simplify: B.C + B.C̄ = B.(C + C̄)
Since C + C̄ = 1: Final Answer: B
📝 Example 3: Simplify A + Ā.B
Solution:
Start with: A + Ā.B
Expand using: A = A + A.B (absorption law in reverse)
A + Ā.B = A + A.B + Ā.B
Factor B from last two terms: A + B.(A + Ā)
Since A + Ā = 1: Final Answer: A + B
💡 Exam Strategy
When simplifying, sometimes you need to make the expression MORE complex first before simplifying. Use the absorption law in reverse: A = A + A.B to introduce terms that can then be combined with other parts of the expression.
⚠️ Proof of De Morgan's Laws
De Morgan's Laws can be proven using truth tables. If the last two columns of each truth table are identical, the laws hold true:
(A.B)' = Ā + B̄ and (A+B)' = Ā.B̄
3. Half Adder Circuit
A half adder is a basic digital circuit used to perform addition of two single-bit numbers. It produces two outputs: the Sum and the Carry.
📖 Half Adder Characteristics
Has two inputs: A and B (the two bits to add)
Produces two outputs: Sum (S) and Carry (Cout)
Sum is produced using XOR gate: S = A XOR B
Carry is produced using AND gate: Cout = A AND B
3.1 Half Adder Truth Table
A
B
Cout (Carry)
S (Sum)
0
0
0
0
0
1
0
1
1
0
0
1
1
1
1
0
📝 How to Read the Truth Table
Remember: You are adding A and B together. The result is written as a 2-bit binary number with Carry as the most significant bit.
The half adder can only add TWO bits. It has no carry input - this is why it's called a "half" adder. If you need to add multiple bits (like in multi-digit addition), you need a full adder.
4. Full Adder Circuit
A full adder extends the half adder to handle the addition of three bits - two input bits plus a carry from a previous addition.
📖 Full Adder Characteristics
Has three inputs: A, B, and Cin (carry from previous stage)
Produces two outputs: Sum (S) and Carry (Cout)
Can be built using two half adders and an OR gate
Used for adding multi-bit binary numbers
4.1 Full Adder Truth Table
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
📝 How to Read Full Adder Truth Table
Add A + B + Cin for each row. The result (0-3) is written as 2-bit binary:
Row 4: 0+1+1=2 → binary "10" → Cout=1, S=0
Row 8: 1+1+1=3 → binary "11" → Cout=1, S=1
🌟 Did You Know?
Multiple full adders can be chained together to add multi-bit numbers! For example, four full adders connected in series can add two 4-bit binary numbers. The carry output from each stage becomes the carry input to the next stage.
5. Flip-Flop Circuits
Flip-flops are sequential logic circuits that can store one bit of data. Unlike combinational circuits (like adders), flip-flops have memory - their output depends on both current inputs AND previous states.
📖 Key Concepts
Combinational circuits: Output depends ONLY on current inputs
Sequential circuits: Output depends on inputs AND previous states
Flip-flops are bistable - they have two stable states (0 and 1)
They are used in counters, control systems, and memory registers
Often edge-triggered (respond to clock signal changes)
5.1 SR Flip-Flop
The SR flip-flop (Set-Reset) is the simplest type. It can be constructed using two cross-coupled NOR gates (or NAND gates).
S (Set)
R (Reset)
Q (next state)
Description
0
0
No change
Memory/Hold state
0
1
0
Reset state
1
0
1
Set state
1
1
0*
Invalid (NOR only)
⚠️ Important Note
In NOR-based SR flip-flops, S=1 and R=1 is NOT invalid - it forces Q=0. In NAND-based designs, this state produces undefined behavior. Always check which gate type is being used in exam questions!
6. JK Flip-Flop
The JK flip-flop is an improved version of the SR flip-flop that solves the invalid state problem by introducing a toggle function.
📖 Problems with SR Flip-Flop
Invalid S=1, R=1 condition leads to conflicting outputs
If inputs don't arrive simultaneously, circuit becomes unstable
No clock synchronization - can change at any time
J
K
Q (next)
Description
0
0
No change
Memory/Hold
0
1
0
Reset
1
0
1
Set
1
1
Q̄ (Toggle)
Output switches!
💡 The Toggle Feature
When J=1 and K=1, the output toggles - it changes from 0 to 1 or from 1 to 0. This is the key difference from SR flip-flop and allows JK flip-flops to be used as counters and frequency dividers!
6.1 SR vs JK Comparison
Feature
SR Flip-Flop
JK Flip-Flop
Invalid State
S=1, R=1 causes issues
J=1, K=1 causes toggle
Clock Required
No (asynchronous)
Yes (synchronous)
Timing Issues
Can be unstable
Synchronized, stable
Common Uses
Simple memory, control
Counters, shift registers
🧠 Memory Trick: JK States
J=0, K=0 = "Just Keep" (no change)
J=0, K=1 = "Kill" (reset to 0)
J=1, K=0 = "Jump" (set to 1)
J=1, K=1 = "Juggle" (toggle back and forth)
7. Karnaugh Maps (K-Maps)
Karnaugh maps provide a visual method for simplifying Boolean expressions without complex algebra. They are faster and less error-prone than Boolean algebra simplification.
📖 What are K-Maps?
A graphical representation of truth tables
Uses Gray code ordering (adjacent cells differ by one bit)
Groups of 1s are identified to simplify expressions
Best for 2-4 variables; more complex for 5+ variables
🌟 Gray Code
Gray code is an ordering of binary numbers where successive values differ by only ONE bit. Example: 00 → 01 → 11 → 10 (not 00 → 01 → 10 → 11). This ensures adjacent cells in a K-map are always related by a single variable change.
7.1 K-Map Rules
📝 Essential K-Map Rules
Values along top and side follow Gray code rules
Only cells containing 1 are considered (for SOP form)
Groups can be a row, column, or rectangle
Groups must contain powers of 2 cells (1, 2, 4, 8, 16...)
Groups should be as large as possible
Groups can overlap
NO diagonal grouping allowed
Corner cells are considered adjacent (wrap-around)
8. 3-Variable and 4-Variable K-Maps
8.1 3-Variable K-Map
A 3-variable K-map has 8 cells (2³ = 8). One variable is on the left, two variables on top.
8.2 4-Variable K-Map
A 4-variable K-map has 16 cells (2⁴ = 16). Two variables on left, two on top.
💡 K-Map Simplification Process
Fill in 1s and 0s from truth table
Group adjacent 1s (powers of 2: 1, 2, 4, 8)
Make groups as large as possible
Groups can overlap - that's okay!
For each group, identify variables that stay constant
Combine group terms with OR (+) for final expression
⚠️ Key Insight
When grouping, look for variables that DON'T change within the group. Those are the variables that appear in your simplified expression. Variables that change (0→1 or 1→0) are eliminated.
9. K-Map Worked Examples
📝 Example: Simplify using K-Map
Truth Table: Output = 1 when inputs are: 011, 101, 110, 111
Sum of Products: ĀBC + AB̄C + ABC̄ + ABC
K-Map grouping:
Group 1: Cells 011 and 111 → B·C (A changes, eliminated)
Group 2: Cells 101 and 111 → A·C (B changes, eliminated)
Group 3: Cells 110 and 111 → A·B (C changes, eliminated)
Final Answer:B·C + A·C + A·B
❌ Common Mistakes in K-Maps
Using binary order instead of Gray code (00, 01, 10, 11 is WRONG!)
Creating diagonal groups (NOT allowed!)
Forgetting that corners are adjacent (wrap-around)
Not making groups as large as possible
Missing the overlap between groups
10. Exam-Style Questions (Part 1)
1. Simplify the following Boolean expression using Boolean algebra: A + B + Ā + B̄ [3 marks]
Answer:
Using associative laws: A + B + Ā + B̄ = (A + Ā) + (B + B̄)
Using inverse laws: (A + Ā) = 1 and (B + B̄) = 1
Therefore: 1 + 1 = 1
Final Answer: 1
Additional points for deeper understanding:
This expression always evaluates to TRUE regardless of input values
This represents a circuit that is always "ON"
No logic gates needed - just connect to logic 1 (high)
2. Complete the truth table for a half adder circuit and explain how the Sum and Carry outputs are derived. [6 marks]
Answer:
A
B
Sum
Carry
0
0
0
0
0
1
1
0
1
0
1
0
1
1
0
1
Sum = A XOR B (outputs 1 when inputs are different)
Carry = A AND B (outputs 1 only when both inputs are 1)
The truth table represents binary addition: 0+0=0, 0+1=1, 1+0=1, 1+1=10
Additional points:
Half adder cannot handle carry from previous stage
Full adder needed for multi-bit addition
Half adder uses just 2 gates: one XOR and one AND
3. Draw a logic circuit for an SR flip-flop using NOR gates and label all inputs and outputs. [5 marks]
Answer:
Draw two NOR gates cross-coupled
Inputs: S (Set) and R (Reset)
Outputs: Q and Q̄ (inverse of Q)
The output of each NOR gate feeds back as input to the other gate
This cross-coupling creates the memory effect
Additional points:
When S=1, R=0: Q=1 (Set state)
When S=0, R=1: Q=0 (Reset state)
When S=0, R=0: No change (Memory state)
In NOR-based SR: S=1, R=1 forces Q=0 (not invalid)
4. Use De Morgan's Laws to simplify: (A + B)̄ [4 marks]
Answer:
Apply De Morgan's second law: (A + B)̄ = Ā · B̄
Break the bar, change the sign: OR becomes AND
Each variable gets its own NOT
Final Answer: Ā · B̄
Additional points:
This is equivalent to a NOR gate = two inverted inputs through AND
Can prove using truth table - both expressions give same output
De Morgan's Laws are fundamental for circuit conversion
5. Explain the difference between a half adder and a full adder. Give one use for each. [5 marks]
Answer:
Feature
Half Adder
Full Adder
Inputs
2 (A, B)
3 (A, B, Cin)
Outputs
2 (Sum, Carry)
2 (Sum, Carry)
Carry Input
No
Yes
Gates Used
XOR + AND
2 Half Adders + OR
Half adder use: Adding the least significant bits (no carry in)
Full adder use: Adding all other bits in multi-bit addition
Additional points:
Full adders can be cascaded for multi-bit addition
Both produce same outputs when Cin=0
ALU uses both types for arithmetic operations
10. Exam-Style Questions (Part 2)
6. Complete the truth table for a JK flip-flop and explain what happens when J=1 and K=1. [5 marks]
Answer:
J
K
Q (next)
Description
0
0
No change
Memory/Hold
0
1
0
Reset
1
0
1
Set
1
1
Q̄
Toggle
When J=1 and K=1, the output toggles
Toggle means Q changes to its opposite value (0→1 or 1→0)
This solves the invalid state problem of SR flip-flop
Additional points:
Toggle function allows JK flip-flop to be used as a counter
Multiple JK flip-flops connected can create binary counters
The clock signal synchronizes the toggle action
7. Using a Karnaugh map, simplify: X = ĀB̄C + ĀBC + AB̄C + ABC [6 marks]
Answer:
Place 1s in cells corresponding to: 001, 011, 101, 111
Group 1: Cells 001 and 101 (column 01) → B̄·C (A changes, eliminated)
Group 2: Cells 011 and 111 (column 11) → B·C (A changes, eliminated)
Final Answer: B̄·C + B·C = C
Additional points:
Can also group all four 1s as one rectangle: just C remains
This is much simpler than algebraic simplification
K-map gives optimal solution with minimum gates
Only need one wire to input C - no gates required!
8. Explain why flip-flops are important in computer memory. [4 marks]
Answer:
Flip-flops can store one bit of data (0 or 1)
They are bistable - have two stable states
The stored value can be read without changing it
Multiple flip-flops can form registers and memory cells
Additional points:
RAM chips use flip-flop-based circuits for storage
CPU registers are built from flip-flops
SR flip-flops are simpler but JK flip-flops are more versatile
Cache memory often uses flip-flop based SRAM
Flip-flops enable sequential logic and state machines