Truth Tables, Logic, and DeMorgan's Laws

Truth tables summarize how we combine two logical conditions based on AND, OR, and NOT. Logic tells us that if two things must be true in order to proceed them both condition_1 AND condition_2 must be true. If it only takes one out of two things to be true, then condition_1 OR condition_2 must be true. DeMorgan's Laws tell us how to negate a boolean expression and what it means to do so.

Truth Values in a computer : Booleans

At the end of the day, one of the few things, and most powerful things a computer can determine if a statement (expression) is "true" or "false". Because true and false are so prevalent in decision making, they are their own keywords. In other words, in a program we write true not the string 'true'.

Logical Operators: AND, OR, and NOT

We can combine several "boolean" statements that have true/false meaning into a single statement using the key concepts AND and OR (and NOT). If I want to go to the movie AND I have enough money, then I will go to the movie. BOTH conditions have to evaluate to true (have to be true) before the entire expression is true.

        
          i_want_to_go_to_move = true;
          
          if ( ( i_want_to_go_to_move ) && ( money > 20 ) )
             go to movie();
          end
        
      

OR is written with double "pipes" ||

AND is written with double "ampersands" &&

True is written: true;

False is written: false;

Not is written in a variety of ways. In Matlab it is the tilde (~). In C, Java, ActionScript, it is written as the exclamation point (!).

Warning: Again, the two Booleans are true and false, (not the strings 'true' and 'false' but keywords true and false. Further, while Matlab allows you to use 1 and 0 for true and false, every time you write a program and need to assign the value's true or false, you should use the keywords true and false, not the shortcut 1,0.


Truth Tables, Logic, and DeMorgan's Laws

Computer programs are constantly making decisions based on the current "STATE" of the data held by the program. For example, a heart monitoring program might sound an alarm if the pulse is too slow or the blood pressure is too weak. Combining multiple conditions to form one True/False value is the domain of Logic.

The primary way to combine two boolean expressions into one is through the use of AND or OR. In most programming languages, AND is written using double ampersands: &&. OR is written using double pipes: ||


The truth tables

Truth tables show the result of combining any two expression boolean expressions using the AND operator and the OR operator (or the NOT operator).

You should memorize/learn these values and be able to duplicate this table:

condition 1
(e.g., X)
condition 2
(e.g., Y)
NOT X
( ~ X )
X AND Y
( X && Y )
X OR Y
( X || Y )
false false true false false
false true true false true
true false false false true
true true false true true

DeMorgan's Laws

DeMorgan's laws tell us how to transform logical expressions (with multiple AND and/or OR statements) using the NOT operator.

For example:

You want your loop to finish after 8 iterations have been made (and you want to use a while loop).

This is the same as saying:

You want your loop to continue when less than or equal to 8 iterations have been made.

Thus to continue, you want the opposite (or the NOT) condition of the finishing condition.

The pseudocode looks something like:

          
          if (count > 8)
          {
             finish
          }
          
        

which becomes:

          
          while ( ! (count > 8) ) // Not the case that the count is greater than 8
          {
            do something
          }
          
        

Now say their is an additional criteria to finishing, say when the total value of some variable is greater than 100.

How you would say this in English:

          
          if (line_count > 8  _OR_  the total is greater than 100)
          {
            finish
          }
          
        

which becomes:

          
          while ( NOT (line_count > 8) _AND_  NOT(the total is greater than 100))
          {
            do something
          }

          %
          % Which can be rewritten as:
          %

          while ( line_count <= 8 && the total is less than or equal to 100)
          {
            do something
          }
          
        

DeMorgan's Laws tell us how to translate from a "positive" version of a statement into a negative version, or more concisely: The DeMorgan laws tells us how to translate an logical expression ( E ) into NOT( E ).

Here is what DeMorgan's law states that:

NOT(A || B) is Equivalent to (NOT(A) AND NOT(B))

Additionally:

NOT(A && B) is Equivalent to (NOT(A) OR NOT(B))

This goes in reverse as well:

(NOT(A) || NOT(B)) is Equivalent to NOT(A AND B)

Thus if you are having problems thinking of when something should continue, think about when it should stop and then use NOT!


Back to Topics List