% 
% hw2.tex
%
%   This is LaTeX template to get you started
%   making problem-set solutions
%
 
\documentclass[11pt]{article}
\usepackage{amsthm,amsmath, amssymb}
\usepackage{color}
\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}
\setlength{\textheight}{9.0in}
\setlength{\textwidth}{6.5in}
\setlength{\topmargin}{-0.5in}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{\bf Homework 4: due 1/29/2019\\[2ex]
       \rm\normalsize ECS 20 (Winter 2019)}
%\date{\today}
\author{Patrice Koehl\\koehl@cs.ucdavis.edu}

\begin{document}
\maketitle

Total number of points: 130 + 5 points extra credit

\emph{(No more extra credit for typing, or uploading in Canvas....)}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 1 \emph{(10 points)}} 
Give a direct proof, an indirect proof, and a proof by contradiction of the statement ``if $n$ is even, then $n+9$ is odd."

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 2 \emph{(10 points)}} 

Let $A=\{2, 4, 6\}$ (set of all even numbers less than 8) and $B=\{3, 6\}$ (set of all multiples of 3 less than 8). Define $\mathcal{P}(A \bigcap B)$, $\mathcal{P}(B)$, and $\mathcal{P}(A \bigcup B)$,
where $\mathcal{P}(C)$ indicates the power set of the set $C$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 3 \emph{(40 points: 10 points for each part)}} 

Let $A$, $B$, and $C$ be three sets in a universe $\mathcal{U}$. Show the following identities:
\begin{itemize}
\item [a)] $ \left(\overline {\left(A - B \right)} \bigcap B \right) - \overline{B} = B$ 
\item [b)] $ \overline {B} - \left( \overline{B}- A\right) = \overline{B} \bigcap A $
\item [c)] $ \left( A - B \right) -  \left( A-C \right)  = A\bigcap C - B$
\item [d)] $ \left( A-B \right) = \left(A-B\right) - \left( B - C \right)$
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 4 \emph{(20 points: 10 points for each part)}}

Let $A$, and $B$ be two sets in a universe $\mathcal{U}$. Using set identities (no truth table or membership table!), show the following implications:

\begin{itemize}
\item [a)] if $A \bigcup B = B$, then $ \overline{\left(\overline{B}-A \right)} \bigcap \left(B \bigcup A \right) = B$.
\item [b)] if $A \bigcap B = A$, then $A \bigcup B = B$
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 5 \emph{(20 points: 10 points for each part)}}

Let $A$, and $B$ be two sets in a universe $\mathcal{U}$. The symmetric difference of A and B, denoted $A \oplus B$, is the set containing those elements in either $A$ or $B$, but not in both $A$ and $B$. This definition can be rewritten as: $A \oplus B = \left(A - B \right) \bigcup \left(B - A\right)$. Show that:
\begin{itemize}
\item [a)] $A \oplus B  = \left( \overline{A} \bigcap B \right) \bigcup \left(A \bigcap \overline{B} \right)$
\item [b)] $A \oplus B = \left( A \bigcup B\right) - \left(A \bigcap B\right)$
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 6 \emph{(10 points)}}

Let $A$, and $B$ be two sets in a universe $\mathcal{U}$. Show that $\vert \overline{A} \bigcup \overline{B}\vert = \vert \mathcal{U} \vert - \vert A \vert - \vert B \vert + \vert A \bigcup B \vert$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 7 \emph{(20 points: 10 points for each part)}}

\begin{itemize}
\item [a)] Let $A$, $B$, and $C$ be three sets in a universe $\mathcal{U}$. Show that $\vert A \bigcup B \bigcup C \vert = \vert A \vert + \vert B \vert + \vert C \vert - \vert A \bigcap B \vert - \vert A \bigcap C \vert - \vert B \bigcap C \vert + \vert A \bigcap B \bigcap C \vert$.

\item [b)] In a group of students, 60 play soccer, \textcolor{red}{40} play hockey, and 36 play cricket, 20 play soccer and hockey, 25 play hockey and cricket, 12 play cricket and soccer and 10 play all the three games. Find the total number of students in the group and how many students only played soccer? (Assume that each student in the group plays at least one game)
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section*{Extra Credit \emph{(5 points)}}

Let $A$, $B$, and $C$ be three sets in a universe $\mathcal{U}$. Using set identities (no truth table or membership table!), show the following identity,

$\left(A \cup B \cup C \right) \cap \overline{\left(A \cap \overline{B} \cap \overline{C}\right)} \cap \overline{C} = B \cap \overline{C}$

\end{document}