Tautologies Example 1: What do you notice about each sentence below? 1. A number is even or a number is not even. 2. Cheryl passes math or Cheryl does not pass math. 3. It is raining or it is not raining. 4. A triangle is isosceles or a triangle is not isosceles. Each sentence in Example 1 is the disjunction of a statement and its negation. Each of these sentences can be written in symbolic form as p or_0.gif ~p. Recall that a disjunction is false if and only if both statements are false; otherwise it is true. By this definition, p or_0.gif ~p is always true, even when statement p is false or statement ~p is false! This is illustrated in the truth table below: p ~p p or_0.gif ~p T F T F T T The compound statement p or_0.gif ~p consists of the individual statements p and ~p. In the truth table above, p or_0.gif ~p is always true, regardless of the truth value of the individual statements. Therefore, we conclude that p or_0.gif ~p is a tautology. Definition: A compound statement, that is always true regardless of the truth value of the individual statements, is defined to be a tautology. Let's look at another example of a tautology. Example 2: Is (p and_0.gif q) conditional_0.gif p a tautology? p q p and_0.gif q (p and_0.gif q) conditional_0.gif p T T T T T F F T F T F T F F F T Solution: The compound statement (p and_0.gif q) conditional_0.gif p consists of the individual statements p, q, and p and_0.gif q. The truth table above shows that (p and_0.gif q) conditional_0.gif p is true regardless of the truth value of the individual statements. Therefore, (p and_0.gif q) conditional_0.gif p is a tautology. In the examples below, we will determine whether the given statement is a tautology by creating a truth table. Example 3: Is x conditional_0.gif (x or_0.gif y) a tautology? x y x or_0.gif y x conditional_0.gif (x or_0.gif y) T T T T T F T T F T T T F F F T Solution: Yes; the truth values of x conditional_0.gif (x or_0.gif y) are {T, T, T, T}. ___________________________________________________________________________________________________ Example 4: Is ~b conditional_0.gif b a tautology? b ~b ~b conditional_0.gif b T F T F T F Solution: No; the truth values of ~b conditional_0.gif b are {T, F}. ___________________________________________________________________________________________________ Example 5: Is (p or_0.gif q) conditional_0.gif (p and_0.gif q) a tautology? p q (p or_0.gif q) (p and_0.gif q) (p or_0.gif q) conditional_0.gif (p and_0.gif q) T T T T T T F T F F F T T F F F F F F T Solution: No; the truth values of (p or_0.gif q) conditional_0.gif (p and_0.gif q) are {T, F, F, T}. ___________________________________________________________________________________________________ Example 6: Is [(p conditional_0.gif q) and_0.gif p] conditional_0.gif p a tautology? p q p conditional_0.gif q (p conditional_0.gif q) and_0.gif p [(p conditional_0.gif q) and_0.gif p] conditional_0.gif p T T T T T T F F F T F T T F T F F T F T Solution: Yes; the truth values of [(p conditional_0.gif q) and_0.gif p] conditional_0.gif p are {T, T, T, T}. ___________________________________________________________________________________________________ Example 7: Is (r conditional_0.gif s) biconditional.gif (s conditional_0.gif r) a tautology? r s r conditional_0.gif s s conditional_0.gif r (r conditional_0.gif s) biconditional.gif (s conditional_0.gif r) T T T T T T F F T F F T T F F F F T T T Solution: No; the truth values of (r conditional_0.gif s) biconditional.gif (s conditional_0.gif r) are {T, F, F, T}. ___________________________________________________________________________________________________ Summary: A compound statement that is always true, regardless of the truth value of the individual statements, is defined to be a tautology. We can construct a truth table to determine if a compound statement is a tautology. ___________________________________________________________________________________________________ Exercises 1. What is the truth value of r or_0.gif ~r? Začátek formuláře (_) True (_) False (_) Not enough information was given. (_) None of the above. RESULTS BOX: _____________________________________________ Konec formuláře 2. Is the following statement a tautology? s conditional_transp.gif ~s Začátek formuláře (_) Yes (_) No (_) Not enough information was given. (_) None of the above. RESULTS BOX: _____________________________________________ Konec formuláře 3. Is the following statement a tautology? [(p or_0.gif q) and_0.gif ~p] conditional_transp.gif q Začátek formuláře (_) Yes (_) No (_) Not enough information was given. (_) None of the above. RESULTS BOX: _____________________________________________ Konec formuláře 4. Is the following statement a tautology? ~(x or_0.gif y) biconditional_transp_0.gif (~x and_0.gif ~y) Začátek formuláře (_) Yes (_) No (_) Not enough information was given. (_) None of the above. RESULTS BOX: _____________________________________________ Konec formuláře 5. Is the following statement a tautology? a and_0.gif ~a Začátek formuláře (_) Yes (_) No (_) Not enough information was given (_) None of the above RESULTS BOX: _____________________________________________ Konec formuláře