Booleans

One of the fundamental things computers can do is choose between two options: if the answer is correct, add a point, otherwise don’t; if the mouse click is inside the box, do something; if the exam score is greater than 90 record an A; etc. In Java the boolean data type is used to represent the condition, the thing that is either true or false. That is it’s either true or false that answer is correct, that the click is inside the box, or that grade is greater than 90. We’ll learn about how to use boolean values to control our programs in a later chapter but for now we’ll focus on how we can compute with boolean values.

---

The data type is named for George Boole, a 19th century English mathematician who invented what is now called Boolean algebra, a system for dealing with statements made up of only true and false values.1

Writing literal boolean values is much simpler than numeric literals because there are only two values and there’s only one way to write each one: true and false. That’s it.

Boolean operators work the same way as all operators: they take one or more values and produce a new value. While the notation for some of the operators may not be familiar to you, you will find that you’ve been using the concepts behind them for as long as you’ve been able to answer yes/no questions.

There are a few kinds of Boolean operators. Some operate on boolean values and produce boolean values just like + operates on two ints and produces an int. We’ll call these logical operators and you’ll discover you already know exactly how they work.

Others operators operate on other kinds of values but produce boolean results such as telling us whether two values are equal or not equal, called equality operators, or whether one numeric value is greater than or less than another, called relational operators.

Logical operators

Logical operators are, as the name suggests, extremely logical. They allow us to combine boolean values in various ways. To take a concrete example, suppose I tell you there’s a kid in school named Hugo. And I tell you a few facts about Hugo: 1) he is funny, 2) he is tall, and 3) whatever your idea of athletic is, he’s the opposite. Armed with those three facts you can probably answer these questions:

• Is Hugo funny and tall?

• Is Hugo funny or athletic?

• Is Hugo not athletic?

If you answered “yes” to all three questions, then you already understand the three logical operators in Java, and, or, and not. Now you just need to learn how to write them in your code.

To illustrate how to write the boolean logical operators let’s assume we have three boolean variables: funny, tall, and athletic that describe Hugo and thus have the values true, true, and false.

The and operator is written &&. It takes two boolean values and evaluates to true if they are both true and false otherwise. In Java we might write the answer to the question, is Hugo funny and tall, as funny && tall which would be true because both values, funny and tall, are true.

The or operator and is written ||. It takes two boolean values and evaluates to true if either one is true, or both. Thus funny || athletic is true because funny is true.2

The not operator operates on just one value and flips, or negates, it. It is written ! and placed before the expression whose value we want to flip. So to ask if Hugo is not funny we write, !funny which we can read back in English as “not funny” which we know is false because funny is true and flipping true gives us false.

Equality operators

A Boolean question that we will frequently need to ask in our programs is are two values the same or specifically not the same. There are two operators in Java for asking those questions: the equals operator, written ==, and the not equals operator, written !=.

The two equality operators operate on values of any type but evaluate to a boolean value. For instance if x is an int variable then x == 10 will be true if the value of x is 10. And x != 9 will be true if the value of x is anything other than 9.

Note that the equals operator is written with two equals signs. In Unit 3 we’ll learn about the assignment operator which is written with just one equals sign, = which is very different. Perhaps one way to remember is that both == and != are written with two characters.

When we use == and != with int values things are pretty straightforward. Two int values are either the same or they are not. But if we compare double values with these operators we may get surprising results. Because double values are only an approximation of the real numbers, two different expressions that should be mathematically equivalent might not be represented by the exactly same double value and thus will not be ==. To see this for yourself, write a line of code below to print the value of the expression 0.3 == 0.1 + 0.2; it will be false!

And in the next section, when we discuss the String data type we’ll learn about how == operates on reference types which also isn’t always the notion of equality that we might care about.

Relational operators

Sometimes when we’re dealing with numeric values we care less about whether they’re exactly the same (or different) but how they relate to each other. For instance, is one bigger than the other? There are four relational operators in Java are used to compare numeric values, producing a boolean value.

