Upload your solutions here.

• Read the course syllabus in its entirety. If you have questions, ask the instructor.
• Read the course FAQ in its entirety. If you have questions, ask the instructor.

Part A

1. Prove one of the distributive laws for ∨ and ∧ for logical statements: if P, Q and R are statements, then
   • (P∨(Q∧R))⇔((P∨Q)∧(P∨R))
   • (P∧(Q∨R))⇔((P∧Q)∨(P∧R))
   [N.B.: The statement of this problem is a slightly less formal rendering of the more precise mathematical content you’re asked to prove. For example, if you choose to prove the first option, you’re really showing the following: for all statements P,Q, and R, the statement (P∨(Q∧R))⇔((P∨Q)∧(P∨R)) is true. The same is true for other problems on this assignment.]
2. Prove one of the Demorgan’s laws for logical statements: if P, Q and R are statements, then
   • ¬(P∨Q)⇔(¬P∧¬Q)
   • ¬(P∧Q)⇔(¬P∨¬Q)
3. Suppose that P,Q and R are statements. Prove that the statement “P⇒(Q∨R)” is equivalent to the statement “(P∧¬Q)⇒R”.[NB: we’ll frequently encounter results formulated as in the first statement. They sound like “Suppose BLAH. Prove THIS or THAT.” This homework problem shows us that we can start our proofs of by saying “Suppose that BLAH and NOT THIS are true. We will prove THAT is true.”]

Part B

4. Is the ∧ connective associative? That is, if P, Q and R are statements, are (P∧Q)∧R and P∧(Q∧R) logically equivalent? (Whatever your assertion, you should — of course — support it with a rigorous proof.)[NB: you won’t be asked to prove it here, but moving forward you can use the fact that the ∨ and ⇔ connectives are associative. It turns out that ⇒ is not associative!]
5. (⋆) Though the connectives ⇒ and ⇔ are extremely useful, it turns out that they are redundant: both can be expressed in terms of ∨,∧ and ¬.
   • Prove that if P and Q are any statements, then (P⇒Q)⇔¬P∨Q
   • Suppose that P and Q are statements. Reexpress P⇔Q in terms of statements involving P and Q, the connectives ∨ and ∧, and the modifier ¬. Prove your assertion, and be careful with parentheses!
   (Note: your answer to the second part will begin by stating your intended assertion and then verifying it. A formal proof does not require you to exhibit where your assertion comes from.)
6. Prove that ⇒ is transitive: if P,Q, and R are statements, then((P⇒Q)∧(Q⇒R))⇒(P⇒R).[N.B.: It is a fact (that you don’t have to prove, but you may use in future assignments) that ⇔ is also transitive.]

Here are some other problems you ought to complete, but you won’t submit them as part of the assignment.

• You have spent an outsized portion of your mathematical life thinking about functions whose domain and codomain are some subsets of R. Often these functions have been continuous. Sometimes in high school, students learn that a function is continuous if its graph can be drawn without picking up the pen while being drawn. The technical definition is more specific, and relies on what it means for f to be continuous at some point x0. The spiritual content of continuity of a function f:R→R at x0 is as follows: for any specified tolerance, there is some notion of “close enough” so that if x is “close enough” to x0, then the distance between f(x0) and f(x) is smaller than the specified tolerance. Write this as a quantified statement, and then write out its negation as a quantified statement. Your statements should take the form of quantified variables followed by a predicate, where your predicate should only include the connectives ∧ and ∨, together with the modifier ¬ (and any necessary parentheses).
• In number theory, Goldbach’s conjecture states that every positive even number greater than 2 can be written as the sum of two prime numbers.
  1. Write Goldbach’s conjecture in the form of a quantified statement. (You might choose to use 2Z to denote the set of even numbers, and P to denote the set of primes.)
  2. Many mathematicians believe that Goldbach’s conjecture is true. What would you need to do in order to prove that Goldbach’s conjecture is false?