6.042/18.] Mathematics for Computer Science February 1, 2005 Srini devadas and Eric Lehman Problem set 1 Solutions Due: Monday February 7 at 9 PM Problem 1. The connectives A(and), V(or), and =(implies)come often not only in com uter programs, but also everyday speech. But devices that compute the nand operation are preferable in computer chip designs. Here is the truth table for nand P nand Q PTTFF F F T TTT For each of the following expressions, find an equivalent expression using only nand and (not (a)A∧B Solution. (A nand B) (b)A∨B Solution (A)nand (B) (c)A Solution. A nand (B) Problem 2. A self-proclaimed"great logician"has invented a new quantifier, on par with a(there exists")and v( for all"). The new quantifier is symbolized by U and read"there exists a unique". The proposition Ua P() is true iff there is exactly one r for which P(z)is true. The logician has noted, There used to be two quantifiers, but now there are three! I have extended the whole field of mathematics by 50%! (a) Write a proposition equivalent to Ur P(ar) using only the 3 quantifier, =, and logical connectives Solution .c(P(r)A-y((a=y)A P(y))
6.042/18.062J Mathematics for Computer Science February 1, 2005 Srini Devadas and Eric Lehman Problem Set 1 Solutions Due: Monday, February 7 at 9 PM Problem 1. The connectives ∧ (and), ∨ (or), and ⇒ (implies) come often not only in computer programs, but also everyday speech. But devices that compute the nand operation are preferable in computer chip designs. Here is the truth table for nand: P Q T T F T F T F T T F F T P nand Q For each of the following expressions, find an equivalent expression using only nand and ¬ (not). (a) A ∧ B Solution. ¬(A nand B) (b) A ∨ B Solution. (¬A) nand (¬B) (c) A B ⇒ Solution. A nand (¬B) Problem 2. A selfproclaimed “great logician” has invented a new quantifier, on par with ∃ (“there exists”) and ∀ (“for all”). The new quantifier is symbolized by U and read “there exists a unique”. The proposition Ux P(x) is true iff there is exactly one x for which P(x) is true. The logician has noted, “There used to be two quantifiers, but now there are three! I have extended the whole field of mathematics by 50%!” (a) Write a proposition equivalent to Ux P(x) using only the ∃ quantifier, =, and logical connectives. Solution. ∃x (P(x) ∧ ¬(∃y (¬(x = y) ∧ P(y)))
Problem set 1 (b)Write a proposition equivalent to Ur P(r) using only the V quantifier, = and logical connectives Solution -Va(p(ar)v-vy(r=yvP(y)) Problem 3. A media tycoon has an idea for an all-news television network called lnn: The Logic News Network. Each segment will begin with the definition of some relevant sets and predicates. The days happenings can then be communicated concisely in logic notation. For example, a broadcast might begin as follows THIS IS LNN. Let S be the set Bill, Monica, Ken, Linda, Betty. Let D(ar)be a predicate that is true if a is deceitful. Let L(a, y)be a predicate that is true if r likes y. Let G(a, y)be a predicate that is true if r gave gifts to y. omplete the broadcast by translating the following statements into logic notation (a) If neither Monica nor Linda is deceitful, then Bill and Monica like each other Solution ((D(Monica)V D(Linda)))=>(L(Bill, Monica)A L(Monica, Bill)) (b) Everyone except for Ken likes Betty, and no one except Linda likes Ken Solution vr∈S(x=Ken∧-L(r, Betty)y(x≠Ken∧L(x,Bety)∧ vx∈S(x= Linda∧L(x,Ken)v(x≠ Linda∧=L(x,Ken) (c) If Ken is not deceitful, then Bill gave gifts to Monica, and Monica gave gifts to Solution D(Ken)→(G( Bill. monica)Ax∈SG( Monica,x) (d) Everyone likes someone and dislikes someone else Solution x∈S∈Sz∈S(y≠2)∧L(x,y)∧=L(x,x) The remaining problems will be graded primarily on the clarity of can't figure out the right idea, we'll give it to you-just ask your 1A, c your proofs- not on whether you have the right idea. In fact, if yo
2 Problem Set 1 (b) Write a proposition equivalent to Ux P(x) using only the ∀ quantifier, =, and logical connectives. Solution. ¬∀x (¬P(x) ∨ ¬∀y (x = y ∨ ¬P(y))) Problem 3. A media tycoon has an idea for an allnews television network called LNN: The Logic News Network. Each segment will begin with the definition of some relevant sets and predicates. The day’s happenings can then be communicated concisely in logic notation. For example, a broadcast might begin as follows: “THIS IS LNN. Let S be the set {Bill, Monica, Ken, Linda, Betty}. Let D(x) be a predicate that is true if x is deceitful. Let L(x, y) be a predicate that is true if x likes y. Let G(x, y) be a predicate that is true if x gave gifts to y.” Complete the broadcast by translating the following statements into logic notation. (a) If neither Monica nor Linda is deceitful, then Bill and Monica like each other. Solution. (¬(D(Monica) ∨ D(Linda))) ⇒ (L(Bill, Monica) ∧ L(Monica, Bill)) (b) Everyone except for Ken likes Betty, and no one except Linda likes Ken. Solution. ∀x ∈ S (x = Ken ∧ ¬L(x, Betty)) ∨ (x = � Ken ∧ L(x, Betty)) ∧ ∀x ∈ S (x = Linda ∧ L(x, Ken)) ∨ (x = � Linda ∧ ¬L(x, Ken)) (c) If Ken is not deceitful, then Bill gave gifts to Monica, and Monica gave gifts to someone. Solution. ¬D(Ken) ⇒ (G(Bill, Monica) ∧ ∃x ∈ S G(Monica, x)) (d) Everyone likes someone and dislikes someone else. Solution. ∀x ∈ S ∃y ∈ S ∃z ∈ S (y �= z) ∧ L(x, y) ∧ ¬L(x, z) The remaining problems will be graded primarily on the clarity of your proofs— not on whether you have the right idea. In fact, if you can’t figure out the right idea, we’ll give it to you– just ask your TA!
Problem Set 1 Problem 4. Let n be a postive integer. Prove that log2 n is rational if and only if n is a power of 2. Assume any basic facts about divisibility that you need; just state your assumptions explicitly Solution. Assumption: If n is a power of 2, then n is a power of 2 Proof. We prove that if n is a power of 2, then log2 n is rational and vice-versa Oe first, we prove that if n is a power of 2, then log n is rational. Assume that n is a power of 2. Then n=2 for some integer k>0. Thus, log2 n= log2 2=k, which is a rationa number Next, we prove that if log2 n is rational, then n is a power of 2. Assume that log2n ational. That means there exist integers a and b such that We can rewrite this equation as follows ( Take 2 to power of each side (Take the b-th power of each side. Thus, n is a power of 2. By our assumption n is a power of 2 Problem 5. A triangle is a set of three people such that either every pair has shaken hands or no pair has shaken hands. Prove that among every six people there is a triangle. Su gestion: Initially, break the problem into two cases: 1. There exist at least three people who shook hands with person X 2. There exist at least three people didnt shake hands with X (Why must at least one of these conditions hold?) Solution Proof. We use case analysis. Let X denote one of the six people. There are two possibili- 1. There exist three people who shook hands with person X. Now there are two fur ther possibilities (a) Among these three, some pair shook hands. Then these two and X form a triangle (b) Among these three, no pair shook hands. Then these three form a triangle
Problem Set 1 3 Problem 4. Let n be a postive integer. Prove that log2 n is rational if and only if n is a power of 2. Assume any basic facts about divisibility that you need; just state your assumptions explicitly. Solution. Assumption: If nb is a power of 2, then n is a power of 2. Proof. We prove that if n is a power of 2, then log2 n is rational and viceversa. First, we prove that if n is a power of 2, then log2 n is rational. Assume that n is a power of 2. Then n = 2k for some integer k ≥ 0. Thus, log2 n = log2 2k = k, which is a rational number. Next, we prove that if log2 n is rational, then n is a power of 2. Assume that log2 n is rational. That means there exist integers a and b such that: a log2 n = b We can rewrite this equation as follows: n = 2a/b (Take 2 to power of each side.) n b = 2a (Take the bth power of each side.) Thus, nb is a power of 2. By our assumption, n is a power of 2. Problem 5. A triangle is a set of three people such that either every pair has shaken hands or no pair has shaken hands. Prove that among every six people there is a triangle. Suggestion: Initially, break the problem into two cases: 1. There exist at least three people who shook hands with person X. 2. There exist at least three people didn’t shake hands with X (Why must at least one of these conditions hold?) Solution. Proof. We use case analysis. Let X denote one of the six people. There are two possibilities: 1. There exist three people who shook hands with person X. Now there are two further possibilities: (a) Among these three, some pair shook hands. Then these two and X form a triangle. (b) Among these three, no pair shook hands. Then these three form a triangle
Problem set 1 2. Otherwise, at most two people shook hands with person X. Thus, there exist three people who didn' t shake hands with X. Again, there are two further possibilities (a)Among these three, every pair shook hands. Then these three form a triangle (b) Among these three, some pair didn' t shake hands. Then these two and X for a triangle roblem 6. Let a and y be nonnegative real numbers. The arithmetic mean of a and y is defined to be(ar +y)/ 2, and the geometric mean is defined to be vay. Prove that the arithmetic mean is equal to the geometric mean if and only if r Solution Proof. We construct a chain of if-and-only-if implications. The arithmetic mean is equal to the geometric mean if and only if r+y=√ x+y=2√y (x+y)2 -+2 cy+y=4.ry x2-2xy+y2=0 (x-y)2=0 y Problem 7. Use case analysis to prove that all integral solutions to the equation subject to these constraints are in this table 3412 3530 4312 These equations reveal something fundamental about the geometry of our three-dimensional world: we'll revisit them in about three weeks
4 Problem Set 1 2. Otherwise, at most two people shook hands with person X. Thus, there exist three people who didn’t shake hands with X. Again, there are two further possibilities: (a) Among these three, every pair shook hands. Then these three form a triangle. (b) Among these three, some pair didn’t shake hands. Then these two and X for a triangle. Problem 6. Let x and y be nonnegative real numbers. The arithmetic mean of x and y is defined to be (x + y)/2, and the geometric mean is defined to be √xy. Prove that the arithmetic mean is equal to the geometric mean if and only if x = y. Solution. Proof. We construct a chain of ifandonlyif implications. The arithmetic mean is equal to the geometric mean if and only if: x + y = √xy x + y = 2√xy 2 ⇔ (x + y) 2 ⇔ = 4xy 2 x 2 ⇔ + 2xy + y = 4xy ⇔ 2 x − 2xy + y 2 = 0 ⇔ (x − y) 2 = 0 ⇔ x − y = 0 ⇔ x = y Problem 7. Use case analysis to prove that all integral solutions to the equation 1 1 1 1 + = + m n e 2 subject to these constraints m ≥ 3 n ≥ 3 e > 0 are in this table: m n e 3 3 6 3 4 12 3 5 30 4 3 12 5 3 30 These equations reveal something fundamental about the geometry of ourthreedimensional world; we’ll revisit them in about three weeks
Problem Set 1 Solution Proof. We use case analysis. Since m 23, one of four cases must hold 1. m=3. There are now four subcase (a)n=3. Rewriting the equation in the form and subtituting in m= n= 3 implies that e= 6, which is the first solution (b)n=4. Substituting the values of m and n into the equation show that e= 12, which is the second solution (c)n=5. Substituting into the equation shows that e 30, which is the third solution (d)n≥6. This implies: 11 Thus, the left side of the equation is strictly less than the right for all e >0,so there are no solutions in this case 2. m= 4. There are two subcases (a)n=3. Subsituting gives e= 12, which is the fourth solution (b)n≥4. This implie 1+10,so there are no solutions in this case 3. m=5. There are two subcases (a)n=3. Subsituting gives e= 30, which is the fifth solution (b)n≥4. This implies: 11111 Again, the equation can not hold, so there are no solutions in this cas 4.m≥6. This implies: 1 1111 m+n=6+3=2 Once more the equation can not hold, so there are no solutions in this case
Problem Set 1 5 Solution. Proof. We use case analysis. Since m ≥ 3, one of four cases must hold: 1. m = 3. There are now four subcases: (a) n = 3. Rewriting the equation in the form 1 e = 1 + 1 nm − 1 2 and subtituting in m = n = 3 implies that e = 6, which is the first solution. (b) n = 4. Substituting the values of m and n into the equation show that e = 12, which is the second solution. (c) n = 5. Substituting into the equation shows that e = 30, which is the third solution. (d) n ≥ 6. This implies: 1 1 1 1 1 m + n ≤ 3 + 6 = 2 Thus, the left side of the equation is strictly less than the right for all e > 0, so there are no solutions in this case. 2. m = 4. There are two subcases: (a) n = 3. Subsituting gives e = 12, which is the fourth solution. (b) n ≥ 4. This implies: 1 1 1 1 1 + = m + n ≤ 4 4 2 Again, the left side of the equation is strictly less than the right for all e > 0, so there are no solutions in this case. 3. m = 5. There are two subcases: (a) n = 3. Subsituting gives e = 30, which is the fifth solution. (b) n ≥ 4. This implies: 1 1 1 1 1 + < m + n ≤ 5 4 2 Again, the equation can not hold, so there are no solutions in this case. 4. m ≥ 6. This implies: 1 1 1 1 1 + = m + n ≤ 6 3 2 Once more, the equation can not hold, so there are no solutions in this case
