Applied Discrete Structures

Book Description:

Applied Discrete Structures is a two semester undergraduate text in discrete mathematics, focusing on the structural properties of mathematical objects. These include matrices, functions, graphs, trees, lattices and algebraic structures. The algebraic structures that are discussed are monoids, groups, rings, fields and vector spaces. Applied Discrete Structures has been approved by the American Institute of Mathematics as part of their Open Textbook Initiative. For more on open textbooks, visit http://www.aimath.org/textbooks/.

Table of Contents

Preface

Introduction

Chapter 1 Set Theory

1.1   Set Notation and Relations

1.2   Basic Set Operations

1.3   Cartesian Products and Power Sets

1.4   Binary Representation of Positive Integers

1.5   Summation Notation and Generalizations

Supplementary Exercises for Chapter 1

Chapter 2 Combinatorics

2.1   Basic Counting Techniques— the Rule of Products

2.2  Permutations

2.3  Partitions of Sets and the Laws of Addition

2.4  Combinations and the Binomial Theorem

Chapter 3 Logic

3.1   Propositions and Logical Operations

3.2  Truth Tables and Propositions Generated by a Set

3.3  Equivalence and Implication

3.4 The Laws of Logic

3.5  Mathematical Systems

3.6  Propositions Over a Universe

3.7 Mathematical Induction

3.8  Quantifiers

3.9 A Review of Methods of Proof

Supplementary Exercises for Chapter 3

Chapter 4 More on Sets

4.1 Methods of Proof for Sets

4.2  Laws of Set Theory

4.3  Minsets

4.4  The Duality Principle

Supplementary Exercises for Chapter 4

Applied Discrete Structures

Applied Discrete Structures by Alan Doerr & Kenneth Levasseur is licensed under a Creative Commons Attribution-Noncommercial-ShareAlike 3.0 United States License.

3Chapter 5 Introduction to Matrix Algebra

5.1   Basic Definition

5.2 Addition and Scalar Multiplication

5.3 Multiplication of Matrices

5.4  Special Types of Matrices

5.5  Laws of Matrix Algebra

5.6  Matrix Oddities

Supplementary Exercises for Chapter 5 

Chapter 6 Relations and Graphs

6.1 Basic Definitions

6.2  Graphs of Relations

6.3  Properties of Relations

6.4  Matrices of Relations

6.5  Closure Operations on Relations

Supplementary Exercises for Chapter 6

Chapter 7 Functions

7.1  Definition of a Function and Notation

7.2  Injective, Surjective, and Bijective Functions

7.3  Composition, Identity, and Inverses

Supplementary Exercises for Chapter 7

Chapter 8 Recursion and Recurrence Relations

8.1   The Many Faces of Recursion

8.2  Sequences

8.3  Recurrence Relations

8.4  Some Common Recurrence Relations

8.5 Generating Functions

8.6 Recursion and Computer Algebra Systems

Supplementary Exercises for Chapter 8

Chapter 9 Graph Theory

9.1 Graphs—a General Introduction

9.2 Data Structures and Computer Generation of Graphs

9.3  Connectivity

9.4  Traversals : Eulerian and Hamiltonian

9.5 Graph Optimization

9.6 Planarlty and Colorings

Supplementary Exercises for Chapter 9

Applied Discrete Structures

Applied Discrete Structures by Alan Doerr & Kenneth Levasseur is licensed under a Creative Commons Attribution-Noncommercial-ShareAlike 3.0 United States License.

4Chapter 10 Trees

10.1   What is a Tree?

10.2   Spanning Trees

10.3   Rooted Trees

10.4   Binary Trees

Supplementary Exercises for Chapter 10

Chapter 11 AlgebraIc Systems

11.1   Operations

11.2   Algebraic Systems

11.3   Some General Properties of Groups

11.4   Zn, the Integers Modulo n

11.5   Subsystems

11.6   Direct Products

11.7   Isomorphisms

11.8   Using Computers to Study Groups

Supplementary Exercises for Chapter 11

Chapter 12 More Matrix Algebra

12.1   Systems of Linear Equations

12.2   Matrix Inversion

12.3   An Introduction to Vector Spaces

12.4  The Diagonialization Process

12.5  Some Applications

Supplementary Exercises for Chapter 12 

Chapter 13 Boolean Algebra

13.1   Posets Revisited

13.2   Lattices

13.3   Boolean Algebras

13.4  Atoms of a Boolean Algebra

13.5   Finite Boolean Algebras as n-tuples of Zeros and Ones

13.6   Boolean Expressions

13.7 A Brief Introduction to the Application of Boolean Algebra to Switching Theory

Supplementary Exercises for Chapter 13

Applied Discrete Structures

Applied Discrete Structures by Alan Doerr & Kenneth Levasseur is licensed under a Creative Commons Attribution-Noncommercial-ShareAlike 3.0 United States License.

5Chapter 14 Monoids and Automata

14.1 Monoids

14.2   Free Monoids and Languages

14.3   Automata, Finite-state Machines

14.4   The Monoid of A Finite-state Machine

14.5   The Machine of A Monoid

Supplementary Exercises for Chapter 14

Chapter 15 Groups Theory and Applications

15.1   Cyclic Groups

15.2   Cosets and Factor Groups

15.3   Permutation Groups

15.4   Normal Subgroups and Group Homomorphisms

15.5   Coding Theory—Group Codes

Supplementary Exercises for Chapter 15

Chapter 16 An Introduction to Rings and Fields

16.1 Rings—Basic Definitions and Concepts

16.2   Fields

16.3   Polynomial Rings

16.4   Field Extensions

16.5   Power Series

Supplementary Exercises for Chapter 16

Solutions and Hints to Selected Exercises