Discrete Mathematics for Computer Science

x e A x is an element ofA 1. Sets, Proof Templates, and Induction

x f A x is not an element ofA 1.

Ix x E A and P(x)} Set notation 1.

2 Integers 1.1. N Natural numbers 1.1.1l

Q Rationals 1.1.

R Real numbers I.1.

A = B Sets A and B are equal 1.1.

A C B A is a subset of B 1.1.

A g B A is nota subset of B 1.1.

A C B A is a proper subset of B 1.1.

A 5 B A is nota proper subset of B 1.1.

b=•a bimplies a i.1.

a b a if and only if b 1.1.

AUB A union B 1.3.

AFnB A intersect B 1.3.

UX Generalized union of family of sets X 1.3.

nX Generalized intersection of family of sets X 1.3.

Um Xi Xm U ...UXn 1.3.

nt=Mxi Xm n n Xn 1.3.

A - B Elements of A not in B 1.3.

A Elements not in A 1.3.

A D B (A U B) - (A n B) 1.3.

P(X) Power set of X 1.3.

X x Y Product of X and Y 1.3.

x A y Meet ofx and y 1.3.

x v y Join ofx and y 1.3.

-x Complement of x 1.3.

T Top 1.

I Bottom 1.3.

JAI Cardinality of A 1.5.
- Si a,, + " -". + a,, 1.7.

"--p Not p 2. Formal Logic

pAq p and q 2.

pvq p or q 2.

p q p implies q 2.

p q p is equivalent to q 2.

S X S logically implies X 2.3.

P 3 AKP Conjecture about complexity 2.5.

(Vx)P(x) For all x, P(x) 2.7.

(3x)P(x) There exists an x such that P(x) 2.7.

(VxE V)P(x) For all X EV, P(x) 2.7.

(3x E V)P(x) There exists an x E V such that P(x) 2.7.

A[i ..j] Array with elements Ail, ..., A[j] 2.7.

1 Sheffer stroke 2.

V Exclusive or 2.

4, Pierce arrow 2.

(x, y) E R or xRy x is R-related to y 3.

R-1 The inverse of the relation R 3.2.

RoS Composition of relations R and S 3.2.

R+ U°° Ri 3.4.

R* URO R' 3.4.

n =- m(modp) n - m = kp for some k E N 3.

Idx Identity relation 3.

Lex Less than or equal relation 3.

Gtx Greater than relation 3.

Gex Greater than or equal relation 3.

[x] Equivalence class of x 3.

min m divides n 3.8.

R D. S Equijoin of relations R and S 3.10.

CHAPTER

1.1 Basic Definitions Sets, Proof Templates, and Induction
- 1.1.1 Describing Sets Mathematically
- 1.1.2 Set Membership
- 1.1.3 Equality of Sets
- 1.1.4 Finite and Infinite Sets
- 1.1.5 Relations Between Sets
- 1.1.6 Venn Diagrams
- 1.1.7 Templates

1.2 Exercises

1.3 Operations on Sets
- 1.3.1 Union and Intersection
- 1.3.2 Set Difference, Complements, and DeMorgan's Laws
- 1.3.3 New Proof Templates
- 1.3.4 Power Sets and Products
- 1.3.5 Lattices and Boolean Algebras

1.4 Exercises

1.5 The Principle of Inclusion-Exclusion
- 1.5.1 Finite Cardinality
- 1.5.2 Principle of Inclusion-Exclusion for Two Sets
- 1.5.3 Principle of Inclusion-Exclusion for Three Sets
- 1.5.4 Principle of Inclusion-Exclusion for Finitely Many Sets

1.6 Exercises
- 1.7 Mathematical Induction viii Contents
  - 1.71 A First Form of Induction
  - 1.72 A Template for Constructing Proofs by Induction
  - 1.73 Application: Fibonacci Numbers
  - 1.74 Application: Size of a Power Set
  - 1.75 Application: Geometric Series
- 1.8 Program Correctness
  - 1.8.1 Pseudocode Conventions
  - 1.8.2 An Algorithm to Generate Perfect Squares
    - 1.8.3 Two Algorithms for Computing Square Roots
