9780130457912

For one-/two- semester, freshman courses in Discrete Mathematics. This carefully organized, very readable text covers every essential topic in discrete mathematics in a logical fashion. Placing each topic in context, it covers concepts associated with discrete mathematical systems that have applications in computer science, engineering, and mathematics. The author introduces more basic concepts at the freshman level than are found in other texts, in a simple, accessible form. Introductory material is balanced with extensive coverage of graphs, trees, recursion, algebra, theory of computing, and combinatorics. Extensive examples throughout the text reinforce concepts.

Preface

xi

Truth Tables, Logic, and Proofs

1

(50)

Statements and Connectives

1

(8)

Conditional Statements

9

(4)

Equivalent Statements

13

(6)

Axiomatic Systems: Arguments and Proofs

19

(10)

Completeness in Propositional Logic

29

(4)

Karnaugh Maps

33

(5)

Circuit Diagrams

38

(13)

Set Theory

51

(46)

Introduction to Sets

51

(3)

Set Operations

54

(7)

Venn Diagrams

61

(6)

Boolean Algebras

67

(5)

Relations

72

(8)

Partially Ordered Sets

80

(3)

Equivalence Relations

83

(4)

Functions

87

(10)

Logic, Integers, and Proofs

97

(44)

Predicate Calculus

97

(8)

Basic Concepts of Proofs and the Structure of Integers

105

(6)

Mathematical Induction

111

(8)

Divisibility

119

(5)

Prime Integers

124

(5)

Congruence Relations

129

(12)

Functions and Matrices

141

(27)

Special Functions

141

(5)

Matrices

146

(10)

Cardinality

156

(2)

Cardinals Continued

158

(10)

Algorithms and Recursion

168

(59)

The ``for'' Procedure and Algorithms for Matrices

168

(3)

Recursive Functions and Algorithms

171

(10)

Complexity of Algorithms

181

(6)

Sorting Algorithms

187

(9)

Prefix and Suffix Notation

196

(3)

Binary and Hexadecimal Numbers

199

(11)

Signed Numbers

210

(3)

Matrices Continued

213

(14)

Graphs, Directed Graphs, and Trees

227

(44)

Graphs

227

(5)

Directed Graphs

232

(5)

Trees

237

(5)

Instant Insanity

242

(2)

Euler Paths and Cycles

244

(6)

Incidence and Adjacency Matrices

250

(8)

Hypercubes and Gray Code

258

(13)

Number Theory

271

(19)

Sieve of Eratosthenes

271

(1)

Fermat's Factorization Method

272

(1)

The Division and Euclidean Algorithms

273

(5)

Continued Fractions

278

(5)

Convergents

283

(7)

Counting and Probability

290

(67)

Basic Counting Principles

290

(6)

Inclusion-Exclusion Introduced

296

(6)

Permutations and Combinations

302

(11)

Generating Permutations and Combinations

313

(3)

Probability Introduced

316

(6)

Generalized Permutations and Combinations

322

(4)

Permutations and Combinations with Repetition

326

(4)

Pigeonhole Principle

330

(4)

Probability Revisited

334

(12)

Bayes' Theorem

346

(2)

Markov Chains

348

(9)

Algebraic Structures

357

(34)

Partially Ordered Sets Revisited

357

(3)

Semigroups and Semilattices

360

(5)

Lattices

365

(6)

Groups

371

(6)

Groups and Homomorphisms

377

(6)

Linear Algebra

383

(8)

Number Theory Revisited

391

(25)

Integral Solutions of Linear Equations

391

(2)

Solutions of Congruence Equations

393

(3)

Chinese Remainder Theorem

396

(5)

Properties of the Function φ

401

(4)

Order of an Integer

405

(11)

Recursion Revisited

416

(39)

Homogeneous Linear Recurrence Relations

416

(9)

Nonhomogeneous Linear Recurrence Relations

425

(9)

Finite Differences

434

(3)

Factorial Polynomials

437

(10)

Sums of Differences

447

(8)

Counting Continued

455

(30)

Occupancy Problems

455

(4)

Catalan Numbers

459

(5)

General Inclusion-Exclusion and Derangements

464

(6)

Rook Polynomials and Forbidden Positions

470

(15)

Generating Functions

485

(31)

Defining the Generating Function (Optional)

485

(2)

Generating Functions and Recurrence Relations

487

(9)

Generating Functions and Counting

496

(5)

Partitions

501

(6)

Exponential Generating Functions

507

(9)

Graphs Revisited

516

(48)

Algebraic Properties of Graphs

516

(14)

Planar Graphs

530

(4)

Coloring Graphs

534

(9)

Hamiltonian Paths and Cycles

