Tautology and Substitution Principles

Date: 02/28/2001 at 09:32:06
From: Sara
Subject: Tautology and Substitution principles

I don't understand the difference between the tautology principle and 
the substitution principle. Can you please help?

Date: 02/28/2001 at 10:48:59
From: Doctor Achilles
Subject: Re: Tautology and Substitution principles

Hi Sara,

Thanks for writing to Dr. Math.

Just to make sure we're on the same page, these are the logical 
symbols I will use:

  ~:  This means "not". The sentence ~p is true if and only if   
      p is false.

  ^:  This means "and". The sentence (p^q) is true if and only if 
      p is true and q is true.

  v:  This means "or". The sentence (pvq) is true if p is true, 
      or if q is true, or if both are true.

  ->:  This means "if...then" or "entails". The sentence (p->q) 
       has this truth table:

    p         q            (p->q)
    T         T              T
    T         F              F
    F         T              T
    F         F              T

  =: This means "if and only if" or "logically equivilant".  
     The sentence (p = q) is true if and only if p has the same truth  
     value as q. They can both be true or they can both be false.

Now that that's out of the way, what is a tautology? A tautology is a 
sentence that is always true. A classic example of a tautology is the 
sentence (pv~p).

Here's why it's a tautology:

  p is either true or false, but we're not sure which

  IF p were true, then the sentence (pv~p) would be true

  IF p were false, then the sentence (pv~p) would be true

So before we even know if p is true, we know (pv~p) is true.

A few other examples of tautologies are: (q->q), (r=r), ~(p&~p), 
((p&q)->q), (((p&q)v(p&~q))=p).  

That last one is a little tricky. Try substituting in different truth 
values for p and for q and see what you get.

What about the substitution rule? There may be more than one 
substitution rule in logic, but this is the one I'm familiar with:

  1) Start with a tautology.  For example ((p&q)->q).

  2) Pick any sentence in logic that you like.  This can be a 
     tautology or not, whatever makes you happy. For example 
     ((r&s)->t).

  3) Replace (substitute) every letter in the tautology from step 1 
     with your new sentence. Let's try replacing q. NOTE: it is VERY 
     important at this step that you get EVERY occurrence of the 
     letter you are replacing. This gives us:

  ((p&((r&s)->t)->((r&s)->t))

We just proved a new tautology. In other words, we just found a new 
logical truth. What this says is: if p is true, and r and s together 
entail t, then r and s together entail t. Not too exciting, I know, 
but logic works in small steps.

Hope all this helps.  If you have any other questions about this or 
any other math topics, please write back.

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