24178: HW 1
From Classes
Revision as of 15:27, 24 January 2017 by HelmutKnaust (Talk | contribs)
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.
- Use a truth table to show that $A\Rightarrow B$ is equivalent to $\neg(A \wedge \neg B)$.
- Show that $A\vee B$ can be written using only the connectives $\neg$ and $\wedge$.
- 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 $\mbox{NOR}$-connectives.
Problem 3. In each case, give an example, or explain why such an example cannot exist:
- 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?
- 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
- $(\exists ! x)A(x)\Longrightarrow(\exists x) A(x)$.
- $(\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.
- Write the statement above using quantifier(s) and predicate(s).
- Negate the sentence using quantifier(s) and predicate(s).
- Write the negation in the form of an English sentence. (Don't just write It is not true that...)