Skip to main content\(\newcommand{\identity}{\mathrm{id}}
\newcommand{\notdivide}{{\not{\mid}}}
\newcommand{\notsubset}{\not\subset}
\newcommand{\lcm}{\operatorname{lcm}}
\newcommand{\gf}{\operatorname{GF}}
\newcommand{\inn}{\operatorname{Inn}}
\newcommand{\aut}{\operatorname{Aut}}
\newcommand{\Hom}{\operatorname{Hom}}
\newcommand{\cis}{\operatorname{cis}}
\newcommand{\chr}{\operatorname{char}}
\newcommand{\Null}{\operatorname{Null}}
\renewcommand{\vec}[1]{\mathbf{#1}}
\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 D Hints and Solutions to Selected Exercises
For the most part, solutions are provided here for odd-numbered exercises.
1 Set Theory
1.1 Set Notation and Relations
1.1.3 Exercises
1.1.3.1.
1.1.3.3.
1.1.3.5.
1.2 Basic Set Operations
1.2.4 Exercises
1.2.4.1.
1.2.4.3.
1.2.4.5.
1.2.4.7.
1.3 Cartesian Products and Power Sets
1.3.4 Exercises
1.3.4.1.
1.3.4.3.
1.3.4.5.
1.3.4.7.
1.3.4.9.
1.4 Binary Representation of Positive Integers
1.4.3 Exercises
1.4.3.1.
1.4.3.3.
1.4.3.5.
1.4.3.7.
1.5 Summation Notation and Generalizations
1.5.3 Exercises
1.5.3.1.
1.5.3.3.
1.5.3.5.
1.5.3.7.
1.5.3.9.
2 Combinatorics
2.1 Basic Counting Techniques - The Rule of Products
2.1.3 Exercises
2.1.3.1.
2.1.3.3.
2.1.3.5.
2.1.3.7.
2.1.3.9.
2.1.3.11.
2.1.3.13.
2.1.3.15.
2.1.3.17.
2.1.3.19.
2.2 Permutations
2.2.2 Exercises
2.2.2.1.
2.2.2.3.
2.2.2.5.
2.2.2.7.
2.2.2.9.
2.2.2.11.
2.3 Partitions of Sets and the Law of Addition
2.3.3 Exercises
2.3.3.1.
2.3.3.3.
2.3.3.5.
2.3.3.7.
2.3.3.9.
2.3.3.11.
2.4 Combinations and the Binomial Theorem
2.4.4 Exercises
2.4.4.1.
2.4.4.2.
2.4.4.3.
2.4.4.5.
2.4.4.7.
2.4.4.9.
2.4.4.11.
2.4.4.13.
2.4.4.15.
2.4.4.17.
3 Logic
3.1 Propositions and Logical Operators
3.1.3 Exercises
3.1.3.1.
3.1.3.3.
3.1.3.5.
3.2 Truth Tables and Propositions Generated by a Set
3.2.3 Exercises
3.2.3.1.
3.2.3.3.
3.2.3.5.
3.3 Equivalence and Implication
3.3.5 Exercises
3.3.5.1.
3.3.5.3.
3.3.5.5.
3.3.5.7.
3.3.5.9.
3.4 The Laws of Logic
3.4.2 Exercises
3.4.2.1.
3.4.2.3.
3.5 Mathematical Systems and Proofs
3.5.4 Exercises
3.5.4.1.
3.5.4.3.
3.5.4.5.
3.5.4.7.
3.6 Propositions over a Universe
3.6.3 Exercises
3.6.3.1.
3.6.3.2.
3.6.3.3.
3.6.3.5.
3.6.3.7.
3.7 Mathematical Induction
3.7.4 Exercises
3.7.4.1.
3.7.4.3.
3.7.4.5.
3.7.4.6.
3.7.4.7.
3.7.4.9.
3.7.4.11.
3.7.4.12.
3.7.4.13.
3.8 Quantifiers
3.8.5 Exercises
3.8.5.1.
3.8.5.3.
3.8.5.5.
3.8.5.6.
3.8.5.7.
3.8.5.9.
3.8.5.10.
3.8.5.11.
3.9 A Review of Methods of Proof
3.9.3 Exercises
3.9.3.1.
3.9.3.3.
3.9.3.5.
4 More on Sets
4.1 Methods of Proof for Sets
4.1.5 Exercises
4.1.5.1.
4.1.5.3.
4.1.5.5.
4.1.5.6.
4.2 Laws of Set Theory
4.2.4 Exercises
4.2.4.1.
4.2.4.3.
4.2.4.5. Hierarchy of Set Operations.
4.3 Minsets
4.3.3 Exercises
4.3.3.1.
4.3.3.3.
4.3.3.5.
4.3.3.7.
4.4 The Duality Principle
4.4.2 Exercises
4.4.2.1.
4.4.2.3.
4.4.2.5.
5 Introduction to Matrix Algebra
5.1 Basic Definitions and Operations
5.1.4 Exercises
5.1.4.1.
5.1.4.3.
5.1.4.5.
5.1.4.7.
5.2 Special Types of Matrices
5.2.3 Exercises
5.2.3.1.
5.2.3.3.
5.2.3.5. Linearity of Determinants.
5.2.3.7.
5.2.3.9.
5.3 Laws of Matrix Algebra
5.3.3 Exercises
5.3.3.1.
5.3.3.3.
5.4 Matrix Oddities
5.4.2 Exercises
5.4.2.1.
5.4.2.3.
5.4.2.5.
5.4.2.7.
6 Relations
6.1 Basic Definitions
6.1.4 Exercises
6.1.4.1.
6.1.4.3.
6.1.4.5.
6.1.4.7.
6.2 Graphs of Relations on a Set
6.2.2 Exercises
6.2.2.1.
6.2.2.3.
6.3 Properties of Relations
6.3.4 Exercises
6.3.4.1.
6.3.4.2.
6.3.4.3.
6.3.4.5.
6.3.4.7.
6.3.4.9.
6.3.4.11.
6.4 Matrices of Relations
6.4.3 Exercises
6.4.3.1.
6.4.3.3.
6.4.3.5.
6.4.3.7.
6.4.3.9.
6.5 Closure Operations on Relations
6.5.3 Exercises
6.5.3.3.
6.5.3.5.
6.5.3.7.
7 Functions
7.1 Definition and Notation
7.1.5 Exercises
7.1.5.1.
7.1.5.3.
7.1.5.5.
7.2 Properties of Functions
7.2.3 Exercises
7.2.3.1.
7.2.3.3.
7.2.3.5.
7.2.3.7.
7.2.3.9.
7.2.3.11.
7.2.3.13.
7.3 Function Composition
7.3.4 Exercises
7.3.4.1.
7.3.4.3.
7.3.4.5.
7.3.4.7.
7.3.4.9.
7.3.4.11.
7.3.4.12.
7.3.4.13.
7.3.4.15.
8 Recursion and Recurrence Relations
8.1 The Many Faces of Recursion
8.1.8 Exercises
8.1.8.1.
8.1.8.3.
8.1.8.5.
8.2 Sequences
8.2.3 Exercises
8.2.3.1.
8.2.3.3.
8.2.3.5.
8.3 Recurrence Relations
8.3.5 Exercises
8.3.5.1.
8.3.5.3.
8.3.5.5.
8.3.5.7.
8.3.5.9.
8.3.5.11.
8.3.5.13.
8.3.5.15.
8.4 Some Common Recurrence Relations
8.4.5 Exercises
8.4.5.1.
8.4.5.3.
8.4.5.4.
8.4.5.5.
8.4.5.7.
8.5 Generating Functions
8.5.7 Exercises
8.5.7.1.
8.5.7.3.
8.5.7.5.
8.5.7.7.
8.5.7.9.
9 Graph Theory
9.1 Graphs - General Introduction
9.1.5 Exercises
9.1.5.1.
9.1.5.3.
9.1.5.5.
9.1.5.7.
9.1.5.9.
9.2 Data Structures for Graphs
9.2.3 Exercises
9.2.3.1.
9.2.3.3.
9.3 Connectivity
9.3.6 Exercises
9.3.6.1.
9.3.6.3.
9.3.6.5.
9.3.6.7.
9.4 Traversals: Eulerian and Hamiltonian Graphs
9.4.3 Exercises
9.4.3.1.
9.4.3.3.
9.4.3.5.
9.4.3.7.
9.4.3.8.
9.4.3.9.
9.4.3.11.
9.5 Graph Optimization
9.5.5 Exercises
9.5.5.1.
9.5.5.3.
9.5.5.5.
9.5.5.7.
9.5.5.9.
9.6 Planarity and Colorings
9.6.3 Exercises
9.6.3.1.
9.6.3.3.
9.6.3.5.
9.6.3.7.
9.6.3.9.
9.6.3.11.
9.6.3.13.
10 Trees
10.1 What Is a Tree?
10.1.3 Exercises
10.1.3.1.
10.1.3.3.
10.1.3.5.
10.2 Spanning Trees
10.2.4 Exercises
10.2.4.1.
10.2.4.3.
10.2.4.5.
10.3 Rooted Trees
10.3.4 Exercises
10.3.4.1.
10.3.4.3.
10.4 Binary Trees
10.4.6 Exercises
10.4.6.1.
10.4.6.3.
10.4.6.5.
10.4.6.7.
10.4.6.8.
11 Algebraic Structures
11.1 Operations
11.1.4 Exercises
11.1.4.1.
11.1.4.3.
11.1.4.5.
11.2 Algebraic Systems
11.2.4 Exercises
11.2.4.1.
11.2.4.3.
11.2.4.5.
11.2.4.7.
11.2.4.8.
11.3 Some General Properties of Groups
11.3.3 Exercises
11.3.3.1.
11.3.3.3.
11.3.3.5.
11.4 Greatest Common Divisors and the Integers Modulo \(n\)
11.4.2 The Euclidean Algorithm
Investigation 11.4.1.
11.4.6 Exercises
11.4.6.1.
11.4.6.3.
11.4.6.5.
11.4.6.7.
11.4.6.10.
11.4.6.11.
11.4.6.12.
11.4.6.13.
11.5 Subsystems
11.5.5 Exercises
11.5.5.1.
11.5.5.3.
11.5.5.5.
11.5.5.7.
11.6 Direct Products
11.6.3 Exercises
11.6.3.1.
11.6.3.3. Algebraic properties of the \(n\)-cube.
11.6.3.5.
11.7 Isomorphisms
11.7.4 Exercises
11.7.4.1.
11.7.4.3.
11.7.4.5.
11.7.4.7.
11.7.4.11.
11.7.4.13.
12 More Matrix Algebra
12.1 Systems of Linear Equations
12.1.7 Exercises
12.1.7.1.
12.1.7.3.
12.1.7.5.
12.1.7.7.
12.2 Matrix Inversion
12.2.3 Exercises
12.2.3.3.
12.2.3.5.
12.3 An Introduction to Vector Spaces
12.3.3 Exercises
12.3.3.3.
12.3.3.7.
12.3.3.9.
12.3.3.11.
12.3.3.13.
12.4 The Diagonalization Process
12.4.4 Exercises
12.4.4.1.
12.4.4.3.
12.4.4.5.
12.4.4.7.
12.5 Some Applications
12.5.5 Exercises
12.5.5.4.
12.5.5.5.
12.5.5.7.
12.6 Linear Equations over the Integers Mod 2
12.6.2 Exercises
12.6.2.1.
12.6.2.2.
12.6.2.3.
13 Boolean Algebra
13.1 Posets Revisited
Exercises
13.1.1.
13.1.3.
13.1.5.
13.1.7.
13.2 Lattices
Exercises
13.2.5.
13.3 Boolean Algebras
Exercises
13.3.1.
13.3.3.
13.3.5.
13.3.7.
13.4 Atoms of a Boolean Algebra
Exercises
13.4.1.
13.4.3.
13.4.5.
13.4.7.
13.4.8.
13.5 Finite Boolean Algebras as \(n\)-tuples of 0’s and 1’s
Exercises
13.5.1.
13.5.3.
13.6 Boolean Expressions
Exercises
13.6.1.
13.6.3.
13.7 A Brief Introduction to Switching Theory and Logic Design
Exercises
13.7.1.
13.7.2.
13.7.3.
14 Monoids and Automata
14.1 Monoids
Exercises
14.1.1.
14.1.3.
14.1.5.
14.2 Free Monoids and Languages
Exercises
14.2.1.
14.2.3.
14.2.5.
14.2.7.
14.2.9.
14.3 Automata, Finite-State Machines
Exercises
14.3.1.
14.3.3.
14.3.5.
14.4 The Monoid of a Finite-State Machine
Exercises
14.4.1.
14.4.3.
14.5 The Machine of a Monoid
Exercises
14.5.1.
15 Group Theory and Applications
15.1 Cyclic Groups
Exercises
15.1.1.
15.1.3.
15.1.5.
15.1.7.
15.1.9.
15.2 Cosets and Factor Groups
Exercises
15.2.1.
15.2.3.
15.2.5.
15.3 Permutation Groups
15.3.5 Exercises
15.3.5.1.
15.3.5.3.
15.3.5.5.
15.3.5.7.
15.3.5.9.
15.3.5.13.
15.4 Normal Subgroups and Group Homomorphisms
15.4.3 Exercises
15.4.3.1.
15.4.3.3.
15.4.3.5.
15.4.3.7.
15.4.3.9.
15.5 Coding Theory, Linear Codes
15.5.4 Exercises
15.5.4.1.
15.5.4.3.
15.5.4.5.
15.5.4.7.
15.5.4.8.
16 An Introduction to Rings and Fields
16.1 Rings, Basic Definitions and Concepts
16.1.6 Exercises
16.1.6.1.
16.1.6.3.
16.1.6.5.
16.1.6.7.
16.1.6.9.
16.1.6.11.
16.1.6.13.
16.2 Fields
Exercises
16.2.5.
16.2.7.
16.3 Polynomial Rings
Exercises
16.3.1.
16.3.3.
16.3.5.
16.3.7.
16.3.9.
16.3.11.
16.4 Field Extensions
Exercises
16.4.1.
16.4.3.
16.4.5.
16.5 Power Series
16.5.3 Exercises
16.5.3.5.
16.5.3.7.