• < Less Than

• > Greater Than

• <= Less than or equal to

• >= Greater than or equal to

If you have trouble telling < and > apart, think of < and > as arrows where the pointy end should point to the smaller value. If < (less than) points towards a smaller number on the left, then it evaluates to true. On the other hand a > (greater than) expression will be true only if the smaller number is on the right hand side. Or maybe you prefer the “hungry alligator” mnemonic beloved by elementary school teachers—think of < and > as the mouths of hungry alligators which always want to eat the bigger number; a < or > expression is only true if the alligator is in fact about to eat the bigger number.

To remember the correct order of the two characters in <= and >=, just write them in the same order you would say them in English: “less than or equal to” not “equal to or less than”.

Unlike in math, we cannot chain together relational operators like \(0 \leq x \leq 100\). Instead we need to combine multiple relational expressions with logical operators. For instance the previous mathematical expression, which checks if \(x\) is between 0 and 100 could be written in Java as 0 <= x && x <= 100. To check if a value is outside a range we can use the or operator to combine two relational expressions: x < 0 || x > 100.3

Some boolean recipes

Some boolean expressions come up over and over in many programs. So it’s worth learning to recognize them:

• To check if a number is positive: number > 0

• To check if a number is negative: number < 0

• To check if a number is not negative: number >= 0

• To check if a number is not positive: number <= 0

The equality operators are also combined with the remainder operator from the previous section in a couple idioms. These idioms come up frequently both in real programming and on the AP exam so they’re worth knowing:

• To check if a number is even: num % 2 == 0

• To check if a number is odd: num % 2 !== 0

• To check if a number is divisible by another number: num % divisor == 0.

• To check if a number is not divisible by another number: num % divisor != 0.4

Short circuit evaluation

Both && and || use what is called short circuit evaluation. That means that the second expression (on the right of the operator) isn’t evaluated if the result from the first expression is enough to tell if the whole boolean expression is true or false. In particular:

• If the first operand to || evaluates to true, then the second expression won’t be evaluated at all because it can’t possibly change the result—one true is enough for the whole || expression to be true.

• If the first operand to an && evaluates to false then the second expression won’t be evaluated since there’s no way for the whole expression to be true if the first operand is false.

This may occasionally yield a minute performance gain if you have two expressions and one is much more expensive to evaluate than the other: put the cheap one first and maybe you won’t have to do the second one.

But a more useful application of short circuiting is to avoid evaluating an expression that may not be safe to evaluate. For instance, recall from the numbers section that doing an int division with a 0 divisor causes an ArithmeticException. Suppose you have a variable d that could possibly be zero but you want to do something if it’s not and if it goes into num fewer than ten times. This boolean expression will safely figure that out because if d is zero the short circuiting of && will prevent it from trying to perform the division: d !== 0 && num / d < 10.

Compound boolean expressions

As with numeric expressions, we can make compound boolean expressions since the operands can be any expressions. Here are some example compound boolean expressions, assuming the variables a, b, c, and d are all booleans:

a && b || c && d
(a || b) && (c || d)
!a && !b

Like arithmetic operators, logical operators have different precedence. ! is the highest, then &&, and then ||. As always, grouping with parentheses, as in the second expression above, has the highest precedence. (Without the parentheses that expression would be equivalent to a || (b && c) || d.)

Simplifying boolean expressions

When you get to using boolean expressions in programs, you’ll probably discover from time to time that you’ve made a very complicated boolean condition. Often times, however, you can simplify a complex expression into an equivalent one just like in math class you might simplify \(a \times b + a \times c\) into \(a \times (b + c)\). And on the AP exam there are often problems that ask you to determine whether two boolean expressions are equivalent.

