Comparing Boolean Expressions

Two students write the “did you pass?” check for a quiz app. Jordan writes !(score < 60), which reads “it is not true that the score is below 60.” Priya writes score >= 60, which reads “the score is at least 60.” Their teammate asks: can we use either one, or will they sometimes disagree? Before you can swap one condition for another, you need a way to answer that question for sure.

In plain words, two conditions are interchangeable when they always give the same answer, no matter what values the variables hold. Not just for the score you happened to try, but for every score that could ever show up. Two Boolean expressions that evaluate to the same value in every possible case are called equivalent Boolean expressions. If you can swap one for the other anywhere in a program and nothing could ever change, they are equivalent.

That “every possible case” part has two consequences:

• One mismatch is enough to prove two expressions are not equivalent. A case where one expression is true and the other is false is called a counterexample. Find one, and you are done.
• Matching on a few cases proves nothing. Two expressions can agree on the values you tried and still disagree on a value you did not try. To show equivalence, you need a reason that covers every case.

int score = 59;
System.out.println(!(score < 60) + " " + (score >= 60));
score = 60;
System.out.println(!(score < 60) + " " + (score >= 60));
score = 61;
System.out.println(!(score < 60) + " " + (score >= 60));

false false
true true
true true

This reasoning gives you a handy pattern. Putting ! in front of a single comparison is the same as using the opposite comparison:

Notice that the opposite of < is >=, not >. The opposite of “below” has to include “equal.”

Now vary the operator. Is temp > 32 || temp == 32 equivalent to temp >= 32? Check around the boundary again:

int temp = 31;
System.out.println((temp > 32 || temp == 32) + " " + (temp >= 32));
temp = 32;
System.out.println((temp > 32 || temp == 32) + " " + (temp >= 32));
temp = 33;
System.out.println((temp > 32 || temp == 32) + " " + (temp >= 32));

false false
true true
true true

Both columns match at 31, 32, and 33. The reason they match everywhere: || is true when either part is true, so the left expression is true when temp is greater than 32 or equal to 32. “Greater than or equal to” is exactly what >= means. They are equivalent.

int score = 60;
System.out.println(!(score < 60));
System.out.println(score > 60);

true
false

In 2.6.1 you proved equivalence by reasoning about what the comparison means. That works, but it can get slippery when an expression combines several boolean variables with &&, ||, and !. You need a method that checks every case mechanically, with no clever insight required.

Here is the good news: a boolean variable has only two possible values, true and false. So an expression built from a couple of boolean variables has only a few possible situations. With one variable there are 2. With two variables, each of the 2 values for the first can pair with each of the 2 values for the second, giving 2 × 2 = 4. With three variables there are 2 × 2 × 2 = 8. You can simply write down every situation and check them all.

A truth table is a table with one row for every possible combination of true and false for the variables, and a column showing the value of each expression in that row. If two expressions have identical columns in every row, they are equivalent, because the table covers every case there is. If any single row differs, that row is a counterexample.

A reliable way to list the rows for two variables a and b is to start with a true for the first two rows and false for the last two, and let b alternate true, false, true, false. That order guarantees no combination is missed or repeated.

boolean member = true;
boolean coupon = true;
System.out.println((member || (member && coupon)) + " " + member);
coupon = false;
System.out.println((member || (member && coupon)) + " " + member);
member = false;
coupon = true;
System.out.println((member || (member && coupon)) + " " + member);
coupon = false;
System.out.println((member || (member && coupon)) + " " + member);

true true
true true
false false
false false

Now vary the expressions. Is !(a && b) equivalent to !a && !b? Many students guess yes, because it looks like the ! was just “handed out” to each part. Build the table:

Compare the !(a && b) column with the !a && !b column. Rows 2 and 3 differ. For example, in row 2, a && b is false, so !(a && b) is true; but !a is false, so !a && !b is false. They are not equivalent. Java agrees:

boolean a = true;
boolean b = true;
System.out.println(!(a && b) + " " + (!a && !b));
b = false;
System.out.println(!(a && b) + " " + (!a && !b));
a = false;
b = true;
System.out.println(!(a && b) + " " + (!a && !b));
b = false;
System.out.println(!(a && b) + " " + (!a && !b));

false false
true false
true false
true true

The second and third lines show the two rows where the expressions disagree. You will see the correct way to move a ! inside parentheses in 2.6.3.

