Tautologies and ContradictionsDate: 02/19/2006 at 02:53:04 From: Timothy Subject: Tautology and Contradiction Hello Dr. Math, I have a question on tautologies and contradictions. On my upcoming test time is limited. In order for me to determine if a well-formed-formula is a tautology or contradiction, I will have to use a truth-table to see if it is all false or true. I was wondering if there is a faster way to determine that? Date: 02/20/2006 at 14:56:43 From: Doctor Achilles Subject: Re: Tautology and Contradiction Hi Timothy, To answer your question about how to tell if something is a tautology, the fall-back is truth tables, and if you're comfortable with those, then I would use them. If you want another method, here's what I do. NOTE: I will be teaching you a lot of new material. If you master it, then you will be able to very quickly figure out if something is a tautology or a contradiction, but it will probably take some time to get comfortable with this. If all of this is too confusing, then you may do better to just use truth tables. First, let me introduce you to a term: "main connective". The main connective is the central logical operation in a logical expression. I will use the word "connective" and "operation" interchangeably, they mean the same thing. The logical operations are: ~ : Not ^ : and v : or ->: if, then <->: if and only if or equivalence The simplest logical expression is a single term: A This is either true or false, but we don't know which. One operation we can apply is: ~A The other operations all require two terms: (A ^ B) (A v B) (A -> B) (A <-> B) We can build more complicated sentences. To build a complicated sentence just requires connecting the basic sentences with operations: ~(A ^ B) This sentence is made by attaching the operator ~ to the sentence (A ^ B). ((A v B) ^ C) I made this by connecting the sentence (A v B) and the sentence C with the ^ operator. ((A -> B) -> A) This sentence connects (A -> B) with A using ->. (((A ^ B) -> C) <-> C) This connects ((A ^ B) -> C) to C using <->. Notice that the -> is not the main connective, even though it's in the middle. ~(A -> (~B v A)) Here the main operator is ~ and it applies to the sentence (A -> (~B v A)). Ok, so what does this have to do with figuring out if a sentence is a tautology or a contradiction or neither? Here's how I solve that kind of problem: Step 1: Find the main connective. Step 2: Figure out if I can find any way to make the sentence true. Step 3: Figure out if I can find any way to make the sentence false. If I cannot make it true, but I can make it false, then it is a contradiction. If I can make it true, but cannot make it false, then it is a tautology. If I can make it true and I can make it false, then it is neither. Step 1 requires some practice. Once you get the hang of it, it won't take long to find the main connective. For step 2: If the main connective is ~, then to make the sentence true, you need to figure out a way to make the sentence inside false. For example, I know that the sentence ~(A v B) can be made true because I know I can make (A v B) false. If the main connective is v, then to make the sentence true, you need to figure out a way to make EITHER of the sentences it connects true. For example, I know that the sentence ((~A ^ A) v (~B ^ B)) must be a contradiction, because I cannot find a way to make either (~A ^ A) or (~B ^ B) true, no matter what I do. If the main connective is ^, then to make the sentence true, you need to figure out a way to make BOTH of the sentences it connects true at the same time. For example, I know that the sentence ((A v FALSE) ^ ~A) is a contradiction, because I cannot make (A v FALSE) true without making A true, which means ~A will be false. If the main connective is ->, then to make the sentence true you can either figure out a way to make the part before the -> false, OR you can make the part after the -> true. For example, I know right away that the sentence: (A -> (((A ^ ~A) v (~B ^ B)) <-> (C ^ ~C))) is not a contradiction, because if I make A false, then the sentence will come out to be true. If the main connective is <->, then you need to find a way to make both parts true OR to make both parts false. For example, I know that ((A ^ ~A) <-> B) is not a contradiction, because (A ^ ~A) is always false, but if I make B false as well, then the sentence will be true. For step 3: Alright, now we've figured out if our sentence can ever be true, now we need to figure out if it ever can be false. If the main connective is ~, then we need to make the sentence inside true. For example, I know that ~(A -> (A v B)) is not a tautology, because I can make (A -> (A v B)) true. If the main connective is ^, then you need to make either of the parts false. For example, I know that (A ^ ((B -> C) v (C -> B))) is not a tautology because I can make it false if A is false. If the main connective is v, then you need to make BOTH of the parts false. For example, I know that (B v (B -> ~B)) is a tautology because if I make B false, then (B -> ~B) comes out true. If the main connective is ->, then you need to make the first part true AND the second part false. For example, I know that (C -> (C ^ D)) is not a tautology because I can make C true and still make (C ^ D) false. If the main connective is <->, then you need to make the two parts have different truth values. For example, I know that ((A ^ ~A) <-> B) is not a tautology because when I make B true, the two sides have different truth values. Ok, let me work through some examples: 1. (~(A v B) ^ B) Step 1, the main connective is ^, it connects ~(A v B) to B. Step 2, I cannot make the sentence true. When I try, I have to make B true. But when B is true, then (A v B) MUST BE true, so ~(A v B) is false. Therefore, I know that this is a contradiction. 2. ((B -> C) v C) Step 1, the main connective is v, it connects: (B -> C) to C. Step 2, I can make the sentence true. All I need to do is make C true. Step 3, I can make the sentence false. To do that I need to make C false, and I need to make (B -> C) false. I can do that when C is false and B is true. Therefore, this is neither a contradiction nor a tautology. 3. ~((A -> B) ^ ~A) Step 1, the main connective is ~, it governs: ((A -> B) ^ ~A) Step 2, I can make the sentence true. To do it, I need to make A true. When A is true, ~A is false, so the sentence ((A -> B) ^ ~A) will be false, so the negation of that (which was our original sentence) is true. Step 3, I can make the sentence false. To do that I need to make A false. When A is false, ~A is true AND (A -> B) is also necessarily true. Therefore, when A is false ((A -> B) ^ ~A) is true and so the negation is false. Therefore, the sentence is neither a contradiction nor a tautology. 4. ((~A ^ C) -> (B v C)) Step 1, the main connective is ->, it connects (~A ^ C) to (B v C). Step 2, I can make the sentence true. All I need to do is make A true (or make C false), either way (~A ^ C) comes out false, so the whole sentence comes out true. Step 3, I cannot make the sentence false. To make the first part true, I need to make A false and C true. If I do that, then the second part MUST also be true. Therefore, the sentence must be a tautology. 5. ((A v ~B) <-> (~A ^ B)) Step 1, the main connective is <->, it connects (A v ~B) to (~A ^ B). Step 2, I cannot make the sentence true. Here's what I try: a) Make the first part true by making A true. When I do that, the second part ends up false. b) Make the first part true by making B false. When I do that, the second part ends up false. c) Make the first part false by making A false and B true. When I do that, the second part ends up true. So there is no way to get the two sides to have the same truth value. Therefore, the sentence is a contradiction. I hope all of this helps. If you have other questions or you'd like to talk about this some more, please write back. - Doctor Achilles, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/