Boolean algebra and simplification of logic expressions

What you'll learn

Boolean algebra forms the mathematical foundation for digital circuits and computer logic. This topic covers how to manipulate and simplify logic expressions using established algebraic laws, reducing complex circuits to their most efficient form. You'll learn to apply De Morgan's laws, absorption rules, and other identities to optimise digital systems, a skill directly assessed in CIE IGCSE Computer Science Paper 1.

Key terms and definitions

Boolean algebra — A branch of mathematics dealing with variables that have only two possible values: TRUE (1) or FALSE (0), used to represent and manipulate logic circuits.

Logic expression — A combination of Boolean variables and operators (AND, OR, NOT) that can be evaluated to produce a Boolean result.

Simplification — The process of reducing a logic expression to its simplest form using Boolean laws, resulting in fewer logic gates and more efficient circuits.

De Morgan's laws — Two fundamental rules that describe how NOT distributes across AND/OR operations: NOT(A AND B) = NOT A OR NOT B, and NOT(A OR B) = NOT A AND NOT B.

Commutative law — A property stating that the order of operands doesn't affect the result: A AND B = B AND A, and A OR B = B OR A.

Distributive law — A rule allowing factorisation in Boolean expressions: A AND (B OR C) = (A AND B) OR (A AND C).

Identity law — Rules defining how Boolean values interact with 1 and 0: A AND 1 = A, A OR 0 = A, A AND 0 = 0, A OR 1 = 1.

Absorption law — A simplification rule where one term absorbs another: A OR (A AND B) = A, and A AND (A OR B) = A.

Core concepts

Boolean operators and notation

Three fundamental operators form the basis of all Boolean expressions:

AND operator (represented by ·, ∧, or juxtaposition):

• Output is 1 only when ALL inputs are 1
• A AND B can be written as A·B, A∧B, or AB
• Examples: 1·1 = 1, 1·0 = 0, 0·0 = 0

OR operator (represented by +, ∨):

• Output is 1 when AT LEAST ONE input is 1
• A OR B can be written as A+B or A∨B
• Examples: 1+0 = 1, 0+0 = 0, 1+1 = 1

