AP Computer Science Java: Lesson 2.8
Conditional Statements - Boolean Expressions

Lesson 2.8 - Boolean Expressions
Purpose: To learn how to evaluate boolean expressions using order of operations

Compound Booleans   Sometimes programmers need to write complex boolean statements or expressions. For instance, consider a game played by two players in which the first person to score 10 points wins. We could write a statement like this to determine whether or not the game is over:

   gameOver = score1>=10 || score2>=10;

This would not work though in the event that both scores were the same (the game would be tied). So the program would also need to check whether or not the two scores were the same. Let's revise:

   gameOver = score1>=10 || score2>=10 && score1!=score2;

This new form checks to see whether either score is at least 10 and that the two scores are different (so one player has more points than the other, ending the game). Only one problem - it will not work due to the order of operations for logical operators.

The order of operations for logical operators is NOT, AND, OR (!, &&, ||). So ! is evaluated first, then &&, followed by ||. So to make the above expression work as intended, parentheses must be added around the OR part so that is evaluated first (otherwise, it evaluates the AND first, potentially causing an invalid result).

   gameOver = (score1>=10 || score2>=10) && score1!=score2;
  

Truth Tables  Up to this point, you have informally learned the following about AND and OR:

   1. AND (&&) is only true when both of its operands are true
   2. OR (||) is only true when at least one of its operands are true

Formally speaking, here are the truth tables for AND and OR (assume A and B represent boolean variables or boolean expressions):

Evaluating Compound Boolean Expressions  In the following expression, assume that A, B and C are declared as boolean variables and that A=false, B=false and C=false. To evaluate the expression we will use the truth tables and the order of operations discussed in this lesson.

A || !B && !(C || B)

Substituting the values of the variables we get:

false || !false && !(false || false)

We begin with the parentheses which evaluate to false since both B and C are false. We now have an expression that reads

false || !false && !(false)

Evaluating the !'s reduces it to

false || true && true

Now evaluate the AND

false || true

Finally, evaluate the OR to get

true (since at least one operand is true)

DeMorgan's Laws  British Mathematician Augustus DeMorgan first discovered the following two theorems which now bear his name:

!(A && B) = !A || !B
!(A || B) = !A && !B

To help you remember them, notice that the ! acts like a negative sign in front of parentheses in Algebra, changing everything inside to its opposite. DeMorgan's Laws become useful in eliminating parentheses in some compound Boolean expressions. Here is an example:

boolean result = !(x==10 || y!=10);

would become

boolean result = x!=10 && y==10;

In closing, Boolean expressions are typically one of the most confusing topics in computer science. In fact, students taking the AP exam usually do poorly on questions on this topic. Focusing on the order of operations and the truth tables are the keys to success.