2.6 Comparing Boolean Expressions

What you need to know

• Boolean expressions are equivalent if they evaluate to the same value for every possible input.
• De Morgan's laws: !(a && b) ≡ !a || !b; !(a || b) ≡ !a && !b. Negating flips the operator and negates each part.
• Negating a comparison flips it to include the boundary: !(x < 5) ≡ x >= 5; !(x == y) ≡ x != y.
• A truth table lists every combination of inputs and the result — the reliable way to prove equivalence when reasoning gets confusing.
• Simplifications: a == true ≡ a; a == false ≡ !a; !!a ≡ a.
• Two if/else structures are equivalent if every input takes the same action, regardless of how the conditions are written.

Worked example

Is !(x > 10 || y <= 0) equivalent to x <= 10 && y > 0?

De Morgan: !(A || B) = !A && !B. !(x > 10) = x <= 10. !(y <= 0) = y > 0. So yes. Check one case: x = 3, y = 4 → original: !(false || false) = true; rewrite: true && true = true. ✓

Going deeper

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

• De Morgan mechanically: to negate (P && Q), negate P, negate Q, change && to ||. To negate (P || Q), negate P, negate Q, change || to &&. Then simplify each negated comparison by flipping it: !(x < 5) → x >= 5.
• Comparison negations: <↔>=, >↔<=, ==↔!=. The negation always flips the boundary's membership.
• Truth tables prove equivalence with certainty. Two variables: four rows. Three: eight. If every row matches, equivalent. If any row differs, not — and that row is your counterexample.
• Simplifications the exam expects: x == true → x; x == false → !x; !!x → x; x && true → x; x || false → x; x && false → false; x || true → true.
• Code equivalence extends beyond boolean expressions: two if/else structures are equivalent if every input takes the same action. Nested ifs vs. compound conditions, chains vs. separate ifs — all can be equivalent or not depending on details. Test.
• A boolean-returning method can often be simplified: if (c) return true; else return false; is just return c;. And if (c) return false; else return true; is return !c;.

Mistakes that cost points

• Negating parts but not the operator. !(a && b) ≠ !a && !b. The && must become ||.
• Dropping the boundary. !(x > 5) is x <= 5, not x < 5.
• Trusting intuition on equivalence. Build the table. It's faster than being wrong.

Practice questions

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

if (x > 0)
{
    if (y > 0)
    {
        return true;
    }
}
return false;