Discrete and Combinatorial Mathematics

by Grimaldi, Ralph P.

• ISBN13: 9780201726343
• ISBN10: 0201726343
• Edition: 5th
• Format: Paperback
• Copyright: 2003-07-17
• Publisher: Pearson

Summary

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 they practice. This new edition continues to feature numerous computer science applications-making this the ideal text for preparing students for advanced study.

Table of Contents

Fundamentals of Discrete Mathematics

Fundamental Principles of Counting

The Rules of Sum and Product

Permutations

Combinations: The Binomial Theorem

Combinations with Repetition

The Catalan Numbers (Optional)

Summary and Historical Review

Fundamentals of Logic

Basic Connectives and Truth Tables

Logical Equivalence: The Laws of Logic

Logical Implication: Rules of Inference

The Use of Quantifiers

Quantifiers, Definitions, and the Proofs of Theorems

Summary and Historical Review

Set Theory

Sets and Subsets

Set Operations and the Laws of Set Theory

Counting and Venn Diagrams

A First Word on Probability

The Axioms of Probability (Optional)

Conditional Probability: Independence (Optional)

Discrete Random Variables (Optional)

Summary and Historical Review

Properties of the Integers: Mathematical Induction

The Well-Ordering Principle: Mathematical Induction

Recursive Definitions

The Division Algorithm: Prime Numbers

The Greatest Common Divisor: The Euclidean Algorithm

The Fundamental Theorem of Arithmetic

Summary and Historical Review

Relations and Functions

Cartesian Products and Relations

Functions: Plain and One-to-One

Onto Functions: Stirling Numbers of the Second Kind

Special Functions

The Pigeonhole Principle

Function Composition and Inverse Functions

Computational Complexity

Analysis of Algorithms

Summary and Historical Review

Languages: Finite State Machines

Language: The Set Theory of Strings

Finite State Machines: A First Encounter

Finite State Machines: A Second Encounter

Summary and Historical Review

Relations: The Second Time Around

Relations Revisited: Properties of Relations

Computer Recognition: Zero-One Matrices and Directed Graphs

Partial Orders

Table of Contents provided by Publisher. All Rights Reserved.