Programs often need the opposite of a compound condition. A movie theater charges a teen price when age >= 13 && age <= 19. To charge everyone else the regular price, you could write !(age >= 13 && age <= 19), but a ! wrapped around a whole compound expression is hard to read and easy to get wrong, as the truth table at the end of 2.6.2 showed. You need a dependable rule for moving that ! inside.

Think about what the words mean. “It is not true that I have both a ticket and a snack” means “I am missing the ticket, or I am missing the snack (or both).” And “It is not true that it is Saturday or Sunday” means “it is not Saturday and it is not Sunday.” When the “not” moves inside, two things happen: each part gets its own “not,” and the joining word flips between “and” and “or.”

These two rules are called De Morgan’s laws:

To apply either law: negate each part, and change && to || or || to &&. Both steps are required; doing only one of them gives a different expression.

Why should you believe these rules? Because a truth table proves them, using the method from 2.6.2.

boolean a = true;
boolean b = true;
System.out.println(!(a && b) + " " + (!a || !b) + "   " + !(a || b) + " " + (!a && !b));
b = false;
System.out.println(!(a && b) + " " + (!a || !b) + "   " + !(a || b) + " " + (!a && !b));
a = false;
b = true;
System.out.println(!(a && b) + " " + (!a || !b) + "   " + !(a || b) + " " + (!a && !b));
b = false;
System.out.println(!(a && b) + " " + (!a || !b) + "   " + !(a || b) + " " + (!a && !b));

false false   false false
true true   false false
true true   false false
true true   true true

In real code, the parts are usually comparisons. Negating a part means using the opposite comparison from the table in 2.6.1.

int age = 12;
System.out.println(!(age >= 13 && age <= 19) + " " + (age < 13 || age > 19));
age = 13;
System.out.println(!(age >= 13 && age <= 19) + " " + (age < 13 || age > 19));
age = 19;
System.out.println(!(age >= 13 && age <= 19) + " " + (age < 13 || age > 19));
age = 20;
System.out.println(!(age >= 13 && age <= 19) + " " + (age < 13 || age > 19));

true true
false false
false false
true true

Now vary the operator that is negated. Days of the week are numbered 1 to 7, with 6 and 7 for Saturday and Sunday. A weekday check written as !(day == 6 || day == 7) uses ||, so the second law applies: negate each part (day != 6, day != 7) and flip || to &&, giving day != 6 && day != 7.

int day = 3;
System.out.println(!(day == 6 || day == 7) + " " + (day != 6 && day != 7));
day = 6;
System.out.println(!(day == 6 || day == 7) + " " + (day != 6 && day != 7));
day = 7;
System.out.println(!(day == 6 || day == 7) + " " + (day != 6 && day != 7));

true true
false false
false false

For day = 3, both are true; for 6 and 7, both are false. Notice why && is right here: a weekday must be not Saturday and not Sunday. With ||, every day would pass, since any day is either not 6 or not 7.

int age = 12;
System.out.println(!(age >= 13 && age <= 19));
System.out.println(age < 13 && age > 19);

true
false

int age = 15;
boolean notTeen = !age >= 13;

int hour = 20;
if (hour < 9 && hour > 17)
{
    System.out.println("Closed");
}
else
{
    System.out.println("Open");
}

if (hour < 9 || hour > 17)

So far every comparison was between numbers or boolean values. Programs also compare objects: is this the same Scanner I was using, or is this the same String object? Topic 2.2 told you that == on reference types compares references, not contents. This subsection shows exactly what that means.

Recall from Topic 1.13 that a reference variable does not hold an object. It holds a reference, which you can picture as the object’s address. Picture it as a sticky note with an address written on it. Assigning one reference variable to another, as in second = first;, copies the address onto a second sticky note. It does not build a second object. Both notes now lead to the same object. When two variables hold references to the same object, they are called aliases of that object, the way one person can go by two names.

When == compares two reference variables, it asks: do these two variables hold the same address? In other words, do they refer to the very same object? != asks the opposite: do they refer to different objects? Neither operator looks inside the objects at all.

String first = new String("Lion");
String second = first;
String third = new String("Lion");
System.out.println(first == second);
System.out.println(first == third);
System.out.println(first != third);

true
false
true

Being aliases is not permanent. Assigning a new reference to one of the variables changes what it refers to:

String first = new String("Lion");
String second = first;
System.out.println(first == second);
second = new String("Lion");
System.out.println(first == second);
System.out.println(second);

true
false
Lion

After line 2, first == second is true. Line 4 builds a brand-new object and stores its address in second, so second no longer refers to the object that first refers to. Line 5 prints false, even though line 6 shows that second still holds the text Lion.

