Applied Discrete Structures [3rd ed] version 5, June 2018

Preface......Page 3
Contents......Page 5
Set Notation and Relations......Page 8
Basic Set Operations......Page 12
Cartesian Products and Power Sets......Page 18
Binary Representation of Positive Integers......Page 20
Summation Notation and Generalizations......Page 24
Basic Counting Techniques - The Rule of Products......Page 28
Permutations......Page 32
Partitions of Sets and the Law of Addition......Page 37
Combinations and the Binomial Theorem......Page 41
Propositions and Logical Operators......Page 48
Truth Tables and Propositions Generated by a Set......Page 53
Equivalence and Implication......Page 55
The Laws of Logic......Page 58
Mathematical Systems and Proofs......Page 60
Propositions over a Universe......Page 66
Mathematical Induction......Page 69
Quantifiers......Page 76
A Review of Methods of Proof......Page 80
Methods of Proof for Sets......Page 83
Laws of Set Theory......Page 88
Minsets......Page 91
The Duality Principle......Page 95
Basic Definitions and Operations......Page 96
Special Types of Matrices......Page 102
Laws of Matrix Algebra......Page 106
Matrix Oddities......Page 107
Basic Definitions......Page 110
Graphs of Relations on a Set......Page 113
Properties of Relations......Page 117
Matrices of Relations......Page 128
Closure Operations on Relations......Page 132
Definition and Notation......Page 137
Properties of Functions......Page 141
Function Composition......Page 145
The Many Faces of Recursion......Page 152
Sequences......Page 158
Recurrence Relations......Page 161
Some Common Recurrence Relations......Page 172
Generating Functions......Page 180
Graphs - General Introduction......Page 194
Data Structures for Graphs......Page 206
Connectivity......Page 210
Traversals: Eulerian and Hamiltonian Graphs......Page 217
Graph Optimization......Page 227
Planarity and Colorings......Page 240
What Is a Tree?......Page 250
Spanning Trees......Page 254
Rooted Trees......Page 260
Binary Trees......Page 267
Operations......Page 277
Algebraic Systems......Page 280
Some General Properties of Groups......Page 285
Greatest Common Divisors and the Inte- gers Modulo......Page 289
Subsystems......Page 297
Direct Products......Page 302
Isomorphisms......Page 309
Systems of Linear Equations......Page 315
Matrix Inversion......Page 324
An Introduction to Vector Spaces......Page 327
The Diagonalization Process......Page 335
Some Applications......Page 343
Linear Equations over the Integers Mod 2......Page 349
Posets Revisited......Page 352
Lattices......Page 356
Boolean Algebras......Page 358
Atoms of a Boolean Algebra......Page 362
-tuples of 0’s and 1’s......Page 366
Boolean Expressions......Page 367
Monoids......Page 372
Free Monoids and Languages......Page 375
Automata, Finite-State Machines......Page 382
The Monoid of a Finite-State Machine......Page 386
The Machine of a Monoid......Page 389
Cyclic Groups......Page 393
Cosets and Factor Groups......Page 399
Permutation Groups......Page 405
Normal Subgroups and Group Homomor- phisms......Page 414
Coding Theory, Group Codes......Page 421
Rings, Basic Definitions and Concepts......Page 427
Fields......Page 435
Polynomial Rings......Page 439
Field Extensions......Page 445
Power Series......Page 449
A.1 An Introduction to Algorithms......Page 454
A.2 The Invariant Relation Theorem......Page 458
Hints & Solutions......Page 461
Notation......Page 583
Refs......Page 586
Index......Page 589