1. Truth Tables and De Morgan's Rules

Boolean expressions are used to control branches and loops in computer programs. Of course, branches and loops are fundamental to programming. This chapter shows some methods for working with boolean expressions.

Truth tables are used to analyze boolean expressions.

De Morgan's rules transform confusing boolean expressions into easier ones.

Chapter Topics:

• Truth Tables
• De Morgan's Rules

Question 1:
(Review :) What is the value of:   x<12 && y>10
Assume that x contains 9 and y contains 7.

Source: Bradley Kjell, http://programmedlessons.org/Java9/chap33/ch33_01.html
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 License.

2. Review of Truth Tables

Answer:
Assume that x contains 9 and y contains 7.
The expression evaluates to False. One way to show this is below.

Review of Truth Tables

A truth table shows the evaluation of a boolean expression.

• Each row of a truth table starts with a selection of truth values for the operands.
• There is one row for each possible selection of truth values.
• The columns show the truth value of expressions and subexpressions containing the operands.

The table at right has four rows for the truth values, one row for each of the four possible choices for the two operands. (The operands are the relational expressions x<12 and y>10.) The last column shows the result of the && operator with those values.

Question 2:
What row of the table is used when x contains 1 and y contains 23?

3. Another Truth Table

Answer:
The last row.

Another Truth Table

Here is another truth table that shows the operands combined with an || operator.

The first several columns of a truth table show all possible boolean values of the operands. In this table, the operands are relational expressions. The remaining columns show how these values are combined by the logical operators.

Question 3:
Decide on values for the last column.

4. Conventional Order

Answer:
Operands
Boolean Expression
x < 12
y > 10
x < 12 || y > 10
F
F
F
F
T
T
T
F
T
T
T
T

Conventional Order

Question 4:
Fill the first table with the conventional order of "0" and "1" (think about what should be in each row 
before you click the buttons). Do the rows in order, starting with the top. Then fill in the second table 
with the conventional order of "T" and "F".

    A    
    B    
    C    
- - -
-
-
-
-
-
-
-
-

    A    
    B    
    C    
- - -
-
-
-
-
-
-
-
-

5. Computer Purchase Problem

Answer:

    A   
    B   
    C   
-
0
0
0
-
0
0
1
-
0
1
0
-
0
1
1
-
1
0
0
-
1
0
1
-
1
1
0
-
1
1
1
-

    A   
    B   
    C   
-
F
F
F
-
F
F
T
-
F
T
F
-
F
T
T
-
T
F
F
-
T
F
T
-
T
T
F
-
T
T
T
-

Computer Purchase Problem

Say that you are shopping for a new computer. You will reject any computer that does not meet your minimum requirements. You require: speed of more than 2000 MHz and more than 512 Meg of memory.

if (  ______(speed > 2000 && memory > 512)  )

  System.out.println("Reject this computer");
  
else

  System.out.println("Acceptable computer");

Question 5:
What should go in the blank so that the program fragment is correct?
(Hint: this is NOT a hard question.)

6. Truth Table

Answer:
if (  !(speed > 2000 && memory > 512)  )
  System.out.println("Reject this computer");
else
  System.out.println("Acceptable computer");

Truth Table

Consider a computer with 2200 MHz speed and 750 Meg of memory. This computer is not rejected. Evaluation proceeds like this:

Question 6:
Does the following program fragment do the same thing as the original fragment?
boolean reject = !(speed > 2000 && memory > 512);

if (  reject  )
  System.out.println("Reject this computer");
else
  System.out.println("Acceptable computer");

7. Precedence of NOT

Answer:Yes. Sometimes boolean variables like reject are used to record a decision that might be used in 
several places in the program.

Precedence of NOT

The NOT operator has high precedence. It is done before arithmetic and relational operators unless you use parentheses. Examine the following:

!speed > 2000   &&   memory > 512
------  
illegal: can't use ! on an arithmetic variable

Since ! has high precedence, the above says to apply it to speed. This won't work because speed is an integer and ! applies only to boolean values.

When parentheses are used

!(speed > 2000   &&   memory > 512)

the ! is the last operation done and is applied to the boolean value of the expression inside parentheses.

Expressions that involve a NOT operator are often hard to read. A confusing expression can sometimes be rewritten to eliminate the NOT.

Question 7:
Look at the original fragment:
if ( !(  speed > 2000   &&   memory > 512 ) )
  System.out.println("Reject this computer");
else
  System.out.println("Acceptable computer");