- 1.9 Exercises
- 1.10 Strong Form of Mathematical Induction
  - 1.10.1 Using the Strong Form of Mathematical Induction
  - 1.10.2 Application: Algorithm to Compute Powers
  - 1.10.3 Application: Finding Factorizations
  - 1.10.4 Application: Binary Search
- 1.11 Exercises
- 1.12 Chapter Review
  - 1.12.1 Summary
  - 1.12.2 Starting to Review
  - 1.12.3 Review Questions
  - 1.12.4 Using Discrete Mathematics in Computer Science

CHAPTER

Formal Logic

2.1 Introduction to Propositional Logic
- 2.1.1 Formulas
- 2.1.2 Expression Trees for Formulas
- 2.1.3 Abbreviated Notation for Formulas
- 2.1.4 Using Gates to Represent Formulas

2.2 Exercises

2.3 Truth and Logical Truth
- 2.3.1 Tautologies
  - 2.3.2 Substitutions into Tautologies Contents ix
  - 2.3.3 Logically Valid Inferences
  - 2.3.4 Combinatorial Networks
  - 2.3.5 Substituting Equivalent Subformulas
  - 2.3.6 Simplifying Negations
- 2.4 Exercises
- 2.5 Normal Forms
  - 2.5.1 Disjunctive Normal Form
  - 2.5.2 Application: DNF and Combinatorial Networks
  - 2.5.3 Conjunctive Normal Form
  - 2.5.4 Application: CNF and Combinatorial Networks
  - 2.5.5 Testing Satisfiability and Validity
  - 2.5.6 The Famous 'P Af r Conjecture
  - 2.5.7 Resolution Proofs: Automating Logic
- 2.6 Exercises
- 2.7 Predicates and Quantification
  - 2.71 Predicates
  - 2.72 Quantification
  - 2.73 Restricted Quantification
  - 2.74 Nested Quantifiers
  - 2.75 Negation and Quantification
  - 2.76 Quantification with Conjunction and Disjunction
  - 2.77 Application: Loop Invariant Assertions

2.8 Exercises

2.9 Chapter Review
- 2.9.1 Summary

CHAPTER

Relations

3.1 Binary Relations
- 3.1.1 n-ary Relations

3.2 Operations on Binary Relations x Contents

3.2.1 Inverses

3.2.2 Composition

3.3 Exercises

3.4 Special Types of Relations

3.4.1 Reflexive and Irreflexive Relations
- 3.4.2 Symmetric and Antisymmetric Relations

3.4.3 Transitive Relations

3.4.4 Reflexive, Symmetric, and Transitive Closures
- 3.4.5 Application: Transitive Closures in Medicine and Engineering

3.5 Exercises

3.6 Equivalence Relations
- 3.6.1 Partitions
- 3.6.2 Comparing Equivalence Relations

3.7 Exercises

3.8 Ordering Relations
- 3.8.1 Partial Orderings
- 3.8.2 Linear Orderings
- 3.8.3 Comparable Elements
- 3.8.4 Optimal Elements in Orderings
- 3.8.5 Application: Finding a Minimal Element
- 3.8.6 Application: Embedding a Partial Order

3.9 Exercises

3.10 Relational Databases: An Introduction
- 3.10.1 Storing Information in Relations
- 3.10.2 Relational Algebra
- 3.11 Exercises
  - 3.12.1 Summary

CHAPTER Contents xi

Functions

4.1 Basic Definitions
- 4.1.1 Functions as Rules
- 4.1.2 Functions as Sets
- 4.1.3 Recursively Defined Functions
- 4.1.4 Graphs of Functions
- 4.1.5 Equality of Functions
- 4.1.6 Restrictions of Functions
- 4.1.7 Partial Functions
- 4.1.8 1-1 and Onto Functions
- 4.1.9 Increasing and Decreasing Functions

4.2 Exercises

4.3 Operations on Functions
- 4.3.1 Composition of Functions
- 4.3.2 Inverses of Functions
- 4.3.3 Other Operations on Functions

4.4 Sequences and Subsequences

4.5 Exercises