Aliases matter because whatever you do through one variable happens to the one shared object. String objects cannot be changed (Topic 1.15), so with strings you rarely notice. A Scanner makes it visible, since reading a value moves the Scanner forward through its input:

import java.util.Scanner;

public class SharedScanner
{
    public static void main(String[] args)
    {
        Scanner reader = new Scanner("7 8 9");
        Scanner sameReader = reader;
        System.out.println(reader == sameReader);
        System.out.println(reader.nextInt());
        System.out.println(sameReader.nextInt());
    }
}

true
7
8

Line 8 makes sameReader an alias of reader, so line 9 prints true. Line 10 reads 7 through reader. Line 11 reads through sameReader, but it is the same Scanner object, which has already moved past the 7, so it reads 8. There is only one Scanner, with one position in its input.

String saved = new String("pass");
String typed = new String("pass");
if (typed == saved)
{
    System.out.println("Welcome");
}
else
{
    System.out.println("Wrong password");
}

Wrong password

String p = new String("pear");
String q = p;
String r = new String("pear");
System.out.println(q == p);
System.out.println(r == p);
System.out.println(q != r);
p = r;
System.out.println(p == r);
System.out.println(q == p);

true
false
true
true
false

In Topic 1.14 you saw that calling a method on a variable holding null crashes the program with a NullPointerException. In real programs a variable is sometimes null on purpose: a player has not picked a nickname yet, or a search found nothing. How can a program find out, before calling a method, whether a variable refers to an object at all?

Recall that null is a special value meaning “this variable refers to no object” (Topic 1.13). Since == and != compare what reference variables hold, they can compare a reference with null too:

Comparing with null never calls a method, so it is always safe, even when the variable is null. That makes it the right first step before using an object.

String nickname = null;
if (nickname == null)
{
    System.out.println("No nickname yet");
}
else
{
    System.out.println(nickname.length());
}
nickname = "Sky";
if (nickname == null)
{
    System.out.println("No nickname yet");
}
else
{
    System.out.println(nickname.length());
}

No nickname yet
3

Often a program wants to check for null and test the object in a single condition. Short-circuit evaluation from Topic 2.5 makes that safe: with &&, if the left side is false, Java never evaluates the right side.

String nickname = null;
if (nickname != null && nickname.length() > 3)
{
    System.out.println("Long nickname");
}
else
{
    System.out.println("No long nickname");
}
nickname = "Skyler";
if (nickname != null && nickname.length() > 3)
{
    System.out.println("Long nickname");
}
else
{
    System.out.println("No long nickname");
}

No long nickname
Long nickname

On line 2, nickname is null, so nickname != null is false. Because the left side of && is false, the whole condition must be false, and Java skips nickname.length() > 3 entirely. The method is never called on null, and the else prints No long nickname. Line 10 stores “Skyler”. On line 11 the null check is true, so Java evaluates nickname.length() > 3, which is 6 > 3, true. Placing the null check on the left of && like this is called a guard.

One more case to keep straight: an empty string is not null. "" is a real String object that happens to have no characters.

String blank = "";
System.out.println(blank == null);
System.out.println(blank.length());

false
0

blank refers to an object, so blank == null is false and blank.length() safely returns 0.

String nickname = null;
System.out.println("Checking");
if (nickname.length() > 3 && nickname != null)
{
    System.out.println("Long nickname");
}

Checking
Exception in thread "main" java.lang.NullPointerException: Cannot invoke "String.length()" because ...

String city = null;
if (city != null || city.length() > 0)
{
    System.out.println("City entered");
}
else
{
    System.out.println("No city");
}

if (city != null && city.length() > 0)

The password check in 2.6.4 failed because == asks “same object?” when the program needed “same contents?”. For two String objects, “same contents” means the same characters. For another kind of object, it might mean something else: two dates might count as the same if their day, month, and year match. Each class gets to decide what “equal” means for its own objects.

A class decides this by providing an equals method: a method that returns true when two objects should count as equivalent, according to rules the class sets. Those rules almost always compare the objects’ attributes, the data each object stores (Topic 1.12). String has an equals method (Topic 1.15) whose rule is: two strings are equal when they have exactly the same characters in the same order, with the same capitalization. So for strings:

Writing an equals method for a class of your own is not part of this course. You only need to call equals methods that classes already provide, mainly the one in String.

String saved = new String("Tiger42");
String typed = new String("Tiger42");
String copy = saved;
System.out.println(typed == saved);
System.out.println(typed.equals(saved));
System.out.println(copy == saved);
System.out.println(copy.equals(saved));
System.out.println(typed.equals("tiger42"));