Does the following do the same thing?
if (  speed <= 2000 || memory <= 512 )
  System.out.println("Reject this computer");
else
  System.out.println("Acceptable computer");
Use some example values for speed and memory and figure out what each fragment does.

8. Equivalent Boolean Expressions

Answer:Yes. The two fragments are equivalent. It may have taken you a while to figure this out, 
and you may not be completely convinced.

Equivalent Boolean Expressions

To decide if the two fragments are equivalent, pick some example values for speed and memory and see if the expressions evaluate to the same boolean values. A systematic way to check two boolean expressions is to use a truth table. To start, look at the "speed" question:

If it is False that the speed is greater than 2000, then it is True that the speed is less than or equal to 2000.

If it is True that the speed is greater than 2000, then it is False that the speed is less than or equal to 2000.

Only one of X>Y and X<=Y can be true for particular values of X and Y.

Another way to say this is !(X>Y) and X<=Y are equivalent. The last two columns of the following table show equivalent expressions.

It is also true that X>Y and !(X<=Y) are equivalent. This is demonstrated in the following question.

Question 8:
Fill in the following table. Fill the cells of a row so they are consistent with the first cell of the row.
speed > 2000
(speed <= 2000)
!(speed <= 2000)
F
T
The first column and the last column have the same T/F values, which shows that 
 speed > 2000 is equivalent to !(speed <= 2000).

9. Equivalent Boolean Expressions

Answer:
speed > 2000
(speed <= 2000)
!(speed <= 2000)
F
T
F
T
F
T

Equivalent Boolean Expressions

The original program fragment used this boolean expression

!(speed > 2000 && memory > 512)

which is explained in the following truth table (repeated from a previous page):

speed <= 2000 || memory <= 512

Question 9:
Is there only one correct way to write an if statement in a program?

10. Equivalent Statements

Answer:Usually there are many equivalent ways to write an if statement.

Equivalent Statements

Here is the original fragment, which uses AND:

if (  !(speed > 2000 && memory > 512)  )
  System.out.println("Reject this computer");
else
  System.out.println("Acceptable computer");

Here is an equivalent fragment that uses OR:

if (  speed <= 2000  ||  memory <= 512 )
  System.out.println("Reject this computer");
else
  System.out.println("Acceptable computer");

Yet another equivalent fragment reverses the order of the true and false branches of the statement.

if (  speed > 2000  &&  memory > 512 )
  System.out.println("Acceptable computer");
else
  System.out.println("Reject this computer");

The last fragment is probably the best choice because it is the easiest to read. It follows the pattern:

if ( expression that returns "true" for the desired condition )
  perform the desired action
else
  perform some other action

Question 10:
Rewrite the following natural language statement into an equivalent easily understood statement.
Not always are robins not seen when the weather is not fair.

11. Not Not

Answer:Not always are robins not seen when the weather is not fair.
Sometimes robins are seen when the weather is not fair.
Robins are sometimes seen in poor weather.

Not Not

Who's there?

!!A is equivalent to A           

The operand A stands for a true/false value or an expression that results in a true/false value. This truth table shows the rule:

Question 11:
Rewrite the following if statement:
if ( !(value != 399) )
  System.out.println("Correct Value"); 
else
  System.out.println("Wrong Value");   

12. Equivalent Relational Expressions

Answer:
if ( value == 399 )
  System.out.println("Correct Value");
else
  System.out.println("Wrong Value");

Equivalent Relational Expressions

Question 12:
Rewrite the following if statement:
if ( !(car.price > 8000 ) )
  System.out.println("Affordable");
else
  System.out.println("Too Expensive!");   

13. De Morgan's Rules

Answer:
if ( value == 399 )
  System.out.println("Correct Value");
else
  System.out.println("Wrong Value");

De Morgan's Rules

!(A && B) is equivalent to !A || !B
!(A || B)is equivalent to !A && !B              

These rules are very useful. Make sure you know them.

Question 13:
Rewrite the following fragment (from a previous example):
boolean reject =  !(speed > 2000 && memory > 512)

14. Another Demonstration

Answer:
Using the De Morgan Rule
!(A && B) is equivalent to !A || !B
the original expression
boolean reject = !(speed > 2000 && memory > 512)
is equivalent to
boolean reject = !(speed > 2000) || !(memory > 512)
which is equivalent to
boolean reject = (speed <= 2000) || (memory <= 512)

Another Demonstration

