Skip to main content\(\def\ds{\displaystyle}
\def\d{\displaystyle}
\def\N{\mathbb N}
\def\B{\mathbf{B}}
\def\Z{\mathbb Z}
\def\Q{\mathbb Q}
\def\R{\mathbb R}
\def\C{\mathbb C}
\def\F{\mathbb F}
\def\pow{\mathcal P}
\def\inv{^{-1}}
\def\iff{\leftrightarrow}
\def\Iff{\Leftrightarrow}
\def\land{\wedge}
\def\And{\bigwedge}
\def\entry{\entry}
\def\AAnd{\d\bigwedge\mkern-18mu\bigwedge}
\def\Vee{\bigvee}
\def\VVee{\d\Vee\mkern-18mu\Vee}
\def\imp{\rightarrow}
\def\Imp{\Rightarrow}
\def\Fi{\Leftarrow}
\def\var{\mbox{var}}
\def\Th{\mbox{Th}}
\def\entry{\entry}
\def\sat{\mbox{Sat}}
\def\con{\mbox{Con}}
\def\iffmodels{\bmodels\models}
\def\dbland{\bigwedge \!\!\bigwedge}
\def\dom{\mbox{dom}}
\def\rng{\mbox{range}}
\def\isom{\cong}
\def\st{\mid}
\def\divides{\mid}
\def\and{\text{ and }}
\def\lcm{\text{lcm}}
\def\modulus{\mathbin{\%}}
\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}{}}
\def\circleA{(-.5,0) circle (1)}
\def\circleAlabel{(-1.5,.6) node[above]{$A$}}
\def\circleB{(.5,0) circle (1)}
\def\circleBlabel{(1.5,.6) node[above]{$B$}}
\def\circleC{(0,-1) circle (1)}
\def\circleClabel{(.5,-2) node[right]{$C$}}
\def\twosetbox{(-2,-1.4) rectangle (2,1.4)}
\def\threesetbox{(-2.5,-2.4) rectangle (2.5,1.4)}
\def\ansfilename{practice-answers}
\def\shadowprops{{fill=black!50,shadow xshift=0.5ex,shadow yshift=0.5ex,path fading={circle with fuzzy edge 10 percent}}}
\newcommand{\hexbox}[3]{
\def\x{-cos{30}*\r*#1+cos{30}*#2*\r*2}
\def\y{-\r*#1-sin{30}*\r*#1}
\draw (\x,\y) node{#3};
}
\renewcommand{\bar}{\overline}
\newcommand{\card}[1]{\left| #1 \right|}
\newcommand{\twoline}[2]{\begin{pmatrix}#1 \\ #2 \end{pmatrix}}
\newcommand{\fixspacing}{\vspace{0pt plus 1filll}\mbox{}}
\usepackage{cancel}
\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\,}$}}}
\)
Appendix A Solutions to the exercises
1 Basic Objects and Symbols
1.1 Propositional Logic
Exercises
1.
2.
3.
4.
5.
6.
7.
8.
9.
1.2 Sets
Exercises
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
1.3 Relations and Functions
Exercises
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
2 Symbolic Logic and Proofs
2.1 Logical Equivalences
Exercises
1.
2.
3.
4.
6.
2.2 Application: Set Equivalences
Exercises
1.
2.
3.
4.
5.
2.3 Propositional Functions and Quantifiers
Exercises
1.
2.
3.
4.
5.
6.
2.4 Logical Arguments
Exercises
1.
2.
3.
6.
7.
8.
2.5 An introduction to proofs
Exercises
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
2.6 Chapter Review
Exercises
2.6.1.
2.6.2.
2.6.3.
2.6.4.
2.6.5.
2.6.6.
2.6.7.
2.6.8.
2.6.9.
2.6.10.
3 Some Classic Number Theory
3.1 Divisibility and Congruences
Exercises
1.
2.
3.
4.
5.
6.
7.
3.2 Prime Numbers
Exercises
1.
2.
3.
4.
5.
3.3 GCDs and The Euclidean Algorithm
Exercises
1.
2.
3.
4.
3.4 Multiplicative Inverses
Exercises
1.
2.
3.
4.
3.5 Modular exponentiation
Exercises
1.
3.6 Application: Encryption
Basic Cipher Examples
Exercises
1.
2.
3.
4 Sequences, Recurrence, and Induction
4.1 Sequences and Series
Exercises
1.
2.
3.
4.
5.
6.
4.2 Solving Recurrence Relations
Exercises
1.
2.
3.
4.
5.
6.
7.
8.
4.3 Mathematical Induction
Exercises
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
5 Counting Techniques
5.1 The Multiplicative and Additive Principles
Exercises
1.
2.
3.
4.
5.
7.
9.
11.
12.
14.
5.2 Permutations and Combinations
Exercises
1.
2.
4.
6.
7.
5.3 Combinatorial Proofs
Exercises
1.
2.
3.
4.
5.
6.
8.
9.
10.
5.4 Counting Fibonacci numbers with tiles
Exercises
1.
2.
