Page 174 - Introduction to Programming with Java: A Problem Solving Approach

140 Chapter 4 Control Statements
1. !!x ←→ x
2. x || false ←→ x
3. x && true ←→ x
4. x || true ←→ true
5. x && false ←→ false
6. x || x ←→ x
7. x && x ←→ x
8. x || !x ←→ true
9. x && !x ←→ false
10. x || y ←→ y || x
11. x && y ←→ y && x
12. x || (y || z) ←→
13. x && (y && z) ←→
⎫
⎬ commutation
⎭ ⎫
⎬ association (x && y) && z ⎭
⎫
(x || y) || z
14. x && (y || z) ←→
x && y || x && z
⎬ distribution && z ←→ (x || y) && (x || z) ⎭
!xA&p& a!ygo PDF Enhancer
15. x || y
16. !(x ||
17. !(x &&
⎬ DeMorgan y) ←→ !x || !y ⎭
⎫
y) ←→
Figure 4.20 Basic identities of Boolean algebra
You can use these identities in any combination to change the form of any conditional expression.
The first 13 identities are relatively straightforward, and you should be able to satisfy yourself of their va- lidity by just thinking about them. Likewise, you shouldn’t have to memorize them. You should be able to use them instinctively. For example, commutation means you can switch the order without changing anything, and association means you can move the parentheses without changing anything. The last four identities are more mysterious, and some of them might even seem unreasonable at first. For example, distribution is a kind of shuffling, and DeMorgan’s theorem says you can negate everything and exchange all and’s and or’s.
Proving the Boolean Identities
Now that you’ve seen the basic identities, let’s see how to prove them. The proof technique is to write a program that compares two arbitrary logical expressions for all possible values of the boolean variables they contain. If the two expressions evaluate to the same truth values for all possible variable values, they are logically equivalent. Figure 4.21 contains a program that does just that for the special case of the expres- sions on either side of basic identity 16 in Figure 4.20.
It’s straightforward to modify the TruthTable program in Figure 4.21 to test any of the other basic iden- tities in Figure 4.20. In fact, you can modify the program to test any prospective logical equivalence. To test a different equivalence, substitute the left and right sides of the prospective equivalence for the expressions assigned to result1 and result2, respectively.