Question 14:
Rewrite the following fragment:
while ( !(input.equals( "quit" ) || (count > limit)) ) 
{
   . . . 
}

15. Oil Change

Answer:
Using the De Morgan Rule
!(A && B) is equivalent to !A && !B
the original expression
while ( !(input.equals( "quit" ) || (count > limit)) ) 
{
   . . . 
}
is equivalent to
while ( !input.equals( "quit" ) && !(count > limit)) ) 
{
   . . . 
}
which is equivalent to
boolean reject = (speed <= 2000) || (memory <= 512)

Oil Change

The owner's manual for a car says to change the oil every three months or every 3000 miles.

boolean newOilNeeded =  months >= 3 || miles >= 3000 ; 

Here is an expression that shows when no oil change is necessary:

boolean oilOK =  !( months >= 3 || miles >= 3000 ); 

Question 15:
Rewrite the last expression using one of De Morgan's rules. Do this in two steps. In the first step, don't change the relational expressions.
boolean oilOK =           
Now further simplify by changing the relational expressions.    
boolean oilOK =     

16. Free Shipping

Answer:
Using the De Morgan Rule
!(A && B) is equivalent to !A && !B
the expression
        boolean oilOK =  !( months >= 3 || miles >= 3000 ); 
is equivalent to
        boolean oilOK =  !( months >= 3 ) && !( miles >= 3000 ); 
which can be further transformed to
       boolean oilOK =  ( months <  3 ) &&  ( miles <  3000 );

Free Shipping

For an on-line shopping site, shipping is free for purchases of $50 or more, unless the merchandise is on sale.

boolean freeShipping =  purchase >= 50 && !onSale; 

Here is an expression that shows when to charge for shipping:

boolean shipping =  !( purchase >= 50 && !onSale ); 

Assume that onSale is a boolean variable.

Question 16:
Rewrite the second expression in two steps. In the first step, apply De Morgan's rule that !(A && B) is equivalent to !(A) || !(B).
boolean shipping =   
In the second step, rewrite the relational expression:  
boolean shipping =    

17. Full Price Hotel

Answer:
Using the De Morgan Rule
!(A && B) is equivalent to !A || !B
the expression
        boolean shipping =  !(purchase >= 50 && !onSale );
is equivalent to
        boolean shipping =  !(purchase >= 50) || !!onSale ;
which can be further transformed to 
boolean shipping = purchase < 50 || onSale ;

Full Price Hotel

boolean fullFare = (days < 14) && onSeason;

boolean discount = !( (days < 14) && onSeason );

Question 17:
Rewrite this expression in two steps. In the first step, apply De Morgan's rule that !(A && B) is equivalent to !A || !B.
boolean discount =  
In the second step, rewrite the relational expression: 
boolean discount =    

18. More De Morgan

Answer:
Using the De Morgan Rule
!(A && B) is equivalent to !A || !B
The expression
boolean discount =  !( (days < 14) && onSeason );
is equivalent to
boolean discount =  !(days < 14) || !onSeason ; 
which can be further transformed to
boolean discount =  days >= 14  || !onSeason ; 

More De Morgan

De Morgan's rules can be extended to three operands:

Expressions with more than three operands behave similarly.

Question 18:
A driver holding a learner's permit may drive a car only during daylight hours and 
 only if accompanied by a licensed driver of age 21 or over.
boolean drivingOK = daylight && passenger.age >= 21  && passenger.licensed;
Assume that passenger refers to an object with an integer member age
         and a boolean member licensed.
Here is an expression that says when driving is not permitted:
boolean noDriving = !(daylight && passenger.age >= 21  && passenger.licensed );
Transform this into a simpler expression.

19. Not at the Beginning and Not in the Middle of the Chapter

Answer:
Using the De Morgan Rule
!(A && B) is equivalent to !A || !B || !C
The expression
boolean noDriving = !(daylight && passenger.age >= 21  && passenger.licensed );
is equivalent to
boolean noDriving = !daylight || !(passenger.age >= 21) ||  !passenger.licensed ;
which can be further transformed to
boolean noDriving = !daylight || passenger.age < 21 ||  !passenger.licensed ;

Not at the Beginning and Not in the Middle of the Chapter

If you are not interested or do not have the time, you may not wish to review the following.

• truth table Truth tables.
• truth tables, row order Conventional order of truth table rows.
• De Morgan, Rules De Morgan's Rules with two operands.
• De Morgan, Rules, three operand De Morgan's Rules with three operands.