\documentclass[11pt]{article}
\def\showsol{1} %make this 1 to show solutions
\def\showhints{0} %make this 1 to show solutions

%%%%%%%%%%%%%%%% First make changes here
\def\ugpnum{1}
\def\ugptopic{Sets, Function, Logic}



\input{starter}




\begin{document}
	\begin{center}
		{\bf \Large \Coursename: Ungraded Practice Problems  \ugpnum}\\ 
		Due: Not for Submission \\
		Topics: \ugptopic
	\end{center}
	\hrulefill

\section{Sets}
\begin{exercise} \Coffeecup
	
		\noindent
		The following sets are described in set builder notation.
		Describe each of them in roster notation, instead.
		
		\begin{enumerate}
			\item
			$\{z^2 \mid z \in \ZZ \mbox{ and } 6 < z^3 < 160 \}$.
			
			\solution{$\{4, 9, 16, 25\}$}
			
			\item
			$\{A \mid A \subseteq \{a, c, e\} \mbox{ and } |A| \neq 2 \}$
			
			\solution{$\{\emptyset, \{a\}, \{c\}, \{e\}, \{a,c,e\} \}$}
			
			\item
			$\{r \mid r \in \RR \mbox{ and } r = r^2 \}$

			\solution{$\{0, 1\}$}
			
			\item
			$\{n \mid n \in \NN \mbox{ and } n > n^2 \}$
			
			\solution{$\emptyset$}
						
			\item
			$\{p \in \ZZ \mid \mbox{$0 < p < 50$ and $p$ does not have 3 as a digit } \}$
			
		\solution{ $\{1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 21,$\\ $22, 24, 25, 26, 27, 28, 29, $
			$40, 41, 42, 44, 45, 46, 47, 48, 49\}$}
			
			\item
			$\{x \mid \mbox{$x$ is a letter in the word \emph{accommodate}}\}$
			
	\solution{ $\{a, c, o, m, d, t, e \}$}
			
			\item
			$\{S \subseteq \{2, 4, 6, 8\} \mid S \cap \{2,4\} \neq \emptyset \mbox{ and $|S|$ is even} \}$
			
			\solution{$\{\{2, 4\}, \{2, 6\}, \{2, 8\}, \{4, 6\}, \{4, 8\}, \{2,4,6,8\}\}$}
			
		\end{enumerate}
\end{exercise}

\vspace{2ex}

