6.042/18.] Mathematics for Computer Science March 9. 2005 Srini devadas and Eric Lehman Quiz 1 YOUR NAME Circle the name of your recitation instructor Ishan Christos Grant You may use one 8.5 11"sheet with notes in you own handwriting on both sides but no other sources of information Calculators are not allowed You may assume all results from lecture, the notes, problem sets, and recitation Write your solutions in the space provided. If you need more space, write on the back of the sheet containing the problem Be neat and write legibly. You will be graded not only on the correctness of your answers, but also on the clarity with which you express them The exam ends at 9: 30 PM · GOOD LUCK! Problem Points Grade Grader 20 123456 15 20 15 15 15 匚 Total100
6.042/18.062J Mathematics for Computer Science March 9, 2005 Srini Devadas and Eric Lehman Quiz 1 YOUR NAME: Circle the name of your recitation instructor: Ishan Christos Grant • You may use one 8.5 × 11” sheet with notes in you own handwriting on both sides, but no other sources of information. • Calculators are not allowed. • You may assume all results from lecture, the notes, problem sets, and recitation. • Write your solutions in the space provided. If you need more space, write on the back of the sheet containing the problem. • Be neat and write legibly. You will be graded not only on the correctness of your answers, but also on the clarity with which you express them. • The exam ends at 9:30 PM. • GOOD LUCK! Problem Points Grade Grader 1 20 2 15 3 20 4 15 5 15 6 15 Total 100
Problem 1.20 point (a)Consider the proposition: R=“ For all x∈S,P(x) implies Q(x) For each statement below: · If r implies that statement, then circle→. If R is implied by that statement, then circle Thus, you might circle zero, one or two arrows next to each statement. Circle only implications that hold for all sets S and all predicates P and Q) For all c E s, Q(ar) implies P(a) For all x E S, - Q()implies P(a) or all T E S, P(r)and Q(a) There does not exist an E S such that not(P(ar) implies Q(a)) fl
Quiz 1 2 Problem 1. [20 points] (a) Consider the proposition: R = “For all x ∈ S, P(x) implies Q(x).” For each statement below: • If R implies that statement, then circle ⇒. • If R is implied by that statement, then circle ⇐. Thus, you might circle zero, one, or two arrows next to each statement. (Circle only implications that hold for all sets S and all predicates P and Q.) ⇒ ⇐ For all x ∈ S, Q(x) implies P(x). ⇒ ⇐ For all x ∈ S, ¬Q(x) implies ¬P(x). ⇒ ⇐ For all x ∈ S, P(x) and Q(x). ⇒ ⇐ There does not exist an x ∈ S such that not (P(x) implies Q(x)). ⇒ ⇐ Pigs fly
(b) Let S be the set of all people, and let M(a, y) be the predicate, r is the mother of y". Translate this proposition into a clear English sentence involving no variables vx(=y(M(x,y)∧M(y,x) There are no two people such that each is the mother of the other. "Or more simply, "No one is their own maternal grandmother (c) Translate the following English sentence into logic notation using the set S and redicatem defined above Everyone has a mother. vx彐yM(y,x)
Quiz 1 3 (b) Let S be the set of all people, and let M(x, y) be the predicate, “x is the mother of y”. Translate this proposition into a clear English sentence involving no variables. ∀x (¬∃y (M(x, y) ∧ M(y, x))) “There are no two people such that each is the mother of the other.” Or, more simply, “No one is their own maternal grandmother.” (c) Translate the following English sentence into logic notation using the set S and predicate M defined above. “Everyone has a mother.” ∀x ∃y M(y, x)
Problem 2.[15 points] Complete this proof that n cents of postage can be formed using 3 and 5 cent stamps for all n 28 Proof. We use strong induction. (a)Let P(n)be the proposition that Solution. n cents of postage can be formed using 3 and 5 cent stamps (b) Base cases Solution. P(8), P(9), and P(10)are all true, since 9=3+3+3 (c) Inductive step Solution For n 10, we assume P( 8),..., P(n)and prove P(n+1). In particular, y assumption P(n-2), we can form n-2 cents of postage. Adding a 3-cent stamp gives n+1 cents of postage, so P(n+1) is true o P(n)is true for all n>8 by the principle of strong induction
Quiz 1 4 Problem 2. [15 points] Complete this proof that n cents of postage can be formed using 3 and 5 cent stamps for all n ≥ 8. Proof. We use strong induction. (a) Let P(n) be the proposition that Solution. n cents of postage can be formed using 3 and 5 cent stamps. (b) Base cases. Solution. P(8), P(9), and P(10) are all true, since: 8 = 5 + 3 9 = 3 + 3 + 3 10 = 5 + 5 (c) Inductive step. Solution. For n ≥ 10, we assume P(8), . . . , P(n) and prove P(n + 1). In particular, by assumption P(n − 2), we can form n − 2 cents of postage. Adding a 3-cent stamp gives n + 1 cents of postage, so P(n + 1) is true. So P(n) is true for all n ≥ 8 by the principle of strong induction
Problem 3. [20 points] Here is how to tweak an undirected grap 1. Select distinct vertices a, b, c, and d such that the graph contains edges a-b and c-d and none of the edges a-c, a-d, b-c, or b- 2. Delete edge c-d and add edges a-c and a-d ●C (a) In the box on the right, draw a graph that can be obtained by tweaking the graph on the left 6 2 2 3 4
Quiz 1 5 Problem 3. [20 points] Here is how to tweak an undirected graph: 1. Select distinct vertices a, b, c, and d such that the graph contains edges a—b and c—d and none of the edges a—c, a—d, b—c, or b—d. ✇ ✇ ✇ a ✇ b c d 2. Delete edge c—d and add edges a—c and a—d: ❅ ❅ ❅ ❅ ❅ ❅ ✇ ❅❅ ✇ ✇ a ✇ b c d (a) In the box on the right, draw a graph that can be obtained by tweaking the graph on the left. ❍❍ ❍ ❍❍ ❍❍ ✟✟✟ ✟✟✟✟ ✟✟ ✟ ✟✟ ✟✟ ❍❍❍❍❍❍❍ ✇ ✇ ✇ ✇ ✇ ✇ 1 2 3 4 5 6 → ❍❍❍❍❍❍❍❍❍❍❍❍❍ ❍❍ ❍ ❍❍ ❍❍ ✟✟✟ ✟✟✟✟ ✟✟ ✟ ✟✟ ✟✟ ❍❍❍❍❍❍❍ ✇ ✇ ✇ ✇ ✇ ✇ 1 2 3 4 5 6