\documentclass[12pt]{article}

\usepackage{amssymb,amsmath,amsthm} 
\usepackage{color}
\usepackage{verbatim}

%%% Margins %%%
\setlength{\topmargin}{0pt}
\setlength{\headheight}{0pt}
\setlength{\headsep}{0pt}
\setlength{\topskip}{0pt}
\setlength{\footskip}{0pt}
\setlength{\oddsidemargin}{-20pt}
\setlength{\textheight}{9in}
\setlength{\textwidth}{6.7in}
\setlength{\parindent}{0pt}
\setlength{\parskip}{4ex}

%%% Macros %%%
% Some macros to get you started
\DeclareMathOperator{\Vol}{Vol}
\DeclareMathOperator{\im}{im}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\QQ}{\mathbb{Q}}




\begin{document}

\pagestyle{empty}

\begin{center}
{\large MATH 108 Fall 2019 \ -  \ {\bf Problem Set 1}}

% Put your name and section here.
{\large due October 4}
\end{center}


\begin{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

	\item Write the truth table for each propositional form, and determine if it is a tautology, a contradiction, or neither.
	\begin{enumerate}
	 \item $P \Leftrightarrow P \wedge (P \vee Q).$
	 \item $[Q \wedge (P \Rightarrow Q)] \Rightarrow P.$
	 \item $P \wedge (P \Leftrightarrow Q) \wedge {\sim} Q.$
	 \item $(P \Rightarrow Q) \Leftrightarrow (Q \Rightarrow P).$
	\end{enumerate}
	Here is an example truth table that you can use as a template:
	
	\begin{tabular}{cc|cc}
	$P$ & $Q$ & $P \vee Q$ & $P \wedge Q$ \\
	\hline
	T & T & T & T \\
	T & F & T & F \\
	F & T & T & F \\
	F & F & F & F
	\end{tabular}
	
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

	\item Rewrite each proposition in English.  You may use mathematical expressions (e.g. ``$x = 0$'') in your answers but replace all the logical symbols.  Take the universe to be all real numbers.
	\begin{enumerate}
	 \item $(\forall x)(\forall y)[(xy > 0) \vee (xy < 0)].$
     \item $(\exists x)(\forall y)(x+y = 0).$
     \item $(\forall y)(\exists x)(x+y = 0).$
     \item $(\forall x)[x > 0 \Rightarrow (\exists y)(xy = 1)].$
     \item $(\forall y)(\exists! x)[(x \leq y) \wedge (y \leq x)].$
     \item $(\forall y)(\exists! x)(y = x^2).$
    \end{enumerate}

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

	\item Determine if each proposition in Problem 2 is true or false in the universe of all real numbers.  Give a short justification for each answer.

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

	\item Let $x$ be a real number.  For each proposition, write the contrapositive.  Then prove the proposition by contraposition.
	\begin{enumerate}
	 \item If $x^2 + 2x < 0$, then $x < 0$.
	 \item If $x(x-4) > -3$, then $x < 1$ or $x > 3$.
    \end{enumerate}

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

	\item Let $a$ and $b$ be positive integers.  Prove each proposition by contradiction.
	 \begin{enumerate}
	  \item If $a$ divides $b$, then $a \leq b$.
	  \item Either $a$ and $b$ are odd, or $ab$ is even.
	  \item If $a < b$ and $ab < 4$, then $a = 1$.
     \end{enumerate}
     
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

	\item For $x$ a real number, $\lfloor x \rfloor$ denotes the ``floor'' of $x$, which is the largest integer less than or equal to $x$.  Prove using cases that for all integers $k$, the value of $\lfloor k^2/2 \rfloor$ is even.
     
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

	\item Let $x$, $y$ and $z$ be three real numbers in the interval $[0,1]$.  Prove that there exists a pair of two of the three numbers that are at distance $\leq 1/2$ apart. [Hint: You can assume without loss of generality that $x \leq y \leq z$.  Why is it sufficient to only consider this case?]
     
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{enumerate}
\end{document}


