Unit 2 Notes – Boolean Expressions (Conditional Logic)
Conditional Statements
The format of an if statement:
if(condition)
{
list of statements...
}
The "list of statements" will only be performed if the condition is TRUE. Also note that the "list of statements" can be one or more statements. Each individual statement must be terminated by a semi-colon. However, THERE IS NO SEMICOLON AFTER THE PARENTHESES OF THE CONDITION! Doing so terminates the connection between the “if” and the statements in the braces. Take care not to do this!
The braces used are actually only necessary if there is more than one statement to be performed if the condition is true. If there are no braces, only one statement is considered to be tied to the “if”. Let's look at some examples.
if(x < 10)
{
System.out.println("Single-digit number");
}
is equivalent to
if(x < 10)
System.out.println("Single-digit number");
or even
if(x < 10) System.out.println("Single-digit number");
But the two following are NOT equivalent:
if(x < 10)
{
System.out.println("Single-digit number");
System.out.println(x);
}
if(x < 10)
System.out.println("Single-digit number");
System.out.println(x);
In the first if, both print statements will only perform if x<10. In the second, only the first print statement is tied to the “if”. The second one will perform no matter what the result of the condition is. Indentation does not determine whether a statement is connected to an “if”, braces do.
In closing, while it is not necessary to put braces for one statement, programmers tend to do so as a good practice. One advantage is not having to remember them later when another statement is added to the “if” block.
Conditions
The condition of an “if” statement must be capable of returning a value of TRUE or FALSE. Additionally, the condition involves making a comparison between one value or expression and another value or expression. Such comparisons require the use of relational operators. Below is a list of Java's relational operators.
The Relational Operators of Java
Operator Meaning Example in if
== is equal to if(x == 3)
!= is not equal to if(x != 3)
< is less than if(x < 3)
> is greater than if(x > 3)
<= is less than or equal to if(x <= 3)
>= is greater than or equal to if(x >= 3)
Equals vs. Is Equal To
One of the first questions asked is what is the difference between = and ==? The difference is that = is used to assign a value to a variable, whereas == is used to determine if a variable contains a value. If a single equal sign is used in the condition, it actually assigns the value to the variable. This is not the intended result and will cause the program to execute incorrectly.
A Fork in the Road
When the condition in an “if” statement is true, the computer performs the statements enclosed in the braces, then moves on to the next portion of the program. But what if the condition is false? The statements inside the braces are ignored and then the computer moves on to the next portion of the program. For example, in the code below, if x is not less than 10, nothing happens.
if(x < 10)
{
System.out.println("Single-digit number");
}
While this may be fine in some situations, many times we want the computer to perform one set of actions if a condition is true and another set of actions if the condition is false. This is a job for the if..else statement! Here's the format:
if(condition)
{
list of statements...
}
else
{
other list of statements...
}
The "list of statements" will be performed if the condition is TRUE while the "other list of statements" will be performed if the condition is FALSE. So unlike the if statement, in an if..else statement, something will occur.
Let's look at an example:
if(x < 10)
{
System.out.println("Single-digit number");
}
else
{
System.out.println("Multi-digit number");
}
The following is equivalent:
if(x >= 10)
{
System.out.println("Multi-digit number");
}
else
{
System.out.println("Single-digit number");
}
Note that in the second form, the condition is the opposite of the original. By switching the statements in the “if” and “else” portions, the result is the same.
Also, since there is only one statement in each block, the original if..else above could be written more compactly as:
if(x < 10) System.out.println("Single-digit number");
else System.out.println("Multi-digit number");
In closing, use an if..else when an action is necessary for both true and false values of the particular condition in your program.
Multiple Conditions (Logical Operators AND/OR)
Sometimes it is necessary to evaluate more than one condition in an if statement. For example, to determine whether a person is a teenager, we need to find out if their age is at least 13, but also less than 20. The following if statement would not be sufficient for this task:
if(age >= 13)
{
System.out.println("You are a teenager");
}
This won't work if age happens to be, say, 35. It will incorrectly display that a 35-year-old is a teenager since 35 is greater than 13. To correctly address this situation, we can use the logical operator AND, which has the symbol &&:
if(age>=13 && age<20)
{
System.out.println("You are a teenager");
}
The && requires that both conditions be met in order to perform the statement in the braces. So if the variable age is 35, it will not enact the display statement since 35 is not less than 20.
Using OR
When only one of two conditions needs to be true to cause some action, the AND operator is not the correct choice. For this task, the OR operator is needed. The symbol for OR is two vertical bars (||). The vertical bar symbol can be found on the backslash key, directly above the enter key. Let's look at an example in which OR will be useful.
Suppose that a game is being played in which scores were being kept for two players in integer variables called score1 and score2. Suppose further that the game is over when one of the player's scores reaches 10. The following if statement could be used to check whether the game is over:
if(score1==10 || score2==10)
{
System.out.println("The game is over");
}
The AND operator would not be appropriate here because we don't need both scores to equal 10, just one of them. It is important to note, however, that an OR will still enact the statement in braces if both conditions are true since at least one of them is true. So if both score1 and score2 equal 10, the display statement will still occur.
In closing, when needing to evaluate more than one condition in an if statement, choose AND if both conditions need to be true and choose OR if only one of the conditions needs to be true. Be careful, as the wrong choice will yield unwanted results.
Smooth Operators
In the last lesson that we discussed how the logical operators AND and OR work. Recall that an AND will engage if both of its conditions are true and an OR will engage if at least one of its conditions are true. Because of these facts, it is possible for the computer to "skip out" of an AND or OR if their rules for engagement are violated by the first condition. This is called short-circuiting.
Short-circuiting may sound like a bad thing (it is in terms of electricity) but in computer science, it means that the computer is saving time by not evaluating conditions that it doesn't need to consider. Let's look at an example involving the AND operator. Consider the following code:
if(x==1 && y>5)
{
list of statements...
}
Suppose that x is not 1. That means the condition x==1 is false. Since AND requires both conditions to be true to engage the list of statements, the result of the condition y>5 is irrelevant. In other words, it doesn't matter whether y>5 is true or false because the first condition is already false, making it impossible for both to be true. So in general, when the first condition of an AND is found to be false, the computer short-circuits the AND by skipping the second condition.
What is the point?
1) Consider that in a large program with thousands of conditions to be evaluated, this results in saved time. Programmers seek to make programs that not only function correctly, but also as efficiently as possible. The short-circuit capability of Java helps toward that goal.
2) To avoid run-time exceptions for things like dividing by 0.
i.e. if (x !=0 && 5/x == .325) Dividing by 0 will cause an arithmetic exception at run-time but in this case it will never happen because it will short circuit if x = 0.
Short-Circuit with OR
The OR operator also has the capability to short-circuit. Recall that an OR will engage when either one of its conditions is true. So if the first condition is true, the value of the second condition is irrelevant. See the example code below:
if(x==1 || y>5)
{
list of statements...
}
In the example, if x is indeed 1, the condition x==1 is true. Since OR requires only one of the conditions to be true to engage the list of statements, the result of the condition y>5 is irrelevant. In other words, it doesn't matter whether y>5 is true or false because the first condition is already true, making the overall result of the OR true. So in general, when the first condition of an OR is found to be true, the computer short-circuits the OR by skipping the second condition.
Just Remember:
1. The AND operator will short-circuit when the first condition is FALSE
2. The OR operator will short-circuit when the first condition is TRUE
Multiple Choices
Let's begin this discussion with an example programming problem:
Suppose that a program is being written that will display the word version of a two-digit integer between 20 and 59. For example, the integer 32 will be displayed in words as thirty-two. The following code could be used to write the part that will appear before the hyphen (assume that n is an int variable):
if(n>=20 && n<30) System.out.println("Twenty");
if(n>=30 && n<40) System.out.println("Thirty");
if(n>=40 && n<50) System.out.println("Forty");
if(n>=50 && n<60) System.out.println("Fifty");
By combining all of the if statements into an (if..else..if) statement. Here is what it would look like (Indentation is optional but makes it easier to read)
if(n>=20 && n<30) System.out.println("Twenty");
else if(n>=30 && n<40) System.out.println("Thirty");
else if(n>=40 && n<50) System.out.println("Forty");
else if(n>=50 && n<60) System.out.println("Fifty");
One more thing
If the value of n was outside the range of 20-59, nothing will happen. For instance, the value 75 does not make any of the conditions true, so nothing is displayed. If we can be sure that n will not be outside the range 20-59, we could write the code as follows:
if(n>=20 && n<30) System.out.println("Twenty");
else if(n>=30 && n<40) System.out.println("Thirty");
else if(n>=40 && n<50) System.out.println("Forty");
else System.out.println("Fifty");
Note that in this version, the last condition is omitted. Since it is the only possibility at that point, the program just displays Fifty without needing to check a condition - it has to be in the 50's at that point. The last else then could be considered a default response - if none of the previous conditions are true, just do this.
In closing, use an if..else..if only when you are coding 3 or more conditional statements that are all based on the same variable or expression. For example, the following could not be converted to an if..else..if:
if(x==1) System.out.println("One");
if(y==2) System.out.println("Two");
if(z==3) System.out.println("Three");
More than one of these conditions can be true, since they are based on different variables. So an if.else..if would not make sense.
True or False?
George Boole was a British mathematician and philosopher in the 1800's who is credited with defining an Algebraic form of logic which is now known as Boolean Algebra. This system of logic is one of the building blocks of computer science. In fact, one of Java's primitive data types is called boolean. A boolean variable is one that is capable of taking only one of two values, true or false. Boolean variables are typically used to take the place of conditions and to make statements more readable.
Declaring a boolean variable can be done in one of two ways:
boolean gameOver;
boolean gameOver = false; // or true
In the first declaration, gameOver has no initial value. In the second, it is initialized with the value false. A boolean variable can also be initialized to true.
Assigning a value to a boolean variable is acheived by assigning a condition like those that appear in the parentheses of an if statement. Here are several examples (assume that all assigned variables are declared boolean):
gameOver = score==10;
busted = points>21;
accepted = age>=16 && gpa>3.00;
gameOver = score1==10 || score2==10;
Note that the right-hand side of each assignment statement is an expression that must evaluate to true or false. The following pair of assignment statements are incorrect:
gameOver = 10; //doesn't assign true or false
busted = points=22; //doesn't have two equal signs
Boolean variables can also be used as if statement conditions. Here are some examples:
if(gameOver) System.out.println("Game is over");
if(busted) balance = balance - bet;
if(accepted) System.out.println("You are accepted!");
It is also acceptable, but redundant, to write an if with a boolean variable condition as follows:
if(gameOver==true) System.out.println("Game is over");
The use of ==true still works, but is not necessary. Either way, if the boolean variable is true, the statement engages. if it is false, it doesn't.
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):
A B A && B A || B
true true true true
true false false true
false true false true
false false false false
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
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;
Recursion
A recursive method is a method that calls itself. Any method that is written recursively could also be written iteratively (an iterative method is a method that does not call itself).
**You will not be required to write a recursive method on the AP Exam but you will have to determine the output of a recursive method. Also, practicing writing recursive methods helps to understand it.
Example: We want to create a method: int factorial(int n) that will return n factorial (n!).
5! = 5*4*3*2*1 = 120
The logic here is that 5! = 5 * 4!
4! = 4* 3!
3! = 3*2!
2! = 2*1!
1! = 1
Base Case:
A base case is when the recursion stops and trace back up the stack that has been called. The base case in this example is 1! because we know it is 1.
public int factorial(int n)
{
if (n == 1) return 1;
else return n*factorial(n-1);
}
Let’s trace factorial (8):
when n = 8, the else clause is performed which calls 8*factorial(7). However, factorial(7) would return 7*factorial(6). This happens until you run factorial(1) which returns 1. So
factorial(2) = 2*1 = 2.
factorial(3) = 3*factorial(2) = 3*2 = 6
factorial(4) = 4*factorial(3) = 4*6 = 24
factorial(5) = 5*factorial(4) = 5*4 = 120
factorial(6) = 6*factorial(5) = 6*120 = 720
factorial(7) = 7*factorial(6) = 7* 720 = 5040
factorial(8) = 8*factorial(7) = 8* 5040 = 40320
Example 2:
System.out.println(adder(7)); // 46
public static int adder(int n)
{
if (n<=0)
return 30;
else
return n + adder(n-2);
}
On the first call to adder, n is 7, and on the second call it’s 5 (7 - 2), etc. Notice that in the return portion of the code that each n is added to the next one in the sequence of calls to adder. Finally, when the n parameter coming into adder gets to 0 or less, the returned value is 30. Thus, we have:
7 + 5 + 3 + 1 + 30 = 46
** Base case in example 2 is when adder(-1) is called.
Example 3 (Fibonacci Sequence):
In this problem we will generate the Fibonacci sequence. This important sequence is found in nature and begins as follows: 0, 1, 1, 2, 3, 5, 8, 13, 21, …
We notice that beginning with the third term, each term is the sum of the preceding two. Recursively, we can define the sequence as follows:
fibonacci(0) = 0
fibonacci(1) = 1
fibonacci(n) = fibonacci(n - 1) + fibonacci(n -2)
Using these three lines, we can write a recursive method to find the kth term of this sequence with the call, System.out.println( fib(k) ); :
public static int fib(int n)
{
if (n = = 0)
{
return 0;
}
else if(n = = 1)
{
return 1;
}
else
{
return fib(n – 1) + fib(n – 2);
}
}
Practice: Trace the calls for fib(5). How many times was the method fib called?
Answer: 15