CMSC 27100 — Problem Set 1

Instructions

This problem set is due on Wednesday October 9, 2019 at 23:59. Solutions to Problems should be submitted on Gradescope and will be graded. 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. Using the inference rules in Definitions 1.7 and 1.8, show that
    1. $p \rightarrow q \vdash \neg q \rightarrow \neg p$ without using the Contrapositive rule from Definition 1.8
    2. $p \rightarrow (q \vee r) \vdash (p \wedge \neg q) \rightarrow r$
  2. 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.
  3. Recall that we can define ordered pairs $(x,y)$ using sets by $\{\{x\},\{x,y\}\}$. Using this definition, prove that $(a,b) = (c,d)$ if and only if $a = c$ and $b = d$.

Exercises

  1. Rosen 1.1 Exercises 31 except e
  2. Rosen 1.5 Exercises 31, 33
  3. Rosen Chapter 1 Supplementary Exercises 21
  4. Problem 1, but using only the rules from Definition 1.7.
  5. 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$
    Express $p \leftrightarrow q$ using standard logical connectives.
    1. Show that $\exists x (P(x) \vee Q(x))$ and $\exists x P(x) \vee \exists x Q(x)$ are logically equivalent.
    2. Show that $\forall x (P(x) \vee Q(x))$ and $\forall x P(x) \vee \forall x Q(x)$ are not logically equivalent.
  7. Rosen 2.1 Exercises 25