Welcome to the Logic of Machines!
Welcome! In this chapter, we are going to dive into Boolean Algebra. If you’ve ever wondered how a computer — which is essentially just a collection of switches — can perform complex tasks like playing a video or calculating your taxes, the answer lies here. Boolean Algebra is the mathematical system used to represent the logic inside a computer’s processor.
Don’t worry if math isn't your favourite subject. Unlike the math you do in school with infinite numbers, Boolean Algebra only uses two: 1 (True) and 0 (False). By the end of these notes, you’ll be able to simplify complex logic problems just like a CPU does!
1. The Building Blocks: Logic Gates and Truth Tables
Before we can do "algebra," we need to understand the basic operations. In standard math, you have +, -, and \(\times\). In Boolean logic, we have Logic Gates.
The Big Three
1. NOT (Negation): This simply flips the input. If you give it a 1, it gives you a 0.
Analogy: The "Opposite Day" gate.
Symbol: \(\neg A\) or \(\overline{A}\)
2. AND (Conjunction): The output is only 1 if BOTH inputs are 1.
Analogy: To go on a school trip, you need a signed permission slip AND a paid deposit. If one is missing, you aren't going!
Symbol: \(A \cdot B\) or \(A \wedge B\)
3. OR (Disjunction): The output is 1 if AT LEAST ONE input is 1.
Analogy: To get into a movie, you can show a digital ticket OR a paper ticket. Either one works!
Symbol: \(A + B\) or \(A \vee B\)
The Exclusive Gate
XOR (Exclusive OR): The output is 1 if the inputs are different (one is 1, the other is 0). If both are the same, the output is 0.
Analogy: A "One or the other, but not both" rule.
Symbol: \(A \oplus B\)
Quick Review: Truth Tables
A Truth Table is just a list of every possible input and what the resulting output will be. When drawing these, always count in binary (00, 01, 10, 11) to make sure you don't miss any combinations!
Key Takeaway: Logic gates are the "physical" version of Boolean operations. Truth tables are the map of how they behave.
2. Simplifying Logic: The Rules of the Game
Computers want to be efficient. If a logic circuit is messy, it uses more electricity and generates more heat. We use Boolean Identities to simplify expressions (make them smaller).
The Basic Rules
- Commutation: The order doesn't matter. \(A + B\) is the same as \(B + A\).
- Association: The grouping doesn't matter for the same operation. \((A + B) + C\) is the same as \(A + (B + C)\).
- Double Negation: Two NOTs cancel out. \(\overline{\overline{A}} = A\). (Like saying "I'm not not going" — it means you are going!)
- Distribution: This works like brackets in algebra. \(A \cdot (B + C) = (A \cdot B) + (A \cdot C)\).
De Morgan’s Laws (The Exam Favourite!)
This is the most important rule to learn for your OCR exam. It’s used to change an AND expression into an OR expression (or vice-versa).
The Rule: \(\overline{A \cdot B} = \overline{A} + \overline{B}\) AND \(\overline{A + B} = \overline{A} \cdot \overline{B}\)
Memory Aid: "Break the bar, change the sign."
If you have a long "NOT" bar over an expression, you can break it into two smaller bars, but you must flip the symbol (AND becomes OR, OR becomes AND).
Key Takeaway: Simplifying expressions makes circuits faster and cheaper to build. De Morgan's Law is your best friend for long "NOT" bars.
3. Karnaugh Maps (K-Maps)
If the algebra rules feel too confusing, Karnaugh Maps are a visual way to simplify logic. It’s like a puzzle where you group 1s together.
How to build a K-Map:
- Create a grid based on your inputs.
- Crucial Step: Use Gray Code for the headings. This means only one bit changes at a time (00, 01, 11, 10). Notice how 11 comes before 10!
- Fill the grid with 1s and 0s from your truth table.
- Circle the 1s: Group them in rectangles or squares of 1, 2, 4, or 8. You want the biggest groups possible!
- Find the survivors: Look at a group. If a variable changes (e.g., \(A\) is 0 for one part of the group but 1 for another), it is discarded. Only the variables that stay the same for the whole group make it into your final answer.
Common Mistake: Never circle a group of 3! Groups must always be a power of 2.
Key Takeaway: K-Maps are great for visual learners. They turn messy truth tables into simple equations by grouping "1" results together.
4. Circuitry: Adders and Flip-Flops
Now we see how this logic actually builds components.
Half Adders vs. Full Adders
How does a computer add numbers? It uses these circuits:
- Half Adder: Adds two bits (\(A\) and \(B\)). It has two outputs: Sum (calculated using an XOR gate) and Carry (calculated using an AND gate).
- Full Adder: This is better. It adds three bits: \(A\), \(B\), and a Carry In from a previous calculation. This allows us to chain them together to add large numbers.
The D-Type Flip-Flop
Logic gates usually just react to inputs immediately. But computers need memory. The D-Type Flip-Flop is a circuit that can store 1 bit of data.
- It has a Data input and a Clock input.
- The value at the Data input is only stored when the Clock "ticks" (usually on the rising edge).
- It "flips" or "flops" between states and stays that way until the next clock pulse.
Analogy: Imagine a camera. The Data input is what you are looking at, and the Clock is the shutter button. The "memory" is the photo that stays there even if you move the camera, until you press the button again.
Key Takeaway: Adders do the math; Flip-Flops are the most basic form of memory (RAM).
Quick Summary Checklist
Before you sit your exam, make sure you can:
- Draw Truth Tables for AND, OR, NOT, and XOR.
- Apply De Morgan’s Law (Break the bar, change the sign!).
- Simplify an expression using Distribution and Association.
- Fill a K-Map using Gray Code (00, 01, 11, 10).
- Explain the difference between a Half and Full Adder.
- Describe how a D-Type Flip-Flop uses a clock signal to store data.
Did you know? Boolean Algebra is named after George Boole, a self-taught mathematician from the 1800s. He invented this system long before electronic computers even existed!