Home | About | Calendar | Projects | Assignments | Classes | Resources
{Programming I}
     
 
DESCRIPTION
 
REMINDERS
 

A statement is any assertion that can be evaluated to true or false.

"It is cold"
"I am female"
"I am a master of C++"

To simplify things, we can use simple variables to represent these statements. P, Q, and R are commonly used in truth tables. These statements can be joined using the && and || operators. If the statement P is "The wall is red" and Q is the statement "The lamp is on," then P || Q is the resulting statement "The wall is red or the Lamp is on." P && !Q is the resulting statement "The wall is red and the lamp is not on."

"The truth value of a compound statement is determined from the truth values of its simple components under certain rules. For example, if P is a true statement then the truth value of !P is F. Similarly, if P has truth value F, then the statement !P has truth value T. These rules are summarized in the following truth table."1

P
!P
T
F
F
T

If we have two statements, P and Q, then P || Q is true except when they are both false. P && Q is false except when both P and Q are true.

P
Q
P || Q
P && Q
T
T
T
T
T
F
T
F
F
T
T
F
F
F
F
F

Using the elementary truth tables, more complex statements can be evaluated quickly and easily. For example, determing the truth value of the expression (P || Q) && (!P && !Q) can be done by evaluating each of the expressions individually.

P
Q
P || Q
!P
!Q
!P && !Q
(P || Q) && (!P && !Q)
T
T
T
F
F
F
F
T
F
T
F
T
F
F
F
T
T
T
F
F
F
F
F
F
T
T
T
F

The statement being evaluated above is called a Contradiction because it always evaluates to False. Statements that always evaluate to True are called Tautologies.

Using truth tables, we can discover that some expressions that we would expect to be equivalent are not.

P
Q
!P
!Q
!P && !Q
P && Q
!(P && Q)
T
T
F
F
F
T
F
T
F
F
T
F
F
T
F
T
T
F
F
F
T
F
F
T
T
T
F
T

and some things that might be hard to test can be tested easily

P
Q
!P
!Q
!P && !Q
P || Q
!(P || Q)
T
T
F
F
F
T
F
T
F
F
T
F
T
F
F
T
T
F
F
T
F
F
F
T
T
T
F
T

The tables above and below here are proofs of DeMorgan's Laws. The fact that the expression (!P && !Q) is equivalent to !(P || Q) and the expression (!P || !Q) is equivalent to !(P && Q) is an important rule for Computer Scientists and Electrical Engineers who wish to use all of these rules to make circuitry.

P
Q
!P
!Q
!P || !Q
P && Q
!(P && Q)
T
T
F
F
F
T
F
T
F
F
T
T
F
T
F
T
T
F
T
F
T
F
F
T
T
T
F
T

Finally, testing truth tables grows exponentially with the number of statements involved:

P
Q
R
P && Q
!R
(P && Q) || (!R)
T
T
T
T
F
T
T
T
F
T
T
T
T
F
T
F
F
F
T
F
F
F
T
T
F
T
T
F
F
F
F
T
F
F
T
T
F
F
T
F
F
F
F
F
F
F
T
T

 

These notes compiled by Christian Day, The Emma Willard School.
References used: "Statements, truth values and truth tables," Peter Williams. http://www.math.csusb.edu/notes/logic/lognot/node1.html. 1/19/2003

 

   Add a reminder here
 
Page prepaed by Christian Day.
Site design by Kelly Moran
BackForward
 
 
Last Updated: