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: Wednesday, June 29, 2022, 12:49 PM

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.

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
Creative Commons License 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.

booleanExpression01

Review of Truth Tables

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 2N 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".


    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:

Boolean Expression

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.

speed > 2000memory > 512speed > 2000 && memory > 512Reject Computer if

!(speed > 2000 && memory > 512)
FF
FT
TF
TT


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 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.

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
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 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

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:

!!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:
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.)

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

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 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

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.

    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:

!(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 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.