4.6 The Pigeon-Hole Principle
- 4.6.1 k to 1 Functions
- 4.6.2 Proofs of the Pigeon-Hole Principle
- 4.6.3 Application: Decimal Expansion of Rational Numbers
- 4.6.4 Application: Problems with Divisors and Schedules
- 4.6.5 Application: Two Combinatorial Results

4.7 Exercises

4.8 Countable and Uncountable Sets
- 4.8.1 Countably Infinite Sets
- 4.8.2 Cantor's First Diagonal Argument
- 4.8.3 Uncountable Sets and Cantor's Second Diagonal Argument
- 4.8.4 Cardinalities of Power Sets

4.9 Exercises

4.10 Chapter Review xii Contents
- 4.10.1 Summary

CHAPTER

Analysis of Algorithms

5.1 Comparing Growth Rates of Functions
- 5.1.1 A Measure for Comparing Growth Rates
- 5.1.2 Properties of Asymptotic Domination
- 5.1.3 Polynomial Functions
  - 5.1.4 Exponential and Logarithmic Functions

5.2 Exercises
- 5.3 Complexity of Programs
  - 5.3.1 Counting Statements
  - 5.3.2 Two Algorithms Illustrating Selection
  - 5.3.3 An Algorithm Illustrating Repetition
  - 5.3.4 An Algorithm Illustrating Nested Repetition
  - 5.3.5 Time Complexity of an Algorithm
  - 5.3.6 Variants on the Definition of Complexity
- 5.4 Exercises
- 5.5 Uncomputability
  - 5.5.1 The Halting Problem
  - 5.6.1 Summary

CHAPTER Contents xiii

Graph Theory

6.1 Introduction to Graph Theory
- 6.1.1 Definitions
- 6.1.2 Subgraphs

6.2 The Handshaking Problem

6.3 Paths and Cycles
- 6.3.1 Hamiltonian Cycles

6.4 Graph Isomorphism

6.5 Representation of Graphs
- 6.5.1 Adjacency Matrix
- 6.5.2 Adjacency Lists

6.6 Exercises

6.7 Connected Graphs
- 6.71 The Relation CONN
- 6.7.2 Depth First Search
- 6.7.3 Complexity of Dfs
- 6.74 Breadth First Search
- 6.7.5 Finding Connected Components

6.8 The K6nigsberg Bridge Problem
- 6.8.1 Graph Tracing

6.9 Exercises

6.10 Trees
- 6.10.1 Definition of Trees
- 6.10.2 Characterization of Trees

6.11 Spanning Trees
- 6.11.1 Kruskal's Algorithm
- 6.11.2 Correctness of Kruskal's Algorithm
- 6.11.3 Kruskal's Algorithm for Weighted Graphs
- 6.11.4 Correctness of Kruskal's Weighted Graph Algorithm

6.12 Rooted Trees xiv Contents
- 6.12.1 Binary Trees
- 6.12.2 Binary Search Trees
  - 6.12.3 Tree Traversals
- 6.12.4 Application: Decision Trees
- 6.13 Exercises
- 6.14 Directed Graphs
  - 6.14.1 Basic Definitions
  - 6.14.2 Directed Trails, Paths, Circuits, and Cycles
  - 6.14.3 Directed Graph Isomorphism
- 6.15 Application: Scheduling a Meeting Facility
  - 6.15.1 WAITFOR Graphs
- 6.16 Finding a Cycle in a Directed Graph
  - 6.16.1 Directed Cycle Detection Algorithm
  - 6.16.2 Correctness of Directed Cycle Detection
- 6.17 Priority in Scheduling
  - 6.171 Algorithm for Topological Sort
  - 6.172 Correctness of Topological Sort Algorithm
- 6.18 Connectivity in Directed Graphs
  - 6.18.1 Strongly Connected Directed Graphs
  - 6.18.2 Application: Designing One-Way Street Grids
- 6.19 Eulerian Circuits in Directed Graphs
- 6.20 Exercises
  - 6.21.1 Summary

CHAPTER

Counting and Combinatorics

7.1 Traveling Salesperson's Problem

