AP® Computer Science A review sheet from Aim for Five (aimforfive.com/csa/units/2/2-6)
Unit 2 · Topic 2.6
2.6 Comparing Boolean Expressions
Two Boolean expressions can look different and still always give the same answer. This topic shows how to prove that with a truth table, how De Morgan's laws rewrite a negated condition, and how comparing objects with == differs from comparing them with equals.
Key terms
- equivalent expressions
- De Morgan's laws
- truth table
- alias
equalsmethod
Equivalent expressions
Two Boolean expressions are equivalent if they give the same result for every possible combination of values. To prove it, build a truth table with a row for each combination and check the two result columns match in every row. To prove two expressions are not equivalent, you only need one row where they differ.
De Morgan's laws
De Morgan's laws tell you how to push a ! into parentheses. When the ! moves inside, each part gets negated, and && and || swap:
!(a && b)is equivalent to!a || !b!(a || b)is equivalent to!a && !b
Negating comparisons
When a and b are comparisons, negate each one by flipping it, not just the direction of the symbol:
| Comparison | Its negation |
|---|---|
| x > 3 | x <= 3 |
| x < 3 | x >= 3 |
| x == 3 | x != 3 |
Checking De Morgan with a truth table
Here's !(a && b) against !a || !b. The column labeled "left side" is !(a && b) and the one labeled "right side" is !a || !b. They match in every row, so the expressions are equivalent.
| a | b | a && b | left side | right side |
|---|---|---|---|---|
| true | true | true | false | false |
| true | false | false | true | true |
| false | true | false | true | true |
| false | false | false | true | true |
Comparing object references
With objects, == and != compare references. Two variables that refer to the same object are called aliases, and == is true for them. Two different objects give false, even when they hold identical data.
You can compare a reference with null using == or != to check whether it refers to an object at all. Calling a method on a null reference throws a NullPointerException, so a check like name != null && name.equals("Ava") uses short-circuiting to stay safe.
To compare contents, classes provide an equals method that decides what "the same" means, usually by comparing attributes. For String, equals checks that the characters match.
String first = new String("map");
String second = new String("map");
String third = first;
String nothing = null;
System.out.println(first == second);
System.out.println(first.equals(second));
System.out.println(first == third);
System.out.println(nothing == null);
This prints false, true, true, true: different objects, same letters, aliases, and a null check.
Not on the exam
You won't be asked to write your own equals method for a class. You just need to use the ones classes already have.
Worked examples
Try each one yourself first, then open the solution.
- Example 1
Applying De Morgan's laws
Which expression is equivalent to
!(x > 3 && y <= 5), wherexandyareintvariables? (A)x > 3 || y <= 5(B)x <= 3 && y > 5(C)x <= 3 || y > 5(D)x < 3 || y >= 5Show the solutionHide the solution
- Step 1: De Morgan:
!(a && b)becomes!a || !b. So the&&turns into||, which rules out (B). - Step 2: Negate each comparison. The opposite of
x > 3isx <= 3(3 itself now counts). The opposite ofy <= 5isy > 5. - Step 3: That gives
x <= 3 || y > 5. Choice (D) flips the symbols but gets the boundaries wrong: withx= 3 andy= 2, the original is true and (D) is false. - Step 4: As a check, try
x= 2 andy= 9: the original is!(false && false), which istrue, and (C) istrue || true, alsotrue. Because every step followed De Morgan's law, (C) agrees with the original for every possiblexandy, not just these.
Answer: (C)
x <= 3 || y > 5. - Step 1: De Morgan:
- Example 2
== versus equals
What does this code print?
String first = new String("map"); String second = new String("map"); String third = first; String nothing = null; System.out.println(first == second); System.out.println(first.equals(second)); System.out.println(first == third); System.out.println(nothing == null);Show the solutionHide the solution
- Step 1:
firstandsecondare made with separatenewcalls, so they're two different objects.first == secondisfalse. - Step 2: They hold the same characters, so
first.equals(second)istrue. - Step 3:
third = firstcopies the reference, makingthirdan alias offirst.first == thirdistrue. - Step 4:
nothingholdsnull, sonothing == nullistrue.
Answer: Four lines:
false,true,true,true. - Step 1:
Common mistakes
- Moving the
!inside without swapping&&and||. Both changes are needed. - Negating
x > 3asx < 3. The opposite of "greater than" is "less than or equal to". - Using
==to compare the contents of two objects. It only tells you whether they're the same object. - Calling
equalson a variable that might benull. Check fornullfirst.
On the exam
- A classic multiple-choice question gives a negated compound condition and asks which expression is equivalent. Apply De Morgan step by step, then test a boundary value to be sure.
- To show two expressions are not equivalent, find one set of values where they disagree. That's often faster than a full truth table.
Connected topics
Videos
Check yourself
4 questions on 2.6 Comparing Boolean Expressions. Pick an answer to see if you got it, and why.
Assume x and y are int variables. Which of the following expressions is equivalent to !(x > 3 && y != 0)?
Assume a and b are boolean variables. Which of the following expressions is equivalent to !(a || !b)?
| a | b | Result |
|---|---|---|
| true | true | false |
| true | false | true |
| false | true | true |
| false | false | false |
Truth table
Which of the following expressions produces the Result column for all four rows of the table?
Assume n is an int variable. Which of the following best describes the values of n for which !(n < 5) && !(n > 10) evaluates to true?
0 of 4 answered