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 com￾puter 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 self­proclaimed “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)))