Boolean Algebra Revision Notes for AQA A-Level Computer Science

Boolean Algebra

Introduction to Boolean algebra

Boolean algebra is a mathematical system named after George Boole, who developed it in the mid-1800s. It's a fundamental concept in computer science because it allows us to work with logical expressions that evaluate to one of two possible values: TRUE or FALSE. This binary nature makes Boolean algebra perfect for representing how digital circuits and computer processors work.

infoNote

The key principle is that logical expressions can produce one of two outcomes, which directly relates to how computers process information using binary digits. In Boolean algebra, we represent these two states using:

1 represents TRUE (the statement or condition is true)
0 represents FALSE (the statement or condition is false)

For example, if we have the Boolean expression "The button has been pressed", we can represent this as a variable $A$ where:

$A = 1$ means the button has been pressed (TRUE)
$A = 0$ means the button has not been pressed (FALSE)

Boolean algebra is closely connected to logic gates, which are the physical components in computer circuits that perform Boolean operations.

Boolean expressions

A Boolean expression is an equation made up of Boolean operations. These expressions can be as simple as a single variable, or they can combine multiple variables using different Boolean operators to create complex logical statements.

Boolean expressions are used throughout computing to:

Control program flow with conditional statements
Validate user input
Search databases and web content
Design digital circuits
Make decisions in embedded systems

Truth tables

To understand and work with Boolean expressions, we use truth tables. A truth table is a visual method that shows the result of a Boolean expression for every possible combination of input values. For each combination of inputs, the table displays the corresponding output.

chatImportant

Truth tables are incredibly useful because they:

Show all possible scenarios at a glance
Help verify that Boolean expressions are correct
Make it easier to understand complex logical operations
Allow us to compare different expressions to see if they're equivalent

For example, if we have two inputs ( $A$ and $B$ ), each can be either 0 or 1, giving us four possible combinations: 00, 01, 10, and 11. A truth table would list all four combinations and show what output ( $Q$ ) results from each.

Relational operators

When creating Boolean expressions, we often need to compare values. We can use relational operators to build these comparisons. These operators evaluate relationships between values and return a Boolean result.

infoNote

These relational operators are commonly used in programming to create conditions that control how a program executes.

Boolean operations

Boolean operations are the fundamental building blocks of Boolean algebra. There are six main operations: AND, OR, NOT, NAND, NOR, and XOR. Let's explore each one in detail.

AND operation

The AND operation produces a TRUE result only when all of its inputs are TRUE. If any input is FALSE, the output will be FALSE. In Boolean notation, we write AND using a dot (.) symbol, so "A AND B" is written as A.B.

lightbulbExample

Real-world Example: Lift Control System

Imagine a lift in a building. For the lift to move, you might need both conditions to be true:

The button has been pressed
The doors are closed

We could express this as: "Button pressed AND Doors closed"

If we define:

$A$ = Button pressed ( $1$ = pressed, $0$ = not pressed)
$B$ = Doors closed ( $1$ = closed, $0$ = open)
$Q$ = Lift should move ( $1$ = yes, $0$ = no)

Then $Q = A \cdot B$ (Q equals A AND B)

Looking at this truth table, we can see that the lift will only move ( $Q = 1$ ) when both the button is pressed ( $A = 1$ ) and the doors are closed ( $B = 1$ ). In all other combinations, the lift stays stationary.

OR operation

The OR operation returns TRUE when at least one of its inputs is TRUE. It only returns FALSE when all inputs are FALSE. In Boolean notation, we write OR using a plus (+) symbol, so "A OR B" is written as A+B.

lightbulbExample

Real-world Example: Employee ID Validation

Consider an employee ID validation system where a worker needs to show proof of identity. They could use either:

A passport, OR
A driving licence

We could express this as: "Proof of ID is Passport OR Driving Licence"

If we define:

$A$ = Passport ( $1$ = has passport, $0$ = no passport)
$B$ = Driving Licence ( $1$ = has licence, $0$ = no licence)
$Q$ = Valid ID provided ( $1$ = yes, $0$ = no)

Then $Q = A + B$ (Q equals A OR B)

The truth table shows that the employee has valid ID ( $Q = 1$ ) in three scenarios: when they have a passport only, a driving licence only, or both. They only lack valid ID when they have neither document.

NOT operation

The NOT operation is different from AND and OR because it only works on a single input. It inverts the input value, so TRUE becomes FALSE and FALSE becomes TRUE. In Boolean notation, we show NOT using a bar over the variable, so "NOT A" is written as $\bar{A}$ .

The NOT operation is also called inversion or negation.

This simple truth table shows that NOT completely flips the value: when the input is 0, the output is 1, and when the input is 1, the output is 0.

lightbulbExample

Practical Application: Search Filtering

The NOT operation is particularly useful when searching. For example, if you're searching for information about "Python" the programming language, you might want to exclude results about snakes. You could search for:

