Problem 1: (a) Build a truth table with columns for p → q, p ∧ (p → q),and so forth to determine whether (p ∧ (p → q)) → q is a tautology. Explainwhy your answer is intuitively reasonable.(b) Verify the result of (a) by applying logical equivalences. State whichequivalence you are using at each step.(c) Prove that for any sets A, B and C we always haveA ∩ (¯A ∪ B) ⊂ B.Solution: (a) A compound proposition, which depends on propositions p,q, r and so forth, is a tautology when it evaluates to true for any values ofthe propositions p, q and so forth. Intuitively, if we know p is true and pimplies q when true, then we know that q is true. The truth table readsp q p → q p ∧ (p → q) (p ∧ (p → q)) → qF F T F TF T T F TT F F F TT T T T T(b) By definition of implication, the given statement is equivalent to¬(p ∧ (¬p ∨ q)) ∨ qwhich by de Morgan is equivalent to¬p ∨ (p ∧ ¬q) ∨ q.Distributing each single-variable or over each and gives(((¬p ∨ p) ∧ (p ∨ ¬q))) ∨ q.Excluded middle and domination simplify the expression top ∨ ¬q ∨ qby associativity of ∨, which reduces to T by associativity, excluded middleand domination.(c) Translate the previous logical statement into sets and quantify.1Problem 2: Define Z+= {1, 2, 3, . . . } andQ+= {p/q | p ∈ Z+∧ q ∈ Z+∧ gcd(p, q) = 1}.Define f : Q+→ Z+by f (p/q) = p + q − 1. Justify your answers to thefollowing questions.(a) Is f onto?(b) Do Z+and Q+have the same cardinality?Solution: (a) Every element n of Z+is given by n = f(p/q) for p/q =n/1 ∈ Q+. Hence f is onto. (Since f(5/3) = f(3/5) = 8, f is not one-to-one.)(b) Since Z+is N with 0 removed, it is infinite and countable. We know thatthe rationals are countable, and a (bijective image of a) subset of a countableset is countable, so Q+is countable. Since it contains Z+, it is infinite, soZ+and Q+have the same cardinality.2Problem 3: (a) Compute (7×11×711×777) mod 13 by modular arithmetic.(b) Compute 66677mod 11.Solution: (a) Since 711 ≡ 61 ≡ −4 (mod 13) and 777 ≡ −3 (mod 13) wehave7 × −2 × −4 × −3 ≡ −14 × 12 ≡ −12 ≡ 1 (mod 13).(b) Since 666 ≡ 6 (mod 11), 66677≡ 677(mod 11). The relevant powers of 6(mod 11) are 62= 36 ≡ 3, 64= 9, 68= 81 ≡ 4, 616 = 16 ≡ 5, 632 = 25 ≡ 3,664 = 9, and 77 = 64 + 8 + 4 + 1 so 677≡ 9 × 4 × 9 × 6 ≡ 3 × −1 ≡ −3 ≡ 8(mod 11). Alternatively, 677= (67)11≡ (9×3×6)11≡ 811= 233= 326×8 ≡ 8(mod 11).3Problem 4: Consider the following pseudocode:G(n ∈ N, m ∈ N, function f : {0, 1, 2, . . . , n − 1} → {0, 1, 2, . . . , m − 1})for i := 0 to m − 1hi:= 0endfor j := 0 to n − 1i := f(j)hi:= hi+ 1endfor i := 0 to m − 1if (hi6= 1) then return Fendreturn Tend(a) What function of f, n and m does G return?(b) What is its worst-case complexity in terms of m and n in big-O notation?Justify your answer.(c) Let n = m > 2. For what values of a ∈ Z does G return T for thefunction f defined by f(j) = aj mod n?Solution: (a) It returns T iff the input function f is a bijection (a one-to-one correspondence).(b) The worst-case complexity is W (m, n) = O(m + n).(c) This function is a bijection when a is invertible (mod n), which happenswhen gcd(a, n) = 1. Note: on the actual exam, the sets were {1, . . . , n} and{1, . . . , m} so this function was (a) not a function into the desired range and(b) never a bijection, since n was not in the range of aj mod n. Hence theanswer “never” was also accepted as