Tautologies in Logic Proofs
Date: 02/14/2001 at 19:36:14 From: Alex Bryant Subject: Logic: Tautologies Dear Dr. Math, I'm in an advanced math class in sixth grade, and we're doing logic proofs. My teacher says that if all your hypotheses and your conclusion are NOT tautologies, you can do the proof. But I think he's wrong because if you do a truth table all the problems we get are tautologies. So is my teacher right or wrong?
Date: 02/15/2001 at 23:13:07 From: Doctor Achilles Subject: Re: Logic: Tautologies Hi Alex, Thanks for writing to Dr. Math. That's a very interesting question. Let's start with a few definitions, just so we're using the same symbols and terms (this might be review for you). The symbols p, q, r, s, and t are simple sentences. ~: 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 and only if p is true, or q is true, or (p^q) is true. ->: This means "implies." The sentence (p->q) is true if and only if the p is false or q is true (the sentence ((~p)vq) is true). =: This means "if and only if." The sentence (p=q) is true if and only if p and q have the same truth value. Any expression that uses the above symbols is a sentence if it uses them in the way shown above. A contradiction is any sentence that must always be false. For example, (p^~p) is a contradiction. A tautology is any sentence that must always be true. For example, (pv~p) is a tautology. A logical argument is a list of premises (hypotheses) and a conclusion. Three examples: P1: (pvq) P1: (pvq) P1: (pvq) P2: ~p P2: ~p P2: p ----------- ----------- ----------- C: q C: ~q C: q A *valid* argument is one where there is no way to make every premise true and make the conclusion false. That is, an argument is valid if and only if you get a tautology when you connect all the premises with ^'s and add a -> and then the conclusion. So the first example is a valid argument if and only if (((pvq)^~p)->q) is a tautology. It is, so the first example above is valid. The second example is valid if and only if (((pvq)^~p)->~q) is a tautology. This is actually a contradiction, so the second example is not valid. The third example is valid if and only if (((pvq)^p)->q) is a tautology. It is neither a tautology nor a contradiction, which means this argument is also not valid. So what does it mean that you can do a proof as long as your hypotheses (premises) and your conclusions are not tautologies? It doesn't break the rules of logic to have tautologies in arguments, but you don't really prove anything if you do. Take a couple of examples: P1: (pv~p) P1: (rvs) P2: q P2: (t=q) ------------ ----------- C: q C: (pv~p) Try making sentences out of those. You will find that they are both tautological sentences. So these are valid proofs. What's wrong with the first example is that P1 does you no good. It's always true, and since you're putting it together with P2 using a ^, the part of the sentence before the -> symbol will always have the same truth value as P2. What's wrong with the second one is that the conclusion is a tautology and that makes the sentence (((rvs)^(t=q))->(pv~p)) a tautology. Both of the premises are irrelevant because the conclusion is always true. If you want to find out even more about logic, check out the following link: Basic Truth Tables and Equivalents in Logic http://mathforum.org/dr.math/problems/carissa.5.23.00.html It's from the high school logic area of the Dr. Math archives, at http://mathforum.org/dr.math/tocs/logic.high.html and I found it by doing a search on the keyword "logic." There's a whole lot more on logic available at the Dr. Math site. You can find it doing the same search at: http://mathforum.org/mathgrepform.html Hope this all helps. If you have any questions about this or any other math topics, or if there is a specific example that has you worried still, please write back. - Doctor Achilles, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.