Computer
Science - C++
LESSON 17: Boolean Algebra - Loop boundaries
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
VOCABULARY: BOOLEAN ASSERTIONS DE MORGAN'S LAWS
&nb sp; BOOLEAN ALGEBRA
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.
A not A
5 == x 5 != x
x < 5 x >= 5
x >= 5 x < 5
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 C++)
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 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.
A B not (A or B) not A not B not A and not B
1 1 0 0 0 0
1 0 0 0 1 0
0 1 0 1 0 0
0 0 1 1 1 1
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.
A B not (A and B) not A not B not A or not B
1 1 0 0 0 0
1 0 1 0 1 1
0 1 1 1 0 1
0 0 1 1 1 1
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
not (A or B) = not A and not 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:
7 player wins
4 5 3 7 player loses
8 6 2 8 player wins
3 player loses
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.cpp, is provided in Handout H.A.17.1. The application of DeMorgan's Laws occurs in function getPoint(). 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 function 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.
not ((sum == point) || (sum == 7))
9. Applying DeMorgan's law results in
(not (sum == point)) && (not (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.
DeMorgan's laws can be very useful in developing conditional loop boundaries.
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.