Defining Problems Using Boolean Logic

Overview

Recall questions on turning English conditions into Boolean expressions, deriving sum-of-products expressions from truth tables, at least one, exactly one and all, majority voting, common mistakes, and checking an expression against its requirement.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   What does it mean to define a problem using Boolean logic?

   Model answer

   It means expressing a set of conditions written in English as a Boolean expression, by identifying each condition as a variable that is either true (1) or false (0), and then joining those variables with AND, OR, NOT and XOR so that the expression is true in exactly the circumstances the requirement describes. Once the problem is in that form it can be simplified algebraically, drawn as a gate diagram or verified with a truth table.

2. 2

   A burglar alarm sounds when the system is armed and either the door sensor or a window sensor is triggered, but not if the override key is turned. Express this in Boolean logic.

   Model answer

   Let A be 'system armed', D be 'door sensor triggered', W be 'window sensor triggered' and K be 'override key turned'. The alarm S = A.(D + W).K', that is A AND (D OR W) AND NOT K. The brackets around D + W are essential: without them the AND would bind to D alone and a window trigger would sound the alarm even when the system was disarmed.

3. 3

   A lift will move only when the doors are closed and either a floor button has been pressed inside or a call button has been pressed outside, and it must not move when the emergency stop is active. Write the expression.

   Model answer

   Let C be 'doors closed', F be 'internal floor button pressed', E be 'external call button pressed' and S be 'emergency stop active'. Move M = C.(F + E).S', that is C AND (F OR E) AND NOT S. The emergency stop appears as a negated variable ANDed onto the whole expression, because it must be able to block the output regardless of every other condition.

4. 4

   How do you derive a Boolean expression directly from a truth table?

   Model answer

   Look at every row where the output is 1. For each such row write a product term that ANDs all the inputs together, taking each variable as itself if it is 1 in that row and negated if it is 0. Then OR all those product terms together. The result is called sum-of-products form, and it is true in exactly those rows and no others. It is correct but not usually minimal, so it is normally simplified afterwards, algebraically or with a Karnaugh map.

5. 5

   A three-input circuit outputs 1 only when exactly one of A, B and C is 1. Derive its sum-of-products expression.

   Model answer

   The output is 1 in three rows: A=0,B=0,C=1; A=0,B=1,C=0; A=1,B=0,C=0. Taking each variable negated where it is 0 gives the terms A'.B'.C, A'.B.C' and A.B'.C'. ORing them, Q = A'.B'.C + A'.B.C' + A.B'.C'. The remaining five rows, including the all-zeros row and the all-ones row, give 0.

6. 6

   Explain the difference between 'at least one', 'exactly one' and 'all', and how each is written.

   Model answer

   'At least one of A and B' is a plain OR: A + B, true in three of the four rows. 'Exactly one' excludes the case where both are true, which is XOR, equivalently A.B' + A'.B. 'All' is a plain AND: A.B, true in only one row. Reading a requirement carelessly and writing OR where the English said 'either ... or ... but not both' is a very common error.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.