Logic Problems and Algorithm Constructs

Overview

Recall questions on solving logic problems with Boolean expressions and checking them exhaustively, the definition of an algorithm, and sequence, assignment, selection and iteration.

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

   A door lock must open only when at least two of its three sensors A, B and C are triggered. Develop a Boolean expression for the OPEN signal and explain how you arrived at it.

   Model answer

   OPEN = (A AND B) OR (A AND C) OR (B AND C). Work through the cases: 'at least two of three' is satisfied by exactly the three possible pairs, so write one AND term for each pair and OR the terms together. The all-three case needs no extra term because if A, B and C are all triggered then (A AND B) is already true, which makes the whole OR true.

2. 2

   How would you check that door-lock expression is correct, and why is trying one set of inputs not enough?

   Model answer

   Build a truth table with a row for every combination of inputs. Three inputs give 2³ = 8 rows. Evaluate the expression in each row and compare the result with what the problem demands: it must be 0 for the four rows 000, 100, 010 and 001 (fewer than two sensors triggered) and 1 for the four rows 110, 101, 011 and 111. One test is not enough because a mistake in a single AND term still leaves most rows correct; only checking every case, or giving a logical argument that covers every case, shows the solution is right.

3. 3

   An alarm should sound when the window sensor W reports open AND the system is armed R, but never while the engineer's override O is on. Give the Boolean expression and say what happens when W = 1, R = 1 and O = 1.

   Model answer

   ALARM = W AND R AND NOT O. With W = 1, R = 1 and O = 1, NOT O = 0, so the three-way AND evaluates to 0 and the alarm stays silent. The override wins, which is exactly what the problem asked for. Note that 'but never while' in the English statement becomes AND NOT, not OR NOT.

4. 4

   A student claims that NOT (A AND B) is the same as (NOT A) AND (NOT B). Show that this is wrong.

   Model answer

   Take A = 1 and B = 0. NOT (A AND B) = NOT 0 = 1, but (NOT A) AND (NOT B) = 0 AND 1 = 0. The two sides differ, so the claim is false. A single counter-example is enough to disprove a claim that two expressions are equivalent. The correct equivalent is NOT (A AND B) = (NOT A) OR (NOT B).

5. 5

   Solve this logic problem and justify your answer: 'If a file is compressed then it is not encrypted. This file is encrypted.'

   Model answer

   The file is not compressed. If it were compressed, the first statement would force it to be unencrypted, which contradicts the fact that it is encrypted. Ruling out the only alternative leaves 'not compressed' as the conclusion.

6. 6

   Why is it worth rewriting a logic problem using single letters and Boolean operators before trying to solve it?

   Model answer

   Ordinary English is ambiguous about logic. 'Or' may mean one or the other or both, or it may mean exactly one; 'unless' can mean AND NOT; 'and' in a list can hide an implied OR. Replacing each condition with a named variable and writing the requirement with AND, OR and NOT fixes one meaning, makes the number of input combinations obvious (n conditions give 2ⁿ cases to check), and lets you test the solution mechanically with a truth table instead of by re-reading the prose.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.