\documentclass[]{amsart}
\usepackage{datetime}
\usepackage{color,array,graphics}
\usepackage{enumerate}
\usepackage{eulervm}
\usepackage[margin=1in]{geometry}
\makeatletter
\DeclareRobustCommand*\cal{\@fontswitch\relax\mathcal}
\makeatother
\setlength{\textheight}{8.5in}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}
\voffset0.0in
\def\OR{\vee}
\def\AND{\wedge}
\def\imp{\rightarrow}
\def\math#1{$#1$}
\def\mand#1{$$#1$$}
\def\mld#1{\begin{equation}
#1
\end{equation}}
\def\eqar#1{\begin{eqnarray}
#1
\end{eqnarray}}
\def\eqan#1{\begin{eqnarray*}
#1
\end{eqnarray*}}
\def\cl#1{{\cal #1}}
\DeclareSymbolFont{AMSb}{U}{msb}{m}{n}
\DeclareMathSymbol{\N}{\mathbin}{AMSb}{"4E}
\DeclareMathSymbol{\Z}{\mathbin}{AMSb}{"5A}
\DeclareMathSymbol{\R}{\mathbin}{AMSb}{"52}
\DeclareMathSymbol{\Q}{\mathbin}{AMSb}{"51}
\DeclareMathSymbol{\I}{\mathbin}{AMSb}{"49}
\DeclareMathSymbol{\C}{\mathbin}{AMSb}{"43}
\begin{document}
\centerline{\bf \Large ASSIGNMENT 1}
\medskip
\section{Warm Up (do before recitation lab)}
\begin{enumerate}[(1)]
\item \math{p} and \math{q} are two propositions that are either \math{T} or
\math{F}. How many rows are there in the truth table of the
compound proposition \math{\neg (p\OR q)\AND\neg p}.
\item Give the truth table for the compound proposition above.
\item {\bf Theorem:} If integer \math{n\in\N} is even then \math{n^2} is even''.
What is wrong with the following proof:
{\sf\small
\begin{enumerate}[1.]
\item Suppose \math{n^2} is even.
\item Let \math{n} have a prime factorization \math{p_1^{q_1}p_2^{q_2}\cdots}.
\item So in the prime factorization of \math{n^2}, each prime appears
an even number of times, \math{n^2=p_1^{2q_1}p_2^{2q_2}\cdots}.
\item Since \math{n^2} is even, 2 is a prime factor of
\math{n^2}, so \math{n^2=2^{2q}\cdots}, with
\math{q>0}.
\item So \math{n=2^{q}\cdots}, with \math{q>0} and so \math{n} has
\math{2} as a factor and is therefore even as stated in the theorem.
\end{enumerate}
}
What does the above proof actually prove?
\item Is \math{n^2+n+41} prime for
\math{n=1,2,3,4,\ldots,10}. Does that mean that \math{n^2+n+41} is
prime for all \math{n\in\N}?
\item Let \math{F(x)} denote `\math{x} is a freshman' and
\math{M(x)} denote `\math{x} is a math major'.
Translate into sensible english:
\begin{enumerate}[(a)]
\item \math{\forall x(M(x)\imp\neg F(x))}
\item \math{\neg\exists x(M(x)\AND\neg F(x))}
\end{enumerate}
\end{enumerate}
\section{Recitation Lab (TA will work these out in lab)}
\begin{enumerate}[(1)]
\item
Using a truth table, determine whether these two compound propositions are
logically equivalent:
\mand{(p\imp q)\imp r\qquad\qquad p\imp(q\imp r).}
\item What is the negation of ``Jan is rich and happy''
\item{\bf [DNF]} Using only
\math{\neg,\AND,\OR}, give a compound proposition which has the following
truth table:
\mand{
\begin{array}{ccc|c}
p&q&r&\\\hline
T&T&T&F\\
T&T&F&T\\
T&F&T&F\\
T&F&F&F\\
F&T&T&T\\
F&T&F&T\\
F&F&T&F\\
F&F&F&F\\
\end{array}
}
\item What is the set \math{\Z\cap\overline\N\cap \cl{S}}, where the
set \math{S} is the set of integers which are perfect squares.
\item Prove that there are infinitely many primes.
\end{enumerate}
\section{Problems (hand these in)}
\begin{enumerate}[(1)]
\item Use a direct proof to show that the product of two odd numbers is odd.
\item Using only
\math{\neg,\AND,\OR}, give a compound proposition which has the following
truth table:
\mand{
\begin{array}{cc|c}
q&r&\\\hline
T&T&F\\
T&F&T\\
F&T&F\\
F&F&F\\
\end{array}
}
\item Compute the \emph{number} of positive
divisors of the following integers:
\mand{
\begin{array}{c}
6,8,12,18,30,\\
4,9,16,25,36
\end{array}
}
Formulate a conjecture that relates a property of the
number of divisors
of \math{n} to a property of \math{n}. Your conjecture should
at the very least agree with your data. State your conjecture
as a theorem. You do not have
to prove your theorem but be {\bf precise} in your statement of the theorem.
(You may want to define some convenient notation, for example
let \math{\phi(n)} be the number of positive divisors of \math{n}).
\item For the Ebola spreading model, a square gets infected if
at least two (non-diagonal) squares are infected. Show the final state of the
grid (who is infected) when the shaded in squares are
initially infected.
\begin{center}
FIGURE NOT INCLUDED
\end{center}
Can you find an arrangement of 5 initial infections that can eventually
infect the whole \math{6\times 6} square. What about with 6 initial infections?
Try the same game with a \math{4\times 4} square and a
\math{5\times 5} square.
Suppose the square is \math{n\times n} where \math{n\in\N}. Formulate a
conjecture that asserts the minimum number of initial
infections required to eventually infect the whole square.
State your conjecture as a theorem.
You do not have
to prove your theorem but be {\bf precise} in your statement of the theorem.
\item Prove or Disprove each of the following theorems:
{\bf Theorem.} If \math{x} and \math{y} are both \emph{irrational}, then
\math{x^y} is irrational.
\newline\hfill\emph{[Hint: We proved in class that
\math{\sqrt{2}} is irrational.]}
{\bf Theorem.} If \math{n} is an integer and \math{n^2} is divisible by
3, then \math{n} is divisible by 3.
\end{enumerate}
\end{document}