HelmutKnaust at 20:33, 24 January 2017

2017-01-24T20:33:57Z

HelmutKnaust: Created page with "'''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 ho..."

2017-01-24T20:27:20Z

Created page with "'''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 ho..."

New page

'''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...'')

@@ Line 4: / Line 4: @@
 #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.
+#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
@@ Line 16: / Line 16: @@
 '''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)\Rightarrow(\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)$.

24178: HW 1 - Revision history

HelmutKnaust at 20:33, 24 January 2017

HelmutKnaust: Created page with "'''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 ho..."