21495: HW 1

Problem 1. Show that the following two statements are equivalent: $(P\wedge Q)\Rightarrow R$ and $(P\wedge \neg R)\Rightarrow \neg Q$.

Problem 2. You have seen how to generate compound statements using the four connectives $\neg, \vee, \wedge$ and $\Rightarrow$. This problem addresses the question whether all four connectives are necessary.

1. Use a truth table to show that $A\Rightarrow B$ is equivalent to $\neg(A \wedge \neg B)$.
2. Show that $A\vee B$ can be written using only the connectives $\neg$ and $\wedge$.
3. Thus the two connectives $\neg$ and $\wedge$ suffice to generate all compound statements. It is possible to further reduce to only one connective, albeit a different one: Let us define the new connective $\mbox{NOR}$ by setting $A \mbox{ NOR } B \Leftrightarrow \neg(A\vee B).$ Show that the four compound statements $\neg A,\ A\vee B,\ A\wedge B$ and $A\Rightarrow B$ can be written using only $\mbox{NOR}$-connectives.

Problem 3. In each case, give an example, or explain why such an example cannot exist:

1. Is there a predicate $A(x,y)$ such that the statement $\forall x\ \exists y:\ A(x,y)$ is true, while the statement $\exists y\ \forall x:\ A(x,y)$ is false?
2. Is there a predicate $A(x,y)$ such that the statement $\exists y\ \forall x:\ A(x,y)$ is true, while the statement $\forall x\ \exists y:\ A(x,y)$ is false?

Problem 4. Prove Theorem 1.3.2: If $A(x)$ is an open statement with variable $x$, then

1. $(\exists ! x)A(x)\Rightarrow(\exists x) A(x)$.
2. $(\exists ! x) A(x)$ is equivalent to $(\exists x)A(x)\wedge(\forall y)(\forall z)(A(y)\wedge A(z)\Rightarrow y=z)$.

Problem 5. A clothing store advertises: For every customer we have a rack of clothes that fit.

1. Write the statement above using quantifier(s) and predicate(s).
2. Negate the sentence using quantifier(s) and predicate(s).
3. Write the negation in the form of an English sentence. (Don't just write It is not true that...)