3.5 Boolean Expressions

What you need to know

• A Boolean value is either true or false. A Boolean expression evaluates to one of those two.
• Relational operators compare values: =, ≠, >, <, ≥, ≤. Note: in AP pseudocode = is comparison, not assignment (assignment is ←).
• Logical operators: NOT a is true when a is false. a AND b is true only when both are true. a OR b is true when at least one is true (including both).
• Precedence: NOT is evaluated before AND, which is before OR. Use parentheses when in doubt — the exam does.
• De Morgan's laws show up as "equivalent expression" questions: NOT (a AND b) = (NOT a) OR (NOT b), and NOT (a OR b) = (NOT a) AND (NOT b).
• Two Boolean expressions are equivalent if they have the same value for every combination of inputs. A truth table proves it.
• The negation of x > 5 is x ≤ 5, not x < 5. Missing the boundary case is a classic distractor.

Worked example

Let age ← 16 and hasLicense ← false.

• age ≥ 16 AND hasLicense → true AND false → false
• age ≥ 16 OR hasLicense → true OR false → true
• NOT (age < 18) → NOT true → false
• NOT (age ≥ 16 AND hasLicense) → NOT false → true, which by De Morgan equals age < 16 OR NOT hasLicense → false OR true → true. ✓

Going deeper

The nuance, edge cases, and connections that turn a 3 into a 5.

• Truth tables are the reliable tool. For two Booleans a and b there are four rows: TT, TF, FT, FF. Evaluate both expressions on each row; if all four match, they're equivalent. For three Booleans, eight rows. It's mechanical and it works.
• Short-circuit evaluation isn't formally in the CSP CED, but understanding that false AND anything is false and true OR anything is true speeds up evaluation and helps you see equivalences.
• De Morgan's laws in practice: to negate "x is between 1 and 10" — which is x ≥ 1 AND x ≤ 10 — you get x < 1 OR x > 10. Flip AND to OR, flip each comparison to its opposite (including the boundary).
• The negation of a comparison flips to the opposite operator, which always includes the boundary the original excluded: NOT(>) is ≤, NOT(≥) is <, NOT(=) is ≠. Students who write NOT(x > 5) as x < 5 miss the case x = 5.
• Relational operators return a Boolean, so x > 5 by itself is a complete Boolean expression that can be assigned: isBig ← x > 5. Then IF (isBig) works without writing IF (isBig = true).
• Precedence: relational operators evaluate first, then NOT, then AND, then OR. So NOT a AND b is (NOT a) AND b. The exam uses parentheses generously, but knows students misgroup when it doesn't.

Mistakes that cost points

• Dropping the boundary when negating. NOT(score ≥ 90) is score < 90, not score ≤ 90 or score < 89.
• De Morgan half-done. NOT(a AND b) becomes (NOT a) OR (NOT b). Students negate the parts but forget to flip AND to OR (giving NOT a AND NOT b, which is wrong).
• Treating OR as exclusive. a OR b is true when both are true, too. It's inclusive or.
• Grouping NOT loosely. NOT a OR b is (NOT a) OR b. NOT applies only to the thing right after it unless parentheses say otherwise.

Practice questions

Written in the style of the real exam. Try each one before revealing the answer.