BHSawesome AP CSA

As with the arithmetic operators, the two logical operators && and || each apply to only two operands and ! only applies to one. But we can build compound expressions where the operands are other expressions using either other logical operators or comparison operators. We saw some examples of this in the previous section.

Once we start writing compound expressions it’s important to know what the precedence of the different operators are and our middle-school PEMDAS is no help. In Java, ! has higher precedence than &&, and && is higher than ||. But parentheses still have the highest precedence of all so we can use them to group things the way we want them to be evaluated. For example !a && b is equivalent to (!a) && b. If instead we want to negate the value produced by the and expression we can write: !(a && b).

Also all the logical operators are lower precedence than the comparison operators which is why we can write 0 <= x && x < 100 rather than having to write: (0 <= x) && (x < 100).

Once we start writing complex compund boolean expressions things can get out of hand. Sometimes this happens organically as we write code because we add subexpressions to an expression as we realize different cases. “I want to run this code when the score is greater than one-hundred. No wait, greater than one-hundred and bonus points are greater than ten. Well, that but also when the player has at least one power up and more than ten bonus points.” Next thing you know we’ve got this (with parentheses added for clarity):

(score > 100 && bonusPoints > 10) || (powerUps > 1 && bonusPoints > 10)

That’s maybe not terrible but it’s not trivial either. When we look at that expression how sure are we that it’s capturing exactly the cases we care about? Luckily there are some techniques for simplifying an expression like that into something that might be easier to understand.

For instance, in this case we can notice that in both sides of the || the condition is something && bonusPoints > 10. Since the whole compound expression can only be true if one side or the other is true but whichever side it is, bonusPoints > 10 will have to be true. So that means we can factor it out similar to how we can factor \(a\) out of \(ab + ac\) to get \(a(b + c)\text{.}\) That gives us this:

bonusPoints > 10 && (score > 100 || powerUps > 1)

This trick also works when we have two || expressions combined with &&. Consider for instance this expression:

(score > 100 || bonusPoints > 10) && (score < 100 || bonusPoints > 10)

This time in order for the whole expression to be true both of the operands to the &&, i.e. the two || expressions have to be true. Since they both contain bonusPoints > 10, if that subexpression is true they will each be true and therefore the whole thing will be true. So we can factor it out like this:

bonusPoints > 10 || (score > 100 && score < 100)

But now there’s an even bigger payoff. Look carefully at the second expression. It’s true when the score is both greater and less than one hundred. Which can never happen so that subexpression will always be false. So we can simplify the larger expression to:

bonusPoints > 10 || false

And since the value of that now depends entirely on the left hand operand of the || we’ve simplified the whole original expression down to just:

bonusPoints > 10

One of the most powerful tools for manipulating boolean expressions are De Morgan’s Laws. Developed by Augustus De Morgan in the 1800s, they show how to simplify the negation of && and || expressions, i.e. anything in either of these two forms: !(a && b) or !(a || b)

The rule is pretty simple: apply the ! to each of the subexpressions and then switch the other operator with && changing to || and || changing to &&.

In Java, De Morgan’s Laws are written with the following operators:

You can probably convince yourself that these are valid with an actual example. Imagine, for instance, that you are trying to express whether you want to go to the movies. You won’t go if you’re broke or if you’re too tired but otherwise you will.

So one way to say whether you’ll go is to say, you’ll go if you’re not broke or tired. Or in Java: !(broke || tired). (In English we hear “broke or tired” as grouped together and both affected by the “not”.)

But another way to say it is that you will go to the movies if you are not broke and you’re not tired. Or in Java: !broke && !tired. Thus !(broke || tired) and !broke && !tired are two different ways of saying the same thing.

By themselves De Morgan’s laws don’t usually lead to big simplifications but by giving us a way to flip && to || and vice versa, they can be a useful step toward rearranging a complex expression into a form where we can apply other rules to simplify it.

And they’re really great for answering AP exam questions that give you one boolean expression and ask you to pick out which of several others is equivalent to it.

We can also simplify negated boolean expressions involving comparison operators like <, >, and ==. And we can negate a comparison expression by flipping the comparison operator. For instance !(a == b) is flipped to a != b. The relational operators can be flipped either by swapping the operands (a < b becomes b < a) or by flipping the operator. But we need to remember which are the actual flipped operators. For < it is not > but >= and likewise for > and <=. In other words, to flip a comparison operator change the < or > to the other symbol and add an = if there isn’t one or remove it if there is.

The other main technique for analyzing boolean expressions is called a truth table. Truth tables are a systematic way of analyzing the boolean expressions for all possible combinations values for the subexpressions.

For simple expressions a truth table can be used to spell out exactly what the values of that expression are. For instance, here are truth tables that show, in case you forgot, how &&, ||, and ! work.

But we can also build truth tables for more complex expressions and if we build tables for two different expressions we can then compare the tables to determine whether the expressions are equivalent.

Building truth tables is a brute force approach which can be more tedious than doing a bit of Boolean algebra but doesn’t rely on any algebraic insight to figure out which rules to apply in order to manipulate one expression into the same form as the other. So if you are comfortable with them, you can always use them to grind out an analysis.

To build a truth table for an expression make at table with, initially, a column for each variable that occurs in the expression. Then add a column to the right for each subexpression, working back up to the whole expression. Each new column should be an expression that combines the expressions we have already made columns for using just one operator.

For instance to make a truth table for the expression !(a && b) we’d make a table with these columns.

Then add as many rows as there are different combinations of values for the variables. With two variables there are \(2^2\) or four combinations.

After that, it’s just a matter of filling in the columns, moving from left to right. Since each column is an expression in terms of one or two subexpressions whose column has already been filled in that should be easy.

To determine if two expressions are equivalent, we can build truth tables for both expressions and then use the tables to check if for each combination of variable values the two expressions produce the same result. For instance, we can now build a table for !a || !b in order to show that De Morgan’s Law for && is true.

To compare the two tables, just look at the rightmost column of each and check that the values are the same for each now. (This assumes that you filled in the variabel combinations in the same order.) If they are, then the two expressions are equivalent. As you can see in those two tables the last column in both reads true, true, true, false so the expressions are equivalent.