Learning Objectives
By the end of this lesson, you will be able to:
- Produce truth tables for logic circuits including half adders and full adders
- Show understanding of flip-flops (SR, JK) and their role as data storage elements
- Understand and apply Boolean algebra rules including De Morgan's laws
- Simplify logic circuits and expressions using Boolean algebra
- Use Karnaugh maps (K-maps) to solve logic problems and simplify expressions
- Draw logic circuits and derive truth tables for flip-flops
- Understand the benefits of using Karnaugh maps for circuit simplification
Key Terms
Boolean Algebra
Mathematics dealing with true/false values (1/0) and logical operations.
Logic Gate
Basic building block of digital circuits (AND, OR, NOT, XOR, NAND, NOR).
Half Adder
Circuit that adds two binary digits producing Sum and Carry outputs.
Full Adder
Circuit that adds three binary digits (including carry-in) producing Sum and Carry-out.
Flip-Flop
Sequential circuit that stores one bit of data (memory element).
Karnaugh Map (K-map)
Graphical method for simplifying Boolean expressions by grouping.
De Morgan's Laws
Boolean algebra rules: ¬(A·B) = ¬A+¬B and ¬(A+B) = ¬A·¬B.
Truth Table
Table showing all possible input combinations and corresponding outputs.
Gray Code
Binary ordering where successive numbers differ by only one bit.
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's the foundation of digital circuit design and computer logic.
Real-life Example: Smart Home Security
Think of a home security system: "Alarm sounds IF (door is open) AND (system is armed) OR (window is broken)". This can be written as a Boolean expression: Alarm = (DoorOpen · SystemArmed) + WindowBroken. Each condition is either true (1) or false (0), and the alarm either sounds (1) or doesn't (0).
Boolean Operators
| Operator | Symbol | Meaning | Example |
|---|---|---|---|
| NOT | ¬A or Ā | Opposite of A | If A=1, then ¬A=0 |
| AND | A·B or A AND B | True only if both are true | 1·1=1, 1·0=0 |
| OR | A+B or A OR B | True if at least one is true | 1+0=1, 0+0=0 |
Boolean Algebra Rules
| Identity/Law | 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·¬A = 0 | A + ¬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) = ¬A + ¬B | ¬(A+B) = ¬A·¬B |
| Double Complement | ¬(¬A) = A | - |
Boolean Algebra Simplification Simulation
Observation: This simulation shows how Boolean expressions can be simplified using algebra rules. The original circuit (left) has multiple gates, while the simplified circuit (right) produces the same output with fewer components. Try different input combinations to verify they give identical outputs.
Check Your Understanding
1. Simplify the Boolean expression: A + B + ¬A + ¬B
Step-by-Step Solution
- Group terms: (A + ¬A) + (B + ¬B)
- Apply inverse law: A + ¬A = 1 and B + ¬B = 1
- Result: 1 + 1
- Apply identity law: 1 + 1 = 1
- Final answer: 1 (Always true regardless of A and B)
2. Apply De Morgan's Law to ¬(A·B)
Explanation
De Morgan's Law states that the complement of an AND operation is equivalent to the OR of the complements.
In words: "NOT (A AND B)" is the same as "(NOT A) OR (NOT B)".
3. What is the result of A·(A+B) using the absorption law?
Solution
The absorption law states that A·(A+B) = A
This makes sense because if A is true, the whole expression is true. If A is false, multiplying by false makes the whole expression false regardless of B.
Logic Circuits
Logic circuits are the physical implementation of Boolean algebra using electronic components called logic gates. These circuits form the basis of all digital computers and electronic devices.
Real-life Example: Calculator Circuits
Every calculator uses logic circuits to perform arithmetic. When you press "5 + 3 =", the calculator uses half adders and full adders to add the binary equivalents (0101 + 0011) and produce the result (1000, which is 8 in decimal). These circuits are made of thousands of tiny logic gates on a silicon chip.
Half Adder Circuit
A half adder is a combinational arithmetic circuit that adds two binary digits (bits). It has two inputs (A and B) and produces two outputs: Sum (S) and Carry (C).
| INPUTS | OUTPUTS | ||
|---|---|---|---|
| A | B | Sum (S) | Carry (C) |
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
Key Insight
Notice that the Sum output is actually an XOR operation (A⊕B), and the Carry output is an AND operation (A·B). So a half adder can be built with just one XOR gate and one AND gate.
Full Adder Circuit
A full adder adds three binary digits: two main inputs (A and B) plus a carry-in (Cin) from a previous addition. It produces Sum (S) and Carry-out (Cout).
| INPUTS | OUTPUTS | |||
|---|---|---|---|---|
| A | B | Cin | Sum (S) | Cout |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
Adder Circuit Simulation
Observation: This simulation shows a full adder circuit. You can toggle the inputs A, B, and Cin and see how the circuit calculates the Sum and Cout. Notice how the circuit is built from two half adders and an OR gate. Try different input combinations and verify they match the truth table above.
Activity 1: Design a Half Adder from NAND Gates
Your task is to complete the truth table for a half adder constructed entirely from NAND gates. The circuit has inputs A and B, and produces outputs Sum (S) and Carry (C).
| A | B | W | X | Y | S (Sum) | C (Carry) |
|---|---|---|---|---|---|---|
| 0 | 0 | |||||
| 0 | 1 | |||||
| 1 | 0 | |||||
| 1 | 1 |
Solution
| A | B | W = NAND(A,B) | X = NAND(A,W) | Y = NAND(W,B) | S = NAND(X,Y) | C = NAND(W,W) |
|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 | 1 | 0 |
| 1 | 1 | 0 | 1 | 1 | 0 | 1 |
Explanation: This demonstrates that NAND gates are functionally complete - you can build any logic circuit using only NAND gates. In fact, most digital chips today use primarily NAND gates because they're simple to manufacture.
Flip-Flops (Sequential Circuits)
Unlike combinational circuits (where output depends only on current inputs), sequential circuits have memory - their output depends on both current inputs AND previous outputs. Flip-flops are the basic building blocks of sequential circuits and computer memory.
Real-life Example: Light Switch Memory
Think of a light switch as a simple memory device. When you flip it up (Set), the light turns ON and stays ON even after you let go. When you flip it down (Reset), it turns OFF and stays OFF. This "remembers" its state. A flip-flop works similarly but with electronic signals instead of mechanical switches.
SR Flip-Flop (Set-Reset)
The SR flip-flop (or "latch") is the simplest sequential circuit. It has two inputs: S (Set) and R (Reset), and two outputs: Q and ¬Q (Q complement, always opposite of Q).
| S | R | Q | ¬Q | Status |
|---|---|---|---|---|
| 1 | 0 | 1 | 0 | Set |
| 0 | 0 | Qprev | ¬Qprev | Hold (Memory) |
| 0 | 1 | 0 | 1 | Reset |
| 1 | 1 | 0 | 0 | Invalid |
Important Note
The invalid state (S=1, R=1) is problematic because it violates the rule that Q and ¬Q should always be opposites. In practice, this state must be avoided. This limitation led to the development of the JK flip-flop.
JK Flip-Flop
The JK flip-flop improves on the SR flip-flop by eliminating the invalid state. It has inputs J (like Set) and K (like Reset), plus a clock input for synchronization.
| J | K | Clock | Qnext | Action |
|---|---|---|---|---|
| 0 | 0 | ↑ | Q | No change |
| 1 | 0 | ↑ | 1 | Set |
| 0 | 1 | ↑ | 0 | Reset |
| 1 | 1 | ↑ | ¬Q | Toggle |
Flip-Flop Simulation
Observation: This simulation shows an SR flip-flop built from NAND gates. Try different S and R inputs. Notice that when both S and R are 0, the flip-flop holds its previous state (memory!). When S=1, R=0, Q becomes 1 (Set). When S=0, R=1, Q becomes 0 (Reset). Avoid S=1, R=1 (invalid state).
Activity 2: Analyze JK Flip-Flop Behavior
A JK flip-flop starts with Q=0. Complete the table below to show how Q changes after each clock pulse with the given J and K inputs.
| Step | J | K | Q before | Clock | Q after | Action |
|---|---|---|---|---|---|---|
| 1 | 1 | 0 | 0 | ↑ | ||
| 2 | 0 | 0 | ↑ | |||
| 3 | 1 | 1 | ↑ | |||
| 4 | 1 | 1 | ↑ |
Solution
| Step | J | K | Q before | Clock | Q after | Action |
|---|---|---|---|---|---|---|
| 1 | 1 | 0 | 0 | ↑ | 1 | Set |
| 2 | 0 | 0 | 1 | ↑ | 1 | No change |
| 3 | 1 | 1 | 1 | ↑ | 0 | Toggle |
| 4 | 1 | 1 | 0 | ↑ | 1 | Toggle |
Explanation: The JK flip-flop's toggle function (J=1, K=1) is its key advantage over the SR flip-flop. This makes JK flip-flops ideal for building counters and frequency dividers in digital circuits.
Karnaugh Maps (K-maps)
A Karnaugh Map is a graphical method for simplifying Boolean expressions by grouping together terms with common factors. It's particularly useful for simplifying expressions with 3-4 variables.
Real-life Example: Simplifying Circuit Design
Imagine designing a circuit for a car's warning system: "Alarm sounds if (door open AND engine on) OR (seatbelt off AND engine on) OR (door open AND seatbelt off)". A K-map helps find the simplest equivalent expression: "Alarm sounds if engine on AND (door open OR seatbelt off)". This simplification uses fewer gates, making the circuit cheaper and more reliable.
K-map Basics
- Number of cells = 2n where n = number of variables
- 3 variables → 8 cells (2×4 grid)
- 4 variables → 16 cells (4×4 grid)
- Variables along edges follow Gray code (only one bit changes between adjacent cells)
- Groups must contain 1, 2, 4, 8, 16... cells (powers of 2)
- Groups can wrap around edges
- Each group corresponds to a simplified product term
3-Variable K-map Example
Simplify the expression: X = ¬A·¬C + B
Truth Table
| A | B | C | X |
|---|---|---|---|
| 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
K-map
Simplified expression: X = B + ¬A·¬C
The vertical group of four 1's corresponds to B (since B=1 for all cells in that group).
The top-left cell (¬A·¬B·¬C) is covered by both groups.
K-map Simplification Simulation
Observation: This interactive K-map lets you click cells to toggle between 0 and 1. Try creating patterns and then click "Group Cells" to see how the simplification works. The algorithm will find the largest possible groups of adjacent 1's (wrapping around edges if helpful) and generate the simplified Boolean expression.
Check Your Understanding
4. How many cells does a 4-variable K-map have?
Explanation
A K-map has 2n cells, where n is the number of variables.
So a 4-variable K-map has 16 cells arranged in a 4×4 grid.
5. Why do K-maps use Gray code ordering instead of binary?
Explanation
Gray code ensures that adjacent cells differ by only one variable. This is crucial for K-maps because:
- Adjacent cells in a K-map should be logically adjacent (differ by one variable)
- This allows grouping cells to eliminate variables
- With binary ordering, adjacent cells might differ by multiple variables
Example: Gray code sequence: 00, 01, 11, 10 (each differs by one bit)
Binary sequence: 00, 01, 10, 11 (01 to 10 differs by two bits)
6. What are the benefits of using K-maps for circuit design?
Key Benefits
- Reduces gate count: Simpler expressions need fewer logic gates
- Lowers power consumption: Fewer gates use less electricity
- Increases speed: Simpler circuits have shorter propagation delays
- Reduces cost: Fewer components means cheaper manufacturing
- Visual approach: Easier to understand than algebraic manipulation
- Systematic method: Provides a clear procedure for simplification
Key Takeaways
- Boolean algebra uses only two values: 1 (true) and 0 (false), with operations NOT, AND, and OR
- Logic gates (AND, OR, NOT, XOR, NAND, NOR) physically implement Boolean operations
- Half adders add two bits producing Sum and Carry; built from XOR and AND gates
- Full adders add three bits (including carry-in); built from two half adders and an OR gate
- Flip-flops are sequential circuits that store one bit of data (memory elements)
- SR flip-flops have Set, Reset, Hold, and Invalid states (S=1, R=1 is invalid)
- JK flip-flops eliminate the invalid state and add Toggle functionality
- De Morgan's Laws are essential for Boolean simplification: ¬(A·B)=¬A+¬B and ¬(A+B)=¬A·¬B
- Karnaugh Maps (K-maps) provide a visual method for simplifying Boolean expressions
- K-maps use Gray code ordering so adjacent cells differ by only one variable
- Circuit simplification reduces gate count, cost, power consumption, and increases speed
- NAND gates are functionally complete - any Boolean function can be implemented using only NAND gates
Question Bank
1. Simplify the Boolean expression A + ¬A·B using Boolean algebra. [3 marks]
Marking Scheme & Answer
- [1 mark] Apply distributive law in reverse: A + ¬A·B = (A + ¬A)·(A + B)
- [1 mark] Apply inverse law: A + ¬A = 1
- [1 mark] Apply identity law: 1·(A + B) = A + B
- [Final answer] A + ¬A·B = A + B
Alternative method: Use absorption law: A + A·B = A, so A + ¬A·B = A + B
2. Complete the truth table for a half adder and explain how it works. [4 marks]
Marking Scheme & Answer
| A | B | Sum (S) | Carry (C) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
- [1 mark] Correct truth table (all 4 rows correct)
- [1 mark] Sum = A XOR B (1 when inputs are different)
- [1 mark] Carry = A AND B (1 only when both inputs are 1)
- [1 mark] Explanation: Adds two binary digits, output is 2-bit result (Carry, Sum)
3. Describe the four states of an SR flip-flop and explain the invalid state. [4 marks]
Marking Scheme & Answer
- [1 mark] Set state (S=1, R=0): Q becomes 1, ¬Q becomes 0
- [1 mark] Reset state (S=0, R=1): Q becomes 0, ¬Q becomes 1
- [1 mark] Hold state (S=0, R=0): Q retains previous value (memory)
- [1 mark] Invalid state (S=1, R=1): Both Q and ¬Q become 0, violating the rule that they should be complements. This state must be avoided.
Note: The invalid state problem in SR flip-flops led to the development of JK flip-flops which eliminate this issue.
4. Apply De Morgan's Law to simplify ¬(A + B·C). [3 marks]
Marking Scheme & Answer
- [1 mark] Apply De Morgan's Law to outer NOT: ¬(A + B·C) = ¬A · ¬(B·C)
- [1 mark] Apply De Morgan's Law to inner NOT: ¬(B·C) = ¬B + ¬C
- [1 mark] Final simplified expression: ¬A · (¬B + ¬C)
Verification: This can be further simplified to ¬A·¬B + ¬A·¬C using the distributive law, but the question only asks for De Morgan's application.
5. Explain the difference between combinational and sequential circuits. [3 marks]
Marking Scheme & Answer
Combinational Circuits:
- Output depends ONLY on current inputs
- No memory elements
- Examples: Adders, multiplexers, decoders
- Built from logic gates only
Sequential Circuits:
- Output depends on current inputs AND previous state
- Contains memory elements (flip-flops)
- Examples: Flip-flops, counters, registers
- Built from logic gates AND flip-flops
[1 mark] Correct definition of combinational circuits
[1 mark] Correct definition of sequential circuits
[1 mark] Clear distinction with examples
6. Draw the truth table for a full adder and derive the Boolean expressions for Sum and Carry-out. [5 marks]
Marking Scheme & Answer
| A | B | Cin | Sum | Cout |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
- [2 marks] Correct truth table (all 8 rows)
- [1.5 marks] Sum expression: S = A ⊕ B ⊕ Cin (XOR of all three inputs)
- [1.5 marks] Carry-out expression: Cout = A·B + B·Cin + A·Cin (OR of three AND pairs)
Alternative Cout expression: Cout = (A⊕B)·Cin + A·B (using XOR for the first term)
7. What is Gray code and why is it used in K-maps? [3 marks]
Marking Scheme & Answer
- [1 mark] Definition: Gray code is an ordering of binary numbers where successive numbers differ by only one bit
- [1 mark] Example: 00, 01, 11, 10 (not 00, 01, 10, 11)
- [1 mark] Use in K-maps: Ensures adjacent cells in the K-map are logically adjacent (differ by only one variable), which allows proper grouping for simplification
Key point: Without Gray code, cells that appear physically adjacent in the K-map might differ by multiple variables, making them unsuitable for grouping together.
8. Compare SR and JK flip-flops, highlighting advantages of JK. [4 marks]
Marking Scheme & Answer
SR Flip-Flop:
- Inputs: S (Set) and R (Reset)
- Invalid state: S=1, R=1
- Four states: Set, Reset, Hold, Invalid
- No toggle function
JK Flip-Flop:
- Inputs: J (like S) and K (like R)
- No invalid state (J=1, K=1 is toggle)
- Four states: Set, Reset, Hold, Toggle
- Includes clock input for synchronization
Advantages of JK flip-flop:
- [1 mark] Eliminates invalid state problem
- [1 mark] Adds toggle function (J=1, K=1 makes output complement itself)
- [1 mark] More versatile for building counters and shift registers
- [1 mark] Clock input allows synchronous operation
9. Use a K-map to simplify F(A,B,C) = Σm(0, 2, 4, 6). [5 marks]
Marking Scheme & Answer
Σm(0, 2, 4, 6) means minterms where function F = 1 at binary equivalents:
- 0 = 000 (¬A·¬B·¬C)
- 2 = 010 (¬A·B·¬C)
- 4 = 100 (A·¬B·¬C)
- 6 = 110 (A·B·¬C)
- [1 mark] Correct K-map with 1's in cells 0, 2, 4, 6
- [2 marks] Grouping: Two groups of two 1's each (vertical pairs)
- [1 mark] First group (columns 00): ¬C (since C=0 for both cells)
- [1 mark] Second group (columns 10): Also ¬C (since C=0 for both cells)
- [Final answer] F = ¬C
Explanation: Notice that all 1's are in columns where C=0. The function is independent of A and B, so F = ¬C.
10. Explain the role of flip-flops in computer memory and give two applications. [4 marks]
Marking Scheme & Answer
- [2 marks] Role in computer memory: Flip-flops are the basic storage elements that can remember/store one bit of data. Multiple flip-flops combined form registers (e.g., 8 flip-flops = 8-bit register), and many registers form memory. They maintain their state (0 or 1) until explicitly changed, providing volatile storage.
- [1 mark] Application 1: Registers in CPU - Store data, instructions, addresses temporarily during processing
- [1 mark] Application 2: Counters - Multiple JK flip-flops can be connected to create binary counters that count clock pulses
Other applications: Shift registers (serial-to-parallel conversion), memory cells in RAM, frequency dividers, state machines. Each flip-flop stores one bit, so 1KB of memory requires 8192 flip-flops.