MATH 211 Exam 1, Spring 2017

Math 211, Discrete Structures 2016-2017 Quiz 1 , February 2° ° Time 50 minutes Question 1. 4) Given the predicates L(cr, y):”2 likes to visite country y”, and Vad country y”. Let the universe be all people. Consider the logical pro Va(ay (L(x, y) AV (2,y)) V Vy(V (e 9) — ~ y))) Choose the correct translation: ae efyoe they like it. (a) For any person and any country, they either visit the conga cae ey dislike. (v) Everyperson, either visited a country they like or never vis Ee aialikes- he likes but not one ne (c) There is a person-who visited all countries Bic they ke. has visited all cou? (d) Everyone has either visited a country or is hen (choose (2) Let f: A —> B be a function such that ArVy(f (x) = gt = then ( i. : | the correct conclusion): fi | fin) Bt (4 ) (a) f is one-to-one. ( (c) There is an element of B that has a unique preimage in A. 4 / ‘KS (d) f is a bijection. / / Question 2. Y Suppose the universe is U = {u,2,-.- Un}. Then ; i. Represent the set S = {uz, Us, Ue, Un} in a binary way ii. What set T corresponds to the following binary representation: T = 1000100010...010 (computer representation). f s. (Be careful ) Draw the logic circuit of the following logical proposition: p VGAT 2? 5.4 about precedence of logical operators). Questjon 3. Suppose p —> s V -r and s —> —4, AN What is wrong with the following argument: If Va(x €G A—7+> 2 €B A gq —_ T. show using inference rules that p \then AC B. Question 4. 3) Prove that n er n(n + 1) ¥ 2] vee (H Let f:A— B,andg:B— C be two functions. Suppose that go f is 1 — Prove that f will also be 1-1. (3) Given that the union of two countable sets is countable, prove that R\Q is uncount- able. Good Luck!