Basic Truth Tables and Equivalents in Logic

Date: 05/23/2000 at 16:45:11
From: Carissa 
Subject: Truth tables

What are the truth tables for p and q, including p^q, p<->q, p<-q, and 
p->q? I'm studying for my regents exam and I need to brush up on this 
area.

Date: 05/24/2000 at 12:22:15
From: Doctor TWE
Subject: Re: Truth tables

Hi Carissa - thanks for writing to Dr. Math.

Here are the basic truth tables and some useful equivalents, I'm 
assuming that you know how to use them in logic problems.

                                          IMPLICATION
                                         (p implies q)  EQUIVALENCE
   NEGATION   CONJUNCTION  DISJUNCTION   (if p then q)  (p equiv. q)
   (not p)     (p and q)    (p or q)     (p only if q)   (p iff q)

    p | ~p     p q | pq     p q | pvq     p q | p->q     p q | p=q
   --------   ----------   -----------   ------------   -----------
    T |  F     T T |  T     T T |  T      T T |  T       T T |  T
    F |  T     T F |  F     T F |  T      T F |  F       T F |  F
               F T |  F     F T |  T      F T |  T       F T |  F
               F F |  F     F F |  F      F F |  T       F F |  T

Note that there are different symbols used for these operations, 
depending on the system used. Here are some of the more common 
alternatives:

Negation: Tilde (~) before the proposition, bar above the proposition.

Conjunction: No symbol between propositions, carat (^) or 'cap' 
between propositions, dot between propositions. (Also related to 
intersection, usually represented by an inverted 'U'.)

Disjunction: 'v' or 'cup' between propositions, plus sign (+) between 
propositions. (Also related to union, usually represented by a 'U'.)

Implication: Right arrow (->) between propositions, 'U' turned 90 
degrees counterclockwise between propositions. (Sometimes these are 
written "backwards"; q<-p is logically equivalent to p->q. The former 
is usually read 'q if p' or 'q is implied by p'.)

Equivalence: Equivalence symbol (similar to the equals sign (=), but 
with 3 parallel segments) between propositions, double arrow (<->) 
between propositions. (Though they are not technically the same, 
frequently the equals sign (=) is used in place of the equivalence 
symbol when typing on a computer, because the latter is not part of 
most standard keyboard symbol sets.)

Another logic connective that you might run into is the exclusive-or. 
This is more commonly used in electronic logic circuits than in 
propositional calculus (the study of logic). Its truth table is the 
opposite of the equivalence truth table (i.e. the outputs are F T T F 
when the tables are written as above). Symbols used for exclusive-or 
include a circled plus sign, an equivalence sign with a slash (/) 
through it (read 'p not equivalent to q'), or sometimes a circled 'v'.

Here are some useful equivalencies:
(Note that T is any tautology - a proposition that's always true, and 
F is a contradiction - a proposition that's always false.)

      p->q = ~pvq                                 Def. of implication
     p<->q = (p->q)(q->p)                         Def. of equivalence
     p(+)q = ~pq v p~q                            Def. of ex-or
     ~(~p) = p                                    Double negation
        ~T = F                  ~F = T            Def. of negations
       pvq = qvp                pq = qp           Commutative laws
   (pvq)vr = pv(qvr)         p(qr) = (pq)r        Associative laws
    p(qvr) = pq v pr        pv(qr) = (pvq)(pvr)   Distributive laws
       pvF = p                  pT = p            Identity laws
      pv~p = T               p(~p) = F            Negation laws
       pvp = p                  pp = p            Idempotent laws
    ~(pvq) = (~p)(~q)        ~(pq) = ~pv~q        DeMorgan's laws
       pvT = T                  pF = F            Universal bound laws
    pv(pq) = p              p(pvq) = p            Absorption laws
   pv(~pq) = pvq           p(~pvq) = pq               "       "

I hope this helps. If you have any more questions, write back.

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