NOT operator (represented by ¬, ‾, or '):

• Inverts the input value
• NOT A can be written as ¬A, Ā, or A'
• Examples: NOT 1 = 0, NOT 0 = 1

In CIE exams, you may encounter any of these notations. The most common are the dot for AND, plus for OR, and bar notation for NOT.

Order of operations

When evaluating Boolean expressions, apply operations in this sequence:

1. Brackets — Evaluate expressions inside parentheses first
2. NOT — Apply all NOT operations next
3. AND — Evaluate all AND operations
4. OR — Finally, evaluate OR operations

Example: A + B·C̄

• First apply NOT: C̄
• Then AND: B·C̄
• Finally OR: A + (B·C̄)

Understanding precedence prevents errors when simplifying or evaluating expressions.

Fundamental Boolean laws

Identity laws:

• A + 0 = A (OR with 0 leaves value unchanged)
• A · 1 = A (AND with 1 leaves value unchanged)
• A + 1 = 1 (OR with 1 always gives 1)
• A · 0 = 0 (AND with 0 always gives 0)

Idempotent laws:

• A + A = A (ORing a variable with itself doesn't change it)
• A · A = A (ANDing a variable with itself doesn't change it)

Complement laws:

• A + Ā = 1 (a variable OR its complement is always TRUE)
• A · Ā = 0 (a variable AND its complement is always FALSE)

Commutative laws:

• A + B = B + A (order doesn't matter for OR)
• A · B = B · A (order doesn't matter for AND)

Associative laws:

• (A + B) + C = A + (B + C) (grouping doesn't matter for OR)
• (A · B) · C = A · (B · C) (grouping doesn't matter for AND)

Distributive laws:

• A · (B + C) = (A · B) + (A · C) (AND distributes over OR)
• A + (B · C) = (A + B) · (A + C) (OR distributes over AND)

Absorption laws:

• A + (A · B) = A (the simpler term absorbs the complex one)
• A · (A + B) = A (the simpler term absorbs the complex one)

De Morgan's laws in detail

These laws are particularly important for CIE examinations:

First law: NOT(A AND B) = NOT A OR NOT B

• Written as: A·B = Ā + B̄
• Breaking a NAND: invert both inputs and change AND to OR
• Example: NOT(X AND Y) = NOT X OR NOT Y

Second law: NOT(A OR B) = NOT A AND NOT B

• Written as: A+B = Ā · B̄
• Breaking a NOR: invert both inputs and change OR to AND
• Example: NOT(P OR Q) = NOT P AND NOT Q

Application: De Morgan's laws allow you to:

• Remove brackets containing AND/OR under a NOT
• Convert between AND and OR operations
• Simplify complex expressions involving NAND/NOR gates

When applying De Morgan's:

1. Break the bar (remove NOT from outside)
2. Change the operator (AND↔OR)
3. Apply NOT to each term individually

Simplification methodology

Follow this systematic approach:

Step 1: Apply De Morgan's laws

• Remove complex NOT operations over brackets
• Convert NAND/NOR gates to simpler forms

Step 2: Apply distributive laws

• Factor out common terms
• Expand brackets where helpful

Step 3: Look for complements

• Find A · Ā = 0 and A + Ā = 1
• These often eliminate entire terms

Step 4: Apply absorption laws

• Identify where simpler terms absorb complex ones
• Remove redundant terms

Step 5: Apply identity and idempotent laws

• Simplify terms involving 0, 1, A·A, or A+A
• Clean up the final expression

Step 6: Verify using truth tables

• Check your simplified expression matches the original
• Test all possible input combinations

Converting between logic gates and Boolean expressions

From circuit to expression:

1. Start at the inputs (leftmost gates)
2. Work systematically toward outputs
3. Write the expression for each gate's output
4. Combine using brackets for clarity
5. The final gate's output is your complete expression

From expression to circuit:

1. Identify the final operation (what happens last)
2. Draw that gate on the right
3. Work backwards, drawing gates for sub-expressions
4. Connect inputs to earlier gate outputs
5. Label all connections clearly

Reducing gate count:

• Simplified expressions use fewer gates
• Each term in sum-of-products form = one AND gate
• Multiple AND outputs feed into final OR gate
• Minimising terms reduces cost and improves speed

Worked examples

Example 1: Simplifying using absorption

Question: Simplify the expression X + X̄Y

Solution:

Using the absorption law variant:

• X + X̄Y can be rewritten using the second distributive law
• X + X̄Y = (X + X̄)(X + Y) by distribution
• X + X̄ = 1 by complement law
• Therefore: 1 · (X + Y) = X + Y by identity law

Answer: X + Y

Alternative method:

• Factor by case analysis
• When X = 1: X + X̄Y = 1 + 0·Y = 1 (expression = 1)
• When X = 0: X + X̄Y = 0 + 1·Y = Y (expression = Y)
• Combined: expression outputs 1 when X=1, or Y when X=0
• This is equivalent to X + Y

[2 marks] — 1 mark for showing working with valid Boolean laws, 1 mark for correct simplified answer.

Example 2: Applying De Morgan's laws

Question: Simplify the expression: NOT((A AND B) OR (C AND NOT D))

Write your answer using symbolic notation.

Solution:

Let E = (A·B) + (C·D̄)

We need to find: Ē

Step 1: Apply De Morgan's first law to break the NOT over OR:

• (A·B) + (C·D̄) = (A·B)‾ · (C·D̄)‾

Step 2: Apply De Morgan's second law to each term:

• (A·B)‾ = Ā + B̄
• (C·D̄)‾ = C̄ + D̄‾ = C̄ + D (double negative)

Step 3: Combine:

• (Ā + B̄) · (C̄ + D)

Answer: (Ā + B̄) · (C̄ + D) or equivalent forms

[3 marks] — 1 mark for correctly applying De Morgan's to remove outer NOT, 1 mark for correctly simplifying each term, 1 mark for correct final expression.

Example 3: Complete simplification with multiple laws

Question: Simplify: AB + AB̄ + ĀB

Show all steps clearly.

Solution:

Step 1: Factor out A from first two terms:

• AB + AB̄ + ĀB = A(B + B̄) + ĀB

Step 2: Apply complement law:

• B + B̄ = 1
• Therefore: A(1) + ĀB = A + ĀB

Step 3: Apply absorption law variant:

• A + ĀB = A + B (using the simplification from Example 1)

Alternative verification using identity law:

• A + ĀB = (A + Ā)(A + B) [distributive]
• = 1 · (A + B) [complement]
• = A + B [identity]

Answer: A + B

[3 marks] — 1 mark for factorising correctly, 1 mark for applying complement law, 1 mark for final simplification to A + B.

Common mistakes and how to avoid them

Confusing AND with OR during De Morgan's application

• Remember: "break the bar, change the sign"
• NOT(AND) becomes OR, NOT(OR) becomes AND
• Double-check you've swapped the operator, not kept it the same

Forgetting to invert ALL terms under the NOT

• De Morgan's requires inverting every variable/expression
• NOT(A AND B) ≠ NOT A AND B (incorrect)
• NOT(A AND B) = NOT A OR NOT B (correct)

Incorrect order of operations

• Always evaluate NOT before AND, and AND before OR
• Use brackets to show clearly which operations happen first
• A + B·C means A + (B·C), not (A + B)·C

Stopping simplification too early

• Check if absorption, identity, or other laws still apply
• Look for patterns like A + ĀB or A·(A + B)
• The simplest form has the fewest operators and terms

Misapplying the distributive law

• A·(B + C) = A·B + A·C ✓ (AND distributes over OR)
• A + B·C ≠ (A + B)·(A + C) without proper expansion ✓
• Be careful which direction you're working (factorising vs expanding)

Losing track of NOT bars in complex expressions

• Use brackets liberally when working with multiple NOTs
• Write each step separately rather than trying to do multiple operations at once
• Check whether double negatives (Ā̄ = A) simplify your expression

Exam technique for "Boolean algebra and simplification of logic expressions"

Command word interpretation:

• "Simplify" — reduce the expression to fewest terms/operators; show working for method marks
• "State the Boolean law" — name the specific law (e.g., "De Morgan's law" or "absorption law")
• "Show that..." — prove both sides are equivalent using laws or truth tables; complete working essential
• "Draw the logic circuit" — convert expression to gates; use standard symbols; label inputs/outputs

Structured approach for simplification questions:

• Write each step on a new line
• State which law you're applying (especially for 3+ mark questions)
• Keep expressions aligned vertically for clarity
• Box or underline your final answer

Mark allocation patterns:

• 2 marks: typically one intermediate step + correct answer
• 3 marks: usually two transformations + final answer, OR full working with named laws
• 4+ marks: multiple laws applied with justification, possibly requiring truth table verification

Time management:

• Spend 30-60 seconds planning which laws to apply
• If stuck, try a truth table to verify your thinking (may earn partial credit)
• Check your answer makes intuitive sense — simplified forms should be shorter than originals

Quick revision summary

Boolean algebra uses AND (·), OR (+), and NOT (‾) operators with variables that are either 0 or 1. Key laws include identity (A·1=A, A+0=A), complement (A·Ā=0, A+Ā=1), and absorption (A+AB=A). De Morgan's laws convert NOT(A AND B) to NOT A OR NOT B and vice versa. Simplification reduces expressions to fewer terms using these laws systematically: apply De Morgan's, factor with distributive law, find complements, apply absorption, then identity laws. Always show working step-by-step.