Homework_1 (1)

EECS 203: Discrete Mathematics Winter 2024 Homework 1 Due Thursday, January 25th , 10:00 pm No late homework accepted past midnight. Number of Problems: 7 + 1 Total Points: 100 + 20 • Match your pages! Your submission time is when you upload the file, so the time you take to match pages doesn’t count against you. • Submit this assignment (and any regrade requests later) on Gradescope. • Justify your answers and show your work (unless a question says otherwise). • By submitting this homework, you agree that you are in compliance with the Engi- neering Honor Code and the Course Policies for 203, and that you are submitting your own work. • Check the syllabus for full details. 1

Individual Portion 1. Collaboration and Support [3 points] (a) Give the names and uniqnames of 2 of your EECS 203 classmates (these could be members of your homework group or other classmates). (b) When you have questions about the course content, where can you ask them? Where are you most likely to ask questions? (c) Name one self-care action you plan to do this semester to maintain your overall well- being. Solution: (a) Emily : mccannem, Alexis : lexislee (b) When I have questions about the course content, I can ask them on Piazza or during discussion sections. Personally, I am most likely to ask questions on Piazza (c) I plan on taking time to indulge in my hobbies this semester to maintain my overall well-being. I’ll be sure to make some time to read and crochet throughout the semester. 2. Rock the Vote [12 points] Let p and q be the following propositions: • p : The election has been decided. • q : The votes have been counted. Express each of these propositions as an English statement: (a) ¬ p → ¬ q (b) ¬ q ∨ ( ¬ p ∧ q ) Solution: (a) If the election has not been decided, then the votes have not been counted. (b) The votes have not been counted, or the votes have been counted and the election hasn’t been decided. 2

must be a knight, but cannot be mayor because they must tell the truth about not being a mayor. In this scenario, there is no city mayor, meaning the city mayor cannot be a knight. Next, assume that the mayor is a knave. This means that B’s statement is true making them a knight. If B is a knight, then C’s statement ”all three of us are knaves” is false, making C a knave. Finally, since B is a knight, we can assume that their statement ”The city mayor is a knave” is true. This means the city mayor could be A or C. If A is a knight and telling the truth about not being the city mayor, then C, the knave, is the city mayor. However, A could also be a knave and lying about not being the city mayor. In conclusion, the city mayor is a knave. 5. Is Equivalence Equivalent to Equality? [15 points] Show that ( b → a ) ∧ ( c → a ) is logically equivalent to ¬ ( b ∨ c ) ∨ a . If you use a truth table, be sure to state why the table tells you what you claim. If you use logical equivalences, be sure to cite each law you use. Solution: I used a truth table to verify that these two statements are logically equivalent. I found that when all three propositions were true, both statements evaluated to true. Since proposition a was the only one on the right side of the connector, I then focused on changing a to false. When proposition a was false in each statement, the entire statement evaluated to false. This confirmed that these statements are logically equivalent. 6. Deduce, Reuse, Recycle [20 points] Given that the following statements are true : ( p ∧ r ) → q ¬ q r ∨ s q ∨ r For each of the propositions, p, q, r, and s , state its truth value and explain. If it cannot be found, briefly explain why. Solution: Proposition q is false. Since the ¬ q is true, then q must have the opposite truth value. 4

Proposition r is true. For an OR statement to evaluate to true, one of the propositions must be true. Since q is false, r must be true. Proposition p is false. If-then p → q statements only evaluate to false when p is true and q is false. Since q is false, the compound ( p ∧ r ) must also evaluate to false to make the entire statement true. Since r is true, p then has to be false. The truth value of proposition s cannot be found. Since only one proposition needs to evaluate to true in an OR statement to make the entire statement evaluate to true, and r is definitively true, s could both be true or false. 7. Preposterous Propositions [18 points] Consider the following truth table, where s , t , and w are unknown propositions. p q r s t w T T T F T F T T F T F F T F T F T T T F F F T F F T T F T T F T F F F F F F T F T T F F F F T F Use the above truth table to answer the following questions. For each unknown proposition, s , t , and w : • Find an equivalent compound proposition using p , q , and/or r . • You may use only ∧ , ∨ , ¬ , and parentheses in each of your answers. • You may use p , q , and r at most once in each of your answers. Solution: s ≡ ( p ∧ ¬ r ) ∧ q I chose this by first comparing the truth values of the compound propositions in the parenthesis, and found that each truth value aligned with s except for the fourth condi- tion, which evaluated to true instead of false. I then decided to add q to the proposition to make this change. I knew that since all but one statement evaluated to false, adding q wouldn’t change much anyways. 5

Groupwork 1 Problems 1. Caught Red-Handed! [20 points] Four friends have been identified as suspects for a recent hack. They have made the follow statements to the authorities: • Redd says that “Blu did it” • Violet says that “I did not do it” • Blu says that “Grey did it” • Grey says that “Blu lied when they said that I did it” (a) If the authorities know exactly one of the four suspects is telling the truth, who did it? (b) If the authorities know exactly one of the four suspects is lying, who did it? Solution: (a) Violet is guilty Case 1 - Redd is telling the truth • Redd says ”Blu did it” - True • Violet says ”I did not do it” - Lie • Blu says ”Grey did it” - Lie • Grey says that ”Blu lied when they said I did it” - Lie This case is not possible. These statements imply that both Blu and Violet did it. Case 2 - Violet is telling the truth • Redd says ”Blu did it” - Lie • Violet says ”I did not do it” - Truth • Blu says ”Grey did it” - Lie • Grey says that ”Blu lied when they said I did it” - Lie This case is not possible. If Blu lied, then Grey is telling the truth about Blu lying, which is not possible. Violet and Grey cannot both tell the truth. Case 3 - Blu is telling the truth 7

• Redd says ”Blu did it” - Lie • Violet says ”I did not do it” - Lie • Blu says ”Grey did it” - Truth • Grey says that ”Blu lied when they said I did it” - Lie This case is not possible. In this scenario, Violet and Grey both did it. Case 4 - Grey is telling the truth • Redd says ”Blu did it” - Lie • Violet says ”I did not do it” - Lie • Blu says ”Grey did it” - Lie • Grey says that ”Blu lied when they said I did it” - Truth This case is plausible because there are no breaks in logic. This means that Violet it guilty. (b) Blu is guilty. Case 1 - Redd is lying • Redd says ”Blu did it” - Lie • Violet says ”I did not do it” - Truth • Blu says ”Grey did it” - Truth • Grey says that ”Blu lied when they said I did it” - Truth This case is not possible. Blu and Grey’s statements contradict each other even though they are both telling the truth. Case 2 - Violet is lying • Redd says ”Blu did it” - Truth • Violet says ”I did not do it” - Lie • Blu says ”Grey did it” - Truth • Grey says that ”Blu lied when they said I did it” - Truth This case is not possible. In this scenario, Blu and Violet are guilty, and Blu and Grey’s statements are contradictory. Case 3 - Blu is lying 8