Name: SSN: Grade:MA334 FINAL EXAM December 1998I pledge my honor that I have abided by the Stevens Honor System.Note: If you need extra space for a problem, please use the previous blank page.1 (10pts)Use a truth table to check the validity of the following argument.• P1: Being fast is a sufficient condition for being a basketball player.• P2: Being a basketball player is a necessary condition for being tall.• P3: Mike is tall, but not fast.• C: Mike is a basketball player.12 (10pts) Prove that for all integers n, n is odd if and only if n3is odd.23 (8pts) LetLet A = {n ∈ Z |−1 <n<5},B = {n ∈ Z | 0 <n≤ 6},C = {1, 3, 5},andD = {2, 4, 6}.• Find CxD.• Find P (A ∩ C).• Find (A ∪ B) ∩(C ∩ D).• Do C and D partition B? Explain.34 (8pts)• Define: Sets A and B have the same cardinality.• Use the above definition to show that A = {x ∈ R | 0 ≤ x ≤ 10} and B = {x ∈ R | 0 ≤ x ≤ 5}have the same cardinality.5 (10pts)Prove or disprove: If f : X → Y and g : Y → Z are onto functions, then gof : X → Z is an ontofunction.46 (12pts) Let A, B, C, D be subsets of a universe U. Prove from first principles (using the elementmethod) or disprove with a counterexample.1. If C ⊆ A − B,thenB ∩C = ∅.2. If B ⊆ A ∪ C,thenA ∩ C = B.3. (A ∩ B) x (C ∩D) ⊆ (AxC) ∩(BxD)57 (16pts) Are the following functions 1-1? onto? If not, explain.1.f: R+→ R+x → x42.f: N → Nn → 2n +13.f: R → Rx → cos x4.f: R −{0}→Rx →2x +1x68 (12pts) Let A = {0, 1},B = {a, b, c} and C = {x, y, z}.• How many functions are there from B to C?• List all the 1-1 functions from A to B.• List all the onto functions from B to C.9 (8pts)1. Let f,g,h : R → R,wheref(x)=x3,g(x)=x4,h(x)=cosx.Findhogof.2. Show that if 65 points are placed in a unit square, at least 2 of them will be no further than14√2apart.710 (16pts) Decide if each of the following relations on a set A is reflexive, symmetric, antisymmetricor transitive. If not, explain.1. A = {all propositions}R: {(p, q) | p → q is true}2. A = {a, b, c, d}R: {(a, b), (a, c), (a, d), (b, c), (b, a), (c, a), (c, d), (d, a)}3. A = ZR: {(m, n) | m · n is even}4. A = RR: {(x, y) ||x|≤1and|y|≥1}811 (12pts) Consider the relations R and S defined on the set A = {a, b, c, d} given below. Find1. RS2. Rs3. Rt4. R25. R ∪ S6. R ∩ S912 (8pts) Let R be a relation defined on points in the plane given by (a, b) R (c, d) if and only ifb = d.1. Prove that R is an equivalence relation2. What is the equivalence class of (2, 3)?1013 (6pts) Let A = {1, 2, 3, 4, 5}. Find, if possible, an equivalence relation R on the set A that doesnot contain either (2, 3)or(3, 5). What is [1] in your relation?14 (10pts) Draw the Hasse diagram for the relation R on A = {2, 3, 5, 7, 10, 15, 21, 30, 35},andwheremRn iff m | n. Partition A into 3 disjoint antichains.1115 (10pts) Prove by induction: ∀ n ≥ 1, the complete bipartite graph Kn,nhas n2edges.1216 (10pts) Prove by induction: ∀ n ≥ 2,ncan be written as a product of primes.1317 (10pts) Prove by induction: ∀ n ≥ 0,n+1Xi=1i · 2i= n · 2n+2+2.1418 (8pts)1. Find, if possible, a simple connected graph on 7 vertices and 12 edges that is hamiltonian.2. Find, if possible, a simple connected graph on 7 vertices and 10 edges that is eulerian.1519 (8pts)1. Find the length (number of edges) of a longest trail in each of the following graphs. Explain.• K3,3• K92. Must every tree have a vertex of degree one? Either prove or disprove with a counterexample.1620 (8pts)1. What is the coefficient of a97b3in (a + b)100?2. How many distinguishable ways can the letters of the word ABRACADABRAABRACADABRAbe arranged?3. A committe has 17 men and 19 women. How many subcommittees of 6 people can be formedwith at least 2 men?4. Given the committee above, how many nonempty subcommittees can be formed of any