Comp 2700 (Discrete Structures) Fall 2016. Problem Set 1. Submissions: This assignment is due at 11:59 PM on the 7th of September, 2016. Each student must submit his or her own assignment. Solutions can either be typed in Latex, MSWord or other such word processing software, or printed clearly. In the former case, please submit a pdf file and in the latter, scan your solution and again submit it as a pdf file. To submit a pdf file, put it inside the PS1 folder under Dropbox for Elearn. If you are done before class time, and are able to print your solutions on a printer, you can turn them in during class - in that case you need not submit again in dropbox. You must write your name and UUID clearly on your submitted assignment. Academic Integrity: You are encouraged to work in groups, but everyone must write out their own solutions. Absolutely no word to word copying is allowed. Please refer to the course policies and schedules about this. If you have worked with other students on the assignment or referred to external sources, please mention all names and sources on your assignment. IDK: If you do not know the solution to a problem, and you admit this by writing \"IDK\" (I DON'T KNOW) for its solution, you get 25% of the points for that problem. This is to reward honest admission, as well as the fact that you thought through it and understood that you do not know something. It is not wise to use this just for fun, as such points will hardly be enough to get a passing grade on the course. Partial solutions: If you are sure that you know how to arrive at a solution, but you get stuck in some place, it is better to write the partial solution rather than IDK. Honest attempts at partial solutions will be awarded and you might end up getting many more points compared to just an \"IDK\" solution. Problem 1 [5 + 5 pts]: Construct the truth table for the following compound propositions: (a) (p q) (p q) (b) ((p q) r) s Problem 2 [5 + 5 pts]: Show that the following are tautologies by using truth tables: (a) [(p q) (q r)] (p r) (b) [(p q) (p r) (q r)] r Problem 3 [10 pts]: We define a logical operator called the Pierce arrow denoted as follows: p q is True when both p and q are False, and it is False otherwise. Find a compound proposition equivalent to p q using only the logical operator . Problem 4 [5 + 5 pts]: For each part below, all the quantifiers have the same nonempty domain. Show that (a) xP (x) xQ(x) is logically equivalent to xy(P (x) Q(y)) (b) xP (x) xQ(x) is logically equivalent to xy(P (x) Q(y)) Problem 5 [5 + 5 pts]: If it is hot today and it rained yesterday, then I will be miserable today. If it is not hot today, then I am going to play soccer. If it did not rain yesterday, it will not rain today. I am not miserable today. Therefore, it did not rain today or I am going to play soccer. (a) Model the above given conditions as logical statements. Clearly define the propositions. Also, indicate the conclusion. (b) If the reasoning is correct, prove it using the rules of inference for propositional logic. Problem 6 [10 pts]: Prove that at least one of the real numbers a1 , a2 , . . . , an is greater than or equal to the average of these numbers. What kind of proof did you use? Problem 7 [10 pts]: If xyP (x, y) is true, does it necessarily follow that xyP (x, y) is true? If it is, prove it. Otherwise, give a counterexample that justifies your answer. Problem 8 [5 pts]: If A, B, C, D are sets does it follow that (A B) (C D) = (A C) (B D)? Problem 9 [15 pts]: The following are basic results in number theory that you may recall: 1 (I) Every odd integer is either of the form 4k + 1 or 4k + 3, i.e., it leaves a remainder of 1 or a remainder of 3 when divided by 4, and, (II) Every positive integer can be expressed as the product of prime numbers. Of course, in the representation there could be a single prime in the product if the number is itself prime, or there could be repeated prime numbers, for example 9 = 3 3, where the is multiplication. Using the above, show that there are infinitely many primes of the form 4k + 3, i.e., there are infinitely many prime numbers that leave a remainder of 3 when divided by 4. What proof strategy did you use? Problem 10 [10 pts]: Prove that in any party (with say, n people) some two shake the same number of hands. 2