% !TEX program = pdflatex
% ---------------------------------------------------------------------------
\documentclass[10pt,a4paper,english]{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{bbm}
\usepackage{mathtools}
\usepackage{physics}
\usepackage{enumitem}
\usepackage{tikz}
\usepackage{xcolor}
\usepackage{fancyvrb}
\usepackage{nth}
\usepackage{multicol}
\makeatletter
\newcommand*{\rom}[1]{\expandafter\@slowromancap\romannumeral #1@}
\makeatother
\newcommand\N[0]{\mathbbm{N}}
\newcommand\Z[0]{\mathbbm{Z}}
\newcommand\R[0]{\mathbbm{R}}
\newcommand\Q[0]{\mathbbm{Q}}
\newcommand\C[0]{\mathbbm{C}}
\title{CS40 Summer 2020 Homework \#3}
\begin{document}
\maketitle
\paragraph{Notes}
\begin{itemize}
\item
You may work with a partner in order to understand the problems and discuss how to approach them.
If you do so, write clearly on your assignment the name of the student you collaborated with.
\item
Please re-read the ``Conduct'' section in the class syllabus.
\item
No late submissions! Turn-in what you have by the deadline.
\end{itemize}
\dotfill
\begin{enumerate}
\item
Use rules of inference and logical equivalences for the following (clearly state which rules you are using):
\begin{enumerate}
\item
Show that the premises ``Randy works hard'', ``If Randy works hard,
then he is a dull boy'', and ``If Randy is a dull boy, then he will not get the job'' imply the
conclusion ``Randy will not get the job''.
\item
Prove the implication $$ \qty(s\to p)\land\qty(q\to\neg p) \rightarrow \neg\qty(q\land s) $$
\end{enumerate}
\item
What are the rule of inference used in the following:
\begin{enumerate}
\item
``If it snows today, the university will be closed. The university will not be closed today. Therefore, it did not snow today.''
\item
``My daughter visited France last week, therefore someone has visited France last week.''
\item
``If I work all night on this homework, then I can answer all the exercises.
If I answer all the exercises, I will understand the material.
Therefore, if I work all night on this homework, then I will understand the material.''
\end{enumerate}
\item
You are given the following statements:
\begin{enumerate}[label=\Roman*]
\item All actors and journalists invited to the party are late.
\item There is at least a person who is on time.
\item There is at least an invited person who is neither a journalist nor an actor.
\end{enumerate}
Formalise the sentences using predicate logic and prove or disprove that \rom{3} is a logical consequence of \rom{1} and \rom{2}.
\item
Assume that the universe for $x$ is all people and the universe for $y$ is the set of all movies.
Translate the statements from natural language to predicate logic using the following predicates and any needed quantifiers:
\begin{multicols}{2}
$S(x,y)$ : $x$ saw $y$.\\
$L(x,y)$ : $x$ liked $y$.
$C(y)$ : $y$ is a comedy.\\
$A(y)$ : $y$ won an award.
\end{multicols}
\begin{enumerate}
\item
No comedy won an award.
\item
Some people have seen every comedy.
\item
No one liked every movie they have seen.
\item
Thomas has never seen a movie that won an award.
\end{enumerate}
\item
Prove the following:
\begin{enumerate}
\item
$x^2 = y^2$ if and only if $x=y$ or $x=-y$.
\item
If $x^3$ is irrational, then $x$ is irrational.
\item
If $x$ and $y$ are even integers, then $xy$ is even.
\end{enumerate}
\item
Prove that the following three statements about positive integers are equivalent (that is, each implies the other):
\begin{enumerate}[label=\Roman*]
\item $n$ is even;
\item $n^3 + 1$ is odd;
\item $n^2 - 1$ is odd.
\end{enumerate}
\item
For each of these pairs of sets, determine whether the first is a subset of the second, the second
is a subset of the first, or neither is a subset of the other.
\begin{enumerate}
\item
The set of people who speak English; and the set of people who speak English with an Australian accent.
\item
The set of fruits; and the set of citrus fruits.
\item
The set of students studying discrete mathematics; and the set of students studying data.
\end{enumerate}
% \item Let $f$ be the function from $\R$ to $\R$ defined by $ f(x) = \lfloor x +1 \rfloor$. Find
% \begin{enumerate}
% \item $ f^{-1}\qty(\{1\})$,
% \item $ f^{-1}\qty(\{ x ~|~ 0 < x < 1 \})$,
% \item $ f^{-1}\qty(\{ x ~|~ x > 4 \})$.
% \end{enumerate}
\item
Decide whether the following statements are true or false. You do not need to justify.
\begin{multicols}{2}
\begin{enumerate}
\item
$\emptyset \in \{\emptyset\}$
\item
$\emptyset \in \{\emptyset, \{\emptyset\}\}$
\item
$\{\emptyset\} \in \{\emptyset\}$
\item
$\{\emptyset\} \in \{\{\emptyset\}\}$
\item
$\{\emptyset\} \subset \{\emptyset, \{\emptyset\}\}$
\item
$\{\{\emptyset\}\} \subset \{\emptyset, \{\emptyset\}\}$
\item
$\{\{\emptyset\}\} \subset \{\{\emptyset\}, \{\emptyset\}\}$
\end{enumerate}
\end{multicols}
\item
A certain company employs 100 programmers.
Of these 46 can program in Java, 34 in Python, and 25 can program in both languages.
How many can program in neither Python nor Java?
\item
\begin{enumerate}
\item Write the power set of each of the following sets:
\begin{enumerate}
\item $\emptyset$
\item $\{\emptyset \}$
\item $ \{ a, \{a, b \}\}$.
\end{enumerate}
\item Let $S= \{a, b \}$.
\begin{enumerate}
\item List all ordered pairs $(A,B)$ with $A \subseteq B \subseteq S$
\item List all ordered pairs $(A,B)$ with $A \subseteq B \subseteq S$, where $B$ is a proper subset of $S$.
\end{enumerate}
\end{enumerate}
\item
In each of the following problems, three sets are described. One of the sets is not similar to the other two.
In each case, find the set that is not like the others. Give reasons for your answers.
\begin{enumerate}
\item
$A = \{ a+b \mid a \in \N, b \in \N \} $;
$B = \{ a-b \mid a \in \N, b \in \N \} $;
$C = \N$.
\item
$A = \{ x^2 \mid x \in \N \} $;
$B = \{ x^2 \mid x \in \Z \} $;
$C = \{ x^2 \mid \in \R \} $.
\item
$A = \{ 4z+2 \mid z \in \Z \} $;
$B = \{ 4z-2 \mid z \in \Z \} $;
$C = \{ 2z+4 \mid z \in \Z \} $.
\end{enumerate}
\end{enumerate}
\end{document}