MPCS 50103 — Problem Set 1

Instructions

This problem set is due on Wednesday January 15, 2020 at 17:00. Solutions to Problems should be submitted on Gradescope and will be graded. Each problem is worth 10 marks in total. Solutions to Exercises will not be graded and you should not submit them, although we will be happy to discuss them with you.

Problems

  1. Sometimes the logical connective $\leftrightarrow$ is used. This is called the biconditional and is read "if and only if". It has the following truth table.
    $\varphi$ $\psi$ $\quad$ $\varphi \leftrightarrow \psi$
    $T$ $T$ $T$
    $T$ $F$ $F$
    $F$ $T$ $F$
    $F$ $F$ $T$
    Find a formula equivalent to $p \leftrightarrow q$ that uses only the standard logical connectives ($\wedge,\vee,\neg,\rightarrow$) and prove that it is logically equivalent by providing the truth table.
  2. Express the negation of each the following statements so that all negation symbols immediately precede predicates.
    1. $P(x,y) \wedge Q(z)$
    2. $\forall x \forall y P(x,y) \vee \forall x \exists y Q(x,y)$
    3. $\forall x (P(x) \rightarrow \neg \exists y Q(x,y))$
  3. Consider the following proposition:
    For all integers $n$, if $3n+2$ is even, then $n$ is even.
    1. Prove this by contraposition.
    2. Prove this by contradiction.

Exercises

  1. Rosen 1.1 Exercises 31 except e
  2. Rosen 1.5 Exercises 31, 33
  3. Rosen Chapter 1 Supplementary Exercises 21
  4. Recall that $\exists x P(x)$ says that there is some object in our domain that satisfies the predicate $P$. Sometimes, we want to say something stronger: that such an object is unique and that there is exactly one object in the domain that satisfies $P$. We can define a new quantifier $\exists!$ for this purpose, to say $\exists! x P(x)$. However, this is non-standard and not really necessary, since we can already express the idea of uniqueness with the language we already have.
    Express $\exists!x P(x)$ using standard logical connectives, quantifiers, and equality (=). Informally justify your answer.

Reflection

Once in a while, there will be a reflection section attached to a problem set. These are meant to give you an opportunity to reflect on your relationship with the course and the things you're learning. I will be reading and responding to your submissions, so this will also allow us to establish a dialogue about your learning in this course.

Completion of this part is optional but is worth an extra 10 marks in total. These will be loosely graded on completion/thoughtfulness and not "correctness" (i.e. what you think I want you to say); you should aim for about a paragraph or two of "thoughtfulness". Please start a new page with your responses when completing this section, separately from the problem set.

  1. What is your background with mathematics? Which mathematical or computer science courses have you previously taken?
  2. What are your expectations for this class? What do you hope to take away from it? (Please feel free to be honest)
  3. If you had to set a few concrete goals for this course, what would they be?
  4. What are your thoughts and feelings about math?
  5. Is there anything else you would like me to know at this point?