Unit 2 Cycle 2 Day 8: I/II/III: Boolean Equivalence
Share
I/II/III: Boolean Equivalence
Section 2.6 — Equivalent Boolean
Key Concept
I/II/III boolean equivalence questions present three expressions and ask which are logically equivalent. Common equivalences tested include: !(a && b) equals !a || !b (De Morgan's), a || a && b equals a (absorption), and a && (a || b) equals a (absorption). To verify equivalence, test all four combinations of truth values for two-variable expressions (TT, TF, FT, FF). If two expressions produce the same result for all combinations, they are equivalent.
Consider the following boolean expressions where x is an int.
Which of the expressions are logically equivalent to each other?
Answer: (D) I, II, and III
By De Morgan's: !(x > 10 || x < 5) = !(x > 10) && !(x < 5) = x <= 10 && x >= 5. All three expressions represent the same condition: x is between 5 and 10, inclusive.
Why Not the Others?
(A) III is also equivalent. x <= 10 && x >= 5 is the simplified form of I and II.
(B) I is also equivalent. It is just the non-simplified De Morgan's form.
(C) II is also equivalent. It is De Morgan's Law applied in reverse to I.
Common Mistake
All three are different ways to write the same condition (5 <= x <= 10). I uses negated individual conditions. II uses De Morgan's in compact form. III uses direct relational operators.
AP Exam Tip
The AP exam loves testing De Morgan's equivalence. Practice converting between the three forms: negated compound, De Morgan's, and direct relational.