Answer Happy

1. Proofs by truth table (30 points) a. Show that the following formula is a tautology: ((p 9)-P)-- b. Show that the following formula is a contradiction: piqpvog c. Show that the following formula is satisfiable but not a tautology: (pvqvr)^(pvavr) 2. Disjunctive and conjuctive normal forms (30 points] a. You have three propositional variables p, q, and r that have to meet one of two conditions: Either exactly one of them is true or all three are true. Write down a truth table meeting those conditions. b. As discussed in class, using the truth table write down an expression in disjunctive normal form (DNF) that is true when the conditions mentioned above are true. c. Using the truth table, write down an expression in conjunctive normal form (CNF) that is true when the conditions mentioned above are true. 3. Translating conditions into a logical formula [20 points] You need to find integers that we'll call "allowable". An allowable integer must be divisible by 5 but not by 25, unless it is also divisible by 125. For example, 5, 10, 15, 20, and 30 are allowable; 25 and 50 are not; but 125 and 250 are. a. Using the "leap year" example done in class, label these conditions with propositional letters and write down a truth table where the last column indicates which combinations are allowable (true), which are not (false), and which can't happen (x). b. Write down a DNF expression that is true when the conditions above are met