"Python - snake" (which is the same as "Python NOT snake")

Let's break this down:

$A$ = Python is found ( $1$ = found, $0$ = not found)
$B$ = snake is found ( $1$ = found, $0$ = not found)
When we NOT the $B$ input, we get TRUE if snake is NOT found

This is then ANDed with the $A$ input to generate the final result. The search engine assumes an AND between Python and NOT snake, making the full expression: "Python AND NOT snake"

This extended truth table shows us the intermediate step (NOT $B$ ) and the final output. The search returns relevant results ( $Q = 1$ ) only when Python is found ( $A = 1$ ) and snake is not found (NOT $B = 1$ ), which occurs in the third row.

Combining AND and OR expressions

We can build more complex Boolean expressions by combining AND and OR operations. This allows us to create sophisticated logical conditions that match real-world scenarios.

lightbulbExample

Example: Barcode Scanner System

Imagine a barcode scanner system where data can be input in two ways:

Using the barcode scanner when it's on and a barcode has been scanned, OR
Entering the barcode number manually

We can express this as:

$A$ = Barcode scanner on ( $1$ = on, $0$ = off)
$B$ = Barcode scanned ( $1$ = scanned, $0$ = not scanned)
$C$ = Barcode number input manually ( $1$ = yes, $0$ = no)
$Q$ = Data from barcode has been read ( $1$ = yes, $0$ = no)

The Boolean expression would be: $Q = (A \text{ AND } B) \text{ OR } C$

In Boolean notation: $Q = A \cdot B + C$

This expression states that data is successfully read when either the scanner is on and has scanned a barcode, or when the number has been entered manually.

chatImportant

Remember: In Boolean notation, the dot (.) represents AND and the plus (+) represents OR.

NAND operation

The NAND operation (meaning "NOT AND") is a combination of the AND and NOT operations. It produces a TRUE result when at least one of the inputs is FALSE. You can think of it as the inverted version of the AND operation. NAND is written in Boolean notation as $\overline{A \cdot B}$ with a bar over the entire expression.

infoNote

NAND gates are extremely important in digital electronics because they can be used to create all other types of logic gates. This makes them very efficient for building integrated circuits, including solid state drives (SSDs) which use NAND flash memory.

Notice how the NAND truth table is the exact opposite of the AND truth table. The output is 1 (TRUE) in every row except when both inputs are 1.

NOR operation

The NOR operation (meaning "NOT OR") combines the OR and NOT operations. It returns TRUE only when all inputs are FALSE. In other words, it's the inverted version of the OR operation. NOR is written in Boolean notation as $\overline{A + B}$ with a bar over the entire expression.

infoNote

Like NAND gates, NOR gates are very useful in digital circuit design. They can also be used to construct other types of logic gates, and they're commonly used in CMOS (Complementary Metal-Oxide-Semiconductor) devices, which are found in most modern computer chips.

The NOR truth table shows that the output is 1 (TRUE) only in the first row where both inputs are 0 (FALSE). In all other cases, the output is 0.

XOR operation

The XOR operation (meaning "eXclusive OR") is a special type of OR operation. It produces a TRUE result only when exactly one of the inputs is TRUE and the other is FALSE. If both inputs are the same (both TRUE or both FALSE), XOR returns FALSE. In Boolean notation, XOR is often written as $A \oplus B$ .

XOR is particularly useful for:

Performing bitwise operations
Creating adder circuits in processors
Comparing values to see if they're different
Encryption algorithms

The XOR truth table shows that $Q = 1$ only when the inputs are different (01 or 10). When the inputs are the same (00 or 11), the output is 0.

Simplifying Boolean expressions

When working with Boolean algebra, it's good practice to reduce expressions to their simplest form. Simplifying Boolean expressions is important because:

chatImportant

Why Simplification Matters:

Simpler expressions are easier to understand
They lead to more efficient circuits with fewer components
Circuits with fewer gates are cheaper to manufacture
Simpler circuits are more reliable as there are fewer components that can fail
They often operate faster

One helpful technique for simplifying is to create a truth table for the expression and analyze the results. Let's look at an example to demonstrate this process.

lightbulbExample

Worked Example: Simplifying $(A \cdot B) + A$

First, we create a truth table showing the intermediate step ( $A \cdot B$ ) and the final result:

$A$	$B$	$A \cdot B$	$(A \cdot B) + A$
0	0	0	0
0	1	0	0
1	0	0	1
1	1	1	1

Looking at the final column, we can see that $(A \cdot B) + A$ equals 1 whenever $A$ equals 1. The value of $B$ doesn't matter when $A$ is 1.

Therefore, the expression simplifies to just $A$ .

We can verify this: $(A \cdot B) + A = A$

Boolean identities and laws

