Formal Methods NameMidterm 1, Spring, 2007Show Your Work! Point values are in square brackets. There are 35 points possible. Tables oftautologies and contradictions are on the last page.1. Use truth tables to prove that the following logical expressions are tautologies. [6 points](a) P → (P ∨Q)(b) (P ∧ Q) → P(c) [P ∧ (P → Q)] → Q(a)P Q P ∨ Q P → (P ∨ Q)T T T TT F T TF T T TF F F T(b)P Q P ∧ Q (P ∧ Q) → PT T T TT F F TF T F TF F F T(c)P Q P → Q P ∧ (P → Q) [P ∧ (P → Q)] → QT T T T TT F F F TF T T F TF F T F T12. Without using a truth table, prove that (P ∧ Q) → (P ∨ Q) is a tautology. You can use anyof the facts on page 7. [3]We give two proofs. The first uses the table of tautologies. The second uses our knowledgeof the various logical operators.First Proof.(P ∧ Q) → (P ∨ Q) ⇔ ¬(P ∧ Q) ∨ (P ∨ Q) Tautology 5⇔ (¬P ∨ ¬Q) ∨ (P ∨ Q) Tautology 1.1d⇔ (P ∨ ¬P ) ∨ (Q ∨ ¬Q) Tautologies 6 and 1.2i⇔ T ∨ T Tautology 1⇔ T Tautology 2Second Proof. An implication can be false only if the hypothesis is true and the conclusionis false. Our hypothesis is P ∧ Q, which can only be true if both P and Q are true. Butif both P and Q are true, then our conclusion, P ∨ Q, must also be true. So whenever thehypothesis is true, the conclusion must also be true. So the implication (P ∧ Q) → (P ∨ Q)is always true, and hence a tautology.3. Which (if any) of the following expressions are tautologies? Which (if any) are contradictions?You don’t need to prove anything. [4](a) P ∨ P Neither(b) P ∧ P Neither(c) ¬P Neither(d) P ↔ P A tautology24. Suppose that f(x) is a real-valued function defined on all the real numbers. Consider thefollowing definitions.i. f(x) is injective iff for all real numbers x and for all real numbers y, f (x) = f(y) impliesx = y.ii. f(x) is surjective iff for each real number y, there exists a real number x such thatf(x) = y.Give clear, idiomatic definitions of the following expressions.(a) f(x) is not injective.(b) f(x) is not surjective.[4](a) f(x) is not injective iff there exists a real number x and there exists a real number y,such that f(x) = f (y) but x 6= y.(b) f(x) is not surjective iff there exists a real number y such that for each real number x,f(x) 6= y.5. Sally wants to prove that if n2is odd, then n is odd. She’s decided to prove the contrapositive.(a) What can Sally assume?(b) What should she prove?(You don’t need to prove anything.) [4]The contrapositive of P → Q is ¬Q → ¬P. In Sally’s theorem, P is “n2is odd,” and Q is “nis odd.”(a) So Sally should ass ume that n is not odd. In light of a theorem proved in class, this isequivalent to assuming that n is even.(b) Sally should prove that n2is not odd. Once again, in light of a theorem proved in class,this is equivalent to proving that n2is even.36. Bob is trying to prove the following theorem.If n is a positive integer that is not a perfect square, then√n is irrational.He’s decided to try using proof by contradiction.(a) What should Bob assume?(b) At some point in his proof, Bob deduces that 0 = 1. He asserts that this is the desiredcontradiction. Sally says that Bob is mistaken: a contradiction must have the formR ∧ ¬R for some statement R. Who’s right? Bob or Sally?(You don’t need to prove anything.) [4]Bob wants to prove P → Q by contradiction, where P is “n is a positive integer that is nota perfect square,” and Q is “√n is irrational.”(a) In a proof by contradiction, you assume P ∧ ¬Q. So Bob should assume that n is apositive integer that is not a perfect square. He should also assume that√n is notirrational, i.e.,√n is rational.(b) Contrary to what the text says, a proof by contradiction does not require that we deducea statement having the form R ∧¬R. It only requires that we deduce a false statement.Since 0 = 1 is false, it will serve as the desired contradiction. Bob is right.7. Bob and Sally have determined that the following statement is false.There exist positive integers n, a, b, and c such that n ≥ 3 and an+ bn= cn.However, they can’t agree on how to show the statement is false. Bob says that they justneed to find a counterexample. Sally says that they need to prove a theorem. Who’s right?(You don’t need to prove anything.) [2]This time Sally wins the prize. A counterexample will disprove a statement that has theform ∀xP (x). In order to disprove a statement that has the form ∃yQ(y), you need to show∀y¬Q(y). So they need to prove that for all positive integers n, a, b, and c such that n ≥ 3,an+ bn6= cn. (This, by the way, is known as Fermat’s last theorem, and, until recently, it wasone of the most famous unsolved problems in mathematics.)48. Suppose x is an irrational number. Prove that 1/x is also irrational. [3]Proof. First note that 0 = 0/1 is rational. So if x is irrational, x 6= 0. So 1/x is a realnumber. Furthermore, since x · 1/x = 1, 1/x 6= 0.Now in order to prove that 1/x is irrational, we use contradiction. So we assume that xis irrational, but 1/x is rational. Since 1/x is rational, there exist integers m and n withn nonzero such that 1/x = m/n. Then since n 6= 0 and 1/x 6= 0, n · 1/x = m is nonzero.Multiplying both sides of this equation by x gives n = xm, and since m is nonzero, n/m = x.But this says that x is rational, contradicting our assumption that x is irrational. Thus, theassumption that 1/x is rational must be false, and if x is irrational, then 1/x is also irrational.59. Consider the following two statements .i. There exists a nonzero integer n such that for every real number x, x ≤ n.ii. For every real number x, there exists an intege r n such that x ≤ n.One statement is true. The other is false. Which is which? (You don’t need to proveanything.) [2]The first statement says that there is an integer n with the property that every real numberis less than or equal to n. Clearly, this is false. For example, if n is any integer, then n + 1 isa real number, and n < n + 1.The second statement says that given a real number x, there is an integer that’s at least aslarge as x. This, of course, is true. For example, if the decimal expansion of x isy.d1d2d3. . . ,then y is an integer and y + 1 is an integer that’s greater than or equal to x.10. Give a direct proof of the fact that …