9780201726343

Discrete and Combinatorial Mathematics: An Applied Introduction

Ralph P. Grimaldi

5th Edition

This fifth edition continues to improve on the features that have made it the market leader. The text offers a flexible organization, enabling instructors to adapt the book to their particular courses. The book is both complete and careful, and it continues to maintain its emphasis on algorithms and applications. Excellent exercise sets allow students to perfect skills as

2-1

Basic Connectives and Truth Tables

Exercises

p.54

2-2

Logical Equivalence: The Law of Logic

Exercises

p.66

2-3

Logical Implication: Rules of Inference

Exercises

p.84

2-4

The Use of Quantifiers

Exercises

p.100

2-5

Quantifiers, Definitions, and the Proofs of Theorems

Exercises

p.116

2-6

Summary and Historical Review

Supplementary Exercises

p.120

3-1

Sets and Subsets

Exercises

p.134

3-2

Set Operations and the Laws of Set Theory

Exercises

p.146

3-3

Counting and Venn Diagrams

Exercises

p.150

3-4

A First Word on Probability

Exercises

p.156

3-5

The Axioms of Probability (Optional)

Exercises

p.164

3-6

Conditional Probability: Independence (Optional)

Exercises

p.173

3-7

Discrete Random Variables (Optional)

Exercises

p.185

3-8

Summary and Historical Review

Supplementary Exercises

p.189

4-1

The Well-Ordering Principle: Mathematical Induction

Exercises

p.208

4-2

Recursive Definitions

Exercises

p.219

4-3

The Division Algorithm: Prime Numbers

Exercises

p.230

4-4

The Greatest Common Divisor: The Euclidean Algorithm

Exercises

p.236

4-5

The Fundamentals Theorem of Arithmetic

Exercises

p.240

4-6

Summary and Historical Review

Supplementary Exercises

p.245

5-1

Cartesian Products and Relations

Exercises

p.252

5-2

Functions: Plain and One-to-One

Exercises

p.258

5-3

Onto Functions: Stirling Numbers of the Second Kind

Exercises

p.265

5-4

Special Functions

Exercises

p.272

5-5

The Pigeonhole Principle

Exercises

p.277

5-6

Function Composition and Inverse Functions

Exercises

p.288

5-7

Computational Complexity

Exercises

p.293

5-8

Analysis of Algorithms

Exercises

p.300

5-9

Summary and Historical Review

Supplementary Exercises

p.305

7-1

Relations Revisited: Properties of Relations

Exercises

p.343

7-2

Computer Recognition: Zero-One Matrices and Directed Graphs

Exercises

p.354

7-3

Partial orders: Hasse Diagrams

Exercises

p.364

7-4

Equivalence Relations and Partitions

Exercises

p.370

7-5

Finite State Machines: The Minimization Process

Exercises

p.376

7-6

Summary and Historical Review

Supplementary Exercises

p.378

9-1

Introductory Examples

Exercises

p.417

9-2

Definition and Examples: Calculating Techniques

Exercises

p.431

9-3

Partitions of Integers

Exercises

p.435

9-4

The Exponential Generating Function

Exercises

p.439

9-5

The Summation Operator

Exercises

p.442

9-6

Summary and Historical Review

Supplementary Exercises

p.445

10-1

The First-Order linear Recurrence Relation

Exercises

p.455

10-2

The Second-Order Linear Homogeneous Recurrence Relation with Constant Coefficients

Exercises

p.468

10-3

The Nonhomogeneous Recurrence Relation

Exercises

p.481

10-4

The Method of Generating Functions

Exercises

p.487

10-5

A Special kind of Nonlinear Recurrence Relation (Optional)

Exercises

p.493

10-6

Divide-and-Conquer Algorithms (Optional)

Exercises

p.504

10-7

Summary and Historical Review

Supplementary Exercises

p.508

11-1

Definitions and Examples

Exercises

p.518

11-2

Subgraphs, Complements, and Graph Isomorphism

Exercises

p.528

11-3

Vertex Degree: Euler Trails and Circuits

Exercises

p.537

11-4

Planar Graphs

Exercises

p.553

11-5

Hamilton Paths and Cycles

Exercises

p.562

11-6

Graph Coloring and Chromatic Polynomials

Exercises

p.571

11-7

Summary and Historical Review

Supplementary Exercises

p.576

12-1

Definitions, Properties, and Examples

Exercises

p.585

12-2

Rooted Trees

Exercises

p.603

12-3

Trees and Sorting

Exercises

p.609

12-4

Weighted Trees and Prefix Codes

Exercises

p.614

12-5

Biconnected Components and Articulation Points

Exercises

p.621

12-6

Summary and Historical Review

Supplementary Exercises

p.625

13-1

Dijkstra's Shortest-Path Algorithm

Exercises

p.638

13-2

Miinimal Spanning Trees: The Algorithms of Kruskal and Prim

Exercises

p.643

13-3

Transport Networks: The Max-Flow Min-Cut Theorem

Exercises

p.658

13-4

Matching Theory

Exercises

p.665

13-5

Summary and Historical Review

Supplementary Exercises

p.669

15-1

Switching Functions: Disjunctive and Conjunctive Normal Forms

Exercises

p.718

15-2

Gating Networks: Minimal Sums of Products: Karnaugh Maps

Exercises

p.727

15-3

Further Applications: Don't Care Conditions

Exercises

p.733

15-4

The Structure of a Bolean Algebra (Optional)

Exercises

p.741

15-5

Summary and Historical Review

Supplementary Exercises

p.743

16-1

Definition, Examples and Elementary Properties

Exercises

p.751

16-2

Homomorphisms, Isomorphisms, Cyclic Groups

Exercises

p.756

16-3

Cosets and Lagarange's Theorem

Exercises

p.758

16-4

The RSA Cryptosystem (Optional)

Exercises

p.761

16-5

Elements of Coding Theory

Exercises

p.765

16-7

The Parity-Check and Generator Matrices

Exercises

p.772

16-9

Hamming Matrices

Exercises

p.779

16-10

Counting and Equivalence: Burnside's Theorem

Exercises

p.785

16-11

The Cycle Index

Exercises

p.788

16-12

The Pattern Inventory: Polya's Method of Enumeration

Exercises

p.793

16-13

Summary and Historical Review

Supplementary Exercises

p.797

17-1

Polynomial Rings

Exercises

p.806

17-2

Irreducible Polynomials: Finite Fields

Exercises

p.813

17-3

Latin Squares

Exercises

p.819

17-4

Finite Geometries and Affine Planes

Exercises

p.824

17-5

Block Designs and Projective Planes

Exercises

p.829

17-6

Summary and Historical Review

Supplementary Exercises

p.832