There are two techniques for determining if two expressions are equivalent and in some cases simplifying expressions. One, is very mechanical and reliable but a bit slower, while the other is quicker but requires a bit of comfort with manipulating expressions according to rules. The slow and reliable way is to build a truth table and is best for determining whether two expressions are equivalent. The quicker way is to use Boolean algebra which is a lot like the algebra you use in math class except the rules for how you can rewrite expressions are based on Boolean operators not arithmetic ones.

Truth Tables

A truth table is a table that contains a row for each possible combination of operands in an expression and then a column that shows the result of the whole expression for each combination. When analyzing complex expressions we will usually create intermediate columns that show the values of sub-expressions for each combination of input. A simple truth table like the one below can show us the result for a simple boolean expression like P && Q when P and Q are boolean variables. For a simple expression we can fill in the the final column based on the definition of the && operator.

P	Q	P && Q
false	false	false
false	true	false
true	false	false
true	true	true

Similarly, here’s the truth table for the expression P || Q.

P	Q	P || Q
false	false	false
false	true	true
true	false	true
true	true	true

Truth tables come into their own when trying to understand a more complex expression. For instance, let’s try to understand funny && (short || !funny).

To build a truth table we need a table with one row for each possible combination of the variables in the expression. Since there are just two, there are four rows. Then we need a column for each of the sub-expressions all the way down to the individual variables. Organize the columns from the simplest sub-expressions to the most complex. So the first two columns will be just the variables, then, in this case, the expression !funny since it only involves one variable. Then the simplest expression that can be built from sub-expressions already in a column is tall || !funny. Then finally we have all the pieces we need to build the full expression which goes in the final column. Here’s the table with the possible values for funny and tall filled in.

funny	tall	!funny	tall || !funny	funny && (tall || !funny)
false	false
false	true
true	false
true	true

Now the process of filling in the rest of the table is pretty mechanical. Moving from left to right fill in one column at a time, reading off the values from the columns you’ve already filled in and applying the basic operator. For instance to fill in the first row of this table we fill in the !funny column by looking at the value in the already-filled-in funny column and applying the ! operator to it. Then we can fill in the tall || !funny columns by looking at the values in the tall column and !funny column and applying the || operator to them. Then finally apply the && operator to the values from the funny column and the tall || !funny columns to fill in the last column. Then do the same for the other three rows and you get this completed truth table:

funny	tall	!funny	tall || !funny	funny && (tall || !funny)
false	false	true	true	false
false	true	true	true	false
true	false	false	false	false
true	true	false	true	true

So what does that get us? One way to use truth tables is to find another table that has the same values in the final column. If you can (and assuming you ordered the rows the same way) that tells you that the two expressions in the two truth tables are equivalent. In this case if you look back at the P && Q truth table you’ll see it has the same values, false, false, false, true. So this more complex expression actually just boils down to funny && tall.

Obviously truth tables work great if you are given two expressions and need to determine if they are equivalent. By filling in two truth tables and seeing if the final columns are the same, you can simply and mechanically determine whether the two expressions are equivalent.

However if you only have one expression and want to simplify it—a more common scenario when you’re writing code—they’re less useful. Or if you have a several expressions and you want to determine which ones are equivalent; filling out a bunch of truth tables can get a bit tedious.

That’s where a bit of familiarity with Boolean algebra can come in handy.

Boolean algebra

If you’ve taken algebra, you should be familiar with simplifying expressions like \(a \times b + a \times c\) into \(a \times (b + c)\). We can do that because of the way the \(\times\) and \(+\) operators work in math. In this case we’re using the “distributive property of multiplication” which says we get the same result whether we multiply a sum or multiply by each element of the sum and then add the results together.

Boolean operators have a similar set of rules that allow us to manipulate Boolean expressions. If you are comfortable with normal mathematical algebra, you might find Boolean algebra easier to deal with than laboriously grinding out truth tables. We won’t cover all the rules which are summarized here but here’s a taste of how it works.

Let’s start with the same complicated expression as before:

funny && (tall || !funny)

