Boolean Algebra (Cambridge (CIE) A Level Computer Science): Revision Note

Boolean algebra

What is Boolean algebra?

• Boolean algebra is a mathematical system used to manipulate Boolean values

• Complex expressions can be made simpler using the rules of Boolean algebra

• This is a more powerful simplification method than Karnaugh maps and can simplify expressions that Karnaugh maps cannot

• There are various different rules that you need to learn and that can then be applied to certain expressions to simplify them

• Combining these rules can mean that complex expressions can be reduced to much simpler ones

General rules

• General AND rules

  • X AND 0 = 0

  • X AND 1 = X

  • X AND A = X

  • NOT X AND X = 0

• Note, the value ox X is unknown and it is used as a placeholder

• Therefore X AND 1 = X means that the output will be whatever the value of X is

• General OR rules

  • X OR 0 = X
    X OR 1 = 1
    X OR A = X
    NOT X OR X = 1

Boolean algebra notation

• In Boolean algebra, expressions are written using shorthand notation:

• A line drawn above a variable or expression means that the value is inverted or negated

• It's the NOT of that value

• When you see multiple horizontal lines, for example:

• It means the whole expression is negated, not just one part

• Always apply De Morgan’s Law starting with the outermost line first

De Morgan's Law

What is De Morgan’s Law?

• De Morgan’s Laws are used to simplify Boolean expressions involving negation of conjunctions (AND) or disjunctions (OR)

• They are particularly useful for rewriting logic circuits using only NAND or NOR gates

• There are two key rules:

  1. NOT (A AND B) is equivalent to (NOT A) OR (NOT B)

     

  2. NOT (A OR B) is equivalent to (NOT A) AND (NOT B)

     

Worked example 1: Simplify ¬(A ∧ B)

Worked example 2: Simplify ¬(A ∨ B)

Why use De Morgan’s Laws?

• Simplifying Boolean expressions using De Morgan’s Laws:

  • Allows for implementation using only NAND or NOR gates

  • Makes circuit design more efficient and cost-effective

  • Is essential in hardware where NAND/NOR logic is cheaper or faster to implement

  • Is commonly used in microprocessor and memory device design (e.g. flash drives)