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