CRN 12107: HW 1 - Revision history

HelmutKnaust at 21:18, 19 January 2017

2017-01-19T21:18:26Z

HelmutKnaust at 12:51, 4 September 2013

2013-09-04T12:51:34Z

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

2013-09-04T12:50:07Z

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

New page

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

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

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

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

@@ Line 20: / Line 20: @@
 #Write the statement above using quantifier(s) and predicate(s).
 #Negate the sentence using quantifier(s) and predicate(s).
-#Write the negation$^1$ in the form of an English sentence.
+#Write the negation in the form of an English sentence. (Don't just write ''It is not true that...'')