CSCI 2824 - Spring 2018 This assignment is due on Friday, February 16 either in class or under your prafessors doo by 12 PM (on. Yau are expected to write up your solutions neatly, with ful explanations and justifications when necesary. Remember that you are encouraged to discuss problems with your classmates, but you must work and write your solutions on your ow Important: On the FRONT of your assignment clearly write your l namd the lecture section you belong to (001 or 02). At the very top of the BACK af your assignment clearly write your full name. 1. Consider the fouowing argument. Let the domain be all people" Premisei: All surfers know how to swim and have to compete at in least one suring competition. Premise i: There is no person that kows ho to swim or does not have to conpete in at least one surfing competition Conclusion: There exist no surters. (a) Translate each of the premes and the conclusion into logical statements using propositional unctions, conectives and quantifiers. Be sure to define all quantities that you use. (b) Use rules of inference and lgical equivalences to show that the argument is valid. Be sure to cite which rules of inference or logical equivalences you use on ench line of your proof, and indicate which line umbes are invalved in ench step. 2. For each claim below, prove or disprove the claim. (a) Every positive integer can be expressed as the sum of two perfect squres. (A perfect square is the square of an integer. 0 may be used in the sum.) (b) For all rational numbers and b, ab is also rationaL 3. Prove each of the following. Be sure to indicate wbether you are using a Direct Proof, a Contrapositive Proof, a Proof by Cuse, or a Proof by Contradiction. If you use Proof by Cases, be sure to indicate what ench caseis, and in each cae, which type of proof you are using. (a) Prove that for an in1)2 is even if and only i n iseven. (b) Let a and b be integers and define c= a x b++1. Prove that e is even if and only if and b are both even (e) Prove that if 5 divides4 ten5 divides 41 4. (a) We saw in class that for sets A and B, the cardinality of their union is given by IAU = IAI + IBI-lan Bl. Derive the folowing analogous rule fr the union of three sets: Hint: Start by treating (BUC)ane set and then apply the two-set rule given toe, along with set Sdentities from Table 1 in Section 2.2 (b) 40 surfers all participated in three competitions on the fallowing planets: Earth (E), Naboo (N) and Bird World B). The following table shaws haw many surfers wiped out in each contest and in their various combinations (e.g. 5 people wiped out in bath the nsts on Earth and Bird World, ad 4 people wiped out in all three contests). aId arci How many people did not wipe out atl in any of these three contests? CSCI 2824 - Spring 2018 This assignment is due on Friday, February 16 either in class or under your prafessors doo by 12 PM (on. Yau are expected to write up your solutions neatly, with ful explanations and justifications when necesary. Remember that you are encouraged to discuss problems with your classmates, but you must work and write your solutions on your ow Important: On the FRONT of your assignment clearly write your l namd the lecture section you belong to (001 or 02). At the very top of the BACK af your assignment clearly write your full name. 1. Consider the fouowing argument. Let the domain be all people" Premisei: All surfers know how to swim and have to compete at in least one suring competition. Premise i: There is no person that kows ho to swim or does not have to conpete in at least one surfing competition Conclusion: There exist no surters. (a) Translate each of the premes and the conclusion into logical statements using propositional unctions, conectives and quantifiers. Be sure to define all quantities that you use. (b) Use rules of inference and lgical equivalences to show that the argument is valid. Be sure to cite which rules of inference or logical equivalences you use on ench line of your proof, and indicate which line umbes are invalved in ench step. 2. For each claim below, prove or disprove the claim. (a) Every positive integer can be expressed as the sum of two perfect squres. (A perfect square is the square of an integer. 0 may be used in the sum.) (b) For all rational numbers and b, ab is also rationaL 3. Prove each of the following. Be sure to indicate wbether you are using a Direct Proof, a Contrapositive Proof, a Proof by Cuse, or a Proof by Contradiction. If you use Proof by Cases, be sure to indicate what ench caseis, and in each cae, which type of proof you are using. (a) Prove that for an in1)2 is even if and only i n iseven. (b) Let a and b be integers and define c= a x b++1. Prove that e is even if and only if and b are both even (e) Prove that if 5 divides4 ten5 divides 41 4. (a) We saw in class that for sets A and B, the cardinality of their union is given by IAU = IAI + IBI-lan Bl. Derive the folowing analogous rule fr the union of three sets: Hint: Start by treating (BUC)ane set and then apply the two-set rule given toe, along with set Sdentities from Table 1 in Section 2.2 (b) 40 surfers all participated in three competitions on the fallowing planets: Earth (E), Naboo (N) and Bird World B). The following table shaws haw many surfers wiped out in each contest and in their various combinations (e.g. 5 people wiped out in bath the nsts on Earth and Bird World, ad 4 people wiped out in all three contests). aId arci How many people did not wipe out atl in any of these three contests