Truth Tables and De Morgan's Rules
Site:  Saylor Academy 
Course:  CS101: Introduction to Computer Science I 
Book:  Truth Tables and De Morgan's Rules 
Printed by:  Guest user 
Date:  Thursday, February 2, 2023, 3:55 AM 
Description
Read this chapter, which discusses Boolean variables as used in decision tables. Truth tables are used to collect variables and their values relative to decisions that have to be made within control structures.
Table of contents
 1. Truth Tables and De Morgan's Rules
 2. Review of Truth Tables
 3. Another Truth Table
 4. Conventional Order
 5. Computer Purchase Problem
 6. Truth Table
 7. Precedence of NOT
 8. Equivalent Boolean Expressions
 9. Equivalent Boolean Expressions
 10. Equivalent Statements
 11. Not Not
 12. Equivalent Relational Expressions
 13. De Morgan's Rules
 14. Another Demonstration
 15. Oil Change
 16. Free Shipping
 17. Full Price Hotel
 18. More De Morgan
 19. Not at the Beginning and Not in the Middle of the Chapter
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.
Both of these techniques are used in programming and in computer hardware design (and in other areas). Questions about boolean expressions and De Morgan's Rules are prominent on the AP Computer Science Test.
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 AttributionNonCommercial 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.
Operands  Boolean Expression  

x < 12  y > 10  x < 12 && y > 10 
F  F  F 
F  T  F 
T  F  F 
T  T  T 
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.
Operands  Boolean Expression  

x < 12  y > 10  x < 12  y > 10  
F  F  
F  T  
T  F  
T  T 
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
Truth tables are usually organized by putting the operands in a conventional order. Following this order helps prevent mistakes. This table follows the conventional order for two operands:
A

B

expression


F

F



F

T



T

F



T

T



Here, A
and B
represent operands. Often these are relational expressions such as x<12
.
The conventional order is easy to remember if you think of F as 0 and T as 1. Arrange the rows in ascending numerical order, as follows:
A

B

expression


0

0



0

1



1

0



1

1



Courses on digital logic usually use 0 for false and 1 for true and use truth tables such as the above. The conventional order is also used with tables with more than two operands. With three operands, a table has eight rows. With N
operands,
a table has 2^{N}
rows.
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".
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:
A truth table is another way to analyze the expression. The first two columns are filled with all possible truth values of the relational expressions. The remaining cells show how these truth values are combined.
If speed
is 2200 and memory
is 750 the the fourth row of the table is selected. The last column shows that this computer is not rejected. All computers are rejected except for those that meet both
requirements, corresponding to the last row of the table.
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 likereject
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 which 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 be 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 the to the same boolean values. A systematic way of to check two boolean
expressions is to use a truth table. To start, look at the "speed" question:
speed > 2000

speed <= 2000


F

T

T

F

If it is False that the speed greater than 2000, then it is True that the speed is less than or equal to 2000.
If it is True that the speed 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.
speed > 2000 
!(speed > 2000) 
speed <= 2000 

F 
T 
T 
T 
F 
F 
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.
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  speed > 2000 && memory > 512  !(speed > 2000 && memory > 512) 

F  F  F  T 
F  T  F  T 
T  F  F  T 
T  T  T  F 
An equivalent program fragment used this boolean expression
speed <= 2000  memory <= 512
which is explained in the following truth table:
speed > 2000  memory > 512  speed <= 2000  memory <= 512  speed <= 2000  memory <= 512 

F  F  T  T  T 
F  T  T  F  T 
T  F  F  T  T 
T  T  F  F  F 
Each table has the same first two columns. The true/false values in the last column of each table are the same, which shows that the two boolean expressions are equivalent. One expression can be used in place of the other in a program.
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 anif
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
Generally, people find statements that involve NOT to be confusing. Avoid using using NOT, if you can. If NOTs are needed, try to apply them to small subexpressions, only.
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?
It is useful to have some rules for rewriting boolean expressions. Here is an easy one:

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:
A 
!A 
!!A 

false 
true 
false 
true 
false 
true 
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
Usually if you have an expression that uses a NOT operator, replace it with an equivalent comparison that does not use a NOT. If this is not possible, rewrite the expression so that the NOT applies to the smallest subexpression possible.
In the following, X
and Y
represent numbers that can be compared.
Expression  Equivalent  Expression  Equivalent  

!(X < Y)  X >= Y  !(X >= Y)  X < Y  
!(X > Y)  X <= Y  !(X <= Y)  X > Y  
!(X == Y)  X != Y  !(X != Y)  X == Y 
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
Augustus De Morgan was a nineteenth century British mathematician who showed the importance of several rules of logic. Two of these, De Morgan's Rules, show how the NOT operator can be moved to the inside of an expression. (Although these rules are named after De Morgan, they were, in fact, known to Aristotle.)

These rules are very useful. Make sure you know them.
This truth table shows why the first rule is true.
A

B

(A && B)

!(A && B)

!A

!B

!A  !B


F

F

F

T

T

T

T

F

T

F

T

T

F

T

T

F

F

T

F

T

T

T

T

T

F

F

F

F

The fourth column and the last column have the same truth values. This shows the the expressions at the top of those columns are equivalent.
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
Here is the other De Morgan rule:
!(A  B)
is equivalent to!A && !B
This truth table shows why this rule is true.
The fourth and the last column have the same truth values, which shows that the expressions at the top of those columns are equivalent.
A

B

(A  B)

!(A  B)

!A

!B

!A && !B


F

F

F

T

T

T

T

F

T

T

F

T

F

F

T

F

T

F

F

T

F

T

T

T

F

F

F

F

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 online 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
A hotel charges full price for its rooms during the "on season" when a reservation is made less than 14 days in advance. Otherwise, a reservation qualifies for a discount.
boolean fullFare = (days < 14) && onSeason;
Assume that onSeason
is a boolean variable. Here is an expression that says when a discount rate may be available:
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
.In the second step, rewrite the relational expression:
boolean discount =
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:
!(A && B && C)
is equivalent to!A  !B  !C
!(A  B  C)
is equivalent to!A && !B && !C
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 memberage
and a boolean memberlicensed
.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.