CRN 12107: HW 1

Problem 1. Exercise 1.2.12(b)

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 \Longleftrightarrow \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 the $\mbox{NOR}$-connective.

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.

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$^1$ in the form of an English sentence.