To help simplify complex Boolean expressions systematically, mathematicians have developed a set of rules called Boolean identities. These are proven relationships that always hold true in Boolean algebra. Understanding these rules allows you to manipulate and simplify expressions algebraically without having to draw truth tables every time.

Let's examine some of the most important identities:

infoNote

Identity Law: This states that ANDing a variable with 1 ( $A \cdot 1 = A$ ) or ORing a variable with 0 ( $A + 0 = A$ ) leaves the variable unchanged. This makes sense: a TRUE statement ANDed with TRUE is still TRUE, and a statement ORed with FALSE depends only on the statement itself.

infoNote

Null (or Dominance) Law: ANDing any variable with 0 always gives 0 ( $A \cdot 0 = 0$ ), and ORing any variable with 1 always gives 1 ( $A + 1 = 1$ ). Think of it this way: if one part of an AND statement is definitely FALSE, the whole thing must be FALSE. Similarly, if one part of an OR statement is definitely TRUE, the whole thing must be TRUE.

infoNote

Idempotence Law: This interesting rule says that ANDing or ORing a variable with itself doesn't change it ( $A \cdot A = A$ and $A + A = A$ ). If something is TRUE, it's still TRUE even if you state it twice!

chatImportant

Inverse Law: ANDing a variable with its inverse gives 0 ( $A \cdot \bar{A} = 0$ ), and ORing a variable with its inverse gives 1 ( $A + \bar{A} = 1$ ). This makes logical sense: something cannot be both TRUE and FALSE at the same time (so A AND NOT A = FALSE), but it must be either TRUE or FALSE (so A OR NOT A = TRUE).

infoNote

Commutative Law: The order in which you AND or OR variables doesn't matter ( $A \cdot B = B \cdot A$ and $A + B = B + A$ ). This is similar to addition and multiplication in regular maths.

infoNote

Associative Law: When you have multiple AND or OR operations, it doesn't matter how you group them with brackets. For example, $(A \cdot B) \cdot C = A \cdot (B \cdot C)$ .

infoNote

Distributive Law: You can factor out or distribute variables across brackets. For example, $A \cdot (B + C) = (A \cdot B) + (A \cdot C)$ . This is similar to multiplying out brackets in algebra, where $2(x + y) = 2x + 2y$ .

infoNote

Absorption Law: This states that $A \cdot (A + B) = A$ and $A + (A \cdot B) = A$ . The extra terms get "absorbed" and don't change the result.

infoNote

Double Complement Law: Taking the NOT of a NOT returns you to the original value. If you invert something twice, you get back to where you started: NOT(NOT $A$ ) = $A$ , or in notation: $\bar{\bar{A}} = A$ .

Using Boolean identities to simplify expressions

Let's see how we can apply these rules to simplify an expression without using truth tables.

lightbulbExample

Worked Example 1: Simplify $A + (A \cdot B)$

Using the Absorption Law directly, we know that $A + (A \cdot B) = A$

We can verify this with logical reasoning:

Suppose $A$ is 1 (TRUE), then $A +$ (anything) will evaluate to 1
On the other hand, suppose $A$ is 0 (FALSE). Then $A \cdot B$ will be 0, which will only evaluate to 1 if $B$ is 1, but that would mean $A$ is 1, which contradicts our supposition
So the expression equals 1 only when $A = 1$ , therefore it simplifies to $A$

lightbulbExample

Worked Example 2: Simplify $A + \bar{A} \cdot B$

This means "A OR (NOT A AND B)", which is the same as "A OR B".

We can prove this using the identities:

Step 1: Start with $A + \bar{A} \cdot B$

Step 2: Using the Distributive Law in reverse (factoring): $(A + \bar{A}) \cdot (A + B)$

Step 3: Using the Inverse Law: $A + \bar{A} = 1$ , so we get: $1 \cdot (A + B)$

Step 4: Using the Identity Law: $1 \cdot (A + B) = A + B$

Therefore, $A + \bar{A} \cdot B = A + B$ (simplified)

lightbulbExample

Worked Example 3: Simplify $(A + B) \cdot (A + C)$ using distribution

Using the Distributive Law, we can expand this:

Step 1: $(A + B) \cdot (A + C)$ can be distributed to: $A \cdot (A + C) + B \cdot (A + C)$

Step 2: Distributing further: $A \cdot A + A \cdot C + B \cdot A + B \cdot C$

Step 3: Using the Idempotence Law ( $A \cdot A = A$ ): $A + A \cdot C + B \cdot A + B \cdot C$

Step 4: This can be factored: $A \cdot (1 + C + B) + B \cdot C$

Step 5: Using the Null Law ( $1 +$ anything $= 1$ ): $A \cdot 1 + B \cdot C$

Step 6: Using the Identity Law: $A + B \cdot C$

Therefore, $(A + B) \cdot (A + C) = A + B \cdot C$ (simplified)

