Introduction to Logic and Truth Tables

Date: 09/27/2000 at 18:49:57
From: Carolyn
Subject: Logic

I can't figure out the p and q thing.

I don't understand about ^, v, and stuff like that. Could you explain 
it to me in an easy way?

Date: 10/02/2000 at 14:29:07
From: Doctor TWE
Subject: Re: Logic

Hi Carolyn - thanks for writing to Dr. Math.

The p's and q's represent "propositions." They're kind of like 
variables in algebra, only instead of representing numbers, they 
represent things that are either true or false. The statement "today 
is Monday" is a proposition because it can be either true (if, indeed 
it is Monday) or false (if, for example, it's Tuesday.) You can also 
think of it as being a variable that can only have one of two values: 
0 (for false) or 1 (for true.) In fact, that is exactly how computers 
deal with them.

The logic expression p^q (read "p and q") is similar to the algebra 
expression A+B. A and B represent numbers, and A+B means we're 
combining those numbers in a certain way. If A = 3 and B = 5, then
A+B = 3+5 = 8. How do we know 3+5 = 8? Because somewhere along the 
line we defined the addition operation and said that 3+5 = 8.

Similarly, if p = T (true) and q = F (false) then p^q = T^F = F. (Note 
that the "variables" p and q take on the "values" T and F instead of 
the "values" 3 and 5.) How do we know that T^F = F? Because (just as 
with addition) somewhere along the line we defined the AND operation 
and said that T^F = F.

How do you know all the possibilities for addition of numbers? 
Probably in elementary school you memorized your addition tables (and 
your subtraction tables, multiplication tables and division tables, 
too). Similarly, we have "truth tables" that tell us what the results 
of logic operations are. Unlike addition tables, which typically have 
100 sums to memorize, 2-variable truth tables have only 4 results for 
you to memorize. This is because each proposition (or variable) can 
only be one of two values: T or F. Here's the AND truth table:

      ^ | T F
     ===+=====
      T | T F
      F | F F

Written this way, we read it as we read an addition table: we read one 
value across the top to find the column and one down the left side to 
find the row. Where that row and column intersect is the answer. So, 
for example, for T^F we'll use the first column (labeled T) and the 
bottom row (labeled F).

             ______ Our column
            /
           |
           V
          +-+
      ^ | |T| F
     ===+=+=+===
      T | |T| F
     +--+-+-+--+
     |F | |F| F| <- Our row
     +--+-+-+--+

Where that row and column intersect we read our result: F. 

More often, however, logic truth tables are written with each 
proposition (or variable) in a column and the result in a separate 
column. Here's the more common way to write the AND truth table:

      p q | p^q
     -----+-----
      T T |  T
      T F |  F
      F T |  F
      F F |  F

In this type of truth table, we look for the row that has the correct 
values for p and q, and read the result from the final column. For 
example:

      p q | p^q
     -----+-----
      T T |  T
     +----+----+
     |T F |  F | <- Our row
     +----+----+
      F T |  F
      F F |  F

so T^F = F.

Just as arithmetic starts off with a few simple operations (addition 
and subtraction), then builds to more complex operations (division, 
multiplication, exponents, etc.), the same holds for logic operations. 
The two basic operations are AND (p^q) and OR (pvq). From these, we 
can build more complex operations like implication, equivalence, 
exclusive-or, and so on. If you want to know more about these 
secondary operations, write back.

I hope this helps.

- Doctor TWE, The Math Forum
  http://mathforum.org/dr.math/