COT3100 Practice Problems for Exam 1.These problems are only meant to help you prepare the first exam. It is not guar-anteed that the exam questions will be similar to these problems.There will be five problems on the exam:1. Propositional logic and equivalences (1.1 and 1.2)2. Predicates and Quantifiers (1.3)3. Rules of Inference and Proofs (1.5)4. Set Operations (2.1 and 2.2)5. Functions and sequences (2.3 and 2.4)The (brief) solutions will be available only after 9pm on Thursday night. However,instead of memorizing the solutions, you should attempt to solve all problems byyourself first.1. What is the truth value of (p ∨ q) → (p ∧ q), when both p and q are false?Solution: You should work out this problem and convince yourself thatyour answer is correct.2. State the converse and contrapositive of, “If I answer this question, then Iwill get 4 points”.Solution: You just need to know the definitions of converse and contrapos-itive. Check out the textbook or lecture slides.3. Which rule of inference allows you to conclude, “Mark has stripes” fromthe statements, “Every zebra has stripes” and “Mark is a zebra”?Solution: Same as above.4. Construct the truth table for the proposition p → (¬q ∨ r).Solution: Clock yourself to make sure that you don’t take more than threeminutes on this problem.5. Prove that there is a positive integer that equals the sum of positive integersnot exceeding it.Solution: 3 is one such number.16. Prove that the product of a rational number and an irrational number is irra-tional.Solution: We know that the product and quotient of two rational numbersare also ration. Therefore, we can prove this by contradiction. Let p, q bethe two numbers with p rational and q irrational. Assume that r = pq is ra-tional. Then, this implies that q = r/p is also rational, which is the desiredcontradiction.7. Prove that the proposition [(p ∨ q) ∧ (¬p ∨ r)] → (q ∨ r) is a tautology.Solution: Compute the truth table and show that it is always true.8. We briefly discussed the uniqueness quantifier, ∃!. The notation ∃!x P (x)meant “There is a unique x, such that P (x) is true.” Express this uniquenessquantification ∃!x P(x) in terms of universal quantifiers, existential quanti-fiers and logical operators. (Hint: You might need to use nested quantifiers).Solution: Here is a partial solution:∃!x P (x) ≡ ∃x∀y{A −→ B}.You have to figure out what to put for A and B.9. Prove that at least one of the real numbers a1, a2, . . . , anis greater than orequal to their average.Solution: Proof by contradiction. If all aiare smaller than their average,then you can show that this average is smaller than itself, which is the con-tradiction.10. For the following argument, explain which rules of inference are used ineach step to lead from the premises to the conclusion:“There is someone in this class who has been to France. Everyone whovisits France visits the Louvre. Therefore, someone in this class has visitedthe Louvre”.Solution: Again, the answer can be found in the textbook (Section 1.5).11. Give one example of a trivial proof and one example of a vacuous proof.Solution: A vacuous proof is a proof that shows the hypothesis is false.Here is an example: Suppose x is a real number. Show that if x2< 0, thenx2+ x6= 2. The (vacuous) proof is to show that x2< 0 is false if x is realnumber. Then, because the hypothesis is false, the implication is alwaystrue.212. Use the rules of inference to prove that if(a) ∀x(P (x) ∨ Q(x))(b) ∀x(¬Q(x) ∨ S(x))(c) ∀x(R(x) → ¬S(x))(d) ∃x ¬P (x)are true, then ∃x ¬R(x) is also true.Solution: Work out this problem yourself. Make sure that you know how tosolve this problem. There are similar examples in the textbook and lectureslides.13. Prove that there cannot exist any real number x such that x2+ 1/x2= π/2.Solution: We did this in class.14. If x is an integer, prove that x = floor(x/2) + ceil(x/2).Solution: There are two cases: (1) x = 2k+1 is odd. Then floor(x/2) = kand ceil(x/2) = k + 1. Therefore, x = floor(x/2) + ceil(x/2). Similarly,if x is even, we can show that x = floor(x/2) + ceil(x/2).15. Prove that |A ∪B ∪C| = |A|+ |B|+ |C|−|A ∩B|−|A ∩C|−|B ∩C|+|A ∩ B ∩ C|.Solution: We went over this problem in class. You need to use the formula|A ∪ B| = |A| + |B| − |A ∩ B|.16. Give an example each of a function from the set of natural numbers to theset of natural numbers which is (a) one-to-one but not onto, (b) onto butnot one-to-one, and (c) neither one-to-one nor onto. Prove your example ineach case.Solution: (a) f(n) = n2. (b) f(n) = b√nc. (c) f(n) = 1.17. Let A1, A2, ...An.. be a countable collection of countable sets. Show thattheir union and intersection are also countable..Solution: The intersection will be a subset of say A1. Because A1is count-able, the intersection (which is a subset) is also countable. To show thattheir union is also countable, you can do the following. First, show thatthe set N>0× N>0is countable, i.e., the set of cartesian product of positiveintegers is countable. The required bijection is constructed exactly as in theproof that shows the set of rational numbers is countable. Once you have3shown that N>0× N>0is countable, you can define an onto function fromN>0× N>0to A1∪ A2∪ ... ∪ An∪ ... showing that the latter set is indeedcountable.18. Determine whether each of these sets is countable. For those that are count-able, exhibit an one-to-one correspondence between the set of natural num-bers and that set.(a) integers not divisible by 3.(b) integers divisible by 5 but not by 7.(c) the real numbers with decimal representations consisting of all 1s.(d) the real numbers with representation of all 1s or 9s.(e) the real numbers not containing 0 in their decimal representation.(f) the real numbers containing only a finite number of 1s in their decimalrepresentation.Solution: (a) and (b) are both countable because they are subsets of the inte-gers. (c) is also countable. (d) will depend on how you read the problem. Ifthe number can contain 1s or 9s but not both, then, it will be countable (it isjust a union of two countable sets). However, if the number can contain both1 and 9 in its decimal representation, then, the set is uncountable. Cantor’sdiagonal argument can be used here to show that this set is uncountable. (e)and (f) are both uncountable.19. Let f be a function from the set A to the set b. Let S and T be subsets of