## An Introduction to Discrete
Mathematics

### Published by Innovative Textbooks

Designed for a freshman-sophomore course in Discrete Mathematics, with two
goals in mind: To acquaint students with a variety of mathematical concepts that
will be needed in the study of computer science; and to introduce students to
the "mathematical" way of thinking, that is, the ideas of a
definition, theorem and a proof. The book does not try to be encyclopedic in
coverage.

### Contents

- Sets, Functions and Proof Techniques
- The Language of Sets
- One-to-one Correspondences
- Countable and Uncountable Sets (Optional)
- Functions
- Inductive Proofs and Inductive Definitions
- Proof by Contradiction

- Logic and Logic Circuits
- Statements, Connectives, and Symbolic Language
- Truth Tables, Tautologies, and Contradictions
- Logical Equivalence
- Valid Arguments
- Boolean Functions and Disjunctive Normal Form
- Logic Circuits
- Karnaugh Maps

- Relations on Sets
- Relations
- Properties of Relations
- Equivalence Relations
- Partially Ordered Sets
- More on Partially Ordered Sets; Maximal and Minimal Elements and
Topological Sorting
- Order Isomorphisms

- Combinatorics - The Art of Counting
- Introduction
- The Multiplication Rule
- The Pigeonhole Principle
- Permutations
- More on Permutations
- Combinations
- Properties of Binomial Coefficients
- The Multinomial Coefficient
- An Introduction to Recurrence Relations
- Second Order Linear Homogeneous Recurrence Relations with Constant
Coefficients
- Second Order Linear Nonhomogeneous Recurrence Relations with Constant
Coefficients
- Generating Functions and Recurrence Relations

- More on Combinatorics
- Permutations with Repetitions
- Combinations with Repetitions
- Linear Equations with Unit Coefficients
- Distributing Balls into Boxes
- The Principle of Inclusion-Exclusion I
- The Principle of Inclusion-Exclusion II
- The Principle of Inclusion-Exclusion III
- An Introduction to Probability

- An Introduction to Graph Theory
- Introduction
- Paths and Connectedness
- Eulerian and Hamiltonian Graphs
- Graph Isomorphisms; Planar Graphs
- Trees; The Depth First Search
- Two Applications of Trees: Binary Search Trees and Huffman Codes
- Undirected Networks; The Minimal Spanning Tree Problem
- Directed Graphs; Strong Connectivity
- Directed Networks: The Shortest Path Problem
- Finite State Machines

**Second edition, 1989, ISBN 1-878015-29-X, 469 pp., Hardcover**

Return to the Math Books' Main Page

Return to the Home Page