\documentclass[11pt]{article}
\usepackage{jeffe,handout,multicol,tikz}
\usetikzlibrary{arrows,automata}
\usepackage[latin1]{inputenc}

\tikzstyle{vertex}=[circle,draw]

\newcommand{\kgmcomment}[1]{}

\begin{document}
\headers{Math303}{Homework 6}{Due: Wed. Feb 21, 2024}

%\makeatletter
%\def\@oddfoot{\hfill \tikz \node[draw] {over} ; }
%\makeatother

\makeatletter
\def\@oddfoot{}
\makeatother

%\noindent
%\hfill Name: \underline{\hspace{3.5in}} 

%\begin{flushright}
%Name: \underline{\hspace{3.5in}} \\
%\end{flushright}
%\hrule

\def\columnseprule{0.4pt}

\newcommand{\PS}{\mathcal{P}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\st}{\colon \,}
\newcommand{\comp}[1]{\overline{#1}}
\renewcommand{\emptyset}{\varnothing}
\newtheorem{theorem}{Theorem}{}


\noindent
\textbf{Directions:} You may work to solve these problems in groups, but all written work must be your own.  Unless the problem indicates otherwise, all problems require some justification; a correct answer without supporting reasoning is not sufficient.  See ``Guidelines and advice' on the course webpage for more information.

\begin{enumerate}

\item Translate the following English statements to symbolic logic.  Is the statement true or false?  Explain.
\begin{enumerate}
	\item Every set has a subset.
	\item Every nonempty set has a subset.
	\item Every set has a nonempty subset.
	\item Every nonempty set has a nonempty subset.
	\item An integer plus an integer always equals an integer.
	\item Every nonempty subset of the natural numbers has a maximum integer.
	\item Between every pair of distinct rational numbers, there is a third rational number.
	\item There is a rational number which is between every pair of distinct rational numbers.
\end{enumerate}

\item Translate the following sentences in symbolic logic to English.  Is the statement true or false?  Explain.
\begin{enumerate}
	\item $\exists x\in\ZZ,  x^4 = 81$
	\item $\forall x\in\ZZ, x^2 \ge 0$
	\item $\forall x\in\NN, \forall y\in \NN, x + y > x \wedge x + y > y$
	\item $\forall x\in\ZZ, \exists y\in \ZZ, (x=2y) \vee (x=2y+1)$
	\item $\forall x\in\ZZ, [(\exists y\in \ZZ, x=6y) \iff (\exists y \in \ZZ, x=2y) \wedge (\exists y \in \ZZ, x = 3y)]$.
\end{enumerate}

\item Carefully negate the following sentences as simply and naturally as possible.
\begin{enumerate}
	\item The integer $9$ is odd and a perfect square.
	\item If $8$ is even, then $8$ is a perfect square.
	\item A real number $x$ is rational if and only if $2x$ is rational.
	\item Some integer is both even and odd.
	\item Every integer is even or odd, but not both.
	\item All values of the function $\cos(x)$ are bounded between $-1$ and $1$.
	\item For every positive real number $\varepsilon$, there exists a positive real number $\delta$ such that for all $x\in\RR$, if $|x-2| < \delta$ then $|\ln x - \ln 2| < \varepsilon$.  
	[\emph{Hints}: it may be easier to first translate to symbolic logic, then negate and simplify, and then translate back.  It will be convenient to define $\RR^+ = \{x\in\RR\st x>0\}$, so that the translation to symbolic logic can begin $\forall \varepsilon\in\RR^+, \exists \delta\in\RR^+, \ldots$.]
\end{enumerate}

\item \emph{Balanced statements.}  Using only the logical operands $\land$ and $\lor$, write a statement $\varphi$ which is true if and only if at least two of $\{P_1, \ldots, P_8\}$ are true, while using each $P_j$ at most $3$ times.  For example, 
\[ [P_1 \land (P_2 \lor \ldots \lor P_8)] \lor [P_2 \land (P_3 \lor \ldots \lor P_8)] \lor \ldots \lor [P_7 \land P_8] \]
is logically equivalent to the desired sentence $\varphi$, but it is not balanced since $P_8$ is used a total of $7$ times.

\end{enumerate}

\end{document}
