AP Computer Science A · Unit 2 lecture · Part 5 of 12 · 9 min

2.6 Comparing Boolean expressionsSame answer for every input

Mr. Thompkins
Two conditions can look completely different and still always agree. The exam asks "which of these is equivalent?" a lot. Here are two tools that settle it every time: a truth table and De Morgan's laws.

Two Boolean expressions are equivalent when they have the same value for every possible input. To prove two expressions equivalent, check every combination of inputs with a truth table. To prove they are not equivalent, you need just one counterexample: a single input where they disagree.

De Morgan's laws tell you how to push a ! inside parentheses. Negate each part, and flip the operator: !(a && b) is the same as !a || !b, and !(a || b) is the same as !a && !b. Negating a comparison flips it, too: !(x < 5) is x >= 5, and !(x == y) is x != y.

aba && b!(a && b)!a || !b
truetruetruefalsefalse
truefalsefalsetruetrue
falsetruefalsetruetrue
falsefalsefalsetruetrue
A truth table proof: the last two columns match in every row, so !(a && b) and !a || !b are equivalent.
?Wait, what's a truth table again?
A truth table lists every possible combination of true and false for the inputs, one row each, and the value of an expression for each row. With two boolean inputs there are 4 rows; with three there are 8. If two expressions have the same column, they're equivalent.

Put the two rules together. "Not between 1 and 10," !(x >= 1 && x <= 10), becomes !(x >= 1) || !(x <= 10), which is x < 1 || x > 10. Notice that >= flipped to <, and && flipped to ||. Forgetting to flip either one is the top trap.

Comparing objects: == versus equals

For objects, == and != compare references. a == b is true only when a and b point to the very same object, which means they're aliases. The equals method compares contents: for Strings, the same characters in the same order. Two separate String objects can hold identical text, and then a == b is false while a.equals(b) is true.

String aString cString b"spring""spring"a == ctruea == bfalsea.equals(b)true
Three String variables and two String objects. a and c are aliases. b points to a different object with the same characters.
1String a = "spring";2String b = new String("spring");13String c = a;4System.out.println(a == b);25System.out.println(a.equals(b));36System.out.println(a == c);47System.out.println(b != null);5
  1. line 2 new always makes a separate object
  2. line 4 Two different objects: different arrows
  3. line 5 Same characters, in order
  4. line 6 Aliases: the very same object
  5. line 7 == and != are the right way to test null
output › false true true true
The same situation in code, run under Java 17. Use equals for contents and == only for "same object" or for null.
?Wait, what's an alias again?
An alias is a second reference to the same object. String c = a; doesn't copy the text, it copies the arrow, so a and c point to one object. That's why a == c is true.

There's one comparison where == is exactly right: checking for null. If a reference might be null, test it with obj == null or obj != null before calling any method on it. Calling obj.equals(...) on a null reference throws a NullPointerException.

Pause and think
Is !(x >= 10 || y < 3) equivalent to x < 10 && y >= 3? Use De Morgan.
I thought about it. Show me
Yes. Negate each part and flip the operator: !(x >= 10) is x < 10, !(y < 3) is y >= 3, and || becomes &&. So the expression is x < 10 && y >= 3.
Find the equivalent condition
A program uses !(age < 13 || age > 19) to test something about an int age. (a) Rewrite it without the !. (b) What does it mean in words? (c) A student claims it's the same as age >= 13 || age <= 19. Give a counterexample.
  1. (a) De Morgan: negate each comparison and flip || to &&. !(age < 13) is age >= 13 and !(age > 19) is age <= 19. So it's age >= 13 && age <= 19.
    Why?
    Two flips per law: each piece, and the operator between them.
  2. (b) It's true for ages 13 through 19: the teenagers.
  3. (c) Try age = 30. The original: 30 < 13 is false, 30 > 19 is true, so the || is true and the ! makes it false. The student's version: 30 >= 13 is true, so the || is true. They disagree, so they're not equivalent. (In fact the student's version is true for every age.)
    Why?
    One input where the two disagree is a complete proof that they are not equivalent.

Answer: (a) age >= 13 && age <= 19 (b) age is 13 to 19 (c) age = 30 makes the original false and the student's version true.

Stuck? Get a hint
  1. Use De Morgan: negate each comparison, and change || to &&.
  2. The negation of < is >=, and the negation of > is <=.
  3. For (c), pick an age far outside 13 to 19 and evaluate both.
Check yourself
Which expression is equivalent to !(a || !b) for all boolean values of a and b?
  1. A!a || b
  2. B!a && b
  3. Ca && !b
  4. D!a && !b
Show the answer

B. De Morgan: negate each part and flip || to &&. !a stays !a, and !(!b) is just b, so the result is !a && b. Choice D is the trap: it forgets that negating !b gives b back. Choice A negates correctly but forgets to flip the operator.

Check yourself
What is printed?
String part = "pe";
String x = part + "ar";
String y = "pear";
System.out.println((x == y) + " " + x.equals(y));
  1. Atrue true
  2. Bfalse true
  3. Cfalse false
  4. Dtrue false
Show the answer

B. x is built from pieces at run time, so it's a new String object, separate from y. x == y compares arrows: false. x.equals(y) compares characters: both are "pear", so true. Choice A is the trap: the text is the same, but == doesn't look at the text.

  • Equivalent means same value for every input. Prove with a truth table; disprove with one counterexample.
  • De Morgan: !(a && b) is !a || !b; !(a || b) is !a && !b.
  • Negated comparisons: !(x < y) is x >= y; !(x == y) is x != y.
  • For objects, == means same object (aliases). equals compares contents. Test for null with ==.