Boolean Expressions and Simplification

A Boolean expression is an algebraic expression that uses Boolean operators (AND, OR, NOT) to describe the output of a logic circuit or condition. In GCSE Computer Science, you need to be able to write, interpret and simplify Boolean expressions.

---

Writing Boolean Expressions

Notation

Operation	Common Notations	Example
NOT	¬A, A̅, NOT A	¬A
AND	A ∧ B, A · B, A AND B	A ∧ B
OR	A ∨ B, A + B, A OR B	A ∨ B
XOR	A ⊕ B, A XOR B	A ⊕ B

Operator Precedence (Order of Operations)

Just like in mathematics where multiplication is done before addition, Boolean algebra has an order of operations:

1. Brackets — evaluate expressions inside brackets first
2. NOT — negation is applied next
3. AND — conjunction is applied next
4. OR — disjunction is applied last

So the expression A ∨ B ∧ C is evaluated as A ∨ (B ∧ C) — the AND is done before the OR.

Exam Tip: When in doubt, use brackets to make the order of operations clear. This avoids ambiguity and makes it easier for you (and the examiner) to follow your working.

---

Converting Between Expressions and Truth Tables

From Expression to Truth Table

To create a truth table from a Boolean expression:

1. Identify all the variables (inputs).
2. List all possible input combinations (2^n rows).
3. Evaluate the expression for each combination, using intermediate columns.

Example: Create a truth table for ¬A ∧ (B ∨ C)

A	B	C	¬A	B ∨ C	¬A ∧ (B ∨ C)
0	0	0	1	0	0
0	0	1	1	1	1
0	1	0	1	1	1
0	1	1	1	1	1
1	0	0	0	0	0
1	0	1	0	1	0
1	1	0	0	1	0
1	1	1	0	1	0

From Truth Table to Expression

To write a Boolean expression from a truth table:

1. Look at the rows where the output is 1.
2. For each such row, write an AND expression that matches the inputs (use ¬ for any input that is 0).
3. Combine all the AND expressions with OR.

This method produces a Sum of Products (SoP) expression.

Example: Given this truth table:

A	B	Output
0	0	0
0	1	1
1	0	1
1	1	0

Rows with output 1: Row 2 (A=0, B=1) and Row 3 (A=1, B=0).

• Row 2: ¬A ∧ B
• Row 3: A ∧ ¬B

Expression: (¬A ∧ B) ∨ (A ∧ ¬B) — which is equivalent to A ⊕ B (XOR).

---

Boolean Algebra Laws

These are the key Boolean algebra laws you should know for GCSE. They allow you to simplify complex expressions.

Identity Laws

• A ∧ 1 = A
• A ∨ 0 = A

Null (Annihilation) Laws

• A ∧ 0 = 0
• A ∨ 1 = 1

Idempotent Laws

• A ∧ A = A
• A ∨ A = A

Complement Laws

• A ∧ ¬A = 0
• A ∨ ¬A = 1

Double Negation (Involution)

• ¬(¬A) = A

Commutative Laws

• A ∧ B = B ∧ A
• A ∨ B = B ∨ A

Associative Laws

• (A ∧ B) ∧ C = A ∧ (B ∧ C)
• (A ∨ B) ∨ C = A ∨ (B ∨ C)

Distributive Laws

• A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C)
• A ∨ (B ∧ C) = (A ∨ B) ∧ (A ∨ C)

Absorption Laws

• A ∨ (A ∧ B) = A
• A ∧ (A ∨ B) = A

De Morgan's Laws

These are particularly important and commonly examined:

• ¬(A ∧ B) = ¬A ∨ ¬B — "NOT (A AND B) is the same as (NOT A) OR (NOT B)"
• ¬(A ∨ B) = ¬A ∧ ¬B — "NOT (A OR B) is the same as (NOT A) AND (NOT B)"

Exam Tip: De Morgan's Laws are frequently tested. A useful way to remember them: "break the bar, change the sign." When you distribute a NOT over a bracket, AND becomes OR and OR becomes AND.

---

Simplification Examples

Example 1: Simplify A ∧ (A ∨ B)

Using the absorption law: A ∧ (A ∨ B) = A

Example 2: Simplify ¬A ∧ A

Using the complement law: ¬A ∧ A = 0

Example 3: Simplify (A ∧ B) ∨ (A ∧ ¬B)

Factor out A (distributive law): A ∧ (B ∨ ¬B) Apply complement law: B ∨ ¬B = 1 Apply identity law: A ∧ 1 = A Result: A

The simplification flow above can be visualised as a sequence of rewrite steps:

graph TD
    S0["(A AND B) OR (A AND NOT B)"] --> S1["A AND (B OR NOT B)"]
    S1 --> S2["A AND 1"]
    S2 --> S3["A"]
    S0 -.distributive.-> S1
    S1 -.complement.-> S2
    S2 -.identity.-> S3

Example 4: Simplify ¬(¬A ∧ ¬B)

Using De Morgan's Law: ¬(¬A ∧ ¬B) = ¬(¬A) ∨ ¬(¬B) = A ∨ B

---

Why Simplification Matters

Simplifying Boolean expressions has practical benefits:

• Fewer logic gates → cheaper and smaller circuits
• Fewer connections → less power consumption
• Less complexity → faster processing and fewer potential faults
• Easier to understand → simpler code and easier maintenance

In industry, engineers use Boolean simplification (and tools like Karnaugh maps) to design efficient circuits for processors, memory and other components.

---

Summary