The process of simplification can involve multiple steps, but with practice, you'll recognize which identities to apply in different situations.

De Morgan's Law

De Morgan's Law is a particularly important method for simplifying Boolean expressions. It provides a systematic way to transform expressions by inverting variables and swapping AND and OR operations. This law is named after Augustus De Morgan, a 19th-century mathematician.

chatImportant

De Morgan's Law is especially useful because it allows us to create Boolean expressions using only NAND or NOR gates. Since these gates are easy and efficient to manufacture, this makes circuit design simpler and more cost-effective. For example, solid state drives (SSDs) are made almost entirely of NAND gates.

De Morgan's Law has two main rules:

Rule 1: NOT (A AND B) is the same as (NOT A) OR (NOT B)

In Boolean notation: $\overline{A \cdot B} = \bar{A} + \bar{B}$

Rule 2: NOT (A OR B) is the same as (NOT A) AND (NOT B)

In Boolean notation: $\overline{A + B} = \bar{A} \cdot \bar{B}$

infoNote

To put it simply: when you apply NOT to an entire expression, you must:

Change AND to OR (or OR to AND)
Invert each individual variable
The whole expression is already negated, so don't add another NOT

You can visualize this concept using a Venn diagram. Imagine two overlapping circles representing $A$ and $B$ . The area outside both circles represents NOT ( $A$ or $B$ ), which is the same as (NOT $A$ ) AND (NOT $B$ ).

Applying De Morgan's Law

When using De Morgan's Law to simplify or rewrite Boolean expressions, follow these essential steps:

chatImportant

Essential Steps for Applying De Morgan's Law:

Apply the law to one operator at a time - Don't try to transform multiple operators simultaneously
Swap the operator - Change AND to OR, or OR to AND
Invert the terms on either side - Apply NOT to each variable or sub-expression
Invert the entire expression - The whole expression is negated

Let's work through an example to see how this works in practice.

lightbulbExample

Worked Example: Simplify $(A + B) \cdot C + (A + \bar{A}) \cdot B$

Following a systematic approach:

Step 1: Starting with the first part $(A + B) \cdot C$

Wait, let me reconsider. Looking at $(A + \bar{B}) \cdot 0$ :
Any value ANDed with its inverse = 0 (Inverse Law)
So $(A + \bar{B}) \cdot 0 = 0$
Any value ANDed with 0 = 0 (Null Law)
Therefore the first part equals 0

Step 2: Now the second part $(A + \bar{A}) \cdot B$

Any value ORed with its inverse = 1 (Inverse Law)
$1 \cdot B = B$ (Identity Law)
Therefore $(A + \bar{A}) \cdot B = 1 \cdot B = B$

Step 3: Combining both parts: $0 + B = B$ (Identity Law)

Therefore, the simplified expression is $B$ (final answer)

We can verify De Morgan's Law using a truth table. For example, to show that an expression simplifies correctly, we would create columns for all variables, intermediate steps, and the final result, then verify that the final column matches our simplified expression.

bookmarkSummary

Key Points to Remember:

Boolean algebra produces values that are either TRUE or FALSE, represented as 1 and 0 respectively
Truth tables are visual tools that show the output of a Boolean expression for every possible combination of inputs
Six main Boolean operations exist:
- AND - all inputs must be TRUE
- OR - at least one input must be TRUE
- NOT - inverts the input
- NAND - TRUE if any input is FALSE
- NOR - TRUE only if all inputs are FALSE
- XOR - TRUE if exactly one input is TRUE
Always simplify Boolean expressions to their simplest form to create more efficient circuits with fewer components, lower costs, and better reliability
De Morgan's Law is a powerful simplification technique that allows you to convert between AND and OR operations by inverting variables and swapping operators, which is particularly useful for creating circuits using only NAND or NOR gates

Boolean Algebra (AQA A-Level Computer Science): Revision Notes

Boolean Algebra

Introduction to Boolean algebra

Boolean expressions

Truth tables

Relational operators

Boolean operations

AND operation

OR operation

NOT operation

Combining AND and OR expressions

NAND operation

NOR operation

XOR operation

Simplifying Boolean expressions

Boolean identities and laws

Using Boolean identities to simplify expressions

De Morgan's Law

Applying De Morgan's Law

Explore AQA A-Level Computer Science Model Answers by Topics

Hardware and Software

Classification of Programming Languages and Translation

Boolean Algebra

Logic Gates

Explore AQA A-Level Computer Science Quizzes by Topics

Hardware and Software

Classification of Programming Languages and Translation

Boolean Algebra

Logic Gates

Explore AQA A-Level Computer Science Flashcards by Topics

Hardware and Software

Classification of Programming Languages and Translation

Boolean Algebra

Logic Gates

Join 100,000+ A-Level students studying Revision Notes with us.