Boolean expressions can be simplified using algebraic rules, making circuits cheaper and faster.
Boolean Algebra Laws
Key Point
| Law family | OR form | AND form |
|---|---|---|
| Identity | A ∨ 0 = A | A ∧ 1 = A |
| Null | A ∨ 1 = 1 | A ∧ 0 = 0 |
| Idempotent | A ∨ A = A | A ∧ A = A |
| Complement | A ∨ ¬A = 1 | A ∧ ¬A = 0 |
| Involution | ¬¬A = A | — |
| Commutative | A ∨ B = B ∨ A | A ∧ B = B ∧ A |
| Associative | (A ∨ B) ∨ C = A ∨ (B ∨ C) | (A ∧ B) ∧ C = A ∧ (B ∧ C) |
| Distributive | A ∨ (B ∧ C) = (A ∨ B) ∧ (A ∨ C) | A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C) |
| Absorption | A ∨ (A ∧ B) = A | A ∧ (A ∨ B) = A |
De Morgan's Laws
Key Point
| Original expression | Equivalent expression | In words |
|---|---|---|
| ¬(A ∧ B) | ¬A ∨ ¬B | NOT (A AND B) = (NOT A) OR (NOT B) |
| ¬(A ∨ B) | ¬A ∧ ¬B | NOT (A OR B) = (NOT A) AND (NOT B) |
Worked Example
Worked Example: Simplifying a Boolean Expression
Simplify: Q = A ∧ B ∨ A ∧ ¬B ∨ ¬A ∧ B
Step 1: Factor out common terms
Q = A ∧ (B ∨ ¬B) ∨ ¬A ∧ B
Step 2: Apply complement law (B + B̅ = 1)
Q = A ∧ 1 ∨ ¬A ∧ B
Step 3: Apply identity law (A.1 = A)
Q = A ∨ ¬A ∧ B
Step 4: Apply absorption (or expand and simplify)
Q = A ∨ ¬A ∧ B
= (A ∨ ¬A) ∧ (A ∨ B) [Distributive law]
= 1 ∧ (A ∨ B) [Complement law]
= A ∨ B [Identity law]
Answer: Q = A ∨ B (much simpler circuit!)
Simplify: Q = A ∧ B ∨ A ∧ ¬B ∨ ¬A ∧ B
Step 1: Factor out common terms
Q = A ∧ (B ∨ ¬B) ∨ ¬A ∧ B
Step 2: Apply complement law (B + B̅ = 1)
Q = A ∧ 1 ∨ ¬A ∧ B
Step 3: Apply identity law (A.1 = A)
Q = A ∨ ¬A ∧ B
Step 4: Apply absorption (or expand and simplify)
Q = A ∨ ¬A ∧ B
= (A ∨ ¬A) ∧ (A ∨ B) [Distributive law]
= 1 ∧ (A ∨ B) [Complement law]
= A ∨ B [Identity law]
Answer: Q = A ∨ B (much simpler circuit!)
The Rules Named in the Specification
The specification names five rules, and a question can ask for one of them by name. Double negation is the rule the table above calls involution.
Key Point
| Rule | What it says | Used to |
|---|---|---|
| De Morgan's Laws | ¬(A ∧ B) ≡ ¬A ∨ ¬B and ¬(A ∨ B) ≡ ¬A ∧ ¬B | Remove a NOT from around a bracket, or put one in |
| Distribution | A ∧ (B ∨ C) ≡ (A ∧ B) ∨ (A ∧ C) and A ∨ (B ∧ C) ≡ (A ∨ B) ∧ (A ∨ C) | Multiply out a bracket, or take out a common term |
| Association | (A ∧ B) ∧ C ≡ A ∧ (B ∧ C) and (A ∨ B) ∨ C ≡ A ∨ (B ∨ C) | Move or remove brackets when the operators are all the same |
| Commutation | A ∧ B ≡ B ∧ A and A ∨ B ≡ B ∨ A | Change the order of the terms |
| Double negation | ¬¬A ≡ A | Cancel two NOTs |
Worked Example
Worked Example: Applying a Named Rule
| Expression | Rule used | Result |
|---|---|---|
| ¬A ∧ ¬B | De Morgan's Law | ¬(A ∨ B) |
| ¬(¬A ∨ B) | De Morgan's Law, then double negation | ¬¬A ∧ ¬B, which is A ∧ ¬B |
| (A ∧ B) ∨ (A ∧ ¬C) | Distribution | A ∧ (B ∨ ¬C) |
| (A ∨ B) ∧ (A ∨ ¬C) | Distribution | A ∨ (B ∧ ¬C) |
| B ∧ A | Commutation | A ∧ B |
| (A ∧ B) ∧ C | Association | A ∧ (B ∧ C) |
Exam Tip
When a question says to explain which rule is used at each step, write the name of the rule next to every line of working, not only beside the final answer.
Defining a Problem with Boolean Logic
A problem described in words can be written as a Boolean expression.
- 1.Give each condition a letter, and the result a letter such as Q.
- 2.Replace "and" with ∧, "or" with ∨ and "not" with ¬.
- 3.Put brackets round the conditions that belong together.
Worked Example
Worked Example: From a Description to an Expression
A greenhouse heater switches on when the temperature is low and either the timer is on or the override button is pressed. It never switches on while the window is open.
Answer: Q = A ∧ (B ∨ C) ∧ ¬D
The brackets are needed. Without them, A ∧ B ∨ C ∧ ¬D would be read as (A ∧ B) ∨ (C ∧ ¬D), because AND is worked out before OR.
A greenhouse heater switches on when the temperature is low and either the timer is on or the override button is pressed. It never switches on while the window is open.
| Letter | Condition |
|---|---|
| A | The temperature is low |
| B | The timer is on |
| C | The override button is pressed |
| D | The window is open |
| Q | The heater switches on |
The brackets are needed. Without them, A ∧ B ∨ C ∧ ¬D would be read as (A ∧ B) ∨ (C ∧ ¬D), because AND is worked out before OR.