Worksheet

A8.5 Simplifying expressions

Boolean algebra and logic circuits · A level · OCR H446 1.4.3, AQA 7517 4.6.5.1, Eduqas A500QS 1.2 · about 25 min

What this lesson is about

A method for simplifying by algebra, worked exam-style examples, and checking the result.

• What "simpler" means
• A method
• Worked examples
• Checking each step by machine
• Simplifying a robot's condition

Questions 5 marks in all

1. [1 mark]Simplify (A ∨ B) ∧ (A ∨ ¬B).

   1. AA
   2. BB
   3. CA ∨ B
   4. D1

2. [1 mark]Simplify ¬(A ∨ B) ∨ (¬A ∧ B).

   1. A¬A
   2. B¬B
   3. C¬A ∧ ¬B
   4. DA ∨ B

3. [1 mark]Simplify (A ∧ B ∧ C) ∨ (A ∧ B ∧ ¬C) ∨ (A ∧ ¬B).

   1. AA
   2. BA ∧ B
   3. CA ∧ C
   4. DB ∨ C

4. [1 mark]Put the steps simplifying A · B + A · B̅ + A̅ · B in order.

   Number the lines 1 to 4 to put them in the right order.

   1. A + A̅ · B
   2. A · 1 + A̅ · B
   3. A + B
   4. A · (B + B̅) + A̅ · B

5. [1 mark]A student writes ¬A ∨ ¬B = ¬A ∧ ¬B as a step. What is wrong?

   1. AThe operator was changed without the bar over the whole that De Morgan needs
   2. BNothing, it is De Morgan's law
   3. CCommutation was used instead of association
   4. DThe NOTs should have cancelled

The task: simplify, then prove it

The function original(a, b, c) computes Q = ¬(A ∨ ¬B) ∨ (A ∧ B) ∨ (A ∧ ¬B ∧ C). Its inputs are bits (0 or 1) and it returns 0 or 1. Simplify Q on paper, then write simplified(a, b, c), taking and returning the same, as a single return line that uses at most two of and, or and not in total. It may not call original or use the bitwise operators &, |, ^ or ~. Print eight lines, one per row in binary order (A outermost, then B, then C), in exactly this form, with every value 0 or 1: A=0 B=1 C=0 original=1 simplified=1

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

def original(a, b, c):
    return int((not (a or not b)) or (a and b) or (a and not b and c))

def simplified(a, b, c):
    return 0

Plan your program here, then type it in and press Run.

Do it on the robot
www.bugbotlab.com/learn/a8-5-simplifying-expressions/
The simulator checks it and tells you when it passes. Nothing to install, no account.

Challenges

1. Simplify (A ∧ B ∧ C) ∨ (A ∧ B ∧ ¬C) ∨ (A ∧ ¬B) by algebra. Check it with same, extended to three inputs.
2. How many two-input gates does Q need as written, and how many after simplifying? Count a NOT as a gate.
3. Write the working for the task as a steps list and check every step by machine.