\documentclass[11pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}

\usepackage[margin=1in]{geometry}
\usepackage{microtype}
\usepackage[parfill]{parskip}

\usepackage{graphicx,grffile}
\graphicspath{ {./img/} }
\usepackage{xcolor}
\usepackage{pgf,tikz,pgfplots}
\pgfplotsset{compat=1.15}
\usetikzlibrary{cd}
\usepackage{caption}

\usepackage[hidelinks]{hyperref}

\usepackage{amsmath,amssymb,amsthm,mathtools,mathrsfs,esdiff,stmaryrd,mathabx,dsfont}

\usepackage[inline]{enumitem}
\setlist[enumerate]{label=(\alph*),ref=(\alph*)}

\usepackage{cleveref}

% \usepackage{suffix}
\usepackage{ragged2e}
\usepackage{framed}

\makeatletter

\newcommand*{\CC}{\mathbb{C}}
\newcommand*{\RR}{\mathbb{R}}
\newcommand*{\QQ}{\mathbb{Q}}
\newcommand*{\ZZ}{\mathbb{Z}}
\newcommand*{\NN}{\mathbb{N}}
\newcommand*{\FF}{\mathbb{F}}
\renewcommand*{\AA}{\mathbb{A}} % Replace Å
\newcommand*{\PP}{\mathbb{P}}
\newcommand*{\GG}{\mathbb{G}}
\renewcommand*{\SS}{\mathbb{S}}
\newcommand*{\TT}{\mathbb{T}}
\newcommand*{\VV}{\mathbb{V}}

\newcommand*{\kA}{\mathfrak{A}}
\newcommand*{\km}{\mathfrak{m}}
\newcommand*{\kp}{\mathfrak{p}}
\newcommand*{\kq}{\mathfrak{q}}

\newcommand*{\sA}{\mathscr{A}}
\newcommand*{\sC}{\mathscr{C}}
\newcommand*{\sE}{\mathscr{E}}
\newcommand*{\sF}{\mathscr{F}}
\newcommand*{\sG}{\mathscr{G}}
\newcommand*{\sH}{\mathscr{H}}
\newcommand*{\sI}{\mathscr{I}}
\newcommand*{\sK}{\mathscr{K}}
\newcommand*{\sO}{\mathscr{O}}
\newcommand*{\sP}{\mathscr{P}}
\newcommand*{\sQ}{\mathscr{Q}}
\newcommand*{\sX}{\mathscr{X}}

\newcommand*{\cM}{\mathcal{M}}

\newcommand*{\nth}{^{\mathrm{th}}}