543

(7)

Weighted Graphs and Shortest Path Algorithms

550

(14)

Trees

564

(56)

Properties of Trees

564

(5)

Binary Search Trees

569

(6)

Weighted Trees

575

(7)

Traversing Binary Trees

582

(7)

Spanning Trees

589

(18)

Minimal Spanning Trees

607

(13)

Networks

620

(28)

Networks and Flows

620

(12)

Matching

632

(7)

Petri Nets

639

(9)

Theory of Computation

648

(41)

Regular Languages

648

(4)

Automata

652

(10)

Finite State Machines with Output

662

(10)

Grammars

672

(10)

Turing Machines

682

(7)

Theory of Codes

689

(19)

Introduction

689

(3)

Generator Matrices

692

(8)

Hamming Codes

700

(8)

Enumeration of Colors

708

(12)

Burnside's Theorem

708

(4)

Polya's Theorem

712

(8)

Rings, Integral Domains, and Fields

720

(30)

Rings and Integral Domains

720

(7)

Integral Domains

727

(3)

Polynomials

730

(6)

Algebra and Polynomials

736

(14)

Group and Semigroup Characters

750

(10)

Complex Numbers

750

(1)

Group Characters

751

(4)

Semigroup Characters

755

(5)

Applications of Number Theory

760

(19)

Application: Pattern Matching

760

(7)

Application: Hashing Functions

767

(5)

Application: Cryptography

772

(7)

Bibliography

779

Answers

1

(1)

Index

1

What is included with this book?

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.

As in the first edition, the purpose of this book is to present an extensive range and depth of topics in discrete mathematics and also work in a theme on how to do proofs. Proofs are introduced in the first chapter and continue throughout the book. Most students taking discrete mathematics are mathematics and computer science majors. Although the necessity of learning to do proofs is obvious for mathematics majors, it is also critical for computer science students to think logically. Essentially, a logical bug-free computer program is equivalent to a logical proof. Also, it is assumed in this book that it is easier to use (or at least not misuse) an application if one understands why it works. With few exceptions, the book is self-contained. Concepts are developed mathematically before they are seen in an applied context. Additions and alterations in the second edition: More coverage of proofs, especially in Chapter 1. Added computer science applications, such as a greedy algorithm for coloring the nodes of a graph, a recursive algorithm for counting the number of nodes on a binary search tree, or an efficient algorithm for computinga b modnfor very large values ofa, b,andn. An extensive increase in the number of problems in the first eight chapters. More problems are included that involve proofs. Additional material is included on matrices. Inclusion of finite states with output and Turing machines. True-False questions at the end of each chapter. Summary questions at the end of each chapter. A glossary at the end of each chapter. Functions and sequences are introduced earlier (in Chapter 2). Calculus is not required for any of the material in this book. College algebra is adequate for the basic chapters. However, although this book is self-contained, some of the remaining chapters require more mathematical maturity than do the basic chapters, so calculus is recommended more for giving maturity, than for any direct uses. This book is intended for either a one- or two-term course in discrete mathematics. The first eight chapters of this book provide a foundation in discrete mathematics and would be appropriate for a first-level course for freshmen or sophomores. These chapters are essentially independent, so that the instructor can pick the material he/she wishes to cover. The remainder of the book contains appropriate material for a second course in discrete mathematics. These chapters expand concepts introduced earlier and introduce numerous advanced topics. Topics are explored from different points of view to show how they may be used in different settings. The range of topics include: Logic--Including truth tables, propositional logic, predicate calculus, circuits, induction, and proofs. Set Theory--Including cardinality of sets, relations, partially ordered sets, congruence relations, graphs, directed graphs, and functions. Algorithms--Including complexity of algorithms, search and sort algorithms, the Euclidean algorithm, Huffman's algorithm, Prim's algorithms, Warshall's algorithm, the Ford-Fulkerson algorithm, the Floyd-Warshall algorithm, and Dijkstra's algorithms. Graph Theory--Including directed graphs, Euler cycles and paths, Hamiltonian cycles and paths, planar graphs, and weighted graphs. Trees--including binary search trees, weighted trees, tree transversal, Huffman's codes, and spanning trees. Combinatorics--including permutations, combinations, inclusion-exclusion, partitions, generating functions, Catalan numbers, Sterling numbers, Rook Polynomials, derangements, and enumeration of colors. Algebra--Including semigroups, groups, lattices, semilattices, Boolean algebras, rings, fields, integral domains,

Amazon no longer offers textbook rentals. We do!

Discrete Mathematics with Combinatorics

Discrete Mathematics with Combinatorics

0130457914

Summary

Table of Contents

Supplemental Materials

Excerpts