Skip to main content
Contents Index Dark Mode Prev Up Next \({\labelitemi}{$\diamond$}
\def\arraystretch{1.5}
\newcommand{\contentsfinish}{}
\newcommand{\separator}{\begin{center}\rule{\columnwidth}{\arrayrulewidth}\end{center}}
\newcommand{\tosay}[1]{\begin{center}\text{\fbox{\scriptsize{#1}}}\end{center}}
\renewcommand{\cftsecfont}{}
\renewcommand{\cftsecpagefont}{}
\renewcommand{\descriptionlabel}[1]{\hspace{\labelsep}\smallcaps{#1}}
\def\oldequation{\equation}
\def\endoldequation{\endequation}
\newcommand{\nl}{
}
\newcommand{\runin}[1]{\textls[50]{\otherscshape #1}}
\renewcommand{\sectionmark}[1]{}
\renewcommand{\subsectionmark}[1]{}
\renewcommand{\sectionmark}[1]{\markboth{{\thesection}.\ \smallcaps{#1}}{\thesection.\ \smallcaps{#1}}}
\renewcommand{\subsectionmark}[1]{}
\renewcommand{\epsilon}{\varepsilon}
\renewcommand{\sectionmark}[1]{\markboth{{\scriptsize\thesection}.\ \smallcaps{#1}}{}}
\renewcommand{\subsectionmark}[1]{}
\newcommand{\makedefaultsection}[2][true]{
}
\newcommand{\timestamp}{{\color{red}Last updated: {\currenttime\ (UTC), \today}}}
\renewcommand{\le}{\leqslant}
\renewcommand{\leq}{\leqslant}
\renewcommand{\geq}{\geqslant}
\renewcommand{\ge}{\geqslant}
\newcommand{\ideal}[1]{\left\langle\, #1 \,\right\rangle}
\newcommand{\subgp}[1]{\left\langle\, #1 \,\right\rangle}
\def\p{\varphi}
\def\isomorphic{\cong}
\def\imp{\to}
\def\iff{\leftrightarrow}
\def\Gal{\text{Gal}}
\def\im{\text{im}}
\def\ran{\text{ran}}
\def\normal{\vartriangleleft}
\renewcommand{\qedsymbol}{$\checkmark$}
\def\lcm{{\text{lcm}\,}}
\newcommand{\q}[1]{{\color{red} {#1}}}
\newcommand{\startimportant}[1]{\end{[{Hint:} #1]\end}}
\renewcommand{\textcircled}[1]{\tikz[baseline=(char.base)]{\node[shape=circle,draw,inner sep=2pt,color=red] (char) {#1};}}
\newcommand{\crossout}[1]{\tikz[baseline=(char.base)]{\node[mynode, cross out,draw] (char) {#1};}}
\newcommand{\set}[1]{\left\{ {#1} \right\}}
\newcommand{\setof}[2]{{\left\{#1\,\colon\,#2\right\}}}
\def\C{{\mathbb C}}
\def\Z{{\mathbb Z}}
\def\bF{{\mathbb F}}
\def\Q{{\mathbb Q}}
\def\N{{\mathbb N}}
\def\U{{\mathcal U}}
\def\pow{{\mathcal P}}
\def\R{{\mathbb R}}
\newcommand{\h}[1]{{\textbf{#1}}}
\def\presnotes{}
\renewcommand{\d}{\displaystyle}
\newcommand{\N}{\mathbb N}
\newcommand{\B}{\mathbf B}
\newcommand{\Z}{\mathbb Z}
\newcommand{\Q}{\mathbb Q}
\newcommand{\R}{\mathbb R}
\newcommand{\C}{\mathbb C}
\newcommand{\U}{\mathcal U}
\newcommand{\pow}{\mathcal P}
\newcommand{\inv}{^{-1}}
\newcommand{\st}{:}
\renewcommand{\iff}{\leftrightarrow}
\newcommand{\Iff}{\Leftrightarrow}
\newcommand{\imp}{\rightarrow}
\newcommand{\Imp}{\Rightarrow}
\newcommand{\isom}{\cong}
\renewcommand{\bar}{\overline}
\newcommand{\card}[1]{\left| #1 \right|}
\newcommand{\twoline}[2]{\begin{pmatrix}#1 \\ #2 \end{pmatrix}}
\newcommand{\vtx}[2]{node[fill,circle,inner sep=0pt, minimum size=4pt,label=#1:#2]{}}
\newcommand{\va}[1]{\vtx{above}{#1}}
\newcommand{\vb}[1]{\vtx{below}{#1}}
\newcommand{\vr}[1]{\vtx{right}{#1}}
\newcommand{\vl}[1]{\vtx{left}{#1}}
\renewcommand{\v}{\vtx{above}{}}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\definecolor{fillinmathshade}{gray}{0.9}
\newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}}
\)
Section 1.2 Logic Review
In basic proof logic, we will usually be proving a statement of the form
If
\(P\) is true, then
\(Q\) is also true.
Example 1 .
Prove that if
\(x\) is an even integer, then
\(x^2\) is an even integer.
However, there are more interesting examples of how to prove things. Recall the
converse of the generic statement:
If
\(Q\) is true, then
\(P\) is true
and the
contrapositive thereof,
If
\(Q\) is not true, then
\(P\) is not true.
Example 2 .
State the converse of
Example 1 , and then its contrapositive. Prove that final statement.
In normal mathematical logic, we say that the contrapositive and the original statement are
logically equivalent . So you should use whichever you find useful in proving theorems!
However, that isn’t the case with the
converse and the original statement.
Example 3 .
Take the statement “If
\(n\) is a prime number, then
\(n\) is a positive integer” and give a reason why it is true, but its converse is false.
In
Example 1 and
Example 2 , we have the highly unusual situation where both
\(P \Rightarrow Q\) and
\(Q \Rightarrow P\) are both true. We say this is a
biconditional statement and write
\(P\Leftrightarrow Q\text{,}\) saying
\(P\) is true if and only if
\(Q\) is true,
or “
\(P\) is necessary and sufficient for
\(Q\) ”, or some variation thereon.
There are a few other tricky logic issues that we should definitely practice.
Or is a word that means many things. In most of math (and here), “
\(A\) or
\(B\) ” means “
\(A\) or
\(B\) or
both ”. This is important in statements like
If
\(x\) or
\(y\) is even, then
\(xy\) is also even.
Example 4 .
Come up with a theorem which is
not true with this meaning of “or” but
is true with the so-called
exclusive or .
Example 5 .
Restate the statements below as accurately as possible in terms of logic, and then do all of the following with as few double negatives as you can, using natural negations where possible:
Negate the statement, “All professors at my university who live in my town are tall and blond.”
Negate the statement, “There exists a student at my university who does not live in my town,” in the most natural way possible (i.e., without double negatives).
Give the contrapositive of the statement, “If there exists a professor at my university who is neither tall nor blond, then all students at my university are young and short.”
Problem 6 .
Formally negate the statement, “For every positive number
\(p\text{,}\) there is a positive integer
\(N\) such that if an integer
\(I\) is greater than
\(N\text{,}\) then the reciprocal of
\(I\) is less than
\(p\text{,}\) ” with as few negatives and as naturally as possible. (But please don’t try to prove it!)