Just like there’s a a distributive property of multiplication, there’s also a distributive property of && that lets us distribute it over the two operands of an || expression:

funny && tall || funny && !funny

Because of the higher precedence of && than || that’s the same as:

(funny && tall) || (funny && !funny)

Let’s look at each side separately. The left hand side is pretty normal looking but the right hand side—the expression funny && !funny—is a bit, well, funny. Aristotle pointed out over a couple thousand years ago that something can’t be true and false at the same time. So any expression like funny && !funny is automatically false. So we can rewrite that as:

(funny && tall) || false

And finally, because only one of the operands of an || has to be true for the whole || expression to be true the false has no effect. So we can eliminate it and we’re left with the much simpler expression:

funny && tall

Note that this is the same simplification we figured out above by recognizing the truth table was the same as the P && Q table.

De Morgan’s laws

One particularly useful bit of Boolean algebra that the College Board wants you to know about are a pair of laws known as De Morgan’s laws. Developed by Augustus De Morgan in the 1800s, they show how to simplify the negation of a Boolean expression involving an && or an ||, something like !(funny && tall) or !(funny || tall).

One way to think about De Morgan’s laws are they are like a distributive property for the ! operator: they tell us how to move the ! inside the parentheses of the negated expression. There are two laws and they are symmetric:

• !(a && b) is equivalent to !a || !b

• !(a || b) is equivalent to !a && !b

In other words, we can move the ! inside the parentheses, applying it to each element of the negated expression individually and then switch the && to || or vice versa.

There are a number of ways to see that these laws are true. Intuitively we understand that if we say some is not funny and tall, meaning !(funny && tall), that in order for that statement to be true it has to be the case that either they are not funny or they are not tall, i.e. !funny || !tall. Similarly, if someone is not funny or tall, i.e. !(funny || tall), then it has to be true that they are both not funny and not tall, i.e. !funny && !tall.

You can also prove De Morgan’s laws by creating truth tables for the four expressions above and seeing which expressions are equivalent.

Applying De Morgan’s laws

De Morgan’s laws are most useful for dealing with expressions involving multiple levels of sub-expressions. Suppose for instance we are casting for a role in our school play and the director says the actor needs to be funny and the assistant director, who isn’t convinced they even need to be funny just says they don’t want an actor who’s funny and tall. Without thinking too much about it, we can combine combine the director’s and the assistant director’s opinions and the combination like this:

funny && !(funny && tall)

But that’s kind of hairy and we’d like to simplify it. We can’t distribute the funny && funny the || because of the ! on the right-hand side. But we can use one of De Morgan’s laws to move the ! inside the parens:

funny && (!funny || !tall)

Now we can distribute funny && over each side:

(funny && !funny) || (funny && !tall)

As above funny && !funny is a contradiction and thus has to be false:

false || funny && !tall

And false has no effect on an || expression so we can simplify down to:

funny && !tall

So we’re looking for someone who’s funny and not tall. In a real world casting situation we’d could just check each actor against the two criteria and only accept actors who met both without thinking about how to combine them. But in a program it’s going to be a lot easier to understand code that contains the expression funny && !tall than the original.5

A note on negation

Note that adding ! operators is not the only way to negate an expression. If an expression is already negated with ! you can negate it by removing the !. So

!(funny || !tall)

simplifies, via De Morgan’s laws, to

!funny && tall

In Boolean expressions involving equality and relational operators instead of adding a ! we can just swap the equality or relational operator to the operator with the opposite meaning: == becomes !=, < becomes >=, > becomes <=, and vice versa. This allows us to get rid of the ! altogether. For instance:

!(x < 3 && y > 2)

becomes:

x >= 3 || y <= 2

For the exam

You do not have to memorize De Morgan’s Laws for the AP exam, but there are usually several questions about identifying equivalent boolean expressions. You can use truth tables or Boolean algebra, whichever you are more comfortable with. However once you are used to it, using Boolean algebra tends to be quicker.