Name: SSN: Grade:MA334 FINAL EXAM December 1999I pledge my honor that I have abided by the Stevens Honor System.1. (10pts)Use a truth table to check the validity of the following argument.• P1: If Bob is not on the Mets, then Tom is on the Yankees.• P2: If Tom is not on the Yankees, then Bob is on the Mets.• C: Bob is not on the Mets or Tom is not on the Yankees.2 (8pts) Let U = Z. Are the following true or false? Explain.• ∀x ∃y [x + y = 0]• ∃y ∀x [x + y = 0]• ∀x ∃!y [xy = 0]• ∀x ∃!y [xy = 1]3 (10pts) Prove or disprove: The even negative integers are a countably infinite set.4 (10pts) Prove that for all integers n, n is odd if and only if n3is odd.Note: Do not use induction.5 (14pts) Let A, B, C be subsets of a universe U . Prove using the element method or disprove witha counterexample.1. If C ⊆ A − B then B ∩ C = φ2. C − (B − A) ⊆ A ∪ (B ∩ C)3. A x (B − C) ⊆ (AxB) − (AxC).6 (12pts)• Partition the set of real numbers R into 5 sets in such a way that the integers 1,2 and 3 fallinto the same set in the partition as√2.• Let T = {5, 6, 7, . . . , 16} If 7 integers are chosen from T , show that some two of them mustsum to 21. Explain.7 (12pts)1. Find a set A and a 1 − 1 function f : A → A that is not an onto function.2. Let f : A → B and g : B → C be onto functions. Prove that gof : A → C is an onto function.8 (12pts) Let Σ = {0, 1} and A = Σ5. For s, t ∈ A, let sRt if and only if the first three characters ofs are the same as the first three characters of t.• Show that R is an equivalence relation.• What are the equivalence classes of R?9 (12pts)• Prove or disprove: If f : N → N given by f(n) = 5n + 3 is a 1-1 function.• Let A = {x ∈ R | − 5 ≤ x ≤ 5} and B = {x ∈ R | 0 ≤ x ≤ 10}. Sketch χA∩B: R → {0, 1}.10 (12pts) Decide if each of the following relations on the given set A is reflexive, symmetric,antisymmetric and/or transitive. If not, explain.1. A = Σ∗, where Σ = {0, 1}R1: {(w1, w2) | w1∗ w2has an even number of 1’s}2. A = {a, b, c, d, e}R2: {(a, a), (b, a), (a, e), (a, d), (b, c), (c, d), (d, c), (d, a)}3. A = ZR3: {(x, y) | |x − y| ≤ 2}11 (12pts)1. Let A = {a, b, c, d}. Find an antisymmetric relation R1on A and a different antisymmetricrelation R2on A such that R1∪ R2is not antisymmetric.2. Let R be a relation on the set of points in the plane given by(x1, y1)R(x2, y2) iff x1= x2.(a) Show that R is an equivalence relation(b) What is [(3, 7)]?12 (12pts) Given the relations R and S on {a, b, c, d}, find• R−1• R2• Rt• RS13 (10pts)• Draw the Hasse diagram for the relation R on P (S), where S = {0, 1, 2}, given by X R Y iffX ⊆ Y .• Find a chain in P (S) of length four.14 (10pts) Prove by induction: ∀ n ≥ 2, n can be written as a product of primes.15 (10pts) Prove by induction: ∀ n ≥ 2, n3− n + 3 ≡ 0 (mod 3).16 (10pts) Prove by induction: ∀ n ≥ 1, the complete graph Knhasn(n − 1)2edges.17 (12pts)Construct a simple graph G on 8 vertices having exactly two vertices of degree two that is1. both hamiltonian and eulerian2. hamiltonian but not eulerian3. eulerian but not hamiltonian4. neither eulerian nor hamiltonian.18 (12pts) Find, if possible, a simple graph having the following properties. If not possible, explainwhy not.1. A graph on 11 vertices in which each vertex has degree 4.2. A graph on 13 vertices in which each vertex has degree 3.3. A tree on 11 vertices with exactly two vertices of degree one and exactly one vertex of degreethree.4. A connected graph with 16 edges and each vertex has degree