Discrete Mathematics and Its Applications

by Rosen, Kenneth

• ISBN13: 9780073229720
• ISBN10: 0073229725
• Edition: 6th
• Format: Hardcover
• Copyright: 2006-07-26
• Publisher: McGraw-Hill Education

Summary

Discrete Mathematics and its Applications, Sixth Edition, is intended for one- or two-term introductory discrete mathematics courses taken by students from a wide variety of majors, including computer science, mathematics, and engineering. This renowned best-selling text, which has been used at over 500 institutions around the world, gives a focused introduction to the primary themes in a discrete mathematics course and demonstrates the relevance and practicality of discrete mathematics to a wide a wide variety of real-world applications...from computer science to data networking, to psychology, to chemistry, to engineering, to linguistics, to biology, to business, and to many other important fields.

Table of Contents

Preface

The MathZone Companion Website To the Student

The Foundations: Logic and Proofs

Propositional Logic

Propositional Equivalences

Predicates and Quantifiers

Nested Quantifiers

Rules of Inference

Introduction to Proofs

Proof Methods and Strategy End-of-Chapter Material

Basic Structures: Sets, Functions, Sequences and Sums

Sets

Set Operations

Functions

Sequences and Summations End-of-Chapter Material

The Fundamentals: Algorithms, the Integers, and Matrices

Algorithms

The Growth of Functions

Complexity of Algorithms

The Integers and Division

Primes and Greatest Common Divisors

Integers and Algorithms

Applications of Number Theory

Matrices End-of-Chapter Material

Induction and Recursion

Mathematical Induction

Strong Induction and Well-Ordering

Recursive Definitions and Structural Induction

Recursive Algorithms

Program Correctness End-of-Chapter Material

Counting

The Basics of Counting

The Pigeonhole Principle

Permutations and Combinations

Binomial Coefficients

Generalized Permutations and Combinations

Generating Permutations and Combinations End-of-Chapter Material

Discrete Probability

An Introduction to Discrete Probability

Probability Theory

Bayes’ Theorem

Expected Value and Variance End-of-Chapter Material

Advanced Counting Techniques

Recurrence Relations

Solving Linear Recurrence Relations

Divide-and-Conquer Algorithms and Recurrence elations

Generating Functions

Inclusion-Exclusion

Applications of Inclusion-Exclusion End-of-Chapter Material

Relations

Relations and Their Properties

n-ary Relations and Their Applications

Representing Relations

Closures of Relations

Equivalence Relations

Partial Orderings End-of-Chapter Material

Graphs

Graphs and Graph Models

Graph Terminology and Special Types of Graphs

Representing Graphs and Graph Isomorphism

Connectivity

Euler and Hamilton Paths

Shortest-Path Problems

Planar Graphs

Graph Coloring End-of-Chapter Material

Trees

Introduction to Trees

Applications of Trees

Tree Traversal

Spanning Trees

Minimum Spanning Trees End-of-Chapter Material

Boolean Algebra

Boolean Functions

Representing Boolean Functions

Logic Gates

Minimization of Circuits End-of-Chapter Material

Modeling Computation

Languages and Grammars

Finite-State Machines with Output

Finite-State Machines with No Output

Language Recognition

Turing Machines End-of-Chapter Material

Appendixes

Axioms for the Real Numbers and the Positive Integers

Exponential and Logarithmic Functions

Pseudocode Suggested Readings

Answers to Odd-Numbered Exercises

Photo Credits

Index of Biographies

Index

Table of Contents provided by Publisher. All Rights Reserved.