INTRODUCTION:

Conditional loops often prove to be one of the most difficult control structures to work with. This lesson will increase your strategies in developing correct loops.

The key topics for this lesson are:

A. Negations of Boolean Assertions
B. Boolean Algebra and DeMorgan's Laws
C. Application of DeMorgan's Laws
D. Generating Random Values

VOCABULARY:

BOOLEAN ASSERTIONS
BOOLEAN ALGEBRA

DE MORGAN'S LAWS

DISCUSSION:

A. Negations of Boolean Assertions

1. A Boolean assertion is simply an expression that results in a true or false answer. For example,

a > 5 0 == b a <= b

are all statements which will result in a true or false answer.

2. To negate a Boolean assertion means to write the opposite of a given Boolean assertion. For example, given the following Boolean assertions noted as A, the corresponding negated statements are the result of applying the not operator to A.

3. Notice that negation of Boolean assertions can be used to re-write code. For example:

if (!(x < 5))
     // do something...

can be rewritten as

if (x >= 5)
     // do something ...

B. Boolean Algebra and DeMorgan's Laws

1. Boolean Algebra is a branch of mathematics devoted to the study of Boolean values and operators. Boolean Algebra consists of these fundamentals operands and operations:

operands (values): true, false

operators : and (&&), or (| |), not (!)

(note: there are other Boolean operators such as ^ (XOR) and equivalence in Java)

2. There are many identities which have been developed to work with compound Boolean expressions. Two of the more useful identities are DeMorgan's Laws which are used to negate compound Boolean expressions.

DeMorgan's Laws:

not (A or B) = not A and not B

not (A and B) = not A or not B

The symbols A and B represent Boolean values, true (1) or false (0).

3. Here is the truth table which proves the first DeMorgan's Law.

Notice that columns with the titles not (A or B) and not A and not B result in the same answers.

4. Following is the truth table which proves the second DeMorgan's Law.

Notice that columns with the titles not (A and B) and not A or not B result in the same answers.

5. Here is a good way to think about both of DeMorgan's Laws. Notice that it is similar to the distributive postulate in mathematics. The not operator is distributed among both terms inside of the parentheses, except the operator switches from and to or, or vice versa.

not (A and B) = not A or not B (!(A && B) == !A || !B)

not (A or B) = not A and not B (!(A || B) == !A && !B)

C. Application of DeMorgan's Laws

1.The casino game of craps involves rolling a pair of dice. The rules of the game are as follows.

- If you roll a 7 or 11 on the first roll, you win.
- If you roll a 2, 3, or 12 on the first roll, you lose.
- Otherwise rolling a 4,5,6,8,9, or 10 establishes what is called the point value.
- If you roll the point value before you roll a 7, you win. If you roll a 7 before you match the point value, you lose.
- After the point value has been matched, or a 7 terminates the game, play resumes from the top.

2. The following sequences of dice rolls gives these results:

3. The rules of the game are set so that the house (casino) always wins a higher percentage of the games. Based on probability calculations, the actual winning percentage of a player is 49.29%.

4. A complete program, craps.java, is provided in Handout H.A.18.1. The application of DeMorgan's Laws occurs in the getPoint() method. The do-while loop has a double exit condition.

do
{
	sum = rollDice();
}
while ((sum != point) && (sum != 7));

5. When developing a conditional loop it is very helpful to think about what assertions are true when the loop will be finished. When the loop is done, what will be true?

6. When the loop in getPoint is done, one of two things will be true:

a. the point will be matched (sum == point).
b. or a seven has been rolled.

These two statements can be combined into one summary assertion statement:
((sum == point) || (sum == 7))
7. The loop assertion states what will be true when the loop is done. Once you have established the loop assertion, writing the boundary condition involves a simple negation of the loop assertion.

8. Taking the assertion developed in Section 6, the negation of the assertion follows.

!((sum == point) || (sum == 7))

9. Applying DeMorgan's law results in
(!(sum == point)) && (!(sum == 7))
Then negate each half of the expression to give

(sum != point) && (sum != 7)

10. Looking at the first half of the developing boundary condition, the statement (sum != point) means that we have not yet matched the point, keep rolling the dice.

11. The second half of the boundary condition (value != 7) means we have not yet "crapped" out (rolled a 7). Keep rolling the dice.

12. DeMorgan's laws can be very useful in developing conditional loop boundaries.

D. Generating Random Values

1. The casino game of craps involves rolling a pair of dice to generate random values within a specified range. Java has a class named Random that makes it easy to get seemingly random numbers into your program.

2. To use the capabilities of the Random class, you must first import the class as follows:

import java.util.Random;

3. A Random object can then be constructed with a statement like

Random die = new Random();

and then use the nextInt method.

/** From the Random class
 *
 * Returns a pseudorandom, uniformly distributed int
 * value between 0 (inclusive) and the specified value
 * n (exclusive), drawn from this random number 
 * generator's sequence.
 */
public int nextInt(int n);

4. For example, you can get a number from 1 to 6 with an expression like:

// The message randomly returns 0, 1, 2, 3, 4, or 5.
// A die is simulated by adding 1 to give a value
//   in the range 1 - 6.
int dieRoll = die.nextInt(6) + 1;

5. The Random class contains additional methods for generating random longs, floats, doubles, bytes, booleans, etc. Please consult the Java documentation for a complete explanation of its capabilities.

SUMMARY/ REVIEW:

Conditional loops are some of the hardest pieces of code to write correctly. The goal of this lesson is to have a structured approach for the construction of conditional loops.