\documentclass{article}
\usepackage{hyperref}
\usepackage{color}

\begin{document}
\flushleft \underline{Homework 1 -- MATH 2510 Spring 2018}
\begin{enumerate}
\item Let $X=\{1,2,3\}$, $Y=\{2,3,4\}$, and $Z=\{1,2,3,5,7\}$.
\begin{enumerate}
\item Is $2 \in X$? Is $2 \in Y$? Is $2 \in Z$? \\
\textit{Solution}: Yes, $2 \in X$. Yes, $2 \in Y$. Yes, $2 \in Z$.
\item Is $X \subseteq Y$? Is $X \subseteq Z$? Is $Y \subseteq Z$? Is $Z \subseteq X$? Is $Z \subseteq Y$? \\
\textit{Solution}: No, $X \not \subseteq Y$, because $1 \in X$ while $1 \not\in Y$. Yes, $Y \subseteq Z$. Not, $Z \not\subseteq X$ because $7 \in Z$ while $7 \not\in X$. No, $Z \not\subseteq Y$ because $7 \in Z$ while $7 \not\in Y$. 
\item  What is $X \cup Y$? What is $X \cup Z$? What is $Y \cup Z$? What is $X \cup Y \cup Z$? \\
\textit{Solution}: Compute
$$X \cup Y = \{1,2,3\} \cup \{2,3,4\} = \{1,2,3,4\},$$
$$X \cup Z = \{1,2,3\} \cup \{1,2,3,5,7\} = \{1,2,3,5,7\},$$
$$Y \cup Z = \{2,3,4\} \cup \{1,2,3,5,7\} = \{1,2,3,4,5,7\},$$
and
$$X \cup Y \cup Z = \{1,2,3\} \cup \{2,3,4\} \cup \{1,2,3,5,7\} = \{1,2,3,4,5,7\}.$$

\item What is $X \cap Y$? What is $X \cap Z$? What is $Y \cap Z$? What is $X \cap Y \cap Z$?  \\
\textit{Solution}: Compute
$$X \cap Y = \{1,2,3\} \cap \{2,3,4\} = \{2,3\},$$
$$X \cap Z = \{1,2,3\} \cap \{1,2,3,5,7\} = \{1,2,3\},$$
$$Y \cap Z = \{2,3,4\} \cap \{1,2,3,5,7\} = \{2,3\},$$
and
$$X \cap Y \cap Z = \{1,2,3\} \cap \{2,3,4\} \cap \{1,2,3,5,7\} = \{2,3\}.$$

\item What is $X \times Y$? \\
\textit{Solution}: Compute
$$\begin{array}{ll}
X \times Y &= \{ (a,b) \colon a \in X, b \in Y \} \\
&= \{ (1,2), (1,3), (1,4), (2,2), (2,3), (2,4), (3,2), (3,3), (3,4)\}.
\end{array}$$
\end{enumerate}

\item Let $X=\{1,2,3\}$ and $Y=\{4,5,6\}$. Let $R \subset X \times Y$ be a relation given by $R = \{(1,5), (1,6), (2,6), (3, 6)\}$. Is $R$ a function? Why or why not? \\
\textit{Solution}: No, $R$ is not a function. This is because both $(1,5) \in R$ and $(1,6) \in R$, but a function is a special kind of a relation with the property that if $(a,b) \in R$ and $(a,c) \in R$, then $b=c$, which does not happen here!

\item Is the following string of symbols a formula of propositional logic? 
$$(A \wedge B) \wedge ((\neg A) \wedge B)$$
\textit{Solution}: Yes. We can build it up using the appropriate rules (rules $(R1)$ and $(R2)$). We know that both $A$ is a formula and $B$ is a formula because they are atomic formulas. It follows that $\neg A$ is a formula. Thus both $A \wedge B$ and $(\neg A) \wedge B$ are formulas. From this we may conclude that $(A \wedge B) \wedge ((\neg A) \wedge B)$ is a formula.

\item Is the following string of symbols a formula of propositional logic? 
$$(A \wedge \neg) \wedge (A \wedge (B \wedge \neg A)).$$
\textit{Solution}: This is not a formula because if it were, then both $(A \wedge (B \wedge \neg A))$ would have to be a formula (it is) and $A \wedge \neg$ would have to be a formula. But $A \wedge \neg$ is not a formula because $\neg$ is not an atomic formula.

\item Prolog exercise. Consider the Prolog code \texttt{family.pl} at \\
\href{https://github.com/tomcuchta/math2510spring2018/blob/master/family.pl}{https://github.com/tomcuchta/math2510spring2018/blob/master/family.pl}. Copy this code to \href{https://swish.swi-prolog.org/}{SWISH}. 
\begin{enumerate}
\item What code do you run to check if Bob is a sibling of Joe? What is the result when it is run? \\
\textit{Solution}: You run \\
\begin{center}\texttt{sibling(bob,joe).}\end{center}
The result is \texttt{true}.
\item What code do you run to check if Tim is a sibling of Alice? What is the result when it is run? \\
\textit{Solution}: You run
\begin{center}\texttt{sibling(tim,alice).}\end{center}
The result is \texttt{false}.
\item What code can you use to define the "brother of" relation? \\
\textit{Solution}: Define the ``brother of" relation with \\
\begin{center} \texttt{ brother(X,Y) :- \\
\hspace{20pt} sibling(X,Y), \\
male(X).} \end{center}
You can check to see that this works by running \texttt{brother(bob,sue).} which returns \texttt{true} while \texttt{brother(sue,bob).} which returns \texttt{false}.
\item What code can you use to define the "uncle of" relation? \\
\textit{Solution}: Define the ``uncle of" relation by
\begin{center} \texttt{ uncle(X,Y) :- \\
\hspace{20pt} parent(Z,Y), \\
\hspace{25pt} brother(X,Z).} \end{center}
Test to see that it works: run \texttt{uncle(joe,tim).} which returns \texttt{true} while \texttt{uncle(tim,joe).} returns \texttt{false}.
\end{enumerate}
\end{enumerate} 
{\color{red} NOTE: the code defined this way behaves strangely with the query \texttt{uncle(jerry,tim).} because it returns \texttt{true} although which you expect to return \texttt{false}. The root of this is the sibling relation being reflexive, i.e. running \texttt{sibling(jerry,jerry).} returns \texttt{true}. This could be fixed by changing the definition of \texttt{sibling} to be the following: \\
\begin{center} \texttt{ sibling(X,Y) :- \\
\hspace{20pt} parent(Z,X), \\
\hspace{20pt} parent(Z,Y), \\
\hspace{5pt} not(X=Y).}
\end{center}
This change will cause the query \texttt{uncle(jery,tim).} to resolve as expected.
}
\end{document}