Words: 1160
EECS 203, Discrete Mathematics Winter 2012, University of Michigan, Ann Arbor Your name Date: January 16, 2012 Homework 1 Solutions Collaborators: Names of collaborators Problem 1 [Ch 1. 1 #22] Write each of these statements in the form “if p, then q” in English. a) If you get promoted, then you wash the boss’s car. b) If the winds are from the south, then there will be a spring thaw. c) If you bought the computer less than a year ago, then the warranty is good. d) If Willy cheats, then he gets caught. e) If you access the website, then you must pay a subscription fee. f) If you know the right people, then you will be elected. ) If Carol is on a boat, then she gets seasick. Problem 2 [Ch 1. 1 #32d] Construct a truth table for the compound proposition (p? q) > (p? q). p T T F F q T F T F (p ? q) T F F F p? q T T T F (p ? q) > (p ? q) T T T T Problem 3 [Ch 1. 2 #12] Are these system speci? cations consistent? “If the ? le system is not locked, then new messages will be queued. If the ? le system is not locked, then the system is functioning normally, and conversely. If new messages are not queued, then they will be sent to the message bu? er. If the ? le system is not locked, then new messages will be sent to the message bu? er.
New messages will not be sent to the message bu? er. “. This system is consistent. We use: L = “The ? le system is locked,” Q = “New messages will be queued,” N = “The system is functioning normally,” B = “New messages will be sent to the message bu? er. ” Then the given speci? cations are ¬L > Q, ¬L – N, ¬Q > B, ¬L > B, and ¬B. If we want consistency, then we had better have B false in order that ¬B be true. This ? rst conditional statement therefore is of the form F > T , which is true. Finally, the biconditional ¬L – N can be satis? ed by taking N to be false. Thus this set of speci? cations is consistent.
Note that there is just this one satisfying truth assignment. 1 Problem 4 [Ch 1. 3 #22] Show that (p > q) ? (p > r) and p > (q ? r) are logically equivalent. Steps (p > q) ? (p > r) ? (¬p ? q) ? (p > r) ? (¬p ? q) ? (¬p ? r) ? ¬p ? (q ? r) ? ¬(¬p) > (q ? r) ? p > (q ? r) Reason Implication Implication Distributive Law Implication Double Negation on p 1. 2. 3. 4. 5. Problem 5 [Ch 1. 3 #30] Show that (p ? q) ? (¬p ? r) > (q ? r) is a tautology. Note: The conjunction ? and disjunction ? operators have higher precedence than conditional > and biconditional operators. So we want to show that ((p ? ) ? (¬p ? r)) > (q ? r) is a tautology. 1) Assume the hypothesis ((p ? q) ? (¬p ? r)) is true. 2) Since we have (p ? q) AND (¬p ? r), we know that each of these must be true for their conjunction to be true. 3) Let’s suppose p is true. Then (p ? q) will always be true (no matter what the truth value of q is). But then ¬p is false, so for (¬p ? r) to be true, r must be true. 4) Because r is true, the conclusion (q ? r) will always be true. 5) Now we have shown that when the hypothesis is true, it must follow that the conclusion is true. Therefore, (p ? q) ? (¬p ? r) > (q ? r) is a tautology.
Problem 6 [Ch 1. 4 #34] Express the negation of these propositions using quanti? ers, and then express the negation in English. a) Let S(x) be “x obeys the speed limit,” where the domain of discourse is drivers. The original statement is ? x¬S(x), then negation is ? xS(x), “All drivers obey the speed limit. ” b) Let S(x) be “x is serious,” where the domain of discourse is Swedish movies. The original statement is ? xS(x)”, the negation is ? x¬S(x), “Some Swedish movies are not serious. ” c) Let S(x) be “x can keep a secret,” where the domain of discourse is people. The original statement is ¬? S(x), the negation is ? xS(x), “Some people can keep a secret. ” d) Let A(x) be “x has a good attitude,” where the domain of discourse is people in this class. The original statement is ? x¬A(x), the negation is ? xA(x), “Everyone in this class has a good attitude. ” 2 Problem 7 [Ch 1. 5 #38] Express the negations of these propositions using quanti? ers, and in English. a) In English, the negation is “Some student in this class does not like mathematics. ” With the obvious propositional function, this is ? x¬L(x). b) In English, the negation is “Every student in this class has seen a computer. With the obvious propositional function, this is ? xS(x). c) In English, the negation is “For every student in this class, there is a mathematics course that this student has not taken. ” With the obvious propositional function, this is ? x? c¬T (x, c). d) As in Exercise 15f, let P (z, y) be “Room z is in building y,”, and let Q(x, z) be “Student x has been in room z. ” Then the original statement is ? x? y? z(P (z, y) ? Q(x, z)). To form the negation, we change all the quanti? ers and put the negation on the inside, then apply De morgan’s law. The negation is therefore ? x? y? z(¬P (z, y) ? Q(x, z)), which is also equivalent to ? x? y? z(P (z, y) > ¬Q(x, z)). In English, this could be read, “For every student there is a building such that for every room in that building, the student has not been in that room. ” Problem 8 Is the following expression logically valid? If yes, give a proof; otherwise give an example that shows it is false. ?x? y(P(x) > P(y)) > ? y? x(P(x) > P(y)) This expression is logically valid because the conclusion of the premise, ? y? x(P (x) > P (y)), is a tautology. The meaning of ? y? x(P (x) > P (y)) is there exists some y for any x chosen, such that P (x) > P (y).
In other words, no matter what x we choose, there is a y such that if P (x) is true, then P (y) must follow. To prove ? y? x(P (x) > P (y)) is a tautology, we consider two cases: 1) If ? xP (x) Since we know that there’s a y which works for every x, we can conclude that P (y) is true. Then we have (T > T) which is T. 2) If ¬? xP (x) This means for every x, P (x) is false, so we cannot conclude if P (y) is true or not. So we have (F > T) which is T. Now that we’ve shown that ? y? x(P (x) > P (y)) is always true, we know that ? x? y(P (x) > P (y)) > ? y? x(P (x) > P (y)) will always be true. 3