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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2013 The Math Forum