\begin{exercise}[Set Operations] \Coffeecup~
	
	\noindent
 Let $A$, $B$, $C$ be sets.  Express the following sets using set operations on $A$, $B$, and $C$.
	For example, if I ask you to express ``the set of all elements that are common to $A$ and $B$,''' 
	your answer should be ``$A \cap B$,'' and not ``$\{x : (x \in A) ~\textrm{and}~(x \in B)\}$.''
	
	\begin{enumerate}
		\item
		Set of all elements that are in at least two of the three sets $A, B, C$.
		
		\solution{
		$(A \cap B) \cup (A \cap C) \cup (B \cap C)$.
	}
	
		\item
		Set of all elements that are in \emph{exactly} one set $A$ or $B$ or $C$.
		
		\solution{
		$(A \setminus (B\cup C)) \cup (B \setminus (C\cup A)) \cup (C \setminus (A\cup B))$}
	\end{enumerate}
\end{exercise}

\vspace{2ex}

\begin{exercise}[Set builder Notation] \Coffeecup ~

\noindent
If $S$, $T$ are arbitrary sets of integers, express the following sets as elegantly as possible using the set builder notation.
\begin{enumerate}
	\item
	The set of all pairs where the first element of the pair is an element of $S$
	and the second element of the pair is a subset of $S$ that does not contain the first element of the pair.
	
\solution{ $\{(a, A) : a\in S, A \subseteq S, a \not\in A\}$}
	
	\item
	The set of all subsets of $S$ that are disjoint from $T$.
	
\solution{ $\{A : A\subseteq S, A \cap T = \emptyset\}$}
	\item
	The set of all numbers that can be expressed as the difference of two numbers in $S$.
	
	\solution{ $\{x-y :  x,y \in S\}$}
\end{enumerate}
\end{exercise}

\vspace{2ex}

\begin{exercise}[Applying Baby Inclusion-Exclusion] \Coffeecup \Coffeecup ~
	
	\noindent
	In the city of Klow, $80\%$ of the population speak Syldavian while $70\%$ of the people speak Bordurian.
	Furthermore, $60\%$ of the population speak both languages.
	If there are $10$ residents who speak neither language, what is the population of Klow?
\end{exercise}

\solution{
Let $U$ be the set of people living in Klow. Let $A\subseteq U$ be the set of people who can speak Syldavian.
Let $B\subseteq U$ be the set of people who can speak Bordurian. $A\cap B$ is the set of people who speak both.
And $U\setminus (A\cup B)$ is the set of people who speak neither.

If we let $x$ be the size of $|U|$, that is, the population of Klow, the data tells us
\begin{itemize}[noitemsep]
	\item $|A| = 0.8x$
	\item $|B| = 0.7x$
	\item $|A\cap B| = 0.3x$
	\item $|U| - |A\cup B| = 10$.
\end{itemize}

Baby Inclusion Exclusion tells us $|A\cup B| = |A| + |B| - |A\cap B| = 0.8x + 0.7x - 0.6x = 0.9x$. Therefore,
$|U| - |A\cup B| = x - 0.9x = 0.1x$. Since $|U| - |A\cup B| = 10$, we get $x = 100$. There are $100$ residents in Klow.

}

\section{Functions}

\begin{exercise}[Proving something is injective]\Coffeecup~
	
	\noindent
	Let $\RR_+ := \{x\in \RR: x\geq 0\}$ be the set of non-negative real numbers. Let $(0,1] := \{r\in \RR: 0< r\leq 1\}$.
	Prove that the following function $f: \RR_+ \to (0,1]$ is valid and injective.
	\[
	f(x) = \frac{1}{1+x}
	\]
\end{exercise}
\solution{
	To check it is valid, we need to show for every non-negative real $x\geq 0$, we must have $0 <f(x) \leq 1$. This amounts to proving 
	$0 < \frac{1}{1+x} \le 1$. Both follow since $x\geq 0$.
	
	To show $f$ is injective, we need to show for every $x$ and $y$ in the domain with $x\neq y$, we must have $f(x)\neq f(y)$. To this end, 
 pick two \emph{arbitrary} $x,y \in \RR_+$ such that $x \neq y$. We may assume without loss of generality that $x < y$ for otherwise we swap their names.
	Since $x < y$, we get $1 + x < 1+y$ and thus $\frac{1}{1+x} > \frac{1}{1+y}$. This implies that $f(x) > f(y)$; in particular, $f(x) \neq f(y)$.
}

\vspace{3ex}
\begin{exercise}[Proving something is surjective]\Coffeecup~
	
	\noindent
	Let $\RR_+ := \{x\in \RR: x\geq 0\}$ be the set of non-negative real numbers. Let $(0,1] := \{r\in \RR: 0< r\leq 1\}$.
	Prove that the following function $f: \RR_+ \to (0,1]$ is surjective.
	\[
	f(x) = \frac{1}{1+x}
	\]
\end{exercise}
\solution{
	To show $f$ is surjective, we need to show that for every $y$ in the co-domain (here this is $(0,1]$), there must exist an $x$ in the domain (here this is $\RR_+$) such that
	$f(x) = y$. To this end, fix an $0 < y \leq 1$. We need to find an $x$ such that $f(x) = y$. That is, $\frac{1}{1+x} = y$. We see that $x = \frac{1}{y} - 1$ satifies this.
	Furthermore, since $y\leq 1$, we get $x\geq 0$. Therefore, this number $x$ is in the domain. 
}



\vspace{3ex}

\begin{exercise}[Composition] \Coffeecup~
	
	
	\noindent
	As you know, given any two functions $g: A \rightarrow B$ and $f: B \rightarrow C$,
	the composition of $f$ and $g$, denoted $g \circ f$, is the function from $A$ to $C$
	given by $(g \circ f)(x) = g(f(x))$.
	
	If $g$ and $f$ are functions from $\RR$ to $\RR$ given by $g(x) = 2x^2+5$ and $f(x) = 3x^2-1$,
	\begin{enumerate}
		\item
		What is $(g \circ f)(x)$?
		
	\solution{$(g \circ f)(x) = g(f(x)) = g(3x^2 -1) = 2(3x^2-1)^2 + 5$.}
		\item
		What is $(f \circ g)(x)$?
		
\solution{$(f \circ g)(x) = f(g(x)) = f(2x^2+5) = 3(2x^2+5)^2 - 1$.}

		\item
		What is $(f \circ f)(x)$?
		
\solution{$(f \circ f)(x) = f(f(x)) = f(3x^2 -1) = 3(3x^2-1)^2 - 1$.}
		\item
		What is $(g \circ g)(x)$?
		
	
\solution{$(g \circ g)(x) = g(g(x)) = g(2x^2 + 5) = 2(2x^2+5)^2 + 5$.}
	\item
		What are the values of $(g \circ f)(2)$, $(f \circ g)(2)$, $(f \circ f)(2)$, and $(g \circ g)(2)$?
		
		\solution{
		$(g \circ f)(2) = 2(3 \times 2^2-1)^2 + 5 = 247$
		
		$(f \circ g)(2) = 3(2 \times 2^2+5)^2 - 1 = 506$
	
		$(f \circ f)(x) = 3(3 \times 2^2-1)^2 - 1 = 362$
		
		$(g \circ g)(x) = 2(2 \times 2^2+5)^2 + 5 = 343$
	}\end{enumerate}
\end{exercise}



\section{Logic}
\begin{exercise}\Coffeecup~
	
Rewrite each of the following statements in English in the form $p \limplies q$.
For example, the statement ``I catch cold if I eat ice cream'' should be rewritten ``I eat ice cream $\limplies$ I catch cold.''
\begin{enumerate}
	\item
	Winds from the south imply a strong thaw.
	
	\noindent
	\solution{
	Winds from the south $\limplies$ a strong thaw.
	}
	\item
	Willy gets caught whenever he cheats.

	\solution{
	Willy cheats $\limplies$ Willy gets caught.}

	\item
	You can access the website only if you pay the subscription fee.
	
	\noindent
\solution{
	You can access the website $\limplies$ you pay the subscription fee.
}
\end{enumerate}
\end{exercise}

\vspace{2ex}

\begin{exercise}\Coffeecup~
	
Let $S$ be the statement $p \limplies q$ for two propositions $p$ and $q$.
Define the {\em converse}, {\em inverse}, and {\em contrapositive} of the statement $S$ to be the statements represented by
$q \limplies p$, $\neg p \limplies \neg q$, and $\neg q \limplies \neg p$, respectively. Now consider the following sentences and do what is asked.

\begin{enumerate}
	\item
	{\em I open my umbrella whenever it rains.}
	
	Rewrite the above sentence in the form $p \limplies q$.
	Then write a natural sounding English sentence that represents its inverse.
	
	\solution{
	It rains $\limplies$ I open my umbrella. \\
	Whenever it doesn't rain, I keep my umbrella closed.}
	
	\item
	{\em I miss class only if I am unwell.}
	
	Rewrite the above sentence in the form $p \limplies q$.
	Then write a natural sounding English sentence that represents its contrapositive.
	
\solution{
	I miss class $\limplies$ I am unwell. \\
	If I am well, I wont miss class.
}
	
	\item
	{\em You can't invent unless you are curious and knowledgeable.}
	
	Rewrite the above sentence in the form $p \limplies q$, using the symbol $\neg$ wherever necessary.
	Then write a natural sounding English sentence that represents its converse.
	
\solution{
	
	You invent things $\limplies$ you are curious and knowledgeable. \\
	If you are curious and knowledgeable, then you invent things. }
\end{enumerate}
\end{exercise}


\vspace{3ex}



\vspace{2ex}

\begin{exercise} \Coffeecup \Coffeecup %\Coffeecup~
	
	Without using truth tables, and using the important equivalences done in class and given in the lecture notes, prove the following logical equivalences.
	\begin{enumerate}
		\item $p \Rightarrow q \equiv \neg q \Rightarrow \neg p$
		
		\solution{ 
			\begin{alignat}{6}
			p \Rightarrow q && ~\equiv~ && \neg p \vee q && \qquad \textrm{Implication as OR}\notag \\
							&& ~\equiv~ && q \vee \neg p && \qquad \textrm{Commutativity}\notag \\
			                && ~\equiv~ && \neg (\neg q) \vee \neg p && ~\qquad \textrm{Negation of Negation}\notag \\
							&& ~\equiv~ && \neg q \Rightarrow \neg p && ~\qquad \textrm{Implication as OR}\notag
			\end{alignat}
		}
		
		

		
		\item $\Big((p \Rightarrow \neg p) \Rightarrow \left((q \Rightarrow (p \Rightarrow p)) \Rightarrow p \right)\Big) \equiv p$ %({\bf 2 points})
		
		\solution{
			\begin{alignat}{6}
			(p \Rightarrow \neg p) \Rightarrow \left((q \Rightarrow (p \Rightarrow p)) \Rightarrow p \right) && ~\equiv~ && (\neg p \vee \neg p) \Rightarrow \left((q \Rightarrow (p \Rightarrow p)) \Rightarrow p \right) && \qquad \textrm{Implication as OR}\notag \\
			&& ~\equiv~ && \neg p \Rightarrow \left((q \Rightarrow (p \Rightarrow p)) \Rightarrow p \right)   && \qquad \textrm{Idempotence}\notag \\
			&& ~\equiv~ && \neg p \Rightarrow \left((q \Rightarrow \true) \Rightarrow p \right)  && \qquad \textrm{Just as in part (b)}\notag \\
			&& ~\equiv~ && \neg p \Rightarrow (\true \Rightarrow p)  && \qquad \textrm{$q\Rightarrow \true \equiv \neg q \vee \true \equiv \true$.}\notag \\
			&& ~\equiv~ && \neg p \Rightarrow (\false \vee p) && ~\qquad \textrm{Implication as OR}\notag \\
			&& ~\equiv~ &&  \neg p \Rightarrow p && ~\qquad \textrm{Operation with $\false$}\notag \\
			&& ~\equiv~ &&  p \vee p && ~\qquad \textrm{Implication as OR}\notag \\
			&& ~\equiv~ &&  p && ~\qquad \textrm{Idempotence} \notag
			\end{alignat}	
			
		}
	\end{enumerate}
\end{exercise}

\vspace{3ex}

\begin{exercise} [Fun with Predicate Logic] \Coffeecup \Coffeecup~
	
		Let $P[1\ldots n, 1 \ldots m]$ be a $2$-dimensional array of the pixels of a black-and-white image: for every $x$ and $y$, the value of $P[x,y] = 0$ if and only if the $(x,y)$th pixel is black, and $P[x,y] = 1$ if it is white. Translate the following statements into predicate logic. 
		%Furthermore, for each statement write the negation in Predicate Logic, and then translate back in English.
	\begin{enumerate}
		\item Every pixel in the image is black.
		\item There is at least one white pixel.
		\item Every row has at least one white pixel.
		\item There is no column with two consecutive white squares.
	\end{enumerate}
\end{exercise}

\solution{
	The predicate $P(x,y)$ takes integer variables where $x$ ranges from $1$ to $n$ and $y$ ranges from $1$ to $n$. $P(x,y)$ evaluates to true if $P[x,y] = 0$, that is, if the $(x,y)$th pixel is black, and it evaluates to false otherwise. Using this, we can express the statements in predicate logic as follows.
	\begin{enumerate}
		\item 
		$\forall 1\leq x \leq m, 1\leq y \leq n : P(x,y)$
		
		\item $\exists 1\leq x \leq m, 1\leq y \le n:  \neg P(x,y)$
		
		\item $\forall 1\leq x\leq m ~~ \exists 1\leq y \leq n : \neg P(x,y)$
		
		\item Sometimes it is easier to write the logical statement of the negation and then negate it. The negation of the statement given 
		is 
		\begin{quote}
			\emph{There is some column with two consecutive white squares}
		\end{quote}
		which can be written as 
		\[
		\exists 1\leq y\le n ~~ \exists 1\leq x \leq m-1: ~~ \neg P(x,y) \wedge \neg P(x+1,y)
		\]
		It's negation is (which is the answer)
		\[
		\forall 1\leq y\leq n ~~~ \forall 1\leq x \leq m-1 : ~~~ P(x,y) \vee P(x+1,y)
		\]
		
	\end{enumerate}
}

\end{document}