MATH 211 Exam 1 With Solution, Spring 2014

MATH 211 SPRING 2014 TEST I VERSION A E NAME: SECTION: (1) True/False Questions (2 points each): Here A, B etc. denote sets while x,y, -+- denote elements, and P(A) denotes the power set of a set A @ F {8} c {4,{{o}}} te) Pe) = (16}} T @) a € {R, N,Q}, where 7 is the well-known number @) F Disjunctive Syllogism uses the tautology ((p V q) A 7p) > ¢ T (®) The proposition (=p — q) — (q — p) is not a contingency T @ Let {an} be a geometric progression with first term a@ = 1 and common ratio r = 2. Then }> a, = 270 — 27°, k=9 Wy @) Aand B are two sets such that card(A) = card(B) = 3, then card(P (A x B)) = Bing 98 zh ®) For any f : A B, S any subset of A we have fags) <5 @) F There exist two sets A and B such that A is both an element of B as well as a subset of B at the same time @) F (ANB)U(ANB)U(ANB) =AUB T @) existential instantiation states that if 3eP(a) is true, then you can prove that P(c) is true for an arbitrarily selected member in the domain. @) F Let f : A— B be a one-to-one function, let S and T be two two subsets of A, then f(SAT) = f(S)N f(T) @) FA universal quantifier has a higher precedence over the logical operator A T @) The inverse of the proposition “you need to buy gasoline whenever you drive more than 400 kilometers” is “if you need to buy gasoline, then you would have driven more than 400 kilometers” (2) (6 pt.) Find a bijective function f from N to Z. Make sure you prove that your function is both one to one and onto. [Ny © \ oS ‘Ss 4 S BG aes g:o- ltl 22 -3 3 H. é a ; nis even ising this alignment, define Fen) = j2? a. -Mm+v) 8 n is ode 2 skis Ack: sugpose f¢m)=f(n2) Sor seme mys Me © IN Case t) thir Commo) wractanae. US SSOm Haen ty eink & oe both even, yecase ne odd value wih rs Sent tea pe siKive value ,S& mo nt oy yn=N.. z 2 Case ti) if the Common valu is <0, thin both n, 8 =nN_rl|an=an- mM. watt be odd. \ n+l se =(nyt) . er oo © = 7 } i " ye a = g stis Ontos lk ZEZ, Th Z>0, then 2* is preimage if (22)= 5 | tf Z<0, Tex ne, Va Qe tse preimage D FGA?) oS -7 \ € is onté. > fo ve) Conia hens &. Preimag s there For f by ON 2 unction' f : Z defined by f(a) = 3a? +1. Is f one-to-one? Is f onto? one te one + Lak ayaegm be sil Ff Car) = far) , S& Borel = Sar +l => 3a) =3a = ap =Qy. Heme Ay=u becouse We Know that they are both positive . set LE iP aati 1 Ls NoT onth 4 lot Z<o¥f aos | hall z har a gre imige , Hun Zat+|=2. But 3aé+! D0, {un Co Z >PoO. This ContPadicté thy assump tien Mack Zio, Se & hoo n& pre-image ro | Ahohore $ is met onthe. (4) Use logical equivalences to prove the following statements, naming each logical equivalence you (a) (6 pt.) Show that the two propositions (p V q) > (p Aq) and q © p are logically equivalent. (evad— Cpr) = VHA Ge wig PEE = (RAY) v (prt) de Movgam’s law = Pv RA (CApvaaCiqy pacigvy) distributve law pvp AC VP) AT negation law, Commutadive K assoc. =O evan (a4 P) idenkity lew PATS Pp Se _ usin —>% = |\pv = , v at ’ by idan bi Primal (b) V6 pt.) Prove -(p > q) = pis a tautology. 1g 4) = P = TV ACp= ») vP wsing °— 1 = UVF = (p—4)vP double vesp Hon = Cv a) v 9 U Sing. poze lyre a” vp Cay Pp) assoCalive law Comm mct ah Ve, Jaw acsecialve jaw negation law dominahom i a Yente the above prope si Km tS @ tame-log y. (5) (6 pt.) Draw a combinatorial circuit that yields the output (pV q) A (=p Vr). Use the smallest number of logical gates possible for this problem. Hint: you may simplify the given proposition using logical equivalences first. aan 2 be ¢—— Remar: No te shat (pvDa pv) + @vr) is 1Pe resolution taut logy Howe ver @vealipvr) <> Gv is not a tau. fy logy [ cmsider, eg. pal, qT, r=F | se the civaat Cannel by reduad ty oe (6) (6 pt.) Let A and B be two sets. Show that if AC B then A~ BC B— A. Which method of proof did you use? We will wwe a direct proof : Swp pose that AcB se Uxek ten xeB, We claim thet A-B=¢, rh not, tn Ax €A-B. Hera x €A andxdB. Se x€B and xe, a contradiction. Sine the emily set is ee of on set, His i) yor A-6 ee a fa\ i xf Vey (7) (6 pt.) Prove that \/2 is irrational. L imitare the proof hat V2 is yrrattmnal |. Sup pnse Va 7 ratimal Hon Hore extst: te Lnvhes ers a amd b, with bfo suchthat Yo = S, Raising we @r <—— ; 2, x farther both Se To the four th power a 2 = re as S Me Hence QA= ab4 SG al if even, S@ A iseven Cprom) that & similarly 8 is tun even. se that a= aK for some d bb ave ne MEET K. Thin ate 16K? amd 16K%. 2 bt Commun Hema b= 9K! LS alot even. Like before, this factor, implies that b aS evem. We have this found that Cause rl % be | a ond b have 2 apa Ummm fachr. cottadiction . if thy % (8) (6 pt.) Prove or disprove that if x is any irrational number then so is Vz. | ey Co_ 4 Sw et be irrational’. (9) In the following let the universe of discourse for x be all students, and the universe of discourse for y be all European countries. Consider the premises: S(x): “a is a student in my class”; V(x, y) is “student x visited country y”. Translate the following statements into logical expressions: (a) (6 pt.) There is a student in my class who never visited any European country: axvy(7 vay) (b) (6 pt.) There is a European country that was visited by more than one student in my class: ay Axydn (x, FLAS CHA Slee), VG y)rVGaif)) (10) Using the predicates of the previous problem translate the following to English: (a) (6 pt.) Sey (AV (2, y1) AVya(n # y2 > V(x, ¥2))) There is a student who visited allf bet one Eien Gumtry (b) (6 pt.) 3x39 (a1 # x2 AVy (AV (21,y) o V(e2,y))) There are two students poker between thn, have visited alll European Coun dries but they never visited the Same MATH 211 SPRING 2014 TEST I VERSION B NAME: SECTION: (1) True/False Questions (2 points each): Here A, B etc. denote sets while x,y,--- denote elements, and P(A) denotes the power set of a set A @) F For any f: A— B, S any subset of A we have SC f~!(f(S)) F Let {an} be a geometric progression with first term @ = 1 and common ratio r = 2. 19 Then Svan = 270 _ 99. k=9 r@) (ANB)U(ANB)=A r ® Let f : A— B bea function, let S and T be two two subsets of A, then f(S)N f(T) C f(SNT) @) F There exist two sets A and B such that A is both an element of B as well as a subset of B at the same time T ® The inverse of the proposition “you need to buy gasoline whenever you drive more than 400 kilometers” is “if you need to buy gasoline, then you would have driven more than 400 kilometers” @) F {4} c {4 {{o}}} 2 @) If A = {a,b}, B = {c,d}, then ({a}, {c}) is an element of P(A x B) G@) FA universal quantifier has a higher precedence over the logical operator A T (®) P(e) = {10} (2) F 7«¢{R,N,Z}, where z is the well-known number (x) F_ The proposition (=p > q) > (q — p) is a contingency T @) Universal generalization states that VxP(x) is true, provided that you can prove that P(c) is true for a specific member in the domain. T 6) Modus tollens uses the tautology pA(p—p) 4 TEST VERSION (B) (9) In the following let the universe of discourse for x be all African countries, and the universe of discourse for y be all students. Consider the premises: S(y): “y is a student in my class” ; V(a,y) is “country x was visited by student y”. Translate the following statements into logical expressions: (a) (6 pt.) There is a student in my class who never visited any African country: ay vx(7 Ve QA S Y)) (b) (6 pt.) There is an African country that was visited by more than one student in my class: Ax At, ay, ( J, th, X SY)a SY, )A Very, MA V(xg.) (10) Using the predicates of the previous problem translate the following to English: (a) (6 pt.) Sy3xi (-V (21, y) AVae(a1 # x2 > V(x2,y))) There aS & student who texted all African Coumtries except ON] (b) (6 pt.) Syr3y2 (sn A y2 AVa (-V(e, m1) > V(x, ¥2))) There are {wo students whe beavis ner vicited the Same ALriCm Country , bu between them, they visited all B Sri can loss unt &