\DeclarePairedDelimiter{\ceil}{\lceil}{\rceil}
\DeclarePairedDelimiter{\floor}{\lfloor}{\rfloor}
\DeclarePairedDelimiterX\innerp[2]{\langle}{\rangle}{#1,#2}
\DeclarePairedDelimiter{\norm}{\lVert}{\rVert}
\DeclarePairedDelimiter{\abs}{\lvert}{\rvert}
\DeclarePairedDelimiter{\order}{\lvert}{\rvert}
\DeclarePairedDelimiter{\ps}{\llbracket}{\rrbracket}
\DeclarePairedDelimiter{\angles}{\langle}{\rangle}

\DeclareMathOperator{\coker}{coker}
\DeclareMathOperator{\Span}{Span}
\DeclareMathOperator{\rank}{rk}
\DeclareMathOperator{\nullity}{null}
\DeclareMathOperator{\diag}{diag}
\DeclareMathOperator{\sgn}{sgn}
\DeclareMathOperator{\tr}{tr}
% \DeclareMathOperator{\degree}{deg}
\DeclareMathOperator{\fchar}{char}
\DeclareMathOperator{\trdeg}{tr.deg}
\DeclareMathOperator{\codim}{codim}
\DeclareMathOperator{\height}{ht}
\DeclareMathOperator{\pd}{pd}

\DeclareMathOperator{\Pl}{Pl}
\DeclareMathOperator{\Sec}{Sec}
\DeclareMathOperator{\Div}{Div}
\let\div\undefined
\DeclareMathOperator{\div}{div}
\DeclareMathOperator{\Cl}{Cl}
\DeclareMathOperator{\Spec}{Spec}

% \newcommand{\divides}{\mid}
% \newcommand{\notdivides}{\nmid}

\newcommand*{\close}{\overline}
\newcommand*{\interior}[1]{#1^\circ}
\newcommand*{\bound}[1]{\partial #1}

\newcommand*{\xto}[1]{\xrightarrow{#1}}
\newcommand*{\xfrom}[1]{\xleftarrow{#1}}
\newcommand*{\To}{\Rightarrow}
\newcommand*{\into}{\hookrightarrow}
\newcommand*{\onto}{\twoheadrightarrow}
\newcommand*{\isoto}{\xto{\sim}}

\newcommand*{\dirlim}{\lim\limits_{longrightarrow}}
\newcommand*{\dirlimarg}[1]{\lim\limits_{\substack{\longrightarrow\\#1}}}
\newcommand*{\invlim}{\lim\limits_{\longleftarrow}}
\newcommand*{\invlimarg}[1]{\lim\limits_{\substack{\longleftarrow\\#1}}}

\newcommand*{\wh}[1]{\widehat{#1}}
\newcommand*{\wt}[1]{\widetilde{#1}}
\newcommand*{\ol}[1]{\overline {#1}}
\newcommand*{\ul}[1]{\underline {#1}}

\DeclareMathOperator{\Aut}{Aut}
\DeclareMathOperator{\Syl}{Syl}
\DeclareMathOperator{\Gal}{Gal}
\DeclareMathOperator{\Frac}{Frac}
\DeclareMathOperator{\Ann}{Ann}
\DeclareMathOperator{\Hom}{Hom}
\DeclareMathOperator{\Ext}{Ext}
\DeclareMathOperator{\Tor}{Tor}
\DeclareMathOperator{\End}{End}
\DeclareMathOperator{\GL}{GL}
\DeclareMathOperator{\PGL}{PGL}
\DeclareMathOperator{\Mat}{Mat}
\DeclareMathOperator{\Gr}{Gr}
\DeclareMathOperator{\im}{im}
\DeclareMathOperator{\lcm}{lcm}

\newcommand*{\sep}{\mathrm{sep}}

\newcommand{\present}[2]{\langle{{#1} \: |  \: {#2}}\rangle}
\newcommand{\cyclic}[1]{\langle{#1}\rangle}

\newcommand*{\residue}[1]{\mkern 1.5mu\overline{\mkern-1.5mu#1\mkern-1.5mu}\mkern 1.5mu}
\newcommand*{\zmod}[1]{ \Z / #1 \Z }

\newcommand*{\lni}{\lim_{n \to \infty}}
\newcommand*{\lNi}{\lim_{N \to \infty}}
\newcommand*{\sni}{\sum_{n=1}^\infty}

\newcommand\restr[2]{{% we make the whole thing an ordinary symbol
  \left.\kern-\nulldelimiterspace % automatically resize the bar with \right
  #1 % the function
  \vphantom{\big|} % pretend it's a little taller at normal size
  \right|_{#2} % this is the delimiter
}}
\newcommand*{\st}{\ \vert\ }

\newcommand{\conj}[1]{\overline{#1}}

\newcommand{\catname}[1]{{\mathsf{#1}}}
\newcommand{\Set}{\mathsf{Set}}
\newcommand{\Alg}[1]{#1\!-\!\mathsf{Alg}}
\newcommand{\Vect}[1]{#1\!-\!\mathsf{Vect}}
\newcommand{\Mod}[1]{#1\!-\!\mathsf{Mod}}
\renewcommand{\mod}[1]{#1\!-\!\mathsf{mod}}
\newcommand{\CommAlg}[1]{#1\!-\!\mathsf{CommAlg}}
\newcommand{\Ring}{\mathsf{Rings}}
\newcommand{\CommRing}{\mathsf{CommRings}}
\newcommand{\Grp}{\mathsf{Grp}}
\newcommand{\Ab}{\mathsf{Ab}}
\newcommand{\Fun}{\mathsf{Fun}}
\newcommand{\For}{\mathsf{For}}
\newcommand{\Fld}{\mathsf{Fld}}
\newcommand{\Open}{\mathsf{Open}}
\newcommand{\Aff}[1]{#1\!-\!\mathsf{Aff}}
\newcommand{\aA}{\mathsf{A}}
\newcommand{\aB}{\mathsf{B}}
\newcommand{\aC}{\mathsf{C}}
\newcommand{\aD}{\mathsf{D}}
\newcommand{\aG}{\mathsf{G}}
\newcommand{\aK}{\mathsf{K}}
\newcommand{\aP}{\mathsf{P}}

\newcommand{\op}{\textnormal{op}}
\newcommand{\fd}{\textnormal{fd}}
\DeclareMathOperator{\Ob}{Ob}
\newcommand{\id}{\mathrm{id}}

\newcommand*{\dir}[2]{(#1) \( \Rightarrow \) (#2)}

% -------------------
% Heading Commands
% -------------------
\newcommand{\class}{Math 294}
\newcommand{\term}{Fall 2024}
\newcommand{\instructor}{Theo Sandstrom}
\newcommand{\head}[2]{%
\thispagestyle{empty}
\vspace*{-0.5in}
\noindent\begin{tabular*}{\textwidth}{l @{\extracolsep{\fill}} r @{\extracolsep{6pt}} l}
	\textbf{#1} & \textbf{Name:} & \makebox[8cm]{\hrulefill} \\
	\textbf{#2} & & \\
	\textbf{\class:\; \term} & & \\
	\textbf{Instructor: \instructor}
\end{tabular*} \\
\rule[2ex]{\textwidth}{2pt} %
}


% -------------------
% Commands
% -------------------
\newcounter{problem}
\newenvironment{problem}
{
  \begin{leftbar}
  \begin{justify}
    \stepcounter{problem}%
    \textbf{Problem \theproblem. }
}
{
\end{justify}
\end{leftbar}
}
\newenvironment{problem*}[1]
{
  \begin{leftbar}
  \begin{justify}
    \stepcounter{problem}%
    \textbf{Problem \theproblem\ (#1). }
}
{
\end{justify}
\end{leftbar}
}


% -------------------
% Header & Footer
% -------------------
\usepackage{fancyhdr}

\fancypagestyle{pages}{
	%Headers
	\fancyhead[L]{}
	\fancyhead[C]{}
	\fancyhead[R]{}
\renewcommand{\headrulewidth}{0pt}
	%Footers
	\fancyfoot[L]{}
	\fancyfoot[C]{}
	\fancyfoot[R]{}
\renewcommand{\footrulewidth}{0.0pt}
}
\headheight=0pt
\footskip=14pt

\pagestyle{pages}

\makeatother

\begin{document}

\head{Worksheet 2}{Week 2: 2024-09-03}

These problems are to be completed in class on Tuesday and Thursday. Work in groups! And come to
office hours if you have further questions! They're great! \vspace{5mm}

\begin{framed}
  \textit{``Insight. Originality. Inspiration. New perspectives. Opening your mind. Finding a
    different way. Playing around. That is mathematics. There is a myth that mathematics is
    about memorization, technicalities, formulas and equations--there is only one correct
    answer. This picture utterly fails to describe the creative process that is professional
    mathematics.}

  Prof. Melanie Wood (b. 1981) is a number theorist at Harvard University. While in high school
  in Indianapolis, she was the first female American to make the US team for the International
  Mathematical Olympiad. At Duke, she won a Gates Cambridge Scholarship, and was named a Putnam
  Fellow.

  \textit{``Numbers and their properties are one of the most ancient and universal interests of
    humanity. Yet numbers hold more secrets that we are still working to reveal. Unlocking these
    mysteries requires new perspectives and often happens when we discover surprising
    connections between different parts of mathematics.''}

  Much of Wood's research has leveraged tools from arithmetic statistics: applying probabilistic
  methods to solve problems in number theory. For certain classes of problem, verifying that a
  hypothesis is true in all cases (e.g. for every prime number) may be infeasible, but Wood has
  found success studying how these number theoretic objects behave \textit{on average}.
  
  \noindent\makebox[\textwidth][c]{
  \begin{minipage}[t]{0.5\linewidth}
    \vspace{-2ex}
    \centering
    \includegraphics[width=\linewidth]{wood}
  \end{minipage}}
\end{framed}

\begin{problem}
  For each of the following, write an equivalent propositional logic statement that does
  \textit{not} make use of implications (\( \Rightarrow \)):
  \begin{enumerate}
  \item \( p \Rightarrow q \)
  \item \( (p \wedge q) \Rightarrow q \)
  \item \( (p \Rightarrow q) \wedge (q \Rightarrow p) \)
  \end{enumerate}
\end{problem}

\vspace{7cm}

\begin{problem}
  \begin{enumerate}
  \item
    Give truth tables for the following propositional logic formulas:
    \begin{enumerate}[label=(\roman*)]
    \item \( (p \wedge q) \vee r \)
    \item \( (p \vee q) \Rightarrow r \)
    \item \( (p \Rightarrow q) \Rightarrow r \)
    \item \( p \Rightarrow (q \Rightarrow r) \)
    \end{enumerate}
  \item In each case, explain the steps you would take to prove a statement of the given form.
  \end{enumerate}
\end{problem}

\vspace{10cm}

\begin{problem}
  Give the negation of each of the above statements, applying De Morgan's law as appropriate.
\end{problem}

\vspace{7cm}

\begin{problem}
  Fontano's is an Italian sandwich shop near campus. Let \( p \) mean ``you get a bag of chips
  and a drink for free from Fontano's'', \( q \) mean ``you buy a sandwich from Fontano's'',
  \( r \) mean ``you buy a slice of pizza from Fontano's'', and \( t \) mean ``it's a Tuesday.''

  Express the meaning of the following propositional formula in plain English:

  \[ t \wedge (q \vee r) \implies p. \]
  (Unfortunately, this is not a true statement.)
\end{problem}

\vspace{3cm}

\begin{problem}
  Consider the statement ``The blue line will be delayed if it has snowed more than one inch,
  and if the blue line is delayed, Theo will be late for his class.'' Write this statement in
  propositional logic, specifying the meaning of each variable.
\end{problem}

\vspace{3cm}

\begin{problem}
  Let \( p \) and \( q \) be propositional variables, and consider the statement
  \( p \Rightarrow q \). This implication may be either true or false. For each of the following
  statements, must the truth value be the same as the original statement? Must it be different?
  Is there enough information to tell one way or the other?
  \begin{enumerate}
  \item \( \neg p \Rightarrow \neg q \)
  \item \( q \Rightarrow p \)
  \item \( \neg q \Rightarrow \neg p \)
  \item \( p \Rightarrow \neg q \)
  \end{enumerate}
  In each case, give a \textit{mathematical proof} as well as an \textit{explanation in plain
    English}.
\end{problem}

\vspace{7cm}

\begin{problem}
  Let \( n \) be a positive integer that divides 4. Prove that either \( n \) is even or \( n \)
  is a perfect square. (Bonus: what numbers could we replace 4 in order for the conclusion to
  remain true?)
\end{problem}

\vspace{7cm}

\begin{problem}
  Recall that a number \( x \) is called \textit{rational} if there exist integers \( m \) and
  \( n \) so that \( x = m / n \). Let \( x \) and \( y \) be rational numbers. Prove that if
  both \( x + y \) and \( x - y \) are rational, then \( x \) and \( y \) are rational.
\end{problem}

\vspace{7cm}

\begin{problem}
  Let \( x \) be a rational number, and \( a \) an irrational number. Is \( x + a \) rational?
  Irrational? Provide proof.
\end{problem}

\vspace{7cm}

\begin{problem}
  Let \( a \) and \( b \) be integers. Prove that if \( a b \) is even, then either \( a \) is
  even or \( b \) is even.
\end{problem}

\end{document}