false
true
true
true
false

Using equals fixes the password check from 2.6.4. Only the condition changes:

String saved = new String("pass");
String typed = new String("pass");
if (typed.equals(saved))
{
    System.out.println("Welcome");
}
else
{
    System.out.println("Wrong password");
}

Welcome

Now vary how the string was made. A string built while the program runs, for example with +, is compared by its characters just the same:

String start = new String("ice");
String word = start + "cream";
System.out.println(word);
System.out.println(word.equals("icecream"));
System.out.println(word.equals("ice cream"));

icecream
true
false

equals does not care how or where the string was made, only what characters it holds. "ice cream" has a space, so it does not match.

What if the argument is null? saved.equals(typed) with typed holding null simply returns false, because there is no object to match. The method is called on saved, which is a real object, so nothing crashes:

String saved = new String("Tiger42");
String typed = null;
System.out.println(saved.equals(typed));

false

You may notice that == sometimes gives true for two separate variables assigned the same literal, such as String first = "hi"; and String second = "hi";. That happens because Java may reuse one object for identical literals in a program, so the two variables end up as aliases. It is a detail of how Java stores literals, not a comparison of text, and a string built with new or put together while the program runs will not necessarily be reused. Never rely on it: compare text with equals.

String saved = null;
System.out.println("Comparing");
System.out.println(saved.equals("Tiger42"));

Comparing
Exception in thread "main" java.lang.NullPointerException: Cannot invoke "String.equals(Object)" because ...

A door lock app stores a secret code and checks codes people enter. A code can also be missing (null) if nothing was entered. The program accepts a code when code != null && code.equals(savedCode). The programmer wants an if statement that tests for rejection first, so the rejection message appears at the top. The rejection condition is the negation:

!(code != null && code.equals(savedCode))

Apply De Morgan’s first law: negate each part and flip && to ||.

The rejection condition becomes code == null || !code.equals(savedCode). That condition is also safe to evaluate when code is null: the left side code == null is then true, so || short-circuits and never calls equals on null.

String savedCode = new String("RX42");
String typedCode = new String("RX42");
String wrongCode = new String("rx42");
String missingCode = null;
System.out.println(typedCode == savedCode);
System.out.println(typedCode.equals(savedCode));
if (typedCode == null || !typedCode.equals(savedCode))
{
    System.out.println("typedCode rejected");
}
else
{
    System.out.println("typedCode accepted");
}
if (wrongCode == null || !wrongCode.equals(savedCode))
{
    System.out.println("wrongCode rejected");
}
else
{
    System.out.println("wrongCode accepted");
}
if (missingCode == null || !missingCode.equals(savedCode))
{
    System.out.println("missingCode rejected");
}
else
{
    System.out.println("missingCode accepted");
}

false
true
typedCode accepted
wrongCode rejected
missingCode rejected

• Two Boolean expressions are equivalent when they give the same value in every possible case. One counterexample proves they are not; agreeing on a few cases proves nothing.
• A truth table lists every combination of values (4 rows for two variables) and proves or disproves equivalence completely.
• De Morgan’s laws: !(a && b) is equivalent to !a || !b, and !(a || b) is equivalent to !a && !b. Negate each part, flip the operator, and remember the opposite of < is >=.
• For references, == and != ask whether two variables refer to the same object. Aliases are ==; separate objects are not, even with identical data.
• Compare a reference with null using == or != before calling a method on it, and put that guard on the left of &&.
• Classes define an equals method to say when two objects are equivalent, usually by comparing attributes. Compare the text of strings with equals, never ==.

String a = new String("map");
String b = a;
String c = new String("map");
b = c;
System.out.println(a == b);
System.out.println(b == c);
System.out.println(a.equals(c));
System.out.println(a != c);

false
true
true
true

String stored = new String("blue");
String entered = new String("blue");
if (entered != stored)
{
    System.out.println("Access denied");
}
else
{
    System.out.println("Access granted");
}

if (!entered.equals(stored))

• I can explain what makes two Boolean expressions equivalent and use one counterexample to show two are not. Reread
• I can build a complete truth table and use it to prove or disprove equivalence. Reread
• I can apply De Morgan's laws to rewrite a negated && or || expression, including comparisons. Reread
• I can predict == and != for two references, including aliases and separate objects with the same data. Reread
• I can check a reference against null and order a guard so no method is called on null. Reread
• I can explain when to use equals instead of == and what a class equals method decides. Reread