7.2 Counting Principles Contents xv
- 7.2.1 The Multiplication Principle
- 72.2 Addition Principle

7.3 Set Decomposition Principle
- 7.3.1 Counting the Complement
- 73.2 Using the Pigeon-Hole Principle
- 7.3.3 Application: UNIX Logon Passwords

7.4 Exercises

7.5 Permutations and Combinations
- 7.5.1 Permutations
- 7.5.2 Linear Arrangements
- 75.3 Circular Permutations
- 7.5.4 Combinations
- 7.5.5 Poker Hands
- 75.6 Counting the Complement
- 7.5.7 Decomposition into Subproblems

7.6 Constructing the kth Permutation

7.7 Exercises

7.8 Counting with Repeated Objects
- 7.8.1 Permutations with Repetitions
  - 78.2 Combinations with Repetitions

7.9 Combinatorial Identities
- 79.1 Binomial Coefficients
  - 79.2 Multinomials

7.10 Pascal's Triangle

7.11 Exercises

7.12 Chapter Review

712.1 Summary

7.12.2 Starting to Review

712.3 Review Questions

7.12.4 Using Discrete Mathematics in Computer Science

CHAPTER xvi Contents

Discrete Probability

8.1 Ideas of Chance in Computer Science
- 8.11 Introductory Examples
- 8.1.2 Basic Definitions
- 8.1.3 Frequency Interpretation of Probability
- 8.1.4 Introductory Example Reconsidered
- 8.1.5 The Combinatorics of Uniform Probability Density
- 8.1.6 Set Theory and the Probability of Events

8.2 Exercises

8.3 Cross Product Sample Spaces
- 8.3.1 A Multiplication Principle
- 8.3.2 The Cross Product of Sample Spaces
- 8.3.3 Bernoulli Trial Processes
- 8.3.4 Events of Cross Product Form
  - 8.3.5 Two Ways of Viewing Events
- 8.4 Exercises
- 8.5 Independent Events and Conditional Probability
  - 8.5.1 Independent Events
  - 8.5.2 Introduction to Conditional Probability
  - 8.5.3 Exploring Conditional Probability
  - 8.5.4 Using Bayes' Rule with the Theorem of Total Probability
- 8.6 Exercises
- 8.7 Discrete Random Variables
  - 8.7.1 Distributions of a Random Variable
  - 8.72 The Binomial Distribution
  - 8.73 The Hypergeometric Distribution
  - 8.74 Expectation of a Random Variable
  - 8.75 The Sum of Random Variables
- 8.8 Exercises
- 8.9 Variance, Standard Deviation, and the Law of Averages
  - 8.9.1 Variance and Standard Deviation
  - 8.9.2 Independent Random Variables

8.10 Exercises Contents xvii

8.11 Chapter Review
- 8.11.1 Summary

CHAPTER

Recurrence Relations

9.1 The Tower of Hanoi Problem
- 9.1.1 Recurrence Relation for the Tower of Hanoi Problem
- 9.1.2 Solving the Tower of Hanoi Recurrence

9.2 Solving First-Order Recurrence Relations
- 9.2.1 Solving First-Order Recurrences Using Back Substitution

9.3 Exercises

9.4 Fibonacci Recurrence Relation
- 9.4.1 Second Order-Recurrence Relations
- 9.4.2 Solving the Fibonacci Recurrence
- 9.4.3 Rules for Solving Second-Order Recurrence Relations

9.5 Exercises

9.6 Divide and Conquer Paradigm

9.7 Binary Search
- 9.71 Correctness
- 9.72 Complexity

9.8 Merge Sort
- 9.8.1 Correctness
- 9.8.2 Example
- 9.8.3 Complexity

9.9 Multiplication of n-Bit Numbers

9.10 Divide-and-Conquer Recurrence Relations
- 9.10.1 Complexity of Divide-and-Conquer Recurrence Relations

9.11 Exercises xviii Contents

9.12 Chapter Review
- 9.12.1 Summary

Appendix A APPENDIX

Appendix B

Index

Discrete Mathematics for Computer Science

Get our desktop app

Company

Features

Documentation

Resources