IGCSE Computer Science (0478): Comprehensive Study Notes – Boolean Logic (Topic 10)
Hello! Welcome to the exciting world of Boolean Logic. Don't worry if the name sounds complicated; it’s actually the simplest form of mathematics because it only deals with two values: TRUE or FALSE. Every decision a computer makes, from opening an app to running a self-driving car, boils down to these simple logical choices. Understanding this chapter is key to knowing how hardware actually thinks!
In this section, we will learn about the basic building blocks of digital systems: Logic Gates.
1. The Fundamentals of Boolean Algebra
What is Boolean Logic?
Boolean logic (or Boolean Algebra) is a system of logic named after mathematician George Boole. It is the foundation of all digital electronics and computer processing.
- It uses only two states: TRUE or FALSE.
- In computer science, these states are represented by Binary Digits:
- TRUE is usually represented by the binary value 1 (or "ON" / High voltage).
- FALSE is usually represented by the binary value 0 (or "OFF" / Low voltage).
Did you know?
Logic gates are physically implemented in the CPU using tiny components called transistors. Millions of these transistors work together based on Boolean logic!
Key Takeaway:
Boolean logic is the math of decision-making, using only 1 (TRUE) or 0 (FALSE).
2. Defining the Standard Logic Gates
A Logic Gate is a physical component that takes one or more binary inputs and produces a single binary output based on a specific logical rule.
The IGCSE syllabus requires you to know six standard gates, plus one variation (XOR/EOR). All gates, except NOT, are usually limited to two inputs in theory, though circuits you draw may have up to three inputs overall.
2.1 The Core Gates (NOT, AND, OR)
A) NOT Gate (The Inverter)
The NOT gate is the simplest gate, as it only has one input. It reverses the input signal.
- Definition: The output is TRUE (1) if the input is NOT TRUE (0), and vice versa.
- Logic Expression: NOT A (or \(\bar{A}\))
- Symbol Description (See Syllabus Page 34): A triangle with a small circle (inversion bubble) on the output line.
Truth Table (NOT):
| A (Input) | Output X |
|---|---|
| 0 | 1 |
| 1 | 0 |
Analogy: If the traffic light is NOT green (0), the output is stop (1).
B) AND Gate
The AND gate requires all inputs to be TRUE to produce a TRUE output.
- Definition: The output is TRUE (1) only if Input A AND Input B are TRUE.
- Logic Expression: A AND B
- Symbol Description (See Syllabus Page 34): A 'D' shape.
Truth Table (AND):
| A | B | Output X |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Memory Aid: Think of multiplication. 0 x 0 = 0, 1 x 0 = 0, 1 x 1 = 1.
C) OR Gate
The OR gate requires at least one input to be TRUE to produce a TRUE output.
- Definition: The output is TRUE (1) if Input A OR Input B (or both) are TRUE.
- Logic Expression: A OR B
- Symbol Description (See Syllabus Page 34): A curved shield shape with a concave input side.
Truth Table (OR):
| A | B | Output X |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Memory Aid: Think of addition (except 1+1 stays 1).
2.2 Derived Gates (NAND, NOR, XOR/EOR)
D) NAND Gate (NOT AND)
The NAND gate is the opposite of the AND gate. The output is FALSE only if all inputs are TRUE.
- Logic Expression: NOT (A AND B)
- Symbol Description: The AND symbol with a small circle (inversion bubble) on the output line.
E) NOR Gate (NOT OR)
The NOR gate is the opposite of the OR gate. The output is TRUE only if all inputs are FALSE.
- Logic Expression: NOT (A OR B)
- Symbol Description: The OR symbol with a small circle (inversion bubble) on the output line.
F) XOR / EOR Gate (Exclusive OR)
The XOR gate outputs TRUE only if the inputs are different.
- Definition: The output is TRUE (1) if Input A is TRUE OR Input B is TRUE, BUT NOT BOTH.
- Logic Expression: A XOR B
- Symbol Description: The OR symbol, but with an extra curved line drawn on the input side.
Truth Table (XOR):
| A | B | Output X |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Quick Review Box:
Key Gate Definitions:
AND: Requires ALL inputs (1, 1 -> 1)
OR: Requires AT LEAST ONE input (0, 1 -> 1)
XOR: Requires EXACTLY ONE input (1, 0 -> 1)
NOT: Flips the input (1 -> 0)
3. Working with Logic Circuits and Expressions
In the exam, you must be able to move between three formats: Problem Statements, Logic Expressions, and Logic Circuits.
3.1 Logic Expressions (Writing the Formula)
A logic expression is a formal way of writing down the relationship between inputs (A, B, C...) and the final output (X).
Example: "The alarm (X) will sound if the door sensor (A) is activated AND the window sensor (B) is activated, OR if the main power (C) is OFF."
Step 1: Assign variables and identify operations.
- A = Door sensor, B = Window sensor, C = Main Power.
- "A AND B"
- "C is OFF" means NOT C.
- The overall link is OR.
Step 2: Write the expression.
X = (A AND B) OR (NOT C)
Always use parentheses (brackets) to show which operations are performed first (like in normal algebra). The NOT operation often applies only to the variable immediately following it.
3.2 Drawing Logic Circuits
To draw a circuit from an expression, start from the variables on the left and work towards the final output on the right.
Expression: X = (A AND B) OR (NOT C)
Step-by-step Circuit Construction:
- Draw Input lines for A, B, and C on the left.
- The first operation is (A AND B). Connect A and B to an AND Gate. The output of this gate is your first temporary result (let's call it T1).
- The second operation is (NOT C). Connect C to a NOT Gate. The output of this gate is T2.
- The final operation is T1 OR T2. Connect the output of the AND gate (T1) and the output of the NOT gate (T2) to an OR Gate.
- The output of the OR gate is the final output, X.
Note: The syllabus requires circuits to be drawn without simplification, meaning you must use the gates exactly as specified in the problem statement or expression.
Common Mistake to Avoid:
When drawing circuits, make sure that lines connecting inputs to a gate are clearly marked with a dot (junction) where they join. If lines cross without a dot, they are not connected.
Key Takeaway:
When writing expressions or drawing circuits, break the problem down into small, manageable gates (AND/OR/NOT) and always use brackets to clarify the order of operations.
4. Truth Tables (The Decision Map)
A Truth Table is essential for testing and documenting a logic circuit or expression. It lists all possible combinations of inputs and shows the resulting output.
4.1 Determining the Number of Rows
The number of rows needed in a truth table depends on the number of inputs:
- If you have n inputs, you need \(2^n\) rows.
- 1 input (A) = \(2^1\) = 2 rows (0, 1)
- 2 inputs (A, B) = \(2^2\) = 4 rows (00, 01, 10, 11)
- 3 inputs (A, B, C) = \(2^3\) = 8 rows (000 to 111)
The IGCSE syllabus limits circuits to a maximum of three inputs, so your largest table will have 8 rows.
4.2 Completing a Truth Table (Step-by-Step)
Let's complete the truth table for the expression: X = (A AND B) OR (NOT C)
Step 1: Set up the inputs (8 rows needed for 3 inputs).
| A | B | C | T1 (A AND B) | T2 (NOT C) | X = T1 OR T2 |
|---|---|---|---|---|---|
| 0 | 0 | 0 | |||
| 0 | 0 | 1 | |||
| 0 | 1 | 0 | |||
| 0 | 1 | 1 | |||
| 1 | 0 | 0 | |||
| 1 | 0 | 1 | |||
| 1 | 1 | 0 | |||
| 1 | 1 | 1 |
Step 2: Calculate intermediate columns (T1 and T2).
- T1 (A AND B): T1 is only 1 when both A and B are 1. (Rows 7 and 8)
- T2 (NOT C): T2 is the opposite of C.
Step 3: Calculate the final output (X).
- X = T1 OR T2: X is 1 if T1 is 1 OR if T2 is 1 (or both).
Completed Truth Table:
| A | B | C | T1 (A AND B) | T2 (NOT C) | X = T1 OR T2 |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 1 |
| 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 | 1 |
Key Takeaway:
Always use intermediate columns (T1, T2, etc.) in your truth table calculations. This makes the process clear and reduces errors, especially for complex expressions.
5. Deriving Expressions from Truth Tables or Circuits
Sometimes you will be given a complete Truth Table or a Logic Circuit and asked to write the corresponding Logic Expression.
5.1 Writing an Expression from a Truth Table
The easiest way to write an expression is to focus only on the rows where the Output is TRUE (1).
Using the example table above, the output X is 1 in rows 1, 3, 5, 7, and 8.
Step 1: Identify the inputs that lead to a TRUE output (1).
- Row 1: A=0, B=0, C=0. This corresponds to: (NOT A) AND (NOT B) AND (NOT C)
- Row 3: A=0, B=1, C=0. This corresponds to: (NOT A) AND B AND (NOT C)
- Row 5: A=1, B=0, C=0. This corresponds to: A AND (NOT B) AND (NOT C)
- Row 7: A=1, B=1, C=0. This corresponds to: A AND B AND (NOT C)
- Row 8: A=1, B=1, C=1. This corresponds to: A AND B AND C
Step 2: Combine all these possibilities using OR.
X = ((NOT A) AND (NOT B) AND (NOT C)) OR ((NOT A) AND B AND (NOT C)) OR (A AND (NOT B) AND (NOT C)) OR (A AND B AND (NOT C)) OR (A AND B AND C)
Don't worry about simplifying this expression unless specifically asked (which is typically outside the scope of the IGCSE core curriculum). Just list all the TRUE combinations connected by ORs.
5.2 Writing an Expression from a Logic Circuit
To write an expression from a circuit, start at the gates closest to the inputs and work your way to the final output.
Example Process:
- Name the inputs (A, B, C...).
- Look at the first layer of gates (closest to the inputs) and write down their intermediate expressions (e.g., T1 = NOT A).
- Look at the second layer of gates. Use the intermediate results as their inputs (e.g., if a gate receives B and T1, its output T2 = B OR T1).
- Continue until you reach the final output (X), and substitute all intermediate variables back into the final expression.
Don't worry if this seems tricky at first! Practice drawing circuits and filling tables, and the relationship between the expression and the visual circuit will become second nature.
6. Real-World Application of Logic Gates
Logic circuits are everywhere, controlling simple automated systems that need to make basic decisions based on inputs (like sensors).
Scenario: A Central Heating System
A central heating furnace (X) should turn ON if the thermostat (T) senses the temperature is too low (T=1), AND if the system timer (S) is currently set to an 'ON' time (S=1). Additionally, the furnace should immediately turn OFF if the safety switch (F) is activated (F=1).
- Inputs: T (Thermostat Low), S (Timer ON), F (Safety Switch Activated).
- Desired Output: X (Furnace ON).
Analysis:
- T and S must both be 1, so we need an AND gate.
- The safety switch F must stop the furnace. If F=1, X must be 0, regardless of T and S. This means the final output must be ANDed with NOT F.
Logic Expression:
X = (T AND S) AND (NOT F)
This simple application shows how logic gates ensure safety and functionality in automated processes, turning complex requirements into simple binary conditions.
Final Key Takeaway:
Boolean logic is the core language of computer hardware. Master the symbols, definitions, and the process of converting between truth tables, expressions, and circuits—this is crucial for exam success in Topic 10!